# Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 8 references that are in the map.
- First posted on arXiv 12 Sep 2026.

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

- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits](https://mlsanity.com/paper/2208.09254/) (2022)
- [Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2404.01198/) (2024)
- [Algorithm Design and Stronger Guarantees for the Improving Multi-Armed Bandits Problem](https://mlsanity.com/paper/2511.10619/) (2025)

## Abstract (arXiv)

In the improving multi-armed bandits problem, each of k arms has an unknown nondecreasing, discretely concave reward curve fi, and pulling arm i for the t-th time yields fi(t). For sufficiently long horizons, Blum and Ravichandran (ALT 2025) proved that randomized algorithms achieve an O(√ k) approximation to the best single arm when the scale m=f^*(T) of the optimal arm is known (T≥2k), and O(√ klog k) when it is not (T>4k), against an Omega(√ k) lower bound. The logarithmic factor is unnecessary: a one-page probe-and-commit algorithm achieves competitive ratio 4√3,√ k for T≥2lfloor√ krfloor, without any knowledge of the scale, and we determine the optimal ratio for every horizon, Theta(√ k+k/T), also for unknown horizons. Without noise, no prior is needed at all: a random-marginal probing algorithm reading neither the scale m, nor the concavity-envelope exponent β of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon T, achieves the optimal Theta(kβ/(1+β)+k/T) simultaneously for every β and every horizon. Under the multiplicative noise model of Blum and Ravichandran, probe-and-commit keeps the same all-horizon order Theta(√ k+k/T) without knowing the noise level (and Theta(√ k) on the same range), but the price of priors jumps: for any fixed noise level varepsilon∈(0,1/2], the uniform price of adaptation φ_varepsilon(k) --- the worst case over horizons T≥16k of the loss relative to kβ/(1+β) for algorithms knowing neither m nor β --- is Theta_varepsilon(√log k/loglog k), the lower bound asymptotic in k at fixed positive varepsilon and matched by a nested random-permutation probing algorithm, whereas knowing either m or β alone restores a constant price.