# Bandits with adversarial scaling

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Mar 2020.

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

- [Learning from an Exploring Demonstrator: Optimal Reward Estimation for Bandits](https://mlsanity.com/paper/2106.14866/) (2021)
- [Hybrid Parameter Search and Dynamic Model Selection for Mixed-Variable Bayesian Optimization](https://mlsanity.com/paper/2206.01409/) (2022)
- [Preferences Evolve And So Should Your Bandits: Bandits with Evolving States for Online Platforms](https://mlsanity.com/paper/2307.11655/) (2023)
- [SLOPT: Bandit Optimization Framework for Mutation-Based Fuzzing](https://mlsanity.com/paper/2211.03285/) (2022)
- [Online Resource Allocation: Bandits feedback and Advice on Time-varying Demands](https://mlsanity.com/paper/2302.04182/) (2023)

## Abstract (arXiv)

We study "adversarial scaling", a multi-armed bandit model where rewards have a stochastic and an adversarial component. Our model captures display advertising where the "click-through-rate" can be decomposed to a (fixed across time) arm-quality component and a non-stochastic user-relevance component (fixed across arms). Despite the relative stochasticity of our model, we demonstrate two settings where most bandit algorithms suffer. On the positive side, we show that two algorithms, one from the action elimination and one from the mirror descent family are adaptive enough to be robust to adversarial scaling. Our results shed light on the robustness of adaptive parameter selection in stochastic bandits, which may be of independent interest.