# Fully adaptive algorithm for pure exploration in linear bandits

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2017.

## Built on by (most cited first, 30 of 43)

- [Minimax Optimal Fixed-Budget Best Arm Identification in Linear Bandits](https://mlsanity.com/paper/2105.13017/) (2021)
- [Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2106.04763/) (2021)
- [Design of Experiments for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2107.09912/) (2021)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Safe Exploration for Efficient Policy Evaluation and Comparison](https://mlsanity.com/paper/2202.13234/) (2022)
- [Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2106.11612/) (2021)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Sample Efficient Demonstration Selection for In-Context Learning](https://mlsanity.com/paper/2506.08607/) (2025)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Top-m identification for linear bandits](https://mlsanity.com/paper/2103.10070/) (2021)
- [Agnostic Active Learning of Single Index Models with Linear Sample Complexity](https://mlsanity.com/paper/2405.09312/) (2024)
- [Meta-Learning for Simple Regret Minimization](https://mlsanity.com/paper/2202.12888/) (2022)
- [Additive Causal Bandits with Unknown Graph](https://mlsanity.com/paper/2306.07858/) (2023)
- [The Role of Contextual Information in Best Arm Identification](https://mlsanity.com/paper/2106.14077/) (2021)
- [Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffs](https://mlsanity.com/paper/2110.13876/) (2021)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)
- [Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learning](https://mlsanity.com/paper/2211.12004/) (2022)
- [Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination](https://mlsanity.com/paper/2111.07458/) (2021)
- [Multi-task Representation Learning for Pure Exploration in Linear Bandits](https://mlsanity.com/paper/2302.04441/) (2023)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Inference-Time Personalized Alignment with a Few User Preference Queries](https://mlsanity.com/paper/2511.02966/) (2025)
- [Experiment Planning with Function Approximation](https://mlsanity.com/paper/2401.05193/) (2024)
- [Near Instance Optimal Model Selection for Pure Exploration Linear Bandits](https://mlsanity.com/paper/2109.05131/) (2021)
- [Price of Safety in Linear Best Arm Identification](https://mlsanity.com/paper/2309.08709/) (2023)
- [SPRT-based Efficient Best Arm Identification in Stochastic Bandits](https://mlsanity.com/paper/2207.11158/) (2022)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [Best Arm Identification in Stochastic Bandits: Beyond β-optimality](https://mlsanity.com/paper/2301.03785/) (2023)
- [A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationarity](https://mlsanity.com/paper/2307.15154/) (2023)
- [Adaptive Experiment Design with Synthetic Controls](https://mlsanity.com/paper/2401.17205/) (2024)
- [Bandit Pareto Set Identification in a Multi-Output Linear Model](https://mlsanity.com/paper/2507.04255/) (2025)

## Abstract (arXiv)

We propose the first fully-adaptive algorithm for pure exploration in linear bandits---the task to find the arm with the largest expected reward, which depends on an unknown parameter linearly. While existing methods partially or entirely fix sequences of arm selections before observing rewards, our method adaptively changes the arm selection strategy based on past observations at each round. We show our sample complexity matches the achievable lower bound up to a constant factor in an extreme case. Furthermore, we evaluate the performance of the methods by simulations based on both synthetic setting and real-world data, in which our method shows vast improvement over existing methods.