In Simple Words
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.
Research question
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.
Participants
Theoretical proof and simulation framework evaluated across 40 operational weeks in Jordan (N = 3,770).
Study Design
Adversarial bandit framework providing worst-case regret bounds for arbitrary, non-i.i.d. sequences of potential outcomes relative to any fixed assignment policy.
Results
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.
Takeaway
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.