2019/09/30 by Yuan Deng, Jon Schneider, Deng, Yuan +2 · 6 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1909.13861
openalex publication_date 2019/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
How should a player who repeatedly plays a game against a no-regret learner strategize to maximize his utility? We study this question and show that under some mild assumptions, the player can always guarantee himself a utility of at least what he would get in a Stackelberg equilibrium of the game. When the no-regret learner has only two actions, we show that the player cannot get any higher utility than the Stackelberg equilibrium utility. But when the no-regret learner has more than two actions and plays a mean-based no-regret strategy, we show that the player can get strictly higher than the Stackelberg equilibrium utility. We provide a characterization of the optimal game-play for the player against a mean-based no-regret learner as a solution to a control problem. When the no-regret learner's strategy also guarantees him a no-swap regret, we show that the player cannot get anything higher than a Stackelberg equilibrium utility.