[#1][#1]

# HSVI can solve
zero-sum Partially Observable Stochastic Games

Aurélien Delage
CITI
INSA Lyon
Villeurbanne
<EMAIL_ADDRESS>
Olivier Buffet
INRIA - CNRS
Université de Lorraine
Villers-lès-Nancy
<EMAIL_ADDRESS>
Jilles S. Dibangoye
CITI
INSA Lyon
Villeurbanne
<EMAIL_ADDRESS>
Abdallah Saffidine
University of New South Wales
Sidney
<EMAIL_ADDRESS>
###### Abstract

State-of-the-art methods for solving 2-player zero-sum imperfect information
games rely on linear programming or regret minimization, though not on dynamic
programming (DP) or heuristic search (HS), while the latter are often at the
core of state-of-the-art solvers for other sequential decision-making
problems. In partially observable or collaborative settings (e.g., POMDPs and
Dec-POMDPs), DP and HS require introducing an appropriate statistic that
induces a fully observable problem as well as bounding (convex) approximators
of the optimal value function. This approach has succeeded in some subclasses
of 2-player zero-sum partially observable stochastic games (zs-POSGs) as well,
but how to apply it in the general case still remains an open question. We
answer it by (i) rigorously defining an equivalent game to work with, (ii)
proving mathematical properties of the optimal value function that allow
deriving bounds that come with solution strategies, (iii) proposing for the
first time an HSVI-like solver that provably converges to an
$\epsilon$-optimal solution in finite time, and (iv) empirically analyzing it.
This opens the door to a novel family of promising approaches complementing
those relying on linear programming or iterative methods.

##  1 Introduction

Solving imperfect information sequential games is a challenging field with
many applications from playing Poker [Kuhn-ctg50] to security games
[BasNitGat-aaai16]. We focus on finite-horizon 2-player zero-sum partially
observable stochastic games (zs-POSGs), an important class of games that is
equivalent to that of zero-sum extensive-form games (zs-EFGs) [OliVla-
tr06]111Note: POSGs are equivalent to the large class of “well-behaved” EFGs
as defined by KovSBBL-corr20.. From the viewpoint of (maximizing) player $1$,
we aim at finding a strategy with a worst-case expected return (i.e., whatever
player $2$’s strategy) within $\epsilon$ of the Nash equilibrium value (NEV).

A first approach to solving a zs-POSG is to turn it into a zs-EFG addressed as
a sequence form linear program (SFLP) [KolMegSte-geb96, Stengel-geb96,
BosEtAl-jair14], giving rise to an exact algorithm. A second approach is to
use an iterative game solver, i.e., either a counterfactual-regret-based
method (CFR) [ZinJohBowPic-nips07, BroSan-science18], or a first-order method
[HodGilPenSan-mor10, KroWauKKSan-mp20], both coming with asymptotic
convergence properties. CFR-based approaches now incorporate deep
reinforcement learning and search, some of them winning against top human
players at heads-up no limit hold’em poker [MorEtAl-science17, BroSan-
science18, BroBakLerQon-nips20]. A third approach, proposed by Wiggers-msc15,
is to use two parallel searches in strategy space, one per player, so that the
gap between both strategies’ security levels (i.e., the values of their
opponent’s best responses) bounds the distance to the NEV.

In contrast, dynamic programming and heuristic search have not been applied to
general zs-POSGs, while often at the core of state-of-the-art solvers in other
problem classes that involve Markovian dynamics, partial observability and
multiple agents (POMDP [Astrom-jmaa65, Smith-phd07], Dec-POMDP [SzeChaZil-
uai05, DibAmaBufCha-jair16], or subclasses of zs-POSGs with simplifying
observability assumptions [GhoMcDSin-jota04, ChaDoy-tcl14, BasSte-jco15,
HorBosPec-aaai17, ColKoc-jet01, HorBos-aaai19]). They all rely on some
statistic that induces a fully observable problem whose value function
($V^{*}$) exhibits continuity properties that allow deriving bounding
approximations. WigOliRoi-ecai16, WigOliRoi-corr16 progress in this direction
for zs-POSGs by demonstrating an important continuity property of the optimal
value function, and proposing a reformulation as a particular equivalent game.
We work in a similar direction,  1. using a game with different observability
hypotheses,  2. proving theoretical results they implicitly rely on, and  3.
building on some of their results to derive an HSVI-like algorithm solving the
zs-POSG.

Section 2 presents some necessary background, including the concept of
occupancy state [DibAmaBufCha-jair16, WigOliRoi-corr16] (i.e., the probability
distribution over the players’ past action-observation histories), and
properties that rely on it. Then, Section 3 describes theoretical
contributions. First, we rigorously reformulate the problem as a non-
observable game, and demonstrate that the Nash equilibrium value can be
expressed with a recursive formula, which is a required tool for DP and HS
(Section 3.1). Second, we exhibit novel continuity properties of optimal value
functions and derive bounding approximators, a second tool made necessary due
to the continuous state space of the new game, before showing that these
approximators come with valid solution strategies for the zs-POSG (Section
3.2). Third, we adapt SmiSim-uai05’ [SmiSim-uai05] HSVI’s algorithmic scheme
to $\epsilon$-optimally solve the problem in finitely many iterations (Section
3.3). Section 4 presents an empirical analysis of the approach. Section 5
discusses similarities and differences of our work with CFR-based continual
resolving methods before concluding.

##  2 Background

Here, we first give basic definitions about zs-POSGs, including the solution
concept at hand. Then we introduce an equivalent game where a state
corresponds to a statistic summarizing past behaviors, which leads to some
important properties of the game’s optimal value.

###  2.1 zs-POSGs

######  Definition 2.1 (zs-POSGs).

As illustrated through a dynamic influence diagram in Figure 1, a (2-player)
zero-sum partially observable stochastic game (zs-POSG) is defined by a tuple
$\langle{\mathcal{}S},{\mathcal{}A}^{1},{\mathcal{}A}^{2},{\mathcal{}Z}^{1},{\mathcal{}Z}^{2},P,r,H,\gamma,b_{0}\rangle$,
where

  * •

${\mathcal{}S}$ is a finite set of states;

  * •

${\mathcal{}A}^{i}$ is (player) $i$’s finite set of actions;

  * •

${\mathcal{}Z}^{i}$ is $i$’s finite set of observations;

  * •

$P_{a^{1},a^{2}}^{z^{1},z^{2}}(s^{\prime}|s)$ is the probability to transition
to state $s^{\prime}$ and receive observations $z^{1}$ and $z^{2}$ when
actions $a^{1}$ and $a^{2}$ are performed while in state $s$;

  * •

$r(s,a^{1},a^{2})$ is a (scalar) reward function;

  * •

$H\in\mathbb{N}$ is a (finite) temporal horizon;

  * •

$\gamma\in[0,1]$ is a discount factor; and

  * •

$b_{0}$ is the initial belief state, i.e., a probability distribution over
states at $t=0$.

$\ S_{t}\ $start$S_{t+1}$$S_{t+2}$$\ Z^{1}_{t}\ $$Z^{1}_{t+1}$$Z^{1}_{t+2}$$\
Z^{2}_{t}\ $$Z^{2}_{t+1}$$Z^{2}_{t+2}$$\ A^{1}_{t}\ $$A^{1}_{t+1}$$\
A^{2}_{t}\
$$A^{2}_{t+1}$Time$t$$t+1$$t+2$$r(s,a^{1},a^{2})$$P^{z^{1},z^{2}}_{a^{1},a^{2}}(s^{\prime}|s)$$r(s,a^{1},a^{2})$$P^{z^{1},z^{2}}_{a^{1},a^{2}}(s^{\prime}|s)$Hidden$1$’s
viewpoint$2$’s viewpoint

Figure 1: Dynamic influence diagram representing the evolution of a zs-POSG

From the Dec-POMDP, POSG and EFG literature, we use the following concepts and
definitions:

$\theta^{i}_{\tau}$

$=(a^{i}_{0},z^{i}_{1},\dots,a^{i}_{\tau-1},z^{i}_{\tau})$ is a length-$\tau$
action-observation history (aoh) for $i$. We note $\Theta_{\tau}^{i}$ the set
of all aohs for player $i$ at horizon $\tau$ such that any aoh
$\theta_{\tau}^{i}$ is in $\cup_{t=0}^{H-1}\Theta^{i}_{t}$.

$\beta^{i}_{\tau}$

is a (behavioral) decision rule (dr) at $\tau$ for $i$, i.e., a mapping from
private aohs in $\Theta^{i}_{\tau}$ to distributions over private actions.
$\beta^{i}_{\tau}(\theta^{i}_{\tau},a^{i})$ is the probability to pick $a^{i}$
when facing $\theta^{i}_{\tau}$.

$\beta^{i}_{\tau:\tau^{\prime}}$

$=(\beta^{i}_{\tau},\dots,\beta^{i}_{\tau^{\prime}})$ is a behavioral strategy
for $i$ from time step $\tau$ to $\tau^{\prime}$ (included).

When considering both players, the last 3 concepts become:

${\boldsymbol{\theta}}_{\tau}$

$=(\theta^{1}_{\tau},\theta^{2}_{\tau})$
($\in{\boldsymbol{\Theta}}=\cup_{t=0}^{H-1}{\boldsymbol{\Theta}}_{t}$), a
joint aoh at $\tau$,

${\boldsymbol{\beta}}_{\tau}$

$=\langle\beta^{1}_{\tau},\beta^{2}_{\tau}\rangle$
($\in{\mathcal{}B}=\cup_{t=0}^{H-1}{\mathcal{}B}_{t}$), a decision rule
profile, and

${\boldsymbol{\beta}}_{\tau:\tau^{\prime}}$

$=\langle\beta^{1}_{\tau:\tau^{\prime}},\beta^{2}_{\tau:\tau^{\prime}}\rangle$,
a behavioral strategy profile.

#### Nash Equilibria

Here, player $1$ (respectively $2$) wants to maximize (resp. minimize) the
expected return, or value, of strategy profile ${\boldsymbol{\beta}}_{0:H-1}$,
defined as the discounted sum of future rewards, i.e.,

$\displaystyle V_{0}({\boldsymbol{\beta}}_{0:H-1})$
$\displaystyle=E\left[\sum_{t=0}^{H-1}\gamma^{t}R_{t}\mid{\boldsymbol{\beta}}_{0:H-1}\right],$

where $R_{t}$ is the random variable associated to the instant reward at $t$.
This leads to the solution concept of Nash equilibrium strategy (NES).

######  Definition 2.2 (Nash Equilibrium).

The strategy profile
${\boldsymbol{\beta}}^{*}_{0:H-1}=\langle\beta^{1*}_{0:H-1},\beta^{2*}_{0:H-1}\rangle$
is a NES if no player has an incentive to deviate, which can be written:

$\displaystyle\forall\beta^{1}_{0:H-1},\
V_{0}(\beta^{1*}_{0:H-1},\beta^{2*}_{0:H-1})$ $\displaystyle\geq
V_{0}(\beta^{1}_{0:H-1},\beta^{2*}_{0:H-1})\text{ and }$
$\displaystyle\forall\beta^{2}_{0:H-1},\
V_{0}(\beta^{1*}_{0:H-1},\beta^{2*}_{0:H-1})$ $\displaystyle\leq
V_{0}(\beta^{1*}_{0:H-1},\beta^{2}_{0:H-1}).$

In such a game, all NESs have the same Nash-equilibrium value (NEV),
$V^{*}_{0}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}V_{0}(\beta^{1*}_{0:H-1},\beta^{2*}_{0:H-1})$. Our specific
objective is to find an $\epsilon$-NES, i.e., a behavioral strategy profile
such that any player would gain at most $\epsilon$ by deviating.

#### Why writing a Bellman Optimality Equation is Hard

Our approach requires writing Bellman optimality equations. The main obstacle
to achieve this is to find an appropriate characterization of a subproblem
that allows

  1. 1.

predicting both the immediate reward and the next possible subproblems given
an immediate decision;

  2. 2.

connecting a subproblem’s solution with solutions of its own (lower-level)
subproblems; and

  3. 3.

prescripting a solution strategy for the subproblem built on solutions of
lower-level subproblems.

In our setting, a player’s aoh does not characterize a subproblem since her
opponent’s strategy is also required to predict the expected reward and the
next aohs. For their part, joint aohs allow predicting next joint aohs given
both player’s immediate decision rules, but would not be appropriate either,
since player $i$ cannot decide how to act when facing some individual aoh
$\theta^{i}_{\tau}$ without considering all possible aohs of his opponent
$\neg i$.

Partial behavioral strategy profiles (sequences of behavioral decision rule
profiles from $t=0$ to some $\tau$) contain enough information to completely
describe the situation at $\tau$, and are thus necessarily predictive. We
still need to demonstrate that they are connected, despite decision rules not
being public, and prescriptive, despite the need to address global-consistency
issues illustrated in the following example.

######  Example 1.

Matching pennies is a well-known 2-player zero-sum game in which each player
has a penny and secretly chooses one side (head or tail). Then, both penny’s
sides are revealed, and player $1$ wins (payoff of $+1$) if both chosen sides
match and looses (payoff of $-1$) if not.

We here formalize this game as a zs-POSG (as illustrated in Figure 2) where
player $1$ actually picks his action at $t=0$, and player $2$ at $t=1$. Hence
the tuple
$\langle{\mathcal{}S},{\mathcal{}A}^{1},{\mathcal{}A}^{2},{\mathcal{}Z}^{1},{\mathcal{}Z}^{2},P,r,H,\gamma,b_{0}\rangle$
where:

  * •

${\mathcal{}S}=\\{s_{i},s_{h},s_{t}\\}$, where $s_{i}$ is the initial state,
and $s_{h}$ and $s_{t}$ represent a memory of $1$’s last move: respectively
"head" or "tail";

  * •

${\mathcal{}A}^{1}={\mathcal{}A}^{2}=\\{a_{h},a_{t}\\}$ for playing "head"
($a_{h}$) or "tail" ($a_{t}$);

  * •

${\mathcal{}Z}^{1}={\mathcal{}Z}^{2}=\\{z_{n}\\}$ a "none" trivial
observation;

  * •

$P_{{\boldsymbol{a}}}^{{\boldsymbol{z}}}(s^{\prime}|s)=T(s,{\boldsymbol{a}},s^{\prime})\cdot\mathcal{O}({\boldsymbol{a}},s^{\prime},{\boldsymbol{z}})$,
using the next two definitions;

  * •

$T$ is deterministic and such that ($\cdot$ is used to denote "for all")

    * –

$T(\cdot,\cdot,a_{h})=s_{h}$,

    * –

$T(\cdot,\cdot,a_{t})=s_{t}$;

  * •

$\mathcal{O}$ is deterministic and always returns "$z_{n}$";

  * •

$r$ is such that

    * –

$r(s_{i},\cdot,\cdot)=0$,

    * –

$r(s_{t},\cdot,a_{t})=r(s_{h},\cdot,a_{h})=+1$,

    * –

$r(s_{t},\cdot,a_{h})=r(s_{h},\cdot,a_{t})=-1$;

  * •

$H=2$;

  * •

$\gamma=1$;

  * •

$b_{0}$ is such that the initial state is $s_{i}$ with probability $1$.

$s_{i}$$s_{h}$$*$$+1$$*,a_{h}$$*$$-1$$*,a_{t}$$a_{h},*$$s_{t}$$*$$-1$$*,a_{h}$$*$$+1$$*,a_{t}$$a_{t},*$nodes
indistinguishable to $P2$ Figure 2: Simplified tree representation of the
sequentialized Matching Pennies game. Irrelevant actions, noted $*$, allow
merging edges with the same action for (i) player $2$ at $t=0$, and (ii)
player $1$ at $t=1$. Notes: (a) Due to irrelevant actions, this game can be
seen as an Extensive Form Game, despite players acting simultaneously. (b)
Players only know about their past action history (in this observation-free
game).

Let us then assume that both players’ drs at $t=0$ are fixed, with
$\beta^{1}_{0}$ randomly picking $a_{t}$ or $a_{h}$ (i.e., it induces a NES
whatever his dr at $t=1$). Then, we face a "subgame" at $t=1$ where any
strategy profile $\langle\beta^{1}_{1:1},\beta^{2}_{1:1}\rangle$ is a NES
profile with Nash equilibrium value $0$. In particular, $2$ can pick a
deterministic strategy $\beta^{2}_{1:1}$, which will be said to be locally
consistent. Yet, for $2$, such a NES in the subgame at $\tau=1$ is not
necessarily globally consistent, i.e., it may not be part of a NES for the
original game (i.e., starting from $\tau=0$). Intuitively, in such global-
consistency issues KovEtAl-aij-2022, Schmid-phd21 (also called safety issues
Burch-aaai-2014), the choices made at latter time steps do not account for
possible deviations from the opponent at earlier time steps.

As detailed in the next section, we will characterize a subproblem not with
the raw data of partial strategy profiles, but with a sufficient statistic,
and this characterization will be used as the state of a new dynamic game
equivalent to the zs-POSG.

###  2.2 Occupancy State and Occupancy Markov Game

We now introduce an equivalent game, in which trajectories correspond to
behavioral strategy profiles, and which we will be able to decompose
temporally (and recursively), a first key tool for DP and HS.

To cope with the necessarily continuous nature of its state space, we will set
this game in occupancy space, i.e., a statistic that sums up past dr profiles.
This will let us derive continuity properties on which to build point-based
approximators.

As WigOliRoi-corr16, let us formally define an occupancy state (os)
$\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}$ as the probability distribution
over joint aohs ${\boldsymbol{\theta}}_{\tau}$ given partial strategy profile
${\boldsymbol{\beta}}_{0:\tau-1}$. This statistic exhibits the usual Markov
and sufficiency properties:

[Adapted from DibAmaBufCha-jair16 [DibAmaBufCha-jair16, Thm. 1] – Proof in
Section B.1]propositionlemOccSufficient (originally stated on page 2.2)
$\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}$, together with
${\boldsymbol{\beta}}_{\tau}$, is a sufficient statistic to compute (i) the
next os,
$T(\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}},{\boldsymbol{\beta}}_{\tau})\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\sigma_{{\boldsymbol{\beta}}_{0:\tau}}$, and (ii) the expected
reward at $\tau$:
$r(\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}},{\boldsymbol{\beta}}_{\tau})\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\operatorname{\mathbb{E}}\left[R_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau-1}\oplus{\boldsymbol{\beta}}_{\tau}\right]$,
where $\oplus$ denotes a concatenation.

Writing from now on $\sigma_{\tau}$, as short for
$\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}$, the os associated with some prefix
strategy profile ${\boldsymbol{\beta}}_{0:\tau-1}$, the proof essentially
relies on deriving the following formulas:
$\forall\theta^{1}_{\tau},a^{1},z^{1},\theta^{2}_{\tau},a^{2},z^{2}$,

$\displaystyle
T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})((\theta^{1}_{\tau},a^{1},z^{1}),(\theta^{2}_{\tau},a^{2},z^{2}))$
(1) $\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}Pr((\theta^{1}_{\tau},a^{1},z^{1}),(\theta^{2}_{\tau},a^{2},z^{2})|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$
(2)
$\displaystyle=\beta^{1}_{\tau}(\theta^{1}_{\tau},a^{1})\beta^{2}_{\tau}(\theta^{2}_{\tau},a^{2})\sigma_{\tau}({\boldsymbol{\theta}}_{\tau})\sum_{s,s^{\prime}}P^{{\boldsymbol{z}}}_{{\boldsymbol{a}}}(s^{\prime}|s)b(s|{\boldsymbol{\theta}}_{\tau}),$
(3) where $b(s|{\boldsymbol{\theta}}_{\tau})$ is a belief state obtained by
Hidden Markov Model filtering; and $\displaystyle
r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}E[r(S,A^{1},A^{2})|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}]$ (4)
$\displaystyle=\sum_{s,{\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}}\sigma_{\tau}({\boldsymbol{\theta}}_{\tau})b(s|{\boldsymbol{\theta}}_{\tau})\beta^{1}_{\tau}(a^{1}|\theta^{1}_{\tau})\beta^{2}_{\tau}(a^{2}|\theta^{2}_{\tau})r(s,{\boldsymbol{a}}).$
(5)

We can then derive, from a zs-POSG, a non-observable zero-sum game similar to
WigOliRoi-corr16’s plan-time NOSG [WigOliRoi-corr16, Definition 4], but
without assuming that the players’ past strategies are public.

######  Definition 2.3 (zero-sum occupancy Markov Game (zs-oMG)).

A zero-sum occupancy Markov game (zs-oMG)222We use (i) “Markov game” instead
of “stochastic game” because the dynamics are not stochastic, and (ii)
“partially observable stochastic game” to stick with the literature. is
defined by the tuple
$\langle{\mathcal{}O}^{\sigma},{\mathcal{}B},T,r,H,\gamma\rangle$, where:

  * •

${\mathcal{}O}^{\sigma}(=\cup_{t=0}^{H-1}{\mathcal{}O}^{\sigma}_{t})$ is the
set of oss induced by the zs-POSG;

  * •

${\mathcal{}B}$ is the set of dr profiles of the zs-POSG;

  * •

$T$ is the deterministic transition function in Equation 1;

  * •

$r$ is the reward function in Equation 4; and

  * •

$H$ and $\gamma$ are as in the zs-POSG

($b_{0}$ is not in the tuple but serves to define $T$ and $r$).

In this game, as in the zs-POSG, a player’s solution is a behavioral strategy.
Besides, the value of a strategy profile ${\boldsymbol{\beta}}_{0:H-1}$ is the
same for both zs-oMG and zs-POSG, so that they share the same $\epsilon$-NEV
and $\epsilon$-NESs. We can thus work with zs-oMGs as a means to solve zs-
POSGs.

The following aims at deriving a recursive expression of $V^{*}_{0}$, as well
as continuity properties.

#### Bellman Optimality Equation

Despite the os at $\tau>0$ not being accessible to any player, let us define a
subgame at $\sigma_{\tau}$ as the restriction starting from time step $\tau$
under this particular occupancy state, meaning that we are seeking strategies
$\beta^{1}_{\tau:H-1}$ and $\beta^{2}_{\tau:H-1}$. $\sigma_{\tau}$ tells us
which aohs each player could be facing with non-zero probability, and are thus
relevant for planning. We can then define the value function in any os
$\sigma_{\tau}$ for any strategy profile ${\boldsymbol{\beta}}_{\tau:H-1}$ as
follows:

$\displaystyle V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:H-1})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}E[\sum_{t=\tau}^{\infty}\gamma^{t-\tau}r(S_{t},A_{t})|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:H-1}].$
(6)

The optimal value of a subgame rooted at $\sigma_{\tau}$,
$V^{*}(\sigma_{\tau})$, is thus the unique NEV for the previous criterion333We
will come back to the validity of this point in Section 3.1.. WigOliRoi-ecai16
then proved key continuity properties of $V^{*}$ discussed next.

#### Concavity and Convexity Results

As a preliminary step, WigOliRoi-corr16 decompose an occupancy state
$\sigma_{\tau}$ into a marginal term $\sigma_{\tau}^{m,1}$ and a conditional
term $\sigma_{\tau}^{c,1}$, where

  * •

$\sigma_{\tau}^{m,1}(\theta_{\tau}^{1})=\sum_{\theta_{\tau}^{2}}\sigma_{\tau}(\theta_{\tau}^{1},\theta_{\tau}^{2})$
is the probability of $1$ facing $\theta_{\tau}^{1}$ under $\sigma_{\tau}$,
and

  * •

$\sigma_{\tau}^{c,1}(\theta_{\tau}^{2}|\theta_{\tau}^{1})=\frac{\sigma_{\tau}(\theta_{\tau}^{1},\theta_{\tau}^{2})}{\sigma_{\tau}^{m,1}(\theta_{\tau}^{1})}$
is the probability of $2$ facing $\theta_{\tau}^{2}$ under $\sigma_{\tau}$
given that $1$ faces $\theta_{\tau}^{1}$,

so that
$\sigma_{\tau}(\theta_{\tau}^{1},\theta_{\tau}^{2})=\sigma_{\tau}^{m,1}(\theta_{\tau}^{1})\cdot\sigma_{\tau}^{c,1}(\theta_{\tau}^{2}|\theta_{\tau}^{1})$.
(Symmetric definitions apply by swapping players $1$ and $2$.) In addition,
let us denote $T^{1}_{m}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ and
$T^{1}_{c}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ the marginal and
conditional terms associated to
$T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$.

Now, if $1$ faces aoh $\theta^{1}_{\tau}$, knows $2$’s future strategy
$\beta^{2}_{\tau:H-1}$, and has access to
$\sigma_{\tau}^{c,1}(\theta^{2}_{\tau}|\theta^{1}_{\tau})$ for any
$\theta_{\tau}^{2}$, then she faces a POMDP whose optimal value we denote
$\nu^{2}_{[\sigma_{\tau}^{c,1},\beta^{2}_{\tau:H-1}]}(\theta^{1}_{\tau})$.
This leads to defining the best-response value vector
$\nu^{2}_{[\sigma_{\tau}^{c,1},\beta^{2}_{\tau:H-1}]}$, which contains one
component per aoh $\theta^{1}_{\tau}$, and writing the value of $1$’s best
response against $\beta^{2}_{\tau:H-1}$ under $\sigma_{\tau}$ as
$\sigma_{\tau}^{m,1}\cdot\nu^{2}_{[\sigma_{\tau}^{c,1},\beta_{\tau:H-1}^{2}]}$.
But then, because $2$ also knows $\sigma_{\tau}$, she can in fact pick
$\beta^{2}_{\tau:H-1}$ to minimize this value, so that we get the following
theorem.

######  Theorem 2.4 ([WigOliRoi-corr16, Thm. 2]).

For any $\tau\in\\{0\mathinner{\ldotp\ldotp}H-1\\}$, $V_{\tau}^{*}$ is (i)
concave w.r.t. $\sigma_{\tau}^{m,1}$ for a fixed $\sigma_{\tau}^{c,1}$, and
(ii) convex w.r.t. $\sigma_{\tau}^{m,2}$ for a fixed $\sigma_{\tau}^{c,2}$.
More precisely,

$\displaystyle V_{\tau}^{*}(\sigma_{\tau})$
$\displaystyle=\min_{\beta_{\tau:H-1}^{2}}\left[\sigma_{\tau}^{m,1}\cdot\nu^{2}_{[\sigma_{\tau}^{c,1},\beta_{\tau:H-1}^{2}]}\right]=\max_{\beta_{\tau:H-1}^{1}}\left[\sigma_{\tau}^{m,2}\cdot\nu^{1}_{[\sigma_{\tau}^{c,2},\beta_{\tau:H-1}^{1}]}\right],\text{where}$

$\nu^{2}_{[\sigma_{\tau}^{c,1},\beta^{2}_{\tau:H-1}]}(\theta^{1}_{\tau})\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\max_{\beta_{\tau:H-1}^{1}}\mathbb{E}_{\theta_{\tau}^{2}\sim\sigma_{\tau}^{c,1}(\theta_{\tau}^{1})}\left\\{\sum_{t=\tau}^{H-1}\gamma^{t-\tau}r(S_{t},A_{t}^{1},A_{t}^{2})\mid\beta_{\tau:H-1}^{1},\beta_{\tau:H-1}^{2}\right\\}$.

###### Proof.

(Sketch) We start from Neu-ma28’s Minimax theorem [Neu-ma28] giving the
following equation:

$\displaystyle
V_{\tau}^{*}(\sigma_{\tau})=\min_{\beta_{\tau:H-1}^{2}}\max_{\beta_{\tau:H-1}^{1}}\left[V_{\tau}(\sigma_{\tau},\beta_{\tau:H-1}^{1},\beta_{\tau:H-1}^{1})\right]$
$\displaystyle=\min_{\beta_{\tau:H-1}^{2}}\max_{\beta_{\tau:H-1}^{1}}\left[\mathbb{E}\left\\{\sum_{t=\tau}^{H-1}\gamma^{t-\tau}r(S_{t},A_{t}^{1},A_{t}^{2})\mid\theta_{\tau}^{1},\beta_{\tau:H-1}^{1},\beta_{\tau:H-1}^{2},\sigma^{c,1}_{\tau}\right\\}\right],$
then, observing that $1$’s best response to $\beta_{\tau:}^{2}$ can be
computed for each aoh $\theta_{\tau}^{1}$ independently, we can swap the
$\max$ operator and part of the expectation one ($\mathbb{E}$) as
follows:††footnotemark:
$\displaystyle=\min_{\beta_{\tau:H-1}^{2}}\mathbb{E}_{\theta^{1}_{\tau}\sim\sigma^{m,1}_{\tau}}\underbrace{\left\\{\max_{\beta_{\tau:H-1}^{1}}\mathbb{E}_{\theta^{2}_{\tau}\sim\sigma_{\tau}^{c,1}(\theta^{1})}\left[\sum_{t=\tau}^{H-1}\gamma^{t-\tau}r(S_{t},A_{t}^{1},A_{t}^{2})\mid\beta_{\tau:H-1}^{1},\beta_{\tau:H-1}^{2}\right]\right\\}}_{\text{best-
response of $1$ to $\beta_{\tau:}^{2}$ under $\theta_{\tau}^{1}$}}$ and,
recognizing the components of vector
$\nu^{2}_{[\sigma_{\tau}^{c,1},\beta_{\tau:H-1}^{2}]}$ and writing the
expectation over aohs $\theta_{\tau:}^{1}$ as a scalar product:
$\displaystyle=\min_{\beta_{\tau:H-1}^{2}}\left[\sigma_{\tau}^{m,1}\cdot\nu^{2}_{[\sigma_{\tau}^{c,1},\beta_{\tau:H-1}^{2}]}\right].$

∎

††footnotetext: Note that this property is well known in Bayesian games, where
aohs correspond to types, cf. [HarsanyiBG-II-ms68, Th. 1, p. 321].

An important observation that ensues from this theorem is that $V^{*}_{\tau}$
is concave in $\sigma_{\tau}^{m,1}$ and convex in $\sigma_{\tau}^{m,2}$. In
practice, however, such continuity properties alone only allow upper-bounding
$V^{*}_{\tau}$ for finitely many conditional terms $\sigma^{c,i}_{\tau}$, thus
not for the whole occupancy space, as required to enable DP and HS in our
game.

In the following, we complement WigOliRoi-corr16’s results with properties of
$V^{*}$ in subgames, plus continuity properties that help designing bounding
approximators, which will lead us to an HSVI-like solver.

##### Note:

To help the reader, Appendix A provides two synthetic tables: Table 3 (p. 3)
to sum up various theoretical properties that are stated in this paper
(assuming a finite temporal horizon), and Table 4 (p. 4) to sum up the
notations used in this paper, including some that are used only in the
appendix.

Also, for convenience, we may replace in the following: (i) subscript
“$\tau:H-1$” with “$\tau:$”, (ii) any function $f({\boldsymbol{x}})$ linear in
vector ${\boldsymbol{x}}$ with either $f(\cdot)\cdot{\boldsymbol{x}}$ or
${{\boldsymbol{x}}}^{\top}\\!\cdot f(\cdot)$, (iii) a full tuple with its few
elements of interest, and (iv) an element (a "field") $x$ of a specific tuple
$t$ by $x[t]$.

##  3 Theoretical Contributions

In this section, we demonstrate how to implement dynamic programming and
heuristic search by (1) rigorously showing that Bellman optimality equation
(Section 3.1) holds, (2) deriving bounding approximators of two novel optimal
value functions, which come with solution strategies (Section 3.2), and (3)
proposing a variant of HSVI that computes (in finite time) a player’s strategy
whose value is within $\epsilon$ of the zs-POSG’s NEV (Section 3.3).

###  3.1 The Optimal Value Function $V^{*}$
and its Recursive Expression

Let us first recall that, contrary to WigOliRoi-corr16 [WigOliRoi-corr16,
Section 5, Lemma 4], we do not make the strong assumption that past decision
rules can be considered as public (and, thus, we do not assume that any player
knows $\sigma_{\tau}$). Indeed, while it is valid in Dec-POMDPs because the
players are willing to coordinate their behaviors, it is a priori not valid in
zs-POSGs, since players are, in the contrary, willing to deceive one another.
Safety issues as presented in Example 1 illustrate the possible flaws of such
an assumption.

We now discuss the existence of an optimal value function $V_{\tau}^{*}$ and
its properties. These results are implicitly used by WigOliRoi-corr16, but it
seems important to state and demonstrate them. A first step is to demonstrate
that Neu-ma28’s minimax theorem [Neu-ma28] applies when in $\sigma_{\tau}$,
thus justifying the definition of the optimal (Nash equilibrium) value of a
subgame.

[Minimax theorem – Proof in Section C.1.2] theoremthUnicityNev (originally
stated on page 3.1) The subgame defined in Equation 6 admits a unique NEV

$\displaystyle V_{\tau}^{*}(\sigma_{\tau})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\max_{\beta_{\tau:H-1}^{1}}\min_{\beta_{\tau:H-1}^{2}}V_{\tau}(\sigma_{\tau},\beta_{\tau:H-1}^{1},\beta_{\tau:H-1}^{2}).$
(7)

$V(\sigma_{\tau},\cdot,\cdot)$ not being bilinear in the space of behavioral
strategies (Section C.1.1), the proof requires reasoning with mixed strategies
(for which the bilinearity holds), i.e., distributions over pure
(deterministic) strategies defined over all time steps. Yet, when in a
subgame, we have to reason only on mixed strategies compatible with the
associated occupancy state $\sigma_{\tau}$ (i.e., which ensure that the os at
$\tau$ is $\sigma_{\tau}$), one step being to extend Kuhn-ctg50’s equivalence
results between behavioral and mixed strategies [Kuhn-ctg50] to the subgames.

Then, defining the optimal action-value function:

$\displaystyle Q^{*}_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma
V^{*}_{\tau+1}(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})),$ (8)

we can now prove that a Bellman optimality equation exists, which justifies
reasoning on subgames despite the non-observability.

[Bellman optimality equation – Proof in Section C.1.2] theorembellmanPpe
(originally stated on page 3.1) $V_{\tau}^{*}(\sigma_{\tau})$ satisfies the
following functional equation:

$\displaystyle V_{\tau}^{*}(\sigma_{\tau})$
$\displaystyle=\max_{\beta_{\tau}^{1}}\min_{\beta_{\tau}^{2}}r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma
V^{*}_{\tau+1}(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}))=\max_{\beta_{\tau}^{1}}\min_{\beta_{\tau}^{2}}Q^{*}_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}).$

The proof requires decomposing min and max operators over different time steps
before swapping them appropriately to end up recognizing the optimal value
function at the next time step ($V^{*}_{\tau+1}$).

Sections 3.1 and 3.1 together show that Theorem 2.4 holds even without
player’s strategies being public so that we can now build on the convex-
concave property to solve zs-oMGs.

###  3.2 Towards Solving zs-OMGs

This section aims at providing the second tool for DP and HS with continuous
state spaces, i.e., bounding approximators of optimal value functions which
will allow generalization across occupancy space. Their update and selection
operators are written as linear programs, and they turn out to come with
solution strategies.

####  3.2.1 Bounding value functions

So far, several issues prevented to apply the HSVI scheme to zs-POSGs,
starting with the continuous spaces of 1\. occupancy states (zs-OMG states)
and 2\. decision rules (zs-OMG actions). One can address (1) by introducing
the bounding functions $\overline{V}_{\tau}(\sigma_{\tau})$ and
$\underline{V}_{\tau}(\sigma_{\tau})$ of $V_{\tau}^{*}(\sigma_{\tau})$ (cf.
Section D.2), for instance:

$\displaystyle\overline{V}_{\tau}(\sigma_{\tau})$
$\displaystyle=\min_{\langle\tilde{\sigma}_{\tau}^{c,1},\langle\overline{\nu}^{2}_{\tau},\beta_{\tau:}^{2}\rangle\rangle\in\overline{{\mathcal{}J}}_{\tau}}\left[\sigma_{\tau}^{m,1}\cdot\overline{\nu}^{2}_{\tau}+\lambda_{\tau}\lVert\sigma_{\tau}-\sigma_{\tau}^{m,1}\tilde{\sigma}_{\tau}^{c,1}\rVert_{1}\right],$

where $\overline{\nu}^{2}_{\tau}$ component-wise upper-bounds
$\nu^{2}_{[\tilde{\sigma}^{c,1}_{\tau},\beta_{\tau:}^{2}]}$ for some
$\beta_{\tau:}^{2}$. They allow generalizing knowledge from the subgame rooted
at $\sigma_{\tau}$ to any other one rooted at $\tilde{\sigma}_{\tau}$. To do
so, we use $V^{*}$’s Lipschitz-Continuity proven below.

[Lipschitz-Continuity of $V^{*}$ \- proof in Section D.1.3]theoremcorVLCOcc
(originally stated on page 3.1) Let
$h_{\tau}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\frac{1-\gamma^{H-\tau}}{1-\gamma}$ (or
$h_{\tau}\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}H-\tau$ if
$\gamma=1$). Then $V^{*}_{\tau}(\sigma_{\tau})$ is $\lambda_{\tau}$-Lipschitz
continuous in $\sigma_{\tau}$ at any depth
$\tau\in\\{0\mathinner{\ldotp\ldotp}H-1\\}$, where
$\lambda_{\tau}=\frac{1}{2}h_{\tau}\left(r_{\max}-r_{\min}\right)$.

Yet, this yields (generally non-convex) Lipschitz-continuous functions whose
$\max$-$\min$ optimization would be intractable, so that (2) remains an issue.
Also, we do not know how to retrieve valid solution strategies. In particular,
and as illustrated in Example 1, simply concatenating decision rules backwards
from $\tau=H-1$ to $0$ would not guarantee globally-consistent solutions, and
could result in exploitable strategies.

But then, combining Sections 3.1 and 2.4 leads to introducing a novel value
function (denoted $W^{1,*}_{\tau}$) through writing, for any os
$\sigma_{\tau}$:

$\displaystyle V_{\tau}^{*}(\sigma_{\tau})$
$\displaystyle=\max_{\beta_{\tau}^{1}}\underbrace{\min_{\beta_{\tau:H-1}^{2}\in{\mathcal{}B}_{\tau}^{2}}\left[r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma\sigma_{\tau+1}^{m,1}\cdot\nu_{[\sigma_{\tau+1}^{c,1},\beta_{\tau+1:H-1}^{2}]}^{2}\right]}_{\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}W^{1,*}_{\tau}(\sigma_{\tau},\beta^{1}_{\tau})}.$

Assuming that player $2$ can only respond with one of finitely many stored
strategies, the concavity and $\lambda_{\tau}$-Lipschitz-continuity of
$W^{1,*}_{\tau}$ allow upper-bounding it with finitely many tuples
$w=\langle\tilde{\sigma}_{\tau},\beta_{\tau}^{2},\langle\overline{\nu}_{\tau+1}^{2},\beta_{\tau+1:}^{2}\rangle\rangle$
stored in sets $\overline{{\mathcal{}I}}_{\tau}$, and where
$\overline{\nu}_{\tau+1}^{2}$ upper-bounds
$\nu^{2}_{[\tilde{\sigma}_{\tau+1}^{c,1},\beta_{\tau+1:}^{2}]}$.

[proof in Section D.2.2]propositioncoreThUpperBounds (originally stated on
page 3.2.1) Let $\overline{{\mathcal{}I}}_{\tau}$ be a set of tuples
$w=\langle\tilde{\sigma}_{\tau},\beta_{\tau}^{2},\langle\overline{\nu}_{\tau+1}^{2},\beta_{\tau+1:}^{2}\rangle\rangle$.
Then,

$\displaystyle\overline{W}_{\tau}(\sigma_{\tau},\beta_{\tau}^{1})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\min_{\langle\tilde{\sigma}_{\tau},\beta_{\tau}^{2},\langle\overline{\nu}_{\tau+1}^{2},\beta_{\tau+1:}^{2}\rangle\rangle\in\overline{{\mathcal{}I}}_{\tau}}\left[r(\sigma_{\tau},\beta_{\tau}^{1},\beta^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\beta_{\tau}^{1},\beta^{2}_{\tau})\cdot\overline{\nu}^{2}_{\tau+1}\right.$
(9) $\displaystyle\qquad\left.+\lambda_{\tau+1}\lVert
T(\sigma_{\tau},\beta_{\tau}^{1},\beta^{2}_{\tau})-T^{1}_{m}(\sigma_{\tau},\beta_{\tau}^{1},\beta^{2}_{\tau})T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\beta^{2}_{\tau})\rVert_{1}\right]$
(10)

upper-bounds $W_{\tau}^{1,*}$ over the whole space
${\mathcal{}O}^{\sigma}_{\tau}\times{\mathcal{}B}_{\tau}^{1}$.

Symmetrically, we define $\underline{W}_{\tau}$ as the lower bound of the
symmetrically defined $W_{\tau}^{2,*}$. As explained in the next two sections,
$\overline{W}_{\tau}$ will be easier to deal with compared to
$\overline{V}_{\tau}$, allowing 1 to seek for decision rules optimistically,
and providing valid solution strategies for 2 for the subgame at $\tau$, i.e.,
ignoring consistency with higher-level subgames.

####  3.2.2 Action Selection and Backup Operators

We now detail the decision rule selection for $1$ using $\overline{W}_{\tau}$
to optimistically guide a trajectory in occupancy space, and how to update
$\overline{W}_{\tau}$ by providing backup operations.

To that end, first note that linearities in $\beta^{1}_{\tau}$ within Equation
10 allow writing
$\overline{W}_{\tau}(\sigma_{\tau},\beta^{1}_{\tau})=\min_{\begin{subarray}{c}w\in\overline{{\mathcal{}I}}_{\tau}\end{subarray}}{\beta^{1}_{\tau}}^{\top}\cdot
M^{\sigma_{\tau}}_{(\cdot,w)}$, where $\beta^{1}_{\tau}$ and
$M^{\sigma_{\tau}}_{(\cdot,w)}$ (for each $w$) are column vectors of dimension
$\lvert\Theta^{1}\times{\mathcal{}A}^{1}\rvert$. $M^{\sigma_{\tau}}$ (see
developed formula in Section D.3.1) is thus a
$|\Theta_{\tau}^{1}\times{\mathcal{}A}^{1}|\times|\overline{{\mathcal{}I}}_{\tau}|$
matrix. Then, $\overline{W}_{\tau}$ being a lower envelope of hyperplanes
leads to a convenient way of computing
$\max_{\beta_{\tau}^{1}}\overline{W}_{\tau}(\sigma_{\tau},\beta_{\tau}^{1})$.

[Proof in Section D.3.1]propositioncore|lpth For any given $\sigma_{\tau}$ and
any set $\overline{{\mathcal{}I}}_{\tau}$ of tuples
$w=\langle\tilde{\sigma}_{\tau},\beta_{\tau}^{2},\langle\overline{\nu}_{\tau+1}^{2},\beta_{\tau+1:}^{2}\rangle\rangle$,
$\max_{\beta_{\tau}^{1}}\overline{W}_{\tau}(\sigma_{\tau},\beta_{\tau}^{1})$
is equivalent to the LP and dual LP:

$\displaystyle\begin{array}[]{ll@{\
}llllll}\textsc{lp}\overline{W}_{\tau}(\sigma_{\tau})\
:&\displaystyle\max_{\beta_{\tau}^{1},v}&v&\text{s.t.}&\text{(i)}&\forall
w\in\overline{{\mathcal{}I}}_{\tau},&v\leq{\beta_{\tau}^{1}}^{\top}\\!\cdot
M^{\sigma_{\tau}}_{(\cdot,w)}&\text{and}\\\
&&&&\text{(ii)}&\forall\theta_{\tau}^{1}\in\Theta_{\tau}^{1},&{\displaystyle\sum_{a^{1}}}\beta_{\tau}^{1}(a^{1}|\theta_{\tau}^{1})=1,\\\
\\\ \textsc{dlp}\overline{W}_{\tau}(\sigma_{\tau})\
:&\displaystyle\min_{\psi^{2}_{\tau},v}&v&\text{ s.t.}&\text{(i)
}&\forall(\theta^{1}_{\tau},a^{1}),&v\geq
M^{\sigma_{\tau}}_{((\theta^{1}_{\tau},a^{1}),\cdot)}\cdot\psi^{2}_{\tau}&\text{and}\\\
&&&&\text{(ii)}&&{\displaystyle\sum_{w\in\overline{{\mathcal{}I}}_{\tau}}}\\!\psi^{2}_{\tau}(w)=1.\end{array}$
(16)

######  Remark 3.1 (Outcomes of this game).

Since $\overline{W}_{\tau}$ upper-bounds $W^{1,*}_{\tau}$, solving this LP
provides $1$ with an optimistically selected immediate decision rule
$\beta^{1}_{\tau}$. For $2$, $\psi_{\tau}^{2}$ is a probability distribution
over tuples containing strategies
$\beta_{\tau}^{2}\oplus\beta_{\tau+1:H-1}^{2}$, thus recursively induces a
strategy, as illustrated by Figure 3, which can be turned into a behavioral
strategy $\beta_{\tau:H-1}^{2}$ (more details in Section D.3.3) whose value is
at worst (from $2$’s viewpoint) the LP’s value, i.e., against $1$’s best
response to it.

$b_{0}$$\cdots$ $--$ $1/3$$2/3$$0$$\cdots$ $--$$0$$1$$2/3$$1/2$$1/2$$\cdots$
$1/2$$1/2$$1/2$$1/2$$\langle\emptyset,\delta_{0:}^{i}\rangle$$\langle\beta_{1}^{i},\delta_{1:}^{i}\rangle$$\langle\beta_{2}^{i},\delta_{2:}^{i}\rangle$$\langle\beta_{3}^{i},\emptyset\rangle$

Figure 3:  Representation of the strategy recursively induced by some
$\psi_{0}^{1}$. At each time step $\tau$, one must (i) sample a next
tuple/node $w_{\tau}^{1}$ from current distribution $\psi_{\tau}^{1}$, (ii)
apply dr $\beta_{\tau}^{1}[w_{\tau}^{1}]$, and (iii) make
$\psi_{\tau+1}^{1}[w_{\tau}^{1}]$ the new current distribution (unless
reaching a leaf).

Then, the following properties allow performing backups, i.e., filling up the
set $\overline{{\mathcal{}I}}_{\tau-1}$ with new tuples $w$ containing, in
particular, vectors $\overline{\nu}_{\tau}^{2}$.

[Proof in Section D.3.2]lemmacore|propBackup For any
$\psi_{\tau}^{2}=\textsc{dlp}\overline{W}_{\tau}(\sigma_{\tau})$, the vector
$\nu_{[\sigma_{\tau}^{c,1},\psi_{\tau}^{2}]}^{2}$ is component-wise upper-
bounded by

$\displaystyle\overline{\nu}_{\tau}^{2}$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\frac{1}{\sigma_{\tau}^{m,1}}M^{\sigma_{\tau}}_{((\theta^{1}_{\tau},a^{1}),\cdot)}\cdot\psi^{2}_{\tau}.$

######  Proposition 3.2 (update).

Let us assume that

  * •

a transition $\sigma_{\tau-1}\to\sigma_{\tau}$ has been performed through
playing $\langle\beta_{\tau-1}^{1},\beta_{\tau-1}^{2}\rangle$, and

  * •

solving $\textsc{dlp}\overline{W}_{\tau}(\sigma_{\tau})$ provides both

    * –

a tree strategy $\psi_{\tau}^{2}$ (as the main solution of the DLP), and

    * –

a vector
$\overline{\nu}_{\tau}^{2}=\frac{1}{\sigma_{\tau}^{m,1}}M^{\sigma_{\tau}}_{((\theta^{1}_{\tau},a^{1}),\cdot)}\cdot\psi^{2}_{\tau}$
(as a by-product).

Then,

  1. 1.

$\overline{{\mathcal{}I}}_{\tau-1}\leftarrow\overline{{\mathcal{}I}}_{\tau-1}\cup\\{\langle\sigma_{\tau-1}^{c,1},\beta_{\tau-1}^{2},\langle\overline{\nu}^{2}_{\tau},\psi_{\tau}^{2}\rangle\rangle\\}$
is a valid update operator in the sense that it preserves
$\overline{W}_{\tau}$’s upper-bounding property, and

  2. 2.

similarly,
$\overline{{\mathcal{}J}}_{\tau}\leftarrow\overline{{\mathcal{}J}}_{\tau}\cup\\{\langle\sigma_{\tau}^{c,1},\langle\overline{\nu}_{\tau}^{2},\psi_{\tau}^{2}\rangle\rangle\\}$
is a valid update operator for $\overline{V}_{\tau}$.

####  3.2.3 Initialization

To initialize the bounds $\overline{W}_{\tau}$ and $\overline{V}_{\tau}$ for
any time step, we begin by generating a trajectory in a forward phase. At each
time step, a uniform decision rule is picked for both players to derive a
sequence of occupancy states $\sigma_{0},\dots,\sigma_{H-1}$. Then, during a
backward phase, for each time step $\tau=H-1,\dots,1$, we create a tuple
$w_{\tau-1,init}=\langle\sigma_{\tau-1}^{c,1},\beta_{\tau-1}^{2},\langle\overline{\nu}_{\tau}^{2},\psi_{\tau}^{2}\rangle\rangle$,
where

  * •

$\sigma_{\tau-1}^{c,1}$ is the conditional term associated to
$\sigma_{\tau-1}$;

  * •

$\beta_{\tau-1}^{2}$ is a uniform decision rule;

  * •

$\psi_{\tau}^{2}$ is

    * –

a degenerate distribution over the only next tuple $w_{\tau+1}$ if $\tau<H-1$
(which induces a concatenation of uniform decision rules for all future time
steps);

    * –

undefined if $\tau=H-1$;

and

  * •

$\overline{\nu}_{\tau}^{2}(\theta_{\tau}^{1})=r_{max}\cdot(H-\tau)$ for any
history $\theta_{\tau}^{1}$ that player $1$ could face.

Tuples $w_{\tau-1,init}$ are added to sets
$\overline{{\mathcal{}I}}_{\tau-1}$. For any time step $\tau\geq 0$, we
similarly create tuples
$\langle\sigma_{\tau}^{c,1},\langle\overline{\nu}_{\tau}^{2},\psi_{\tau:}^{2}\rangle\rangle$
and add them to sets $\overline{{\mathcal{}J}}_{\tau}$. The lower bounds are
initialized symmetrically.

We now show that occupancy states can also be prescriptive, allowing one to
retrieve an $\epsilon$-NES for the subgame at occupancy state $\sigma_{\tau}$
once the bounds are withing $\epsilon$ from each other, in particular at
$\tau=0$.

####  3.2.4 Extracting a NES

Vectors $\overline{\nu}^{2}_{0}$ upper bounding the value of their associated
strategies, the following result tells when and how to extract an
$\epsilon$-optimal solution strategy for this player.

[]theoremthInclusionWandV (originally stated on page 3.2.4) If sets
$\overline{\mathcal{J}}_{0}$ and $\underline{\mathcal{J}}_{0}$ are such that
$\overline{V}_{0}(\sigma_{0})-\underline{V}_{0}(\sigma_{0})\leq\epsilon,$ then
$\operatorname*{arg\,max}_{\underline{w}\in\underline{\mathcal{J}}_{0}}\underline{\nu}^{2}_{0}$
and
$\operatorname*{arg\,min}_{\overline{w}\in\overline{\mathcal{J}}_{0}}\overline{\nu}^{2}_{0}$
respectively provide strategies $\psi_{0}^{1}$ and $\psi_{0}^{2}$ that form an
$\epsilon$-NES of the zs-POSG.

###### Proof.

First, let us notice that, at $\tau=0$, the occupancy-state space is reduced
to a singleton, $\\{\sigma_{0}=\langle 1\rangle\\}$, because of the single
(empty) joint aoh. The value vectors $\nu$ are thus one-dimensional, and here
considered as scalar numbers.

Let us assume that sets $\overline{\mathcal{J}}_{0}$ and
$\underline{\mathcal{J}}_{0}$ are such that

$\displaystyle\overline{V}_{0}(\sigma_{0})-\underline{V}_{0}(\sigma_{0})$
$\displaystyle\leq\epsilon,$

and let
$\underline{w}^{*}=\langle\sigma_{0}^{c,1},\langle\underline{\nu}_{0}^{*},\psi_{0}^{1,*}\rangle\rangle$
and
$\overline{w}^{*}=\langle\sigma_{0}^{c,1}\langle\overline{\nu}_{0}^{*},\psi_{0}^{2,*}\rangle\rangle$
be the tuples returned by
$\operatorname*{arg\,max}_{\underline{w}\in\underline{{\mathcal{}J}}_{0}}\underline{\nu}_{0}^{2}$
and
$\operatorname*{arg\,min}_{\overline{w}\in\overline{{\mathcal{}J}}_{0}}\overline{\nu}_{0}^{1}$.
Then, noting that $\sigma_{0}=\langle 1\rangle$,

$\displaystyle\nu^{1}_{[\sigma_{0}^{c,2},\psi_{0}^{1,*}]}-\nu^{2}_{[\sigma_{0}^{c,1},\psi_{0}^{2,*}]}$
$\displaystyle\leq\overline{\nu}_{0}^{*}-\underline{\nu}_{0}^{*}$
$\displaystyle=\max_{\underline{w}\in\underline{{\mathcal{}J}}_{0}}\underline{\nu}_{0}^{2}-\min_{\overline{w}\in\overline{{\mathcal{}J}}_{0}}\overline{\nu}_{0}^{1}$
$\displaystyle=\overline{V}_{0}(\sigma_{0})-\underline{V}_{0}(\sigma_{0})$
$\displaystyle\leq\epsilon.$

Thus, $\psi_{0}^{1}$ and $\psi_{0}^{2}$ are two strategies whose security
levels (values against best-responding opponents) are $\epsilon$-close, and
thus form an $\epsilon$-NES of the zs-POSG. ∎

Note: This result can be generalized to any $\sigma_{\tau}$ at later time
steps, but this generalization is not used in practice.

Distributions $\psi_{0}^{2}$ are stored and could be executed as is. Section
D.3.3 still presents a conversion process to retrieve a behavioral strategy
$\beta_{0:H-1}^{2}$ from a distribution $\psi_{0}^{2}$ over tuples
$w\in\overline{{\mathcal{}I}}_{0}$. Next, we see how to design a practical
HSVI-based algorithm that provably returns sets $\overline{{\mathcal{}J}}_{0}$
and $\underline{{\mathcal{}J}}_{0}$ satisfying Section 3.2.4 after finitely
many iterations.

###  3.3 HSVI for zs-POSGs

This section details our adaptation of the general HSVI scheme for
$\epsilon$-optimally solving zs-POSGs, and presents a theoretical finite-time
convergence property.

####  3.3.1 Algorithm

HSVI for zs-POSGs is described in Algorithm 1. As vanilla HSVI, it relies on
(i) generating trajectories while acting optimistically (lines 1+1), i.e.,
player $1$ (resp. $2$) acting “greedily” w.r.t. $\overline{W}_{\tau}$ (resp.
$\underline{W}_{\tau}$), and (ii) locally updating the upper and lower bounds
(lines 1+1). Both phases rely on solving the same games described by LP (16).
At $\tau=H-1$, algorithm 1 selects drs by solving an exact game, and algorithm
1 returns a distribution reduced to the single element added in algorithm 1.

A key difference with SmiSim-uai05’s HSVI algorithm [SmiSim-uai05] lies in the
criterion for stopping trajectories. The branching factor for zs-oMGs being
infinite, we make use of $V^{*}$’s Lipschitz-continuity to implement the same
adaptations as HorBosPec-aaai17 used for zs-OS-POSGs. The Lipschitz-continuity
allows controlling the variations of the value function within small balls of
radius $\rho$ around a previously visited occupancy-state. A finite number of
such balls is sufficient to cover the whole space. Then, Section 3.3.2 (below)
ensures $\epsilon$-optimality in finite time if stopping trajectories when
$\overline{V}_{\tau}(\sigma_{\tau})-\underline{V}_{\tau}(\sigma_{\tau})\leq
thr(\tau)$, with the threshold function
$thr(\tau)\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\gamma^{-\tau}\epsilon-\sum_{i=1}^{\tau}2\rho\lambda_{\tau-i}\gamma^{-i}$.

1

2Fct  _zs-oMG-HSVI(_$b_{0}\simeq\sigma_{0}$_)_

3 foreach  _$\tau\in 0\mathinner{\ldotp\ldotp}H-1$_ do

4 Initialize $\overline{V}_{\tau}$, $\underline{V}_{\tau}$,
$\overline{W}_{\tau}$, & $\underline{W}_{\tau}$

5 while  _
$\left[\overline{V}_{0}(\sigma_{0})-\underline{V}_{0}(\sigma_{0})>thr(0)\right]$
_ do

6 Explore(_$\sigma_{0},0,-,-$_)

7 return
_$\operatorname*{arg\,max}_{w_{0}\in\underline{\mathcal{J}}_{0}}\underline{\nu}^{1}_{0}$_

8

9

10Fct
_Explore(_$\sigma_{\tau},\tau,\sigma_{\tau-1},{\boldsymbol{\beta}}_{\tau-1}$_)_

11 if
_$\left[\overline{V}_{\tau}(\sigma_{\tau})-\underline{V}_{\tau}(\sigma_{\tau})
>thr(\tau)\right]$ _ then

12 if  _$\tau <H-1$_ then

13
$\overline{\beta}_{\tau}^{1}\leftarrow\textsc{lp}\overline{W}_{\tau}(\sigma)$

14
$\underline{\beta}_{\tau}^{2}\leftarrow\textsc{lp}\underline{W}_{\tau}(\sigma)$

15
Explore(_$T(\sigma_{\tau},\overline{\beta}_{\tau}^{1},\underline{\beta}_{\tau}^{2}),\tau+1,\sigma_{\tau},\langle\overline{\beta}^{1}_{\tau},\underline{\beta}^{2}_{\tau}\rangle$_)

16 else ($\tau=H-1$)

17 $(\overline{\beta}_{\tau}^{1},\underline{\beta}^{2}_{\tau})\leftarrow
NES\left(r(\sigma,\beta^{1}_{\tau},\beta^{2}_{\tau})\right)$

18

19
$\overline{{\mathcal{}I}}^{1}_{\tau}\leftarrow\overline{{\mathcal{}I}}^{1}_{\tau}\cup\\{\langle{\sigma^{c,1}_{\tau},\underline{\beta}^{2}_{\tau},-}\rangle\\}$

20

21
$\underline{{\mathcal{}I}}^{2}_{\tau}\leftarrow\underline{{\mathcal{}I}}^{2}_{\tau}\cup\\{\langle{\sigma^{c,2}_{\tau},\overline{\beta}^{1}_{\tau},-}\rangle\\}$

22 $\textnormal{{$\overline{\text{\bf
Update}}$}}({\overline{W}_{\tau-1},\langle\sigma_{\tau},\sigma^{c,1}_{\tau-1},\underline{\beta}^{2}_{\tau-1}\rangle})$

23

24 $\textnormal{{$\underline{\text{\bf
Update}}$}}({\underline{W}_{\tau-1},\langle\sigma_{\tau},\sigma^{c,2}_{\tau-1},\overline{\beta}^{1}_{\tau-1}\rangle})$

25

26

27

28

29Fct  _$\overline{\text{\bf
Update}}$(_$\overline{W}_{\tau-1},\langle{\sigma_{\tau},\sigma^{c,1}_{\tau-1},\overline{\beta}^{2}_{\tau-1}}\rangle$
_) _

30
$\langle\overline{\nu}^{2}_{\tau},\psi_{\tau}^{2}\rangle\leftarrow\textsc{dlp}\overline{W}_{\tau}(\sigma_{\tau},)$

31
$\overline{{\mathcal{}I}}_{\tau-1}\leftarrow\overline{{\mathcal{}I}}_{\tau-1}\cup\\{\langle{\sigma^{c,1}_{\tau-1},\underline{\beta}^{2}_{\tau-1},\langle\overline{\nu}^{2}_{\tau},\psi^{2}_{\tau}\rangle}\rangle\\}$

32
$\overline{\mathcal{J}}_{\tau}\leftarrow\overline{\mathcal{J}}_{\tau}\cup\\{\langle{\sigma_{\tau}^{c,1},\langle\overline{\nu}^{2}_{\tau},\psi_{\tau}^{2}\rangle}\rangle\\}$

33

Algorithm 1 zs-oMG-HSVI($b_{0},[\epsilon,\rho]$)
[here returning a tuple $w_{0}$ containing a solution strategy
$\underline{\psi}^{1}_{0}$ for player $1$]

##### Setting $\rho$

As can be observed, this threshold function should always return positive
values, which requires a small enough (but $>0$) $\rho$. For a given problem
(cf. Section E.1.1, Section E.1.1), the maximum possible value $\rho_{\max}$
depends on the Lipschitz constants at each time step, which themselves depend
on the initial upper and lower bounds of the optimal value function. Setting
$\rho\in(0,\rho_{\max})$ means making a trade-off between generating many
trajectories (small $\rho$) and long ones (large $\rho$).

####  3.3.2 Finite-Time Convergence

[Proof in Section E.2.1]theoremthmTermination (originally stated on page
3.3.2) zs-oMG-HSVI (Algorithm 1) terminates in finite time with an
$\epsilon$-approximation of $V^{*}_{0}(\sigma_{0})$ that statisfies Section
3.2.4.

The finite time complexity suffers from the same combinatorial explosion as
for Dec-POMDPs, and is even worse as we have to handle “infinitely branching”
trees of possible futures. More precisely, the bound on the number of
iterations depends on the number of balls of radius $\rho$ required to cover
occupancy simplexes at each depth.

Also, the following proposition allows solving infinite horizon problems as
well (when $\gamma<1$) by bounding the length of HSVI’s trajectories using the
boundedness of $\overline{V}-\underline{V}$ and the exponential growth of
$thr(\tau)$.

[Proof in Section E.2.2]propositionlemFiniteTrials (originally stated on page
3.3.2) When $\gamma<1$, the length of trajectories is upper bounded by
$T_{\max}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\left\lceil\log_{\gamma}\frac{\epsilon-\frac{2\rho\lambda^{\infty}}{1-\gamma}}{W-\frac{2\rho\lambda^{\infty}}{1-\gamma}}\right\rceil$,
where $\lambda^{\infty}$ is a depth-independent Lipschitz constant and
$W\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\lVert\overline{V}^{(0)}-\underline{V}^{(0)}\rVert_{\infty}$ is
the maximum width between initializations.

##  4 Experiments

Experiments presented in this section aim at validating the proposed approach
and comparing its behavior to the behavior of some reference algorithms.

###  4.1 Setup

#### Benchmark Problems

Five benchmark problems were used. Adversarial Tiger and Competitive Tiger
were introduced by Wiggers-msc15. Mabc and Recycling Robot are well-known Dec-
POMDP benchmark problems (cf. http://masplan.org) and were adapted to our
competitive setting by making player $2$ minimize (rather than maximize) the
objective function. The fifth benchmark is the adaptation of the well-known
Matching Pennies game detailed in Example 1, with a small difference in that
$r(s_{h},\cdot,a_{h})=+2$ instead of $+1$; this change breaks the symmetry in
the optimal strategy, so that HSVI can not find the NES by "chance" by trying
uniform strategies. We only consider finite horizons $H$ and $\gamma=1$. Table
1 gives the cardinal of the state, action and observation sets for each of
these problems.

Table 1: Number of states/actions/observations for each benchmark problem | $\mathcal{S}$ | $\mathcal{A}^{1}$ | $\mathcal{A}^{2}$ | $\mathcal{O}^{1}$ | $\mathcal{O}^{2}$
---|---|---|---|---|---
Competitive Tiger | 2 | 4 | 4 | 3 | 3
Adversarial Tiger | 2 | 3 | 2 | 2 | 2
Recycling Robot | 4 | 3 | 3 | 2 | 2
Mabc | 4 | 2 | 2 | 2 | 2
Matching Pennies | 3 | 2 | 2 | 1 | 1

#### Algorithms

For conciseness, Algorithm 1 is here denoted HSVI, and compared against Random
search and Informed search Wiggers-msc15 (both using Wiggers-msc15’s
implementation (unlicensed and unreleased)), SFLP [KolMegSte-geb96], and CFR+
Tammelin-arxiv14 (both using open_spiel [LanctotEtAl2019OpenSpiel] (Apache
license)).

All algorithms (but SFLP, which is exact) used a target error $\epsilon=1$% of
the initial gap $H\cdot(r_{\max}-r_{\min})$. HSVI ran with
$\lambda_{\tau}=(H-\tau)\cdot(r_{\max}-r_{\min})$, and $\rho$ the middle of
its feasible interval. We also use FB-HSVI’s LPE lossless compression of
probabilistically equivalent action-observation histories in occupancy states,
so as to reduce their dimensionality [DibAmaBufCha-jair16]. Experiments ran on
an Ubuntu machine with i7-10810U 1.10 GHz Intel processor and 16 GB available
RAM, and the code is available under MIT license at
https://gitlab.com/aureliendelage1/hsviforzsposgs.

Random and Informed, only ran once, providing fairly representative results.

###  4.2 Results

##### Performance Measures

A common performance measure in 2-player zero-sum games is the exploitability
of a strategy $\beta^{i}_{0:}$, i.e., the difference between the strategy’s
security level (the value of $\neg i$’s best response to $\beta^{i}_{0:}$) and
the Nash equilibrium value $V^{*}_{0}(\sigma_{0})$:

$\displaystyle\text{exploitability}(\beta^{i}_{0:})$ $\displaystyle=\lvert
V^{*}(\sigma_{0})-\sigma^{m,1}_{0}\cdot\nu^{i}_{[\sigma^{c,\neg
i}_{0},\beta^{i}_{0:}]}\rvert$ $\displaystyle=\lvert
V^{*}(\sigma_{0})-\nu^{i}_{[\sigma^{c,\neg i}_{0},\beta^{i}_{0:}]}\rvert,$

noting that $\sigma_{0}$ is a degenerate distribution over a single element,
the pair of empty action-observation histories. In our setting, it will be
convenient to look at the (average) exploitability of a strategy profile
$\langle\beta_{0:}^{1},\beta_{0:}^{2}\rangle$:

$\displaystyle\text{exploitability}(\beta_{0:}^{1},\beta_{0:}^{2})$
$\displaystyle=\frac{(V^{*}(\sigma_{0})-\nu^{1}_{[\sigma^{c,2}_{0},\beta^{1}_{0:}]})+(\nu^{2}_{[\sigma^{c,1}_{0},\beta^{2}_{0:}]}-V^{*}(\sigma_{0}))}{2}$
$\displaystyle=\frac{\nu^{2}_{[\sigma^{c,1}_{0},\beta^{2}_{0:}]}-\nu^{1}_{[\sigma^{c,2}_{0},\beta^{1}_{0:}]}}{2}.$

This quantity is a more concise statistic than both individual
exploitabilities, and can be obtained by solving two POMDPs (fixing one
player’s strategy or the other) without requiring to know the actual NEV.

This exploitability can also be defined as half of the gap between security
levels (SL-gap). To analyze the convergence of algorithms with respect to the
initial gap, we will look at the SL-gap percentage, i.e.,

$\displaystyle\text{SL-gap percentage}(\beta_{0:}^{1},\beta_{0:}^{2})$
$\displaystyle=\frac{\nu^{2}_{[\sigma^{c,1}_{0},\beta^{2}_{0:}]}-\nu^{1}_{[\sigma^{c,2}_{0},\beta^{1}_{0:}]}}{H\cdot(R_{\max}-R_{\min})}$
$\displaystyle=\frac{2\cdot\text{exploitability}(\beta_{0:}^{1},\beta_{0:}^{2})}{H\cdot(R_{\max}-R_{\min})}.$

####  4.2.1 Comparison with the state of the art

Table 2 gives the convergence time of Wiggers-msc15’s two heuristic
algorithms, CFR+, SFLP, and HSVI on the benchmark problems with various
horizons, or the SL-gap percentage when reaching a 1 h time limit. Executions
not returning any result (i.e., for Random, Informed and CFR+, not performing
a single iteration) are noted out-of-time [oot].

This table first shows that HSVI always outperforms the heuristic baseline
provided by Wiggers-msc15’s algorithms, thus proving the interest of an HSVI
scheme. However, HSVI is outperformed by both SFLP and CFR+, unless they run
out of time. As can be noted, HSVI is able to keep improving even when the
horizon grows thanks to the LPE compression, taking advantage of underlying
structure in some games (e.g., Recycling Robot, a problem with
transition+observation independence (TOI), when scaling to larger horizons).

Table 2: Comparison of different solvers on various benchmark problems.
Reported values are the running times until the algorithm’s error gap (based
on bounds for HSVI) is lower than 1 %, or, if the timeout limit is reached,
the security-level gap percentages (100 % if gap
$=H\cdot(R_{\max}-R_{\min})$). Notes: (1) Horizons with a star exponent
($H^{*}$) are those for which the security-level computations ran out of time
so that, for HSVI, we give the gap between the pessimistic bounds. (2) Even
though Random and Informed contain randomness, we ran them only once, getting
fairly representative results.

Domain H Wiggers HSVI SFLP CFR+ Rand. Inf. Comp Tiger 2 0.63/(12.0*2) * 100 %
2.00/(12.0*2) * 100 % 6 $\mathrm{s}$ 1 $\mathrm{s}$ 18 $\mathrm{s}$ 3
2.53/(12.0*3) * 100 % 2.20/(12.0*3) * 100 % 1.38/(12.0*3) * 100 % 48
$\mathrm{s}$ 30 $\mathrm{\text{m}}$ 4 5.81/(12.0*4) * 100 % 3.71/(12.0*4) *
100 % 2.28/(12.0*4) * 100 % 14 $\mathrm{\text{m}}$ [oot] $5^{*}$ [oot] [oot]
32/(12.0*5) * 100 % [oot] [oot] Rec. Robot 2 0.24/(3.552*2) * 100 %
0.36/(3.552*2) * 100 % 5 $\mathrm{s}$ 1 $\mathrm{s}$ 30 $\mathrm{s}$ 3
0.98/(3.552*3) * 100 % 1.62/(3.552*3) * 100 % 4 $\mathrm{\text{m}}$ 1
$\mathrm{s}$ 13 $\mathrm{\text{m}}$ 4 2.0/(3.552*4) * 100 % 2.78/(3.552*4) *
100 % 0.7/(3.552*4) * 100 % 13 $\mathrm{s}$ 0.21/(3.552*4) * 100 % 5 [oot]
[oot] 1.9/(3.552*5) * 100 % [oot] [oot] $6^{*}$ [oot] [oot] 9.70/(3.552*6) *
100 % [oot] [oot] Adv Tiger 2 1 $\mathrm{s}$ 0.59/(8.0*2) * 100 % 1
$\mathrm{s}$ 1 $\mathrm{s}$ 1 $\mathrm{s}$ 3 0.35/(8.0*3) * 100 % 1.05/(8.0*3)
* 100 % 2 $\mathrm{\text{m}}$ 1 $\mathrm{s}$ 8 $\mathrm{s}$ 4 0.92/(8.0*4) *
100 % 1.79/(8.0*4) * 100 % 0.83/(8.0*4) * 100 % 8 $\mathrm{s}$ 13
$\mathrm{\text{m}}$ MABC 2 45 $\mathrm{s}$ 0.15/(0.4*2) * 100 % 8 $\mathrm{s}$
3 $\mathrm{s}$ 5 $\mathrm{s}$ 3 0.05/(0.4*3) * 100 % 0.11/(0.4*3) * 100 % 27
$\mathrm{s}$ 1 $\mathrm{s}$ 1 $\mathrm{\text{m}}$ 4 0.29/(0.4*4) * 100 %
0.58/(0.4*4) * 100 % 0.07/(0.4*4) * 100 % 3 $\mathrm{s}$ 47
$\mathrm{\text{m}}$ MP 4 2 $\mathrm{\text{m}}$ 5.6/(3.0*4) * 100 % 5
$\mathrm{s}$ 1 $\mathrm{s}$ 2 $\mathrm{s}$ 5 9 $\mathrm{\text{m}}$
6.87/(3.0*5) * 100 % 1 $\mathrm{\text{m}}$ 1 $\mathrm{s}$ 10 $\mathrm{s}$ 6
0.40/(3.0*6) * 100 % 8.03/(3.0*6) * 100 % 8 $\mathrm{\text{m}}$ 2 $\mathrm{s}$
1 $\mathrm{\text{m}}$

We now study the dynamic behavior of the algorithms at hand by providing and
analyzing the bounds and exploitability graphs for the same benchmarks.

####  4.2.2 Bounding Graphs

Left-side graphs in Figures 4, 5, 6, 7, 8 and 9 show how the computed upper-
and lower-bounding values $\overline{V}_{0}(\sigma_{0})$ and
$\underline{V}_{0}(\sigma_{0})$ (respectively the dotted dark and light green
curves) evolve as a function of computation time (always given in seconds).
The solid dark and light green curves show the security levels
$\nu_{[\sigma_{0},\psi_{0}^{2}]}^{1}$ and
$\nu_{[\sigma_{0},\psi_{0}^{1}]}^{2}$ of the current returned strategies
$\psi_{0}^{2}$ and $\psi_{0}^{1}$. Note that, when best-response computations
to obtain security levels are expensive (e.g., for the competitive tiger
problem, with $H=4$), they are performed either periodically (e.g. every $10$
iterations) or only once, at the end. In the captions, we indicate the
(arbitrary) frequency of the POMDP evaluations. For example, $(1,1,once)$
means that, for the first two horizons, the POMDP evaluations were done after
each iteration, and, for the last one, only once (at the end).

Overall, we observe consistent curves with (i) security levels in-between
bounds and around the NEV, and (ii) bounds converging monotonically. Note that
HSVI stops when the gap between bounds is small enough, while the gap between
SLs (used by Informed, Random and CFR, and whose computation can be time-
consuming) can be much smaller. As a matter of fact, one can notice that
strategies $\psi_{0}^{i}$ returned at each iteration by HSVI are often better
(in terms of security level) than their pessimistic lower- or upper-bounding
guarantees $\underline{\nu}_{[\sigma_{0},\psi_{0}^{1}]}^{1}$ and
$\overline{\nu}_{[\sigma_{0},\psi_{0}^{2}]}^{2}$.

####  4.2.3 Exploitability Graphs

Right-side graphs in Figures 4, 5, 6, 7, 8 and 9 show the exploitability of
the returned strategy profile as a function of computation time for HSVI,
Random, Informed, and CFR+ for the different benchmarks considered. A limit
precision of $10^{-7}$ (chosen empirically, according to the LP solver’s
precision) was applied to HSVI’s exploitability.

As can be observed, Random and Informed tend to produce reasonable strategies
quickly, but struggle to improve them so as to converge towards an
$\epsilon$-NES with $\epsilon\simeq 0$. In contrast, our algorithm keeps
improving as computation time increases. The exploitation graphs support the
observed behavior in Table 2 that HSVI converges in reasonable time compared
to Wiggers-msc15’s algorithms. However, the graphs also show that CFR+
essentially outperforms HSVI when the problems are difficult enough (i.e.,
when the temporal horizon grows) but the traversal of the whole tree still
remains tractable (thus allowing CFR+ to perform iterations). An interesting
observation is that, on small enough problems, HSVI achieves very low
exploitabilities earlier than CFR+.

Finally, HSVI’s exploitability graph shares strong similarities with those of
BosEtAl-jair14’s double-oracle algorithms [BosEtAl-jair14, Fig. 8 and 11].
This can be understood as HSVI iteratively building two sets of strategies,
one per player, until they are sufficient to support NES profiles, so that the
average exploitability is almost zero. But note that BosEtAl-jair14 construct
LPs using pure strategies (deterministic best responses), while HSVI’s
strategies are stochastic.

Figure 4:  Adversarial Tiger ($H=2,3,4$) (1,1,10): (left) Evolution of (in
dotted lines) the upper- and lower-bound values, and (in solid lines) the
security levels of the returned strategies for HSVI as a function of time
(ms). (right) Exploitability ($=\frac{\text{SL-gap}}{2}$) as a function of
time (s) for Random, Informed, CFR+, and HSVI.

Figure 5:  Competitive Tiger ($H=2,3$) (1,1): (left) Evolution of (in dotted
lines) the upper- and lower-bound values, and (in solid lines) the security
levels of the returned strategies for HSVI as a function of time (ms). (right)
Exploitability ($=\frac{\text{SL-gap}}{2}$) as a function of time (s) for
Random, Informed, CFR+, and HSVI.

Figure 6:  Mabc ($H=2,3,4$) (1,1,10): (left) Evolution of (in dotted lines)
the upper- and lower-bound values, and (in solid lines) the security levels of
the returned strategies for HSVI as a function of time (ms). (right)
Exploitability ($=\frac{\text{SL-gap}}{2}$) as a function of time (s) for
Random, Informed, CFR+, and HSVI.

Figure 7:  Recycling Robot ($H=2,3,4$) (1,1,10): (left) Evolution of (in
dotted lines) the upper- and lower-bound values, and (in solid lines) the
security levels of the returned strategies for HSVI as a function of time
(ms). (right) Exploitability ($=\frac{\text{SL-gap}}{2}$) as a function of
time (s) for Random, Informed, CFR+, and HSVI.

Figure 8: Recycling Robot ($H=5,6$) (once,none): (left) Evolution of (in
dotted lines) the upper- and lower-bound values, and (in solid lines) the
security levels of the returned strategies for HSVI as a function of time
(ms).

Figure 9:  Matching Pennies ($H=4,5,6$) (1,1,1): (left) Evolution of (in
dotted lines) the upper- and lower-bound values, and (in solid lines) the
security levels of the returned strategies for HSVI as a function of time
(ms). (right) Exploitability ($=\frac{\text{SL-gap}}{2}$) as a function of
time (s) for Random, Informed, CFR+, and HSVI.

Having empirically studied the behavior of HSVI compared to other basic
offline solvers, we now provide insight about the connections between HSVI and
continual (thus online) resolving methods.

##  5 Comparison with Continual Resolving

Continual Resolving techniques share some similarities with our approach, but
also important differences. The purpose of this section is to clarify these
points. It starts with a quick description of CFR, on which Continual
Resolving is built.

###### Counterfactual Regret Minimization (CFR)

ZinJohBowPic-nips07 belongs to the self-play family of algorithms, which gave
rise to several CFR-based approaches [Tammelin-arxiv14, BurMorSch-jair19,
LanctotEtAl-nips09, BroKroSan-aaai17]). It iteratively traverses the whole
game tree and applies, in each private history, a regret-matching update rule
based on a specific type of regret called counterfactual regrets. Iteratively
updating an initially uniform strategy asymptotically converges towards a NES.
However, the tree traversal becomes intractable when the tree size is large.

Built on top of the CFR framework, approaches based on limited-lookahead
continual resolving (LLCR) (inspired by Burch et al.’s decomposition Burch-
aaai-2014) such as DeepStack MorEtAl-science17, Libratus BroSan-science18,
ReBeL BroBakLerQon-nips20 and Player of Games SchmidEtAl-arxiv21, perform well
by exploiting a temporal decomposition in subgames, which are specified
through knowledge about both players’ past strategies. Our approach thus
shares similarities with these works.

Yet, as we will see in the next sections, a closer look at LLCR [Schmid-phd21]
demonstrates how fundamentally different they are, starting with the fact that
LLCR is an online search algorithm, i.e., is meant to make good decisions at
each time step, based on the current knowledge about the state of the game,
while HSVI, as SFLP or CFR (and its variants), is an offline algorithm
returning a complete solution strategy.

###  5.1 Continual Resolving

(Continual) Resolving techniques have been the first ingredient to adapt CFR
to online settings. They address the problem of solving the complete subgame
(down to its end) starting in the current situation at $\tau$, while
maintaining the global consistency (aka safety) of the whole strategy, i.e.,
not making choices that could encourage the opponent to deviate in the past,
before $\tau$. This is achieved by introducing constraints, called gadgets, in
a preliminary stage of the subgame that represent possible deviations and
their values, but increase the size of the game tree so that it is practically
intractable MorEtAl-science17. For its part, HSVI solves similar subgames, but
ensuring only local consistency, i.e., only considering the subgame. Global
consistency comes from the way HSVI combines "lower-level" solutions in its
backtracking process, without adding any gadget modifying the game.

For both Resolving and HSVI, solving a subgame requires sufficient statistics
that represent a prefix strategy profile from $t=0$ to $\tau$. In Resolving’s
online setting, this may seem surprising, since the opponent’s actual strategy
is not public. Yet, Resolving does not actually require knowing or guessing
the opponent’s actual strategy. In Resolving, any opponent Nash equilibrium
strategy is appropriate, since the purpose is to verify that the opponent has
no incentive to deviate from the Nash equilibrium. A requirement for Resolving
is for the sufficient statistics to represent complete strategies (given the
current public information), so that decisions are anticipated for player $i$
even in aohs (infostates) not reachable given player $\neg i$’s strategy. This
leads to using ranges KovEtAl-Corr-2019, a vector that gives, for each player,
her contribution to the probability of any history she could face at time step
$\tau$. In contrast, HSVI’s occupancy state is not necessarily related to a
Nash equilibrium strategy in any manner, and leads to ignoring unreachable
aohs, which helps to reduce the size of the decision-making (sub)problem.

###  5.2 Limited Lookahead

Continual Resolving alone solves complete subgames, thus larger problems at
early stages of the game than at the end, which is not appropriate in an
online setting. To address this issue through limiting the lookahead of
subgames, one needs to estimate the value of the leaves of any truncated
subgame. This is achieved through learning offline, for each player $i$, deep
networks that, given the current public belief state, map each aoh to its
value under some Nash equilibrium strategy profile. Note that the target
function is not unique [KovEtAl-Corr-2019, Proposition A.1], since each NES
profile maps to different value vectors. Still, according to KovEtAl-
Corr-2019, this does not seem to cause problems in practice.

In contrast, the individual value functions HSVI considers (the "$\nu$"
functions) are uniquely defined since they correspond to the best responses to
given (not necessarily Nash equilibrium) strategies of the opponent.

###  5.3 Limited Lookahead Continual Resolving as a General Scheme?

The previous subsections highlight to what extent HSVI and LLCR are
fundamentally different, in particular because they are not on the same
algorithmic level. LLCR should be seen as a general scheme in which the
subgame solver used, namely CFR, could be replaced by other "basic" offline
algorithms such as HSVI or SFLP. But we leave further investigation on this
topic for future work.

##  6 Discussion

This paper addresses the problem of $\epsilon$-optimally solving zs-POSGs. In
contrast to SFLP or CFR+, we provide the necessary foundational building
blocks to apply dynamic programming (in tandem with heuristic search) to solve
zs-POSGs. We introduce Bellman optimality equations and uniform-continuity
properties of the optimal value function. Next, we exhibit rules for updating
value functions while preserving uniform continuity and the ability to extract
globally-consistent solutions. Finally, we describe the first effective DP
algorithm for zs-POSGs, zs-oMG-HSVI, with finite-time convergence to an
$\epsilon$-optimal solution. Experiments support our theoretical findings.

We believe our approach complements existing ones, e.g., SFLP and CFR+, in two
dimensions. First, it breaks the original zs-POSG into subgames. Second, it
generalizes values from visited subgames to unvisited ones. Our performances
are as good as or better than those from SFLP and CFR+ for small-dimensional
subgames (e.g., with TOI structure). Unfortunately, the advantage of breaking
the original problem into subgames and exploiting uniform continuity
properties often fails to fully manifest in the overall computational time.

Despite some similarities, our (offline) approach is fundamentally different
from (online) continual resolving approaches. The latter could even possibly
be adapted to use other offline methods than CFR-based ones, including HSVI.

We hope that this approach will lay the foundation for further work in the
area of both exact and approximate DP solutions for zs-POSGs. In the short
term, we shall investigate pruning techniques, better Lipschitz constants, and
improved initial bounding approximators using solutions from relaxations of
zs-POSGs, e.g., zs-OS-POSGs. In the long term, we shall investigate (deep) RL
for zs-POSGs, similarly to a recent approach for Dec-POMDPs [BonDibLaePerSim-
ECML-18]. The latter shall investigate the trade-off between the update-rule
accuracy and the computational efficiency when facing high-dimensional
subgames, hence providing competitive solvers.

##  Appendix A Synthetic Tables

For convenience, we provide two synthetic tables: Table 3 to sum up various
theoretical properties that are stated in this paper (assuming a finite
temporal horizon), and Table 4 to sum up the notations used in this paper,
adding some notations that appear only in the appendix.

More precisely, Table 3 indicates, for various functions $f$ and variables
$x$, properties that $f$ is known to exhibit with respect to $x$. We denote by

-

a function with no known (or used) property (see also comment below);

n/a

a non-applicable case;

$Lin$

a linear function;

$LC$

a Lipschitz-continuous function;

$Cv$

(resp. $Cc$) a convex (resp. concave) function;

$PWLCv$

(resp. $PWLCc$) a piecewise linear and convex (resp. concave) function;

$\perp\\!\\!\\!\perp$

the function being independent of the variable;

$\neg P$

the negation of some property $P$ (i.e., $P$ is known not to hold).

Note also that, as $\sigma_{\tau}=\sigma_{\tau}^{c,1}\sigma_{\tau}^{m,1}$, the
linearity or Lipschitz-continuity properties of any function w.r.t.
$\sigma_{\tau}$ extends to both $\sigma_{\tau}^{c,1}$ and
$\sigma_{\tau}^{m,1}$. Reciprocally, related negative results extend from
$\sigma_{\tau}^{c,1}$ or $\sigma_{\tau}^{m,1}$ to $\sigma_{\tau}$. In these
three columns, we just indicate results that cannot be derived from one of the
two other columns.

Table 3: Known properties of various functions appearing in this work

| $\sigma_{\tau}$ | $\sigma_{\tau}^{m,1}$ | $\sigma_{\tau}^{c,1}$ | $\beta_{\tau}^{i}$ | $\beta_{\tau}^{\neg i}$
---|---|---|---|---|---
$T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ | $Lin$ | (section 2.2, p. 2.2) | - | - | $Lin$ | (section 2.2, p. 2.2) | $Lin$ | (section 2.2, p. 2.2)
$T^{i}_{m}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ | $Lin$ | (lemma 1, p. 1) | - | - | $Lin$ | (lemma 1, p. 1) | $Lin$ | (lemma 1, p. 1)
$T^{i}_{c}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ | - | $\perp\\!\\!\\!\perp$ | (lemma 2, p. 2) | - | $\perp\\!\\!\\!\perp$ | (lemma 2, p. 2) | -
$V_{\tau}^{*}(\sigma_{\tau})$ | $LC$ | (section D.1.3, p. D.1.3) | $PWLCv$ | (theorem 2.4, p. 2.4) | - | n/a | n/a
$W_{\tau}^{i,*}(\sigma_{\tau},\beta_{\tau}^{i})$ | $LC$ | (from $Q^{*}_{\tau+1}$ LC) | - | - | $\neg Lin$ | (from $Q^{*}$ $\neg Lin$) | n/a
$\nu^{2}_{[\sigma^{c,1}_{\tau},\beta^{2}_{\tau:}]}$ | n/a | n/a | $LC$ | (lemma 3, p. 3) | n/a | -

Table 4: Various notations used in this work  $\neg i$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $i$’s opponent. Thus: $\neg 1=2$, and $\neg 2=1$.
---|---|---
Histories and occupancy states
$\theta^{i}_{\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $(a^{i}_{0},z^{i}_{1},\dots,a^{i}_{\tau-1},z^{i}_{\tau})$ ($\in\Theta^{i}=\cup_{t=0}^{H-1}\Theta^{i}_{t}$) is a length-$\tau$ action-observation history (aoh) for $i$.
${\boldsymbol{\theta}}_{\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $(\theta^{1}_{\tau},\theta^{2}_{\tau})$ ($\in{\boldsymbol{\Theta}}=\cup_{t=0}^{H-1}{\boldsymbol{\Theta}}_{t}$) is a joint aoh at $\tau$.
$\sigma_{\tau}({\boldsymbol{\theta}}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Occupancy state (os) $\sigma_{\tau}$ ($\in{\mathcal{}O}^{\sigma}=\cup_{t=0}^{H-1}{\mathcal{}O}^{\sigma}_{t}$, where ${\mathcal{}O}^{\sigma}_{\tau}\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}\Delta({\boldsymbol{\Theta}}_{\tau})$), i.e., probability distribution over joint aohs ${\boldsymbol{\theta}}_{\tau}$ (typically for some applied ${\boldsymbol{\beta}}_{0:\tau-1}$).
$\sigma_{\tau}^{m,i}(\theta^{i}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Marginal term of $\sigma_{\tau}$ from player $i$’s point of view ($\sigma_{\tau}^{m,i}\in\Delta(\Theta_{\tau}^{i})$).
$\sigma_{\tau}^{c,i}(\theta^{\neg i}_{\tau}|\theta^{i}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Conditional term of $\sigma_{\tau}$ from $i$’s point of view ($\sigma_{\tau}^{c,i}:\Theta_{\tau}^{i}\mapsto\Delta(\Theta_{\tau}^{\neg i})$).
$b(s|{\boldsymbol{\theta}}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Belief state, i.e., probability distribution over states given a joint aoh ($b(s|{\boldsymbol{\theta}}_{\tau}):{\mathcal{}S}\times{\boldsymbol{\Theta}}_{\tau}\mapsto{\mathbb{R}}$). Can be computed by an HMM filtering process.
$o_{\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Full occupancy state $o_{\tau}$ ($\in\Delta({\mathcal{}S}\times{\boldsymbol{\Theta}}_{\tau})$), i.e., $Pr(s,{\boldsymbol{\theta}}_{\tau})$ for the current ${\boldsymbol{\beta}}_{0:\tau-1}$, and thus verifies $\sigma_{\tau}({\boldsymbol{\theta}}_{\tau})=\sum_{s\in{\mathcal{}S}}o_{\tau}(s,{\boldsymbol{\theta}}_{\tau})$. Is used in the implementation to simplify computations (e.g., of $r_{t}$ and $\sigma_{\tau+1}$ through $b$).
Decision rules and strategies
$\pi^{i}_{0:\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  A pure strategy for $i$ is a mapping $\pi^{i}_{0:\tau}$ from private histories in $\Theta^{i}_{t}$ ($\forall t\in\\{0\mathinner{\ldotp\ldotp}\tau\\}$) to single private actions in ${\mathcal{}A}^{i}$. By default, $\pi^{i}\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}\pi^{i}_{0:H-1}$.
$\mu^{i}_{0:\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  A mixed strategy $\mu^{i}_{0:\tau}$ for $i$ is a probability distribution over pure strategies. It is used by first sampling one of the pure strategies (at $t=0$), and then executing it until $t=\tau$.
$\mu^{i}_{0:\tau^{\prime}\mid\sigma_{\tau}\rangle}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  ($\tau\leq\tau^{\prime}$) is a mixed strategy compatible with some os $\sigma_{\tau}$, i.e., that could induce this os at $\tau$ (assuming an appropriate complementary $\mu^{\neg i}_{0:\tau^{\prime}\mid\sigma_{\tau}\rangle}$).
$\beta^{i}_{\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  A (behavioral) decision rule (dr) at time $\tau$ for $i$ is a mapping $\beta^{i}_{\tau}$ from private aohs in $\Theta^{i}_{\tau}$ to distributions over private actions. We note $\beta^{i}_{\tau}(\theta^{i}_{\tau},a^{i})$ the probability to pick $a^{i}$ when facing $\theta^{i}_{\tau}$.
$\beta^{i}_{\tau:\tau^{\prime}}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $(\beta^{i}_{\tau},\dots,\beta^{i}_{\tau^{\prime}})$ is a behavioral strategy for $i$ from time step $\tau$ to $\tau^{\prime}$ (included).
$rw^{i}(\theta^{i}_{\tau},a^{i}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $\prod_{t=0}^{\tau}\beta^{i}_{0:}(a^{i}_{t}|a^{i}_{0},z^{i}_{1},a^{i}_{1},\dots,z^{i}_{t})$ is the realization weight (RW) of sequence $a^{i}_{0},z^{i}_{1},a^{i}_{1},\dots,a^{i}_{\tau}(=\theta^{i}_{\tau},a^{1}_{\tau})$ under strategy $\beta^{i}_{0:}$.
$rw^{i}(\phi^{i}_{\tau:\tau^{\prime}}|\theta^{i}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $\prod_{t=\tau}^{\tau^{\prime}}\beta^{i}_{0:}(a^{i}_{t}|\theta^{i}_{\tau},a^{i}_{\tau},\dots,z^{i}_{t})$ is the RW of a suffix sequence $\phi^{i}_{\tau:\tau^{\prime}}=a^{i}_{\tau},\dots,a^{i}_{\tau^{\prime}}$ “conditioned” on a prefix sequence/aoh $\theta^{i}_{\tau}$.
$\boldsymbol{\pi}_{0:\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  is a pure strategy profile.
$\boldsymbol{\mu}_{0:\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  is a mixed strategy profile.
$\boldsymbol{\mu}_{0:\tau^{\prime}\mid\sigma_{\tau}\rangle}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  ($\tau\leq\tau^{\prime}$) is a mixed strategy profile compatible with some os $\sigma_{\tau}$, i.e., that could induce this os at $\tau$.
${\boldsymbol{\beta}}_{\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $\langle\beta^{1}_{\tau},\beta^{2}_{\tau}\rangle$ ($\in{\mathcal{}B}=\cup_{t=0}^{H-1}{\mathcal{}B}_{t}$) is a decision rule profile.
${\boldsymbol{\beta}}_{\tau:\tau^{\prime}}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $\langle\beta^{1}_{\tau:\tau^{\prime}},\beta^{2}_{\tau:\tau^{\prime}}\rangle$ is a behavioral strategy profile.
Rewards and value functions
---
$r_{\max}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ | $\max_{s,{\boldsymbol{a}}}r(s,{\boldsymbol{a}})$ |  Maximum possible reward.
$r_{\min}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ | $\min_{s,{\boldsymbol{a}}}r(s,{\boldsymbol{a}})$ |  Minimum possible reward.
$V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $E[\sum_{t=\tau}^{H-1}\gamma^{t}R_{t}\mid\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:}]$, |  Value of ${\boldsymbol{\beta}}_{\tau:H-1}$ in os $\sigma_{\tau}$.
|  |  where $R_{t}$ is the random var. for the reward at $t$.
$V_{\tau}^{*}(\sigma_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ | $\max_{\beta^{1}_{\tau:}}\min_{\beta^{2}_{\tau:}}V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})$ |  Optimal value function
$Q_{\tau}^{*}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ | $r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma V_{\tau+1}^{*}(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}))$ |  Opt. (joint) action-value fct.
$W_{\tau}^{i,*}(\sigma_{\tau},\beta_{\tau}^{i})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  $opt_{\beta^{\neg i}_{\tau}}Q_{\tau}^{*}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$, |  Opt. (individual) action-value fct.
|  |  where $opt=\max$ if $i=1$, $\min$ otherwise.
$\nu^{2}_{[\sigma_{\tau}^{c,1},\beta_{\tau:}^{2}]}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Vector of values (one component per aoh $\theta^{1}_{\tau}$) for $1$’s best response to $\beta_{\tau:}^{2}$ assuming $\sigma_{\tau}^{c,1}$. This solution of a POMDP allows computing $V_{\tau}^{*}$ (see Theorem 2.4).
Approximations
$\overline{V}_{\tau}(\sigma_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Upper bound approximation of $V^{*}_{\tau}(\sigma_{\tau})$; relies on data set $\overline{{\mathcal{}I}}_{\tau-1}$.
$\underline{V}_{\tau}(\sigma_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Lower bound approximation of $V^{*}_{\tau}(\sigma_{\tau})$; relies on data set $\underline{{\mathcal{}I}}_{\tau-1}$.
$\overline{W}_{\tau}(\sigma_{\tau},\beta^{1}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Upper bound approximation of $W_{\tau}^{*,1}(\sigma_{\tau},\beta^{1}_{\tau})$; relies on data set $\overline{\mathcal{I}}_{\tau}$.
$\underline{W}_{\tau}(\sigma_{\tau},\beta^{2}_{\tau})$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Lower bound approximation of $W_{\tau}^{*,2}(\sigma_{\tau},\beta^{2}_{\tau})$; relies on data set $\underline{\mathcal{I}}_{\tau}$.
$\overline{\nu}_{\tau}^{2}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Vector (with one component per aoh $\theta^{1}_{\tau}$) used in $\overline{V}_{\tau}$ and $\overline{W}_{\tau-1}$ (if $\tau\geq 1$).
Miscellaneous
$w_{\tau}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Denotes a triplet $\langle\sigma^{c,1}_{\tau-1},\beta^{1}_{\tau-1},\overline{\nu}^{2}_{\tau},\rangle\in\overline{\mathcal{I}}_{\tau}$ (or a triplet in $\underline{\mathcal{I}}_{\tau}$).
$\psi_{\tau}^{2}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Distribution over triplets $w_{\tau+1}\in\overline{\mathcal{I}}_{\tau+1}$ (inducing a recursively defined strategy from $\tau$ to $H-1$). Often denotes the strategy it induces.
$x^{\top}$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  The transpose of a (usually column) vector $x$ of ${\mathbb{R}}^{n}$.
$c[y]$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Denotes field $c$ of object/tuple $y$.
$\mathit{Supp}(d)$ | $\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}$ |  Support of distribution $d$, i.e., set of its non-zero probability elements.

##  Appendix B Background

###  B.1 Occupancy States

The following result shows that the occupancy state is (i) Markovian, i.e.,
its value at $\tau$ only depends on its previous value $\sigma_{\tau-1}$, the
system dynamics $P_{a^{1},a^{2}}^{z^{1},z^{2}}(s^{\prime}|s)$, and the last
behavioral decision rules $\beta^{1}_{\tau-1}$ and $\beta^{2}_{\tau-1}$, and
(ii) sufficient to estimate the expected reward. Note that it holds for
general-sum POSGs with any number of agents, and as many reward functions;
similar results have already been established, e.g., for Dec-POMDPs (cf.
[DibAmaBufCha-jair16, Theorem 1]).

*

###### Proof.

Let us first derive a recursive way of computing
$\sigma_{{\boldsymbol{\beta}}_{0:\tau}}({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau},{\boldsymbol{z}}_{\tau+1})$:

$\displaystyle\sigma_{{\boldsymbol{\beta}}_{0:\tau}}({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau},{\boldsymbol{z}}_{\tau+1})\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}Pr({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau},{\boldsymbol{z}}_{\tau+1}\mid{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle=\sum_{s_{\tau},s_{\tau+1}}Pr({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau},{\boldsymbol{z}}_{\tau+1},s_{\tau},s_{\tau+1}\mid{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle=\sum_{s_{\tau},s_{\tau+1}}Pr({\boldsymbol{z}}_{\tau+1},s_{\tau+1}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau},s_{\tau},{\boldsymbol{\beta}}_{0:\tau})Pr({\boldsymbol{a}}_{\tau}\mid{\boldsymbol{\theta}}_{\tau},s_{\tau},{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle\qquad\qquad
Pr(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{\beta}}_{0:\tau})Pr({\boldsymbol{\theta}}_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle=\sum_{s_{\tau},s_{\tau+1}}\underbrace{Pr({\boldsymbol{z}}_{\tau+1},s_{\tau+1}\mid{\boldsymbol{a}}_{\tau},s_{\tau})}_{=P_{{\boldsymbol{a}}_{\tau}}^{{\boldsymbol{z}}_{\tau+1}}(s_{\tau+1}|s_{\tau})}\underbrace{Pr({\boldsymbol{a}}_{\tau}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{\beta}}_{\tau})}_{={\boldsymbol{\beta}}({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau})}\underbrace{Pr(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{\beta}}_{0:\tau})}_{=b(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau})}\underbrace{Pr({\boldsymbol{\theta}}_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau-1})}_{=\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}({\boldsymbol{\theta}}_{\tau})},$
(where $b(s\mid{\boldsymbol{\theta}}_{\tau})$ is the belief over states
obtained by a usual HMM filtering process)
$\displaystyle=\sum_{s_{\tau},s_{\tau+1}}P_{{\boldsymbol{a}}_{\tau}}^{{\boldsymbol{z}}_{\tau+1}}(s_{\tau+1}|s_{\tau}){\boldsymbol{\beta}}({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau})b(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau})\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}({\boldsymbol{\theta}}_{\tau}).$

$\sigma_{{\boldsymbol{\beta}}_{0:\tau}}$ can thus be computed from
$\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}$ and ${\boldsymbol{\beta}}_{\tau}$
without explicitly using ${\boldsymbol{\beta}}_{0:\tau-1}$ or earlier
occupancy states.

Then, let us compute the expected reward at $\tau$ given
${\boldsymbol{\beta}}_{0:\tau}$:

$\displaystyle
E[r(S_{\tau},A^{1}_{\tau},A^{2}_{\tau})\mid{\boldsymbol{\beta}}_{0:\tau}]$
$\displaystyle=\sum_{s_{\tau},{\boldsymbol{a}}_{\tau}}r(s_{\tau},{\boldsymbol{a}}_{\tau})Pr(s_{\tau},{\boldsymbol{a}}_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle=\sum_{s_{\tau},{\boldsymbol{a}}_{\tau}}\sum_{{\boldsymbol{\theta}}_{\tau}}r(s_{\tau},{\boldsymbol{a}}_{\tau})Pr(s_{\tau},{\boldsymbol{a}}_{\tau},{\boldsymbol{\theta}}_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle=\sum_{s_{\tau},{\boldsymbol{a}}_{\tau}}\sum_{{\boldsymbol{\theta}}_{\tau}}r(s_{\tau},{\boldsymbol{a}}_{\tau})Pr(s_{\tau},{\boldsymbol{a}}_{\tau}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{\beta}}_{0:\tau})Pr({\boldsymbol{\theta}}_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau})$
$\displaystyle=\sum_{s_{\tau},{\boldsymbol{a}}_{\tau}}\sum_{{\boldsymbol{\theta}}_{\tau}}r(s_{\tau},{\boldsymbol{a}}_{\tau})\underbrace{Pr({\boldsymbol{a}}_{\tau}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{\beta}}_{0:\tau})}_{{\boldsymbol{\beta}}_{\tau}({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau})}\underbrace{Pr(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau},{\boldsymbol{\beta}}_{0:\tau})}_{b(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau})}\underbrace{Pr({\boldsymbol{\theta}}_{\tau}\mid{\boldsymbol{\beta}}_{0:\tau})}_{\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}({\boldsymbol{\theta}}_{\tau})}$
$\displaystyle=\sum_{s_{\tau},{\boldsymbol{a}}_{\tau}}\sum_{{\boldsymbol{\theta}}_{\tau}}r(s_{\tau},{\boldsymbol{a}}_{\tau}){\boldsymbol{\beta}}_{\tau}({\boldsymbol{\theta}}_{\tau},{\boldsymbol{a}}_{\tau})b(s_{\tau}\mid{\boldsymbol{\theta}}_{\tau})\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}({\boldsymbol{\theta}}_{\tau}).$

The expected reward at $\tau$ can thus be computed from
$\sigma_{{\boldsymbol{\beta}}_{0:\tau-1}}$ and ${\boldsymbol{\beta}}_{\tau}$
without explicitly using ${\boldsymbol{\beta}}_{0:\tau-1}$ or earlier
occupancy states. ∎

##  Appendix C Occupancy Markov Games: Definition and Preliminary Properties

###  C.1 Properties of $V^{*}$

Before proving the postulates implicitly used by [WigOliRoi-corr16], we need
to show that we can reason with mixed strategies in subgames as is usually
done on full games.

####  C.1.1 $V^{*}$ is not linear in $\beta$ (behavioral strategies)

Let us consider the following (finite-horizon, deterministic) Non-Observable
MDP:

$\displaystyle{\mathcal{}S}$ $\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\\{-2,-1,0,+1,+2\\},\quad b_{0}(0)=1,$ (always start in $s=0$)
$\displaystyle{\mathcal{}A}$ $\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\\{-1,+1\\},$ (moves = add or subtract 1) $\displaystyle T(s,a)$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\min\\{+2,\max\\{-2,s+a\\}\\},$ (dép. de $+1$ ou $-1$ dans
${\mathcal{}S}$) $\displaystyle{\mathcal{}Z}$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}\\{none\\},\quad
O(none)\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}1,$ (no observation)
$\displaystyle r(s)$ $\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\begin{cases}+1&\text{si }s\in\\{-2,+2\\}\\\
0&\text{sinon,}\end{cases}$ ($\lvert s\rvert=2$ : victoire !)
$\displaystyle\gamma$ $\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}1,\quad H\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}2.$

Let us then consider two particular behavioral strategies:

$\displaystyle\forall\theta,\ \beta^{+}(A=+1|\theta)$ $\displaystyle=1$
(always $+1$), and $\displaystyle\forall\theta,\ \beta^{-}(A=-1|\theta)$
$\displaystyle=1$ $\displaystyle\text{(always $-1$)}.$

These two strategies are optimal, with an expected return of $+1$, because, at
$t=H=2$, $\beta^{+}$ reaches $+2$ w.p. $1$, and $\beta^{-}$ reaches $-2$ w.p.
$1$:

$\displaystyle V(\beta^{+})$ $\displaystyle=V(\beta^{-})=+1.$

Let us now consider their linear combination
$\beta^{\pm}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\frac{1}{2}\beta^{+}+\frac{1}{2}\beta^{-}$:

$\displaystyle\forall\theta,\ \beta^{\pm}(A=-1|\theta)$ $\displaystyle=0.5,$
$\displaystyle\forall\theta,\ \beta^{\pm}(A=+1|\theta)$ $\displaystyle=0.5.$

Here, the probability to reach $s=-2$ or $s=+2$ at the last time step is much
lower, and gives the value of that strategy:

$\displaystyle V(\beta^{\pm})$
$\displaystyle=Pr(s_{2}=+2|\beta^{\pm})+Pr(s_{2}=+2|\beta^{\pm})$
$\displaystyle=Pr(a_{0}=+1|\beta^{\pm})\cdot Pr(a_{1}=+1|\beta^{\pm})$
$\displaystyle+Pr(a_{0}=-1|\beta^{\pm})\cdot Pr(a_{1}=-1|\beta^{\pm})$
$\displaystyle=\underbrace{0.5\cdot 0.5}_{0.25}+\underbrace{0.5\cdot
0.5}_{0.25}=0.5.$

####  C.1.2 Back to Mixed Strategies

We now generalize mixed strategies as a mathematical tool to handle subgames
of a zs-OMG as normal-form games, and give some preliminary results.

First, for a given $\sigma_{\tau}$ and $\tau\leq\tau^{\prime}$, let
$\boldsymbol{\mu}_{0:\tau^{\prime}-1|\sigma_{\tau}\rangle}$ denote a mixed
strategy profile that is defined over $0:\tau^{\prime}-1$, and induces (/is
compatible with) $\sigma_{\tau}$ at time $\tau$. Then, to complete a given
mixed prefix strategy
$\boldsymbol{\mu}_{0:\tau^{\prime}-1|\sigma_{\tau}\rangle}$ (here
$\tau=\tau^{\prime}$), the solver should provide each player with a different
suffix strategy to execute for each $\theta^{i}_{\tau}$ it could be facing. We
now detail how to build an equivalent set of mixed full strategies for $i$.
Each of the pure prefix strategies $\pi^{i}_{0:\tau-1}$ used in
$\mu^{i}_{0:\tau-1|\sigma_{\tau}\rangle}$ (belonging to a set denoted
$\Pi^{i}_{0:\tau-1|\sigma_{\tau}\rangle}$) can be extended by appending a
different pure suffix strategy $\pi^{i}_{\tau:H-1}$ at each of its leaf nodes,
which leads to a large set of pure strategies
$\Pi^{i}_{0:H-1}(\pi^{i}_{0:\tau-1})$. Then, let
$M^{i}_{0:H-1|\sigma_{\tau}\rangle}$ be the set of mixed full strategies
$\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}$ obtained by considering the
distributions over
$\bigcup_{\pi^{i}_{0:\tau-1}\in\Pi^{i}_{0:\tau-1|\sigma_{\tau}\rangle}}\Pi^{i}_{0:H-1}(\pi^{i}_{0:\tau-1})$
that verify, $\forall\pi^{i}_{0:\tau-1}$,

$\displaystyle\sum_{\begin{subarray}{c}\pi^{i}_{0:H-1}\in\\\
\Pi^{i}_{0:H-1}(\pi^{i}_{0:\tau-1})\end{subarray}}\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:H-1})$
$\displaystyle=\mu^{i}_{0:\tau-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:\tau-1}).$
(17)

This is the set of mixed strategies compatible with $\sigma_{\tau}$.

[Proof in App. LABEL:proofLemEquivalence]lemmalemEquivalence
$M^{i}_{0:H-1|\sigma_{\tau}\rangle}$ is convex and equivalent to the set of
behavioral strategies $\beta^{i}_{0:H-1|\sigma_{\tau}\rangle}$, thus
sufficient to search for a Nash equilibrium in $\sigma_{\tau}$.

###### Proof.

Let $\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}$ and
$\nu^{i}_{0:H-1|\sigma_{\tau}\rangle}$ be two mixed strategies in
$M^{i}_{0:H-1|\sigma_{\tau}\rangle}$, i.e., which are both full and compatible
with occupancy state $\sigma_{\tau}$ at time step $\tau$, and
$\alpha\in[0,1]$. Then, for any $\pi^{i}_{0:\tau-1}$,

$\displaystyle\sum_{\pi^{i}_{0:H-1}\in\Pi^{i}_{0:H-1}(\pi^{i}_{0:\tau-1})}\left[\alpha\cdot\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:H-1})+(1-\alpha)\cdot\nu^{i}_{0:H-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:H-1})\right]$
$\displaystyle=\alpha\left[\sum_{\pi^{i}_{0:H-1}\in\Pi^{i}_{0:H-1}(\pi^{i}_{0:\tau-1})}\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:H-1})\right]$
$\displaystyle\qquad+(1-\alpha)\left[\sum_{\pi^{i}_{0:H-1}\in\Pi^{i}_{0:H-1}(\pi^{i}_{0:\tau-1})}\nu^{i}_{0:H-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:H-1})\right]$
(because both mixed strategies are compatible with $\sigma_{\tau}$ (eq. 17, p.
17):)
$\displaystyle=\alpha\cdot\mu^{i}_{0:\tau-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:\tau-1})+(1-\alpha)\cdot\mu^{i}_{0:\tau-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:\tau-1})$
$\displaystyle=\mu^{i}_{0:\tau-1|\sigma_{\tau}\rangle}(\pi^{i}_{0:\tau-1}).$

Eq. 17 thus also applies to
$\alpha\cdot\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}+(1-\alpha)\cdot\nu^{i}_{0:H-1|\sigma_{\tau}\rangle}$,
proving that it belongs to $M^{i}_{0:H-1|\sigma_{\tau}\rangle}$ and, as a
consequence, that this set is convex.

The equivalence with the set of behavioral strategies simply relies on the
fact that all mixed strategies over $\tau:H-1$ can be independently generated
at each action-observation history $\theta^{i}_{0:\tau-1}$. ∎

While only future rewards are relevant when making a decision at $\tau$,
reasoning with mixed strategies defined from $t=0$ will be convenient because
$V_{\tau}(\sigma_{\tau},\cdot,\cdot)$ is linear in
$\mu^{i}_{0:H-1|\sigma_{\tau}\rangle}$, which allows coming back to a standard
normal-form game and applying known results.

In the remaining, we simply note $\mu^{i}$ (without index) the mixed
strategies in $M^{i}_{0:H-1|\sigma_{\tau}\rangle}$, set which we now note
$M^{i}_{|\sigma_{\tau}\rangle}$. Also, since we shall work with local game
$Q^{*}_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$, let us define:
$M^{i}_{|\sigma_{\tau},\beta^{j}_{\tau}\rangle}$ the set of $i$’s mixed
strategies compatible with occupancy states reachable given $\sigma_{\tau}$
and $\beta^{j}_{\tau}$ (with either $j=i$ or $j=-i$). Then,
$M^{i}_{|T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})\rangle}\subseteq
M^{i}_{|\sigma_{\tau},\beta^{j}_{\tau}\rangle}\subseteq
M^{i}_{|\sigma_{\tau}\rangle}$ (inclusion due to the latter sets being less
constrained in their definition). As a consequence, if maximizing some
function $f$ over $i$’s mixed strategies compatible with a given
$\sigma_{\tau}$:

$\displaystyle\max_{\mu^{i}\in
M^{i}_{|\sigma_{\tau}\rangle}}f(\sigma_{\tau},\mu^{i},\dots)$
$\displaystyle\geq\max_{\mu^{i}\in
M^{i}_{|\sigma_{\tau},\beta^{j}_{\tau}\rangle}}f(\sigma_{\tau},\mu^{i},\dots)\geq\max_{\mu^{i}\in
M^{i}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}f(\sigma_{\tau},\mu^{i},\dots).$

####  C.1.3 Von Neumann’s Minimax Theorem for Subgames and a Bellman
Optimality Equation

Using the previous results, one can show that Neu-ma28’s minimax theorem
applies in any subgame, allowing to swap operators $\max$ and $\min$.

*

###### Proof.

For any occupancy state $\sigma_{\tau}$,

$\displaystyle\max_{\beta_{\tau:}^{1}}\min_{\beta_{\tau:}^{2}}V(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})$
$\displaystyle=\max_{\mu_{\tau:}^{1}}\min_{\mu_{\tau:}^{2}}V(\sigma_{\tau},\boldsymbol{\mu}_{\tau:})\qquad\text{(\cite[citeauthor]{\@@bibref{Authors}{Kuhn-
ctg50}{}{}}'s theorem (generalized))}$ (18)
$\displaystyle=\min_{\mu_{\tau:}^{2}}\max_{\mu_{\tau:}^{1}}V(\sigma_{\tau},\boldsymbol{\mu}_{\tau:})\qquad\text{(\cite[citeauthor]{\@@bibref{Authors}{Neu-
ma28}{}{}}'s theorem)}$ (19)
$\displaystyle=\min_{\beta_{\tau:}^{2}}\max_{\beta_{\tau:}^{1}}V(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})\qquad\text{(again
\cite[citeauthor]{\@@bibref{Authors}{Kuhn-ctg50}{}{}}'s theorem
(generalized))}$ (20)

∎

One can also show that a Bellman optimality equation allows relating optimal
values in subgames at $\tau$ and $\tau+1$, leading to a recursive expression
of $V^{*}_{0}$.

*

###### Proof.

Focusing, without loss of generality, on player $1$, we have (complementary
explanations follow for numbered lines in particular):

$\displaystyle\max_{\beta^{1}_{\tau}}\min_{\beta^{2}_{\tau}}Q^{*}_{\tau}(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})=\max_{\beta^{1}_{\tau}}\min_{\beta^{2}_{\tau}}\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})+\gamma
V^{*}_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}))\right]$
(21) ($V^{*}_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}))$
being the Nash equilibrium value of normal-form game
$V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}),\mu^{1},\mu^{2})$:)
$\displaystyle=\max_{\beta^{1}_{\tau}}\min_{\beta^{2}_{\tau}}\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})+\gamma\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}),\mu^{1},\mu^{2})\right]$
(22)
$\displaystyle=\max_{\beta^{1}_{\tau}}\min_{\beta^{2}_{\tau}}\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})+\gamma
V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}),\mu^{1},\mu^{2})\right]$
(23) (using the equivalence between maximin and minimax values for the
(constrained normal-form) game at $\tau+1$, the last two max and min operators
can be swapped:)
$\displaystyle=\max_{\beta^{1}_{\tau}}\min_{\beta^{2}_{\tau}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}\rangle}}\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})+\gamma
V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}),\mu^{1},\mu^{2})\right]$
(24) (merging both mins (and with explanations thereafter):)
$\displaystyle=\max_{\beta^{1}_{\tau}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau},\beta^{1}_{\tau}\rangle}}\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu^{2})\rangle}}$
(25)
$\displaystyle\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu_{2}))+\gamma
V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu_{2})),\mu^{1},\mu^{2})\right]$
(26) (since ignoring the opponent’s decision rule does not influence the
expected return:) $\displaystyle=\max_{\beta^{1}_{\tau}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau}\rangle}}\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau},\beta^{1}_{\tau}\rangle}}\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu_{2}))+\gamma
V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu_{2})),\mu^{1},\mu^{2})\right]$
(27) (using again the minimax theorem’s equivalence between maximin and
minimax on an appropriate game:)
$\displaystyle=\max_{\beta^{1}_{\tau}}\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau},\beta^{1}_{\tau}\rangle}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau}\rangle}}\left[r(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu_{2}))+\gamma
V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau}(\mu_{2})),\mu^{1},\mu^{2})\right]$
(28) (merging both maxs (and with explanations thereafter):)
$\displaystyle=\max_{\mu^{1}\in
M^{1}_{|\sigma_{\tau}\rangle}}\min_{\mu^{2}_{\tau}|\sigma_{\tau})}\left[r(\sigma_{\tau},\beta^{1}_{\tau}(\mu_{1}),\beta^{2}_{\tau}(\mu_{2}))+\gamma
V_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau}(\mu^{1}),\beta^{2}_{\tau}(\mu_{2})),\mu^{1},\mu^{2})\right]$
(29) (again with the equivalence property discussed before the lemma:)
$\displaystyle=\max_{\mu^{1}\in M^{1}_{|\sigma_{\tau}\rangle}}\min_{\mu^{2}\in
M^{2}_{|\sigma_{\tau}\rangle}}V_{\tau}(\sigma_{\tau},\mu^{1},\mu^{2})$ (30)
$\displaystyle=\max_{\beta^{1}_{\tau:H-1|\sigma_{\tau}\rangle}}\min_{\beta^{2}_{\tau:H-1|\sigma_{\tau}\rangle}}V_{\tau}(\sigma_{\tau},\beta^{1}_{\tau:H-1},\beta^{2}_{\tau:H-1})$
(31) $\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}V^{*}_{\tau}(\sigma_{\tau}).$ (32)

More precisely, line 26 (and, similarly, line 29) is obtained by observing
that

  * •

minimizing over both (i) $\beta^{2}_{\tau}$ and (ii) $\mu^{2}$ constrained by
$\sigma_{\tau}$ and ${\boldsymbol{\beta}}_{\tau}$ is equivalent to minimizing
over $\mu^{2}$ constrained by $\sigma_{\tau}$ and $\beta^{1}_{\tau}$; and

  * •

in the reminder of the formula, decision rule $\beta^{2}_{\tau}$ at time
$\tau$ can be retrieved as a function of $\mu^{2}$ (noted
$\beta^{2}_{\tau}(\mu^{2})$).

Also, line 28 results from the observation that, while
$M^{1}_{|\sigma_{\tau},\beta^{1}_{\tau}\rangle}$ and
$M^{2}_{|\sigma_{\tau}\rangle}$ allow to actually make decisions over
different time intervals, we are here minimizing over $\mu^{2}$ while
maximizing over $\mu^{1}$ a function that is linear in both input spaces. This
amounts to solving some 2-player zero-sum normal-form game, hence the
applicability of von Neumann’s minimax theorem.

The above derivation tells us that the maximin value (the best outcome player
$1$ can guarantee whatever player $2$’s strategy) in the one-time-step game is
thus the Nash equilibrium value (NEV) for the complete subgame from $\tau$
onwards. ∎

##  Appendix D Solving zs-OMGs

###  D.1 Preliminary Properties

####  D.1.1 Properties of $T^{1}_{m}$ and $T^{1}_{c}$

The first two lemmas below present properties of $T^{1}_{m}$ and $T^{1}_{c}$
that will be useful afterwards.

######  Lemma 1.

$T^{1}_{m}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ is linear in
$\sigma_{\tau}$, $\beta^{1}_{\tau}$, and $\beta^{2}_{\tau}$.

###### Proof.

$\displaystyle
T^{1}_{m}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})(\theta^{1}_{\tau},a^{1},z^{1})$
(33)
$\displaystyle=\sum_{\theta^{2}_{\tau},a^{2},z^{2}}T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})({(\theta^{1}_{\tau},a^{1},z^{1}),(\theta^{2}_{\tau},a^{2},z^{2})})\qquad\text{(from
{\lx@cref{creftypecap~refnum}{eq|transition}})}$ (34)
$\displaystyle=\sum_{s^{\prime},\theta^{2}_{\tau},a^{2},z^{2}}\beta^{1}_{\tau}(\theta^{1}_{\tau},a^{1})\beta^{2}_{\tau}(\theta^{2}_{\tau},a^{2})\sum_{s}P^{z^{1},z^{2}}_{a^{1},a^{2}}(s^{\prime}|s)b(s|\theta^{1}_{\tau},\theta^{2}_{\tau})\sigma_{\tau}(\theta^{1}_{\tau},\theta^{2}_{\tau})$
(35)
$\displaystyle=\beta^{1}_{\tau}(\theta^{1}_{\tau},a^{1})\sum_{\theta^{2}_{\tau},a^{2}}\beta^{2}_{\tau}(\theta^{2}_{\tau},a^{2})\sum_{s,s^{\prime},z^{2}}P^{z^{1},z^{2}}_{a^{1},a^{2}}(s^{\prime}|s)b(s|\theta^{1}_{\tau},\theta^{2}_{\tau})\sigma_{\tau}(\theta^{1}_{\tau},\theta^{2}_{\tau}).$
(36)

∎

######  Lemma 2.

$T^{1}_{c}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ is independent of
$\beta^{1}_{\tau}$ and $\sigma^{m,1}_{\tau}$.

###### Proof.

See Wiggers-msc15, Lemma 4.2.3. ∎

####  D.1.2 Linearity and Lipschitz-continuity of
$T(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})$

[]lemmalemOccLin At depth $\tau$,
$T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ is linear in
$\beta^{1}_{\tau}$, $\beta^{2}_{\tau}$, and $\sigma_{\tau}$, where
${\boldsymbol{\beta}}_{\tau}=\langle\beta^{1}_{\tau},\beta^{2}_{\tau}\rangle$.
It is more precisely $1$-Lipschitz-continuous ($1$-LC) in $\sigma_{\tau}$ (in
$1$-norm), i.e., for any $\sigma_{\tau}$, $\sigma^{\prime}_{\tau}$:

$\displaystyle\lVert
T(\sigma^{\prime}_{\tau},{\boldsymbol{\beta}}_{\tau})-T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})\rVert_{1}$
$\displaystyle\leq
1\cdot\lVert\sigma^{\prime}_{\tau}-\sigma_{\tau}\rVert_{1}.$

###### Proof.

Let $\sigma$ be an occupancy state at time $\tau$ and
${\boldsymbol{\beta}}_{\tau}$ be a decision rule. Then, as seen in the proof
of Section 2.2, the next occupancy state
$\sigma^{\prime}=T(\sigma,{\boldsymbol{\beta}}_{\tau})$ satisfies, for any
$s^{\prime}$ and $({\boldsymbol{\theta}},{\boldsymbol{a}},{\boldsymbol{z}})$:

$\displaystyle\sigma^{\prime}({\boldsymbol{\theta}},{\boldsymbol{a}},{\boldsymbol{z}})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}Pr({\boldsymbol{\theta}},{\boldsymbol{a}},{\boldsymbol{z}}|\sigma,\beta^{1}_{\tau},\beta^{2}_{\tau})$
$\displaystyle=\beta^{1}_{\tau}(\theta^{1},a^{1})\beta^{2}_{\tau}(\theta^{2},a^{2})\left[\sum_{s^{\prime},s\in{\mathcal{}S}}P_{{\boldsymbol{a}}}^{{\boldsymbol{z}}}(s^{\prime}|s)b(s|{\boldsymbol{\theta}})\right]\sigma({\boldsymbol{\theta}}).$

$b(s|{\boldsymbol{\theta}})$ depending only on the model (transition function
and initial belief), the next occupancy state $\sigma^{\prime}$ thus evolves
linearly w.r.t. (i) private decision rules $\beta^{1}_{\tau}$ and
$\beta^{2}_{\tau}$, and (ii) the occupancy state $\sigma$.

The $1$-Lipschitz-continuity holds because each component of vector
$\sigma_{\tau}$ is distributed over multiple components of $\sigma^{\prime}$.
Indeed, let us view two occupancy states as vectors
${\boldsymbol{x}},{\boldsymbol{y}}\in{\mathbb{R}}^{n}$, and their
corresponding next states under ${\boldsymbol{\beta}}_{\tau}$ as
$M{\boldsymbol{x}}$ and $M{\boldsymbol{y}}$, where $M\in{\mathbb{R}}^{m\times
n}$ is the corresponding transition matrix (i.e., which turns $\sigma$ into
$\sigma^{\prime}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$). Then,

$\displaystyle\lVert M{\boldsymbol{x}}-M{\boldsymbol{y}}\rVert_{1}$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm def}}}}{{=}}\sum_{j=1}^{m}\
\lvert\sum_{i=1}^{n}M_{i,j}(x_{i}-y_{i})\rvert$
$\displaystyle\leq\sum_{j=1}^{m}\sum_{i=1}^{n}\lvert
M_{i,j}(x_{i}-y_{i})\rvert$ (convexity of $\lvert\cdot\rvert$)
$\displaystyle=\sum_{j=1}^{m}\sum_{i=1}^{n}M_{i,j}\lvert x_{i}-y_{i}\rvert$
($\forall{i,j},\ M_{i,j}\geq 0$)
$\displaystyle=\sum_{i=1}^{n}\underbrace{\sum_{j=1}^{m}M_{i,j}}_{=1}\lvert
x_{i}-y_{i}\rvert$ ($M$ is a transition matrix)
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\lVert{\boldsymbol{x}}-{\boldsymbol{y}}\rVert_{1}.$

∎

####  D.1.3 Lipschitz-Continuity of $V^{*}$

The next two results demonstrate that, in the finite horizon setting, $V^{*}$
is Lipschitz-continuous (LC) in occupancy space, which allows defining LC
upper- and lower-bound approximations.

lemmalemVLinOcc At depth $\tau$,
$V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})$ is linear w.r.t.
$\sigma_{\tau}$ and ${\boldsymbol{\beta}}_{\tau:}$.

Note: This result in fact applies to any reward function of a general-sum POSG
with any number of agents (here $N$), e.g., to a Dec-POMDP. The following
proof handles the general case (with
${\boldsymbol{\beta}}_{\tau}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\langle\beta^{1}_{\tau},\dots,\beta^{N}_{\tau}\rangle$, and
${\boldsymbol{\beta}}_{\tau}({\boldsymbol{a}}|{\boldsymbol{\theta}})=\prod_{i=1}^{N}\beta^{i}_{\tau}(a^{i},\theta^{1})$).

###### Proof.

This property trivially holds for $\tau=H-1$ because

$\displaystyle V_{H-1}(\sigma_{H-1},{\boldsymbol{\beta}}_{H-1:})$
$\displaystyle=r(\sigma_{H-1},{\boldsymbol{\beta}}_{H-1})$
$\displaystyle=\sum_{s,{\boldsymbol{a}}}\left(\sum_{\boldsymbol{\theta}}Pr(s,{\boldsymbol{a}}|{\boldsymbol{\theta}})\sigma_{H-1}({\boldsymbol{\theta}})\right)r(s,{\boldsymbol{a}})$
$\displaystyle=\sum_{s,{\boldsymbol{a}}}\left(\sum_{\boldsymbol{\theta}}b(s|{\boldsymbol{\theta}}){\boldsymbol{\beta}}_{\tau}({\boldsymbol{a}}|{\boldsymbol{\theta}})\sigma_{H-1}({\boldsymbol{\theta}})\right)r(s,{\boldsymbol{a}})$
$\displaystyle=\sum_{s,{\boldsymbol{\theta}}}b(s|{\boldsymbol{\theta}})\sigma_{H-1}({\boldsymbol{\theta}})\left(\sum_{{\boldsymbol{a}}}{\boldsymbol{\beta}}_{\tau}({\boldsymbol{a}}|{\boldsymbol{\theta}})r(s,{\boldsymbol{a}})\right).$

Now, let us assume that the property holds for
$\tau+1\in\\{1\mathinner{\ldotp\ldotp}H-1\\}$. Then,

$\displaystyle V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})$
$\displaystyle=\sum_{s,{\boldsymbol{a}}}\Big{(}\sum_{\boldsymbol{\theta}}b(s|{\boldsymbol{\theta}}){\boldsymbol{\beta}}_{\tau}({\boldsymbol{a}}|{\boldsymbol{\theta}})\sigma_{\tau}({\boldsymbol{\theta}})\Big{)}r(s,{\boldsymbol{a}})+\gamma
V_{\tau+1}\left(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}),{\boldsymbol{\beta}}_{\tau+1:}\right)$
$\displaystyle=\sum_{s,{\boldsymbol{\theta}}}b(s|{\boldsymbol{\theta}})\sigma_{\tau}({\boldsymbol{\theta}})\Big{(}\sum_{{\boldsymbol{a}}}{\boldsymbol{\beta}}_{\tau}({\boldsymbol{a}}|{\boldsymbol{\theta}})r(s,{\boldsymbol{a}})\Big{)}+\gamma
V_{\tau+1}\left(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}),{\boldsymbol{\beta}}_{\tau+1:}\right).$

As

  * •

$T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ is linear in $\sigma_{\tau}$
(Section D.1.2) and

  * •

$V_{\tau+1}(\sigma_{\tau+1},{\boldsymbol{\beta}}_{\tau+1:})$ is linear in
$\sigma_{\tau+1}$ (induction hypothesis),

their composition,
$V_{\tau+1}(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}),{\boldsymbol{\beta}}_{\tau+1:})$,
is also linear in $\sigma_{\tau}$, and so is
$V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau:})$. Similarly,
$V_{\tau}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})$ is linear in
${\boldsymbol{\beta}}_{\tau}$ for any $\sigma_{\tau}$. ∎

*

###### Proof.

At depth $\tau$, the value of any behavioral strategy
${\boldsymbol{\beta}}_{\tau:}$ is bounded, independently of $\sigma_{\tau}$,
by

$\displaystyle V^{\max}_{\tau}$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}h_{\tau}r_{\max},\quad\text{where
}r_{\max}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\max_{s,{\boldsymbol{a}}}r(s,{\boldsymbol{a}}),\text{ and }$
$\displaystyle V^{\min}_{\tau}$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}h_{\tau}r_{\min},\quad\text{where
}r_{\min}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\min_{s,{\boldsymbol{a}}}r(s,{\boldsymbol{a}}).$

Thus, $V_{{\boldsymbol{\beta}}_{\tau:}}$ being a linear function defined over
a probability simplex (${\mathcal{}O}^{\sigma}_{\tau}$) (cf. Section D.1.3)
and bounded by $[V^{\min}_{\tau},V^{\max}_{\tau}]$, we can apply Horak-phd19’s
PhD thesis’ Lemma 3.5 (p. 33) Horak-phd19 to establish that it is also
$\lambda_{\tau}$-LC, i.e.,

$\displaystyle\lvert
V_{{\boldsymbol{\beta}}_{\tau:}}(\sigma)-V_{{\boldsymbol{\beta}}_{\tau:}}(\sigma^{\prime})\rvert$
$\displaystyle\leq\lambda_{\tau}\lVert\sigma-\sigma^{\prime}\rVert_{1}\quad(\forall\sigma,\sigma^{\prime}),$
$\displaystyle\text{with }\lambda_{\tau}$
$\displaystyle=\frac{V^{\max}_{\tau}-V^{\min}_{\tau}}{2}.$

Considering now optimal solutions, this means that, at depth $\tau$ and for
any $(\sigma,\sigma^{\prime})\in{\mathcal{}O}^{\sigma}_{\tau}$:

$\displaystyle V^{*}_{\tau}(\sigma)-V^{*}_{\tau}(\sigma^{\prime})$
$\displaystyle=\max_{\beta^{1}_{\tau:}}\min_{\beta^{2}_{\tau:}}V_{\tau}(\sigma,\beta^{1}_{\tau:},\beta^{2}_{\tau:})-\max_{\beta^{\prime
1}_{\tau:}}\min_{\beta^{\prime
2}_{\tau:}}V_{\tau}(\sigma^{\prime},\beta^{\prime 1}_{\tau:},\beta^{\prime
2}_{\tau:})$
$\displaystyle\leq\max_{\beta^{1}_{\tau:}}\min_{\beta^{2}_{\tau:}}\left[V_{\tau}(\sigma^{\prime},\beta^{1}_{\tau:},\beta^{2}_{\tau:})+\lambda_{\tau}\lVert\sigma-\sigma^{\prime}\rVert_{1}\right]-\max_{\beta^{\prime
1}_{\tau:}}\min_{\beta^{\prime
2}_{\tau:}}V_{\tau}(\sigma^{\prime},\beta^{\prime 1}_{\tau:},\beta^{\prime
2}_{\tau:})$
$\displaystyle=\lambda_{\tau}\lVert\sigma-\sigma^{\prime}\rVert_{1}.$

Symmetrically,
$V^{*}_{\tau}(\sigma)-V^{*}_{\tau}(\sigma^{\prime})\geq-\lambda_{\tau}\lVert\sigma-\sigma^{\prime}\rVert_{1}$,
hence the expected result:

$\displaystyle\lvert V^{*}_{\tau}(\sigma)-V^{*}_{\tau}(\sigma^{\prime})\rvert$
$\displaystyle\leq\lambda_{\tau}\lVert\sigma-\sigma^{\prime}\rVert_{1}.$

∎

As it will be used later, let us also present the following lemma.

######  Lemma 3.

Let us consider $\tau\in\\{0\mathinner{\ldotp\ldotp}H-1\\}$,
$\theta^{1}_{\tau}$, and $\psi^{2}_{\tau}$. Then
$\nu^{2}_{[\sigma^{c,1}_{\tau},\psi^{2}_{\tau}]}(\theta^{1}_{\tau})$ is
$\lambda_{\tau}$-LC in $\sigma^{c,1}_{\tau}(\cdot|\theta^{1}_{\tau})$.

Equivalently, we will also write that
$\nu^{2}_{[\sigma^{c,1}_{\tau},\psi^{2}_{\tau}]}$ is $\lambda_{\tau}$-LC in
$\sigma^{c,1}_{\tau}$ in vector-wise 1-norm, i.e.:

$\displaystyle{\boldsymbol{v}}{\lvert\nu^{2}_{[\sigma^{c,1}_{\tau},\psi^{2}_{\tau}]}-\nu^{2}_{[\tilde{\sigma}^{c,1}_{\tau},\psi^{2}_{\tau}]}\rvert}_{1}$
$\displaystyle\ \vec{\leq}\
\lambda_{\tau}{\boldsymbol{v}}{\lVert\sigma^{c,1}_{\tau}-\tilde{\sigma}^{c,1}_{\tau}\rVert}_{1},$

where (i) the absolute value of a vector is obtained by taking the absolute
value of each component; and (ii) the vector-wise 1-norm of a matrix is a
vector made of the 1-norm of each of its component vectors.

###### Proof.

For any $\theta^{1}_{\tau}$, $\sigma^{c,1}_{\tau}$ and $\psi^{2}_{\tau}$
induce a POMDP for Player $1$ from $\tau$ on, where (i) the state at any
$t\in\\{\tau\mathinner{\ldotp\ldotp}H-1\\}$ corresponds to a pair $\langle
s,\theta^{2}_{t}\rangle$, and (ii) the initial belief is derived from
$\sigma^{c,1}_{\tau}(\cdot|\theta^{1}_{t})$. The belief state at $t$ thus
gives:

$\displaystyle b_{\theta^{1}_{t}}(s,\theta^{2}_{t})$
$\displaystyle\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}Pr(s,\theta^{2}_{t}|\theta^{1}_{t})=\underbrace{Pr(s|\theta^{2}_{t},\theta^{1}_{t})}_{b^{\text{\sc
hmm}}_{\theta^{2}_{t},\theta^{1}_{t}}(s)}\cdot\underbrace{Pr(\theta^{2}_{t}|\theta^{1}_{t})}_{\sigma^{c,1}_{t}(\theta^{2}_{t}|\theta^{1}_{t})}.$

So,

  * •

the value function of any behavioral strategy $\beta^{1}_{\tau:}$ is linear at
$t$ in $b_{\theta^{1}_{t}}$, thus (in particular) in
$\sigma^{c,1}_{t}(\cdot|\theta^{1}_{t})$; and

  * •

the optimal value function is LC at $t$ also in $b_{\theta^{1}_{t}}$ (with the
same depth-dependent upper-bounding Lipschitz constant $\lambda_{t}$ as in the
proof of Section 3.2.1),555The proof process is similar. The only difference
lies in the space at hand, but without any impact on the resulting formulas.
thus (in particular) in $\sigma^{c,1}_{t}(\cdot|\theta^{1}_{t})$.

Using $t=\tau$, the optimal value function is
$\nu^{2}_{[\sigma^{c,1}_{\tau},\psi^{2}_{\tau}]}(\theta^{1}_{\tau})$, which is
thus $\lambda_{\tau}$-LC in $\sigma^{c,1}_{\tau}(\cdot|\theta^{1}_{\tau})$. ∎

###  D.2 Bounding Approximations of $V^{*}$, $W^{1,*}$ and $W^{2,*}$

####  D.2.1 $\overline{V}_{\tau}$ and $\underline{V}_{\tau}$

To find a form that could be appropriate for an upper bound approximation of
$V^{*}_{\tau}$, let us consider an os $\sigma_{\tau}$ and a single tuple
$\langle{\tilde{\sigma}_{\tau},\nu^{2}_{[\tilde{\sigma}_{\tau}^{c,1},\beta^{2}_{\tau:}]}}\rangle$,
and define $\zeta_{\tau}\stackrel{{\scriptstyle{\textrm{\rm
def}}}}{{=}}\sigma_{\tau}^{m,1}\tilde{\sigma}_{\tau}^{c,1}$. Then,

$\displaystyle V^{*}(\sigma_{\tau})$ $\displaystyle\leq
V^{*}(\zeta_{\tau})+\lambda_{\tau}\lVert\sigma_{\tau}-\zeta_{\tau}\rVert_{1}$
(LC, cf. Section 3.2.1)
$\displaystyle=V^{*}(\sigma_{\tau}^{m,1}\tilde{\sigma}_{\tau}^{c,1})+\lambda_{\tau}\lVert\sigma_{\tau}-\zeta_{\tau}\rVert_{1}$
$\displaystyle\leq\sigma_{\tau}^{m,1}\cdot\nu^{2}_{[\tilde{\sigma}_{\tau}^{c,1},\beta^{2}_{\tau:}]}+\lambda_{\tau}\lVert\sigma_{\tau}-\sigma_{\tau}^{m,1}\tilde{\sigma}_{\tau}^{c,1}\rVert_{1}.$
(Cvx, cf. Theorem 2.4)

Notes:

  * •

$\tilde{\sigma}^{m,1}_{\tau}$ does not appear in the resulting upper bound,
thus will not need to be specified.

  * •

For $\tau=H-1$, $\nu^{2}_{[\tilde{\sigma}_{\tau}^{c,1},\beta_{\tau:}^{2}]}$ is
a simple function of $r$, $\tilde{\sigma}_{\tau}^{c,1}$, $\beta_{\tau:}^{2}$,
and the dynamics of the system, as described in Eq. (9) of WigOliRoi-corr16.

From this, we can deduce the following appropriate forms of upper and
(symmetrically) lower bound function approximations for $V^{*}_{\tau}$:

$\displaystyle\overline{V}_{\tau}(\sigma_{\tau})$
$\displaystyle=\min_{\langle\tilde{\sigma}_{\tau}^{c,1},\langle\overline{\nu}^{2}_{\tau},\psi_{\tau:}^{2}\rangle\rangle\in\overline{{\mathcal{}J}}_{\tau}}\left[\sigma_{\tau}^{m,1}\cdot\overline{\nu}^{2}_{\tau}+\lambda_{\tau}\lVert\sigma_{\tau}-\sigma_{\tau}^{m,1}\tilde{\sigma}_{\tau}^{c,1}\rVert_{1}\right],\text{
and}$ $\displaystyle\underline{V}_{\tau}(\sigma_{\tau})$
$\displaystyle=\max_{\langle\tilde{\sigma}_{\tau}^{c,2},\langle\underline{\nu}^{1}_{\tau},\psi_{\tau:}^{1}\rangle\rangle\in\underline{{\mathcal{}J}}_{\tau}}\left[\sigma_{\tau}^{m,2}\cdot\underline{\nu}^{1}_{\tau}-\lambda_{\tau}\lVert\sigma_{\tau}-\sigma_{\tau}^{m,2}\tilde{\sigma}_{\tau}^{c,2}\rVert_{1}\right],$

which are respectively concave in $\sigma^{m,1}_{\tau}$ and convex in
$\sigma^{m,2}_{\tau}$, and which both exploit the Lipschitz continuity.

####  D.2.2 $\overline{W}_{\tau}$ and $\underline{W}_{\tau}$

Note: We discuss all depths from $0$ to $H-1$, even though we do not need
these approximations at $\tau=H-1$.

Let us first see how concavity-convexity properties affect $W_{\tau}^{*,1}$.

######  Lemma 4.

Considering that vectors $\nu^{2}_{[\sigma_{H}^{c,1},\beta_{H:}^{2}]}$ are
null vectors, we have, for all $\tau\in\\{0\mathinner{\ldotp\ldotp}H-1\\}$:

$\displaystyle W_{\tau}^{1,*}(\sigma_{\tau},\beta^{1}_{\tau})$
$\displaystyle=\min_{\beta^{2}_{\tau},\langle\beta_{\tau+1:}^{2},\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\rangle}\beta^{1}_{\tau}\cdot\Big{[}{r(\sigma_{\tau},\cdot,\beta^{2}_{\tau})}$
$\displaystyle\qquad+{\gamma
T^{1}_{m}(\sigma_{\tau},\cdot,\beta^{2}_{\tau})\cdot\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}}\Big{]}.$

###### Proof.

Considering that vectors $\nu^{2}_{[\sigma_{H}^{c,1},\beta^{2}_{H:}]}$ are
null vectors, we have, for all $\tau\in\\{0\mathinner{\ldotp\ldotp}H-1\\}$:

$\displaystyle W_{\tau}^{1,*}(\sigma_{\tau},\beta^{1}_{\tau})$
$\displaystyle=\min_{\beta^{2}_{\tau}}Q^{*}_{\tau}(\sigma_{\tau},\beta^{1}_{\tau},\beta^{2}_{\tau})=\min_{\beta^{2}_{\tau}}\left[r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma
V^{*}_{\tau+1}(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}))\right]$ (Line
below exploits Theorem 2.4 (p. 2.4) and $T^{1}_{c}$’s independence from
$\beta^{1}_{\tau}$ (Lemma 2).)
$\displaystyle=\min_{\beta^{2}_{\tau}}\left[r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma\min_{\langle\beta_{\tau+1:}^{2},\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\rangle}\left[T^{1}_{m}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})\cdot\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\right]\right]$
$\displaystyle=\min_{\beta^{2}_{\tau},\langle\beta_{\tau+1:}^{2},\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\rangle}\left[r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})\cdot\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\right]$
(Line below exploits $r$ and $T^{1}_{m}$’s linearity in $\beta^{1}_{\tau}$
(Lemma 1).)
$\displaystyle=\min_{\beta^{2}_{\tau},\langle\beta_{\tau+1:}^{2},\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\rangle}{\beta^{1}_{\tau}}^{\top}\\!\cdot\Big{[}{r(\sigma_{\tau},\cdot,\beta^{2}_{\tau})}$
$\displaystyle\qquad+\gamma
T^{1}_{m}(\sigma_{\tau},\cdot,\beta^{2}_{\tau})\cdot\nu^{2}_{{[T^{1}_{c}(\sigma_{\tau},\beta^{2}_{\tau}),\beta^{2}_{\tau+1:}]}}\Big{]}.$

∎

Note that, since $V^{*}_{H}=0$, $\tau=H-1$ is a particular case which can be
simply re-written:

$\displaystyle W_{\tau}^{1,*}(\sigma_{\tau},\beta^{1}_{\tau})$
$\displaystyle=\min_{\beta^{2}_{\tau}}{\beta^{1}_{\tau}}^{\top}\\!\cdot
r(\sigma_{\tau},\cdot,\beta^{2}_{\tau}).$

To find a form that could be appropriate for an upper bound approximation of
$W^{*,1}_{\tau}$, let us now consider an os $\sigma_{\tau}$ and a single tuple
$\langle{\tilde{\sigma}_{\tau},\tilde{\beta}^{2}_{\tau},\nu^{2}_{[T^{1}_{c}(\tilde{\sigma}_{\tau},\tilde{\beta}^{2}_{\tau}),\tilde{\beta}_{\tau+1:}^{2}]}}\rangle$.
Then,

$\displaystyle W_{\tau}^{1,*}(\sigma_{\tau},\beta^{1}_{\tau})$
$\displaystyle=\min_{\beta^{2}_{\tau}}\left[r(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau})+\gamma
V^{*}_{\tau+1}(T(\sigma_{\tau},{\boldsymbol{\beta}}_{\tau}))\right]$ (37)
$\displaystyle\leq
r(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})+\gamma
V^{BR,1}_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})|\tilde{\beta}_{\tau+1:}^{2})$
(38) (Use $\tilde{\beta}^{2}_{\tau}$ & $\tilde{\beta}^{2}_{\tau+1:}$ instead
of mins) (where
$V^{BR,1}_{\tau+1}(T(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})|\tilde{\beta}_{\tau+1:}^{2})$
is the value of 1’s best response to $\tilde{\beta}^{2}_{\tau+1:}$ if in
$T(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})$)
$\displaystyle=r(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})\cdot\underbrace{\nu^{2}_{[T^{1}_{c}(\sigma^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau}),\tilde{\beta}_{\tau+1:}^{2}]}}$
(39) (Lem. 3 of WigOliRoi-corr16) $\displaystyle\leq
r(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\beta^{1}_{\tau},\tilde{\beta}^{2}_{\tau})\cdot\Big{(}{\nu^{2}_{[T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau}),\tilde{\beta}_{\tau+1:}^{2}]}}$
(41) $\displaystyle\qquad\qquad{+\lambda_{\tau+1}\cdot{\boldsymbol{v}}{\lVert
T^{1}_{c}(\sigma^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})-T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})\rVert}_{1}}\Big{)}$
(42) (Lemma 3: $\lambda_{\tau+1}$-LC of
$\nu^{2}_{[T^{1}_{c}(\sigma^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau}),\tilde{\beta}_{\tau+1:}^{2}]}$)
$\displaystyle={\beta^{1}_{\tau}}^{\top}\\!\cdot\Big{[}r(\sigma_{\tau},\cdot,\tilde{\beta}^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\cdot,\tilde{\beta}^{2}_{\tau})\cdot\Big{(}{\nu^{2}_{[T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau}),\tilde{\beta}_{\tau+1:}^{2}]}}$
(43) $\displaystyle\qquad\qquad{+\lambda_{\tau+1}\cdot{\boldsymbol{v}}{\lVert
T^{1}_{c}(\sigma^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})-T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})\rVert}_{1}}\Big{)}\Big{]}$
(44) (Linearity in $\beta^{1}_{\tau}$)
$\displaystyle={\beta^{1}_{\tau}}^{\top}\\!\cdot\Big{[}r(\sigma_{\tau},\cdot,\tilde{\beta}^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\cdot,\tilde{\beta}^{2}_{\tau})\cdot{\nu^{2}_{[T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau}),\tilde{\beta}_{\tau+1:}^{2}]}}$
(46) $\displaystyle\qquad\qquad{+\gamma\lambda_{\tau+1}\cdot\lVert
T(\sigma_{\tau},\cdot,\tilde{\beta}^{2}_{\tau})-T^{1}_{m}(\sigma_{\tau},\cdot,\tilde{\beta}^{2}_{\tau})T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})\rVert_{1}}\Big{]}$
(47) (Alternative writing)

From this, we can deduce the following appropriate forms of (i) upper bounding
approximation for $W^{1,*}_{\tau}$ and (ii) (symmetrically) of lower bound
approximation for $W^{2,*}_{\tau}$:

$\displaystyle\overline{W}_{\tau}(\sigma_{\tau},\beta^{1}_{\tau})$
$\displaystyle=\min_{\langle\tilde{\sigma}^{c,1}_{\tau},\beta^{2}_{\tau},\overline{\nu}^{2}_{\tau+1}\rangle\in\overline{\mathcal{I}}_{\tau}}{\beta^{1}_{\tau}}^{\top}\cdot\Big{[}{r(\sigma_{\tau},\cdot,\beta^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\cdot,\beta^{2}_{\tau})\cdot\overline{\nu}^{2}_{\tau+1}}$
$\displaystyle\qquad+\gamma\lambda_{\tau+1}\cdot\lVert
T(\sigma_{\tau},\cdot,\beta^{2}_{\tau})-T^{1}_{m}(\sigma_{\tau},\cdot,\beta^{2}_{\tau})T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\beta^{2}_{\tau})\rVert_{1}\Big{]},\text{
and}$ $\displaystyle\underline{W}_{\tau}(\sigma_{\tau},\beta^{2}_{\tau})$
$\displaystyle=\max_{\langle\tilde{\sigma}^{c,2}_{\tau},\beta^{1}_{\tau},\underline{\nu}^{1}_{\tau+1}\rangle\in\underline{\mathcal{I}}_{\tau}}{\beta^{2}_{\tau}}^{\top}\cdot\Big{[}{r(\sigma_{\tau},\beta^{1}_{\tau},\cdot)+\gamma
T^{2}_{m}(\sigma_{\tau},\beta^{1}_{\tau},\cdot)\cdot\underline{\nu}^{1}_{\tau+1}}$
$\displaystyle\qquad\qquad-\gamma\lambda_{\tau+1}\cdot\lVert
T(\sigma_{\tau},\beta^{1}_{\tau},\cdot)-T^{2}_{m}(\sigma_{\tau},\beta^{1}_{\tau},\cdot)T^{2}_{c}(\tilde{\sigma}^{c,2}_{\tau},\beta^{1}_{\tau})\rVert_{1}\Big{]},$

where $\overline{\nu}^{2}_{\tau+1}$ and $\underline{\nu}^{1}_{\tau+1}$
respectively upper and lower bound the actual vectors associated to the
players’ future strategies (resp. of $2$ and $1$).

Again, $\tau=H-1$ is a particular case where only the reward term is
preserved.

This constitutes the proof to the following proposition

*

###  D.3 Related Operators

####  D.3.1 Selection Operator: Solving for $\beta^{1}_{\tau}$ as an LP

######  Proposition D.1.

Using now a distribution $\psi^{2}_{\tau}$ over tuples
$w=\langle\tilde{\sigma}^{c,1}_{\tau},\beta^{2}_{\tau},\overline{\nu}^{2}_{\tau+1}\rangle\in\overline{\mathcal{I}}^{1}_{\tau}$,
the corresponding upper-bounding value for “profile”
$\langle\beta^{1}_{\tau},\psi^{2}_{\tau}\rangle$ when in $\sigma_{\tau}$ can
be written as an expectancy:

$\displaystyle{\beta^{1}_{\tau}}^{\top}\cdot
M^{\sigma_{\tau}}\cdot\psi^{2}_{\tau},$

where $M^{\sigma_{\tau}}$ is an
$|\Theta^{1}_{\tau}\times{\mathcal{}A}^{1}|\times|\overline{\mathcal{I}}^{1}_{\tau}|$
matrix.

###### Proof.

From the right-hand side term in (Equation 43), the upper-bounding value
associated to $\sigma_{\tau}$, $\beta^{1}_{\tau}$ and a tuple
$\langle\tilde{\sigma}^{c,1}_{\tau},\beta^{2}_{\tau},\overline{\nu}^{2}_{\tau+1}\rangle\in\overline{\mathcal{I}}^{1}_{\tau}$
can be written:

$\displaystyle{\beta^{1}_{\tau}}^{\top}\\!\cdot\Big{[}r(\sigma_{\tau},\cdot,\beta^{2}_{\tau})+\gamma
T^{1}_{m}(\sigma_{\tau},\cdot,\beta^{2}_{\tau})\cdot\Big{(}\overline{\nu}^{2}_{\tau+1}{+\lambda_{\tau+1}\cdot{\boldsymbol{v}}{\lVert
T^{1}_{c}(\sigma^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})-T^{1}_{c}(\tilde{\sigma}^{c,1}_{\tau},\tilde{\beta}^{2}_{\tau})\rVert}_{1}}\Big{)}\Big{]}.$

Using now a distribution $\psi^{2}_{\tau}$ over tuples
$w=\langle\tilde{\sigma}^{c,1}_{\tau},\beta^{2}_{\tau},\overline{\nu}^{2}_{\tau+1}\rangle\in\overline{\mathcal{I}}^{1}_{\tau}$,
the corresponding upper-bounding value for “profile”
$\langle\beta^{1}_{\tau},\psi^{2}_{\tau}\rangle$ when in $\sigma_{\tau}$ can
be written as an expectancy: