Rui Yan1<EMAIL_ADDRESS>
Gabriel Santos1<EMAIL_ADDRESS>
Gethin Norman1,2<EMAIL_ADDRESS>
David Parker1<EMAIL_ADDRESS>
Marta Kwiatkowska1<EMAIL_ADDRESS>
1Department of Computer Science, University of Oxford, Oxford, OX1 3QD, UK
2School of Computing Science, University of Glasgow, Glasgow, G12 8QQ, UK

# HSVI-based Online Minimax Strategies for Partially Observable Stochastic
Games with Neural Perception Mechanisms

###### Abstract

We consider a variant of continuous-state partially-observable stochastic
games with neural perception mechanisms and an asymmetric information
structure. One agent has partial information, with the observation function
implemented as a neural network, while the other agent is assumed to have full
knowledge of the state. We present, for the first time, an efficient online
method to compute an $\varepsilon$-minimax strategy profile, which requires
only one linear program to be solved for each agent at every stage, instead of
a complex estimation of opponent counterfactual values. For the partially-
informed agent, we propose a continual resolving approach which uses lower
bounds, pre-computed offline with heuristic search value iteration (HSVI),
instead of opponent counterfactual values. This inherits the soundness of
continual resolving at the cost of pre-computing the bound. For the fully-
informed agent, we propose an inferred-belief strategy, where the agent
maintains an inferred belief about the belief of the partially-informed agent
based on (offline) upper bounds from HSVI, guaranteeing $\varepsilon$-distance
to the value of the game at the initial belief known to both agents.

###### keywords:

Minimax strategies, continual resolving, partially observable stochastic
games.

##  1 Introduction

Partially-observable stochastic games (POSGs) are a modelling formalism that
enables strategic reasoning and (near-)optimal synthesis of strategies and
equilibria in multi-agent settings with partial observations and uncertainty.
_One-sided POSGs_ (Horák et al., 2023) are a tractable subclass of two-agent,
zero-sum POSGs with an asymmetric information structure, where only one agent
has partial information while the other agent is assumed to have full
knowledge. This is well suited to autonomous safety- or security-critical
settings, such as patrolling or pursuit-evasion games, which require reasoning
about worst-case assumptions. Since real-world settings increasingly often
utilise neural networks (NNs) for perception tasks such as localisation and
object detection, _one-sided neuro-symbolic POSGs (one-sided NS-POSGs)_ were
introduced (Yan et al., 2023). In this model the agent with partial
information observes the environment only through a trained NN classifier, and
consequently the game is generalised to _continuous environments_ , to align
with NN semantics, while observations remain discrete. A point-based NS-HSVI
method was developed to approximate values of one-sided NS-POSGs working with
(polyhedral decompositions of) the continuous space.

Strategy synthesis for continuous games is more challenging than for the
finite-state case (Horák et al., 2023), since continuous-state spaces lead to
an infinite number of strategies and discretisation suffers from the curse of
dimensionality. Several _offline_ methods exist, based on counterfactual
regret minimisation, heuristics or reinforcement learning (see Related Work,
below). In this paper, we consider _online_ methods, which can improve
efficiency and adaptability. The best performing online method (Moravčík et
al., 2017) continually resolves a local strategy that only keeps track of the
agent’s belief of its opponent state and a vector of opponent counterfactual
values. Apart from Horák et al. (2023), existing continual resolving
approaches (Moravčík et al., 2017; Šustr et al., 2019; Schmid et al., 2023)
are for extensive form games (EFGs), and cannot be directly applied to POSGs.
This is because, although the two formalisms are connected (Kovařík et al.,
2022), transitioning between them is not straightforward.

Contributions. We develop a _continual resolving_ approach for one-sided NS-
POSGs, addressing several challenges. Firstly, existing continual resolving
approaches need to estimate the opponent’s counterfactual values by solving a
subgame at each stage (Moravčík et al., 2017), which would be intractable for
continuous games. Instead, for the agent with partial observation
($\mathsf{Ag}_{1}$), we use the lower bound computed offline by NS-HSVI (Yan
et al., 2023), giving a polyhedral bound without solving a subgame. At each
stage, we solve a linear program (LP), whose size is linear in the number of
states in the current belief rather than the number of states reached, to
compute the agent’s action choice and update the lower bound. Thus, a _stage
strategy_ is computed online, in the spirit of continual resolving, for each
situation as it arises during execution, instead of storing a complete
strategy. Although we require offline computation for NS-HSVI, existing
continual resolving approaches need to train deep counterfactual value
networks to solve the subgame. Importantly, our NS-HSVI continual resolving
does not lose soundness, i.e., $\varepsilon$-exploitability (Burch et al.,
2014).

We can use any synthesis method for fully-observable stochastic games to
generate an $\varepsilon$-minimax strategy for the fully-informed agent
($\mathsf{Ag}_{2}$) (Yan et al., 2022). However, solving the fully-observable
case would generate a _complete_ strategy, which can be costly in terms of
memory. We instead propose an online _inferred-belief_ strategy by observing
that, by using the offline upper bound from NS-HSVI, $\mathsf{Ag}_{2}$ only
needs to keep track of an inferred belief about $\mathsf{Ag}_{1}\\!$’s belief
and solve an LP, linear in the number of states in the current belief, to
synthesise an action and the next inferred-belief of $\mathsf{Ag}_{2}$. Since
$\mathsf{Ag}_{2}$ is fully informed, it does not need to store its belief.
This allows us to generate a simpler strategy than the complete strategy for
$\mathsf{Ag}_{2}$, which guarantees the value at the initial belief, known to
both agents, but cannot optimally employ the suboptimal actions of
$\mathsf{Ag}_{1}$ during play.

Summarising the contribution, we present, for the first time, an efficient
online method to compute an $\varepsilon$-minimax strategy profile for one-
sided NS-POSGs, a variant of two-player continuous-state POSGs with neural
perception mechanisms, by exploiting bounds pre-computed offline by a variant
of HSVI. We implement our approach, evaluate it on a pursuit-evasion model
inspired by mobile robotics and investigate the synthesised agent strategies.

Related Work. Existing offline strategy synthesis methods for _one-sided_
POSGs include a space partition approach (Zheng et al., 2022), a point-based
approximate algorithm for continuous observations (Zheng et al., 2023),
projection to POMDPs based on factored representations (Carr et al., 2021) and
HSVI algorithms for finite (Horák et al., 2023) and continuous-state spaces
(Yan et al., 2023). Since POSGs and EFGs are connected through factored-
observation stochastic games (Kovařík et al., 2022), we next review relevant
methods for two-agent zero-sum EFGs.

Counterfactual Regret Minimization (CFR) (Zinkevich et al., 2007) exploits the
fact that the time-averaged strategy profile of regret minimizing algorithms
converges to an $\varepsilon$-minimax strategy profile, in two-agent zero-sum
EFGs with imperfect information. Since its introduction, a variety of CFR
variants have been proposed and successfully applied to games (Lanctot et al.,
2009; Lisỳ et al., 2015; Burch et al., 2014). However, since the CFR-based
approaches require iterative traversal of the game tree, they become
intractable when the tree is large. Additionally, these approaches are
_offline_ algorithms, returning a complete solution strategy that is difficult
to represent and store.

A number of algorithms based on game-theoretic learning models such as
reinforcement learning and heuristic search have also been proposed, which are
able to compute strategies for two-agent zero-sum games with imperfect
information, including (Bosansky et al., 2014; Heinrich et al., 2015; Lanctot
et al., 2017; McAleer et al., 2021) and heuristic search value iteration
(HSVI) (Yan et al., 2023; Delage et al., 2023), which we utilise in our work.
However, these approaches are also offline algorithms and unable to refine
strategies at test time.

The most related approach is _continual resolving_ used in Horák et al.
(2023), which is based on DeepStack (Moravčík et al., 2017), although other
variants have also been proposed, e.g., (Šustr et al., 2019; Schmid et al.,
2023; Brown et al., 2020). Both Horák et al. (2023) and our work are variants
of continual resolving for one-sided POSGs, except we consider continuous-
state spaces. Under the belief update in Horák et al. (2023), the current
state could be missed and the belief might be empty. We assume a uniform stage
strategy to fix this issue and ensure that the true state is always in the
current belief. The LP size in Horák et al. (2023) is fixed, while the LP in
our case varies at each stage because of no prior enumeration of all reachable
states. Horák et al. (2023) performs the belief update before
$\mathsf{Ag}_{1}$ taking action and observing, whereas we update the belief
using the action and the next observation, which results in a more accurate
belief.

##  2 Background

We briefly review the model of Yan et al. (2023), which generalises _one-sided
POSGs_ (Horák et al., 2023) to continuous-state spaces and allows neural
perception mechanisms. Let $\mathbb{P}(X)$ and $\mathbb{F}(X)$ denote the
spaces of probability measures and functions on a Borel space $X$,
respectively.

One-sided NS-POSGs. A _one-sided neuro-symbolic POSG (NS-POSG)_ $\mathsf{C}$
is a two-player zero-sum infinite-horizon game with discrete actions and
observations, where one player ($\mathsf{Ag}_{1}$) is partially informed and
the other ($\mathsf{Ag}_{2}$) is fully informed. Unlike Horák et al. (2023),
the game is played in a closed continuous environment $S_{E}$, which
$\mathsf{Ag}_{1}$ perceives only using perception function $\mathit{obs}_{1}$
given as a (trained) ReLU NN classifier that maps environment states to so
called _percepts_ , ranging over a finite set $\mathit{Per}_{1}$. The use of
classifiers is aligned with, e.g., object detection or vision tasks in
autonomous systems. We further assume that $\mathsf{Ag}_{1}$ has a discrete
local state space $\mathit{Loc}_{1}$, which is observable to both agents, and
that $\mathsf{Ag}_{2}$ has full knowledge of the environment’s state.

A game $\mathsf{C}$ comprises agents $\mathsf{Ag}_{1}{=}$
$(S_{1},A_{1},\mathit{obs}_{1},\delta_{1})$, $\mathsf{Ag}_{2}{=}(A_{2})$ and
environment $E{=}(S_{E},\delta_{E})$, where
$S_{1}=\mathit{Loc}_{1}{\times}\mathit{Per}_{1}$; $A=A_{1}{\times}A_{2}$ are
joint actions; $\mathit{obs}_{1}\mathrel{\mathop{\mathchar
58\relax}}(\mathit{Loc}_{1}{\times}S_{E})\to\mathit{Per}_{1}$ is
$\mathsf{Ag}_{1}\\!$’s perception function (note that we allow NNs to
additionally depend on local states); $\delta_{1}\mathrel{\mathop{\mathchar
58\relax}}(S_{1}{\times}A)\to\mathbb{P}(\mathit{Loc}_{1})$ is
$\mathsf{Ag}_{1}\\!$’s local transition function; and
$\delta_{E}\mathrel{\mathop{\mathchar
58\relax}}(\mathit{Loc}_{1}{\times}S_{E}{\times}A)\to\mathbb{P}(S_{E})$ is
$E$’s finite-branching transition function. We work in the _belief space_
$S_{B}\subseteq\mathbb{P}(S)$, where $S=S_{1}{\times}S_{E}$, and assume an
initial belief $b^{\mathit{init}}$ using the particle-based representation
(Porta et al., 2006; Doucet et al., 2001). A belief of $\mathsf{Ag}_{1}$ is
given by $b=(s_{1},b_{1})$, where $s_{1}\in S_{1}$,
$b_{1}\in\mathbb{P}(S_{E})$ and $b_{1}$ is represented by a weighted particle
set $\\{(s_{E}^{i},\kappa_{i})\\}_{i=1}^{N_{b}}$ where $\kappa_{i}\geq 0$ and
$\mbox{$\sum\nolimits_{i=1}^{N_{b}}$}\kappa_{i}=1$.

The game starts in a state $s=(s_{1},s_{E})$, where
$s_{1}=(\mathit{loc}_{1},\mathit{per}_{1})\in S_{1}$, and $s$ is sampled from
$b^{\mathit{init}}$. At each _stage_ of the game, both agents concurrently
choose one of their actions. If $a=(a_{1},a_{2})\in A$ is chosen, the local
state $\mathit{loc}_{1}$ of $\mathsf{Ag}_{1}$ is updated to
$\mathit{loc}_{1}^{\prime}\in\mathit{Loc}_{1}$ via $\delta_{1}(s_{1},a)$,
while the environment updates its state to $s_{E}^{\prime}\in S_{E}$ via
$\delta_{E}(\mathit{loc}_{1},s_{E},a)$. Finally, $\mathsf{Ag}_{1}$, based on
$\mathit{loc}_{1}^{\prime}$, generates its percept
$\mathit{per}_{1}^{\prime}=\mathit{obs}_{1}(\mathit{loc}^{\prime}_{1},s^{\prime}_{E})$
at $s_{E}^{\prime}$ and $\mathsf{C}$ reaches the state
$s^{\prime}=((\mathit{loc}_{1}^{\prime},\mathit{per}_{1}^{\prime}),s_{E}^{\prime})$.
The probability of transitioning from $s$ to $s^{\prime}$ under $a$ is
$\delta(s,a)(s^{\prime})=\delta_{1}(s_{1},a)(\mathit{loc}_{1}^{\prime})\delta_{E}(\mathit{loc}_{1},s_{E},a)(s_{E}^{\prime})$.

Strategies. We distinguish between a _history_ $\pi$ (a sequence of states and
joint actions, where $\pi(k)$ is the $(k{+}1)$th state, and $\pi[k]$ is the
$(k{+}1)$th action) and a (local) _action-observation history (AOH)_ for
$\mathsf{Ag}_{i}$ (a sequence of its observations and actions). For the fully-
informed $\mathsf{Ag}_{2}$, an AOH is a history. A _strategy_ of
$\mathsf{Ag}_{i}$ is a mapping $\sigma_{i}\mathrel{\mathop{\mathchar
58\relax}}\mathit{FPaths}_{\mathsf{C},i}\to\mathbb{P}(A_{i})$, where
$\mathit{FPaths}_{\mathsf{C},i}$ is the set of $\mathsf{Ag}_{i}$’s finite
AOHs. A _(strategy) profile_ $\sigma=(\sigma_{1},\sigma_{2})$ is a pair of
strategies and we denote by $\Sigma_{i}$ and $\Sigma$ the sets of strategies
of $\mathsf{Ag}_{i}$ and profiles. The choices for the players after a history
$\pi$ are given by _stage strategies_ : for $\mathsf{Ag}_{1}$ this is a
distribution $u_{1}\in\mathbb{P}(A_{1})$ and for $\mathsf{Ag}_{2}$ a function
$u_{2}\mathrel{\mathop{\mathchar 58\relax}}S\to\mathbb{P}(A_{2})$, i.e.,
$u_{2}\in\mathbb{P}(A_{2}\mid S)$. Given a belief $(s_{1},b_{1})$, if
$\mathsf{Ag}_{1}$ chooses $a_{1}$, _assumes_ $\mathsf{Ag}_{2}$ chooses $u_{2}$
and observes $s_{1}^{\prime}$, then the updated belief of $\mathsf{Ag}_{1}$
via Bayesian inference is denoted
$(s_{1}^{\prime},b_{1}^{s_{1},a_{1},u_{2},s_{1}^{\prime}})$.

Objectives and values. We focus on infinite-horizon expected accumulated
reward $\mathbb{E}_{b}^{\sigma}[Y]$ when starting from $b$ under $\sigma$,
where $Y(\pi)=\sum_{k=0}^{\infty}\beta^{k}r(\pi(k),\pi[k])$ for an infinite
history $\pi$, reward structure $r\mathrel{\mathop{\mathchar
58\relax}}(S{\times}A)\to\mathbb{R}$ and discount $\beta\in(0,1)$, and
$\mathsf{Ag}_{1}$ and $\mathsf{Ag}_{2}$ maximise and minimise the expected
value. Given $\varepsilon{\geq}0$, a profile
$\sigma^{\star}=(\sigma_{1}^{\star},\sigma_{2}^{\star})$ is an _$\varepsilon$
-minimax strategy profile_ if for any $b\in S_{B}$,
$\smash{\mathbb{E}_{b}^{\sigma^{\star}}}[Y]\leq\mathbb{E}_{b}^{\sigma_{1}^{\star},\sigma_{2}}[Y]{+}\varepsilon$
for all $\sigma_{2}$ and
$\mathbb{E}_{b}^{\sigma^{\star}}[Y]\geq\mathbb{E}_{b}^{\sigma_{1},\sigma_{2}^{\star}}[Y]{-}\varepsilon$
for all $\sigma_{1}$. If $\varepsilon{=}0$, then
$\smash{\mathbb{E}_{b}^{\sigma^{\star}}}[Y]$ is the _value_ of $\mathsf{C}$,
denoted $V^{\star}$.

One-sided NS-HSVI. HSVI is an anytime algorithm that approximates the value
$V^{\star}$ via _lower_ and _upper bound_ functions, updated through
heuristically generated beliefs. One-sided NS-HSVI (Yan et al., 2023) works
with the continuous-state space of a one-sided NS-POSG using a generalisation
of $\alpha$-functions, similar to Porta et al. (2006), except it uses
_polyhedral_ representations induced from NNs instead of Gaussian mixtures.
For $\varepsilon>0$, one-sided NS-HSVI returns lower and upper bound functions
$V_{\mathit{lb}}^{\Gamma},V_{\mathit{ub}}^{\Upsilon}\in\mathbb{F}(S_{B})$ to
approximate $V^{\star}$ such that $V_{\mathit{lb}}^{\Gamma}(b)\leq
V^{\star}(b)\leq V_{\mathit{ub}}^{\Upsilon}(b)$ for all $b\in S_{B}$ and
$V_{\mathit{ub}}^{\Upsilon}(b^{\mathit{init}})-V_{\mathit{lb}}^{\Gamma}(b^{\mathit{init}})\leq\varepsilon$.
Given $f\mathrel{\mathop{\mathchar 58\relax}}S\to\mathbb{R}$ and belief
$(s_{1},b_{1})$, let $\langle f,(s_{1},b_{1})\rangle=\,\mbox{$\int_{s_{E}\in
S_{E}}$}f(s_{1},s_{E})b_{1}(s_{E})\textup{d}s_{E}$. The lower bound
$V_{\mathit{lb}}^{\Gamma}$ is represented via a finite set
$\Gamma\subseteq\mathbb{F}(S)$ of _piecewise-constant (PWC)_
$\alpha$-functions such that
$V_{\mathit{lb}}^{\Gamma}(s_{1},b_{1})=\max_{\alpha\in\Gamma}\langle\alpha,(s_{1},b_{1})\rangle$.
The upper bound $V_{\mathit{ub}}^{\Upsilon}$ is represented by a finite set of
belief-value pairs $\Upsilon\subseteq S_{B}{\times}\mathbb{R}$ and computed
via an LP.

##  3 NS-HVSI Continual resolving

_Continual resolving_ , e.g., (Moravčík et al., 2017), is an online method for
computing an $\varepsilon$-minimax strategy in two-player, zero-sum imperfect
information EFGs; it keeps track of an agent’s belief of its opponent state
and opponent counterfactual values to build and solve a subgame to synthesise
choices, without building a complete strategy. It is _sound_ , in computing an
$\varepsilon$-minimax strategy, but can be expensive as it needs to estimate
opponent counterfactual values by traversing the game tree.

We now present a novel variant of continual resolving, which utilises the
_lower bound_ function $V_{\mathit{lb}}^{\Gamma}$ computed by one-sided NS-
HSVI to synthesise an $\varepsilon$-minimax strategy for $\mathsf{Ag}_{1}$
that achieves the desired $\varepsilon$ distance to the value function at the
initial belief. The method is efficient as it only requires solving a single
LP at each stage. We first introduce the following minimax operator.

######  Definition 1 (Minimax)

The minimax operator $T\mathrel{\mathop{\mathchar
58\relax}}\mathbb{F}(S_{B}){\rightarrow}\mathbb{F}(S_{B})$ is given by:

$\displaystyle[TV](s_{1},b_{1})$
$\displaystyle=\smash{\max\nolimits_{u_{1}\in\mathbb{P}(A_{1})}\min\nolimits_{u_{2}\in\mathbb{P}(A_{2}\mid
S)}\mathbb{E}_{(s_{1},b_{1}),u_{1},u_{2}}[r(s,a)]}$
$\displaystyle+\smash{\beta\mbox{$\sum\nolimits_{(a_{1},s_{1}^{\prime})\in
A_{1}\times
S_{1}}$}P(a_{1},s_{1}^{\prime}\mid(s_{1},b_{1}),u_{1},u_{2})V(s^{\prime}_{1},b_{1}^{s_{1},a_{1},u_{2},s_{1}^{\prime}})}$
(1)

for $V\in\mathbb{F}(S_{B})$ and $(s_{1},b_{1})\in S_{B}$, where
$\mathbb{E}_{(s_{1},b_{1}),u_{1},u_{2}}[r(s,a)]$ is the expected value of $r$.

Algorithm 1 NS-HSVI continual resolving for $\mathsf{Ag}_{1}\\!$’s strategy
via the lower bound

Input: $(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})$, a finite set of PWC
functions $\Gamma\subseteq\mathbb{F}(S)$ from one-sided NS-HSVI

1:$\mathit{Resolve}_{1}((s_{1}^{\mathit{init}},b_{1}^{\mathit{init}}),\alpha^{\mathit{init}})$
where
$\alpha^{\mathit{init}}=\arg\max_{\alpha\in\Gamma}\langle\alpha,(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})\rangle$

2:function $\mathit{Resolve}_{1}$($(s_{1},b_{1}),\alpha_{1}$)

3:
$(\overline{v}^{\star},\overline{\lambda}_{1}^{\star},\overline{p}_{1}^{\star})\leftarrow$
solve the LP (2) at $(s_{1},b_{1})$

4: $u_{1}^{\mathit{lb}}(a_{1})\leftarrow p^{\star a_{1}}$ for all $a_{1}\in
A_{1}$

5: sample and play $a_{1}\sim u_{1}^{\mathit{lb}}$

6: $s_{1}^{\prime}\leftarrow$ observed $\mathsf{Ag}_{1}$’s agent state

7: $\alpha^{\star
a_{1},s_{1}^{\prime}}\leftarrow\mbox{$\sum_{\alpha\in\Gamma}$}(\lambda^{\star
a_{1},s_{1}^{\prime}}_{\alpha}/p^{\star a_{1}})\alpha$,
$u_{2}^{\mathit{lb}}\leftarrow$ an assumed stage strategy for
$\mathsf{Ag}_{2}$

8:
$\mathit{Resolve}_{1}((s_{1}^{\prime},b_{1}^{s_{1},a_{1},u_{2}^{\mathit{lb}},s_{1}^{\prime}}),\alpha^{\star
a_{1},s_{1}^{\prime}})$

NS-HSVI continual resolving. Motivated by (Horák et al., 2023, Section 9.2),
our online game-playing algorithm _NS-HSVI continual resolving_ , see
Algorithm 1, generates a strategy for $\mathsf{Ag}_{1}$, denoted
$\sigma_{1}^{\mathit{lb}}$, by using the HSVI lower bound instead of opponent
counterfactual values used in Moravčík et al. (2017). Since we have pre-
computed $V_{\mathit{lb}}^{\Gamma}$ offline, our NS-HSVI continual resolving
only keeps track of a belief $(s_{1},b_{1})$ and a PWC function $\alpha_{1}$
in the the convex hull, $\textup{Conv}(\Gamma)$, of $\Gamma$. Importantly,
$\Gamma$ can be used to compute an action to play and update the tracking
information at each stage (a belief and a PWC function) by solving the LP
presented below, thus avoiding the need to estimate the opponent
counterfactual values.

######  Definition 2 (Stage strategy)

For $((s_{1},b_{1}),\alpha_{1})\in S_{B}\times\textup{Conv}(\Gamma)$ where
$b_{1}$ is represented by $\\{(s_{E}^{i},\kappa_{i})\\}_{i=1}^{N_{b}}$, a
stage strategy $u_{1}^{\mathit{lb}}$ for $\mathsf{Ag}_{1}$ is such that
$u_{1}^{\mathit{lb}}(a_{1})=p^{\star a_{1}}$ for $a_{1}\in A_{1}$, where
$(v_{s_{E}^{i}}^{\star})_{i=1}^{N_{b}}$, $\smash{(\lambda^{\star
a_{1},s_{1}^{\prime}}_{\alpha})_{(a_{1},s_{1}^{\prime})\in A_{1}\times
S_{1},\alpha\in\Gamma}}$ and $\smash{(p^{\star a_{1}})_{a_{1}\in A_{1}}}$ is a
solution to the following LP:

$\displaystyle\mbox{\rm
maximise}\;\;\smash{\mbox{$\sum_{i=1}^{N_{b}}$}\kappa_{i}v_{s_{E}^{i}}}\;\;\mbox{\rm
subject to}$ $\displaystyle v_{s_{E}^{i}}$
$\displaystyle\leq\mbox{$\sum_{a_{1}\in
A_{1}}$}p^{a_{1}}r((s_{1},s_{E}^{i}),(a_{1},a_{2}))+\beta\mbox{$\sum_{(a_{1},s_{1}^{\prime})\in
A_{1}\times S_{1},s_{E}^{\prime}\in S_{E}}$}$
$\displaystyle\;\;\;\cdot\delta((s_{1},s_{E}^{i}),(a_{1},a_{2}))(s_{1}^{\prime},s_{E}^{\prime})\mbox{$\sum_{\alpha\in\Gamma}\lambda_{\alpha}^{a_{1},s_{1}^{\prime}}$}\alpha(s_{1}^{\prime},s_{E}^{\prime})\quad\mbox{for
}1\leq i\leq N_{b}\mbox{ and }a_{2}\in A_{2}$ $\displaystyle v_{s_{E}^{i}}$
$\displaystyle\geq\alpha_{1}(s_{1},s_{E}^{i})\quad\mbox{for }1\leq i\leq
N_{b}$ $\displaystyle\lambda^{a_{1},s_{1}^{\prime}}_{\alpha}$
$\displaystyle\geq 0\quad\mbox{for }a_{1}\in A_{1},\;s_{1}^{\prime}\in
S_{1}\mbox{ and }\alpha\in\Gamma$ $\displaystyle p^{a_{1}}$
$\displaystyle=\mbox{$\sum_{\alpha\in\Gamma}$}\lambda_{\alpha}^{a_{1},s_{1}^{\prime}}\quad\mbox{for
}a_{1}\in A_{1}\mbox{ and }s_{1}^{\prime}\in S_{1}$
$\displaystyle\mbox{$\sum_{a_{1}\in A_{1}}$}p^{a_{1}}$ $\displaystyle=1.$ (2)

Compared with the LP in Yan et al. (2023) for solving
$[TV_{\mathit{lb}}^{\Gamma}](s_{1},b_{1})$, the LP (2) includes the additional
constraints $\smash{v_{s_{E}^{i}}\geq\alpha_{1}(s_{1},s_{E}^{i})}$ for $1\leq
i\leq N_{b}$ (Horák et al., 2023, Section 9.2) to refine the minimax stage
strategy in $[TV_{\mathit{lb}}^{\Gamma}](s_{1},b_{1})$, such that the lower
bound from $\alpha_{1}$ can be kept as the game evolves, since multiple
minimax stage strategies for $\mathsf{Ag}_{1}$ may exist and some of them may
deviate from $\alpha_{1}$.

$(s_{1},b_{1}),\alpha_{1}$LP: HSVI $\Gamma$ belief update
$(s_{1}^{\prime},b_{1}^{\prime}),\alpha_{1}^{\prime}$$(s_{1},b_{1})$$a_{1}{\sim}u_{1}^{\mathit{lb}}$$s_{1}^{\prime}$$(s_{1}^{\prime},b_{1}^{\prime})$$a_{2}{\sim}u_{2}$$\alpha_{1}^{\prime}$$(s_{1},b_{1})$LP:
HSVI $\Upsilon$ belief update
$(s_{1}^{\prime},b_{1}^{\prime})$$(s_{1},b_{1})$$a_{2}{\sim}u_{2}^{\mathit{ub}}$$a_{1}{\sim}u_{1}$$s_{1}^{\prime}$$a_{1}$$(s_{1}^{\prime},b_{1}^{\prime})$
Figure 1: Left: NS-HSVI continual resolving for the partially-informed agent
$\mathsf{Ag}_{1}$ (blue). Right: inferred-belief strategy synthesis for the
fully-informed agent $\mathsf{Ag}_{2}$ (red).

We illustrate how the strategy $\sigma_{1}^{\mathit{lb}}$ is obtained in Fig.
1 (left), where the red and orange circles indicate the current state, with
the size of the interior solid circle representing the probability. When
resolving the game locally $((s_{1},b_{1}),\alpha_{1})$, $\mathsf{Ag}_{1}$
(blue) plays an action $a_{1}$ sampled from a stage strategy
$u_{1}^{\mathit{lb}}$ computed via (2). Simultaneously, $\mathsf{Ag}_{2}$
(red) plays an action $a_{2}$ sampled from a stage strategy $u_{2}$, which is
unknown to $\mathsf{Ag}_{1}$. The game moves to the next state and
consequently $\mathsf{Ag}_{1}$ observes a new agent state $s_{1}^{\prime}\in
S_{1}$. Based on $a_{1}$, $s_{1}^{\prime}$ and an _assumed_ stage strategy
$u_{2}^{\mathit{lb}}$ for $\mathsf{Ag}_{2}$, see lines 7–8 of Algorithm 1,
$\mathsf{Ag}_{1}$ updates its belief to
$(s_{1}^{\prime},b_{1}^{s_{1},a_{1},u_{2}^{\mathit{lb}},s_{1}^{\prime}})$ via
Bayesian inference, and generates $\alpha^{\star
a_{1},s_{1}^{\prime}}\in\textup{Conv}(\Gamma)$ from a solution to (2), which
forms a new pair for the next resolving.

###### Remark 1

There are two key properties of Algorithm 1. First, LP (2) admits at least one
solution as $V_{\mathit{lb}}^{\Gamma}$ is computed by the one-sided NS-HSVI.
Second, the current state has to be in the support of the current belief,
i.e., $\mathsf{Ag}_{1}$ does not lose track of the current state. Such a
belief is called a proper belief and this is ensured by assuming the uniform
stage strategy for $\mathsf{Ag}_{2}$.

######  Lemma 1 (Existence and proper belief)

For the NS-HSVI continual resolving at $((s_{1},b_{1}),\alpha_{1})$, the LP
(2) admits at least one solution, and if the current state is $(s_{1},s_{E})$,
then $b_{1}(s_{E})>0$.

######  Proof 3.1.

The optimal value $V^{\star}$ has lower and upper bounds
$L=\min\nolimits_{s\in S,a\in A}r(s,a)/(1-\beta)$ and $U=\max\nolimits_{s\in
S,a\in A}r(s,a)/(1-\beta)$. Let $V_{\mathit{lb}}^{\Gamma^{\prime}}$ be the
lower bound of one-sided NS-HSVI (Yan et al., 2023). Existence follows if (2)
admits one solution after any point-based update. The key is to check the
feasibility of the first two constraints for $v_{s_{E}^{i}}$ of (2). Initially
$\Gamma^{\prime}=\\{\alpha_{0}\\}$ with $\alpha_{0}(s)=L$ for $s\in S$, and
since $\alpha_{1}=\alpha_{0}$ it is straightforward to verify that (2) admits
at least one solution.

For the inductive step, we assume that (2) admits at least one solution for
$\alpha\in\Gamma$ and $\alpha_{1}\in\textup{Conv}(\Gamma)$. The point-based
update computes a new set $\Gamma^{\prime}=\Gamma\cup\\{\alpha^{\star}\\}$ of
PWC functions, where (2) admits at least one solution for
$\alpha_{1}=\alpha^{\star}$. Thus, (2) admits at least one solution for
$\alpha\in\Gamma$ and
$\alpha_{1}\in\textup{Conv}(\Gamma)\cup\\{\alpha^{\star}\\}$. Following the
proof of (Horák et al., 2023, Lemma 9.6), we can show that (2) admits at least
one solution for $\alpha\in\Gamma^{\prime}$ and
$\alpha_{1}\in\textup{Conv}(\textup{Conv}(\Gamma)\cup\\{\alpha^{\star}\\})$,
i.e., $\alpha_{1}\in\textup{Conv}(\Gamma^{\prime})$.

To show the belief is proper, since the initial state is sampled from
$(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})$, which is known to
$\mathsf{Ag}_{1}$, and the uniform stage strategy for $\mathsf{Ag}_{2}$ is
assumed, then the result follows.

We next show that our NS-HSVI continual resolving can inherit the soundness of
continual resolving, i.e., it can compute an $\varepsilon$-minimax strategy
for $\mathsf{Ag}_{1}$.

######  Theorem 3.2 ($\varepsilon$-minimax strategy for $\mathsf{Ag}_{1}$).

The strategy $\sigma_{1}^{\mathit{lb}}$ in Algorithm 1 is an
$\varepsilon$-minimax strategy for $\mathsf{Ag}_{1}$ at
$(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})$, i.e.,
$\mathbb{E}_{(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})}^{\sigma_{1}^{\mathit{lb}},\sigma_{2}}[Y]\geq
V^{\star}(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})-\varepsilon$ for all
$\sigma_{2}\in\Sigma_{2}$.

######  Proof 3.3.

We adapt the proof presented for discrete one-sided POSGs in (Horák et al.,
2023, Proposition 9.7). Let $\mathbb{E}_{s}^{\sigma}[Y]$ denote the expected
value of $Y$ when starting from $s\in S$ under $\sigma\in\Sigma$. Consider any
$b=(s_{1},b_{1})\in S_{B}$ and $\alpha_{1}\in\textup{Conv}(\Gamma)$. We assume
that $\mathsf{Ag}_{1}$ follows $\mathit{Resolve}_{1}$ in Algorithm 1 at the
first $t$ stages and then follows the uniform stage strategy. We denote such a
strategy by $\sigma_{1}^{b,\alpha_{1},t}$. Lemma 1 guarantees that
$\mathit{Resolve}_{1}$ can run for $t$ stages. We next prove that, for any
$s_{E}$ with $b_{1}(s_{E})>0$, the expected value of $Y$ from $(s_{1},s_{E})$
under $\sigma_{1}^{b,\alpha_{1},t}$ has the bound by $\alpha_{1}$:

$\smash{\mathbb{E}_{(s_{1},s_{E})}^{\sigma_{1}^{b,\alpha_{1},t},\sigma_{2}}[Y]\geq\alpha_{1}(s_{1},s_{E})-\beta^{t}(U-L)\quad\textup{
for all }\sigma_{2}\in\Sigma_{2}.}$ (3)

We prove (3) by induction on $t\in\mathbb{N}$. For $t{=}0$, (3) holds as $U$
and $L$ are trivial lower and upper bounds, and
$\alpha_{1}\in\textup{Conv}(\Gamma)$ and $\alpha(s)\leq U$ for all $s\in S$
and $\alpha\in\Gamma$. We assume (3) holds for the first $t$ stages and any
$b^{\prime}=(s_{1}^{\prime},b_{1}^{\prime})\in S_{B}$. The strategy
$\smash{\sigma_{1}^{b,\alpha_{1},t+1}}$ implies that, at $(s_{1},b_{1})$,
$\mathsf{Ag}_{1}$ takes $u_{1}^{\mathit{lb}}$ (line 4) and then follows the
strategy $\sigma_{1}^{b^{\prime},\alpha^{\prime},t}$ if $a_{1}$ is taken and
$s_{1}^{\prime}$ is observed, where
$b^{\prime}=(s_{1}^{\prime},b_{1}^{\prime})$,
$\smash{b_{1}^{\prime}=b_{1}^{s_{1},a_{1},u_{2}^{\mathit{lb}},s_{1}^{\prime}}}$
and $\alpha^{\prime}=\alpha^{\star a_{1},s_{1}^{\prime}}$. Letting
$u_{2}\in\mathbb{P}(A_{2}\mid S)$ be the stage strategy of $\mathsf{Ag}_{2}$
at $b$ given by $\sigma_{2}$, using $b_{1}(s_{E})>0$ by Lemma 1, the left side
of (3) by replacing $t$ with $t+1$ equals:

$\displaystyle\mathbb{E}_{u_{1}^{\mathit{lb}},u_{2}}[r((s_{1},s_{E}),a)]+\beta\mbox{$\sum_{(a_{1},a_{2})\in
A\wedge(s_{1}^{\prime},s_{E}^{\prime})\in
S}$}u_{1}^{\mathit{lb}}(a_{1})u_{2}(a_{2}\mid s_{1},s_{E})$
$\displaystyle\qquad\cdot\delta((s_{1},s_{E}),(a_{1},a_{2}))(s_{1}^{\prime},s_{E}^{\prime})\mathbb{E}_{(s_{1}^{\prime},s_{E}^{\prime})}^{\sigma_{1}^{b^{\prime},\alpha^{\prime},t},\sigma_{2}}[Y]$
by definition of $u_{1}^{\mathit{lb}}$, $u_{2}$ and $\delta$
$\displaystyle\geq\min\nolimits_{a_{2}\in A_{2}}\Big{(}\mbox{$\sum_{a_{1}\in
A_{1}}$}u_{1}^{\mathit{lb}}(a_{1})r((s_{1},s_{E}),(a_{1},a_{2}))+\beta\mbox{$\sum_{a_{1}\in
A_{1}\wedge(s_{1}^{\prime},s_{E}^{\prime})\in S}$}u_{1}^{\mathit{lb}}(a_{1})$
$\displaystyle\qquad\cdot\delta((s_{1},s_{E}),(a_{1},a_{2}))(s_{1}^{\prime},s_{E}^{\prime})\mathbb{E}_{(s_{1}^{\prime},s_{E}^{\prime})}^{\sigma_{1}^{b^{\prime},\alpha^{\prime},t},\sigma_{2}}[Y]\Big{)}$
by linearity in $u_{2}$ $\displaystyle\geq\smash{\min\nolimits_{a_{2}\in
A_{2}}\big{(}\mbox{$\sum_{a_{1}\in
A_{1}}$}u_{1}^{\mathit{lb}}(a_{1})r((s_{1},s_{E}),(a_{1},a_{2}))+\beta\mbox{$\sum_{a_{1}\in
A_{1}\wedge(s_{1}^{\prime},s_{E}^{\prime})\in S}$}u_{1}^{\mathit{lb}}(a_{1})}$
$\displaystyle\qquad\cdot\delta((s_{1},s_{E}),(a_{1},a_{2}))(s_{1}^{\prime},s_{E}^{\prime})(\alpha^{\star
a_{1},s_{1}^{\prime}}(s_{1}^{\prime},s_{E}^{\prime})-\beta^{t}(U-L))\big{)}$
by induction $\displaystyle=\smash{\min\nolimits_{a_{2}\in
A_{2}}\big{(}\mbox{$\sum_{a_{1}\in
A_{1}}$}u_{1}^{\mathit{lb}}(a_{1})r((s_{1},s_{E}),(a_{1},a_{2}))+\beta\mbox{$\sum_{a_{1}\in
A_{1}\wedge(s_{1}^{\prime},s_{E}^{\prime})\in S}$}u_{1}^{\mathit{lb}}(a_{1})}$
$\displaystyle\qquad\cdot\delta((s_{1},s_{E}),(a_{1},a_{2}))(s_{1}^{\prime},s_{E}^{\prime})\alpha^{\star
a_{1},s_{1}^{\prime}}(s_{1}^{\prime},s_{E}^{\prime})\big{)}-\beta^{t+1}(U-L)$
rearranging $\displaystyle\geq v^{\star}_{s_{E}}-\beta^{t+1}(U-L)$ since
$(\overline{v}^{\star},\overline{\lambda}_{1}^{\star},\overline{p}_{1}^{\star})$
is a solution to (2) (first constraint)
$\displaystyle\geq\alpha_{1}(s_{1},s_{E})-\beta^{t+1}(U-L)$ since
$(\overline{v}^{\star},\overline{\lambda}_{1}^{\star},\overline{p}_{1}^{\star})$
is a solution to (2) (second constraint)

and hence (3) holds. Letting
$\sigma_{1}^{\mathit{lb}}=\lim_{t\rightarrow\infty}\sigma_{1}^{b^{\mathit{init}},\alpha^{\mathit{init}},t}$
by definition:

$\displaystyle\mathbb{E}_{b^{\mathit{init}}}^{\sigma_{1}^{\mathit{lb}},\sigma_{2}}[Y]$
$\displaystyle=\mbox{$\int_{s_{E}\in
S_{E}}$}b_{1}^{\mathit{init}}(s_{E})\mathbb{E}_{(s_{1}^{\mathit{init}},s_{E})}^{\sigma_{1}^{\mathit{lb}},\sigma_{2}}[Y]\textup{d}s_{E}$
$\displaystyle\geq\langle\alpha^{\mathit{init}},(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})\rangle$
by (3) and definition of $\langle\cdot,\cdot\rangle$
$\displaystyle=V_{\mathit{lb}}^{\Gamma}(b^{\mathit{init}})$ by line 1 of
Algorithm 1 $\displaystyle\geq V^{\star}(b^{\mathit{init}})-\varepsilon$ since
$V_{\mathit{lb}}^{\Gamma}$ is returned by one-sided NS-HSVI

which completes the proof.

##  4 Inferred-Belief Strategy Synthesis

We complement our variant of continual resolving with strategy synthesis for
$\mathsf{Ag}_{2}$, which utilises the _upper bound_ function
$V_{\mathit{ub}}^{\Upsilon}$ pre-computed offline and keeps track of an
_inferred_ belief about what $\mathsf{Ag}_{1}$ believes, which could differ
from $\mathsf{Ag}_{1}\\!$’s true belief. Any offline method for fully-
observable stochastic games could instead be used, with the associated high
computational and storage cost of generating a complete strategy. Instead, we
present an efficient _online_ algorithm, where only one LP is solved at each
stage, to synthesise an $\varepsilon$-minimax strategy for $\mathsf{Ag}_{2}$.
Since we have pre-computed the offline upper bound, this strategy can
guarantee the minimax value from the initial belief, which is known to both
agents, but cannot optimally employ the suboptimal actions of
$\mathsf{Ag}_{1}$ during play.

Algorithm 2 Inferred-belief strategy synthesis for $\mathsf{Ag}_{2}$ via the
upper bound

Input: $(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})$, a finite set of
belief-value pairs $\Upsilon$ by one-sided NS-HSVI

1:$\mathit{Resolve}_{2}(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})$

2:function $\mathit{Resolve}_{2}$($s_{1},b_{1}$)

3: $\smash{u_{2}^{\mathit{ub}}\leftarrow}$ $\mathsf{Ag}_{2}\\!$’s minimax
strategy in $\smash{[TV_{\mathit{ub}}^{\Upsilon}](s_{1},b_{1})}$,
$(s_{1},s_{E})\leftarrow$ current observed state

4: sample and play $a_{2}\sim u_{2}^{\mathit{ub}}(\cdot\mid s_{1},s_{E})$

5: $(a_{1},s_{1}^{\prime})\leftarrow$ $\mathsf{Ag}_{1}\\!$’s action and
updated agent state

6:
$\mathit{Resolve}_{2}(s_{1}^{\prime},b_{1}^{s_{1},a_{1},u_{2}^{\mathit{ub}},s_{1}^{\prime}})$

Inferred-belief strategy synthesis. Our inferred-belief strategy synthesis for
$\mathsf{Ag}_{2}$ (Algorithm 2) returns a strategy $\sigma_{2}^{\mathit{ub}}$
based on $V_{\mathit{ub}}^{\Upsilon}$. The main idea of
$\sigma_{2}^{\mathit{ub}}$ is that $\mathsf{Ag}_{2}$ keeps a belief
$(s_{1},b_{1})$, about $\mathsf{Ag}_{1}\\!$’s belief at the current stage, and
then computes an action via $\mathit{Resolve}_{2}$ based on $(s_{1},b_{1})$
and $V_{\mathit{ub}}^{\Upsilon}$. This belief $(s_{1},b_{1})$ is _inferred_ ,
as $\mathsf{Ag}_{2}$ has no access to what $\mathsf{Ag}_{1}$ actually believes
about the state, except the initial belief which is common knowledge. However,
since $\mathsf{Ag}_{2}$ is fully-informed, it can simulate an inferred belief
update of $\mathsf{Ag}_{1}$, i.e., its belief about $\mathsf{Ag}_{1}\\!$’s
next belief.

We illustrate the obtained strategy $\sigma_{2}^{\mathit{ub}}$ in Fig. 1
(right). If $(s_{1},b_{1})$ is what $\mathsf{Ag}_{2}$ believes about
$\mathsf{Ag}_{1}\\!$’s belief and $(s_{1},s_{E})$ is the current state
observed by $\mathsf{Ag}_{2}$, then $\mathsf{Ag}_{2}$ chooses $a_{2}$ sampled
from the stage strategy $u_{2}^{\mathit{ub}}$ conditioned on $(s_{1},s_{E})$
in $[TV_{\mathit{ub}}^{\Upsilon}](s_{1},b_{1})$ computed via an LP (Yan et
al., 2023). At the same time, $\mathsf{Ag}_{1}$ takes $a_{1}\in A_{1}$ sampled
from a stage strategy $u_{1}$, where $\mathsf{Ag}_{2}$ does not know $u_{1}$.
Then, the game moves to the next state and thus $\mathsf{Ag}_{1}$ observes
$s_{1}^{\prime}\in S_{1}$. Based on $a_{1}$, $s_{1}^{\prime}$ and
$u_{2}^{\mathit{ub}}$, $\mathsf{Ag}_{2}$ updates its belief about
$\mathsf{Ag}_{1}\\!$’s belief via Bayesian inference to
$\smash{(s_{1}^{\prime},b_{1}^{s_{1},a_{1},u_{2}^{\mathit{ub}},s_{1}^{\prime}})}$.

We next show that the inferred-belief strategy is sound, i.e., the inferred-
belief carries enough information to generate an $\varepsilon$-minimax
strategy for $\mathsf{Ag}_{2}$.

######  Lemma 2 (Monotonicity)

If $V_{\mathit{ub}}^{\Upsilon}$ is an upper bound generated during the one-
sided NS-HSVI, then $[TV_{\mathit{ub}}^{\Upsilon}](s_{1},b_{1})\leq
V_{\mathit{ub}}^{\Upsilon}(s_{1},b_{1})$ for all $(s_{1},b_{1})\in S_{B}$.

######  Proof 4.1.

For a given set $\Upsilon$ of belief-value pairs, we first show
$[TV_{\mathit{ub}}^{\Upsilon}]$ is convex and continuous. From (Yan et al.,
2023, Theorem 6 and 7) we have that
$[TV_{\mathit{ub}}^{\Upsilon}](s_{1},b_{1})=\mbox{$\sup_{\alpha\in\Gamma^{\Upsilon}}$}\langle\alpha,(s_{1},b_{1})\rangle$,
where $\Gamma^{\Upsilon}\subseteq\mathbb{F}(S)$ and $L\leq\alpha(s)\leq U$ for
all $s\in S$ and $\alpha\in\Gamma^{\Upsilon}$. By (Horák et al., 2023,
Proposition 4.9), it follows that $[TV_{\mathit{ub}}^{\Upsilon}](s_{1},\cdot)$
is convex. For $b_{1},b_{1}^{\prime}\in\mathbb{P}(S_{E})$ and
$\alpha\in\Gamma^{\Upsilon}$, using (Yan et al., 2023, Theorem 1), we have
$|\langle\alpha,(s_{1},b_{1})\rangle-\langle\alpha,(s_{1},b_{1}^{\prime})\rangle|\leq
K_{\mathit{ub}}(b_{1},b_{1}^{\prime})$, where $K_{\mathit{ub}}$ measures
belief difference, and hence
$|[TV_{\mathit{ub}}^{\Upsilon}](s_{1},b_{1})-[TV_{\mathit{ub}}^{\Upsilon}](s_{1},b_{1}^{\prime})|\leq
K_{\mathit{ub}}(b_{1},b_{1}^{\prime})$.

Let $V_{\mathit{ub}}^{\Upsilon^{t}}$ and $I^{t}$ be the upper bound and the
associated index set after the $t$-th point-based update, respectively.
Similarly to (Horák et al., 2023, Lemma 9.11), we can now prove the
monotonicity of $[TV_{\mathit{ub}}^{\Upsilon^{t}}]$ by induction on
$t\in\mathbb{N}$. For $t{=}0$, since
$\Upsilon^{0}=\\{((s_{1}^{i},b_{1}^{i}),U)\in S_{B}{\times}\mathbb{R}\mid i\in
I^{0}\\}$ for some initial index set $I^{0}$. For any $(s_{1},b_{1})\in
S_{B}$, using (1), we have
$[TV_{\mathit{ub}}^{\Upsilon^{0}}](s_{1},b_{1})\leq\mbox{$\max_{s\in S\wedge
a\in A}$}r(s,a)+\beta U=(1-\beta)U+\beta
U=U=V_{\mathit{ub}}^{\Upsilon^{0}}(s_{1},b_{1})$.

For the inductive step, we assume that
$[TV_{\mathit{ub}}^{\Upsilon^{t}}](s^{\prime}_{1},b^{\prime}_{1})\leq
V_{\mathit{ub}}^{\Upsilon^{t}}(s^{\prime}_{1},b^{\prime}_{1})$ for all
$(s^{\prime}_{1},b^{\prime}_{1})\in S_{B}$. Thus $y_{i}\geq
V_{\mathit{ub}}^{\Upsilon^{t}}(s^{i}_{1},b^{i}_{1})\geq[TV_{\mathit{ub}}^{\Upsilon^{t}}](s^{i}_{1},b^{i}_{1})$
for $i\in I^{t}$. Let $(s_{1},b_{1})\in S_{B}$ be the belief for the
$(t{+}1)$-th point-based update. By lines 8 and 9 of (Yan et al., 2023,
Algorithm 1), we have
$y^{\star}=[TV_{\mathit{ub}}^{\Upsilon^{t}}](s_{1},b_{1})$ and
$\Upsilon^{t+1}=\Upsilon^{t}\cup\\{((s_{1},b_{1}),y^{\star})\\}$. Using (Yan
et al., 2023, Lemma 4), we have
$V_{\mathit{ub}}^{\Upsilon^{t}}(s^{\prime}_{1},b^{\prime}_{1})\geq
V_{\mathit{ub}}^{\Upsilon^{t+1}}(s^{\prime}_{1},b^{\prime}_{1})$ for all
$(s^{\prime}_{1},b^{\prime}_{1})\in S_{B}$, from which
$[TV_{\mathit{ub}}^{\Upsilon^{t}}](s^{i}_{1},b^{i}_{1})\geq[TV_{\mathit{ub}}^{\Upsilon^{t+1}}](s^{i}_{1},b^{i}_{1})$
for any $i\in I^{t+1}$. Therefore we have that
$y^{i}\geq[TV_{\mathit{ub}}^{\Upsilon^{t}}](s^{i}_{1},b^{i}_{1})\geq[TV_{\mathit{ub}}^{\Upsilon^{t+1}}](s^{i}_{1},b^{i}_{1})$
for any $i\in I^{t+1}$. Now, for any $(s_{1}^{\prime},b_{1}^{\prime})\in
S_{B}$, if $\smash{(\lambda_{i}^{\star})_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}}$ is a solution for
$V_{\mathit{ub}}^{\Upsilon^{t+1}}(s_{1}^{\prime},b_{1}^{\prime})$, then by
construction:

$\displaystyle\smash{V_{\mathit{ub}}^{\Upsilon^{t+1}}(s_{1}^{\prime},b_{1}^{\prime})}=\smash{\mbox{$\sum\nolimits_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}$}\lambda_{i}^{\star}y_{i}+K_{\mathit{ub}}(b_{1}^{\prime},\mbox{$\sum\nolimits_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}$}\lambda_{i}^{\star}b_{1}^{i})}$
$\displaystyle\geq\mbox{$\sum\nolimits_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}$}\lambda_{i}^{\star}[TV_{\mathit{ub}}^{\Upsilon^{t+1}}](s_{1}^{i},b_{1}^{i})+K_{\mathit{ub}}(b_{1}^{\prime},\mbox{$\sum\nolimits_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}$}\lambda_{i}^{\star}b_{1}^{i})$
by induction
$\displaystyle\geq\smash{[TV_{\mathit{ub}}^{\Upsilon^{t+1}}](s_{1}^{\prime},\mbox{$\sum\nolimits_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}$}\lambda_{i}^{\star}b_{1}^{i})+K_{\mathit{ub}}(b_{1}^{\prime},\mbox{$\sum\nolimits_{i\in
I^{t+1}_{s^{\prime}_{\vstretch{.75}{\hstretch{.75}{1}}}}}$}\lambda_{i}^{\star}b_{1}^{i})}$
since $[TV_{\mathit{ub}}^{\Upsilon^{t+1}}]$ is convex
$\displaystyle\geq[TV_{\mathit{ub}}^{\Upsilon^{t+1}}](s_{1}^{\prime},b_{1}^{\prime})$
since $[TV_{\mathit{ub}}^{\Upsilon^{t+1}}]$ is $K_{\mathit{ub}}$-continuous

and hence by induction $[TV_{\mathit{ub}}^{\Upsilon}]$ is monotone as
required.

######  Theorem 4.2 ($\varepsilon$-minimax strategy for $\mathsf{Ag}_{2}$).

The strategy $\sigma_{2}^{\mathit{ub}}$ in Algorithm 2 is an
$\varepsilon$-minimax strategy for $\mathsf{Ag}_{2}$ at
$(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})$, i.e.,
$\mathbb{E}_{(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})}^{\sigma_{1},\sigma_{2}^{\mathit{ub}}}[Y]\leq
V^{\star}(s_{1}^{\mathit{init}},b_{1}^{\mathit{init}})+\varepsilon$ for all
$\sigma_{1}\in\Sigma_{1}$.

######  Proof 4.3.

Consider $b{=}(s_{1},b_{1})\in S_{B}$. We assume that $\mathsf{Ag}_{2}$
follows $\mathit{Resolve}_{2}$ in Algorithm 2 for the first $t$ stages and
then follows the uniform strategy, and denote this strategy by
$\smash{\sigma_{2}^{b,t}}$. We prove by induction on $t\in\mathbb{N}$ that the
expected value of $Y$ from $b$ under $\smash{\sigma_{2}^{b,t}}$ has the
following upper bound:

$\smash{\mathbb{E}_{b}^{\sigma_{1},\sigma_{2}^{b,t}}[Y]\leq
V_{\mathit{ub}}^{\Upsilon}(b)+\beta^{t}(U-L)}\qquad\textup{ for all
}\sigma_{1}\in\Sigma_{1}.$ (4)

For $t=0$, the strategy $\smash{\sigma_{2}^{b,0}}$ implies that
$\mathsf{Ag}_{2}$ adopts the uniform strategy, and therefore (4) directly
follows as $U$ and $L$ are lower and upper bounds.

For the inductive step, we assume (4) holds for the first $t$ stages. The
strategy $\sigma_{2}^{b,t+1}$ implies that at $b=(s_{1},b_{1})$,
$\mathsf{Ag}_{2}$ takes $u_{2}^{\mathit{ub}}$ (line 4) and then if $a_{1}$ is
taken and $s_{1}^{\prime}$ is observed, follows the strategy
$\smash{\sigma_{2}^{b^{\prime},t}}$, where
$b^{\prime}=(s_{1}^{\prime},b_{1}^{\prime})$ and
$b_{1}^{\prime}=b_{1}^{s_{1},a_{1},u_{2}^{\mathit{ub}},s_{1}^{\prime}}$.
Letting $u_{1}\in\mathbb{P}(A_{1})$ be $\mathsf{Ag}_{1}\\!$’s stage strategy
at $b$ given by any $\sigma_{1}$, the left-hand side of (4) by replacing $t$
with $t+1$ equals:

$\displaystyle\mathbb{E}_{b,u_{1},u_{2}^{\mathit{ub}}}[r(s,a)]+\beta\mbox{$\sum_{(a_{1},s_{1}^{\prime})\in
A_{1}\times S_{1}}$}P(a_{1},s_{1}^{\prime}\mid
b,u_{1},u_{2}^{\mathit{ub}})\mathbb{E}_{b^{\prime}}^{\sigma_{1},\sigma_{2}^{b^{\prime},t}}[Y]$
$\displaystyle\leq\mathbb{E}_{b,u_{1},u_{2}^{\mathit{ub}}}[r(s,a)]+\beta\mbox{$\sum_{(a_{1},s_{1}^{\prime})\in
A_{1}\times S_{1}}$}P(a_{1},s_{1}^{\prime}\mid
b,u_{1},u_{2}^{\mathit{ub}})(V_{\mathit{ub}}^{\Upsilon}(b^{\prime})+\beta^{t}(U-L))$
by induction
$\displaystyle\leq\mathbb{E}_{b,u_{1}^{\mathit{ub}},u_{2}^{\mathit{ub}}}[r(s,a)]+\beta\mbox{$\sum_{(a_{1},s_{1}^{\prime})\in
A_{1}\times S_{1}}$}P(a_{1},s_{1}^{\prime}\mid
b,u_{1}^{\mathit{ub}},u_{2}^{\mathit{ub}})V_{\mathit{ub}}^{\Upsilon}(b^{\prime})+\beta^{t+1}(U-L)$
rearranging and since $u_{1}^{\mathit{ub}}$ is a minimax strategy
$\displaystyle=[TV_{\mathit{ub}}^{\Upsilon}](b)+\beta^{t+1}(U-L)$ by
definition of $[TV_{\mathit{ub}}^{\Upsilon}]$ $\displaystyle\leq
V_{\mathit{ub}}^{\Upsilon}(b)+\beta^{t+1}(U-L)$ by Lemma 2

as required. Now, letting
$\sigma_{2}^{\mathit{ub}}=\lim_{t\rightarrow\infty}\smash{\sigma_{2}^{b^{\mathit{init}},t}}$,
from (4) we have:

$\displaystyle\smash{\mathbb{E}_{b^{\mathit{init}}}^{\sigma_{1},\sigma_{2}^{\mathit{ub}}}[Y]\leq
V_{\mathit{ub}}^{\Upsilon}(b^{\mathit{init}})\leq
V^{\star}(b^{\mathit{init}})+\varepsilon}$

where the last inequality follows from the fact that
$V_{\mathit{ub}}^{\Upsilon}$ is returned by one-sided NS-HSVI.

######  Corollary 1 ($\varepsilon$-minimax strategy profile).

The profile $(\sigma_{1}^{\mathit{lb}},\sigma_{2}^{\mathit{ub}})$ is an
$\varepsilon$-minimax strategy profile.

##  5 Experiments

Figure 2: Snippets of a synthesised strategy for the pursuer and evader (from
left to right).

We evaluated our method on a variant of a _pursuit-evasion_ game (Horák et
al., 2023), inspired by mobile robotics (Chung et al., 2011; Isler and Karnad,
2008); see the appendix of Yan et al. (2023) for more detail. The game
involves a _pursuer_ , whose aim is to capture an _evader_. The pursuer is
equipped with a ReLU NN classifier, which takes the location (coordinates) of
the pursuer as input and outputs one of the 9 abstract grid cells, each
consisting of multiple polytopes, with the initial decomposition obtained by
computing the preimage of the NN (Matoba and Fleuret, 2020). The pursuer
therefore observes which cell it is in, but not its exact location, and knows
neither the exact location nor cell of the evader. The evader is fully
informed and knows the exact locations of both agents. The evader is captured
when both agents are in the same cell. We set a discount of $0.7$, reward 100
for capture and timeout of 2$h$. The (offline) lower and upper bounds for the
value of the initial belief are $5.0699$ and $6.0665$, respectively. We
synthesise strategies, which demonstrate that the pursuer can eventually
capture the evader with positive probability. Fig. 2 shows stage strategies
and lower bounds of states in the belief of the pursuer (top), and evader’s
strategies and inferred beliefs (bottom), at different stages. Lower bounds
are coloured green and inferred beliefs yellow. The agent positions are
highlighted (pink dot for pursuer and light green for evader). The belief of
the pursuer and inferred-belief of the evader do not always coincide, e.g., in
the third column, the state with bound $2.14$ is in the pursuer’s belief, but
not the inferred belief. We observe that the pursuer’s strategy selects the
moves according to the magnitude of the bound, e.g., in the fourth column, the
pursuer moves up or right, since the top right evader position has the highest
bound.

##  6 Conclusions

We have developed an efficient online method to synthesise strategies for a
variant of one-sided continuous-state POSGs with discrete observations and
validated it on a pursuit-evasion game, in which the partially-informed agent
uses a neural network for perception. We have shown that combining continual
resolving, inferred beliefs and HSVI bounds computed offline can generate an
$\varepsilon$-minimax strategy profile online. For future work, we will
consider aggressive assumed stage strategies for the fully-informed agent,
since uniform strategies may lead to a large number of states in the belief
and consequently large LPs to solve. Acknowledgements. This project was funded
by the ERC under the European Union’s Horizon 2020 research and innovation
programme (FUN2MODEL, grant agreement No.834115).

## References

  * Bosansky et al. (2014) Branislav Bosansky, Christopher Kiekintveld, Viliam Lisy, and Michal Pechoucek.  An exact double-oracle algorithm for zero-sum extensive-form games with imperfect information.  _Journal of Artificial Intelligence Research_ , 51:829–866, 2014.
  * Brown et al. (2020) Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong.  Combining deep reinforcement learning and search for imperfect-information games.  In _Advances in Neural Information Processing Systems_ , pages 17057–17069, 2020.
  * Burch et al. (2014) Neil Burch, Michael Johanson, and Michael Bowling.  Solving imperfect information games using decomposition.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 28(1), pages 602–608, 2014.
  * Carr et al. (2021) Steven Carr, Nils Jansen, Sudarshanan Bharadwaj, Matthijs TJ Spaan, and Ufuk Topcu.  Safe policies for factored partially observable stochastic games.  In _Robotics: Science and System XVII_ , 2021.
  * Chung et al. (2011) Timothy H Chung, Geoffrey A Hollinger, and Volkan Isler.  Search and pursuit-evasion in mobile robotics: A survey.  _Autonomous robots_ , 31:299–316, 2011.
  * Delage et al. (2023) Aurélien Delage, Olivier Buffet, Jilles S Dibangoye, and Abdallah Saffidine.  HSVI can solve zero-sum partially observable stochastic games.  _Dynamic Games and Applications_ , pages 1–55, 2023.
  * Doucet et al. (2001) Arnaud Doucet, Nando De Freitas, and Neil James Gordon, editors.  _Sequential Monte Carlo methods in practice_ , volume 1(2), 2001\. Springer.
  * Heinrich et al. (2015) Johannes Heinrich, Marc Lanctot, and David Silver.  Fictitious self-play in extensive-form games.  In _International Conference on Machine Learning_ , pages 805–813. PMLR, 2015.
  * Horák et al. (2023) Karel Horák, Branislav Bošanskỳ, Vojtěch Kovařík, and Christopher Kiekintveld.  Solving zero-sum one-sided partially observable stochastic games.  _Artificial Intelligence_ , 316:103838, 2023.
  * Isler and Karnad (2008) Volkan Isler and Nikhil Karnad.  The role of information in the cop-robber game.  _Theoretical Computer Science_ , 399(3):179–190, 2008.
  * Kovařík et al. (2022) Vojtěch Kovařík, Martin Schmid, Neil Burch, Michael Bowling, and Viliam Lisỳ.  Rethinking formal models of partially observable multiagent decision making.  _Artificial Intelligence_ , 303:103645, 2022.
  * Lanctot et al. (2009) Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling.  Monte Carlo sampling for regret minimization in extensive games.  In _Advances in Neural Information Processing Systems_ , volume 22, 2009.
  * Lanctot et al. (2017) Marc Lanctot, Vinicius Zambaldi, Audrūnas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel.  A unified game-theoretic approach to multiagent reinforcement learning.  In _Proceedings of the International Conference on Neural Information Processing Systems_ , page 4193–4206, 2017.
  * Lisỳ et al. (2015) Viliam Lisỳ, Marc Lanctot, and Michael H Bowling.  Online Monte Carlo counterfactual regret minimization for search in imperfect information games.  In _Proceedings of the International Conference on Autonomous Agents and Multiagent Systems_ , pages 27–36, 2015.
  * Matoba and Fleuret (2020) Kyle Matoba and François Fleuret.  Computing preimages of deep neural networks with applications to safety, 2020.  openreview.netforum?id=FN7$\\_$BUOG78e.
  * McAleer et al. (2021) Stephen McAleer, John B Lanier, Kevin A Wang, Pierre Baldi, and Roy Fox.  XDO: A double oracle algorithm for extensive-form games.  volume 34, pages 23128–23139, 2021.
  * Moravčík et al. (2017) Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling.  Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.  _Science_ , 356(6337):508–513, 2017.
  * Porta et al. (2006) Josep M Porta, Nikos Vlassis, Matthijs TJ Spaan, and Pascal Poupart.  Point-based value iteration for continuous POMDPs.  _Journal of Machine Learning Research_ , 7:2329–2367, 2006\.
  * Schmid et al. (2023) Martin Schmid, Matej Moravčík, Neil Burch, Rudolf Kadlec, Josh Davidson, Kevin Waugh, Nolan Bard, Finbarr Timbers, Marc Lanctot, G Zacharias Holland, et al.  Student of games: A unified learning algorithm for both perfect and imperfect information games.  _Science Advances_ , 9(46):eadg3256, 2023.
  * Šustr et al. (2019) Michal Šustr, Vojtěch Kovařík, and Viliam Lisý.  Monte Carlo continual resolving for online strategy computation in imperfect information games.  In _Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems_ , page 224–232, 2019.
  * Yan et al. (2022) Rui Yan, Gabriel Santos, Gethin Norman, David Parker, and Marta Kwiatkowska.  Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games (extended version).  arXiv.2202.06255, 2022.
  * Yan et al. (2023) Rui Yan, Gabriel Santos, Gethin Norman, David Parker, and Marta Kwiatkowska.  Partially observable stochastic games with neural perception mechanisms.  arXiv.2310.11566, 2023.
  * Zheng et al. (2022) Wei Zheng, Taeho Jung, and Hai Lin.  The Stackelberg equilibrium for one-sided zero-sum partially observable stochastic games.  _Automatica_ , 140:110231, 2022.
  * Zheng et al. (2023) Wei Zheng, Taeho Jung, and Hai Lin.  Continuous-observation one-sided two-player zero-sum partially observable stochastic game with public actions.  _IEEE Transactions on Automatic Control_ , pages 1–15, 2023.
  * Zinkevich et al. (2007) Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione.  Regret minimization in games with incomplete information.  In _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2007.