← Back to all news
arXiv Machine Learning By Angel Y. He, David Parker

Robust PAC Learning of Concurrent Stochastic Games

Read the original on arXiv Machine Learning →

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.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv Machine Learning.

Related stories

Hugging Face Trending Papers
Sep 3

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 $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.

benchmarks
More like this →
arXiv Machine Learning
Jul 17

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

arXiv:2607. 14877v1 Announce Type: new 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.

By Ali Asadi, Krishnendu Chatterjee, Pavol Kebis
reinforcement-learningsafety
More like this →
arXiv AI
6d ago

Provably Efficient Q-learning for Robust Reinforcement Learning

The paper introduces a sample‑efficient asynchronous Q‑learning algorithm for robust reinforcement learning in infinite‑horizon, discounted robust MDPs with total‑variation uncertainty. It proves that, given a single Markovian trajectory, the algorithm achieves an entrywise ε‑approximation of the optimal Q‑function with a sample complexity bounded by a nearly minimax‑optimal expression involving the discount factor, uncertainty level, mixing time, and occupancy probability. This result improves significantly over prior bounds for robust RL.

By Yuchen Jiao, Gen Li
agentsreinforcement-learningrobotics
More like this →