# Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners

arXiv: https://arxiv.org/abs/2006.07562 · HTML: https://mlsanity.com/paper/2006.07562/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2020.

## Built on by (most cited first, 6 of 6)

- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [Pure Exploration with Structured Preference Feedback](https://mlsanity.com/paper/2104.05294/) (2021)
- [Choosing Answers in varepsilon-Best-Answer Identification for Linear Bandits](https://mlsanity.com/paper/2206.04456/) (2022)

## Abstract (arXiv)

We study the problem of best arm identification in linearly parameterised multi-armed bandits. Given a set of feature vectors Xsubsetℝd, a confidence parameter δ and an unknown vector θ^*, the goal is to identify argmaxx∈XxTθ^*, 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 textitPhased 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.