mlsanityData to 7 Oct 2026

Fully adaptive algorithm for pure exploration in linear bandits

arXiv 1710.05552 ↗First posted 16 Oct 2017stat.MLcited by 43

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 12; 2022: 7; 2023: 9; 2024: 5; 2025: 6; 2026: 4.

43 papers.

Sort:

By area:

  1. 2021Minimax Optimal Fixed-Budget Best Arm Identification in Linear Banditscited by 32
  2. 2021Fixed-Budget Best-Arm Identification in Structured Banditscited by 22
  3. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  4. 2022Active Learning with Safety Constraintscited by 16
  5. 2022Safe Exploration for Efficient Policy Evaluation and Comparisoncited by 15
  6. 2021Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximationcited by 14
  7. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  8. 2025Sample Efficient Demonstration Selection for In-Context Learningcited by 12
  9. 2021Top-m identification for linear banditscited by 11
  10. 2021Dealing With Misspecification In Fixed-Confidence Linear Top-m Identificationcited by 11
  11. 2024Agnostic Active Learning of Single Index Models with Linear Sample Complexitycited by 11
  12. 2022Meta-Learning for Simple Regret Minimizationcited by 10
31 more
  1. 2023Additive Causal Bandits with Unknown Graphcited by 10
  2. 2021The Role of Contextual Information in Best Arm Identificationcited by 8
  3. 2021Breaking the Moments Condition Barrier: No-Regret Algorithm for Bandits with Super Heavy-Tailed Payoffscited by 8
  4. 2022On Elimination Strategies for Bandit Fixed-Confidence Identificationcited by 8
  5. 2021Mean-based Best Arm Identification in Stochastic Bandits under Reward Contaminationcited by 6
  6. 2022Contextual Bandits in a Survey Experiment on Charitable Giving: Within-Experiment Outcomes versus Policy Learningcited by 6
  7. 2023Multi-task Representation Learning for Pure Exploration in Linear Banditscited by 6
  8. 2023Pure Exploration in Asynchronous Federated Banditscited by 6
  9. 2024Experiment Planning with Function Approximationcited by 5
  10. 2021Near Instance Optimal Model Selection for Pure Exploration Linear Banditscited by 4
  11. 2023Price of Safety in Linear Best Arm Identificationcited by 4
  12. 2025Inference-Time Personalized Alignment with a Few User Preference Queriescited by 4
  13. 2022SPRT-based Efficient Best Arm Identification in Stochastic Banditscited by 3
  14. 2023Optimal Exploration is no harder than Thompson Samplingcited by 3
  15. 2023Best Arm Identification in Stochastic Bandits: Beyond β-optimalitycited by 2
  16. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  17. 2024Adaptive Experiment Design with Synthetic Controlscited by 2
  18. 2025Bandit Pareto Set Identification in a Multi-Output Linear Modelcited by 2
  19. 2021Pure Exploration with Structured Preference Feedbackcited by 1
  20. 2022Choosing Answers in varepsilon-Best-Answer Identification for Linear Banditscited by 1
  21. 2023Fixed-Budget Best-Arm Identification in Sparse Linear Banditscited by 1
  22. 2024Linear Submodular Maximization with Bandit Feedbackcited by 1
  23. 2025Experimental Design for Semiparametric Banditscited by 1
  24. 2023Estimating Optimal Policy Value in General Linear Contextual Banditscited by 0
  25. 2024Optimal Thresholding Linear Banditcited by 0
  26. 2025Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Banditscited by 0
  27. 2025Challenger-Based Combinatorial Bandits for Subcarrier Selection in OFDM Systemscited by 0
  28. 2026On The Complexity of Best-Arm Identification in Non-Stationary Linear Banditscited by 0
  29. 2026Nearly Optimal Best Arm Identification for Semiparametric Banditscited by 0
  30. 2026MESHA: Mechanism-Enforced Sequential Halving for Strategic Linear Banditscited by 0
  31. 2026Data Efficient Sample Selection for In-Context Learningcited by 0