2020/06/13 by Mohammadi Zaki, Zaki, Mohammadi, Avinash Mohan +3 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2006.07562
openalex publication_date 2020/06/13 · openalex created_date 2020/06/19 · openalex updated_date 2026/07/28
We study the problem of best arm identification in linearly parameterised multi-armed bandits. Given a set of feature vectors X⊂ℝd, a confidence parameter δ and an unknown vector θ^*, the goal is to identify argmaxx\inXxTθ^*, with probability at least 1-δ, using noisy measurements of the form xTθ^*. For this fixed confidence (δ-PAC) setting, we propose an explicitly implementable and provably order-optimal sample-complexity algorithm to solve this problem. Previous approaches rely on access to minimax optimization oracles. The algorithm, which we call the Phased Elimination Linear Exploration Game (PELEG), maintains a high-probability confidence ellipsoid containing θ^* in each round and uses it to eliminate suboptimal arms in phases. PELEG achieves fast shrinkage of this confidence ellipsoid along the most confusing (i.e., close to, but not optimal) directions by interpreting the problem as a two player zero-sum game, and sequentially converging to its saddle point using low-regret learners to compute players' strategies in each round. We analyze the sample complexity of PELEG and show that it matches, up to order, an instance-dependent lower bound on sample complexity in the linear bandit setting. We also provide numerical results for the proposed algorithm consistent with its theoretical guarantees.