Multi-Armed Bandits with Time-Varying and State-Dependent Rewards

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2496 papers603 conceptsfrozen 2026-10-04

In the classic multi-armed bandit (MAB) problem, a decision-maker faces a row of slot machines, each with a fixed but unknown probability of payout. The goal is to maximize total reward by balancing "exploration" (trying different arms to learn their means) and "exploitation" (pulling the arm currently believed to be the best).

However, this "stationary" assumption—that the rules of the game never change—is a luxury rarely found in the real world. In news recommendation, a trending topic today is "rotting" tomorrow. In crowdsourcing, a worker’s performance might "rise" as they gain skill or drop as they succumb to fatigue. In these scenarios, the past is a diminishingly reliable guide to the future.

The Problem with Memory

Standard algorithms like Upper Confidence Bound (UCB) or Thompson Sampling work by averaging all historical observations. In a stationary world, more data always leads to better estimates. But in a non-stationary environment, old data becomes "stale." If an arm’s reward distribution shifts, a long history of high rewards will blind the algorithm to a recent collapse in performance.

To solve this, researchers have developed frameworks that allow agents to "forget" or adapt.

Abrupt Shifts and the Reset Button

One common framing is the piecewise-stationary bandit. Here, the environment remains stable for a period and then undergoes a sudden, discrete change. Yang Cao and colleagues introduced Monitored-UCB (M-UCB), which essentially equips the standard UCB algorithm with a "reset button" Nearly Optimal Adaptive Procedure for Piecewise-Stationary Bandit: a Change-Point Detection Approach.

The intuition is simple: the agent continuously monitors the incoming rewards for statistical anomalies. If the rewards for an arm suddenly deviate significantly from their historical average, the algorithm detects a "change-point," wipes its memory of that arm, and starts exploring it as if it were brand new. Fang Liu and Ness Shroff have similarly explored these change-detection frameworks to bridge the gap between static and adversarial environments A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problem.

Rested vs. Restless Dynamics

A more complex form of non-stationarity occurs when the rewards change based on the agent's own actions. This is often categorized into two settings:

  1. Rested Bandits: The state of an arm only evolves when you pull it. Think of training a machine learning model. As Leonardo Cella and Claudio Gentile describe, a model's performance (the "arm") only improves while it is being actively trained Best Model Identification: A Rested Bandit Formulation. When you stop training it, its progress freezes.
  2. Restless Bandits: The state of an arm evolves regardless of whether you pull it. This is common in seasonality or market trends. Pierre Laforgue and Nicolò Cesa-Bianchi introduced Last Switch Dependent (LSD) Bandits to model behaviors like boredom, where the utility of an action depends on the time elapsed since it was last chosen Break your Bandit Routine with LSD Rewards.

Rising, Rotting, and Recovering

The "shape" of the change often dictates the strategy.

  • Rising Bandits: In scenarios like Automated Machine Learning (AutoML), rewards typically increase over time as models converge. Alberto Maria Metelli notes that in "Rising" settings, an arm that looks bad now might be the optimal choice later if given enough investment Stochastic Rising Bandits.
  • Recovering Bandits: Sometimes an arm needs to "recharge." Ciara Pike-Burke and Steffen Grünewälder model this using Gaussian Processes to learn "recovery functions" Recovering Bandits. If you pull an arm too frequently, its reward drops (satiation); if you let it rest, its reward gradually bounces back.
  • Rotting Bandits: Conversely, some rewards strictly decrease with use, such as a worker becoming fatigued or a marketing campaign losing its novelty. Gianmarco Genalti and colleagues have unified these concepts into Graph-Triggered Bandits, where pulling one arm can even cause the rewards of other connected arms to rise or rot Bridging Rested and Restless Bandits with Graph-Triggering.

Why It Works: The Trade-off of Time

The fundamental intuition across these papers is that time is a context. In a stationary bandit, the only relevant information is the arm's identity. In a non-stationary bandit, the relevant information is the arm's identity plus some temporal state (e.g., "How long has it been since I pulled this?" or "How many times have I pulled this in total?").

By modeling these temporal dependencies—whether through change-point detection, sliding windows, or explicit recovery functions—algorithms can move from simply reacting to the past to strategically planning for a shifting future. As Nicolas Nguyen and Claire Vernade demonstrate with their work on Lipschitz bandits, the goal is to achieve "minimax-optimal" performance, ensuring the agent learns as fast as the environment changes Non-Stationary Lipschitz Bandits.

Papers in this version

Showing 60 of 496 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 424 papers
  2. Version 1 · 2026-10-04 · 496 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_stationary_reward_distributions_92e66b43,
  title = {non-stationary reward distributions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-stationary-reward-distributions/rdr_92e66b43b4114fa1bd3626784cf01b5f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_armed_bandits_with_time_varying_an_92e66b43_v1,
  title = {Multi-Armed Bandits with Time-Varying and State-Dependent Rewards},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-armed-bandits-with-time-varying-and-state-dependent-rewards/rdr_92e66b43b4114fa1bd3626784cf01b5f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}