Actions Speak What You Want: Provably Sample-Efficient Reinforcement Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks

Siyu Chen, Mengdi Wang, Zhuoran YangarXiv 2023 · OpenReview

TL;DR

This paper tackles the challenge of learning in a two-player game where one player (the leader) tries to influence the other (the follower) to achieve her goals, but crucially, the leader doesn't know the follower's true rewards. They develop provably sample-efficient algorithms for this "Quantal Stackelberg Equilibrium" problem, both online and offline, even with complex function approximation.

What Problem Does This Paper Address?

In many real-world scenarios, like human-robot interaction or negotiations, one agent (the leader) needs to influence another agent (the follower) to achieve a desired outcome. This is often modeled as a Stackelberg game, where the leader commits to a strategy, and the follower best responds. However, a significant challenge arises when the leader doesn't know the follower's true preferences (rewards) and can only observe the follower's actions. This makes it difficult for the leader to learn an optimal strategy, as she needs to infer the follower's behavior from limited, indirect information. This paper addresses this problem in the context of Reinforcement Learning (RL) within Markov games, specifically focusing on learning a "Quantal Stackelberg Equilibrium" (QSE), where the follower acts with bounded rationality (quantal response) and the leader must learn to influence this boundedly rational follower without observing their rewards.

Methods

The core of the paper's contribution lies in developing sample-efficient algorithms for learning the QSE. The approach has two main pillars:

  1. Learning the Follower's Behavior: The leader infers the follower's "quantal response" (a probabilistic best response influenced by an entropy regularization term, reflecting bounded rationality) using Maximum Likelihood Estimation (MLE). This is crucial because the leader doesn't observe the follower's rewards directly.
  2. Leader's Decision Making: The leader then uses this learned model of the follower to optimize her own policy. This is achieved through standard RL techniques (model-free or model-based), but adapted to incorporate the uncertainty in the learned follower model.

The algorithms are designed for both online (learning through interaction) and offline (learning from a fixed dataset) settings. They also handle function approximation, allowing for large state spaces. A key theoretical contribution is a novel "performance-difference lemma" that bridges the leader's decision problem and the follower's inferred behavior, quantifying how errors in inferring the follower's model affect the leader's performance. The algorithms leverage "optimism" (in online settings) and "pessimism" (in offline settings) principles to handle uncertainty.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees and algorithmic development, assuming access to data generated by interactions in a Markov game.

Key Insights and Ideas

  • Inferring Intent from Actions: The paper highlights that even without direct reward signals, a leader can infer a follower's intentions and preferences by observing their actions in response to different leader strategies. This is a powerful idea for multi-agent learning.
  • Bridging Bilevel Optimization and RL: Learning a Stackelberg equilibrium is inherently a bilevel optimization problem. The paper shows how to effectively tackle this within an RL framework, particularly when the lower level (follower's response) is learned from data.
  • Quantal Response as a Realistic Model: Using a "quantal response" model for the follower acknowledges that real-world agents often act with bounded rationality, making the learned equilibrium more practical.
  • Uncertainty Quantification is Key: The algorithms' sample efficiency hinges on accurately quantifying the uncertainty in the learned follower model and using this uncertainty to guide exploration (optimism) or avoid overestimation (pessimism).

Key Results

The paper proposes provably sample-efficient algorithms for learning the Quantal Stackelberg Equilibrium in episodic Markov games. These algorithms achieve sublinear regret (for online learning) and suboptimality bounds (for offline learning). Specifically:

  • Algorithms are developed for both online and offline settings.
  • They handle both myopic (short-sighted) and farsighted followers.
  • They incorporate function approximation for large state spaces.
  • When specialized to linear settings with myopic followers, the algorithms are computationally efficient.
  • A novel performance-difference lemma is introduced, which is crucial for analyzing the bilevel optimization structure.

Limitations and Future Work

  • Identifiability of Follower's Reward: The paper notes that learning the absolute value of the follower's utilities is generally not possible without additional constraints, as constant shifts in utilities don't affect the quantal response. While this is addressed for myopic followers, it's a point of consideration for farsighted ones.
  • Computational Complexity: While theoretical guarantees are provided, the practical computational complexity of some algorithms, especially those involving maximin problems or complex confidence sets, might be a limitation.
  • Future Work: The authors suggest exploring more complex scenarios, such as relaxing assumptions on the follower's response or dealing with more general game structures. The paper also mentions that relaxing the linear constraint on the follower's reward for farsighted followers is an area for future work.

Summary updated

Abstract

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.
BibTeX
@misc{chen2023actions,
  author = {Siyu Chen and Mengdi Wang and Zhuoran Yang},
  title = {{Actions Speak What You Want: Provably Sample-Efficient Reinforcement Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks}},
  year = {2023},
  eprint = {2307.14085},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2307.14085},
}
Figure