Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptions
We address payoff-based decentralized learning in infinite-horizon zero-sum Markov games. In this setting, each player makes decisions based solely on received rewards, without observing the opponent's strategy or actions nor sharing information. Prior works established finite-time convergence to an approximate Nash equilibrium under strong reachability and mixing time assumptions. We propose a convergent algorithm that significantly relaxes these assumptions, requiring only the existence of a single policy (not necessarily known) with bounded reachability and mixing time. Our key technical novelty is introducing Tsallis entropy regularization to smooth the best-response policy updates. By suitably tuning this regularization, we ensure sufficient exploration, thus bypassing previous stringent assumptions on the MDP. By establishing novel properties of the value and policy updates induced by the Tsallis entropy regularizer, we prove finite-time convergence to an approximate Nash equilibrium.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Bidding Games on Markov Decision Processes with Quantitative Reachability Objectives
Graph games are fundamental in strategic reasoning of multi-agent systems and their environments. We study a new family of graph games which combine stochastic environmental uncertainties and auction-based interactions a…
Stopping Criteria for Value Iteration on Concurrent Stochastic Reachability and Safety Games
We consider two-player zero-sum concurrent stochastic games (CSGs) played on graphs with reachability and safety objectives. These include degenerate classes such as Markov decision processes or turn-based stochastic gam…
PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance
Reachability is the most fundamental logical objective, yet it is notoriously difficult to learn in reinforcement learning settings: even for Markov decision processes, PAC learning of reachability is impossible without …
Reinforcement LearningMulti-Player Zero-Sum Markov Games with Networked Separable Interactions
We study a new class of Markov games, \emph(multi-player) zero-sum Markov Games} with \emph{Networked separable interactions} (zero-sum NMGs), to model the local interaction structure in non-cooperative multi-agent seque…
Decision MakingSequential Decision MakingA New Framework for Bounding Reachability Probabilities of Continuous-time Stochastic Systems
This manuscript presents an innovative framework for constructing barrier functions to bound reachability probabilities for continuous-time stochastic systems described by stochastic differential equations (SDEs). The re…