# Pure Exploration via Frank-Wolfe Self-Play

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 72 references that are in the map.
- First posted on arXiv 24 Sep 2025.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Optimization, Learning, and Games with Predictable Sequences](https://mlsanity.com/paper/1311.1869/) (2013)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [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)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [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)
- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [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)
- [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)
- [An Analysis of Quantile Temporal-Difference Learning](https://mlsanity.com/paper/2301.04462/) (2023)
- [Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games](https://mlsanity.com/paper/2002.09806/) (2020)
- [Faster Rates for Convex-Concave Games](https://mlsanity.com/paper/1805.06792/) (2018)
- [Structure Adaptive Algorithms for Stochastic Bandits](https://mlsanity.com/paper/2007.00969/) (2020)
- [Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities](https://mlsanity.com/paper/2204.09228/) (2022)
- [Frank-Wolfe Algorithms for Saddle Point Problems](https://mlsanity.com/paper/1610.07797/) (2016)
- [Gradient Ascent for Active Exploration in Bandit Problems](https://mlsanity.com/paper/1905.08165/) (2019)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Adaptive Algorithms for Relaxed Pareto Set Identification](https://mlsanity.com/paper/2307.00424/) (2023)
- [Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification](https://mlsanity.com/paper/2402.10592/) (2024)
- [Negative Stepsizes Make Gradient-Descent-Ascent Converge](https://mlsanity.com/paper/2505.01423/) (2025)
- [A Counter-Example to Karlin's Strong Conjecture for Fictitious Play](https://mlsanity.com/paper/1412.4840/) (2014)
- [Ranking and Selection with Covariates for Personalized Decision Making](https://mlsanity.com/paper/1710.02642/) (2017)
- [Dual-Directed Algorithm Design for Efficient Pure Exploration](https://mlsanity.com/paper/2310.19319/) (2023)
- [A Contextual Ranking and Selection Method for Personalized Medicine](https://mlsanity.com/paper/2206.12640/) (2022)

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

- [Annealed Entropic Allocation for Ranking and Selection](https://mlsanity.com/paper/2606.11347/) (2026)

## Abstract (arXiv)

We study pure exploration in structured stochastic multi-armed bandits, aiming to efficiently identify the correct hypothesis from a finite set of alternatives. For a broad class of tasks, asymptotic analyses reduce to a maximin optimization that admits a two-player zero-sum game interpretation between an experimenter and a skeptic: the experimenter allocates measurements to rule out alternatives while the skeptic proposes alternatives. We reformulate the game by allowing the skeptic to adopt a mixed strategy, yielding a concave-convex saddle-point problem. This viewpoint leads to Frank-Wolfe Self-Play (FWSP): a projection-free, regularization-free, tuning-free method whose one-hot updates on both sides match the bandit sampling paradigm. However, structural constraints introduce sharp pathologies that complicate algorithm design and analysis: our linear-bandit case study exhibits nonunique optima, optimal designs with zero mass on the best arm, bilinear objectives, and nonsmoothness at the boundary. We address these challenges via a differential-inclusion argument, proving convergence of the game value for best-arm identification in linear bandits. Our analysis proceeds through a continuous-time limit: a differential inclusion with a Lyapunov function that decays exponentially, implying a vanishing duality gap and convergence to the optimal value. Although Lyapunov analysis requires differentiability of the objective, which is not guaranteed on the boundary, we show that along continuous trajectories the algorithm steers away from pathological nonsmooth points and achieves uniform global convergence to the optimal game value. We then embed the discrete-time updates into a perturbed flow and show that the discrete game value also converges. Building on FWSP, we further propose a learning algorithm based on posterior sampling. Numerical experiments demonstrate a vanishing duality gap.