Solving zero-sum one-sided partially observable stochastic games

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Solving zero-sum one-sided partially observable stochastic games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Solving zero-sum one-sided partially observable stochastic games

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název periodika

Artificial Intelligence

ISSN

0004-3702

e-ISSN

1872-7921

Svazek periodika

316

Číslo periodika v rámci svazku

103838

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

47

Strana od-do

—

Kód UT WoS článku

000912095000001

EID výsledku v databázi Scopus

2-s2.0-85144303060