Adversarial Non-Stationarity Bounds in Multi-Armed Bandits
RCTClinical Trial
Adaptive learning algorithms typically assume that outcome distributions remain stationary over time, but real-world field trials are vulnerable to seasonal shifts, policy shocks, or sample drift. If potential outcomes change non-stationarily, standard adaptive algorithms could lock into suboptimal assignment policies based on outdated early data.
Picture this
Imagine playing a card game where an opponent can secretly alter the deck rules between rounds. If you assume the deck never changes, early luck might trick you into a permanently failing strategy. An adversarial algorithm assumes the opponent will change the rules in the worst possible way, maintaining a guaranteed strategy that limits maximum potential losses no matter how the deck is shuffled over time.
What the evidence says
Proves that algorithms like the Tempered Thompson Algorithm achieve worst-case average regret on the order of $O(1/\sqrt{T})$ (up to logarithmic terms) relative to any fixed targeted assignment policy, guaranteeing robust participant welfare even under non-stationary outcome distributions.
- Who was studied
- Theoretical proof and simulation framework evaluated across 40 operational weeks in Jordan (N = 3,770).
- How
- Adversarial bandit framework providing worst-case regret bounds for arbitrary, non-i.i.d. sequences of potential outcomes relative to any fixed assignment policy.
What to do
Maintain non-zero minimum treatment assignment probabilities ($\gamma > 0$) in adaptive algorithms to secure $O(1/\sqrt{T})$ worst-case regret bounds against non-stationary shocks during field deployment.
From the source
"Remarkably, bandit algorithms (such as Thompson sampling) are able to achieve worst-case average regret (relative to any fixed treatment or targeted assignment policy) on the order of $1/\sqrt{T}$ (up to logarithmic terms)."
An Adaptive Targeted Field Experiment: Job Search Assistance for Refugees in Jordan