Solving zero-sum one-sided partially observable stochastic games

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00364587" target="_blank" >RIV/68407700:21230/23:00364587 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1016/j.artint.2022.103838" target="_blank" >https://doi.org/10.1016/j.artint.2022.103838</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.artint.2022.103838" target="_blank" >10.1016/j.artint.2022.103838</a>

Result language

angličtina

Original language name

Solving zero-sum one-sided partially observable stochastic games

Original language description

Many real-world situations are dynamic, with long-term interactions between multiple agents with uncertainty and limited observations. The agents must reason about which actions to take while also predicting and learning about what actions the other agents will take and how their choices will interact. In the most general setting, there is no limitation on the length of the sequence of actions the agent can perform - that is, there is no fixed horizon that can be used as an endpoint for analysis. These settings can be modeled as partially observable stochastic games (POSGs). Many adversarial domains (e.g., security settings) can be modeled as strictly competitive (or zero-sum) variants of these games. While these models are capable of modeling a wide variety of realistic problems, 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 complete approach for solving zero-sum, 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) experimentally 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.(c) 2022 Elsevier B.V. All rights reserved.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Artificial Intelligence

ISSN

0004-3702

e-ISSN

1872-7921

Volume of the periodical

316

Issue of the periodical within the volume

103838

Country of publishing house

GB - UNITED KINGDOM

Number of pages

47

Pages from-to

—

UT code for WoS article

000912095000001

EID of the result in the Scopus database

2-s2.0-85144303060