Research map / Bandits and online learning / Multi-armed bandits
Forced Exploration in Bandit Problems
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 Forced Exploration (FE), a parameter-free bandit algorithm that alternates greedy selection with forced pulls scheduled by a non-decreasing sequence, with sliding-window and periodic-reset variants for piecewise-stationary settings, giving sub-Gaussian regret bounds.
Problem
Multi-armed bandits typically need reward-distribution parameters (e.g., sub-Gaussian variance, bounds, kurtosis) to run, which practitioners often lack, and this is worse in non-stationary settings.
Approach
Each round, an arm that has gone unpulled for at least f(r) steps is forced to be pulled; otherwise the greedy empirical-mean rule is used. The forcing sequence f(r) is non-decreasing, and it is periodically reset with a sliding window for non-stationary environments. The method needs no variance or bound information.
Key results
- Stationary regret bound for exponential forcing sequence is asymptotically O(me^{1/m}(log T)^2), which the authors say matches the lower-bound order but is not optimal.
- Remark gives a Gaussian regret bound of order sqrt(T) log T (up to K and log factors), and piecewise-stationary asymptotic bound O(sqrt(T B_T) log T) for constant B_T.
- In experiments, FE-Exp performs competitively with LB-SDA-LM and other non-parametric baselines on Gaussian and Bernoulli rewards; LB-SDA-LM is strongest on Bernoulli but weaker on Gaussian.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FE-EXP with exponential forced exploration | Forced Exploration (FE) · Stationary Gaussian and Bernoulli rewards | cumulative expected regret | Helped |
| Use LB-SDA-LM | Bandit algorithms · Stationary Bernoulli rewards | cumulative expected regret | Helped |
| Use LB-SDA-LM | Bandit algorithms · Stationary Gaussian rewards with unknown variance in (0,1) | cumulative expected regret | Hurt |
| Use constant or linear forced-exploration sequences (ablation) | FE · Stationary Gaussian and Bernoulli rewards | cumulative expected regret | No clear effect |
| Add a sliding window and periodic exploration-sequence reset (ablation) | FE-EXP · Piecewise-stationary Gaussian and Bernoulli rewards | cumulative expected regret | Helped |
| Use a constant rather than linear forced-exploration sequence (ablation) | SW-FE · Piecewise-stationary Gaussian and Bernoulli rewards | cumulative expected regret | Helped |
| Use SW-FE-EXP with exponential forced exploration (ablation) | SW-FE · Piecewise-stationary Gaussian and Bernoulli rewards | cumulative expected regret | Helped |
Surprising findings
- The authors note that a constant forcing sequence with f(r)=sqrt(T) in stationary settings cannot simply be reused in non-stationary settings, so they use sqrt(tau) instead.
- The authors state that for logarithmic-regret impossibility results on light-tailed distributions, their exponential-sequence upper bound cannot be optimal.
Limitations
- Theoretical upper bounds for the exponential sequence are asymptotic and not optimal.
- Lattimore (2017) baseline was implemented with an approximate alternative, which the authors say may cause high variance in results.
- Experiments use only 100 (stationary) or 10 (non-stationary) runs and only Gaussian and Bernoulli rewards.
Experimental setup
Datasets: synthetic Gaussian bandit instances synthetic Bernoulli bandit instances
Benchmarks: synthetic Gaussian bandits (K=10, T=100000) synthetic Bernoulli bandits (K=10, T=100000) piecewise-stationary Gaussian and Bernoulli bandits (K=5, B_T=5, T=100000)
Metrics: cumulative expected regret
Baselines: LB-SDA-LM Lattimore (2017) algorithm approximation SW-LB-SDA CUSUM M-UCB SW-TS
Builds on: UCB Thompson Sampling SW-UCB explore-then-commit epsilon-greedy
Closest papers by meaning
- Lenient Regret for Multi-Armed Bandits (AAAI 2021 · similarity 0.91)
- Recovering Bandits (NeurIPS 2019 · similarity 0.91)
- A Closer Look at the Worst-case Behavior of Multi-armed Bandit Algorithms (NeurIPS 2021 · similarity 0.91)
- Multi-Armed Bandits with Minimum Aggregated Revenue Constraints (ICLR 2026 · similarity 0.90)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.89)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.89)
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.