Optimal Best-Arm Identification in Bandits with Access to Offline Data

Autor:	Agrawal, Shubhada, Juneja, Sandeep, Shanmugam, Karthikeyan, Suggala, Arun Sai
Rok vydání:	2023
Předmět:	Computer Science - Machine Learning Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	Learning paradigms based purely on offline data as well as those based solely on sequential online learning have been well-studied in the literature. In this paper, we consider combining offline data with online learning, an area less studied but of obvious practical importance. We consider the stochastic $K$-armed bandit problem, where our goal is to identify the arm with the highest mean in the presence of relevant offline data, with confidence $1-\delta$. We conduct a lower bound analysis on policies that provide such $1-\delta$ probabilistic correctness guarantees. We develop algorithms that match the lower bound on sample complexity when $\delta$ is small. Our algorithms are computationally efficient with an average per-sample acquisition cost of $\tilde{O}(K)$, and rely on a careful characterization of the optimality conditions of the lower bound problem. Comment: 45 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2306.09048 Zobrazit plný text záznamu View this record from Arxiv