Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
arXiv:2609.17595v1 Announce Type: new Abstract: In the improving multi-armed bandits problem, each of k arms has an unknown nondecreasing, discretely concave reward curve f_i, and pulling arm i for the t-th time yields f_i(t). For sufficiently long horizons, Blum and Ravichandran (ALT 2025) proved that randomized algorithms achieve an O(sqrt k) approximation to the best single arm when the scale m=f^*(T) of the optimal arm is known (Tge2k), and O(sqrt klog k) when it is not (T>4k), against an Omega(sqrt k) lower bound. The logarithmic factor is unnecessary: a one-page emph{probe-and-commit} algorithm achieves competitive ratio 4sqrt3,sqrt k for Tge2lfloorsqrt krfloor, without any knowledge of the scale, and we determine the optimal ratio for every horizon, Theta(sqrt k+k/T), also for unknown horizons. Without noise, emph{no prior is needed at all}: a random-marginal probing algorithm reading neither the scale m, nor the concavity-envelope exponent beta of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon T, achieves the optimal Theta(k^{beta/(1+beta)}+k/T) simultaneously for every beta and every horizon. Under the multiplicative noise model of Blum and Ravichandran, probe-and-commit keeps the same all-horizon order Theta(sqrt k+k/T) without knowing the noise level (and Theta(sqrt k) on the same range), but the price of priors jumps: for any fixed noise level varepsilonin(0,1/2], the uniform price of adaptation phi_varepsilon(k) --- the worst case over horizons Tge16k of the loss relative to k^{beta/(1+beta)} for algorithms knowing neither m nor beta --- is Theta_varepsilon(sqrt{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 beta alone restores a constant price.