arXiv:2610. 01181v1 Announce Type: new Abstract: We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs.
By S. Rasoul Etesami
arXiv:2609. 14959v1 Announce Type: new Abstract: We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $\alpha$-potential games.
By S. Rasoul Etesami
The paper introduces aspiration-based perturbed learning automata (APLA), a payoff‑based learning scheme that incorporates an aspiration factor to reinforce action selection in distributed multi‑player games. It presents a stochastic stability analysis of APLA in positive‑utility games with noisy observations, establishing that the infinite‑dimensional Markov chain induced by the dynamics can be reduced to a finite‑dimensional one. This work extends previous results beyond potential and coordination games to generic non‑zero‑sum games, with a second part focusing on weakly acyclic games.
By Georgios C. Chasparis
We introduce the first Probably Approximately Correct (PAC) learning framework for general-sum concurrent stochastic games (CSGs) with transition uncertainty, while addressing the challenge of Nash equilibrium (NE) existence. Our algorithm maintains data-driven $L^1$ confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal $\varepsilon$-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage.
The paper investigates learning Nash equilibria in partially observable Markov games (POMGs) where agents cannot fully observe the state. By focusing on a subclass with independent state transitions and a Markov potential game structure, the authors propose an independent learning algorithm that allows agents to converge to an approximate Nash equilibrium using only their own observations and actions, without communication. Under a filter stability assumption, finite‑history policies are shown to approximate the POMG sufficiently, enabling a surrogate near‑potential Markov game and yielding quasi‑polynomial sample and computational complexity.
By Philip Jordan, Maryam Kamgarpour
The paper presents the first PAC learning framework for general-sum concurrent stochastic games with uncertain transitions, addressing the challenge of Nash equilibrium existence. It introduces data‑driven L¹ confidence sets over transition kernels and a robust CSG solver that computes a social‑welfare optimal ε‑NE, or provides a certificate that no exact NE exists. The algorithm achieves polynomial sample complexity under a minimum reachability condition and is validated on benchmark CSGs with near‑optimal performance.
By Angel Y. He, David Parker