Pure Exploration with Infinite Answers
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910047716507648 |
|---|---|
| author | Poiani, Riccardo Bernasconi, Martino Celli, Andrea |
| author_facet | Poiani, Riccardo Bernasconi, Martino Celli, Andrea |
| contents | We study pure exploration problems in which the set of correct answers is possibly infinite. For example, such problems arise when regressing a continuous function on the means of the bandit or when learning Nash equilibria by querying noisy values of the payoff matrix. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_22473 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pure Exploration with Infinite Answers Poiani, Riccardo Bernasconi, Martino Celli, Andrea Machine Learning We study pure exploration problems in which the set of correct answers is possibly infinite. For example, such problems arise when regressing a continuous function on the means of the bandit or when learning Nash equilibria by querying noisy values of the payoff matrix. 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. |
| title | Pure Exploration with Infinite Answers |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.22473 |