Pure Exploration via Frank–Wolfe Self-Play
Xinyu Liu, Chao Qin, Wei You · 2025
Read Pure Exploration via Frank–Wolfe Self-Play by Xinyu Liu, Chao Qin, Wei You (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19901.txt.
Introduction
Pure exploration asks which arm, treatment, or hypothesis is best, using as few samples as possible. Xinyu Liu, Chao Qin, and Wei You recast that hunt as a game between an experimenter and a skeptic. The experimenter spends measurements to rule options out; the skeptic proposes the hardest alternative. Letting the skeptic mix strategies turns the game into a saddle-point problem.
Their method, Frank-Wolfe Self-Play, needs no projections, regularization, or tuning knobs. Single-arm updates on both sides match how bandit sampling actually works. A linear bandit case study exposes pathologies such as nonunique optima that break naive designs. Efficient exploration underlies clinical trials and A/B testing. A tuning-free method lowers the barrier to principled experiment design.
Catalog record
| CREATOR | Xinyu Liu, Chao Qin, Wei You |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 95 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-19901
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pure Exploration via Frank–Wolfe Self-Play Xinyu Liu, Chao Qin, Wei You Abstract 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 game-value convergence with a vanishing duality gap. 1 Introduction A central goal in modern data-driven science is to efficiently identify the correct hypothesis from a finite set of alternatives. Examples include identifying the best alternative (best-arm identification, BAI; Audibert et al. 2010 ); identifying all alternatives that exceed a given threshold (thresholding bandits; Lai and Liao 2012 ); and identifying all Pareto-optimal alternatives under multiple objectives (Pareto set identification; Kone et al. 2023 ). To the best of our knowledge, this line of work traces back to Chernoff 1959 . In recent years, multiple disciplines have witnessed a surge of interest in characterizing fundamental performance limits and developing algorithms that attain them ( Glynn and Juneja 2004 , Garivier and Kaufmann 2016 , Russo 2020 , Kasy and Sautmann 2021 , Qin and You 2025 ) . Interestingly, these asymptotic analyses often reduce to a maximin optimization that admits a two-player zero-sum game interpretation between an experimenter and a skeptic; the game’s equilibrium characterizes both the fundamental limits and the structure of optimal algorithms ( Qin and Russo 2024 ) . The experimenter aims to answer a question of interest about the true state of nature \bm{\theta}\in\mathbb{R}^{d} . To this end, the experimenter gathers convincing evidence by selecting \bm{p}\in\Delta_{K} that specifies the allocation of measurement effort across the K alternatives, where \Delta_{K}\subset\mathbb{R}^{K} denotes the probability simplex. The skeptic, in turn, chooses an alternative state \bm{\vartheta}\in\mathrm{Alt}(\bm{\theta}) , which represents an instance with a different correct answer, in an attempt to mislead the experimenter’s evidence collection. Given strategies (\bm{p},\bm{\vartheta}) , the experimenter’s payoff is \Gamma(\bm{p},\bm{\vartheta})\triangleq\sum_{i\in[K]}p_{i}\mathrm{KL}(P_{\bm{\theta},i}\|P_{\bm{\vartheta},i}), where P_{\bm{\theta},i} and P_{\bm{\vartheta},i} denote the observation laws of arm i under \bm{\theta} and \bm{\vartheta} , respectively, and \mathrm{KL}(\cdot\|\cdot) is the Kullback–Leibler divergence. The payoff measures the expected amount of discriminative information against the skeptic’s alternative \bm{\vartheta} weighted by the experimenter’s allocation \bm{p} . Because the interaction is zero-sum, the experimenter seeks to maximize and the skeptic to minimize this quantity, leading to the maximin formulation that underpins attainable performance limits for many pure-exploration problems: \displaystyle\max_{\bm{p}\in\Delta_{K}}\inf_{\bm{\vartheta}\in\mathrm{Alt}(\bm{\theta})}\Gamma(\bm{p},\bm{\vartheta}). As in Wang et al. 2021 , the skeptic’s decision space \mathrm{Alt}(\bm{\theta}) decomposes as the union of a finite set of \mathrm{Alt}_{x}(\bm{\theta}) , where each index x\in\mathcal{X}(\bm{\theta}) denotes a “confusing scenario” that could flip the correct answer. The set \mathrm{Alt}_{x}(\bm{\theta}) collects all instances in which that scenario occurs. The maximin problem is equivalent to \displaystyle\max_{\bm{p}\in\Delta_{K}}\min_{x\in\mathcal{X}}D(\bm{p},x),\quad\text{where}\quad D(\bm{p},x)\triangleq\inf_{\bm{\vartheta}\in\mathrm{Alt}_{x}(\bm{\theta})}\Gamma(\bm{p},\bm{\vartheta}), (1) where D(\bm{p},x) quantifies the discriminative information the experimenter can obtain against the most challenging alternative in \mathrm{Alt}_{x}(\bm{\theta}) . Although asymptotic in nature, this maximin formulation both motivates and guides the design of practical algorithms. For example, in best-arm identification, a confusing scenario arises when a suboptimal arm x\neq I^{*}(\bm{\theta}) appears superior to the true best arm I^{*}(\bm{\theta}) . The well-known (top-two) Thompson sampling allocates measurement effort so as to gather equal evidence to rule out each such scenario, thereby enabling it to quickly identify the best arm ( Russo 2020 ) . This corresponds to the structural requirement of the optimal allocation, known as the (discriminative) information-balance condition: in ( 1 ), D(\bm{p},x)=D(\bm{p},x^{\prime}) for all x,x^{\prime}\neq I^{*}(\bm{\theta}) ( Russo 2020 , Garivier and Kaufmann 2016 ) . Thus, the skeptic is agnostic among the scenarios, as each is equally hard. However, this information balance property can fail to hold for structured bandits (such as linear bandits), suggesting that a naive modification of Thompson sampling may be inadequate. In fact, adapting optimism-based bandit algorithms (such as Thompson sampling) to such problems can be fundamentally inefficient, as they inherently prioritize exploring high-performing arms over efficiently uncovering the most informative ones. For illustration, Section 2 presents a simple linear-bandit instance, where the optimal allocation assigns zero sampling to the highest-performing arm, even though the objective is to identify it. Thompson Sampling and its variants nonetheless allocate substantial effort to this arm, thereby incurring markedly suboptimal performance. This example highlights the cost of ignoring the problem’s information structure—an effect also observed in regret minimization; see Lattimore and Szepesvari 2017 . An optimization expert might ask: if the maximin formulation characterizes performance limits, why not treat it as a standard optimization problem and derive pure-exploration algorithms by solving it directly? A natural first approach is to view ( 1 ) as a maximization over \bm{p} alone—maximize \min_{x\in\mathcal{X}}D(\bm{p},x) with respect to \bm{p} —and apply the Frank–Wolfe algorithm. When the feasible set for the allocation vector is the simplex, the linear minimization oracle returns a vertex (a one-hot vector), which aligns naturally with the one-arm-at-a-time sampling paradigm of bandit algorithms. However, even for unstructured problems such as BAI, numerical evidence indicates that Frank–Wolfe fails to attain asymptotic optimality ( Ménard 2019 , Degenne et al. 2020a , Wang et al. 2021 ) . A key reason is nonsmoothness : each D(\bm{p},x) in ( 1 ) is concave, so the objective is concave but typically nondifferentiable in \bm{p} , violating the bounded-curvature assumption for classical Frank–Wolfe guarantees ( Jaggi 2013 ) . The nonsmoothness that breaks vanilla Frank–Wolfe comes from the skeptic’s exact best responses—given \bm{p} , the skeptic solves \min_{x\in\mathcal{X}}D(\bm{p},x) . But what if they move simultaneously? A natural question one may ask is whether the original maximin formulation in ( 1 ) admits a Nash equilibrium. Its existence is crucial: it anchors simultaneous-play algorithms and provides primal–dual optimality certificates. Interestingly, Qin and Russo 2024 show that even in the case of BAI, a strict minimax inequality holds. To guarantee the existence of a Nash equilibrium, we allow the skeptic to play a mixed strategy \bm{\mu}=(\mu_{x})_{x\in\mathcal{X}}\in\Delta_{|\mathcal{X}|} over scenarios x\in\mathcal{X} . Under a mixed-strategy pair (\bm{p},\bm{\mu}) , the payoff function becomes