Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

Zhuoyu Cheng; Kohei Hatano; Eiji Takimoto

cs.LGMar 27, 2026

Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

Authors: Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto

Organizations: Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan. · Department of Informatics, Kyushu University, Japan. · RIKEN AIP, Japan.

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.

Figures & tables

Figure 1: Average regret of algorithms for artificial data sets. The yellow line corresponds to the results of Algorithm 1 , the blue line corresponds to the SCRiBLe algorithm Abernethy et al. (2008)

Explore similar work

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoOnline Convex Optimization Bandit Convex Optimization
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
A Perturbation Approach to Unconstrained Linear Bandits
Mar 30, 2026Andrew Jacobsen, Dorian Baudry, Shinji Ito +1Adversarial Bandits Dynamic Regret Minimization
Università degli Studi di Milano · Politecnico di Milano · Inria, Univ. Grenoble Alpes, Grenoble INP, CNRS, LIG, 38000 Grenoble, France +1
Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets
Oct 13, 2026Chen-Yu WeiAdversarial Bandits Bandit Convex Optimization
University of Virginia

Jun 18, 2026J/K move · Enter open · S save

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

Zhuoyu Cheng, Kohei Hatano, Eiji Takimoto

Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan

Online Convex Optimization Bandit Convex Optimization Adversarial Perturbations Adversarial Bandits

Open paper AskPDF arXiv

We study adversarial bandit optimization in which the loss functions may be non-convex and non-smooth. In each round, the learner selects an action and observes only the loss incurred at that action. The loss consists of an underlying convex and

β

-smooth component and an adversarial perturbation that may be chosen after observing the learner's action. The perturbations are subject to a global budget controlling their cumulative magnitude over time. This framework extends the globally budgeted, post-action perturbation model from underlying linear losses to general convex and

β

-smooth losses. For this broader class, we establish expected regret guarantees that explicitly characterize the effect of the perturbation budget. To establish these guarantees, we modify a standard bandit optimization algorithm and develop an analysis that controls the additional regret caused by the perturbations. In the absence of perturbations, our results reduce to regret guarantees for the standard bandit convex optimization setting with

β

-smooth losses.

Abstract

Explore similar work

Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

A Perturbation Approach to Unconstrained Linear Bandits

Follow the Perturbed Leader for Linear Bandits: T\sqrt{T}T​ Regret over General Convex Sets

Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets