# Solving Zero-Sum One-Sided Partially Observable Stochastic Games

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2020.

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

- [Games for AI Control: Models of Safety Evaluations of AI Deployment Protocols](https://mlsanity.com/paper/2409.07985/) (2024)
- [Learning Near-Optimal Intrusion Responses Against Dynamic Attackers](https://mlsanity.com/paper/2301.06085/) (2023)
- [Conjectural Online Learning with First-order Beliefs in Asymmetric Information Stochastic Games](https://mlsanity.com/paper/2402.18781/) (2024)
- [Automated Security Response through Online Learning with Adaptive Conjectures](https://mlsanity.com/paper/2402.12499/) (2024)
- [HSVI can solve zero-sum Partially Observable Stochastic Games](https://mlsanity.com/paper/2210.14640/) (2022)
- [Learning Security Strategies through Game Play and Optimal Stopping](https://mlsanity.com/paper/2205.14694/) (2022)
- [Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability](https://mlsanity.com/paper/2510.23744/) (2025)
- [Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2310.11566/) (2023)
- [On Minimizing Adversarial Counterfactual Error in Adversarial RL](https://mlsanity.com/paper/2406.04724/) (2024)
- [HSVI-based Online Minimax Strategies for Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2404.10679/) (2024)
- [On Dynamic Programming Theory for Leader-Follower Stochastic Games](https://mlsanity.com/paper/2512.05667/) (2025)
- [Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Games](https://mlsanity.com/paper/2608.24986/) (2026)

## Abstract (arXiv)

Many security and other real-world situations are dynamic in nature and can be modelled as strictly competitive (or zero-sum) dynamic games. In these domains, agents perform actions to affect the environment and receive observations -- possibly imperfect -- about the situation and the effects of the opponent's actions. Moreover, there is no limitation on the total number of actions an agent can perform -- that is, there is no fixed horizon. These settings can be modelled as partially observable stochastic games (POSGs). However, solving general POSGs is computationally intractable, so we focus on a broad subclass of POSGs called one-sided POSGs. In these games, only one agent has imperfect information while their opponent has full knowledge of the current situation. We provide a full picture for solving one-sided POSGs: we (1) give a theoretical analysis of one-sided POSGs and their value functions, (2) show that a variant of a value-iteration algorithm converges in this setting, (3) adapt the heuristic search value-iteration algorithm for solving one-sided POSGs, (4) describe how to use approximate value functions to derive strategies in the game, and (5) demonstrate that our algorithm can solve one-sided POSGs of non-trivial sizes and analyze the scalability of our algorithm in three different domains: pursuit-evasion, patrolling, and search games.