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

• URL: http://arxiv.org/abs/2604.04394v1
• Date: Mon, 06 Apr 2026 03:48:42 GMT
• Title: Finite-Time Analysis of Q-Value Iteration for General-Sum Stackelberg Games
• Abstract summary: This paper studies the convergence of Stackelberg Q-value iteration in two-player general-sum Markov games from a control-theoretic perspective.<n>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.
• Score: 6.622208195193136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Dual Ensembled Multiagent Q-Learning with Hypernet Regularizer [62.01554688056335]
  Overestimation in the multiagent setting has received comparatively little attention.<n>We propose a novel hypernet regularizer on hypernetwork weights and biases to constrain the optimization of online global Q-network to prevent overestimation accumulation.
  arXiv  Detail & Related papers  (2025-02-04T05:14:58Z)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property [89.96815099996132]
  We develop a new framework to characterize optimistic policy gradient methods in multi-player games with a single controller. Our approach relies on a natural generalization of the classical Minty property that we introduce, which we anticipate to have further applications beyond Markov games.
  arXiv  Detail & Related papers  (2023-12-19T11:34:10Z)
• Reinforcement Learning With Reward Machines in Stochastic Games [25.834116101920834]
  We develop an algorithm called Q-learning with reward machines for games (QRM-SG) We prove that Q-functions learned in QRM-SG converge to the Q-functions at a Nash equilibrium. The three case studies show that QRM-SG can learn the best-response strategies effectively.
  arXiv  Detail & Related papers  (2023-05-27T05:32:30Z)
• Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation [56.715186432566576]
  We propose a new model, independent linear Markov game, for reinforcement learning with a large state space and a large number of agents. We design new algorithms for learning correlated equilibria (CCE) and Markov correlated equilibria (CE) with sample bounds complexity that only scalely with each agent's own function class complexity. Our algorithms rely on two key technical innovations: (1) utilizing policy replay to tackle non-stationarity incurred by multiple agents and the use of function approximation; and (2) separating learning Markov equilibria and exploration in the Markov games.
  arXiv  Detail & Related papers  (2023-02-07T18:47:48Z)
• Uncoupled Learning of Differential Stackelberg Equilibria with Commitments [43.098826226730246]
  We present uncoupled'' learning dynamics based on zeroth-order gradient estimators. We prove that they converge to differential Stackelberg equilibria under the same conditions as previous coupled methods. We also present an online mechanism by which symmetric learners can negotiate leader-follower roles.
  arXiv  Detail & Related papers  (2023-02-07T12:46:54Z)
• On the Convergence of No-Regret Learning Dynamics in Time-Varying Games [89.96815099996132]
  We characterize the convergence of optimistic gradient descent (OGD) in time-varying games. Our framework yields sharp convergence bounds for the equilibrium gap of OGD in zero-sum games. We also provide new insights on dynamic regret guarantees in static games.
  arXiv  Detail & Related papers  (2023-01-26T17:25:45Z)
• Learning in Stackelberg Games with Non-myopic Agents [60.927889817803745]
  We study Stackelberg games where a principal repeatedly interacts with a non-myopic long-lived agent, without knowing the agent's payoff function.<n>We provide a general framework that reduces learning in presence of non-myopic agents to robust bandit optimization in the presence of myopic agents.
  arXiv  Detail & Related papers  (2022-08-19T15:49:30Z)
• Independent and Decentralized Learning in Markov Potential Games [3.549868541921029]
  We study a multi-agent reinforcement learning dynamics, and analyze its behavior in infinite-horizon discounted Markov potential games.<n>We focus on the independent and decentralized setting, where players do not know the game parameters, and cannot communicate or coordinate.
  arXiv  Detail & Related papers  (2022-05-29T07:39:09Z)
• Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games [78.65798135008419]
  It remains vastly open how to learn the Stackelberg 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.
  arXiv  Detail & Related papers  (2021-02-23T05:11:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.