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

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.