  Real world applications such as economics and policy making often involve
solving multi-agent games with two unique features: (1) The agents are
inherently asymmetric and partitioned into leaders and followers; (2) The
agents have different reward functions, thus the game is general-sum. The
majority of existing results in this field focuses on either symmetric solution
concepts (e.g. Nash equilibrium) or zero-sum games. It remains vastly open how
to learn the Stackelberg equilibrium -- an asymmetric analog of the Nash
equilibrium -- in general-sum games efficiently from samples.
  This paper initiates the theoretical study of sample-efficient learning of
the Stackelberg equilibrium in two-player turn-based general-sum games. We
identify a fundamental gap between the exact value of the Stackelberg
equilibrium and its estimated version using finite samples, which can not be
closed information-theoretically regardless of the algorithm. We then establish
a positive result on sample-efficient learning of Stackelberg equilibrium with
value optimal up to the gap identified above. We show that our sample
complexity is tight with matching upper and lower bounds. Finally, we extend
our learning results to the setting where the follower plays in a Markov
Decision Process (MDP), and the setting where the leader and the follower act
simultaneously.
