# Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 15 references that are in the map.
- First posted on arXiv 1 Apr 2024.

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

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Efficient Automatic CASH via Rising Bandits](https://mlsanity.com/paper/2012.04371/) (2020)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)

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

- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)
- [Ads that Stick: Near-Optimal Ad Optimization through Psychological Behavior Models](https://mlsanity.com/paper/2509.20304/) (2025)
- [Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting](https://mlsanity.com/paper/2409.05980/) (2024)
- [Rising Multi-Armed Bandits with Known Horizons](https://mlsanity.com/paper/2602.10727/) (2026)
- [Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise](https://mlsanity.com/paper/2609.17595/) (2026)

## Abstract (arXiv)

We give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem has k arms, each of whose reward function is a concave and increasing function of the number of times that arm has been pulled so far. We show that for any randomized online algorithm, there exists an instance on which it must suffer at least an Omega(√k) approximation factor relative to the optimal reward. We then provide a randomized online algorithm that guarantees an O(√k) approximation factor, if it is told the maximum reward achievable by the optimal arm in advance. We then show how to remove this assumption at the cost of an extra O(log k) approximation factor, achieving an overall O(√k log k) approximation relative to optimal.