# Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games

arXiv: https://arxiv.org/abs/2604.04394 · HTML: https://mlsanity.com/paper/2604.04394/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, one of 15 directions in Deep reinforcement learning methods.
- Builds on 17 of its 39 references that are in the map.
- First posted on arXiv 6 Apr 2026.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 17 of 17)

- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction](https://mlsanity.com/paper/2006.03041/) (2020)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [Convergence of Learning Dynamics in Stackelberg Games](https://mlsanity.com/paper/1906.01217/) (2019)
- [Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?](https://mlsanity.com/paper/2112.13521/) (2021)
- [Regret Minimization and Convergence to Equilibria in General-sum Markov Games](https://mlsanity.com/paper/2207.14211/) (2022)
- [A Discrete-Time Switching System Analysis of Q-learning](https://mlsanity.com/paper/2102.08583/) (2021)
- [On the convergence of policy gradient methods to Nash equilibria in general stochastic games](https://mlsanity.com/paper/2210.08857/) (2022)
- [Periodic Q-Learning](https://mlsanity.com/paper/2002.09795/) (2020)
- [Learning Correlated Stackelberg Equilibrium in General-Sum Multi-Leader-Single-Follower Games](https://mlsanity.com/paper/2210.12470/) (2022)
- [Finite-sample Guarantees for Nash Q-learning with Linear Function Approximation](https://mlsanity.com/paper/2303.00177/) (2023)
- [Finite-Time Analysis of Minimax Q-Learning for Two-Player Zero-Sum Markov Games: Switching System Approach](https://mlsanity.com/paper/2306.05700/) (2023)
- [Finite-Time Error Analysis of Soft Q-Learning: Switching System Approach](https://mlsanity.com/paper/2403.06366/) (2024)
- [Finding a Multiple Follower Stackelberg Equilibrium: A Fully First-Order Method](https://mlsanity.com/paper/2509.08161/) (2025)
- [Learning in Stackelberg Markov Games](https://mlsanity.com/paper/2509.16296/) (2025)

## Abstract (arXiv)

Reinforcement learning has been successful both empirically and theoretically in single-agent settings, but extending these results to multi-agent reinforcement learning in general-sum Markov games remains challenging. This paper studies the convergence of Stackelberg Q-value iteration in two-player general-sum Markov games from a control-theoretic perspective. We introduce a relaxed policy condition tailored to the Stackelberg setting and model the learning dynamics as a switching system. By constructing upper and lower comparison systems, we establish finite-time error bounds for the Q-functions and characterize their convergence properties. Our results provide a novel control-theoretic perspective on Stackelberg learning. Moreover, to the best of the authors' knowledge, this paper offers the first finite-time convergence guarantees for Q-value iteration in general-sum Markov games under Stackelberg interactions.