Research map / Bandits and online learning / Multi-armed bandits
Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit
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 GenTS-Explore, a Thompson-sampling-style pure exploration algorithm for real-valued combinatorial bandits whose action set can be exponentially large in the number of arms, with a new problem-dependent lower bound and matching upper bound up to constants.
Problem
Identifying the optimal action from a finite real-valued action set (possibly exponentially large in the number of arms d) using as few arm pulls as possible in a stochastic multi-armed bandit.
Approach
Generalizes TS-Explore to real-valued action sets by sampling Gaussian reward vectors around empirical means, using an offline linear-optimization oracle, and pulling arms chosen by a new R-CPE-MAB arm selection rule based on squared action differences weighted by pull counts; introduces G-gap and hardness measure H = sum_s 1/Delta_(s)^2 with a matching lower bound.
Key results
- On synthetic knapsack instances, the R-CPE-MAB arm selection strategy needed as little as 1/3 to 1/2 the rounds of the naive strategy in some cases.
- The upper bounds of GenTS-Explore match the lower bound H up to problem-dependent constants, and are tighter than the TS-Explore bound O(width * sum 1/Delta_s^2).
- On the production planning problem, the R-CPE-MAB arm selection strategy also required fewer rounds than the naive strategy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use R-CPE-MAB arm selection instead of naive arm selection | GenTS-Explore · Knapsack | rounds to termination: 1/3 to 1/2 | Helped |
| Use R-CPE-MAB arm selection instead of naive arm selection | GenTS-Explore · Production planning | rounds to termination | Helped |
Surprising findings
- The naive arm selection strategy from CPE-MAB can be substantially worse than the R-CPE-MAB strategy in real-valued settings, since uncertainty on arms with large action-difference coefficients is amplified.
Limitations
- Upper bound retains a log^2(|A|) factor, unlike RAGE/Peace which avoid the log|A| term in some regimes
- Requires an offline oracle for linear optimization and a finite output set
- Experiments are small synthetic instances
Experimental setup
Datasets: synthetic knapsack instances synthetic production planning instances
Benchmarks: knapsack problem (synthetic) production planning problem (synthetic)
Metrics: number of arm pulls normalized between arm selection strateg
Baselines: naive arm selection strategy (CPE-MAB)
Builds on: TS-Explore RAGE Peace algorithm transductive linear bandit
Closest papers by meaning
- Combinatorial Stochastic-Greedy Bandit (AAAI 2024 · similarity 0.89)
- The Batch Complexity of Bandit Pure Exploration (ICML 2025 · similarity 0.88)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
- Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.88)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.88)
- Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits (NeurIPS 2024 · similarity 0.87)
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.