  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.
