# Strategy Synthesis for Zero-Sum Neuro-Symbolic Concurrent Stochastic Games

arXiv: https://arxiv.org/abs/2202.06255 · HTML: https://mlsanity.com/paper/2202.06255/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 66 references that are in the map.
- First posted on arXiv 13 Feb 2022.

## Builds on (most cited first, 16 of 16)

- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving](https://mlsanity.com/paper/1610.03295/) (2016)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [From Statistical Relational to Neuro-Symbolic Artificial Intelligence](https://mlsanity.com/paper/2003.08316/) (2020)
- [Neurosymbolic Reinforcement Learning with Formally Verified Exploration](https://mlsanity.com/paper/2009.12612/) (2020)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [A Reachability Method for Verifying Dynamical Systems with Deep Neural Network Controllers](https://mlsanity.com/paper/1903.00520/) (2019)
- [Automatic Verification of Concurrent Stochastic Systems](https://mlsanity.com/paper/2008.04613/) (2020)
- [Distributed Asynchronous Policy Iteration for Sequential Zero-Sum Games and Minimax Control](https://mlsanity.com/paper/2107.10406/) (2021)
- [Comparison of Algorithms for Simple Stochastic Games (Full Version)](https://mlsanity.com/paper/2008.09465/) (2020)
- [A Mixed Value and Policy Iteration Method for Stochastic Control with Universally Measurable Policies](https://mlsanity.com/paper/1308.3814/) (2013)
- [Qualitative Analysis of Concurrent Mean-payoff Games](https://mlsanity.com/paper/1409.5306/) (2014)
- [Policy Evaluation and Seeking for Multi-Agent Reinforcement Learning via Best Response](https://mlsanity.com/paper/2006.09585/) (2020)
- [On Convergence of Value Iteration for a Class of Total Cost Markov Decision Processes](https://mlsanity.com/paper/1411.1459/) (2014)
- [Comparison of Information Structures for Zero-Sum Games and a Partial Converse to Blackwell Ordering in Standard Borel Spaces](https://mlsanity.com/paper/2005.06673/) (2020)

## Built on by (most cited first, 5 of 5)

- [Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2310.11566/) (2023)
- [Multi-Agent Verification and Control with Probabilistic Model Checking](https://mlsanity.com/paper/2308.02829/) (2023)
- [Collision Avoidance Verification of Multiagent Systems with Learned Policies](https://mlsanity.com/paper/2403.03314/) (2024)
- [HSVI-based Online Minimax Strategies for Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2404.10679/) (2024)
- [LTL Verification of Memoryful Neural Agents](https://mlsanity.com/paper/2503.02512/) (2025)

## Abstract (arXiv)

Neuro-symbolic approaches to artificial intelligence, which combine neural networks with classical symbolic techniques, are growing in prominence, necessitating formal approaches to reason about their correctness. We propose a novel modelling formalism called neuro-symbolic concurrent stochastic games (NS-CSGs), which comprise two probabilistic finite-state agents interacting in a shared continuous-state environment. Each agent observes the environment using a neural perception mechanism, which converts inputs such as images into symbolic percepts, and makes decisions symbolically. We focus on the class of NS-CSGs with Borel state spaces and prove the existence and measurability of the value function for zero-sum discounted cumulative rewards under piecewise-constant restrictions on the components of this class of models. To compute values and synthesise strategies, we present, for the first time, practical value iteration (VI) and policy iteration (PI) algorithms to solve this new subclass of continuous-state CSGs. These require a finite decomposition of the environment induced by the neural perception mechanisms of the agents and rely on finite abstract representations of value functions and strategies closed under VI or PI. First, we introduce a Borel measurable piecewise-constant (B-PWC) representation of value functions, extend minimax backups to this representation and propose a value iteration algorithm called B-PWC VI. Second, we introduce two novel representations for the value functions and strategies, constant-piecewise-linear (CON-PWL) and constant-piecewise-constant (CON-PWC) respectively, and propose Minimax-action-free PI by extending a recent PI method based on alternating player choices for finite state spaces to Borel state spaces, which does not require normal-form games to be solved.