Adversarial bandit optimization for approximately linear functions
Not on the map. Why?
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.
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
7 of 24 references.
References · 7
- 2019Introduction to Online Convex Optimizationcited by 803
- 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
- 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
- 2020Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisationcited by 33
- 2018Learning in Non-convex Games with an Optimization Oraclecited by 24
- 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
- 2022Non-convex online learning via algorithmic equivalencecited by 11
Built on by
Citing papers per year: 2026: 2.
2 papers.