Robust PAC Learning of Concurrent Stochastic Games

Abstract

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. 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 \(p_{\mathrm{reach}}>0\) over relevant state–action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity \(\widetilde{\mathcal{O}}\big(R_{\max}^2H^4|S|^2|A|/(p_{\mathrm{reach}}\varepsilon^2)\big)\). Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.

Two challenges

How it works

Setting. The true game \(\mathcal{G}^\star\) is a finite two-player general-sum CSG. The learner knows its \(|S|\) states, \(|A|\) joint actions, rewards (bounded by \(R_{\max}\)) and transition support, but not its transition probabilities \(P^\star\). It chooses both players’ actions (centralised exploration) and learns from sampled trajectories. Objectives are reaching target states \(S_T\) or accumulating reward, within a horizon \(H\) or unbounded.

Confidence sets. For each non-target pair \((s,a)\) (with \(s\notin S_T\)), the learner keeps an \(L^1\) ball \(\mathcal{P}_t(s,a)\) of distributions with the known support, centred at the empirical distribution \(\widehat{P}_{sa,t}\). Its radius shrinks as \((s,a)\) is visited more often, and with probability at least \(1-\delta/2\) every ball contains the true distribution \(P^\star_{sa}\), at every episode. The learner stops exploring once \(\Delta_t\le\varepsilon/4\), where \(\Delta_t:=\tfrac12R_{\max}H^2\max_{(s,a)}\sup_{p\in\mathcal{P}_t(s,a)}\|p-\widehat{P}_{sa,t}\|_1\) bounds how far any player’s value under a kernel in the confidence sets can be from its value under the empirical model (Lemma 2).

Robust exploration. To decide where to explore, the learner solves an auxiliary exploration RMDP (robust Markov decision process). Known pairs keep their confidence sets; unknown (under-visited) pairs move to an absorbing state \(z\) and collect reward 1 on that move, so a profile’s expected reward is its probability of reaching an unknown pair. Write \(p^e_t(P)\) for this probability under the exploration profile \(\sigma^e_t\) and kernel \(P\), and \(\mathcal{P}^e_t\) for the RMDP’s uncertainty set. Because \(\sigma^e_t\) maximises the worst case over \(\mathcal{P}^e_t\), as long as unknown pairs remain and the confidence sets contain \(P^\star\) (Lemma 6; \(p_{\mathrm{reach}}\) is defined under Main result):

With an optimistic (best-case) objective this bound need not hold: a best-case probability over the confidence sets need not lower-bound the probability under \(P^\star\). Sampling \(\widetilde{\mathcal{O}}(1/p_{\mathrm{reach}})\) trajectories per episode makes each episode reach an unknown pair with high probability. Freedman’s inequality then shows that, with probability at least \(1-\delta/2\), every non-target pair is visited \(n_{\min}\) times within \(\widetilde{\mathcal{O}}(n_{\min}|S||A|)\) episodes, which is enough for \(\Delta_t\le\varepsilon/4\).

An equilibrium, or a certificate. The Nash margin measures how far a stationary profile \(\sigma\) is from being an NE:

So \(\mu(\sigma,P)\ge 0\) if and only if \(\sigma\) is an NE, and \(\bar\mu:=\max_\sigma\mu(\sigma,P^\star)\ge 0\) if and only if the true game has an exact stationary NE. Once \(\Delta_t\le\varepsilon/4\), a robust CSG solver is run on the learned model. If it finds a robust \(\varepsilon\)-NE, it returns one with the highest worst-case social welfare. Whenever the confidence sets contain \(P^\star\), that profile is an \(\varepsilon\)-NE of the true game, and \(\varepsilon\)-optimal if an exact stationary NE exists; and if the solver finds none, no exact stationary NE exists.

Main result

Experiments

Implemented in PRISM-games and evaluated on six benchmark CSGs, with \(\delta=0.05\), \(\varepsilon=0.2\) (\(\varepsilon=0.1\) for RQ1) and 10 random seeds.

RQ1: correct outputs at termination

When an exact stationary NE exists, the returned profile attains the NE value that the exact PRISM-games solver computes on the true game. Without one, the algorithm certifies non-existence (Cyclic Preferences, reachability reward) or returns a valid \(\varepsilon\)-NE (Hide-or-Run, unbounded reachability): the certificate is sound, but not complete.

RQ2: exploration strategy

RQ3: sample-complexity scaling

Poster

Open the poster (PDF)

Citation

@inproceedings{he2026robust,
  title     = {Robust {PAC} Learning of Concurrent Stochastic Games},
  author    = {He, Angel Y. and Parker, David},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  year      = {2026}
}

Acknowledgements

This work is supported by the EPSRC Centre for Doctoral Training no. EP/Y035070/1 and the UKRI AI Hub on Mathematical Foundations of AI.