cs.LGJul 16, 2026

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

Authors: Ali Asadi, Krishnendu Chatterjee, Pavol Kebis

Organizations: Institute of Science and Technology Austria (ISTA), Austria

Abstract

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 additional assumptions. This difficulty also holds in turn-based stochastic games (TBSGs), where two adversarial players interact on a finite state space. In this work, we consider turn-based stochastic games with reachability objectives. For such settings, adversarial learning, in which players are adversarial even in the learning phase, is impossible. Therefore, the goal is to consider learning, in which both players learn the unknown model together. In this spirit, previous literature on PAC learning in TBSGs considers (a)~public information shared by both players; and (b)~centralized learning, which means that players share the same learning algorithm. In this work, our contribution is two-fold. First, we relax these strong assumptions and ensure learning: (i)~with private information not shared with the other player; and (ii)~decentralized learning where the players do not share the same learning algorithm. To the best of our knowledge, this work is the first positive result for decentralized and private information learning of TBSGs with reachability objectives. Second, we introduce a game-theoretic generalization of the Expected Conditional Distance (ECD) parameter, which measures the expected length of reaching the target set. We establish a polynomial-sample complexity bound with respect to the number of states, actions, ECD parameter, and inverses of error tolerance and failure probability.

Explore similar work

CardsList
Sep 3, 2026cs.LG

Robust PAC Learning of Concurrent Stochastic Games

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 L1L^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. Crucially, we introduce a Nash margin characterisation that enables principled reasoning about equilibrium existence: the framework either returns an ε\varepsilon-approximate NE whose social-welfare value is ε\varepsilon-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition preach>0p_{\mathrm{reach}}>0 over relevant state-action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity O~(Rmax⁡2H4∣S∣2∣A∣/(preachε2))\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right). Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.
Angel Y. He, David Parker
Zero--Sum Differential GameNash EquilibriumEquilibriumOptimal PoliciesSoft Actor-CriticAction Space
AskPDF
May 23, 2026cs.LG

Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves asymptotic convergence to optimal policies. However, this approach provides limited insight into convergence dynamics. In this work, we present an alternative approach that provides deeper theoretical insights into convergence. Our approach builds on PAC learning with assumptions. PAC learning guarantees near-optimal policies with high confidence in finite time but requires knowing internal MDP parameters like minimum transition probability. We argue that while these parameters are unknown in RL, they can be iteratively refined and estimated with increasing accuracy. By iteratively satisfying PAC conditions, we show that exact optimality can be achieved in the limit. Empirical evaluations on standard benchmarks validate our theoretical insights into convergence dynamics.
Amogh Palasamudram, Jakub Svoboda, Suguman Bansal +1
Optimal PoliciesReachability
AskPDF
Sep 2, 2024cs.LG

Decentralized Best-Response-Based Learning in Two-Player Zero-Sum Stochastic Games: A Finite-Sample Analysis

We present a finite-sample analysis of decentralized learning in two-player zero-sum matrix games and stochastic games, with a focus on best-response-based learning algorithms. In matrix games, the learning algorithm is payoff-based and symmetric: each player updates its policy using only its own payoff observations, incrementally moving toward an estimated smoothed best response to the opponent's latest policy. For stochastic games, we build on this matrix-game primitive to develop a learning algorithm called value iteration with smoothed best response (VI-SBR), which combines smoothed-best-response learning in induced matrix games with a decentralized, model-free approximation of minimax value iteration. We establish finite-sample guarantees in both settings. For matrix games, our results imply a sample complexity of O(ε−1)\mathcal{O}(ε^{-1}) for finding an εε-Nash distribution and, with explicit exploration, O~(ε−8)\tilde{\mathcal{O}}(ε^{-8}) for finding an εε-Nash equilibrium. For stochastic games, we prove that the exploration-enhanced VI-SBR algorithm achieves a sample complexity of O~(ε−8)\tilde{\mathcal{O}}(ε^{-8}) for finding an εε-Nash equilibrium. Technically, our analysis develops a coupled Lyapunov-drift framework. This framework simultaneously handles stochastic iterative algorithms with multiple interacting stochastic iterates, the non-zero-sum auxiliary games generated by independently updated value functions, and the time-inhomogeneous Markovian noise induced by time-varying policies. The resulting tools may be useful more broadly for analyzing learning algorithms with coupled stochastic iterates and nonstationary sampling processes.
Zaiwei Chen, Kaiqing Zhang, Eric Mazumdar +2
Zero--Sum Differential GameImperfect-Information GamesStochastic ApproximationFinite-SampleDecentralization
AskPDF