# Adversarial Bandit Optimization with Globally Bounded Perturbations to Linear Losses

arXiv: https://arxiv.org/abs/2603.26066 · HTML: https://mlsanity.com/paper/2603.26066/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 27 references that are in the map.
- First posted on arXiv 27 Mar 2026.

## Builds on (most cited first, 12 of 12)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation](https://mlsanity.com/paper/2006.00475/) (2020)
- [Learning in Non-convex Games with an Optimization Oracle](https://mlsanity.com/paper/1810.07362/) (2018)
- [Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds](https://mlsanity.com/paper/2302.12370/) (2023)
- [Online-to-PAC Conversions: Generalization Bounds via Regret Analysis](https://mlsanity.com/paper/2305.19674/) (2023)
- [Non-convex online learning via algorithmic equivalence](https://mlsanity.com/paper/2205.15235/) (2022)
- [Generalization bounds for mixing processes via delayed online-to-PAC conversions](https://mlsanity.com/paper/2406.12600/) (2024)
- [Generalization Bounds and Stopping Rules for Learning with Self-Selected Data](https://mlsanity.com/paper/2505.07367/) (2025)
- [Online-to-PAC generalization bounds under graph-mixing dependencies](https://mlsanity.com/paper/2410.08977/) (2024)
- [Adversarial bandit optimization for approximately linear functions](https://mlsanity.com/paper/2505.20734/) (2025)

## Built on by (most cited first, 1 of 1)

- [Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses](https://mlsanity.com/paper/2606.19891/) (2026)

## Abstract (arXiv)

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.