Iterative Algorithms for Solving one-sided Partially Observable Stochastic Shortest Path Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00379798" target="_blank" >RIV/68407700:21230/24:00379798 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Iterative Algorithms for Solving one-sided Partially Observable Stochastic Shortest Path Games

Popis výsledku v původním jazyce

Real-world scenarios often involve dynamic interactions among competing agents, where decisions are made considering actions taken by others. These situations can be modeled as partially observable stochastic games (POsts), POst s), with zero-sum variants capturing strictly competitive interactions (e.g., security scenarios). While such models address a broad range of problems, they commonly focus on infinite-horizon scenarios with discounted-sum objectives. Using the discounted-sum objective, however, can lead to suboptimal solutions in cases where the length of the interaction does not directly affect the gained rewards of the players. We thus focus on games with undiscounted objective and an indefinite horizon where every realization of the game is guaranteed to terminate after some unspecified number of turns. To manage the computational complexity of solving POsts s in general, we restrict to games with one-sided partial observability where only one player has imperfect information while their opponent is provided with full information about the current situation. We introduce two novel algorithms based on the heuristic search value iteration ( HsVI ) algorithm that iteratively solve sequences of easier-to-solve approximations of the game using fundamentally different approaches for constructing the sequences: (1) in toalHorizon, , the game approximations are based on a limited number of turns in which players can change their actions, (2) in toalDiscount, , the game approximations are constructed using an increasing discount factor. We provide theoretical qualitative guarantees for algorithms, and we also experimentally demonstrate that these algorithms are able to find near-optimal solutions on pursuit-evasion games and a game modeling privilege escalation problem from computer security.

Název v anglickém jazyce

Iterative Algorithms for Solving one-sided Partially Observable Stochastic Shortest Path Games

Popis výsledku anglicky

Real-world scenarios often involve dynamic interactions among competing agents, where decisions are made considering actions taken by others. These situations can be modeled as partially observable stochastic games (POsts), POst s), with zero-sum variants capturing strictly competitive interactions (e.g., security scenarios). While such models address a broad range of problems, they commonly focus on infinite-horizon scenarios with discounted-sum objectives. Using the discounted-sum objective, however, can lead to suboptimal solutions in cases where the length of the interaction does not directly affect the gained rewards of the players. We thus focus on games with undiscounted objective and an indefinite horizon where every realization of the game is guaranteed to terminate after some unspecified number of turns. To manage the computational complexity of solving POsts s in general, we restrict to games with one-sided partial observability where only one player has imperfect information while their opponent is provided with full information about the current situation. We introduce two novel algorithms based on the heuristic search value iteration ( HsVI ) algorithm that iteratively solve sequences of easier-to-solve approximations of the game using fundamentally different approaches for constructing the sequences: (1) in toalHorizon, , the game approximations are based on a limited number of turns in which players can change their actions, (2) in toalDiscount, , the game approximations are constructed using an increasing discount factor. We provide theoretical qualitative guarantees for algorithms, and we also experimentally demonstrate that these algorithms are able to find near-optimal solutions on pursuit-evasion games and a game modeling privilege escalation problem from computer security.

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í

2024

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

International Journal of Approximate Reasoning

ISSN

0888-613X

e-ISSN

1873-4731

Svazek periodika

175

Číslo periodika v rámci svazku

December

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

47

Strana od-do

1-47

Kód UT WoS článku

001331827100001

EID výsledku v databázi Scopus

2-s2.0-85205540055