Non-Stationary Bandit Problems
You'll learn how to handle bandit problems where reward distributions change over time, requiring your agent to continuously adapt.
The Challenge of Change
Until now, we've assumed that each arm's reward distribution stays constant—pull the red lever enough times and you'll eventually know its true average. But what if the casino secretly adjusts the slot machines overnight? Or what if you're recommending news articles whose popularity shifts by the hour?
Non-stationary bandit problems occur when the true reward distributions drift over time. Yesterday's best arm might be today's worst. The sample-average method we learned earlier becomes problematic because it weighs all past experiences equally—ancient history drags down your estimates even when the world has changed.
Exponential Recency-Weighted Averaging
Instead of treating all samples equally, we use a constant step-size α (typically between 0.05 and 0.3):
Q(a) ← Q(a) + α[R - Q(a)]
This is different from the sample-average Q(a) ← Q(a) + (1/n)[R - Q(a)] where step size shrinks to zero.
With constant α, recent rewards have exponentially more influence than old ones. If α = 0.1, today's reward matters 10× more than a reward from ~20 steps ago. This creates a "fading memory" that automatically forgets outdated information.
Analogy: It's like using a weighted moving average of stock prices instead of an all-time average. Recent trends matter more than ancient history when predicting tomorrow's price.
The trade-off? Constant step-size never fully converges (it keeps adapting), but that's exactly what you want when chasing a moving target.
Key Takeaway: In non-stationary environments, use constant step-size α instead of sample averaging to give recent rewards more weight, allowing your value estimates to track changing reward distributions.