Pure Exploration with Infinite Answers

Riccardo Poiani, Martino Bernasconi, Andrea Celli
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:2989-2997, 2026.

Abstract

We study pure exploration problems where the set of correct answers is possibly infinite, e.g., the regression of any continuous function of the means of the bandit. We derive an instance-dependent lower bound for these problems. By analyzing it, we discuss why existing methods (i.e., Sticky Track-and-Stop) for finite answer problems fail at being asymptotically optimal in this more general setting. Finally, we present a framework, Sticky-Sequence Track-and-Stop, which generalizes both Track-and-Stop and Sticky Track-and-Stop, and that enjoys asymptotic optimality. Due to its generality, our analysis also highlights special cases where existing methods enjoy optimality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-poiani26a, title = { Pure Exploration with Infinite Answers }, author = {Poiani, Riccardo and Bernasconi, Martino and Celli, Andrea}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {2989--2997}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/poiani26a/poiani26a.pdf}, url = {https://proceedings.mlr.press/v300/poiani26a.html}, abstract = { We study pure exploration problems where the set of correct answers is possibly infinite, e.g., the regression of any continuous function of the means of the bandit. We derive an instance-dependent lower bound for these problems. By analyzing it, we discuss why existing methods (i.e., Sticky Track-and-Stop) for finite answer problems fail at being asymptotically optimal in this more general setting. Finally, we present a framework, Sticky-Sequence Track-and-Stop, which generalizes both Track-and-Stop and Sticky Track-and-Stop, and that enjoys asymptotic optimality. Due to its generality, our analysis also highlights special cases where existing methods enjoy optimality. } }
Endnote
%0 Conference Paper %T Pure Exploration with Infinite Answers %A Riccardo Poiani %A Martino Bernasconi %A Andrea Celli %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-poiani26a %I PMLR %P 2989--2997 %U https://proceedings.mlr.press/v300/poiani26a.html %V 300 %X We study pure exploration problems where the set of correct answers is possibly infinite, e.g., the regression of any continuous function of the means of the bandit. We derive an instance-dependent lower bound for these problems. By analyzing it, we discuss why existing methods (i.e., Sticky Track-and-Stop) for finite answer problems fail at being asymptotically optimal in this more general setting. Finally, we present a framework, Sticky-Sequence Track-and-Stop, which generalizes both Track-and-Stop and Sticky Track-and-Stop, and that enjoys asymptotic optimality. Due to its generality, our analysis also highlights special cases where existing methods enjoy optimality.
APA
Poiani, R., Bernasconi, M. & Celli, A.. (2026). Pure Exploration with Infinite Answers . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:2989-2997 Available from https://proceedings.mlr.press/v300/poiani26a.html.

Related Material