Near Optimal Pure Exploration in Logistic Bandits

Document detail

ID

oai:arXiv.org:2410.20640

Topic

Statistics - Machine Learning Computer Science - Machine Learnin...

Author

Rivera, Eduardo Ochoa Tewari, Ambuj

Year

2024

listing date

2/12/2025

Keywords

pure exploration optimal

Metrics

Abstract

Bandit algorithms have garnered significant attention due to their practical applications in real-world scenarios.

However, beyond simple settings such as multi-arm or linear bandits, optimal algorithms remain scarce.

Notably, no optimal solution exists for pure exploration problems in the context of generalized linear model (GLM) bandits.

In this paper, we narrow this gap and develop the first track-and-stop algorithm for general pure exploration problems under the logistic bandit called logistic track-and-stop (Log-TS).

Log-TS is an efficient algorithm that asymptotically matches an approximation for the instance-specific lower bound of the expected sample complexity up to a logarithmic factor.

;Comment: 25 pages, 2 figures.

arXiv admin note: text overlap with arXiv:2006.16073 by other authors

Rivera, Eduardo Ochoa,Tewari, Ambuj, 2024, Near Optimal Pure Exploration in Logistic Bandits