# Adversarial bandit optimization for approximately linear functions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 24 references that are in the map.
- First posted on arXiv 27 May 2025.

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

- [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)
- [Non-convex online learning via algorithmic equivalence](https://mlsanity.com/paper/2205.15235/) (2022)

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

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

## Abstract (arXiv)

We consider a bandit optimization problem for nonconvex 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.