Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games

1. Problem Definition

The paper addresses Two-Player General-Sum Stochastic Stackelberg Games (SSGs).

• Setting: A dynamic environment modeled as a Markov Game with two agents: a Leader (Agent A) and a Follower (Agent B).
• Objective: The Leader aims to maximize their expected cumulative discounted reward, anticipating that the Follower will always play a Best Response (BR) to the Leader's policy.
• Key Constraint: The Follower is non-myopic (considers future rewards) and acts as a rational agent optimizing their own reward function. The environment (transition probabilities and reward functions) is known.
• The Core Challenge:
  • In general-sum settings, a Stationary Stackelberg Equilibrium (SSE)—a policy tuple where the Leader maximizes their payoff given the Follower's BR—does not always exist.
  • Existing methods (e.g., value iteration based on dynamic programming operators or policy gradient methods) often fail to guarantee monotone improvement in the Leader's performance.
  • Consequently, these methods may converge to low-quality policies or fail to converge to an SSE even if one exists, because the fixed points of their operators do not necessarily correspond to the true Stackelberg value function.

2. Methodology

The authors propose a novel Pareto-Optimal Policy Iteration algorithm. The methodology consists of three main theoretical pillars:

A. Analysis of Existing Dynamic Programming (DP) Operators

The authors analyze the DP operators used in prior works (e.g., Bucarey et al., 2022).

• They prove that the fixed point of these operators yields a value function where the Follower's strategy is a best response only to the specific fixed-point policy, not necessarily to arbitrary policies.
• This disconnect means the fixed point does not guarantee the Leader's optimal performance under the true Best Response Follower, especially when an SSE does not exist.

B. Derivation of a Policy Improvement Theorem

To overcome the lack of monotone improvement, the authors derive a Policy Improvement Theorem (Theorem 8) for SSGs with a Best-Response Follower.

• They define a Q-function $Q^{f' \dagger}_A(s, f)$ representing the Leader's immediate reward plus the discounted value of the next state, assuming the Follower plays the Best Response to the new policy $f$, while the value of the next state is evaluated under the old policy $f'$.
• Theorem 8 establishes that if $Q^{f' \dagger}_A(\cdot, f) \succeq V^{f' \dagger}_A$ (the new Q-value dominates the old value function), then the new policy $f$ yields a value function $V^{f \dagger}_A$ that dominates $V^{f' \dagger}_A$.
• This allows for policy updates without needing to compute the full value function for the new policy immediately, similar to standard Policy Iteration in single-agent MDPs.

C. Pareto-Optimality as a Target

Since an SSE may not exist (i.e., no single policy maximizes the Leader's value across all states simultaneously), the authors introduce Pareto-Optimality (PO) as the target.

• Definition: A value function is Pareto-optimal if no other reachable value function strictly dominates it in all states.
• Properties:
  • If an SSE exists, the SSE value function is the unique Pareto-optimal value function.
  • If no SSE exists, the set of Pareto-optimal value functions (the Pareto front) always exists and provides a "reasonable" set of optimal trade-offs.
• Scalarization: To guide the search, the algorithm uses a Pareto-compliant scalarization function $L$ (e.g., a weighted sum of state values) to select the next policy from the set of improving policies.

D. The Algorithm (Pareto-Optimal Policy Iteration)

The proposed algorithm (Algorithm 1) proceeds as follows:

1. Initialize a Leader policy $f_0$.
2. Evaluate: Compute the Leader's value function $V^{f_t \dagger}_A$ under the current policy and the Follower's Best Response.
3. Policy Improvement: Construct the set of policies $W_{\succeq}(f_t)$ that satisfy the improvement condition $Q^{f_t \dagger}_A(\cdot, f) \succeq V^{f_t \dagger}_A$.
4. Selection: Select a new policy $f_{t+1}$ from this set that maximizes the scalarized value $L[Q^{f_t \dagger}_A(\cdot, f)]$.
5. Iterate: Repeat until no further improvement is possible.

3. Key Contributions

1. Theoretical Analysis of DP Operators: The paper explicitly derives the fixed points of existing DP operators for SSGs, proving they do not guarantee optimal Leader performance when SSEs do not exist.
2. Policy Improvement Theorem: A new theorem is derived specifically for general-sum SSGs with Best-Response Followers, enabling monotone improvement guarantees.
3. Pareto-Optimal Policy Iteration: A novel algorithm is proposed that guarantees monotone improvement in the Leader's state values.
4. Convergence Guarantees:
   • The algorithm is proven to converge to the boundary of the reachable value function space.
   • Crucially, if the Leader is myopic ($\gamma_A = 0$), the algorithm is guaranteed to converge to a Pareto-optimal policy. This is the first theoretical guarantee of its kind for general-sum myopic-leader SSGs.
5. Handling Non-Existence of SSE: The framework provides a robust solution even when a stationary Stackelberg equilibrium does not exist, converging instead to the Pareto front.

4. Results and Significance

• Theoretical Significance: The work bridges a gap in game-theoretic RL by providing the first convergence guarantees for general-sum SSGs where the Follower is non-myopic and the Leader is myopic. It shifts the focus from finding a potentially non-existent SSE to finding Pareto-optimal policies.
• Practical Implications:
  • Monotonicity: Unlike policy gradient methods which can oscillate or degrade, this method ensures the Leader's performance never decreases during iteration.
  • Robustness: It handles scenarios where the "optimal" strategy is a trade-off between different states (Pareto front), which is common in real-world applications like e-commerce platform design or security games.
  • Application: The authors discuss applications in Policy Teaching (guiding an agent's behavior via environment manipulation), where the Leader (teacher) modifies transition probabilities to induce a specific Best Response in the Follower (student).
• Limitations:
  • The algorithm requires knowledge of the transition function and the ability to compute the Follower's Best Response (which can be computationally expensive).
  • For non-myopic Leaders ($\gamma_A > 0$), convergence to the Pareto front is not strictly guaranteed (only to the boundary), though monotone improvement is maintained.
  • The search space for the next policy can be large, requiring heuristics (like splitting the policy space) for practical implementation.

Conclusion

Kudo and Akimoto present a rigorous framework for solving two-player general-sum stochastic Stackelberg games. By abandoning the strict requirement for a Stationary Stackelberg Equilibrium and adopting Pareto-optimality as the target, they developed a Policy Iteration algorithm that guarantees monotone improvement and convergence to optimal trade-offs, particularly in the case of myopic Leaders. This offers a significant theoretical and practical advancement over existing dynamic programming and gradient-based approaches.