Research map / Bandits and online learning / Multi-armed bandits
Instance-Optimal Pure Exploration for Linear Bandits on Continuous Arms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes PMCA, a tractable instance-dependent algorithm for ε-best arm identification with linear bandit feedback on continuous arm sets, using reparametrization of the sampling distribution via its covariance matrix and projected subgradient descent with a Frank-Wolfe approximate projection.
Problem
Pure exploration (ε-best arm identification) with linear bandit feedback on continuous arm sets under a Bayesian linear reward model; prior methods are instance-independent or intractable because the optimization is over an infinite-dimensional space of probability measures with a non-smooth objecti
Approach
Reparametrize sampling distributions by their covariance matrix V(π), optimize with projected subgradient descent over the convex set V(X), and handle projection and distribution reconstruction via a Frank-Wolfe method connected to the approximate Carathéodory problem, requiring only quadratic and fractional quadratic argmax oracles.
Key results
- Theorem 6.2 establishes asymptotic instance-dependent optimality: lim (1/t) log P_t(error) = -1/(2 tau*), matching the lower bound from Lemma 4.1.
- On synthetic X ⊂ R^2 instances (e.g. a,b=0.2,0.4 to 0.2,1.0), PMCA achieves lower log(p_t) than Uniform and MVR in most instances, though MVR is better in some (e.g. (0.0,1.6)).
- CPU time: PMCA about 1.5 s per run vs about 0.2 s for MVR (excluding evaluation) in the reported instance.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PMCA instead of Uniform sampling | Pure exploration on continuous linear-bandit arms · Synthetic continuous arms | posterior error upper bound | Helped |
| use PMCA instead of MVR | Pure exploration on continuous linear-bandit arms · Synthetic continuous arms | posterior error upper bound | Mixed |
Surprising findings
- MVR, an instance-independent method, outperforms the proposed method in some problem instances such as (a,b)=(0.0,1.6).
Limitations
- Optimality result is asymptotic; no finite-time analysis for the practical algorithm.
- Only the sampling rule is optimized; the recommendation rule is assumed given, with experiments and theory focusing on greedy recommendation.
- Analysis restricted to Bayesian linear reward model; generalization to Gaussian process reward is left open.
Experimental setup
Benchmarks: synthetic unit-circle arc arm sets in R^2
Metrics: upper bound on posterior misidentification probability p_t ( CPU time
Baselines: Uniform sampling MVR
Builds on: Track-and-Stop Lazy Track-and-Stop Salim et al. Wasserstein gradient flow Dinkelbach fractional programming Frank-Wolfe
Closest papers by meaning
- Gamification of Pure Exploration for Linear Bandits (ICML 2020 · similarity 0.91)
- Best Arm Identification in Generalized Linear Bandits via Hybrid Feedback (NeurIPS 2026 · similarity 0.90)
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits (NeurIPS 2024 · similarity 0.89)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.89)
- Breaking the $\log(1/\Delta_2)$ Barrier: Better Batched Best Arm Identification with Adaptive Grids (ICLR 2025 · similarity 0.88)
- New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem (AAAI 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.