# Optimal Exploration is no harder than Thompson Sampling

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 60 references that are in the map.
- First posted on arXiv 9 Oct 2023.

## Builds on (most cited first, 30 of 33)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Non-Asymptotic Pure Exploration by Solving Games](https://mlsanity.com/paper/1906.10431/) (2019)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Policy Evaluation and Optimization with Continuous Treatments](https://mlsanity.com/paper/1802.06037/) (2018)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits](https://mlsanity.com/paper/1610.04491/) (2016)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Mirror Descent and the Information Ratio](https://mlsanity.com/paper/2009.12228/) (2020)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Top Two Algorithms Revisited](https://mlsanity.com/paper/2206.05979/) (2022)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits](https://mlsanity.com/paper/2011.11222/) (2020)
- [Efficient Contextual Bandits with Continuous Actions](https://mlsanity.com/paper/2006.06040/) (2020)
- [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [Best Arm Identification in Generalized Linear Bandits](https://mlsanity.com/paper/1905.08224/) (2019)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Seeker: Real-Time Interactive Search](https://mlsanity.com/paper/1905.13125/) (2019)
- [Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast](https://mlsanity.com/paper/2009.11338/) (2020)
- [On Elimination Strategies for Bandit Fixed-Confidence Identification](https://mlsanity.com/paper/2205.10936/) (2022)

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

- [Enhancing Preference-based Linear Bandits via Human Response Time](https://mlsanity.com/paper/2409.05798/) (2024)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Data Efficient Sample Selection for In-Context Learning](https://mlsanity.com/paper/2609.06670/) (2026)

## Abstract (arXiv)

Given a set of arms Zsubset ℝd and an unknown parameter vector θ_ast∈ℝd, the pure exploration linear bandit problem aims to return argmaxz∈ Z ztopθast, with high probability through noisy measurements of xtopθast with x∈ Xsubset ℝd. Existing (asymptotically) optimal methods require either a) potentially costly projections for each arm z∈ Z or b) explicitly maintaining a subset of Z under consideration at each time. This complexity is at odds with the popular and simple Thompson Sampling algorithm for regret minimization, which just requires access to a posterior sampling and argmax oracle, and does not need to enumerate Z at any point. Unfortunately, Thompson sampling is known to be sub-optimal for pure exploration. In this work, we pose a natural question: is there an algorithm that can explore optimally and only needs the same computational primitives as Thompson Sampling? We answer the question in the affirmative. We provide an algorithm that leverages only sampling and argmax oracles and achieves an exponential convergence rate, with the exponent being the optimal among all possible allocations asymptotically. In addition, we show that our algorithm can be easily implemented and performs as well empirically as existing asymptotically optimal methods.