Fooling Algorithms in Non-Stationary Bandits using Belief Inertia

Gal Mendelson, Ellad B. TadmorarXiv 2025 · DOI · arXiv

Abstract

We study the problem of worst case regret in piecewise stationary multi armed bandits. While the minimax theory for stationary bandits is well established, understanding analogous limits in time-varying settings is challenging. Existing lower bounds rely on what we refer to as infrequent sampling arguments, where long intervals without exploration allow adversarial reward changes that induce large regret. In this paper, we introduce a fundamentally different approach based on a belief inertia argument. Our analysis captures how an algorithm's empirical beliefs, encoded through historical reward averages, create momentum that resists new evidence after a change. We show how this inertia can be exploited to construct adversarial instances that mislead classical algorithms such as Explore Then Commit, epsilon greedy, and UCB, causing them to suffer regret that grows linearly with T and with a substantial constant factor, regardless of how their parameters are tuned, even with a single change point. We extend the analysis to algorithms that periodically restart to handle non stationarity and prove that, even then, the worst case regret remains linear in T. Our results indicate that utilizing belief inertia can be a powerful method for deriving sharp lower bounds in non stationary bandits.

Introduction

In the classic Multi-Armed Bandit (MAB) problem, an agent repeatedly chooses between different actions ("arms") to maximize cumulative reward, balancing the exploration of unknown arms with the exploitation of known good ones. Standard MAB theory assumes the environment is stationary—the reward probabilities for each arm never change.

However, real-world environments are often non-stationary. While we have strong theoretical lower bounds for stationary bandits, understanding the fundamental limits in time-varying settings is much harder. Previous lower bounds relied on "infrequent sampling" arguments—the idea that if an algorithm is exploiting well, it rarely checks suboptimal arms and misses when they suddenly become optimal. This paper argues that infrequent sampling is only a symptom of a deeper problem: belief inertia.

The Belief Inertia Argument

The authors introduce a fundamentally new theoretical approach called a belief inertia argument. Instead of just assuming an algorithm isn't looking at suboptimal arms, they analyze why: the algorithm has built up a massive statistical "belief" (encoded via empirical averages) that a specific arm is best.

The method works by letting the algorithm run long enough to confidently identify an optimal arm. Then, a single "breakpoint" is introduced where the reward distributions abruptly change. Because the algorithm has accumulated so much historical data, its empirical averages are heavily anchored. It takes a massive amount of new evidence to overturn this belief, creating a momentum that resists the new reality of the environment.

Vulnerability of Classical Algorithms

The authors mathematically prove that this inertia induces worst-case linear regret ($\Omega(T)$) in classical algorithms, even with a single change point:

  • Explore-Then-Commit (ETC): Once it commits, it is completely blind to changes, suffering regret of at least $(1 - 1/K)T$.
  • $ε$-greedy: Suffers regret of at least $T/8$ for any choice of exploration rate $ε$. Small $ε$ fails to detect changes, while large $ε$ wastes rewards on sub-optimal arms.
  • Upper Confidence Bound (UCB): UCB's robustness is undermined by shrinking confidence intervals. Heavy sampling of an initially optimal arm shrinks its confidence bonus to near zero. When the environment changes, the old arm's deeply anchored index traps the algorithm.
UCB Index evolution demonstrating belief inertia: after the breakpoint at t=191, the algorithm continues to select the sub-optimal arm (Arm A) because the optimal arm's (Arm B) index remains suppressed by historical data.

As illustrated in Figure 1, the UCB index for the initially optimal arm remains higher than the new optimal arm long after the breakpoint. The algorithm is effectively "fooled" by its own historical confidence, leading to the continued selection of a sub-optimal action and linear regret.

Key Results and Periodic Restarts

The paper establishes that these failures are not easily fixed by common heuristics. For instance, periodic restarts—a common strategy for handling non-stationarity—introduce their own costs. The authors prove that anticipating $d$ changes by restarting costs a $\sqrt{d}$ penalty in regret even if the environment never actually changes. If changes occur more frequently than the restart period, the worst-case regret remains linear.

Conclusion

This research highlights a fundamental trade-off in bandit algorithms: the same statistical confidence that enables efficient exploitation in stationary environments creates a dangerous inertia in non-stationary ones. Future work will extend this framework to analyze algorithms explicitly built for non-stationarity, such as Sliding-Window UCB or Discounted UCB, to determine how effectively they can overcome the anchoring effect of past data.

Summary updated

Abstract

We study the problem of worst case regret in piecewise stationary multi armed bandits. While the minimax theory for stationary bandits is well established, understanding analogous limits in time-varying settings is challenging. Existing lower bounds rely on what we refer to as infrequent sampling arguments, where long intervals without exploration allow adversarial reward changes that induce large regret. In this paper, we introduce a fundamentally different approach based on a belief inertia argument. Our analysis captures how an algorithm's empirical beliefs, encoded through historical reward averages, create momentum that resists new evidence after a change. We show how this inertia can be exploited to construct adversarial instances that mislead classical algorithms such as Explore Then Commit, epsilon greedy, and UCB, causing them to suffer regret that grows linearly with T and with a substantial constant factor, regardless of how their parameters are tuned, even with a single change point. We extend the analysis to algorithms that periodically restart to handle non stationarity and prove that, even then, the worst case regret remains linear in T. Our results indicate that utilizing belief inertia can be a powerful method for deriving sharp lower bounds in non stationary bandits.
BibTeX
@misc{mendelson2025fooling,
  author = {Gal Mendelson and Ellad B. Tadmor},
  title = {{Fooling Algorithms in Non-Stationary Bandits using Belief Inertia}},
  year = {2025},
  eprint = {2511.05620},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.05620},
  howpublished = {arXiv},
}
Figure