©2021 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

This work has been submitted to the IEEE for possible publication. Copyright
may be transferred without notice, after which this version may no longer be
accessible.

# Hamilton-Jacobi Equations for Two Classes of State-Constrained Zero-Sum
Games

Donggun Lee  Student Member, IEEE  and Claire J. Tomlin  Fellow, IEEE This
research is supported by ONR under the BRC program in multibody control
systems, by DARPA under the Assured Autonomy program, and by NSF grant
#1837244.Donggun Lee is with the Department of Mechanical Engineering,
University of California, Berkeley, USA<EMAIL_ADDRESS>J.
Tomlin is with the Department of Electrical Engineering and Computer Sciences,
University of California, Berkeley, USA<EMAIL_ADDRESS>
###### Abstract

This paper presents Hamilton-Jacobi (HJ) formulations for two classes of two-
player zero-sum games: one with a maximum cost value over time, and one with a
minimum cost value over time. In the zero-sum game setting, player A minimizes
the given cost while satisfying state constraints, and player B wants to
prevent player A’s success. For each class of problems, this paper presents
two HJ equations: one for time-varying dynamics, cost, and state constraint;
the other for time-invariant dynamics, cost, and state constraint. Utilizing
the HJ equations, the optimal control for each player is analyzed, and a
numerical algorithm is presented to compute the solution to the HJ equations.
A two-dimensional water system is introduced as an example to demonstrate the
proposed HJ framework.

##  1 Introduction

In two-player zero-sum games, one player’s control signal minimizes a cost
while satisfying a state constraint, while the second player’s control signal
tries either to maximize the cost or to violate the state constraint. An
optimal control problem may be considered a special case of the zero-sum game:
a control signal that minimizes the given cost while satisfying the constraint
is to be determined.

The Hamilton-Jacobi (HJ) partial differential equation (PDE) can be used to
represent zero-sum games for dynamical systems. The HJ formulation includes a
cost function in the form of the integration of a stage cost and a terminal
cost, nonlinear dynamics, control constraints, and state constraints.

The zero-sum game can be classified according to 1) whether the terminal time
is a given constant or a variable to be determined, and 2) whether or not
state constraints exist. If the problem is state-unconstrained and the
terminal time is a given constant, the Hamilton-Jacobi-Isaacs (HJI) PDE [1]
applies. For the state-constrained problem where the terminal time is given,
[2] presents the corresponding HJ equation. For problems where the terminal
time is a variable to be determined, [3] deals with the state-unconstrained
problem where the stage cost is zero, and [4, 5] deal with the zero-stage-cost
and state-constrained problems. This paper generalizes the previous work to
deal with the case of non-zero stage-cost and state constraint.

This paper proposes HJ equations for two classes of state-constrained problems
where the terminal time is a variable to be determined and the stage cost is
non-zero. In the first class of problems, player A wants to minimize the
maximum cost over time while satisfying the state constraint, and player B
wants to prevent player A’s success. This class of problems can be interpreted
as a robust control problem on the time and disturbances that optimizes the
maximum cost over time with respect to the worst disturbances. In the second
class of problems, player A wants to minimize the minimum cost over time while
satisfying the state constraint, and player B again wants to prevent player
A’s success. This class of problems can be interpreted as another robust
control problem on the disturbances that optimizes the minimum cost over time
with respect to the worst disturbances.

The proposed HJ equations can generally deal with both time-varying and time-
invariant dynamics, cost, and state constraint. Furthermore, this paper
presents additional HJ equations equivalent to the proposed HJ equations for
the time-invariant case.

###  1.1 Contribution

This paper presents four HJ equations for zero-sum games: two classes, and
time-varying and time-invariant. Among the four HJ equations, three equations
are proposed by this paper, and the other one is presented in [6] and reviewed
here for completeness. Also, this paper provides and presents analysis for the
optimal control signal for each player, numerical algorithm to compute the
proposed HJ equation, as well as a practical example.

###  1.2 Organization

The organization of this paper is as follows. Section 2 presents a
mathematical formulation for two classes of state-constrained zero-sum games.
Section 3 presents the HJ equations for the first class of problems both time-
varying and time-invariant. Section 4 presents the HJ equations for the second
class of problems for both the time-varying and time-invariant cases. Section
5 presents analysis for an optimal control signal based on the solution to the
HJ equations. Section 6 presents a numerical algorithm to compute the solution
to the HJ equations for each class of problem. Section 7 provides a practical
example where our HJ formulation can be utilized, and Section 8 concludes this
paper. Proofs are detailed in the Appendices.

##  2 Two Classes of State-Constrained Zero-Sum Games

We first present the two classes of two-player zero-sum games, called Problems
1 and 2. Consider a dynamical system:

$\displaystyle\dot{\mathrm{x}}(s)=f(s,\mathrm{x}(s),\alpha(s),\beta(s)),s\in[t,T],\text{
and }\mathrm{x}(t)=x,$ (1)

where $(t,x)$ are the initial time and state,
$\mathrm{x}\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow\mathbb{R}^{n}$ is the state trajectory,
$f\mathrel{\mathop{\mathchar 58\relax}}[0,T]\times\mathbb{R}^{n}\times A\times
B\rightarrow\mathbb{R}^{n}$ is the dynamics,
$A\subset\mathbb{R}^{m_{a}},B\subset\mathbb{R}^{m_{b}}$ are the control
constraints, $\alpha\in\mathcal{A}(t),\beta\in\mathcal{B}(t)$ are the control
signals, in each, player A controls $\alpha$ and player B controls $\beta$,
and the sets of measurable control signals are

$\displaystyle\begin{split}&\mathcal{A}(t)\coloneqq\\{\alpha\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow A~{}|~{}\|\alpha\|_{L^{\infty}(t,T)}<\infty\\},\\\
&\mathcal{B}(t)\coloneqq\\{\beta\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow
B~{}|~{}\|\beta\|_{L^{\infty}(t,T)}<\infty\\}.\end{split}$ (2)

In each zero-sum game, we specify each player’s control signal or strategy:
player A wants to minimize the cost under the state constraint, and player B
wants to prevent player A’s success, although the cost is defined in different
ways for Problems 1 and 2. In each problem, we introduce two value functions
depending on which players play first or second.

###### Problem 1

For given initial time and state $(t,x)$, solve

$\displaystyle\begin{split}&\vartheta_{1}^{+}(t,x)\coloneqq\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}\\\
&\quad\max_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\delta[\alpha](s))ds+g(\tau,\mathrm{x}(\tau)),\end{split}$
(3) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau],$ (4)

where $\mathrm{x}$ solves (1) for $(\alpha,\delta[\alpha])$; and solve

$\displaystyle\begin{split}&\vartheta_{1}^{-}(t,x)\coloneqq\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t)}\\\
&\quad\max_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\gamma[\beta](s),\beta(s))ds+g(\tau,\mathrm{x}(\tau)),\end{split}$
(5) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau],$ (6)

where $\mathrm{x}$ solves (1) for $(\gamma[\beta],\beta)$.

$\Delta(t)$ is a set of non-anticipative strategies for player B, and
$\Gamma(t)$ is a set of non-anticipative strategies for player A. The non-
anticipative strategy outputs a control signal for the second player as a
reaction to the first player’s control signal without using the future
information. The non-anticipative strategy has been introduced by Elliott and
Kalton [7]:

$\displaystyle\Delta(t)\coloneqq$
$\displaystyle\\{\delta\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}(t)\rightarrow\mathcal{B}(t)~{}|~{}\forall
s\in[t,\tau]\text{ and }\alpha,\bar{\alpha}\in\mathcal{A}(t),$
$\displaystyle\text{ if }\alpha(\tau)=\bar{\alpha}(\tau)\text{ a.e.
}\tau\in[t,s],$ $\displaystyle\text{ then
}\delta[\alpha](\tau)=\delta[\bar{\alpha}](\tau)\text{ a.e. }\tau\in[t,s]\\}.$
(7) $\displaystyle\Gamma(t)\coloneqq$
$\displaystyle\\{\gamma\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(t)\rightarrow\mathcal{A}(t)~{}|~{}\forall
s\in[t,\tau],\beta,\bar{\beta}\in\mathcal{B}(t),$ $\displaystyle\text{ if
}\beta(\tau)=\bar{\beta}(\tau)\text{ a.e. }\tau\in[t,s],$ $\displaystyle\text{
then }\gamma[\beta](\tau)=\gamma[\bar{\beta}](\tau)\text{ a.e.
}\tau\in[t,s]\\}.$ (8)

###### Problem 2

For given initial time and state $(t,x)$, solve

$\displaystyle\begin{split}&\vartheta_{2}^{+}(t,x)\coloneqq\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}\\\
&\quad\min_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\delta[\alpha](s))ds+g(\tau,\mathrm{x}(\tau)),\end{split}$
(9) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau],$ (10)

where $\mathrm{x}$ solves (1) for $(\alpha,\delta[\alpha])$; and solve

$\displaystyle\begin{split}&\vartheta_{2}^{-}(t,x)\coloneqq\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t)}\\\
&\quad\min_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\gamma[\beta](s),\beta(s))ds+g(\tau,\mathrm{x}(\tau)),\end{split}$
(11) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau],$ (12)

where $\mathrm{x}$ solves (1) for $(\gamma[\beta],\beta)$.

For both problems, $L\mathrel{\mathop{\mathchar
58\relax}}[t,T]\times\mathbb{R}^{n}\times A\times B\rightarrow\mathbb{R}$ is
the stage cost, $g\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is the terminal
cost, $f\mathrel{\mathop{\mathchar 58\relax}}[t,T]\times\mathbb{R}^{n}\times
A\times B\rightarrow\mathbb{R}^{n}$ is the system dynamics, and
$c\mathrel{\mathop{\mathchar
58\relax}}[t,T]\times\mathbb{R}^{n}\rightarrow\mathbb{R}$ is the state
constraint function.

The difference between $\vartheta_{i}^{+}$ and $\vartheta_{i}^{-}$ ($i=1,2$)
is play order. In $\vartheta_{i}^{+}(t,x)$, at each time $s\in[t,T]$, player A
first plays $\alpha(s)$, and then player B reacts by following its own
strategy $\delta[\alpha](s)$. Despite this play order at each time, the choice
of player B’s strategy comes first since it should be chosen without
information about player A’s control signal. In other words, player B first
chooses its strategy, and then player A chooses its control signal. In
$\vartheta_{i}^{-}(t,x)$, at each time $s$, player B first plays $\beta(s)$,
and then player A reacts with its strategy $\gamma[\beta](s)$. Similarly to
$\vartheta_{i}^{+}(t,x)$, in $\vartheta_{i}^{-}(t,x)$, player A first chooses
its strategy, and then player B chooses its control signal.

Problems 1 and 2 are representative of many practical problems. For Problem 1,
consider two water systems where player A controls the water level of pond 1
that is connected to pond 2. Suppose player B is precipitation. Player A needs
to minimize the highest water level of pond 1 over time while satisfying
constraints for water level of pond 1 and 2 under the worst precipitation
assumption. For Problem 2, consider a car that tries to change its lane while
avoiding collision with other cars. Here, the cost is the distance to the goal
lane, and the car wants to successfully change lanes at some time in the given
time interval, while other cars might bother to lane change.

This paper assumes the following.

######  Assumption 1 (Lipschitz continuity and compactness)

  1. 1.

$A$ and $B$ are compact;

  2. 2.

$f\mathrel{\mathop{\mathchar 58\relax}}[0,T]\times\mathbb{R}^{n}\times A\times
B\rightarrow\mathbb{R}^{n}$, $f=f(t,x,a,b)$ is Lipschitz continuous in $(t,x)$
for each $(a,b)\in A\times B$;

  3. 3.

the stage cost $L\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times A\times B\rightarrow\mathbb{R}$,
$L=L(t,x,a,b)$ is Lipschitz continuous in $(t,x)$ for each $(a,b)\in A\times
B$;

  4. 4.

for all $(t,x)\in[0,T]\times\mathbb{R}^{n}$, $\\{f(t,x,a,b)~{}|~{}a\in A,b\in
B\\}$ and $\\{L(t,x,a,b)~{}|~{}a\in A,b\in B\\}$ are compact and convex;

  5. 5.

the terminal cost $g\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\rightarrow\mathbb{R}$, $g=g(t,x)$ is
Lipschitz continuous in $(t,x)$;

  6. 6.

the state constraint $c\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\rightarrow\mathbb{R}$, $c=c(t,x)$ is
Lipschitz continuous in $(t,x)$;

  7. 7.

the stage cost ($L$) and the terminal cost ($g$) are bounded below.

##  3 Hamilton-Jacobi Equations for Problem 1

###  3.1 HJ equation for Problem 1 (time-varying case)

In this subsection, we derive an HJ equation for Problem 1
($\vartheta_{1}^{\pm}$). Unfortunately, for some initial time and state
$(t,x)$, there is no control $\alpha$ (or strategy $\gamma$) of player A that
satisfies the state constraint for all strategies $\delta$ of player B (or
control signal $\beta$). In this case, $\vartheta_{1}^{\pm}(t,x)$ is infinity.
Thus, $\vartheta_{1}^{\pm}$ is neither continuous nor differentiable in
$(0,T)\times\mathbb{R}^{n}$.

To overcome this issue, we utilize an additional variable $z\in\mathbb{R}$ to
define continuous value functions $V_{1}^{\pm}$ in (13) and (14) that combine
the cost $\vartheta_{1}^{\pm}$ in (3) or (5), and the constraint in (4) or
(6). We call this method the augmented-$z$ method. This method has been
utilized to handle state constraints to solve other HJ problems [2, 6].
$V_{1}^{\pm}$ is well-defined in $[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$.

$\displaystyle
V_{1}^{+}(t,x,z)\coloneqq\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}J_{1}(t,x,z,\alpha,\delta[\alpha]),$
(13) $\displaystyle
V_{1}^{-}(t,x,z)\coloneqq\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t)}J_{1}(t,x,z,\gamma[\beta],\beta),$
(14)

where cost $J_{1}\mathrel{\mathop{\mathchar
58\relax}}(t,x,z,\alpha,\beta)\rightarrow\mathbb{R}$ is defined as follows:

$\displaystyle\begin{split}&J_{1}(t,x,z,\alpha,\beta)\coloneqq\max_{\tau\in[t,T]}\max\bigg{\\{}\max_{s\in[t,\tau]}c(s,\mathrm{x}(s)),\\\
&\quad\quad\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\beta(s))ds+g(\tau,\mathrm{x}(\tau))-z\bigg{\\}},\end{split}$
(15)

where $\mathrm{x}$ solves (1). Define the auxiliary state trajectory
$\mathrm{z}$ solving

$\displaystyle\dot{\mathrm{z}}(s)=-L(s,\mathrm{x}(s),\alpha(s),\beta(s)),s\in[t,T],\text{
and }\mathrm{z}(t)=z.$ (16)

Then, (1) and (16) are the joint ODEs whose solution is the augmented state
trajectories: $(\mathrm{x},\mathrm{z})\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow\mathbb{R}^{n+1}$

$\displaystyle\small\begin{bmatrix}\dot{\mathrm{x}}(s)\\\
\dot{\mathrm{z}}(s)\end{bmatrix}=\begin{bmatrix}f(s,\mathrm{x}(s),\alpha(s),\beta(s))\\\
-L(s,\mathrm{x}(s),\alpha(s),\beta(s))\end{bmatrix},s\in[t,T],\begin{bmatrix}\mathrm{x}(t)\\\
\mathrm{z}(t)\end{bmatrix}=\begin{bmatrix}x\\\ z\end{bmatrix}.$ (17)

Then, $J_{1}$ in (15) becomes

$\displaystyle\begin{split}J_{1}=&\max_{\tau\in[t,T]}\max\Big{\\{}\max_{s\in[t,\tau]}c(s,\mathrm{x}(s)),g(\tau,\mathrm{x}(\tau))-\mathrm{z}(\tau)\Big{\\}}\\\
=&\max\Big{\\{}\max_{s\in[t,T]}c(s,\mathrm{x}(s)),\max_{\tau\in[t,T]}g(\tau,\mathrm{x}(\tau))-\mathrm{z}(\tau)\Big{\\}}.\end{split}$
(18)

The last equality is derived by the distributive property of the maximum
operations.

Lemma 1 shows that $\vartheta_{1}^{\pm}$ can be found if $V_{1}^{\pm}$ are
known. For initial time and state $(t,x)$ for which there is no control or
strategy of player A such that the state constraint ($c(s,\mathrm{x}(s))\leq
0,s\in[t,T]$) is satisfied for player B’s best control signal or strategy,
$V_{1}^{\pm}(t,x,z)$ is always greater than 0 for all $z\in\mathbb{R}$. In
this case, Lemma 1 implies that $\vartheta_{1}^{\pm}(t,x)$ is infinity.

######  Lemma 1 (Equivalence of two value functions)

Suppose Assumption 1 holds. For all $(t,x)\in[0,T]\times\mathbb{R}^{n}$,
$\vartheta_{1}^{+}$ ((3) subject to (4)), $\vartheta_{1}^{-}$ ((5) subject to
(6)), $V_{1}^{+}$ in (13), and $V_{1}^{-}$ in (14) have the following
relationship.

$\displaystyle\vartheta_{1}^{\pm}(t,x)=\min z\text{ subject to
}V_{1}^{\pm}(t,x,z)\leq 0.$ (19)

This implies that

$\displaystyle\begin{split}\vartheta_{1}^{+}(t,x)&=\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}\max_{\tau\in[t,T]}\\\
&\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\delta[\alpha](s))ds+g(\tau,\mathrm{x}(\tau)),\end{split}$
(20) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,T],$ (21)

where $\mathrm{x}$ solves (1) for $(\alpha,\delta[\alpha])$, and

$\displaystyle\begin{split}\vartheta_{1}^{-}(t,x)&=\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t)}\max_{\tau\in[t,T]}\\\
&\int_{t}^{\tau}L(s,\mathrm{x}(s),\gamma[\beta](s),\beta(s))ds+g(\tau,\mathrm{x}(\tau)),\end{split}$
(22) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,T],$ (23)

where $\mathrm{x}$ solves (1) for $(\gamma[\beta],\beta)$.

Proof. See Appendix .1.

The rest of this subsection focuses on the derivation of the corresponding HJ
equation for $V_{1}^{\pm}$. The HJ equation is based on the principle of
dynamic programming in Lemma 2.

######  Lemma 2 (Optimality condition)

Fix $(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$. Consider a small
step $h>0$ such that $t+h\leq T$, $V_{1}^{+}$ (13) has the following property:

$\displaystyle\begin{split}&V_{1}^{+}(t,x,z)=\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}\max\Big{\\{}\max_{s\in[t,t+h]}c(s,\mathrm{x}(s)),\\\
&\max_{s\in[t,t+h]}g(\mathrm{x}(s))-\mathrm{z}(s),V_{1}^{+}(t+h,\mathrm{x}(t+h),\mathrm{z}(t+h))\Big{\\}},\end{split}$
(24)

where $(\mathrm{x},\mathrm{z})$ solves (17) for $(\alpha,\delta[\alpha])$.
Similarly, for $V_{1}^{-}$ (14),

$\displaystyle\begin{split}&V_{1}^{-}(t,x,z)=\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t)}\max\Big{\\{}\max_{s\in[t,t+h]}c(s,\mathrm{x}(s)),\\\
&\max_{s\in[t,t+h]}g(\mathrm{x}(s))-\mathrm{z}(s),V_{1}^{-}(t+h,\mathrm{x}(t+h),\mathrm{z}(t+h))\Big{\\}},\end{split}$
(25)

where $(\mathrm{x},\mathrm{z})$ solves (17) for $(\gamma[\beta],\beta)$.

Proof. See Appendix .2.

Theorem 1 presents the corresponding HJ equations for $V_{1}^{\pm}$ in (13)
and (14) using viscosity theory. Intuitively, the HJ equation in Theorem 1 is
derived as $h$ in Lemma 2 converges to zero.

###### Theorem 1

(HJ equation for Problem 1) For all
$(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$, $V_{1}^{\pm}$ in (13)
and (14) is the unique viscosity solution to the HJ equation:

$\displaystyle\begin{split}\max\Big{\\{}c(t,x)-&V_{1}^{\pm}(t,x,z),g(t,x)-z-V_{1}^{\pm}(t,x,z),\\\
&V_{1,t}^{\pm}-\bar{H}^{\pm}(t,x,z,D_{x}V_{1}^{\pm},D_{z}V_{1}^{\pm})\Big{\\}}=0\end{split}$
(26)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where
$\bar{H}^{\pm}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle\bar{H}^{+}(t,x,z,p,q)\coloneqq\max_{a\in A}\min_{b\in B}-p\cdot
f(t,x,a,b)+qL(t,x,a,b),$ (27)
$\displaystyle\bar{H}^{-}(t,x,z,p,q)\coloneqq\min_{b\in B}\max_{a\in A}-p\cdot
f(t,x,a,b)+qL(t,x,a,b),$ (28)

and

$\displaystyle V_{1}^{\pm}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (29)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$. Denote
$V_{1,t}^{\pm}=\frac{\partial V_{1}^{\pm}}{\partial t}$,
$D_{x}V_{1}^{\pm}=\frac{\partial V_{1}^{\pm}}{\partial x}$, and
$D_{z}V_{1}^{\pm}=\frac{\partial V_{1}^{\pm}}{\partial z}$.

Proof. See Appendix .3.

###  3.2 HJ equation for Problem 1 (time-invariant case)

We define the problem as time-invariant if the stage cost, terminal cost,
dynamics, and state constraints are all independent of time.

In this section, we convert $\vartheta_{1}^{\pm}$ ((3) subject to (4) and (5)
subject to (6)) to a fixed-terminal-time problem for the time-invariant case
of Problem 1, which allows to utilize methods for the fixed-terminal-time
problems [2]. In the fixed-terminal-time problem, optimal control signals of
players have to be determined, but the terminal time does not need to be
specified but is given.

The conversion of Problem 1 to a fixed-terminal-time problem by introducing a
freezing control signal $\mu\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow[0,1]$ to the dynamics and a set of freezing control
signals:

$\displaystyle\dot{\mathrm{x}}(s)=f(\mathrm{x}(s),\alpha(s),\beta(s))\mu(s),s\in[t,T],\mathrm{x}(t)=x,$
(30) $\displaystyle\mathcal{M}(t)\coloneqq\\{\mu\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow[0,1]~{}|~{}\|\mu\|_{L^{\infty}(t,T)}<\infty\\}.$
(31)

This freezing control signal controls the contribution of the two players to
the system. For example, $\mu(s)=0$ implies that the state stops at $s$, and
the two players do not contribute to the system. On the other hand, $\mu(s)=1$
allows the state evolves by the control signals of the players. The maximum
over $\tau$ operation in Problem 1 can be replaced by the maximum over the
freezing control signal if it eliminates contribution of the two players after
the maximal terminal time.

We present fixed-terminal-time problems as below:

$\displaystyle\begin{split}\tilde{\vartheta}_{1}^{+}(t&,x)\coloneqq\sup_{\delta\in\Delta(t),\nu_{A}\in\textrm{N}_{A}(t)}\inf_{\alpha\in\mathcal{A}(t)}\\\
&\int_{t}^{T}L(\mathrm{x}(s),\alpha(s),\delta[\alpha](s))\nu_{A}[\alpha](s)ds+g(\mathrm{x}(T)),\end{split}$
(32) $\displaystyle\quad\quad\quad\text{subject to }c(\mathrm{x}(s))\leq
0,s\in[t,T],$ (33)

where $\mathrm{x}$ solves (30) for $(\alpha,\delta[\alpha],\nu_{A}[\alpha])$;

$\displaystyle\begin{split}\tilde{\vartheta}_{1}^{-}(t&,x)\coloneqq\inf_{\tilde{\gamma}\in\tilde{\Gamma}(t)}\sup_{\beta\in\mathcal{B}(t),\mu\in\mathcal{M}(t)}\\\
&\int_{t}^{T}L(\mathrm{x}(s),\tilde{\gamma}[\beta,\mu](s),\beta(s))\mu(s)ds+g(\mathrm{x}(T)),\end{split}$
(34) $\displaystyle\quad\quad\quad\text{subject to }c(\mathrm{x}(s))\leq
0,s\in[t,T],$ (35)

where $\mathrm{x}$ solves (30) for $(\tilde{\gamma}[\beta,\mu],\beta,\mu)$.
$\textrm{N}_{A}$ is a set of non-anticipative strategies for the freezing
control to player A, and $\tilde{\Gamma}$ is a set of non-anticipative
strategies for player A to player B and the freezing control:

$\displaystyle\textrm{N}_{A}(t)\coloneqq\\{\nu_{A}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}(t)\rightarrow\mathcal{M}(t)~{}|~{}\forall
s\in[t,\tau],\alpha,\bar{\alpha}\in\mathcal{A}(t),$
$\displaystyle~{}~{}~{}\text{if }\alpha(\tau)=\bar{\alpha}(\tau)\text{ a.e.
}\tau\in[t,s],$ $\displaystyle~{}~{}~{}\text{then
}\nu_{A}[\alpha](\tau)=\nu_{A}[\bar{\alpha}](\tau)\text{ a.e.
}\tau\in[t,s]\\},$ (36)
$\displaystyle\tilde{\Gamma}(t)\coloneqq\\{\tilde{\gamma}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(t)\times\mathcal{M}(t)\rightarrow\mathcal{A}(t)~{}|~{}\forall
s\in[t,\tau],\beta,\bar{\beta}\in\mathcal{B}(t),$
$\displaystyle~{}~{}~{}\mu,\bar{\mu}\in{\mathcal{M}}(t),\text{if
}\beta(\tau)=\bar{\beta}(\tau),\mu(\tau)=\bar{\mu}(\tau)\text{ a.e.
}\tau\in[t,s],$ $\displaystyle~{}~{}~{}\text{then
}\tilde{\gamma}[\beta,\mu](\tau)=\tilde{\gamma}[\bar{\beta},\bar{\mu}](\tau)\text{
a.e. }\tau\in[t,s]\\}.$ (37)

After introducing the auxiliary variable $z\in\mathbb{R}$, define cost
$\tilde{J}$ by combining the cost and the constraint of
$\tilde{\vartheta}_{1}^{\pm}$:

$\displaystyle\begin{split}&\tilde{J}(t,x,z,\alpha,\beta,\mu)\coloneqq\max\big{\\{}\max_{s\in[t,T]}c(\mathrm{x}(s)),g(\mathrm{x}(T))-\mathrm{z}(T)\big{\\}},\end{split}$
(38)

where $(\mathrm{x},\mathrm{z})$ solves, for $s\in[t,T]$,

$\displaystyle\begin{split}&\begin{bmatrix}\dot{\mathrm{x}}(s)\\\
\dot{\mathrm{z}}(s)\end{bmatrix}=\begin{bmatrix}f(\mathrm{x}(s),\alpha(s),\beta(s))\\\
-L(\mathrm{x}(s),\alpha(s),\beta(s))\end{bmatrix}\mu(s),~{}\begin{bmatrix}\mathrm{x}(t)\\\
\mathrm{z}(t)\end{bmatrix}=\begin{bmatrix}x\\\ z\end{bmatrix}.\end{split}$
(39)

Lemma 3 claims that the zero-sum games whose cost is $\tilde{J}$ are
equivalent to $V_{1}^{\pm}$ in (13) and (14), which corresponds to
$\vartheta_{1}^{\pm}$.

###### Lemma 3

Consider $V_{1}^{\pm}$ in (13) and (14), and $\tilde{J}$ in (38). For all
$(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$,

$\displaystyle
V_{1}^{+}(t,x,z)=\sup_{\begin{subarray}{c}\delta\in\Delta(t),\\\
\nu_{A}\in\textrm{N}_{A}(t)\end{subarray}}\inf_{\alpha\in\mathcal{A}(t)}\tilde{J}(t,x,z,\alpha,\delta[\alpha],\nu_{A}[\alpha]),$
(40) $\displaystyle
V_{1}^{-}(t,x,z)=\inf_{\tilde{\gamma}\in\tilde{\Gamma}(t)}\sup_{\begin{subarray}{c}\beta\in\mathcal{B}(t),\\\
\mu\in\mathcal{M}(t)\end{subarray}}\tilde{J}(t,x,z,\tilde{\gamma}[\beta,\mu],\beta,\mu).$
(41)

Proof. See Appendix .4.

###### Corollary 1

(Equivalent fixed-terminal-time game to the time-invariant Problem 1)

$\displaystyle\vartheta_{1}^{\pm}\equiv\tilde{\vartheta}_{1}^{\pm},$ (42)

where $\vartheta_{1}^{+}$ is (3) subject to (4), $\vartheta_{1}^{-}$ is (5)
subject to (6), $\tilde{\vartheta}_{1}^{+}$ is (32) subject to (33), and
$\tilde{\vartheta}_{1}^{-}$ is (34) subject to (35).

Proof. Let the right hand terms in (40) and (41) be denoted as $W_{1}^{\pm}$.
By Corollary 5.3 in [2], $\tilde{\vartheta}_{1}^{\pm}(t,x)=\min z$ subject to
$W_{1}^{\pm}(t,x,z)\leq 0$. This fact and Lemma 1 allow us to conclude (42). ∎

This corollary remarks that the free-terminal-time games
($\vartheta_{1}^{\pm}$) can be converted to fixed-terminal-time games
($\tilde{\vartheta}_{1}^{\pm}$), in which only control signals and strategies
have to be specified, since the terminal time is fixed.

In Lemma 3, $V_{1}^{\pm}$ is converted to a fixed-terminal-time game, whose
corresponding HJ equation has been investigated in [2]. This allows us to
derive an HJ equation for the time-invariant Problem 1 in Theorem 2.

###### Theorem 2

(HJ equation for Problem 1 (time-invariant version)) Consider Problem 1 for
the time-invariant case. For all
$(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$, $V_{1}^{\pm}$ in (13)
and (14) is the unique viscosity solution to the HJ equation:

$\displaystyle\begin{split}\max&\Big{\\{}c(x)-V_{1}^{\pm}(t,x,z),\\\
&V_{1,t}^{\pm}-\min\big{\\{}0,\bar{H}^{\pm}(x,z,D_{x}V_{1}^{\pm},D_{z}V_{1}^{\pm})\big{\\}}\Big{\\}}=0\end{split}$
(43)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}^{+}$ and
$\bar{H}^{-}$ are defined in (27) and (28), respectively, without the time
dependency, and

$\displaystyle V_{1}^{\pm}(T,x,z)=\max\\{c(x),g(x)-z\\}$ (44)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

Proof. See Appendix .5.
Note that the Hamiltonian $\bar{H}^{\pm}$ in (43) is time-invariant.

We observe that the right two terms in the HJ equation (26) $\max\\{g-z-
V_{1}^{\pm},V_{1,t}^{\pm}-\bar{H}^{\pm}\\}$ become
$V_{1,t}^{\pm}-\min\\{0,\bar{H}^{\pm}\\}$ in (43). Note that these two terms
are not algebraically equal.

###  3.3 HJ equation for Problem 1 (optimal control setting)

In this subsection, we solve Problem 1 in the optimal control problem setting:
for given initial time and state $(t,x)$,

$\displaystyle\vartheta_{1}(t,x)$
$\displaystyle\coloneqq\inf_{\alpha\in\mathcal{A}(t)}\max_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds+g(\tau,\mathrm{x}(\tau)),$
(45) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau],$ (46)

where $\mathrm{x}$ solves

$\displaystyle\dot{\mathrm{x}}(s)=f(s,\mathrm{x}(s),\alpha(s)),s\in[t,T],\text{
and }\mathrm{x}(t)=x.$ (47)

Section 3.1 and 3.2 present the HJ equations for Problem 1 in the zero-sum
game setting. By removing player B in the zero-sum game, we can get HJ
equations for Problem 1 in the optimal control setting. Thus, Theorem 1 and 2
imply the following remark.

###### Remark 1

(HJ equation for Problem 1 (optimal control setting)) Let $V_{1}$ be the
unique viscosity solution to the HJ equation:

$\displaystyle\begin{split}\max\Big{\\{}c(t,x)-&V_{1}(t,x,z),g(t,x)-z-V_{1}(t,x,z),\\\
&V_{1,t}-\bar{H}(t,x,z,D_{x}V_{1},D_{z}V_{1})\Big{\\}}=0\end{split}$ (48)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where
$\bar{H}\mathrel{\mathop{\mathchar
58\relax}}[0,T]\times\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}^{n}\times\mathbb{R}\rightarrow\mathbb{R}$

$\displaystyle\bar{H}(t,x,z,p,q)\coloneqq\max_{a\in A}-p\cdot
f(t,x,a)+qL(t,x,a),$ (49)

and

$\displaystyle V_{1}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (50)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$. Then,

$\displaystyle\vartheta_{1}(t,x)=\min z\text{ subject to }V_{1}(t,x,z)\leq 0,$
(51)

where $\vartheta_{1}$ is (45) subject to (46).

If Problem 1 is time-invariant, $V_{1}$ is the unique viscosity solution to
the HJ equation:

$\displaystyle\begin{split}\max&\Big{\\{}c(x)-V_{1}(t,x,z),\\\
&V_{1,t}-\min\big{\\{}0,\bar{H}(x,z,D_{x}V_{1},D_{z}V_{1})\big{\\}}\Big{\\}}=0\end{split}$
(52)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}$ is defined in
(49) with ignoring the time dependency, and

$\displaystyle V_{1}(T,x,z)=\max\\{c(x),g(x)-z\\}$ (53)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

##  4 Hamilton-Jacobi Equations for Problem 2

Problem 2 in the zero-sum game setting is defined in Section 2. Section 4.1
and 4.2 present HJ equations for the time-varying and time-invariant Problem
2, respectively. Section 4.3 presents HJ equations for Problem 2 and the time-
invariant Problem 2 in the optimal control setting.

For Problem 2 in the zero-sum game and optimal control settings, the
corresponding HJ equations have been presented in the authors’ previous work
[6]. This section first presents this previous work and then proposes HJ
equations for the time-invariant version.

###  4.1 HJ equation for the time-varying Problem 2

This subsection provides an HJ formulation for Problem 2: solve
$\vartheta_{2}^{+}$ in (9) subject to (10) and $\vartheta_{2}^{-}$ in (11)
subject to (12). For $(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$,
define the augmented value functions corresponding to the upper and lower
value functions ($\vartheta_{2}^{\pm}$):

$\displaystyle
V_{2}^{+}(t,x,z)\coloneqq\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}J_{2}(t,x,a,\alpha,\delta[\alpha]),$
(54) $\displaystyle
V_{2}^{-}(t,x,z)\coloneqq\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t)}J_{2}(t,x,a,\gamma[\beta],\beta),$
(55)

where cost $J_{2}\mathrel{\mathop{\mathchar
58\relax}}(t,x,z,\alpha,\beta)\rightarrow\mathbb{R}$ is defined as follows:

$\displaystyle\begin{split}J_{2}(t,x&,z,\alpha,\beta)\coloneqq\min_{\tau\in[t,T]}\max\bigg{\\{}\max_{s\in[t,\tau]}c(s,\mathrm{x}(s)),\\\
&\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\beta(s))ds+g(\tau,\mathrm{x}(\tau))-z\bigg{\\}},\end{split}$
(56)

where $\mathrm{x}$ solves (1) for $(\alpha,\beta)$. [6] proved that, for all
$(t,x)\in[t,T]\times\mathbb{R}^{n}$,

$\displaystyle\vartheta_{2}^{\pm}(t,x)=\min z\text{ subject to
}V_{2}^{\pm}(t,x,z)\leq 0,$ (57)

and $V_{2}^{\pm}$ are the unique viscosity solutions to the HJ equations in
Theorem 3.

###### Theorem 3

(HJ equation for Problem 2) [6] For all
$(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$, $V_{2}^{\pm}$ in (54)
and (55) are the unique viscosity solutions to the HJ equations:

$\displaystyle\max\Big{\\{}c$
$\displaystyle(t,x)-V_{2}^{\pm}(t,x,z),\min\big{\\{}g(t,x)-z-V_{2}^{\pm}(t,x,z),$
$\displaystyle
V_{2,t}^{\pm}-\bar{H}^{\pm}(t,x,z,D_{x}V_{2}^{\pm},D_{z}V_{2}^{\pm})\big{\\}}\Big{\\}}=0$
(58)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}^{\pm}$ are
defined in (27) and (28), and

$\displaystyle V_{2}^{\pm}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (59)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

We observe that the difference between the two types of HJ equations for
$V_{1}^{\pm}$ and $V_{2}^{\pm}$ is that the minimum operation in (58) for
$V_{2}^{\pm}$ is replaced by the maximum operation in (26). This is from the
difference between $\vartheta_{1}^{\pm}$ and $\vartheta_{2}^{\pm}$:
$\vartheta_{1}^{\pm}$ in (3) and (5) have $\max_{\tau}$ operation, and
$\vartheta_{2}^{\pm}$ in (9) and (11) have $\min_{\tau}$ operation.

###  4.2 HJ equation for Problem 2 (time-invariant case)

Through similar analysis to that in Section 3.2, this subsection derives the
HJ equations for the time-invariant Problem 2. For Problem 1, the freezing
control signal $\mu\mathrel{\mathop{\mathchar 58\relax}}[t,T]\rightarrow[0,1]$
allows to convert to the fixed-terminal-time problems by replacing the maximum
over $\tau$ operation in Problem 1 to the supremum over the freezing control
signal or strategy. Instead, Problem 2 is specified in terms of the minimum
over $\tau$ operation, which will be replaced by the infimum over the freezing
control signal or strategy.

Consider two fixed-terminal-time problems:

$\displaystyle\begin{split}\tilde{\vartheta}_{2}^{+}(t&,x)\coloneqq\sup_{\tilde{\delta}\in\tilde{\Delta}(t)}\inf_{\alpha\in\mathcal{A}(t),\mu\in\mathcal{M}(t)}\\\
&\int_{t}^{T}L(\mathrm{x}(s),\alpha(s),\tilde{\delta}[\alpha,\mu](s))\mu(s)ds+g(\mathrm{x}(T)),\end{split}$
(60) $\displaystyle\quad\quad\quad\text{subject to }c(\mathrm{x}(s))\leq
0,s\in[t,T],$ (61)

where $\mathrm{x}$ solves (30) for $(\alpha,\tilde{\delta}[\alpha,\mu],\mu)$,
$\mathcal{M}$ is defined in (31), and $\tilde{\delta}$ is the non-anticipative
strategy for player B to both player A and the freezing control:

$\displaystyle\tilde{\Delta}$
$\displaystyle(t)\coloneqq\\{\tilde{\delta}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}(t)\times\mathcal{M}(t)\rightarrow\mathcal{B}(t)~{}|~{}\forall
s\in[t,\tau],\alpha,\bar{\alpha}\in\mathcal{A}(t),$
$\displaystyle\mu,\bar{\mu}\in\mathcal{M}(t),\text{if
}\alpha(\tau)=\bar{\alpha}(\tau),\mu(\tau)=\bar{\mu}(\tau)\text{ a.e.
}\tau\in[t,s],$ $\displaystyle\text{then
}\tilde{\delta}[\beta,\mu](\tau)=\tilde{\delta}[\bar{\beta},\bar{\mu}](\tau)\text{
a.e. }\tau\in[t,s]\\};$ (62)
$\displaystyle\begin{split}\tilde{\vartheta}_{1}^{-}(t&,x)\coloneqq\inf_{\gamma\in\Gamma(t),\nu_{B}\in\textrm{N}_{B}(t)}\sup_{\beta\in\mathcal{B}(t)}\\\
&\int_{t}^{T}L(\mathrm{x}(s),\gamma[\beta](s),\beta(s))\nu_{B}[\beta](s)ds+g(\mathrm{x}(T)),\end{split}$
(63) $\displaystyle\quad\quad\quad\text{subject to }c(\mathrm{x}(s))\leq
0,s\in[t,T],$ (64)

where $\mathrm{x}$ solves (30) for $(\gamma[\beta],\beta,\nu_{B}[\beta])$, and
the non-anticipative strategy for the freezing control to player B is

$\displaystyle\textrm{N}_{B}(t)$
$\displaystyle\coloneqq\\{\nu_{B}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(t)\rightarrow\mathcal{M}(t)~{}|~{}\forall
s\in[t,\tau],\beta,\bar{\beta}\in\mathcal{B}(t),$ $\displaystyle\text{if
}\beta(\tau)=\bar{\beta}(\tau)\text{ a.e. }\tau\in[t,s],$
$\displaystyle\text{then
}\nu_{B}[\beta](\tau)=\nu_{B}[\bar{\beta}](\tau)\text{ a.e. }\tau\in[t,s]\\}.$
(65)

Recall $\tilde{J}$ in (38), which contains the cost and the constraint of
$\tilde{\vartheta}_{2}^{\pm}$. Following similar steps of the proof of Lemma
3, Lemma 4 can be proved.

###### Lemma 4

Recall $\tilde{J}$ in (38), and consider $V_{2}^{\pm}$ in (54) and (55). For
all $(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$,

$\displaystyle
V_{2}^{+}(t,x,z)=\sup_{\tilde{\delta}\in\tilde{\Delta}(t)}\inf_{\begin{subarray}{c}\alpha\in\mathcal{A}(t),\\\
\mu\in\mathcal{M}(t)\end{subarray}}\tilde{J}(t,x,z,\alpha,\tilde{\delta}[\alpha,\mu],\mu),$
(66) $\displaystyle
V_{2}^{-}(t,x,z)=\inf_{\begin{subarray}{c}\gamma\in\Gamma(t),\\\
\nu_{B}\in\textrm{N}_{B}(t)\end{subarray}}\sup_{\beta\in\mathcal{B}(t)}\tilde{J}(t,x,z,\gamma[\beta],\beta,\nu_{B}[\beta]).$
(67)

By combining the HJ formulation for the fixed-terminal-time problems [2] and
Lemma 4, the HJ equation for the time-invariant Problem 2 is derived in
Theorem 4. The proof for Theorem 4 is analogous to the proof for Theorem 2.

###### Theorem 4

(HJ equation for Problem 2 (time-invariant version)) Consider Problem 2 in the
time-invariant case. For all
$(t,x,z)\in[0,T]\times\mathbb{R}^{n}\times\mathbb{R}$, $V_{2}^{\pm}$ in (54)
and (55) are the unique viscosity solutions to the HJ equations:

$\displaystyle\begin{split}\max&\Big{\\{}c(x)-V_{2}^{\pm}(t,x,z),\\\
&V_{2,t}^{\pm}-\max\big{\\{}0,\bar{H}^{\pm}(x,z,D_{x}V_{2}^{\pm},D_{z}V_{2}^{\pm})\big{\\}}\Big{\\}}=0\end{split}$
(68)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}^{+}$ and
$\bar{H}^{-}$ are defined in (27) and (28), respectively, without the time
dependency, and

$\displaystyle V_{2}^{\pm}(T,x,z)=\max\\{c(x),g(x)-z\\}$ (69)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

In comparison between the HJ equations for Problem 2 and its time-invariant
version, $\min\\{g-z-V_{2}^{\pm},V_{2,t}^{\pm}-\bar{H}^{\pm}\\}$ in (58)
becomes $V_{2,t}^{\pm}-\max\\{0,\bar{H}^{\pm}\\}$ in (68). Note that the
difference between Problem 1 and 2 leads to the difference in HJ equations for
the time-invariant problems: (43) has the term
$V_{1,t}^{\pm}-\min\\{0,\bar{H}^{\pm}\\}$, but (68) has the term
$V_{2,t}^{\pm}-\max\\{0,\bar{H}^{\pm}\\}$.

###  4.3 HJ equation for Problem 2 (optimal control setting)

In this subsection, we solve Problem 2 in the optimal control setting: for
given initial time and state $(t,x)$,

$\displaystyle\vartheta_{2}(t,x)$
$\displaystyle\coloneqq\inf_{\alpha\in\mathcal{A}(t)}\min_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s))ds+g(\tau,\mathrm{x}(\tau)),$
(70) $\displaystyle\text{subject to }\quad c(s,\mathrm{x}(s))\leq 0,\quad
s\in[t,\tau],$ (71)

where $\mathrm{x}$ solves (47). By removing the contribution of player B in
Theorem 3 and 4, we solve $\vartheta_{2}$ using the HJ equations in the
following remark.

###### Remark 2

(HJ equation for Problem 2 (optimal control setting)) Let $V_{2}$ be the
unique viscosity solution to the HJ equation [6]:

$\displaystyle\max\Big{\\{}$ $\displaystyle
c(t,x)-V_{2}(t,x,z),\min\big{\\{}g(t,x)-z-V_{2}(t,x,z),$ $\displaystyle
V_{2,t}-\bar{H}(t,x,z,D_{x}V_{2},D_{z}V_{2})\big{\\}}\Big{\\}}=0$ (72)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}$ is defined in
(49), and

$\displaystyle V_{2}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (73)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$. Then,

$\displaystyle\vartheta_{2}(t,x)=\min z\text{ subject to }V_{2}(t,x,z)\leq 0,$
(74)

where $\vartheta_{2}$ is (70) subject to (71).

If Problem 2 is time-invariant, $V_{2}$ is the unique viscosity solution to
the HJ equation:

$\displaystyle\begin{split}\max&\Big{\\{}c(x)-V_{2}(t,x,z),\\\
&V_{2,t}-\max\big{\\{}0,\bar{H}(x,z,D_{x}V_{2},D_{z}V_{2})\big{\\}}\Big{\\}}=0\end{split}$
(75)

in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$, where $\bar{H}$ is defined in
(49) without the time dependency, and

$\displaystyle V_{2}(T,x,z)=\max\\{c(x),g(x)-z\\}$ (76)

on $\\{t=T\\}\times\mathbb{R}^{n}\times\mathbb{R}$.

##  5 Optimal Control Signal and Strategy

The optimal control signal or strategy for Problems 1 and 2 are specified by
the HJ equations in Section 3 and 4. This section utilizes the HJ equations in
Theorem 1 and 3, and the method in this section can be simply extended for the
other HJ equations in Theorems 2 and 4, and Remarks 1 and 2.

Recall $V_{i}^{\pm}$ ($i=1,2$) defined in (13), (14), (54), (55), and suppose
$V_{i}^{\pm}$ is computed from the HJ equations in Theorems 1 and 3.

Lemmas 3 and 4 imply the following remark.

######  Remark 3 (Find $\vartheta_{i}^{\pm}$ from $V_{i}^{\pm}$)

For initial time $t=0$ and state $x\in\mathbb{R}^{n}$,

$\displaystyle(\mathrm{x}_{*}(0),\mathrm{z}_{*}(0))=(x,\vartheta_{i}^{\pm}(0,x)),$
(77)

where $(\mathrm{x}_{*},\mathrm{z}_{*})$ is an optimal trajectory for
$V_{i}^{\pm}$.

With the initial augmented state $(\mathrm{x}_{*}(0),\mathrm{z}_{*}(0))$, the
optimal control and strategy can be found at
$(t,\mathrm{x}_{*}(t),\mathrm{z}_{*}(t))$, and the optimal state trajectory is
also updated by solving the ODE (17).

Define $\tilde{H}_{i}^{\pm}\mathrel{\mathop{\mathchar 58\relax}}A\times
B\rightarrow\mathbb{R}$ for a fixed
$(t,x,z)\in(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$

$\displaystyle\begin{split}\tilde{H}_{i}^{\pm}(a,b)\coloneqq&-D_{x}V_{i}^{\pm}(t,x,z)\cdot
f(t,x,a,b)\\\ &+D_{z}V_{i}^{\pm}(t,x,z)L(t,x,a,b)\end{split}$ (78)

for $i=1,2$, thus

$\displaystyle\bar{H}^{+}(t,x,z,D_{x}V_{i}^{+},D_{z}V_{i}^{+})=\max_{a\in
A}\min_{b\in B}\tilde{H}_{i}^{+}(a,b),$ (79)
$\displaystyle\bar{H}^{-}(t,x,z,D_{x}V_{i}^{-},D_{z}V_{i}^{-})=\min_{b\in
B}\max_{a\in A}\tilde{H}_{i}^{-}(a,b),$ (80)

where $\bar{H}^{+}$ and $\bar{H}^{-}$ are defined in (27) and (28),
respectively. In this section, we omit $(t,x,z)$ to simplify notation. Using
the notation with $\tilde{H}_{i}^{\pm}$ (78), the HJ equation (26) for
$V_{1}^{+}$ is equal to

$\displaystyle\max\\{c-V_{1}^{+},g-z-V_{1}^{+},V_{1,t}^{+}-\max_{a\in
A}\min_{b\in B}\tilde{H}_{1}^{+}(a,b)\\}=0.$ (81)

The HJ equation implies that optimal control signal or strategy is determined
by the gradient information at the current time and state $(t,x,z)$, but the
past history of the state trajectory and optimal control signals is not
necessary. For example, in $V_{1}^{+}$, $\alpha_{*}(t)=a_{*}$,
$\delta_{*}[\alpha_{*}](t)=b_{*}$ where $a_{*}$ and $b_{*}$ are solutions to

$\displaystyle\max\\{c-V_{1}^{+},g-z-
V_{1}^{+},V_{1,t}^{+}-\tilde{H}_{1}^{+}(a,b)\\}=0.$ (82)

at $(t,x,z)$. In other words, it is sufficient to specify optimal controls for
player A and B in $(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$ to generate the
optimal control signal or strategy. The maxmini solution $(a_{*},b_{*})$ for
the Hamiltonian $\bar{H}_{V}^{+}$ ($\max_{a\in A}\min_{b\in
B}\tilde{H}_{1}^{+}(a,b)$) is certainly optimal, but there are more solutions.
Similarly, for $V_{1}^{-}$ or $V_{2}^{\pm}$, any pair of $(a_{*},b_{*})$
satisfying the corresponding HJ equation is optimal.

In the HJ equation (81) (or (26)) for $V_{1}^{\pm}$, we have three terms:
$c-V_{1}^{\pm}$, $g-z-V_{1}^{\pm}$, or $V_{1,t}^{\pm}-\bar{H}^{\pm}$, and, at
least, one of these terms is zero. By considering which term is bigger or
smaller among the three terms, all possible optimal controls for
$\vartheta_{1}^{\pm}$ ($V_{1}^{\pm}$) and $\vartheta_{2}^{\pm}$
($V_{2}^{\pm}$) is derived in Remark 4.

Although $(a_{*},b_{*})$ satisfying the HJ equation is optimal, we need to
consider the order of players: player A plays first in $V_{i}^{+}$ but player
B plays first in $V_{i}^{-}$. In $V_{i}^{+}$, we first find a set of optimal
control for player A, and then investigate a set of optimal control for player
B when player A applies its optimal control. On the other hand, in
$V_{1}^{-}$, we first investigate a set of optimal control for player B, and
then find a set of optimal control for player A after applying an optimal
control of player B. Based on this argument, Remark 4 presents optimal
controls for $V_{i}^{+}$ according to classification, and optimal controls for
$V_{i}^{-}$ can be analogously extended.

######  Remark 4 (Optimal controls for $V_{i}^{+}$)

Fix $(t,x,z)\in(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$.

Optimal controls for $\vartheta_{1}^{+}$ ($V_{1}^{+}$) are the following:

  1. 1.

Case 1: $\max\\{c-V_{1}^{+},g-z-V_{1}^{+}\\}\geq V_{1,t}^{+}-\bar{H}^{+}$

$\displaystyle a_{*}\in\\{a\in A~{}|~{}V_{1,t}^{+}-\min_{b\in
B}\tilde{H}_{1}^{+}(a,b)\leq 0\\},$ (83) $\displaystyle b_{*}\in B;$ (84)

  2. 2.

Case 2: $\max\\{c-V_{1}^{+},g-z-V_{1}^{+}\\}<V_{1,t}^{+}-\bar{H}^{+}$

$\displaystyle a_{*}\in\arg\max_{a\in A}\min_{b\in B}\tilde{H}_{1}^{+}(a,b),$
(85) $\displaystyle b_{*}\in\arg\min_{b\in B}\tilde{H}_{1}^{+}(a_{*},b).$ (86)

Optimal controls for $\vartheta_{2}^{+}$ $(V_{2}^{+})$ are the following:

  1. 1.

Case 1: $c-V_{2}^{+}\geq V_{2,t}^{+}-\bar{H}^{+}$

(83) and (84) where $V_{1}^{+}$ and $\tilde{H}_{1}^{+}$ are replaced by
$V_{2}^{+}$ and $\tilde{H}_{2}^{+}$, respectively;

  2. 2.

Case 2: $g-z-V_{2}^{+}\geq V_{2,t}^{+}-\bar{H}^{+}\geq c-V_{2}^{+}$

(85) and (86) where $V_{1}^{+}$ and $\tilde{H}_{1}^{+}$ are replaced by
$V_{2}^{+}$ and $\tilde{H}_{2}^{+}$, respectively;

  3. 3.

Case 3: $V_{2,t}^{+}-\bar{H}^{+}\geq\max\\{c-V_{2}^{+},g-z-V_{2}^{+}\\}$

$\displaystyle a_{*}\in A,$ (87) $\displaystyle b_{*}\in\\{b\in
B~{}|~{}V_{2,t}^{+}-\tilde{H}_{2}^{+}(a_{*},b)\geq 0\\}.$ (88)

##  6 Numerical Computation for the Hamilton-Jacobi equation

In this section, we present a numerical algorithm based on level set methods
[8] to compute the solutions to the four HJ equations for Problems 1 and 2.
Algorithm 1 deals with the HJ equations for Problem 1 ((26), (43), (48),
(52)), and Algorithm 2 deals with the HJ equations for Problem 2 ((58), (68),
(72), (75)). Level set methods have been utilized to solve a variety of HJ
formulations [9, 5, 6].

Algorithm 1 solves the HJ equation (26) in two steps. At line 6 in Algorithm
1, we first compute the HJ PDE
($V_{1,t}^{\pm}-\bar{H}^{\pm}(t,x,z,D_{x}V_{1}^{\pm},D_{z}V_{1}^{\pm})=0$),
and line 7 in Algorithm 1 replaces $V_{1}^{\pm}$ by one of $c(t,x)$,
$g(t,x)-z$ or itself to satisfy the HJ equation (26).

For solving the HJ PDE at step 1, the Lax-Friedrichs scheme [10] is utilized
on the temporal discretization $\\{t_{0}=0,...,t_{K}=T\\}$ and the spatial
discretization
$\\{(x_{0},z_{0}),...,(x_{N},z_{N})\\}\subset\mathbb{R}^{n}\times\mathbb{R}$:

$\displaystyle
V_{1}^{\pm}(t_{k},x_{i},z_{i})=V_{1}^{\pm}(t_{k+1},x_{i},z_{i})-\Delta_{k}\hat{\bar{H}}^{\pm}(\phi_{x}^{+},\phi_{x}^{-},\phi_{z}^{+},\phi_{z}^{-}),$
(89)

where $\Delta_{k}=t_{k+1}-t_{k}$, $(\phi_{x}^{\pm},\phi_{z}^{\pm})$ are
numerical approximation for $(D_{x}V_{1}^{\pm},D_{z}V_{1}^{\pm})$ (gradients
with respect to $(x,z)$ at $(t_{k+1},x_{i},z_{i})$), and

$\displaystyle\hat{\bar{H}}^{\pm}(\phi_{x}^{+},\phi_{x}^{-},\phi_{z}^{+}$
$\displaystyle,\phi_{z}^{-})=\bar{H}^{\pm}\big{(}t_{k+1},x_{i},z_{i},\frac{\phi_{x}^{+}+\phi_{x}^{-}}{2},\frac{\phi_{z}^{+}+\phi_{z}^{-}}{2}\big{)}$
$\displaystyle-\alpha_{x}\cdot\frac{\phi_{x}^{+}+\phi_{x}^{-}}{2}-\alpha_{z}\frac{\phi_{z}^{+}+\phi_{z}^{-}}{2},$
(90)

where $\hat{H}^{\pm}$ are defined in (27) and (28), and
$\alpha_{x}=(\alpha_{x_{1}},...,\alpha_{x_{n}})$
($\alpha_{x_{i}}=\max|D_{p_{i}}\bar{H}^{\pm}|$) and
$\alpha_{z}(=\max|D_{q}\bar{H}^{\pm}|)$ are dissipation coefficients for
numerical viscosity, based on the partial derivatives of $\bar{H}^{\pm}$ [11].
The fifth-order accurate HJ WENO (weighted essentially nonoscillatory) method
[11] is used for the gradient $\phi_{x}^{\pm},\phi_{z}^{\pm}$. In (89), the
first-order Euler method is used for the temporal partial derivative, but
higher-order methods, such as third-order accurate TVD (total variation
diminishing) Runge-Kutta (RK) [12] can be used. [11] provided the empirical
observation that level set methods are sensitive to spatial accuracy, thus
high-order scheme for spatial derivatives is desired, but high-order
approximation for temporal derivatives does not significantly increase the
accuracy.

For the time-invariant Problem 1, line 9 in Algorithm 1 solves the HJ equation
(43) whose Hamiltonian has the minimum with 0 operation. Then, line 10 in
Algorithm 1 updates $V_{1}^{\pm}$ with the maximum between $c$ and itself to
satisfy the HJ equation (43) without considering $g-z$ term.

For Problem 1 in optimal control setting, Algorithm 1 also works with
utilizing the correct Hamiltonian $\bar{H}$ (49) instead of $\bar{H}^{\pm}$
((27) and (28)).

Algorithm 1 Computing the solution $V_{1}^{\pm}$ or $V_{1}$ to the HJ
equations for Problem 1 in the zero-sum game and optimal control settings.
This algorithm deals with the four HJ equations: (26), (43), (48), and (52).

1:Input: the temporal discretization: $\\{t_{0}=0,...,t_{K}=T\\}$, the spatial
discretization: $\\{(x_{0},z_{0}),...,(x_{N},z_{N})\\}$

2:Output: $V_{1}^{\pm}$ (or $V_{1}$)

3:$V_{1}^{\pm}(\text{or
}V_{1})(T,x_{i},z_{i})\leftarrow\max\\{c(T,x_{i}),g(T,x_{i})-z_{i}\\},\forall
i$

4:for $k\in\\{K-1,...,0\\}$ do

5: case solving the HJ equations (26) or (48)

6: [l]$V_{1}^{\pm}(\text{or }V_{1})(t_{k},x_{i},z_{i})\leftarrow
V_{1}^{\pm}(\text{or }V_{1})(t_{k+1},x_{i},z_{i})-$

7: $\Delta_{k}\hat{\bar{H}}^{\pm}(\text{or
}\hat{\bar{H}})(\phi_{x}^{+},\phi_{x}^{-},\phi_{z}^{+},\phi_{z}^{-}),\forall
i$

8: [l]$V_{1}^{\pm}(\text{or
}V_{1})(t_{k},x_{i},z_{i})\leftarrow\max\\{c(t_{k},x_{i}),$

9: $g(t_{k},x_{i})-z_{i},V_{1}^{\pm}(\text{or
}V_{1})(t_{k},x_{i},z_{i})\\},\forall i$

10: case solving the HJ equations (43) or (52)

11: [l]$V_{1}^{\pm}(\text{or }V_{1})(t_{k},x_{i},z_{i})\leftarrow
V_{1}^{\pm}(\text{or }V_{1})(t_{k+1},x_{i},z_{i})-$

12: $\Delta_{k}\min\\{0,\hat{\bar{H}}^{\pm}(\text{or
}\hat{\bar{H}})(\phi_{x}^{+},\phi_{x}^{-},\phi_{z}^{+},\phi_{z}^{-})\\},\forall
i$

13: [l]$V_{1}^{\pm}(\text{or
}V_{1})(t_{k},x_{i},z_{i})\leftarrow\max\\{c(t_{k},x_{i}),$

14: $V_{1}^{\pm}(\text{or }V_{1})(t_{k},x_{i},z_{i})\\},\forall i$

Algorithm 2 numerically solves Problem 2 in zero-sum game and optimal control
setting. At line 6 in Algorithm 2, we compute the HJ PDE
($V_{2,t}^{\pm}-\bar{H}^{\pm}(t,x,z,D_{x}V_{2}^{\pm},D_{z}V_{2}^{\pm})=0$) in
the HJ equation (58). Line 7 and 8 in Algorithm 2 update $V_{2}^{\pm}$ by
choosing among $c,g-z$ and itself so that the HJ equation (58) holds.

For the time-invariant Problem 2, line 10 in Algorithm 2 first solve the HJ
PDEs ((68) or (75)) whose Hamiltonian has the maximum operation with 0. Line
11 updates $V_{2}^{\pm}$ (or $V_{2}$) by choosing between $c$ and itself so
that the HJ equation (68) (or (75)) holds.

Algorithm 2 Computing the solution $V_{2}^{\pm}$ or $V_{2}$ to the HJ
equations for Problem 2 in the zero-sum game and optimal control settings.
This algorithm deals with the four HJ equations: (58), (68), (72), and (75).

1:Input: the temporal discretization: $\\{t_{0}=0,...,t_{K}=T\\}$, the spatial
discretization: $\\{(x_{0},z_{0}),...,(x_{N},z_{N})\\}$

2:Output: $V_{2}^{\pm}$ (or $V_{2}$)

3:$V_{2}^{\pm}(\text{or
}V_{2})(T,x_{i},z_{i})\leftarrow\max\\{c(T,x_{i}),g(T,x_{i})-z_{i}\\},\forall
i$

4:for $k\in\\{K-1,...,0\\}$ do

5: case solving the HJ equations (58) or (72)

6: [l]$V_{2}^{\pm}(\text{or }V_{2})(t_{k},x_{i},z_{i})\leftarrow
V_{2}^{\pm}(\text{or }V_{2})(t_{k+1},x_{i},z_{i})-$

7: $\Delta_{k}\hat{\bar{H}}^{\pm}(\text{or
}\hat{\bar{H}})(\phi_{x}^{+},\phi_{x}^{-},\phi_{z}^{+},\phi_{z}^{-}),\forall
i$

8: [l]$V_{2}^{\pm}(\text{or
}V_{2})(t_{k},x_{i},z_{i})\leftarrow\min\\{g(t_{k},x_{i})-z_{i},$

9: $V_{2}^{\pm}(\text{or }V_{2})(t_{k},x_{i},z_{i})\\},\forall i$

10: [l]$V_{2}^{\pm}(\text{or
}V_{2})(t_{k},x_{i},z_{i})\leftarrow\max\\{c(t_{k},x_{i}),$

11: $V_{2}^{\pm}(\text{or }V_{2})(t_{k},x_{i},z_{i})\\},\forall i$

12: case solving the HJ equations (68) or (75)

13: [l]$V_{2}^{\pm}(\text{or }V_{2})(t_{k},x_{i},z_{i})\leftarrow
V_{2}^{\pm}(\text{or }V_{2})(t_{k+1},x_{i},z_{i})-$

14: $\Delta_{k}\max\\{0,\hat{\bar{H}}^{\pm}(\text{or
}\hat{\bar{H}})(\phi_{x}^{+},\phi_{x}^{-},\phi_{z}^{+},\phi_{z}^{-})\\},\forall
i$

15: [l]$V_{2}^{\pm}(\text{or
}V_{2})(t_{k},x_{i},z_{i})\leftarrow\max\\{c(t_{k},x_{i}),$

16: $V_{2}^{\pm}(\text{or }V_{2})(t_{k},x_{i},z_{i})\\},\forall i$

##  7 Example

This section provides an example for Problem 1; examples for Problem 2 can be
found in [6]. In this example, we solve a zero-sum game for two ponds, as
shown in Figure 1. This example is motivated by the water system in [13].

Figure 1:  Water system with two ponds.

Precipitation on pond 1 increases the water level of pond 1, and pond 1
(player A) wants to minimize the highest water level in the time horizon (1 s)
by controlling amount of outflow to pond 2. We assume that the water level
increasing rate on pond 1 due to the precipitation is unknown but bounded by 0
and 10 $m/s$. The precipitation is considered as player B. These numbers and
units can be easily changed to realistic problems. We determine an optimal
control signal and strategy even in the worst behavior of player B.

In the water system, we have two states: $x_{1}$ and $x_{2}$ represent the
water level of pond 1 and 2. The state trajectories are solving the following
dynamics:

$\displaystyle\begin{split}&\dot{\mathrm{x}}_{1}(s)=\beta(s)-\sqrt{2g\mathrm{x}_{1}(s)}\alpha(s),\\\
&\dot{\mathrm{x}}_{2}(s)=0.5\sqrt{2g\mathrm{x}_{1}(s)}\alpha(s)-0.5\mathrm{x}_{2}(s),\end{split}$
(91)

where $\alpha(s)\in A=[0,1]$, $\beta(s)\in B=[0,10]$, and $g$ is the
gravitational constant: 9.81 $m/s^{2}$. In the dynamics for $\mathrm{x}_{1}$,
the first term $\beta$ is by the precipitation (player B), and the second term
$\sqrt{2g\mathrm{x}_{1}}\alpha$ is the water level decreasing rate by pond 1
(player A). The term $\sqrt{2g\mathrm{x}_{1}}$ is by Bernoulli’s equation, and
pond 1 controls the area of outflows ($\alpha$) between 0 and 1. We set the
bottom area of pond 2 is twice bigger than pond 1, thus the dynamics for
$\mathrm{x}_{2}$ contains $0.5\sqrt{2g\mathrm{x}_{1}}\alpha$. Also, we assume
that pond 2’s water is used for drinking water, which causes a decreasing rate
$0.5\mathrm{x}_{2}$.

The dynamics (91) is not Lipschitz at $x_{1}=0$. To avoid this, we approximate
$\sqrt{2gx_{1}}$ with a sinusoidal function $4.82\sin(1.17x_{1})$ if $x_{1}$
is less than 1. This sinusoidal-approximate function has the same value and
first derivative at $x_{1}=1$: $\sqrt{2g}\simeq 4.82\sin(1.17)$ and
$\sqrt{g/2}\simeq 4.82*1.17*\cos(1.17)$. The approximated (Lipschitz) dynamics
are

$\displaystyle\begin{split}&\dot{\mathrm{x}}_{1}(s)=\beta(s)-\begin{cases}\sqrt{2g\mathrm{x}_{1}(s)}\alpha(s),&\mathrm{x}_{1}(s)\geq
1,\\\
4.82\sin(1.17\mathrm{x}_{1}(s))\alpha(s),&\mathrm{x}_{1}(s)<1,\end{cases}\\\
&\dot{\mathrm{x}}_{2}(s)=\begin{cases}0.5\sqrt{2g\mathrm{x}_{1}(s)}\alpha(s),&\mathrm{x}_{1}(s)\geq
1,\\\
2.41\sin(1.17\mathrm{x}_{1}(s))\alpha(s),&\mathrm{x}_{1}(s)<1,\end{cases}-0.5\mathrm{x}_{2}(s),\end{split}$
(92)

We solve the two zero-sum games: the upper value function is

$\displaystyle\quad\quad\vartheta_{1}^{+}(0,x_{1},x_{2}),=\max_{\delta\in\Delta(0)}\min_{\alpha\in\mathcal{A}(0)}\max_{\tau\in[0,1]}\mathrm{x}_{1}(\tau),$
(93) $\displaystyle\text{subject to
}\max\\{|\mathrm{x}_{1}(s)-7.5|-7.5,|\mathrm{x}_{2}(s)-3|-2\\}\leq 0,$ (94)

where $A=[0,1]$, $B=[0,10]$, $\mathcal{A}(0)=\\{[0,1]\rightarrow
A~{}|~{}\|\alpha\|_{L^{\infty}(0,1)}<\infty\\}$,
$\mathcal{B}(0)=\\{[0,1]\rightarrow
B~{}|~{}\|\beta\|_{L^{\infty}(0,1)}<\infty\\}$, $\Delta(0)$ is a set of non-
anticipative strategies for player B (pond 2) as in (7), and
$(\mathrm{x}_{1},\mathrm{x}_{2})$ solves (92) for $(\alpha,\delta[\alpha])$;
and the lower value function is

$\displaystyle\quad\quad\vartheta_{1}^{-}(0,x_{1},x_{2}),=\min_{\gamma\in\Gamma(0)}\max_{\beta\in\mathcal{B}(0)}\max_{\tau\in[0,1]}\mathrm{x}_{1}(\tau),$
(95) $\displaystyle\text{subject to
}\max\\{|\mathrm{x}_{1}(s)-7.5|-7.5,|\mathrm{x}_{2}(s)-3|-2\\}\leq 0,$ (96)

where $\Gamma(0)$ is a set of non-anticipative strategies for player A (pond
1) as in (8), and $(\mathrm{x}_{1},\mathrm{x}_{2})$ solves (92) for
$(\gamma[\beta],\beta)$. The state constraint implies that the water level of
pond 1 has to be between 0 and 15 $m$ and the one of pond 2 is between 1 and 5
$m$. In these games, pond 1 (player A) wants to minimize the worst water level
of pond 1 in the time horizon while satisfying the state constraint for
preventing flood in pond 1 and 2.

We will solve the HJ equation (26) for $V_{1}^{\pm}$ corresponding to
$\vartheta_{1}^{\pm}$ ((94) or (96)). We have the Hamiltonian

$\displaystyle\bar{H}^{+}(t,x,z,p,q)=\max_{a\in A}\min_{b\in
B}-p_{1}b+0.5p_{2}x_{2}$
$\displaystyle\quad\quad+\begin{cases}(p_{1}-0.5p_{2})\sqrt{2gx_{1}}a&\text{if
}x_{1}\geq 1\\\ (p_{1}-0.5p_{2})4.82\sin(1.17x_{1})a&\text{if
}x_{1}<1\end{cases}$ $\displaystyle\quad\quad=\begin{cases}-10p_{1}&\text{if
}p_{1}\geq 0\\\ 0&\text{if }p_{1}<0\end{cases}+0.5p_{2}x_{2}$
$\displaystyle\quad\quad+\begin{cases}(p_{1}-0.5p_{2})\sqrt{2gx_{1}}&\text{if
}\begin{tabular}[]{l}$p_{1}-0.5p_{2}\geq 0$\\\ $x_{1}\geq 1$\end{tabular}\\\
(p_{1}-0.5p_{2})4.82\sin(1.17x_{1})&\text{if
}\begin{tabular}[]{l}$p_{1}-0.5p_{2}\geq 0$\\\ $x_{1}<1$\end{tabular}\\\
0&\text{if }p_{1}-0.5p_{2}<0\end{cases}$
$\displaystyle=\bar{H}^{-}(t,x,z,p,q)$ (97)

where $x=(x_{1},x_{2})\in\mathbb{R}^{2}$ and
$p=(p_{1},p_{2})\in\mathbb{R}^{2}$. (97) implies

$\displaystyle V_{1}^{+}\equiv V_{1}^{-}\equiv V_{1}^{\pm}\text{ and
}\vartheta_{1}^{+}\equiv\vartheta_{1}^{-}\equiv\vartheta_{1}^{\pm}.$ (98)

We use $V_{1}^{\pm}$ to denote the same value functions $V_{1}^{+}$ and
$V_{1}^{-}$.

The red curvature in Figure 2 (a) shows the zero-level set of
$V_{1}^{\pm}(0,x_{1},x_{2})$, numerically computed by Algorithm 1. This
algorithm is programmed by utilizing the level set toolbox [8] and the
helperOC toolbox [14] in Matlab, and this simulation is carried out on a
laptop with a 2.8 GHz Quad-Core i7 CPU and 16 GB RAM. Each of $x_{1}$,
$x_{2}$, and $z$ axis has 81 discretization points, and the time interval
$[0,1]$ is discretized with 201 points. The computation time for $V_{1}^{\pm}$
is 237 $s$. In Figure 2 (a), the value of $V_{1}^{\pm}$ inside of the red
curvature is negative, on the other hand, the value outside of the curvature
is positive.

This example is time-invariant, so both HJ equations in (26) and (43) can be
utilized. In this example, we solve the HJ equation (26).

---
(a)
(b)
Figure 2:  (a) The zero-level set of $V_{1}^{\pm}$ is shown in this figure.
The value of $V_{1}^{\pm}$ inside of the curvature is negative, but the value
is positive outside. The blue planes are $z$-level planes of 4, 6, 8, 10, 12,
14, and 16. (b) The $z$-level sets are shown in $(x_{1},x_{2})$-space. The
$z$-level sets for $z\geq 15$ are the same (the outer curvature). The
$z$-level sets also show $\vartheta_{1}^{\pm}$ by Lemma 1. For example, for
$(1.60,2.85)$ on the $z$-level set of 4, $\vartheta_{1}^{\pm}$ is 4. On the
other hand, consider $(0.11,2)$ on multiple $z$-level sets from 4.22 to any
greather levels, for which $\vartheta_{1}^{\pm}$ is the minimum $z$-level that
contains the point: $\vartheta_{1}^{\pm}(0.05,2)=4.22$.

Lemma 1 describes how to compute $\vartheta_{1}^{\pm}$ from the zero-level set
of $V_{1}^{\pm}$, which is illustrated in Figure 2. Figure 2 (a) illustrates
the intersection of the zero-level set of $V_{1}^{\pm}$ and each $z$-level
plane, and Figure 2 (b) shows these intersections in the state space,
$(x_{1},x_{2})$: the $z$-level sets on the zero-level set of $V_{1}^{\pm}$. As
illustrated in Figure 2 (b), the lower $z$-level is achieved in the smaller
region in $(x_{1},x_{2})$. In this example, as $z$-level is increasing, the
inner area of the $z$-level set on the subzero-level set of $V_{1}^{\pm}$ is
increasing and also converging at the $z$-level of 15, which is the outer
curvature in Figure 2 (b). For $(x_{1},x_{2})$ outside of the outer curvature
indicated with $z\geq 15$, there is no control signal or strategy for pond 1
(player A) to satisfy the state constraint, which implies that
$\vartheta_{1}^{\pm}(0,x_{1},x_{2})$ is infinity. On the other hand, for
$(x_{1},x_{2})$ on a unique $z$-level set, the $z$-level is equal to
$\vartheta_{1}^{\pm}$. For example, the $z$-level set of 6 is the only
$z$-level set passing through $(2.6,2)$. In this case,
$\vartheta_{1}^{\pm}(0,2.6,2)=6$. On the other hand, for $(x_{1},x_{2})$ on
multiple $z$-level sets, the minimum value of $z$-level is
$\vartheta_{1}^{\pm}$. For example, $(0.05,2)$ is on the $z$-level sets of any
number greater than or equal to 4.5. In this case,
$\vartheta_{1}^{\pm}(0,0.05,2)$ is 4.5 since 4.5 is the minimum $z$-level that
contains the point $(0.05,2)$.

---
(a)
(b)
Figure 3:  State trajectories by applying an optimal control signal and
strategy for two players (pond 1 and the precipitation) where the initial
states are (a) $(x_{1},x_{2})=(10,4)$ and (b) $(x_{1},x_{2})=(2,1.1)$.

Using the value function $V_{1}^{\pm}$ and $\vartheta_{1}^{\pm}$, the method
presented in Section 5 provides a state trajectory and an optimal control and
strategy for the two players (pond 1 and the precipitation). Among multiple
solutions for optimal control and strategy presented in Remark 4, we choose

$\displaystyle\begin{split}&a_{*}\in\arg\max_{a\in A}\min_{b\in
B}\tilde{H}_{1}^{+}(a,b),\\\ &b_{*}\in\arg\min_{b\in
B}\tilde{H}_{1}^{+}(a_{*},b),\end{split}$ (99)

which satisfies the eight equations (83) to (86) since
$\bar{H}^{+}=\bar{H}^{-}$ and $\tilde{H}_{1}^{+}=\tilde{H}_{1}^{-}$, where
$\tilde{H}_{1}^{\pm}$ is equal to $D_{x}V_{1}^{\pm}\cdot f+D_{z}V_{1}^{\pm}L$
as defined in (78).

Figure 3 shows state trajectories for two different initial states:
$(x_{1},x_{2})=(10,4)$ and $(2,1.1)$. As shown in Figure 3 (a), for the
initial state $(10,4)$, $\mathrm{x}_{2}$ hits the boundary of the state
constraint: $\mathrm{x}_{2}(1)=5$, and $\mathrm{x}_{1}$ is maximized at $t=1$.
Since the initial water levels of the two ponds are high, the precipitation
(player B) tries to increase the water level of pond 1 for all time, but
player A tries to balance the water levels of the two ponds. On the other
hand, for the initial state $(2,1.1)$, Figure 3 (b) shows that
$\mathrm{x}_{2}$ strictly satisfies the state constraint $[1,5]$.
$\mathrm{x}_{1}$ is maximized at $t=0.015$ and increasing for the later time.
Since the initial water levels of the two ponds are low, the precipitation
(player B) tries to violate the state constraint by not increasing the water
level of pond 1. However, player A tries to balance the two ponds’ water level
so that all ponds have more water than the minimum levels.

As discussed in Section 6, there are some numerical issues in Algorithm 1.
First, we observe that (99) provides a bang-bang control, thus the state
trajectories are not smooth as shown in Figure 3. This happens due to frequent
sign change of the gradient along the time horizon. Second, the numerical
error on $V_{1}^{\pm}$ causes inaccurate $\vartheta_{1}^{\pm}$ by Lemma 1,
which could potentially cause unsafety even though the violation of the state
constraint might be smaller for the smaller grid size. In practice, we suggest
having a safety margin to the state constraint: for example, use
$c(s,\mathrm{x}(s))+\epsilon\leq 0$ for small $\epsilon>0$ instead of
$c(s,\mathrm{x}(s))\leq 0$.

##  8 Conclusion and Future Work

This paper presented four HJ equations for the two classes of state-
constrained zero-sum games where the terminal time is a variable to be
determined and the stage cost is non-zero. For each class of problems, two HJ
equations have presented: one for time-varying version, and the other for the
time-invariant version. This paper also analyzed the optimal control and
strategy for each player using the gradient of the viscosity solution to the
HJ equations, and also presented a numerical algorithm to compute the
viscosity solution. As a practical example, a 2D water system demonstrates one
of the presented HJ formulations.

Although our HJ formulation can be generally utilized for the two classes of
problems, the numerical computation of Algorithms 1 and 2 is intractable for
high-dimensional system (higher than four or five). This is because the
computational complexity is exponential in the dimension of the state. In
future, We aim to alleviate this complexity by deriving corresponding Lax and
Hopf theory or by applying approximation techniques in reinforcement learning.

###  .1 Proof of Lemma 1

Proof.
(i) $\vartheta_{1}^{+}(t,x)-z\leq 0\Rightarrow V_{1}^{+}(t,x,z)\leq 0$

$\vartheta_{1}^{+}(t,x)-z\leq 0$ implies that, for all $\delta\in\Delta(t)$,
there exists $\alpha\in\mathcal{A}(t)$ such that

$\displaystyle\max_{\tau\in[t,T]}\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\delta[\alpha](s))ds+g(\tau,\mathrm{x}(\tau))-z\leq\epsilon$
(100)

and $c(s,\mathrm{x}(s))\leq 0$ for $s\in[t,\tau]$ for any small $\epsilon>0$,
where $\mathrm{x}$ solves (1) for $(\alpha,\delta[\alpha])$. Thus, for all
$\delta$, there exists $\alpha$ such that
$J_{1}(t,x,z,\alpha,\delta)\leq\epsilon$, which concludes
$V_{1}^{+}(t,x,z)\leq 0$. Note that $J_{1}$ is defined in (15).

(ii) $V_{1}^{+}(t,x,z)\leq 0\Rightarrow\vartheta_{1}^{+}(t,x)-z\leq 0$

Assumption 1 implies that, for any $\delta\in\Delta(t)$, there exists
$\alpha\in\mathcal{A}$ such that $J_{1}(t,x,z,\alpha,\delta[\alpha])\leq
V_{1}^{+}(t,x,z)$. If $V_{1}^{+}(t,x,z)\leq 0$, for any $\delta\in\Delta(t)$,
there exists $\alpha$ such that $\max_{s\in[t,\tau]}c(s,\mathrm{x}(s))\leq 0$
and
$\int_{t}^{\tau}L(s,\mathrm{x}(s),\alpha(s),\delta[\alpha](s))ds+g(\tau,\mathrm{x}(s))-z\leq
0$ for all $\tau\in[t,T]$. Thus, $\vartheta_{1}^{+}(t,x)-z\leq 0$.

(i) and (ii) concludes (19).

(iii) Let $\tilde{\vartheta}_{1}^{+}$ be the right hand term in (20) subject
to (21). Then, the following statement can be proved by analogous proofs in
(i) and (ii).

$\displaystyle\tilde{\vartheta}_{1}^{+}(t,x)=\min z$ $\displaystyle\text{
subject to
}\sup_{\delta}\inf_{\alpha}\max\\{\max_{s\in[t,T]}c(s,\mathrm{x}(s)),$
$\displaystyle\max_{\tau\in[t,T]}g(\tau,\mathrm{x}(\tau))-\mathrm{z}(\tau)\\}\leq
0.$ (101)

By (18) and (19), we conclude
$\vartheta_{1}^{+}(t,x)=\tilde{\vartheta}_{1}^{+}(t,x)$.

(iv) The proof for $V_{1}^{-}$ and $\vartheta^{-}_{1}$ is similar to that for
$V_{1}+$ and $\vartheta^{+}_{1}$. ∎

###  .2 Proof of Lemma 2

Proof. Consider $(\mathrm{x},\mathrm{z})$ solving (17) for any
$(\alpha,\beta)$, and a small $h>0$. (18) implies

$\displaystyle J_{1}(t$
$\displaystyle,x,z,\alpha,\beta)=\max\Big{\\{}\max_{s\in[t,t+h]}c(s,\mathrm{x}(s)),$
$\displaystyle\max_{s\in[t,t+h]}g(s,\mathrm{x}(s))-\mathrm{z}(s),\max\big{\\{}\max_{s\in[t+h,T]}c(s,\mathrm{x}(s)),$
$\displaystyle\max_{s\in[t+h,T]}g(s,\mathrm{x}(s))-\mathrm{z}(s)\big{\\}}\Big{\\}}.$
(102)

(i) For all $\alpha\in\mathcal{A}(t)$ and $\delta\in\Delta(t)$, there exists
$\alpha_{1}\in\mathcal{A}(t)$, $\delta_{1}\in\Delta(t)$,
$\alpha_{2}\in\mathcal{A}(t+h)$, $\delta_{2}\in\Delta(t+h)$ such that

$\displaystyle\alpha(s)=\begin{cases}\alpha_{1}(s),&s\in[t,t+h],\\\
\alpha_{2}(s),&s\in(t+h,T],\end{cases}$ (103)
$\displaystyle\delta[\alpha](s)=\begin{cases}\delta_{1}[\alpha](s),&s\in[t,t+h],\\\
\delta_{2}[\alpha](s),&s\in(t+h,T].\end{cases}$ (104)

Then, we have

$\displaystyle
V_{1}^{+}(t,x,z)=\sup_{\begin{subarray}{c}\delta_{1}\in\Delta(t)\\\
\delta_{2}\in\Delta(t+h)\end{subarray}}\inf_{\begin{subarray}{c}\alpha_{1}\in\mathcal{A}(t)\\\
\alpha_{2}\in\mathcal{A}(t+h)\end{subarray}}J_{1}(t,x,z,\alpha,\delta[\alpha])$
$\displaystyle=\sup_{\delta_{1}\in\Delta(t)}\inf_{\alpha_{1}\in\mathcal{A}(t)}\max\Big{\\{}\max_{s\in[t,t+h]}c(s,\mathrm{x}(s)),$
$\displaystyle\max_{s\in[t,t+h]}g(s,\mathrm{x}(s))-\mathrm{z}(s),\sup_{\delta_{2}\in\Delta(t+h)}\inf_{\alpha_{2}\in\mathcal{A}(t+h)}\max$
$\displaystyle\big{\\{}\max_{s\in[t+h,T]}c(s,\mathrm{x}(s)),\max_{s\in[t+h,T]}g(s,\mathrm{x}(s))-\mathrm{z}(s)\big{\\}}\Big{\\}}.$
(105)

The last equality is deduced by combining (102) and that the first two terms
of $V_{1}^{+}$ ($\max_{s\in[t,t+h]}c(s,\mathrm{x}(s))$,
$\max_{s\in[t,t+h]}g(s,\mathrm{x}(s))-\mathrm{z}(s)$) are independent of
$(\alpha_{2},\delta_{2})$. (105) concludes (24).

(ii) The proof for (25) is similar to (i). ∎

###  .3 Proof of Theorem 1

Proof. (i) At $t=T$, the definition of $V_{1}^{\pm}$ ((13) and (14)) implies
(29).

(ii) For $U\in C^{\infty}([0,T]\times\mathbb{R}^{n}\times\mathbb{R})$ such
that $V_{1}^{+}-U$ has a local maximum at
$(t_{0},x_{0},z_{0})\in(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$ and
$(V_{1}^{+}-U)(t_{0},x_{0},z_{0})=0$, we will prove

$\displaystyle\begin{split}\max\big{\\{}&c(t_{0},x_{0})-U_{0},g(t_{0},x_{0})-z_{0}-U_{0},\\\
&U_{t0}-\bar{H}^{+}(t_{0},x_{0},z_{0},D_{x}U_{0},D_{z}U_{0})\big{\\}}\geq
0,\end{split}$ (106)

where $U_{0}=U(t_{0},x_{0},z_{0})$, $U_{t0}=U_{t}(t_{0},x_{0},z_{0})$,
$D_{x}U_{0}=D_{x}U(t_{0},x_{0},z_{0})$, and
$D_{z}U_{0}=D_{z}U(t_{0},x_{0},z_{0})$.

Suppose not. There exists $\theta>0$, $a_{1}\in A$ such that

$\displaystyle c(t,x)-U_{0}<-\theta,\quad g(t,x)-z-U_{0}<-\theta,$ (107)
$\displaystyle\begin{split}&U_{t}(t,x,z)+D_{x}U(t,x,z)\cdot f(t,x,a_{1},b)\\\
&\quad\quad\quad\quad\quad\quad-
D_{z}U(t,x,z)L(t,x,a_{1},b)\leq-\theta\end{split}$ (108)

for all $b\in B$ and all points $(t,x,z)$ sufficiently close to
$(t_{0},x_{0},z_{0})$: $|t-t_{0}|+\|x-x_{0}\|+|z-z_{0}|<h_{1}$ for small
enough $h_{1}>0$. Consider state trajectories $\mathrm{x}$ and $\mathrm{z}$
solving (17) for $\alpha_{1}\equiv a_{1}$, $t=t_{0}$, $x=x_{0}$, $z=z_{0}$,
and any $\beta\in\mathcal{B}(t_{0})$. By Assumption 1, there exists a small
$h$ such that $\|\mathrm{x}(s)-x_{0}\|+|\mathrm{z}(s)-z_{0}|<h_{1}-h$
($s\in[t_{0},t_{0}+h]$), then,

$\displaystyle
c(s,\mathrm{x}(s))-U_{0}<-\theta,~{}g(s,\mathrm{x}(s))-\mathrm{z}(s)-U_{0}<-\theta,$
(109) $\displaystyle U_{t}(s,\mathrm{x}(s),\mathrm{z}(s))$
$\displaystyle+D_{x}U(s,\mathrm{x}(s),\mathrm{z}(s))\cdot
f(s,\mathrm{x}(s),a_{1},\beta(s))$ $\displaystyle-
D_{z}U(s,\mathrm{x}(s),\mathrm{z}(s))L(s,\mathrm{x}(s),a_{1},\beta(s))\leq-\theta$
(110)

for all $s\in[t_{0},t_{0}+h]$ and $\beta\in\mathcal{B}(t_{0})$.

Since $V_{1}^{+}-U$ has a local maximum at $(t_{0},x_{0},z_{0})$,

$\displaystyle
V_{1}^{+}(t_{0}+h,\mathrm{x}(t_{0}+h),\mathrm{z}(t_{0}+h))-V_{1}^{+}(t_{0},x_{0},z_{0})$
$\displaystyle\leq$ $\displaystyle
U(t_{0}+h,\mathrm{x}(t_{0}+h),\mathrm{z}(t_{0}+h))-U(t_{0},x_{0},z_{0})$
$\displaystyle=$
$\displaystyle\int_{t_{0}}^{t_{0}+h}U_{t}(s,\mathrm{x}(s),\mathrm{z}(s))$
$\displaystyle+$ $\displaystyle D_{x}U(s,\mathrm{x}(s),\mathrm{z}(s))\cdot
f(s,\mathrm{x}(s),a_{1},\delta[\alpha_{1}](s))$ $\displaystyle-$
$\displaystyle
D_{z}U(s,\mathrm{x}(s),\mathrm{z}(s))L(s,\mathrm{x}(s),a_{1},\delta[\alpha_{1}](s))ds\leq-\theta
h$ (111)

for all $\delta\in\Delta(t_{0})$, according to (110). Lemma 2 implies

$\displaystyle
V_{1}^{+}(t_{0},x_{0},z_{0})\leq\sup_{\delta\in\Delta(t_{0})}\max\big{\\{}\max_{s\in[t_{0},t_{0}+h]}c(s,\mathrm{x}(s)),$
$\displaystyle\max_{s\in[t,t+h]}g(\mathrm{x}(s))-\mathrm{z}(s),V_{1}^{+}(t_{0}+h,\mathrm{x}(t_{0}+h),\mathrm{z}(t_{0}+h))\big{\\}}.$
(112)

By subtracting $U_{0}$ on the both sides in (112) and then applying (109) and
(111), we have

$\displaystyle 0\leq\max\\{-\theta,-\theta,-\theta h\\}<0,$ (113)

which is contradiction. Thus, (106) is proved.
(iii) For $U\in C^{\infty}([0,T]\times\mathbb{R}^{n}\times\mathbb{R})$ such
that $V_{1}^{+}-U$ has a local minimum at
$(t_{0},x_{0},z_{0})\in(0,T)\times\mathbb{R}^{n}\times\mathbb{R}$ and
$(V_{1}^{+}-U)(t_{0},x_{0},z_{0})=0$, we will prove

$\displaystyle\begin{split}\max\big{\\{}&c(t_{0},x_{0})-U_{0},g(t_{0},x_{0})-z_{0}-U_{0},\\\
&U_{t0}-\bar{H}^{+}(t_{0},x_{0},z_{0},D_{x}U_{0},D_{z}U_{0})\big{\\}}\leq
0,\end{split}$ (114)

Since $J_{1}(t_{0},x_{0},z_{0},\alpha)$ (15) is greater than the value at
$\tau=t_{0}$,

$\displaystyle
J_{1}(t_{0},x_{0},z_{0},\alpha,\delta[\alpha])\geq\max\big{\\{}c(x_{0},x_{0}),g(t_{0},x_{0})-z_{0}\big{\\}},$
(115)

for all $\alpha\in\mathcal{A}(t_{0}),\delta\in\Delta(t_{0})$. By subtracting
$U_{0}$ on the both sides, and taking the supremum over $\delta$ and the
infimum over $\alpha$, sequentially, on the both side, we have

$\displaystyle
0\geq\max\big{\\{}c(x_{0},x_{0})-U_{0},g(t_{0},x_{0})-z_{0}-U_{0}\big{\\}}.$
(116)

The rest of the proof is to show

$\displaystyle U_{t0}-\bar{H}^{+}(t_{0},x_{0},z_{0},D_{x}U_{0},D_{z}U_{0})\leq
0.$ (117)

Suppose not. For some $\theta>0$,

$\displaystyle\begin{split}U_{t}(t,x,z)+&\max_{b\in B}D_{x}U(t,x,z)\cdot
f(t,x,a,b)\\\ &-D_{z}U(t,x,z)L(t,x,a,b)\geq\theta\end{split}$ (118)

for all $a\in A$ and all points $(t,x,z)$ sufficiently close to
$(t_{0},x_{0},z_{0})$: $|t-t_{0}|+\|x-x_{0}\|+|z-z_{0}|<h_{1}$ for small
enough $h_{1}>0$. Consider state trajectories $\mathrm{x}_{1}$ and
$\mathrm{z}_{1}$ solving (17) for any $\alpha\in\mathcal{A}(t_{0})$,
$\beta=\delta_{1}[\alpha]$, where

$\displaystyle\delta_{1}[\alpha](s)\in\arg\max_{b\in
B}D_{x}U(s,\mathrm{x}_{1}(s),\mathrm{z}_{1}(s))\cdot
f(s,\mathrm{x}_{1}(s),\alpha(s),b)$ $\displaystyle\quad\quad\quad-
D_{z}U(s,\mathrm{x}_{1}(s),\mathrm{z}_{1}(s))L(s,\mathrm{x}_{1}(s),\alpha(s),b),$
(119)

$t=t_{0}$, $x=x_{0}$, and $z=z_{0}$. Since there exists a small $h>0$ such
that $\|\mathrm{x}_{1}(s)-x_{0}\|+|\mathrm{z}_{1}(s)-z_{0}|<h_{1}-h$
($s\in[t_{0},t_{0}+h]$),

$\displaystyle\begin{split}&U_{t}(s,\mathrm{x}_{1}(s),\mathrm{z}_{1}(s))\\\
+&D_{x}U(s,\mathrm{x}_{1}(s),\mathrm{z}_{1}(s))\cdot
f(s,\mathrm{x}_{1}(s),\alpha(s),\delta_{1}[\alpha](s))\\\
-&D_{z}U(s,\mathrm{x}_{1}(s),\mathrm{z}_{1}(s))L(s,\mathrm{x}_{1}(s),\alpha(s),\delta_{1}[\alpha](s))\geq\theta\end{split}$
(120)

for all $s\in[t_{0},t_{0}+h]$. By integrating (120) over
$s\in[t_{0},t_{0}+h]$, we have

$\displaystyle
U(t_{0}+h,\mathrm{x}_{1}(t_{0}+h),\mathrm{z}_{1}(t_{0}+h))-U(t_{0},x,z)\geq\theta
h.$ (121)

Since (121) holds for all $\alpha\in\mathcal{A}(t_{0})$ and
$\delta\in\Delta(t_{0})$,

$\displaystyle\begin{split}\sup_{\delta\in\Delta(t_{0})}\inf_{\alpha\in\mathcal{A}(t_{0})}U(t_{0}+h,\mathrm{x}(t_{0}+h),\mathrm{z}(t_{0}+h))\\\
\quad\quad-U(t_{0},x,z)\geq\theta h,\end{split}$ (122)

where $\mathrm{x},\mathrm{z}$ solve (17) for
$(\alpha,\delta,t_{0},x_{0},z_{0})$.

Since $V_{1}^{+}-U$ has a local minimum at $(t_{0},x_{0},z_{0})$,

$\displaystyle\sup_{\delta\in\Delta(t_{0})}\inf_{\alpha\in\mathcal{A}(t_{0})}\begin{tabular}[]{l}$V_{1}^{+}(t_{0}+h,\mathrm{x}(t_{0}+h),\mathrm{z}(t_{0}+h))$\\\
$\quad\quad\quad\quad\quad\quad\quad\quad\quad-
V_{1}^{+}(t_{0},x_{0},z_{0})$\end{tabular}$ (125) $\displaystyle\geq$
$\displaystyle\sup_{\delta\in\Delta(t_{0})}\inf_{\alpha\in\mathcal{A}(t_{0})}\begin{tabular}[]{l}$U(t_{0}+h,\mathrm{x}(t_{0}+h),\mathrm{z}(t_{0}+h))$\\\
$\quad\quad\quad\quad\quad\quad\quad\quad\quad-U(t_{0},x_{0},z_{0})$\end{tabular}$
(128) $\displaystyle\geq$ $\displaystyle~{}\theta h$ (129)

according to (122). However, Lemma 2 implies

$\displaystyle\sup_{\delta\in\Delta(t_{0})}\inf_{\alpha\in\mathcal{A}(t_{0})}V_{1}^{+}(t_{0}+h,\mathrm{x}$
$\displaystyle(t_{0}+h),\mathrm{z}(t_{0}+h))$ $\displaystyle\leq
V_{1}^{+}(t_{0},x_{0},z_{0}),$ (130)

which contradicts (129).

(iv) The proof for the viscosity solution $V_{1}^{-}$ is similar to (ii) and
(iii) for $V_{1}^{+}$. Also, the uniqueness follows from the uniqueness
theorems for viscosity solutions, Theorem 4.2 in [15], and the extension of
Theorem 1 in [16]. ∎

###  .4 Proof of Lemma 3

Proof. Set $\tilde{V}_{1}^{+}$ and $\tilde{V}_{1}^{-}$ be the right hand terms
in (40) and (41), respectively. $V_{1}^{+}$ are $V_{1}^{-}$ are defined in
(13) and (14), respectively.

(i) In this proof, we utilize the following properties in [3, 17], presented
as below.

Define a pseudo-time operator $\sigma_{\mu}\mathrel{\mathop{\mathchar
58\relax}}[t,T]\rightarrow[t,T]$ for a given $\mu\in\mathcal{M}(t)$ (defined
in (31)) and the corresponding inverse operator:

$\displaystyle\sigma_{\mu}(s)=\int_{t}^{s}\mu(\tau)d\tau+t;$ (131)
$\displaystyle\sigma^{-1}_{\mu}(s)\coloneqq\min\tau\text{ subject to
}\sigma_{\mu}(\tau)=s.$ (132)

Then,

$\displaystyle\sigma_{\mu}\big{(}\sigma^{-1}_{\mu}(s)\big{)}=s,\quad
s\in[t,\sigma_{\mu}(T)],$ (133)
$\displaystyle\sigma^{-1}_{\mu}\big{(}\sigma_{\mu}(s)\big{)}=s,\quad
s\in\textrm{Range}(\sigma_{\mu}^{-1}),$ (134)

where
$\textrm{Range}(\sigma_{\mu}^{-1})\coloneqq\\{\sigma^{-1}_{\mu}(s)~{}|~{}s\in[t,\sigma_{\mu}(T)]\\}$.

Consider two state trajectories: $(\mathrm{x},\mathrm{z})$ solving (17) for
$(\tilde{\alpha}(\sigma_{\mu}^{-1}(\cdot)),\tilde{\beta}(\sigma_{\mu}^{-1}(\cdot)))$
for $s\in[t,\sigma_{\mu}(T)]$; $(\tilde{\mathrm{x}},\tilde{\mathrm{z}})$
solving (39) for $(\tilde{\alpha},\tilde{\beta},\mu)$, and
$\mathrm{x}(t)=\tilde{\mathrm{x}}(t)=x$. Then,

$\displaystyle\mathrm{x}\big{(}\sigma_{\mu}(s)\big{)}=\tilde{\mathrm{x}}(s),\quad
s\in[t,T],$ (135) $\displaystyle
g\big{(}\mathrm{x}(\sigma_{\mu}(T))\big{)}-\mathrm{z}(\sigma_{\mu}(T))=g\big{(}\tilde{\mathrm{x}}(T)\big{)}-\tilde{\mathrm{z}}(T).$
(136)

(135) is according to Lemma 4 in [9], and (136) is derived by combining two
lemmas (Lemma 4 and 6) in [9].

(ii) $\tilde{V}_{1}^{+}(t,x,z)\geq V_{1}^{+}(t,x,z)$

For small $\epsilon>0$, there exists $\delta_{1}\in\Delta(t)$ such that

$\displaystyle\begin{split}V_{1}^{+}&(t,x,z)-\epsilon\leq\inf_{\alpha}\max_{\tau\in[t,T]}\max\big{\\{}\max_{s\in[t,\tau]}c(\mathrm{x}_{1}(s)),\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
g\big{(}\mathrm{x}_{1}(\tau)\big{)}-\mathrm{z}_{1}(\tau)\big{\\}},\end{split}$
(137)

where $(\mathrm{x}_{1},\mathrm{z}_{1})$ solves (17) for
$(\alpha,\delta_{1}[\alpha])$. Denote $\tau_{*}(\alpha)$ is the maximizer of
the right hand term in (137) for each $\alpha\in\mathcal{A}(t)$:

$\displaystyle\begin{split}&\tau_{*}(\alpha)\coloneqq\arg\max_{\tau\in[t,T]}\max\big{\\{}\max_{s\in[t,\tau]}c(\mathrm{x}_{1}(s)),g\big{(}\mathrm{x}_{1}(\tau)\big{)}-\mathrm{z}_{1}(\tau)\big{\\}}.\end{split}$
(138)

Define a particular strategy $\nu_{A,1}\in\textrm{N}_{A}(t)$:

$\displaystyle\nu_{A,1}[\alpha](s)\coloneqq\begin{cases}1,&s\in[t,\tau_{*}(\alpha)],\\\
0,&s\in(\tau_{*}(\alpha),T].\end{cases}$ (139)

Consider a state trajectory $(\tilde{\mathrm{x}}_{1},\tilde{\mathrm{z}}_{1})$
solving (39) for $(\alpha,\delta_{1}[\alpha],\nu_{A,1}[\alpha])$. Then, we
have

$\displaystyle(\tilde{\mathrm{x}}_{1},\tilde{\mathrm{z}}_{1})(s)=\begin{cases}(\mathrm{x}_{1},\mathrm{z}_{1})(s),&s\in[t,\tau_{*}(\alpha)],\\\
(\mathrm{x}_{1},\mathrm{z}_{1})(\tau_{*}(\alpha)),&s\in(\tau_{*}(\alpha),T],\end{cases}$
(140)

Since $\tilde{V}_{1}^{+}$ has the supremum over $(\delta,\nu_{A})$-space
operation,

$\displaystyle\tilde{V}_{1}^{+}(t,x,z)\geq\inf_{\alpha}\max\big{\\{}\max_{s\in[t,T]}c(\tilde{\mathrm{x}}_{1}(s)),g\big{(}\tilde{\mathrm{x}}_{1}(T)\big{)}-\tilde{\mathrm{z}}_{1}(T)\big{\\}}$
$\displaystyle=\inf_{\alpha}\max\big{\\{}\max_{s\in[t,\tau_{*}(\alpha)]}c(\mathrm{x}_{1}(s)),g\big{(}{\mathrm{x}}_{1}(\tau_{*}(\alpha))\big{)}-\mathrm{z}_{1}(\tau_{*}(\alpha))\big{\\}}$
$\displaystyle\geq V_{1}^{+}(t,x,z)-\epsilon.$ (141)

The second equality is according to (140), and the third inequality is by
(137).

(iii) $V_{1}^{+}(t,x,z)\geq\tilde{V}_{1}^{+}(t,x,z)$

Define $\tilde{\mathfrak{A}}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}(t)\rightarrow\mathcal{A}(t)$ and its psuedo inverse
function ${\mathfrak{A}}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}(t)\rightarrow\mathcal{A}(t)$:

$\displaystyle(\tilde{\mathfrak{A}}_{\mu}(\alpha))(s)\coloneqq\begin{cases}\alpha\big{(}\sigma_{\mu}(s)\big{)},&s\in\textrm{Range}(\sigma^{-1}_{\mu}),\\\
\text{any }a\in A,&s\notin\textrm{Range}(\sigma^{-1}_{\mu}),\end{cases}$ (142)
$\displaystyle(\mathfrak{A}_{\mu}(\tilde{\alpha}))(s)\coloneqq\begin{cases}\tilde{\alpha}(\sigma^{-1}_{\mu}(s)),&s\in[t,\sigma_{\mu}(T)],\\\
\text{any }a\in A,&s\in(\sigma_{\mu}(T),T],\end{cases}$ (143)

Also, define $\tilde{\mathfrak{D}}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\Delta(t)\rightarrow\Delta(t)$ and its psuedo inverse function
$\mathfrak{D}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\Delta(t)\rightarrow\Delta(t)$:

$\displaystyle(\tilde{\mathfrak{D}}_{\mu}(\delta))[\tilde{\alpha}](s)=\begin{cases}\delta[\mathfrak{A}_{\mu}(\tilde{\alpha})](\sigma_{\mu}(s)),&s\in\textrm{Range}(\sigma^{-1}_{\mu}),\\\
\text{any }b\in B,&s\notin\textrm{Range}(\sigma^{-1}_{\mu}),\end{cases}$ (144)
$\displaystyle(\mathfrak{D}_{\mu}(\tilde{\delta}))[\alpha](s)=\begin{cases}\tilde{\delta}[\tilde{\mathfrak{A}}_{\mu}(\alpha)](\sigma^{-1}_{\mu}(s)),&s\in[t,\sigma_{\mu}(T)],\\\
\text{any }b\in B,&s\in(\sigma_{\mu}(T),T].\end{cases}$ (145)

These definitions satisfy the following properties:

$\displaystyle\begin{split}&(\tilde{\mathfrak{A}}_{\mu}(\mathfrak{A}_{\mu}(\tilde{\alpha})))(s)=\tilde{\alpha}(s),\\\
&(\tilde{\mathfrak{D}}_{\mu}(\mathfrak{D}_{\mu}(\tilde{\delta})))[\tilde{\alpha}](s)=\tilde{\delta}[\tilde{\alpha}](s),\end{split}\quad\text{for
}s\in\textrm{Range}(\sigma^{-1}_{\mu})$ (146)
$\displaystyle\begin{split}&(\mathfrak{A}_{\mu}(\tilde{\mathfrak{A}}_{\mu}(\alpha)))(s)={\alpha}(s),\\\
&(\mathfrak{D}_{\mu}(\tilde{\mathfrak{D}}_{\mu}(\delta)))[\alpha](s)=\delta[\alpha](s),\end{split}\quad\text{for
}s\in[t,\sigma_{\mu}(T)],$ (147)
$\displaystyle\big{\\{}\alpha={\mathfrak{A}}_{\mu}(\tilde{\alpha})~{}|~{}\tilde{\alpha}\in\mathcal{A}(t)\big{\\}}=\mathcal{A}(t),\forall\mu\in\mathcal{M}(t)$
(148)
$\displaystyle\big{\\{}\delta={\mathfrak{D}}_{\mu}(\tilde{\delta})~{}|~{}\tilde{\delta}\in\Delta(t)\big{\\}}=\Delta(t),\forall\mu\in\mathcal{M}(t).$
(149)

Consider $(\tilde{\mathrm{x}},\tilde{\mathrm{z}})$ solving (39) for
$(\tilde{\alpha},\tilde{\delta}[\tilde{\alpha}],\mu)$,
$(\mathrm{x},\mathrm{z})$ solving (17) for
$(\mathfrak{A}_{\mu}(\tilde{\alpha}),(\mathfrak{D}_{\mu}(\tilde{\delta}))[\mathfrak{A}_{\mu}(\tilde{\alpha})])$,
and $(\mathrm{x}_{1},\mathrm{z}_{1})$ solving (17) for
$(\alpha,\delta[\alpha])$. Then, we have

$\displaystyle\sup_{\tilde{\delta}\in\Delta(t)}\inf_{\tilde{\alpha}\in\mathcal{A}(t)}\max\big{\\{}\max_{s\in[t,T]}c(\tilde{\mathrm{x}}(s)),g(\tilde{\mathrm{x}}(T))-\tilde{\mathrm{z}}(T)\big{\\}}$
$\displaystyle=$
$\displaystyle\sup_{\tilde{\delta}\in\Delta(t)}\inf_{\tilde{\alpha}\in\mathcal{A}(t)}\max\big{\\{}\max_{s\in[t,\sigma_{\mu}(T)]}c(\mathrm{x}(s)),$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad
g(\mathrm{x}(\sigma_{\mu}(T)))-{\mathrm{z}}(\sigma_{\mu}(T))\big{\\}},$ (150)
$\displaystyle=$
$\displaystyle\sup_{\delta\in\Delta(t)}\inf_{\alpha\in\mathcal{A}(t)}\max\big{\\{}\max_{s\in[t,\sigma_{\mu}(T)]}c(\mathrm{x}_{1}(s)),$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad
g(\mathrm{x}_{1}(\sigma_{\mu}(T)))-{\mathrm{z}}_{1}(\sigma_{\mu}(T))\big{\\}},$
(151) $\displaystyle\leq$ $\displaystyle V_{1}^{+}(t,x,z).$ (152)

(150) is by (135) and (136), and (151) is according to (148) and (149). Since
the above inequality holds for all $\mu$, we substitute $\nu_{A}[\alpha]$ for
$\mu$ and take the supremum over $\nu_{A}$ on the both sides, which concludes
$\tilde{V}_{1}^{+}(t,x,z)\leq V_{1}^{+}(t,x,z)$.

By (ii) and (iii), we conclude $V_{1}^{+}(t,x,z)=\tilde{V}_{1}^{+}(t,x,z)$.

(iv) $V_{1}^{-}(t,x)=\tilde{V}_{1}^{-}(t,x)$

Define $\tilde{\mathfrak{B}}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(t)\rightarrow\mathcal{B}(t)$ and its pseudo inverse
function $\mathfrak{B}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{B}(t)\rightarrow\mathcal{B}(t)$:

$\displaystyle(\tilde{\mathfrak{B}}_{\mu}(\beta))(s)\coloneqq\begin{cases}\beta\big{(}\sigma_{\mu}(s)\big{)},&s\in\text{Range}(\sigma_{\mu}^{-1}),\\\
\text{any }b\in B,&s\notin\text{Range}(\sigma_{\mu}^{-1}),\end{cases}$ (153)
$\displaystyle(\mathfrak{B}_{\mu}(\tilde{\beta}))(s)\coloneqq\begin{cases}\tilde{\beta}(\sigma^{-1}_{\mu}(s)),&s\in[t,\sigma_{\mu}(T)],\\\
\text{any }b\in B,&s\in(\sigma_{\mu}(T),T],\end{cases}$ (154)

Also, define $\tilde{\mathfrak{C}}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\Gamma(t)\rightarrow\tilde{\Gamma}(t)$, where $\tilde{\Gamma}(t)$ is
defined in (37), and its pseudo inverse function
$\mathfrak{C}_{\mu}\mathrel{\mathop{\mathchar
58\relax}}\tilde{\Gamma}(t)\rightarrow\Gamma(t)$:

$\displaystyle(\tilde{\mathfrak{C}}_{\mu}(\gamma))[\tilde{\beta},\mu](s)=\begin{cases}\gamma[\mathfrak{B}_{\mu}(\tilde{\beta})]\big{(}\sigma_{\mu}(s)\big{)},&s\in\text{Range}(\sigma_{\mu}^{-1}),\\\
\text{any }a\in A,&s\notin\text{Range}(\sigma_{\mu}^{-1}),\end{cases}$ (155)
$\displaystyle({\mathfrak{C}_{\mu}}(\tilde{\gamma}))[\beta](s)=\begin{cases}\tilde{\gamma}[\tilde{\mathfrak{B}}_{\mu}(\beta),\mu]\big{(}\sigma^{-1}_{\mu}(s)\big{)},&s\in[t,\sigma_{\mu}(T)],\\\
\text{any }a\in A,&s\in(\sigma_{\mu}(T),T].\end{cases}$ (156)

These definitions satisfy the following properties: for any
$\mu\in\mathcal{M}(t)$,

$\displaystyle\big{\\{}\beta={\mathfrak{B}}_{\mu}(\tilde{\beta})~{}|~{}\tilde{\beta}\in\mathcal{B}(t)\big{\\}}=\mathcal{B}(t),$
(157)
$\displaystyle\big{\\{}\gamma={\mathfrak{C}}_{\mu}(\tilde{\gamma})~{}|~{}\tilde{\gamma}\in\tilde{\Gamma}(t)\big{\\}}=\Gamma(t).$
(158)

Consider $(\tilde{\mathrm{x}},\tilde{\mathrm{z}})$ solving (39) for
$(\tilde{\gamma}[\tilde{\beta},\mu],\tilde{\beta},\mu)$,
$(\mathrm{x},\mathrm{z})$ solving (17) for
$(\mathfrak{C}_{\mu}(\tilde{\gamma})[\mathfrak{B}_{\mu}(\tilde{\beta})],\mathfrak{B}_{\mu}(\tilde{\beta}))$,
and $(\mathrm{x}_{1},\mathrm{z}_{1})$ solving (17) for
$(\gamma[\beta],\beta)$.

$\displaystyle\tilde{V}_{1}^{-}(t,x,z)=\inf_{\tilde{\gamma}\in\tilde{\Gamma}(t)}\sup_{\tilde{\beta}\in\mathcal{B}(t),\mu\in\mathcal{M}(t)}\max\big{\\{}\max_{s\in[t,T]}c(\tilde{\mathrm{x}}(s)),$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
g(\tilde{\mathrm{x}}(T))-\tilde{\mathrm{z}}(T)\big{\\}}$
$\displaystyle=\inf_{\tilde{\gamma}\in\tilde{\Gamma}(t)}\sup_{\tilde{\beta}\in\mathcal{B}(t),\mu\in\mathcal{M}(t)}\max\big{\\{}\max_{s\in[t,\sigma_{\mu}(T)]}c(\mathrm{x}(s)),$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
g(\mathrm{x}(\sigma_{\mu}(T)))-\mathrm{z}(\sigma_{\mu}(T))\big{\\}}$ (159)
$\displaystyle=\inf_{\gamma\in\Gamma(t)}\sup_{\beta\in\mathcal{B}(t),\mu\in\mathcal{M}(t)}\max\big{\\{}\max_{s\in[t,\sigma_{\mu}(T)]}c(\mathrm{x}_{1}(s)),$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad
g(\mathrm{x}_{1}(\sigma_{\mu}(T)))-\mathrm{z}_{1}(\sigma_{\mu}(T))\big{\\}}.$
(160)

(159) is by (135) and (136), and (160) is by (157) and (158). In the term in
(160), $\mu$ only controls the terminal time ($\sigma_{\mu}(T)$), hence, the
supremum over $\mu$ can be converted to the maximum over $\tau$, which
concludes $V_{1}^{-}(t,x,z)=\tilde{V}_{1}^{-}(t,x,z)$.

∎

###  .5 Proof of Theorem 2

Proof. The terminal value is derived by substituting $T$ for $t$ in (40) or
(41):

$\displaystyle V_{1}^{\pm}(T,x,z)=\max\\{c(T,x),g(T,x)-z\\}$ (161)

for all $(x,z)\in\mathbb{R}^{n}\times\mathbb{R}$.

(i) [2] has presented the HJ equation for state-constrained problems, in which
the terminal time is fixed. By applying the HJ equation in [2] to $V_{1}^{+}$,

$\displaystyle 0=\max\big{\\{}c(x)$ $\displaystyle-
V_{1}^{+},V^{+}_{1,t}-\tilde{H}_{1}^{+}(x,z,D_{x}V_{1}^{+},D_{z}V_{1}^{+})\big{\\}},$
(162)

where

$\displaystyle\tilde{H}_{1}^{+}(x,z,p,q)\coloneqq\max_{a\in
A}\min_{\begin{subarray}{c}b\in B\\\ b_{d}\in[0,1]\end{subarray}}-p\cdot
f(x,a,b)b_{d}+qL(x,a,b)b_{d}.$ (163)

Since, for all $a\in A,b\in B$, the term $-p\cdot
f(x,a,b)b_{d}+qL(x,a,b)b_{d}$ is minimized at $b_{d}=0$ or 1,

$\displaystyle\begin{split}\tilde{H}_{1}^{+}(x,z,p,q)&=\max_{a\in
A}\min\big{\\{}0,\\\ &\min_{b\in B}-p\cdot
f(x,a,b)+qL(x,a,b)\big{\\}}.\end{split}$ (164)

Also, $0$ does not depend on $a$, thus, the maximum over $a$ operation can
move into the minimum operation:

$\displaystyle\begin{split}\tilde{H}_{1}^{+}(x,z,p&,q)=\min\\{0,\bar{H}^{+}(x,z,p,q)\\},\end{split}$
(165)

where $\bar{H}^{+}$ is defined in (27). By applying (165) to (162), (43) is
proved for $V_{1}^{+}$.

(ii) By applying [2] to $V_{1}^{-}$,

$\displaystyle 0=\max\big{\\{}c(x)$ $\displaystyle-
V_{1}^{-},V^{-}_{1,t}-\tilde{H}_{1}^{-}(x,z,D_{x}V_{1}^{-},D_{z}V_{1}^{-})\big{\\}},$
(166)

where

$\displaystyle\tilde{H}_{1}^{-}(x,z,p,q)\coloneqq\min_{\begin{subarray}{c}b\in
B\\\ b_{d}\in[0,1]\end{subarray}}\max_{a\in A}-p\cdot
f(x,a,b)b_{d}+qL(x,a,b)b_{d}.$ (167)

Since $b_{d}\in[0,1]$ is non-negative,

$\displaystyle\tilde{H}_{1}^{-}(x,z,p,q)$
$\displaystyle=\min_{b_{d}\in[0,1]}b_{d}\min_{b\in B}\max_{a\in A}[-p\cdot
f(x,a,b)$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad+qL(x,a,b)]$
$\displaystyle=\min\\{0,\bar{H}^{-}(x,z,p,q)\\},$ (168)

where $\bar{H}^{-}$ is defined in (28). (166) and (168) prove (43) for
$V_{1}^{-}$. ∎

## References

  * [1] L. C. Evans and P. E. Souganidis, “Differential games and representation formulas for solutions of Hamilton-Jacobi-Isaacs equations,” _Indiana University mathematics journal_ , vol. 33, no. 5, pp. 773–797, 1984.
  * [2] A. Altarovici, O. Bokanowski, and H. Zidani, “A general hamilton-jacobi framework for non-linear state-constrained control problems,” _ESAIM: Control, Optimisation and Calculus of Variations_ , vol. 19, no. 2, pp. 337–357, 2013.
  * [3] I. M. Mitchell, A. M. Bayen, and C. J. Tomlin, “A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games,” _IEEE Transactions on Automatic Control_ , vol. 50, no. 7, pp. 947–957, 2005.
  * [4] K. Margellos and J. Lygeros, “Hamilton-Jacobi formulation for reach-avoid differential games,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 8, pp. 1849–1861, 2011.
  * [5] J. F. Fisac, M. Chen, C. J. Tomlin, and S. S. Sastry, “Reach-avoid problems with time-varying dynamics, targets and constraints,” in _Proceedings of the 18th international conference on hybrid systems: computation and control_. ACM, 2015, pp. 11–20.
  * [6] D. Lee, A. Keimer, A. M. Bayen, and C. J. Tomlin, “Hamilton-Jacobi Formulation for State-Constrained Optimal Control and Zero-Sum Game Problems,” in _Decision and Control (CDC), 2020 IEEE 59th Conference on_. IEEE, 2020, accepted.
  * [7] R. J. Elliott and N. J. Kalton, _The existence of value in differential games_. American Mathematical Soc., 1972, vol. 126.
  * [8] I. M. Mitchell and J. A. Templeton, “A toolbox of Hamilton-Jacobi solvers for analysis of nondeterministic continuous and hybrid systems,” in _International Workshop on Hybrid Systems: Computation and Control_. Springer, 2005, pp. 480–494.
  * [9] I. M. Mitchell and C. J. Tomlin, “Overapproximating reachable sets by Hamilton-Jacobi projections,” _J. Scientific Computing_ , vol. 19, no. 1-3, pp. 323–346, 2003.
  * [10] M. G. Crandall and P.-L. Lions, “Two approximations of solutions of hamilton-jacobi equations,” _Mathematics of computation_ , vol. 43, no. 167, pp. 1–19, 1984.
  * [11] S. Osher and R. Fedkiw, _Level Set Methods and Dynamic Implicit Surfaces_. Springer-Verlag, 2003, vol. 153.
  * [12] C.-W. Shu and S. Osher, “Efficient implementation of essentially non-oscillatory shock-capturing schemes,” _Journal of computational physics_ , vol. 77, no. 2, pp. 439–471, 1988.
  * [13] M. P. Chapman, K. M. Smith, V. Cheng, D. L. Freyberg, and C. J. Tomlin, “Reachability analysis as a design tool for stormwater systems,” in _2018 IEEE Conference on Technologies for Sustainability (SusTech)_. IEEE, 2018, pp. 1–8.
  * [14] M. Chen, S. Herbert, S. Bansal, and C. Tomlin, “Optimal control helper toolbox,” http://github.com/HJReachability/helperOC.
  * [15] E. Barron and H. Ishii, “The bellman equation for minimizing the maximum cost,” _Nonlinear Analysis: Theory, Methods & Applications_, vol. 13, no. 9, pp. 1067–1090, 1989.
  * [16] L. C. Evans, _Partial differential equations_. American Mathematical Society, 2010.
  * [17] D. Lee and C. J. Tomlin, “A Hopf-Lax formula in Hamilton-Jacobi analysis of reach-avoid problems,” _IEEE Control Systems Letters_ , vol. 5, no. 3, pp. 1055–1060, 2020.

[]Donggun Lee is a Ph.D. student in Mechanical Engineering at UC Berkeley. He
received B.S. and M.S. degrees in Mechanical Engineering from Korea Advanced
Institute of Science and Technology (KAIST), Daejeon, Korea, in 2009 and 2011,
respectively. Donggun works in the area of control theory and robotics. []Dr.
Claire Tomlin is the Charles A. Desoer Professor of Engineering in EECS at
Berkeley. She was an Assistant, Associate, and Full Professor in Aeronautics
and Astronautics at Stanford from 1998 to 2007, and in 2005 joined Berkeley.
Claire works in the area of control theory and hybrid systems, with
applications to air traffic management, UAV systems, energy, robotics, and
systems biology. She is a MacArthur Foundation Fellow (2006), an IEEE Fellow
(2010), in 2017 she was awarded the IEEE Transportation Technologies Award,
and in 2019 was elected to the National Academy of Engineering and the
American Academy of Arts and Sciences.