The classic multi-armed bandit (MAB) framework relies on a clean but fragile assumption: when an agent pulls an arm, the resulting reward is drawn independently from a stationary probability distribution. In the real world, this independent and identically distributed (i.i.d.) assumption frequently falls apart. If a recommendation engine shows a user the same movie suggestion repeatedly, the user becomes desensitized, causing the reward to drop. If an algorithm selects a wireless channel for data transmission, the channel's quality fluctuates based on underlying physical states.
In these environments, rewards exhibit temporal dependency: the payoff of an action today is fundamentally shaped by the history of actions taken yesterday. When rewards have memory, standard exploration-exploitation strategies fail. A greedy algorithm might pull a highly rewarding arm right now, completely unaware that doing so tanks its utility for future rounds. To maximize long-term rewards, algorithms must move away from treating non-stationarity as an arbitrary, adversarial force and instead directly exploit the underlying temporal structure of the environment.
Modeling the Structure of Memory
To build algorithms that can plan ahead, we first need a mathematical language to describe how the past influences the present. The literature converges on two primary ways to model this memory: Markov chains and autoregressive processes.
In a Markovian bandit framework, each arm's reward is governed by an underlying state machine. The system transitions from one state to another based on a transition matrix, meaning the current reward depends directly on the immediate previous state. As explored by Cem Tekin et al. in Online Algorithms for the Multi-Armed Bandit Problem with Markovian Rewards, the core challenge is that an arm's state often only updates or becomes visible when it is actively played. This introduces significant analytical complexity because successive observations are tightly coupled, making it harder for the agent to form unbiased estimates of an arm's true mean value.
Alternatively, temporal dependencies can be captured via an autoregressive (AR) process, where the reward at any given time step is a linear combination of a fixed number of previous rewards plus stochastic noise. Qinyi Chen in Dynamic Bandits with Temporal Structure demonstrates that modeling rewards as a first-order autoregressive (AR-1) process provides a powerful middle ground between static stochastic models and completely arbitrary adversarial models. Instead of assuming the environment changes unpredictably, the agent leverages the predictable momentum of the time-series data.
In more complex settings, such as the framework proposed by Francesco Bacchiocchi et al. in Autoregressive Bandits, these autoregressive coefficients are action-dependent. This means the agent's choices do not just passively observe a trend; they actively steer the long-term trajectory of future rewards.
The Cost of Repetition: Recovering and Recharging Payoffs
A particularly intuitive form of temporal dependency occurs when an arm's payoff is a function of the elapsed time since it was last selected. This is known as the recovering or recharging bandit problem.
Imagine a content recommendation system. If you recommend a user's favorite song, the immediate engagement is high. However, if you repeat that recommendation in the very next round, the expected reward drops significantly due to saturation or boredom. If you wait, the user's interest gradually recovers to its baseline level.
Arm Reward
^
| /--- Baseline Reward
| /
| / <-- Recovery Curve
| /
+--+-----------------------> Time since last pull
Pull
The authors of Recovering Bandits formalize this by modeling these unknown recovery functions using Gaussian Processes. Because an action taken today penalizes the availability of rewards tomorrow, the mathematical objective shifts from identifying a single "best arm" to finding an optimal sequence or cycle of actions.
To solve this, Leonardo Cella et al. in Stochastic Bandits with Delay-Dependent Payoffs show that when rewards are penalized within a specific delay threshold, simple "ranking policies" provide an excellent approximation. Instead of greedily picking the highest-value arm, the algorithm cycles through a top tier of arms, deliberately giving each one sufficient time to clear its penalty threshold and return to its baseline level. When these recovery rates are entirely unknown, Orestis Papadigenopoulos et al. in Non-Stationary Bandits under Recharging Payoffs: Improved Planning with Sublinear Regret demonstrate that agents can simultaneously learn the underlying recovery curves and optimize the scheduling sequence with sublinear regret.
Restoring Independence via Strategic Waiting
Why do these algorithms actually work? The core algorithmic insight across this research direction is finding clever ways to handle or bypass the temporal correlation so that classical statistical guarantees can still apply.
One prominent strategy is strategic waiting. If an environment follows a mixing process where temporal dependencies naturally decay over time, the agent can introduce deliberate delays between pulls of the same arm. As shown by Julien Audiffren et al. in Cornering Stationary and Restless Mixing Bandits with Remix-UCB, by inserting a calculated "waiting period," the internal state of the arm is allowed to decorrelate from its past history. During these waiting intervals, the agent pulls other optimal arms to maintain high cumulative rewards. Once statistical independence is recovered, the agent can safely apply standard Upper Confidence Bound (UCB) techniques to update its estimates without being misled by transient historical correlations.
Another strategy is periodic memory resets. In fast-changing autoregressive environments, old data can quickly become a liability, biasing the agent's current estimates with outdated trends. To counter this, Qinyi Chen in Dynamic Bandits with Temporal Structure introduces an alternating and restarting mechanism. By intentionally wiping the agent's memory at mathematically optimized intervals, the algorithm prevents historical noise from locking the agent into suboptimal choices, successfully balancing continuous tracking with fresh exploration.
Key Foundational Work
Online Algorithms for the Multi-Armed Bandit Problem with Markovian Rewards (2010) — contributed 1 concept elements to this direction.
Decentralized Learning for Multi-player Multi-armed Bandits (2012) — contributed 1 concept elements to this direction.