Research map / Bandits and online learning / Multi-armed bandits
Batch Ensemble for Variance Dependent Regret in Stochastic Bandits
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 Batch Ensemble, a tuning-free multi-armed bandit algorithm that takes the minimum of batch-averaged (slightly shrunk) empirical means as an optimistic index, and proves variance-dependent and instance-dependent regret bounds with synthetic experiments.
Problem
Stochastic multi-armed bandits require balancing exploration and exploitation, and existing optimistic methods typically hard-code distributional assumptions (e.g., bounded support, variance estimates, KL), which can be misspecified or need tuning.
Approach
Split each arm's samples into l batches, compute a shrunk empirical mean per batch (sum divided by batch size + 2), take the minimum across batches as an optimistic loss estimator, and play greedily; the analysis (not the algorithm) adapts to Bernoulli, symmetric, scaled, and lower-variance-bounded distributions, with a single parameter (number of batches).
Key results
- Regret bound of order sqrt(T * min(mu_star K, sum sigma_a^2)) log(6TK/delta) + 11K log^2(6TK/delta) with a fixed number of batches l = (7/2) log(2T/delta), with no dependence on arm scale or variance in the algorithm.
- On synthetic Bernoulli, Gaussian and exponential bandits, the Ensemble implementations are close to UCB-KL and significantly better than UCB, UCB-V and MARS in low-variance settings (e.g., 5 Bernoulli arms with means 0.001 to 0.3).
- Anytime expected regret with l_t = 8 log t achieves 17 sqrt(t min(mu_star K, sum sigma^2)) log(72t) + 84 K log^2(72t).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Ensemble methods instead of UCB, UCB-V, or MARS | Synthetic Bernoulli MAB with 5 arms and a clear, low-variance best arm · Bernoulli arms with means 0.001, 0.15, 0.2, 0.25, 0.3 | averaged pseudo-regret | Helped |
| Use Ensemble methods instead of UCB or MARS | Synthetic Bernoulli MAB with 10 high-mean arms · Bernoulli arms with means 0.9, 0.91, 0.92, …, 0.99 | averaged pseudo-regret | Helped |
| Use Ensemble methods instead of UCB-V or UCB | Synthetic Bernoulli MAB with randomly sampled means · Bernoulli arms with 10 random means | averaged pseudo-regret | Helped |
| Use Ensemble methods instead of UCB-KL | Synthetic Gaussian MAB with random means and variance 1 · Gaussian arms with 10 random means | averaged pseudo-regret | Helped |
| Use Ensemble methods instead of UCB-KL | Synthetic exponential MAB with random scales · Exponential arms with 10 random scales | averaged pseudo-regret | Helped |
| Use Ensemble methods instead of the remaining compared methods | Batch Ensemble · Synthetic benchmarks across Bernoulli, Gaussian, and exponential MAB environments | averaged pseudo-regret | Helped |
| Use EnsembleAdaptiveEfficient instead of EnsembleAdaptive (ablation) | Batch Ensemble · Synthetic MAB benchmarks | averaged pseudo-regret | Mixed |
Surprising findings
- Exponential-arm experiments (non-symmetric, without warmup) still show the ensemble outperforming UCB-KL, even though the theory does not guarantee this without a warmup phase.
Limitations
- Theoretical guarantees are proven for Bernoulli arms; extensions to other distributions rely on an unproven conjecture or a warmup phase for general (non-symmetric) distributions.
- Experiments are limited to synthetic environments with T=2000 and 100 simulations; the MDP extension is left to future work.
- Bounds depend on Bernstein-type variance rather than tight KL-based Chernoff bounds, so they are not fully tight.
Experimental setup
Benchmarks: synthetic Bernoulli MAB (5 and 10 arms) synthetic Gaussian MAB (10 arms) synthetic exponential MAB (10 arms)
Metrics: pseudo-regret averaged over 100 simulations
Baselines: UCB UCB-V UCB-KL MARS
Builds on: UCB UCB-V KL-UCB MARS Bootstrapped DQN
Closest papers by meaning
- Stochastic Rising Bandits (ICML 2022 · similarity 0.88)
- Regret Bounds for Batched Bandits (AAAI 2021 · similarity 0.88)
- On the Optimality of Batch Policy Optimization Algorithms (ICML 2021 · similarity 0.88)
- Ensemble sampling for linear bandits: small ensembles suffice (NeurIPS 2024 · similarity 0.88)
- Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback (ICML 2024 · similarity 0.86)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.86)
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.