Solving zero-sum one-sided partially observable stochastic games
From MaRDI portal
Abstract: 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.
Cites work
- An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information
- DeepStack: expert-level artificial intelligence in heads-up no-limit poker
- Distributionally robust partially observable Markov decision process with moment-based ambiguity
- Efficient computation of behavior strategies
- Efficient computation of equilibria for extensive two-person games
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- scientific article; zbMATH DE number 2067975 (Why is no real title available?)
- scientific article; zbMATH DE number 1509479 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 2243398 (Why is no real title available?)
- Networks. An introduction.
- On a minimax theorem and its applications to functional analysis
- On general minimax theorems
- On Stefan Banach and some of his results
- Optimal control of Markov processes with incomplete state information
- Optimally solving Dec-POMDPs as continuous-state MDPs
- Superhuman AI for heads-up no-limit poker: Libratus beats top professionals
- The Optimal Control of Partially Observable Markov Processes over the Infinite Horizon: Discounted Costs
- The role of information in the cop-robber game
- Zero-sum stochastic games with partial information
Cited in
(4)- HSVI can solve zero-sum partially observable stochastic games
- Strategy synthesis for partially observable stochastic games with neural perception mechanisms (invited talk)
- Iterative algorithms for solving one-sided partially observable stochastic shortest path games
- Dynamic repair and maintenance of heterogeneous machines dispersed on a network: a rollout method for online reinforcement learning
This page was built for publication: Solving zero-sum one-sided partially observable stochastic games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098841)
