[name=Theorem]thm [name=Lemma]lem [name=Proposition]pro [name=Corollary]cor

# On Convex Optimal Value Functions For POSGs

Rafael F. Cunha
University of Groningen, Bernoulli Institute, The Netherlands
<EMAIL_ADDRESS>
Jacopo Castellini
Univ Lyon, INSA Lyon, Inria, CITI, EA3720, 69621 Villeurbanne, France
<EMAIL_ADDRESS>
Johan Peralez
Univ Lyon, INSA Lyon, Inria, CITI, EA3720, 69621 Villeurbanne, France
<EMAIL_ADDRESS>
Jilles S. Dibangoye
University of Groningen, Bernoulli Institute, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

Multi-agent planning and reinforcement learning can be challenging when agents
cannot see the state of the world or communicate with each other due to
communication costs, latency, or noise. Partially Observable Stochastic Games
(POSGs) provide a mathematical framework for modelling such scenarios. This
paper aims to improve the efficiency of planning and reinforcement learning
algorithms for POSGs by identifying the underlying structure of optimal state-
value functions. The approach involves reformulating the original game from
the perspective of a trusted third party who plans on behalf of the agents
simultaneously. From this viewpoint, the original POSGs can be viewed as
Markov games where states are occupancy states, i.e., posterior probability
distributions over the hidden states of the world and the stream of actions
and observations that agents have experienced so far. This study mainly proves
that the optimal state-value function is a convex function of occupancy states
expressed on an appropriate basis in all zero-sum, common-payoff, and
Stackelberg POSGs.

##  1 Introduction

The Partially Observable Stochastic Game (POSG) framework is widely used for
formalizing problems in multi-agent sequential decision-making (Harsanyi,
1997; Hansen et al., 2004; Shoham and Leyton-Brown, 2008). This framework is
designed to address situations where multiple agents interact with each other
to control a dynamic environment and optimize their individual preferences
despite stochasticity and sensing uncertainty. Recently, researchers have
focused on the subclasses of zero-sum, common-payoff, and Stackelberg POSGs
(_st_ -POSGs) (Von Neumann and Morgenstern, 1944; Bernstein et al., 2000;
Tambe, 2011). Various approaches have been developed to solve POSGs, with many
relying on dynamic programming. These approaches aim to find a solution for
the original game by recursively finding solutions for its subgames. However,
often solutions of interest exist within a continuum, which requires
leveraging uniform continuity properties of optimal state-value functions.
Unfortunately, there is a lack of knowledge regarding the uniform continuity
properties of optimal state-value functions, which can make it challenging to
generalize knowledge from one partial solution to another, restricting the
efficiency of existing techniques.

Recent advancements in studying optimal state-value functions for games have
showcased innovative ways to generalize knowledge from past experiences. These
approaches utilize uniform continuity properties, providing insights into the
underlying structure of optimal state-value functions for specific games. The
structural analysis of optimal state-value functions can be traced back to the
seventies, with Smallwood and Sondik (1973) demonstrating that the optimal
state-value functions of finite-horizon Partially Observable Markov Decision
Processes (POMDPs) are piecewise linear and convex functions of belief states.
This discovery paved the way for a collection of efficient algorithms,
including those developed by Smith and Simmons (2005); Pineau et al. (2006);
Shani et al. (2013). As such, many authors have since investigated the
underlying structure of optimal value functions for subclasses of finite-
horizon POSGs. For instance, Gmytrasiewicz and Doshi (2005) have shown that
piecewise linearity and convexity of optimal state-value functions of belief
states extends to Interactive Partially Observable Markov Decision Processes
(I-POMDPs). Fehr et al. (2018) demonstrates that POMDPs with Lipschitz reward
functions have Lipschitz-continuous near-optimal value functions. Similarly,
Dibangoye et al. (2012, 2016) have proven that the optimal state-value
functions of finite-horizon common-payoff POSGs (_dec_ -POMDPs) are piecewise
linear and convex functions of occupancy states on the standard basis. In
finite-horizon one-sided zero-sum POSGs (_zs_ -POSGs), Sorin (2003); Horák et
al. (2017) have demonstrated the convexity of the optimal state-value function
over belief states. Moreover, Wiggers et al. (2016) have established the
linearity of optimal state-value functions of finite-horizon best-response
problems in the space of distributions over the histories of an agent.
Recently, Delage et al. (2023) have complemented this linearity property by
demonstrating the Lipchitz-continuity, which generalizes values between
occupancy states for finite-horizon _zs_ -POSGs.

It is worth noting that uniform continuity properties are not all equal. For
instance, the linearity property highlighted in Wiggers et al. (2016) does not
facilitate the generalization of values from one experience to another.
Utilizing this property in isolation proves challenging. Undoubtedly, the
Lipchitz-continuity property from Delage et al. (2023) is useful in
generalizing values across different experiences. However, it is worth noting
that this approach can sometimes result in poor generalization. Generally, the
stronger the uniform continuity property, the better. Unfortunately, there is
no constructive approach for revealing the underlying structure of optimal
state-value functions. Presently, exhibiting a uniform continuity property
appears more like an art than science. This paper introduces a methodology for
identifying the underlying structure of optimal state-value functions to
address this bottleneck and enhance the ability to create efficient planning
and reinforcement learning algorithms for finite-horizon POSGs. The approach
involves reformulating the original game from the perspective of a trusted
third party who plans on behalf of the agents simultaneously. From this
viewpoint, the original finite-horizon POSGs can be viewed as finite-horizon
Markov games where states are occupancy states, which are posterior
probability distributions over the hidden states of the world and the stream
of actions and observations that agents have experienced so far (i.e., their
private histories).

Section 2 ✓ Original models ✗ Optimal decision-making POSG $M$(master
game)$\mathbf{1}$$\mathbf{1}$POMDP $M(a_{0:}^{\neg i})$(slave
game)$\mathbf{*}$$\mathbf{*}$ Sections 4 and 5 ✓ Optimal decision-making ✓
Uniform continuity OMG $M^{\prime\prime}$(master
game)$\mathbf{1}$$\mathbf{1}$MDP $M^{\prime\prime}(a_{0:}^{\neg i})$(slave
game)$\mathbf{*}$$\mathbf{*}$ Section 3 ✓ Optimal decision-making ✗ Uniform
continuity PTMG $M^{\prime}$(master game)$\mathbf{1}$$\mathbf{1}$MDP
$M^{\prime}(a_{0:}^{\neg i})$(slave game)$\mathbf{*}$$\mathbf{*}$Central
planner raw viewpointCentral planner concise viewpoint Figure 1: The paper
employs a three-step transformation methodology to convert original games into
appropriate representations for optimal decision-making. The methodology
involves the use of several game-theoretic models, including Partially
Observable Stochastic Game (POSG), Partially Observable Markov Decision
Process (POMDP), Markov Decision Process (MDP), Plan-Time Markov Game (PTMG),
and Occupancy-State Markov Game (OMG). Best viewed in color.

#### Contributions.

This study provides a proof that the optimal state-value function for the
best-response problem, specifically for a slave game, is piecewise linear and
convex over occupancy states when expressed on the standard basis, and linear
over occupancy states when expressed appropriately. Additionally, the study
presents the uniform continuity properties of optimal state-value functions
for certain well-known subclasses of finite-horizon POSGs, which are master
games. Specifically, when expressed appropriately, the optimal state-value
functions for two subclasses of POSGs, namely zs-POSGs and st-POSGs, are
convex over occupancy states. These uniform continuity properties are stronger
than the previous ones. Moreover, the study demonstrates that the optimal
state-value functions of dec-POMDPs are piecewise linear and convex over
occupancy states when expressed on the standard basis—a property originally
established by Dibangoye et al. (2016). We instead provide a simpler proof.
The authors emphasize the tightness of these properties, which is evidenced by
the fact that they match pre-existing results in narrower settings under
further assumptions. The study highlights a methodology to reveal uniform
continuity properties of optimal value functions of master games, which is
perhaps the most significant takeaway of this paper. This methodology
comprises a series of transformations that produce three models for master and
slave games, each sufficient to solve the others optimally. However, the last
master and slave game formulations make it possible to exhibit uniform
continuity properties that were not possible with the previous ones, yet the
sufficiency of the former required the introduction of the latter. The key to
establishing uniform continuity properties for master games appears to be the
ability to appropriately express the optimal value function of the master
games with those of the slave games. The authors hope that these findings will
serve as a foundation for more efficient planning and reinforcement learning
algorithms to exploit the structural properties inherent in POSGs.

The current paper is structured as follows, with each section delving into a
unique representation of master and slave games, as illustrated in Figure 1.
Section 2 presents a formal description of these games, along with the
relevant solution concepts. It also introduces the notations used throughout
the document, preliminary properties, and Bellman’s equations for the state-
and action-value functions under fixed joint policies. In Section 3, a
reformulation of master and slave games from the perspective of a trusted
third party (or central planner) who plans on behalf of the agents is
presented, providing a framework for optimal decision-making at the planning
phase and decentralized decision-making at the execution phase. Section 4
examines the connections between master and slave games through summaries of
the central planner’s knowledge, namely occupancy states. Finally, the main
results of this paper are provided in Section 5. The convexity properties of
the optimal state-value functions of all slave and master games are presented
here. The paper concludes with a discussion on the potential impact of the
current findings.

##  2 Background

This section formally describes master and slave games and the solution
concepts of interest. Additionally, this section introduces the notation used
throughout the document, preliminary properties, and Bellman’s equations for
the state- and action-value functions.

decision 1perception 1decision 2perception 2agentsenvironment Figure 2:
Illustration of agents and their environment for the tiger problem.

#### Notation.

This paper uses uppercase letter $Y$ to refer to random variables and
lowercase letter $y$ to refer to their realizations. The corresponding domains
are represented by calligraphic uppercase letter $\mathcal{Y}$. When we want
to represent a vector containing all values of $y$ between two integers
$t_{0}$ and $t_{1}$, we use the notation $y_{t_{0}:t_{1}}$. Similarly,
$y^{i_{0}:i_{1}}$ represents a shorthand notation for the vector
$(y^{i_{0}},\ldots,y^{i_{1}})$, where $i_{0}$ and $i_{1}$ are integers
satisfying $i_{0}\leq i_{1}$. If $i_{1}<i_{0}$, we represent this as
$y^{i_{1}:i_{0}}\doteq\emptyset$. However, when we want to represent the
Cartesian product of all values of domains
$\mathcal{Y}^{i_{0}},\ldots,\mathcal{Y}^{i_{1}}$ between two integers $i_{0}$
and $i_{1}$, we use the notation
$\mathcal{Y}^{i_{0}:i_{1}}\doteq\mathcal{Y}^{i_{0}}\times\ldots\times\mathcal{Y}^{i_{1}}$.
We use subscripts to represent control interval indexes and superscripts to
index agents. The probability of an event is denoted by $\Pr\\{\cdot\\}$, and
the expectation of a random variable is represented by
$\mathbb{E}\\{\cdot\\}$. When dealing with a finite set $\mathcal{Y}$, we
represent the cardinality of $\mathcal{Y}$ with $|\mathcal{Y}|$, and
$\mathbb{N}_{\leq|\mathcal{Y}|}$ as a set of integers ranging from 0 to
$|\mathcal{Y}|$. Additionally, $\mathcal{P}(\mathcal{Y})$ represents the
$(|\mathcal{Y}|-1)$-dimensional real simplex. The set-theoretic support of a
function $f\colon\mathcal{Y}\to\mathbb{R}$ is represented by
$\mathtt{supp}(f)$, which is the set of points in $\mathcal{Y}$ where $f$ is
non-zero. We use the short-hand notations $y^{i_{0}:}$ and $y^{:i_{1}}$ to
represent the vector $y^{i_{0}:n}$ and $y^{0:i_{1}}$, respectively, where
$i_{0}$ and $i_{1}$ are integers satisfying $i_{0},i_{1}\in\mathbb{N}_{\leq
n}$. Finally, we use the Kronecker delta
$\delta_{\cdot}(\cdot)\colon\mathcal{Y}_{0}\times\mathcal{Y}_{1}\to\\{0,1\\}$
in our calculations.

###  2.1 Master Games as POSGs

This subsection will discuss finite-horizon POSGs and their solution concepts,
including the Bellman’s equations. To help readers better understand the
concepts presented in this paper, we will use a simple toy master game called
the tiger problem, illustrated in Figure 2.

######  Example 1.

In the tiger problem, there are two doors, one hiding a tiger named Hobbes,
and the other hiding a pile of gold. Two agents, Calvin and Susie, aim to
determine which door contains the treasure so that they can claim it as
quickly as possible. The tiger can be on the left, referred to as
$x_{\textsc{tl}}$, or on the right, referred to as $x_{\textsc{tr}}$. The
agents can perform one of three actions: $u_{\textsc{ol}}$ (open left),
$u_{\textsc{or}}$ (open right), and $u_{\textsc{l}}$ (listen). Even after
opening a door, there are only two possible observations for each agent: to
hear the tiger on the left, $z_{\textsc{hl}}$, or to hear the tiger on the
right, $z_{\textsc{hr}}$. If both agents perform $u_{\textsc{l}}$, the state
of the world remains unchanged. However, any other joint action results in a
transition to either state with a probability of $0.5$, effectively resetting
the problem. When the world is in state $x_{\textsc{tl}}$, the joint action
$(u_{\textsc{l}},u_{\textsc{l}})$ results in observation $z_{\textsc{hl}}$ for
any agent with a probability of 0.85 and observation $z_{\textsc{hr}}$ with a
probability of 0.15. This applies similarly for state $x_{\textsc{tr}}$.
Regardless of the state, all other joint actions result in either observation
with a probability of 0.5.

$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$StatestartStateStateObservation1
Reward1Observation1 Reward1Observation1 Reward1Observation2
Reward2Observation2 Reward2Observation2
Reward2Action1Action1Action2Action2Time$t$$t$+$1$$t$+$2$HiddenAgent $1$’s
viewpointAgent $2$’s
viewpoint$p^{u}_{x,x^{\prime}}$$p^{u}_{x,x^{\prime}}$$p^{u}_{x,x^{\prime}}$
Figure 3: A graphical model of a two-agent, partially observable stochastic
game.

In a POSG, schematically depicted in Figure 3, agents begin with uncertain
knowledge about the game’s initial belief state, which is determined by the
initial belief state $s_{0}$, i.e., a distribution over hidden states. At each
time step, the game is in a particular state $x$, and each agent $i$ can
choose an action $u^{i}$ from their action space. The game then responds by
transitioning to a new state $x^{\prime}$, based on the actions of all agents
$u$, and a transition probability distribution
$(p^{u}_{x,x^{\prime}})_{x,x^{\prime}\in\mathcal{X},u\in\mathcal{U}}$.
Additionally, each agent $i$ receives an immediate reward $r^{i}_{xu}$ and
individual observation $z^{i}$, based on joint observation $z$ and an
observation probability distribution
$(p^{u,z}_{x^{\prime}})_{x^{\prime}\in\mathcal{X},u\in\mathcal{U},z\in\mathcal{Z}}$,
providing them with potentially incomplete and noisy knowledge about the
game’s current state $x^{\prime}$. This process continues until the horizon is
exhausted.

######  Definition 1.

A $n$-agent, partially observable stochastic game (POSG) is given by a tuple
$M\doteq(\mathcal{X},\mathcal{U},\mathcal{Z},p,r)$. The set $\mathcal{X}$
represents a finite collection of hidden states, denoted as $x$. The finite
set of joint actions is denoted as $\mathcal{U}=\mathcal{U}^{1:}$, and the
actions taken by the agents are denoted as $u=u^{1:n}$. The finite set of
observations is denoted as $\mathcal{Z}=\mathcal{Z}^{1:}$, and the
observations made by the agents are denoted as $z=z^{1:n}$. The transition
function $p_{x,x^{\prime}}^{u,z}$ is given by $p^{u}_{x,x^{\prime}}\cdot
p^{u,z}_{x^{\prime}}$, and specifies the probability of the process state
being $x^{\prime}$ and having observation $z$ after taking action $u$ in
hidden state $x$. The reward function $r_{x,u}$ specifies the reward vector
$r^{1:n}_{x,u}$ received by the agents after they take joint action $u$ in
state $x$.

#### Assumptions.

Throughout the paper, we assume that the process described by $M$ operates
under the following conditions: the observation space of each agent $i$ is
made up of a public subspace and a private subspace, denoted as
$\mathcal{Z}^{i}=\mathcal{W}\times\tilde{\mathcal{Z}}^{i}$, cf. (Kovařìk et
al., 2022). The public observations are accessible to all agents.
Additionally, rewards are bounded on both sides, with a positive scalar $c$
such that $\|r^{\cdot}_{\cdot,\cdot}\|_{\infty}\leq c$. The planning horizon,
referred to as $\ell$, is finite. However, if an infinite-horizon solution is
required, any $\ell$-horizon solution where
$\ell=\lceil\log_{\gamma}{({(1-\gamma)\epsilon}/{c})}\rceil$ can provide an
$\epsilon$-close approximation to any infinite-horizon solution. This finding
holds for a discount factor $\gamma\in[0,1)$ and scalar $\epsilon>0$.

$\varsigma_{0}^{i}$$\varsigma_{1}^{i,1}$$\varsigma_{1}^{i,|\mathcal{U}^{i}||\mathcal{Z}^{i}|}$$\cdots$$\cdots$_depth_
$\ell$_branching_ $|\mathcal{U}^{i}||\mathcal{Z}^{i}|$ Figure 4: A $\ell$-step
policy tree captures a sequence of $\ell$ time steps, each of which can be
conditioned on the outcome of previous decisions. Each node is labelled with
the decision made if it is reached.

The goal of solving game $M$ is to identify a joint policy that satisfies a
specific criterion based on the problem at hand. This involves determining a
series of individual decision rules for each agent, denoted by
${a}^{1:n}_{0:\ell-1}$ or simply ${a}_{0:}$. Under a joint policy, every time
step $t$, each agent $i$ follows a unique private decision rule
${a}^{i}_{t}\colon o^{i}_{t}\mapsto\varsigma^{i}_{t}$, where
$\varsigma^{i}_{t}\in\mathcal{P}(\mathcal{U}^{i})$, which is dependent on the
$t$-step private history $o^{i}_{t}\doteq(u^{i}_{0:t-1},z^{i}_{1:t})$, with
the first private history being $o^{i}_{0}\doteq\emptyset$, as shown in Figure
4. Every joint policy $a_{0:}$ will have a performance index induced by state-
value functions $\upsilon^{a_{0:}}_{M,\gamma,0:}$ that are defined as follows.

######  Definition 2.

For every agent $i$, the $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M,\gamma,t}\colon\mathcal{X}\times\mathcal{O}_{t}\to\mathbb{R}$
under the joint policy $a_{t:}$ is given by: for any arbitrary hidden state
$x_{t}$ and joint history $o_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle\doteq\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|x_{t},o_{t},a_{t:}\\},$

with boundary condition $\upsilon^{\cdot}_{M,\gamma,\ell}(\cdot)\doteq 0$.

One can extend Definition 2 by abuse of notation to hold over posterior
probability distributions over hidden states and histories as follows.

######  Definition 3.

For every agent $i$, the $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M,\gamma,t}\colon\mathcal{P}(\mathcal{X}\times\mathcal{O}_{t})\to\mathbb{R}$
under joint policy $a_{t:}$ is given by: for any distribution $s_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M,\gamma,t}(s_{t})$
$\displaystyle\doteq\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|s_{t},a_{t:}\\},$

with boundary condition $\upsilon^{i,\cdot}_{M,\gamma,\ell}(\cdot)\doteq 0$.

The performance index for joint policy $a_{0:}$ at initial belief state
$s_{0}$ is given by $\upsilon^{a_{0:}}_{M,\gamma,0}(s_{0})$. As discussed
below, defining the Bellman’s equations underlying state-value functions under
a fixed joint policy will prove useful.

[] The $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M,\gamma,t}\colon\mathcal{X}\times\mathcal{O}_{t}\to\mathbb{R}$
satisfies a recursion formula, known as Bellman’s equations, i.e., for any
arbitrary hidden state $x_{t}$ and joint history $o_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle=\textstyle\sum_{u_{t}\in\mathcal{U}}~{}a_{t}(u_{t}|o_{t})\cdot
q^{i,a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t})$ $\displaystyle
q^{i,a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t})$ $\displaystyle\doteq\textstyle
r^{i}_{x_{t}u_{t}}+\gamma\sum_{x_{t+1}\in\mathcal{X}}\sum_{z\in\mathcal{Z}}p_{x_{t},x_{t+1}}^{u_{t},z_{t+1}}\cdot\upsilon^{i,a_{t+1:}}_{M,\gamma,t+1}(x_{t+1},(o_{t},u_{t},z_{t+1})),$
(1)

with boundary condition
$\upsilon^{i,\cdot}_{M,\gamma,\ell}(\cdot)=q^{i,\cdot}_{M,\gamma,\ell}(\cdot)\doteq
0$.

###### Proof.

The proof proceeds by induction. It is obviously true at the last time step
$t=\ell-1$, i.e., for every hidden state $x_{t}$, and joint history $o_{t}$,

$\displaystyle\upsilon^{a_{\ell-1}}_{M,\gamma,\ell-1}(x_{\ell-1},o_{\ell-1})$
$\displaystyle\doteq\mathbb{E}\\{r_{x_{\ell-1},U_{\ell-1}}|x_{\ell-1},o_{\ell-1},a_{\ell-1}\\}.$

Expanding the expectation over joint actions results in the following
expression:

$\displaystyle\upsilon^{a_{\ell-1}}_{M,\gamma,\ell-1}(x_{\ell-1},o_{\ell-1})$
$\displaystyle={\textstyle\sum_{u_{\ell-1}\in\mathcal{U}}~{}a_{\ell-1}(u_{\ell-1}|o_{\ell-1})\cdot
q^{\cdot}_{M,\gamma,\ell-1}(x_{\ell-1},o_{\ell-1},u_{\ell-1})},$

where $q^{\cdot}_{M,\gamma,\ell-1}(x_{\ell-1},o_{\ell-1},u_{\ell-1})\doteq
r_{x_{\ell-1},u_{\ell-1}}$. Suppose the induction hypothesis holds from time
step $t+1$ onward. The recursive scheme holds for time step $t$, for hidden
state $x_{t}$ and joint history $o_{t}$,

$\displaystyle\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle\doteq\textstyle{\mathbb{E}\left\\{\sum_{\tau=t}^{\ell-1}~{}\gamma^{\tau-t}\cdot
r_{X_{\tau},U_{\tau}}|x_{t},o_{t},a_{t:}\right\\}}.$

Splitting the immediate reward and the future rewards leads to the following
expression:

$\displaystyle\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle=\textstyle{\mathbb{E}\left\\{r_{x_{t},U_{t}}+\gamma\sum_{\tau=t+1}^{\ell-1}~{}\gamma^{\tau-t-1}\cdot
r_{X_{\tau},U_{\tau}}|x_{t},o_{t},a_{t:}\right\\}}.$

Expanding the expectation of the future rewards over all histories at time
step $t+1$ yields:

$\displaystyle\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle=\textstyle\mathbb{E}\left\\{r_{x_{t},U_{t}}+\gamma\mathbb{E}{\left\\{\sum_{\tau=t+1}^{\ell-1}~{}\gamma^{\tau-t-1}\cdot
r_{X_{\tau},U_{\tau}}|X_{t+1},(o_{t},U_{t},Z_{t+1}),a_{t+1:}\right\\}}|x_{t},o_{t},a_{t}\right\\}.$

The inner expectation is the state-value function of hidden states and
histories at time step $t+1$, by Definition 2 of
$\upsilon^{a_{t+1:}}_{M,\gamma,t+1}$, i.e.,

$\displaystyle\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle=\textstyle\mathbb{E}\\{r_{x_{t},U_{t}}+\gamma\upsilon^{a_{t+1:}}_{M,\gamma,t+1}(X_{t+1},(o_{t},U_{t},Z_{t+1}))|x_{t},o_{t},a_{t}\\}.$

The application of definition of $q^{a_{t+1:}}_{M,\gamma,t}$ in (1) produces
the following expression:

$\displaystyle\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle=\textstyle\mathbb{E}\\{q^{a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},U_{t})|x_{t},o_{t},a_{t}\\}.$

Finally, the expansion of the expectation over joint actions produces the
target expression:

$\displaystyle\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle=\textstyle\sum_{u_{t}\in\mathcal{U}}a_{t}(u_{t}|o_{t})\cdot
q^{a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t}).$

Hence, the proof holds for any arbitrary time step $t$. Which ends the proof.
∎

###  2.2 Solution Concepts

After learning how to calculate the state- and action-value functions for a
fixed joint policy, we also need to determine how to identify a suitable
policy for each agent based on state-value functions. Unfortunately, no
universal definition of good policies can be applied to all multi-agent
sequential decision-making problems. Instead, this paper proposes solution
concepts that refine the notion of a best-response policy, including but not
limited to Nash Equilibrium, optimal joint policy, or strong Stackelberg joint
policy. To better understand the concept of best response, consider the
scenario where an agent knows how other agents will act. In this case, the
multi-agent sequential decision-making problem becomes simple, and the agent
is left with a single-agent problem of selecting the utility-maximizing policy
based on the other agents’ fixed policies, i.e., a best-response policy.

######  Definition 4.

A best-response policy of agent $i$ to joint policy $a^{\neg
i}_{0:}\in\mathcal{A}_{0:}^{\neg i}$ of the other agents is a policy
$a^{i}_{0:}\in\mathcal{A}_{0:}^{i}$ satisfying
$\upsilon^{i,(a^{i}_{0:},a^{\neg
i}_{0:})}_{M,\gamma,0}(s_{0})\geq\upsilon^{i,(\underline{a}^{i}_{0:},a^{\neg
i}_{0:})}_{M,\gamma,0}(s_{0})$, for all
$\underline{a}^{i}_{0:}\in\mathcal{A}_{0:}^{i}$. Set
$\mathcal{A}_{0:}^{i}(a^{\neg i}_{0:})$ of best-responses w.r.t. $a^{\neg
i}_{0:}$ is made of all the possible randomized policies and is thus infinite
except in degenerate cases where a unique (deterministic) best-response, i.e.,

$\displaystyle\mathcal{A}_{0:}^{i}(a^{\neg i}_{0:})$
$\displaystyle\doteq\\{a^{i}_{0:}\in\mathcal{A}_{0:}^{i}|\upsilon^{i,(a^{i}_{0:},a^{\neg
i}_{0:})}_{M,\gamma,0}(s_{0})\geq\upsilon^{i,(\underline{a}^{i}_{0:},a^{\neg
i}_{0:})}_{M,\gamma,0}(s_{0}),\forall\underline{a}^{i}_{0:}\in\mathcal{A}_{0:}^{i}\\}.$

The properties of best-response policies are numerous and significant.
Firstly, they yield the same performance index for a specific joint policy
$a^{\neg i}_{0:}$ of the other agents. Consequently, deterministic (or pure)
policies are just as effective as randomized policies. Additionally, if a
randomized policy is a best-response, every deterministic policy within its
support must also be a best response. Perfect recall ensures that these
properties hold, regardless of whether the best-response is deterministic,
mixed, or stochastic.

Up to this point, it is assumed that an agent knows other agents’ policies.
However, an agent may not know how other agents will act. Nevertheless, it is
possible to utilize the concept of best-response to define all solution
concepts of interest in this paper. A notable example of such concepts is the
most central notion in non-cooperative game theory, namely the Nash
Equilibrium. A formal definition follows.

######  Definition 5.

A joint policy $a_{0:}\in\mathcal{A}_{0:}$ is a Nash Equilibrium if the policy
of any agent is a best response to those of the other agents, i.e.,
$a^{i}_{0:}\in\mathcal{A}_{0:}^{i}(a^{\neg i}_{0:})$ for every agent $i$.

A Nash Equilibrium exists in any game with a finite set of agents and a finite
deterministic policy space per agent. A Nash equilibrium refers to a stable
joint policy where no agent is willing to deviate from its policy, provided
they know the policies other agents will follow. Multiple Nash equilibria can
exist, all of which are self-enforcing if agents adhere to such behaviour.
Each agent’s best interest is to stick with its policy. However, it is
important to note that these equilibria may not be optimal for the agents,
meaning they may not provide optimal values for any agent and can often offer
significantly different values. All solution concepts considered onward are
refinements of Nash Equilibria. Optimization problems determining the best-
response policies are slave games for a master game. To solve a master game,
it is necessary to address a multitude of slave games, which may potentially
be infinite in number. This is due to numerous Nash equilibria involving
mutually beneficial best-response policies.

In this paper, we will be placing a particular emphasis on three significant
subclasses of POSGs: zero-sum POSG (zs-POSG), common-payoff POSG (dec-POMDP),
and Stackelberg POSG (st-POSG). Our primary objective is to exhibit the
underlying structure of their optimal value functions.

######  Definition 6.

A two-player POSG $M$ is said to be a zs-POSG if the sum of the rewards of
both players equals zero, i.e., $r^{1}=-r^{2}$.

Optimally solving zs-POSG $M$ aims at finding a Nash equilibrium.
Interestingly, every Nash equilibrium of a zs-POSG $M$ will yield the same
performance index at the initial belief state $s_{0}$:
$\upsilon_{M,\gamma,0}^{i,*}(s_{0})\doteq\textstyle\max_{a^{i}_{0:}\in\mathcal{A}_{0:}^{i}}\min_{a^{\neg
i}_{0:}\in\mathcal{A}_{0:}^{\neg i}}\upsilon_{M,\gamma,0}^{i,a_{0:}}(s_{0})$.

######  Definition 7.

A $n$-player POSG $M$ is a dec-POMDP if all players have the same rewards,
i.e., $r^{1}=\ldots=r^{n}$.

Optimally solving dec-POMDP $M$ aims at finding an _optimal joint policy_ ,
i.e., a Nash equilibrium whose performance index at the initial belief state
$s_{0}$ is:
$\upsilon_{M,\gamma,0}^{*}(s_{0})\doteq\textstyle\max_{a^{1:}_{0:}\in\mathcal{A}_{0:}^{1:}}\upsilon_{M,\gamma,0}^{a_{0:}}(s_{0})$.

######  Definition 8.

A two-player POSG $M$ is a st-POSG if (the leader) player $1$ publicly
announces its policy to (the follower) player $2$ beforehand.

Optimally solving st-POSG $M$ aims at finding a _strong Stackelberg
equilibrium_ , i.e., a Nash equilibrium whose performance index is:
$\upsilon_{M,\gamma,0}^{1,*}(s_{0})\doteq\textstyle\max_{a^{1}_{0:}\in\mathcal{A}_{0:}^{1}}\max_{a^{2}_{0:}\in\mathcal{A}_{0:}^{2}(a^{1}_{0:})}\upsilon_{M,\gamma,0}^{1,a_{0:}}(s_{0})$.
It is worth noting that solving a POSG optimally, and in particular solving
zs-POSG, dec-POMDP, and st-POSG optimally, aims at finding a Nash equilibrium.

###  2.3 Slave Games As POMDPs

In this subsection, we will formally introduce the concept of slave games as a
mean to determine a best-response policy for an agent given a master game
expressed as a POSG alongside the joint policy that the other agents follow.
We will also delve into the expression of slave games as POMDPs and their
corresponding solution concepts, including Bellman’s optimality equations. To
aid comprehension, we will utilize a particular scenario of the tiger problem
as an example, depicted in Figure 5.

My policy is $a^{\neg i}_{0:}$ I know $a^{\neg i}_{0:}$ is Calvin’s policy
decision 1perception 1decision 2perception 2agentsenvironment Figure 5:
Illustration of agents and their environment for the tiger problem where
Calvin acts according to a public and fixed policy.

######  Example 2.

In this particular scenario of the tiger problem, Calvin follows a
predetermined policy $a_{0:}^{\neg i}$, while Susie is aware of this.
Nevertheless, Susie must still identify the correct door to claim the treasure
as quickly as possible, cf. Figure 5.

######  Definition 9.

Consider the master game $M$. A slave game $M(a^{\neg i}_{0:})$ is
characterized by the tuple
$(\mathcal{X},\mathcal{O},\mathcal{U}^{i},\mathcal{Z}^{i},p,r^{i})$. Here,
$\mathcal{X}$ represents a finite space of hidden states, $\mathcal{O}$
denotes the space of hidden joint histories, $\mathcal{U}^{i}$ is the finite
action space, and $\mathcal{Z}^{i}$ represents the finite observation space.
All other aspects of $M(a^{\neg i}_{0:})$ are consistent with those in $M$.

Let us consider master game $M$. Within $M$, there exists a slave game denoted
by $M(a^{\neg i}_{0:})$. Agent $i$ is part of a POMDP, as depicted in Figure
6. At each time step, the state of the world is determined by the underlying
state in $M$ and the joint history of all agents. However, agent $i$ can only
access its private history, not the underlying state nor the histories of the
other agents. Regardless, agent $i$ can still utilize their history to make
informed decisions, which results in an immediate reward signal and a new
observation. This process repeats in a new underlying state and joint history
at each successive time step until the game concludes.

$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$$p^{u,z}_{x^{\prime}}$History
StatestartHistory StateHistory StateObservationi RewardiObservationi
RewardiObservationi RewardiActioniActioniTime$t$$t$+$1$$t$+$2$HiddenAny agent
$i$’s
viewpoint$p^{u}_{x,x^{\prime}}$$p^{u}_{x,x^{\prime}}$$p^{u}_{x,x^{\prime}}$
Figure 6: The graphical model of a slave game as a partially observable Markov
decision process from any agent $i$’s viewpoint. Blue circles represent the
states of the problem, including the state of the underlying environment and
the joint histories. Green circles denote both private observations and
rewards agent $i$ received.Finally, red circles are private actions that agent
$i$ took.

The goal of solving the slave game $M(a^{\neg i}_{0:})$ is to find a best-
response policy $a^{i}_{0:}$ for agent $i$. A best-response policy will
maximize the expected $\gamma$-discounted cumulative reward, starting from the
initial belief state $s_{0}$, providing the other agents act according to
$a^{\neg i}_{0:}$. Every best-response policy will have the same performance
index at the initial belief state $s_{0}$.

######  Definition 10.

Consider a slave game $M(a^{\neg i}_{0:})$ w.r.t. the master game $M$. The
$t$-step optimal value function $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}\colon\mathcal{O}^{i}_{t}\to\mathbb{R}$ of $M(a^{\neg
i}_{0:})$ is given by: for any arbitrary private history $o^{i}_{t}$,

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle\doteq\textstyle\max_{a^{i}_{t:}\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{\textstyle{\sum_{\tau=t}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|o^{i}_{t},a^{i}_{t:},a^{\neg i}_{0:}\\}.$

with boundary condition $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,\ell}^{i}(\cdot)\doteq 0$.

One can extend Definition 10 by abuse of notation to hold over posterior
probability distributions over private histories of agent $i$, namely marginal
occupancy states, as follows.

######  Definition 11.

Consider a slave game $M(a^{\neg i}_{0:})$ w.r.t. the master game $M$. The
$t$-step optimal value function $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}\colon\mathcal{P}(\mathcal{O}^{i}_{t})\to\mathbb{R}$ of
any best-response policy is given by: for any arbitrary marginal occupancy
state $s^{\mathtt{m},i}_{t}$,

$\displaystyle\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(s^{\mathtt{m},i}_{t})$
$\displaystyle\doteq\textstyle\max_{a^{i}_{t:}\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{\textstyle{\sum_{\tau=t}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|s^{\mathtt{m},i}_{t},a^{i}_{t:},a^{\neg i}_{0:}\\}.$

with boundary condition $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,\ell}^{i}(\cdot)\doteq 0$.

When dealing with a slave game formulated as a POMDP, it is important to note
that the agent only has access to partial information about the game state.
Therefore, relying on the state to reason in such a process is not feasible.
Enumerating and evaluating all $\ell$-step policy alternatives is
computationally expensive. Instead, the best-response policy can be computed
based on the private history of that agent.

[] The $t$-step optimal state-value function $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}\colon\mathcal{O}^{i}_{t}\to\mathbb{R}$ of a slave game
$M(a^{\neg i}_{0:})$ satisfies a recursion formula, known as Bellman’s
optimality equations, i.e., for any arbitrary private history $o^{i}_{t}$, we
have:

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle=\textstyle\max_{u^{i}_{t}\in\mathcal{U}^{i}}~{}q_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(o^{i}_{t},u^{i}_{t}),$ $\displaystyle q_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(o^{i}_{t},u^{i}_{t})$
$\displaystyle\doteq\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t+1}^{i}(\langle
o^{i}_{t},u^{i}_{t},Z^{i}_{t+1}\rangle)|o^{i}_{t},u^{i}_{t},a^{\neg
i}_{0:}\\}$

with boundary condition $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,\ell}^{i}(\cdot)=q_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(\cdot,\cdot)\doteq 0$.

###### Proof.

The proof starts by defining the best-response policy from time step $t$
onward, providing joint policy of the other agents $a^{\neg
i}_{0:}\in\mathcal{A}^{\neg i}_{0:}$, cf. Definition 10:

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle\doteq\textstyle\max_{a^{i}_{t:}\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{\textstyle{\sum_{\tau=t}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|o^{i}_{t},a^{i}_{t:},a^{\neg i}_{0:}\\}.$

Let $\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i,a^{i}_{t:}}\colon
o^{i}_{t}\mapsto\mathbb{E}\\{\textstyle{\sum_{\tau=t}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|o^{i}_{t},a^{i}_{t:},a^{\neg i}_{0:}\\}$ be a
$t$-step value function under policy $a^{i}_{t:}$ in the slave game $M(a^{\neg
i}_{0:})$. Re-arranging terms by decoupling the immediate reward from the
future rewards leads to the following expression:

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle=\textstyle\max_{(u^{i}_{t},a^{\neg
i}_{t+1:})\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon^{i,a^{i}_{t+1:}}_{M(a^{\neg
i}_{0:}),\gamma,t+1}(\langle
o^{i}_{t},u^{i}_{t},Z^{i}_{t+1}\rangle)|o^{i}_{t},(u^{i}_{t},a^{i}_{t+1:},a^{\neg
i}_{0:})\\}.$

It is worth noticing that the policy $(u^{i}_{t},a^{i}_{t+1:})$ rooted at
history $o^{i}_{t}$ can be written recursively as a tree $\langle
u^{i}_{t},(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\rangle$ with initial
action being $u^{i}_{t}$ and the tree after seeing private observation $z^{i}$
being $a^{i,z^{i}}_{t+1:}$. Consequently, replacing $(u^{i}_{t},a^{i}_{t+1:})$
by $\langle u^{i}_{t},(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\rangle$
results in the following expression:

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle=\textstyle\max_{\langle
u^{i}_{t},(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\rangle\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon^{i,a^{i,Z^{i}_{t+1}}_{t+1:}}_{M(a^{\neg
i}_{0:}),\gamma,t+1}(o^{i}_{t},u^{i}_{t},Z^{i}_{t+1})|o^{i}_{t},(u^{i}_{t},a^{i}_{t+1:},a^{\neg
i}_{0:})\\}.$

One can split the $\max$ operator into two parts, the first one over private
actions $\max_{u^{i}_{t}\in\mathcal{U}^{i}}$ and the other one over the future
decision rules
$\max_{(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\in\mathcal{A}^{i}_{t+1:}}$,
as follows:

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle=\textstyle\max_{u^{i}_{t}\in\mathcal{U}^{i}}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\max_{a^{i,Z_{t+1}^{i}}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}~{}\upsilon^{i,a^{i,Z_{t+1}^{i}}_{t+1:}}_{M(a^{\neg
i}_{0:}),\gamma,t+1}(\langle
o^{i}_{t},u^{i}_{t},Z^{i}_{t+1}\rangle)|o^{i}_{t},(u^{i}_{t},a^{\neg
i}_{0:})\\}.$

By Definition 10, we know that the following holds:

$\displaystyle\upsilon^{i}_{M(a^{\neg
i}_{0:}),\gamma,t+1}((o^{i}_{t},u^{i}_{t},z^{i}_{t+1}))$
$\displaystyle\doteq\textstyle\max_{a^{i,z_{t+1}^{i}}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}~{}\upsilon^{i,a^{i,z_{t+1}^{i}}_{t+1:}}_{M(a^{\neg
i}_{0:}),\gamma,t+1}(\langle o^{i}_{t},u^{i}_{t},z^{i}_{t+1}\rangle),$

which leads us to the following expression:

$\displaystyle\upsilon_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t})$
$\displaystyle=\textstyle\max_{u^{i}_{t}\in\mathcal{U}^{i}}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon^{i}_{M(a^{\neg
i}_{0:}),\gamma,t+1}(\langle
o^{i}_{t},u^{i}_{t},Z^{i}_{t+1}\rangle)|o^{i}_{t},(u^{i}_{t},a^{\neg
i}_{0:})\\}.$

Which ends the proof. ∎

The tabular nature of state- and action-value functions in a slave game
results in linearity over marginal occupancy states.

[] The $t$-step optimal state-value function $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}\colon\mathcal{P}(\mathcal{O}^{i}_{t})\to\mathbb{R}$ is
linear over posterior probability distributions of private histories, i.e.,
for any arbitrary marginal occupancy state $s^{\mathtt{m},i}_{t}$,

$\displaystyle\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(s^{\mathtt{m},i}_{t})$
$\displaystyle=\textstyle\sum_{o^{i}_{t}\in\mathcal{O}_{t}^{i}}~{}s^{\mathtt{m},i}_{t}(o^{i}_{t})\cdot\upsilon_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(o^{i}_{t}).$

Similarly, the $t$-step optimal action-value function $q_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}\colon\mathcal{P}(\mathcal{O}^{i}_{t})\times\mathcal{A}^{i}\to\mathbb{R}$
is linear over posterior probability distributions of private histories, i.e.,
for any arbitrary marginal occupancy state $s^{\mathtt{m},i}_{t}$ and private
decision rule $a^{i}_{t}$,

$\displaystyle q_{M(a^{\neg
i}_{0:}),\gamma,t}^{i}(s^{\mathtt{m},i}_{t},a^{i}_{t})$
$\displaystyle=\textstyle\sum_{o^{i}_{t}\in\mathcal{O}_{t}^{i}}~{}s^{\mathtt{m},i}_{t}(o^{i}_{t})\sum_{u^{i}_{t}\in\mathcal{U}^{i}}~{}a^{i}_{t}(u^{i}_{t}|o^{i}_{t})\cdot
q_{M(a^{\neg i}_{0:}),\gamma,t}^{i}(o^{i}_{t},u^{i}_{t}).$

with boundary condition $\upsilon_{M(a^{\neg
i}_{0:}),\gamma,\ell}^{i}(\cdot)=q_{M(a^{\neg
i}_{0:}),\gamma,\ell}^{i}(\cdot,\cdot)\doteq 0$.

###### Proof.

The proof follows directly from that in Lemma 11. ∎

The optimal state- and action-value functions in slave games are shown to be
linear across probability distributions of private histories in Corollary 11.
However, it is important to note that this finding cannot be directly applied
to the optimal value function of the master game. This is because the master
game requires optimal value function formulations for all the slave games,
encompassing all agents’ histories. Efforts have been made to apply Corollary
11 in showing the uniform continuity properties of optimal value functions of
master games. A notable instance is incorporating a weak convexity property
for the optimal value functions of zs-POSGs by Wiggers et al. (2016). To gain
a more comprehensive understanding of this, it is essential to define some
basilar concepts.

######  Definition 12.

Let $s_{t}\in\mathcal{P}(\mathcal{X}\times\mathcal{O}_{t})$ be a posterior
probability distribution over hidden states and joint histories, namely an
occupancy state, and define the corresponding factors:

  * •

marginal occupancy state $s_{t}^{\mathtt{m},i}$, i.e., for any private history
$o^{i}_{t}$,

$s_{t}^{\mathtt{m},i}(o^{i}_{t})=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o^{\neg
i}_{t}\in\mathcal{O}^{\neg i}_{t}}s_{t}(x_{t},o^{i}_{t},o^{\neg i}_{t}),$

  * •

conditional occupancy state $s_{t}^{\mathtt{c},i}$, i.e., for any hidden state
$x_{t}$ and joint history $\langle o^{i}_{t},o^{\neg i}_{t}\rangle$,

$s_{t}^{\mathtt{c},i}(x_{t},o^{\neg
i}_{t}|o^{i}_{t})=s_{t}(x_{t},o^{i}_{t},o^{\neg
i}_{t})/s_{t}^{\mathtt{m},i}(o^{i}_{t}).$

We shall use short-hand notation $s_{t}\doteq s_{t}^{\mathtt{m},i}\odot
s_{t}^{\mathtt{c},i}$ to represent occupancy state $s_{t}$ given by: for any
arbitrary hidden state $x_{t}$ and joint history $o_{t}$,
$s_{t}(x_{t},o_{t})=s_{t}^{\mathtt{m},i}(o^{i}_{t})\cdot
s_{t}^{\mathtt{c},i}(x_{t},o^{\neg i}_{t}|o^{i}_{t})$.

Intuitively, the $t$-step conditional occupancy state $s_{t}^{\mathtt{c},i}$
is a summary of the suffix joint policy $a^{\neg i}_{:t-1}$ together with the
initial belief $s_{0}$. Consequently, a slave game $M(a_{0:}^{\neg i})$ can be
expressed as a sequence of slave subgames, one slave subgame
$M(s_{t}^{\mathtt{c},i},a^{\neg i}_{t:})$ for each time step $t$. So, solving
slave game $M(a_{0:}^{\neg i})$ relies on solving sequence of slave subgames
$\langle M(a_{0:}^{\neg i}),M(s_{1}^{\mathtt{c},i},a^{\neg
i}_{1:}),\ldots,M(s_{\ell-1}^{\mathtt{c},i},a^{\neg i}_{\ell-1:})\rangle$
through Bellman’s principle of optimality. We are now ready to state the
convexity properties of interest.

[] [Wiggers et al.] Consider the _zs_ -POSG $M$. The $t$-step optimal state-
value function
$\upsilon_{M,\gamma,t}^{i,*}\colon\mathcal{P}(\mathcal{X}\times\mathcal{O}_{t})\to\mathbb{R}$
is convex over marginal occupancy states for a fixed conditional occupancy
state, i.e., for any occupancy state $s_{t}\doteq s_{t}^{\mathtt{m},\neg
i}\odot s_{t}^{\mathtt{c},\neg i}$,

$\displaystyle\upsilon_{M,\gamma,t}^{i,*}(s_{t})$
$\displaystyle=\textstyle\max_{a^{i}_{t:}\in\mathcal{A}_{t:}^{i}}\upsilon^{i}_{M(s_{t}^{\mathtt{c},\neg
i},a^{i}_{t:}),\gamma,t}(s^{\mathtt{m},\neg i}_{t}),$

where $\upsilon^{i}_{M(s_{t}^{\mathtt{c},\neg
i},a^{i}_{t:}),\gamma,t}\doteq-\upsilon^{\neg i}_{M(s_{t}^{\mathtt{c},\neg
i},a^{i}_{t:}),\gamma,t}$ and $M(s_{t}^{\mathtt{c},\neg i},a^{i}_{t:})$
describes the slave subgame given the conditional occupancy state
$s_{t}^{\mathtt{c},\neg i}$ and private decision rule $a^{i}_{t:}$.

Theorem 12 stipulates that the optimal value functions for zs-POSGs are convex
functions of marginal occupancy states, given a fixed conditional occupancy
state. However, this property alone does not facilitate value generalization
across different occupancy states. To address this challenge, Delage et al.
(2023) integrated Lipschitz continuity and the convexity property in Theorem
12, thus allowing for the generalization across occupancy states.

[] [Delage et al.] Consider a _zs_ -POSG $M$. The $t$-step optimal state-value
function
$\upsilon_{M,\gamma,t}^{i,*}\colon\mathcal{P}(\mathcal{X}\times\mathcal{O}_{t})\to\mathbb{R}$
is $\kappa_{t}$-Lipschitz continuous over occupancy states. There exists a
collection $\mathcal{V}^{i}_{t}$ of linear functions across marginal occupancy
states such that for any occupancy state $s_{t}\doteq s_{t}^{\mathtt{m},\neg
i}\odot s_{t}^{\mathtt{c},\neg i}$, and vector $\upsilon^{\neg
i}_{M(\tilde{s}_{t}^{\mathtt{c},\neg
i},a^{i}_{t:}),\gamma,t}\in\mathcal{V}^{i}_{t}$ associated to conditional
occupancy state $\tilde{s}_{t}^{\mathtt{c},\neg i}$, the following holds:

$\displaystyle\upsilon_{M,\gamma,t}^{i,*}(s_{t})$
$\displaystyle\leq\upsilon^{i}_{M(\tilde{s}_{t}^{\mathtt{c},\neg
i},a^{i}_{t:}),\gamma,t}(s^{\mathtt{m},\neg
i}_{t})+\kappa_{t}\|s_{t}-s_{t}^{\mathtt{m},\neg
i}\odot\tilde{s}_{t}^{\mathtt{c},\neg i}\|,$

where $\upsilon^{i}_{M(\tilde{s}_{t}^{\mathtt{c},\neg
i},a^{i}_{t:}),\gamma,t}\doteq-\upsilon^{\neg
i}_{M(\tilde{s}_{t}^{\mathtt{c},\neg i},a^{i}_{t:}),\gamma,t}$, and
$M(s_{t}^{\mathtt{c},\neg i},a^{i}_{t:})$ describes the slave subgame given
conditional occupancy state $s_{t}^{\mathtt{c},\neg i}$ and private decision
rule $a^{i}_{t:}$, and $\kappa_{t}\doteq\frac{1-\gamma^{\ell-t}}{1-\gamma}c$
is the Lipschitz constant at time step $t$.

Using Theorem 12 allows the generalization of values across various occupancy
states by harmonizing local convexity and Lipschitz continuity properties.
Nonetheless, it is worth noting that the Lipschitz constant can result in
imprecise approximations, which may ultimately impede algorithmic efficiency.

##  3 Problem Reformulations

The existing literature on master and slave games primarily focuses on an
agent-centric perspective. However, this approach poses significant challenges
in terms of knowledge transfer from Markov games to POSGs. In particular, the
agent-centric perspective is not always geared to ease optimal decision-
making. As such, adopting a more generalized approach to knowledge transfer is
necessary to address this limitation. This section examines the dynamics of
master and slave games from the perspective of a trusted third party acting on
behalf of all involved agents simultaneously. To accomplish this goal, we
shall introduce two reformulations: plan-time Markov games, which use the
history available at planning time to the trusted third party about master or
slave games, and occupancy Markov games, which leverage sufficient statistics
to represent the history available to the trusted third party. We shall
demonstrate that both reformulations maintain the ability to solve the
original master or slave games optimally.

public observationstrusted third partybehaviorsplan-time environmentdecision
1perception 1decision 2perception 2distribution of individual behaviors Figure
7: A plan-time environment for the tiger problem from the perspective of a
trusted third party. While each agent knows its decision and perception, which
may differ from one agent to the other, the trusted third party has only
access to public observations about the plan-time environment.

###  3.1 Master Game Reformulations

In this subsection, we will discuss agents delegating their decision-making
authority to a trusted third party, also known as a central planner. Within
this setting, we shall distinguish between the planning and execution phases.
During the planning phase, the central planner is given the power to make
decisions on behalf of the agents by using publicly available information
about the environment, agents, decisions, and perceptions. It is important to
note that the central planner may have information at the planning time that
is typically unknown to all agents at the execution stage. At the planning
time, the central planner provides the agents with decision rules to follow at
each time step, but each agent may only have access to their private decision
rules. However, it is important to note that the central planner may not have
access to agent histories or decisions at the execution stage. From the
central planner viewpoint, the plan-time environment includes the original
environment and the agents interacting with it, as shown in Figure 7. The
central planner remains external to the plan-time environment.

Games can be viewed as interactions between agents and their environment or,
alternatively, as interactions between a central planner and a plan-time
environment, resulting in what is known as a _plan-time Markov game_. However,
this alternate perspective does not impact how agents behave in the original
game. Both approaches to the game can yield similar solutions under mild
conditions. For example, if agents disclose all of their confidential
information at every stage, both views are equivalent. Nonetheless, agents may
possess divergent and conflicting information about the game at each stage. In
plan-time Markov games, a central planner executes a joint decision rule on
behalf of all agents and receives public observations available to all agents
involved in the game. Figure 8 illustrates the process. The initial belief
state, history of public observations, and joint policy are integral
components of plan-time histories.

$0$$t$$t+1$$t+2$$\ldots$Time$y_{0}$$y_{t}$$y_{t+1}$$y_{t+2}$$\cdots$$a_{0}$$a_{t}$$a_{t+1}$$w_{t}$$w_{t+1}$$w_{t+2}$
$r^{1:n}_{0}$$r^{1:n}_{t}$$r^{1:n}_{t+1}$$r^{1:n}_{t+2}$$\cdots$knowsinfersselects
Figure 8: Influence diagram for a plan-time Markov game.

######  Definition 13.

A plan-time history for the central planner at time step $t$ includes the
initial belief state and the joint policy of all agents up to time step $t-1$,
and the history of public observation up to time step $t$, i.e.,
$y_{t}\doteq\langle s_{0},a_{0:t-1},w_{1:t}\rangle$, with boundary condition
$y_{0}\doteq s_{0}$.

The plan-time histories describe a simultaneous-moves stochastic Markov game,
i.e., a plan-time Markov game. During the execution phase, the agents do not
have access to the plan-time history, the exception being public observations.
Consequently, since the central planner makes decisions on behalf of the
agents, these decisions cannot rely on the plan-time history. To maintain
consistency with the original master game, the plan-time Markov game should
not be interpreted outside the context in which it was introduced.

######  Definition 14.

A $n$-agent, simultaneous-move, plan-time Markov game w.r.t. $M$ is given by a
tuple
$M^{\prime}\doteq\langle\mathcal{Y},\mathcal{A},\mathcal{W},\rho_{M^{\prime}},\omega_{M^{\prime}},r_{M^{\prime}}\rangle$,
where $\mathcal{Y}$ is the space of all plan-time histories; $\mathcal{A}$ is
the space of actions describing joint decision rules; $\mathcal{W}$ is the
space of public observations;
$\rho_{M^{\prime}}\colon\mathcal{Y}\times\mathcal{A}\times\mathcal{W}\to\mathcal{Y}$
is the deterministic transition rule, where
$\rho_{M^{\prime}}(y_{t},a_{t},w_{t+1})\doteq(y_{t},a_{t},w_{t+1})$;
$\omega_{M^{\prime}}\colon\mathcal{Y}\times\mathcal{A}\times\mathcal{W}\to[0,1]$
is the public observation model, where
$\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})\doteq\Pr\\{w_{t+1}|y_{t},a_{t}\\}$;
and $r_{M^{\prime}}\colon\mathcal{Y}\times\mathcal{A}\to\mathbb{R}^{n}$
describes the reward function—i.e.,
$r^{i}_{M^{\prime}}(y_{t},a_{t})\doteq{\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}}~{}\Pr\\{x_{t},o_{t}|y_{t}\\}\sum_{u_{t}\in\mathcal{U}}r^{i}_{x_{t}u_{t}}\cdot
a_{t}(u_{t}|o_{t})$.

Definition 14 provides a central-planner viewpoint about the master game $M$.
It differs from that of Nayyar et al. (2011); Oliehoek (2013); Dibangoye et
al. (2016) by allowing the explicit utilization of public observations. Doing
so shall later prove useful to connect our general results to narrower
settings. Please note that $M^{\prime}$ is a Markov game in which the agents
cannot observe the states. This means that the solution for this game involves
a sequence of actions conditional on public observations, where the state of
the game has no impact on the actions taken. The main objective of solving
game $M^{\prime}$ is to find a sequence of actions $a^{1:}_{0:}$ conditional
on public observations, also known as a joint policy $a_{0:}$. This policy is
determined by a performance index represented by state-value functions. To
better understand the relationship between games $M$ and $M^{\prime}$, we
introduce the state-value function under a joint policy $a_{0:}$ when
expressed in the plan-time game $M^{\prime}$.

######  Definition 15.

The $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M^{\prime},\gamma,t}\colon\mathcal{Y}_{t}\to\mathbb{R}$
of agent $i$ under joint policy $a_{t:}$ is given by: for any arbitrary plan-
time history $y_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M^{\prime},\gamma,t}(y_{t})$
$\displaystyle=\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{M^{\prime}}(Y_{\tau},a_{\tau})|y_{t},a_{t:}\\},$

with boundary condition
$\upsilon^{i,\cdot}_{M^{\prime},\gamma,\ell}(\cdot)\doteq 0$.

The optimal joint policy for the original master game $M$ can be found by
searching for an optimal joint policy in the surrogate master game
$M^{\prime}$.

[] In a master game $M$ and the corresponding plan-time Markov game
$M^{\prime}$, if a joint policy $a_{0:}$ has the optimal performance index in
$M^{\prime}$ at the initial belief state $s_{0}$, it will also have the same
optimal performance index in $M$ at the initial belief state $s_{0}$.

###### Proof.

First, the solution of interest for both games lies in joint policies. Second,
regardless of solution concepts of interest, the state-value functions under a
joint policy characterize a good solution. Let $a_{0:}$ be a Nash equilibrium
of the plan-time game $M^{\prime}$, i.e., for any agent $i$,
$a^{i}_{0:}\in\mathcal{A}^{i}_{0:}(a^{\neg i}_{0:})$,

$\displaystyle\mathcal{A}^{i}_{0:}(a^{\neg i}_{0:})$
$\displaystyle\doteq\\{a^{i}_{0:}|a^{i}_{0:}\in\mathcal{A}^{i}_{0:}\colon\upsilon^{i,(a^{i}_{0:},a^{\neg
i}_{0:})}_{M^{\prime},\gamma,0}(y_{0})\geq\upsilon^{i,(\underline{a}^{i}_{0:},a^{\neg
i}_{0:})}_{M^{\prime},\gamma,0}(y_{0}),\forall\underline{a}^{i}_{0:}\in\mathcal{A}^{i}_{0:}\\}.$

Let us show that it is also a Nash equilibrium for the master game $M$. To do
so, it only suffices to show that
$\upsilon^{a_{0:}}_{M^{\prime},\gamma,0}(y_{0})=\upsilon^{a_{0:}}_{M,\gamma,0}(s_{0})$
for any arbitrary joint policy $a_{0:}$.

$\displaystyle\upsilon^{a_{0:}}_{M^{\prime},\gamma,0}(y_{0})$
$\displaystyle\doteq\textstyle\mathbb{E}\\{\sum_{t=0}^{\ell-1}\gamma^{t}\cdot
r_{M^{\prime}}(Y_{t},a_{t})|y_{0},a_{0:}\\}.$ (2)

The injection of definition of $r_{M^{\prime}}$, cf. Definition 14, into (2),
results in the following:

$\displaystyle\upsilon^{a_{0:}}_{M^{\prime},\gamma,0}(y_{0})$
$\displaystyle=\textstyle\sum_{t=0}^{\ell-1}\gamma^{t}\mathbb{E}\left\\{\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\Pr\\{x_{t},o_{t}|y_{t}\\}\sum_{u_{t}\in\mathcal{U}}r_{x_{t},u_{t}}\cdot
a_{t}(u_{t}|o_{t})|y_{0},a_{0:}\right\\}.$

Replace the expression into the bracket with an expectation leads us to the
following

$\displaystyle\upsilon^{a_{0:}}_{M^{\prime},\gamma,0}(y_{0})$
$\displaystyle=\textstyle\mathbb{E}\left\\{\sum_{t=0}^{\ell-1}\gamma^{t}\mathbb{E}_{(x_{t},o_{t})\sim\Pr\\{\cdot|Y_{t}\\},u_{t}\sim
a_{t}(\cdot|o_{t})}\\{r_{x_{t}u_{t}}\\}|y_{0},a_{0:}\right\\}.$

Exploiting the linearity of the expectation gives us the following expression

$\displaystyle\upsilon^{a_{0:}}_{M^{\prime},\gamma,0}(y_{0})$
$\displaystyle=\textstyle\mathbb{E}_{(x_{0:\ell-1},o_{0:\ell-1},u_{0:\ell-1})\sim\Pr\\{\cdot|y_{0},a_{0:}\\}}\\{\sum_{t=0}^{\ell-1}\gamma^{t}\cdot
r_{x_{t}u_{t}}\\}$
$\displaystyle=\textstyle\mathbb{E}\\{\sum_{t=0}^{\ell-1}\gamma^{t}\cdot
r_{X_{t},U_{t}}|y_{0},a_{0:}\\}$
$\displaystyle=\textstyle\mathbb{E}\\{\sum_{t=0}^{\ell-1}\gamma^{t}\cdot
r_{X_{t},U_{t}}|s_{0},a_{0:}\\},$ (since $y_{0}\doteq s_{0}$)
$\displaystyle\doteq\upsilon^{a_{0:}}_{M,\gamma,0}(s_{0}).$

The expression presented above demonstrates that for any arbitrary joint
policy $a_{0:}$, both $M^{\prime}$ and $M$ deliver the same evaluation, that
is to say,
$\upsilon^{a_{0:}}_{M^{\prime},\gamma,0}(y_{0})=\upsilon^{a_{0:}}_{M,\gamma,0}(s_{0})$.
As the state-value functions characterize a Nash equilibrium, the fact that
$M^{\prime}$ and $M$ provide the same evaluation for a fixed joint policy
indicates that if a joint policy $a_{0:}$ is a Nash equilibrium for
$M^{\prime}$, it is also a Nash equilibrium for $M$. This argument can
similarly apply to refinements of Nash equilibria, such as subgame perfect
Nash equilibria or optimal joint policies. This concludes the proof. ∎

According to Proposition 15, solving the plan-time Markov game $M^{\prime}$ is
the same as solving the master game $M$. However, keeping track of the plan-
time histories in $M^{\prime}$ can be hard as they constantly grow with each
time step. To simplify things, we can summarize history using the concept of
occupancy state, cf. Figure 9.

######  Definition 16.

A $t$-step occupancy state $s_{t}$ is a posterior probability distribution
over hidden states and joint histories conditional upon a $t$-step plan-time
history $y_{t}$, i.e., for any arbitrary hidden state $x_{t}$, joint history
$o_{t}$,

$\displaystyle s_{t}(x_{t},o_{t})$
$\displaystyle\doteq\Pr\\{x_{t},o_{t}|y_{t}\\}.$

plan-time history $y_{1}$occupancy state
$s_{1}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{\emptyset}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{u_{\textsc{l}}}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{z_{\textsc{hl}}}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{?}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{z_{\textsc{hr}}}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{?}}$${\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{\emptyset}}$${\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{u_{\textsc{ol}}}}$${\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{z_{\textsc{hl}}}}$${\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{?}}$${\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{z_{\textsc{hr}}}}$${\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{?}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\emptyset}{\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\emptyset}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{u_{\textsc{l}}}},{\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{u_{\textsc{ol}}}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{z_{\textsc{hl}}}},{\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{z_{\textsc{hl}}}}$.125$x_{\textsc{tl}}$.125$x_{\textsc{tr}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{z_{\textsc{hr}}}},{\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{z_{\textsc{hr}}}}$.125$x_{\textsc{tl}}$.125$x_{\textsc{tr}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{z_{\textsc{hr}}}},{\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{z_{\textsc{hl}}}}$.125$x_{\textsc{tl}}$.125$x_{\textsc{tr}}$${\color[rgb]{0,0.6,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0.6,0}\boldsymbol{z_{\textsc{hl}}}},{\color[rgb]{0.6,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.6,0,0}\boldsymbol{z_{\textsc{hr}}}}$.125$x_{\textsc{tl}}$.125$x_{\textsc{tr}}$
Figure 9: Illustration of a plan-time history $y_{1}$ and its corresponding
occupancy state $s_{1}$ in case of no public observations.

The probability distributions over hidden states and joint histories lay in
the space $\mathcal{P}(\mathcal{X}\times\mathcal{O})$, which includes the
space of reachable occupancy states $\mathcal{S}$. This convex space indicates
that combining occupancy states by blending joint policies can produce a new
occupancy state. These occupancy states describe a Markov game called the
occupancy-state Markov game. In this game, the central planner simultaneously
makes decisions for all agents and receives public observations as feedback,
as shown in Figure 10.

######  Definition 17.

A $n$-agent, simultaneous-move, occupancy-state Markov game w.r.t.
$M^{\prime}$ (resp. $M$) is given by a tuple
$M^{\prime\prime}\doteq\langle\mathcal{S},\mathcal{A},\mathcal{W},\rho_{M^{\prime\prime}},\omega_{M^{\prime\prime}},p_{M^{\prime\prime}},r_{M^{\prime\prime}}\rangle$,
where $\mathcal{S}$ is the occupancy-state space, occupancy states being
conditional probability distributions over hidden states and joint histories;
$\mathcal{A}$ is the space of actions describing joint decision rules;
$\mathcal{W}$ is the space of public observations available to all agents
involved in the game. Mappings $\rho_{M^{\prime\prime}}$,
$\omega_{M^{\prime\prime}}$, $p_{M^{\prime\prime}}$, and
$r_{M^{\prime\prime}}$ are described as follows:

  * •

The deterministic transition rule
$\rho_{M^{\prime\prime}}\colon\mathcal{S}\times\mathcal{A}\times\mathcal{W}\to\mathcal{S}$
prescribes the next occupancy state
$s_{t+1}\doteq\rho_{M^{\prime\prime}}(s_{t},a_{t},w_{t+1})$ upon taking
decision rule $a_{t}$ in occupancy state $s_{t}$ and receiving public
observation $w_{t+1}$—i.e., for any arbitrary hidden state $x_{t+1}$, joint
history $o_{t}$, joint action $u_{t}$, and joint (private) observation
$\tilde{z}_{t+1}$,

$\displaystyle
s_{t+1}(x_{t+1},(o_{t},u_{t},\tilde{z}_{t+1},w_{t+1}))~{}\propto~{}{\textstyle\sum_{x_{t}\in\mathcal{X}}}~{}s_{t}(x_{t},o_{t})\cdot
p_{x_{t},x_{t+1}}^{u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle}\cdot
a_{t}(u_{t}|o_{t}).$

  * •

The observation probability model
$\omega_{M^{\prime\prime}}\colon\mathcal{S}\times\mathcal{A}\times\mathcal{W}\to[0,1]$
prescribes the probability of receiving public observation $w_{t+1}$ upon
taking decision rule $a_{t}$ in occupancy state $s_{t}$—i.e.,

$\displaystyle\omega_{M^{\prime\prime}}(w_{t+1}|s_{t},a_{t})$
$\displaystyle\doteq\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\sum_{x_{t+1}\in\mathcal{X}}\sum_{\tilde{z}_{t+1}\in\tilde{\mathcal{Z}}}p_{x_{t},x_{t+1}}^{u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle}\cdot
a_{t}(u_{t}|o_{t})\cdot s_{t}(x_{t},o_{t}).$

  * •

The transition probability model
$p_{M^{\prime\prime}}\colon\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1]$
defines the probability of reaching next occupancy state $s_{t+1}$ upon taking
decision rule $a_{t}$ in occupancy state $s_{t}$—i.e.,

$\displaystyle p_{M^{\prime\prime}}(s_{t},a_{t},s_{t+1})$
$\displaystyle\doteq{\textstyle\sum_{w\in\mathcal{W}}}~{}\omega_{M^{\prime\prime}}(w_{t+1}|s_{t},a_{t})\cdot\delta_{\rho_{M^{\prime\prime}}(s_{t},a_{t},w_{t+1})}(s_{t+1}).$

  * •

The reward model
$r_{M^{\prime\prime}}\colon\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{n}$
describes the linear reward function upon taking decision rule $a_{t}$ in
occupancy state $s_{t}$—i.e.,

$\displaystyle
r^{i}_{M^{\prime\prime}}(s_{t},a_{t})\doteq\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s_{t}(x_{t},o_{t})\sum_{u_{t}\in\mathcal{U}}a_{t}(u_{t}|o_{t})\cdot
r^{i}_{x_{t},u_{t}}.$

$0$$t$$t+1$$t+2$$\ldots$Time$s_{0}$$s_{t}$$s_{t+1}$$s_{t+2}$$\cdots$$a_{0}$$a_{t}$$a_{t+1}$$w_{t}$$w_{t+1}$$w_{t+2}$
$r^{1:n}_{0}$$r^{1:n}_{t}$$r^{1:n}_{t+1}$$r^{1:n}_{t+2}$$\cdots$knowsinfersselects
Figure 10: Influence diagram for an occupancy-state Markov game.

The occupancy-state Markov game falls under the category of Markov games.
Since the public observations have been made explicit, the reformulation leads
to a stochastic rather than a deterministic process, as shown in Dibangoye et
al. (2016). The aim of solving $M^{\prime\prime}$ is to find a joint policy
similar to the ones used in both $M$ and $M^{\prime}$. However, in this game,
occupancy states replace plan-time histories, which can lead to overlooking
crucial information, such as the joint policy. Doing so may not be the best
approach for optimal decision-making. The substitution of occupancy states to
plan-time histories requires guarantees that the former are sufficient
statistics of the latter concerning three aspects: (i) predicting the current
expected reward, (ii) predicting the next public observations, and (iii)
estimating the next occupancy state. With these properties in hand, one can
formally define a Markov game. Formal proofs of these properties follow.

[] The $t$-step occupancy state, defined as
$s_{t}\doteq\Pr\\{X_{t},O_{t}|y_{t}\\}$, is a sufficient statistic of the
plan-time history $y_{t}$ for an accurate prediction of the expected reward
that will be received immediately after executing the decision rule $a_{t}$,
i.e., $r_{M^{\prime}}(y_{t},a_{t})=r_{M^{\prime\prime}}(s_{t},a_{t})$.

###### Proof.

The proof starts with the definition of the expected reward conditional on
plan-time history $y_{t}$ and decision rule $a_{t}$, i.e.,

$\displaystyle r_{M^{\prime}}(y_{t},a_{t})$
$\displaystyle\doteq\mathbb{E}\\{r_{X_{t},U_{t}}|y_{t},a_{t}\\}.$

The expansion over hidden states, joint histories and joint actions leads to
the following expression:

$\displaystyle r_{M^{\prime}}(y_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\Pr\\{x_{t},o_{t},u_{t}|y_{t},a_{t}\\}\cdot
r_{x_{t},u_{t}}.$

The decomposition of the joint probability as the product of conditional
probabilities gives the following expression:

$\displaystyle r_{M^{\prime}}(y_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\Pr\\{x_{t}|y_{t},a_{t},o_{t},u_{t}\\}\Pr\\{u_{t}|y_{t},a_{t},o_{t}\\}\cdot
r_{x_{t},u_{t}}\cdot\Pr\\{o_{t}|y_{t}\\}.$

By removing terms that do not influence conditional probabilities, we obtain
the following expression:

$\displaystyle r_{M^{\prime}}(y_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\Pr\\{x_{t}|y_{t},o_{t}\\}\Pr\\{u_{t}|a_{t},o_{t}\\}\cdot
r_{x_{t},u_{t}}\cdot\Pr\\{o_{t}|y_{t}\\}.$

Finally re-arranging terms, noticing that
$s_{t}(x_{t},o_{t})\doteq\Pr\\{x,o|y_{t}\\}=\Pr\\{x_{t}|y_{t},o_{t}\\}\cdot\Pr\\{o_{t}|y_{t}\\}$
and $a_{t}(u_{t}|o_{t})\doteq\Pr\\{u_{t}|a_{t},o_{t}\\}$, we have that

$\displaystyle r_{M^{\prime}}(y_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}a_{t}(u_{t}|o_{t})\cdot
r_{x_{t},u_{t}}\cdot s_{t}(x_{t},o_{t}).$

By the definition of $r_{M^{\prime\prime}}(s_{t},a_{t})$, from Definition 17,
the following holds:

$\displaystyle r_{M^{\prime}}(y_{t},a_{t})$
$\displaystyle=r_{M^{\prime\prime}}(s_{t},a_{t}).$

Which ends the proof. ∎

[] The $t$-step occupancy state, defined as
$s_{t}\doteq\Pr\\{X_{t},O_{t}|y_{t}\\}$, is a sufficient statistic of the
plan-time history $y_{t}$ for predicting of the next public observation
$w_{t+1}$ following the executing of the decision rule $a_{t}$, i.e.,
$\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})=\omega_{M^{\prime\prime}}(w_{t+1}|s_{t},a_{t})$.

###### Proof.

The proof starts with the definition of the probability of receiving public
observation $w_{t+1}$ upon taking decision rule $a_{t}$ in plan-time history
$y_{t}$, i.e.,

$\displaystyle\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})$
$\displaystyle\doteq\Pr\\{w_{t+1}|y_{t},a_{t}\\}.$

The expansion of the conditional probability $\Pr\\{w_{t+1}|y_{t},a_{t}\\}$
over hidden states $x_{t},x_{t+1}$, joint histories $o_{t}$, and joint actions
$u_{t}$ and joint private observations $\tilde{z}_{t+1}$, result in the
following expression:

$\displaystyle\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\sum_{x_{t+1}\in\mathcal{X}}\sum_{\tilde{z}_{t+1}\in\tilde{\mathcal{Z}}}\Pr\\{x_{t},o_{t},u_{t},x_{t+1},\tilde{z}_{t+1},w_{t+1}|y_{t},a_{t}\\}.$

The decomposition of the joint probability as a product of conditional
probabilities yields the following result:

$\displaystyle\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\sum_{x_{t+1}\in\mathcal{X}}\sum_{\tilde{z}_{t+1}\in\tilde{\mathcal{Z}}}\Pr\\{x_{t+1},\tilde{z}_{t+1},w_{t+1}|y_{t},a_{t},x_{t},o_{t},u_{t}\\}$
$\displaystyle\quad\cdot\Pr\\{x_{t}|y_{t},a_{t},u_{t},o_{t}\\}\cdot\Pr\\{u_{t}|y_{t},a_{t},o_{t}\\}\cdot\Pr\\{o_{t}|y_{t},a_{t}\\}.$

The first factor is the game’s dynamics; the second factor is the probability
of the hidden states given plan-time history and joint history; the third
factor is the probability of joint actions given decision rule and joint
history, and the last factor is the probability of joint histories given the
plan-time history, i.e.,

$\displaystyle\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\sum_{x_{t+1}\in\mathcal{X}}\sum_{\tilde{z}_{t+1}\in\tilde{\mathcal{Z}}}\Pr\\{x_{t+1},\tilde{z}_{t+1},w_{t+1}|x_{t},u_{t}\\}$
$\displaystyle\quad\cdot\Pr\\{x_{t}|y_{t},o_{t}\\}\cdot\Pr\\{u_{t}|a_{t},o_{t}\\}\cdot\Pr\\{o_{t}|y_{t}\\}.$

Re-arranging and re-naming terms yield the following expression

$\displaystyle\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}\sum_{u_{t}\in\mathcal{U}}\sum_{x_{t+1}\in\mathcal{X}}\sum_{\tilde{z}_{t+1}\in\tilde{\mathcal{Z}}}p_{x_{t},x_{t+1}}^{u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle}\cdot
a_{t}(u_{t}|o_{t})\cdot s_{t}(x_{t},o_{t}).$

Consequently, the following equality holds by Definition 17 for
$\omega_{M^{\prime\prime}}(w_{t+1}|s_{t},a_{t})$:

$\displaystyle\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})$
$\displaystyle=\omega_{M^{\prime\prime}}(w_{t+1}|s_{t},a_{t}).$

Which ends the proof. ∎

[] The $t$-step occupancy state, defined as
$s_{t}\doteq\Pr\\{X_{t},O_{t}|y_{t}\\}$, is a sufficient statistic of the
plan-time history $y_{t}$ for predicting the subsequent occupancy state
following the executing of the decision rule $a_{t}$ and the reception of
public observation $w_{t+1}$, i.e.,
$\rho_{M^{\prime}}(y_{t},a_{t},w_{t+1})=\rho_{M^{\prime\prime}}(s_{t},a_{t},w_{t+1})$.

###### Proof.

In demonstrating the sufficiency of the occupancy states, we also derive the
rule for updating occupancy states from one time step to the next. For the
process defined by $M^{\prime}$, the only information that the central planner
obtains during the plan time $t$ is the fact that a particular decision rule
$a_{t}$ has been followed, and public observation $w_{t+1}$ has been received
at the end of the plan time. If $(y_{t},a_{t},w_{t+1})$ denotes the total data
available to the central planner at plan time $t+1$, then we can write:

$\displaystyle y_{t+1}$ $\displaystyle\doteq(y_{t},a_{t},w_{t+1}),$

$y_{t+1}$ represents the plan-time history before time step $t+1$ plus the
additional information that a particular decision rule was recorded and public
observation occurred. By Definition 16, occupancy states are written as
follows: for every hidden state $x_{t+1}$, joint history $o_{t}$, joint action
$u_{t}$, and joint observation $\langle\tilde{z}_{t+1},w_{t+1}\rangle$,

$\displaystyle
s_{t+1}(x_{t+1},(o_{t},u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle))$
$\displaystyle\doteq\Pr\\{x_{t+1},(o_{t},u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle)|y_{t+1}\\}.$
(3)

The application of Bayes’ rule and the substitution of $y_{t+1}$ by
$(y_{t},a_{t},w_{t+1})$ in (3) yield

$\displaystyle
s_{t+1}(x_{t+1},(o_{t},u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle))$
$\displaystyle=\frac{\Pr\\{x_{t+1},o_{t},u_{t},\tilde{z}_{t+1},w_{t+1}|y_{t},a_{t}\\}}{\Pr\\{w_{t+1}|y_{t},a_{t}\\}}.$
(4)

From Lemma 10, we know that the denominator of (4) is given
$\omega_{M^{\prime}}(w_{t+1}|y_{t},a_{t})=\omega_{M^{\prime\prime}}(w_{t+1}|s_{t},a_{t})$.
The expansion of the joint probability in the numerator of (4) as a product of
conditional probabilities yields

$\displaystyle
s_{t+1}(x_{t+1},(o_{t},u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle))$
$\displaystyle~{}\propto\sum_{x_{t}\in\mathcal{X}}\Pr\\{x_{t},x_{t+1},o_{t},u_{t},\tilde{z}_{t+1},w_{t+1}|y_{t},a_{t}\\}.$

The expansion of the joint probability as a product of conditional
probabilities gives us the following expression:

$\displaystyle
s_{t+1}(x_{t+1},(o_{t},u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle))$
$\displaystyle~{}\propto\sum_{x_{t}\in\mathcal{X}}\Pr\\{x_{t+1},\tilde{z}_{t+1},w_{t+1}|x_{t},o_{t},u_{t},y_{t},a_{t}\\}$
$\displaystyle\quad\cdot\Pr\\{x_{t}|y_{t},a_{t},o_{t},u_{t}\\}\cdot\Pr\\{u_{t}|y_{t},a_{t},o_{t}\\}\cdot\Pr\\{o_{t}|y_{t},a_{t}\\}$

Re-arranging terms

$\displaystyle
s_{t+1}(x_{t+1},(o_{t},u_{t},\langle\tilde{z}_{t+1},w_{t+1}\rangle))$
$\displaystyle~{}\propto\sum_{x_{t}\in\mathcal{X}}p_{x_{t},x_{t+1}}^{u_{t},\tilde{z}_{t+1},w_{t+1}}\cdot
a_{t}(u_{t}|o_{t})\cdot s_{t}(x_{t},o_{t}).$

Consequently, the following equality holds by Definition 17 for
$\rho_{M^{\prime\prime}}(s_{t},a_{t},w_{t+1})$:

$\displaystyle s_{t+1}$
$\displaystyle=\rho_{M^{\prime\prime}}(s_{t},a_{t},w_{t+1}).$

Which ends the proof. ∎

We introduce state-value functions for a fixed joint policy under
$M^{\prime\prime}$ to determine if occupancy states are sufficient. These
state-value functions compute the expected cumulative $\gamma$-discounted
reward from the initial belief state $s_{0}$ onward. They are represented as
$\upsilon_{M^{\prime\prime},\gamma,0}^{a_{0:}}(s_{0})\doteq\mathbb{E}\\{\textstyle{\sum_{t=0}^{\ell-1}}~{}\gamma^{t}\cdot
r_{M^{\prime\prime}}(S_{t},a_{t})|s_{0},a_{0:}\\}$.

######  Definition 18.

The $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M^{\prime\prime},\gamma,t}\colon\mathcal{S}_{t}\to\mathbb{R}$
under the joint policy $a_{t:}$ is given by: for any occupancy state $s_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle\doteq\textstyle\mathbb{E}\left\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{M^{\prime\prime}}(S_{\tau},a_{\tau})|s_{t},a_{t:}\right\\},$

with boundary condition $\upsilon^{i,\cdot}_{M,\gamma,\ell}(\cdot)\doteq 0$.

According to the following lemma, the state-value functions satisfy Bellman’s
equations for occupancy states at every time step.

[] The $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M^{\prime\prime},\gamma,t}\colon\mathcal{S}_{t}\to\mathbb{R}$
under the joint policy $a_{0:}$ satisfies Bellman’s equations: for any
occupancy state $s_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=q^{i,a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t}),$
$\displaystyle q^{i,a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t})$
$\displaystyle\doteq\textstyle
r^{i}_{M^{\prime\prime}}(s_{t},a_{t})+\gamma\sum_{s_{t+1}\in\mathcal{S}_{t+1}}p_{M^{\prime\prime}}(s_{t},a_{t},s_{t+1})\cdot\upsilon^{i,a_{t+1:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1}),$

with boundary condition
$\upsilon^{i,\cdot}_{M^{\prime\prime},\gamma,\ell}(\cdot)\doteq 0$.

###### Proof.

The proof follows directly from the definition of the state-value functions
under joint policy $a_{0:}$ over the occupancy states: for time step $t$,
occupancy state $s_{t}$,

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle\doteq\textstyle\mathbb{E}\left\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r_{M^{\prime\prime}}(S_{\tau},a_{\tau})|s_{t},a_{t:}\right\\},$

Exploiting the fact that $r_{M^{\prime\prime}}(s_{t},a_{t})$ is not a random
variable, we obtain the following expression:

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle
r_{M^{\prime\prime}}(s_{t},a_{t})+\gamma\mathbb{E}\left\\{\sum_{\tau=t+1}^{\ell-1}\gamma^{\tau-t-1}\cdot
r_{M^{\prime\prime}}(S_{\tau},a_{\tau})|s_{t},a_{t:}\right\\}.$

The expansion of the expectation over all next occupancy states (through
public observations) gives the following expression:

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle
r_{M^{\prime\prime}}(s_{t},a_{t})+\gamma\mathbb{E}\left\\{\mathbb{E}\\{\sum_{\tau=t+1}^{\ell-1}\gamma^{\tau-t-1}\cdot
r_{M^{\prime\prime}}(S_{\tau},a_{\tau})|s_{t+1},a_{t+1:}\\}|s_{t},a_{t}\right\\}.$

The injection of Definition 18 of
$\upsilon^{a_{t+1:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1})$ instead of the
inner expectation gives the following expression:

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle
r_{M^{\prime\prime}}(s_{t},a_{t})+\gamma\mathbb{E}_{s_{t+1}\sim
p_{M^{\prime\prime}}(s_{t},a_{t},\cdot)}\left\\{\upsilon^{a_{t+1:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1})|s_{t},a_{t}\right\\}.$

By definition of the expectation, we know that the expression becomes:

$\displaystyle\overset{\text{Definition
\ref{def:state:value:fct:m:os}}}{=}\textstyle
r_{M^{\prime\prime}}(s_{t},a_{t})+\gamma\sum_{s_{t+1}\in\mathcal{S}_{t+1}}p_{M^{\prime\prime}}(s_{t},a_{t},s_{t+1})\cdot\upsilon^{a_{t+1:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1})$
$\displaystyle\doteq q^{a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t}).$

Which ends the proof. ∎

It is important to recognize that state- and action-value functions in the
master game $M$ under a fixed joint policy, which have a tabular nature,
inherently display uniform continuity characteristics. The following
explanation highlights the simple yet significant linear properties associated
with these functions, providing a fixed joint policy. It is worth noting that
these uniform continuity properties apply to occupancy states.

[] The $t$-step state-value function
$\upsilon^{i,a_{t:}}_{M^{\prime\prime},\gamma,t}\colon\mathcal{S}_{t}\to\mathbb{R}$
under joint policy $a_{t:}$ is linear over occupancy states: for any occupancy
state $s_{t}$,

$\displaystyle\upsilon^{i,a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X},o_{t}\in\mathcal{O}_{t}}s_{t}(x_{t},o_{t})\cdot\upsilon^{i,a_{t:}}_{M,\gamma,t}(x_{t},o_{t}).$

Similarly, the $t$-step action-value function
$q^{i,a_{t+1:}}_{M^{\prime\prime},t}\colon\mathcal{S}_{t}\times\mathcal{A}_{t}\to\mathbb{R}$
under the joint policy $a_{t+1:}$ is linear over occupancy states and joint
decision rules: for any occupancy state $s_{t}\in\mathcal{S}_{t}$ and joint
decision rule $a_{t}$

$\displaystyle q^{i,a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X},o_{t}\in\mathcal{O}_{t}}s_{t}(x_{t},o_{t})\sum_{u_{t}\in\mathcal{U}}a_{t}(u_{t}|o_{t})\cdot
q^{i,a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t}).$

###### Proof.

The proof starts with the definition of the state- and action-value functions
for a fixed joint policy at time step $t$ and occupancy state $s_{t}$,

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle\doteq\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r_{M^{\prime\prime}}(S_{\tau},a_{\tau})|s_{t},a_{t:}\\}.$

It is worth noticing that the dynamics of occupancy states are stochastic,
which makes it possible to rewrite
$\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$ as follows:

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle
q^{a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t})$ $\displaystyle
q^{a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t})$
$\displaystyle=\textstyle
r_{M^{\prime\prime}}(s_{t},a_{t})+\gamma\sum_{s_{t+1}\in\mathcal{S}_{t+1}}p_{M^{\prime\prime}}(s_{t},a_{t},s_{t+1})\cdot\upsilon^{a_{t+1:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1}).$

The property naturally holds when the horizon is exhausted, i.e.,
$\upsilon^{\cdot}_{M^{\prime\prime},\gamma,\ell}(\cdot)=q^{\cdot}_{M^{\prime\prime},\gamma,\ell}(\cdot,\cdot)\doteq
0$. Suppose it also holds at time step $t+1$ onward, i.e.,

$\displaystyle\upsilon^{a_{t+1:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s_{t+1}(x_{t},o_{t})\cdot\upsilon^{a_{t+1:}}_{M,\gamma,t+1}(x_{t},o_{t})$
$\displaystyle q^{a_{t+2:}}_{M^{\prime\prime},\gamma,t+1}(s_{t+1},a_{t+1})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s_{t+1}(x_{t},o_{t})\sum_{u_{t}\in\mathcal{U}}a_{t+1}(u_{t}|o_{t})\cdot
q^{a_{t+2:}}_{M,\gamma,t+1}(x_{t},o_{t},u_{t}).$

Then, it follows that

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle q^{a_{t+1:}}_{M,\gamma,t}(s_{t},a_{t})$
$\displaystyle q^{a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s_{t}(x_{t},o_{t})\sum_{u_{t}\in\mathcal{U}}a_{t}(u_{t}|o_{t})\cdot
q^{a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t})$ $\displaystyle
q^{a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t})$ $\displaystyle=\textstyle
r_{x_{t},u_{t}}+\gamma\sum_{x_{t+1}\in\mathcal{X},z_{t+1}\in\mathcal{Z}}p_{x_{t}x_{t+1}}^{u_{t}z_{t+1}}\cdot\upsilon^{a_{t+1:}}_{M,\gamma,t+1}(x_{t+1},(o_{t},u_{t},z_{t+1})).$

Re-arranging terms then yield the target results, i.e.,

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s_{t}(x_{t},o_{t})\cdot\upsilon^{a_{t:}}_{M,\gamma,t}(x_{t},o_{t})$
$\displaystyle q^{a_{t+1:}}_{M^{\prime\prime},\gamma,t}(s_{t},a_{t})$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s_{t}(x_{t},o_{t})\sum_{u_{t}\in\mathcal{U}}a_{t}(u_{t}|o_{t})\cdot
q^{a_{t+1:}}_{M,\gamma,t}(x_{t},o_{t},u_{t}).$

Hence, the property holds for any arbitrary time step. Which ends the proof. ∎

Lemma 18 highlights that when a fixed joint policy is utilized, the state- and
action-value functions can be elegantly expressed as linear functions of
occupancy states across all types of master games that are represented as
partially observable stochastic games. This linearity property is a
fundamental aspect that contributes greatly to proving the convexity property
of optimal value functions for specific master games, including the common-
reward partially observable stochastic games family (_dec_ -POMDP).

The conditions for the sufficiency of occupancy states in optimally solving
master games as occupancy-state Markov games are presented in the following
proposition.

[] Let $M$ be a master game, $M^{\prime}$ be the corresponding plan-time
Markov game, and $M^{\prime\prime}$ the associated occupancy-state Markov
game. If we let $a_{0:}$ be a solution of $M^{\prime\prime}$, then $a_{0:}$ is
also a solution of $M$ and $M^{\prime}$.

###### Proof.

Proposition 15 demonstrates that a solution for $M^{\prime}$ is also valid for
$M$. The only thing left to prove is that if $a_{0:}$ is a solution for
$M^{\prime\prime}$, then it is also a solution for $M^{\prime}$. Initially, we
need to show that the state-value function for any particular time step $t$
under a fixed joint policy is dependent on the plan-time history $y_{t}$ only
through the corresponding occupancy state $s_{t}$, which is defined as
$(\Pr\\{x_{t},o_{t}|y_{t}\\})_{x_{t}\in\mathcal{X},o_{t}\in\mathcal{O}_{t}}$.
For any arbitrary fixed joint policy $a_{t:}$,

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime},\gamma,t}(y_{t})$
$\displaystyle\doteq\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r_{M^{\prime}}(Y_{\tau},a_{\tau})|y_{t},a_{t:}\\}.$

The application of Lemma 10, Lemma 10, and Lemma 10, lead to the following
expression:

$\displaystyle\upsilon^{a_{t:}}_{M^{\prime},\gamma,t}(y_{t})$
$\displaystyle=\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r_{M^{\prime\prime}}(S_{\tau},a_{\tau})|s_{t},a_{t:}\\},$
$\displaystyle\doteq\upsilon^{a_{t:}}_{M^{\prime\prime},\gamma,t}(s_{t}).$

Which ends the proof. ∎

Please note that Propositions 15 and 18 do not provide a practical solution to
master games. Rather, they show that finding a solution to either reformulated
version will result in a valid solution for the original master game. It is
crucial to remember that the solution for these reformulated games does not
depend on their states, as they are non-observable. Therefore, it is not
advisable to use state-dependent solutions when solving these reformulations,
as is often done in fully observable settings.

public observationstrusted third party My policy is $a^{\neg i}_{0:}$
behaviorsplan-time environmentdecision 1perception 1decision 2perception 2
Figure 11: A plan-time environment for the tiger problem from the perspective
of the trusted third party, now reasoning only on behalf of Suzie given that
Calvin’s policy is plan-time. He knows Suzie’s decisions and perceptions, but
when it comes to Calvin, he has only access to public observations, including
Calvin’s policy and the plan-time environment.

###  3.2 Slave Game Reformulations

This subsection presents a new perspective on the slave games, viewed from the
point of view of a trusted third party. As depicted in Figure 11, the slave
games were originally formulated as a single-agent decision-making problem,
assuming that other agents had a fixed joint policy. However, this approach
led to weak uniform continuity properties, as discussed in Theorems 12 and 12,
due to the use of different viewpoints to describe master and slave games,
making it difficult to blend their value functions. This subsection aims to
provide a unified perspective of both master and slave games from the point of
view of a trusted third party, making it easier to identify properties of the
slave games that can be applied to master games.

The central planner can think for one agent when considering a trusted third-
party viewpoint. The other agents have a predetermined collective strategy,
and this information is known to the central planner and the agent for whom it
makes decisions. The central planner then gives that agent a set of rules to
follow at every time step. In this scenario, the central planner can receive
information about the action taken and the observations made by the specific
agent it decides for. The private plan-time environment, viewed from the
trusted third party’s perspective, includes the original game environment and
all interacting agents. However, unlike the master game’s plan-time
environment, the other agents have a predetermined joint policy, and the
central planner can only see the private history of the agent they are
reasoning for, not the private histories of the other agents. This
reformulation turns the slave games into the private plan-time Markov game.
Still, it does not affect how the single agent, the central planner, is
reasoning to act in the original environment. Additionally, we will prove that
both games, although not equivalent, can lead to equivalent solutions under
mild conditions. The central planner collects data at the end of each time
step, known as the private plan-time history. This includes the initial belief
state, the private history of the specific agent taken into account, and the
collective policy of all other agents.

######  Definition 19.

For an agent $i$, a private plan-time history at time step $t$ includes the
initial belief state, its individual history and the joint policy of all other
agents except agent $i$, up to time step $t-1$, i.e., $y_{t}^{i}\doteq\langle
s_{0},o^{i}_{t},a^{\neg i}_{:t-1}\rangle$, with boundary condition
$y_{0}^{i}\doteq s_{0}$.

Private plan-time histories describe a special process called private plan-
time Markov game that is illustrated in Figure 12. A formal description of
this game follows.

######  Definition 20.

Consider the master game $M$ and its surrogate $M^{\prime}$. Let $a^{\neg
i}_{0:}$ be a joint policy of all agents except agent $i$. Private plan-time
Markov game $M^{\prime}(a^{\neg i}_{0:})$ is characterized by the tuple
$\langle\mathcal{Y}^{i},\mathcal{U}^{i},\mathcal{Z}^{i},\rho^{i}_{M^{\prime}},\omega^{i}_{M^{\prime}},r^{i}_{M^{\prime}}\rangle$.
Here, $\mathcal{Y}^{i}$ represents a space of private plan-time histories,
$\mathcal{U}^{i}$ is the finite action space, and $\mathcal{Z}^{i}$ is the
finite observation space. Mappings $\rho^{i}_{M^{\prime}}$,
$\omega^{i}_{M^{\prime}}$, and $r^{i}_{M^{\prime}}$ are formally defined as
follows:

  * •

Mapping
$\rho^{i}_{M^{\prime}}\colon\mathcal{Y}^{i}\times\mathcal{U}^{i}\times\mathcal{Z}^{i}\to\mathcal{Y}^{i}$
describes a transition rule over private plan-time histories, i.e., for any
private plan-time history $y^{i}_{t}$, action $u_{t}^{i}$, and observation
$z^{i}_{t+1}$, the next private plan-time history is given by:
$\rho^{i}_{M^{\prime}}(y_{t}^{i},u_{t}^{i},z_{t+1}^{i})\doteq(y_{t}^{i},a^{\neg
i}_{t},u^{i}_{t},z^{i}_{t+1})$.

  * •

Mapping
$\omega^{i}_{M^{\prime}}\colon\mathcal{Y}^{i}\times\mathcal{U}^{i}\times\mathcal{Z}^{i}\to[0,1]$
is the observation rule, i.e., for any private plan-time history $y^{i}_{t}$,
action $u_{t}^{i}$, and observation $z^{i}_{t+1}$, the observation probability
is given by:
$\omega^{i}_{M^{\prime}}(z_{t+1}^{i}|y_{t}^{i},u_{t}^{i})\doteq\Pr\\{z^{i}_{t+1}|y_{t}^{i},u_{t}^{i},a^{\neg
i}_{t}\\}$.

  * •

Mapping
$r^{i}_{M^{\prime}}\colon\mathcal{Y}^{i}\times\mathcal{U}^{i}\to\mathbb{R}$
defines the reward model, i.e., for any private plan-time history $y^{i}_{t}$,
action $u_{t}^{i}$, the reward is given by:
$r^{i}_{M^{\prime}}(y_{t}^{i},u_{t}^{i})\doteq\mathbb{E}\\{r^{i}_{X_{t},U_{t}}|y_{t}^{i},u_{t}^{i},a^{\neg
i}_{t}\\}$.

$0$$t$$t+1$$t+2$$\ldots$Time$y^{i}_{0}$$y^{i}_{t}$$y^{i}_{t+1}$$y^{i}_{t+2}$$\cdots$$u^{i}_{0}$$u^{i}_{t}$$u^{i}_{t+1}$$z^{i}_{t}$$z^{i}_{t+1}$$z^{i}_{t+2}$$r^{i}_{0}$$r^{i}_{t}$$r^{i}_{t+1}$$r^{i}_{t+2}$$\cdots$knowsinfersselects
Figure 12: Influence diagram for a private plan-time Markov game.

Upon careful examination of private plan-time Markov games, it becomes
apparent that they can be constructed using slave games. This removes the need
for the explicit creation of the former, allowing for the generation of its
components as required. Slave games are linked to partially observable Markov
decision processes, while private plan-time Markov games have a more direct
connection. However, it is important to note that private plan-time Markov
games were introduced as surrogate games for the original slave games, and
their objectives remain the same. Solving a private plan-time Markov game aims
to determine the agent’s best-response policy, denoted as $a^{i}_{0:}$.
Interestingly, a one-to-one mapping exists between private plan-time histories
in these games and private histories in slave games, i.e.,

$\varphi^{i}_{M^{\prime}}\colon\left\\{\begin{array}[]{lcl}\mathcal{Y}^{i}&\to&\mathcal{O}^{i}\\\
y^{i}_{t}\doteq(s_{0},o^{i}_{t},a^{\neg
i}_{:t-1})&\mapsto&o^{i}_{t}\end{array}\right.$

This partially explains why best-response policies achieve identical
performance indices in both settings. It is worth noticing that because a
private plan-time Markov game $M^{\prime}(a^{\neg i}_{0:})$ is a Markov game,
one can actually optimally solve it by breaking it into a sequence of subgames
$\langle M^{\prime}(a^{\neg i}_{0:}),M^{\prime}(a^{\neg
i}_{1:}),M^{\prime}(a^{\neg i}_{2:}),\ldots,M^{\prime}(a^{\neg
i}_{\ell-1:})\rangle$ solved recursively.

######  Definition 21.

Consider a private plan-time Markov game $M^{\prime}(a^{\neg i}_{0:})$ w.r.t.
the slave game $M(a^{\neg i}_{0:})$. The $t$-step optimal value function
$\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}\colon\mathcal{Y}^{i}_{t}\to\mathbb{R}$ of a private plan-
time Markov subgame $M^{\prime}(a^{\neg i}_{t:})$ is given by: for any private
plan-time history $y^{i}_{t}$,

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y_{t}^{i})$
$\displaystyle\doteq\textstyle\max_{a^{i}_{t:}\in\mathcal{A}^{i}_{t:}}\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau}U_{\tau}}|y^{i}_{t},a_{t:}\\}.$

The optimal state-value functions of private plan-time Markov game
$M^{\prime}(a^{\neg i}_{0:})$ exhibit a special property: they are also
solutions of the Bellman’s optimality equations.

[] The $t$-step optimal state-value function $\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}\colon\mathcal{Y}^{i}_{t}\to\mathbb{R}$ is the solution of
Bellman’s optimality equations, i.e., for any arbitrary private plan-time
history $y^{i}_{t}$,

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y_{t}^{i})$
$\displaystyle=\textstyle\max_{u^{i}_{t}\in\mathcal{U}^{i}}~{}q^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}(y_{t}^{i},u^{i}_{t}),$ $\displaystyle
q^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y_{t}^{i},u^{i}_{t})$
$\displaystyle\doteq
r^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t})+\gamma\\!\\!\\!\sum_{z^{i}_{t+1}\in\mathcal{Z}^{i}}\\!\\!\\!\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y_{t}^{i},u^{i}_{t})\cdot\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t},z^{i}_{t+1})),$

with boundary condition
$\upsilon^{i}_{M^{\prime},\gamma,\ell}(\cdot)=q^{i}_{M^{\prime},\gamma,\ell}(\cdot)\doteq
0$.

###### Proof.

The proof follows directly from the definition of optimal state-value
functions for private plan-time Markov game $M^{\prime}(a^{\neg i}_{t:})$, cf.
Definition 21, i.e.,

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle\textstyle\doteq\max_{a^{i}_{t:}\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{\textstyle{\sum_{\tau=t}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|y^{i}_{t},a_{t:}\\}.$

Let $\upsilon_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}^{i,a^{i}_{t:}}\colon
y^{i}_{t}\mapsto\mathbb{E}\\{\textstyle{\sum_{\tau=t}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|y^{i}_{t},a_{t:}\\}$ be a $t$-step value function
under the policy $a^{i}_{t:}$ in the slave game $M^{\prime}(a^{\neg i}_{t:})$.
Re-arranging terms by decoupling the immediate reward from the future rewards
leads successively to the following expressions:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle=\max_{(u^{i}_{t},a^{i}_{t+1:})\in\mathcal{A}^{i}_{t:}}~{}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},Z^{i}_{t+1}))|y^{i}_{t},u^{i}_{t},a^{\neg
i}_{t},a_{t+1:}\\},$

where $\upsilon^{i,a_{t+1:}^{i}}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1}))\doteq\mathbb{E}\\{\sum_{\tau=t+1}^{\ell-1}~{}\gamma^{\tau-t-1}\cdot
r^{i}_{X_{\tau},U_{\tau}}|\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1}),a_{t+1:}\\}$.
It is worth noticing that policy $(u^{i}_{t},a^{i}_{t+1:})$ rooted at history
$o^{i}_{t}$ can be written recursively as a tree $\langle
u^{i}_{t},(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\rangle$ with initial
action being $u^{i}_{t}$ and the subtree after seeing private observation
$z^{i}$ being $a^{i,z^{i}}_{t+1:}$. Consequently, replacing
$(u^{i}_{t},a^{i}_{t+1:})$ by $\langle
u^{i}_{t},(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\rangle$ results in:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle=\\!\\!\\!\max_{\langle
u^{i}_{t},(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\rangle\in\mathcal{A}^{i}_{t:}}\\!\\!\\!\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon^{i,a^{i,z^{i}_{t+1}}_{t+1:}}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1}))|y^{i}_{t},u^{i}_{t},a^{\neg
i}_{t},a_{t+1:}\\}.$

One can split the $\max$ operator into two parts, the first one over private
actions $\max_{u^{i}_{t}\in\mathcal{U}^{i}}$ and the other one over the future
decision rules
$\max_{(a^{i,z^{i}}_{t+1:})_{z^{i}\in\mathcal{Z}^{i}}\in\mathcal{A}^{i}_{t+1:}}$,
as follows:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle=\max_{u^{i}_{t}\in\mathcal{U}^{i}}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\max_{a^{i,z_{t+1}^{i}}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}~{}\upsilon^{i,a^{i,z_{t+1}^{i}}_{t+1:}}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1}))|y^{i}_{t},u^{i}_{t},a^{\neg
i}_{t}\\}.$

By Definition 21, we know that the following holds:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1}))$
$\displaystyle\doteq\max_{a^{i,z_{t+1}^{i}}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}~{}\upsilon^{i,a^{i,z_{t+1}^{i}}_{t+1:}}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1})),$

which leads us to the following expression:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle=\max_{u^{i}_{t}\in\mathcal{U}^{i}}\mathbb{E}\\{r^{i}_{X_{t},U_{t}}+\gamma\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},Z^{i}_{t+1}))|y^{i}_{t},u^{i}_{t},a^{\neg
i}_{t}\\}.$

By the application of Definition 20, we know that
$r^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t})\doteq\mathbb{E}\\{r^{i}_{X_{t},U_{t}}|y_{t}^{i},u_{t}^{i},a^{\neg
i}_{t}\\}$, which results in the following expression:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle=\max_{u^{i}_{t}\in
U^{i}}\left\\{r^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t})+\gamma\mathbb{E}\\{\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},Z^{i}_{t+1}))|y^{i}_{t},u^{i}_{t},a^{\neg
i}_{t}\\}\right\\}.$

The expansion over the private observations of the expectation yields the
following expression:

$\displaystyle\upsilon^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y^{i}_{t})$
$\displaystyle=\max_{u^{i}_{t}\in\mathcal{U}^{i}}~{}q^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}(y_{t}^{i},u^{i}_{t}),$ $\displaystyle
q^{i}_{M^{\prime}(a^{\neg i}_{t:}),\gamma,t}(y_{t}^{i},u^{i}_{t})$
$\displaystyle\doteq
r^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t})+\gamma\sum_{z^{i}_{t+1}\in\mathcal{Z}^{i}}\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y_{t}^{i},u^{i}_{t})\cdot\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t},z^{i}_{t+1})).$

Which ends the proof. ∎

The following proposition explicitly connects the games $M(a^{\neg i}_{0:})$
and $M^{\prime}(a^{\neg i}_{0:})$, such that solving either game solves the
other.

[] Let $M(a^{\neg i}_{0:})$ be a slave game and $M^{\prime}(a^{\neg i}_{0:})$
be the corresponding private plan-time Markov game. If we let $a_{0:}^{i}$ be
the best-response policy of $M^{\prime}(a^{\neg i}_{0:})$, then it is also the
best-response policy of $M(a^{\neg i}_{0:})$.

###### Proof.

The proof consists in demonstrating that optimal state-value functions for
$M^{\prime}(a^{\neg i}_{t:})$ and $M(a^{\neg i}_{0:})$ achieve the same
performance index on equivalent inputs, i.e., for any time step $t$ and
private plan-time history $y^{i}_{t}$, $\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}(y_{t}^{i})=\upsilon^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}))$. Consequently, the
best-response policy $a_{t:}^{i}$ solution of Bellman’s optimality equations
for $M^{\prime}(a^{\neg i}_{t:})$ achieves the best performance index also for
$M(a^{\neg i}_{0:})$. Thus, it is also a best-response policy for $M(a^{\neg
i}_{0:})$. Starting with the definition of the optimal action-value function
for $M(a^{\neg i}_{0:})$ at time step $t$ and private history
$\varphi^{i}_{M^{\prime}}(y_{t}^{i})$, we have that:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle\doteq\max_{a^{i}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}\mathbb{E}\left\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t},a^{i}_{t+1:},a^{\neg
i}_{0:}\right\\}.$

There is no loss in replacing $(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),a^{\neg
i}_{:t-1})$ by $y_{t}^{i}$, consequently it follows that:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle=\max_{a^{i}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}\mathbb{E}\left\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{X_{\tau},U_{\tau}}|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{t},a_{t+1:}\right\\}.$

The following splits the immediate and the future rewards:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle=\max_{a^{i}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}\mathbb{E}\left\\{r^{i}_{X_{t},U_{t}}+\gamma\sum_{\tau=t+1}^{\ell-1}\gamma^{\tau-t-1}\cdot
r^{i}_{X_{\tau},U_{\tau}}|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{t},a_{t+1:}\right\\}.$

Re-arranging terms leads to the following expression:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle=\max_{a^{i}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}\mathbb{E}\left\\{r^{i}_{X_{t},U_{t}}|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{t}\right\\}+\gamma\mathbb{E}\left\\{\sum_{\tau=t+1}^{\ell-1}\gamma^{\tau-t-1}\cdot
r^{i}_{X_{\tau},U_{\tau}}|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{t},a_{t+1:}\right\\}.$

By the application of Definition 20, we know that
$r^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t})\doteq\mathbb{E}\\{r^{i}_{X_{t},U_{t}}|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{t}\\}$, which results in the following expression:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle=r^{i}_{M^{\prime}}(y_{t}^{i},u^{i}_{t})+\gamma\max_{a^{i}_{t+1:}\in\mathcal{A}^{i}_{t+1:}}\mathbb{E}\left\\{\sum_{\tau=t+1}^{\ell-1}\gamma^{\tau-t-1}\cdot
r^{i}_{X_{\tau},U_{\tau}}|y_{t}^{i},(u^{i}_{t},a^{i}_{t+1:},a^{\neg
i}_{t+1:})\right\\}.$

The expansion of all private observations of agent $i$ produces the following
expression:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle=r^{i}_{M^{\prime}}(y_{t}^{i},u_{t}^{i})+\gamma\mathbb{E}_{z^{i}_{t+1}\sim\Pr\\{\cdot|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{0:}\\}}\\{\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y_{t}^{i},u_{t}^{i},z_{t+1}^{i}))\\}$

By the application of Definition 20, we know that
$\omega^{i}_{M^{\prime}}(z_{t+1}^{i}|y_{t}^{i},u_{t}^{i})\doteq\Pr\\{z^{i}_{t+1}|y_{t}^{i},u^{i}_{t},a^{\neg
i}_{t}\\}$, which results in the following expression:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t})$
$\displaystyle=\textstyle
r^{i}_{M^{\prime}}(y_{t}^{i},u_{t}^{i})+\gamma\sum_{z_{t+1}^{i}\in\mathcal{Z}^{i}}\omega^{i}_{M^{\prime}}(z_{t+1}^{i}|y_{t}^{i},u_{t}^{i})\cdot\upsilon^{i}_{M^{\prime}(a^{\neg
i}_{t+1:}),\gamma,t+1}(\rho^{i}_{M^{\prime}}(y_{t}^{i},u_{t}^{i},z_{t+1}^{i})).$

By the application of the definition of $q^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}(y_{t}^{i},u_{t}^{i})$, it follows that:

$\displaystyle q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u_{t}^{i})$
$\displaystyle=q^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}(y_{t}^{i},u_{t}^{i}).$

The greedy selection of the best-response policy $a^{i}_{0:}$ w.r.t. joint
policy $a^{\neg i}_{0:}$ of the other agents is given as follows: at time step
$t$, and private history $\varphi^{i}_{M^{\prime}}(y_{t}^{i})$,

$\displaystyle a_{t}^{i}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}))$
$\displaystyle\in\textstyle\operatorname*{\arg\,\max}_{u_{t}^{i}\in\mathcal{U}^{i}}~{}q^{i}_{M(a^{\neg
i}_{0:}),\gamma,t}(\varphi^{i}_{M^{\prime}}(y_{t}^{i}),u^{i}_{t}),$
$\displaystyle\in\textstyle\operatorname*{\arg\,\max}_{u_{t}^{i}\in\mathcal{U}^{i}}~{}q^{i}_{M^{\prime}(a^{\neg
i}_{t:}),\gamma,t}(y_{t}^{i},u_{t}^{i}).$

Which ends the proof. ∎

Proposition 21 demonstrates that a solution for $M^{\prime}(a^{\neg i}_{0:})$
can also serve as a solution for the original slave game $M(a^{\neg i}_{0:})$.
Nonetheless, like other historical data, private plan-time histories grow in
size with each time step, making them less feasible to use. Hence, we suggest
a substitute statistic, private occupancy states, to tackle this problem.
Nevertheless, before we delve deeper into this subject, it is essential to
establish the definition of private occupancy states.

######  Definition 22.

Each agent $i$ has a private occupancy state at a specific time step $t$,
represented as $s^{i}_{t}$ (also denoted as $s^{i,o_{t}^{i}}_{t}$ when needed
to make the dependence from a given private history $o_{t}^{i}$ more
explicit). This state is the posterior probability distribution over hidden
states and joint histories based on their private plan-time history
$y^{i}_{t}$, expressed as $\Pr\\{X_{t},O_{t}|y^{i}_{t}\\}$. The initial
condition is defined as $s^{i}_{0}=s_{0}$.

The concept of hierarchical information-sharing in two-agent games has been
studied extensively, with research indicating that the private occupancy state
can be expressed in a more concise manner (Sorin, 2003; Hadfield-Menell et
al., 2016; Horák et al., 2017; Xie et al., 2020). If agent 2 has unrestricted
access to agent 1’s actions and observations at every time step $t$ without
incurring any cost, denoted by $(u^{1}_{t-1},z^{1}_{t})\sqsubseteq z_{t}^{2}$,
then the private occupancy state at that specific time step $t$ can be
represented as a posterior probability distribution over the hidden states,
commonly referred to as the belief state. This is denoted as
$\Pr\\{x_{t}|y^{2}_{t}\\}$, where $x$ belongs to the set $\mathcal{X}$.
Furthermore, if agent 2 can observe the underlying state of the game, i.e.,
one-sidedness, then the private occupancy state at a specific time step $t$ is
equivalent to that underlying state. The conciseness of private occupancy
states is crucial in identifying strong uniform continuity properties for the
optimal state-value functions.

The optimal state- and action-value functions of a slave game can be better
understood through private occupancy states. Revealing the uniform continuity
property of those value functions allows for knowledge transfer between
different private occupancy states. While private occupancy states can be more
concise for a single slave game, it is important to consider knowledge
transfer between multiple slave games. Transfer of knowledge from one slave
game to another one is important because to solve a master game, we need to
solve multiple slave games. Defining private occupancy states as posterior
distributions over hidden states and histories of other agents $\neg i$ or as
private histories of agent $i$, as shown by Wiggers et al. (2016), is adequate
for solving a single slave game optimally. However, using a more concise
statistic for a single slave game would make knowledge transfer between slave
games more difficult, especially in exhibiting the relationship between the
optimal state-value function of the master game and the corresponding slave
games. This insight explains why previous attempts to establish convexity
properties of the optimal state-value functions of the master game failed. The
following section explores how private occupancy states are sufficient for
optimally solving any slave game.

##  4 Connecting Slave and Master Games

This section will discuss an alternative method to solve a slave game by
utilizing private occupancy states instead of private plan-time histories. We
will analyze if using private occupancy states is enough to solve the
reformulated slave games optimally. Furthermore, we will establish a
correlation between private occupancy states and occupancy states to merge the
state-value functions of master and slave games. We will first define the
Markov decision process that private occupancy states induce.

$0$$t$$t+1$$t+2$$\ldots$Time$s^{i}_{0}$$s^{i}_{t}$$s^{i}_{t+1}$$s^{i}_{t+2}$$\cdots$$u^{i}_{0}$$u^{i}_{t}$$u^{i}_{t+1}$$z^{i}_{t}$$z^{i}_{t+1}$$z^{i}_{t+2}$$r^{i}_{0}$$r^{i}_{t}$$r^{i}_{t+1}$$r^{i}_{t+2}$$\cdots$knowsinfersselects
Figure 13: Influence diagram for a private occupancy-state Markov game.

######  Definition 23.

Let $M$ be a master game, and let $M(a^{\neg i}_{0:})$ (respectively
$M^{\prime}(a^{\neg i}_{0:})$) be its corresponding slave game. A private
occupancy-state Markov decision process is given by a tuple
$M^{\prime\prime}(a^{\neg
i}_{0:})\doteq(\mathcal{S}^{i},\mathcal{U}^{i},\mathcal{Z}^{i},\omega^{i}_{M^{\prime\prime}},\rho^{i}_{M^{\prime\prime}},p^{i}_{M^{\prime\prime}},r^{i}_{M^{\prime\prime}})$.
Here, $\mathcal{S}^{i}$ is the finite private occupancy-state space,
$\mathcal{U}^{i}$ represents the finite action space, and $\mathcal{Z}^{i}$ is
the finite observation space. Mappings $\omega^{i}_{M^{\prime\prime}}$,
$\rho^{i}_{M^{\prime\prime}}$, $p^{i}_{M^{\prime\prime}}$, and
$r^{i}_{M^{\prime\prime}}$ are formally described as follows.

  * •

The observation function
$\omega^{i}_{M^{\prime\prime}}\colon\mathcal{S}^{i}\times\mathcal{U}^{i}\times\mathcal{Z}^{i}\to[0,1]$
gives the probability of private observation $z^{i}_{t+1}$ upon taking action
$u^{i}_{t}$ starting in private occupancy state $s^{i,o^{i}_{t}}_{t}$, i.e.,

$\displaystyle\omega^{i}_{M^{\prime\prime}}(z^{i}_{t+1}|s^{i,o^{i}_{t}}_{t},u^{i}_{t})$
$\displaystyle\doteq\sum_{x_{t},x_{t+1}\in\mathcal{X}}\sum_{u_{t}^{\neg
i}\in\mathcal{U}^{\neg i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg
i}}\sum_{o^{\neg i}_{t}\in\mathcal{O}^{\neg
i}_{t}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\cdot a^{\neg i}_{t}(u_{t}^{\neg
i}|o_{t}^{\neg i})\cdot s^{i,o^{i}_{t}}_{t}(x_{t},o_{t}).$

  * •

The transition rule
$\rho^{i}_{M^{\prime\prime}}\colon\mathcal{S}^{i}\times\mathcal{U}^{i}\times\mathcal{Z}^{i}\to\mathcal{S}^{i}$
gives the next private occupancy state upon receiving private observation
$z^{i}_{t+1}$ after taking private action $u^{i}_{t}$ starting in private
occupancy state $s^{i}_{t}$ , i.e., for any arbitrary hidden state $x_{t+1}$
and joint history $(o_{t},u_{t},z^{i}_{t+1},z^{\neg i}_{t+1})$,

$\displaystyle s^{i}_{t+1}(x_{t+1},(o_{t},u_{t},z^{i}_{t+1},z^{\neg
i}_{t+1}))$
$\displaystyle~{}\propto~{}\sum_{x_{t}\in\mathcal{X}}p^{u_{t}\langle
z^{i}_{t+1},z^{\neg i}_{t+1}\rangle}_{x_{t}x_{t+1}}\cdot a^{\neg
i}_{t}(u_{t}^{\neg i}|o_{t}^{\neg i})\cdot s^{i}_{t}(x_{t},o_{t}).$

  * •

The transition probability function
$p^{i}_{M^{\prime\prime}}\colon\mathcal{S}^{i}\times\mathcal{U}^{i}\times\mathcal{S}^{i}\to[0,1]$
gives the probability of private occupancy state $s^{i}_{t+1}$ upon taking
action $u_{t}^{i}$ in private occupancy state $s^{i}_{t}$ , i.e.,

$\displaystyle p^{i}_{M^{\prime\prime}}(s^{i}_{t},u^{i}_{t},s^{i}_{t+1})$
$\displaystyle\doteq\sum_{z_{t+1}^{i}\in\mathcal{Z}^{i}}\omega^{i}_{M^{\prime\prime}}(z^{i}_{t+1}|s^{i}_{t},u^{i}_{t})\cdot\delta_{\rho^{i}_{M^{\prime\prime}}(s^{i}_{t},u^{i}_{t},z_{t+1}^{i})}(s^{i}_{t+1}).$

  * •

The reward model
$r^{i}_{M^{\prime\prime}}\colon\mathcal{S}^{i}\times\mathcal{U}^{i}\to\mathbb{R}$
gives the immediate expected reward upon taking private action $u_{t}^{i}$ in
private occupancy state $s^{i}_{t}$ , i.e.,

$\displaystyle r^{i}_{M^{\prime\prime}}(s^{i}_{t},u^{i}_{t})$
$\displaystyle\doteq\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}\in\mathcal{O}_{t}}s^{i}_{t}(x_{t},o_{t})\sum_{u^{\neg
i}_{t}\in\mathcal{U}^{\neg i}}a^{\neg i}_{t}(u_{t}^{\neg i}|o^{\neg
i}_{t})\cdot r^{i}_{x_{t},u_{t}}.$

The Markov decision process associated with private occupancy states is called
the private occupancy-state Markov decision process, as depicted in Figure 13.
Using occupancy states for master game reformulations raises questions similar
to those regarding the use of private occupancy states in the context of slave
games. Bellman’s principle of optimality allows us to solve
$M^{\prime\prime}(a^{\neg i}_{0:})$ by solving recursively a sequence of
smaller Markov decision processes $\langle M^{\prime\prime}(a^{\neg
i}_{0:}),M^{\prime\prime}(a^{\neg i}_{1:}),\ldots,M^{\prime\prime}(a^{\neg
i}_{\ell-1:})\rangle$. The reader may wonder if private occupancy states are
sufficient statistics for optimally solving slave games through private
occupancy-state Markov decision processes. One way to prove this claim is to
demonstrate that private occupancy states are sufficient statistics of private
plan-time histories for optimally solving $M^{\prime\prime}(a^{\neg i}_{0:})$,
as private plan-time histories are proven to preserve the ability to solve the
original slave games optimally, as outlined in Proposition 21.

###  4.1 Sufficiency of Private Occupancy States

This subsection illustrates how private occupancy states can act as sufficient
statistics for the complete data accessible to the trusted third party who is
reasoning on behalf of agent $i$ in any given slave game $M(a^{\neg i}_{0:})$
(or $M^{\prime}(a^{\neg i}_{0:})$). These statistics are sufficient for
optimally solving any slave game. Using this as a basis, we prove that the
optimal action- and state-value functions of a slave game $M(a^{\neg i}_{0:})$
(or $M^{\prime}(a^{\neg i}_{0:})$) depend on private plan-time histories only
through private occupancy states.

[] For each agent $i$, the private occupancy state at time step $t$, defined
as $s^{i}_{t}\doteq\Pr\\{X_{t},O_{t}|y^{i}_{t}\\}$, is a sufficient statistic
of the private plan-time history $y_{t}^{i}$ for optimally solving
$M^{\prime}(a^{\neg i}_{0:})$, i.e.,

$\textstyle\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{M^{\prime\prime}}(S^{i}_{\tau},U^{i}_{\tau})|s^{i}_{t},a^{i}_{t:},a^{\neg
i}_{0:}\\}=\mathbb{E}\\{\sum_{\tau=t}^{\ell-1}\gamma^{\tau-t}\cdot
r^{i}_{M^{\prime}}(Y^{i}_{\tau},U^{i}_{\tau})|y^{i}_{t},a^{i}_{t:},a^{\neg
i}_{0:}\\}.$

Also, an optimal solution for $M^{\prime\prime}(a^{\neg i}_{0:})$ is also a
solution for $M(a^{\neg i}_{0:})$ (respectively, $M^{\prime}(a^{\neg
i}_{0:})$).

To prove this theorem, we must establish three properties. Firstly, we need to
prove that private occupancy states are enough to accurately predict the
probability of an observation being received by agent $i$ after taking action
$u^{i}_{t}$, as stated in Lemma 4.1. Secondly, we must show that the private
occupancy states describe a Markov process, meaning that the current private
occupancy state is enough to estimate the next one, as stated in Lemma 4.1.
Finally, we must prove that the private occupancy states are sufficient to
accurately estimate the immediate reward when taking action $u^{i}_{t}$, as
stated in Lemma 4.1. In the following, we will establish these three
fundamental properties to demonstrate the sufficiency of private occupancy
states of private plan-time histories for optimally solving slave games.

[] For each agent $i$, the private occupancy state at time step $t$, defined
as $s^{i}_{t}\doteq\Pr\\{X_{t},O_{t}|y^{i}_{t}\\}$, is a sufficient statistic
of the private plan-time history $y_{t}^{i}$ for prediction of the next
private observation $z^{i}_{t+1}$ following the execution of the private
action $u^{i}_{t}$—i.e.,
$\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})=\omega^{i}_{M^{\prime\prime}}(z^{i}_{t+1}|s^{i}_{t},u^{i}_{t})$.

###### Proof.

For each agent $i$, the probability of private observation $z^{i}_{t+1}$ at
the end of time step $t+1$ can be rewritten as the sum over all possible
hidden states $x_{t}$, and joint histories $o_{t}^{\neg i}$, and private
actions $u_{t}^{\neg i}$ at the end of time step $t$, as well as all joint
observations $z_{t+1}^{\neg i}$, and hidden states $x_{t+1}$ at the end of
time step $t+1$, i.e.,

$\displaystyle\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})$
$\displaystyle\doteq\Pr\\{z^{i}_{t+1}|y^{i}_{t},a^{\neg i}_{t},u^{i}_{t}\\}$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}^{\neg
i}\in\mathcal{O}_{t}^{\neg i}}\sum_{u_{t}^{\neg i}\in\mathcal{U}^{\neg
i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg
i}}\sum_{x_{t+1}\in\mathcal{X}}\Pr\\{x_{t},o_{t}^{\neg i},u_{t}^{\neg
i},z_{t+1}^{\neg i},x_{t+1}|y^{i}_{t},a^{\neg i}_{t},u^{i}_{t}\\}.$

The application of Bayes’ rule and the replacement of $y^{i}_{t}$ by
$(s_{0},o^{i}_{t},a_{:t-1}^{\neg i})$ yield

$\displaystyle\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}^{\neg
i}\in\mathcal{O}_{t}^{\neg i}}\sum_{u_{t}^{\neg i}\in\mathcal{U}^{\neg
i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg
i}}\sum_{x_{t+1}\in\mathcal{X}}\frac{\Pr\\{s_{0},x_{t},o_{t},u_{t},z_{t+1},x_{t+1},a_{:t}^{\neg
i}\\}}{\Pr\\{y^{i}_{t},a^{\neg i}_{t},u^{i}_{t}\\}}.$ (5)

The expansion of the joint probability in (5) as a product of conditional
probabilities yields

$\displaystyle\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{o_{t}^{\neg
i}\in\mathcal{O}_{t}^{\neg i}}\sum_{u_{t}^{\neg i}\in\mathcal{U}^{\neg
i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg i}}\sum_{x_{t+1}\in\mathcal{X}}$
$\displaystyle\textstyle\qquad\Pr\\{z_{t+1},x_{t+1}|s_{0},x_{t},o_{t},u_{t},a_{:t}^{\neg
i}\\}\cdot\Pr\\{u^{\neg i}_{t}|s_{0},x_{t},o_{t},a_{:t}^{\neg i},u^{i}_{t}\\}$
$\displaystyle\textstyle\qquad\cdot\Pr\\{x_{t},o^{\neg
i}_{t}|y^{i}_{t},a_{t}^{\neg i},u^{i}_{t}\\}\cdot\Pr\\{y^{i}_{t},a_{t}^{\neg
i},u^{i}_{t}\\}/\Pr\\{y^{i}_{t},a^{\neg i}_{t},u^{i}_{t}\\}.$ (6)

The first probability in (6) is simply the dynamics
$(p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}})$ of $M$, i.e.,

$\displaystyle\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{u_{t}^{\neg
i}\in\mathcal{U}^{\neg i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg
i}}\sum_{x_{t+1}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}$
$\displaystyle\textstyle\qquad\sum_{o_{t}^{\neg i}\in\mathcal{O}_{t}^{\neg
i}}\Pr\\{u^{\neg i}_{t}|s_{0},x_{t},o_{t},a_{:t}^{\neg
i},u^{i}_{t}\\}\cdot\Pr\\{x_{t},o^{\neg i}_{t}|y^{i}_{t},a_{t}^{\neg
i},u^{i}_{t}\\}.$ (7)

The second probability in (7) defines the probability of taking joint action
$u^{\neg i}_{t}$ upon experiencing joint history $o^{\neg i}_{t}$, i.e.,

$\displaystyle\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{u_{t}^{\neg
i}\in\mathcal{U}^{\neg i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg
i}}\sum_{x_{t+1}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\sum_{o_{t}^{\neg
i}\in\mathcal{O}_{t}^{\neg i}}$ $\displaystyle\textstyle\qquad a^{\neg
i}_{t}(u_{t}^{\neg i}|o_{t}^{\neg i})\cdot\Pr\\{x_{t},o^{\neg
i}_{t}|y^{i}_{t},a_{t}^{\neg i},u^{i}_{t}\\}.$ (8)

The third probability in (8) defines the probability of the previous private
occupancy state at hidden state $x_{t}$ and joint history $o_{t}$, i.e.,

$\displaystyle\omega^{i}_{M^{\prime}}(z^{i}_{t+1}|y^{i}_{t},u^{i}_{t})$
$\displaystyle=\sum_{x_{t}\in\mathcal{X}}\sum_{u_{t}^{\neg
i}\in\mathcal{U}^{\neg i}}\sum_{z_{t+1}^{\neg i}\in\mathcal{Z}^{\neg
i}}\sum_{x_{t+1}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\sum_{o_{t}^{\neg
i}\in\mathcal{O}_{t}^{\neg i}}a^{\neg i}_{t}(u_{t}^{\neg i}|o_{t}^{\neg
i})\cdot s^{i}_{t}(x_{t},o_{t})$
$\displaystyle\doteq\omega^{i}_{M^{\prime\prime}}(z^{i}_{t+1}|s^{i}_{t},u^{i}_{t}).$

Which ends the proof. ∎

Based on Lemma 4.1, it is possible to make precise predictions about a private
observation $z^{i}_{t+1}$ by knowing private occupancy state $s^{i}_{t}$,
private decision $a^{\neg i}_{t}$, and private action $u^{i}_{t}$. This
prediction can be made without knowing the private plan-time history
$y^{i}_{t}$.

[] For each agent $i$, the private occupancy state at time step $t$, defined
as $s^{i}_{t}\doteq\Pr\\{X_{t},O_{t}|y^{i}_{t}\\}$, is a sufficient statistic
of the private plan-time history $y_{t}^{i}$ for predicting the subsequent
private occupancy state following the execution the private action $u^{i}_{t}$
and the reception of the private observation $z^{i}_{t+1}$, i.e.,
$\rho^{i}_{M^{\prime}}(y^{i}_{t},u^{i}_{t},z^{i}_{t+1})=\rho^{i}_{M^{\prime\prime}}(s^{i}_{t},u^{i}_{t},z^{i}_{t+1})$.

###### Proof.

In demonstrating the sufficiency of private occupancy states, we also derive
the rule for updating private occupancy states from one time step to the next.
For the process defined by $M^{\prime}(a^{\neg i}_{0:})$, the only information
that agent $i$ obtains during time step $t$ is the fact that a particular
decision rule $a^{\neg i}_{t}$ has been followed by agents $\neg i$, private
action $u_{t}^{i}$ has been executed by agent $i$, and private observation
$z^{i}_{t+1}$ has been received at the end of time step $t+1$ by agent $i$,
then we can write

$\displaystyle y^{i}_{t+1}$ $\displaystyle\doteq(y^{i}_{t},a^{\neg
i}_{t},u^{i}_{t},z^{i}_{t+1}).$

That is, $y^{i}_{t+1}$ represents the private plan-time history of agent $i$
before time step $t+1$ plus the additional information that a particular
decision rule and private action were recorded and private observation
occurred. By Definition 22, private occupancy states are written as follows:
for every hidden state $x_{t+1}$, history $o_{t}^{\neg i}$, action
$u_{t}^{\neg i}$, and observation $z_{t+1}^{\neg i}$,

$\displaystyle s^{i}_{t+1}(x_{t+1},(o_{t},u_{t},z_{t+1}))$
$\displaystyle\doteq\Pr\\{x_{t+1},o_{t}^{\neg i},u_{t}^{\neg i},z_{t+1}^{\neg
i}|y^{i}_{t+1}\\}.$ (9)

The application of Bayes’ rule and the substitution of $y^{i}_{t+1}$ by
$(y^{i}_{t},a^{\neg i}_{t},u^{i}_{t},z^{i}_{t+1})$ in (9) yield

$\displaystyle s^{i}_{t+1}(x_{t+1},(o_{t}^{\neg i},u_{t}^{\neg
i},z_{t+1}^{\neg i},o^{i}_{t+1}))$
$\displaystyle=\Pr\\{s_{0},o_{t},u_{t},z_{t+1},x_{t+1},a^{\neg
i}_{:t}\\}/\Pr\\{y^{i}_{t+1}\\}.$ (10)

The expansion of (10) over all hidden states $x_{t}$ produces

$\displaystyle s^{i}_{t+1}(x_{t+1},(o_{t}^{\neg i},u_{t}^{\neg
i},z_{t+1}^{\neg i},o^{i}_{t+1}))$
$\displaystyle=\textstyle\sum_{x_{t}\in\mathcal{X}}\Pr\\{s_{0},x_{t},o_{t},u_{t},z_{t+1},x_{t+1},a^{\neg
i}_{:t}\\}/\Pr\\{y^{i}_{t+1}\\}.$ (11)

The expansion of the joint probability in the numerator of (11) as a product
of conditional probabilities yields

$\displaystyle s^{i}_{t+1}(x_{t+1},(o_{t}^{\neg i},u_{t}^{\neg
i},z_{t+1}^{\neg
i},o^{i}_{t+1}))=\textstyle\sum_{x_{t}\in\mathcal{X}}\Pr\\{z_{t+1},x_{t+1}|s_{0},x_{t},o_{t},u_{t},a^{\neg
i}_{:t}\\}$ $\displaystyle\qquad\cdot\Pr\\{u^{\neg
i}_{t}|s_{0},x_{t},o_{t},a^{\neg i}_{:t},u^{i}_{t}\\}\cdot\Pr\\{x_{t},o^{\neg
i}_{t}|s_{0},o^{\neg i}_{t},a^{\neg
i}_{:t},u^{i}_{t}\\}\cdot\frac{\Pr\\{s_{0},o^{\neg i}_{t},a^{\neg
i}_{:t},u^{i}_{t}\\}}{\Pr\\{y^{i}_{t+1}\\}}.$ (12)

The first probability in the numerator of (12) is independent of private plan-
time history $y^{i}_{t}$, decision rule $a^{\neg i}_{t}$ at the end of time
step $t$; it is simply the dynamics of $M$, i.e.,

$\displaystyle s^{i}_{t+1}(x_{t+1},(o_{t}^{\neg i},u_{t}^{\neg
i},z_{t+1}^{\neg
i},o^{i}_{t+1}))=\textstyle\sum_{x_{t}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\cdot\Pr\\{u^{\neg
i}_{t}|s_{0},x_{t},o_{t},a^{\neg i}_{:t},u^{i}_{t}\\}$
$\displaystyle\qquad\cdot\Pr\\{x_{t},o^{\neg i}_{t}|s_{0},o^{\neg
i}_{t},a^{\neg i}_{:t},u^{i}_{t}\\}\cdot\frac{\Pr\\{y^{i}_{t},a^{\neg
i}_{t},u^{i}_{t}\\}}{\Pr\\{y^{i}_{t+1}\\}}.$ (13)

The second probability in the numerator of (13) defines the probability of
taking joint action $u_{t}^{\neg i}$ of agents $\neg i$ upon experiencing
joint history $o_{t}^{\neg i}$, i.e.,

$\displaystyle\overset{\eqref{eq:thm:sufficiency:occupancy:state:factor:9:0}}{=}\textstyle\sum_{x_{t}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\cdot
a^{\neg i}_{t}(u^{\neg i}_{t}|o^{\neg i}_{t})\cdot\Pr\\{x_{t},o^{\neg
i}_{t}|s_{0},o^{\neg i}_{t},a^{\neg
i}_{:t+1},u^{i}_{t}\\}\cdot\frac{\Pr\\{y^{i}_{t},a^{\neg
i}_{t},u^{i}_{t}\\}}{\Pr\\{y^{i}_{t+1}\\}}.$ (14)

Moreover, the third probability in the numerator of (14) will be independent
of private action $u^{i}_{t}$ as well as decision rule $a^{\neg i}_{t}$, since
current decision rule alternatives do not affect current joint history. Hence,
it defines the probability of the previous private occupancy state at hidden
state $x_{t}$ and joint history $o^{\neg i}_{t}$, i.e.,

$\displaystyle\overset{\eqref{eq:thm:sufficiency:occupancy:state:factor:9:0}}{=}\sum_{x_{t}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\cdot
a^{\neg i}_{t}(u^{\neg i}_{t}|o^{\neg i}_{t})\cdot
s^{i}_{t}(x_{t},o_{t})\cdot\frac{\Pr\\{y^{i}_{t},a^{\neg
i}_{t},u^{i}_{t}\\}}{\Pr\\{y^{i}_{t+1}\\}}.$ (15)

The last probability in the numerator of (15) can be simplified by the
denominator in (15), i.e.,

$\displaystyle\overset{\eqref{eq:thm:sufficiency:occupancy:state:factor:9:0}}{=}\sum_{x_{t}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\cdot
a^{\neg i}_{t}(u^{\neg i}_{t}|o^{\neg i}_{t})\cdot
s^{i}_{t}(x_{t},o_{t})/\Pr\\{z^{i}_{t+1}|y^{i}_{t},a^{\neg
i}_{t},u^{i}_{t}\\}.$ (16)

From Lemma 4.1, we know the denominator in (16) depends on private plan-time
history $y^{i}_{t}$ only through corresponding private occupancy state
$s^{i}_{t}$, i.e.,

$\displaystyle\overset{\eqref{eq:thm:sufficiency:occupancy:state:factor:9:0}}{=}\sum_{x_{t}\in\mathcal{X}}p^{u_{t}z_{t+1}}_{x_{t}x_{t+1}}\cdot
a^{\neg i}_{t}(u^{\neg i}_{t}|o^{\neg i}_{t})\cdot
s^{i}_{t}(x_{t},o_{t})/\Pr\\{z^{i}_{t+1}|s^{i}_{t},a^{\neg
i}_{t},u^{i}_{t}\\}.$

where
$\omega^{i}_{M^{\prime\prime}}(z^{i}_{t+1}|s^{i}_{t},u^{i}_{t})\doteq\Pr\\{z^{i}_{t+1}|s^{i}_{t},a^{\neg
i}_{t},u^{i}_{t}\\}$ serves as a normalizing constant. The important feature
of the update rule of private occupancy states is that the calculation of the
private occupancy states after time step $t+1$ requires only $s^{i}_{t}$, the
private occupancy state at time step $t$; thus, $s^{i}_{t+1}$ summarizes all
the information gained before time step $t$ and represents a sufficient
statistic of the complete data $y^{i}_{t+1}$ available to agent $i$ for
predicting the joint history. ∎

Lemma 4.1 essentially states that private occupancy states describe a Markov
process.

[] For each agent $i$, the private occupancy state at time step $t$, defined
as $s^{i}_{t}\doteq\Pr\\{X_{t},O_{t}|y^{i}_{t}\\}$, is a sufficient statistic