HSVI Can Solve Zero-Sum Partially Observable Stochastic Games

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. Note: POSGs are equivalent to the large class of “well-behaved” EFGs as defined by [28].

2. As discussed in the following, due to global-consistency issues, this game is not equivalent to the original zs-POSG.

3. We 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.

4. Note that the same distinction between two possible transformations exists for Dec-POMDPs that are translated either in Occupancy MDPs or in Non-Observable MDPs [14].

5. In the Dec-POMDP setting, assuming that decision rules are public is valid because agents collaborate.

6. The proof process is similar. The only difference lies in the space at hand, but without any impact on the resulting formulas.

This research was funded, in whole or in part, by ANR Project PLASMA (ANR-19-CE23-0018). A CC-BY public copyright license has been applied by the authors to the present document and will be applied to all subsequent versions up to the Author Accepted Manuscript arising from this submission, in accordance with the Grant’s open access conditions. https://creativecommons.org/licenses/by/4.0/.

Authors and Affiliations

1. INSA Lyon and Inria, CITI, Universite de Lyon, 69621, Villeurbanne, France

   Aurélien Delage

2. INRIA, CNRS, LORIA, Universite de Lorraine, 54000, Villers-lès-Nancy, France

   Olivier Buffet

3. Bernoulli Institute for Mathematics, Computer Science and Artificial Intelligence, University of Groningen, Broerstraat 5, 9712, CP, Groningen, The Netherlands

   Jilles S. Dibangoye

4. University of New South Wales, Sidney, 2052, Australia

   Abdallah Saffidine

Corresponding author

Correspondence to Aurélien Delage.

Conflict of interest

The authors declare that they have no conflict of interest.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work has been conducted while Jilles Dibangoye was at INSA Lyon.

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), Table 4 and Table 5 to, respectively, sum up the notations and abbreviations 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;

\(\textit{PWLCv}\):

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

\(\perp \!\!\! \perp \):

the function being independent of the variable;

\(\lnot 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.

Appendix B Background

1.1 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'|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 [14, Theorem 1].

Proposition 12

(originally stated on page 7) \(\sigma _{{\varvec{\beta }}_{0:\tau -1}}\), together with \({\varvec{\beta }}_\tau \), is a sufficient statistic to compute (i) the next os, \(T(\sigma _{{\varvec{\beta }}_{0:\tau -1}},{\varvec{\beta }}_\tau ) {\mathop {=}\limits ^{\tiny {\text {def}}}}\sigma _{{\varvec{\beta }}_{0:\tau }}\), and (ii) the expected reward at \(\tau \): \(r(\sigma _{{\varvec{\beta }}_{0:\tau -1}},{\varvec{\beta }}_\tau ) {\mathop {=}\limits ^{\tiny {\text {def}}}}{{\,\mathrm{\mathbb {E}}\,}}\left[ R_\tau \mid {\varvec{\beta }}_{0:\tau -1} \oplus {\varvec{\beta }}_\tau \right] \), where \(\oplus \) denotes a concatenation.

Proof

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

(where \(b(s \mid {\varvec{\theta }}_\tau )\) is the belief over states obtained by a usual HMM filtering process)

\(\sigma _{ {\varvec{\beta }}_{0:\tau } }\) can thus be computed from \(\sigma _{{\varvec{\beta }}_{0:\tau -1}}\) and \({\varvec{\beta }}_\tau \) without explicitly using \({\varvec{\beta }}_{0:\tau -1}\) or earlier occupancy states.

Then, let us compute the expected reward at \(\tau \) given \({\varvec{\beta }}_{0:\tau }\):

The expected reward at \(\tau \) can thus be computed from \(\sigma _{{\varvec{\beta }}_{0:\tau -1}}\) and \({\varvec{\beta }}_\tau \) without explicitly using \({\varvec{\beta }}_{0:\tau -1}\) or earlier occupancy states. \(\square \)

Appendix C Occupancy Markov Games: Definition and Preliminary Properties

1.1 C.1 Properties of \(V^*\)

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

1.1.1 C.1.1 \(V^*\) is Not Linear in \(\beta \) (Behavioral Strategies)

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

Let us then consider two particular behavioral strategies:

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:

Let us now consider their linear combination \(\beta ^\pm {\mathop {=}\limits ^{\tiny {\text {def}}}}\frac{1}{2}\beta ^+ + \frac{1}{2} \beta ^-\):

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:

This confirms that, in a POMDP, the value is not linear in the space of behavioral strategies. As a consequence, in a zs-POSG, the value is not (bi)linear in the spaces of behavioral strategies of both players.

1.1.2 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 \le \tau '\), let \({\varvec{\mu }}_{0:\tau '-1|\sigma _\tau \rangle }\) denote a mixed strategy profile that is defined over \(0:\tau '-1\), and induces \(\sigma _\tau \) at time \(\tau \). We will also write that it is compatible with \(\sigma _\tau \). Then, to complete a given mixed prefix strategy \({\varvec{\mu }}_{0:\tau '-1|\sigma _\tau \rangle }\) (here \(\tau =\tau '\)), 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}\),

This is the set of mixed strategies compatible with \(\sigma _\tau \).

Lemma 2

\(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}\),

(because both mixed strategies are compatible with \(\sigma _\tau \) (eq. C1, p. 35):)

Equation C1 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}\). \(\square \)

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 ,{\varvec{\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=\lnot i\)). Then, \(M^i_{|T(\sigma _\tau ,{\varvec{\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 \):

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

Using the previous results, one can show that von Neumann’s minimax theorem applies in any subgame, allowing to swap \(\max \) and \(\min \) operators.

Theorem 3

(originally stated on page 10) The subgame defined in Eq. (3) admits a unique NEV

Proof

For any occupancy state \(\sigma _\tau \),

\(\square \)

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\).

Theorem 4

(originally stated on page 10) \(V_\tau ^*(\sigma _\tau )\) satisfies the following functional equation:

Proof

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

(\(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 )\):)

(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:)

(merging both mins (and with explanations thereafter):)

(since ignoring the opponent’s decision rule does not influence the expected return:)

(using again the minimax theorem’s equivalence between maximin and minimax on an appropriate game:)

(merging both maxs (and with explanations thereafter):)

(again with the equivalence property discussed before the lemma:)

More precisely, line C5 (and, similarly, line C7) is obtained by observing that

• minimizing over both (i) \(\beta ^2_\tau \) and (ii) \(\mu ^2\) constrained by \(\sigma _\tau \) and \({\varvec{\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 C6 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. \(\square \)

Appendix D Solving zs-OMGs

1.1 D.1 Preliminary Properties

1.1.1 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 afterward.

Lemma 3

\(T^{1}_m(\sigma _\tau , {\varvec{\beta }}_\tau )\) is linear in \(\sigma _\tau \), \(\beta ^1_\tau \), and \(\beta ^2_\tau \).

Proof

\(\square \)

Lemma 4

\(T^{1}_c(\sigma _\tau , {\varvec{\beta }}_\tau )\) is independent of \(\beta ^1_\tau \) and \(\sigma ^{m,1}_\tau \).

Proof

See [45], Lemma 4.2.3. \(\square \)

1.1.2 D.1.2 Linearity and Lipschitz-continuity of \(T (\sigma _\tau , \beta ^1_\tau , \beta ^2_\tau )\)

Lemma 5

At depth \(\tau \), \(T(\sigma _\tau ,{\varvec{\beta }}_\tau )\) is linear in \(\beta ^1_\tau \), \(\beta ^2_\tau \), and \(\sigma _\tau \), where \({\varvec{\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 '_\tau \):

Proof

Let \(\sigma \) be an occupancy state at time \(\tau \) and \({\varvec{\beta }}_\tau \) be a decision rule.

Then, as seen in the proof of Theorem 1, the next occupancy state \(\sigma ' = T(\sigma ,{\varvec{\beta }}_\tau )\) satisfies, for any \(s'\) and \(({\varvec{\theta }},{\varvec{a}},{\varvec{z}})\):

\(b(s|{\varvec{\theta }})\) depending only on the model (transition function and initial belief),

the next occupancy state \(\sigma '\) 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 '\).

Indeed, let us view two occupancy states as vectors \({\varvec{x}},{\varvec{y}}\in {{\mathbb {R}}}^n\), and their corresponding next states under \({\varvec{\beta }}_\tau \) as \(M {\varvec{x}}\) and \(M {\varvec{y}}\), where \(M \in {{\mathbb {R}}}^{m\times n}\) is the corresponding transition matrix (i.e., which turns \(\sigma \) into \(\sigma ' {\mathop {=}\limits ^{\tiny {\text {def}}}}T(\sigma _\tau ,{\varvec{\beta }}_\tau )\)).

Then,

\(\square \)

1.1.3 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.

Lemma 6

At depth \(\tau \), \(V_\tau (\sigma _\tau ,{\varvec{\beta }}_{\tau :})\) is linear w.r.t. \(\sigma _\tau \) and \({\varvec{\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 \({\varvec{\beta }}_\tau {\mathop {=}\limits ^{\tiny {\text {def}}}}\langle \beta ^1_\tau , \dots , \beta ^N_\tau \rangle \), and \({\varvec{\beta }}_\tau ({\varvec{a}}|{\varvec{\theta }}) = \prod _{i=1}^N \beta ^i_\tau (a^i,\theta ^1)\)).

Proof

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

Now, let us assume that the property holds for .

Then,

As

• \(T(\sigma _\tau ,{\varvec{\beta }}_\tau )\) is linear in \(\sigma _\tau \) (Lemma 5) and

• \(V_{\tau +1}(\sigma _{\tau +1}, {\varvec{\beta }}_{\tau +1:})\) is linear in \(\sigma _{\tau +1}\) (induction hypothesis),

their composition, \(V_{\tau +1} ( T (\sigma _\tau ,{\varvec{\beta }}_\tau ), {\varvec{\beta }}_{\tau +1:} )\), is also linear in \(\sigma _\tau \), and so is \(V_\tau (\sigma _\tau ,{\varvec{\beta }}_{\tau :})\). Similarly, \(V_\tau (\sigma _\tau ,{\varvec{\beta }}_\tau )\) is linear in \({\varvec{\beta }}_\tau \) for any \(\sigma _\tau \). \(\square \)

Theorem 5

(originally stated on page 9)

Let \(h_{\tau } {\mathop {=}\limits ^{\tiny {\text {def}}}}\frac{1-\gamma ^{H-\tau }}{1-\gamma }\) (or \(h_{\tau } {\mathop {=}\limits ^{\tiny {\text {def}}}}H-\tau \) if \(\gamma =1\)).

Then \(V^*_\tau (\sigma _\tau )\) is \(\lambda _{\tau }\)-Lipschitz continuous in \(\sigma _\tau \) at any depth , where \(\lambda _{\tau } = \frac{1}{2} h_{\tau } \left( r_{\max } - r_{\min } \right) \).

Proof

At depth \(\tau \), the value of any behavioral strategy \({\varvec{\beta }}_{\tau :}\) is bounded, independently of \(\sigma _\tau \), by

Thus, \(V_{{\varvec{\beta }}_{\tau :}}\) being a linear function defined over a probability simplex (\({{\mathcal {O}}}^\sigma _\tau \)) (cf.Appendix 1) and bounded by \([V^{\min }_\tau ,V^{\max }_\tau ]\), we can apply Horák’s PhD thesis’ Lemma 3.5 (p. 33) [20] to establish that it is also \(\lambda _{\tau }\)-LC, i.e.,

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

Symmetrically, \(V^*_\tau (\sigma ) - V^*_\tau (\sigma ') \ge -\lambda _{\tau } \Vert \sigma -\sigma '\Vert _{1}\), hence the expected result:

\(\square \)

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

Lemma 7

Let us consider , \(\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.:

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 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:

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 Theorem 5),^{Footnote 6} 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 )\). \(\square \)

1.2 D.2 Bounding Approximations of \(V^*\), \(W^{1,*}\) and \(W^{2,*}\)

1.2.1 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 {\mathop {=}\limits ^{\tiny {\text {def}}}}\sigma _\tau ^{m,1}{\tilde{\sigma }}_\tau ^{c,1}\). Then,

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 [47].

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

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

1.2.2 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 8

Considering that vectors \(\nu ^2_{[\sigma _{H}^{c,1},\beta _{H:}^2]}\) are null vectors, we have, for all :

Proof

Considering that vectors \(\nu ^2_{[\sigma _{H}^{c,1},\beta ^2_{H:}]}\) are null vectors, we have, for all :

(Line below exploits Theorem 2 (p. 8) and \(T^{1}_c\)’s independence from \(\beta ^1_\tau \) (Lemma 4).)

(Line below exploits r and \(T^{1}_m\)’s linearity in \(\beta ^1_\tau \) (Lemma 3).)

\(\square \)

Note that, since \(V^*_H=0\), \(\tau =H-1\) is a particular case which can be simply re-written:

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,

(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 )\))

(Lemma 3 of [47])

(D12)

(Lemma 7: \(\lambda _{\tau +1}\)-LC of \(\nu ^2_{[T^{1}_c(\sigma ^{c,1}_\tau , {\tilde{\beta }}^2_\tau ), {\tilde{\beta }}_{\tau +1:}^2]}\))

(D13)

(Linearity in \(\beta ^1_\tau \))

(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 \):

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

Proposition 13

(originally stated on page 11) 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,

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

1.3 D.3 Related Operators

1.3.1 D.3.1 Selection Operator: Solving for \(\beta ^1_\tau \) as an LP

Proposition 14

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:

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 (Eq. D13), 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:

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:

(where x[w] denotes the field x of tuple w)

where \(M^{\sigma _\tau }\) is an \(|\Theta ^1_\tau \times {{\mathcal {A}}}^1| \times |\overline{\mathcal {I}}^1_\tau |\) matrix. \(\square \)

For implementation purposes, using Eqs. (2) and (D9) (to develop, respectively, \(r(\cdot ,\cdot ,\cdot )\) and \(T^{1}_m(\cdot ,\cdot ,\cdot )\)), we can derive the expression of a component, i.e., the upper-bounding value if \(a^1\) is applied in \(\theta ^1_\tau \) while w is chosen:

Then, solving \(\max _{\beta ^1_\tau } {\overline{W}}_{\tau }(\sigma _\tau , \beta ^1_\tau )\) can be rewritten as solving a zero-sum game where pure strategies are:

• for Player 1, the choice of not 1, but \(|\Theta ^1_\tau |\) actions (among \(|{{\mathcal {A}}}^1|\)) and,

• for Player 2, the choice of 1 element of \(\overline{\mathcal {I}}^1_\tau \).

One can view it as a Bayesian game with one type per history \(\theta ^1_\tau \) for 1, and a single type for 2.

With our upper bound, \(\max _{\beta ^1_\tau } {\overline{W}}_{\tau }(\sigma _\tau ,\beta ^1_\tau )\) can thus be solved as the LP:

whose dual LP is given by

As can be noted, \(M^{\sigma _\tau }\)’s columns corresponding to 0-probability histories \(\theta ^1_\tau \) in \(\sigma ^{m,1}_\tau \) are empty (full of zeros), so that the corresponding decision rules (for these histories) are not relevant and can be set arbitrarily. The actual implementation thus ignores these histories, whose corresponding decision rules also do not need to be stored.

Remark 2

(Interpretation of \(M^{\sigma _\tau }\)) The content of this matrix can be interpreted by noting that, a given w containing a behavioral strategy \(\beta ^2_{\tau :H-1}\) and an os\({\tilde{\sigma }}_\tau \), a pair \(\langle w, \theta ^1_\tau \rangle \) induces a POMDP for player 1 whose state space is made of pairs \(\langle s, \theta ^2_t\rangle \), and whose initial belief \(b_\tau \) depends on \({\tilde{\sigma }}_\tau \) and \(\theta _\tau ^1\). Solving this POMDP amounts to finding a best response of player 1 to \(\beta _{\tau :H-1}^2\). In this setting, an element \(M^{\sigma _\tau }_{((\theta _\tau ^1,a^1),w)}\) is an upper-bound of the optimal (POMDP) Q-value when player 1 performs \(a^1\) while facing \(b_\tau \) (\(Q^*_{\text {POMDP}}(b_\tau ,a^1)\)).

1.3.2 D.3.2 Upper Bounding \(\nu ^2_{[\sigma ^{c,1}_\tau ,\psi ^{2}_{\tau }]}\)

Adding a new complete tuple to \(\overline{\mathcal {I}}^1_\tau \) requires a new vector \(\overline{\nu }^2_{\tau }\) that upper bounds the vector \(\nu ^2_{[\sigma ^{c,1}_\tau ,\psi ^2_\tau ]}\) associated to the strategy induced by \(\psi ^2_\tau \). We can obtain one in a recursive manner (not solving the induced POMDP).

Proposition 15

For each \(\psi ^2_\tau \) obtained as the solution of the aforementioned (dual) LP in \(\sigma _\tau \), and each \(\theta ^1_\tau \), \(\nu ^2_{[\sigma ^{c,1}_{\tau }, \psi ^2_{\tau }]}(\theta ^1_\tau )\) is upper-bounded by a value \(\overline{\nu }^2_{\tau }(\theta ^1_\tau )\) that depends on vectors \(\overline{\nu }^2_{\tau +1}\) in the support of \(\psi ^2_\tau \). In particular, if \(\theta ^1_\tau \in Supp (\sigma ^{m,1}_\tau )\), we have:

Proof

For a newly derived \(\psi ^2_\tau \), as \(\nu ^2_{[\sigma ^{c,1}_\tau , \psi ^2_\tau ]}(\theta ^1_\tau )\) is the value of 1’s best action (\(\in {{\mathcal {A}}}^1\)) if 1 (i) observes \(\theta ^1_\tau \), while in \(\sigma ^{c,1}_\tau \) and (ii) 2 plays \(\psi ^2_\tau \), we have:

(where \(\sigma ^{c,1}_{\tau +1}=T^{1}_c(\sigma ^{c,1}_\tau , \beta ^2_\tau [w])\) (Lemma 4, p. 39)

then, as \(\nu ^2_{[\sigma ^{c,1}_{\tau +1}, \psi ^2_{\tau +1}[w]]}\) is \(\lambda _{\tau +1}\)-LC in (any) \(\sigma ^{c,1}_{\tau +1}\) (Lemma 7),

\(\square \)

1.3.3 D.3.3 Strategy Conversion

Firstly, we give details regarding solutions of Dual LPs (Eq. 7) inducing behavioral strategies. As suggested in Sect. 3.2.2, one can show by induction that for any timestep \(\tau \), each \(\psi _{\tau }^2\) is actually equivalent to an element of \(\Delta ({{\mathcal {B}}}_{\tau :}^2)\). The following lemma shows that for any timestep \(\tau \), each element of \(\Delta ({{\mathcal {B}}}_{\tau :}^2)\) induces an element of \({{\mathcal {B}}}_{\tau :}^2\).

Lemma 9

Each \(\psi _{\tau }^i \in \Delta {({{\mathcal {B}}}_{\tau :}^i)}\) induces a behavioral strategy. More precisely, we prove that (i) there is a natural injection from the set \({{\mathcal {B}}}_{\tau :}^i\) to the set of distributions \(\Delta ({{\mathcal {B}}}_{\tau :}^i)\) and (ii) there is a surjection from the set \(\Delta ({{\mathcal {B}}}_{\tau :}^i)\) to \({{\mathcal {B}}}_{\tau :}^i\).

Proof

By induction on \(\tau \in \{0,\dots ,H-1\}\), we prove that \(\cup _{t=\tau }^H {{\mathcal {B}}}_t^i \subset \cup _{t=\tau }^H \Delta ({{\mathcal {B}}}^i_t)\). Firstly, for \(\tau = H-1\), for all \( \beta _{H-1} \in {{\mathcal {B}}}_{H-1}\), one can pick the degenerate distribution \(\psi _{H-1} = \beta _{H-1}\) which is in \(\Delta ({{\mathcal {B}}}^i_{H-1})\). Next, assume that \(\cup _{t=\tau +1}^{H-1} {{\mathcal {B}}}_{t}^i \subset \cup _{t=\tau +1}^{H-1} \Delta ({{\mathcal {B}}}^i_{t})\) for some \(\tau \in \{0,\dots ,H-2\}\), then for all \(\beta _{\tau :H-1},\ \beta _{\tau :H-1} = \beta _\tau \oplus \beta _{\tau +1:H-1}\). By the induction hypothesis, there is \(\psi _{\tau +1:H-1} \in \Delta ({{\mathcal {B}}}_{\tau +1:H-1})\) equal to \(\beta _{\tau +1:H-1}\). Thus, we define \(\psi _{\tau :H-1} = \beta _{\tau } \oplus \psi _{\tau +1:H-1} = \beta _\tau \oplus \beta _{\tau +1:H-1} = \beta _{\tau :H-1}\) which is in \({{\mathcal {B}}}_{\tau :H-1}\). From this follows a natural injection from the behavioral strategies’ set to the set of distributions over behavioral strategies.

The surjection from \(\Delta ({{\mathcal {B}}}_{\tau :}^i)\) to \({{\mathcal {B}}}_{\tau :}^i\) is given by the realization weight computation algorithm detailed in Algorithm 2. \(\square \)

As discussed in Appendix D.3.3, no effort is required to extract a solution strategy for a player from the lower bound (for 1) or the upper bound (for 2), but that strategy is in an unusual recursive form. We will here see (in the finite horizon setting) how to derive a (unique) equivalent behavioral strategy \(\beta ^i_{0:}\) using realization weights [23] in intermediate steps. To that end, we first define these realization weights in the case of a behavioral strategy (rather than for a mixed strategy as done by Koller et al.) and present some useful properties.

About Realization Weights

Let us denote \(rw^i(a^i_0, z^i_1, a^i_1, \dots , a^i_\tau )\) the realization weight (RW) of sequence \(a^i_0, z^i_1, a^i_1,\) \(\dots , a^i_\tau \) under strategy \(\beta ^i_{0:}\), defined as

This definition already leads to useful results such as:

and

We now extend Koller et al.’s definition by introducing conditional realization weights, where the realization weight of a suffix sequence is “conditioned” on a prefix sequence:

As can be noted, this definition only requires the knowledge of a partial strategy \(\beta ^i_{\tau :}\) rather than a complete strategy \(\beta ^i_{0:}\).

Mixing Realization Weights

Let \(\tau '\ge \tau +1\), and \(rw^i[w]\) denote the realization weights of some element w at \(\tau +1\). Then, for some \(\psi ^i_\tau \), we have

From \(w^i_0\) to \(\beta ^i_{0:}\)

Extracting \(\beta ^i_{0:}\) from \(w^i_0\)

Full size image

Using the above results, function Extract in Algorithm 2 derives a behavioral strategy \(\beta ^i_{0:}\) equivalent to the recursive strategy induced by some tuple \(w^i_0\) in 3 steps as follows:

1. 1.

   From \(w^i_0\) to \(rw(\theta ^i_{0:H-1}, a^i_{H-1})\) (\(\forall (\theta ^i_{0:H-1}, a^i_{H-1})\)) — These (classical) realization weights are obtained by recursively going through the directed acyclic graph describing the recursive strategy, computing full length (conditional) realization weights \(rw(\theta ^i_{t:H-1}, a^i_{H-1} | \theta ^i_{0:t})\) (for \(t=H-1\) down to 0). When in a leaf node, at depth \(H-1\), the initialization is given by Eq. D20 when \(\tau =\tau '=H-1\):

   $$\begin{aligned} rw^i(a^i_{H-1} | a^i_0, \dots , z^i_{H-1})&{\mathop {=}\limits ^{\tiny {\text {def}}}}\prod _{t={H-1}}^{{H-1}} \beta ^i(a^i_t | a^i_0, \dots , z^i_t) \\&= \beta ^i(a^i_{H-1} | a^i_0, \dots , z^i_{H-1}). \end{aligned}$$

   Then, in the backward phase, we can compute full length realization weights \(rw(\theta ^i_{t+1:H-1}, a^i_{H-1} | \theta ^i_{0:t})\) with increasingly longer suffixes (thus shorter prefixes) using (i) Eq. D23 (in function FRecGetRWMix, line 25) to “mix” several strategies using the distribution \(\psi ^i_t\) attached to the current w, and (ii) Eq. D21, with \(\tau '=H-1\), (in function FRecGetRWCat, line 16) to concatenate the behavioral decision rule \(\beta ^i_t\) attached to the current w in front of the strategy induced by the distribution \(\psi ^i_t\) also attached to w. Note: Memoization can here be used to avoid repeating the same computations.

2. 2.

   Retrieving (classical) realization weights \(rw(\theta ^i_{0:t}, a^i_t | -)\) (\(\forall t\)) — We can now compute realization weights \(rw(\theta ^i_{0:t}, a^i_t | -)\) for all t’s using Eq. D19 (line 6).

3. 3.

   Retrieving behavioral decision rules \(\beta ^i_t\) — Applying Equation  D16 (line 9) then provides the expected behavioral decision rules.

In practice, lossless compressions are used to reduce the dimensionality of the occupancy state (cf.Sect. 4.1.2), which are currently lost in the current implementation of the conversion. Ideally, one would like to preserve compressions whenever possible or at least retrieve them afterward, and possibly identify further compressions in the solution strategy.

Appendix E HSVI for zs-POSGs

This section presents results that help (i) tune zs-oMG-HSVI’s radius parameter \(\rho \), ensuring that trajectories will always stop, and (ii) then demonstrate the finite time convergence of this algorithm.

1.1 E.1 Algorithm

1.1.1 E.1.1 Setting \(\rho \)

Proposition 16

Bounding \(\lambda _{\tau }\) by \(\lambda ^{\infty } = \frac{1}{2} \frac{1}{1-\gamma } \left[ r_{\max } - r_{\min } \right] \) when \(\gamma <1\), and noting that

one can ensure positivity of the threshold at any by enforcing

\(0< \rho < \frac{1-\gamma }{2\lambda ^\infty }\epsilon \) (or \(0< \rho <\frac{\epsilon }{(r_{\max }-r_{\min }) (H + 1)H}\) if \(\gamma =1\)).

Proof

\(\underline{\text {Let us first consider the case}\,\,\gamma <1.}\)

We have (for ):

Then, let us derive the following equivalent inequalities:

To ensure positivity of the threshold for any \(\tau \ge 1\), one thus just needs to set \(\rho \) as a positive value smaller than \(\frac{1-\gamma }{2\lambda ^\infty }\epsilon \).

\(\underline{\text {Let us now consider the case}\,\,\gamma =1.}\)

We have (for \(\tau \in \{1,\dots ,H-1\}\)):

Then, let us derive the following equivalent inequalities:

The function \(f: \tau \mapsto \frac{\epsilon }{(r_{\max }-r_{\min }) (2\,H + 1 - \tau ) \tau }\) reaches its minimum (for \(\tau \in (0,H+1)\)) when \(\tau =H+\frac{1}{2}\). To ensure positivity of the threshold for any , one thus just needs to set \(\rho \) as a positive value smaller than \(\frac{\epsilon }{(r_{\max }-r_{\min }) (H + 1)H}\). \(\square \)

1.2 E.2 Finite-Time Convergence

1.2.1 E.2.1 Convergence Proof

Proving the finite-time convergence of zs-oMG-HSVI to an error-bounded solution requires some preliminary lemmas.

Lemma 10

Let \((\sigma _0,\dots ,\sigma _{\tau +1})\) be a full trajectory generated by zs-oMG-HSVI and \({\varvec{\beta }}_\tau \) the behavioral dr profile that induced the last transition, i.e., \(\sigma _{\tau +1}= T(\sigma _\tau , {\varvec{\beta }}_\tau )\).

Then, after updating \({\overline{W}}_{\tau }\) and \({\underline{W}}_{\tau }\), we have that \({\overline{W}}_{\tau }(\sigma _\tau ,\beta ^1_\tau ) - {\underline{W}}_{\tau }(\sigma _\tau ,\beta ^2_\tau ) \le \gamma thr(\tau +1)\).

Proof

By definition,

Therefore, after the update (\(\beta ^2_\tau \) and \(\beta ^1_\tau \) being added to their respective bags (\(\overline{\mathcal {I}}^1_\tau \) and \(\underline{\mathcal {I}}^2_\tau \)) along with vectors \(\overline{\nu }^2_{\tau +1}\) and \(\underline{\nu }^1_{\tau +1}\)),

Then,

\(\square \)

Lemma 11

(Monotonic evolution of \({\overline{W}}_{\tau }\) and \({\underline{W}}_{\tau }\)) Let \(K{\overline{W}}_{\tau }\) and \(K{\underline{W}}_{\tau }\) be the approximations after an update at \(\sigma _\tau \) with behavioral dr \(\langle \overline{\beta }^1_\tau , \underline{\beta }^2_\tau \rangle \) (respectively, associated to vectors \(\overline{\nu }^2_{\tau +1}\) and \(\underline{\nu }^1_{\tau +1}\)).

Let also \(K^{(n+1)}{\overline{W}}_{\tau }\) and \(K^{(n+1)}{\underline{W}}_{\tau }\) be the same approximations after n other updates (in various os s). Then,

Proof

Starting from the definition,

Then, this upper bound approximation can only be refined, so that, for any \(n \in {{\textbf{N}}}\),

The expected result thus holds for \({\overline{W}}_{\tau }\), and symmetrically for \({\underline{W}}_{\tau }\). \(\square \)

Lemma 12

After updating, in order, \({\overline{W}}_{\tau }\) and \(\overline{V}_\tau \), we have

After updating, in order, \({\underline{W}}_{\tau }\) and \(\underline{V}_\tau \), we have

Proof

After updating \(\overline{\mathcal {I}}^1_\tau \), the algorithm computes (Algorithm 1, line 20) a new solution \(\overline{\psi }^2_\tau \) of the dual LP (at \(\sigma ^1_\tau \)) and the associated vector \(\overline{\nu }^2_\tau \), so that

This vector will feed \(\overline{bagV}_\tau \) along with \(\sigma ^1_\tau \), so that

As a consequence,

The symmetric property holds for \(K\underline{V}_\tau \) and \(K{\underline{W}}_{\tau }\), which concludes the proof. \(\square \)

Theorem 10

(originally stated on page 15) zs-oMG-HSVI (Algorithm 1) terminates in finite time with an \(\epsilon \)-approximation of \(V^*_0(\sigma _0)\) that satisfies Theorem 9.

Proof

We will prove by induction from \(\tau =H\) to 0, that the algorithm stops expanding os s at depth \(\tau \) after finitely many iterations (/trajectories).

First, by definition of horizon H, no os \(\sigma _H\) is ever expanded. The property thus holds at \(\tau =H\).

Let us now assume that the property holds at depth \(\tau +1\) after \(N_{\tau +1}\) iterations.

By contradiction, let us assume that the algorithm generates infinitely many trajectories of length \(\tau +1\). Then, because \({{\mathcal {O}}}^\sigma _\tau \times {{\mathcal {B}}}_\tau \) is compact, after some time the algorithm will have visited \(\langle \sigma _\tau , {\varvec{\beta }}_\tau \rangle \), then, some iterations later, \(\langle \sigma _\tau ^{'}, {\varvec{\beta }}_\tau ^{'} \rangle \), such that \(\Vert \sigma _\tau - \sigma _\tau ^{'} \Vert _1 \le \rho \). Let us also note the corresponding terminal os s (because trajectories beyond iteration \(N_{\tau +1}\) do not go further) \(\sigma _{\tau +1} = T(\sigma _\tau , \beta _\tau )\) and \(\sigma _{\tau +1}^{'} = T(\sigma _\tau ^{'}, {\varvec{\beta }}_\tau ^{'})\). Now, we show that the second trajectory should not have happened, i.e., \(\overline{V}(\sigma _\tau ^{'}) - \underline{V}(\sigma _\tau ^{'}) \le thr(\tau )\).

Combining the previous lemmas,

Symmetrically, we also have

Hence,

Therefore, \(\sigma ^{'}_\tau \) should not have been expanded.

This shows that the algorithm will generate only a finite number of trajectories of length \(\tau \). \(\square \)

1.2.2 Handling Infinite Horizons

Proposition 17

(originally stated on page 16)

When \(\gamma <1\), the length of trajectories is upper-bounded by , where \(\lambda ^\infty \) is a depth-independent Lipschitz constant and \(W{\mathop {=}\limits ^{\tiny {\text {def}}}}\Vert \overline{V}^{(0)}-\underline{V}^{(0)}\Vert _\infty \) is the maximum width between initializations.

Proof

(detailed version) Since W is the largest possible width, any trajectory stops in the worst case at depth \(\tau \) such that

\(\square \)

Even if the problem horizon is infinite, trajectories will thus have bounded length. Then, everything beyond this effective horizon will rely on the upper- and lower-bound initializations and the corresponding strategies.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions