1

# Strategy Complexity of Reachability in Countable Stochastic 2-Player Games

Stefan Kiefer  Department of Computer ScienceUniversity of OxfordUK ,  Richard
Mayr  School of InformaticsUniversity of EdinburghUK ,  Mahsa Shirmohammadi
IRIF & CNRSUniversité Paris citéFrance and  Patrick Totzke  Department of
Computer ScienceUniversity of LiverpoolUK

(March 2022)

###### Abstract.

We study countably infinite stochastic 2-player games with reachability
objectives. Our results provide a complete picture of the memory requirements
of $\varepsilon$-optimal (resp. optimal) strategies. These results depend on
whether the game graph is infinitely branching and on whether one requires
strategies that are uniform (i.e., independent of the start state).

Our main result is that $\varepsilon$-optimal (resp. optimal) Maximizer
strategies in infinitely branching turn-based reachability games require
infinite memory. This holds even under very strong restrictions. Even if all
states have an almost surely winning Maximizer strategy, strategies with a
step counter plus finite private memory are still useless.

Regarding _uniformity_ , we show that for Maximizer there need not exist
positional uniformly $\varepsilon$-optimal strategies even in finitely
branching turn-based games, whereas there always exists one that uses one bit
of public memory, even in concurrent games with finite action sets.

Stochastic Games, Countable Systems, Reachability, Uniform Strategies, Memory,
Strategy Complexity

††copyright: none††conference: Preprint; 2022††journalyear: ;††ccs: Theory of
computation Random walks and Markov chains††ccs: Mathematics of computing
Probability and statistics

##  1\. Introduction

### Background.

Stochastic 2-player games, first introduced by Shapley in his seminal 1953
work (Shapley, 1953), model dynamic interactions in which the environment
responds randomly to players’ actions. Shapley’s games were generalized by
Gillette (Gillette, 1958) and Kumar and Shiau (Kumar and Shiau, 1981) to allow
infinite state and action sets and non-termination. They play a central role
in the solution of many problems in economics (Sorin, 1992; Nowak, 2005;
Jaskiewicz and Nowak, 2011; Solan and Vieille, 2015; Bacharach, 2019),
evolutionary biology (Raghaven et al., 2012), and computer science (de Alfaro
and Henzinger, 2001; Neyman and Sorin, 2003; Altman et al., 2005, 2007; Solan
and Vieille, 2015; Svoreňová and Kwiatkowska, 2016; Bouyer et al., 2016) among
others.

In general concurrent games, in each state both players independently choose
an action and the next state is determined according to a pre-defined
distribution that depends on 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 games were
studied first in the sequence of works (Filar, 1980, 1981; Vrieze et al.,
1983; Vrieze, 1987; Condon, 1992), but have recently received much attention
by computer scientists (Gimbert and Horn, 2010; Chen et al., 2013; Bouyer et
al., 2016; Kiefer et al., 2017a; Bertrand et al., 2017). An even more special
case of stochastic games are _Markov Decision Processes (MDPs)_ : MDPs are
turn-based games where all controlled states are Maximizer states. Since
Minimizer is passive, they are also called games against nature.

A strategy for a player is a function that, given a history of a play,
determines the next action of the player. Objectives are defined via functions
that assign numerical rewards to plays, and the Maximizer (resp. Minimizer)
aim to maximize (resp. minimize) the expected reward. A central result in
zero-sum 2-player stochastic games with finite action sets is the existence of
a _value_ for the large class of Borel measurable objectives (Martin, 1998;
Maitra and Sudderth, 1998) (i.e., that $\sup_{\it Max}\inf_{\it Min}={\it
value}=\inf_{\it Min}\sup_{\it Max}$ over Maximizer/Minimizer strategies). In
particular, this implies the existence of $\varepsilon$-optimal strategies for
every $\varepsilon>0$ and either player, i.e., strategies that enforce that
the outcome of a game is $\varepsilon$-close to its value, regardless of the
behavior of the other player. Optimal strategies ($\varepsilon$-optimal for
$\varepsilon=0$) need not exist in general, but their properties can be
studied in those cases where they do exist, e.g., (Puterman, 1994; Kučera,
2011; Kiefer et al., 2017b, 2020a).

The nature of good ($\varepsilon$-optimal, resp. optimal) strategies in
stochastic games and their memory requirements is relevant to computer
scientists (Brázdil et al., 2014; Kiefer et al., 2017a, 2020a), in particular,
in the sense of computability (Kučera, 2011); and it is also a central notion
for mathematicians (Aumann, 1981; Kalai, 1990; Maitra and Sudderth, 2007;
Laraki et al., 2013; Flesch et al., 2018; Flesch et al., 2021) and economists
(Nowak, 2005; Bacharach, 2019).

The simplest type of strategy is _memoryless deterministic (MD)_ : for each
state $s$ it defines a single action that the player always chooses when the
game is in $s$. A slightly more general strategy is _memoryless randomized
(MR)_ , also known as _positional_ : for each state $s$ it defines a fixed
probability distribution over the player’s actions from which he always
samples when the game is in $s$. More complex strategies might use some finite
memory. The strategy chooses an action depending only on the current state and
the current memory mode. The memory mode can be updated in every step
according to the current state, the action being taken, and the next state. In
general, for strategies that are not deterministic but use randomization, this
memory update may also be randomized. Therefore, in the case of games, a
player does not necessarily know for sure the current memory mode of the other
player. It may be advantageous for a player to keep his memory mode hidden
from the other player. Thus one distinguishes between public memory and
private memory. A step counter is a discrete clock that is incremented after
every round of the game. Since this happens deterministically, it is always
public. Strategies that use only a step counter are also called _Markov
strategies_. Combinations of the above are possible, e.g., a strategy that
uses a step counter and an additional finite public/private general purpose
memory. The amount/type of memory and randomization required for a good
strategy for a given objective is also called its _strategy complexity_.

### The reachability objective.

With a reachability objective, a play is defined as winning for Maximizer iff
it visits a defined target state (or a set of target states) at least once.
Thus Maximizer aims to maximize the probability that the target is reached.
Dually, Minimizer aims to minimize the probability of reaching the target. So,
from Minimizer’s point of view, this is the dual _safety objective_ of
avoiding the target.

Reachability is arguably the simplest objective in games on graphs. It can
trivially be encoded into the usual reward-based objectives, i.e., every play
that reaches the target gets reward $1$ and all other plays get reward $0$.
Moreover, it can be encoded into many other objectives, by using the following
intuition: “First you need to reach the target, and only then can you satisfy
the other objective.” E.g., this works for Büchi, Parity and average-payoff
objectives.

Despite their apparent simplicity, reachability games are not trivial. While
both players have optimal MD strategies in finite-state turn-based
reachability games (Condon, 1992) (see also (Kučera, 2011, Proposition 5.6.c,
Proposition 5.7.c)), this does not carry over to finite-state concurrent
reachability games. A counterexample is the _Hide-or-Run_ game by Kumar and
Shiau (Kumar and Shiau, 1981; de Alfaro et al., 1998), where Maximizer has no
optimal strategy.

In countably infinite reachability games, Maximizer does not have any optimal
strategy even if the game is turn-based, in fact not even in countably
infinite finitely-branching MDPs (Kiefer et al., 2017c).

On the other hand, Ornstein (Ornstein, 1969) showed that Maximizer has
$\varepsilon$-optimal MD strategies in countably infinite MDPs. Better yet,
the MD strategies can be made uniform, i.e., independent of the start state.
This led to the question whether Ornstein’s results can be generalized from
MDPs to countably infinite stochastic games.

Secchi (Secchi, 1997, Corollary 3.9) proved the following.

###### Proposition 1.1.

Maximizer has $\varepsilon$-optimal positional (MR) strategies in countably
infinite concurrent reachability games with finite action sets.

However, these MR strategies are not uniform, i.e., they depend on the start
state. In fact, Nowak and Raghavan (Nowak and Raghavan, 1991) showed that
there cannot exist any uniformly $\varepsilon$-optimal positional Maximizer
strategies in countably infinite concurrent reachability games with finite
action sets. Their counterexample is called the _Big Match on $\mathbb{N}$_
(which, in turn, is inspired by the _Big Match_ (Gillette, 1958; Solan and
Vieille, 2015; D. and Ferguson, 1968; Hansen et al., 2018)).

However, several fundamental questions remained open:

Q1.:

Does the negative result of Nowak and Raghavan (Nowak and Raghavan, 1991)
still hold in the special case of countable _turn-based_ (finitely branching)
reachability games?

Q2.:

If uniformly $\varepsilon$-optimal Maximizer strategies cannot be positional,
do they exist at all, e.g., by using more memory, and if yes, how much memory
do they need?

Q3.:

Does the positive result of Secchi (Proposition 1.1) still hold if the
restriction to finite action sets is dropped? The question is meaningful,
since concurrent games where only one player has infinite action sets are
still determined (Flesch et al., 2020, Theorem 11) (though not if both players
have infinite action sets, unless one imposes other restrictions). Moreover,
what about infinitely branching turn-based reachability games? How much memory
do good Maximizer strategies need in these cases?

### Our contribution.

Our results, summarized in Tables 1 and 2, provide a comprehensive view on the
strategy complexity of (uniformly) $\varepsilon$-optimal strategies for
reachability (and also about optimal strategies when they exist).

Maximizer | countable | turn-based games | turn-based games | concurrent games
---|---|---|---|---
MDPs | finite-branching | infinite-branching | finite action sets
$\varepsilon$-optimal | MD | MD |  $\infty$-memory | MR
(Ornstein, 1969, Thm. B) |  (Kučera, 2011, Proposition 5.7.c), Lemma B.1 | Theorem 7.4 | (Secchi, 1997, Cor. 3.9)
uniform $\varepsilon$-optimal | MD | no MR, Theorem 4.2 |  $\infty$-memory | no MR (Nowak and Raghavan, 1991)
(Ornstein, 1969, Thm. B) | det. public 1-bit, Theorem 3.5 | Theorem 7.4 | rand. public 1-bit, Theorem 3.5
Optimal | MD | no FR |  $\infty$-memory |  $\infty$-memory
(Ornstein, 1969, Prop. B) | (Kučera, 2011, Prop. 5.7.b) | Theorem 7.4 | Proposition B.3
Almost surely winning | MD | MD |  $\infty$-memory | MR
(Ornstein, 1969, Prop. B) | (Kiefer et al., 2017a, Thm. 5.3) | Theorem 7.4 | Theorem 3.6
Table 1. The strategy complexity of Maximizer for the reachability objective. Since optimal (and a.s. winning) strategies do not exist in general, the results in the two bottom rows are conditioned upon their existence. “$\infty$-memory” means that even randomized strategies with a step counter plus an arbitrarily large finite private memory do not suffice. Deterministic strategies are useless in concurrent games, regardless of memory. Minimizer | turn-based games | turn-based games | concurrent games
---|---|---|---
finite-branching | infinite-branching | finite action sets
(uniform) $\varepsilon$-optimal |  | no FR, (Kiefer et al., 2017c, Theorem 3) |
MD, (Brázdil et al., 2011, Theorem 3.1) | det. Markov, Theorem D.2 | MR, (Nowak and Raghavan, 1991, Theorem 1)
Optimal | MD, (Brázdil et al., 2011, Theorem 3.1) |  $\infty$-memory, Proposition D.4 | MR, (Nowak and Raghavan, 1991, Theorem 1)
Table 2. The strategy complexity of Minimizer for the reachability objective.
Since optimal Minimizer strategies do not exist in general for infinitely
branching games (unlike in the other cases), the result of Proposition D.4 is
conditioned upon their existence. Deterministic strategies are useless in
concurrent games, regardless of memory.

Our first result strengthens the negative result of Nowak and Raghavan (Nowak
and Raghavan, 1991) to the turn-based case.

###### First Lower-Bound result (Q1) 0.

(Theorem 4.2) There exists a finitely branching turn-based version of the Big
Match on $\mathbb{N}$ where Maximizer still does not have any uniformly
$\varepsilon$-optimal MR strategy.

Our second result solves the open question about uniformly
$\varepsilon$-optimal Maximizer strategies. While uniformly
$\varepsilon$-optimal Maximizer strategies cannot be positional, $1$ bit of
memory is enough.

###### Main Upper-Bound result (Q2) 0.

(Theorem 3.5) In concurrent games with finite action sets and reachability
objective, for any $\varepsilon>0$, Maximizer has a uniformly
$\varepsilon$-optimal public-memory 1-bit strategy. This strategy can be
chosen as deterministic if the game is turn-based and finitely branching.

Our main contribution (Theorem 1.2) addresses Q3. It determines the strategy
complexity of Maximizer in infinitely branching reachability games. Our result
is a very strong lower bound, and we present the path towards it via a
sequence of (unfulfilled) hopes for an upper bound.

Hope 1.  In turn-based reachability games, Maximizer has $\varepsilon$-optimal
MD strategies.

This is motivated by the fact that the property holds if the game is finitely
branching ((Kučera, 2011, Proposition 5.7.c) and Lemma B.1) or if it is just
an MDP (Ornstein, 1969).

One might even have hoped for _uniformly_ $\varepsilon$-optimal MD strategies,
i.e., strategies that do not depend on the start state of the game, but this
hope was crushed by the answer to Q1.

Let us mention a concern about Hope 1 as stated (i.e., disregarding
uniformity). Consider any turn-based reachability game that is finitely
branching, and let $x\in[0,1]$ be the value of the game. The proof of
Proposition 1.1 actually shows that for every $\varepsilon>0$, Maximizer has
both a strategy and a time horizon $n\in\mathbb{N}$ such that for all
Minimizer strategies, the game visits the target state with probability at
least $x-\varepsilon$ _within the first $n$ steps_ of the game. There is no
hope that such a guarantee on the time horizon can be given in infinitely
branching games. Indeed, consider the infinitely many states
$f_{0},f_{1},f_{2},\ldots$, where $f_{0}$ is the target state and for $i>0$
state $f_{i}$ leads to $f_{i-1}$ regardless of the players’ actions, and an
additional Minimizer state, $u$, where Minimizer chooses, by her action, one
of the $f_{i}$ as successor state. In this game, starting from $u$, Maximizer
wins with probability $1$ (he is passive in this game). Minimizer cannot avoid
losing, but her strategy determines when $f_{0}$ is visited. This shows that a
proof of Hope 1 would require different methods.

In case Hope 1 turns out to be false, there are various plausible weaker
versions. Let us briefly discuss their motivation.

Hope 2.  Hope 1 is true if MD is replaced by MR.

This is motivated by Proposition 1.1, i.e., that in concurrent games with
finite action sets for both players, Maximizer has $\varepsilon$-optimal MR
but not MD strategies. In fact, (Flesch et al., 2020, Theorem 12.3) implies
that this holds even under the weaker assumption that just Minimizer has
finite action sets (while Maximizer is allowed infinite action sets).

Hope 3.  Hope 1 is true if Maximizer has an optimal strategy.

This is motivated by the fact that in MDPs with _Büchi_ objective (i.e., the
player tries to visit a set of target states infinitely often), if the player
has an optimal strategy, he also has an MD optimal strategy. The same is not
true for $\varepsilon$-optimal strategies (they require memory) (Kiefer et
al., 2017c). This example shows that although optimal strategies do not always
exist, if they do exist, they may be simpler.

Hope 4.  Hope 1 is true if Maximizer has an almost-surely winning strategy,
i.e., a strategy that guarantees him to visit the target state with
probability $1$.

This is weaker than Hope 1, because an almost-surely winning strategy is
necessarily optimal.

In a turn-based game, let us associate to each state $s$ its _value_ , which
is the value of the game when started in $s$. We call a controlled step $s\to
s^{\prime}$ _value-decreasing_ (resp., _value-increasing_), if the value of
$s^{\prime}$ is smaller (resp., larger) than the value of $s$. It is easy to
see that Maximizer cannot do value-increasing steps and Minimizer cannot do
value-decreasing steps, but the opposite is possible in general.

Hope 5.  Hope 1 is true if Maximizer does not have value-decreasing steps.

Hope 6.  Hope 1 is true if Minimizer does not have value-increasing steps.

Hopes 1 and 1 are motivated by the fact that sometimes the absence of
Maximizer value-decreasing steps or the absence of Minimizer value-increasing
steps implies the existence of optimal Maximizer strategies and then Hope 1
might apply. For example, in finitely branching turn-based reachability games,
the absence of Maximizer value-decreasing steps or the absence of Minimizer
value-increasing steps implies the existence of optimal Maximizer strategies,
and they can be chosen MD (Kiefer et al., 2017a, Theorem 5).

Hope 7.  Hope 1 is true for games with acyclic game graph.

This is motivated, e.g., by the fact that in _safety_ MDPs (where the only
active player tries to _avoid_ a particular state $f$) with acyclic game graph
and infinite action sets the player has $\varepsilon$-optimal MD strategies
(Kiefer et al., 2020a, Corollary 26). The same does not hold without the
acyclicity assumption (Kiefer et al., 2017c, Theorem 3).

Hope 8.  Hope 1 is true if Maximizer can additionally use a step counter to
choose his actions.

This is weaker than Hope 1, because by using a step counter Maximizer
effectively makes the game graph acyclic.

Hope 9.  In turn-based reachability games, Maximizer has $\varepsilon$-optimal
strategies that use only finite memory.

This is motivated, e.g., by the fact that in MDPs with acyclic game graph and
Büchi objective, the player has $\varepsilon$-optimal deterministic strategies
that require only 1 bit of memory, but no $\varepsilon$-optimal MR strategies
(Kiefer et al., 2019).

It might be advantageous for Maximizer to keep his memory mode private. This
motivates the following final weakening of Hope 1.

Hope 10.  In turn-based reachability games, Maximizer has
$\varepsilon$-optimal strategies that use only private finite memory.

The main contribution of this paper is to crush all these hopes. That is, Hope
1 is false, even if all weakenings proposed in Hopes 1-1 are imposed _at the
same time_. Specifically, we show:

###### Theorem 1.2.

There is a turn-based reachability game (necessarily, by Proposition 1.1, with
infinite action sets for Minimizer) with the following properties:

  1. (1)

for every Maximizer state, Maximizer has at most two actions to choose from;

  2. (2)

for every state Maximizer has a strategy to visit the target state with
probability $1$, regardless of Minimizer’s strategy;

  3. (3)

for every Maximizer strategy that uses only a step counter and private finite
memory and randomization, for every $\varepsilon>0$, Minimizer has a strategy
so that the target state is visited with probability at most $\varepsilon$.

This lower bound trivially carries over to concurrent stochastic games with
infinite Minimizer action sets, and for all Borel objectives that subsume
reachability, e.g., Büchi, co-Büchi, Parity, average-reward and total-reward.

##  2\. Preliminaries

A _probability distribution_ over a countable set $S$ is a function
$f:S\to[0,1]$ with $\sum_{s\in S}f(s)=1$. We write $\mathcal{D}(S)$ for the
set of all probability distributions over $S$.

We study perfect information 2-player stochastic games between two players
$\Box$ (Maximizer) and $\Diamond$ (Minimizer).

Concurrent stochastic games. 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 Maximizer and Minimizer,
respectively. 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. The set of _plays_ from an
initial state $s_{0}$ is given by the infinite sequences in $Z^{\omega}$ where
the first triple contains $s_{0}$. The game from $s_{0}$ is played in stages
$\mathbb{N}=\\{0,1,2,\dots\\}$. At every stage $t\in\mathbb{N}$, the play is
in some state $s_{t}$. Maximizer chooses an action $a_{t}\in A(s_{t})$ and
Minimizer chooses an action $b_{t}\in B(s_{t})$. The next state $s_{t+1}$ is
then chosen according to the distribution $p(s_{t},a_{t},b_{t})$. (Since we
just consider the reachability objective here, we don’t define a reward
function.)

Turn-based stochastic games. A special case of concurrent stochastic games are
turn-based games, where in each round either Maximizer or Minimizer has a
single action to play. Turn-based games
${\mathcal{G}}=(S,(S_{\Box},S_{\Diamond},S_{\ocircle}),{\longrightarrow},P)$
are defined such that the countable set of states $S$ is partitioned into the
set $S_{\Box}$ of states of player$~{}\Box$, the set $S_{\Diamond}$ of states
of player $\Diamond$ and _random states_ $S_{\ocircle}$. The relation
$\mathord{{\longrightarrow}}\subseteq S\times S$ is the transition relation.
We write $s{\longrightarrow}{}s^{\prime}$ if
$(s,s^{\prime})\in{\longrightarrow}$, and we assume that each state $s$ has a
_successor_ state $s^{\prime}$ with $s{\longrightarrow}s^{\prime}$. The
probability function $P:S_{\ocircle}\to\mathcal{D}(S)$ assigns to each random
state $s\in S_{\ocircle}$ a probability distribution over its successor
states.

The game ${\mathcal{G}}$ is called _finitely branching_ if each state has only
finitely many successors; otherwise, it is _infinitely branching_. A game is
_acyclic_ if the underlying graph $(S,{\longrightarrow})$ is acyclic. Let
$\odot\in\\{\Box,\Diamond\\}$. At each stage $t$, if the game is in state
$s_{t}\in S_{\odot}$ then player $\odot$ chooses a successor state $s_{t+1}$
with $s_{t}{\longrightarrow}{}s_{t+1}$; otherwise the game is in a random
state $s_{t}\in S_{\ocircle}$ and proceeds randomly to $s_{t+1}$ with
probability $P(s_{t})(s_{t+1})$. If $S_{\odot}=\emptyset$, we say that player
$\odot$ is _passive_ , and the game is a _Markov decision process (MDP)_. A
Markov chain is an MDP where both players are passive.

Strategies and Probability Measures. The set of histories at stage $t$ is
denoted by $H_{t}$, i.e.,
$H_{0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}S$ and
$H_{t}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}Z^{t}\times S$. Let
$H\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcup_{t\in\mathbb{N}}H_{t}$
be the set of all histories. For each history $h$, let $s_{h}$ denote the
final state in $h$. (In the special case of turn-based games, the history can
be represented by the sequence of states $s_{0}s_{1}\cdots s_{h}$, where
$s_{i}{\longrightarrow}{}s_{i+1}$ for all $i\in\mathbb{N}$.) We say that a
history $h\in H_{t}$ _visits_ the set of states $T\subseteq S$ at stage $t$ if
$s_{h}\in T$.

A mixed action for Maximizer (resp. Minimizer) in state $s$ is a distribution
over $A(s)$ (resp. $B(s)$). A _strategy_ for Maximizer (resp. Minimizer) is a
function $\sigma$ (resp. $\pi$) that to each history $h\in H$ assigns a mixed
action $\sigma(h)\in\mathcal{D}(A(s_{h}))$ (resp.
$\pi(h)\in\mathcal{D}(B(s_{h}))$ for Minimizer). For turn-based games this
means instead a distribution $\sigma(h)\in\mathcal{D}(S)$ over successor
states if $s_{h}\in S_{\Box}$ (and similarly for Minimizer with $s_{h}\in
S_{\Diamond}$). Let $\Sigma$ (resp. $\Pi$) denote the set of strategies for
Maximizer (resp. Minimizer).

An initial state $s_{0}$ and a pair of strategies $\sigma,\pi$ for Maximizer
and Minimizer induce a probability measure on sets of plays. We write
${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({{\mathfrak{R}}})$ for the
probability of a measurable set of plays ${\mathfrak{R}}$ starting from
$s_{0}$. It is initially defined for the cylinder sets and extended to the
sigma algebra by Carathéodory’s unique extension theorem (Billingsley, 1995).

Objectives. We consider the reachability objective for Maximizer. 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. From Minimizer’s point of view,
this is the dual _safety_ objective
$\mathtt{Safety}(T)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}Z^{\omega}\setminus\mathtt{Reach}(T)$
of plays that never visit $T$. Maximizer (resp. Minimizer) attempts to
maximize (resp. minimize) the probability of $\mathtt{Reach}(T)$.

Value and Optimality. For a game ${\mathcal{G}}$, initial state $s_{0}$ and
objective ${\mathfrak{R}}$ the _lower value_ is defined as

$\alpha(s_{0})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\sigma\in\Sigma}\inf_{\pi\in\Pi}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({{\mathfrak{R}}})$

Similarly, the _upper value_ is defined as

$\beta(s_{0})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\inf_{\pi\in\Pi}\sup_{\sigma\in\Sigma}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({{\mathfrak{R}}})$

The inequality $\alpha(s_{0})\leq\beta(s_{0})$ always holds. If
$\alpha(s_{0})=\beta(s_{0})$, then this quantity is called the _value_ of the
game, denoted by ${\mathtt{val}_{{\mathcal{G}},{\mathfrak{R}}}(s_{0})}$.
Reachability objectives, like all Borel objectives, have value by (Maitra and
Sudderth, 1998). For $\varepsilon>0$, a strategy $\sigma\in\Sigma$ from
$s_{0}$ for Maximizer is called $\varepsilon$-optimal if
$\forall\pi\in\Pi.\,{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({{\mathfrak{R}}})\geq{\mathtt{val}_{{\mathcal{G}},{\mathfrak{R}}}(s_{0})}-\varepsilon$.
Similarly, a strategy $\pi\in\Pi$ from $s_{0}$ for Minimizer is called
$\varepsilon$-optimal if
$\forall\sigma\in\Sigma.\,{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}({{\mathfrak{R}}})\leq{\mathtt{val}_{{\mathcal{G}},{\mathfrak{R}}}(s_{0})}+\varepsilon$.
A $0$-optimal strategy is called optimal.

Memory-based Strategies. A _memory-based strategy_ $\sigma$ of Maximizer is a
strategy that can be described by a tuple $({\sf M},{\sf
m}_{0},\sigma_{\alpha},\sigma_{\sf m})$ where ${\sf M}$ is the set of memory
states, ${\sf m}_{0}\in{\sf M}$ is the initial memory state, and the functions
$\sigma_{\alpha}$ and $\sigma_{\sf m}$ describe how actions are chosen and
memory states updated; see below. A play according to $\sigma$ generates a
random sequence of memory states ${\sf m}_{0},\dots,{\sf m}_{t},{\sf
m}_{t+1},\dots$ from a given set of memory states ${\sf M}$, where ${\sf
m}_{t}$ is the memory state at stage $t$. The strategy $\sigma$ selects the
action at stage $t$ according to a distribution that depends only on the
current state $s_{t}$ and the memory ${\sf m}_{t}$. Maximizer’s action $a_{t}$
is chosen via a distribution $\sigma_{\alpha}(s_{t},{\sf
m}_{t})\in\mathcal{D}(A(s_{t}))$. (Minimizer’s action is $b_{t}$). The next
memory state ${\sf m}_{t+1}$ of Maximizer is chosen according to a
distribution $\sigma_{m}(s_{t},a_{t},b_{t},s_{t+1})\in\mathcal{D}({\sf M})$
that depends on the chosen actions and the observed outcome. The memory is
_private_ if the other player cannot see the memory state. Otherwise, it is
_public_.

Let $\sigma[{\sf m}]$ denote the memory-based strategy $\sigma$ that starts in
memory state ${\sf m}$. In cases where the time is relevant and the strategy
has access to the time (by using a step counter) $\sigma[{\sf m}](t)$ denotes
the strategy $\sigma$ in memory mode ${\sf m}$ at time $t$.

A _finite-memory strategy_ is one where $|{\sf M}|<\infty$. A _$k$ -memory
strategy_ is a memory-based strategy with at most $k$ memory states, i.e.,
$|{\sf M}|\leq k$. A $2$-memory strategy is also called a _1-bit strategy_. A
strategy is _memoryless_ (also called positional or stationary) if $|{\sf
M}|=1$. A strategy is called _Markov_ if it uses only a step counter but no
additional memory. A strategy is _deterministic_ (also called pure) if the
distributions for the action and memory update are Dirac. Otherwise, it is
called _randomized_ (or mixed). Pure stationary strategies are also called MD
(memoryless deterministic) and mixed stationary strategies are also called MR
(memoryless randomized). Similarly, pure (resp. mixed) finite-memory
strategies are also called FD (resp. FR).

A finite-memory strategy $\sigma$ is called _uniformly $\varepsilon$-optimal_
for an objective ${\mathfrak{R}}$ if there is a memory state ${\sf
m}_{0}\in{\sf M}$ such that $\forall s\in
S.\forall\pi.\,{\mathcal{P}}_{{\mathcal{G}},s,\sigma[{\sf
m}_{0}],\pi}({{\mathfrak{R}}})\geq{\mathtt{val}_{{\mathcal{G}},{\mathfrak{R}}}(s)}-\varepsilon$,
i.e., the strategy performs well from every state.

The definitions above carry over directly to the simpler turn-based games with
chosen/observed transitions instead of actions.

##  3\. Uniform Strategies in Concurrent Games

10 |  |  Min
---|---|---
|  | 0 | 1
Max | 0 | $c_{i-1}$ | $c_{i+1}$
1 | $\mathrm{lose}$ | $\mathrm{win}$
actions at $c_{i}$ ($i\in\mathbb{Z}$)

$\cdots$$~{}c_{i-1}~{}$$c_{i}$$~{}c_{i+1}~{}$$\cdots$$\mathrm{win}$$\mathrm{lose}$$0$$1$$0$$0$$1$$1$$1$$0$

Figure 1. Concurrent Big Match on $\mathbb{Z}$; see Definition 3.1

First, we consider the concurrent version of the big match on the integers, in
the formulation of (Fristedt et al., 1995).

###### Definition 3.1 (Concurrent big match on $\mathbb{Z}$).

This game is shown in Figure 1. The state space is $\\{c_{i}\mid
i\in\mathbb{Z}\\}\cup\\{\mathrm{win},\mathrm{lose}\\}$, where the states
$\mathrm{win}$ and $\mathrm{lose}$ are absorbing. Both players have the action
set $\\{0,1\\}$ at each state. If Maximizer chooses action $1$ in $c_{i}$ then
the game is decided in this round: If Minimizer chooses $0$ (resp. $1$) then
the game goes to $\mathrm{lose}$ (resp. $\mathrm{win}$). If Maximizer chooses
action $0$ in $c_{i}$ and Minimizer chooses action $0$ (resp. $1$) then the
game goes to $c_{i-1}$ (resp. $c_{i+1}$). Maximizer wins iff state
$\mathrm{win}$ is reached or $\liminf\\{i\mid\mbox{$c_{i}$
visited}\\}=-\infty$.

###### Theorem 3.2 ((Fristedt et al., 1995, Theorem 1.1)).

In the concurrent big match on $\mathbb{Z}$, shown in Figure 1, every state
$c_{i}$ has value $1/2$. An optimal strategy for Minimizer is to toss a fair
coin at every stage. Maximizer has no optimal strategy, but for any start
state $c_{x}$ and any positive integer $N$, he can win with probability $\geq
N/(2N+2)$ by choosing action $1$ with probability $1/(n+1)^{2}$ whenever the
current state is $c_{i}$ with $i=x+N-n$ for some $n\geq 0$.

The concurrent big match on $\mathbb{Z}$ is not a reachability game, due to
its particular winning condition. However, the following slightly modified
version (played on $\mathbb{N}$) is a reachability game.

###### Definition 3.3 (Concurrent big match on $\mathbb{N}$).

This game is shown in Figure 2. The state space is $\\{c_{i}\mid
i\in\mathbb{N}\\}\cup\\{\mathrm{lose}\\}$ where $\mathrm{lose}$ and $c_{0}$
are absorbing. Both players have the action set $\\{0,1\\}$ at each state. If
Maximizer chooses action $1$ in $c_{i}$ then the game is decided in this
round: If Minimizer chooses $0$ (resp. $1$) then the game goes to
$\mathrm{lose}$ (resp. $c_{0}$). If Maximizer chooses action $0$ in $c_{i}$
and Minimizer chooses action $0$ (resp. $1$) then the game goes to $c_{i-1}$
(resp. $c_{i+1}$).

Maximizer wins iff $c_{0}$ is reached, i.e., we have the reachability
objective $\mathtt{Reach}(\\{c_{0}\\})$.

The following theorem summarizes results on the concurrent big match on
$\mathbb{N}$ by combining results from (Fristedt et al., 1995) and (Nowak and
Raghavan, 1991).

10 |  |  Min
---|---|---
|  | 0 | 1
Max | 0 | $c_{i-1}$ | $c_{i+1}$
1 | $\mathrm{lose}$ | $c_{0}$
actions at $c_{i}$ ($i\geq 1$)

$c_{0}$$\cdots$$~{}c_{i-1}~{}$$c_{i}$$~{}c_{i+1}~{}$$\cdots$$\mathrm{lose}$$0$$1$$0$$0$$1$$1$$1$$0$

Figure 2. Concurrent Big Match on $\mathbb{N}$; see Definition 3.3.

###### Theorem 3.4.

Denote by ${\mathcal{G}}$ the concurrent big match game on $\mathbb{N}$, as
shown in Figure 2, and let $x\geq 0$.

  1. (1)

${\mathtt{val}_{{\mathcal{G}}}(c_{x})}=(x+2)/(2x+2)\geq 1/2$.

  2. (2)

For every start state $c_{x}$ and $N\geq 0$, Maximizer can win with
probability $\geq N/(2N+2)$ by choosing action $1$ with probability
$1/(n+1)^{2}$ whenever the current state is $c_{i}$ with $i=x+N-n$ for some
$n\geq 0$.

  3. (3)

For any $\varepsilon<1/2$ there does not exist any uniformly
$\varepsilon$-optimal positional (MR) strategy for Maximizer.

Every MR Maximizer strategy $\sigma$ attains arbitrarily little from $c_{x}$
as $x\to\infty$. Formally,

$\limsup_{x\to\infty}\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0$

###### Proof.

Item 1 follows directly from (Fristedt et al., 1995, Proposition 5.1).

Item 2 follows from Theorem 3.2, since it is easier for Maximizer to win in
the game of Definition 3.3 than in the game of Definition 3.1.

Towards item 3, we follow the proof of (Nowak and Raghavan, 1991, Lemma 4).
Let $\sigma$ be an MR Maximizer strategy and $f(x)$ the probability that
$\sigma$ picks action $1$ at state $c_{x}$. There are two cases.

In the first case $\sum_{x\geq 1}f(x)<\infty$. Let $\pi$ be the strategy of
Minimizer that always picks action $1$. For all $x\geq 1$ we have

$\displaystyle{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))\leq$
$\displaystyle\ f(x)+(1-f(x))f(x+1)$ $\displaystyle+(1-f(x))(1-f(x+1))f(x+2)$
$\displaystyle+\dots\ \leq\sum_{k=x}^{\infty}f(k)<\infty.$

Thus
$\limsup_{x\to\infty}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0$.

In the second case $\sum_{x\geq 1}f(x)=\infty$. Let $\pi$ be the strategy of
Minimizer that always picks action $0$. For all $x\geq 1$ we have

$\displaystyle{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}$
$\displaystyle(\mathtt{Reach}(\\{c_{0}\\}))$ $\displaystyle=$
$\displaystyle\;(1-f(x))(1-f(x-1))\cdots(1-f(1))$ $\displaystyle=$
$\displaystyle\prod_{k=1}^{x}(1-f(k))$ $\displaystyle\leq$
$\displaystyle\;\frac{1}{1+\sum_{k=1}^{x}f(k)}\qquad\qquad\qquad\text{by
\lx@cref{creftype~refnum}{prop:Weierstrass}}$

Thus
$\limsup_{x\to\infty}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0$.

Since, by item 1, ${\mathtt{val}_{{\mathcal{G}}}(c_{x})}=(x+2)/(2x+2)\geq 1/2$
for every $x\geq 0$, the MR strategy $\sigma$ cannot be uniformly
$\varepsilon$-optimal for any $\varepsilon<1/2$. ∎

While uniformly $\varepsilon$-optimal Maximizer strategies cannot be
positional, we show that they can be chosen with just 1 bit of public memory
(Appendix B).

###### Theorem 3.5.

For any concurrent game with finite action sets and reachability objective,
for any $\varepsilon>0$, Maximizer has a uniformly $\varepsilon$-optimal
public 1-bit strategy. If the game is turn-based and finitely branching,
Maximizer has a deterministic such strategy.

###### Proof sketch..

The full proof can be found in Appendix B. Here we just sketch the
construction of the 1-bit strategy.

Let us describe the 1-bit strategy in terms of a _layered_ game with state
space $S\times\\{0,1\\}$, where the $S$ is the state space of the original
game and second component ($0$ or $1$) reflects the current memory state of
Maximizer. Accordingly, we think of the state space as organized in two
_layers_ , the “inner” and the “outer” layer, with the memory state being $0$
and $1$, respectively. In these terms, our goal is to construct, for the
layered game, a _memoryless_ strategy for Maximizer. The current state of the
layered game is known to both players, which corresponds to the (1-bit) memory
being public in the original game. In particular, Minimizer always knows the
distribution of actions that Maximizer is about to play.

In general Maximizer does not have uniformly $\varepsilon$-optimal memoryless
strategies in reachability games; cf. Theorem 3.4. Our construction exploits
the special structure in the layered game, namely, the symmetry of the two
layers. The memoryless Maximizer strategy we construct will be
$\varepsilon$-optimal from each state $(s,0)$ in the inner layer, but not
necessarily from the states in the outer layer.

As building blocks we use memoryless (yet non-uniform) $\varepsilon$-optimal
strategies which are known to exist. In the turn-based finitely branching case
they are even MD. These memoryless strategies have the convenient property
that they are likely to reach the target within a bounded subspace and thus
can be left unspecified outside (see Lemma B.1 in the appendix). We
iteratively “fix” such non-uniform $\varepsilon$-optimal memoryless strategies
in finite subsets of the state space of the layered game. In the limit, when
the whole state space of the layered game has been covered, these fixings
define a uniformly $\varepsilon$-optimal public 1-bit strategy.

Loosely speaking, we fix good memoryless strategies in those regions of the
inner layer where they have a near-optimal attainment and otherwise we only
fix them in the outer layer. As a consequence, the resulting 1-bit strategy is
$\varepsilon$-optimal from every state if the initial memory mode is $0$, but
not necessarily if the initial memory mode is $1$. ∎

Almost surely winning Maximizer strategies, if they exist, can be chosen as
memoryless (Appendix B).

###### Theorem 3.6.

Given a concurrent game with finite action sets and a reachability objective,
there is a single randomized memoryless Maximizer strategy that is almost
surely winning from every state that admits an almost surely winning strategy.

##  4\. Uniform Strategies in Turn-based Games

We now define a finitely branching turn-based game in Definition 4.1 that is
very similar to the concurrent big match on $\mathbb{N}$, as shown in Figure
2. The difference is that at each $c_{i}$ Maximizer has to announce his mixed
choice of actions first, rather than concurrently with Minimizer. Note that
Maximizer only announces his distribution over the actions $\\{0,1\\}$, not
any particular action. Since a good Maximizer strategy needs to work even if
Minimizer knows it in advance, this makes no difference with respect to the
attainment of positional Maximizer strategies. Another slight difference is
that Maximizer is restricted to choosing distributions with only _rational_
probabilities where the probability of picking action $1$ is of the form $1/k$
for some $k\in\mathbb{N}$. However, since we know that there exist good
Maximizer strategies of this form (cf. Theorem 3.4), it is not a significant
restriction.

###### Definition 4.1 (Turn-based big match on $\mathbb{N}$).

This game is shown in Figure 3. Maximizer controls the set $\\{c_{i}\mid
i\in\mathbb{N}\\}\cup\\{c_{i,j}\mid
i,j\in\mathbb{N}\\}\cup\\{\mathrm{lose}\\}$ of states, whereas Minimzer
controls only the states in $\\{d_{i,j}\mid i,j\in\mathbb{N}\\}$. The
remaining set $\\{r_{i,j}^{0},r_{i,j}^{1}\mid i,j\in\mathbb{N}\\}$ of states
are random. For all $i,j\in\mathbb{N}$, there are following transitions

$\displaystyle c_{i}{\longrightarrow}c_{i,1}\qquad\quad
c_{i,j}{\longrightarrow}c_{i,j+1}\qquad\quad c_{i,j}{\longrightarrow}d_{i,j}$
$\displaystyle d_{i,j}{\longrightarrow}r_{i,j}^{0}\qquad\quad
d_{i,j}{\longrightarrow}r_{i,j}^{1}$

and $\mathrm{lose}{\longrightarrow}\mathrm{lose}$. Intuitively, by going from
$c_{i}$ to $d_{i,j}$, Maximizer chooses action $1$ with probability $1/j$ and
action $0$ with probability $1-1/j$. Minimizer chooses actions $0$ or $1$ by
going from $d_{i,j}$ to $r_{i,j}^{0}$ or $r_{i,j}^{1}$, respectively. The
probabilistic function is defined by

$\displaystyle P(r_{i,j}^{0})(\mathrm{lose})=1/j\qquad$ $\displaystyle\qquad
P(r_{i,j}^{0})(c_{i-1})=1-1/j$ $\displaystyle P(r_{i,j}^{1})(c_{0})=1/j\qquad$
$\displaystyle\qquad P(r_{i,j}^{1})(c_{i+1})=1-1/j$

where $i,j\in\mathbb{N}$. The objective is $\mathtt{Reach}(\\{c_{0}\\})$.

This finitely branching turn-based game mimics the behavior of the game in
Definition 3.3.

For an alternative construction of a finitely branching turn-based
reachability game without uniformly $\varepsilon$-optimal positional Maximizer
strategies see Appendix C.

$~{}c_{0}~{}$$\cdots$$c_{i-1}$$c_{i+1}$$~{}c_{i}~{}$$~{}c_{i,1}~{}$$\vdots$$~{}c_{i,j}~{}$$\vdots$$d_{i,1}$$d_{i,j}$$r^{0}_{i,1}$$r^{1}_{i,1}$$r^{0}_{i,j}$$r^{1}_{i,j}$$\mathrm{lose}$$1$$1$$\frac{1}{j}$$\mathrm{lose}$$\frac{1}{j}$$1-\frac{1}{j}$$1-\frac{1}{j}$$\vdots$$\vdots$
Figure 3. Turn-based Big Match on $\mathbb{N}$.

###### Theorem 4.2.

Consider the turn-based big match game ${\mathcal{G}}$ on $\mathbb{N}$ from
Definition 4.1 and let $x\geq 0$.

  1. (1)

For every start state $c_{x}$ and $N\geq 0$, Maximizer can win with
probability $\geq N/(2N+2)$ by choosing the transitions
$c_{i}{\longrightarrow}\dots d_{i,j}$ where $j=(n+1)^{2}$ whenever he is in
state $c_{i}$ with $i=x+N-n$ for some $n\geq 0$.

In particular, ${\mathtt{val}_{{\mathcal{G}}}(c_{x})}\geq 1/2$.

  2. (2)

For any $\varepsilon<1/2$ there does not exist any uniformly
$\varepsilon$-optimal positional (MR) strategy for Maximizer.

Every MR Maximizer strategy $\sigma$ attains arbitrarily little from $c_{x}$
as $x\to\infty$. Formally,

$\limsup_{x\to\infty}\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0$

###### Proof.

Let ${\mathcal{G}}^{\prime}$ be the concurrent game from Definition 3.3.

Towards item 1, consider the concurrent game ${\mathcal{G}}^{\prime}$ and the
turn-based game ${\mathcal{G}}$ from Definition 4.1. Let $c_{x}$ be our start
state. After fixing the Maximizer strategy from Theorem 3.4(2) in
${\mathcal{G}}^{\prime}$, we obtain an MDP ${\mathcal{M}}^{\prime}$ from
Minimizer’s point of view. Similarly, after fixing the strategy described
above in ${\mathcal{G}}$, we obtain an MDP ${\mathcal{M}}$. Then
${\mathcal{M}}^{\prime}$ and ${\mathcal{M}}$ are almost isomorphic (apart from
linear chains of steps $c_{j,j}{\longrightarrow}c_{i,j+1}\dots$ in
${\mathcal{M}}^{\prime}$), and thus the infimum of the chance of winning, over
all Minimizer strategies are the same. Therefore the result follows from
Theorem 3.4(2).

Towards item 2, note that every Maximizer MR strategy $\sigma$ in
${\mathcal{G}}$ corresponds to a Maximizer MR strategy $\sigma^{\prime}$ in
${\mathcal{G}}^{\prime}$. First, forever staying in states $c_{i,j}$ is
losing, since the target is never reached. Thus, without restriction, we
assume that $\sigma$ almost surely moves from $c_{i}$ to some $d_{i,j}$
eventually. Let $p_{i,j}$ be the probability that $\sigma$ moves from $c_{i}$
to $d_{i,j}$. Thus the corresponding strategy $\sigma^{\prime}$ in
${\mathcal{G}}^{\prime}$ in $c_{i}$ plays action $1$ with probability
$\sum_{j}p_{i,j}(1/j)$ and action $0$ otherwise. Again the MDPs resulting from
fixing the respective strategies in ${\mathcal{G}}$ and
${\mathcal{G}}^{\prime}$ are (almost) isomorphic, and thus the result follows
from Theorem 3.4(3). ∎

##  5\. No Positional Strategies for Reachability in Infinitely Branching
Games

$u$$~{}~{}\ldots$Definition 5.1$\cdots$$D_{i}$Definition
6.1$~{}c_{0}~{}$$\cdots$$c_{i-1}$$~{}c_{i}~{}$$c_{i+1}$$~{}c_{i,1}~{}$$\vdots$$~{}c_{i,j}~{}$$\vdots$$d_{i,1}$$d_{i,j}$$r^{0}_{i,1}$$r^{1}_{i,1}$$r^{0}_{i,j}$$r^{1}_{i,j}$$1$$\frac{1}{j}$$1-\frac{1}{j}$$1-\frac{1}{j}$$\vdots$$\vdots$$\mathrm{lose}$$1$$\frac{1}{j}$
Figure 4. The scheme of games defined in Definition 5.1 and in Definition 6.1,
where in the former the teal-coloured boxes are replaced with a line
connecting $u$ directly to the $c_{i}$, whereas in the latter such a teal-
coloured box is replaced with a Delay gadget $D_{i}$ illustrated in Figure 5.

In finitely branching turn-based stochastic 2-player games with reachability
objectives, Maximizer has $\varepsilon$-optimal MD strategies (but no uniform
$\varepsilon$-optimal MD or MR strategies).

Now we show that this does not carry over to infinitely branching turn-based
reachability games. In this case, there are not even $\varepsilon$-optimal MR
strategies, i.e., good Maximizer strategies need memory. The reason for this
is the infinite branching of Minimizer, since infinite branching of Maximizer
states and random states can easily be encoded into finite branching in the
case of reachability objectives.

###### Definition 5.1.

Consider the finitely branching turn-based reachability game from Definition
4.1. We construct an infinitely branching game ${\mathcal{G}}$ by adding a new
Minimizer-controlled initial state $u$, Minimizer-transitions
$u{\longrightarrow}c_{i}$ for all $i\in\mathbb{N}$ and
$\mathrm{lose}{\longrightarrow}u$. See Figure 4 for a scheme of this game. The
objective is still $\mathtt{Reach}(\\{c_{0}\\})$.

###### Theorem 5.2.

Let ${\mathcal{G}}$ be the infinitely branching turn-based reachability game
from Definition 5.1.

  1. (1)

All states in ${\mathcal{G}}$ are almost sure winning. I.e., for every state
$s$ there exists a Maximizer strategy $\sigma$ such that
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=1$.

  2. (2)

For each MR Maximizer strategy $\sigma$ we have

$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},u,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0.$

I.e., for any $\varepsilon<1$ there does not exist any $\varepsilon$-optimal
MR Maximizer strategy $\sigma$ from state $u$.

###### Proof.

Towards item 1, first note that by playing

$c_{i}{\longrightarrow}c_{i,1}{\longrightarrow}d_{i,1}$

Maximizer can enforce that he either wins (if Minimizer goes to $r_{i,1}^{1}$)
or the game returns to state $u$ (via state $\mathrm{lose}$ if Minimizer goes
to $r_{i,1}^{0}$). Thus it suffices to show that Maximizer can win almost
surely from state $u$. We construct a suitable strategy $\sigma$ (which is not
MR). By Theorem 4.2, ${\mathtt{val}_{{\mathcal{G}}}(c_{x})}\geq 1/2$ for every
$x$. Moreover, the game from $c_{x}$ is finitely branching unless we return to
$u$. Thus there exists a strategy $\sigma_{x}$ and a finite horizon $h_{x}$
such that
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma_{x},\pi}(\mathtt{Reach}_{h_{x}}(\\{c_{0}\\}))\geq
1/4$. Then $\sigma$ plays from $u$ as follows. If Minimizer moves
$u{\longrightarrow}c_{x}$ then first play $\sigma_{x}$ for $h_{x}$ steps,
unless $c_{0}$ or $u$ are reached first. Then play to reach $u$ again, i.e.,
the next time that the play reaches a state $c_{i}$ play
$c_{i}{\longrightarrow}c_{i,1}{\longrightarrow}d_{i,1}$ (thus either Maximizer
wins or the play returns to $u$). So after every visit to $u$ the Maximizer
strategy $\sigma$ wins with probability $\geq 1/4$ before seeing $u$ again,
and otherwise the play returns to $u$. Thus
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))\geq
1-(1/4)^{\infty}=1$. This proves item 1.

###### Claim 5.1.

Suppose that for each MR Maximizer strategy $\sigma$ and every $\varepsilon>0$
there is a Minimizer strategy $\pi(\sigma,\varepsilon)$ such that, from $u$,
the probability of visiting $c_{0}$ before revisiting $u$ is at most
$\varepsilon$. Then item 2 is true.

###### Proof of the claim.

Suppose the precondition of the claim. Let $\sigma$ be an MR Maximizer
strategy. Let $\pi$ be the Minimizer strategy that, after the $i$-th visit to
$u$, plays $\pi(\sigma,\varepsilon\cdot 2^{-i})$ until the next visit to $u$.
It follows that
${\mathcal{P}}_{{\mathcal{G}},u,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))\leq\sum_{i\geq
1}\varepsilon\cdot 2^{-i}=\varepsilon$. ∎

It remains to prove the precondition of the claim. Let $\sigma$ be an MR
Maximizer strategy, and let $\varepsilon>0$. By Theorem 4.2(2), there are
$i\in\mathbb{N}$ and a Minimizer strategy $\pi$ such that
${\mathcal{P}}_{{\mathcal{G}}^{\prime},c_{i},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))\leq\varepsilon$,
where ${\mathcal{G}}^{\prime}$ is the finitely branching subgame of
${\mathcal{G}}$ from Definition 4.1. The Minimizer strategy
$\pi(\sigma,\varepsilon)$ that, in ${\mathcal{G}}$, from $u$ goes to $c_{i}$
and then plays $\pi$ has the required property. ∎

$b_{i}$$~{}~{}\ldots$entering the
gadget$~{}b_{i,0}~{}$$~{}b_{i,1}~{}$$~{}b_{i,2}~{}$$\ldots$$~{}b_{i,j}~{}$$\vdots$exiting
the gadget$~{}~{}\ldots$delay $0$delay $1$delay $j$ Figure 5. Delay Gadget
$D_{i}$, used in Figure 4.

##  6\. No Markov Strategies for Reachability in Infinitely Branching Games

We strengthen the result from the previous section by modifying the game so
that even Markov strategies are useless for Maximizer. The modification of the
game allows Minimizer to cause an arbitrary but finite delay before any state
$c_{i}$ is entered.

###### Definition 6.1.

Consider the infinitely branching turn-based reachability game from Definition
5.1. We modify it as follows. For each $i\in\mathbb{N}$ we add a Minimizer-
controlled state $b_{i}$ and redirect all transitions going into $c_{i}$ to go
into $b_{i}$ instead. Each $b_{i}$ is infinitely branching: for each
$j\in\mathbb{N}$ we add a random state $b_{i,j}$ and a transition
$b_{i}{\longrightarrow}b_{i,j}$. We add further states so that the game moves
(deterministically, via a chain of random states) from $b_{i,j}$ to $c_{i}$ in
exactly $j$ steps. See Figures 4 and 5 for a depiction of this game. The
objective is still $\mathtt{Reach}(\\{c_{0}\\})$.

###### Theorem 6.2.

Let ${\mathcal{G}}$ be the infinitely branching turn-based reachability game
from Definition 6.1.

  1. (1)

All states in ${\mathcal{G}}$ are almost sure winning. I.e., for every state
$s$ there exists a Maximizer strategy $\sigma$ such that
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=1$.

  2. (2)

For every Markov Maximizer strategy $\sigma$ it holds that
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},u,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0$.
I.e., no Markov Maximizer strategy is $\varepsilon$-optimal from state $u$ for
any $\varepsilon<1$.

###### Proof.

Item 1 follows from Theorem 5.2(1), as the modification in Definition 6.1 only
allows Minimizer to cause finite delays.

Towards item 2, the idea of the proof is that for every Markov Maximizer
strategy $\sigma$, Minimizer can cause delays that make $\sigma$ behave in the
way it would after a long time. This way, Minimizer turns $\sigma$
approximately to an MR-strategy, which is useless by Theorem 5.2(2).

In more detail, fix any Markov Maximizer strategy $\sigma$. As in the proof of
Theorem 4.2(2), we can assume that whenever the game is in $c_{i}$, the
strategy $\sigma$ almost surely moves eventually to some $d_{i,j}$. Let
$p_{i,j,t}$ be the probability that strategy $\sigma$, when it is in $c_{i}$
at time $t$, moves to $d_{i,j}$. Thus, a corresponding Maximizer strategy in
the (concurrent) big match, when it is in $c_{i}$ at time $t$, picks action
$1$ with probability
$f(i,t)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sum_{j}p_{i,j,t}(1/j)$;
cf. the proof of Theorem 4.2(2). For each $i\in\mathbb{N}$, let $f(i)$ be an
accumulation point of $f(i,1),f(i,2),\ldots$; e.g., take
$f(i)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\liminf_{t}f(i,t)$. We
have that

(1) $\displaystyle\forall_{i\in\mathbb{N}}\ \forall_{t_{0}\in\mathbb{N}}\
\forall_{\varepsilon>0}\ \exists_{t\geq t_{0}}:$ $\displaystyle\quad
f(i,t)\leq f(i)+\varepsilon$ (2) $\displaystyle\forall_{i\in\mathbb{N}}\
\forall_{t_{0}\in\mathbb{N}}\ \forall_{\varepsilon>0}\ \exists_{t\geq t_{0}}:$
$\displaystyle\quad f(i,t)\geq f(i)-\varepsilon$

Similarly to the proof of Theorem 5.2(2) (see 5.1 therein), it suffices to
show that after each visit to $u$, Minimizer can make the probability of
visiting $c_{0}$ before seeing $u$ again arbitrarily small. Let
$\varepsilon>0$. We show that Minimizer has a strategy $\pi$ to make this
probability at most $\varepsilon$.

Consider the first case where $\sum_{i\geq 1}f(i)<\infty$. Then there is
$i_{0}\in\mathbb{N}$ such that $\sum_{i\geq i_{0}}f(i)\leq\varepsilon/2$. In
$u$, strategy $\pi$ moves to $b_{i_{0}}$. Whenever the game is in some
$b_{i}$, strategy $\pi$ moves to some $b_{i,j}$ so that the game will arrive
in $c_{i}$ at a time $t$ that satisfies $f(i,t)\leq
f(i)+2^{-i}\cdot\varepsilon/2$; such $t$ exists due to (1). In $c_{i}$
Maximizer (using $\sigma)$ moves (eventually) to some $d_{i,j}$. Then $\pi$
always chooses “action $1$”; i.e., $\pi$ moves to $r_{i,j}^{1}$. In this way,
the play, restricted to states $c_{i}$, is either of the form
$c_{i_{0}},c_{i_{0}+1},\ldots$ (Maximizer loses) or of the form
$c_{i_{0}},c_{i_{0}+1},\ldots,c_{i_{0}+k},c_{0}$ (Maximizer wins). The
probability of the latter can be bounded similarly to the proof of Theorem
3.4(3); i.e., we have

$\displaystyle{\mathcal{P}}_{{\mathcal{G}},u,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))$
$\displaystyle\leq\
\sum_{i=i_{0}}^{\infty}f(i)+2^{-i}\cdot\frac{\varepsilon}{2}$
$\displaystyle\leq\ \frac{\varepsilon}{2}+\frac{\varepsilon}{2}\ =\
\varepsilon\,.$

Now consider the second case where $\sum_{i\geq 1}f(i)=\infty$. Then there is
$i_{0}\in\mathbb{N}$ such that
$\sum_{i=1}^{i_{0}}f(i)\geq\frac{1}{\varepsilon}$. In $u$, strategy $\pi$
moves to $b_{i_{0}}$. Whenever the game is in some $b_{i}$, strategy $\pi$
moves to some $b_{i,j}$ so that the game will arrive in $c_{i}$ at a time $t$
that satisfies $f(i,t)\geq f(i)-2^{-i}$; such $t$ exists due to (2). In
$c_{i}$ Maximizer (using $\sigma)$ moves (eventually) to some $d_{i,j}$. Then
$\pi$ always chooses “action $0$”; i.e., $\pi$ moves to $r_{i,j}^{0}$. In this
way, the play, restricted to states $c_{i}$, is either of the form
$c_{i_{0}},c_{i_{0}-1},\ldots,c_{0}$ (Maximizer wins) or of the form
$c_{i_{0}},c_{i_{0}-1},\ldots,c_{i_{0}-k}$ (for some $k<i_{0}$), followed by
$\mathrm{lose},u$ (Maximizer does not reach $c_{0}$ before revisiting $u$).
The probability of the former can be bounded similarly to the proof of Theorem
3.4(3); i.e., the probability that the play reaches $c_{0}$ before $u$ is
upper-bounded by

$\displaystyle\prod_{i=1}^{i_{0}}$ $\displaystyle(1-\max\\{f(i)-2^{-i},0\\})$
$\displaystyle\leq\
\frac{1}{1+\sum_{i=1}^{i_{0}}(f(i)-2^{-i})}\qquad\qquad\text{by
\lx@cref{creftype~refnum}{prop:Weierstrass}}$ ∎ $\displaystyle\leq\
\frac{1}{\sum_{i=1}^{i_{0}}f(i)}\ \leq\ \varepsilon\,.$

##  7\. Good Strategies for Reachability Require Infinite Memory

Game $G_{k+1}$ constructed inductively from $\\{G^{i}_{k}\mid
i\in\mathbb{N}\\}$$u$$~{}~{}\ldots$$D_{0}$$\ldots$$D_{i-1}$$D_{i}$$D_{i+1}$$~{}c_{0}~{}$$\ldots$$c_{i-1}$$~{}c_{i}~{}$$c_{i+1}$$\vdots$$\vdots$Game
$G^{i}_{k}$an ingoing transition to each state in
$G^{i}_{k}$$u^{k,i}$$~{}~{}\ldots$$D^{k,i}_{0}$$c^{k,i}_{0}$$\mathrm{win^{k,i}}$$\mathrm{lose^{k,i}}$$~{}c_{i,1}~{}$$\vdots$$~{}c_{i,j}~{}$$\vdots$$d_{i,1}$$d_{i,j}$$r^{0}_{i,1}$$r^{1}_{i,1}$$r^{0}_{i,j}$$r^{1}_{i,j}$$\mathrm{lose}$$1$$\frac{1}{j}$$1$$\frac{1}{j}$$1-\frac{1}{j}$$1-\frac{1}{j}$
Figure 6. The scheme of the nested construction in Definition 7.1.

We show that even finite private memory, in addition to a step counter, is
useless for Maximizer in infinitely branching reachability games. To this end,
we define a nested version of the game of Definition 6.1, where the memory
requirements increase unboundedly with the nesting depth.

###### Definition 7.1.

Let ${\mathcal{G}}$ be the game from Definition 6.1. We inductively define the
_$k$ -nested_ game ${\mathcal{G}}_{k}$ as follows (see Fig. 6). For the base
case, let
${\mathcal{G}}_{1}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathcal{G}}$.

For every $i\geq 1$ let ${\mathcal{G}}_{k}^{i}$ be a fresh copy of
${\mathcal{G}}_{k}$ and let $u^{k,i}$ (resp. $c_{0}^{k,i}$) be the initial
state $u$ (resp. the target state $c_{0}$) in ${\mathcal{G}}_{k}^{i}$. For
every $k\geq 1$ we construct ${\mathcal{G}}_{k+1}$ by modifying
${\mathcal{G}}$ as follows. The idea is that at every state $c_{i}$ Maximizer
first needs to win the subgame ${\mathcal{G}}_{k}^{i}$ before continuing in
the game ${\mathcal{G}}_{k+1}$, but Minimizer can choose at which state $s$ in
${\mathcal{G}}_{k}^{i}$ the subgame is entered.

We make the state $c_{i}$ Minimizer-controlled and replace the previous
Maximizer transition $c_{i}{\longrightarrow}c_{i,1}$ by Minimizer transitions
$c_{i}{\longrightarrow}s$ for every state $s$ in ${\mathcal{G}}_{k}^{i}$.
Moreover, we add the transitions
$c_{0}^{k,i}{\longrightarrow}\mathrm{win}^{k,i}{\longrightarrow}c_{i,1}$. (The
new state $\mathrm{win}^{k,i}$ is not strictly needed. It just indicates that
Maximizer has won and exited the subgame ${\mathcal{G}}_{k}^{i}$.) Note that
also in ${\mathcal{G}}_{k+1}$ Minimizer can introduce arbitrary delays between
states $b_{i}$ and $c_{i}$.

The objective in ${\mathcal{G}}_{k+1}$ is still $\mathtt{Reach}(\\{c_{0}\\})$.

###### Lemma 7.2.

For any $k\geq 1$ let ${\mathcal{G}}_{k}$ be the infinitely branching turn-
based reachability game from Definition 7.1.

  1. (1)

All states in ${\mathcal{G}}_{k}$ are almost sure winning. I.e., for every
state $s$ there exists a Maximizer strategy $\sigma$ such that

$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{k},s,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=1.$

  2. (2)

For each Maximizer strategy $\sigma$ with a step counter plus a private finite
memory with $\leq k$ modes

$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{k},u,\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0.$

I.e., for any $\varepsilon<1$ there does not exist any $\varepsilon$-optimal
step counter plus $k$ memory mode Maximizer strategy $\sigma$ from state $u$
in ${\mathcal{G}}_{k}$.

###### Proof sketch..

The full proof can be found in Appendix E. We prove both items simultaneously
by induction on $k$. The base case of $k=1$ follows immediately from Theorem
6.2 and the induction step for Item 1 is easily shown by repeatedly applying
Item 1 of Theorem 6.2.

The main obstacle in the induction step $k\to k+1$ for Item 2 is that
Maximizer has total freedom how to use his memory. One cannot assume that he
neatly organizes the memory with some modes reserved to handle the recursive
subgames ${\mathcal{G}}_{k}^{i}$ and others to handle the outer game
${\mathcal{G}}_{k+1}$. Moreover, both the steps and the memory updates can be
randomized and the memory modes are private. Finally, Maximizer’s choices can
depend on the step counter.

In our construction, Minimizer can largely negate the benefit of Maximizer’s
step counter by introducing arbitrary finite delays (similar, but not
identical, to Theorem 6.2). However, these delays need to be chosen carefully,
in order to match up with the argument why Maximizer’s $k+1$ private memory
modes are insufficient.

Since Maximizer’s memory is private, Minimizer does not know its content and
thus sometimes needs to hedge her bets and randomize. However, since this
private memory is finite, the penalty for the hedging is only a constant
factor $1/(k+1)$, which eventually becomes irrelevant.

We show that each Maximizer strategy falls into one of the following two
cases. For each case, we construct a good strategy for Minimizer that limits
Maximizer’s attainment to some arbitrarily small $\varepsilon$.

In the first case, there exist sufficiently many subgames
${\mathcal{G}}_{k}^{i}$ in which Minimizer can ensure the following property:
When (and if) Maximizer wins the subgame, then, in the outer game
${\mathcal{G}}_{k+1}$, Maximizer will play action ‘1’ with a (somewhat) high
probability in the next round. Then Minimizer can play action ‘0’ in the outer
game ${\mathcal{G}}_{k+1}$ and wins with that high probability. Since this
happens in sufficiently many subgames, Minimizer has a very high chance of
winning.

In the remaining second case, Minimizer cannot enforce the first case, in most
of the subgames ${\mathcal{G}}_{k}^{i}$. For every state in these subgames and
every time $t$ there exists a ‘forbidden’ memory mode for Maximizer. If
Maximizer sets his memory to this forbidden mode (for the current state and
time), then he will play action ‘1’ with a (somewhat) low probability in the
outer game ${\mathcal{G}}_{k+1}$ after (and if) he wins the subgame,
regardless of Minimizer’s choices inside the subgame. Minimizer always plays
action ‘1’ in the outer game ${\mathcal{G}}_{k+1}$. So if Maximizer enters a
forbidden memory mode in (sufficiently many) subgames ${\mathcal{G}}_{k}^{i}$,
then Minimizer will win the outer game by going to states $c_{i}$ with higher
and higher index numbers $i$, i.e., more distant from the target $c_{0}$. On
the other hand, if Maximizer does not enter any forbidden memory mode in the
subgame ${\mathcal{G}}_{k}^{i}$, then he is effectively reducing the number of
his available memory modes from $k+1$ to $k$. Inside the subgame
${\mathcal{G}}_{k}^{i}$, Minimizer plays a good strategy that limits the
attainment of any Maximizer strategy with only $k$ memory modes. Such a
Minimizer strategy exists by the induction hypothesis. So, in either case,
whether Maximizer enters a forbidden memory mode in the subgames
${\mathcal{G}}_{k}^{i}$ or not, his chances of winning the outer game
${\mathcal{G}}_{k+1}$ are low. ∎

In order to show that Maximizer needs infinite memory, in addition to a step
counter, we combine all the nested games ${\mathcal{G}}_{k}$ into a single
game.

###### Definition 7.3.

For all $k\geq 1$ consider the nested games ${\mathcal{G}}_{k}$ from
Definition 7.1 with initial state $u^{k}$ and target state $c_{0}^{k}$,
respectively. We construct a game ${\mathcal{G}}$ with initial state $s_{0}$,
target state $f$, Minimizer-controlled transitions
$s_{0}{\longrightarrow}u_{k}$ for all $k$, and Maximizer controlled
transitions $c_{0}^{k}{\longrightarrow}f$ for all $k$. The objective in
${\mathcal{G}}$ is $\mathtt{Reach}(\\{f\\})$.

###### Theorem 7.4.

Let ${\mathcal{G}}$ be the infinitely branching turn-based reachability game
from Definition 7.3.

  1. (1)

All states in ${\mathcal{G}}$ are almost sure winning. I.e., for every state
$s$ there exists a Maximizer strategy $\sigma$ such that
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s,\sigma,\pi}(\mathtt{Reach}(\\{f\\}))=1$.

  2. (2)

For each Maximizer strategy $\sigma$ with a step counter plus a private finite
memory we have

$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(\\{f\\}))=0.$

I.e., for any $\varepsilon<1$ there does not exist any $\varepsilon$-optimal
step counter plus finite private memory Maximizer strategy $\sigma$ from state
$s_{0}$ in ${\mathcal{G}}$.

###### Proof.

Towards Item 1, every state in ${\mathcal{G}}_{k}$ is almost sure winning by
Lemma 7.2(1). Thus, after the first step $s_{0}{\longrightarrow}u^{k}$ into
some game ${\mathcal{G}}_{k}$, Maximizer just needs to play the respective
almost sure winning strategy in ${\mathcal{G}}_{k}$.

Towards Item 2, consider a Maximizer strategy $\sigma$ with a step counter and
a finite memory with some number of modes $k\in\mathbb{N}$. Then, by Lemma
7.2(2), for every $\delta>0$, Minimizer can choose a first step
$s_{0}{\longrightarrow}u^{k}$ into ${\mathcal{G}}_{k}$ and a strategy in
${\mathcal{G}}_{k}$ that upper-bounds Maximizer’s attainment to $\leq\delta$.
∎

##  8\. Conclusion

Our results show that infinite action sets for Minimizer make stochastic
reachability games much more difficult for Maximizer. In particular,
Proposition 1.1, the existence of positional $\varepsilon$-optimal Maximizer
strategies in concurrent games, no longer holds if Minimizer is allowed
infinite action sets. Even in turn-based reachability games with infinitely
branching Minimizer states, Maximizer strategies based on a step counter plus
arbitrary finite private memory are useless.

Moreover, our results highlight the differences between MDPs and 2-player
stochastic games w.r.t. the reachability objective. While Ornstein’s
construction (Ornstein, 1969) can turn $\varepsilon$-optimal positional
strategies into uniform ones in MDPs, this is not possible even in finitely
branching turn-based stochastic games. On the other hand, just 1 bit of public
memory is enough for uniformly $\varepsilon$-optimal strategies, even in
concurrent reachability games with finite action sets.

## References

  * (1)
  * Altman et al. (2007) E. Altman, K. Avrachenkov, N. Bonneau, Merouane M. Debbah, R. El-Azouzi, and D. Menasche. 2007.  Constrained stochastic games in wireless networks. In _IEEE global communications conference (GLOBECOM)_ , IEEE (Ed.). Washington.
  * Altman et al. (2005) E. Altman, K. Avrachenkov, R. Marquez, and G. B. Miller. 2005.  Zero-sum constrained stochastic games with independent state processes.  _Math. Methods Oper. Res._ 62, 3 (2005), 375–386.  https://doi.org/10.1007/s00186-005-0034-4
  * Aumann (1981) Robert J Aumann. 1981\.  Survey of repeated games.  _Essays in game theory and mathematical economics in honor of Oskar Morgenstern_ (1981).
  * Bacharach (2019) Michael Bacharach. 2019\.  _Economics and the Theory of Games_.  CRC Press.
  * Bertrand et al. (2017) N. Bertrand, B. Genest, and H. Gimbert. 2017.  Qualitative Determinacy and Decidability of Stochastic Games with Signals.  _J. ACM_ 64, 5 (2017), 33:1–33:48.  https://doi.org/10.1145/3107926
  * Billingsley (1995) Patrick Billingsley. 1995\.  _Probability and Measure_.  Wiley, New York, NY.  Third Edition.
  * Bouyer et al. (2016) P. Bouyer, N. Markey, M. Randour, A. Sangnier, and D. Stan. 2016.  Reachability in Networks of Register Protocols under Stochastic Schedulers. In _International Colloquium on Automata, Languages and Programming (ICALP)_ _(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 55)_. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 106:1–106:14.
  * Brázdil et al. (2011) Tomás Brázdil, Václav Brožek, Antonín Kučera, and Jan Obdrzálek. 2011\.  Qualitative Reachability in Stochastic BPA Games.  _Information and Computation_ 209 (2011).  Issue 8. http://arxiv.org/abs/1003.0118
  * Brázdil et al. (2014) T. Brázdil, S. Kiefer, A. Kučera, P. Novotný, and J.P. Katoen. 2014.  Zero-Reachability in Probabilistic Multi-Counter Automata. In _ACM/IEEE Symposium on Logic in Computer Science (LICS)_ (Vienna, Austria) _(CSL-LICS ’14)_. Association for Computing Machinery, New York, NY, USA, Article 22, 10 pages.
  * Bromwich (1955) T.J.I’A. Bromwich. 1955\.  _An Introduction to the Theory of Infinite Series_.  McMillan and Company, London.
  * Chen et al. (2013) T. Chen, V. Forejt, M. Kwiatkowska, D. Parker, and A. Simaitis. 2013.  PRISM-games: A model checker for stochastic multi-player games. In _International Conference on TOOLS and Algorithms for the Construction and Analysis of Systems_. Springer, 185–191.
  * Condon (1992) Anne Condon. 1992\.  The complexity of stochastic games.  _Information and Computation_ 96, 2 (1992), 203–224.  https://doi.org/10.1016/0890-5401(92)90048-K
  * D. and Ferguson (1968) D. and T. S. Ferguson. 1968\.  The Big Match.  _The Annals of Mathematical Statistics_ 39, 1 (1968), 159 – 163.  https://doi.org/10.1214/aoms/1177698513
  * de Alfaro and Henzinger (2001) L. de Alfaro and T. A. Henzinger. 2001.  Interface automata. In _International Symposium on Foundations of Software Engineering_. ACM, 109–120.  https://doi.org/10.1145/503209
  * de Alfaro et al. (1998) L. de Alfaro, T. A. Henzinger, and O. Kupferman. 1998\.  Concurrent Reachability Games. In _39th Annual Symposium on Foundations of Computer Science, FOCS ’98, November 8-11, 1998, Palo Alto, California, USA_. IEEE Computer Society, 564–575.  https://doi.org/10.1109/SFCS.1998.743507
  * Filar (1980) Jerzy Andrzej Filar. 1980\.  _Algorithms for solving some undiscounted stochastic games_.  Ph. D. Dissertation. University of Illinois at Chicago.
  * Filar (1981) Jerzy Andrzej Filar. 1981\.  Ordered field property for stochastic games when the player who controls transitions changes from state to state.  _Journal of Optimization Theory and Applications_ 34, 4 (1981), 503–515.
  * Flesch et al. (2021) J. Flesch, P. J. Herings, J. Maes, and A. Predtetchinski. 2021\.  Subgame Maxmin Strategies in Zero-Sum Stochastic Games with Tolerance Levels.  _Dynamic Games and Applications_ 11, 4 (2021), 704–737.
  * Flesch et al. (2020) J Flesch, A. Predtetchinski, and W. Sudderth. 2020\.  Positive zero-sum stochastic games with countable state and action spaces.  _Applied Mathematics and Optimization_ 82 (2020), 499–516.  Issue 2.
  * Flesch et al. (2018) J. Flesch, A. Predtetchinski, and W. D. Sudderth. 2018\.  Characterization and simplification of optimal strategies in positive stochastic games.  _Journal of Applied Probability_ 55, 3 (2018), 728–741.
  * Fristedt et al. (1995) Bert Fristedt, Stephan K. Lapic, and William D. Sudderth. 1995\.  The Big Match on the Integers. In _New Trends in Dynamic Games and Applications_ _(Annals of the International Society of Dynamic Games)_ , Olsder G.J. (Ed.). Birkhäuser Boston.
  * Gillette (1958) D. Gillette. 1958\.  stochastic games with zero stop robabilities.  In _Contributions to the Theory of Games (AM-39), Volume III_. Princeton University Press, 179–188.  https://doi.org/10.1515/9781400882151-011
  * Gimbert and Horn (2010) H. Gimbert and F. Horn. 2010.  Solving Simple Stochastic Tail Games. In _Annual ACM-SIAM Symposium on Discrete Algorithms_. 847–862.  https://doi.org/10.1137/1.9781611973075
  * Hansen et al. (2018) K.A. Hansen, R. Ibsen-Jensen, and A. Neyman. 2018\.  The Big Match with a Clock and a Bit of Memory. In _Economics and Computation (EC)_. Association for Computing Machinery, New York, NY, USA, 149–50.  https://doi.org/10.1145/3219166.3219198
  * Jaskiewicz and Nowak (2011) A. Jaskiewicz and A. S. Nowak. 2011.  Stochastic Games with Unbounded Payoffs: Applications to Robust Control in Economics.  _Dynamic Games and Applications_ 1, 2 (2011), 253–279.  https://doi.org/10.1007/s13235-011-0013-8
  * Kalai (1990) E. Kalai. 1990.  Bounded Rationality and Strategic Complexity in Repeated Games.  In _Game Theory and Applications_ , T. Ichiishi, A. Neyman, and Y. Tauman (Eds.). Academic Press, San Diego, 131–157.  https://doi.org/10.1016/B978-0-12-370182-4.50010-6
  * Kiefer et al. (2019) Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke. 2019.  Büchi Objectives in Countable MDPs. In _International Colloquium on Automata, Languages and Programming (ICALP)_ _(LIPIcs, Vol. 132)_. 119:1–119:14.  https://doi.org/10.4230/LIPIcs.ICALP.2019.119 Full version at https://arxiv.org/abs/1904.11573.
  * Kiefer et al. (2020a) Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke. 2020a.  Strategy Complexity of Parity Objectives in Countable MDPs. In _International Conference on Concurrency Theory (CONCUR)_. 7:1–:17.  https://doi.org/10.4230/LIPIcs.CONCUR.2020.7
  * Kiefer et al. (2020b) Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, Patrick Totzke, and Dominik Wojtczak. 2020b.  How to play in infinite MDPs (Invited Talk). In _International Colloquium on Automata, Languages and Programming (ICALP)_. 3:1–3:18.  https://doi.org/10.4230/LIPIcs.ICALP.2020.3
  * Kiefer et al. (2017a) Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Dominik Wojtczak. 2017a.  On strong determinacy of countable stochastic games. In _ACM/IEEE Symposium on Logic in Computer Science (LICS)_. IEEE Computer Society, 1–12.  https://doi.org/10.1109/LICS.2017.8005134
  * Kiefer et al. (2017b) Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Dominik Wojtczak. 2017b.  On Strong Determinacy of Countable Stochastic Games. In _ACM/IEEE Symposium on Logic in Computer Science (LICS)_.  https://doi.org/10.1109/LICS.2017.8005134
  * Kiefer et al. (2017c) Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Dominik Wojtczak. 2017c.  Parity Objectives in Countable MDPs. In _ACM/IEEE Symposium on Logic in Computer Science (LICS)_.  https://doi.org/10.1109/LICS.2017.8005100
  * Kumar and Shiau (1981) P. R. Kumar and T. H. Shiau. 1981.  Existence of Value and Randomized Strategies in Zero-Sum Discrete-Time Stochastic Dynamic Games.  _SIAM Journal on Control and Optimization_ 19, 5 (1981), 617–634.  https://doi.org/10.1137/0319039
  * Kučera (2011) Antonín Kučera. 2011\.  Turn-Based Stochastic Games.  In _Lectures in Game Theory for Computer Scientists_ , Krzysztof R. Apt and Erich Grädel (Eds.). Cambridge University Press, 146–184.  https://doi.org/10.1017/CBO9780511973468.006
  * Laraki et al. (2013) R. Laraki, A. P. Maitra, and W. D. Sudderth. 2013.  Two-Person Zero-Sum Stochastic Games with Semicontinuous Payoff.  _Dynamic Games and Applications_ 3, 2 (2013), 162–171.
  * Maitra and Sudderth (1998) A. Maitra and W. Sudderth. 1998.  Finitely Additive Stochastic Games with Borel Measurable Payoffs.  _International Journal of Game Theory_ 27, 2 (jul 1998), 257–267.  https://doi.org/10.1007/s001820050071
  * Maitra and Sudderth (1996) Ashok P. Maitra and William D. Sudderth. 1996.  _Discrete Gambling and Stochastic Games_.  Springer-Verlag.
  * Maitra and Sudderth (2007) Ashok P. Maitra and William D. Sudderth. 2007.  Subgame-Perfect Equilibria for Stochastic Games.  _Mathematics of Operations Research_ 32, 3 (2007), 711–722.  https://doi.org/10.1287/moor.1070.0264
  * Martin (1998) Donald A. Martin. 1998\.  The determinacy of Blackwell games.  _Journal of Symbolic Logic_ 63, 4 (1998), 1565–1581.  https://doi.org/10.2307/2586667
  * Neyman and Sorin (2003) Abraham Neyman and Sylvain Sorin. 2003.  _Stochastic Games and Applications_.  Springer, Dordrecht.  https://doi.org/10.1007/978-94-010-0189-2
  * Nowak (2005) A. Nowak. 2005.  _Advances in dynamic games : applications to economics, finance, optimization, and stochastic control_.  Birkhaeuser, Boston.
  * Nowak and Raghavan (1991) A.S. Nowak and T.E.S. Raghavan. 1991.  Positive Stochastic Games and a Theorem of Ornstein.  In _Stochastic Games And Related Topics_ , T.E.S Raghavan, T.S. Ferguson, T. Parthasarathy, and O.J. Vrieze (Eds.). Theory and Decision Library (Game Theory, Mathematical Programming and Operations Research), Vol. 7. Springer.
  * Ornstein (1969) Donald Ornstein. 1969\.  On the Existence of Stationary Optimal Strategies.  _Proc. Amer. Math. Soc._ 20, 2 (1969), 563–569.  https://doi.org/10.2307/2035700
  * Puterman (1994) Martin L. Puterman. 1994\.  _Markov Decision Processes: Discrete Stochastic Dynamic Programming_ (1st ed.).  John Wiley & Sons, Inc., New York, NY, USA.
  * Raghaven et al. (2012) T. Raghaven, T.S. Ferguson, T. Parthasarathy, and O. Vrieze. 2012.  _Stochastic games and related topics: in honor of Professor LS Shapley_. Vol. 7.  Springer Science & Business Media.
  * Secchi (1997) Piercesare Secchi. 1997\.  Stationary Strategies for Recursive Games.  _Math. Oper. Res._ 22, 2 (1997), 494–512.  https://doi.org/10.1287/moor.22.2.494
  * Shapley (1953) Lloyd S Shapley. 1953\.  Stochastic games.  _Proceedings of the National Academy of Sciences_ 39, 10 (1953), 1095–1100.
  * Solan and Vieille (2015) Eilon Solan and Nicolas Vieille. 2015.  Stochastic games.  _Proceedings of the National Academy of Sciences_ 112, 45 (2015), 13743–13746.  https://doi.org/10.1073/pnas.1513508112 arXiv:https://www.pnas.org/content/112/45/13743.full.pdf
  * Sorin (1992) Sylvain Sorin. 1992\.  Repeated games with complete information.  In _Handbook of Game Theory with Economic Applications_ , R.J. Aumann and S. Hart (Eds.). Handbook of Game Theory with Economic Applications, Vol. 1. Elsevier, Chapter 4, 71–107.  https://ideas.repec.org/h/eee/gamchp/1-04.html
  * Svoreňová and Kwiatkowska (2016) Mária Svoreňová and Marta Kwiatkowska. 2016.  Quantitative verification and strategy synthesis for stochastic games.  _European Journal of Control_ 30 (2016), 15–30.
  * Vrieze et al. (1983) O.J. Vrieze, , S. H. Tijs, T. E. S. Raghavan, and J. A. Filar. 1983.  A finite algorithm for the switching control stochastic game.  _Operations-Research-Spektrum_ 5, 1 (1983), 15–24.  https://doi.org/10.1007/BF01720283
  * Vrieze (1987) O.J. Vrieze. 1987\.  _Stochastic Games with Finite State and Action Spaces_.  Centrum voor Wiskunde en Informatica.  https://books.google.fr/books?id=59tbPwAACAAJ

##  Appendix A Technical Lemmas

The following inequality is due to Weierstrass.

###### Proposition A.1 ((Bromwich, 1955, p. 104-105)).

Given an infinite sequence of real numbers $a_{n}$ with $0\leq a_{n}\leq 1$,

$\prod_{k=1}^{n}(1-a_{k})\leq\frac{1}{1+\sum_{k=1}^{n}a_{k}}$

###### Proof.

By induction on $n$. In the base case of $n=1$ we have
$(1-a_{1})(1+a_{1})=(1-a_{1}^{2})\leq 1$ as required.

For the induction hypothesis we assume

$\prod_{k=1}^{n}(1-a_{k})\left(1+\sum_{k=1}^{n}a_{k}\right)\leq 1$

For the induction step we have

$\displaystyle\prod_{k=1}^{n+1}(1-a_{k})\left(1+\sum_{k=1}^{n+1}a_{k}\right)$
$\displaystyle=(1-a_{n+1})\prod_{k=1}^{n}(1-a_{k})\left(\left(1+\sum_{k=1}^{n}a_{k}\right)+a_{n+1}\right)$
$\displaystyle\leq(1-a_{n+1})\left(1+a_{n+1}\prod_{k=1}^{n}(1-a_{k})\right)$
$\displaystyle\leq(1-a_{n+1})(1+a_{n+1})$ $\displaystyle=(1-a_{n+1}^{2})\leq
1$

∎

###### Proposition A.2.

Given an infinite sequence of real numbers $a_{n}$ with $0\leq a_{n}<1$, we
have

$\prod_{n=1}^{\infty}(1-a_{n})>0\quad\Leftrightarrow\quad\sum_{n=1}^{\infty}a_{n}<\infty.$

and the “$\Rightarrow$” implication holds even for the weaker assumption
$0\leq a_{n}\leq 1$.

###### Proof.

If $a_{n}=1$ for any $n$ then the “$\Rightarrow$” implication is vacuously
true, but the “$\Leftarrow$” implication does not hold in general. In the
following we assume $0\leq a_{n}<1$.

In the case where $a_{n}$ does not converge to zero, the property is trivial.
In the case where $a_{n}\rightarrow 0$, it is shown by taking the logarithm of
the product and using the limit comparison test as follows.

Taking the logarithm of the product gives the series

$\sum_{n=1}^{\infty}\ln(1-a_{n})$

whose convergence (to a finite number $\leq 0$) is equivalent to the
positivity of the product. It is also equivalent to the convergence (to a
number $\geq 0$) of its negation $\sum_{n=1}^{\infty}-\ln(1-a_{n})$. But
observe that (by L’Hôpital’s rule)

$\lim_{x\rightarrow 0}\frac{-\ln(1-x)}{x}=1.$

Since $a_{n}\rightarrow 0$ we have

$\lim_{n\rightarrow\infty}\frac{-\ln(1-a_{n})}{a_{n}}=1.$

By the limit comparison test, the series $\sum_{n=1}^{\infty}-\ln(1-a_{n})$
converges if and only if the series $\sum_{n=1}^{\infty}a_{n}$ converges. ∎

###### Proposition A.3.

Given an infinite sequence of real numbers $a_{n}$ with $0\leq a_{n}\leq 1$,

$\prod_{n=1}^{\infty}a_{n}>0\quad\Rightarrow\quad\forall\varepsilon>0\,\exists
N.\,\prod_{n=N}^{\infty}a_{n}\geq(1-\varepsilon).$

###### Proof.

If $a_{n}=0$ for any $n$ then the property is vacuously true. In the following
we assume $a_{n}>0$. Since $\prod_{n=1}^{\infty}a_{n}>0$, by taking the
logarithm we obtain $\sum_{n=1}^{\infty}\ln(a_{n})>-\infty$. Thus for every
$\delta>0$ there exists an $N$ s.t.
$\sum_{n=N}^{\infty}\ln(a_{n})\geq-\delta$. By exponentiation we obtain
$\prod_{n=N}^{\infty}a_{n}\geq\exp(-\delta)$. By picking
$\delta=-\ln(1-\varepsilon)$ the result follows. ∎

##  Appendix B Proofs from Section 3

The following auxiliary lemma is essentially known; see, e.g., (Maitra and
Sudderth, 1996, Section 7.7). We extend it slightly to fit our purposes, i.e.,
for the proof of Theorem 3.5 below.

###### Lemma B.1.

For any concurrent game with state space $S$ and finite action sets and
reachability objective $\mathtt{Reach}(T)$, for any finite set $S_{0}\subseteq
S$ of initial states, and for any $\varepsilon>0$, there are a memoryless
strategy $\sigma$ and a finite set of states $R\subseteq S$ such that for all
$s_{0}\in S_{0}$

$\inf_{\pi\in\Pi}{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Reach}_{R}(T))\
\geq\ {\mathtt{val}_{\mathtt{Reach}(T)}(s_{0})}-\varepsilon\,,$

where $\mathtt{Reach}_{R}(T)$ denotes the objective of visiting $T$ while
remaining in $R$ before visiting $T$. If the game is turn-based and finitely
branching, there is a deterministic (i.e., MD) such strategy $\sigma$.

###### Proof.

It is shown in (Maitra and Sudderth, 1996, Section 7.7) that for all $s\in S$

(3) $\lim_{n\to\infty}{\mathtt{val}_{\mathtt{Reach}_{n}(T)}(s)}\ =\
{\mathtt{val}_{\mathtt{Reach}(T)}(s)}\,,$

where $\mathtt{Reach}_{n}(T)$ denotes the objective of visiting $T$ within at
most $n$ steps.

To achieve the uniformity (across the set $S_{0}$ of initial states) required
by the statement of the lemma, we add a fresh “random” state (i.e., a state in
which each player has only a single action available) that branches uniformly
at random to a state in $S_{0}$. Call this state $\hat{s}_{0}$. The value of
$\hat{s}_{0}$ is the arithmetic average of the values of the states in
$S_{0}$. It follows that every $\varepsilon/|S_{0}|$-optimal memoryless
strategy for Maximizer in $\hat{s}_{0}$ must be $\varepsilon$-optimal in every
state in $S_{0}$. So it suffices to prove the statement of the lemma under the
assumption that $S_{0}$ is a singleton, say $S_{0}=\\{s_{0}\\}$.

Fix $\varepsilon>0$, and let
$\varepsilon^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\varepsilon/4$.
By (3) there is $n$ such that
${\mathtt{val}_{\mathtt{Reach}_{n}(T)}(s_{0})}={\mathtt{val}_{\mathtt{Reach}(T)}(s_{0})}-\varepsilon^{\prime}$.
Let $\sigma$ be a Maximizer strategy such that

$\inf_{\pi\in\Pi}{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Reach}_{n}(T))\
\geq\ {\mathtt{val}_{\mathtt{Reach}(T)}(s_{0})}-2\varepsilon^{\prime}\,.$

Since for each state the sets of actions available to the players is finite,
there is a finite set $R\subseteq S$ such that for all Minimizer strategies
$\pi$ the play, within $n$ steps, remains in $R$ with probability at least
$1-\varepsilon^{\prime}$. Indeed, we show by induction that for all $m\geq 0$
there is a finite set $R_{m}\subseteq S$ such that for all Maximizer and all
Minimizer strategies, the play, within $m$ steps, remains in $R_{m}$ with
probability at least $1-\frac{m}{n}\varepsilon^{\prime}$. For the base case,
$m=0$, take $R_{0}=\\{s_{0}\\}$. For the inductive step, suppose this is true
for $m\geq 0$. Then define
$R_{m+1}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}R_{m}\cup\bigcup\\{S(s,a,b)\mid
s\in R_{m},\ a\in A(s),\ b\in B(s)\\}$, where $S(s,a,b)\subseteq S$ is defined
to be a finite set of states such that $p(s,a,b)(S(s,a,b))\geq
1-\frac{1}{n}\varepsilon^{\prime}$ (recall from the definition of concurrent
games that $p(s,a,b)\in\mathcal{D}(S)$ is the probability distribution over
successor states of $s$ when the players choose actions $a,b$). This makes the
inductive claim true for $m+1$.

It follows that

$\inf_{\pi\in\Pi}{\mathcal{P}}_{s_{0},\sigma,\pi}(\mathtt{Reach}_{R}(T))\geq{\mathtt{val}_{\mathtt{Reach}(T)}(s_{0})}-3\varepsilon^{\prime}$

(note that the restriction on the time horizon, $n$, has been lifted here).
The restriction of the objective to the (finitely many) states in $R$ means
that we have effectively another reachability game. It is known (see, e.g.,
(Secchi, 1997, Corollary 3.9)) that for concurrent games with finite action
sets and reachability objective, Maximizer has a memoryless
$\varepsilon^{\prime}$-optimal strategy. In turn-based games with finitely
many states, he even has an MD optimal strategy (Condon, 1992). So Maximizer
has a memoryless (in the turn-based case: MD) strategy $\sigma^{\prime}$ so
that

$\displaystyle\inf_{\pi\in\Pi}{\mathcal{P}}_{s_{0},\sigma^{\prime},\pi}(\mathtt{Reach}_{R}(T))\
$ $\displaystyle\geq\
{\mathtt{val}_{\mathtt{Reach}(T)}(s_{0})}-4\varepsilon^{\prime}$ ∎
$\displaystyle=\ {\mathtt{val}_{\mathtt{Reach}(T)}(s_{0})}-\varepsilon\,.$

See 3.5

###### Proof.

Denote the game by $\hat{\mathcal{G}}$, over state space $S$. It is convenient
to describe the 1-bit strategy in terms of a game ${\mathcal{G}}$ with state
space $S\times\\{0,1\\}$, where the second component ($0$ or $1$) reflects the
current memory state of Maximizer. Accordingly, we think of the state space of
${\mathcal{G}}$ as organized in two _layers_ , the “inner” and the “outer”
layer, with the memory state being $0$ and $1$, respectively. In these terms,
our goal is to construct, for the layered game ${\mathcal{G}}$, a _memoryless_
strategy for Maximizer. Upon reaching the target, the memory state is
irrelevant, so for notational simplicity we denote the objective as
$\mathtt{Reach}(T)$, also in the layered game ${\mathcal{G}}$ (instead of
$\mathtt{Reach}(T\times\\{0,1\\})$). The current state of the layered game is
known to both players (to Minimizer in particular); this corresponds to the
(1-bit) memory being public in the original game $\hat{\mathcal{G}}$: at each
point in the game, Minimizer knows the distribution of actions that Maximizer
is about to play. Notice that the values of states $(s,0)$ and $(s,1)$ in
${\mathcal{G}}$ are equal to the value of $s$ in $\hat{\mathcal{G}}$; this is
because the definition of value does not impose restrictions on the memory of
strategies and so the players could, in $\hat{\mathcal{G}}$, simulate the two
layers of ${\mathcal{G}}$ in their memory if that were advantageous.

In general Maximizer does not have uniform $\varepsilon$-optimal memoryless
strategies in reachability games; cf. Theorem 3.4. So our construction will
exploit the special structure in the layered game, namely, the symmetry of the
two layers. The memoryless Maximizer strategy we construct will be
$\varepsilon$-optimal from each state $(s,0)$ in the inner layer, but not
necessarily from the states in the outer layer.

As building blocks we use the non-uniform memoryless strategies we get from
Lemma B.1; in the turn-based finitely branching case they are even MD. We
combine them by “plastering” the state space (of the layered game). This is
inspired by Ornstein’s construction (Ornstein, 1969); see (Kiefer et al.,
2020b, Section 3.2) for a recent description.111 These papers consider MDPs,
i.e., Minimizer is passive. In MDPs Maximizer has uniform
$\varepsilon$-optimal MD strategies (even without layering the system).

In the general concurrent case, a memoryless strategy prescribes for each
state $(s,i)$ a probability distribution over Maximizer’s actions. We define a
memoryless strategy by successively _fixing_ such distributions in more and
more states. Technically, one can _fix_ a state $s$ by replacing the actions
$A(s)$ available to Maximizer by a single action which is a convex combination
over $A(s)$. Visually, we “plaster” the whole state space by the fixings. This
is in general an infinite (but countable) process; it defines a memoryless
strategy for Maximizer in the limit.

In the turn-based and finitely branching case, an MD strategy prescribes one
outgoing transition for each Maximizer state. Accordingly, _fixing_ a
Maximizer state means restricting the outgoing transitions to a single such
outgoing transition. The plastering proceeds similarly as in the concurrent
case; it defines an MD strategy for Maximizer in the limit.

Put the states of $\hat{\mathcal{G}}$ in some order, i.e.,
$s_{1},s_{2},\ldots$ with $S=\\{s_{1},s_{2},\ldots\\}$. The plastering
proceeds in _rounds_. In round $i\geq 1$ we fix the states in
$S_{i}[0]\times\\{0\\}$ and in $S_{i}[1]\times\\{1\\}$, where
$S_{1}[0],S_{2}[0],\ldots\subseteq S$ are pairwise disjoint and
$S_{1}[1],S_{2}[1],\ldots\subseteq S$ are pairwise disjoint; see Figure 7 for
an example of sets $S_{i}[0]$ and $S_{i}[1]$ in a two- layers game. Define
$F_{i}[0]\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcup_{j\leq
i}S_{j}[0]$ and
$F_{i}[1]\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcup_{j\leq
i}S_{j}[1]$. So $F_{i}[0]\times\\{0\\}$ and $F_{i}[1]\times\\{1\\}$ are the
states that have been fixed by the end of round $i$. We will keep an invariant
$F_{i}[0]\subseteq F_{i}[1]\subseteq F_{i+1}[0]$.

Let ${\mathcal{G}}_{i}$ be the game obtained from ${\mathcal{G}}$ after the
fixings of the first $i-1$ rounds (with ${\mathcal{G}}_{1}={\mathcal{G}}$).
Define

$S_{i}[0]\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}(\\{s_{i}\\}\cup
S_{i-1}[1])\setminus F_{i-1}[0]$

(and $S_{1}[0]\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{s_{1}\\}$),
the set of states to be fixed in round $i$. In particular, round $i$
guarantees that states $(s,0)$ whose “outer sibling” $(s,1)$ has been fixed
previously are also fixed, ensuring $F_{i-1}[1]\subseteq F_{i}[0]$. Note also
that $\bigcup_{j=1}^{\infty}S_{j}[0]=\bigcup_{j=1}^{\infty}S_{j}[1]=S$. The
set $S_{i}[1]$ will be defined below.

outer layerinner
layer$s_{1}$$s_{1}$$S_{1}[0]$$s_{3}$$s_{3}$$S_{1}[1]$$s_{2}$$s_{2}$$S_{2}[0]$$s_{4}$$s_{4}$$S_{2}[1]$$S_{3}[0]$$s_{5}$$s_{5}$$S_{3}[1]$$S_{4}[0]$$s_{6}$$s_{6}$$S_{6}[1]$$S_{6}[0]$
Figure 7. Example of sets $S_{i}[0]$ and $S_{i}[1]$ in the two layers of
${\mathcal{G}}$, where the outer and inner layers are $S\times\\{1\\}$ and
$S\times\\{0\\}$, respectively.

In round $i$ we fix the states in
$(S_{i}[0]\times\\{0\\})\cup(S_{i}[1]\times\\{1\\})$ in such a way that

  1. (A)

starting from any $(s,0)$ with $s\in S_{i}[0]$, the (infimum over all
Minimizer strategies $\pi$) probability of reaching $T$ using only fixed
states is not much less than the value
${\mathtt{val}_{{\mathcal{G}}_{i},\mathtt{Reach}(T)}((s,0))}$; and

  2. (B)

for all states $(s,0)\in S\times\\{0\\}$ in the inner layer, the value
${\mathtt{val}_{{\mathcal{G}}_{i+1},\mathtt{Reach}(T)}((s,0))}$ is almost as
high as ${\mathtt{val}_{{\mathcal{G}}_{i},\mathtt{Reach}(T)}((s,0))}$.

The purpose of goal (A) is to guarantee good progress towards the target when
starting from any state $(s,0)$ in $S_{i}[0]\times\\{0\\}$. The purpose of
goal (B) is to avoid fixings that would cause damage to the values of other
states in the inner layer.

We want to define the fixings in round $i$. First we define an auxiliary game
$\bar{\mathcal{G}}_{i}$ with state space
$\bar{S}_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}(F_{i}[0]\times\\{0,1\\})\cup(S\setminus
F_{i}[0])$. Game $\bar{\mathcal{G}}_{i}$ is obtained from ${\mathcal{G}}_{i}$
by collapsing, for all $s\in S\setminus F_{i}[0]$, the siblings $(s,0),(s,1)$
(neither of which have been fixed yet) to a single state $s$. See Figure 8.
The game $\bar{\mathcal{G}}_{i}$ inherits the fixings from
${\mathcal{G}}_{i}$. The values remain equal; in particular, for $s\in
S\setminus F_{i}[0]$, the values of $(s,0)$ and $(s,1)$ in ${\mathcal{G}}_{i}$
and the value of $s$ in $\bar{\mathcal{G}}_{i}$ are all equal.

outer layerinner
layer$s_{1}$$s_{1}$$S_{1}[0]$$s_{3}$$s_{3}$$S_{1}[1]$$s_{2}$$s_{2}$$S_{2}[0]$$s_{4}$$s_{4}$$S_{2}[1]$$S_{3}[0]$$s_{5}$$s_{6}$$S\setminus
F_{3}[0]$ Figure 8. Example of a game $\bar{\mathcal{G}}_{3}$.

Let $\varepsilon_{i}>0$. We apply Lemma B.1 to $\bar{\mathcal{G}}_{i}$ with
set of initial states $S_{i}[0]\times\\{0\\}$. So Maximizer has a memoryless
strategy $\sigma_{i}$ for $\bar{\mathcal{G}}_{i}$ and a finite set of states
$R\subseteq\bar{S}_{i}$ such that for all $s\in S_{i}[0]$ we have
$\inf_{\pi}{\mathcal{P}}_{\bar{\mathcal{G}}_{i},(s,0),\sigma_{i},\pi}(\mathtt{Reach}_{R}(T))\geq{\mathtt{val}_{{\mathcal{G}}_{i},\mathtt{Reach}(T)}((s,0))}-\varepsilon_{i}$.

Now we carry the strategy $\sigma_{i}$ from $\bar{\mathcal{G}}_{i}$ to
${\mathcal{G}}_{i}$ by suitably adapting it (see below). Then we obtain
${\mathcal{G}}_{i+1}$ from ${\mathcal{G}}_{i}$ by fixing (the adapted version
of) $\sigma_{i}$ in ${\mathcal{G}}_{i}$.

More precisely, we adapt $\sigma_{i}$ to ${\mathcal{G}}_{i}$ by treating
states $s\in S\setminus F_{i}[0]$ in $\bar{\mathcal{G}}_{i}$ as states in the
_outer_ layer $(s,1)$ of ${\mathcal{G}}_{i}$. In particular, transitions that
in $\bar{\mathcal{G}}_{i}$ go from a state $(s,j)\in F_{i}[0]\times\\{0,1\\}$
to a state $s^{\prime}\in S\setminus F_{i}[0]$ (or vice versa, respectively),
go in ${\mathcal{G}}_{i}$ from $(s,j)$ to $(s^{\prime},1)$ (or vice versa,
respectively). Accordingly, define
$S_{i}[1]\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}(S_{i}[0]\setminus
F_{i-1}[1])\cup((S\setminus F_{i}[0])\cap R)$ (this ensures $F_{i}[0]\subseteq
F_{i}[1]$), and obtain ${\mathcal{G}}_{i+1}$ from ${\mathcal{G}}_{i}$ by
fixing the adapted version of $\sigma_{i}$ in
$(S_{i}[0]\times\\{0\\})\cup(S_{i}[1]\times\\{1\\})$. This yields, for all
$s\in S_{i}[0]$,

(4)
$\displaystyle\inf_{\sigma,\pi}{\mathcal{P}}_{{\mathcal{G}}_{i+1},(s,0),\sigma,\pi}(\mathtt{Reach}_{(F_{i}[0]\times\\{0\\})\cup(F_{i}[1]\times\\{1\\})}(T))\quad\geq\quad{\mathtt{val}_{{\mathcal{G}}_{i},\mathtt{Reach}(T)}((s,0))}-\varepsilon_{i},$

achieving goal (A) above. Notice that the fixings in ${\mathcal{G}}_{i+1}$
“lock in” a good attainment from $S_{i}[0]\times\\{0\\}$, regardless of the
Maximizer strategy $\sigma$. Now we extend (4) to achieve goal (B) from above:
for all $s\in S$ we have

(5) ${\mathtt{val}_{{\mathcal{G}}_{i+1},\mathtt{Reach}(T)}((s,0))}\ \geq\
{\mathtt{val}_{{\mathcal{G}}_{i},\mathtt{Reach}(T)}((s,0))}-\varepsilon_{i}\,.$

Indeed, consider any Maximizer strategy $\sigma$ in ${\mathcal{G}}_{i}$ from
any $(s,0)$. Without loss of generality we can assume that $\sigma$ is such
that the play enters the outer layer only (if at all) after having entered
$F_{i}[0]\times\\{0\\}$. Now change $\sigma$ to a strategy $\sigma^{\prime}$
in ${\mathcal{G}}_{i+1}$ so that as soon as $F_{i}[0]\times\\{0\\}$ is
entered, $\sigma^{\prime}$ respects the fixings (and plays arbitrarily
afterwards). By (4) this decreases the (infimum over Minimizer strategies
$\pi$) probability by at most $\varepsilon_{i}$. Thus,

$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i+1},(s,0),\sigma^{\prime},\pi}(\mathtt{Reach}(T))\
\geq\
\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i},(s,0),\sigma,\pi}(\mathtt{Reach}(T))-\varepsilon_{i}\,.$

Taking the supremum over strategies $\sigma$ in ${\mathcal{G}}_{i}$ yields
(5).

For any $\varepsilon>0$ choose
$\varepsilon_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}2^{-i}\varepsilon$;
thus, $\sum_{i\geq 1}\varepsilon_{i}=\varepsilon$. Let $\sigma$ be the
memoryless strategy that respects all fixings in all ${\mathcal{G}}_{i}$.
Then, by (5), for all $s\in S$ we have

$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},(s,0),\sigma,\pi}(\mathtt{Reach}(T))\
\geq\
{\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(T)}((s,0))}-\sum_{i=1}^{\infty}\varepsilon_{i}\,,$

so $\sigma$ is $\varepsilon$-optimal in ${\mathcal{G}}$ from all $(s,0)$.
Hence, the corresponding public 1-bit memory strategy (with initial memory
state $0$, corresponding to the inner layer) is uniform $\varepsilon$-optimal
in $\hat{\mathcal{G}}$. ∎

See 3.6

###### Proof.

Let ${\mathcal{G}}$ be a concurrent game with state space $S$, and let
$\mathtt{Reach}(T)$ be a reachability objective.

Without restriction, we can assume that all states in $S$ admit an almost
surely winning strategy. Otherwise, we consider the subgame
${\mathcal{G}}^{\prime}$ obtained by restricting ${\mathcal{G}}$ to
$S^{\prime}$, where $S^{\prime}\subseteq S$ is the subset of states that admit
an almost surely winning strategy in ${\mathcal{G}}$. Then all states in
$S^{\prime}$ admit an almost surely winning strategy in
${\mathcal{G}}^{\prime}$. (Note that this construction of
${\mathcal{G}}^{\prime}$ would not work if we replaced the “almost surely
winning” condition by the weaker condition of “having value $1$”.)

In order to construct a memoryless Maximizer strategy $\hat{\sigma}$ that wins
almost surely from every state, we inductively define a sequence of modified
games ${\mathcal{G}}_{i}$ in which the strategy of Maximizer is already fixed
on a finite subset of the state space, and where all states in
${\mathcal{G}}_{i}$ still admit an almost surely winning strategy. Fix an
enumeration $s_{1},s_{2},\ldots$ of $S$ in which very state $s$ appears
_infinitely often_.

For the base base we have
${\mathcal{G}}_{0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathcal{G}}$
and the property holds by our assumption on ${\mathcal{G}}$.

Given ${\mathcal{G}}_{i}$ we construct ${\mathcal{G}}_{i+1}$ as follows. We
use Lemma B.1 to get a memoryless strategy $\sigma_{i}$ and a finite subset of
states $R_{i}$ s.t.
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i},s_{i},\sigma_{i},\pi}(\mathtt{Reach}_{R_{i}}(T))\geq{\mathtt{val}_{{\mathcal{G}}_{i}}(s_{i})}-2^{-i}=1-2^{-i}$.

Let ${\mathcal{G}}_{i}^{\prime}$ be the subgame of ${\mathcal{G}}_{i}$ that is
restricted to $R_{i}$. Let
$R_{i}^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{s\in
R_{i}\mid\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i}^{\prime},s,\sigma_{i},\pi}(\mathtt{Reach}_{R_{i}}(T))>0\\}$
be the subset of states in $R_{i}$ where $\sigma_{i}$ has strictly positive
attainment in ${\mathcal{G}}_{i}^{\prime}$. In particular, we have $s_{i}\in
R_{i}^{\prime}$ for all $i\geq 1$. Since $R_{i}^{\prime}$ is finite, we have

$\lambda_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\min_{s\in
R_{i}^{\prime}}\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i}^{\prime},s,\sigma_{i},\pi}(\mathtt{Reach}_{R_{i}}(T))>0.$

We now construct ${\mathcal{G}}_{i+1}$ by modifying ${\mathcal{G}}_{i}$ as
follows. For every state $s\in R_{i}^{\prime}$ we fix Maximizer’s (randomized)
action according to $\sigma_{i}$. Then
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i+1},s_{i},\sigma,\pi}(\mathtt{Reach}(T))\geq
1-2^{-i}$ and
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}_{i+1},s,\sigma,\pi}(\mathtt{Reach}_{R_{i}^{\prime}}(T))\geq\lambda_{i}$
for all $s\in R_{i}^{\prime}$ and all $\sigma\in\Sigma_{{\mathcal{G}}_{i+1}}$
(and thus in particular for the strategy $\hat{\sigma}$ that we will
construct).

Now we show that in ${\mathcal{G}}_{i+1}$ all states $s$ still have an almost
surely winning strategy.

Let $\sigma$ be an a.s. winning Maximizer strategy from $s$ in
${\mathcal{G}}_{i}$, which exists by the induction hypothesis. We now define
an a.s. winning Maximizer strategy $\sigma^{\prime}$ from $s$ in
${\mathcal{G}}_{i+1}$.

If the game does not enter $R_{i}^{\prime}$ then $\sigma^{\prime}$ plays
exactly as $\sigma$ (which is possible since outside $R_{i}^{\prime}$ no
Maximizer actions have been fixed). If the game enters $R_{i}^{\prime}$ then
it will reach the target within $R_{i}^{\prime}$ with probability
$\geq\lambda_{i}$. Moreover, if the game stays inside $R_{i}^{\prime}$ forever
then it will almost surely reach the target, since
$(1-\lambda_{i})^{\infty}=0$. Plays that do not stay inside $R_{i}^{\prime}$
then exit $R_{i}^{\prime}$ at some state $s^{\prime}\notin R_{i}^{\prime}$.
Then, from $s^{\prime}$, $\sigma^{\prime}$ plays an a.s. winning strategy
w.r.t. ${\mathcal{G}}_{i}$ (which exists by the induction hypothesis).

Now we show that $\sigma^{\prime}$ wins almost surely from $s$ in
${\mathcal{G}}_{i+1}$. The set of plays which visit $R_{i}^{\prime}$
infinitely often eventually reach the target (except for a nullset), since
$(1-\lambda_{i})^{\infty}=0$. The set of plays which visit $R_{i}^{\prime}$
only finitely often eventually forever play an a.s. winning strategy outside
of $R_{i}^{\prime}$ and thus (except for a nullset) also eventually reach the
target. Hence $\sigma^{\prime}$ almost surely wins from $s$ in
${\mathcal{G}}_{i+1}$.

Finally, we can construct the memoryless Maximizer strategy $\hat{\sigma}$.
Since our enumeration of the states $s_{1},s_{2},\dots$ contains every state
in $S$ and $s_{i}\in R_{i}^{\prime}$, in the limit of the games
${\mathcal{G}}_{\infty}$ all Maximizer choices are fixed. The memoryless
Maximizer strategy $\hat{\sigma}$ plays according to these fixed choices,
i.e., it plays like $\sigma_{i}$ at state $s_{i}$ for all $i\in\mathbb{N}$.

We obtain
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s_{i},\hat{\sigma},\pi}(\mathtt{Reach}(T))\geq\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s_{i},\sigma_{i},\pi}(\mathtt{Reach}(T))\geq
1-2^{-i}$ for all $i\in\mathbb{N}$. Let $s\in S$. Since $s=s_{i}$ holds for
infinitely many $i$, we obtain
$\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},s,\hat{\sigma},\pi}(\mathtt{Reach}(T))=1$
as required. ∎

###### Definition B.2.

We define a concurrent reachability game ${\mathcal{G}}$ with finite action
sets, initial state $s_{0}$ and target state $t$. At state $s_{0}$ both
players have only one action. The distribution $p(s_{0})$ over successor
states is defined as $p(s_{0})(s_{i}^{\prime})=\frac{1}{2^{i}}$ for all $i\geq
1$. At all states $s_{i}^{\prime}$ (where $i\geq 1$), Maximizer has only one
action, so $s_{i}^{\prime}$ is effectively Minimizer-controlled. At
$s_{i}^{\prime}$ she chooses between an action, say $a_{i}$, that leads with
probability $1-\frac{1}{2^{i}}$ to the target $t$ and with probability
$\frac{1}{2^{i}}$ to a losing sink state, and an action that leads to a state
$s_{1}^{\prime\prime}$. There are also states $s_{i}^{\prime\prime}$ for all
$i\geq 2$. At all states $s_{i}^{\prime\prime}$ (where $i\geq 1$), Minimizer
has only one action, so $s_{i}^{\prime\prime}$ is effectively Maximizer-
controlled. At $s_{i}^{\prime\prime}$ he chooses between an action that leads
to $s_{i+1}^{\prime\prime}$ and an action that leads with probability
$1-\frac{1}{2^{i}}$ to $t$ and with probability $\frac{1}{2^{i}}$ to a losing
sink state. The latter action is also called $a_{i}$, without risk of
confusion, because it is equivalent to Minimizer’s action $a_{i}$ at
$s_{i}^{\prime}$.

###### Proposition B.3.

There exists a concurrent reachability game ${\mathcal{G}}$ with finite action
sets, initial state $s_{0}$ and objective $\mathtt{Reach}(\\{t\\})$ as in
Definition B.2, such that

  1. (1)

Maximizer has an optimal strategy from $s_{0}$.

  2. (2)

Every randomized Maximizer strategy from $s_{0}$ that uses only a step counter
and finite private memory is not optimal.

###### Proof.

We have ${\mathtt{val}_{{\mathcal{G}}}(s_{i}^{\prime\prime})}=1$ for all $i$,
and so ${\mathtt{val}_{{\mathcal{G}}}(s_{i}^{\prime})}=1-\frac{1}{2^{i}}$ for
all $i$, and so
${\mathtt{val}_{{\mathcal{G}}}(s_{0})}=\sum_{i=1}^{\infty}\frac{1}{2^{i}}\cdot(1-\frac{1}{2^{i}})$.
(The latter series equals $\frac{2}{3}$, but that will not be needed.) It
follows that the only optimal Minimizer strategy chooses at $s_{i}^{\prime}$
(where $i\geq 1$) action $a_{i}$. Note that Maximizer does not make any
nontrivial choices if Minimizer plays her optimal strategy.

Towards Item 1, Maximizer’s optimal strategy $\sigma$ from $s_{0}$ is defined
as follows. In plays where the state $s_{1}^{\prime\prime}$ is not reached,
Maximizer does not make any decisions. If $s_{1}^{\prime\prime}$ is reached,
Maximizer considers the history of this play: If Minimizer chose the action
that leads from $s_{i}^{\prime}$ to $s_{1}^{\prime\prime}$ for some $i\geq 1$,
then Maximizer chooses actions that lead, from $s_{1}^{\prime\prime}$ via
states $s_{2}^{\prime\prime},\ldots,s_{i-1}^{\prime\prime}$ to state
$s_{i}^{\prime\prime}$ for the same $i$, and at state $s_{i}^{\prime\prime}$
he chooses action $a_{i}$. Note that in this way Maximizer takes the action
that Minimizer refused to take (although it would have been optimal for her)
at $s_{i}^{\prime}$. With this Maximizer strategy $\sigma$, for every
Minimizer strategy $\pi$, the probability to reach $t$ equals
${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(\\{t\\})=\sum_{i=1}^{\infty}\frac{1}{2^{i}}\cdot(1-\frac{1}{2^{i}})={\mathtt{val}_{{\mathcal{G}}}(s_{0})}$;
i.e., $\sigma$ is optimal.

Towards Item 2, we note that the step counter from $s_{0}$ is implicit in the
states of ${\mathcal{G}}$ (except in the target $t$ and the losing sink
state), and thus superfluous for Maximizer strategies. Hence it suffices to
prove the property for Maximizer strategies with finite memory. Let $\sigma$
be an FR Maximizer strategy with finitely many memory modes $\\{1,\dots,k\\}$.
At state $s_{1}^{\prime\prime}$ this strategy $\sigma$ can base its decision
only on the current memory mode ${\sf m}\in\\{1,\dots,k\\}$. Let $X({\sf
m})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathcal{P}}_{{\mathcal{G}},s_{1}^{\prime\prime},\sigma[{\sf
m}],\pi}(\mathtt{Reach}(\\{t\\})$ be the probability of reaching the target if
$\sigma$ is in mode ${\sf m}$ at state $s_{1}^{\prime\prime}$. (From state
$s_{1}^{\prime\prime}$ only Maximizer plays, thus Minimizer has no influence.)
Since $X({\sf m})<1$ and the memory is finite, we have
$Y\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\max_{{\sf
m}\in\\{1,\dots,k\\}}X({\sf m})<1$. There exists a number $i$ sufficiently
large such that $Y<1-\frac{1}{2^{i}}$. Let $\pi$ be a Minimizer strategy from
$s_{0}$ that takes the action that leads from $s_{i}^{\prime}$ to
$s_{1}^{\prime\prime}$, but chooses action $a_{j}$ at all states
$s_{j}^{\prime}$ with $j\neq i$. Then we have

${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(\\{t\\})\ \leq\
\frac{1}{2^{i}}Y+\sum_{j\neq
i}\frac{1}{2^{j}}\cdot\left(1-\frac{1}{2^{j}}\right)\ <\
\sum_{j=1}^{\infty}\frac{1}{2^{j}}\cdot\left(1-\frac{1}{2^{j}}\right)\ =\
{\mathtt{val}_{{\mathcal{G}}}(s_{0})}$

and thus $\sigma$ is not optimal. ∎

##  Appendix C Proofs from Section 4

We can construct an even simpler turn-based finitely branching reachability
game without uniform $\varepsilon$-optimal Maximizer strategies via applying
Theorem 3.5 to the concurrent game of Definition 3.3.

###### Definition C.1.

Consider the concurrent reachability game from Definition 3.3 and let
$\varepsilon=1/4$. By Theorem 3.5, Maximizer has a uniform
$\varepsilon$-optimal 1-bit strategy $\hat{\sigma}$. Let $p_{i,0}$ (resp.
$p_{i,1}$) be the probability that $\hat{\sigma}$ picks action $1$ at state
$c_{i}$ when in memory mode $0$ (resp. memory mode $1$).

We construct a turn-based reachability game ${\mathcal{G}}$ with branching
degree two where Maximizer can pick randomized actions according to these
probabilities $p_{i,0},p_{i,1}$, but nothing else. Let
${\mathcal{G}}=(S,(S_{\Box},S_{\Diamond},S_{\ocircle}),{\longrightarrow},P)$
where $S_{\Box}=\\{c_{i}\mid i\in\mathbb{N}\\}\cup\\{\mathrm{lose}\\}$,
$S_{\Diamond}=\\{d_{i,0},d_{i,1}\mid i\in\mathbb{N}\\}$, and
$S_{\ocircle}=\\{r_{i,0,0},r_{i,0,1},r_{i,1,0},r_{i,1,1}\mid
i\in\mathbb{N}\\}$. We have controlled transitions
$c_{i}{\longrightarrow}d_{i,j}$, $d_{i,j}{\longrightarrow}r_{i,j,k}$ for all
$i\in\mathbb{N}$ and $j,k\in\\{0,1\\}$ and
$\mathrm{lose}{\longrightarrow}\mathrm{lose}$. Intuitively, by going from
$c_{i}$ to $d_{i,j}$, Maximizer chooses action $1$ with probability $p_{i,j}$
and action $0$ otherwise. Minimizer chooses action $k$ by going from $d_{i,j}$
to $r_{i,j,k}$. The random transitions are defined by
$P(r_{i,j,0})(\mathrm{lose})=p_{i,j}$, $P(r_{i,j,0})(c_{i-1})=1-p_{i,j}$,
$P(r_{i,j,1})(c_{0})=p_{i,j}$, $P(r_{i,j,1})(c_{i+1})=1-p_{i,j}$.

The objective is $\mathtt{Reach}(\\{c_{0}\\})$.

###### Theorem C.2.

Consider the turn-based reachability game ${\mathcal{G}}$ of branching degree
two from Definition C.1 and let $x\geq 0$.

  1. (1)

${\mathtt{val}_{{\mathcal{G}}}(c_{x})}\geq 1/4$.

  2. (2)

There does not exist any uniformly $\varepsilon$-optimal positional (MR)
strategy for Maximizer.

Every MR Maximizer strategy $\sigma$ attains arbitrarily little from $c_{x}$
as $x\to\infty$. Formally,

$\limsup_{x\to\infty}\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))=0$

###### Proof.

Let ${\mathcal{G}}^{\prime}$ be the concurrent game from Definition 3.3. We
have ${\mathtt{val}_{{\mathcal{G}}^{\prime}}(c_{x})}\geq 1/2$ by Theorem 3.4.
Consider the $(1/4)$-optimal 1-bit Maximizer strategy $\hat{\sigma}$ used in
${\mathcal{G}}^{\prime}$ in Definition C.1. We can define a corresponding
1-bit Maximizer strategy $\sigma$ in ${\mathcal{G}}$. In every state $c_{i}$,
it picks the move $c_{i}{\longrightarrow}d_{i,j}$ whenever its memory mode is
$j$, and it updates its memory in the same way as $\hat{\sigma}$. Then

$\displaystyle{\mathtt{val}_{{\mathcal{G}}}(c_{x})}$
$\displaystyle\geq\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}},c_{x},\sigma,\pi}(\mathtt{Reach}(\\{c_{0}\\}))$
$\displaystyle=\inf_{\pi}{\mathcal{P}}_{{\mathcal{G}}^{\prime},c_{x},\hat{\sigma},\pi}(\mathtt{Reach}(\\{c_{0}\\}))$
$\displaystyle\geq{\mathtt{val}_{{\mathcal{G}}^{\prime}}(c_{x})}-1/4\geq 1/4.$

For item 2, the argument is exactly the same as in Theorem 4.2(2). ∎

##  Appendix D Minimizer Strategies

###### Lemma D.1.

Acyclic turn-based games with reachability objective admit uniformly
$\varepsilon$-optimal MD strategies for Minimizer. That is, for every such
game
${\mathcal{G}}=(S,(S_{\Box},S_{\Diamond},S_{\ocircle}),{\longrightarrow},P)$,
reachability target $T\subseteq S$ and every $0<\varepsilon<1$ there exists an
MD Minimizer strategy $\pi$ which satisfies, for every state $s_{0}\in S$ and
every Maximizer strategy $\sigma$, that
${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(T))\leq{\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(T)}(s_{0})}(1+\varepsilon)$.

###### Proof.

Let us shortly write
${\mathtt{val}(s)}={\mathtt{val}_{{\mathcal{G}},\mathtt{Reach}(T)}(s)}$ for
the value of a state $s$ and let $\iota:S\to\mathbb{N}\setminus\\{0\\}$ be an
enumeration of the state space starting at 1. Define $\pi$ as the MD-strategy
that, at any state $s\in S_{\Diamond}$, picks a successor $s^{\prime}$ such
that

${\mathtt{val}(s^{\prime})}\quad\leq\quad{\mathtt{val}(s)}(1+\ln(1+\varepsilon)2^{-\iota(s)}).$

To show that this strategy $\pi$ satisfies the claim we (over)estimate the
error by
$L(s)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\prod_{s^{\prime}\in\mathit{Post}^{*}(s)}(1+\ln(1+\varepsilon)2^{-\iota(s^{\prime})})$
where $\mathit{Post}^{*}(s)\subseteq S$ is the set of states reachable from
state $s\in S$ (under any pair of strategies). Notice that this guarantees
that

(6)
$1<L(s)\leq\prod_{i>0}\left(1+\ln(1+\varepsilon)2^{-i}\right)\leq\exp\left(\sum_{i>0}\ln(1+\varepsilon)2^{-i}\right)\leq\exp(\ln(1+\varepsilon))=1+\varepsilon$

where the third inequality uses that $1+x\leq\exp(x)$.

Let $\sigma$ be an arbitrary Maximizer strategy. For this pair $\sigma,\pi$ of
strategies let’s consider plays $(X_{i})_{i\geq 0}$ that start in $s_{0}\in S$
and proceed according to $\sigma,\pi$, and let
${\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}$ be the expectation with
respect to ${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}$.

An induction on $n$ using our choice of strategy gives, for every initial
state $s_{0}\in S$, that

(7)
${\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}({\mathtt{val}(X_{n})})\leq{\mathtt{val}(s_{0})}L(s_{0}).$

Indeed, this trivially holds for $n=0$ as
${\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}({\mathtt{val}(X_{0})})={\mathtt{val}(s_{0})}$
and $L(s_{0})>1$. For the induction step there are three cases.

_Case 1: $s_{0}\in S_{\Diamond}$ and $\pi(s_{0})=s$._ Let $\sigma{[s_{0}\to
s]}$ denote the Maximizer strategy from $s$ that behaves just like $\sigma$
does after observing the first step, i.e., satisfies $\sigma{[s_{0}\to
s]}(sh)=\sigma(s_{0}sh)$ for all suffix histories $h\in S^{*}$. Then

$\displaystyle{\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}({\mathtt{val}(X_{n+1})})$
$\displaystyle={\mathcal{E}}_{{\mathcal{G}},s,\sigma{[s_{0}\to
s]},\pi}({\mathtt{val}(X_{n})})$ $\displaystyle\leq{\mathtt{val}(s)}L(s)$ ind.
hyp.
$\displaystyle\leq{\mathtt{val}(s_{0})}\left(1+\ln(1+\varepsilon)2^{-\iota(s_{0})}\right)L(s)$
def. of $\pi$ $\displaystyle\leq{\mathtt{val}(s_{0})}L(s_{0})$
$\displaystyle\text{acyclicity; def.~{}of }L(s_{0}).$

_Case 2: $s_{0}\in S_{\Box}$._ Again, for any state $s$ let $\sigma{[s_{0}\to
s]}$ denote the suffix strategy consistent with $\sigma$ after the first step.
Then

$\displaystyle{\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}({\mathtt{val}(X_{n+1})})$
$\displaystyle=\sum_{s\in
S}\sigma(s_{0})(s)\cdot{\mathcal{E}}_{{\mathcal{G}},s,\sigma{[s_{0}\to
s]},\pi}({\mathtt{val}(X_{n})})$ $\displaystyle\leq\sum_{s\in
S}\sigma(s_{0})(s)\cdot{\mathtt{val}(s)}L(s)$ by ind. hyp.
$\displaystyle\leq\sum_{s\in
S}\sigma(s_{0})(s)\cdot{\mathtt{val}(s)}\left(1+\ln(1+\varepsilon)2^{-\iota(s_{0})}\right)L(s)$
$\displaystyle(1+\ln(1+\varepsilon)2^{-\iota(s_{0})})>1$
$\displaystyle\leq\sum_{s\in S}\sigma(s_{0})(s)\cdot{\mathtt{val}(s)}L(s_{0})$
$\displaystyle\text{acyclicity; def.~{}of }L(s_{0})$
$\displaystyle\leq{\mathtt{val}(s_{0})}L(s_{0}).$

_Case 3: $s_{0}\in S_{\ocircle}$_ is analogous to case 2, with the only
difference that the initial successor distribution is $P(s_{0})$, the one
fixed by the game, instead of $\sigma(s_{0})$ and the last inequality becomes
an equality.

Together with the observation (Eq. 6) that $L(s_{0})\leq(1+\varepsilon)$ for
every $s_{0}$, we derive that

(8)
$\liminf_{n\to\infty}{\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}({\mathtt{val}(X_{n})})\leq{\mathtt{val}(s_{0})}(1+\varepsilon).$

Finally, to show the claim, let $[X_{n}\in T]:S^{\omega}\to\\{0,1\\}$ be the
random variable that indicates that the $n$th state is in $T$. Note that
$[X_{n}\in T]\leq{\mathtt{val}(X_{n})}$ because target states have value $1$.
We conclude that

$\displaystyle{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(T))$
$\displaystyle=\quad{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}\left(\bigcup_{i=0}^{\infty}{\mathtt{Reach}_{i}(T)}\right)$
semantics of $\mathtt{Reach}(T)$
$\displaystyle=\quad\smashoperator[]{\lim_{n\to\infty}^{}}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}\left(\bigcup_{i=0}^{n}\mathtt{Reach}_{i}(T)\right)$
continuity of measures from below
$\displaystyle=\quad\smashoperator[]{\lim_{n\to\infty}^{}}{\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}\left(\mathtt{Reach}_{n}(T)\right)$
$T$ is a sink
$\displaystyle=\quad\smashoperator[]{\lim_{n\to\infty}^{}}{\mathcal{E}}_{{\mathcal{G}},s_{0},\sigma,\pi}([X_{n}\in
T])$ definition of $[X_{n}\in T]$
$\displaystyle\leq\quad\liminf_{n\to\infty}{\mathcal{E}}({\mathtt{val}(X_{n})})$
as $[X_{n}\in T]\leq{\mathtt{val}(X_{n})}$
$\displaystyle\leq\quad{\mathtt{val}(s_{0})}(1+\varepsilon)$
$\displaystyle\text{by \lx@cref{creftype~refnum}{eq:exi-lim}.}\qed$

###### Theorem D.2.

Turn-based games, even infinitely branching ones, with reachability objective
admit uniformly $\varepsilon$-optimal strategies for Minimizer that are
deterministic and Markov.

###### Proof.

For a given game
${\mathcal{G}}=(S,(S_{\Box},S_{\Diamond},S_{\ocircle}),{\longrightarrow},P)$
and reachability target $T\subseteq S$, one can construct the acyclic game
that encodes the stage (clock value) into the states:
$\mathcal{G}^{\prime}=(S,(S_{\Box}^{\prime},S_{\Diamond}^{\prime},S_{\ocircle}^{\prime}),{\longrightarrow}^{\prime},P^{\prime})$
where $S^{\prime}=S\times\mathbb{N}$,
$S_{\Box}^{\prime}=S_{\Box}\times\mathbb{N}$,
$S_{\Diamond}^{\prime}=S_{\Diamond}\times\mathbb{N}$
$S_{\ocircle}^{\prime}=S_{\ocircle}\times\mathbb{N}$, and for all
$i\in\mathbb{N}$, $(s,i){\longrightarrow}^{\prime}(t,i+1)\iff
s{\longrightarrow}t$ and $P((s,i))((t,i+1))=P(s)(t)$.

Every Markov strategy in $\mathcal{G}$ uniquely gives rise to a positional
strategy in $\mathcal{G}^{\prime}$ and vice versa. The claim now follows from
Lemma D.1. ∎

In infinitely branching turn-based reachability games, optimal Minimizer
strategies need not exist (Kiefer et al., 2017c). When they do exist, they may
need infinite memory. We slightly improve the result of (Kučera, 2011,
Proposition 5.6.(a)) by showing that even a step counter does not help
Minimizer.

###### Definition D.3.

We define an infinitely branching turn-based reachability game ${\mathcal{G}}$
with initial state $s_{0}$ and target state $t$. Let $s_{0}$ be Maximizer-
controlled. We have transitions $s_{0}\to s_{i}^{\prime}$ for all $i\geq 1$.
All states $s_{i}^{\prime}$ are random states with
$P(s_{i}^{\prime})(t)=1/2-2^{-i}$ and and $P(s_{i}^{\prime})(u)=1/2+2^{-i}$.
The state $u$ is Minimizer-controlled with transitions $u\to
s_{i}^{\prime\prime}$ for all $i\geq 1$. All states $s_{i}^{\prime\prime}$ are
random states with $P(s_{i}^{\prime\prime})(t)=2^{-i}$ and
$P(s_{i}^{\prime\prime})(b)=1-2^{-i}$ for a losing sink state $b$.

###### Proposition D.4.

There exists an infinitely branching turn-based reachability game
${\mathcal{G}}$ with initial state $s_{0}$ and objective
$\mathtt{Reach}(\\{t\\})$ as in Definition D.3, such that

  1. (1)

Minimizer has an optimal strategy from $s_{0}$.

  2. (2)

Every randomized Minimizer strategy from $s_{0}$ that uses only a step counter
and finite private memory is not optimal.

###### Proof.

Towards Item 1, we note that ${\mathtt{val}_{{\mathcal{G}}}(u)}=0$ and thus
${\mathtt{val}_{{\mathcal{G}}}(s_{0})}=1/2$. Minimizer’s optimal strategy
$\pi$ from $s_{0}$ is defined as follows. In plays where the state $u$ is not
reached, Minimizer does not make any decisions. If state $u$ is reached,
Minimizer considers the history of this play: If Maximizer made the step
$s_{0}\to s_{i}^{\prime}$ for some $i\geq 1$, then Minimizer plays $u\to
s_{i}^{\prime\prime}$ for the same $i$. Now we show that $\pi$ is optimal for
Minimizer from $s_{0}$. Let $\sigma$ be an arbitrary Maximizer strategy from
$s_{0}$ and let $x_{i}$ be the probability that $\sigma$ chooses the step
$s_{0}\to s_{i}^{\prime}$. This must be a distribution, i.e., $\sum_{i\geq
1}x_{i}=1$. Then we have

${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(\\{t\\})=\sum_{i\geq
1}x_{i}((1/2-2^{-i})+(1/2+2^{-i})2^{-i})\leq\sum_{i\geq
1}x_{i}(1/2)=1/2={\mathtt{val}_{{\mathcal{G}}}(s_{0})}$

as required.

Towards Item 2, we note that the step counter from $s_{0}$ is implicit in the
states of ${\mathcal{G}}$, and thus superfluous for Minimizer strategies.
Hence it suffices to prove the property for Minimizer strategies with finite
memory. Let $\pi$ be an FR Minimizer strategy with finitely many memory modes
$\\{1,\dots,k\\}$. In state $u$ this strategy $\pi$ can base its decision only
on the current memory mode ${\sf m}\in\\{1,\dots,k\\}$. Let $X({\sf
m})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathcal{P}}_{{\mathcal{G}},u,\sigma,\pi[{\sf
m}]}(\mathtt{Reach}(\\{t\\})$ be the probability of reaching the target if
$\pi$ is in mode ${\sf m}$ at state $u$. (From state $u$ only Minimizer plays,
thus Maximizer has no influence.) Since $X({\sf m})>0$ and the memory is
finite, we have $Y\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\min_{{\sf
m}\in\\{1,\dots,k\\}}X({\sf m})>0$. There exists a number $i$ sufficiently
large such that $2^{-i}<Y/2$. Let $\sigma$ be a Maximizer strategy from
$s_{0}$ that chooses the transition $s_{0}\to s_{i}^{\prime}$. Then we have

${\mathcal{P}}_{{\mathcal{G}},s_{0},\sigma,\pi}(\mathtt{Reach}(\\{t\\})\geq(1/2-2^{-i})+(1/2+2^{-i})Y>1/2={\mathtt{val}_{{\mathcal{G}}}(s_{0})}$

and thus $\pi$ is not optimal. ∎

##  Appendix E Proofs from Section 7

See 7.2

###### Proof.

We show Item 1 by induction on $k$.

In the base case of $k=1$ we have ${\mathcal{G}}_{1}={\mathcal{G}}$ from
Definition 6.1, and thus the result holds by Theorem 6.2(Item 1).

Induction step $k{\longrightarrow}k+1$. For every state $s$ in
${\mathcal{G}}_{k+1}$ outside of any subgame, let $\sigma^{\prime}(s)$ be the
almost sure winning Maximizer strategy from $s$ in the non-nested game
${\mathcal{G}}_{1}$, obtained from above. By the induction hypothesis, for any
state $s$ in a subgame ${\mathcal{G}}_{k}^{i}$ there exists a Maximizer
strategy $\sigma_{k}^{i}(s)$ from $s$ that almost surely wins this subgame
${\mathcal{G}}_{k}^{i}$.

We now construct a Maximizer strategy $\sigma(s)$ from any state $s$ in
${\mathcal{G}}_{k+1}$. If $s$ is not in any strict subgame then $\sigma(s)$
plays like $\sigma^{\prime}(s)$ outside of the subgames. Whenever a subgame
${\mathcal{G}}_{k}^{i}$ is entered at some state $x$ then it plays like
$\sigma_{k}^{i}(x)$ until $\mathrm{win}^{k,i}$ is reached (which happens
eventually almost surely by the definition of $\sigma_{k}^{i}(x)$) and the
play exits the subgame, and then it continues with the outer strategy
$\sigma^{\prime}(s)$. Similarly, if the start state $s$ is in some subgame
${\mathcal{G}}_{k}^{i}$ then it first plays $\sigma_{k}^{i}(s)$ until
$\mathrm{win}^{k,i}$ is reached (which happens eventually almost surely by the
definition of $\sigma_{k}^{i}(s)$) and the play exits the subgame, and then it
continues like the strategy $\sigma^{\prime}(c_{i,1})$ described above. Then
$\sigma(s)$ wins almost surely, since the strategies $\sigma^{\prime}$ and
$\sigma_{k}^{i}$ win almost surely.

Towards Item 2, we show, by induction on $k$, a slightly stronger property.
For each Maximizer strategy $\sigma$ in ${\mathcal{G}}_{k}$ with a step
counter plus a private finite memory with $\leq k$ modes, for every $\delta>0$
there exists a Minimizer strategy $\pi$ that upper-bounds Maximizer’s
attainment by $\delta$ regardless of Maximizer’s initial memory mode and the
starting time. Formally,

(9) $\forall\delta>0\,\exists\pi\,\forall{\sf m}\,\forall t\
{\mathcal{P}}_{{\mathcal{G}}_{k},u,\sigma[{\sf
m}](t),\pi}(\mathtt{Reach}(\\{c_{0}\\}))\leq\delta$

For the base case $k=1$ we have ${\mathcal{G}}_{1}={\mathcal{G}}$ from
Definition 6.1. Since $k=1$, Maximizer has only one memory mode. Moreover,
Minimizer’s strategy from the proof of Theorem 6.2(2) works regardless of the
starting time $t$ (since it just chooses delays in the states $b_{i}$ to
satisfy (1) and (2)). Thus we obtain (9).

Induction step $k{\longrightarrow}k+1$. Consider the game
${\mathcal{G}}_{k+1}$ and a fixed Maximizer strategy $\sigma$ with a step
counter plus $(k+1)$ private memory modes from state $u$. Let
$\\{0,1,\dots,k\\}$ denote the $k+1$ private memory modes of $\sigma$.

From every state $c_{i}$ in ${\mathcal{G}}_{k+1}$ we enter the subgame
${\mathcal{G}}_{k}^{i}$, at some state chosen by Minimizer. When (and if)
Maximizer wins this subgame then we are in state $\mathrm{win}^{k,i}$ and the
game ${\mathcal{G}}_{k+1}$ continues with Maximizer’s choice at $c_{i,1}$,
etc.

Consider the state $c_{i}$, visited at some time $t$ with some Maximizer
memory mode ${\sf m}$. Let $\pi^{\prime}$ be some Minimizer strategy. Then let
$\alpha(i,{\sf m},t,\pi^{\prime})$ be the probability that Maximizer will play
action “1” (wrt. the encoded concurrent game) in the next round in
${\mathcal{G}}_{k+1}$ after winning the subgame ${\mathcal{G}}_{k}^{i}$ (i.e.,
after reaching $\mathrm{win}^{k,i}$), or loses the subgame (never reaches
$\mathrm{win}^{k,i}$). So $\alpha(i,{\sf m},t,\pi^{\prime})$ is the
probability of losing the subgame ${\mathcal{G}}_{k}^{i}$ plus
$\sum_{j}(1/j)\cdot p_{j}$, where $p_{j}$ is the probability of winning the
subgame and then directly going to $d_{i,j}$ (i.e., in the same round, without
seeing any other state $c_{i}$ before). To define this formally, let
$C_{-i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{c_{j}\mid j\neq
i\\}$. We let

$\displaystyle\alpha(i,{\sf m},t,\pi^{\prime})$
$\displaystyle\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\mathcal{P}}_{{\mathcal{G}}_{k+1},c_{i},\sigma[{\sf
m}](t),\pi^{\prime}}(\neg\mathtt{Reach}(\\{\mathrm{win}^{k,i}\\}))$
$\displaystyle+\sum_{j}(1/j){\mathcal{P}}_{{\mathcal{G}}_{k+1},c_{i},\sigma[{\sf
m}](t),\pi^{\prime}}(d_{i,j}\ \mathsf{before}\ C_{-i})$

(where $(d_{i,j}\ \mathsf{before}\ C_{-i})$ denotes the set of plays that
visit state $d_{i,j}$ before visiting any state in $C_{-i}$). The probability
$\alpha(i,{\sf m},t,\pi^{\prime})$ depends on $i$ (since we are looking at
state $c_{i}$), on Maximizer’s private memory mode ${\sf
m}\in\\{0,1,\dots,k\\}$ at state $c_{i}$, at the time $t\in\mathbb{N}$ when we
are at $c_{i}$ and on Minimizer’s strategy $\pi^{\prime}$. Let $\alpha(i,{\sf
m},t)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\pi^{\prime}}\alpha(i,{\sf
m},t,\pi^{\prime})$ be the supremum over all Minimizer strategies. Let
$\alpha(i,t)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\min_{{\sf
m}\in\\{0,\dots,k\\}}\alpha(i,{\sf m},t)$ the minimum over all memory modes.
Intuitively, when entering the subgame ${\mathcal{G}}_{k}^{i}$ from $c_{i}$ at
time $t$, for each Maximizer memory mode ${\sf m}$, for each $\varepsilon>0$,
Minimizer has a strategy to make the probability of Maximizer playing action
“1” after winning the subgame (or else losing the subgame) at least
$\alpha(i,t)-\varepsilon$. Let $\alpha(i)$ be the maximal accumulation point
of the infinite sequence $\alpha(i,1),\alpha(i,2),\dots$, i.e.,
$\alpha(i)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\limsup_{t}\alpha(i,t)$.
We have:

(10) $\displaystyle\forall\,i\in\mathbb{N}\ \forall\,\varepsilon>0\
\forall\,t_{0}\in\mathbb{N}\ \exists\,t\geq t_{0}:$
$\displaystyle\quad\alpha(i,t)\geq\alpha(i)-\varepsilon$ (11)
$\displaystyle\forall\,i\in\mathbb{N}\ \forall\,\varepsilon>0\
\exists\,t_{0}\in\mathbb{N}\ \forall\,t\geq t_{0}:$
$\displaystyle\quad\alpha(i,t)\leq\alpha(i)+\varepsilon$

Now there are two cases.

In the first case, $\sum_{i}\alpha(i)$ diverges. Intuitively, since we have
$\alpha(i)=\limsup_{t}\alpha(i,t)$, Minimizer chooses the delays at the states
$b_{i}$ in order to make $\alpha(i,t)$ “large”, i.e., close to $\alpha(i)$, by
using (10).

Analogously to 5.1, it suffices, for every $\varepsilon>0$ to construct a
Minimizer strategy $\pi$ in ${\mathcal{G}}_{k+1}$ from state $u$ that makes
the probability of visiting $c_{0}$ before revisiting $u$ (denoted as the
event “${{c_{0}}\ \mathsf{before}\ u}$”) at most $\varepsilon$.

We construct a Minimizer strategy $\pi$ that plays as follows. First $\pi$
picks the transition $u{\longrightarrow}b_{i_{0}}$ for a sufficiently high
$i_{0}\in\mathbb{N}$, to be determined. At every state $d_{i,j}$, outside of
the subgames, $\pi$ always plays action “0”, i.e.,
$d_{i,j}{\longrightarrow}r_{i,j}^{0}$. This implies that the state $c_{i}$ is
not visited again, unless the state $u$ is re-visited first. (If Maximizer
plays action “1” then he loses this round and the game goes back to $u$. If
Maximizer plays “0” then the game goes down to $c_{i-1}$.)

At every state $b_{i}$ at each time $t^{\prime}$ the strategy $\pi$ picks a
delay such that the game arrives at $c_{i}$ at a time $t$ such that

(12) $\alpha(i,t)\geq\alpha(i)-\frac{1}{4}2^{-i}.$

This is possible by Eq. 10. Let $T_{i}$ be the set of the times $t$ that
satisfy (12). Minimizer’s strategy ensures that the states $c_{i}$ are only
reached at times $t\in T_{i}$.

From state $c_{i}$, at each time $t$, for each memory mode ${\sf m}$ there
exists a Minimizer strategy $\pi(i,{\sf m},t)$ such that we have
$\alpha(i,{\sf m},t,\pi(i,{\sf m},t))\geq\alpha(i,{\sf
m},t)-\frac{1}{4}2^{-i}$, by the definition of $\alpha(i,{\sf
m},t)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\pi^{\prime}}\alpha(i,{\sf
m},t,\pi^{\prime})$.

Since the Maximizer memory mode ${\sf m}$ is private, Minimizer does not know
it. So our Minimizer strategy $\pi$ hedges her bets over all possible ${\sf
m}\in\\{0,\dots,k\\}$ and plays each strategy $\pi(i,{\sf m},t)$ with equal
probability $\frac{1}{k+1}$. It follows that for every $i$ and time $t\in
T_{i}$ chosen according to Eq. 12, after (and if) winning the subgame
${\mathcal{G}}_{k}^{i}$, Maximizer plays action “1” with probability

(13) $\begin{array}[]{l}\alpha(i,{\sf
m},t,\pi)\geq\frac{1}{k+1}(\alpha(i,t)-\frac{1}{4}2^{-i})\\\
\geq\frac{1}{k+1}(\alpha(i)-\frac{1}{4}2^{-i}-\frac{1}{4}2^{-i})=\frac{1}{k+1}(\alpha(i)-\frac{1}{2}2^{-i})\end{array}$

Since, outside of subgames, Minimizer always plays action “0” and each state
$c_{i}$ is visited at most once (unless state $u$ is re-visited), we get for