# Comparator-adaptive Convex Bandits

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

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

- [Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits](https://mlsanity.com/paper/2202.06151/) (2022)
- [Improved Regret for Bandit Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2402.09152/) (2024)
- [Distributed Online Learning for Joint Regret with Communication Constraints](https://mlsanity.com/paper/2102.07521/) (2021)
- [Best of Both Worlds: Regret Minimization versus Minimax Play](https://mlsanity.com/paper/2502.11673/) (2025)
- [Parameter-Free Dynamic Regret for Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.25916/) (2026)
- [Decentralized Parameter-Free Online Learning](https://mlsanity.com/paper/2510.15644/) (2025)
- [State-free Reinforcement Learning](https://mlsanity.com/paper/2409.18439/) (2024)
- [Learning Safely Without Knowing the World:COMPASS-Hedge](https://mlsanity.com/paper/2603.22348/) (2026)
- [A Perturbation Approach to Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.28201/) (2026)
- [Decentralized Parameter-Free Online Learning with Compressed Gossip](https://mlsanity.com/paper/2605.27831/) (2026)
- [Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits](https://mlsanity.com/paper/2608.15996/) (2026)

## Abstract (arXiv)

We study bandit convex optimization methods that adapt to the norm of the comparator, a topic that has only been studied before for its full-information counterpart. Specifically, we develop convex bandit algorithms with regret bounds that are small whenever the norm of the comparator is small. We first use techniques from the full-information setting to develop comparator-adaptive algorithms for linear bandits. Then, we extend the ideas to convex bandits with Lipschitz or smooth loss functions, using a new single-point gradient estimator and carefully designed surrogate losses.