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

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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.

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

2024

Confidentiality

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

Name of the periodical

International Journal of Approximate Reasoning

ISSN

0888-613X

e-ISSN

1873-4731

Volume of the periodical

175

Issue of the periodical within the volume

December

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

47

Pages from-to

1-47

UT code for WoS article

001331827100001

EID of the result in the Scopus database

2-s2.0-85205540055