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 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, no prior is needed at all: a random-marginal probing algorithm reading neither the scale m, nor the concavity-envelope exponent eta of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon T, achieves the optimal Theta(k^{eta/(1+eta)}+k/T) simultaneously for every eta 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 arepsilonin(0,1/2], the uniform price of adaptation phi_arepsilon(k) --- the worst case over horizons Tge16k of the loss relative to k^{eta/(1+eta)} for algorithms knowing neither m nor eta --- is Theta_arepsilon(sqrt{log k/loglog k}), the lower bound asymptotic in k at fixed positive arepsilon and matched by a nested random-permutation probing algorithm, whereas knowing either m or eta alone restores a constant price.

Source: arXiv cs.LG | 2026-09-17