Metraipolis › archive › dc_b3657355ecf2
Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence — arXiv:2610.20997
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.20997
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:20:07.154Z
- SHA-256 of the archived text
06380f775625b18a56b37be09a5e5a27b6a7101613ce7d9fbd33981c780656e7- Stable URL of this page
https://metraipolis.com/documento/dc_b3657355ecf2
How to cite
Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence — arXiv:2610.20997 — arXiv (en), https://arxiv.org/abs/2610.20997 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b3657355ecf2 (Metraipolis archive dc_b3657355ecf2, sha256 06380f775625b18a56b37be09a5e5a27b6a7101613ce7d9fbd33981c780656e7)
BibTeX
@misc{dcb3657355ecf2,
title = {Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence — arXiv:2610.20997},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.20997},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b3657355ecf2; sha256 06380f775625b18a56b37be09a5e5a27b6a7101613ce7d9fbd33981c780656e7},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.20997. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study fixed-budget adaptive experimentation aimed at maximizing the probability of obtaining sufficient posterior evidence that a recommended design's mean performance exceeds a target. Unlike best-arm identification, this objective does not require finding the best design. For Gaussian bandits with a Gaussian prior, we propose \emph{Halve-Then-Greedy} (HTG), which combines a large initial balanced allocation, successive halving, and posterior-greedy sampling. We prove instance-dependent, finite-budget exponential bounds on posterior-failure probability that capture both separation from unfavorable arms and the presence of multiple favorable arms. On one-positive-arm families, we establish an asymptotic sample-complexity lower bound that HTG matches up to a logarithmic factor. We further analyze uniform sampling and sequential halving, revealing regimes where they require more samples than HTG by linear and logarithmic factors, respectively. Simulations illustrate HTG's sample-efficiency advantages and their dependence on instance structure.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.20997 — 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-16T08:48:02.670Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).