Online Learning in Stackelberg Games with an Omniscient Follower
This work addresses a novel variant of Stackelberg games for researchers in game theory and online learning, though it appears incremental by modifying the follower's knowledge assumption.
The paper tackles the problem of online learning in a two-player decentralized cooperative Stackelberg game with an omniscient follower, showing that the sample complexity for regret minimization can vary drastically from constant to exponential depending on the reward structure.
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.