Metraipolis › archive › dc_3ca079e5126a
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise — arXiv:2609.17595
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.17595
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T15:04:21.250Z
- SHA-256 of the archived text
92d575a136ef189c61956f2805f6a1d6c921415c574fe63e1bc882a669e9b115- Stable URL of this page
https://metraipolis.com/documento/dc_3ca079e5126a
How to cite
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise — arXiv:2609.17595 — arXiv (en), https://arxiv.org/abs/2609.17595 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3ca079e5126a (Metraipolis archive dc_3ca079e5126a, sha256 92d575a136ef189c61956f2805f6a1d6c921415c574fe63e1bc882a669e9b115)
BibTeX
@misc{dc3ca079e5126a,
title = {Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise — arXiv:2609.17595},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.17595},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3ca079e5126a; sha256 92d575a136ef189c61956f2805f6a1d6c921415c574fe63e1bc882a669e9b115},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.17595. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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>4k$), against an $\Omega(\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, $\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 $\varepsilon\in(0,1/2]$, the uniform price of adaptation $\phi_\varepsilon(k)$ --- the worst case over horizons $T\ge16k$ of the loss relative to $k^{\beta/(1+\beta)}$ for algorithms knowing neither $m$ nor $\beta$ --- is $\Theta_\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 $\beta$ alone restores a constant price.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-17 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.17595 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T14:08:19.051Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).