Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto · 2026

Read Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses by Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26066.txt.

Introduction

Cheng, Hatano, and Takimoto study adversarial bandit problems where losses are bent versions of linear ones. Each round, the learner picks an action and then sees a loss. The loss is a linear part plus a perturbation chosen by an adversary. A global budget caps the total size of all perturbations. The authors prove expected and high-probability regret bounds for this model. As a side result, they improve the classic bound for bandit linear optimization. They also prove a matching lower bound on expected regret.

Catalog record

CREATORZhuoyu Cheng, Kohei Hatano, Eiji Takimoto
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44414
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.26066

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto Abstract We study a class of adversarial bandit optimization problems in which the loss functions may be non-convex and non-smooth. In each round, the learner observes a loss that consists of an underlying linear component together with an additional perturbation applied after the learner selects an action. The perturbations are measured relative to the linear losses and are constrained by a global budget that bounds their cumulative magnitude over time. Under this model, we establish both expected and high-probability regret guarantees. As a special case of our analysis, we recover an improved high-probability regret bound for classical bandit linear optimization, which corresponds to the setting without perturbations. We further complement our upper bounds by proving a lower bound on the expected regret. keywords Bandit optimization, self-concordant barrier, high-probability regret bound, Globally bounded perturbations 1 Introduction Bandit optimization can be viewed as a sequential interaction between a learner and an adversary. The interaction unfolds over a finite horizon of T rounds. The problem is specified by a pair (\mathcal{K},\mathcal{F}) , where \mathcal{K}\subseteq\mathbb{R}^{d} denotes a bounded, closed, and convex action set, and \mathcal{F} is a class of loss functions mapping from \mathcal{K} to \mathbb{R} . At each round t\in[T] , the learner selects an action x_{t}\in\mathcal{K} . Subsequently, the adversary specifies a loss function f_{t}\in\mathcal{F} , and the learner observes only the scalar loss value f_{t}(x_{t}) . The loss function f_{t} itself is not revealed to the learner. Throughout this paper, we restrict attention to an oblivious adversary, meaning that the sequence of loss functions \{f_{t}\}_{t=1}^{T} is fixed prior to the start of the game. 1 1 1 We do not consider adaptive adversaries that may select f_{t} based on the learner’s past actions x_{1},\ldots,x_{t-1} . The performance of the learner is measured by the regret, defined as \displaystyle\sum_{t=1}^{T}f_{t}(x_{t})-\min_{x\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(x), (1) which can be studied either in expectation or with high probability. Bandit optimization with convex loss functions has been extensively investigated. Early work by 10 established regret bounds of order \mathcal{O}(d^{1/3}T^{3/4}) , while later results improved the dependence on the horizon, including the information-theoretic bound \widetilde{\mathcal{O}}(d^{2.5}\sqrt{T}) due to 16 . In the special case of linear losses, 2 introduced the SCRiBLe algorithm and obtained an expected regret bound of \mathcal{O}(d\sqrt{T\ln T}) , which is optimal in its dependence on T ( 8 ) . High-probability guarantees for bandit linear optimization were later established by 17 , who proposed a variant of SCRiBLe with lifting and increasing learning rates and derived a regret bound of \widetilde{\mathcal{O}}(d^{2}\sqrt{T}) . More recently, attention has also turned to bandit optimization with non-convex loss functions. For instance, 4 studied smooth and bounded non-convex losses and obtained regret bounds of order \mathcal{O}(\mathrm{poly}(d)T^{2/3}) . Related results under alternative structural assumptions were presented by 12 , where non-convex losses are assumed to admit a reparameterization into convex functions. In this work, we focus on a class of bandit optimization problems with non-convex and non-smooth loss functions that can be viewed as perturbations of linear functions. More precisely, each loss function can be decomposed into a linear term and an additive non-convex perturbation. The perturbations may be chosen adversarially and are constrained by a total budget over the horizon T . Specifically, the cumulative magnitude of the perturbations over the T rounds is bounded by a constant C . This model is fundamentally different from stochastic linear bandit settings (e.g., 1 ; 5 ), and standard techniques for handling stochastic noise are not directly applicable. We develop a new approach for analyzing high-probability regret in this setting, based on a novel decomposition of the regret. Our main contributions can be summarized as follows: 1. For C\neq 0 , we differ from the analysis of SCRiBLe with lifting and increasing learning rates ( 17 ) . Instead, we work within a more general SCRiBLe framework ( 2 ) and derive both expected and high-probability regret bounds of \widetilde{\mathcal{O}}\!\left(d\sqrt{T}+d\sqrt{TC}+dC\right). 2. For C=0 , the problem reduces to classical bandit linear optimization. We obtain an improved high-probability regret bound compared to prior work ( 17 ) . In particular, for confidence level 1-\gamma , our bound is \mathcal{O}\!\left(d\sqrt{T\ln T}+\ln T\sqrt{T\ln\!\left(\tfrac{\ln T}{\gamma}\right)}+\ln\!\left(\tfrac{\ln T}{\gamma}\right)\right). 3. Finally, we establish a lower bound of order \Omega(C) on the expected regret, demonstrating that the dependence on the perturbation budget C in our upper bounds is unavoidable. 1.1 Relation to the previous version This manuscript is a revised and extended version of a previous conference publication ( 9 ) . Compared to that version, the current paper extends the setting in several important ways. In the earlier work, the perturbation in each round was bounded by a constant \epsilon ; here, we consider a more general setting where the sum of the absolute values of perturbations across T rounds is bounded by a constant C , allowing for particularly large perturbations in some rounds. Furthermore, we no longer rely on the more complex SCRiBLe with lifting algorithm ( 9 ) , and instead employ the standard SCRiBLe algorithm ( 3 ) . This allows us to analyze regret directly in the original dimension d , without lifting the problem to d+1 dimensions. In addition, the previous Assumption 1 in 9 is no longer required, as it imposed severe restrictions on the practical applicability of the analysis. Consequently, our formulation and results are more general and practically feasible. Finally, we develop a new analytical approach to derive regret bounds, redesign the experiments. 2 Related Work Bandit linear optimization was originally introduced by 6 , who studied the problem under oblivious adversaries and derived a regret bound of \mathcal{O}(d^{3/5}T^{2/3}) . Subsequently, 18 extended the analysis to adaptive adversaries and established a regret bound of \mathcal{O}(dT^{3/4}) . A major research direction in bandit optimization focuses on gradient estimation obtained through smoothing-based methods. In particular, 10 proposed a seminal approach for constructing unbiased gradient estimators from bandit feedback. Building on this framework, 2 introduced the SCRiBLe algorithm and proved an expected regret bound of \mathcal{O}(d\sqrt{T\ln T}) against oblivious adversaries. Later, 7 obtained a high-probability regret bound of \mathcal{O}(d^{2/3}\sqrt{T\ln(dT)}) under additional structural assumptions. More recently, 17 developed a refined variant of SCRiBLe and derived a high-probability regret bound of \widetilde{O}(d^{2}\sqrt{T}) that applies to both oblivious and adaptive adversaries. Beyond these classical results, 15 ; 14 proposed bandit linear algorithms capable of adapting between stochastic and adversarial regimes, achieving \mathcal{O}(d\sqrt{T\ln T}) regret in adversarial environments. Additionally, 21 explored a conceptual connection between bandit optimization and Bayesian black-box optimization, providing a unified perspective on regret guarantees across the two settings. Unlike bandit convex optimization, which has been extensively studied, bandit optimization with non-convex loss functions presents additional challenges due to the difficulty of balancing exploration and exploitation in non-convex domains. 11 investigated non-convex losses in conjunction with non-stationary data and obtained a regret bound of O(\sqrt{T+poly(T)}) . Similarly, 22 established an O(\sqrt{T\ln T}) regret bound for non-convex losses. However, both works rely on smoothness assumptions, whereas the loss functions considered in our setting are neither convex nor smooth. 2.1 Comparison to SCRiBLe-Based Methods The original SCRiBLe algorithm ( 3 ) does not provide high-probability regret guarantees. To address this limitation, 17 introduced

Read the complete text