Rethinking Formal Models of Partially Observable Multiagent Decision Making (Extended Abstract)

1 Introduction

Sequential decision-making is one of the core topics of artificial intelligence research. The ability of an AI agent to perform actions, observe their consequences, and perform further actions towards a goal is instrumental in domains from robotics and autonomous driving to medical decision diagnosis and automated personal assistants. Recent progress has led to unprecedented results in many large-scale problems of this type. While conceptually simpler problems can be modelled with perfect information or by regarding the other agents as stationary parts of the environment, realistic models of real-world situations require rigorous treatment of imperfect information and multiple independent decision-makers operating in a shared environment. The most popular gametheoretical model in these setting - extensive form games (EFG) - dates back to 1953 [von Neumann and Morgenstern, 1953]. EFGs have served the community well, and many impressive results build on top of this particular framework [Moravˇcík et al., 2017; Brown and Sandholm, 2017b; Brown and Sandholm, 2019].

∗ This is an extended abstract for [Kovaˇrík et al., 2022].

However, EFGs lose crucial information inherently present in many environments: the observations received by the agents. Observations are essential not only for specifying what information was received, but also to know who received it and when. Since EFGs simply group states indistinguishable to the acting player, the notion of information being public or private is forever lost, and so are the data about the timing. However, these concepts are essential for recent search algorithms [Moravˇcík et al., 2017; Brown and Sandholm, 2017a; Brown et al., 2020], where decomposition and reasoning about subgames crucially rely on the notion of public information. While it is common to try to recover the necessary information from the EFG model [Burch et al., 2014; Johanson et al., 2011; Šustr et al., 2019], we show that this is impossible to do in general. Practical implementations thus bypass the model by using algorithms that are built with game-specific concepts (e.g., dealing cards in poker), rather than developing algorithms running purely on top of the information provided by the formal model.

On the high-level, the key contributions of this paper are as follows: First, we argue that to get the most value out of game-theoretical models, we should no longer discard information about whether observations in an environment are observed jointly or privately. We propose that this can be done by using factored-observation stochastic games (FOSGs), a minor extension to the existing partially-observable stochastic game model. Additionally, we show EFGs and POSGs/FOSGs should not be viewed as two unrelated models. Instead, EFGs are derived objects that can be obtained by "unrolling" some underlying FOSG. This both highlights a new application for standalone EFG research and suggests that explicitly reasoning about the underlying FOSG can have significant benefits. (Indeed, FOSGs have the potential to enable new techniques and insights, make results accessible to a broader audience, and align our formal language with recent domainimplementations which often already resemble FOSGs.) More specifically, the full paper shows:

1. There is an an equivalence between POSGs and FOSGs. Any POSG result directly applies to FOSGs as well, since it suffices to merely forget the factorization of observations (Proposition 2.3).
2. We provide a mapping between EFGs and FOSGs. Every FOSG has a canonical extensive-form representation, and every "well-behaved" (perfect recall and timeable) EFG corresponds to some FOSG (Theorems 3.6 and 3.10).
3. Moreover, this relationship between FOSGs and EFGs suggests that our extended definition (Def. 3.5) is a natural way of formalizing EFGs. As a combination of several recent extensions of the EFG model [Burch et al., 2014; Johanson et al., 2011; Brown et al., 2018; Seitz et al., 2019], our formalization removes the need for implementing modern search algorithms in a domain-specific manner. In particular, it preempts various problems with decomposition that are difficult or even impossible to solve in the historical formalization of EFGs (Section 3.3).
4. Finally, we demonstrate that translating EFG results to FOSGs is straightforward: Decomposition in FOSGs has intuitive properties (Section 4.3) and two key EFG techniques - counterfactual regret minimization and sequence form - are easy to formulate in this framework (Sections 4.2 and 4.4).

In the remainder of this extended abstract, we give a formal definition of the proposed model. For a demonstration of the formalism on the example of Kuhn poker, and further details and results, we invite the reader to read [Kovaˇrík et al., 2022].

2 Factored-Observation Stochastic Games

In this section, we describe the factored-observation stochastic game model as a variation on partially-observable stochastic games. Since a key feature of the model is its ability to talk about public information, let us first explain what this concept refers to, why is it important, and why incorporating it into our models is natural, useful, and inexpensive.

2.1 Public Information and Decomposition

A piece of information is said to be common knowledge among a group of agents if all the agents know it, they all know that they know it, they all know that they all know that they know it, and so on [Fagin et al., 2003]. Figuring out which information is common knowledge is often difficult, as it requires putting oneself in shoes of the other agents and accurately reasoning about their thought processes. In contrast, a piece of information is public among a group of agents if each agent received it in a way that trivially reveals that the information is common knowledge. Some actions that create public knowledge are (a) speaking out loud in a group (b) placing a card face-up, or (c) moving a piece on a game board.

To see why public information is important, first note that the essence of game theory is that playing well requires knowing which actions the other players might take, which tends to involve reasoning about the information they have. Knowing that some information I is common knowledge is therefore immensely useful for decomposition. Indeed, each player will only reason about situations compatible with I (and about others' reasoning about situations compatible with I, others' reasoning about reasoning about situations compatible with I, etc.). Situations compatible with I can, therefore, be considered mostly independently of those incompatible with it (the limited dependence is explained in, e.g., [Moravˇcík et al., 2017]). However, finding out which information is common knowledge can be costly, so the best approach will often be to decompose games based on the subset of common knowledge that is public. Once we can decompose problems into smaller pieces, we become able to solve large problems that would otherwise be intractable. Indeed, we have recently seen breakthroughs in a number of problems that were made computationally feasible by decomposition based on public knowledge - examples include poker [Moravˇcík et al., 2017; Brown and Sandholm, 2017b; Brown and Sandholm, 2019], Hanabi [Foerster et al., 2019; Lerer et al., 2020], general EFGs [Šustr et al., 2019; Li et al., 2020; Davis et al., 2019], Dec-POMDPs [Spaan et al., 2008; de Witt et al., 2019], and one-sided POSGs [Horák and Bošanský, 2019].

However, the existing game-theoretic and MARL models do not have a built-in way of describing public knowledge. This is a serious problem because figuring out whether a piece of information is public or not might be difficult (or impossible) unless one remembers how the information was obtained. (Indeed, suppose I know that a friend would be happy to pick me up from an airport, and they know I would be glad if they did. This alone says nothing about whether the information is public among us - therefore, unless we explicitly talked about this, I should probably take a taxi. For more technical examples, see Section 3.3.) Making use of decomposition thus typically required adding some component on top of the employed formal model. In addition to requiring a non-trivial conceptual and technical effort, this was often done in a domain-specific manner [Moravˇcík et al., 2017; Brown and Sandholm, 2019], which made the devised methods difficult to generalize. If the generalization were straightforward, the situation in imperfect-information games would by now likely be closer to that in perfect-information games or single-agent RL, where many of the state-of-the-art algorithms are very general [Silver et al., 2017; Schrittwieser et al., 2019; Badia et al., 2020]. This suggests that using a model which keeps track of public information by default would have significant benefits.

Fortunately, as witnessed by the examples (a), (b), and (c), the information about which knowledge is public is inherently a part of the description of many games and real-world situations. In other words, public knowledge is typically already a part of a problem's natural definition; the model we propose merely preserves this information while models used in the past discard it.

2.2 Description of the Basic Model

Informally, the model we are about to describe captures a situation where multiple actors take actions - possibly simultaneously - which influence how the world's state changes. The new world-state might be more or less desirable for individual actors, which is captured by corresponding reward functions. Rather than having full knowledge of the world state, the agents perceive it through observations. These are further "factored", such that if some information is public, each agent will know that everybody else also has access to it. In the following paragraph, ↪→ indicates a partial function, defined on a subset of the stated domain.

A factored-observation stochastic game (FOSG) is a tuple G = 〈N , W, p, winit , A, T , R, O〉, where N is the player set, W is the set of world states, winit is a designated initial state, p : W → 2N is a player function, A is the space of joint actions, T : W ×A ↪→∆W is the transition function, R : W×A ↪→ RN is the reward function, O : W×A×W ↪→ O is the observation function, and we have:

• N = {1, . . . ,N} for some N ∈ N.
• W is compact. For formal convenience, we assume that p(winit ) = ∅.
• A = ∏i∈N Ai, where each Ai is an arbitrary set of i's actions.
• For each i ∈ p(w), Ai(w) ⊂ Ai denotes a nonempty compact set of i's (legal) actions at w. We denote A(w) := ∏i∈p(w) Ai(w).
• We denote Ai(w) := {noop} for i /∈ p(w), which allows us to identify each a ∈ A(w) with an element of ∏i∈N Ai(w) by appending to it the appropriate number of noop actions.
• The transition probabilities T (w, a) ∈ ∆W, a ∈ A(w), are defined for all w ∈ W with non-empty p(w) and for some w with no active players.
• A world state with p(w) = ∅ and undefined T (w, a) is called terminal.
• R(w, a) = (Ri(w, a))i∈N for each non-terminal state w and a ∈ A(w).
• O is factored into private observations and public observations as O = (Opriv(1), . . . , Opriv(N), Opub).
• O = ∏i∈N Opriv(i) ×Opub, where O(·) are arbitrary

• sets (of possible observations).
• We assume that O(·)(w, a, w′ ) ∈ O(·) is defined for every non-terminal w, a ∈ A(w), and w′ from the support of T (w, a).

The game proceeds as follows: It starts in the initial state winit . In each state, each active player i ∈ p(w) learns which actions are legal for them (either by deduction or by being explicitly told) and selects ai ∈ Ai(w). (While the player obviously knows which action they took, they often will not know the actions of the other players, or possibly not even which of them were active at w.) The game then transitions to a new state w′ , drawn from the distribution T (w, a) that corresponds to the joint action a = (ai)i∈p(w). This generates the observation O(w, a, w′ ), from which each player receives Oi(w, a,w′ ) := (Opriv(i)(w, a,w′ ),Opub(w, a,w′ )) ∈ Oi (i.e., the public observation together with their private observation, in manner which allows distinguishing between the two). Finally, each player is assigned the reward Ri(w, a). However, a player might not know how much reward they received, unless this is - explicitly or implicitly - a part of Oi. This process repeats until a terminal state is reached. The goal of each player is to maximize the sum of rewards Ri(w, a, w′ ) obtained during the game.

Acknowledgements

We are grateful to Tomáš Gavenˇciak, Karel Horák, and Marc Lanctot for discussions related to an earlier version of this paper. This work was supported by the Czech Science Foundation grants no. 18-27483Y and no. GA22-26655S, and the Czech Ministry of Education Youth and Sports grant RCI no. CZ.02.1.01/0.0/0.0/16019/0000765.