Forced Exploration in Bandit Problems

Qi Han, Li Zhu, Fei GuoAAAI 2024 · OpenReview

TL;DR

Researchers have developed a "plug-and-play" multi-armed bandit algorithm that achieves near-optimal performance without needing prior knowledge of reward distributions (like variance or bounds). By alternating between a simple greedy rule and a "forced exploration" schedule, the algorithm effectively handles both stable environments and tricky non-stationary scenarios where reward patterns shift over time.

What Problem Does This Paper Address?

The Multi-Armed Bandit (MAB) problem is a cornerstone of reinforcement learning, modeling the trade-off between exploration (trying new things) and exploitation (sticking with what works). Most classic algorithms, like Upper Confidence Bound (UCB) or Thompson Sampling, come with a catch: they require "prior knowledge." To calculate a confidence interval, you usually need to know if the rewards are bounded (e.g., between 0 and 1) or know the specific variance of the distribution.

In the real world—think clinical trials or shifting user preferences in recommendation systems—we rarely have this information. Furthermore, many environments are non-stationary, meaning the "best" choice today might be the "worst" tomorrow. Existing non-parametric methods often struggle with unbounded rewards (like Gaussian distributions with unknown variance) or require complex tuning. This paper seeks a simple, robust algorithm that works across different reward types without needing a manual for every new distribution.

Methods

The authors introduce the Forced Exploration (FE) algorithm. Its logic is refreshingly simple:

  1. The Greedy Rule: Most of the time, the algorithm pulls the arm with the highest estimated mean reward.
  2. Forced Exploration: The algorithm maintains a counter for how many times each arm has not been pulled. It takes a non-decreasing sequence $\{f(r)\}$ as input. If an arm hasn't been pulled for a certain number of rounds defined by this sequence, the algorithm "forces" a pull of that arm, regardless of its current performance.

The "knob" for this algorithm is the sequence $f(r)$. The authors analyze three types:

  • Constant: $f(r) = \sqrt{T}$
  • Linear: $f(r) = r$
  • Exponential: $f(r) = a^r$ (This is the most powerful, leading to logarithmic regret).

For changing environments, they propose SW-FE (Sliding Window Forced Exploration). This version only looks at recent data (a sliding window) and periodically resets the forced exploration counter. This reset is crucial; it ensures that even if an arm looked bad a thousand rounds ago, the algorithm will eventually re-test it to see if the environment has shifted in its favor.

Datasets

As is standard for theoretical MAB research, the authors evaluated their approach using synthetic simulations rather than static datasets:

  • Stationary Settings: Gaussian rewards (with randomly generated means and variances) and Bernoulli rewards.
  • Non-stationary Settings: Piecewise-stationary environments where reward distributions for 5 arms were regenerated at 5 distinct "breakpoints" throughout 100,000 rounds.

Key Insights and Ideas

  • Decoupling Distribution from Exploration: By using a deterministic "forced" schedule instead of a distribution-dependent confidence bound, the algorithm becomes agnostic to the underlying math of the rewards. It doesn't matter if the reward is a 0/1 coin flip or a bell curve; the exploration schedule remains the same.
  • The Power of the Exponential Sequence: The authors show that an exponential exploration sequence ($f(r) = a^r$) allows the algorithm to achieve $O(\log^2 T)$ regret. This matches the order of lower bounds for stationary bandits, proving that "forced" exploration can be just as efficient as more complex, distribution-aware methods.
  • The Reset Trick: In non-stationary settings, simply using a sliding window isn't enough. If the exploration sequence $f(r)$ grows to infinity, the algorithm eventually stops exploring. By resetting the sequence periodically, SW-FE maintains a "perpetual curiosity" that is essential for detecting changes in the environment.

Key Results

  • Competitive Performance: In stationary Gaussian tests, the FE-Exp (exponential) variant outperformed several established non-parametric algorithms (like LB-SDA) and performed similarly to UCB, despite UCB having the advantage of knowing the distribution parameters.
  • Robustness in Flux: In non-stationary environments (piecewise-stationary), the SW-FE-Exp algorithm achieved a regret bound of $O(\sqrt{T B_T} \log T)$, where $B_T$ is the number of changes.
  • Empirical Edge: In Bernoulli trials, while specialized algorithms like LB-SDA-LM (designed specifically for exponential families) performed best, the FE variants were close behind, demonstrating that the "one-size-fits-all" approach doesn't sacrifice much efficiency for its added flexibility.

Limitations and Future Work

  • Hyperparameter Sensitivity: While the algorithm doesn't need reward distribution info, it still requires choosing a sequence $f(r)$ and, in non-stationary cases, a window size $\tau$. The authors suggest $\tau = \sqrt{T \log T / B_T}$, but in practice, the number of breakpoints $B_T$ is often unknown.
  • Asymptotic Optimality: The regret bounds provided are asymptotic. While they match the order of optimal bounds, there is still a small gap in the constant factors compared to algorithms that have full access to distribution information.
  • Future Directions: The authors suggest exploring how to adaptively tune the window size $\tau$ and the exploration sequence $f(r)$ without any prior knowledge of the time horizon $T$ or the number of changes $B_T$.

Summary updated

Abstract

The multi-armed bandit(MAB) is a classical sequential decision problem. Most work requires assumptions about the reward distribution (e.g., bounded), while practitioners may have difficulty obtaining information about these distributions to design models for their problems, especially in non-stationary MAB problems. This paper aims to design a multi-armed bandit algorithm that can be implemented without using information about the reward distribution while still achieving substantial regret upper bounds. To this end, we propose a novel algorithm alternating between greedy rule and forced exploration. Our method can be applied to Gaussian, Bernoulli and other subgaussian distributions, and its implementation does not require additional information. We employ a unified analysis method for different forced exploration strategies and provide problem-dependent regret upper bounds for stationary and piecewise-stationary settings. Furthermore, we compare our algorithm with popular bandit algorithms on different reward distributions.
BibTeX
@inproceedings{han2024forced,
  author = {Qi Han and Li Zhu and Fei Guo},
  title = {{Forced Exploration in Bandit Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=VIcUnPxGJE},
}
Figure