Search papers, labs, and topics across Lattice.
This paper addresses the challenges of PAC learning in turn-based stochastic games (TBSGs) with reachability objectives by relaxing traditional assumptions of public and centralized information sharing. The authors introduce a decentralized approach where players learn with private information and different algorithms, marking a significant advancement in the feasibility of learning in adversarial settings. A novel game-theoretic generalization of the Expected Conditional Distance (ECD) is proposed, leading to a polynomial-sample complexity bound that enhances understanding of reachability in TBSGs.
Decentralized learning with private information in turn-based stochastic games is now achievable, breaking new ground in adversarial learning scenarios.
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.
