Online Learning in Stackelberg Games with an Omniscient Follower
Online Learning in Stackelberg Games with an Omniscient Follower
复制标题
DOI：
10.48550/arxiv.2301.11518
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
Geng Zhao;Banghua Zhu;Jiantao Jiao;Michael I. Jordan
中科院分区：
文献类型：
--
作者：
Geng Zhao;Banghua Zhu;Jiantao Jiao;Michael I. Jordan
研究了两人分散合作Stackelberg博弈中的在线学习问题。在每一轮中，领导者首先采取行动，跟随者在观察领导者的行动后采取行动。领导者的目标是学会根据互动的历史来最大限度地减少累积的遗憾。与传统的重复斯塔克伯格博弈不同，我们假设跟随者是无所不知的，完全知道真正的回报，并且他们总是对领导者的行动做出最佳反应。我们分析了在这个重复的Stackelberg博弈中后悔最小化的样本复杂性。我们发现，根据奖励结构，全知追随者的存在可能会改变样本的复杂性急剧，从常数到指数，即使是线性合作Stackelberg游戏。这对领导者的学习过程和随后的后悔分析提出了独特的挑战。
We study the problem of online learning in a two-player decentralized cooperative Stackelberg game. In each round, the leader first takes an action, followed by the follower who takes their action after observing the leader's move. The goal of the leader is to learn to minimize the cumulative regret based on the history of interactions. Differing from the traditional formulation of repeated Stackelberg games, we assume the follower is omniscient, with full knowledge of the true reward, and that they always best-respond to the leader's actions. We analyze the sample complexity of regret minimization in this repeated Stackelberg game. We show that depending on the reward structure, the existence of the omniscient follower may change the sample complexity drastically, from constant to exponential, even for linear cooperative Stackelberg games. This poses unique challenges for the learning process of the leader and the subsequent regret analysis.