11institutetext: University of Oxford, UK 22institutetext: University of
Edinburgh, UK 33institutetext: IRIF & CNRS, Université Paris cité, France
44institutetext: University of Liverpool, UK

# Memoryless Strategies in
Stochastic Reachability Games

Stefan Kiefer 11 Richard Mayr 22 Mahsa Shirmohammadi 33 Patrick Totzke 44

###### Abstract

We study concurrent stochastic reachability games played on finite graphs. Two
players, Max and Min, seek respectively to maximize and minimize the
probability of reaching a set of target states. We prove that Max has a
memoryless strategy that is optimal from all states that have an optimal
strategy. Our construction provides an alternative proof of this result by
Bordais, Bouyer and Le Roux [4], and strengthens it, as we allow Max’s action
sets to be countably infinite.

###### Keywords:

Stochastic games Reachability Strategy Complexity.

##  1 Introduction

#### Background.

We study 2-player zero-sum stochastic games. First introduced by Shapley in
his seminal 1953 work [22], they model dynamic interactions in which the
environment responds randomly to players’ actions. Shapley’s games were
generalized in [11] and [16] to allow infinite state and action sets and non-
termination.

In _concurrent games_ , the two players (Max and Min) jointly create an
infinite path through a directed graph. In each round of the play, both
independently choose an action. The next state is then determined according to
a pre-defined distribution that depends on the current state and the chosen
pair of actions. _Turn-based games_ (also called switching-control games) are
a subclass where each state is owned by some player and only this player gets
to choose an action. These have received much attention by computer
scientists, e.g., [12, 6, 5, 14, 2]. An even more special case of stochastic
games are _Markov Decision Processes (MDPs)_ where all states are owned by Max
(i.e., Min is passive). MDPs are also called _games against nature_.

We consider _reachability objectives_ which are defined w.r.t. a given subset
of _target_ states. A play is defined as winning for Max iff it visits a
target state at least once. Thus Max aims to maximize the probability that the
target set is reached. Dually, Min aims to minimize the probability of
reaching the target. So Min pursues the dual _safety objective_ of avoiding
the target.

Reachability is arguably the simplest objective in games on graphs. It can
trivially be encoded into reward-based objectives; i.e., every play that
reaches the target gets reward $1$ and all other plays get reward $0$.

In turn-based reachability games over finite state spaces, there always exist
optimal Max strategies that are memoryless (choices only depend on the current
state and not the history of the play; this is also called positional) and
deterministic (always chose on action as opposed to randomising among several)
[7], [17, Proposition 5.6.c, Proposition 5.7.c].

This does not carry over to finite concurrent reachability games. E.g., in the
_snowball game_ (aka _Hide-or-Run_ game) [9, Example 1][16, 1] (also see
Example 2 later in this paper), Max does not have an optimal strategy.
However, by [21, Corollary 3.9], Max always has $\varepsilon$-optimal
randomized memoryless strategies, and this holds even in countably infinite
reachability games with finite action sets. (Deterministic strategies are
generally useless in concurrent games, even in very simple games such as
_Rock-Paper-Scissors_.)

Even though optimal Max strategies do not always exist, it is still
interesting how much memory they need in those instances where they do exist.
For finite concurrent reachability games with finite action sets, it was
recently shown by Bordais, Bouyer and Le Roux [4] that optimal Max strategies,
if they exist, can be chosen as randomized memoryless. The proof is
constructive and iteratively builds the strategy on the finite state space. To
show the correctness, one needs to argue about the performance of the
constructed strategy. The proof in [4] heavily relies on the properties of
induced finite MDPs, obtained by fixing one strategy in the game. In
particular, it uses the existence of end components in these finite MDPs and
their particular properties.

#### Our contribution.

We give an alternative proof of this result by Bordais, Bouyer and Le Roux
[4]. While our proof is also constructive, it is simpler and works directly
from first principles on games, without using properties of induced MDPs.
Moreover, it uses a construction that we call “leaky games”, by which we
reduce the reachability objective to its dual safety objective. Finally, our
result is slightly stronger, because it holds even if Max is allowed countably
infinite action sets (while Min still has finite action sets). 111It may be
possible to generalize the proof in [4] to countably infinite Max actions
sets, but this would require (at least) a generalization of the fixpoint
theorem [4, Theorem 12] to this setting.

This result requires the state space to be finite. However, for other results
in this paper we allow the state space and action sets to be countably
infinite, unless explicitly stated otherwise.

##  2 Preliminaries

A _probability distribution_ over a countable set $S$ is a function
$\alpha:S\to[0,1]$ with $\sum_{s\in S}\alpha(s)=1$. The _support_ of $\alpha$
is the set $\\{s\in S\mid\alpha(s)>0\\}$. We write $\mathcal{D}(S)$ for the
set of all probability distributions over $S$. For $\alpha\in\mathcal{D}(S)$
and a function $v:S\to\mathbb{R}$ we write
$\langle\alpha,v\rangle\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sum_{s\in
S}\alpha(s)v(s)$ for the expectation of $v$ with respect to $\alpha$.

### Stochastic Games

We study perfect information stochastic games between two players, Max(imizer)
and Min(imizer). A _(concurrent) game_ ${\mathcal{G}}$ is played on a
countable set of states $S$. For each state $s\in S$ there are nonempty
countable _action_ sets $A(s)$ and $B(s)$ for Max and Min, respectively. A
_mixed action_ for Max (resp. Min) in state $s$ is a distribution over $A(s)$
(resp. $B(s)$).

Let $Z\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{(s,a,b)\mid s\in S,\
a\in A(s),\ b\in B(s)\\}$. For every triple $(s,a,b)\in Z$ there is a
distribution $p(s,a,b)\in\mathcal{D}(S)$ over successor states. We call a
state $s\in S$ a _sink_ state if $p(s,a,b)=s$ for all $a\in A(s)$ and $b\in
B(s)$. We extend the _transition function_ $p$ to mixed actions
$\alpha\in\mathcal{D}(A(s))$ and $\beta\in\mathcal{D}(B(s))$ by letting

$p(s,\alpha,\beta)\,\,\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sum_{a\in
A(s)}\sum_{b\in B(s)}\alpha(a)\beta(b)p(s,a,b),$

which is a distribution over $S$. A _play_ from an initial state $s_{0}$ is an
infinite sequence in $Z^{\omega}$ where the first triple contains $s_{0}$.
Starting from $s_{0}$, the game is played in stages
$\mathbb{N}=\\{0,1,2,\dots\\}$. At every stage $n\in\mathbb{N}$, the play is
in some state $s_{n}$. Max chooses a mixed action
$\alpha_{n}\in\mathcal{D}(A(s_{n}))$ and Min chooses a mixed action
$\beta_{n}\in\mathcal{D}(B(s_{n}))$. The next state $s_{n+1}$ is then chosen
according to the distribution $p(s_{n},a_{n},b_{n})$.

### Strategies and Probability Measures

The set of _histories_ at stage $n$, with $n\in\mathbb{N}$, is denoted by
$H_{n}$. That is, $H_{0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}S$
and $H_{n}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}Z^{n}\times S$ for
all $n>0$. Let
$H\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcup_{n\in\mathbb{N}}H_{n}$
be the set of all histories; note that $H$ is countable. For each history
$h=(s_{0},a_{0},b_{0})\cdots(s_{n-1},a_{n-1},b_{n-1})s_{n}\in H_{n}$, let
$s_{h}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}s_{n}$ denote the final
state in $h$.

A _strategy_ for Max is a function $\sigma$ that to each history $h\in H$
assigns a mixed action $\sigma(h)\in\mathcal{D}(A(s_{h}))$. Denote by $\Sigma$
the set of strategies for Max. Analogously, a _strategy_ for Min is a function
$\pi$ that to each history $h$ assigns a mixed action
$\pi(h)\in\mathcal{D}(B(s_{h}))$, and $\Pi$ denotes the set of strategies for
Min. A Max strategy is called _memoryless_ if $\sigma(h)$ depends only on
$s_{h}$; i.e., for all $h,h^{\prime}\in H$ with $s_{h}=s_{h^{\prime}}$ we have
$\sigma(h)=\sigma(h^{\prime})$. A memoryless strategy $\sigma$ is fully
determined by $(\sigma(s))_{s\in S}$. A _memory-based strategy_ bases its
decisions not only on the current state, but also on the current mode of its
memory, and it can update its memory at every step, depending on the observed
events in this step. Memory is called _public_ if the content is also
observable by the opposing player and _private_ otherwise. Finite-memory
strategies use a memory with only finitely many different possible modes. A
step counter is a special case of infinite memory in the form of a discrete
clock that gets incremented at every step, independently of the actions of the
players. Strategies that use just a step counter are also called _Markov
strategies_.

An initial state $s_{0}$ and a pair of strategies $\sigma,\pi$ for Max and Min
induce a probability measure on sets of plays. We write
${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({E})$ for the probability of a
measurable set of plays $E$ starting from $s_{0}$. It is initially defined for
the cylinder sets generated by the histories and then extended to the sigma-
algebra by Carathéodory’s unique extension theorem [3]. Given a random
variable $V:Z^{\omega}\to\mathbb{R}$, we will write
${\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}(V)$ for the expectation of $V$
w.r.t. ${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}$. We may drop
${\mathcal{G}}$ from the subscript when it is understood.

### Objectives

We consider reachability and safety objectives. Given a set $T\subseteq S$ of
states, the _reachability_ objective $\mathtt{Reach}(T)$ is the set of plays
that visit $T$ at least once, i.e., $s_{h}\in T$ holds for some history $h$
that is a prefix of the play. The dual _safety_ objective
$\mathtt{Avoid}(T)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}Z^{\omega}\setminus\mathtt{Reach}(T)$
consists of the plays that never visit $T$. We can and will assume that
$T=\\{\top\\}$ holds for a sink state $\top\in S$ and write
$\mathtt{Reach}(\top)$ for $\mathtt{Reach}(\\{\top\\})$. Similarly, we assume
that there is another sink state $\bot\in S$, with $\bot\neq\top$, and write
$\mathtt{Avoid}(\bot)$ for $\mathtt{Avoid}(\\{\bot\\})$. Max attempts to
maximize the probability of achieving the given objective (usually
$\mathtt{Reach}(\top)$ or $\mathtt{Avoid}(\top)$), whereas Min attempts to
minimize it.

### Value and Optimality

For a game ${\mathcal{G}}$, objective $E$ and initial state $s_{0}$, the
_lower value_ and _upper value_ of $s_{0}$ are respectively defined as

${\mathtt{val}^{\downarrow}_{{\mathcal{G}},E}(s_{0})}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\sigma\in\Sigma}\inf_{\pi\in\Pi}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({E})\quad\text{and}\quad{\mathtt{val}^{\uparrow}_{{\mathcal{G}},E}(s_{0})}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\inf_{\pi\in\Pi}\sup_{\sigma\in\Sigma}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({E})\,.$

The inequality
${\mathtt{val}^{\downarrow}_{{\mathcal{G}},E}(s_{0})}\leq{\mathtt{val}^{\uparrow}_{{\mathcal{G}},E}(s_{0})}$
holds by definition. If
${\mathtt{val}^{\downarrow}_{{\mathcal{G}},E}(s_{0})}={\mathtt{val}^{\uparrow}_{{\mathcal{G}},E}(s_{0})}$,
then this quantity is called the _value_ , denoted by
${\mathtt{val}_{{\mathcal{G}},E}(s_{0})}$. For reachability objectives, like
all Borel objectives, the value exists if all action sets are finite [18], and
even if for all states $s$ we have that $A(s)$ is finite or $B(s)$ is finite
[10, Theorem 11]. We always assume the latter, so that
${\mathtt{val}_{{\mathcal{G}},E}(s_{0})}$ exists. For $\varepsilon\geq 0$, a
Max strategy $\sigma$ is called _$\varepsilon$ -optimal_ from $s_{0}$ if for
all Min strategies $\pi$ we have
${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({E})\geq{\mathtt{val}_{{\mathcal{G}},E}(s_{0})}-\varepsilon$.
A $0$-optimal strategy is also called _optimal_. For $E=\mathtt{Reach}(\top)$
or $E=\mathtt{Avoid}(\bot)$ we have

${\mathtt{val}_{{\mathcal{G}},E}(s_{0})}\ =\
\sup_{\alpha\in\mathcal{D}(A(s_{0}))}\inf_{\beta\in\mathcal{D}(B(s_{0}))}\langle
p(s_{0},\alpha,\beta),{\mathtt{val}_{{\mathcal{G}},E}}{}\rangle\,.$ (1)

We note in passing that the equality in (1) also holds in the states
$\top,\bot$, as these are sink states.

##  3 Martingales for Safety

For the remainder of the paper we fix a game ${\mathcal{G}}$ over a countable
state space $S$. Whenever we make finiteness assumptions on $S$ and the action
sets, we state them explicitly. Several times we use the following lemma, a
consequence of the optional-stopping theorem for submartingales.

###### Lemma 1

Let $\sigma$ and $\pi$ be Max and Min strategies, respectively. Suppose
$v:S\to[0,1]$ is a function with $v(\bot)=0$ such that $\langle
p(s_{h},\sigma(h),\pi(h)),v\rangle\geq v(s_{h})$ holds for all histories $h$.
Then ${\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Avoid}(\bot))\geq v(s_{0})$
holds for all $s_{0}\in S$.

###### Proof

Let $s_{0}\in S$. Define a sequence of random variables $V(0),V(1),\ldots$
with $V(i):Z^{\omega}\to[0,1]$ by

$V(i)((s_{0},a_{0},b_{0})(s_{1},a_{1},b_{1})\cdots)\
\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\ v(s_{i})\,.$

Similarly, denote by $H(i):Z^{\omega}\to H_{i}$ the function that maps each
random play to its unique prefix in $H_{i}$. Recall that we can create random
variables via composition of functions. Consider the function $s:H\to S$ that
maps each finite history $h$ to its final state $s_{h}$; this function
composed with $H(i)$ is the random variable $s_{H(i)}:Z^{\omega}\to S$.
Moreover, the function $v$ composed with $s_{H(i)}$ is the random variable
$v(s_{H(i)})$. Note that $V(i)=v(s_{H(i)})$. For $i\geq 0$, let
$\mathcal{F}_{i}$ be the sigma-algebra generated by the cylinder sets
corresponding to the histories $h\in H_{i}$. Then $V(i)$ and $H(i)$ are
$\mathcal{F}_{i}$-measurable. By the assumption on $v$ we have

$\displaystyle{\mathcal{E}}_{s_{0},\sigma,\pi}(V(i+1)\mid\mathcal{F}_{i})\ $
$\displaystyle=\
{\mathcal{E}}_{s_{0},\sigma,\pi}(v(s_{H(i+1)})\mid\mathcal{F}_{i})$
$\displaystyle=\ \sum_{s\in S}p(s_{H(i)},\sigma(H(i)),\pi(H(i)))v(s)$
$\displaystyle=\ \langle p(s_{H(i)},\sigma(H(i)),\pi(H(i))),v\rangle$
$\displaystyle\geq\ v(s_{H(i)})\ =\ V(i)\;.$

It follows that $V(0),V(1),\ldots$ is a submartingale with respect to the
filtrations $\mathcal{F}_{0},\mathcal{F}_{1},\ldots$. Moreover $|V(i)|\leq 1$
holds for all $i$. This boundedness condition together with the optional-
stopping theorem imply that, almost surely, $V(0),V(1),\ldots$ converges to a
random variable $V(\infty)$ with

${\mathcal{E}}_{s_{0},\sigma,\pi}(V(\infty))\ \geq\
{\mathcal{E}}_{s_{0},\sigma,\pi}(V(0))\ =\ v(s_{0})\,.$

On the other hand, since $\bot$ is a sink,

$\displaystyle{\mathcal{E}}_{s_{0},\sigma,\pi}(V(\infty))\ $ $\displaystyle=\
{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Avoid}(\bot))\cdot{\mathcal{E}}_{s_{0},\sigma,\pi}(V(\infty)\mid\mathtt{Avoid}(\bot))$
$\displaystyle\ \
\mbox{}+{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Reach}(\bot))\cdot{\mathcal{E}}_{s_{0},\sigma,\pi}(V(\infty)\mid\mathtt{Reach}(\bot))$
$\displaystyle\leq\
{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Avoid}(\bot))\cdot
1+{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Reach}(\bot))\cdot 0$
$\displaystyle=\ {\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Avoid}(\bot))\,.$ ∎

##  4 Optimal Safety

We will construct memoryless strategies for reachability from strategies for
safety. The following proposition will be useful for this purpose and is of
independent interest.

###### Proposition 1

Suppose Max’s action sets are finite. Then Max has a memoryless strategy
$\sigma$ that is optimal for $\mathtt{Avoid}(\bot)$ from every state. That is,
for all $s\in S$ and all Min strategies $\pi$

${\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Avoid}(\bot))\ \geq\
{\mathtt{val}_{\mathtt{Avoid}(\bot)}(s)}\,.$

###### Proof

Since Max has only finite action sets, the supremum in (1) is taken over a
compact set of mixed actions. Therefore, it is a maximum; i.e, for every $s\in
S$ there is a mixed action, say $\sigma(s)\in\mathcal{D}(A(s))$, such that for
all mixed Min actions $\beta\in\mathcal{D}(B(s))$

${\mathtt{val}_{\mathtt{Avoid}(\bot)}(s)}\ \leq\ \langle
p(s,\sigma(s),\beta),{\mathtt{val}_{\mathtt{Avoid}(\bot)}}\rangle\,.$ (2)

Extend $\sigma$ to a memoryless Max strategy in the natural way, and let $\pi$
be an arbitrary Min strategy. Then the function
${\mathtt{val}_{\mathtt{Avoid}(\bot)}}$ satisfies the conditions of Lemma 1.
Thus,
${\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Avoid}(\bot))\geq{\mathtt{val}_{\mathtt{Avoid}(\bot)}(s)}$
holds for all $s$. ∎

transition | $s$ | $\bot$
---|---|---
function $p$
$p(s,a_{i},b)$ | $1-2^{-i}\;$ | $\;2^{-i}$

$s$$\bot$$a_{i}$$b$$:~{}2^{-i}$$a_{i}$$b$$:~{}1-2^{-i}$

Figure 1: A finite-state MDP where Max has no $\varepsilon$-optimal memoryless
strategy for safety objective $\mathtt{Avoid}(\bot)$. The state $\bot$ is a
sink state. The set $\\{a_{i}\mid i\in\mathbb{N}\\}$ of Max’s actions at $s$
is countable, while Min only has a single action $b$.

###### Example 1

The assumption that Max has finite action sets cannot be dropped from
Proposition 1. This assumption is required even for finite-state MDPs, i.e.,
when $S$ is finite and Min has only one action per state. In fact, memoryless
$\varepsilon$-optimal strategies do not always exist for safety objectives. As
an example, consider the game depicted in Figure 1, which was first discussed
in [15]. The strategy that plays $a_{i+k}$ at stage $i$ is
$\frac{1}{2^{k}}$-optimal for Max; indeed, the probability of reaching $\bot$
at stage $i$ will be at most $2^{-(i+k+1)}$. Hence, the probability of
$\mathtt{Avoid}(\bot)$ is at least
$1-\sum_{i\in\mathbb{N}}2^{-(i+k+1)}=1-\frac{1}{2^{k}}$, as required. This
implies that ${\mathtt{val}_{\mathtt{Avoid}(\bot)}(s)}=1$.

Let $\sigma$ be some arbitrary memoryless strategy for Max. The probability
that state $\bot$ is not reached at stage $i$ is
$(1-p(s,\sigma(s),b)(\bot))^{i}$. Clearly, the probability of the event
$\mathtt{Avoid}(\bot)$ is $0$. ∎

##  5 $\varepsilon$-Optimal Reachability

Max does not always have optimal strategies for reachability, even when $S$
and all action sets are finite.

###### Example 2

Consider the game depicted in Figure 2, introduced in [16], also known as
_snowball_ or _hide-or-run_ [8]. Following the intuition given in [8], Max
initially hides behind a bush (state $s$) and his goal is to reach home (state
$\top$) without being hit by a snowball; Min is armed with a single snowball.

Below, in order to show that ${\mathtt{val}_{\mathtt{Reach}(\top)}(s)}=1$, for
all $\varepsilon$, such that $0<\varepsilon<1$, we exhibit an
$\varepsilon$-optimal strategy for Max. Given $\varepsilon$, consider the
memoryless Max’s strategy $\sigma$ defined by $\sigma(s)(hide)=1-\varepsilon$
and $\sigma(s)(run)=\varepsilon$. After fixing $\sigma$ in the game, by
Proposition 1, Min has optimal memoryless strategies $\pi$ for
$\mathtt{Avoid}(\top)$ in the new game. Let $\pi$ be a memoryless strategy for
Min, defined as

$\pi(s)(throw)=x\qquad\text{ and }\qquad\pi(s)(wait)=1-x.$

for some $0\leq x\leq 1$. Then

${\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Reach}(\top))=\varepsilon(1-x)+(1-\varepsilon)x+(1-\varepsilon)(1-x){\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Reach}(\top)).$

Solving this for ${\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Reach}(\top))$ yields

${\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Reach}(\top))\ =\
1-\frac{x\varepsilon}{\varepsilon+x(1-\varepsilon)}\ \geq\
1-\frac{x\varepsilon}{x\varepsilon+x(1-\varepsilon)}\ =\ 1-\varepsilon\,,$

implying that $\sigma$ is an $\varepsilon$-optimal strategy for Max.

A straightforward argument shows that there is no optimal strategy for Max in
this game. If Max always plays hide, Min can wait forever. If not, assume that
at some stage Max plays run with probability $\varepsilon>0$; then Min would
throw to reach $\bot$ with a positive probability.

transition | $s$ | $\top$ | $\bot$
---|---|---|---
function $p$
$p(s,h,w)$ | $1\;$ | $\;0\;$ | $\;0$
$p(s,h,t)$ | $0$ | $1$ | $0$
$p(s,r,w)$ | $0$ | $1$ | $0$
$p(s,r,t)$ | $0$ | $0$ | $1$

$s$$\top$$\bot$$r$$t$$r$$w$$h$$t$$h$$w$

Figure 2: The snowball game where Max has no optimal strategy for
$\mathtt{Reach}(\top)$. The states $\top$ and $\bot$ are sink states. Max’s
action set at $s$ is $\\{hide,run\\}$, shown as $h$ and $r$ in the figure,
while Min’s action set is $\\{wait,throw\\}$, shown as $w$ and $t$.

∎

In this section we prove the following proposition.

###### Proposition 2

Suppose that Min’s action sets are finite. Then for every $\varepsilon>0$ and
every finite subset of states $S_{0}\subseteq S$ Max has a memoryless strategy
$\sigma$ that is $\varepsilon$-optimal for $\mathtt{Reach}(\top)$ from all
$s_{0}\in S_{0}$ and for each $s\in S$ the support of $\sigma(s)$ is finite.

###### Remark 1

The assumption that Min’s action sets are finite can be replaced by the
assumption that $S$ is finite. The proof requires an extension of Lemma 1.

Proposition 2 does not carry over to countably infinite reachability games
with infinite action sets for Min; see Section 7.

For the rest of the section we assume that Min’s action sets are finite.
Towards a proof of Proposition 2 we consider, for $n\geq 0$, the horizon-
restricted reachability objective
$\mathtt{Reach}_{n}(\top)\subseteq\mathtt{Reach}(\top)$ consisting of the
plays that reach $\top$ within at most $n$ steps. For $s\in S$ write
${\mathtt{val}_{n}(s)}$ for ${\mathtt{val}_{\mathtt{Reach}_{n}(\top)}(s)}$. We
have ${\mathtt{val}_{0}(\top)}=1$ and ${\mathtt{val}_{0}(s)}=0$ for all
$s\neq\top$. For all $n\geq 0$, since
$\mathtt{Reach}_{n}(\top)\subseteq\mathtt{Reach}_{n+1}(\top)$, we have for all
$s\in S$

$\displaystyle{\mathtt{val}_{n}(s)}\ \leq\ {\mathtt{val}_{n+1}(s)}\ $
$\displaystyle=\
\sup_{\alpha\in\mathcal{D}(A(s))}\inf_{\beta\in\mathcal{D}(B(s))}\langle
p(s,\alpha,\beta),{\mathtt{val}_{n}}\rangle$ $\displaystyle=\
\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{n}}\rangle\,,$

as Min’s action sets are finite. For all $s\in S$, since
${\mathtt{val}_{0}(s)}\leq{\mathtt{val}_{1}(s)}\leq\ldots\leq 1$, there is a
limit
${\mathtt{val}_{\infty}(s)}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\lim_{n\to\infty}{\mathtt{val}_{n}(s)}$.

###### Lemma 2

Suppose that Min’s action sets are finite. For all $s\in S$ we have

${\mathtt{val}_{\infty}(s)}\ =\ \sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in
B(s)}\langle p(s,\alpha,b),{\mathtt{val}_{\infty}}\rangle\,.$

###### Proof

Let $s\in S$. Towards the “$\leq$” inequality, for any $n$ we have

$\displaystyle{\mathtt{val}_{n+1}(s)}\ $ $\displaystyle=\
\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{n}}\rangle$ $\displaystyle\leq\
\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{\infty}}\rangle\,.$

Thus,
${\mathtt{val}_{\infty}(s)}\leq\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in
B(s)}\langle p(s,\alpha,b),{\mathtt{val}_{\infty}}\rangle$.

Towards the “$\geq$” inequality, for any fixed $\alpha$ and $b$ the function
$\langle p(s,\alpha,b),\cdot\rangle:\mathbb{R}^{S}\to\mathbb{R}$ is a linear
map and, thus, continuous. Hence, for any $\alpha$

$\displaystyle\lim_{n\to\infty}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{n}}\rangle\ $ $\displaystyle=\ \min_{b\in
B(s)}\lim_{n\to\infty}\langle p(s,\alpha,b),{\mathtt{val}_{n}}\rangle$
$\displaystyle=\ \min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{\infty}}\rangle\,.$

It follows that

$\displaystyle{\mathtt{val}_{\infty}(s)}\ =\
\lim_{n\to\infty}{\mathtt{val}_{n+1}(s)}\ $ $\displaystyle=\
\lim_{n\to\infty}\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{n}}\rangle$ $\displaystyle\geq\
\sup_{\alpha\in\mathcal{D}(A(s))}\lim_{n\to\infty}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{n}}\rangle$ $\displaystyle=\
\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{\infty}}\rangle\,.$ ∎

Now the following lemma follows from Lemma 1.

###### Lemma 3

Suppose that Min’s action sets are finite. Then
${\mathtt{val}_{\mathtt{Reach}(\top)}}={\mathtt{val}_{\infty}}$.

###### Proof

Since $\mathtt{Reach}(\top)\supseteq\mathtt{Reach}_{n}(\top)$, we have
${\mathtt{val}_{\mathtt{Reach}(\top)}}\geq{\mathtt{val}_{n}}$. Towards the
other inequality, define a function $v:S\to[0,1]$ by
$v(s)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1-{\mathtt{val}_{\infty}(s)}$.
We have $v(\top)=1-{\mathtt{val}_{\infty}(\top)}=0$. Let $\sigma$ be an
arbitrary Max strategy. For every history $h$, let
$b_{h}\in\operatorname*{arg\,min}_{b\in B(s_{h})}\langle
p(s_{h},\sigma(h),b),{\mathtt{val}_{\infty}}\rangle$. Define a Min strategy
$\pi$ with $\pi(h)(b_{h})=1$ for all histories $h$. For all histories $h$ we
have

$\displaystyle\langle p(s_{h},\sigma(h),\pi(h)),v\rangle\ $ $\displaystyle=\
1-\langle p(s_{h},\sigma(h),\pi(h)),{\mathtt{val}_{\infty}}\rangle$ from the
definition of $v$ $\displaystyle\geq\ 1-{\mathtt{val}_{\infty}(s_{h})}$
$\displaystyle=\ v(s_{h})$ definition of $v$.

By Lemma 1, for all $s\in S$

${\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Reach}(\top))\ =\
1-{\mathcal{P}}_{s,\sigma,\pi}(\mathtt{Avoid}(\top))\ \leq\
1-v(s)={\mathtt{val}_{\infty}(s)}\,.$

Since $\sigma$ was arbitrary, we conclude that
${\mathtt{val}_{\mathtt{Reach}(\top)}}\leq{\mathtt{val}_{\infty}}$. ∎

Let us introduce an operation on games which makes transitions “leak” to
$\bot$. The intention is to “reduce” reachability to safety, in the sense that
in a leaky game, $\mathtt{Avoid}(\bot)$ is included in (and, hence, equal to)
$\mathtt{Reach}(\top)$ up to a measure-zero set of plays. We set up the leaky
game so that Max has an optimal strategy for $\mathtt{Avoid}(\bot)$, which,
according to Proposition 1, can be chosen to be memoryless.

For technical reasons, which will manifest themselves later, we associate the
leaks with Min actions. Concretely, for a state $s$, a Min action $b\in B(s)$,
and some $\varepsilon>0$, by _making $b$ leak $\varepsilon$_ we refer to
obtaining from $p$ another transition function $\check{p}$ by setting, for all
$a\in A(s)$ and $t\in S$,

$\check{p}(s,a,b)(t)\ \stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\
\begin{cases}(1-\varepsilon)p(s,a,b)(t)&\text{if }t\neq\bot\\\
(1-\varepsilon)p(s,a,b)(\bot)+\varepsilon&\text{if }t=\bot\,.\end{cases}$

Intuitively, a fraction of $\varepsilon$ of the probability mass leaks to
$\bot$ whenever $b$ is taken. We use leaks to prove Proposition 2.

######  Proof (of Proposition 2)

Let $\varepsilon>0$, and let $S_{0}\subseteq S$ be finite. Choose
$\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}>0$ such that
$\varepsilon_{1}+\varepsilon_{2}+\varepsilon_{3}=\varepsilon$. For each $s\in
S$ choose $a(s)\in A(s)$. By Lemma 3, since $S_{0}$ is finite, there is $n\geq
0$ such that
${\mathtt{val}_{n}(s)}\geq{\mathtt{val}_{\mathtt{Reach}(\top)}(s)}-\varepsilon_{1}$
holds for all $s\in S_{0}$. Inductively define (in general non-memoryless) Max
strategies $\sigma_{0},\ldots,\sigma_{n}$ as follows. For each history $h$,
define
$\sigma_{0}(h)(a(s_{h}))\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1$.
For $i\in\\{0,\ldots,n-1\\}$ and each state $s\in S$ we have
$\sup_{\alpha\in\mathcal{D}(A(s))}\min_{b\in B(s)}\langle
p(s,\alpha,b),{\mathtt{val}_{i}}\rangle={\mathtt{val}_{i+1}(s)}$; thus we can
define $\sigma_{i+1}(s)$ so that $\min_{b\in B(s)}\langle
p(s,\sigma_{i+1}(s),b),{\mathtt{val}_{i}}\rangle\geq{\mathtt{val}_{i+1}(s)}-\frac{\varepsilon_{2}}{n}$.
Since $\frac{\varepsilon_{2}}{n}>0$, we can assume without loss of generality
that the support of $\sigma_{i+1}(s)$ is finite. Finally, define
$\sigma_{i+1}(zh)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sigma_{i}(h)$
for all $z\in Z$ and $h\in H$.

We show inductively that for all $i\in\\{1,\ldots,n\\}$ and all $s\in S$

$\inf_{\pi\in\Pi}{\mathcal{P}}_{{\mathcal{G}},s,\sigma_{i},\pi}(\mathtt{Reach}_{i}(\top))\
\geq\ {\mathtt{val}_{i}(s)}-i\cdot\frac{\varepsilon_{2}}{n}\,.$ (3)

This is immediate for $i=0$. For $i\in\\{0,\ldots,n-1\\}$ we have

$\displaystyle\inf_{\pi\in\Pi}{\mathcal{P}}_{{\mathcal{G}},s,\sigma_{i+1},\pi}(\mathtt{Reach}_{i+1}(\top))$
$\displaystyle\geq\ \min_{b\in B(s)}\langle
p(s,\sigma_{i+1}(s),b),\inf_{\pi\in\Pi}{\mathcal{P}}_{{\mathcal{G}},\cdot,\sigma_{i},\pi}(\mathtt{Reach}_{i}(\top))\rangle$
$\displaystyle\geq\ \min_{b\in B(s)}\langle
p(s,\sigma_{i+1}(s),b),{\mathtt{val}_{i}}\rangle-i\cdot\frac{\varepsilon_{2}}{n}$
induction hypothesis $\displaystyle\geq\
{\mathtt{val}_{i+1}(s)}-\frac{\varepsilon_{2}}{n}-i\cdot\frac{\varepsilon_{2}}{n}$
$\displaystyle\text{definition of }\sigma_{i+1}(s)\,,$

proving (3).

Now in every state except $\top$, make each Min action leak
$\frac{\varepsilon_{3}}{n}$. Further, remove any Max actions that $\sigma_{n}$
never takes. Call the resulting game ${\mathcal{G}}^{-}$. Then Max’s action
sets in ${\mathcal{G}}^{-}$ are finite and we have for all $s_{0}\in S$ and
all Min strategies $\pi$

$\displaystyle{\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma_{n},\pi}(\mathtt{Avoid}(\bot))$
$\displaystyle\geq\
{\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma_{n},\pi}(\mathtt{Reach}_{n}(\top))$
$\displaystyle\mathtt{Avoid}(\bot)\supseteq\mathtt{Reach}_{n}(\top)$
$\displaystyle\geq\
{\mathcal{P}}_{{\mathcal{G}},s,\sigma_{n},\pi}(\mathtt{Reach}_{n}(\top))-\varepsilon_{3}$
at most $n\cdot\frac{\varepsilon_{3}}{n}$ leaks in $n$ steps
$\displaystyle\geq\ {\mathtt{val}_{n}(s)}-\varepsilon_{2}-\varepsilon_{3}$ by
(3) $\displaystyle\geq\
{\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(\top)}(s)}-\varepsilon_{1}-\varepsilon_{2}-\varepsilon_{3}$
choice of $n$ $\displaystyle=\
{\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(\top)}(s)}-\varepsilon$ choice of
$\varepsilon_{1},\varepsilon_{2},\varepsilon_{3}$.

Thus, for all $s\in S_{0}$

${\mathtt{val}_{{\mathcal{G}}^{-},\mathtt{Avoid}(\bot)}(s)}\ \geq\
{\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(\top)}(s)}-\varepsilon\,.$ (4)

Due to the leaks, in ${\mathcal{G}}^{-}$ the events $\mathtt{Reach}(\top)$ and
$\mathtt{Avoid}(\bot)$ coincide up to measure zero for all Max and all Min
strategies. Since Max’s action sets in ${\mathcal{G}}^{-}$ are finite, by
Proposition 1 Max has a memoryless strategy $\sigma$ that is optimal for
$\mathtt{Avoid}(\bot)$ from every state. Thus, for all $s\in S_{0}$ and all
Min strategies $\pi$

$\displaystyle{\mathcal{P}}_{{\mathcal{G}},s,\sigma,\pi}(\mathtt{Reach}(\top))\
$ $\displaystyle\geq\
{\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma,\pi}(\mathtt{Reach}(\top))$
$\displaystyle=\
{\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma,\pi}(\mathtt{Avoid}(\bot))$ as
argued above $\displaystyle\geq\
{\mathtt{val}_{{\mathcal{G}}^{-},\mathtt{Avoid}(\bot)}(s)}$ $\sigma$ is
optimal $\displaystyle\geq\
{\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(\top)}(s)}-\varepsilon$ by (4).

That is, the memoryless strategy $\sigma$ is $\varepsilon$-optimal from all
$s\in S_{0}$, and for each $s\in S$ the support of $\sigma(s)$ is finite. ∎

##  6 Optimal Reachability

In this section we show the following result, a generalization of Bordais et
al. [4, Theorem 28], via a different proof.

###### Theorem 6.1

Suppose that $S$ and Min’s action sets are finite. Then for every
$\varepsilon>0$ Max has a memoryless strategy $\sigma$ that is
$\varepsilon$-optimal for $\mathtt{Reach}(\top)$ from all states and optimal
from all states from which Max has any optimal strategy.

transition | $s_{1}$ | $\bot$
---|---|---
function $p$
$p(s_{0},a,b_{q})$ | $q\;$ | $\;1-q$

$s_{0}$$s_{1}$$\top$$\bot$$r$$t$$r$$w$$h$$t$$h$$w$$a$$b_{q}$$:q$$a$$b_{q}$$:1-q$

Figure 3: A game where Max has no _memoryless_ optimal strategy for
$\mathtt{Reach}(\top)$. The states $\top$ and $\bot$ are sink states. Min’s
action set at $s_{0}$ is $\\{b_{q}\mid q\in(\frac{1}{2},1)\cap\mathbb{Q}\\}$,
while Max has a single action $a$ at $s_{0}$. The game in dashed box is the
snowball game from Figure 2.

The assumption that Min’s action sets are finite cannot be dropped, as the
following example shows.

###### Example 3

Consider the game depicted in Figure 3, wherein state $s_{1}$ is the start
state of the snowball game from Example 2. Recall that
${\mathtt{val}_{\mathtt{Reach}(\top)}(s_{1})}=1$, but Max does not have an
optimal strategy from $s_{1}$. By this, and the fact that Min can choose
$b_{q}$ for $q$ arbitrary close to $\frac{1}{2}$, we deduce that
${\mathtt{val}_{\mathtt{Reach}(\top)}(s_{0})}=\frac{1}{2}$. Observe that when
taking action $b_{q}$ at $s_{0}$, Min is increasing the value from
$\frac{1}{2}$ to $q>\frac{1}{2}$. Indeed, we claim that Max has an optimal
strategy from $s_{0}$. If Max observes which action $b_{q}$ Min takes in
$s_{0}$, and plays a $(q-\frac{1}{2})$-optimal strategy from $s_{1}$, the
probability of reaching $\top$ will be at least $q\cdot(1-(q-\frac{1}{2}))\geq
q-(q-\frac{1}{2})=\frac{1}{2}$. But Max has to “remember” Min’s value increase
in order to play sufficiently well in $s_{1}$. So Max does not have a
memoryless optimal strategy from $s_{0}$. In fact, a step counter (discrete
clock) would not help Max either, since the step counter value does not
contain any information about $q$. ∎

Figure 4: A finitely-branching turn-based reachability game ${\mathcal{G}}$
with initial state $u_{1}$, where optimal Max strategies cannot be memoryless
(and cannot even be Markov). For clarity, we have drawn several copies of the
target state $t$. The number $y_{i}$ is defined as
$\frac{1}{2}-\frac{1}{2^{i+1}}$.

The assumption that $S$ is finite cannot be dropped either, not even for the
subclass of turn-based games, as the following example shows.

###### Example 4

Consider the finitely-branching turn-based reachability game depicted in
Figure 4 (from [13, Section 9]). The initial state is $u_{1}$, states $u_{i}$
are Min-controlled, states $s_{i}$ are Max-controlled and $t$ is the target
state.

At every state $u_{i}$, Min can either go right (red transition) or go up. At
every state $s_{i}$, Max can either go right (red transition) or go down. It
is easy to show that
${\mathtt{val}_{{\mathcal{G}}}(s_{i})}>{\mathtt{val}_{{\mathcal{G}}}(u_{i})}$
for all $i$. Thus the only locally optimal Min move is to go right. Similarly,
${\mathtt{val}_{{\mathcal{G}}}(s_{i})}>y_{i}$, and thus the only locally
optimal Max move is to go right.

Max has an optimal strategy from $u_{1}$ (and also from every other state) as
follows. First, always go right. If Min ever goes up at some $u_{i}$ then go
down at $s_{i}$. Intuitively, by going up, Min increases the value (i.e.,
gives a “gift” to Max). By going down at $s_{i}$, Max plays sub-optimally
locally, but realizes most of the value of $s_{i}$, i.e., loses less than
Min’s previous gift.

However, no memoryless strategy (and not even any Markov strategy, i.e., any
strategy that uses only a step counter) can be optimal for Max from $u_{1}$.
First, a step counter gives no advantage to Max, since in this example the
step counter is implicit in the current state anyway. For any memoryless Max
strategy, there are to cases. Either this strategy never goes down with any
positive probability at any state $s_{i}$. Then Min can avoid the target $t$
completely by always playing up, and thus this Max strategy is not optimal.
Otherwise, let $s_{j}$ be first state where Max goes down with some positive
probability. This Max strategy is not optimal either, since Min can always go
right (locally optimal), and Max’s choice at $s_{j}$ is locally sub-optimal.

See [13, Section 9] for a formal proof of this example. It is also shown there
that, in every countably infinite finitely-branching turn-based reachability
game, optimal Max strategies (if they exist at all) can be chosen as
deterministic and using a step counter plus 1 bit of public memory. So the
example above is tight. ∎

Now we prove Theorem 6.1. Let $S$ and Min’s action sets be finite. We
partition the finite state space $S$ into $S_{0},S_{1}$ so that $S_{0}$
contains exactly the states from which Max has an optimal strategy for
$\mathtt{Reach}(\top)$, and $S_{1}$ contains exactly the states from which Max
does not have an optimal strategy. Clearly, $\top,\bot\in S_{0}$.

By the finiteness of Min’s action sets and (1), for every value-$0$ state $s$
and every mixed Max action $\alpha\in\mathcal{D}(A(s))$ Min has an action $b$
that keeps the game (surely) in a value-$0$ state. Therefore, an optimal Max
strategy cannot rely on Min “gifts” in value-$0$ states. Hence, we can assume
without loss of generality that $\bot$ is the only value-$0$ state. We write
$S_{0}^{+}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}S_{0}\setminus\\{\bot\\}$,
so that all states in $S_{0}^{+}$ have a positive value.

The challenge is that the play can “cross over” between $S_{0}$ and $S_{1}$.
Our approach is as follows. First we fix a memoryless strategy $\sigma_{0}$ on
$S_{0}$ that is optimal for Max as long as Min responds optimally. Then,
building on the idea of the previous section, we add “leaks” to the game so
that

  * •

in $S_{0}$ the leaks do not decrease the value and Max still has an optimal
strategy;

  * •

in $S_{1}$ the leaks decrease the value only by little.

After having fixed $\sigma_{0}$ on $S_{0}$ and introduced suitable leaks, an
optimal safety strategy for $\mathtt{Avoid}(\bot)$ will serve as the
memoryless strategy $\sigma$ claimed in Theorem 6.1. This strategy extends
$\sigma_{0}$ to the whole state space and is optimal from $S_{0}$ (no matter
what Min does).

Below, to avoid clutter whenever we write ${\mathtt{val}(s)}$ we mean
${\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(\top)}(s)}$ where ${\mathcal{G}}$
is the original game, even when other auxiliary games are discussed.

We start by defining a memoryless strategy, $\sigma_{0}$, only on $S_{0}$ so
that $\sigma_{0}$ is optimal from $S_{0}$ as long as Min “does not increase
the value”.

For a state $s\in S_{0}$, call a mixed Max action $\alpha\in\mathcal{D}(A(s))$
_optimality-preserving_ if for all Min actions $b\in B(s)$ we have $\langle
p(s,\alpha,b),{\mathtt{val}}\rangle\geq{\mathtt{val}(s)}$ and if $\langle
p(s,\alpha,b),{\mathtt{val}}\rangle={\mathtt{val}(s)}$ then the support of
$p(s,\alpha,b)$ is a subset of $S_{0}$. Note that every optimal Max strategy
from $S_{0}$ is optimality-preserving at least in the first step. Therefore,
every state in $S_{0}$ has an optimality-preserving mixed Max action.

For a state $s\in S_{0}$ and an optimality-preserving mixed action $\alpha$,
call a Min action $b\in B(s)$ _value-preserving_ if $\langle
p(s,\alpha,b),{\mathtt{val}}\rangle={\mathtt{val}(s)}$ and _value-increasing_
otherwise (i.e., $\langle
p(s,\alpha,b),{\mathtt{val}}\rangle>{\mathtt{val}(s)})$.

We define inductively a non-decreasing sequence $R(0),R(1),R(2),\ldots$ of
subsets of $S_{0}$. Define
$R(0)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\top\\}$. For every
$n\geq 0$, define $R(n+1)$ as $R(n)$ union the set of those states $s\in
S_{0}$ from which Max has an optimality-preserving mixed action, say
$\alpha_{s}$, and a number $\delta_{s}>0$ such that for all value-preserving
Min actions $b\in B(s)$ we have $p(s,\alpha_{s},b)(R(n))\geq\delta_{s}$. We
note in passing that the existence of $\delta_{s}>0$ is guaranteed due to
finiteness of Min’s action set. Informally speaking, $R(n+1)$ consists of
those states that are already in $R(n)$ or have an optimality-preserving mixed
action $\alpha_{s}$ so that in the next step $R(n)$ is entered with a positive
probability unless Min takes a value-increasing action. Defining
$R\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}R(|S|-1)$, since $S$ is
finite we have $R=R(|S|-1)=R(|S|)=R(|S|+1)=\ldots$. Moreover, we can define
$\delta\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\min_{s\in
R}\delta_{s}>0$.

###### Lemma 4

We have $R=S_{0}^{+}$.

###### Proof

By an easy induction, $\bot\not\in R$. Hence $R\subseteq S_{0}^{+}$. Towards
the reverse inclusion, suppose there is $s\in S_{0}\setminus R$. It suffices
to show that $s=\bot$. Let $\sigma$ be an arbitrary optimal Max strategy
starting from $s$. Note that $\sigma(s)$ is optimality-preserving. Since
$s\not\in R=R(|S|)$, there is a value-preserving Min action $b\in B(s)$ such
that the support of $p(s,\sigma(s),b)$ does not overlap with $R(|S|-1)=R$.
That is, the support of $p(s,\sigma(s),b)$ is a subset of $S_{0}\setminus R$
and, thus, does not contain $\top$. Since $\sigma$ is optimal, $\sigma$ has to
play optimally—and, thus, has to use optimality-preserving mixed actions—as
long as Min has taken only value-preserving actions. Then it follows
inductively that there is a deterministic Min strategy (playing $b$ in the
very first step) that keeps the play in $S_{0}\setminus R$ forever. In
particular, $\top$ is not reached. Since the optimal strategy $\sigma$ was
arbitrary, we have ${\mathtt{val}(s)}=0$; i.e., $s=\bot$. ∎

Define $\sigma_{0}$ to be the memoryless Max strategy on $S_{0}$ with
$\sigma_{0}(s)=\alpha_{s}$ for all $s\in S_{0}$, where $\alpha_{s}$ is from
the definition of $R(n)$. For $s\in S_{0}$, call $b\in B(s)$ _value-
preserving_ (or _value-increasing_) if $b$ is value-preserving (or value-
increasing, respectively) for $s$ and $\sigma_{0}(s)$.

###### Lemma 5

For any Max strategy that plays $\sigma_{0}$ on $S_{0}$ and any Min strategy,
almost all plays that eventually remain in $S_{0}^{+}$ and eventually contain
only value-preserving Min actions reach $\top$.

###### Proof

Let $\sigma$ be a Max strategy that plays $\sigma_{0}$ on $S_{0}$, and let
$\pi$ be a Min strategy. Since the set of (finite) histories is countable, it
suffices to consider the set of plays which always remain in $S_{0}^{+}$ and
contain only value-preserving Min actions. Let $s\in S_{0}^{+}$. By Lemma 4,
we have $s\in R$. Let $n\leq|S|-1$ be the smallest $n$ with $s\in R(n)$. We
have $p(s,\sigma_{0}(s),b)(R(n-1))\geq\delta$ for all value-preserving Min
actions $b$. It follows that at any time the probability that in at most
$|S|-1$ steps $R(0)=\\{\top\\}$ is reached is at least $\delta^{|S|-1}>0$.
Thus, almost surely $\top$ is eventually reached. ∎

Since $S_{0}$ and Min’s action sets are finite, we can choose an
$\varepsilon>0$ small enough so that for all $s\in S_{0}$ and all value-
increasing Min actions $b$ we have

$\langle
p(s,\sigma_{0}(s),b),{\mathtt{val}}\rangle\geq{\mathtt{val}(s)}+2\varepsilon$
(5)

So any value increase by a Min action is at least $2\varepsilon$.

Define a game ${\mathcal{G}}_{1}$ with state space $S_{1}\cup\\{\top,\bot\\}$.
Its transition function $p_{1}$ is obtained from $p$ by redirecting
probability mass away from $S_{0}\setminus\\{\top,\bot\\}$ as follows. Each
transition to a state $s\in S_{0}\setminus\\{\top,\bot\\}$ is redirected to
$\top$ with probability ${\mathtt{val}(s)}$ and to $\bot$ with probability
$1-{\mathtt{val}(s)}$. Then the value of each state in ${\mathcal{G}}_{1}$ is
equal to its value in ${\mathcal{G}}$.

As in the proof of Proposition 2 we obtain from ${\mathcal{G}}_{1}$ a “leaky”
version, ${\mathcal{G}}_{1}^{-}$, with transition function $p_{1}^{-}$, such
that Max’s action sets are finite and, defining
$v(s)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathtt{val}_{{\mathcal{G}}_{1}^{-},\mathtt{Avoid}(\bot)}(s)}$
for all $s\in S_{1}\cup\\{\top,\bot\\}$, we have

$v(s)\ \geq\ {\mathtt{val}(s)}-\varepsilon\qquad\text{for all }s\in S_{1}.$
(6)

By Proposition 1 Max has a memoryless optimal (for safety) strategy
$\sigma_{1}$ in ${\mathcal{G}}_{1}^{-}$. Thus, for all $s\in S_{1}$ and all
$b\in B(s)$, as in Equation 2, we have

$\langle p_{1}^{-}(s,\sigma_{1}(s),b),v\rangle\ \geq\ v(s)\,.$

Next we define a “leaky” version, ${\mathcal{G}}^{-}$, of the whole game
${\mathcal{G}}$ with the whole state space $S$ and a transition function
$p^{-}$. On $S_{1}$, function $p^{-}$ is defined similarly to $p_{1}^{-}$,
except that the probability mass that was directed away from
$S_{0}\setminus\\{\top,\bot\\}$ in the definition of ${\mathcal{G}}_{1}$ is
now not directed away and instead enters $S_{0}$ as originally. However, the
leaks in every transition from $S_{1}$ are also present in $p^{-}$. Extend the
function $v$ to the whole state space $S$ by defining
$v(s)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathtt{val}(s)}$ for
all $s\in S_{0}$. Then, for all $s\in S_{1}$ and all $b\in B(s)$

$\langle p^{-}(s,\sigma_{1}(s),b),v\rangle\ =\ \langle
p_{1}^{-}(s,\sigma_{1}(s),b),v\rangle\ \geq\ v(s)\,.$

On $S_{0}$, the transition function $p^{-}$ is obtained from $p$ by making
value-increasing Min actions leak $\varepsilon$, in the sense defined in
Section 5. For all $s\in S_{0}$ and all value-increasing Min actions $b\in
B(s)$

$\displaystyle\langle p^{-}(s,\sigma_{0}(s),b),v\rangle$ $\displaystyle\geq\
\langle p^{-}(s,\sigma_{0}(s),b),{\mathtt{val}}\rangle-\varepsilon$ by (6) and
the definition of $v$ on $S_{0}$ $\displaystyle\geq\ \langle
p(s,\sigma_{0}(s),b),{\mathtt{val}}\rangle-\varepsilon-\varepsilon$ from the
definition of $p^{-}$ $\displaystyle\geq\
{\mathtt{val}(s)}+2\varepsilon-\varepsilon-\varepsilon$ $\displaystyle\text{by
}\eqref{eq:cond-2ep}$ $\displaystyle=\ v(s)$ definition of $v$ on $S_{0}$.

For all $s\in S_{0}$ and all value-preserving Min actions $b\in B(s)$

$\displaystyle\langle p^{-}(s,\sigma_{0}(s),b),v\rangle$ $\displaystyle=\
\langle p(s,\sigma_{0}(s),b),v\rangle$ from the definition of $p^{-}$
$\displaystyle=\ \langle p(s,\sigma_{0}(s),b),{\mathtt{val}}\rangle$ support
of $p(s,\sigma_{0}(s),b)$ is a subset of $S_{0}$ $\displaystyle=\
{\mathtt{val}(s)}$ $b$ is value-preserving $\displaystyle=\ v(s)$ definition
of $v$ on $S_{0}$.

Define the memoryless strategy $\sigma$ by naturally combining $\sigma_{0}$
and $\sigma_{1}$. We have shown above that for all $s\in S$ and all $b\in
B(s)$ we have $\langle p^{-}(s,\sigma(s),b),v\rangle\geq v(s)$. From applying
Lemma 1 we conclude that for all $s\in S$ and all Min strategies $\pi$ we have

${\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma,\pi}(\mathtt{Avoid}(\bot))\ \geq\
v(s)\,.$

In ${\mathcal{G}}^{-}$, due to the leaks, almost all $\bot$-avoiding plays
eventually remain in $S_{0}^{+}$ and eventually have only value-preserving Min
actions. But by Lemma 5, almost all of these plays reach $\top$. Thus, we have
for all $s\in S$ and all Min strategies $\pi$

${\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma,\pi}(\mathtt{Reach}(\top))\ =\
{\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma,\pi}(\mathtt{Avoid}(\bot))\ \geq\
v(s)\,,$

which, by definition, equals ${\mathtt{val}(s)}$ if $s\in S_{0}$ and, by (6),
is at least ${\mathtt{val}(s)}-\varepsilon$ if $s\in S_{1}$. Since
${\mathcal{P}}_{{\mathcal{G}},s,\sigma,\pi}(\mathtt{Reach}(\top))\geq{\mathcal{P}}_{{\mathcal{G}}^{-},s,\sigma,\pi}(\mathtt{Reach}(\top))$,
this completes the proof of Theorem 6.1.

##  7 Conclusion and Related Work

We have shown that, in finite reachability games with finite action sets for
Min, optimal Max strategies, where they exist, can be chosen as memoryless
randomized. However, this does not carry over to countably infinite
reachability games.

Intuitively, the reason for this is that Min can play sub-optimally and give
“gifts” to Max that increase the expected value of the current state, but
delay progress towards the target. In countably infinite reachability games,
Min might give infinitely many smaller and smaller gifts and delay progress
indefinitely, unless Max uses memory to keep track of these gifts in order to
react correctly.

Finite reachability games are simpler, because gifts from Min to Max are
universally lower bounded in size, due to the finite state space and the
finiteness of Min’s action sets. Therefore, Min cannot give infinitely many
gifts to Max, except in a nullset of the plays. Without such distracting
gifts, Max can make steady progress towards the target. Moreover, if Min does
give a gift once, then Max does not need to remember how large it was, since
it is universally lower bounded.

The existence of optimal strategies is also affected by the size of the state
space. While finite turn-based reachability games always admit optimal Max
strategies [7], even in countably infinite MDPs, optimal Max strategies for
reachability need not exist. However, it was shown by Ornstein [20, Thm. B]
that $\varepsilon$-optimal Max strategies for reachability in countably
infinite MDPs can be chosen as memoryless and deterministic. These strategies
can even be made uniform, i.e., independent of the start state. Moreover, if
an optimal strategy does exist for Max in a countable MDP, then there also
exists one that is memoryless and deterministic [20, Prop. B].

These results on countable MDPs do not carry over to countable 2-player
stochastic reachability games. While Max always has $\varepsilon$-optimal
randomized memoryless strategies in countable concurrent reachability games
with finite action sets [21, Corollary 3.9], these strategies depend on the
start state and cannot be made uniform [19]. This non-uniformity even holds
for the subclass of countable finitely branching turn-based reachability games
[13]. However, uniformity can be regained with $1$ bit of public memory, i.e.,
there exist uniformly $\varepsilon$-optimal Max strategies in countable
concurrent reachability games with finite action sets that are deterministic
and use just $1$ bit of public memory [13]. Optimal Max strategies in
countable turn-based finitely branching reachability games, where they exist,
can be chosen to use just a step counter and $1$ bit of public memory (but not
just a step counter or just finite memory). On the other hand, in concurrent
games with finite action sets, a step counter plus finite private memory does
not suffice for optimal Max strategies in general [13].

If Min is allowed infinite action sets (resp. infinite branching) in countably
infinite reachability games, then Max generally needs infinite memory for
$\varepsilon$-optimal, optimal and almost surely winning strategies. There
exists a turn-based countable reachability game with infinite Min branching
(and finite Max branching), such that every state admits an almost surely
winning strategy for Max, and yet every Max strategy that uses only a step
counter plus finite private memory is still useless (in the sense that Min can
make its attainment arbitrarily close to zero) [13].

## References

  * [1] de Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. In: Annual Symposium on Foundations of Computer Science (FOCS). pp. 564–575. IEEE Computer Society (1998). https://doi.org/10.1109/SFCS.1998.743507
  * [2] Bertrand, N., Genest, B., Gimbert, H.: Qualitative determinacy and decidability of stochastic games with signals. Journal of the ACM 64(5), 33:1–33:48 (2017), https://doi.org/10.1145/3107926
  * [3] Billingsley, P.: Probability and Measure. Wiley, New York, NY (1995), third edition
  * [4] Bordais, B., Bouyer, P., Le Roux, S.: Optimal strategies in concurrent reachability games. In: Computer Science Logic (CSL). LIPIcs, vol. 216, pp. 7:1–7:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.CSL.2022.7
  * [5] Bouyer, P., Markey, N., Randour, M., Sangnier, A., Stan, D.: Reachability in Networks of Register Protocols under Stochastic Schedulers. In: International Colloquium on Automata, Languages and Programming (ICALP). vol. 55, pp. 106:1–106:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). https://doi.org/10.4230/LIPIcs.ICALP.2016.106
  * [6] Chen, T., Forejt, V., Kwiatkowska, M., Parker, D., Simaitis, A.: Prism-games: A model checker for stochastic multi-player games. In: Tools and Algorithms for the Construction and Analysis of Systems (TACAS). pp. 185–191. Springer (2013). https://doi.org/10.1007/978-3-642-36742-7_13
  * [7] Condon, A.: The complexity of stochastic games. Information and Computation 96(2), 203–224 (1992). https://doi.org/10.1016/0890-5401(92)90048-K
  * [8] De Alfaro, L., Henzinger, T.A., Kupferman, O.: Concurrent reachability games. Theor. Comput. Sci. 386(3), 188–217 (2007). https://doi.org/10.1016/j.tcs.2007.07.008
  * [9] Everett, H.: Recursive games. In: Contributions to the Theory of Games, Volume III, Annals of Mathematics Studies, vol. 39, pp. 47–78. Princeton University Press, Princeton, N.J. (1957). https://doi.org/10.1515/9781400882151-004
  * [10] Flesch, J., Predtetchinski, A., Sudderth, W.: Positive zero-sum stochastic games with countable state and action spaces. Applied Mathematics and Optimization 82, 499–516 (2020). https://doi.org/10.1007/s00245-018-9536-3
  * [11] Gillette, D.: Stochastic games with zero stop probabilities. In: Contributions to the Theory of Games (AM-39), Volume III, pp. 179–188. Princeton University Press (dec 1958). https://doi.org/10.1515/9781400882151-011
  * [12] Gimbert, H., Horn, F.: Solving simple stochastic tail games. In: Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 847–862 (2010). https://doi.org/10.1137/1.9781611973075
  * [13] Kiefer, S., Mayr, R., Shirmohammadi, M., Totzke, P.: Strategy complexity of reachability in countable stochastic 2-player games. Dynamic Games and Applications (2023), https://arxiv.org/abs/2203.12024, to appear
  * [14] Kiefer, S., Mayr, R., Shirmohammadi, M., Wojtczak, D.: On strong determinacy of countable stochastic games. In: ACM/IEEE Symposium on Logic in Computer Science (LICS). pp. 1–12. IEEE Computer Society (2017). https://doi.org/10.1109/LICS.2017.8005134
  * [15] Kiefer, S., Mayr, R., Shirmohammadi, M., Wojtczak, D.: Parity Objectives in Countable MDPs. In: ACM/IEEE Symposium on Logic in Computer Science (LICS) (2017). https://doi.org/10.1109/LICS.2017.8005100
  * [16] Kumar, P.R., Shiau, T.H.: Existence of value and randomized strategies in zero-sum discrete-time stochastic dynamic games. SIAM Journal on Control and Optimization 19(5), 617–634 (1981). https://doi.org/10.1137/0319039
  * [17] Kučera, A.: Turn-based stochastic games. In: Apt, K.R., Grädel, E. (eds.) Lectures in Game Theory for Computer Scientists, pp. 146–184. Cambridge University Press (2011). https://doi.org/10.1017/CBO9780511973468.006
  * [18] Maitra, A., Sudderth, W.: Finitely additive stochastic games with Borel measurable payoffs. International Journal of Game Theory 27(2), 257–267 (July 1998). https://doi.org/10.1007/s001820050071
  * [19] Nowak, A., Raghavan, T.: Positive stochastic games and a theorem of Ornstein. In: Stochastic Games And Related Topics, Theory and Decision Library (Game Theory, Mathematical Programming and Operations Research), vol. 7. Springer (1991). https://doi.org/10.1007/978-94-011-3760-7_11
  * [20] Ornstein, D.: On the existence of stationary optimal strategies. Proceedings of the American Mathematical Society 20(2), 563–569 (1969). https://doi.org/10.2307/2035700
  * [21] Secchi, P.: Stationary strategies for recursive games. Math. Oper. Res. 22(2), 494–512 (1997). https://doi.org/10.1287/moor.22.2.494
  * [22] Shapley, L.S.: Stochastic games. Proceedings of the National Academy of Sciences 39(10), 1095–1100 (1953). https://doi.org/10.1073/pnas.39.10.1095