No-Regret Learning in Dynamic Stackelberg Games

• 成果类型: Article
• 署名作者: Lauffer, Niklas; Ghasemi, Mahsa; Hashemi, Abolfazl; Savas, Yagiz; Topcu, Ufuk
• 署名单位: University of California System; University of California Berkeley; Purdue University System; Purdue University; University of Texas System; University of Texas Austin
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3330797
• 发表日期: 2024
• 页码: 1418-1431
• 关键词: games; Heuristic algorithms; Atmospheric modeling; STANDARDS; security; Reinforcement Learning; Markov processes; Iterative learning control; no-regret learning; online learning; Stackelberg games; stochastic games

摘要

In a Stackelberg game, a leader commits to a randomized strategy and a follower chooses their best strategy in response. We consider an extension of a standard Stackelberg game, called a discrete-time dynamic Stackelberg game, that has an underlying state space that affects the leader's rewards and available strategies and evolves in a Markovian manner depending on both the leader and follower's selected strategies. Although standard Stackelberg games have been utilized to improve scheduling in security domains, their deployment is often limited by requiring complete information of the follower's utility function. In contrast, we consider scenarios where the follower's utility function is unknown to the leader; however, it can be linearly parameterized. Our objective is then to provide an algorithm that prescribes a randomized strategy to the leader at each step of the game based on observations of how the follower responded in previous steps. We design an online learning algorithm that, with high probability, is no-regret, i.e., achieves a regret bound (when compared to the best policy in hindsight), which is sublinear in the number of time steps; the degree of sublinearity depends on the number of features representing the follower's utility function. The regret of the proposed learning algorithm is independent of the size of the state space and polynomial in the rest of the parameters of the game. We show that the proposed learning algorithm outperforms existing model-free reinforcement learning approaches.