Best Response Convergence for Zero-sum Stochastic Dynamic Games with Partial and Asymmetric Information
We analyze best response dynamics for finding a Nash equilibrium of an infinite horizon zero-sum stochastic linear quadratic dynamic game (LQDG) with partial and asymmetric information. We derive explicit expressions for each player's best response within the class of pure linear dynamic output feedback control strategies where the internal state dimension of each control strategy is an integer multiple of the system state dimension. With each best response, the players form increasingly higher-order belief states, leading to infinite-dimensional internal states. However, we observe in extensive numerical experiments that the game's value converges after just a few iterations, suggesting that strategies associated with increasingly higher-order belief states eventually provide no benefit. To help explain this convergence, our numerical analysis reveals rapid decay of the controllability and observability Gramian eigenvalues and Hankel singular values in higher-order belief dynamics, indicating that the higher-order belief dynamics become increasingly difficult for both players to control and observe. Consequently, the higher-order belief dynamics can be closely approximated by low-order belief dynamics with bounded error, and thus feedback strategies with limited internal state dimension can closely approximate a Nash equilibrium.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games
We propose a novel independent and payoff-based learning framework for stochastic games that is model-free, game-agnostic, and gradient-free. The learning dynamics follow a best-response-type actor-critic architecture, w…
Fictitious play in zero-sum stochastic games
We present a novel variant of fictitious play dynamics combining classical fictitious play with Q-learning for stochastic games and analyze its convergence properties in two-player zero-sum stochastic games. Our dynamics…
Q-LearningLast-Iterate Convergence of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
In this paper, we consider two-player zero-sum matrix and stochastic games and develop learning dynamics that are payoff-based, convergent, rational, and symmetric between the two players. Specifically, the learning dyna…
Independent Learning in Stochastic Games
Reinforcement learning (RL) has recently achieved tremendous successes in many artificial intelligence applications. Many of the forefront applications of RL involve multiple agents, e.g., playing chess and Go games, aut…
Autonomous DrivingReinforcement Learning (RL)A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
We study two-player zero-sum stochastic games, and propose a form of independent learning dynamics called Doubly Smoothed Best-Response dynamics, which integrates a discrete and doubly smoothed variant of the best-respon…