Bridging Adversarial and Nonstationary Multi-armed Bandit
Not on the map. Why?
Abstract (arXiv)
In the multi-armed bandit framework, there are two formulations that are commonly employed to handle time-varying reward distributions: adversarial bandit and nonstationary bandit. Although their oracles, algorithms, and regret analysis differ significantly, we provide a unified formulation in this paper that smoothly bridges the two as special cases. The formulation uses an oracle that takes the best-fixed arm within time windows. Depending on the window size, it turns into the oracle in hindsight in the adversarial bandit and dynamic oracle in the nonstationary bandit. We provide algorithms that attain the optimal regret with the matching lower bound.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 14 of its 27 references that are in the map. First posted on arXiv 5 Jan 2022.
Builds on
14 of 27 references.
References · 14
- 2013Non-stationary Stochastic Optimizationcited by 173
- 2018Stochastic bandits robust to adversarial corruptionscited by 118
- 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
- 2018Learning to Optimize under Non-Stationaritycited by 85
- 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
- 2018What Doubling Tricks Can and Can't Do for Multi-Armed Banditscited by 69
- 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
- 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
- 2019A Survey on Practical Applications of Multi-Armed and Contextual Banditscited by 44
- 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 41
- 2020Prediction with Corrupted Expert Advicecited by 26
- 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 20
2 more
- 2020Learning Product Rankings Robust to Fake Userscited by 12
- 2020Regime Switching Banditscited by 9
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.