Actions Speak What You Want: Provably Sample-Efficient Reinforcement
  Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks
Siyu Chen Mengdi Wang Zhuoran Yang
We study reinforcement learning (RL) for learning a Quantal Stackelberg
Equilibrium (QSE) in an episodic Markov game with a leader-follower structure.
In specific, at the outset of the game, the leader announces her policy to the
follower and commits to it. The follower observes the leader's policy and, in
turn, adopts a quantal response policy by solving an entropy-regularized policy
optimization problem induced by leader's policy. The goal of the leader is to
find her optimal policy, which yields the optimal expected total return, by
interacting with the follower and learning from data. A key challenge of this
problem is that the leader cannot observe the follower's reward, and needs to
infer the follower's quantal response model from his actions against leader's
policies. We propose sample-efficient algorithms for both the online and
offline settings, in the context of function approximation. Our algorithms are
based on (i) learning the quantal response model via maximum likelihood
estimation and (ii) model-free or model-based RL for solving the leader's
decision making problem, and we show that they achieve sublinear regret upper
bounds. Moreover, we quantify the uncertainty of these estimators and leverage
the uncertainty to implement optimistic and pessimistic algorithms for online
and offline settings. Besides, when specialized to the linear and myopic
setting, our algorithms are also computationally efficient. Our theoretical
analysis features a novel performance-difference lemma which incorporates the
error of quantal response model, which might be of independent interest.