# Solving Hierarchical Information-Sharing Dec-POMDPs:
An Extensive-Form Game Approach

Johan Peralez  Aurélien Delage  Olivier Buffet  Jilles S. Dibangoye

###### Abstract

A recent theory shows that a multi-player decentralized partially observable
Markov decision process can be transformed into an equivalent single-player
game, enabling the application of Bellman’s principle of optimality to solve
the single-player game by breaking it down into single-stage subgames.
However, this approach entangles the decision variables of all players at each
single-stage subgame, resulting in backups with a double-exponential
complexity. This paper demonstrates how to disentangle these decision
variables while maintaining optimality under hierarchical information sharing,
a prominent management style in our society. To achieve this, we apply the
principle of optimality to solve any single-stage subgame by breaking it down
further into smaller subgames, enabling us to make single-player decisions at
a time. Our approach reveals that extensive-form games always exist with
solutions to a single-stage subgame, significantly reducing time complexity.
Our experimental results show that the algorithms leveraging these findings
can scale up to much larger multi-player games without compromising
optimality.

Machine Learning, ICML

The multi-player decentralized partially observable Markov decision process
(Dec-POMDP) is a general game-theoretic setting for decision-making by a team
of collaborative players (Amato et al., 2013). In this multi-player game,
players must coordinate while they can neither see the actual state of the
world nor explicitly share what they see or do with each other due to
communication costs, latency, or noise. This so-called silent coordination
dilemma provides a partial explanation of the worst-case complexity
results—i.e., infinite-horizon cases are undecidable, finite-horizon ones are
NEXP-hard, and finding $\epsilon$-approximations remains hard (Bernstein et
al., 2002; Rabinovich et al., 2003). Methods for Dec-POMDPs are split between
local and global, each with strengths and weaknesses.

Local methods trade global optima, or $\epsilon$-approximations for weaker
solution concepts, e.g., local optima, Nash equilibria, or any arbitrary
feasible solution. While they share core ideas with global methods, their
primary focus is on solving relaxations of the original multi-player game,
e.g., independent planners reason in isolation, policy gradient targets first-
order solutions of non-convex functions (Tan, 1998; Peshkin et al., 2001; Bono
et al., 2018). Of particular attention, local methods using deep neural
networks can apply effectively to virtually any non-critical application,
e.g., online services, logistics, or board games (Lowe et al., 2017; Foerster
et al., 2018; Rashid et al., 2018).

On the other hand, in many critical and high-stakes applications, e.g., search
and rescue, security, and healthcare, global methods can find solutions with
the required theoretical guarantees, but scalability remains a significant
issue. These algorithms recast the original multi-player game into an
equivalent single-player one, which overcomes the silent coordination dilemma
and allows the principle of optimality to apply. Intuitively, this principle
decomposes the single-player game into single-stage subgames and solves them
recursively. Yet, doing so, in return, virtually entangles decision variables
of all players at each single-stage subgame, resulting in double-exponential
complexity. Because they update decision variables of all players in sync at
every single-stage subgame, even a single update can be prohibitively
expensive (Szer & Charpillet, 2005; MacDermed & Isbell, 2013; Nayyar et al.,
2013; Oliehoek, 2013). To somewhat mitigate this burden, branch-and-bound
search algorithms and mixed-integer linear programs were introduced, but the
limitation remains (Oliehoek et al., 2010; Dibangoye et al., 2009, 2013,
2016). In many cases, however, real-world environments contain significant
structure that can be exploited (Amato et al., 2013).

Indeed, several forms of structure have been investigated in the past—e.g.,
dynamics independence (Becker et al., 2004; Dibangoye et al., 2012), weak-
separability (Nair et al., 2005; Dibangoye et al., 2014), and delayed
information-sharing (Nayyar et al., 2010). Algorithms that use such structures
can optimally solve structured multi-player games much faster than generic
ones. This paper exploits HIS structure, a dominant management style in our
society for corporations, governments, criminal enterprises, armies, and
religions. This management style involves each player being aware of what its
subordinate knows, and this knowledge is passed down the chain of command. In
other words, player $n$ at the top of the hierarchy knows all that player
$n-1$ knows; player $n-2$ knows all that player $n-3$ knows, and so forth.
Moreover, HIS is equivalent to one-sidedness when only two players are
involved, which was previously recognized as a tractable structure for two-
person partially observable stochastic games (Horák et al., 2017; Horák &
Bošanskỳ, 2019; Hadfield-Menell et al., 2016; Malik et al., 2018; Xie et al.,
2020). Still, little is known about how HIS affects existing theory and
algorithms.

The main contribution of this paper is the proof that under the HIS
assumption, perfect-information extensive-form games always exist with
solutions to single-stage subgames, resulting in a significant reduction in
time complexity. When expressed as extensive-form games, one can optimize all
decision variables in isolation while preserving optimality, resulting in an
exponential drop in time complexity, hence generalizing to multiple players a
similar property to that available under one-sidedness (Xie et al., 2020). To
show this result, we apply the principle of optimality to solve any single-
stage subgame by breaking it down further into smaller subgames, enabling us
to make one-player decisions at a time. In the resulting perfect-information
extensive-form game, we exhibit concise representations of states and actions
along with Bellman’s optimality equations to solve the game. Finally, we
present a point-based value-iteration algorithm for solving the original
multi-player game leveraging HIS properties. Experiments show that algorithms
exploiting these findings scale up to much larger multi-player games without
compromising optimality.

##  1 Background

This section presents state-of-the-art multi- and single-player formulations
for Dec-POMDPs under HIS.

#### Notation.

For integers $t_{1}\leq t_{2}$, $\kappa_{t_{1}:t_{2}}$ is a shorthand for
$(\kappa_{t_{1}},\kappa_{t_{1}+1},\ldots,\kappa_{t_{2}})$. Let
$\kappa_{t_{1}:t_{2}}$ be a complete vector, shorthands $\kappa_{t_{1}:}$ and
$\kappa_{:t_{2}}$ denote suffix and prefix, respectively.

###  1.1 Multi-Player Formulation

An $n$-player Dec-POMDP is given by tuple $M\doteq\langle
n,X,U,Z,p,r,s_{0},\gamma,\ell\rangle$, where $X$ is a finite set of hidden
states; $U^{i}$ is the finite actions set for player $i$, where
$U=U^{1}\times\cdots\times U^{n}$ specifies the set of joint actions
$u=(u^{1},\ldots,u^{n})$; $Z^{i}$ is the finite observation set for player
$i$, where $Z=Z^{1}\times\cdots\times Z^{n}$ specifies the set of joint
observations $z=(z^{1},\ldots,z^{n})$; function $p\colon X\times
U\to\triangle(X\times Z)$ describes a transition function with conditional
probability distribution $p(y,z|x,u)$ defining the probability of
transitioning from state $x$ to $y$ after taking joint action $u$ and seeing
$z$; function $r\colon X\times U\to\mathbb{R}$ is a reward model with $r(x,u)$
being the immediate reward received after taking joint action $u$ from state
$x$; $s_{0}$ is the initial state distribution, $\gamma$ is the discount
factor, and $\ell$ is the number of stages.

In the remainder, we consider $M$ under the HIS assumption. That is, every
player $i$ has instantaneous and cost-free access to its subordinate actions
and observations at every stage $\tau$—i.e., for each player $i+1$, there
exists a mapping $\zeta^{i+1}\colon
z_{\tau}^{i+1}\mapsto(u^{:i}_{\tau-1},z^{:i}_{\tau})$ whenever
$\Pr\\{u^{:i}_{\tau-1},z^{:i+1}_{\tau}\\}$ is non-zero then
$\zeta^{i+1}(z_{\tau}^{i+1})=(u^{:i}_{\tau-1},z^{:i}_{\tau})$. Player $1$ is
at the bottom of the hierarchy, i.e., the player whose actions and
observations are public to all other players, and player $n$ is at the top of
the hierarchy, i.e., the player that sees all actions and observations. These
characteristics are embodied in many real-world applications, including
autonomous vehicle platooning, assembly line optimization, or railway traffic
control. Consider an autonomous vehicle platooning that relies on a leading
vehicle followed by a group of autonomous vehicles; see Figure 1. Autonomous
vehicles involved in platooning can exchange information between vehicles
using Vehicle-to-Everything (V2X) communications in an HIS fashion. That is
the total data transit from each autonomous vehicle $i$ to its following
autonomous vehicle $i+1$. The objective of platoon control is to determine the
control input of the following autonomous vehicles so that all the vehicles
move at the same speed while maintaining the desired distances between each
pair of preceding and following vehicles. Platooning constitutes an efficient
technique for increasing road capacity, reducing fuel consumption, and
enhancing driving safety and comfort.

###  1.2 Limitations of Multi-Player Formulations

$~{}n~{}$$i\\!\\!+\\!\\!2$$i\\!\\!+\\!\\!1$$i$$~{}1~{}$$\circ\circ\circ$$\circ\circ\circ$
Figure 1: V2X information transmitted to vehicles in the platooning.

While HIS is a dominant management style in our society, little is known about
how HIS affects existing theories and algorithms. In general, solving $M$ aims
at finding optimal joint policy $a_{0:}\doteq(a_{0},\ldots,a_{\ell-1})$, i.e.,
an $n$-tuple of sequences of private decision rules
$a^{i}_{0:}\doteq(a^{i}_{0},\ldots,a^{i}_{\ell-1})$, one per player. For each
player $i$, private decision rule $a^{i}_{\tau}\colon o^{i}_{\tau}\mapsto
u_{\tau}^{i}$ depends on $\tau$-step histories
$o^{i}_{\tau}\doteq(u^{i}_{0:\tau-1},z^{i}_{1:\tau})$, with $0$-step private
history being $o^{i}_{0}\doteq\emptyset$. A joint policy is optimal if it
maximizes the expected cumulative reward starting at initial state
distribution $s_{0}$ onward and given by
$\upsilon_{0}^{a_{0:}}(s_{0})\doteq\mathbb{E}_{(x_{0},o_{0})\sim\Pr\\{\cdot|s_{0},a_{0:}\\}}\\{\alpha_{0}^{a_{0:}}(x_{0},o_{0})\\}$
where
$\alpha_{\tau}^{a_{\tau:}}(x_{\tau},o_{\tau})\doteq\mathbb{E}_{(x_{\tau:\ell-1},u_{\tau:\ell-1})\sim\Pr\\{\cdot|x_{\tau},o_{\tau},a_{\tau:}\\}}\\{\textstyle{\sum_{t=\tau}^{\ell-1}}~{}\gamma^{\tau-t}\cdot
r(x_{t},u_{t})\\}$ for any game stage $\tau$. Unfortunately, optimally solving
$M$ in its multi-player formulation is non-trivial because of the silent
coordination dilemma (Rabinovich et al., 2003). Indeed, no statistics on what
the players see and do are sufficient to solve $M$ optimally. Private
histories $o^{i}_{\tau}$ are not geared to perform policy evaluation, let
alone policy ordering. In addition, joint histories
$o_{\tau}\doteq(o^{1}_{\tau},\ldots,o^{n}_{\tau})$ cannot ensure policy
disentanglement, i.e., an individual policy per player. To better understand
this, notice that multi-player coordination is based on common ground, i.e.,
knowledge, beliefs, and assumptions shared among players about the environment
at each stage, making it possible to perform policy ordering and
disentanglement. Paradoxically, $M$ aims to coordinate agents without common
ground, thus explaining the silent coordination dilemma. The motivation for a
single-player reformulation is twofold: first, to provide the central planner
with the common ground at the offline planning phase, which achieves policy
ordering and disentanglement, then to ease the transfer of theories and
algorithms from single- to multi-player formulations.

###  1.3 Single-Player Reformulation

The single-player reformulation describes $M$ from the perspective of an
offline central planner (Szer & Charpillet, 2005; Nayyar et al., 2013;
Oliehoek, 2013; Dibangoye et al., 2013, 2016). This planner reasons for all
players in sync, prescribing a joint decision rule and receiving rewards and
public observations. Game $M$ lies in some underlying state and players have
experienced a joint history at each plan-time stage. Unfortunately, the
central planner can see neither the state nor the joint history. Yet, it can
still prescribe to players what joint decision rule to follow based only upon
the joint policy it has prescribed to players so far. Upon executing the
prescribed joint decision rule, the central planner receives the expected
immediate reward and the next public observation, i.e., the information of
player $1$. This process follows at the next plan-time stage, but the game has
another underlying state, and players are experiencing another joint history.
This process repeats until the number of stages is exhausted. The summary of
the history of prescribed joint decision rules and received public
observations, i.e., occupancy state, describes a Markov decision process.
Occupancy states proved to be common ground for coordinating players under the
silent coordination dilemma, i.e., occupancy states are sufficient statistics
for optimal decision-making in Dec-POMDPs (Dibangoye et al., 2013, 2016).

Markov decision process $M^{\prime}\doteq\langle
S,A,\boldsymbol{T},\boldsymbol{R},s_{0},\gamma,\ell\rangle$ w.r.t. $M$
consists of the occupancy-state space $S$, where occupancy states are
conditional probability distribution over hidden states and joint histories;
the action space $A$ prescribing joint decision rules; the transition
probability $\boldsymbol{T}\colon S\times A\to\triangle(S)$, where
$\boldsymbol{T}(s_{\tau},a_{\tau},s_{\tau+1})\doteq\sum_{o,z}\delta_{\rho(s_{\tau},a_{\tau},z^{1})}^{s_{\tau+1}}\sum_{x,y}{s}_{\tau}(x,o)\cdot
p(y,z|x,a_{\tau}(o))$, where the next occupancy state
$s_{\tau+1}\doteq\rho(s_{\tau},a_{\tau},z^{1}_{\tau+1})$ follows from taking
joint decision rule $a_{\tau}$ in occupancy state $s_{\tau}$ and then
receiving public observation $z^{1}_{\tau+1}$, i.e., for any arbitrary hidden
state $y$ and joint history $(o,u,z)$, we have
${s}_{\tau+1}(y,(o,u,z))\propto~{}\sum_{x}{s}_{\tau}(x,o)\cdot\delta_{z_{\tau+1}^{1}}^{z^{1}}\cdot\delta_{a_{\tau}(o)}^{u}\cdot
p(y,z|x,u)$; and finally, $\boldsymbol{R}\colon{S}\times{A}\to\mathbb{R}$ is
the expected immediate reward function, i.e.,
$\boldsymbol{R}({s}_{\tau},{a}_{\tau})\doteq\sum_{x,o}{s}_{\tau}(x,o)\cdot
r(x,{a}_{\tau}(o))$. Recasting the original multi-player game into an
equivalent single-player one allows the principle of optimality to solve the
single-player game by breaking it down into single-stage subgames and solving
them recursively. Consequently, optimally solving $M$ aims at finding
solutions $V_{\tau}^{*}(s_{\tau})$ of single-stage subgame for every occupancy
state $s_{\tau}$, i.e.,
$V_{\tau}^{*}(s_{\tau})=\max_{a_{\tau}}Q^{*}_{\tau}(s_{\tau},a_{\tau})$, where
$\textstyle
Q^{*}_{\tau}(s_{\tau},a_{\tau})\doteq\boldsymbol{R}(s_{\tau},a_{\tau})+\gamma\sum_{s_{\tau+1}}\boldsymbol{T}(s_{\tau},a_{\tau},s_{\tau+1})\cdot
V^{*}_{\tau+1}(s_{\tau+1})$ with boundary condition $V^{*}_{\ell}(\cdot)\doteq
0$. Each occupancy state $s_{\tau}$ has its corresponding single-stage subgame
$G_{s_{\tau}}\doteq\langle n,A,Q^{*}_{\tau}(s_{\tau},\cdot)\rangle$, whose
solution is $V^{*}_{\tau}(s_{\tau})$. Optimally solving single-stage subgame
$G_{s_{\tau}}$ is significantly more efficient by leveraging the piecewise-
linearity and convexity property of action-value functions $Q^{*}_{\tau}$.

######  Lemma 1.1.

For every game stage $\tau$, the optimal value function $Q^{*}_{\tau}\colon
S\times A\to\mathbb{R}$ is piecewise-linear and convex over occupancy states
and joint decision rules. Alternatively, there exists a finite collection
${\mathcal{Q}}_{\tau}\subseteq\\{\beta^{a_{\tau+1:}}_{\tau}|a_{\tau+1:}\in
A_{\tau+1:}\\}$ of action-value functions $\beta^{a_{\tau+1:}}_{\tau}$ under
joint policy $a_{\tau+1:}$, such that: for occupancy state $s_{\tau}$ and
joint decision rule $a_{\tau}$,

${Q}^{*}_{\tau}({s}_{\tau},{a}_{\tau})=\textstyle\max_{\beta_{\tau}\in{\mathcal{Q}}_{\tau}}~{}\mathbb{E}_{(x,o,u)\sim\Pr\\{\cdot|{s}_{\tau},{a}_{\tau}\\}}\\{\beta_{\tau}(x,o,u)\\}$
$\beta^{a_{\tau+1:}}_{\tau}(x,o,u)=r(x,u)+\textstyle\gamma\mathbb{E}_{(y,z)\sim
p(\cdot|x,u)}\\{\alpha^{a_{\tau+1:}}_{t+1}(y,(o,z))\\}$

with boundary condition
$\alpha^{\cdot}_{\ell}(\cdot)=\beta^{\cdot}_{\ell}(\cdot)\doteq 0$.

Lemma 1.1 allows us to optimally solve a single-stage subgame $G_{s_{\tau}}$
by taking the best among solutions of single-stage subgames
$G_{s_{\tau}}^{\beta_{\tau}}\doteq\langle
n,A,Q_{\beta_{\tau}}(s_{\tau},\cdot)\rangle$ induced by action-value function
$\beta_{\tau}\in\mathcal{Q}_{\tau}$ under a fixed joint policy, where
$Q_{\beta_{\tau}}(s_{\tau},\cdot)\colon
a_{\tau}\mapsto\mathbb{E}_{(x,o,u)\sim\Pr\\{\cdot|s_{\tau},a_{\tau}\\}}\\{\beta_{\tau}(x,o,u)\\}$.
In particular, the linearity of $Q_{\beta_{\tau}}(s_{\tau},\cdot)$ over joint
decision rules will play a crucial role in disentangling decision variables.

###  1.4 Limitations of Single-Player Reformulations

The single-player reformulation applies under HIS, but the curse of
dimensionality restricts its scalability in the face of games with many
players. To better understand this, notice that the complexity of optimally
solving a single-player reformulation depends on two operators: the point-
based backup operator, which optimally solves single-stage subgame
$G_{s_{\tau}}^{\beta_{\tau}}$, and the estimation operator, which updates all
decision variables involved in the common ground, i.e., occupancy states. In
either case, the single-player reformulation is not geared to exploit HIS.
State-of-the-art approaches to solving $G_{s_{\tau}}^{\beta_{\tau}}$ perform
either brute-force or implicit enumeration and evaluation of double-
exponentially many joint decision rules (Oliehoek et al., 2010; Dibangoye et
al., 2009, 2013, 2016). This provides an intuitive explanation for the
negative complexity results: optimally solving $G_{s_{\tau}}^{\beta_{\tau}}$
is NP-hard, and finding $\epsilon$-approximations remains hard (Tsitsiklis,
1984). The estimation operator also suffers from the curse of dimensionality.
Indeed, the number of decision variables of all players in the common ground
under the silent coordination dilemma grows exponentially with time and team
size. In this paper, we investigate the following question.

_How can we improve the representations of common ground and Bellman
optimality equations to scale-up point-based backup and estimation operators
to optimally solving $G_{s_{\tau}}^{\beta_{\tau}}$and eventually $M^{\prime}$
(resp. $M$) under HIS?_

##  2 Hierarchical Information Sharing

This section explores the ramifications of HIS assumption in achieving an
optimal solution for a single-stage subgame, specifically,
$G_{s_{\tau}}^{\beta_{\tau}}$.

###  2.1 From Single-Stage to Extensive-Form Games

While the principle of optimality allows us to break down the single-player
reformulation $M^{\prime}$ into smaller subgames $G_{s_{\tau}}^{\beta_{\tau}}$
per stage, an alternative approach is to segment single-stage subgames
$G_{s_{\tau}}^{\beta_{\tau}}$ per player further. That allows the centralized
planner to act sequentially for each player, starting from player $1$ up to
player $n$. In addition, instead of choosing a decision rule for each player
based on the current occupancy state and decision rules selected thus far, the
planner can independently branch over each history that HIS makes available to
the current player, without compromising optimality. A formal description of
this process follows.

Starting from player $1$ at the bottom of the hierarchy, cf. Figure 2, the
planner chooses action $u^{1}_{\tau}$ according to its total available
information $\varsigma^{1}_{\tau}=(s_{\tau},o_{\tau}^{1})$. It then moves to
player $2$, the next player in the reversed order of the hierarchy, but now it
randomly lands on total available information
$\varsigma^{2}_{\tau}=(\varsigma_{\tau}^{1},u^{1}_{\tau},o_{\tau}^{2})$ and
chooses action $u^{2}_{\tau}$. The process continues until the planner reaches
player $n$ at the top of the hierarchy, where it randomly lands on total
available information
$\varsigma^{n}_{\tau}=(\varsigma_{\tau}^{n-1},u^{n-1}_{\tau},o_{\tau}^{n})$
and chooses action $u_{\tau}^{n}$ and receives expected rewards
$R(\varsigma_{\tau}^{n},u_{\tau}^{n})\doteq\mathbb{E}_{x\sim\Pr\\{\cdot|\varsigma_{\tau}^{n},u_{\tau}^{n}\\}}\\{\beta_{\tau}(x,o,u)\\}$
upon taking action $u_{\tau}^{n}$ in information state $\varsigma_{\tau}^{n}$.
Upon acting sequentially for $i$ players, the total information available to
the planner denoted
$\varsigma_{\tau}^{i+1}\doteq(\varsigma_{\tau}^{i},u^{i}_{\tau},o_{\tau}^{i+1})$,
is the current occupancy state $s_{\tau}$ of the single-stage subgame
$G_{s_{\tau}}^{\beta_{\tau}}$ along with the sequence of actions that the
planner selected and private histories that the planner received according to
probability
$T(\varsigma_{\tau}^{i+1}|\varsigma_{\tau}^{i})\doteq\Pr\\{o_{\tau}^{i+1}|s_{\tau},o_{\tau}^{1},\ldots,o_{\tau}^{i}\\}\cdot\delta_{\varsigma_{\tau}^{i},u^{i}_{\tau},o_{\tau}^{i+1}}^{\varsigma_{\tau}^{i+1}}$.

$\varsigma^{1}$$u^{1}$$\varsigma_{\tau}$$\varsigma_{\square}^{2}$$\varsigma_{\tau}$$\varsigma_{{\color[rgb]{0.76953125,0,0.390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0,0.390625}\square}}^{2}$$\cdots$$\cdots$$u^{1}$$\varsigma_{\tau}$$\varsigma_{{\color[rgb]{0.76953125,0,0.390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0,0.390625}\square}}^{2}$$\varsigma_{\tau}$$\varsigma_{\square}^{2}$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$u^{1}$$u^{1}$$\square$${\color[rgb]{0.76953125,0,0.390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0,0.390625}\square}$${\color[rgb]{0.76953125,0,0.390625}\definecolor[named]{pgfstrokecolor}{rgb}{0.76953125,0,0.390625}\square}$$\square$
Figure 2: The search space for a single-stage subgame from a centralized
planner acting sequentially one player at a time, illustrated as an AND/OR
tree. OR nodes (triangle) represent alternative ways to solve
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$. AND nodes (circle) represent subproblem
alternatives to be solved. Best viewed in color.

The total available information of the sequential-move central planner when
solving a single-stage subgame describes a common-payoff perfect-information
extensive-form game (Shoham & Leyton-Brown, 2008).

######  Definition 2.1.

The common-payoff perfect-information extensive-form game w.r.t.
$G_{s_{\tau}}^{\beta_{\tau}}$ is a tuple
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}\doteq\langle n,\Sigma,\Psi,T,R\rangle$
where: $n$ is the number of players; $\Sigma$ is the set of nodes that
occupancy state $s_{\tau}$ induces; $\Psi\colon\Sigma\to
2^{\cup_{i=1}^{n}U^{i}}$ is a function that specifies the allowed actions from
each node $\varsigma\in\Sigma$; transition function
$T\colon\Sigma\times(\cup_{i=1}^{n}U^{i})\times\Sigma\to[0,1]$ specifies the
probability of a successor node; reward function
$R\colon\Sigma\times(\cup_{i=1}^{n}U^{i})\to\mathbb{R}$ specifies the common
payoff received upon taking an action in a node.

###  2.2 Optimally Solving $G_{s_{\tau}}^{\beta_{\tau}}$ As
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$

Optimally solving a common-payoff perfect-information extensive-form game aims
at finding the action-value functions $\beta^{1:n,*}_{\tau}$ mapping nodes and
actions to optimal values. Unlike the original single-stage subgame
$G_{s_{\tau}}^{\beta_{\tau}}$, the perfect information extensive form game
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ makes the HIS structure explicit. Every
time the planner acts on behalf of a player, that player is perfectly informed
about all the histories that have previously occurred—i.e., all histories of
its subordinates. Hence, the total information nodes include the actions the
planner selected for the subordinates of the current player, along with the
histories of its subordinates. Nonetheless, both games yield the same
solution.

######  Theorem 2.2.

Any optimal solution for $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ is also an
optimal solution for $G_{s_{\tau}}^{\beta_{\tau}}$. Besides, the optimal
action-value functions $\beta^{1:n,*}_{\tau}$ of
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ is the solution of the Bellman’s
optimality equations: at any $i$, $\varsigma_{\tau}^{i}$, and $u_{\tau}^{i}$,

$\displaystyle\beta^{i,*}_{\tau}(\varsigma_{\tau}^{i},u^{i}_{\tau})$
$\displaystyle=\mathbb{E}_{\varsigma_{\tau}^{i+1}\sim
T(\cdot|\varsigma_{\tau}^{i},u^{i}_{\tau})}\\{\max_{u^{i+1}_{\tau}}\beta_{\tau}^{i+1,*}(\varsigma_{\tau}^{i+1},u_{\tau}^{i+1})\\},$

with boundary condition
$\beta_{\tau}^{n,*}\colon(\varsigma_{\tau}^{n},u^{n}_{\tau})\mapsto
R(\varsigma_{\tau}^{n},u^{n}_{\tau})$. Also, greedy decision rule
$a^{i,*}_{\tau}$ for any player $i$ at $o^{i}_{\tau}$ is:

$\displaystyle a^{i,*}_{\tau}(o^{i}_{\tau})$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{u^{i}_{\tau}}\beta^{i,*}_{\tau}(\varsigma^{i}_{\tau},u^{i}_{\tau}),$

where $\varsigma^{i}_{\tau}\doteq\langle
s_{\tau},o^{1:i}_{\tau},a^{1:i-1,*}_{\tau}(o^{1:i-1}_{\tau})\rangle$.

###### Proof.

The proof proceeds in two steps. First, it shows that the original game
$G_{s_{\tau}}^{\beta_{\tau}}$ can alternatively be solved via a sequential-
move central planner, which breaks $G_{s_{\tau}}^{\beta_{\tau}}$ down into
smaller subgames $\langle
G_{s_{\tau},\emptyset}^{\beta_{\tau}},G_{s_{\tau},a^{1}_{\tau}}^{\beta_{\tau}},\ldots,G_{s_{\tau},a^{1:n-1}_{\tau}}^{\beta_{\tau}}\rangle$,
one subgame per player. To this end, recall the goal of optimally solving
$G_{s_{\tau}}^{\beta_{\tau}}$, i.e., finding a joint decision rule which
yields the highest performance index,
$V_{\beta_{\tau}}(s_{\tau})\doteq\max_{a_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau})$.
The expansion of joint decision rule $a_{\tau}$ as a $n$-tuple of private
decision rules $(a^{1}_{\tau},a^{2}_{\tau},\ldots,a^{n}_{\tau})$ allows to
rewite the objectif of $G_{s_{\tau}}^{\beta_{\tau}}$ as follows,
$V_{\beta_{\tau}}(s_{\tau})=\max_{a^{1}_{\tau}}\max_{a^{2}_{\tau}}\ldots\max_{a^{n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau})$.
Let $Q^{i}_{\beta_{\tau}}(s_{\tau},\cdot)\colon
a^{1:i}_{\tau}\mapsto\max_{a^{i+1:n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau})$
be a sequential action-value function. Then, it follows that

$\displaystyle V_{\beta_{\tau}}(s_{\tau})$
$\displaystyle=\max_{a^{1}_{\tau}}\max_{a^{2}_{\tau}}\ldots\max_{a^{n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau}),$
$\displaystyle=\max_{a^{1}_{\tau}}~{}\left[\max_{a^{2}_{\tau}}\ldots\max_{a^{n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau})\right],$
$\displaystyle=\max_{a^{1}_{\tau}}~{}Q^{1}_{\beta_{\tau}}(s_{\tau},a^{1}_{\tau}).$

Interestingly, for every player $i\in\\{1,2,\ldots,n-1\\}$, the action-value
functions $Q^{i}_{\beta_{\tau}}(s_{\tau},a^{1:i}_{\tau})$ satisfy the
following recursion

$\displaystyle Q^{i}_{\beta_{\tau}}(s_{\tau},a^{1:i}_{\tau})$
$\displaystyle=\max_{a^{i+1}_{\tau}}\max_{a^{i+2}_{\tau}}\ldots\max_{a^{n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau}),$
$\displaystyle=\max_{a^{i+1}_{\tau}}~{}\left[\max_{a^{i+2}_{\tau}}\ldots\max_{a^{n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau})\right],$
$\displaystyle=\max_{a^{i+1}_{\tau}}~{}Q^{i+1}_{\beta_{\tau}}(s_{\tau},a^{1:i+1}_{\tau}),$

with boundary condition $Q^{n}_{\beta_{\tau}}(s_{\tau},a_{\tau})\doteq
Q_{\beta_{\tau}}(s_{\tau},a_{\tau})$. For any arbitrary player
$i\in\\{2,3,\ldots,n\\}$, define game
$G^{\beta_{\tau}}_{s_{\tau},a^{1:i-1}_{\tau}}\doteq\langle
i,A^{i},Q^{i}_{\beta_{\tau}}(s_{\tau},a^{1:i-1}_{\tau},\cdot)\rangle$ to be
the subgame upon the sequential-move central planner selected decision rules
$a^{1:i-1}_{\tau}$ starting in game $G_{s_{\tau}}^{\beta_{\tau}}$, with
boundary condition $G^{\beta_{\tau}}_{s_{\tau},\emptyset}\doteq\langle
1,A^{1},Q^{1}_{\beta_{\tau}}(s_{\tau},\cdot)\rangle$. Consequently, optimally
solving the original game $G_{s_{\tau}}^{\beta_{\tau}}$ can be performed by
optimally solving smaller subgames $\langle
G_{s_{\tau},\emptyset}^{\beta_{\tau}},G_{s_{\tau},a^{1}_{\tau}}^{\beta_{\tau}},\ldots,G_{s_{\tau},a^{1:n-1}_{\tau}}^{\beta_{\tau}}\rangle$,
one subgame per player, recursvively.

Next, we shall prove that the best decision rule in any arbitrary sequential-
move subgame $G^{\beta_{\tau}}_{s_{\tau},a^{1:i-1}_{\tau}}$ depends on the
current occupancy state $s_{\tau}$ along with previously selected decision
rules $a^{1:i-1}_{\tau}$, only through the corresponding nodes
$\varsigma_{\tau}^{i}\doteq(s_{\tau},u^{1:i-1}_{\tau},o^{1:i}_{\tau})$ of the
perfect information extensive form game $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$.
In other words, instead of selecting actions for all private histories of
player $i$ in sync, one can choose the best action for each private history
independently without compromising optimality. The proof of this statement
proceeds by induction from player $n$ to player $1$. At player $n$, the greedy
decision rule $\hat{a}^{n}_{\tau}$ satisfies the following:

$\displaystyle\hat{a}^{n}_{\tau}$
$\displaystyle\in\textstyle\operatorname*{\arg\\!\max}_{a^{n}_{\tau}}~{}Q^{n}_{\beta_{\tau}}(s_{\tau},a_{\tau}),$
$\displaystyle\in\textstyle\operatorname*{\arg\\!\max}_{a^{n}_{\tau}}~{}Q_{\beta_{\tau}}(s_{\tau},a_{\tau}),$
$\displaystyle\in\textstyle\operatorname*{\arg\\!\max}_{a^{n}_{\tau}}~{}\mathbb{E}_{(x,o,u)\sim\Pr\\{\cdot|s_{\tau},a_{\tau}\\}}\\{\beta_{\tau}(x,o,u)\\}.$

Expanding over private histories of player $n$, we have that

$\displaystyle\hat{a}^{n}_{\tau}(o^{n}_{\tau})$
$\displaystyle\in\textstyle\operatorname*{\arg\\!\max}_{u^{n}_{\tau}}~{}\mathbb{E}_{(x,o,u)\sim\Pr\\{\cdot|s_{\tau},o^{n}_{\tau},a_{\tau}\\}}\\{\beta_{\tau}(x,o,u)\\}.$

Leveraging information available to player $n$ as provided by the HIS
assumption, we know that the knowledge of private history $o_{\tau}^{n}$
implies the knowledge of histories of all other players $o^{1:n-1}_{\tau}$,
hence the joint history $o_{\tau}$, i.e.,

$\displaystyle\hat{a}^{n}_{\tau}(o^{n}_{\tau})$
$\displaystyle\in\textstyle\operatorname*{\arg\\!\max}_{u^{n}_{\tau}}~{}\mathbb{E}_{x\sim\Pr\\{\cdot|s_{\tau},o_{\tau},a_{\tau}\\}}\\{\beta_{\tau}(x,o,u)\\}.$

In addition, the knowledge of $o^{1:n-1}_{\tau}$ together with the decision
rules $a^{1:n-1}_{\tau}$ the sequential-move central planner selected
previously, makes it possible to access node
$\varsigma_{\tau}^{n}\doteq\langle
s_{\tau},o^{1:n}_{\tau},a^{1:n-1}_{\tau}(o^{1:n-1}_{\tau})\rangle$ such that:

$\displaystyle\hat{a}^{n}_{\tau}(o^{n}_{\tau})$
$\displaystyle\in\textstyle\operatorname*{\arg\\!\max}_{u^{n}_{\tau}}~{}\beta_{\tau}^{n}(\varsigma_{\tau}^{n},u^{n}_{\tau}),$

where
$\beta_{\tau}^{n}\colon(\varsigma_{\tau}^{n},u^{n}_{\tau})\mapsto\mathbb{E}_{x\sim\Pr\\{\cdot|\varsigma_{\tau}^{n},u^{n}_{\tau}\\}}\\{\beta_{\tau}(x,o,u)\\}$,
which proves the statement holds at player $n$. Define function
$\alpha_{\tau}^{n}\colon\varsigma_{\tau}^{n}\mapsto\max_{u^{n}_{\tau}}\beta_{\tau}^{n}(\varsigma_{\tau}^{n},u_{\tau}^{n})$
at player $n$. Notice that the value of the sequential-move subgame
$G^{\beta_{\tau}}_{s_{\tau},a^{1:n-1}_{\tau}}$ can be rewritten as follows:

$\displaystyle Q^{n-1}_{\beta_{\tau}}(s_{\tau},a_{\tau}^{1:n-1})$
$\displaystyle=\max_{a^{n}_{\tau}}Q^{n}_{\beta_{\tau}}(s_{\tau},a_{\tau})$
$\displaystyle=\mathbb{E}_{\varsigma_{\tau}^{n}\sim\Pr\\{\cdot|s_{\tau},a_{\tau}^{1:n-1}\\}}\\{\max_{u^{n}_{\tau}}\beta_{\tau}^{n}(\varsigma_{\tau}^{n},u^{n}_{\tau})\\}$
$\displaystyle=\mathbb{E}_{\varsigma_{\tau}^{n}\sim\Pr\\{\cdot|s_{\tau},a_{\tau}^{1:n-1}\\}}\\{\alpha_{\tau}^{n}(\varsigma_{\tau}^{n})\\}.$

Suppose the statement holds for any player $i>1$, with greedy decision rule
$\hat{a}^{i}_{\tau}(o^{i}_{\tau})\in\operatorname*{\arg\\!\max}_{u^{i}_{\tau}}~{}\beta_{\tau}^{i}(\varsigma_{\tau}^{i},u^{i}_{\tau})$.
Define function
$\alpha_{\tau}^{i}\colon\varsigma_{\tau}^{i}\mapsto\max_{u^{i}_{\tau}}\beta_{\tau}^{i}(\varsigma_{\tau}^{i},u_{\tau}^{i})$
at player $i$. Also, the value of the sequential-move subgame
$G^{\beta_{\tau}}_{s_{\tau},a^{1:i-1}_{\tau}}$ can be rewritten by expanding
over the sequential-move nodes $\varsigma_{\tau}^{i}\doteq\langle
s_{\tau},o^{1:i}_{\tau},a^{1:i-1}_{\tau}(o^{1:i-1}_{\tau})\rangle$, i.e.,

$\displaystyle Q^{i-1}_{\beta_{\tau}}(s_{\tau},a_{\tau}^{1:i-1})$
$\displaystyle=\mathbb{E}_{\varsigma_{\tau}^{i}\sim\Pr\\{\cdot|s_{\tau},a_{\tau}^{1:i-1}\\}}\\{\alpha_{\tau}^{i}(\varsigma_{\tau}^{i})\\}.$

We are now ready to prove the statement also holds at player $i-1$. From the
sequential-move central planner’s viewpoint, decision rule
$\hat{a}_{\tau}^{i-1}$ satisfies the following expression:

$\displaystyle\hat{a}^{i-1}_{\tau}$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{a^{i-1}_{\tau}}~{}Q^{i-1}_{\beta_{\tau}}(s_{\tau},a^{1:i-1}_{\tau}),$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{a^{i-1}_{\tau}}\mathbb{E}_{\varsigma_{\tau}^{i}\sim\Pr\\{\cdot|s_{\tau},a_{\tau}^{1:i-1}\\}}\\{\alpha_{\tau}^{i}(\varsigma_{\tau}^{i})\\}.$

Similarly to player $n$, the knowledge of $o^{1:i-1}_{\tau}$ together with the
decision rules $a^{1:i-2}_{\tau}$ the sequential-move central planner selected
previously, makes it possible to access node
$\varsigma_{\tau}^{i-1}\doteq\langle
s_{\tau},o^{1:i-1}_{\tau},a^{1:i-2}_{\tau}(o^{1:i-2}_{\tau})\rangle$ such
that:

$\displaystyle\hat{a}^{i-1}_{\tau}(o^{i-1}_{\tau})$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{u^{i-1}_{\tau}}~{}\beta_{\tau}^{i-1}(\varsigma_{\tau}^{i-1},u_{\tau}^{i-1}),$

where
$\beta_{\tau}^{i-1}\colon(\varsigma_{\tau}^{i-1},u_{\tau}^{i-1})\mapsto\mathbb{E}_{\varsigma_{\tau}^{i}\sim\Pr\\{\cdot|\varsigma_{\tau}^{i-1},u_{\tau}^{i-1}\\}}\\{\alpha_{\tau}^{i}(\varsigma_{\tau}^{i})\\}$,
which proves the statement holds at player $i-1$. Define function
$\alpha_{\tau}^{i-1}\colon\varsigma_{\tau}^{i-1}\mapsto\max_{u^{i-1}_{\tau}}\beta_{\tau}^{i-1}(\varsigma_{\tau}^{i-1},u_{\tau}^{i-1})$
at player $i-1$. Consequently, the value of the sequential-move subgame
$G^{\beta_{\tau}}_{s_{\tau},\emptyset}$ can be rewritten by expanding over the
sequential-move nodes $\varsigma_{\tau}^{1}\doteq\langle
s_{\tau},o^{1}_{\tau}\rangle$, i.e.,

$\displaystyle V_{\beta_{\tau}}(s_{\tau})$
$\displaystyle=\mathbb{E}_{\varsigma_{\tau}^{1}\sim\Pr\\{\cdot|s_{\tau}\\}}\\{\alpha_{\tau}^{1}(\varsigma_{\tau}^{1})\\}.$

The value of a cooperative game being unique, we know the optimal solution for
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ is also an optimal solution for
$G_{s_{\tau}}^{\beta_{\tau}}$. In demonstrating this statement, we also
exhibited Bellman’s optimality equations, providing the solution of the
perfect-information extensive-form game $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$,
i.e., at any player $i$, node $\varsigma_{\tau}^{i}$, and action
$u_{\tau}^{i}$,

$\displaystyle\beta^{i,*}_{\tau}(\varsigma_{\tau}^{i},u^{i}_{\tau})$
$\displaystyle=\mathbb{E}_{\varsigma_{\tau}^{i+1}\sim
T(\cdot|\varsigma_{\tau}^{i},u^{i}_{\tau})}\\{\max_{u^{i+1}_{\tau}}\beta_{\tau}^{i+1,*}(\varsigma_{\tau}^{i+1},u_{\tau}^{i+1})\\},$

with boundary condition
$\beta_{\tau}^{n,*}\colon(\varsigma_{\tau}^{n},u^{n}_{\tau})\mapsto
R(\varsigma_{\tau}^{n},u^{n}_{\tau})$. Which ends the proof. ∎

Theorem 2.2 introduces Bellman’s optimality equations that enable us to find a
greedy joint decision at single-stage subgame $G_{s_{\tau}}^{\beta_{\tau}}$ by
solving the corresponding extensive-form game
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$. It proceeds in two phases. From player
$n$ at the top of the hierarchy to player $1$ at the bottom, a backward pass
computes optimal action-values
$\beta^{i,*}_{\tau}(\varsigma_{\tau}^{i},u_{\tau}^{i})$ for each player $i$,
each node $\varsigma^{i}_{\tau}$, and each action $u_{\tau}^{i}$. Then, from
player $1$ at the bottom of the hierarchy to player $n$ at the top, a forward
pass selects a greedy decision rule independently for each player $i$, and
each node $\varsigma_{\tau}^{i}$. This backward induction algorithm requires a
linear time complexity with the number of players, nodes, and actions
$\mathbf{O}(n|\Sigma||U^{*}|)$ instead of double exponential
$\mathbf{O}(|O^{*}|^{|U^{*}|^{n}})$ where
$O^{*}\doteq\operatorname*{\arg\\!\max}_{O^{i}}|O^{i}|$ with $O^{i}$ being the
set of reachable histories of player $i$ in $s_{\tau}$ and
$U^{*}\doteq\operatorname*{\arg\\!\max}_{U^{i}}|U^{i}|$. A careful reader
would notice that the linearity of $\beta_{\tau}$ over occupancy states and
joint decision rules is key in demonstrating Theorem 2.2.

###  2.3 Nested-Occupancy States

Upon inspection of perfect-information extensive-form game
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$, one can see that despite the polynomial-
time complexity of the point-based backup, $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$
may contain a significant number of nodes. That is because nodes in
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ provide total information available to the
planner at any player $i$—i.e., $\varsigma_{\tau}^{i}\doteq\langle
s_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau}\rangle$, which may result in redundant
and unnecessary computations. To address this challenge, we propose the
introduction of a statistic referred to as _nested-occupancy state_ that we
shall maintain in place of the total information available to the planner.

At player $i$, a nested-occupancy state
$s^{i}_{\tau}\doteq(b^{i}_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau})$ consists of a
private history $o^{i}_{\tau}$ of player $i$, the actions of its subordinates
$u^{:i-1}_{\tau}$, and a nested-belief state $b^{i}_{\tau}$. Besides, the
nested-belief state $b^{i}_{\tau}$ at player $i$ is a posterior distribution
over histories $o^{i+1}_{\tau}$ and nested-belief states $b^{i+1}_{\tau}$ of
the immediate superior player $i+1$. This distribution is conditional on the
total data available to the planner at player $i$, i.e.,
$b^{i}_{\tau}(o^{i+1}_{\tau},b^{i+1}_{\tau})\doteq\Pr\\{o^{i+1}_{\tau},b^{i+1}_{\tau}|\varsigma^{i}_{\tau}\\}$,
for any histories $o^{i+1}_{\tau}$ and nested-belief states $b^{i+1}_{\tau}$;
with boundary condition
$b^{n}_{\tau}(x_{\tau})\doteq\Pr\\{x_{\tau}|\varsigma^{n}_{\tau}\\}$, for any
hidden state $x_{\tau}$. Interestingly, the nested-occupancy state has many
important properties. First, it is a sufficient statistic for optimally
solving $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$.

######  Theorem 2.3 (Proof in Appendix B).

At player $i$, the nested-occupancy state $s^{i}_{\tau}$ is a sufficient
statistic of the total data $\varsigma_{\tau}^{i}$ available to the planner
for optimally solving the perfect-information extensive-form game
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$.

Theorem 2.3 suggests using a nested-occupancy state as an alternative to the
total data available to the planner without compromising optimality. This
statistic facilitates the aggregation of histories of a player that convey the
same information about the game, thus effectively reducing the dimensionality
of the game. Prior to delving further, it is necessary to introduce three
equivalence relations. First, two nested-occupancy states at player $i$,
represented as
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\doteq(b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$
and
$s_{\tau}^{i,\circ}\doteq(b^{i,\circ}_{\tau},o^{i,\circ}_{\tau},u^{:i-1,\circ}_{\tau})$,
are considered $\mathscr{B}_{1}$-equivalent if they differ only through their
histories, i.e., whenever
$(b^{i,\circ}_{\tau},u^{:i-1,\circ}_{\tau})=(b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$
then
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\sim_{\mathscr{B}_{1}}s_{\tau}^{i,\circ}$.
Similarly, they are considered $\mathscr{B}_{2}$-equivalent if they share the
same nested-belief state and histories of subordinates, i.e., whenever
$(b^{i,\circ}_{\tau},o^{i-1,\circ}_{\tau})=(b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},o^{i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$
then
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\sim_{\mathscr{B}_{2}}s_{\tau}^{i,\circ}$.
Last, two private histories are considered $\mathscr{P}$-equivalent if their
optimal actions or, more generally, policies are interchangeable.

######  Theorem 2.4 (Proof in Appendix C.4).

Let $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ be a perfect-information extensive-
form game. Let
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>be two nested-occupancy states induced by occupancy state $s_{\tau}$ at player
$i$. The following properties hold.

  1. 1.

If
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\sim_{\mathscr{B}_{1}}s_{\tau}^{i,\circ}$
then
$\beta^{i,*}_{\tau}(s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}},u^{i}_{\tau})=\beta^{i,*}_{\tau}(s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\circ}},u^{i}_{\tau})$.

  2. 2.

If
$s_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\sim_{\mathscr{B}_{2}}s_{\tau}^{i,\circ}$
then
$o_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\sim_{\mathscr{P}}o_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>
Theorem 2.4 establishes that two $\mathscr{B}_{1}$-equivalent nested-occupancy
states have the same optimal actions, resulting in significant computational
savings. Moreover, it showcases that two $\mathscr{B}_{2}$-equivalent nested-
occupancy states have their corresponding histories following the same policy.
This insight allows for compact occupancy states, wherein only one history per
equivalent class is retained, leading to faster estimations. Similarly,
Dibangoye et al. (2016) employed compact occupancy states while utilizing the
complete distribution over hidden states and histories of all teammates to
determine when two histories are equivalent. Our equivalence relations,
however, are based on nested belief states that are more concise than
occupancy states, resulting in a more aggressive compression. At player $n$,
for instance, the planner groups together histories that share the belief
state, and this process continues down the hierarchy.

##  3 Near-Optimally Solving $M^{\prime}$ Under HIS

This section adapts the point-based value-iteration (PBVI) algorithm (Pineau
et al., 2003) to compute $\epsilon$-optimal joint policy for $M^{\prime}$
(resp. $M$) under HIS starting at initial state distribution $s_{0}$ for
planning horizon $\ell$. We chose the PBVI algorithm because it leverages the
linear functions $\beta_{\tau}$ involved in the optimal value function.
Besides, it is guaranteed to find near-optimal solutions asymptotically.
Notice that algorithms that do not leverage the linear functions
$\beta_{\tau}$, e.g., feature-based heuristic search value iteration
(Dibangoye et al., 2013, 2016), cannot benefit from our findings.

PBVI, cf. Algorithm 1 in Appendix A, has two main parts for solving
$M^{\prime}$ (resp. $M$) under HIS. First, it bounds the size of the value
function at each stage $\tau$ of the game by representing the value only at a
finite, reachable occupancy subset $\tilde{S}_{\tau}$. Next, it optimizes the
value function represented as a collection $\mathcal{V}_{\tau}$ at each stage
$\tau$ using point-based backup, i.e., at any stage $\tau$,
$\mathcal{V}_{\tau}=\\{\mathtt{backup}(s_{\tau},\mathcal{V}_{\tau+1})\colon
s_{\tau}\in\tilde{S}_{\tau}\\}$, where backups are executed in no particular
order, i.e.,
$\mathtt{backup}(s_{\tau},\mathcal{V}_{\tau+1})=\operatorname*{\arg\\!\max}_{\alpha_{\tau}^{a_{\tau:}}\colon
a_{\tau}\in
A,\alpha_{\tau}^{a_{\tau+1:}}\in\mathcal{V}_{\tau}}~{}Q_{\beta_{\tau}^{a_{\tau+1:}}}(s_{\tau},a_{\tau})$.
Each iteration traverses occupancy-state subsets bottom up. This iterative
process repeats until convergence or until a budget, e.g., CPU time, memory,
or number of iterations, has been exhausted. The algorithm adds supplemental
points into occupancy subsets to improve the value functions further. It
selects candidate points using a portfolio of exploration strategies,
including random explorations and greedy w.r.t. underlying (PO)MDP value
functions. For every stage $\tau$, the algorithm adds only candidate points
beyond a certain distance from the occupancy subset $\tilde{S}_{\tau}$ to
create a new occupancy-state set $\tilde{S}_{\tau+1}$.

For any arbitrary occupancy-state subsets $\tilde{S}_{0:}$, PBVI produces a
value $\upsilon_{0}(s_{0})$. The error between $\upsilon_{0}(s_{0})$ and
$\upsilon^{*}_{0}(s_{0})$ is bounded. The bound depends on how
$\tilde{S}_{0:}$ samples the entire occupancy-state space; with denser
sampling, the estimate $\upsilon_{0}(s_{0})$ converges to
$\upsilon^{*}_{0}(s_{0})$. The remainder of this section states and proves our
error bound.

Define the density $\delta_{\tilde{S}_{0:}}$ to be the maximum distance from
any legal occupancy state to subsets $\tilde{S}_{0:}$. More precisely,
$\delta_{\tilde{S}_{0:}}\doteq\max_{\tau\in\llbracket
0:\ell-1\rrbracket}\max_{s\in
S_{\tau}}\min_{s^{\prime}\in\tilde{S}_{\tau}}\|s-s^{\prime}\|_{1}$. Define a
positive scalar $c$ such that $\|r(\cdot,\cdot)\|_{\infty}\leq c$.

######  Theorem 3.1 (Proof in Appendix D).

For any occupancy subsets $\tilde{S}_{0:}$, the error of the PBVI algorithm is
bounded by

$\upsilon^{*}_{0}(s_{0})-\upsilon_{0}(s_{0})\leq
2c\delta_{\tilde{S}_{0:}}\frac{1+\ell\gamma^{\ell+1}-(\ell+1)\gamma^{\ell}}{(1-\gamma)^{2}}.$

It is worth noticing that whenever $\ell$ goes to infinity, our bound meets
that from Pineau et al. (2003) for infinite-horizon partially observable
Markov decision processes.

##  4 Experiments

This section presents the outcomes of our experiments, which were carried out
to juxtapose our findings with the leading-edge theory employed in global
methods, encompassing the utilization of the PBVI algorithm as a standard
algorithmic scheme. Our analysis involves three variants of the PBVI
algorithm, namely PBVIenum, PBVImilp, and hPBVI, each employing distinct
methods of performing point-based backups. PBVIenum relies on brute-force
enumeration of joint decision rules. At the same time, PBVImilp utilizes
mixed-integer linear programs (MILPs) for implicit enumeration following the
state-of-art approach for general Dec-POMDPs (Dibangoye et al., 2016). We used
ILOG CPLEX Optimization Studio to solve the MILPs. Finally, hPBVI incorporates
our findings to facilitate point-based backups under hierarchical information
sharing. Global methods are not designed to scale up with players. To present
a comprehensive view, we have also compared our results against local policy-
and value-based methods, i.e., asynchronous actor-critic (A2C) (Konda &
Tsitsiklis, 1999) and independent $Q$-learning (IQL) (Tan, 1998),
respectively. The experiments were executed on an Ubuntu machine with 32GB of
available RAM and a 2.5GHz processor, utilizing only one core, with a time
limit of 30 minutes.

We have comprehensively assessed various algorithms using several two-player
benchmarks sourced from academic literature, available at masplan.org. These
benchmarks encompass mabc, recycling, grid3x3, boxpushing, mars, and tiger. To
enable a comparison of multiple players, we have also introduced the multi-
player variants of these benchmarks. Please refer to Appendix E for a detailed
definition of these multi-player benchmarks.

Table 1: Snapshot of empirical results, cf. Appendix F. For each game($n$) and
algorithm, we report time (in seconds) per backup and the best value for
horizon $\ell=30$. oot means time limit of 30 minutes has been exceeded and
’–’ is not applicable.

| hPBVI | PBVImilp | PBVIenum | A2C | IQL
---|---|---|---|---|---
tiger(2) | 0.02 | 112.5 | 0.20 | 112.5 | 0.05 | 112.5 | – | 94.05 | – | 20.55
tiger(3) | 0.07 | 262.5 | 16.03 | 262.5 | 14.25 | 262.5 | – | 190.38 | – | 31.72
tiger(4) | 0.23 | 393.75 | oot | oot | – | 218.49 | – | -74.07
tiger(6) | 8.12 | 650.0 | oot | oot | – | 496.45 | – | -89.18
tiger(8) | 864.03 | 1012.5 | oot | oot | – | 738.22 | – | -16.95
recycling(2) | 0.02 | 93.73 | 0.61 | 93.73 | 0.04 | 93.73 | – | 93.37 | – | 93.22
recycling(3) | 0.042 | 229.5 | 15.93 | 229.5 | 135.84 | 223.5 | – | 139.12 | – | 128.66
recycling(4) | 0.13 | 306.0 | 1148.82 | 258.94 | oot | – | 166.68 | – | 154.18
recycling(6) | 7.18 | 459.0 | oot | oot | – | -50.71 | – | 204.25
recycling(8) | 94.58 | 381.89 | oot | oot | – | -110.11 | – | 251.73
mabc(2) | 0.05 | 27.42 | 0.15 | 27.40 | 0.04 | 27.42 | – | 27.18 | – | 27.2
mabc(3) | 0.03 | 23.24 | 1.21 | 23.24 | 0.65 | 23.24 | – | 23.27 | – | 23.24
mabc(4) | 0.07 | 24.94 | 223.26 | 24.94 | oot | – | 24.36 | – | 24.94
mabc(7) | 1.66 | 27.25 | oot | oot | – | 16.72 | – | 26.82
mabc(10) | 139.82 | 27.75 | oot | oot | – | 12.25 | – | 24.84
grid3x3(2) | 0.61 | 24.44 | 1329.33 | 24.33 | oot | – | 22.93 | – | 24.35
grid3x3(3) | 65.43 | 28.16 | oot | oot | – | 27.92 | – | 28.16
mars(2) | 0.28 | 84.33 | 248.61 | 76.15 | oot | – | 43.20 | – | 52.86
boxpushing(2) | 0.66 | 675.46 | 24.58 | 576.30 | oot | – | 180.11 | – | 614.6

Our study aimed to assess the reduction in complexity achieved by point-based
backups and its effect on solving larger multi-player games. Our findings show
that hPBVI performs point-based backups significantly faster than other
methods, which enables it to scale up to larger teams, as illustrated in Table
1. Specifically, hPBVI was able to perform point-based backups for up to 10
players in about 139.82 seconds in $\mathtt{mabc(10)}$ at $\ell=30$, while
PBVIenum ran out of time for 4 players, and PBVImilp for 5 players.
Additionally, hPBVI converges faster than PBVIenum and PBVImilp in 2- to
3-player domains. For example, hPBVI can converge in under 1 second in
$\mathtt{grid3x3(2)}$ at $\ell=30$, while PBVImilp takes about 1329.33
seconds, not to mention PBVIenum. Our results in Table 1 demonstrate that
hPBVI can scale up to larger teams of players where neither PBVImilp nor
PBVIenum can.

Local methods A2C and IQL do scale up to larger teams as expected.
Surprisingly, they perform very well on certain domains with weakly coupled
players, as shown in $\mathtt{mabc(4)}$ and $\mathtt{grid3x3(3)}$, cf. Table
1. However, hPBVI always performs better A2C and IQL on all benchmarks except
$\mathtt{mabc(4)}$ and $\mathtt{grid3x3(3)}$, which exhibit local behaviors
that are global optimal solutions. Moreover, it converges faster than A2C and
IQL on all tested benchmarks, Figures 11,12,13,14 report anytime performances
in Appendix F. Although this observation goes beyond our original goal, it
provides encouraging insights when comparing local against global methods over
teams of medium sizes. Nonetheless, we caution readers against drawing general
conclusions from this observation, as different local methods may yield
different local optima and convergence rates.

##  5 Discussion

This paper presents a point-based value iteration algorithm for near-optimally
solving Dec-POMDPs. It exploits a hierarchical information-sharing structure,
a dominant management style in our society for corporations, governments,
criminal enterprises, armies, and religions. Under this assumption, it shows
that point-based backup operations can be solved as perfect-information
extensive-form games without compromising optimality. Doing so results in an
exponential complexity drop, allowing global methods to scale up to larger
teams of players. A thorough empirical analysis reveals that algorithms
utilizing our findings can scale up to larger teams of players. In contrast,
the state-of-the-art global approaches quickly ran out of resources. Another
important empirical finding is that our approach scales to all medium-sized
tested domains while providing equal or better performances than a state-of-
the-art local method.

Traditionally, global methods have been considered ineffective in games that
involve medium to large-sized teams of players. For instance, state-of-the-art
Dec-POMDP solvers such as FB-HSVI were only designed for two players (Oliehoek
et al., 2010; Dibangoye et al., 2009, 2013, 2016). However, we have presented
a paper that puts forth several propositions for developing global methods
that possess the scalability of local methods while maintaining global
guarantees. In applications where the stakes are high and critical, such as
search and rescue, security, and healthcare, scalable global methods with more
reliable solutions than those from local methods are essential.

Similarly to Kovařík et al. (2022), our paper demonstrates that simultaneous-
move games can be solved sequentially and centrally while allowing each player
to act optimally in a decentralized manner. This sequential and centralized
training for decentralized execution (SCTDE) approach enables us to leverage
private information available to players in a simple manner. Additionally, the
SCTDE approach enables us to reason for each player individually in a way that
is similar to extensive-form games. This results in a significant reduction in
complexity, especially when faced with public observations. This insight also
allows us to transfer theories and algorithms from extensive-form games to
simultaneous-move games. While our study demonstrates how to optimally solve
single-stage games as extensive-form games, the principle we discussed also
applies to planning and learning to act in multi-stage general-sum games.

Our study focuses on analyzing the line hierarchical structure. Although
previous studies, such as Xie et al. (2020), have successfully applied the
SCTDE approach in two-player common-payoff games, our paper extends the
research to multiple players. Additionally, our research can be further
expanded to consider other structures, such as a tree structure, where players
at the same level are independent. In the past, several forms of structure
have been investigated such as dynamics independence (Becker et al., 2004),
weak-separability (Nair et al., 2005), and delayed information-sharing (Nayyar
et al., 2010). However, it is not clear how the hierarchical assumption
affects these structures and the corresponding planning and learning theories.

##  6 Impact Statements

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none
which we feel must be specifically highlighted here.

## References

  * Amato et al. (2012) Amato, C., Bernstein, D. S., and Zilberstein, S.  Optimizing memory-bounded controllers for decentralized pomdps.  _arXiv preprint arXiv:1206.5258_ , 2012.
  * Amato et al. (2013) Amato, C., Chowdhary, G., Geramifard, A., Üre, N. K., and Kochenderfer, M. J.  Decentralized control of partially observable markov decision processes.  In _CDC_ , 2013.
  * Becker et al. (2004) Becker, R., Zilberstein, S., Lesser, V. R., and Goldman, C. V.  Solving Transition Independent Decentralized Markov Decision Processes.  _JAIR_ , 22:423–455, 2004.
  * Bellman (1957) Bellman, R. E.  _Dynamic Programming_.  Dover Publications, Incorporated, 1957.
  * Bernstein et al. (2002) Bernstein, D. S., Givan, R., Immerman, N., and Zilberstein, S.  The Complexity of Decentralized Control of Markov Decision Processes.  _Mathematics of Operations Research_ , 27, 2002.
  * Bono et al. (2018) Bono, G., Dibangoye, J. S., Matignon, L., Pereyron, F., and Simonin, O.  Cooperative Multi-agent Policy Gradient.  In _ECML-PKDD_ , pp. 459–476, 2018.
  * Dibangoye et al. (2009) Dibangoye, J. S., Mouaddib, A., and Chaib-draa, B.  Point-based incremental pruning heuristic for solving finite-horizon Dec-POMDPs.  In _AAMAS_ , pp. 569–576, 2009.
  * Dibangoye et al. (2012) Dibangoye, J. S., Amato, C., and Doniec, A.  Scaling up decentralized mdps through heuristic search.  In de Freitas, N. and Murphy, K. P. (eds.), _UAI_ , pp. 217–226, 2012.
  * Dibangoye et al. (2013) Dibangoye, J. S., Amato, C., Buffet, O., and Charpillet, F.  Optimally solving Dec-POMDPs as continuous-state MDPs.  In _IJCAI_ , pp. 90–96, 2013.
  * Dibangoye et al. (2014) Dibangoye, J. S., Amato, C., Buffet, O., and Charpillet, F.  Exploiting Separability in Multi-Agent Planning with Continuous-State MDPs.  In _AAMAS_ , 2014.
  * Dibangoye et al. (2016) Dibangoye, J. S., Amato, C., Buffet, O., and Charpillet, François, D.  Optimally solving Dec-POMDPs as continuous-state MDPs.  _JAIR_ , 2016.
  * Foerster et al. (2018) Foerster, J. N., Farquhar, G., Afouras, T., Nardelli, N., and Whiteson, S.  Counterfactual multi-agent policy gradients.  In _AAAI_ , 2018.
  * Hadfield-Menell et al. (2016) Hadfield-Menell, D., Russell, S. J., Abbeel, P., and Dragan, A.  Cooperative inverse reinforcement learning.  In _NIPS_ , 2016.
  * Hansen et al. (2004) Hansen, E. A., Bernstein, D. S., and Zilberstein, S.  Dynamic Programming for Partially Observable Stochastic Games.  In _AAAI_ , 2004.
  * Horák & Bošanskỳ (2019) Horák, K. and Bošanskỳ, B.  Solving partially observable stochastic games with public observations.  In _AAAI_ , 2019.
  * Horák et al. (2017) Horák, K., Bošanskỳ, B., and Pěchouček, M.  Heuristic search value iteration for one-sided partially observable stochastic games.  In _AAAI_ , 2017.
  * Kaelbling et al. (1998) Kaelbling, L. P., Littman, M. L., and Cassandra, A. R.  Planning and acting in partially observable stochastic domains.  _Artificial intelligence_ , pp. 99–134, 1998.
  * Konda & Tsitsiklis (1999) Konda, V. R. and Tsitsiklis, J. N.  Actor-critic algorithms.  In _Neural Information Processing Systems_ , 1999.
  * Kovařík et al. (2022) Kovařík, V., Schmid, M., Burch, N., Bowling, M., and Lisỳ, V.  Rethinking formal models of partially observable multiagent decision making.  _Artificial Intelligence_ , 303:103645, 2022.
  * Lowe et al. (2017) Lowe, R., WU, Y., Tamar, A., Harb, J., Pieter Abbeel, O., and Mordatch, I.  Multi-agent actor-critic for mixed cooperative-competitive environments.  In _NIPS_ , volume 30, pp. 6379–6390, 2017.
  * MacDermed & Isbell (2013) MacDermed, L. C. and Isbell, C. L.  Point based value iteration with optimal belief compression for dec-pomdps.  In _NIPS_ , 2013.
  * Malik et al. (2018) Malik, D., Palaniappan, M., Fisac, J., Hadfield-Menell, D., Russell, S., and Dragan, A.  An efficient, generalized Bellman update for cooperative inverse reinforcement learning.  In _ICML_ , 2018.
  * Nair et al. (2003) Nair, R., Tambe, M., Yokoo, M., Pynadath, D. V., and Marsella, S.  Taming decentralized pomdps: Towards efficient policy computation for multiagent settings.  In _International Joint conference on Artificial Intelligence (IJCAI)_ , 2003.
  * Nair et al. (2005) Nair, R., Varakantham, P., Tambe, M., and Yokoo, M.  Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs.  In _AAAI_ , 2005.
  * Nayyar et al. (2010) Nayyar, A., Mahajan, A., and Teneketzis, D.  Optimal control strategies in delayed sharing information structures.  _IEEE Transactions on Automatic Control_ , 2010.
  * Nayyar et al. (2013) Nayyar, A., Mahajan, A., and Teneketzis, D.  Decentralized stochastic control with partial history sharing: A common information approach.  _IEEE Transactions on Automatic Control_ , 58(7):1644–1658, 2013.
  * Oliehoek (2013) Oliehoek, F. A.  Sufficient plan-time statistics for decentralized pomdps.  In _Twenty-Third International Joint Conference on Artificial Intelligence_ , 2013.
  * Oliehoek et al. (2010) Oliehoek, F. A., Spaan, M. T. J., Dibangoye, J. S., and Amato, C.  Heuristic search for identical payoff bayesian games.  In _AAMAS_ , pp. 1115–1122, 2010.
  * Ooi & Wornell (1996) Ooi, J. and Wornell, G.  Decentralized control of a multiple access broadcast channel: performance bounds.  In _CDC_ , volume 1, pp. 293–298 vol.1, 1996.  doi: 10.1109/CDC.1996.574318.
  * Peshkin et al. (2001) Peshkin, L., Kim, K.-E., Meuleau, N., and Kaelbling, L. P.  Learning to cooperate via policy search.  _arXiv preprint cs/0105032_ , 2001.
  * Pineau et al. (2003) Pineau, J., Gordon, G., Thrun, S., et al.  Point-based value iteration: An anytime algorithm for pomdps.  In _IJCAI_ , volume 3, pp. 1025–1032, 2003.
  * Rabinovich et al. (2003) Rabinovich, Z., Goldman, C. V., and Rosenschein, J. S.  The complexity of multiagent systems: The price of silence.  In _AAMAS_ , 2003.
  * Rashid et al. (2018) Rashid, T., Samvelyan, M., de Witt, C. S., Farquhar, G., Foerster, J. N., and Whiteson, S.  QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning.  In _ICML_ , 2018.
  * Shoham & Leyton-Brown (2008) Shoham, Y. and Leyton-Brown, K.  _Multiagent systems: Algorithmic, game-theoretic, and logical foundations_.  Cambridge University Press, 2008.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Szer & Charpillet (2005) Szer, D. and Charpillet, F.  An optimal best-first search algorithm for solving infinite horizon dec-pomdps.  In _ECML_ , 2005.
  * Tan (1998) Tan, M.  Multi-agent Reinforcement Learning: Independent vs. Cooperative Agents.  In Huhns, M. N. and Singh, M. P. (eds.), _Readings in Agents_ , pp. 487–494. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1998\.
  * Tsitsiklis (1984) Tsitsiklis, J. N.  _Problems in decentralized decision making and computation_.  PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1984.
  * Xie et al. (2020) Xie, Y., Dibangoye, J., and Buffet, O.  Optimally solving two-agent decentralized POMDPs under one-sided information sharing.  In _ICML_ , pp. 10473–10482, 2020.

##  Appendix A The PBVI Algorithm

This section presents a pseudocode for the point-based value iteration
algorithm to solve decentralized, partially observable Markov decision
processes with hierarchical information sharing near-optimally.

${\mathtt{function}~{}\mathtt{PBVI}()}$

Initialize $\tilde{S}_{0:}$ and $\mathcal{V}_{0:}$.

while $\mathcal{V}_{0:}$ has not converged do

$\mathtt{improve}(\mathcal{V}_{0:},\tilde{S}_{0:})$.

$\tilde{S}_{0:}\leftarrow\mathtt{expand}(\tilde{S}_{0:})$.

end while

${\mathtt{function}~{}\mathtt{improve}(\mathcal{V}_{0:},\tilde{S}_{0:})}$

for $\tau=\ell-1$ to $0$ do

for $s_{\tau}\in\tilde{S}_{\tau}$ do

$\mathcal{V}_{\tau}\leftarrow\mathcal{V}_{\tau}\cup\\{\mathtt{backup}(s_{\tau},\mathcal{V}_{\tau+1})\\}$.

end for

end for

Algorithm 1 PBVI for $M^{\prime}$ under HIS.

##  Appendix B Proof of Theorem 2.3

This section shows that the nested-occupancy state is a sufficient statistic
for the central planner to optimally solve perfect-information extensive-form
game $\bar{G}_{s_{\tau}}^{\beta_{\tau}}$ for any player $i$.

###### Proof.

The nested-occupancy state is a sufficiency statistic of the total data
available to the planner at any player $i$ for optimally solving
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$, if it is sufficient to predict (1) the
next nested-occupancy state and (2) the immediate reward. Let the total data
available to the planner at player $i$ be
$\varsigma_{\tau}^{i}\doteq(s_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau})$. Let
$u^{i}_{\tau}$ be the action chosen at player $i$ after experiencing total
data $\varsigma_{\tau}^{i}$. The nested-occupancy state
$s^{i}_{\tau}\doteq(b^{i}_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau})$ summarizing
$\varsigma_{\tau}^{i}$ is sufficient to predict the next nested-occupancy
state $s^{i+1}_{\tau}$, if and only if the following holds
$\Pr\\{s^{i+1}_{\tau}
|\varsigma^{i}_{\tau},u^{i}_{\tau}\\}=\Pr\\{s^{i+1}_{\tau}
|s^{i}_{\tau},u^{i}_{\tau}\\}$. To prove this property, we start with the
definition of a nested-belief state $b^{i}_{\tau}$ associated with nested-
occupancy state $s^{i}_{\tau}$, i.e.,

$\displaystyle\Pr\\{s^{i+1}_{\tau} |\varsigma^{i}_{\tau},u_{\tau}^{i}\\}$
$\displaystyle\doteq\Pr\\{b^{i+1}_{\tau},o^{i+1}_{\tau},u^{:i,\bullet}_{\tau}
|s_{\tau},o^{i}_{\tau},u^{:i,\circ}_{\tau}\\},$ (by definition of
$\varsigma_{\tau}^{i}$ and $s^{i}_{\tau}$)
$\displaystyle=\Pr\\{b^{i+1}_{\tau},o^{i+1}_{\tau}
|s_{\tau},o^{i}_{\tau},u^{:i,\circ}_{\tau}\\}\cdot\Pr\\{u^{:i,\bullet}_{\tau}|s_{\tau},o^{i}_{\tau},u^{:i,\circ}_{\tau}\\},$
(by application of the Bayes rule)
$\displaystyle=\Pr\\{b^{i+1}_{\tau},o^{i+1}_{\tau}
|\varsigma_{\tau}^{i}\\}\cdot\Pr\\{u^{:i,\bullet}_{\tau}|u^{:i,\circ}_{\tau}\\},$
(by checking constraint $u^{:i,\bullet}_{\tau}=u^{:i,\circ}_{\tau}$)
$\displaystyle=b^{i}_{\tau}(b^{i+1}_{\tau},o^{i+1}_{\tau})\cdot\mathbb{1}\\{u^{:i,\circ}_{\tau}=u^{:i,\bullet}_{\tau}\\},$
$\displaystyle\text{(by definition of $b^{i}_{\tau}$)}.$

It will prove useful to define transition rule
$\tilde{T}\colon(s^{i+1}_{\tau}|b^{i}_{\tau},u_{\tau}^{:i})\mapsto\Pr\\{s^{i+1}_{\tau}|
b^{i}_{\tau},u_{\tau}^{:i}\\}$, describing the probability to transitionning
into nested-occupancy state $s^{i+1}_{\tau}$ upon talking action
$u^{i}_{\tau}$ in nested-occupancy state $s^{i}_{\tau}$. Notice that the
transition does not depend on the current history $o^{i}_{\tau}$, or it does
so only through $(b^{i}_{\tau},u_{\tau}^{:i})$. Next, we show the sufficiency
of nested-occupancy states to predict immediate rewards. Since rewards occur
only at player $n$, we shall only consider nested occupancy states at that
player. The nested-occupancy state
$s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},u^{:n-1}_{\tau})$ summarizing
$\varsigma_{\tau}^{n}$ is sufficient to predict the immediate reward upon
taking action $u^{n}_{\tau}$, if and only if there exists a reward function
$(s_{\tau}^{n},u^{n}_{\tau})\mapsto\tilde{R}(s_{\tau}^{n},u^{n}_{\tau})$ such
that the following holds:
$R(\varsigma_{\tau}^{n},u^{n}_{\tau})=\tilde{R}(s_{\tau}^{n},u^{n}_{\tau})$.
To prove this statement, we start with the definition of
$R(\varsigma_{\tau}^{n},u^{n}_{\tau})$, i.e.,

$\displaystyle R(\varsigma_{\tau}^{n},u^{n}_{\tau})$
$\displaystyle\doteq\mathbb{E}_{x\sim\Pr\\{\cdot|\varsigma_{\tau}^{n},u_{\tau}^{n}\\}}\\{\beta_{\tau}(x,o,u)\\},$
(by definition of $R(\varsigma_{\tau}^{n},u^{n}_{\tau})$)
$\displaystyle=\mathbb{E}_{x\sim
b^{n}_{\tau}(\cdot)}\\{\beta_{\tau}(x,o,u)\\},$ $\displaystyle\text{(by
definition of $b^{n}_{\tau}$)}.$

If we let $\tilde{R}(s_{\tau}^{n},u^{n}_{\tau})\doteq\mathbb{E}_{x\sim
b^{n}_{\tau}(\cdot)}\\{\beta_{\tau}(x,o,u)\\}$, then the statement holds.

Nested-occupancy states describe a perfect-information extensive-form game
$\tilde{G}_{s_{\tau}}^{\beta_{\tau}}\doteq\langle
n,\tilde{\Sigma},\tilde{\Psi},\tilde{T},\tilde{R}\rangle$ where nodes
$\tilde{\Sigma}$ are nested-occupancy states,
$\tilde{\Psi}\colon\tilde{\Sigma}\to 2^{(\cup_{i=1}^{n}U^{i})}$ specifies the
action set available to each nested-occupancy state, and $\tilde{T}$ and
$\tilde{R}$ are already defined. Clearly, any optimal solution for perfect-
information extensive-form game $\tilde{G}_{s_{\tau}}^{\beta_{\tau}}$ is also
optimal for perfect-information extensive-form game
$\bar{G}_{s_{\tau}}^{\beta_{\tau}}$. To prove this statement, we need to prove
that the optimal action-value functions $\tilde{\beta}_{\tau}^{1:n,*}$ of
$\tilde{G}_{s_{\tau}}^{\beta_{\tau}}$ such that at any player $i$ and node
$\varsigma_{\tau}^{i}$ (resp. nested-occupancy state $s^{i}_{\tau}$) and
action $u^{i}_{\tau}$ the following equality holds:
$\beta_{\tau}^{i,*}(\varsigma_{\tau}^{i},u_{\tau}^{i})=\tilde{\beta}_{\tau}^{i,*}(s_{\tau}^{i},u_{\tau}^{i})$.
We prove the statement by induction. The statement trivially holds at player
$n$ since
$R(\varsigma_{\tau}^{n},u^{n}_{\tau})=\tilde{R}(s_{\tau}^{n},u^{n}_{\tau})$,
then $\beta_{\tau}^{n,*}(\varsigma_{\tau}^{i},u_{\tau}^{i})\doteq
R(\varsigma_{\tau}^{n},u^{n}_{\tau})=\tilde{R}(s_{\tau}^{n},u^{n}_{\tau})\doteq\tilde{\beta}_{\tau}^{i,*}(s_{\tau}^{i},u_{\tau}^{i})$.
Suppose the statement hold at player $i+1$ onward, i.e.,
$\beta_{\tau}^{i+1,*}(\varsigma_{\tau}^{i+1},u_{\tau}^{i+1})=\tilde{\beta}_{\tau}^{{i+1},*}(s_{\tau}^{i+1},u_{\tau}^{i+1})$.
We are now ready to show it also hold at player $i$. We start with the
expression of the optimal action-value function $\beta_{\tau}^{i,*}$, i.e.,

$\displaystyle\beta^{i,*}_{\tau}(\varsigma_{\tau}^{i},u^{i}_{\tau})$
$\displaystyle=\textstyle\mathbb{E}_{\varsigma_{\tau}^{i+1}\sim
T(\cdot|\varsigma_{\tau}^{i},u^{i}_{\tau})}\\{\max_{u^{i+1}_{\tau}}\beta_{\tau}^{i+1,*}(\varsigma_{\tau}^{i+1},u_{\tau}^{i+1})\\},$
(by Theorem 2.2)
$\displaystyle=\textstyle\mathbb{E}_{s_{\tau}^{i+1}\sim\Pr\\{\cdot|\varsigma_{\tau}^{i},u^{i}_{\tau}\\}}\\{\max_{u^{i+1}_{\tau}}\tilde{\beta}_{\tau}^{i+1,*}(s_{\tau}^{i+1},u_{\tau}^{i+1})\\},$
(by induction hypothesis)
$\displaystyle=\textstyle\mathbb{E}_{s_{\tau}^{i+1}\sim\tilde{T}(\cdot|b_{\tau}^{i},u^{:i}_{\tau})}\\{\max_{u^{i+1}_{\tau}}\tilde{\beta}_{\tau}^{i+1,*}(s_{\tau}^{i+1},u_{\tau}^{i+1})\\},$
(by definition of $\tilde{T}(\cdot|b_{\tau}^{i},u^{:i}_{\tau})$)
$\displaystyle=\tilde{\beta}^{i,*}_{\tau}(s_{\tau}^{i},u^{i}_{\tau}),$
$\displaystyle\text{(by definition of $\tilde{\beta}^{i,*}_{\tau}$)}.$

The statement holds for player $i$, thus for any arbitrary player.
Consequently, one can use nested-occupancy states instead of total data
available to the planner without compromising optimality, which ends the
proof. ∎

##  Appendix C Equivalence Relations

This section presents crucial properties necessary for grouping private
histories that convey the same information about the game. To cluster two
private histories of a player and reason similarly for the entire cluster, it
is imperative to ensure that making identical immediate and future decisions
for all members in the cluster does not compromise optimality. To do so, we
need to specify how the information we rely on to make decisions evolves over
stages. In particular, we need to exhibit rules for calculating the next-stage
nested-occupancy state given the current one and decisions made at the current
stage.

###  C.1 Predicting Next-Stage Observations

This subsection shows that the observation at stage $\tau+1$ and player $i$
can be accurately predicted using only the nested occupancy states at stage
$\tau$ and player $i$ along with decision rules at stage $\tau$ and players
$i$ to $n$.

######  Lemma C.1.

Let $\varsigma_{\tau}^{i}\doteq\langle
s_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau}\rangle$ be total data available to the
planner at stage $\tau$ and player $i$. Let $a^{i:}_{\tau}$ be the decision
rules for player $i$ to player $n$ at stage $\tau$. Let
$s_{\tau}^{i}\doteq\langle b^{i}_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau}\rangle$
be the nested-occupancy state at stage $\tau$ and player $i$ summarizing total
data $\varsigma_{\tau}^{i}$. The probability
$\Pr\\{z^{i}_{\tau+1}|\varsigma^{i}_{\tau},a^{i:}_{\tau}\\}$ that the planner
receives observation $z^{i}_{\tau+1}$ on behalf of player $i$ upon acting
according to $\langle u^{i}_{\tau},a^{i+1:}_{\tau}\rangle$ starting in total
data $\varsigma_{\tau}^{i}$ satisfies the following recursion:

$\displaystyle\Omega^{i}(z^{i}_{\tau+1}|b^{i}_{\tau},u^{:i}_{\tau},a^{i+1:}_{\tau})$
$\displaystyle=\sum_{s^{i+1}_{\tau}}\tilde{T}(s^{i+1}_{\tau}|b^{i}_{\tau},u^{:i}_{\tau})\sum_{z^{i+1}_{\tau+1}}\mathbb{1}\\{z^{i}_{\tau+1}\sqsubseteq\zeta^{i+1}(z^{i+1}_{\tau+1})\\}\cdot\Omega^{i+1}(z^{i+1}_{\tau+1}|b^{i+1}_{\tau},u_{\tau}^{:i},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}),$
(1)

with boundary condition
$\Omega^{n}(z^{n}_{\tau+1}|b^{n}_{\tau},u_{\tau}^{:n})\doteq\sum_{x}\sum_{y}b^{n}_{\tau}(x)\cdot
p(y,z^{n}_{\tau+1}|x,u_{\tau}^{:n})$.

###### Proof.

Starting from conditional probability distribution
$\Pr\\{z^{i}_{\tau+1}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}$
and expanding over nested-occupancy states $s^{i+1}_{\tau}$ and observations
$z^{i+1}_{\tau+1}$ of player $i+1$

$\displaystyle\Pr\\{z^{i}_{\tau+1}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}$
$\displaystyle=\sum_{s^{i+1}_{\tau}}\sum_{z^{i+1}_{\tau+1}}\Pr\\{s^{i+1}_{\tau},z^{i+1}_{\tau+1},z^{i}_{\tau+1}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}.$

The expansion of the joint probability into the product of conditional
probabilities yields the following expression:

$\displaystyle=\sum_{s^{i+1}_{\tau}}\sum_{z^{i+1}_{\tau+1}}\Pr\\{z^{i}_{\tau+1}|s^{i+1}_{\tau},z^{i+1}_{\tau+1},\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}\cdot\Pr\\{z^{i+1}_{\tau+1}|s^{i+1}_{\tau},\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}\cdot\Pr\\{s^{i+1}_{\tau}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}.$
(2)

The first factor in (2) depends solely upon $z^{i+1}_{\tau+1}$ and not on the
tuple $(s^{i+1}_{\tau},\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau})$,
i.e.,

$\displaystyle\Pr\\{z^{i}_{\tau+1}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}$
$\displaystyle=\sum_{s^{i+1}_{\tau}}\sum_{z^{i+1}_{\tau+1}}\Pr\\{z^{i}_{\tau+1}|z^{i+1}_{\tau+1}\\}\cdot\Pr\\{z^{i+1}_{\tau+1}|s^{i+1}_{\tau},\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}\cdot\Pr\\{s^{i+1}_{\tau}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}.$
(3)

The last factor in (3) depends solely upon $\langle
b^{i}_{\tau},u^{:i}_{\tau}\rangle$ and not on tuple
$\langle\varsigma^{i}_{\tau},a^{i+1:}_{\tau}\rangle$, which becomes after re-
arranging terms:

$\displaystyle\Pr\\{z^{i}_{\tau+1}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}$
$\displaystyle=\sum_{s^{i+1}_{\tau}}\tilde{T}(s^{i+1}_{\tau}|b^{i}_{\tau},u^{:i}_{\tau})\sum_{z^{i+1}_{\tau+1}}\Pr\\{z^{i}_{\tau+1}|z^{i+1}_{\tau+1}\\}\cdot\Pr\\{z^{i+1}_{\tau+1}|s^{i+1}_{\tau},\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}.$
(4)

Equation (4) makes it possible to prove the statement, Equation (1),
recursively. We start at player $n-1$, i.e.,

$\displaystyle\Pr\\{z^{n-1}_{\tau+1}|\varsigma^{n-1}_{\tau},u^{n-1}_{\tau},a^{n}_{\tau}\\}$
$\displaystyle=\sum_{s^{n}_{\tau}}\tilde{T}(s^{n}_{\tau}|b^{n-1}_{\tau},u^{:n-1}_{\tau})\sum_{z^{n}_{\tau+1}}\Pr\\{z^{n-1}_{\tau+1}|z^{n}_{\tau+1}\\}\cdot\Pr\\{z^{n}_{\tau+1}|s^{n}_{\tau},\varsigma^{n-1}_{\tau},u^{n-1}_{\tau},a^{n}_{\tau}\\}.$
(5)

The boundary condition gives the last factor in (5), i.e., for nested-
occupancy state
$s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},u^{:n-1}_{\tau})$,

$\displaystyle\Pr\\{z^{n-1}_{\tau+1}|\varsigma^{n-1}_{\tau},u^{n-1}_{\tau},a^{n}_{\tau}\\}$
$\displaystyle=\sum_{s^{n}_{\tau}}\tilde{T}(s^{n}_{\tau}|b^{n-1}_{\tau},u^{:n-1}_{\tau})\sum_{z^{n}_{\tau+1}}\mathbb{1}\\{z^{n-1}_{\tau+1}\sqsubseteq
z^{n}_{\tau+1}\\}\cdot\Omega^{n}(z^{n}_{\tau+1}|b^{n}_{\tau},\langle
u_{\tau}^{:n-1},a^{n}_{\tau}(o^{n}_{\tau})\rangle).$ (6)

Let
$\Omega^{n-1}\colon(z^{n-1}_{\tau+1}|b^{n-1}_{\tau},u^{:n-1}_{\tau},a^{n}_{\tau})\mapsto\
\sum_{s^{n}_{\tau}}\tilde{T}(s^{n}_{\tau}|b^{n-1}_{\tau},u^{:n-1}_{\tau})\sum_{z^{n}_{\tau+1}}\mathbb{1}\\{z^{n-1}_{\tau+1}\sqsubseteq\zeta^{n}(z^{n}_{\tau+1})\\}\cdot\Omega^{n}(z^{n}_{\tau+1}|b^{n}_{\tau},u_{\tau}^{:n-1},a^{n}_{\tau}(o^{n}_{\tau}))$
be the observation model for predicting next observation at stage $\tau$ and
player $n-1$. Then, statement (1) holds at stage $\tau$ and player $n-1$.
Suppose the statement holds for any arbitrary stage $\tau$ and player $i+1$.
We are ready to prove it also holds at stage $\tau$ and player $i$. Starting
at (4), the application of the induction hypothesis yields:

$\displaystyle\Pr\\{z^{i}_{\tau+1}|\varsigma^{i}_{\tau},u^{i}_{\tau},a^{i+1:}_{\tau}\\}$
$\displaystyle=\sum_{s^{i+1}_{\tau}}\tilde{T}(s^{i+1}_{\tau}|b^{i}_{\tau},u^{:i}_{\tau})\sum_{z^{i+1}_{\tau+1}}\mathbb{1}\\{z^{i}_{\tau+1}\sqsubseteq\zeta^{i+1}(z^{i+1}_{\tau+1})\\}\cdot\Omega^{i+1}(z^{i+1}_{\tau+1}|b^{i+1}_{\tau},u^{:i}_{\tau},a^{i+1:}_{\tau}).$
(7)

If we let
$\Omega^{i}\colon(z^{i}_{\tau+1}|b^{i}_{\tau},u^{:i}_{\tau},a^{i+1:}_{\tau})\mapsto\sum_{s^{i+1}_{\tau}}\tilde{T}(s^{i+1}_{\tau}|b^{i}_{\tau},u^{:i}_{\tau})\sum_{z^{i+1}_{\tau+1}}\mathbb{1}\\{z^{i}_{\tau+1}\sqsubseteq\zeta^{i+1}(z^{i+1}_{\tau+1})\\}\cdot\Omega^{i+1}(z^{i+1}_{\tau+1}|b^{i+1}_{\tau},u^{:i}_{\tau},a^{i+1:}_{\tau})$
be the observation model for predicting next observation at stage $\tau$ and
player $i$, then statement (1) holds at stage $\tau$ and player $i$. Thus, the
statement holds for any stage and player, which ends the proof. ∎

###  C.2 Predicting Next-Stage Nested-Occupancy States

This subsection proves the nested-occupancy states describe a Markovian
process, i.e., the next-stage nested-occupancy state depends only upon the
current one. Notice that nested-occupancy states have three components. Only
the nested belief states are nonobservable and need to be estimated. If we
know how to estimate the nested belief state, we can add the history and
actions of subordinates, thereby constructing a nested-occupancy state.

######  Lemma C.2.

Let $\varsigma_{\tau}^{i}\doteq\langle
s_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau}\rangle$ be total data available to the
planner at stage $\tau$ and player $i$. Let $a^{i:}_{\tau}$ be the decision
rules for player $i$ to player $n$ at stage $\tau$. Let
$s_{\tau}^{i}\doteq\langle b^{i}_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau}\rangle$
be the nested-occupancy state at stage $\tau$ and player $i$ summarizing total
data $\varsigma_{\tau}^{i}$. The next-stage nested-belief state
$b^{i}_{\tau+1}\doteq T^{i}(b^{i}_{\tau},\langle
u^{i}_{\tau},a^{i+1:}_{\tau}\rangle,z^{i}_{\tau+1})$, upon acting according to
$\langle u^{i}_{\tau},a^{i+1:}_{\tau}\rangle$ in nested-occupancy state
$s_{\tau}^{i}$ and receiving observation $z^{i}_{\tau+1}$, satisfies the
following recursion: for any history and nested-belief tuple
$(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$,

$\displaystyle b^{i}_{\tau+1}(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$
$\displaystyle\propto\textstyle\sum_{s^{i+1}_{\tau}\doteq(b^{i+1}_{\tau},o^{i+1}_{\tau},u_{\tau}^{:i})}\tilde{T}(s^{i+1}_{\tau}
|b_{\tau}^{i},u^{:i}_{\tau})\sum_{z^{i+1}_{\tau+1}}\mathbb{1}\\{z^{i}_{\tau+1}\sqsubseteq\zeta^{i+1}(z^{i+1}_{\tau+1})\\}\cdot\delta_{\langle
o^{i+1}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),z^{i+1}_{\tau+1}\rangle}^{o^{i+1}_{\tau+1}}$
$\displaystyle\quad\delta_{T^{i+1}(b^{i+1}_{\tau},\langle
u^{:i}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}\rangle,z^{i+1}_{\tau+1})}^{b^{i+1}_{\tau+1}}\cdot\Omega^{i+1}(z^{i+1}_{\tau+1}|b^{i+1}_{\tau},\langle
u^{:i}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}\rangle).$

with boundary condition $b^{n}_{\tau+1}\doteq
T^{n}(b^{n}_{\tau},u^{:n}_{\tau},z^{n}_{\tau+1})$ where
$b^{n}_{\tau+1}(y)\propto\sum_{x}b^{n}_{\tau}(x)\cdot
p(y,z^{n}_{\tau+1}|x,u^{:n}_{\tau})$ for any hidden state $y$.

###### Proof.

The proof proceeds by induction. Starting with player $n-1$, we define the
nested-belief state $b^{n-1}_{\tau+1}$ at stage $\tau+1$ and player $n-1$ upon
acting according to $\langle u^{n-1}_{\tau},a^{n}_{\tau}\rangle$ in total data
available to the planner $\varsigma_{\tau}^{n-1}\doteq\langle
s_{\tau},o^{n-1}_{\tau},u^{:n-2}_{\tau}\rangle$ and receiving observation
$z^{n-1}_{\tau+1}$, as follows: for any history and nested-belief tuple
$(o^{n}_{\tau+1},b^{n}_{\tau+1})$,

$\displaystyle b^{n-1}_{\tau+1}(o^{n}_{\tau+1},b^{n}_{\tau+1})$
$\displaystyle\doteq\Pr\\{o^{n}_{\tau+1},b^{n}_{\tau+1}|\varsigma_{\tau}^{n-1},u^{n-1}_{\tau},a^{n}_{\tau},z^{n-1}_{\tau+1}\\}.$
(8)

The expansion of (8) over nested-occupancy states $s^{n}_{\tau}$ at stage
$\tau$ and player $n$ and histories $z^{n}_{\tau+1}$ at stage $\tau+1$ and
player $n$, result in the following expression:

$\displaystyle b^{n-1}_{\tau+1}(o^{n}_{\tau+1},b^{n}_{\tau+1})$
$\displaystyle=\sum_{s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},u_{\tau}^{:n-1})}\sum_{z^{n}_{\tau+1}}\Pr\\{s^{n}_{\tau},z^{n}_{\tau+1},o^{n}_{\tau+1},b^{n}_{\tau+1}|\varsigma_{\tau}^{n-1},u^{n-1}_{\tau},a^{n}_{\tau},z^{n-1}_{\tau+1}\\}.$
(9)

The application of Bayes’ rule in expression (9) yields the following
expression:

$\displaystyle b^{n-1}_{\tau+1}(o^{n}_{\tau+1},b^{n}_{\tau+1})$
$\displaystyle=\sum_{s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},u_{\tau}^{:n-1})}\sum_{z^{n}_{\tau+1}}\frac{\Pr\\{s^{n}_{\tau},z^{n}_{\tau+1},o^{n}_{\tau+1},b^{n}_{\tau+1},\varsigma_{\tau}^{n-1},u^{n-1}_{\tau},a^{n}_{\tau},z^{n-1}_{\tau+1}\\}}{\Pr\\{\varsigma_{\tau}^{n-1},u^{n-1}_{\tau},a^{n}_{\tau},z^{n-1}_{\tau+1}\\}}.$
(10)

The expansion of the joint probability into the product of conditional
probabilities and the application of Lemma C.1 yield the following expression:

$\displaystyle b^{n-1}_{\tau+1}(o^{n}_{\tau+1},b^{n}_{\tau+1})$
$\displaystyle=\textstyle\sum_{s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},u_{\tau}^{:n-1})}\sum_{z^{n}_{\tau+1}}\Pr\\{z^{n-1}_{\tau+1}|z^{n}_{\tau+1}\\}\cdot\Pr\\{o^{n}_{\tau+1}|o^{n}_{\tau},a^{n}_{\tau}(o^{n}_{\tau}),z^{n}_{\tau+1}\\}\cdot\Pr\\{b^{n}_{\tau+1}|b^{n}_{\tau},\langle
u^{:n-1}_{\tau},a^{n}_{\tau}(o^{n}_{\tau})\rangle,z^{n}_{\tau+1}\\}\cdot$
$\displaystyle\quad\Pr\\{z^{n}_{\tau+1}|b^{n}_{\tau},\langle
u^{:n-1}_{\tau},a^{n}_{\tau}(o^{n}_{\tau})\rangle\\}\cdot\Pr\\{s^{n}_{\tau}
|\varsigma_{\tau}^{n-1},u^{n-1}_{\tau}\\}/\Pr\\{z^{n-1}_{\tau+1}|\varsigma_{\tau}^{n-1},u^{n-1}_{\tau},a^{n}_{\tau}\\}$
(11)

Using the boundary condition, we obtain the following expression, i.e.,

$\displaystyle b^{n-1}_{\tau+1}(o^{n}_{\tau+1},b^{n}_{\tau+1})$
$\displaystyle\propto\textstyle\sum_{s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},u_{\tau}^{:n-1})}\sum_{z^{n}_{\tau+1}}\mathbb{1}\\{z^{n-1}_{\tau+1}\sqsubseteq\zeta^{n}(z^{n}_{\tau+1})\\}\cdot\delta_{\langle
o^{n}_{\tau},a^{n}_{\tau}(o^{n}_{\tau}),z^{n}_{\tau+1}\rangle}^{o^{n}_{\tau+1}}$
$\displaystyle\quad\delta_{T^{n}(b^{n}_{\tau},\langle
u^{:n-1}_{\tau},a^{n}_{\tau}(o^{n}_{\tau})\rangle,z^{n}_{\tau+1})}^{b^{n}_{\tau+1}}\cdot\Omega^{n}(z^{n}_{\tau+1}|b^{n}_{\tau},\langle
u^{:n-1}_{\tau},a^{n}_{\tau}(o^{n}_{\tau})\rangle)\cdot\tilde{T}(s^{n}_{\tau}
|b_{\tau}^{n-1},u^{:n-1}_{\tau})$ (12)

Hence, the statement holds at stage $\tau$ and player $n-1$. Suppose it holds
at stage $\tau$ and player $i+1$. We are now ready to show the statement also
holds at stage $\tau$ and player $i$. We start with the definition the nested-
belief state $b^{i}_{\tau+1}$ at stage $\tau+1$ and player $i$ upon acting
according to $\langle u^{i}_{\tau},a^{i+1:}_{\tau}\rangle$ in total data
available to the planner $\varsigma_{\tau}^{i}\doteq\langle
s_{\tau},o^{i}_{\tau},u^{:i-1}_{\tau}\rangle$ and receiving observation
$z^{i}_{\tau+1}$. The proof proceeds similarly to that of player $n-1$, i.e.,

$\displaystyle b^{i}_{\tau+1}(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$
$\displaystyle\doteq\Pr\\{o^{i+1}_{\tau+1},b^{i+1}_{\tau+1}|\varsigma_{\tau}^{i},u^{i}_{\tau},a^{i+1:}_{\tau},z^{i}_{\tau+1}\\}.$
(13)

The expansion of (13) over nested-occupancy states $s^{i+1}_{\tau}$ at stage
$\tau$ and player $i+1$ and histories $z^{i+1}_{\tau+1}$ at stage $\tau+1$ and
player $i+1$, result in the following expression:

$\displaystyle b^{i}_{\tau+1}(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$
$\displaystyle=\textstyle\sum_{s^{i+1}_{\tau}\doteq(b^{i+1}_{\tau},o^{i+1}_{\tau},u_{\tau}^{:i})}\sum_{z^{i+1}_{\tau+1}}\Pr\\{s^{i+1}_{\tau},z^{i+1}_{\tau+1},o^{i+1}_{\tau+1},b^{i+1}_{\tau+1}|\varsigma_{\tau}^{i},u^{i}_{\tau},a^{i+1:}_{\tau},z^{i}_{\tau+1}\\}.$
(14)

The application of Bayes’ rule in expression (14) yields the following
expression: for any pairs $(o^{1:i+1}_{\tau+1},b^{i+1}_{\tau+1})$,

$\displaystyle b^{i}_{\tau+1}(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$
$\displaystyle=\sum_{s^{i+1}_{\tau}\doteq(b^{i+1}_{\tau},o^{i+1}_{\tau},u_{\tau}^{:i})}\sum_{z^{i+1}_{\tau+1}}\Pr\\{s^{i+1}_{\tau},z^{i+1}_{\tau+1},o^{i+1}_{\tau+1},b^{i+1}_{\tau+1},\varsigma_{\tau}^{i},u^{i}_{\tau},a^{i+1:}_{\tau},z^{i}_{\tau+1}\\}/\Pr\\{\varsigma_{\tau}^{i},u^{i}_{\tau},a^{i+1:}_{\tau},z^{i}_{\tau+1}\\}.$
(15)

The expansion of the joint probability into the product of conditional
probabilities and the application of Lemma C.1 yield the following expression:

$\displaystyle b^{i}_{\tau+1}(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$
$\displaystyle=\textstyle\sum_{s^{i+1}_{\tau}\doteq(b^{i+1}_{\tau},o^{i+1}_{\tau},u_{\tau}^{:i})}\sum_{z^{i+1}_{\tau+1}}\Pr\\{z^{i}_{\tau+1}|z^{i+1}_{\tau+1}\\}\cdot\Pr\\{o^{i+1}_{\tau+1}|o^{i+1}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),z^{i+1}_{\tau+1}\\}\cdot$
$\displaystyle\quad\Pr\\{b^{i+1}_{\tau+1}|b^{i+1}_{\tau},\langle
u^{:i}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}\rangle,z^{i+1}_{\tau+1}\\}\cdot\Pr\\{z^{i+1}_{\tau+1}|b^{i+1}_{\tau},\langle
u^{:i}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}\rangle\\}\cdot$
$\displaystyle\quad\Pr\\{s^{i+1}_{\tau}
|\varsigma_{\tau}^{i},u^{i}_{\tau}\\}/\Pr\\{z^{i}_{\tau+1}|\varsigma_{\tau}^{i},u^{i}_{\tau},a^{i+1:}_{\tau}\\}$
(16)

Using the boundary condition and the induction hypothesis, we obtain the
following expression, i.e.,

$\displaystyle b^{i}_{\tau+1}(o^{i+1}_{\tau+1},b^{i+1}_{\tau+1})$
$\displaystyle\propto\textstyle\sum_{s^{i+1}_{\tau}\doteq(b^{i+1}_{\tau},o^{i+1}_{\tau},u_{\tau}^{:i})}\tilde{T}(s^{i+1}_{\tau}
|b_{\tau}^{i},u^{:i}_{\tau})\sum_{z^{i+1}_{\tau+1}}\mathbb{1}\\{z^{i}_{\tau+1}\sqsubseteq\zeta^{i+1}(z^{i+1}_{\tau+1})\\}\cdot\delta_{\langle
o^{i+1}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),z^{i+1}_{\tau+1}\rangle}^{o^{i+1}_{\tau+1}}$
$\displaystyle\quad\delta_{T^{i+1}(b^{i+1}_{\tau},\langle
u^{:i}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}\rangle,z^{i+1}_{\tau+1})}^{b^{i+1}_{\tau+1}}\cdot\Omega^{i+1}(z^{i+1}_{\tau+1}|b^{i+1}_{\tau},\langle
u^{:i}_{\tau},a^{i+1}_{\tau}(o^{i+1}_{\tau}),a^{i+2:}_{\tau}\rangle).$ (17)

Hence, the statement holds at any stage $\tau$ and player $i$, which ends the
proof. ∎

###  C.3 Nested Belief States, Policies and Action-Value Functions At Player
$n$

This section establishes many important properties regarding player $n$.
First, it establishes that for any given stage and player $n$, the planner can
make decisions based on belief states instead of histories. To prove this
statement, one must demonstrate that belief states are capable of predicting
(1) the next observation for the subsequent stage and player $n$; (2) the next
belief state for the subsequent stage and player $n$; and (3) the immediate
reward. Next, it shows that belief-dependent policies are optimal at player
$n$. Finally, it describes the action-value functions under a history-
dependent policy of player $1$ to $n-1$ and a belief-dependent policy of
player $n$.

######  Lemma C.3.

Let $a^{:n-1}_{\tau}$ be a joint decision rule of player $1$ to $n-1$. Let
$b^{n}_{\tau}$ be a nested belief state, $o^{:n-1}_{\tau}$ be a joint history
of player $1$ to $n-1$, and $a^{:n-1}_{\tau}(o^{:n-1}_{\tau})$ be a joint
action of player $1$ to $n-1$ when following joint policy $a^{:n-1}_{\tau}$.
Let
$s^{n}_{\tau}\doteq(b^{n}_{\tau},o^{n}_{\tau},a^{:n-1}_{\tau}(o^{:n-1}_{\tau}))$
be a nested-occupancy state at stage $\tau$ and player $n$. Then, the
following propositions hold for any nested-occupancy state $s^{n}_{\tau}$ at
stage $\tau$ and player $n$.

  1. 1.

For any action $u^{n}_{\tau}$ and observation $z^{n}_{\tau+1}$, we have
$\Pr\\{z^{n}_{\tau+1}|s^{n}_{\tau},u^{n}_{\tau}\\}=\Omega^{n}(z^{n}_{\tau+1}|b_{\tau}^{n},\langle
u_{\tau}^{n},a^{:n-1}_{\tau}(o^{:n-1}_{\tau})\rangle)$.

  2. 2.

For any action $u^{n}_{\tau}$ and observation $z^{n}_{\tau+1}$, we have
$\Pr\\{b^{n}_{\tau+1}|s^{n}_{\tau},u^{n}_{\tau},z^{n}_{\tau+1}\\}=\delta^{b^{n}_{\tau+1}}_{T^{n}(b_{\tau}^{n},\langle
u_{\tau}^{n},a^{:n-1}_{\tau}(o^{:n-1}_{\tau})\rangle,z^{n}_{\tau+1})}$.

  3. 3.

For any action $u^{n}_{\tau}$, we have
$\mathbb{E}_{(x_{\tau},u_{\tau})\sim\Pr\\{\cdot
|s^{n}_{\tau},u^{n}_{\tau}\\}}\\{r(x_{\tau},u_{\tau})\\}=\mathbb{E}_{(x_{\tau},u_{\tau})\sim\Pr\\{\cdot
|b^{n}_{\tau},u_{\tau}^{n},a^{:n-1}_{\tau}(o^{:n-1}_{\tau})\\}}\\{r(x_{\tau},u_{\tau})\\}$.

###### Proof.

The two first propositions hold directly from Lemmas C.1 and C.2. The last
proposition holds because the immediate rewards depend on the histories of
player $n$ only through the corresponding belief states. Which ends the proof.
∎

######  Lemma C.4.

The optimal policy of player $n$ depends only upon the belief state not on
histories.

###### Proof.

The proof proceeds by induction. Let $a^{:n-1}_{0:}$ be the joint policy of
player $1$ to $n-1$. The best-response decision rule of player $n$ at stage
$\ell-1$ is written as follows: for any history $o^{n}_{\ell-1}$,

$\displaystyle a^{n}_{\ell-1}(o^{n}_{\ell-1})$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{u^{n}_{\ell-1}}~{}\mathbb{E}_{(x_{\ell-1},u_{\ell-1})\sim\Pr\\{\cdot
|b^{n}_{\ell-1},o^{n}_{\ell-1},u^{n}_{\ell-1},a^{:n-1}_{\ell-1}(o^{:n-1}_{\ell-1})\\}}\\{r(x_{\ell-1},u_{\ell-1})\\}$
(by Definition)
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{u^{n}_{\ell-1}}~{}\mathbb{E}_{(x_{\ell-1},u_{\ell-1})\sim\Pr\\{\cdot
|b^{n}_{\ell-1},u_{\ell-1}^{n},a^{:n-1}_{\ell-1}(o^{:n-1}_{\ell-1})\\}}\\{r(x_{\ell-1},u_{\ell-1})\\}.$
(by Lemma C.3)

The statement holds at stage $\ell-1$. Define the value function
$\tilde{\alpha}^{n}_{\ell-1}$ under the joint policy $a^{:n-1}_{0:}$ of player
$1$ to $n-1$,

$\bar{\alpha}^{n}_{\ell-1}\colon(b^{n}_{\ell-1},o^{:n-1}_{\ell-1})\mapsto\textstyle\max_{u^{n}_{\ell-1}}~{}\mathbb{E}_{(x_{\ell-1},u_{\ell-1})\sim\Pr\\{\cdot
|b^{n}_{\ell-1},u_{\ell-1}^{n},a^{:n-1}_{\ell-1}(o^{:n-1}_{\ell-1})\\}}\\{r(x_{\ell-1},u_{\ell-1})\\}.$

Define the value function $\bar{\beta}^{n}_{\ell-2}$ under the joint policy
$a^{:n-1}_{0:}$ of player $1$ to $n-1$,

$\bar{\beta}^{n}_{\ell-2}\colon(b^{n}_{\ell-2},o^{:n-1}_{\ell-2},u_{\ell-2})\mapsto\textstyle\mathbb{E}_{(x_{\ell-2},b^{n}_{\ell-1},o^{:n-1}_{\ell-1})\sim\Pr\\{\cdot
|b^{n}_{\ell-2},u_{\ell-2},o^{:n-1}_{\ell-2}\\}}\\{r(x_{\ell-2},u_{\ell-2})+\gamma\bar{\alpha}^{n}_{\ell-1}(b^{n}_{\ell-1},o^{:n-1}_{\ell-1})\\}.$

The best-response decision rule of player $n$ at stage $\ell-2$ is written as
follows: for any history $o^{n}_{\ell-2}$,

$\displaystyle a^{n}_{\ell-2}(o^{n}_{\ell-2})$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{u^{n}_{\ell-2}}~{}\bar{\beta}^{n}_{\ell-2}(b^{n}_{\ell-2},o^{:n-1}_{\ell-2},\langle
u_{\ell-2}^{n},a^{:n-1}_{\ell-2}(o^{:n-1}_{\ell-2})\rangle).$

Consequently, the statement holds for stages $\ell-1$ and $\ell-2$. Suppose
the statement holds for stage $\tau+1$, that is there exists an action-value
function $\bar{\beta}^{n}_{\tau}$ under the joint policy $a^{:n-1}_{0:}$ of
player $1$ to $n-1$,

$\bar{\beta}^{n}_{\tau}\colon(b^{n}_{\tau},o^{:n-1}_{\tau},u_{\tau})\mapsto\textstyle\mathbb{E}_{(x_{\tau},b^{n}_{\tau+1},o^{:n-1}_{\tau+1})\sim\Pr\\{\cdot
|b^{n}_{\tau},u_{\tau},o^{:n-1}_{\tau}\\}}\\{r(x_{\tau},u_{\tau})+\gamma\bar{\alpha}^{n}_{\tau+1}(b^{n}_{\tau+1},o^{:n-1}_{\tau+1})\\}.$

We are now ready to show the statement also holds at stage $\tau$. The best-
response decision rule of player $n$ at stage $\tau$ is written as follows:
for any history $o^{n}_{\tau}$,

$\displaystyle a^{n}_{\tau}(o^{n}_{\tau})$
$\displaystyle\textstyle\in\operatorname*{\arg\\!\max}_{u^{n}_{\tau}}~{}\bar{\beta}^{n}_{\tau}(b^{n}_{\tau},o^{:n-1}_{\tau},\langle
u_{\tau}^{n},a^{:n-1}_{\tau}(o^{:n-1}_{\tau})\rangle).$

This proves the statement holds for stage $\tau$, ending the proof. ∎

Lemma C.4 shows that the HIS assumption allows player $n$ to act based solely
upon belief states instead of histories optimally. In other words, a belief-
dependent policy exists as good or better than any history-dependent policy of
player $n$. The subsequent lemma shows how the use of belief-dependent
policies for player $n$ affects the description of the action-value function
under a joint history-dependent policy of player $1$ to $n-1$ and a belief-
dependent policy for player $n$.

######  Lemma C.5.

Let $a^{:n-1}_{0:}$ be the joint history-dependent policy of player $1$ to
$n-1$, $\tilde{a}^{n}_{0:}$ be the belief-dependent policy of player $n$. The
action-value function under joint policy $\langle
a^{:n-1}_{0:},\tilde{a}^{n}_{0:}\rangle$ is given as follows:

$\bar{\beta}^{n}_{\tau}\colon(b^{n}_{\tau},o^{:n-1}_{\tau},u^{:n}_{\tau})\mapsto\mathbb{E}_{(x_{\tau},b^{n}_{\tau+1},o^{:n-1}_{\tau+1})\sim\Pr\\{\cdot
|b^{n}_{\tau},u_{\tau},o^{:n-1}_{\tau}\\}}\\{r(x_{\tau},u_{\tau})+\gamma\bar{\beta}^{n}_{\tau+1}(b^{n}_{\tau+1},o^{:n-1}_{\tau+1},\langle
a^{:n-1}_{\tau+1}(o^{:n-1}_{\tau+1}),\tilde{a}^{n}_{\tau+1}(b^{n}_{\tau+1})\rangle)\\}$

with boundary condition $\bar{\beta}^{n}_{\ell}(\cdot,\cdot,\cdot)\doteq 0$.

###### Proof.

The proof follows directly from the proof of Lemma C.4. ∎

###  C.4 Proof of Theorem 2.4

###### Proof.

We shall treat each proposition separately.

#### Statement 1.

We prove the first statement by induction. We begin the proof by demonstrating
that the statement holds at player $n$. Let
$s^{n,\circ}_{\tau}\doteq(b^{n,\circ}_{\tau},o^{n,\circ}_{\tau},u^{:n-1,\circ}_{\tau})$
and
$s^{n,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau}\doteq(b^{n,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},o^{n,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{:n-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$
be two nested-occupancy states. Suppose
$s^{n,\circ}_{\tau}\sim_{\mathscr{B}_{1}}s^{n,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>that is
$(b^{n,\circ}_{\tau},u^{:n-1,\circ}_{\tau})=(b^{n,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{:n-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$.
Consider the action-value function $\tilde{\beta}^{n,*}_{\tau}$ at stage
$\tau$, player $n$, nested-occupancy state $s^{n,\circ}_{\tau}$ and action
$u^{n}_{\tau}$, i.e.,

$\displaystyle\tilde{\beta}^{n,*}_{\tau}(s^{n,\circ}_{\tau},u^{n}_{\tau})$
$\displaystyle\doteq\mathbb{E}_{x\sim
b^{n,\circ}_{\tau}(\cdot)}\\{\beta_{\tau}(x,o^{n,\circ}_{\tau},\langle
u^{:n-1,\circ}_{\tau},u^{n}_{\tau}\rangle)\\}$
$\displaystyle=\bar{\beta}^{n}_{\tau}(b^{n,\circ}_{\tau},o^{:n-1,\circ}_{\tau},\langle
u^{:n-1,\circ}_{\tau},u^{n}_{\tau}\rangle)$ $\displaystyle\text{(by Lemma
\ref{lem:action:value:fct:n})}.$

Since the action-value function $\bar{\beta}^{n}_{\tau}$ depends on the
nested-occupancy state only through the belief state $b^{n,\circ}_{\tau}$,
joint history $o^{:n-1,\circ}_{\tau}$, and joint action $\langle
u^{:n-1,\circ}_{\tau},u^{n}_{\tau}\rangle$, not upon joint history
$o^{n,\circ}_{\tau}$, thus does the action-value function
$\tilde{\beta}^{n,*}_{\tau}$. Hence, the first statement holds at player $n$.
Suppose the statement holds for player $i+1$. We are now ready to show it also
holds at player $i$. We start with the expression of optimal action-value
$\tilde{\beta}_{\tau}^{i,*}(s^{i,\circ}_{\tau},u^{i}_{\tau})$ for nested-
occupancy state $s^{i,\circ}_{\tau}$ and action $u^{i}_{\tau}$, i.e.,

$\displaystyle\tilde{\beta}_{\tau}^{i,*}(s^{i,\circ}_{\tau},u^{i}_{\tau})$
$\displaystyle=\textstyle\mathbb{E}_{s_{\tau}^{i+1,\circ}\sim\tilde{T}(\cdot|b_{\tau}^{i,\circ},\langle
u^{i}_{\tau},u^{:i-1,\circ}_{\tau}\rangle)}\\{\max_{u^{i+1}_{\tau}}\tilde{\beta}_{\tau}^{i+1,*}(s_{\tau}^{i+1,\circ},u_{\tau}^{i+1})\\}.$

An inspection of the transition function
$\tilde{T}(\cdot|b_{\tau}^{i,\circ},u^{:i}_{\tau})$ reveals that it depends on
nested-occupancy state $s_{\tau}^{i,\circ}$ only though nested-belief state
$b_{\tau}^{i,\circ}$ and joint action $u^{:i}_{\tau}$. Consequently, if we let
$s^{i,\circ}_{\tau}\sim_{\mathscr{B}_{1}}s^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>then we know
$(b^{i,\circ}_{\tau},u^{:i,\circ}_{\tau})=(b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{:i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$,
which leads to the statement:

$\displaystyle\tilde{\beta}_{\tau}^{i,*}(s^{i,\circ}_{\tau},u^{i}_{\tau})$
$\displaystyle=\textstyle\mathbb{E}_{s_{\tau}^{i+1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}\sim\tilde{T}(\cdot|b_{\tau}^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}},\langle
u^{i}_{\tau},u^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau}\rangle)}\\{\max_{u^{i+1}_{\tau}}\tilde{\beta}_{\tau}^{i+1,*}(s_{\tau}^{i+1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}},u_{\tau}^{i+1})\\}$
$\displaystyle=\tilde{\beta}_{\tau}^{i,*}(s^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{i}_{\tau}).$

This expression proves the first statement at any stage $\tau$ and player $i$.

#### Statement 2.

To prove the second statement, we build upon the first statement. If we let
$s^{i,\circ}_{\tau}\sim_{\mathscr{B}_{2}}s^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>then for any arbitrary joint action $u_{\tau}^{:i-1}$ we know that
$(b^{i,\circ}_{\tau},o^{i,\circ}_{\tau},u_{\tau}^{:i-1})\sim_{\mathscr{B}_{1}}(b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u_{\tau}^{:i-1})$.
If
$s^{i,\circ}_{\tau}\sim_{\mathscr{B}_{2}}s^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>we know that histories of subordinates are identical
$o^{:i-1,\circ}_{\tau}=o^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>then the following holds
$u_{\tau}^{:i-1}=a_{\tau}^{:i-1,*}(o^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})=a_{\tau}^{:i-1,*}(o^{:i-1,\circ}_{\tau})$.
Consequently, by the application of the first statement, we have for any
arbitrary action $u^{i}_{\tau}$,

$\tilde{\beta}_{\tau}^{i,*}(\langle
b^{i,\circ}_{\tau},o^{i,\circ}_{\tau},a_{\tau}^{:i-1,*}(o^{:i-1,\circ}_{\tau})\rangle,u^{i}_{\tau})=\tilde{\beta}_{\tau}^{i,*}(\langle
b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},a_{\tau}^{:i-1,*}(o^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})\rangle,u^{i}_{\tau}).$

Consequently, the sets of optimal actions
$A^{i,*}_{\tau}(o^{i,\circ}_{\tau})\doteq\operatorname*{\arg\\!\max}_{u^{i}_{\tau}}\tilde{\beta}_{\tau}^{i,*}(\langle
b^{i,\circ}_{\tau},o^{i,\circ}_{\tau},a_{\tau}^{:i-1,*}(o^{:i-1,\circ}_{\tau})\rangle,u^{i}_{\tau})$
and
$A^{i,*}_{\tau}(o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})\doteq\operatorname*{\arg\\!\max}_{u^{i}_{\tau}}\tilde{\beta}_{\tau}^{i,*}(\langle
b^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},a_{\tau}^{:i-1,*}(o^{:i-1,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})\rangle,u^{i}_{\tau})$
at histories $o^{i,\circ}_{\tau}$ and
$o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>respectively, are equivalent, i.e.,
$A^{i,*}_{\tau}(o^{i,\circ}_{\tau})=A^{i,*}_{\tau}(o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$.
Since
$a^{i,*}_{\tau}(o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$
and $a^{i,*}_{\tau}(o^{i,\circ}_{\tau})$ belong to the same set
$A^{i,*}_{\tau}(o^{i,\circ}_{\tau})=A^{i,*}_{\tau}(o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau})$,
they are interchangeable. In other words, the optimal action for history
$o^{i,\circ}_{\tau}$ is also optimal for history
$o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and vice versa. Interestingly, one can show that the expansions $\langle
o^{i,\circ}_{\tau},u^{i}_{\tau},z^{i}_{\tau+1}\rangle$ and $\langle
o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{i}_{\tau},z^{i}_{\tau+1}\rangle$
of histories $o^{i,\circ}_{\tau}$ and
$o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>upon taking the same action $u^{i}_{\tau}$ and receiving the same observation
$z^{i}_{\tau+1}$, respectively, will also have equivalent optimal actions.
Hence, essentially providing that the optimal policy for history
$o^{i,\circ}_{\tau}$ is also optimal for history
$o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>and vice versa. To show this statement, first notice that both histories
$\langle o^{i,\circ}_{\tau},u^{i}_{\tau},z^{i}_{\tau+1}\rangle$ and $\langle
o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{i}_{\tau},z^{i}_{\tau+1}\rangle$
will have the same histories of subordinates because original histories
$o^{i,\circ}_{\tau}$ and
$o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>had the same histories of subordinates and original histories
$o^{i,\circ}_{\tau}$ and
$o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>were expanded using the same action and observation. Next, we need to show
that the nested-belief states associated with the expanded histories $\langle
o^{i,\circ}_{\tau},u^{i}_{\tau},z^{i}_{\tau+1}\rangle$ and $\langle
o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color@gray@fill{.5}\bullet}}_{\tau},u^{i}_{\tau},z^{i}_{\tau+1}\rangle$
are also equivalent. The proof of this statement follows directly from the
fact that the transition function from one stage to the next one depends on
$\tilde{T}$, $T^{\cdot}$ and $\Omega^{\cdot}$. A careful inspection of these
functions reveals that they depend on nested-occupancy states at player $i$
only through nested-belief states at player $i$, joint histories of superiors
of player $i$, and actions of subordinates as demonstrated in Lemmas C.2 and
C.1. Histories of the current player are only used to select the action for
that player. However, our histories of interest have the same optimal action
set. So, assuming these histories take the same action does not hurt.
Consequently, if we let
$s^{i,\circ}_{\tau}\sim_{\mathscr{B}_{2}}s^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>then we know that
$o^{i,\circ}_{\tau}\sim_{\mathscr{P}}o^{i,{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>which ends the proof. Which ends the proof for both propositions. ∎

##  Appendix D Proof of Theorem 3.1

###### Proof.

For simplicity, throughout the proof, we assume with no loss of generality
that the central planner does not rely on public observations, so transition
function $\boldsymbol{T}$ is deterministic. Let $a^{*}_{0:}$ be an optimal
joint policy with value functions $\upsilon^{*}_{0:}$. Let $s^{*}_{\tau}$ be
the occupancy state generated under joint policy $a^{*}_{0:}$, with boundary
condition $s^{*}_{0}\doteq s_{0}$. Let $\upsilon_{0:}$ be the value function
that the PBVI algorithm produced over occupancy subsets $\tilde{S}_{0:}$.
Then, it follows that:

$\displaystyle\upsilon^{*}_{0}(s^{*}_{0})-\upsilon_{0}(s^{*}_{0})$
$\displaystyle=\textstyle(\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\boldsymbol{R}(s^{*}_{\tau},a^{*}_{\tau}))-\upsilon_{0}(s^{*}_{0}),\quad\text{(definition
of $\upsilon^{*}_{0}(s^{*}_{0})$)}$
$\displaystyle=\textstyle(\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\boldsymbol{R}(s^{*}_{\tau},a^{*}_{\tau}))-\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot(\upsilon_{\tau}(s^{*}_{\tau})-\upsilon_{\tau}(s^{*}_{\tau}))-\upsilon_{0}(s^{*}_{0}),\quad\text{(adding
zero)}.$

Next, we use the fact that $\upsilon_{\ell}(\cdot)\doteq 0$ to re-arrange
terms:

$\displaystyle=\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\boldsymbol{R}(s^{*}_{\tau},a^{*}_{\tau})+\left(\gamma^{\ell}\cdot\upsilon_{\ell}(s^{*}_{\ell})+\sum_{\tau=1}^{\ell-1}\gamma^{\tau}\cdot\upsilon_{\tau}(s^{*}_{\tau})\right)-\left(\gamma^{0}\cdot\upsilon_{0}(s^{*}_{0})+\sum_{\tau=1}^{\ell-1}\gamma^{\tau}\cdot\upsilon_{\tau}(s^{*}_{\tau})\right),$
$\displaystyle=\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\boldsymbol{R}(s^{*}_{\tau},a^{*}_{\tau})+\sum_{\tau=0}^{\ell-1}\gamma^{\tau+1}\cdot\upsilon_{\tau+1}(s^{*}_{\tau+1})-\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\upsilon_{\tau}(s^{*}_{\tau}),$
$\displaystyle=\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\left(\boldsymbol{R}(s^{*}_{\tau},a^{*}_{\tau})+\gamma\cdot\upsilon_{\tau+1}(s^{*}_{\tau+1})-\upsilon_{\tau}(s^{*}_{\tau})\right).$

Define $\upsilon^{\cdot}_{\tau}(s_{\tau})\colon
a_{\tau}\mapsto\boldsymbol{R}(s_{\tau},a_{\tau})+\gamma\cdot\upsilon_{\tau+1}(\boldsymbol{T}(s_{\tau},a_{\tau}))$.
It follows that

$\displaystyle\upsilon^{*}_{0}(s^{*}_{0})-\upsilon_{0}(s^{*}_{0})$
$\displaystyle=\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\left(\upsilon^{a^{*}_{\tau}}_{\tau}(s^{*}_{\tau})-\upsilon_{\tau}(s^{*}_{\tau})\right).$

If we fix
$s_{\tau}\doteq\operatorname*{\arg\\!\min}_{\tilde{s}_{\tau}\in\tilde{S}_{\tau}}\|s^{*}_{\tau}-\tilde{s}_{\tau}\|_{1}$,
then we know that $\|s^{*}_{\tau}-s_{\tau}\|_{1}\leq\delta_{\tilde{S}_{0:}}$
by definition of $\delta_{\tilde{S}_{0:}}$. Using action-values
$\upsilon^{a^{*}_{\tau}}_{\tau}(s_{\tau})$ to add zero into the previous error
bound results in:

$\displaystyle\upsilon^{*}_{0}(s^{*}_{0})-\upsilon_{0}(s^{*}_{0})$
$\displaystyle=\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\left(\upsilon^{a^{*}_{\tau}}_{\tau}(s^{*}_{\tau}))-\upsilon^{a^{*}_{\tau}}_{\tau}(s_{\tau})+\upsilon^{a^{*}_{\tau}}_{\tau}(s_{\tau})-\upsilon_{\tau}(s^{*}_{\tau})\right).$

Taking the best joint decision rule for $\upsilon^{\cdot}_{\tau}(s_{\tau})$
results in value $\upsilon_{\tau}(s_{\tau})$ greater or equal to
$\upsilon^{a^{*}_{\tau}}_{\tau}(s_{\tau})$, which leads to

$\displaystyle\upsilon^{*}_{0}(s^{*}_{0})-\upsilon_{0}(s^{*}_{0})$
$\displaystyle\leq\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\left(\upsilon^{a^{*}_{\tau}}_{\tau}(s^{*}_{\tau})-\upsilon^{a^{*}_{\tau}}_{\tau}(s_{\tau})+\upsilon_{\tau}(s_{\tau})-\upsilon_{\tau}(s^{*}_{\tau})\right).$

Recall that under a fixed joint policy, value functions are linear functions
of occupancy states, which allows us to re-arrange terms as follows:

$\displaystyle\upsilon^{*}_{0}(s^{*}_{0})-\upsilon_{0}(s^{*}_{0})$
$\displaystyle\leq\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\left(\upsilon^{a^{*}_{\tau}}_{\tau}(s^{*}_{\tau})-\upsilon_{\tau}(s^{*}_{\tau})+\upsilon_{\tau}(s_{\tau})-\upsilon^{a^{*}_{\tau}}_{\tau}(s_{\tau})\right)$
$\displaystyle=\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot(\upsilon^{a^{*}_{\tau}}_{\tau}-\upsilon_{\tau})\cdot(s^{*}_{\tau}-s_{\tau}).$

The application of the Hölder inegality, the use of the definition of
$\delta_{\tilde{S}_{0:}}$, and the use of the bounded reward function
$r(\cdot,\cdot)$, permit us to conclude:

$\displaystyle\upsilon^{*}_{0}(s^{*}_{0})-\upsilon_{0}(s^{*}_{0})$
$\displaystyle\leq\textstyle\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\|\upsilon^{a^{*}_{\tau}}_{\tau}-\upsilon_{\tau}\|_{\infty}\cdot\|s^{*}_{\tau}-s_{\tau}\|_{1}$
$\displaystyle=\textstyle\delta_{\tilde{S}_{0:}}\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\cdot\|\upsilon^{a^{*}_{\tau}}_{\tau}-\upsilon_{\tau}\|_{\infty}$
$\displaystyle\leq\textstyle
2c\delta_{\tilde{S}_{0:}}\sum_{\tau=0}^{\ell-1}\gamma^{\tau}\sum_{t=\tau}^{\ell-1}\gamma^{t-\tau}$
$\displaystyle=\textstyle
2c\delta_{\tilde{S}_{0:}}\sum_{\tau=0}^{\ell-1}\sum_{t=\tau}^{\ell-1}\gamma^{t}$
$\displaystyle=\textstyle
2c\delta_{\tilde{S}_{0:}}\sum_{\tau=0}^{\ell-1}\frac{\gamma^{\tau}-\gamma^{\ell}}{1-\gamma}$
$\displaystyle=\textstyle
2c\delta_{\tilde{S}_{0:}}\frac{1}{1-\gamma}\sum_{\tau=0}^{\ell-1}(\gamma^{\tau}-\gamma^{\ell})$
$\displaystyle=\textstyle
2c\delta_{\tilde{S}_{0:}}\frac{1}{1-\gamma}\sum_{\tau=0}^{\ell-1}\frac{1+\ell\gamma^{\ell+1}-(\ell+1)\gamma^{\ell}}{1-\gamma}$
$\displaystyle=\textstyle
2c\delta_{\tilde{S}_{0:}}\frac{1+\ell\gamma^{\ell+1}-(\ell+1)\gamma^{\ell}}{(1-\gamma)^{2}}.$

Which ends the proof. ∎

##  Appendix E Multi-Player Benchmarks

#### Multi-player Tiger.

The mono-player tiger problem was first introduced by Kaelbling et al. (1998)
and was later generalized to a two-player version by Nair et al. (2003). This
game describes a scenario where players face two closed doors, one of which
conceals a treasure while the other hides a dangerous tiger. Neither player
knows which door leads to the treasure and which one to the tiger, but they
can receive partial and noisy information about the tiger’s location by
listening. At any given time, each player can choose to open either the left
or right door, which will either reveal the treasure or the tiger, and reset
the game. To gain more information about the tiger’s location, players can
listen to hear the tiger on the left or right side, but with uncertain
accuracy. We have extended this problem to an $n$-player version by
incorporating hierarchical information-sharing and modifying the transition,
observation, and reward models following Nair et al. (2003), while ensuring
that the original two-player problem can still be recovered.

#### Multi-player Recycling Robot.

The recycling robot task was first introduced by Sutton & Barto (2018) as a
single-player problem. Later on, Amato et al. (2012) generalized it to a two-
player version in 2012. The multi-player formulation requires robots to work
together to recycle soda cans. In this problem, both robots have a battery
level, which can be either high or low. They have to choose between collecting
small or big wastes and recharging their own battery level. Collecting small
or big wastes can decrease the robot’s battery level, with a higher
probability when collecting the big waste. When a robot’s battery is
completely exhausted, it needs to be picked up and placed onto a recharging
spot, which results in a negative reward. The coordination problem arises when
robots cannot pick up a big waste independently. To solve this problem, an
$n$-player Dec-POMDP was derived by allowing a big soda to be picked up only
when all robots try to collect it simultaneously. The other transition and
observation probabilities come from the $n$ independent single-player models
introduced by Sutton & Barto (2018).

#### Multi-player Broadcast Channel.

In 1996, Ooi & Wornell (1996) introduced a scenario in which a unique channel
is shared by $n$ players, who aim at transmitting packets. The time is
discretized, and only one packet can be transmitted at each time step. If two
or more players attempt to send a packet at the same time, the transmission
fails due to a collision. In 2004, Hansen et al. extended this problem to a
partially observable one, focusing on two players (Hansen et al., 2004). We
used similar adaptations to define a partially observable version of the
original $n$-player broadcast channel.

#### Multi-player Grid3x3.

This problem was first introduced by Bernstein et al. (2002). It involves two
players who want to meet each other as soon as possible on a two-dimensional
grid. Each player has five possible actions: moving north, south, west, east,
or staying in place. To simulate an uncertain environment, each player’s
action has a fixed probability of being successful. Additionally, each player
can only sense their own location and has no knowledge of the other player’s
location. To adapt the problem for multiple players, we placed M players on
the grid, each with the same actions and perceptions as described above. The
reward has been redefined as the largest number of players minus one present
at one of the two meeting points. This way, the original problem can be
retrieved for two players.

##  Appendix F Experiments

We conducted three sets of experiments to assess our findings:

  1. 1.

To assess the exponential drop in time complexity of backups with respect to
an increasing number of players, we maintain the average time required to
perform a single backup, cf. Section F.1 – Average Backup Time for Increasing
Players.

  2. 2.

To assess the exponential drop in time complexity of backups with respect to
increasing horizons, we maintain the average time required to perform a single
backup, cf. Section F.2 – Average Backup Time for Increasing Horizon.

  3. 3.

To assess the superiority of our findings with respect to the state-of-the-art
approach to solve general decentralized partially Markov decision processes
near-optimally, cf. Section F.3 – Against State-Of-The-Art Solvers.

###  F.1 Average Backup Time for Increasing Players

This section investigates the average computational time required to perform a
single backup for increasing players, cf. Figures 3,4,5, and 6. The
experiments show that on all tested benchmarks, hPBVI exhibits a reduction in
time complexity compared to the other variants. Moreover, hPBVI can handle a
larger number of agents (up to 9 for the Tiger, MABC, and Recycling) compared
to the other variants, which are limited to a maximum of 5 agents. This time-
complexity reduction in hPBVI is the result of our findings providing the
ability to fully exploit the hierarchical information-sharing structure.

Figure 3: ABT for the tiger problem and different numbers of players. Figure
4: ABT for the recycling problem and different numbers of players. Figure 5:
ABT for the mabc problem and different numbers of players. Figure 6: ABT for
the grid3x3 problem and different numbers of players.

###  F.2 Average Backup Time for Increasing Horizons

This section investigates the average computational time required to perform a
single backup for increasing horizons, cf. Figures 7, 8, 9, and 10. The
experiments show once again that on all tested benchmarks, hPBVI exhibits an
exponential drop in time complexity compared to the other variants. However,
all three variants of the PBVI algorithm exhibit an increase in time
complexity with respect to the planning horizon. This increase in time
complexity is expected since, as time goes the number of backups also
increases.

Figure 7: Average backup time as a function of planning horizons for Tiger.
Figure 8: Average backup time as a function of planning horizons for
Recycling. Figure 9: Average backup time as a function of planning horizons
for MABC. Figure 10: Average backup time as a function of planning horizons
for Grid3x3, BoxPushing and Mars.

###  F.3 Against State-Of-The-Art Solvers

In this section, we compare our PBVI algorithm variants with two local
algorithms, namely A2C and IQL, which are state-of-the-art and can handle a
large number of players, as shown in Figures 11, 12, 13, and 13. However,
these algorithms prioritize scalability over optimality and may get stuck in
local optima. Our experiments demonstrate that hPBVI consistently outperforms
all competitors in nearly all tested benchmarks in terms of convergence time
and the value of the solution found within 30 minutes. In some weakly coupled
domains, A2C and IQL find nearly optimal solutions close to those found by
hPBVI.

Figure 11: Anytime values for Tiger and $\ell=30$. Figure 12: Anytime values
for Recycling and $\ell=30$. Figure 13: Anytime values for Multi-agent
broadcast channel and $\ell=30$. Figure 14: Anytime values for Grid3x3,
BoxPushing and Mars.