Adversarial Non-Stationarity Bounds in Multi-Armed Bandits
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.