Explore, Refine, then Commit: Nearly Optimal Multi-Group Mean Estimation with Active Learning

Shourya Pandey, Syamantak Kumar
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:5197-5243, 2026.

Abstract

We present nearly optimal algorithms for simultaneously estimating the means of multiple distributions given a fixed total sample budget while ensuring uniform confidence intervals for the distributions. Our algorithms are based on the well-known _explore-then-commit_ policy from the bandit literature along with an additional refinement phase between the exploration phase and the commit phase. Our algorithms achieve regret $\tilde{O}( (\log \sigma_{\min}^{-1})^{0.5} T^{-1.5})$ when the rewards are subgaussian and $\tilde{O}(\sigma_{\min}^{-1}T^{-1.5})$ regret when the rewards have bounded fourth moment, where $T$ is the horizon and $\sigma_{\min}^2$ is the minimum among the variances of the distributions of the $G$ arms. We also provide lower bounds on the regret that nearly match the upper bounds for a constant $G$ in both these cases. IImportantly, we show that the dependence on $\sigma_{\min}$ in both cases is necessary, resolving a long-standing open problem of [Carpentier et al]. We also study the setting where the distributions are hypercontractive. This distribution class includes the family of {Gaussian} distributions but also includes several families of heavy-tailed distributions. We propose an algorithm for hypercontractive reward distributions that achieves a $\tilde{O}(T^{-1.5})$ regret, independent of $\sigma_{\min}$, and show a nearly matching lower bound for Gaussians.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-pandey26a, title = {Explore, Refine, then Commit: Nearly Optimal Multi-Group Mean Estimation with Active Learning}, author = {Pandey, Shourya and Kumar, Syamantak}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {5197--5243}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/pandey26a/pandey26a.pdf}, url = {https://proceedings.mlr.press/v337/pandey26a.html}, abstract = {We present nearly optimal algorithms for simultaneously estimating the means of multiple distributions given a fixed total sample budget while ensuring uniform confidence intervals for the distributions. Our algorithms are based on the well-known _explore-then-commit_ policy from the bandit literature along with an additional refinement phase between the exploration phase and the commit phase. Our algorithms achieve regret $\tilde{O}( (\log \sigma_{\min}^{-1})^{0.5} T^{-1.5})$ when the rewards are subgaussian and $\tilde{O}(\sigma_{\min}^{-1}T^{-1.5})$ regret when the rewards have bounded fourth moment, where $T$ is the horizon and $\sigma_{\min}^2$ is the minimum among the variances of the distributions of the $G$ arms. We also provide lower bounds on the regret that nearly match the upper bounds for a constant $G$ in both these cases. IImportantly, we show that the dependence on $\sigma_{\min}$ in both cases is necessary, resolving a long-standing open problem of [Carpentier et al]. We also study the setting where the distributions are hypercontractive. This distribution class includes the family of {Gaussian} distributions but also includes several families of heavy-tailed distributions. We propose an algorithm for hypercontractive reward distributions that achieves a $\tilde{O}(T^{-1.5})$ regret, independent of $\sigma_{\min}$, and show a nearly matching lower bound for Gaussians.} }
Endnote
%0 Conference Paper %T Explore, Refine, then Commit: Nearly Optimal Multi-Group Mean Estimation with Active Learning %A Shourya Pandey %A Syamantak Kumar %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-pandey26a %I PMLR %P 5197--5243 %U https://proceedings.mlr.press/v337/pandey26a.html %V 337 %X We present nearly optimal algorithms for simultaneously estimating the means of multiple distributions given a fixed total sample budget while ensuring uniform confidence intervals for the distributions. Our algorithms are based on the well-known _explore-then-commit_ policy from the bandit literature along with an additional refinement phase between the exploration phase and the commit phase. Our algorithms achieve regret $\tilde{O}( (\log \sigma_{\min}^{-1})^{0.5} T^{-1.5})$ when the rewards are subgaussian and $\tilde{O}(\sigma_{\min}^{-1}T^{-1.5})$ regret when the rewards have bounded fourth moment, where $T$ is the horizon and $\sigma_{\min}^2$ is the minimum among the variances of the distributions of the $G$ arms. We also provide lower bounds on the regret that nearly match the upper bounds for a constant $G$ in both these cases. IImportantly, we show that the dependence on $\sigma_{\min}$ in both cases is necessary, resolving a long-standing open problem of [Carpentier et al]. We also study the setting where the distributions are hypercontractive. This distribution class includes the family of {Gaussian} distributions but also includes several families of heavy-tailed distributions. We propose an algorithm for hypercontractive reward distributions that achieves a $\tilde{O}(T^{-1.5})$ regret, independent of $\sigma_{\min}$, and show a nearly matching lower bound for Gaussians.
APA
Pandey, S. & Kumar, S.. (2026). Explore, Refine, then Commit: Nearly Optimal Multi-Group Mean Estimation with Active Learning. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:5197-5243 Available from https://proceedings.mlr.press/v337/pandey26a.html.

Related Material