Adversarial bandit optimization for approximately linear functions
Zhuoyu Cheng ✉, Kohei Hatano, Eiji Takimoto · 2025
Read Adversarial bandit optimization for approximately linear functions by Zhuoyu Cheng ✉, Kohei Hatano, Eiji Takimoto (2025) 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-2505-20734.txt.
Introduction
Zhuoyu Cheng and co-authors study a learning problem where a player must pick actions while losses shift in a hostile way. In their 2025 paper, each round's loss is a linear function plus a small extra term. That extra term is chosen after the player moves and can be any shape at all.
The authors prove bounds on regret, the gap between the player's losses and the best fixed choice in hindsight. They give both expected bounds and bounds that hold with high chance. Their result also sharpens a known high-chance bound for plain bandit linear optimization, the case with no added term. A matching lower bound on expected regret shows how far any method can go.
Catalog record
| CREATOR | Zhuoyu Cheng ✉, Kohei Hatano, Eiji Takimoto |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20734
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 for approximately linear functions Zhuoyu Cheng ✉, Kohei Hatano, Eiji Takimoto Abstract We consider a bandit optimization problem for non-convex and non-smooth functions, where in each trial the loss function is the sum of a linear function and a small but arbitrary perturbation chosen after observing the player’s choice. We give both expected and high probability regret bounds for the problem. Our result also implies an improved high-probability regret bound for the bandit linear optimization, a special case with no perturbation. We also give a lower bound on the expected regret. 1 Introduction Bandit optimization is a sequential game between a player and an adversary. The game is played over T rounds, where T is a positive natural number called the horizon. The game is specified by a pair (\mathcal{K},\mathcal{F}) , where \mathcal{K}\subseteq\mathbb{R}^{d} is a bounded closed convex set and \mathcal{F}\subseteq\{f:\mathcal{K}\to\mathbb{R}\} is a function class. In each round t\in[T] , the player first chooses an action x_{t}\in\mathcal{K} and the adversary chooses a loss function f_{t}\in\mathcal{F} , and then the player receives the value f_{t}(x_{t}) as the loss. Note that f_{t} itself is unknown to the player. In this paper, we assume the adversary is oblivious, i.e., the loss functions are specified before starting the game 1 1 1 We do not consider the case where the adversary is adaptive, i.e., it can choose the t -th loss function f_{t} depending on the previous actions x_{1},\dots,x_{t-1} . . The goal of the player is to minimize the regret \displaystyle\sum_{t=1}^{T}f_{t}(x_{t})-\min_{x\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(x) (1) in expectation (expected regret) or with high probability (high-probability regret). For convex loss functions, the bandit optimization has been extensively studied (see, e.g., [ 3 , 9 , 17 ] ). \mathcal{O}(d^{1/3}T^{3/4}) regret bounds are shown by Flaxman et al. [ 10 ] . Lattimore [ 16 ] shows an information-theoretic regret bound \widetilde{O}(d^{2.5}\sqrt{T}) for convex loss functions. For linear loss functions, Abernethy et al. [ 3 ] propose the SCRiBLe algorithm and give an expected regret bound \mathcal{O}(d\sqrt{T\ln T}) , achieving optimal dependence on T [ 8 ] . Lee et al. [ 17 ] propose SCRiBLe with lifting and increasing learning rates and show a high-probability regret bound \widetilde{O}(d^{2}\sqrt{T}) . Recently, non-convex functions are also getting popular in this literature. For example, Agarwal et al. [ 4 ] show a regret bound \mathcal{O}(poly(d)T^{2/3}) for smooth and bounded non-convex functions. Ghai et al. [ 12 ] propose algorithms with regret bounds \mathcal{O}(poly(d)T^{2/3}) under the assumption that non-convex functions are reparameterized as some convex functions. In this paper, we investigate the bandit optimization problem for a class of non-convex and non-smooth loss functions. The function class consists of non-smooth and non-convex functions that are "close" to linear functions, in the sense that functions in the class can be viewed as linear functions with adversarial non-convex perturbations whose amount is up to \epsilon . Bandit optimization for linear loss functions with stochastic noise (e.g., [ 1 , 5 ] ) cannot be applied to our problem. We propose a novel approach to analyzing high-probability regret, introducing a new method for decomposing regret. 1. When \epsilon\neq 0 , we propose a modification of SCRiBLe with lifting and increasing learning rates [ 17 ] and leverage the properties of the \nu -normal barrier [ 19 ] to prove its high probability regret bound \widetilde{O}(d\sqrt{T}+\sqrt{\epsilon}dT+\epsilon dT) . We also derive its expected regret \widetilde{O}(d\sqrt{T}+\sqrt{\epsilon}dT+\epsilon dT) . 2. When \epsilon=0 , this problem becomes bandit linear optimization, a special case with no perturbation. Compared to the result of [ 17 ] , holding with probability 1-\gamma , \mathcal{O}(\ln^{2}(dT)d^{2}\ln T\sqrt{T\ln\frac{\ln(dT)}{\gamma}}) , we use a different regret decomposition approach to achieve a better high-probability regret bound \mathcal{O}(d\sqrt{T\ln T}+\ln T\sqrt{T\ln(\frac{\ln T}{\gamma})}+\ln(\frac{\ln T}{\gamma})) . 3. We prove a lower bound \Omega(\epsilon T) , characterizing the minimal dependence on the parameter \epsilon . 2 Related Work Bandit linear optimization was first proposed by Awerbuch & Kleinberg [ 6 ] , who achieved a regret bound of \mathcal{O}(d^{3/5}T^{2/3}) against oblivious adversaries. Later, McMahan & Blum [ 18 ] established a regret bound of \mathcal{O}(dT^{3/4}) when facing adaptive adversaries. A foundational approach in bandit optimization problems involves gradient-based smoothing techniques. Flaxman et al. [ 10 ] proposed a method for constructing an unbiased estimator of the loss function’s gradient in the bandit setting. Abernethy et al. [ 3 ] introduced the SCRiBLe algorithm and achieved an expected regret bound of \mathcal{O}(d\sqrt{T\ln T}) against oblivious adversaries. Bartlett et al. [ 7 ] proposed a high-probability regret bound of \mathcal{O}(d^{2/3}\sqrt{T\ln dT}) under a special condition. Subsequently, Lee et al. [ 17 ] presented a high-probability regret bound \widetilde{O}(d^{2}\sqrt{T}) for both oblivious and adaptive adversaries. In recent work, Ito and Takemura [ 15 , 14 ] proposed a bandit linear algorithm that adapts to both stochastic and adversarial environments, achieving a regret bound of \mathcal{O}(d\sqrt{T\ln T}) in the adversarial setting. Rodemann et al. [ 21 ] established a connection between bandit problems and Bayesian black-box optimization, offering theoretical foundations for regret bounds across both domains. Unlike bandit convex optimization problems, which have been extensively explored and analyzed, bandit non-convex optimization problems introduce unique challenges due to the complexity of exploring and exploiting in a non-convex area. Gao et al. [ 11 ] considered both non-convex losses and non-stationary data and established a regret bound of O(\sqrt{T+poly(T)} . Yang et al. [ 22 ] achieved a regret bound of O(\sqrt{T\ln T}) for non-convex loss functions. However, they both require the loss functions to have smoothness properties, and our loss functions are neither convex nor smooth. 2.1 Comparison to Lee et al. [ 17 ] Our approach builds upon Lee et al.’s work. Below, we highlight the key differences between our method and Lee et al.’s in the context of the oblivious bandit setting: 1. Simplified Regret Analysis: While Lee et al.’s regret analysis adds unnecessary complexity in the oblivious bandit setting, our approach offers a simplified analysis with clearer and more interpretable results. 2. Reduced Dependence on d : Lee et al.’s analysis results in a regret bound with greater dependence on d , whereas our method derives a bound with significantly reduced dependence on d (This distinction is demonstrated in the introduction and further illustrated in the case where \epsilon=0 ). 3. Revised Generality of Problem Setting: Like the SCRiBLe algorithm [ 3 ] , our approach is more general, treating bandit linear optimization as a special case within a broader problem framework. 3 Preliminaries This section introduces some necessary notations and defines an \epsilon -approximately linear function. Then we give our problem setting. 3.1 Notation We abbreviate the 2 -norm \|\cdot\|_{2} as \|\cdot\| . For a twice differentiable convex function \mathcal{R}:\mathbb{R}^{d}\to\mathbb{R} and any x,h\in\mathbb{R}^{d} , let \|h\|_{x}=\|h\|_{\nabla^{2}\mathcal{R}(x)}=\sqrt{h^{\top}\nabla^{2}\mathcal{R}(x)h} , and \|h\|_{x}^{*}=\|h\|_{(\nabla^{2}\mathcal{R}(x))^{-1}}=\sqrt{h^{\top}(\nabla^{2}\mathcal{R}(x))^{-1}h} , respectively. For any v\in\mathbb{R}^{d} , let v^{\perp} be the space orthogonal to v . Let \mathbb{S}^{d}_{1}=\{x\mid\|x\|=1\} . The vector e_{i}\in\mathbb{R}^{d} is a standard basis vector with a value of 1 in the i -th position and 0 in all other positions. I is an identity matrix with dimensionality implied by context. 3.2 Problem Setting Let \mathcal{K}\subseteq\mathbb{R}^{d} be a bounded and closed ball of radius D centered at the zero vector. Furthermore, we assume that \mathcal{K} contains the unit ball. Otherwise, we