{"ID":22920037,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-19T11:38:38.408397438Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17595","arxiv_id":"2609.17595","title":"Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise","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 ($T\\ge2k$), and $O(\\sqrt k\\log k)$ when it is not ($T\u003e4k$), against an $Ω(\\sqrt k)$ lower bound. The logarithmic factor is unnecessary: a one-page \\emph{probe-and-commit} algorithm achieves competitive ratio $4\\sqrt3\\,\\sqrt k$ for $T\\ge2\\lfloor\\sqrt k\\rfloor$, without any knowledge of the scale, and we determine the optimal ratio for every horizon, $Θ(\\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 $β$ of Blum, Garicano, Ravichandran and Sharma (UAI 2026), nor the horizon $T$, achieves the optimal $Θ(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 $Θ(\\sqrt k+k/T)$ without knowing the noise level (and $Θ(\\sqrt k)$ on the same range), but the price of priors jumps: for any fixed noise level $\\varepsilon\\in(0,1/2]$, the uniform price of adaptation $φ_\\varepsilon(k)$ --- the worst case over horizons $T\\ge16k$ of the loss relative to $k^{β/(1+β)}$ for algorithms knowing neither $m$ nor $β$ --- is $Θ_\\varepsilon(\\sqrt{\\log k/\\log\\log 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.","short_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)$ approxim...","url_abs":"https://arxiv.org/abs/2609.17595","url_pdf":"https://arxiv.org/pdf/2609.17595v1","authors":"[\"Xuan Li\"]","published":"2026-09-12T11:38:57Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}