Rethinking formal models of partially observable multiagent decision making

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00355502" target="_blank" >RIV/68407700:21230/22:00355502 - isvavai.cz</a>

Result on the web

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

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

Rethinking formal models of partially observable multiagent decision making

Original language description

Multiagent decision-making in partially observable environments is usually modelled as either an extensive-form game (EFG) in game theory or a partially observable stochastic game (POSG) in multiagent reinforcement learning (MARL). One issue with the current situation is that while most practical problems can be modelled in both formalisms, the relationship of the two models is unclear, which hinders the transfer of ideas between the two communities. A second issue is that while EFGs have recently seen significant algorithmic progress, their classical formalization is unsuitable for efficient presentation of the underlying ideas, such as those around decomposition. To solve the first issue, we introduce factored-observation stochastic games (FOSGs), a minor modification of the POSG formalism which distinguishes between private and public observation and thereby greatly simplifies decomposition. To remedy the second issue, we show that FOSGs and POSGs are naturally connected to EFGs: by “unrolling” a FOSG into its tree form, we obtain an EFG. Conversely, any perfect-recall timeable EFG corresponds to some underlying FOSG in this manner. Moreover, this relationship justifies several minor modifications to the classical EFG formalization that recently appeared as an implicit response to the model’s issues with decomposition. Finally, we illustrate the transfer of ideas between EFGs and MARL by presenting three key EFG techniques – counterfactual regret minimization, sequence form, and decomposition – in the FOSG framework.

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

<a href="/en/project/GJ18-27483Y" target="_blank" >GJ18-27483Y: Online Solution Methods for Imperfect-Information Games</a><br>

Continuities

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

Publication year

2022

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

303

Issue of the periodical within the volume

103645

Country of publishing house

GB - UNITED KINGDOM

Number of pages

21

Pages from-to

1-21

UT code for WoS article

000728710000004

EID of the result in the Scopus database

2-s2.0-85120166639