University of Edinburgh, UK University of Edinburgh, UK Richard Mayr and Eric
Munday [200]Theory of computation Random walks and Markov chains
[100]Mathematics of computing Probability and statistics This is the full
version of a CONCUR 2021 paper [17].Serge Haddad and Daniele Varacca 2 32nd
International Conference on Concurrency Theory (CONCUR 2021) CONCUR 2021
CONCUR 2021 August 23–27, 2021 Virtual Conference 203 2

# Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives
in Countable MDPs

Richard Mayr  Eric Munday

###### Abstract

We study countably infinite Markov decision processes (MDPs) with real-valued
transition rewards. Every infinite run induces the following sequences of
payoffs: 1\. Point payoff (the sequence of directly seen transition rewards),
2\. Total payoff (the sequence of the sums of all rewards so far), and 3\.
Mean payoff. For each payoff type, the objective is to maximize the
probability that the $\liminf$ is non-negative. We establish the complete
picture of the strategy complexity of these objectives, i.e., how much memory
is necessary and sufficient for $\varepsilon$-optimal (resp. optimal)
strategies. Some cases can be won with memoryless deterministic strategies,
while others require a step counter, a reward counter, or both.

###### keywords:

Markov decision processes, Strategy complexity, Mean payoff

##  1 Introduction

Background. Markov decision processes (MDPs) are a standard model for dynamic
systems that exhibit both stochastic and controlled behavior [18].
Applications include control theory [5, 1], operations research and finance
[2, 6, 20], artificial intelligence and machine learning [23, 21], and formal
verification [9, 3].

An MDP is a directed graph where states are either random or controlled. In a
random state the next state is chosen according to a fixed probability
distribution. In a controlled state the controller can choose a distribution
over all possible successor states. By fixing a strategy for the controller
(and an initial state), one obtains a probability space of runs of the MDP.
The goal of the controller is to optimize the expected value of some objective
function on the runs. The type of strategy necessary to achieve an
$\varepsilon$-optimal (resp. optimal) value for a given objective is called
its _strategy complexity_.

Transition rewards and liminf objectives. MDPs are given a reward structure by
assigning a real-valued (resp. integer or rational) reward to each transition.
Every run then induces an infinite sequence of seen transition rewards
$r_{0}r_{1}r_{2}\dots$. We consider the $\liminf$ of this sequence, as well as
two other important derived sequences.

1.

The point payoff considers the $\liminf$ of the sequence
$r_{0}r_{1}r_{2}\dots$ directly.

2.

The total payoff considers the $\liminf$ of the sequence
$\left\\{\sum_{i=0}^{n-1}r_{i}\right\\}_{n\in\mathbb{N}}$, i.e., the sum of
all rewards seen so far.

3.

The mean payoff considers the $\liminf$ of the sequence
$\left\\{\frac{1}{n}\sum_{i=0}^{n-1}r_{i}\right\\}_{n\in\mathbb{N}}$, i.e.,
the mean of all rewards seen so far in an expanding prefix of the run.

For each of the three cases above, the $\liminf$ threshold objective is to
maximize the probability that the $\liminf$ of the respective type of sequence
is $\geq 0$.

Our contribution. We establish the strategy complexity of all the $\liminf$
threshold objectives above for _countably infinite_ MDPs. (For the simpler
case of finite MDPs, see the paragraph on related work below.) We show the
amount and type of memory that is sufficient for $\varepsilon$-optimal
strategies (and optimal strategies, where they exist), and corresponding lower
bounds in the sense of Remark 2.1. This is not only the distinction between
memoryless, finite memory and infinite memory, but the type of infinite memory
that is necessary and sufficient. A step counter is an integer counter that
merely counts the number of steps in the run (i.e., like a discrete clock),
while a reward counter is a variable that records the sum of all rewards seen
so far. (The reward counter has the same type as the transition rewards in the
MDP, i.e., integers, rationals or reals.) While these use infinite memory, it
is a very restricted form, since this memory is not directly controlled by the
player. Strategies using only a step counter are also called Markov strategies
[18].

Some of the $\liminf$ objectives can be attained by memoryless deterministic
(MD) strategies, while others require (in the sense of Remark 2.1) a step
counter, a reward counter, or both. It depends on the type of objective
(point, total, or mean payoff) and on whether the MDP is finitely or
infinitely branching. For clarity of presentation, our counterexamples use
large transition rewards and high degrees of branching. However, the lower
bounds hold even for just binary branching MDPs with transition rewards in
$\\{-1,0,1\\}$; cf. Appendix E.

For our objectives, the strategy complexities of $\varepsilon$-optimal and
optimal strategies (where they exist) coincide, but the proofs are different.
Table 1 shows the results for all combinations.

| Point payoff | Total payoff | Mean payoff
---|---|---|---
$\varepsilon$-optimal, infinitely branching | SC 4.3, 5.16 | SC+RC 4.3, 3.11, 5.18 | SC+RC 4.1, 3.10, 5.17
optimal, infinitely branching | SC 4.3, 5.19 | SC+RC 3.18, 4.3, 5.19 | SC+RC 3.17, 4.2, 5.19
$\varepsilon$-optimal, finitely branching | MD 5.10 | RC 3.11, 5.12 | SC+RC 4.1, 3.10, 5.17
optimal, finitely branching | MD 5.14 | RC 3.18, 5.14 | SC+RC 3.17, 4.2, 5.19
Table 1: Strategy complexity of $\varepsilon$-optimal/optimal strategies for
point, total and mean payoff objectives in infinitely/finitely branching MDPs.
MD stands for memoryless deterministic, SC for step counter, RC for reward
counter and SC+RC for both. All strategies are deterministic and randomization
does not help. For each result, we list the numbers of the theorems that show
the upper and lower bounds on the strategy complexity. The lower bounds hold
in the sense of Remark 2.1, but work for integer rewards. The upper bounds
hold even for real-valued rewards.

Some complex new proof techniques are developed to show these results. E.g.,
the examples showing the lower bound in cases where both a step counter and a
reward counter are required use a finely tuned tradeoff between different
risks that can be managed with both counters, but not with just one counter
plus arbitrary finite memory. The strategies showing the upper bounds need to
take into account convergence effects, e.g., the sequence of point rewards
$-1/2,-1/3,-1/4,\dots$ _does_ satisfy $\liminf$ $\geq 0$, i.e., one cannot
assume that rewards are integers.

Due to space constraints, we sketch some proofs in the main body. Full proofs
can be found in the Appendix.

Related work. Mean payoff objectives for _finite_ MDPs have been widely
studied; cf. survey in [8]. There exist optimal MD strategies for $\liminf$
mean payoff (which are also optimal for $\limsup$ mean payoff since the
transition rewards are bounded), and the associated computational problems can
be solved in polynomial time [8, 18]. Similarly, see [7] for a survey on
$\limsup$ and $\liminf$ point payoff objectives in finite stochastic games and
MDPs, where there also exist optimal MD strategies, and the more recent paper
by Flesch, Predtetchinski and Sudderth [11] on simplifying optimal strategies.

All this does _not_ carry over to countably infinite MDPs. Optimal strategies
need not exist (not even for much simpler objectives), ($\varepsilon$-)optimal
strategies can require infinite memory, and computational problems are not
defined in general, since a countable MDP need not be finitely presented [16].
Moreover, attainment for $\liminf$ mean payoff need not coincide with
attainment for $\limsup$ mean payoff, even for very simple examples. E.g.,
consider the acyclic infinite graph with transitions $s_{n}\rightarrow
s_{n+1}$ for all $n\in\mathbb{N}$ with reward $(-1)^{n}2^{n}$ in the $n$-th
step, which yields a $\liminf$ mean payoff of $-\infty$ and a $\limsup$ mean
payoff of $+\infty$.

Mean payoff objectives for countably infinite MDPs have been considered in
[18, Section 8.10], e.g., [18, Example 8.10.2] (adapted in Figure 4) shows
that there are no optimal MD (memoryless deterministic) strategies for
$\liminf$/$\limsup$ mean payoff. [19, Counterexample 1.3] shows that there are
not even $\varepsilon$-optimal memoryless randomized strategies for
$\liminf$/$\limsup$ mean payoff. (We show much stronger lower/upper bounds;
cf. Table 1.)

Sudderth [22] considered an objective on countable MDPs that is related to our
point payoff threshold objective. However, instead of maximizing the
probability that the $\liminf$/$\limsup$ is non-negative, it asks to maximize
the _expectation_ of the $\liminf$/$\limsup$ point payoffs, which is a
different problem (e.g., it can tolerate a high probability of a negative
$\liminf$/$\limsup$ if the remaining cases have a huge positive
$\liminf$/$\limsup$). Hill & Pestien [12] showed the existence of good
randomized Markov strategies for the $\limsup$ of the _expected_ average
reward up-to step $n$ for growing $n$, and for the _expected_ $\liminf$ of the
point payoffs.

##  2 Preliminaries

Markov decision processes. 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$. A
_Markov decision process_ (MDP)
${\mathcal{M}}=(S,S_{\Box},S_{\ocircle},{\longrightarrow},P,r)$ consists of a
countable set $S$ of _states_ , which is partitioned into a set $S_{\Box}$ of
_controlled states_ and a set $S_{\ocircle}$ of _random states_ , a
_transition relation_ ${\longrightarrow}\subseteq S\times S$, and a
_probability function_ $P:S_{\ocircle}\to\mathcal{D}(S)$. We write
$s{\longrightarrow}{}s^{\prime}$ if $(s,s^{\prime})\in{\longrightarrow}$, and
refer to $s^{\prime}$ as a _successor_ of $s$. We assume that every state has
at least one successor. The probability function $P$ assigns to each random
state $s\in S_{\ocircle}$ a probability distribution $P(s)$ over its (non-
empty) set of successor states. A _sink in ${\mathcal{M}}$_ is a subset
$T\subseteq S$ closed under the ${\longrightarrow}$ relation, that is, $s\in
T$ and $s{\longrightarrow}s^{\prime}$ implies that $s^{\prime}\in T$.

An MDP is _acyclic_ if the underlying directed graph $(S,{\longrightarrow})$
is acyclic, i.e., there is no directed cycle. It is _finitely branching_ if
every state has finitely many successors and _infinitely branching_ otherwise.
An MDP without controlled states ($S_{\Box}=\emptyset$) is called a _Markov
chain_.

In order to specify our mean/total/point payoff objectives (see below), we
define a function $\mathit{r}:S\times S\to\mathbb{R}$ that assigns numeric
rewards to transitions.

Strategies and Probability Measures. A _run_ $\rho$ is an infinite sequence of
states and transitions $s_{0}e_{0}s_{1}e_{1}\cdots$ such that
$e_{i}=(s_{i},s_{i+1})\in{\longrightarrow}$ for all $i\in\mathbb{N}$. Let
${\textit{Runs}_{{\mathcal{M}}}^{s_{0}}}$ be the set of all runs from $s_{0}$
in the MDP ${\mathcal{M}}$. A _partial run_ is a finite prefix of a run,
${\textit{pRuns}_{{\mathcal{M}}}^{s_{0}}}$ is the set of all partial runs from
$s_{0}$ and ${\textit{pRuns}_{{\mathcal{M}}}}$ the set of partial runs from
any state.

We write $\rho_{s}(i)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}s_{i}$
for the $i$-th state along $\rho$ and
$\rho_{e}(i)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}e_{i}$ for the
$i$-th transition along $\rho$. We sometimes write runs as $s_{0}s_{1}\cdots$,
leaving the transitions implicit. We say that a (partial) run $\rho$ _visits_
$s$ if $s=\rho_{s}(i)$ for some $i$, and that $\rho$ starts in $s$ if
$s=\rho_{s}(0)$.

A _strategy_ is a function
$\sigma:{\textit{pRuns}_{{\mathcal{M}}}}\\!\cdot\\!S_{\Box}\to\mathcal{D}(S)$
that assigns to partial runs $\rho s$, where $s\in S_{\Box}$, a distribution
over the successors $\\{s^{\prime}\in S\mid
s{\longrightarrow}{}s^{\prime}\\}$. The set of all strategies in
${\mathcal{M}}$ is denoted by $\Sigma_{\mathcal{M}}$ (we omit the subscript
and write $\Sigma$ if ${\mathcal{M}}$ is clear from the context). A (partial)
run $s_{0}e_{0}s_{1}e_{1}\cdots$ is consistent with a strategy $\sigma$ if for
all $i$ either $s_{i}\in S_{\Box}$ and $\sigma(s_{0}e_{0}s_{1}e_{1}\cdots
s_{i})(s_{i+1})>0$, or $s_{i}\in S_{\ocircle}$ and $P(s_{i})(s_{i+1})>0$.

An MDP ${\mathcal{M}}=(S,S_{\Box},S_{\ocircle},{\longrightarrow},P,r)$, an
initial state $s_{0}\in S$, and a strategy $\sigma$ induce a probability space
in which the outcomes are runs starting in $s_{0}$ and with measure
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}$ defined as follows. It is first
defined on _cylinders_ $s_{0}e_{0}s_{1}e_{1}\ldots
s_{n}{\textit{Runs}_{{\mathcal{M}}}^{s_{n}}}$: if $s_{0}e_{0}s_{1}e_{1}\ldots
s_{n}$ is not a partial run consistent with $\sigma$ then
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}(s_{0}e_{0}s_{1}e_{1}\ldots
s_{n}{\textit{Runs}_{{\mathcal{M}}}^{s_{n}}})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}0$.
Otherwise,
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}(s_{0}e_{0}s_{1}e_{1}\ldots
s_{n}{\textit{Runs}_{{\mathcal{M}}}^{s_{n}}})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\prod_{i=0}^{n-1}\bar{\sigma}(s_{0}e_{0}s_{1}\ldots
s_{i})(s_{i+1})$, where $\bar{\sigma}$ is the map that extends $\sigma$ by
$\bar{\sigma}(ws)=P(s)$ for all partial runs
$ws\in{\textit{pRuns}_{{\mathcal{M}}}}\\!\cdot\\!S_{\ocircle}$. By
Carathéodory’s theorem [4], this extends uniquely to a probability measure
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}$ on the Borel $\sigma$-algebra
$\mathcal{F}$ of subsets of ${\textit{Runs}_{{\mathcal{M}}}^{s_{0}}}$.
Elements of $\mathcal{F}$, i.e., measurable sets of runs, are called _events_
or _objectives_ here. For $X\in\mathcal{F}$ we will write
$\overline{X}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\textit{Runs}_{{\mathcal{M}}}^{s_{0}}}\setminus
X\in\mathcal{F}$ for its complement and
${\mathcal{E}}_{{\mathcal{M}},s_{0},\sigma}$ for the expectation wrt.
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}$. We drop the indices if possible
without ambiguity.

Objectives. We consider objectives that are determined by a predicate on
infinite runs. We assume familiarity with the syntax and semantics of the
temporal logic LTL [10]. Formulas are interpreted on the structure
$(S,{\longrightarrow})$. We use $\llbracket{\varphi}\rrbracket^{s}$ to denote
the set of runs starting from $s$ that satisfy the LTL formula ${\varphi}$,
which is a measurable set [24]. We also write $\llbracket{\varphi}\rrbracket$
for $\bigcup_{s\in S}\llbracket{\varphi}\rrbracket^{s}$. Where it does not
cause confusion we will identify $\varphi$ and $\llbracket{\varphi}\rrbracket$
and just write ${\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\varphi})$ instead of
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}(\llbracket{\varphi}\rrbracket^{s})$.
The reachability objective of eventually visiting a set of states $X$ can be
expressed by $\llbracket{\sf
F}X\rrbracket\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\,|\,\exists
i.\,\rho_{s}(i)\in X\\}$. Reaching $X$ within at most $k$ steps is expressed
by $\llbracket{\sf F}^{\leq
k}X\rrbracket\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\,|\,\exists
i\leq k.\,\rho_{s}(i)\in X\\}$. The definitions for eventually visiting
certain transitions are analogous. The operator ${\sf G}$ (always) is defined
as $\neg{\sf F}\neg$. So the safety objective of avoiding $X$ is expressed by
${\sf G}\neg X$.

  * •

The ${\it PP}_{\liminf\geq 0}$ objective is to maximize the probability that
the $\liminf$ of the _point_ payoffs (the immediate transition rewards) is
$\geq 0$, i.e., ${\it PP}_{\liminf\geq
0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\mid\liminf_{n\in\mathbb{N}}\mathit{r}(\rho_{e}(n))\geq
0\\}$.

  * •

The ${\it TP}_{\liminf\geq 0}$ objective is to maximize the probability that
the $\liminf$ of the _total_ payoff (the sum of the transition rewards seen so
far) is $\geq 0$, i.e., ${\it TP}_{\liminf\geq
0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\mid\liminf_{n\in\mathbb{N}}\sum_{j=0}^{n-1}\mathit{r}(\rho_{e}(j))\geq
0\\}$.

  * •

The ${\it MP}_{\liminf\geq 0}$ objective is to maximize the probability that
the $\liminf$ of the _mean_ payoff is $\geq 0$, i.e., ${\it MP}_{\liminf\geq
0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\mid\liminf_{n\in\mathbb{N}}\frac{1}{n}\sum_{j=0}^{n-1}\mathit{r}(\rho_{e}(j))\geq
0\\}$.

An objective ${\varphi}$ is called _tail_ in ${\mathcal{M}}$ if for every run
$\rho^{\prime}\rho$ in ${\mathcal{M}}$ with some finite prefix $\rho^{\prime}$
we have
$\rho^{\prime}\rho\in\llbracket{\varphi}\rrbracket\Leftrightarrow\rho\in\llbracket{\varphi}\rrbracket$.
An objective is called a _tail objective_ if it is tail in every MDP. ${\it
PP}_{\liminf\geq 0}$ and ${\it MP}_{\liminf\geq 0}$ are tail objectives, but
${\it TP}_{\liminf\geq 0}$ is not. Also ${\it PP}_{\liminf\geq 0}$ is more
general than co-Büchi. (The special case of integer transition rewards
coincides with co-Büchi, since rewards $\leq-1$ and accepting states can be
encoded into each other.)

Strategy Classes. Strategies are in general _randomized_ (R) in the sense that
they take values in $\mathcal{D}(S)$. A strategy $\sigma$ is _deterministic_
(D) if $\sigma(\rho)$ is a Dirac distribution for all $\rho$. General
strategies can be _history dependent_ (H), while others are restricted by the
size or type of memory they use, see below. We consider certain classes of
strategies:

  * •

A strategy $\sigma$ is _memoryless_ (M) (also called _positional_) if it can
be implemented with a memory of size $1$. We may view M-strategies as
functions $\sigma:S_{\Box}\to\mathcal{D}(S)$.

  * •

A strategy $\sigma$ is _finite memory_ (F) if there exists a finite memory
${\sf M}$ implementing $\sigma$. Hence FR stands for finite memory randomized.

  * •

A _step counter strategy_ bases decisions only on the current state and the
number of steps taken so far, i.e., it uses an unbounded integer counter that
gets incremented by $1$ in every step. Such strategies are also called _Markov
strategies_ [18].

  * •

_$k$ -bit Markov strategies_ use $k$ extra bits of general purpose memory in
addition to a step counter [15].

  * •

A _reward counter strategy_ uses infinite memory, but only in the form of a
counter that always contains the sum of all transition rewards seen to far.

  * •

A _step counter + reward counter strategy_ uses both a step counter and a
reward counter.

See Appendix A for a formal definition how strategies use memory. Step
counters and reward counters are very restricted forms of memory, since the
memory update is not directly under the control of the player. These counters
merely record an aspect of the partial run.

Optimal and $\varepsilon$-optimal Strategies. Given an objective ${\varphi}$,
the value of state $s$ in an MDP ${\mathcal{M}}$, denoted by
${\mathtt{val}_{{\mathcal{M}},{\varphi}}(s)}$, is the supremum probability of
achieving ${\varphi}$. Formally,
${\mathtt{val}_{{\mathcal{M}},{\varphi}}(s)}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sup_{\sigma\in\Sigma}{\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\varphi})$
where $\Sigma$ is the set of all strategies. For $\varepsilon\geq 0$ and state
$s\in S$, we say that a strategy is _$\varepsilon$ -optimal_ from $s$ if
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\varphi})\geq{\mathtt{val}_{{\mathcal{M}},{\varphi}}(s)}-\varepsilon$.
A $0$-optimal strategy is called _optimal_. An optimal strategy is _almost-
surely winning_ if ${\mathtt{val}_{{\mathcal{M}},{\varphi}}(s)}=1$.
Considering an MD strategy as a function $\sigma:S_{\Box}\to S$ and
$\varepsilon\geq 0$, $\sigma$ is _uniformly_ $\varepsilon$-optimal (resp.
uniformly optimal) if it is $\varepsilon$-optimal (resp. optimal) from _every_
$s\in S$.

######  Remark 2.1.

To establish an upper bound $X$ on the strategy complexity of an objective
${\varphi}$ in countable MDPs, it suffices to prove that there always exist
good ($\varepsilon$-optimal, resp. optimal) strategies in class $X$ (e.g., MD,
MR, FD, FR, etc.) for objective ${\varphi}$.

Lower bounds on the strategy complexity of an objective ${\varphi}$ can only
be established in the sense of proving that good strategies for ${\varphi}$ do
not exist in some classes $Y$, $Z$, etc. Classes of strategies that use
different types of _restricted_ infinite memory are generally not comparable,
e.g., step counter strategies are incomparable to reward counter strategies.
In particular, there is no weakest type of infinite memory with restricted
use. Therefore statements like “good strategies for objective ${\varphi}$
require at least a step counter” are always _relative_ to the considered
alternative strategy classes. In this paper, we only consider the strategy
classes of memoryless, finite memory, step counter, reward counter and
_combinations thereof_. Thus, when we write in Table 1 that an objective
requires a step counter (SC), it just means that a reward counter (RC) plus
finite memory is not sufficient.

For our upper bounds, we use deterministic strategies. Moreover, we show that
allowing randomization does not help to reduce the strategy complexity, in the
sense of Remark 2.1.

##  3 When is a step counter not sufficient?

In this section we will prove that strategies with a step counter plus
arbitrary finite memory are not sufficient for $\varepsilon$-optimal
strategies for ${\it MP}_{\liminf\geq 0}$ or ${\it TP}_{\liminf\geq 0}$. We
will construct an acyclic MDP where the step counter is implicit in the state
such that $\varepsilon$-optimal strategies for ${\it MP}_{\liminf\geq 0}$ and
${\it TP}_{\liminf\geq 0}$ still require infinite memory.

###  3.1 Epsilon-optimal strategies

We construct an acyclic MDP $\mathcal{M}$ in which the step counter is
implicit in the state as follows.

$s_{n}$$c_{n}$$s_{n+1}$$\perp$$\delta_{k(n)}(n)$$+k(n)m_{n}$$\delta_{j}(n)$$+jm_{n}$$\delta_{1}(n)$$+m_{n}$$\delta_{0}(n)$$+0$$-k(n)m_{n}$$-0$$\varepsilon_{0}(n)$$\varepsilon_{1}(n)$$-m_{n}$$-jm_{n}$$\varepsilon_{j}(n)$
Figure 1: A typical building block with $k(n)+1$ choices, first random then
controlled. The number of choices $k(n)+1$ grows unboundedly with $n$. This is
the $n$-th building block of the MDP in Figure 2. The $\delta_{i}(n)$ and
$\varepsilon_{i}(n)$ are probabilities depending on $n$ and the $\pm im_{n}$
are transition rewards. We index the successor states of $s_{n}$ and $c_{n}$
from $0$ to $k(n)$ to match the indexing of the $\delta$’s and $\varepsilon$’s
such that the bottom state is indexed with $0$ and the top state with $k(n)$.
$s_{0}$B1B2B3B4B5$+0$$+1$$+2$$+3$$-1$$-1$$-1$$-1$$4$ steps Figure 2: The
buildings blocks from Figure 1 represented by black boxes are chained together
($n$ increases as you go to the right). The chain of white boxes allows to
skip arbitrarily long prefixes while preserving path length. The positive
rewards from the white states to the black boxes reimburse the lost reward
accumulated until then. The $-1$ rewards between white states ensure that
skipping gadgets forever is losing.

The system consists of a sequence of gadgets. Figure 1 depicts a typical
building block in this system. The system consists of these gadgets chained
together as illustrated in Figure 2, starting with $n$ sufficiently high at
$n=N^{*}$. In the controlled choice, there is a small chance in all but the
top choice of falling into a $\bot$ state. These $\bot$ states are
abbreviations for an infinite chain of states with $-1$ reward on the
transitions and are thus losing. The intuition behind the construction is that
there is a random transition with branching degree $k(n)+1$. Then, the only
way to win, in the controlled states, is to play the $i$-th choice if one
arrived from the $i$-th choice. Thus intuitively, to remember what this choice
was, one requires at least $k(n)+1$ memory modes. That is to say, the one and
only way to win is to mimic, and mimicry requires memory.

######  Remark 3.1.

$\mathcal{M}$ is acyclic, finitely branching and for every state $s\in
S,\exists n_{s}\in\mathbb{N}$ such that every path from $s_{0}$ to $s$ has
length $n_{s}$. That is to say the step counter is implicit in the state.

Additionally, the number of transitions in each gadget now grows unboundedly
with $n$ according to the function $k(n)$. Consequently, we will show that the
number of memory modes required to play correctly grows above every finite
bound. This will imply that no finite amount of memory suffices for
$\varepsilon$-optimal strategies.

Notation: All logarithms are assumed to be in base $e$.

$\displaystyle\text{log}_{1}n\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{log}n,\quad\text{log}_{i+1}n\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{log}(\text{log}_{i}n)$
$\displaystyle\delta_{0}(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\dfrac{1}{\text{log}n},\quad\delta_{i}(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\dfrac{1}{\text{log}_{i+1}n},\quad\delta_{k(n)}(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1-\sum_{j=0}^{k(n)-1}\delta_{j}(n)$
$\displaystyle\varepsilon_{0}(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\dfrac{1}{n\text{log}n},\
\varepsilon_{i+1}(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\dfrac{\varepsilon_{i}(n)}{\text{log}_{i+2}n},\
\text{i.e.
}\varepsilon_{i}(n)=\dfrac{1}{n\cdot\text{log}n\cdot\text{log}_{2}n\cdots\text{log}_{i+1}n},\varepsilon_{k(n)}(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}0$
$\displaystyle\text{Tower}(0)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}e^{0}=1,\quad\text{Tower}(i+1)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}e^{\text{Tower}(i)},\quad
N_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{Tower}(i)$

######  Lemma 3.2.

The family of series $\sum_{n>N_{j}}\delta_{j}(n)\cdot\varepsilon_{i}(n)$ is
divergent for all $i,j\in\mathbb{N}$, $i<j$.

Additionally, the related family of series
$\sum_{n>N_{i}}\delta_{i}(n)\cdot\varepsilon_{i}(n)$ is convergent for all
$i\in\mathbb{N}.$

######  Proof 3.3.

These are direct consequences of Cauchy’s Condensation Test.

######  Definition 3.4.

We define $k(n)$, the rate at which the number of transitions grows. We define
$k(n)$ in terms of fast growing functions $g,\text{Tower}$ and $h$ defined for
$i\geq 1$ as follows:

$g(i)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{min}\left\\{N:\left(\sum_{n>N}\delta_{i-1}(n)\varepsilon_{i-1}(n)\right)\leq
2^{-i}\right\\},\quad h(1)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}2$

$h(i+1)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\left\lceil\text{max}\left\\{g(i+1),\text{Tower}(i+2),\text{min}\left\\{m+1\in\mathbb{N}:\sum^{m}_{n=h(i)}\varepsilon_{i-1}(n)\geq
1\right\\}\right\\}\right\rceil.$

Note that function $g$ is well defined by Lemma 3.2, and $h(i+1)$ is well
defined since for all $i$, $\sum^{\infty}_{n=h(i)}\varepsilon_{i-1}(n)$
diverges to infinity. $k(n)$ is a slow growing unbounded step function defined
in terms of $h$ as
$k(n)\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}h^{-1}(n)$. The Tower
function features in the definition to ensure that the transition
probabilities are always well defined. $g$ and $h$ are used to smooth the
proofs of Lemma 3.6 and 3 respectively. _Notation:_
$N^{*}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{min}\\{n\in\mathbb{N}:k(n)=1\\}$.
This is intuitively the first natural number for which the construction is
well defined.

The reward $m_{n}$ which appears in the $n$-th gadget is defined such that it
outweighs any possible reward accumulated up to that point in previous
gadgets. As such we define
$m_{n}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}2k(n)\sum_{i=N^{*}}^{n-1}m_{i},$
with $m_{N^{*}}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1$ and where
$k(n)$ is the branching degree.

To simplify the notation, the state $s_{0}$ in our theorem statements refers
to $s_{N^{*}}$.

######  Lemma 3.5.

For $k(n)\geq 1$, the transition probabilities in the gadgets are well
defined.

######  Lemma 3.6.

For every $\varepsilon>0$, there exists a strategy $\sigma_{\varepsilon}$ with
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma_{\varepsilon}}({\it
MP}_{\liminf\geq 0})\geq 1-\varepsilon$ that cannot fail unless it hits a
$\perp$ state. Formally,
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma_{\varepsilon}}({\it
MP}_{\liminf\geq 0}\wedge{\sf
G}(\neg\perp))={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma_{\varepsilon}}({\sf
G}(\neg\perp))\geq 1-\varepsilon$. So in particular,
${\mathtt{val}_{{\mathcal{M}},{\it MP}_{\liminf\geq 0}}(s_{0})}=1$.

######  Proof 3.7 (Proof sketch).

(Full proof in Appendix B.) We define a strategy $\sigma$ which in $c_{n}$
always mimics the choice in $s_{n}$. Playing according to $\sigma$, the only
way to lose is by dropping into the $\perp$ state. This is because by
mimicking, the player finishes each gadget with a reward of 0. From $s_{0}$,
the probability of surviving while playing in all the gadgets is

$\prod_{n\geq
N^{*}}\left(1-\sum_{j=0}^{k(n)-1}\delta_{j}(n)\cdot\varepsilon_{j}(n)\right)>0.$

Hence the player has a non zero chance of winning when playing $\sigma$.

When playing with the ability to skip gadgets, as illustrated in Figure 2, all
runs not visiting a $\bot$ state are winning since the total reward never dips
below $0$. We then consider the strategy $\sigma_{\varepsilon}$ which plays
like $\sigma$ after skipping forwards by sufficiently many gadgets (starting
at $n\gg N^{*}$). Its probability of satisfying ${\it MP}_{\liminf\geq 0}$
corresponds to a tail of the above product, which can be made arbitrarily
close to $1$ (and thus $\geq 1-\varepsilon$) by Proposition B.4. Thus the
strategies $\sigma_{\varepsilon}$ for arbitrarily small $\varepsilon>0$
witness that ${\mathtt{val}_{{\mathcal{M}},{\it MP}_{\liminf\geq
0}}(s_{0})}=1$.

######  Lemma 3.8.

For any FR strategy $\sigma$, almost surely either the mean payoff dips below
$-1$ infinitely often, or the run hits a $\perp$ state, i.e.
${\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\it MP}_{\liminf\geq 0})=0$.

######  Proof 3.9 (Proof sketch).

(Full proof in Appendix B.) Let $\sigma$ be some FR strategy with $k$ memory
modes. We prove a _lower bound_ $e_{n}$ on the probability of a local error
(reaching a $\bot$ state, or seeing a mean payoff $\leq-1$) in the current
$n$-th gadget. This lower bound $e_{n}$ holds regardless of events in past
gadgets, regardless of the memory mode of $\sigma$ upon entering the $n$-th
gadget, and cannot be improved by $\sigma$ randomizing its memory updates.

The main idea is that, once $k(n)>k+1$ (which holds for $n\geq N^{\prime}$
sufficiently large) by the Pigeonhole Principle there will always be a memory
mode confusing at least two different branches $i(n),j(n)\neq k(n)$ of the
previous random choice at state $s_{n}$. This confusion yields a probability
$\geq e_{n}$ of reaching a $\bot$ state or seeing a mean payoff $\leq-1$,
regardless of events in past gadgets and regardless of the memory upon
entering the $n$-th gadget. We show that $\sum_{n\geq N^{\prime}}e_{n}$ is a
_divergent_ series. Thus, by Proposition B.2, $\prod_{n\geq
N^{\prime}}(1-e_{n})=0$. Hence, ${\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\it
MP}_{\liminf\geq 0})\leq\prod_{n\geq N^{\prime}}(1-e_{n})=0$.

Lemma 3.6 and Lemma 3.8 yield the following theorem.

######  Theorem 3.10.

There exists a countable, finitely branching and acyclic MDP $\mathcal{M}$
whose step counter is implicit in the state for which
${\mathtt{val}_{{\mathcal{M}},{\it MP}_{\liminf\geq 0}}(s_{0})}=1$ and any FR
strategy $\sigma$ is such that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it MP}_{\liminf\geq 0})=0$. In
particular, there are no $\varepsilon$-optimal $k$-bit Markov strategies for
any $k\in\mathbb{N}$ and any $\varepsilon<1$ for ${\it MP}_{\liminf\geq 0}$ in
countable MDPs.

All of the above results/proofs also hold for ${\it TP}_{\liminf\geq 0}$,
giving us the following theorem.

######  Theorem 3.11.

There exists a countable, finitely branching and acyclic MDP $\mathcal{M}$
whose step counter is implicit in the state for which
${\mathtt{val}_{{\mathcal{M}},{\it TP}_{\liminf\geq 0}}(s_{0})}=1$ and any FR
strategy $\sigma$ is such that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it TP}_{\liminf\geq 0})=0$. In
particular, there are no $\varepsilon$-optimal $k$-bit Markov strategies for
any $k\in\mathbb{N}$ and any $\varepsilon<1$ for ${\it TP}_{\liminf\geq 0}$ in
countable MDPs.

###  3.2 Optimal strategies

$s_{0}$$i$$i+1$$i+2$$i+1$$i+2$$i+3$$r_{i,1}$$r_{i+1,1}$$r_{i+2,1}$$-m_{i+2}$$+m_{i+2}$$-m_{i+3}$$+m_{i+3}$$-m_{i+4}$
Figure 3: Each row represents a copy of the MDP depicted in Figure 2. Each
white circle labeled with a number $i$ represents the correspondingly numbered
gadget (like in Figure 1) from that MDP. Now, instead of the bottom states in
each gadget leading to an infinite losing chain, they lead to a restart state
$r_{i,j}$ which leads to a fresh copy of the MDP (in the next row). Each
restart incurs a penalty guaranteeing that the mean payoff dips below $-1$
before refunding it and continuing on in the next copy of the MDP. The states
$r_{i,j}$ are labeled such that the $j$ indicates that if a run sees this
state, then it is the $j$th restart. The $i$ indicates that the run entered
the restart state from the $i$th gadget of the current copy of the MDP. The
black states are dummy states inserted in order to preserve path length
throughout.

Even for acyclic MDPs with the step counter implicit in the state, optimal
(and even almost sure winning) strategies for ${\it MP}_{\liminf\geq 0}$
require infinite memory. To prove this, we consider a variant of the MDP from
the previous section which has been augmented to include restarts from the
$\perp$ states. For the rest of the section, $\mathcal{M}$ is the MDP
constructed in Figure 3.

######  Remark 3.12.

$\mathcal{M}$ is acyclic, finitely branching and the step counter is implicit
in the state. We now refer to the rows of Figure 3 as gadgets, i.e., a gadget
is a single instance of Figure 2 where the $\perp$ states lead to the next
row.

######  Lemma 3.13.

There exists a strategy $\sigma$ such that
${\mathcal{P}}_{{\mathcal{M}},\sigma,s_{0}}({\it MP}_{\liminf\geq 0})=1$.

######  Proof 3.14 (Proof sketch).

(Full proof in Appendix B.) Recall the strategy $\sigma_{1/2}$ defined in
Lemma 3.6 which achieves at least $1/2$ in each gadget that it is played in.
We then construct the almost surely winning strategy $\sigma$ by concatenating
$\sigma_{1/2}$ strategies in the sense that $\sigma$ plays just like
$\sigma_{1/2}$ in each gadget from each gadget’s start state.

Since $\sigma$ achieves at least $1/2$ in every gadget that it sees, with
probability 1, runs generated by $\sigma$ restart only finitely many times.
The intuition is then that a run restarting finitely many times must spend an
infinite tail in some final gadget. Since $\sigma$ mimics in every controlled
state, not restarting anymore directly implies that the total payoff is
eventually always $\geq 0$. Hence all runs generated by $\sigma$ and
restarting only finitely many times satisfy ${\it MP}_{\liminf\geq 0}$.
Therefore all but a nullset of runs generated by $\sigma$ are winning, i.e.
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it MP}_{\liminf\geq 0})=1$.

######  Lemma 3.15.

For any FR strategy $\sigma$, ${\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\it
MP}_{\liminf\geq 0})=0$.

######  Proof 3.16 (Proof sketch).

(Full proof in Appendix B.) Let $\sigma$ be any FR strategy. We partition the
runs generated by $\sigma$ into runs restarting infinitely often, and those
restarting only finitely many times. Any runs restarting infinitely often are
losing by construction. Those runs restarting only finitely many times, once
in the gadget they spend an infinite tail in, let the mean payoff dip below
$-1$ infinitely many times with probability 1 by Lemma 3.8. Hence we have that
${\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\it MP}_{\liminf\geq 0})=0$.

From Lemma 3.13 and Lemma 3.15 we obtain the following theorem.

######  Theorem 3.17.

There exists a countable, finitely branching and acyclic MDP $\mathcal{M}$
whose step counter is implicit in the state for which $s_{0}$ is almost surely
winning ${\it MP}_{\liminf\geq 0}$, i.e.,
$\exists\hat{\sigma}\,{\mathcal{P}}_{{\mathcal{M}},s_{0},\hat{\sigma}}({\it
MP}_{\liminf\geq 0})=1$, but every FR strategy $\sigma$ is such that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it MP}_{\liminf\geq 0})=0$. In
particular, almost sure winning strategies, when they exist, cannot be chosen
$k$-bit Markov for any $k\in\mathbb{N}$ for countable MDPs.

All of the above results/proofs also hold for ${\it TP}_{\liminf\geq 0}$,
giving us the following theorem.

######  Theorem 3.18.

There exists a countable, finitely branching and acyclic MDP $\mathcal{M}$
whose step counter is implicit in the state for which $s_{0}$ is almost surely
winning ${\it TP}_{\liminf\geq 0}$, i.e.,
$\exists\hat{\sigma}\,{\mathcal{P}}_{{\mathcal{M}},s_{0},\hat{\sigma}}({\it
TP}_{\liminf\geq 0})=1$, but every FR strategy $\sigma$ is such that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it TP}_{\liminf\geq 0})=0$. In
particular, almost sure winning strategies, when they exist, cannot be chosen
$k$-bit Markov for any $k\in\mathbb{N}$ for countable MDPs.

##  4 When is a reward counter not sufficient?

In this part we show that a reward counter plus arbitrary finite memory does
not suffice for ($\varepsilon$-)optimal strategies for ${\it MP}_{\liminf\geq
0}$, even if the MDP is finitely branching.

The same lower bound holds for ${\it TP}_{\liminf\geq 0}$/${\it
PP}_{\liminf\geq 0}$, but only in infinitely branching MDPs. The finitely
branching case is different for ${\it TP}_{\liminf\geq 0}$/${\it
PP}_{\liminf\geq 0}$; cf. Section 5.

The techniques used to prove these results are similar to those in Section 3
and proofs can be found in Appendix C.

######  Theorem 4.1.

There exists a countable, finitely branching, acyclic MDP
${\mathcal{M}}_{\text{\emph{RI}}}$ with initial state $(s_{0},0)$ with the
total reward implicit in the state such that

  * •

${\mathtt{val}_{{\mathcal{M}}_{\text{\emph{RI}}},{\it MP}_{\liminf\geq
0}}((s_{0},0))}=1$,

  * •

for all FR strategies $\sigma$, we have
${\mathcal{P}}_{{\mathcal{M}}_{\text{\emph{RI}}},(s_{0},0),\sigma}({\it
MP}_{\liminf\geq 0})=0$.

######  Theorem 4.2.

There exists a countable, finitely branching and acyclic MDP
${\mathcal{M}}_{\text{\emph{Restart}}}$ whose total reward is implicit in the
state where, for the initial state $s_{0}$,

  * •

there exists an HD strategy $\sigma$ s.t.
${\mathcal{P}}_{{\mathcal{M}}_{\text{\emph{Restart}}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})=1$.

  * •

for every FR strategy $\sigma$,
${\mathcal{P}}_{{\mathcal{M}}_{\text{\emph{Restart}}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})=0$.

######  Theorem 4.3.

There exists an infinitely branching MDP ${\mathcal{M}}$ as in Figure 7 with
reward implicit in the state and initial state $s$ such that

  * •

every FR strategy $\sigma$ is such that
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\it TP}_{\liminf\geq 0})=0$ and
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\it PP}_{\liminf\geq 0})=0$

  * •

there exists an HD strategy $\sigma$ s.t.
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\it TP}_{\liminf\geq 0})=1$ and
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}({\it PP}_{\liminf\geq 0})=1$.

Hence, optimal (and even almost-surely winning) strategies and
$\varepsilon$-optimal strategies for ${\it TP}_{\liminf\geq 0}$ and ${\it
PP}_{\liminf\geq 0}$ require infinite memory beyond a reward counter.

######  Remark 4.4.

The MDPs from Section 3 and Section 4 show that good strategies for ${\it
MP}_{\liminf\geq 0}$ require at least (in the sense of Remark 2.1) a reward
counter and a step counter, respectively. There does, of course, exist a
_single MDP_ where good strategies for ${\it MP}_{\liminf\geq 0}$ require at
least both a step counter and a reward counter. We construct such an MDP by
‘gluing’ the two different MDPs together via an initial random state which
points to each with probability $1/2$.

##  5 Upper bounds

We establish upper bounds on the strategy complexity of $\liminf$ threshold
objectives for mean payoff, total payoff and point payoff. It is noteworthy
that once the reward structure of an MDP has been encoded into the states,
then these threshold objectives take on a qualitative flavor not dissimilar to
Safety or co-Büchi (cf. [16]). Indeed, if the transition rewards are
restricted to integer values, then ${\it TP}_{\liminf\geq 0}$ boils down to
eventually avoiding all transitions with negative reward (since negative
rewards would be $\leq-1$). This is a co-Büchi objective. However, if the
rewards are not restricted to integers, then the picture is not so simple.

For _finitely branching_ MDPs, we show that there exist $\varepsilon$-optimal
MD strategies for ${\it PP}_{\liminf\geq 0}$. In turn, this yields the
requisite upper bound for finitely branching ${\it TP}_{\liminf\geq 0}$, i.e.,
using just a reward counter.

For _infinitely branching_ MDPs, a step counter suffices in order to achieve
${\it PP}_{\liminf\geq 0}$ $\varepsilon$-optimally. Then, by encoding the
total reward into the states, this will also give us SC+RC upper bounds for
${\it MP}_{\liminf\geq 0}$ as well as infinitely branching ${\it
TP}_{\liminf\geq 0}$ (i.e., using both a step counter and a reward counter).

First we show how to encode the total reward level into the state in a given
MDP.

######  Remark 5.1.

Given an MDP ${\mathcal{M}}$ and initial state $s_{0}$, we can construct an
MDP $R({\mathcal{M}})$ with initial state $(s_{0},0)$ and with the reward
counter implicit in the state such that strategies in $R({\mathcal{M}})$ can
be translated back to ${\mathcal{M}}$ with an extra reward counter; cf.
Definition D.1 for a formal definition.

By labeling transitions in $R({\mathcal{M}})$ with the state encoded total
reward of the target state, we ensure that the point rewards in
$R({\mathcal{M}})$ correspond exactly to the total rewards in ${\mathcal{M}}$.

######  Lemma 5.2.

Let ${\mathcal{M}}$ be an MDP with initial state $s_{0}$. Then given an MD
(resp. Markov) strategy $\sigma^{\prime}$ in $R({\mathcal{M}})$ attaining
$c\in[0,1]$ for ${\it PP}_{\liminf\geq 0}$ from $(s_{0},0)$, there exists a
strategy $\sigma$ attaining $c$ for ${\it TP}_{\liminf\geq 0}$ in
${\mathcal{M}}$ from $s_{0}$ which uses the same memory as $\sigma^{\prime}$
plus a reward counter.

######  Remark 5.3.

Given an MDP ${\mathcal{M}}$ and initial state $s_{0}$, we can construct an
acyclic MDP $S({\mathcal{M}})$ with initial state $(s_{0},0)$ and with the
step counter implicit in the state such that MD strategies in
$S({\mathcal{M}})$ can be translated back to ${\mathcal{M}}$ with the use of a
step counter to yield deterministic Markov strategies in ${\mathcal{M}}$; cf.
[15, Lemma 4].

######  Remark 5.4.

In order to tackle the mean payoff objective ${\it MP}_{\liminf\geq 0}$ on
${\mathcal{M}}$, we define a new acyclic MDP $A({\mathcal{M}})$ which encodes
both the step counter and the average reward into the state. However, since we
want the point rewards in $A({\mathcal{M}})$ to coincide with the _mean
payoff_ in the original MDP ${\mathcal{M}}$, the transition rewards in
$A({\mathcal{M}})$ are given as the encoded rewards divided by the step
counter (unlike in $R({\mathcal{M}})$); cf. Definition D.3 for a formal
definition.

######  Lemma 5.5.

Let ${\mathcal{M}}$ be an MDP with initial state $s_{0}$. Then given an MD
strategy $\sigma^{\prime}$ in $A({\mathcal{M}})$ attaining $c\in[0,1]$ for
${\it PP}_{\liminf\geq 0}$ from $(s_{0},0,0)$, there exists a strategy
$\sigma$ attaining $c$ for ${\it MP}_{\liminf\geq 0}$ in ${\mathcal{M}}$ from
$s_{0}$ which uses just a reward counter and a step counter.

######  Proof 5.6.

The proof is very similar to that of Lemma 5.2.

######  Lemma 5.7.

([15, Lemma 23]) For every acyclic MDP with a safety objective and every
$\varepsilon>0$, there exists an MD strategy that is uniformly
$\varepsilon$-optimal.

######  Theorem 5.8.

([13, Theorem 7]) Let
${\mathcal{M}}=(S,S_{\Box},S_{\ocircle},{\longrightarrow},P,r)$ be a countable
MDP, and let ${\varphi}$ be an event that is tail in ${\mathcal{M}}$. Suppose
for every $s\in S$ there exist $\varepsilon$-optimal MD strategies for
${\varphi}$. Then:

1.

There exist uniform $\varepsilon$-optimal MD strategies for ${\varphi}$.

2.

There exists a single MD strategy that is optimal from every state that has an
optimal strategy.

###  5.1 Finitely Branching Case

In order to prove the main result of this section, we use the following result
on the $\mathtt{Transience}$ objective, which is the set of runs that do not
visit any state infinitely often. Given an MDP
${\mathcal{M}}=(S,S_{\Box},S_{\ocircle},{\longrightarrow},P,r)$,
$\mathtt{Transience}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigwedge_{s\in
S}{\sf F}{\sf G}\neg s$.

######  Theorem 5.9.

([13, Theorem 8]) In every countable MDP there exist uniform
$\varepsilon$-optimal MD strategies for $\mathtt{Transience}$.

######  Theorem 5.10.

Consider a finitely branching MDP
${\mathcal{M}}=(S,S_{\Box},S_{\ocircle},{\longrightarrow},P,r)$ with initial
state $s_{0}$ and a ${\it PP}_{\liminf\geq 0}$ objective. Then there exist
$\varepsilon$-optimal MD strategies.

######  Proof 5.11.

Let $\varepsilon>0$. We begin by partitioning the state space into two sets,
$S_{\text{safe}}$ and $S\setminus S_{\text{safe}}$. The set $S_{\text{safe}}$
is the subset of states which is surely winning for the safety objective of
only using transitions with non-negative rewards (i.e., never using
transitions with negative rewards at all). Since ${\mathcal{M}}$ is finitely
branching, there exists a uniformly optimal MD strategy $\sigma_{\text{safe}}$
for this safety objective [18, 16].

We construct a new MDP ${\mathcal{M}}^{\prime}$ by modifying ${\mathcal{M}}$.
We create a gadget $G_{\text{safe}}$ composed of a sequence of new controlled
states $x_{0},x_{1},x_{2},\dots$ where all transitions $x_{i}\to x_{i+1}$ have
reward $0$. Hence any run entering $G_{\text{safe}}$ is winning for ${\it
PP}_{\liminf\geq 0}$. We insert $G_{\text{safe}}$ into ${\mathcal{M}}$ by
replacing all incoming transitions to $S_{\text{safe}}$ with transitions that
lead to $x_{0}$. The idea behind this construction is that when playing in
${\mathcal{M}}$, once you hit a state in $S_{\text{safe}}$, you can win surely
by playing an optimal MD strategy for safety. So we replace $S_{\text{safe}}$
with the surely winning gadget $G_{\text{safe}}$. Thus

${\mathtt{val}_{{\mathcal{M}},{\it PP}_{\liminf\geq
0}}(s_{0})}={\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}$ (1)

and if an $\varepsilon$-optimal MD strategy exists in ${\mathcal{M}}$, then
there exists a corresponding one in ${\mathcal{M}}^{\prime}$, and vice-versa.

We now consider a general (not necessarily MD) $\varepsilon$-optimal strategy
$\sigma$ for ${\it PP}_{\liminf\geq 0}$ from $s_{0}$ on
${\mathcal{M}}^{\prime}$, i.e.,

${\mathcal{P}}_{{\mathcal{M}}^{\prime},s_{0},\sigma}({\it PP}_{\liminf\geq
0})\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-\varepsilon.$ (2)

Define the safety objective $\text{Safety}_{i}$ which is the objective of
never seeing any point rewards $<-2^{-i}$. This then allows us to characterize
${\it PP}_{\liminf\geq 0}$ in terms of safety objectives.

${\it PP}_{\liminf\geq 0}=\bigcap_{i\in\mathbb{N}}{\sf F}(\text{Safety}_{i}).$
(3)

Now we define the safety objective
$\text{Safety}_{i}^{k}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\sf
F}^{\leq k}(\text{Safety}_{i})$ to attain $\text{Safety}_{i}$ within at most
$k$ steps. This allows us to write

${\sf F}(\text{Safety}_{i})=\bigcup_{k\in\mathbb{N}}\text{Safety}_{i}^{k}.$
(4)

By continuity of measures from above we get

$0=\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left({\sf
F}(\text{Safety}_{i})\cap\bigcap_{k\in\mathbb{N}}\overline{\text{Safety}^{k}_{i}}\right)=\lim_{k\to\infty}\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left({\sf
F}(\text{Safety}_{i})\cap\overline{\text{Safety}^{k}_{i}}\right).$

Hence for every $i\in\mathbb{N}$ and
$\varepsilon_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\varepsilon\cdot
2^{-i}$ there exists $n_{i}$ such that

$\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left({\sf
F}(\text{Safety}_{i})\cap\overline{\text{Safety}^{n_{i}}_{i}}\right)\leq\varepsilon_{i}.$
(5)

Now we can show the following claim (proof in Section D.1).

######  Claim 1.

${\mathcal{P}}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it
PP}_{\liminf\geq 0}}(s_{0})}-2\varepsilon.$

Since ${\mathcal{M}}^{\prime}$ does not have an implicit step counter, we use
the following construction to approximate one. We define the distance $d(s)$
from $s_{0}$ to a state $s$ as the length of the shortest path from $s_{0}$ to
$s$. Let
$\text{Bubble}_{n}(s_{0})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{s\in
S\mid d(s)\leq n\\}$ be those states that can be reached within $n$ steps from
$s_{0}$. Since ${\mathcal{M}}^{\prime}$ is finitely branching,
$\text{Bubble}_{n}(s_{0})$ is finite for every fixed $n$. Let

$\text{Bad}_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{t\in\longrightarrow_{{\mathcal{M}}^{\prime}}\mid
t=s\longrightarrow_{{\mathcal{M}}^{\prime}}s^{\prime},s\notin\text{Bubble}_{n_{i}}(s_{0})\text{
and }r(t)<-2^{-i}\\}$

be the set of transitions originating outside $\text{Bubble}_{n_{i}}(s_{0})$
whose reward is too negative. Thus a run from $s_{0}$ that satisfies
$\text{Safety}_{i}^{n_{i}}$ cannot use any transition in $\text{Bad}_{i}$,
since (by definition of $\text{Bubble}_{n_{i}}(s_{0})$) they would come after
the $n_{i}$-th step.

Now we create a new state $\perp$ whose only outgoing transition is a self
loop with reward $-1$. We transform ${\mathcal{M}}^{\prime}$ into
${\mathcal{M}}^{\prime\prime}$ by re-directing all transitions in
$\text{Bad}_{i}$ to the new target state $\perp$ for every $i$. Notice that
any run visiting $\perp$ must be losing for ${\it PP}_{\liminf\geq 0}$ due to
the negative reward on the self loop, but it must also be losing for
$\mathtt{Transience}$ because of the self loop.

We now show that the change from ${\mathcal{M}}^{\prime}$ to
${\mathcal{M}}^{\prime\prime}$ has decreased the value of $s_{0}$ for ${\it
PP}_{\liminf\geq 0}$ by at most $2\varepsilon$, i.e.,

${\mathtt{val}_{{\mathcal{M}}^{\prime\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-2\varepsilon.$ (6)

Equation 6 follows from the following steps.

$\displaystyle{\mathtt{val}_{{\mathcal{M}}^{\prime\prime},{\it
PP}_{\liminf\geq 0}}(s_{0})}$
$\displaystyle\geq{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma}\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)$
by def. of ${\mathcal{M}}^{\prime\prime}$
$\displaystyle\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-2\varepsilon$ by 1

In the next step (proof in Section D.1) we argue that under _every_ strategy
$\sigma^{\prime\prime}$ from $s_{0}$ in ${\mathcal{M}}^{\prime\prime}$ the
attainment for ${\it PP}_{\liminf\geq 0}$ and $\mathtt{Transience}$ coincide,
i.e.,

######  Claim 2.

$\forall\sigma^{\prime\prime}.\,{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq
0})={\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}(\mathtt{Transience}).$

By Theorem 5.9, there exists a uniformly $\varepsilon$-optimal MD strategy
$\widehat{\sigma}$ from $s_{0}$ for $\mathtt{Transience}$ in
${\mathcal{M}}^{\prime\prime}$, i.e.,

${\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\hat{\sigma}}(\mathtt{Transience})\geq{\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\mathtt{Transience}}(s_{0})}-\varepsilon.$
(7)

We construct an MD strategy $\sigma^{*}$ in ${\mathcal{M}}$ which plays like
$\sigma_{\text{safe}}$ in $S_{\text{safe}}$ and plays like $\widehat{\sigma}$
everywhere else.

$\displaystyle{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma^{*}}({\it
PP}_{\liminf\geq 0})$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}}^{\prime},s_{0},\hat{\sigma}}({\it
PP}_{\liminf\geq 0})$ def. of $\sigma^{*}$ and $\sigma_{\text{safe}}$
$\displaystyle\geq{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\hat{\sigma}}({\it
PP}_{\liminf\geq 0})$ new losing sink in ${\mathcal{M}}^{\prime\prime}$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\hat{\sigma}}(\mathtt{Transience})$
by 2
$\displaystyle\geq{\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\mathtt{Transience}}(s_{0})}-\varepsilon$
by (7) $\displaystyle={\mathtt{val}_{{\mathcal{M}}^{\prime\prime},{\it
PP}_{\liminf\geq 0}}(s_{0})}-\varepsilon$ by 2
$\displaystyle\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-2\varepsilon-\varepsilon$ by (6)
$\displaystyle={\mathtt{val}_{{\mathcal{M}},{\it PP}_{\liminf\geq
0}}(s_{0})}-3\varepsilon$ by (1)

Hence $\sigma^{*}$ is a $3\varepsilon$-optimal MD strategy for ${\it
PP}_{\liminf\geq 0}$ from $s_{0}$ in ${\mathcal{M}}$ as required.

######  Corollary 5.12.

Given a finitely branching MDP ${\mathcal{M}}$, there exist
$\varepsilon$-optimal strategies for ${\it TP}_{\liminf\geq 0}$ which use just
a reward counter.

######  Proof 5.13.

By Theorem 5.10 and Lemma 5.2.

######  Corollary 5.14.

Given a finitely branching MDP ${\mathcal{M}}$ and initial state $s_{0}$,
optimal strategies, where they exist,

  * •

for ${\it PP}_{\liminf\geq 0}$ can be chosen MD.

  * •

for ${\it TP}_{\liminf\geq 0}$ can be chosen with just a reward counter.

######  Proof 5.15.

Since ${\it PP}_{\liminf\geq 0}$ is tail, the first claim follows from Theorem
5.10 and Theorem 5.8.

Towards the second claim, we place ourselves in $R({\mathcal{M}})$ where ${\it
TP}_{\liminf\geq 0}$ is tail. Moreover, in $R({\mathcal{M}})$ the objectives
${\it TP}_{\liminf\geq 0}$ and ${\it PP}_{\liminf\geq 0}$ coincide. Thus we
can apply Theorem 5.10 to obtain $\varepsilon$-optimal MD strategies for ${\it
TP}_{\liminf\geq 0}$ from every state of $R({\mathcal{M}})$. From Theorem 5.8
we obtain a single MD strategy that is optimal from every state of
$R({\mathcal{M}})$ that has an optimal strategy. By Lemma 5.2 we can translate
this MD strategy on $R({\mathcal{M}})$ back to a strategy on ${\mathcal{M}}$
with just a reward counter.

###  5.2 Infinitely Branching Case

For infinitely branching MDPs, $\varepsilon$-optimal strategies for ${\it
PP}_{\liminf\geq 0}$ require more memory than in the finitely branching case.
However, the proofs are similar to those in Section 5.1 and can be found in
Section D.2.

######  Theorem 5.16.

Consider an MDP ${\mathcal{M}}$ with initial state $s_{0}$ and a ${\it
PP}_{\liminf\geq 0}$ objective. For every $\varepsilon>0$ there exist

  * •

$\varepsilon$-optimal MD strategies in $S({\mathcal{M}})$.

  * •

$\varepsilon$-optimal deterministic Markov strategies in ${\mathcal{M}}$.

######  Corollary 5.17.

Given an MDP ${\mathcal{M}}$ and initial state $s_{0}$, there exist
$\varepsilon$-optimal strategies $\sigma$ for ${\it MP}_{\liminf\geq 0}$ which
use just a step counter and a reward counter.

######  Corollary 5.18.

Given an MDP ${\mathcal{M}}$ with initial state $s_{0}$,

  * •

there exist $\varepsilon$-optimal MD strategies for ${\it TP}_{\liminf\geq 0}$
in $S(R({\mathcal{M}}))$,

  * •

there exist $\varepsilon$-optimal strategies for ${\it TP}_{\liminf\geq 0}$
which use a step counter and a reward counter.

######  Corollary 5.19.

Given an MDP ${\mathcal{M}}$ and initial state $s_{0}$, optimal strategies,
where they exist,

  * •

for ${\it PP}_{\liminf\geq 0}$ can be chosen with just a step counter.

  * •

for ${\it MP}_{\liminf\geq 0}$ and ${\it TP}_{\liminf\geq 0}$ can be chosen
with just a reward counter and a step counter.

##  6 Conclusion and Outlook

We have established matching lower and upper bounds on the strategy complexity
of $\liminf$ threshold objectives for point, total and mean payoff on
countably infinite MDPs; cf. Table 1.

The upper bounds hold not only for integer transition rewards, but also for
rationals or reals, provided that the reward counter (in those cases where one
is required) is of the same type. The lower bounds hold even for integer
transition rewards, since all our counterexamples are of this form.

Directions for future work include the corresponding questions for $\limsup$
threshold objectives. While the $\liminf$ point payoff objective generalizes
co-Büchi (see Section 2), the $\limsup$ point payoff objective generalizes
Büchi. Thus the lower bounds for $\limsup$ point payoff are at least as high
as the lower bounds for Büchi objectives [14, 15].

## References

  * [1] Pieter Abbeel and Andrew Y. Ng.  Learning first-order Markov models for control.  In Advances in Neural Information Processing Systems 17, pages 1–8. MIT Press, 2004.  URL: http://papers.nips.cc/paper/2569-learning-first-order-markov-models-for-control.
  * [2] Galit Ashkenazi-Golan, János Flesch, Arkadi Predtetchinski, and Eilon Solan.  Reachability and safety objectives in Markov decision processes on long but finite horizons.  Journal of Optimization Theory and Applications, 185:945–965, 2020\.
  * [3] Christel Baier and Joost-Pieter Katoen.  Principles of Model Checking.  MIT Press, 2008.
  * [4] P. Billingsley.  Probability and Measure.  Wiley, New York, NY, 1995.  Third Edition.
  * [5] Vincent D. Blondel and John N. Tsitsiklis.  A survey of computational complexity results in systems and control.  Automatica, 36(9):1249–1274, 2000.
  * [6] Nicole Bäuerle and Ulrich Rieder.  Markov Decision Processes with Applications to Finance.  Springer-Verlag Berlin Heidelberg, 2011.
  * [7] K. Chatterjee, L. Doyen, and T. Henzinger.  A survey of stochastic games with limsup and liminf objectives.  In Proc. of ICALP, volume 5556 of LNCS. Springer, 2009.
  * [8] Krishnendu Chatterjee and Laurent Doyen.  Games and Markov decision processes with mean-payoff parity and energy parity objectives.  In Proc. of MEMICS, volume 7119 of LNCS, pages 37–46. Springer, 2011.
  * [9] Edmund M. Clarke, Thomas A. Henzinger, Helmut Veith, and Roderick Bloem, editors.  Handbook of Model Checking.  Springer, 2018.  URL: https://doi.org/10.1007/978-3-319-10575-8, doi:10.1007/978-3-319-10575-8.
  * [10] E.M. Clarke, O. Grumberg, and D. Peled.  Model Checking.  MIT Press, Dec. 1999.
  * [11] János Flesch, Arkadi Predtetchinski, and William Sudderth.  Simplifying optimal strategies in limsup and liminf stochastic games.  Discrete Applied Mathematics, 251:40–56, 2018.
  * [12] T.P. Hill and V.C. Pestien.  The existence of good Markov strategies for decision processes with general payoffs.  Stoch. Processes and Appl., 24:61–76, 1987.
  * [13] S. Kiefer, R. Mayr, M. Shirmohammadi, and P. Totzke.  Transience in countable MDPs.  In Proc. of CONCUR, volume 203 of LIPIcs, 2021.  Full version at https://arxiv.org/abs/2012.13739.
  * [14] Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke.  Büchi objectives in countable MDPs.  In ICALP, volume 132 of LIPIcs, pages 119:1–119:14, 2019\.  Full version at https://arxiv.org/abs/1904.11573.  doi:10.4230/LIPIcs.ICALP.2019.119.
  * [15] Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Patrick Totzke.  Strategy Complexity of Parity Objectives in Countable MDPs.  In CONCUR, pages 7:1–:17, 2020.  doi:10.4230/LIPIcs.CONCUR.2020.7.
  * [16] Stefan Kiefer, Richard Mayr, Mahsa Shirmohammadi, and Dominik Wojtczak.  Parity Objectives in Countable MDPs.  In LICS. IEEE, 2017.  doi:10.1109/LICS.2017.8005100.
  * [17] Richard Mayr and Eric Munday.  Strategy Complexity of Mean Payoff, Total Payoff and Point Payoff Objectives in Countable MDPs.  In Proc. of CONCUR, volume 203 of LIPIcs, 2021.
  * [18] Martin L. Puterman.  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994.
  * [19] S. M. Ross.  Introduction to Stochastic Dynamic Programming.  Academic Press, New York, 1983.
  * [20] Manfred Schäl.  Markov decision processes in finance and dynamic options.  In Handbook of Markov Decision Processes, pages 461–487. Springer, 2002.
  * [21] Olivier Sigaud and Olivier Buffet.  Markov Decision Processes in Artificial Intelligence.  John Wiley & Sons, 2013.
  * [22] William D. Sudderth.  Optimal Markov strategies.  Decisions in Economics and Finance, 43:43–54, 2020.
  * [23] R.S. Sutton and A.G Barto.  Reinforcement Learning: An Introduction.  Adaptive Computation and Machine Learning. MIT Press, 2018.
  * [24] M.Y. Vardi.  Automatic verification of probabilistic concurrent finite-state programs.  In Proc. of FOCS’85, pages 327–338, 1985.

##  Appendix A Introduction to Strategy Complexity

A simple example.

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{k}$$-1$$-1$$-1$$-1$$-\dfrac{1}{2}$$-\dfrac{1}{3}$$-\dfrac{1}{4}$$-\dfrac{1}{k}$
Figure 4: Adapted from [18, Example 8.10.2]. While there is no optimal MD
(memoryless deterministic) strategy, the following strategy is optimal for lim
inf/lim sup mean payoff: Loop $\exp(\exp(k))$ many times in state $s_{k}$ for
all $k$. In this particular example, this can be implemented with either just
a step counter or just a reward counter, but in general both are needed; cf.
Table 1.

Memory and strategies.

We formalize the amount of _memory_ needed to implement strategies. Let ${\sf
M}$ be a countable set of memory modes, and let $\tau:{\sf M}\times
S\to\mathcal{D}({\sf M}\times S)$ be a function that meets the following two
conditions: for all modes ${\sf m}\in{\sf M}$,

  * •

for all controlled states $s\in S_{\Box}$, the distribution $\tau({\sf m},s)$
is over ${\sf M}\times\\{s^{\prime}\mid s{\longrightarrow}{}s^{\prime}\\}$.

  * •

for all random states $s\in S_{\ocircle}$, and $s^{\prime}\in S$, we have
$\sum_{{\sf m}^{\prime}\in{\sf M}}\tau({\sf m},s)({\sf
m}^{\prime},s^{\prime})=P(s)(s^{\prime})$.

The function $\tau$ together with an initial memory mode ${\sf m}_{0}$ induce
a strategy $\sigma_{\tau}$ as follows. Consider the Markov chain with the set
${\sf M}\times S$ of states and the probability function $\tau$. A sequence
$\rho=s_{0}\cdots s_{i}$ corresponds to a set $H(\rho)=\\{({\sf
m}_{0},s_{0})\cdots({\sf m}_{i},s_{i})\mid{\sf m}_{0},\ldots,{\sf
m}_{i}\in{\sf M}\\}$ of runs in this Markov chain. Each $\rho s\in
s_{0}S^{*}S_{\Box}$ induces a probability distribution $\mu_{\rho
s}\in\mathcal{D}({\sf M})$, the probability of being in state $({\sf m},s)$
conditioned on having taken some partial run from $H(\rho s)$. We define
$\sigma_{\tau}$ such that $\sigma_{\tau}(\rho s)(s^{\prime})=\sum_{{\sf
m},{\sf m}^{\prime}\in{\sf M}}\mu_{\rho s}({\sf m})\tau({\sf m},s)({\sf
m}^{\prime},s^{\prime})$ for all $\rho s\in S^{*}S_{\Box}$ and all
$s^{\prime}\in S$.

We say that a strategy $\sigma$ can be _implemented_ with memory ${\sf M}$ if
there exist ${\sf m}_{0}\in{\sf M}$ and $\tau$ such that
$\sigma_{\tau}=\sigma$.

##  Appendix B Missing proofs from Section 3

See 3.5

######  Proof B.1.

Recall that Tower$(i)$ is $i$ repeated exponentials. Thus,
log(Tower$(i)$)=Tower$(i-1)$.

When checking whether probabilities in a given gadget are well defined, first
we choose a gadget. The choice of gadget gives us a branching degree $k(n)+1$
which in turn lower bounds the value of $n$ in that gadget. So for a branching
degree of $k(n)+1$, we have $n$ lower bounded by Tower$(k(n)+1)$ by definition
of $k(n)$.

We need to show that $\sum_{i=0}^{k(n)-1}\delta_{i}(n)\leq 1$. Indeed, we have
that:

$\sum_{i=0}^{k(n)-1}\delta_{i}(n)\leq\sum_{i=0}^{k(n)-1}\dfrac{1}{\text{log}_{i+1}(\text{Tower}(k(n)+1))}\\\
=\sum_{i=1}^{k(n)}\dfrac{1}{\text{Tower}(i)}<\sum_{i=1}^{k(n)}\dfrac{1}{e^{i}}<\sum_{i=1}^{k(n)}\dfrac{1}{2^{i}}<1.$

Hence, for $k(n)\geq 1$, the transition probabilities are well defined, i.e.
$\delta_{0}(n),\delta_{1}(n),...,\delta_{k(n)}(n)$ do indeed sum to 1.

######  Proposition B.2.

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

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

######  Proof B.3.

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 B.4.

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 B.5.

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.

See 3.6

######  Proof B.6.

We define a strategy $\sigma$ which in $c_{n}$ always mimics the choice in
$s_{n}$. We first prove that playing this way gives us a positive chance of
winning. Then we show that there are strategies $\sigma_{\varepsilon}$ that
attain $1-\varepsilon$ from $s_{0}$ without hitting a $\perp$ state. This
implies in particular that ${\mathtt{val}_{{\mathcal{M}},{\it MP}_{\liminf\geq
0}}(s_{0})}=1$.

Playing according to $\sigma$, the only way to lose is by dropping into the
$\perp$ state. This is because by mimicking, the player finishes each gadget
with a reward of 0. In the $n$-th gadget, the chance of reaching the $\perp$
state is $\sum_{j=0}^{k(n)-1}\delta_{j}(n)\cdot\varepsilon_{j}(n)$. Thus, the
probability of surviving while playing in all the gadgets is

$\prod_{n\geq
N^{*}}\left(1-\sum_{j=0}^{k(n)-1}\delta_{j}(n)\cdot\varepsilon_{j}(n)\right).$

However, by Proposition B.2, this product is strictly greater than 0 if and
only if the sum

$\sum_{n\geq
N^{*}}\left(\sum_{i=0}^{k(n)-1}\delta_{i}(n)\varepsilon_{i}(n)\right)$

is finite. With some rearranging exploiting the definition of $k(n)$ we see
that this is indeed the case:

$\displaystyle\sum_{n\geq
N^{*}}\left(\sum_{i=0}^{k(n)-1}\delta_{i}(n)\varepsilon_{i}(n)\right)$
$\displaystyle\leq$ $\displaystyle\sum_{i\geq
1}\left(\sum_{n=g(i)}^{\infty}\delta_{i-1}(n)\varepsilon_{i-1}(n)\right)$ by
definition of $k(n)$ $\displaystyle\leq$ $\displaystyle\sum_{i\geq 1}2^{-i}$
by definition of $g(n)$ $\displaystyle\leq$ $\displaystyle 1$

Hence the player has a non zero chance of winning.

When playing with the ability to skip gadgets, as illustrated in Figure 2, all
runs not visiting a $\perp$ state are winning since the total reward never
dips below $0$. Hence
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma_{\varepsilon}}({\it
MP}_{\liminf\geq
0}\wedge\neg\perp)={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma_{\varepsilon}}(\neg\perp)$.
Thus the idea is to skip an arbitrarily long prefix of gadgets to push the
chance of winning $\varepsilon$ close to $1$ by pushing the chance of visiting
a $\perp$ state $\varepsilon$ close to $0$. From the $N$-th state, for $N\geq
N^{*}$, the chance of winning is

$\prod_{n\geq
N}\left(1-\sum_{j=0}^{k(n)-1}\delta_{j}(n)\cdot\varepsilon_{j}(n)\right)>0$

By Proposition B.4 this can be made arbitrarily close to $1$ by choosing $N$
sufficiently large.

Let
$N_{\varepsilon}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\text{min}\left\\{N\in\mathbb{N}\mid\prod_{n\geq
N}\left(1-\sum_{j=0}^{k(n)-1}\delta_{j}(n)\cdot\varepsilon_{j}(n)\right)\geq
1-\varepsilon\right\\}$. Now define the strategy $\sigma_{\varepsilon}$ to be
the strategy that plays like $\sigma$ after skipping forwards by
$N_{\varepsilon}$ gadgets. Thus, by definition $\sigma_{\varepsilon}$ attains
$1-\varepsilon$ for all $\varepsilon>0$.

Thus, by playing $\sigma_{\varepsilon}$ for an arbitrarily small $\varepsilon$
the chance of winning must be arbitrarily close to 1. Hence,
${\mathtt{val}_{{\mathcal{M}},{\it MP}_{\liminf\geq 0}}(s_{0})}=1$.

######  Lemma B.7.

For any sequence $\\{\alpha_{n}\\}$, where $\alpha_{n}\in[0,1]$ for all $n$,
and any functions $i(n),j(n):\mathbb{N}\to\mathbb{N}$ with
$i(n),j(n)\in\\{0,1,...,k(n)-1\\},i(n)<j(n)$ for all $n$, the following sum
diverges:

$\sum_{n=k^{-1}(2)}^{\infty}\Big{(}\delta_{j(n)}(n)(\alpha_{n}\varepsilon_{j(n)}(n)+(1-\alpha_{n})\varepsilon_{i(n)}(n))+\delta_{i(n)}(n)(\alpha_{n}+(1-\alpha_{n})\varepsilon_{i(n)}(n))\Big{)}.$
(8)

######  Proof B.8.

We can narrow our focus by noticing that

$\displaystyle\sum_{n=k^{-1}(2)}^{\infty}\Big{(}\delta_{j(n)}(n)(\alpha_{n}\varepsilon_{j(n)}(n)+(1-\alpha_{n})\varepsilon_{i(n)}(n))+\delta_{i(n)}(n)(\alpha_{n}+(1-\alpha_{n})\varepsilon_{i(n)}(n))\Big{)}$
$\displaystyle=\sum_{n=k^{-1}(2)}^{\infty}\alpha_{n}\delta_{j(n)}(n)\varepsilon_{j(n)}(n)+(1-\alpha_{n})\delta_{i(n)}\varepsilon_{i(n)}(n)\qquad\text{Convergent
by def. of $\delta_{i}(n),\varepsilon_{i}(n)$}$
$\displaystyle+\sum_{n=k^{-1}(2)}^{\infty}(1-\alpha_{n})\delta_{j(n)}\varepsilon_{i(n)}(n)+\alpha_{n}\delta_{i(n)}(n)$

Hence the divergence of (8) depends only on the divergence of
$\sum_{n=k^{-1}(2)}^{\infty}(1-\alpha_{n})\delta_{j(n)}\varepsilon_{i(n)}(n)+\alpha_{n}\delta_{i(n)}(n)$.
No matter how the sequence $\\{\alpha_{n}\\}$ behaves, for every $n$ we have
that either $\alpha_{n}\geq 1/2$ or $1-\alpha_{n}\geq 1/2$. Hence for every
$n$ it is the case that

$\displaystyle(1-\alpha_{n})\delta_{j(n)}(n)\varepsilon_{i(n)}(n)+\alpha_{n}\delta_{i(n)}(n)\,\geq\,$
$\displaystyle\dfrac{1}{2}\delta_{j(n)}(n)\varepsilon_{i(n)}(n)$ or
$\displaystyle\,\geq\,$ $\displaystyle\dfrac{1}{2}\delta_{i(n)}(n)$

Define the function $f$ as follows:

$f(n)=\left\\{\begin{array}[]{ll}\dfrac{1}{2}\delta_{i(n)}(n)\text{ if
$\alpha_{n}\geq 1/2$}\\\ \\\
\dfrac{1}{2}\delta_{j(n)}(n)\varepsilon_{i(n)}(n)\text{
otherwise}\end{array}\right.$

Hence no matter how $\\{\alpha_{n}\\}$ behaves, we have that

$\sum_{n=k^{-1}(2)}^{\infty}\Big{(}\delta_{j(n)}(n)(\alpha_{n}\varepsilon_{j(n)}(n)+(1-\alpha_{n})\varepsilon_{i(n)}(n))+\delta_{i(n)}(n)(\alpha_{n}+(1-\alpha_{n})\varepsilon_{i(n)}(n))\Big{)}\geq\sum_{n=k^{-1}(2)}^{\infty}f(n).$

We know that both
$\sum_{n=k^{-1}(2)}^{\infty}\dfrac{1}{2}\delta_{j(n)}(n)\varepsilon_{i(n)}(n)$
and $\sum_{n=k^{-1}(2)}^{\infty}\dfrac{1}{2}\delta_{i(n)}(n)$ diverge for all
$i(n),j(n)\in\\{0,1,...,k(n)-1\\}$, $i(n)<j(n)$, as shown in 3.

Thus
$\sum_{n=k^{-1}(2)}^{\infty}\dfrac{1}{2}\delta_{j(n)}(n)\varepsilon_{i(n)}(n)$
and $\sum_{n=k^{-1}(2)}^{\infty}\dfrac{1}{2}\delta_{i(n)}(n)$ must also
diverge no matter how $i(n)$ and $j(n)$ behave. As a result it must be the
case that $\sum_{n=k^{-1}(2)}^{\infty}f(n)$ diverges. Hence (8) must be
divergent as desired as $i(n)$ and $j(n)$ vary for $n\geq k^{-1}(2)$.

######  Claim 3.

The sum
$\sum_{n=k^{-1}(2)}^{\infty}\dfrac{1}{2}\delta_{j(n)}(n)\varepsilon_{i(n)}(n)$
diverges for all $i(n),j(n)\in\\{0,1,...,k(n)-1\\}$ with $i(n)<j(n)$.

######  Proof B.9.

This result is not immediate because the range of values the indexing
functions $i(n)$ and $j(n)$ can take grows with $k(n)$ as $n$ increases.

Under the assumption that $i(n)<j(n)$ we have that
$\delta_{j(n)}(n)\varepsilon_{i(n)}(n)\geq\delta_{j(n)}(n)\varepsilon_{j(n)-1}(n)\geq\delta_{k(n)-1}(n)\varepsilon_{k(n)-2}(n)=\varepsilon_{k(n)-1}(n)$.
Thus it suffices to show that
$\sum_{n=k^{-1}(2)}^{\infty}\varepsilon_{k(n)-1}(n)$ diverges:

$\displaystyle\sum_{n=k^{-1}(2)}^{\infty}\varepsilon_{k(n)-1}(n)$
$\displaystyle=\sum^{\infty}_{a=2}\quad\sum_{n=k^{-1}(a)}^{k^{-1}(a+1)-1}\varepsilon_{a-1}(n)$
splitting the sum up
$\displaystyle=\sum^{\infty}_{a=2}\quad\sum_{n=h(a)}^{h(a+1)-1}\varepsilon_{a-1}(n)$
$k(n)=h^{-1}(n)$ $\displaystyle\geq\sum^{\infty}_{a=2}1$ definition of $h(n)$

Note that the definition of $h(i)$ says exactly that a block of the form
$\sum_{n=h(a)}^{h(a+1)-1}\varepsilon_{a-1}(n)$ is at least $1$. Hence
$\sum_{n=k^{-1}(2)}^{\infty}\dfrac{1}{2}\delta_{j(n)}(n)\varepsilon_{i(n)}(n)$
diverges as required.

See 3.8

######  Proof B.10.

Let $\sigma$ be some FR strategy with $k$ memory modes. Our MDP consists of a
linear sequence of gadgets (Figure 1) and is in particular acyclic. The $n$-th
gadget is entered at state $s_{n}$ and takes 4 steps. Locally in the $n$-th
gadget there are 3 possible scenarios:

(1)

The random transition picks some branch $i$ at $s_{n}$ and the strategy then
picks a branch $j>i$ at $c_{n}$.

By the definition of the payoffs (multiples of $m_{n}$; cf. Definition 3.4),
this means that we see a mean payoff $\leq-1$, regardless of events in past
gadgets. This is because the numbers $m_{n}$ grow so quickly with $n$ that
even the combined maximal possible rewards of all past gadgets are so small in
comparison that they do not matter for the outcome in the $n$-th gadget, i.e.,
rewards from past gadgets cannot help to avoid seeing a mean payoff $\leq-1$
in the above scenario.

(2)

We reach the losing sink $\bot$ (and thus will keep seeing a mean payoff
$\leq-1$ forever). This happens with probability $\varepsilon_{j}(n)$ if the
strategy picks some branch $j$ at $c_{n}$, regardless of past events.

(3)

All other cases.

As explained above, due to the definition of the rewards (Definition 3.4),
events in past gadgets do not make the difference between (1),(2),(3) in the
current gadget. It just depends on the choices of the strategy $\sigma$ in the
current gadget.

Let ${\it Bad}_{n}$ be the event of seeing either of the two unfavorable
outcomes (1) or (2) in the $n$-th gadget. Let $p_{n}$ be the probability of
${\it Bad}_{n}$ under strategy $\sigma$. Since $\sigma$ has memory, the
probabilities $p_{n}$ are not necessarily independent. However, we show _lower
bounds_ $e_{n}\leq p_{n}$ that hold universally for every FR strategy $\sigma$
with $\leq k$ memory modes and every $n$ such that $k(n)>k+1$. The lower bound
$e_{n}$ will hold regardless of the memory mode of $\sigma$ upon entering the
$n$-th gadget.

Memory updates. First we show that $\sigma$ randomizing its memory update
after observing the random transition from state $s_{n}$ does _not_ help to
reduce the probability of event ${\it Bad}_{n}$. I.e., we show that without
restriction $\sigma$ can update its memory deterministically after observing
the transition from state $s_{n}$.

Once in the controlled state $c_{n}$, the strategy $\sigma$ can base its
choice only on the current state (always $c_{n}$ in the $n$-th gadget) and on
the current memory mode. Thus, in state $c_{n}$, in each memory mode ${\sf
m}$, the strategy has to pick a distribution $\mathcal{D}^{c_{n}}_{{\sf m}}$
over the available transitions from $c_{n}$. By the finiteness of the number
of memory modes of $\sigma$ (just $\leq k$ by our assumption above), for each
possible reward level $x$ (obtained in the step from the preceding random
transition) there is a best memory mode ${\sf m}(x)$ such that
$\mathcal{D}^{c_{n}}_{{\sf m}(x)}$ is optimal (in the sense of minimizing the
probability of event ${\it Bad}_{n}$) for that particular reward level $x$.
(In case of a tie, just use an arbitrary tie break, e.g., some pre-defined
linear order on the memory modes.)

Therefore, upon witnessing a reward level $x$ in the random transition from
state $s_{n}$, the strategy $\sigma$ can minimize the probability of event
${\it Bad}_{n}$ by _deterministically_ setting its memory to ${\sf m}(x)$.
Thus randomizing its memory update does not help to reduce the probability of
${\it Bad}_{n}$, and we may assume without restriction that $\sigma$ updates
its memory deterministically.

(Note that the above argument only works because it is local to the current
gadget where we have a finite number of decisions (here just one), we have a
finite number of memory modes, and a one-dimensional criterion for local
optimality (minimizing the probability of event ${\it Bad}_{n}$). We do _not_
claim that randomized memory updates are useless for every strategy in every
MDP and every objective.)

The lower bounds $e_{n}$. Now we consider an FR strategy $\sigma$ that without
restriction updates its memory _deterministically_ after each random choice
(from state $s_{n}$) in the $n$-th gadget. It can still randomize its actions,
however.

Let $N^{\prime}$ be the minimal number such that for all $n\geq N^{\prime}$ we
have $k(n)>k+1$. In particular, this implies $N^{\prime}\geq k^{-1}(2)$, and
thus we can apply Lemma B.7 later.

Once $n\geq N^{\prime}$, then by the Pigeonhole Principle there will always be
a memory mode confusing at least two different transitions $i(n),j(n)\neq
k(n)$ from state $s_{n}$ to $c_{n}$. Note that this holds regardless of the
memory mode of $\sigma$ upon entering the $n$-th gadget. (The strategy might
confuse many other scenarios, but just one confused pair $i(n),j(n)\neq k(n)$
is enough for our lower bound.) Without loss of generality, let $j(n)$ be
larger of the two confused transitions, i.e., $i(n)<j(n)$. Let $i(n)$ and
$j(n)$ be two functions taking values in $\\{0,1,...,k(n)-1\\}$ where
$i(n)<j(n)$ for all $n$.

Confusing two transitions $i(n)$ and $j(n)$ from $s_{n}$ to $c_{n}$ (where
without restriction $i(n)<j(n)$), the strategy is in the same memory mode
afterwards. However, it can still randomize its choices in state $c_{n}$. To
prove our lower bound on the probability of ${\it Bad}_{n}$, it suffices to
consider the case where the strategy only randomizes over the outgoing
transitions $i(n)$ and $j(n)$ from state $c_{n}$. This is because, by 4, every
other behavior would perform even worse, in the sense of yielding a higher
probability of ${\it Bad}_{n}$.

That is to say that the strategy picks the higher $j(n)$-th branch with some
probability $\alpha_{n}$ and the lower $i(n)$-th branch with probability
$1-\alpha_{n}$. (We leave the probabilities $\alpha_{n}$ unspecified here.
Using Lemma B.7, we’ll show that our result holds regardless of their values.)

The local chance of the event ${\it Bad}_{n}$ is then lower bounded by

$e_{n}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\delta_{j(n)}(n)(\alpha_{n}\varepsilon_{j(n)}(n)+(1-\alpha_{n})\varepsilon_{i(n)}(n))+\delta_{i(n)}(n)(\alpha_{n}+(1-\alpha_{n})\varepsilon_{i(n)}(n)).$

The term above just expresses a case distinction. In the first scenario, the
random transition chooses the $j(n)$-th branch (with probability
$\delta_{j(n)}(n)$) and then the strategy chooses the $j(n)$-th branch with
probability $\alpha_{n}$ and the lower $i(n)$-th branch with probability
$1-\alpha_{n}$, and you obtain the respective chances of reaching the sink
$\bot$. In the second scenario, the random transition chooses the $i(n)$-th
branch (with probability $\delta_{i(n)}(n)$). If the strategy then chooses the
higher $j(n)$-th branch (with probability $\alpha_{n}$) then we have outcome
(1), yielding a mean payoff $\leq-1$. If the strategy chooses the $i(n)$-th
branch (with probability $1-\alpha_{n}$) then we still have a chance of
$\varepsilon_{i(n)}(n)$ of reaching the sink.

Since, as shown above, randomized memory updates do not help to reduce the
probability of ${\it Bad}_{n}$, the lower bound $e_{n}$ for deterministic
updates carries over to the general case. Thus, even for general randomized FR
strategies $\sigma$ with $k$ memory modes, the probability of event ${\it
Bad}_{n}$ in the $n$-th gadget (for $n\geq N^{\prime}$) is lower bounded by
$e_{n}$, regardless of the memory mode ${\sf m}$ upon entering the gadget and
regardless of events in past gadgets. We write $\sigma[{\sf m}]$ for the
strategy $\sigma$ in memory mode ${\sf m}$ and obtain

$\forall n\geq N^{\prime}.\ \forall{\sf m}.\
{\mathcal{P}}_{\mathcal{M},\sigma[m],s_{n}}({\it Bad}_{n})\geq e_{n}$ (9)

The final step. Let ${\it
Bad}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\cup_{n}{\it Bad}_{n}$.

Since $i(n),j(n)\neq k(n)$ and $N^{\prime}\geq k^{-1}(2)$, we apply Lemma B.7
to conclude that the series
$\sum_{n=N^{\prime}}^{\infty}e_{n}=\sum_{n=N^{\prime}}^{\infty}\delta_{j(n)}(n)(\alpha_{n}\varepsilon_{j(n)}(n)+(1-\alpha_{n})\varepsilon_{i(n)}(n))+\delta_{i(n)}(n)(\alpha_{n}+(1-\alpha_{n})\varepsilon_{i(n)}(n))$
is divergent, regardless of the behavior of $i(n),j(n)$ or the sequence
$\\{\alpha_{n}\\}$.

Finally, we obtain

$\displaystyle{\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\it MP}_{\liminf\geq
0})$ $\displaystyle\leq{\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\sf F}{\sf
G}\neg{\it Bad})$ set inclusion
$\displaystyle={\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}\left(\bigcup_{l}{\sf
F}^{\leq l}{\sf G}\neg{\it Bad}\right)$ def. of ${\sf F}$
$\displaystyle=\lim_{l\to\infty}{\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}({\sf
F}^{\leq l}{\sf G}\neg{\it Bad})$ continuity of measures
$\displaystyle\leq\lim_{l\to\infty}{\mathcal{P}}_{\mathcal{M},\sigma,s_{0}}\left(\bigcap_{n\geq
l/4}\neg{\it Bad}_{n}\right)$ 4 steps per gadget
$\displaystyle\leq\lim_{4N^{\prime}\leq l\to\infty}\prod_{n\geq l/4\geq
N^{\prime}}(\max_{\sf m}\,{\mathcal{P}}_{\mathcal{M},\sigma[{\sf
m}],s_{n}}(\neg{\it Bad}_{n}))$ linear sequence of gadgets, finite memory,
---
and past events do not help to avoid ${\it Bad}_{n}$
$\displaystyle\leq\lim_{4N^{\prime}\leq l\to\infty}\prod_{n\geq l/4\geq
N^{\prime}}(1-e_{n})$ by (9) $\displaystyle=\lim_{4N^{\prime}\leq
l\to\infty}0$ divergence of $\sum_{n=N^{\prime}}^{\infty}e_{n}$ and
Proposition B.2 $\displaystyle=0$

$s_{n}$$c_{n}$$s_{n+1}$$\perp$$\delta_{j(n)}(n)$$+j(n)m_{n}$$\delta_{i(n)}(n)$$+i(n)m_{n}$$\alpha_{n}$$-j(n)m_{n}$$1-\alpha_{n}$$-i(n)m_{n}$$\varepsilon_{j(n)}(n)$$\varepsilon_{i(n)}(n)$
Figure 5: When transitions $i(n)$ and $j(n)$ are confused in the player’s
memory, the player’s choice is at least as bad as the reduced play in this
simplified gadget.

######  Claim 4.

Assume that the transitions $i(n)$ and $j(n)$ (with $i(n)<j(n)$) leading to
state $c_{n}$ are confused in the memory of the strategy. Then we can assume
without restriction that the strategy only plays transitions $i(n)$ and $j(n)$
with nonzero probability from state $c_{n}$, since every other behavior yields
a higher probability of the event ${\it Bad}_{n}$ (cf. Figure 5).

######  Proof B.11.

When confusing transitions $i(n)$ and $j(n)$ with $i(n)<j(n)$, the player’s
choice of transition from $c_{n}$ can be broken down into 5 distinct cases.
The player can choose transition $x(n)$ as follows.

1.

$x(n)=i(n)$

2.

$x(n)=j(n)$

3.

$x(n)>j(n)$

4.

$x(n)<i(n)$

5.

$i(n)<x(n)<j(n)$

Case 1 leads to a probability of ${\it Bad}_{n}$ of
$\delta_{j(n)}(n)\varepsilon_{i(n)}(n)+\delta_{i(n)}(n)\varepsilon_{i(n)}(n)$.

Case 2 leads to a probability of ${\it Bad}_{n}$ of
$\delta_{j(n)}(n)\varepsilon_{j(n)}(n)+\delta_{i(n)}(n)$.

Case 3 leads to a mean payoff $\leq-1$ (and thus ${\it Bad}_{n}$) with
probability $1$. This is the worst possible case.

Case 4 leads to a probability of ${\it Bad}_{n}$ of
$\delta_{j(n)}(n)\varepsilon_{x(n)}(n)+\delta_{i(n)}(n)\varepsilon_{x(n)}(n)>\delta_{j(n)}(n)\varepsilon_{i(n)}(n)+\delta_{i(n)}(n)\varepsilon_{i(n)}(n)$,
i.e., this is worse than Case 1.

Case 5 leads to a probability of ${\it Bad}_{n}$ of
$\delta_{j(n)}(n)\varepsilon_{x(n)}(n)+\delta_{i(n)}(n)>\delta_{j(n)}(n)\varepsilon_{j(n)}(n)+\delta_{i(n)}(n)$,
i.e., this is worse than Case 2.

Hence, without restriction we can assume that only cases 1 and 2 will get
played with positive probability, that is to say that in state $c_{n}$ the
strategy will only randomize over the outgoing transitions $i(n)$ and $j(n)$.

See 3.13

######  Proof B.12.

We will show that there exists a strategy $\sigma$ that satisfies the mean
payoff objective with probability 1 from $s_{0}$. Towards this objective we
recall the strategy $\sigma_{1/2}$ defined in Lemma 3.6. In a given gadget of
this MDP with restarts, playing $\sigma_{1/2}$ in said gadget, there is a
probability of at most 1/2 of restarting in that gadget. We then construct
strategy $\sigma$ by concatenating $\sigma_{1/2}$ strategies in the sense that
$\sigma$ plays just like $\sigma_{1/2}$ in each gadget from each gadget’s
start state.

Let ${\mathfrak{R}}$ be the set of runs induced by $\sigma$ from $s_{0}$. We
partition ${\mathfrak{R}}$ into the sets ${\mathfrak{R}}_{i}$ and
${\mathfrak{R}}_{\infty}$ of runs such that
${\mathfrak{R}}=\left(\bigcup_{i=0}^{\infty}{\mathfrak{R}}_{i}\right)\cup{\mathfrak{R}}_{\infty}$.
We define for $i=0$

${\mathfrak{R}}_{0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\forall\ell\in\mathbb{N}.\,\neg{\sf
F}(r_{\ell,1})\\},$

for $i\geq 1$

${\mathfrak{R}}_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\exists
j\in\mathbb{N}.\,{\sf F}(r_{j,i})\wedge\forall\ell\in\mathbb{N}.\,\neg{\sf
F}(r_{\ell,i+1})\\}$

and

${\mathfrak{R}}_{\infty}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\forall
i\in\mathbb{N}\ \exists j\in\mathbb{N}.\,{\sf F}(r_{j,i})\\}.$

That is to say for all $i\in\mathbb{N}$, ${\mathfrak{R}}_{i}$ is the set of
runs in ${\mathfrak{R}}$ that restart exactly $i$ times and
${\mathfrak{R}}_{\infty}$ is the set of runs in ${\mathfrak{R}}$ that restart
infinitely many times.

We go on to define the sets of runs ${\mathfrak{R}}_{\geq
i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcup_{j=i}^{\infty}{\mathfrak{R}}_{j}$
which are those runs which restart at least $i$ times. In particular note that
${\mathfrak{R}}_{\infty}=\bigcap_{i=0}^{\infty}{\mathfrak{R}}_{\geq i}$ and
${\mathfrak{R}}_{\geq i+1}\subseteq{\mathfrak{R}}_{\geq i}$.

By construction, any run $\rho\in{\mathfrak{R}}_{\infty}$ is losing since the
negative reward that is collected upon restarting instantly brings the mean
payoff below $-1$ by definition of $m_{n}$. Thus restarting infinitely many
times translates directly into the mean payoff dropping below $-1$ infinitely
many times and thus a strictly negative $\liminf$ mean payoff. As a result it
must be the case that ${\mathfrak{R}}_{\infty}\subseteq\neg{\it
MP}_{\liminf\geq 0}$.

After every restart, the negative reward is reimbursed. Intuitively, going
through finitely many restarts does not damage the chances of winning. We now
show that, except for a nullset, the runs restarting only finitely many times
satisfy the objective. Indeed, every run with only finitely many restarts must
spend an infinite tail in some final gadget in which it does not restart. In
this final gadget, the strategy plays just like $\sigma_{1/2}$, which means
that it mimics the random choice in every controlled state. Since, by
assumption, there are no more restarts, we obtain
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge\forall
j\in\mathbb{N},{\sf G}(\neg r_{j,i+1}))$. We then apply Lemma 3.6 to obtain
that

${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge\forall
j\in\mathbb{N},{\sf G}(\neg
r_{j,i+1}))={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge{\it
MP}_{\liminf\geq 0}).$ (10)

In other words, except for a nullset, the run restarting finitely often (here
$i$ times) satisfy ${\it MP}_{\liminf\geq 0}$. Furthermore, notice that from
this observation, the sets ${\mathfrak{R}}_{i}$ partition the set of winning
runs.

We show now that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})=0$. We do
so firstly by showing by induction that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\geq i})\leq
2^{-i}$ for $i\geq 1$, then applying the continuity of measures from above to
obtain that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})=0$.

Our base case is $i=1$. ${\mathfrak{R}}$, by definition of $\sigma$, is the
set of runs induced by playing $\sigma_{1/2}$ in every gadget. By Lemma 3.6
$\sigma$ attains $\geq 1/2$ in every gadget. Therefore in particular the
probability of a run leaving the first gadget is no more than $1/2$, i.e.
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\geq 1})\leq 1/2$.

Now suppose that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\geq i})\leq
2^{-i}$. After restarting at least $i$ times, the probability of a run
restarting at least once more is still $\leq 1/2$ since the strategy being
played in every gadget is $\sigma_{1/2}$. Hence

${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\geq
i+1})\leq{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\geq
i})\cdot\dfrac{1}{2}\leq 2^{-(i+1)}$

which is what we wanted.

Now we use the fact that
${\mathfrak{R}}_{\infty}=\bigcap_{i=0}^{\infty}{\mathfrak{R}}_{\geq i}$ and
${\mathfrak{R}}_{\geq i+1}\subseteq{\mathfrak{R}}_{\geq i}$ to apply
continuity of measures from above and obtain:

${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}\left(\bigcap_{i=0}^{\infty}{\mathfrak{R}}_{\geq
i}\right)=\lim_{i\to\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\geq
i})\leq\lim_{i\to\infty}2^{-i}=0.$

Hence ${\mathfrak{R}}_{\infty}$ is a null set.

We can now write down the following:

$\displaystyle 1$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}})$
$\displaystyle=\left(\sum_{i=0}^{\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})\right)+{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})$
$\displaystyle\text{by partition of }{\mathfrak{R}}$
$\displaystyle=\left(\sum_{i=0}^{\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge{\it
MP}_{\liminf\geq
0})\right)+{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})$
by Equation 10
$\displaystyle=\left(\sum_{i=0}^{\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge{\it
MP}_{\liminf\geq
0})\right)+{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty}\wedge{\it
MP}_{\liminf\geq 0})$ $\displaystyle\text{by
}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})=0$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})$ $\displaystyle\text{by partition of }{\it
MP}_{\liminf\geq 0}$

Thus
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})=1$, i.e. $\sigma$ wins almost surely.

See 3.15

######  Proof B.13.

There are two ways to lose when playing in this MDP: either the mean payoff
dips below $-1$ infinitely often because the run takes infinitely many
restarts, or the run only takes finitely many restarts, but the mean payoff
drops below $-1$ infinitely many times in the last copy of the gadget that the
run stays in. Recall that in Lemma 3.8 we showed that any FR strategy with
probability 1 either restarts or lets the mean payoff dip below $-1$
infinitely often.

Let $\sigma$ be any FR strategy and let ${\mathfrak{R}}$ to be the set of runs
induced by $\sigma$ from $s_{0}$. We partition ${\mathfrak{R}}$ into the sets
${\mathfrak{R}}_{i}$ and ${\mathfrak{R}}_{\infty}$ of runs such that
${\mathfrak{R}}=\left(\bigcup_{i=0}^{\infty}{\mathfrak{R}}_{i}\right)\cup{\mathfrak{R}}_{\infty}$.
Where we define for $i=0$

${\mathfrak{R}}_{0}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\forall\ell\in\mathbb{N},\neg{\sf
F}(r_{\ell,1})\\},$

for $i\geq 1$

${\mathfrak{R}}_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\exists
j\in\mathbb{N},{\sf F}(r_{j,i})\wedge\forall\ell\in\mathbb{N},\neg{\sf
F}(r_{\ell,i+1})\\}$

and

${\mathfrak{R}}_{\infty}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\forall
i,\exists j\text{ F}(r_{j,i})\\}.$

That is to say for all $i\in\mathbb{N}$, ${\mathfrak{R}}_{i}$ is the set of
runs in ${\mathfrak{R}}$ that restart exactly $i$ times and
${\mathfrak{R}}_{\infty}$ is the set of runs in ${\mathfrak{R}}$ that restart
infinitely many times.

We go on to define the sets of runs ${\mathfrak{R}}_{\geq
i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcup_{j=i}^{\infty}{\mathfrak{R}}_{j}$
which are those runs which restart at least $i$ times. In particular note that
${\mathfrak{R}}_{\infty}=\bigcap_{i=0}^{\infty}{\mathfrak{R}}_{\geq i}$ and
${\mathfrak{R}}_{\geq i+1}\subseteq{\mathfrak{R}}_{\geq i}$.

Note that any run in ${\mathfrak{R}}_{\infty}$ is losing by construction. The
negative reward that is collected upon restarting instantly brings the mean
payoff below $-1$ by definition of $m_{n}$. Thus restarting infinitely many
times translates directly into the mean payoff dropping below $-1$ infinitely
many times. Thus ${\mathfrak{R}}_{\infty}\subseteq\neg{\it MP}_{\liminf\geq
0}$ and so it follows that
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty}\wedge\neg{\it
MP}_{\liminf\geq 0})$. Since the sets ${\mathfrak{R}}_{i}$ and
${\mathfrak{R}}_{\infty}$ partition ${\mathfrak{R}}$ we have that:

${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}})=\left(\sum_{i=0}^{\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})\right)+{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty}).$

It remains to show that every set ${\mathfrak{R}}_{i}$ is almost surely
losing, i.e.
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge\neg{\it
MP}_{\liminf\geq 0}).$ Consider a run $\rho\in{\mathfrak{R}}_{i}$. By
definition it restarts exactly $i$ times. As a result, it spends infinitely
long in the $i+1$st gadget. Because $\sigma$ is an FR strategy, it must be the
case that any substrategy $\sigma^{*}$ induced by $\sigma$ that is played in a
given gadget is also an FR strategy. This allows us to apply Lemma 3.8 to
obtain that

${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}\left({\mathfrak{R}}_{i}\wedge(\neg{\it
MP}_{\liminf\geq 0}\vee\exists j\in\mathbb{N},{\sf F}(r_{j,i+1}))\right).$
(11)

However, any run $\rho\in{\mathfrak{R}}_{i}$ never sees any state $r_{j,i+1}$
for any $j$ by definition. Therefore it follows that

${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}\left({\mathfrak{R}}_{i}\wedge(\neg{\it
MP}_{\liminf\geq 0}\vee\exists j\in\mathbb{N},{\sf
F}(r_{j,i+1}))\right)={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}\left({\mathfrak{R}}_{i}\wedge(\neg{\it
MP}_{\liminf\geq 0})\right)$

Hence
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge\neg{\it
MP}_{\liminf\geq 0})$ as required.

As a result we have that

$\displaystyle 1$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}})$
$\displaystyle=\left(\sum_{i=0}^{\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i})\right)+{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty})$
$\displaystyle\text{by partition of }{\mathfrak{R}}$
$\displaystyle=\left(\sum_{i=0}^{\infty}{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{i}\wedge\neg{\it
MP}_{\liminf\geq
0})\right)+{\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\mathfrak{R}}_{\infty}\wedge\neg{\it
MP}_{\liminf\geq 0})$ by Equation 11
$\displaystyle={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}(\neg{\it
MP}_{\liminf\geq 0})$ $\displaystyle\text{by partition of }{\mathfrak{R}}$

That is to say that for any FR strategy $\sigma$,
${\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it MP}_{\liminf\geq 0})=0$.

##  Appendix C Missing proofs from Section 4

In this part we show that a reward counter plus arbitrary finite memory does
not suffice for ($\varepsilon$-)optimal strategies for ${\it MP}_{\liminf\geq
0}$ or for infinitely branching ${\it TP}_{\liminf\geq 0}$/${\it
PP}_{\liminf\geq 0}$ in countable MDPs.

First we consider ${\it MP}_{\liminf\geq 0}$ by presenting an MDP adapted from
Figure 1 that has the current total reward implicit in the state and show that
neither $\varepsilon$-optimal nor almost-sure ${\it MP}_{\liminf\geq 0}$ can
be achieved by FR strategies (finite memory randomized).

$s_{n}$$s_{n+1}$$c_{n}$$\perp$$\delta_{k(n)}(n)$$\delta_{i}(n)$$\delta_{1}(n)$$\delta_{0}(n)$$nm_{n}^{k(n)}$
steps$nm_{n}^{i}$ steps$nm_{n}$ steps$n$
steps$-m_{n}^{k(n)}$$-m_{n}^{i}$$-m_{n}$$-1$$+m_{n}^{k(n)}$$+m_{n}^{i}$$+m_{n}$$+1$$\varepsilon_{i}(n)$$\varepsilon_{1}(n)$$\varepsilon_{0}(n)$
Figure 6: All transition rewards are $0$ unless specified. Recall that
$\sum\delta_{i}(n)\cdot\varepsilon_{i}(n)$ is convergent and
$\sum\delta_{j}(n)\cdot\varepsilon_{i}(n)$ is divergent for all $i,j$ with
$j>i$. The negative reward incurred before falling into the $\perp$ state is
reimbursed. We do not show it in the figure for readability. In the state
before $s_{n+1}$, if the correct transition was chosen, the mean payoff is
$-1/n$. If the incorrect transition was chosen, then either the mean payoff is
$<-m_{n}/n$, or the risk of falling into $\perp$ is too high.

We use the example from Figure 6. It is very similar to Figure 1, but differs
in the following ways.

  * •

The current total reward level is implicit in each state.

  * •

The step counter is no longer implicit in the state.

  * •

In the random choice, instead of changing the reward levels in each choice, it
is the path length that differs.

  * •

The definition of $m_{n}$ is different, it is now
$m_{n}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\sum_{i=N^{*}}^{n-1}m_{i}^{k(n)}$
with $m_{N^{*}}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1$.

We construct a finitely branching acyclic MDP ${\mathcal{M}}_{\text{RI}}$
(Reward Implicit) which has the total reward implicit in the state. We do so
by chaining together the gadgets from Figure 6 as is shown in Figure 2.

See 4.1

######  Proof C.1.

This follows from Lemma C.2 and Lemma C.4.

######  Lemma C.2.

${\mathtt{val}_{{\mathcal{M}}_{\text{\emph{RI}}},{\it MP}_{\liminf\geq
0}}((s_{0},0))}=1$.

######  Proof C.3.

We define a strategy $\sigma$ which, in $c_{n}$ always mimics the random
choice in $s_{n}$. Playing according to $\sigma$, the only way to lose is by
dropping into the bottom state. This is because by mimicking, the mean payoff
in each gadget is lower bounded by $-1/n$. The rest of the proof is identical
to Lemma 3.6.

######  Lemma C.4.

Any FR strategy $\sigma$ in ${\mathcal{M}}_{\text{\emph{RI}}}$ is such that
${\mathcal{P}}_{{\mathcal{M}}_{\text{\emph{RI}}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})=0$.

######  Proof C.5.

When playing with finitely many memory modes, there are two ways for a run in
${\mathcal{M}}_{\text{RI}}$ to lose. Either it falls into a losing sink, or it
never falls into a sink but its mean payoff is $<-1$. The proof that either of
these occurs with probability $1$ is the same as in Lemma 3.8.

Now we construct the MDP ${\mathcal{M}}_{\text{Restart}}$ by chaining together
the gadgets from Figure 6 in the way shown in Figure 3.

See 4.2

######  Proof C.6.

This follows from Lemma C.7 and Lemma C.9.

######  Lemma C.7.

There exists an HD strategy $\sigma$ such that
${\mathcal{P}}_{{\mathcal{M}}_{\text{\emph{Restart}}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})=1$.

######  Proof C.8.

The proof is identical to that of Lemma 3.13.

######  Lemma C.9.

For any FR strategy $\sigma$,
${\mathcal{P}}_{{\mathcal{M}}_{\text{\emph{Restart}}},s_{0},\sigma}({\it
MP}_{\liminf\geq 0})=0$.

######  Proof C.10.

The proof is identical to that of Lemma 3.15.

$s$$r_{1}$$\cdots$$r_{i}$$\cdots$$t$$\cdots$$\cdots$$\frac{1}{2}$$-1$$\frac{1}{2^{i}}$$-1$$\frac{1}{2}$$1-\frac{1}{2^{i}}$$+1$

Figure 7:  We present an infinitely branching MDP adapted from [16, Figure 3]
and augmented with a reward structure. All of the edges carry reward $0$
except the edges entering $t$ that carry reward $-1$ and the edge from $t$ to
$s$ carries reward $+1$. As a result, entering $t$ necessarily brings the
total reward down to $-1$ before resetting it to $0$. We use a reduction to
co-Büchi to show that infinite memory is required for almost-sure as well as
$\varepsilon$-optimal strategies for ${\it TP}_{\liminf\geq 0}$ as well as
${\it PP}_{\liminf\geq 0}$.

See 4.3

######  Proof C.11.

This follows directly from [16, Theorem 4] and the observation that in Figure
7, ${\it TP}_{\liminf\geq 0}$, ${\it PP}_{\liminf\geq 0}$ and co-Büchi
objectives coincide.

Consequently, when the MDP ${\mathcal{M}}$ is infinitely branching and has the
reward counter implicit in the state, both ${\it TP}_{\liminf\geq 0}$ and
${\it PP}_{\liminf\geq 0}$ require at least a step counter.

##  Appendix D Missing proofs from Section 5

######  Definition D.1.

Let ${\mathcal{M}}$ be an MDP. From a given initial state $s_{0}$, the reward
level in each state $s\in S$ can be any of the countably many values
$r_{1},r_{2},\dots$ corresponding to the rewards accumulated along all the
possible paths leading to $s$ from $s_{0}$. We then construct the MDP
$R({\mathcal{M}})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}(S^{\prime},S_{\Box}^{\prime},S_{\ocircle}^{\prime},\longrightarrow_{R({\mathcal{M}})},P^{\prime})$
as follows:

  * •

The state space of $R({\mathcal{M}})$ is
$S^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{(s,r)\mid s\in
S\text{ and }r\in\mathbb{R}\text{ is a reward level attainable at }s\\}$. Note
that $S^{\prime}$ is countable. We write $s_{0}^{\prime}$ for the initial
state $(s_{0},0)$.

  * •

$S_{\Box}^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{(s,r)\in
S^{\prime}\mid s\in S_{\Box}\\}$ and
$S_{\ocircle}^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}S^{\prime}\setminus
S_{\Box}^{\prime}$.

  * •

The set of transitions in $R({\mathcal{M}})$ is

$\displaystyle\longrightarrow_{R({\mathcal{M}})}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{$
$\displaystyle\left((s,r),(s^{\prime},r^{\prime})\right)\mid(s,r),(s^{\prime},r^{\prime})\in
S^{\prime},$ $\displaystyle s\longrightarrow s^{\prime}\text{ in
}{\mathcal{M}}\text{ and
}r^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}r+r(s\to
s^{\prime})\\}.$

  * •

$P^{\prime}:S_{\ocircle}^{\prime}\to\mathcal{D}(S^{\prime})$ is defined such
that

$P^{\prime}(s,r)(s^{\prime},r^{\prime})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\begin{cases}P(s)(s^{\prime})&\text{
if }(s,r)\longrightarrow_{R({\mathcal{M}})}(s^{\prime},r^{\prime})\\\ 0&\text{
otherwise }\end{cases}$

  * •

The reward for taking transition $(s,r)\longrightarrow(s^{\prime},r^{\prime})$
is $r^{\prime}$.

See 5.2

######  Proof D.2.

Let $\sigma^{\prime}$ be an MD (resp. Markov) strategy in $R({\mathcal{M}})$
attaining $c\in[0,1]$ for ${\it PP}_{\liminf\geq 0}$ from $(s_{0},0)$. We
define a strategy $\sigma$ on ${\mathcal{M}}$ from $s_{0}$ that uses the same
memory as $\sigma^{\prime}$ plus a reward counter. Then $\sigma$ plays on
${\mathcal{M}}$ exactly like $\sigma^{\prime}$ plays on $R({\mathcal{M}})$,
keeping the reward counter in its memory instead of in the state. I.e., at a
given state $s$ (and step counter value $m$, in case $\sigma^{\prime}$ was a
Markov strategy) and reward level $r$, $\sigma$ plays exactly as
$\sigma^{\prime}$ plays in state $(s,r)$ (and step counter value $m$, in case
$\sigma^{\prime}$ was a Markov strategy). By our construction of
$R({\mathcal{M}})$ and the definition of $\sigma$, the sequences of point
rewards seen by $\sigma^{\prime}$ in runs on $R({\mathcal{M}})$ coincide with
the sequences of total rewards seen by $\sigma$ in runs in ${\mathcal{M}}$.
Hence we obtain
${\mathcal{P}}_{R({\mathcal{M}}),(s_{0},0),\sigma^{\prime}}({\it
PP}_{\liminf\geq 0})={\mathcal{P}}_{{\mathcal{M}},s_{0},\sigma}({\it
TP}_{\liminf\geq 0})$ as required.

######  Definition D.3.

Given an MDP ${\mathcal{M}}$ with initial state $s_{0}$, we define the new MDP
$A({\mathcal{M}})$. From the initial state $s_{0}$, the reward level in each
state $s\in S$ can be any of the countably many values $r_{1},r_{2},\dots$
corresponding to the rewards accumulated along all the possible paths leading
to $s$ from $s_{0}$.

We then construct
$A({\mathcal{M}})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}(S^{\prime},S_{\Box}^{\prime},S_{\ocircle}^{\prime},\longrightarrow_{A({\mathcal{M}})},P^{\prime})$
as follows:

  * •

The state space of $A({\mathcal{M}})$ is

$S^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{(s,n,r)\mid
s\in S,n\in\mathbb{N}\text{ and }r\in\\!\mathbb{R}\,\text{ is a reward level
attainable at $s$ at step $n$}\\}$

Note that $S^{\prime}$ is countable. We write $s_{0}^{\prime}$ for the initial
state $(s_{0},0,0)$ of $A({\mathcal{M}})$.

  * •

$S_{\Box}^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{(s,n,r)\in
S^{\prime}\mid s\in S_{\Box}\\}$ and
$S_{\ocircle}^{\prime}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}S^{\prime}\setminus
S_{\Box}^{\prime}$.

  * •

The set of transitions in $A({\mathcal{M}})$ is

$\displaystyle\longrightarrow_{A({\mathcal{M}})}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{$
$\displaystyle\left((s,n,r),(s^{\prime},n+1,r^{\prime})\right)\mid$
$\displaystyle(s,n,r),(s^{\prime},n+1,r^{\prime})\in S^{\prime},$
$\displaystyle s\longrightarrow s^{\prime}\text{ in }{\mathcal{M}}\text{ and
}r^{\prime}=r+r(s\rightarrow s^{\prime})\\}.$

  * •

$P^{\prime}:S_{\ocircle}^{\prime}\to\mathcal{D}(S^{\prime})$ is defined such
that

$P^{\prime}(s,n,r)(s^{\prime},n^{\prime},r^{\prime})\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\begin{cases}P(s)(s^{\prime})&\text{if
}(s,n,r)\\!\rightarrow_{A({\mathcal{M}})}\\!(s^{\prime},n^{\prime},r^{\prime})\\\
0&\\!\\!\text{otherwise}\end{cases}$

  * •

The reward for taking transition
$(s,n,r)\longrightarrow(s^{\prime},n^{\prime},r^{\prime})$ is
$r^{\prime}/n^{\prime}$.

###  D.1 Proofs from Section 5.1

In this section we consider finitely branching MDPs. We need the following
technical lemma that holds only for finitely branching MDPs.

######  Lemma D.4.

Given a finitely branching countable MDP ${\mathcal{M}}$, a subset
$T\subseteq\to$ of the transitions and a state $s$, we have

${\mathtt{val}_{{\mathcal{M}},\neg{\sf F}T}(s)}<1\ \Rightarrow\ \exists
k\in\mathbb{N}.\,{\mathtt{val}_{{\mathcal{M}},\neg{\sf F}^{\leq k}T}(s)}<1$

i.e., if it is impossible to completely avoid $T$ then there is a bounded
threshold $k$ and a fixed nonzero chance of seeing $T$ within $\leq k$ steps,
regardless of the strategy.

######  Proof D.5.

If suffices to show that $\forall
k\in\mathbb{N}.\,{\mathtt{val}_{{\mathcal{M}},\neg{\sf F}^{\leq k}T}(s)}=1$
implies ${\mathtt{val}_{{\mathcal{M}},\neg{\sf F}T}(s)}=1$. Since
${\mathcal{M}}$ is finitely branching, the state $s$ has only finitely many
successors $\\{s_{1},\dots,s_{n}\\}$.

Consider the case where $s$ is a controlled state. If we had the property
$\forall{1\leq i\leq n}\,\exists
k_{i}\in\mathbb{N}.\,{\mathtt{val}_{{\mathcal{M}},\neg{\sf F}^{\leq
k_{i}}T}(s_{i})}<1$ then we would have ${\mathtt{val}_{{\mathcal{M}},\neg{\sf
F}^{\leq k}T}(s)}<1$ for $k=(\max_{1\leq i\leq n}k_{i})+1$ which contradicts
our assumption. Thus there must exist an $i\in\\{1,\dots,n\\}$ with $\forall
k\in\mathbb{N}.\,{\mathtt{val}_{{\mathcal{M}},\neg{\sf F}^{\leq
k}T}(s_{i})}=1$. We define a strategy $\sigma$ that chooses the successor
state $s_{i}$ when in state $s$.

Similarly, if $s$ is a random state, we must have $\forall
k\in\mathbb{N}.\,{\mathtt{val}_{{\mathcal{M}},\neg{\sf F}^{\leq
k}T}(s_{i})}=1$ for all its successors $s_{i}$.

By using our constructed strategy $\sigma$, we obtain
${\mathcal{P}}_{{\mathcal{M}},s,\sigma}(\neg{\sf F}T)=1$ and thus
${\mathtt{val}_{{\mathcal{M}},\neg{\sf F}T}(s)}=1$ as required.

See 1

######  Proof D.6.

$\displaystyle\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)$
$\displaystyle\geq\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\cap\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)$
$\displaystyle=\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\left(\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\cap\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)\cup\left(\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)\right)$
$\displaystyle=\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\cap\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\cup\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\right)\right)$
$\displaystyle=1-\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\cup\left(\overline{\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)\right)$ $\displaystyle\geq
1-\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\right)-\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\overline{\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$
$\displaystyle=\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left({\it
PP}_{\liminf\geq
0}\right)-\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\overline{\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$ by (3)
$\displaystyle\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-\varepsilon-\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\bigcup_{i\in\mathbb{N}}\overline{\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$ by (2)
$\displaystyle\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-\varepsilon-\sum_{i\in\mathbb{N}}\mathcal{P}_{{\mathcal{M}}^{\prime},s_{0},\sigma}\left(\overline{\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$
$\displaystyle\geq{\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-\varepsilon-\sum_{i\in\mathbb{N}}\varepsilon_{i}$ by (5)
$\displaystyle={\mathtt{val}_{{\mathcal{M}}^{\prime},{\it PP}_{\liminf\geq
0}}(s_{0})}-2\varepsilon$

See 2

######  Proof D.7.

First we show that

$\mathtt{Transience}\subseteq{\it PP}_{\liminf\geq 0}\quad\text{in
${\mathcal{M}}^{\prime\prime}$}.$ (12)

Let $\rho\in\mathtt{Transience}$ be a transient run. Then $\rho$ can never
visit the state $\perp$. Moreover, $\rho$ must eventually leave every finite
set forever. In particular $\rho$ must satisfy ${\sf F}{\sf
G}(\neg\text{Bubble}_{n_{i}}(s_{0}))$ for every $i$, since
$\text{Bubble}_{n_{i}}(s_{0})$ is finite, because
${\mathcal{M}}^{\prime\prime}$ is finitely branching. Thus $\rho$ must either
fall into $G_{\text{safe}}$, in which case it satisfies ${\it PP}_{\liminf\geq
0}$, or for every $i$, $\rho$ must eventually leave
$\text{Bubble}_{n_{i}}(s_{0})$ forever. By definition of
$\text{Bubble}_{n_{i}}(s_{0})$ and ${\mathcal{M}}^{\prime\prime}$, the run
$\rho$ must eventually stop seeing rewards $<-2^{-i}$ for every $i$. In this
case $\rho$ also satisfies ${\it PP}_{\liminf\geq 0}$. Thus (12).

Secondly, we show that

$\forall\sigma^{\prime\prime}.\
{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0}\cap\overline{\mathtt{Transience}})=0.$ (13)

i.e., except for a null-set, ${\it PP}_{\liminf\geq 0}$ implies
$\mathtt{Transience}$ in ${\mathcal{M}}^{\prime\prime}$.

Let $\sigma^{\prime\prime}$ be an arbitrary strategy from $s_{0}$ in
${\mathcal{M}}^{\prime\prime}$ and ${\mathfrak{R}}$ be the set of all runs
induced by it. For every $s\in S$, let
${\mathfrak{R}}_{s}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\rho\text{
satisfies }{\sf G}{\sf F}(s)\\}$ be the set of runs seeing state $s$
infinitely often. In particular, any run $\rho\in{\mathfrak{R}}_{s}$ is not
transient. Indeed, $\overline{\mathtt{Transience}}=\bigcup_{s\in
S}{\mathfrak{R}}_{s}$. We want to show that for every state $s\in S$ and
strategy $\sigma^{\prime\prime}$

${\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0}\cap{\mathfrak{R}}_{s})=0.$ (14)

Since any runs seeing a state in $G_{\text{safe}}$ are transient, any
${\mathfrak{R}}_{s}$ with $s\in G_{\text{safe}}$ must be empty. Similarly, any
run seeing $\perp$ is losing for ${\it PP}_{\liminf\geq 0}$ by construction.
Hence we have (14) for any state $s$ where $s=\perp$ or $s\in
G_{\text{safe}}$.

Now consider ${\mathfrak{R}}_{s}$ where $s$ is neither in $G_{\text{safe}}$
nor $\perp$. Let $T_{\it
neg}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{t\in\longrightarrow\
\mid\ r(t)<0\\}$ be the subset of transitions with negative rewards in
${\mathcal{M}}^{\prime\prime}$.

We now show that ${\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\neg{\sf
F}T_{\it neg}}(s)}<1$ by assuming the opposite and deriving a contradiction.
Assume that ${\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\neg{\sf F}T_{\it
neg}}(s)}=1$. The objective $\neg{\sf F}T_{\it neg}$ is a safety objective.
Thus, since ${\mathcal{M}}^{\prime\prime}$ is finitely branching, there exists
a strategy from $s$ that surely avoids $T_{\it neg}$ (always pick an optimal
move) [18, 16]. (This does not hold in infinitely branching MDPs where optimal
moves might not exist.) However, by construction of
${\mathcal{M}}^{\prime\prime}$, this implies that $s\in G_{\text{safe}}$.
Contradiction. Thus ${\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\neg{\sf
F}T_{\it neg}}(s)}<1$.

Since ${\mathcal{M}}^{\prime\prime}$ is finitely branching, we can apply Lemma
D.4 and obtain that there exists a threshold $k_{s}$ such that
${\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\neg{\sf F}^{\leq k_{s}}T_{\it
neg}}(s)}<1$. Therefore
$\delta_{s}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}1-{\mathtt{val}_{{\mathcal{M}}^{\prime\prime},\neg{\sf
F}^{\leq k_{s}}T_{\it neg}}(s)}>0$. Thus, under every strategy, upon visiting
$s$ there is a chance $\geq\delta_{s}$ of seeing a transition in $T_{\it neg}$
within the next $\leq k_{s}$ steps. Moreover, the subset $T^{s}_{\it
neg}\subseteq T_{\it neg}$ of transitions that can be reached in $\leq k_{s}$
steps from $s$ is finite, since ${\mathcal{M}}^{\prime\prime}$ is finitely
branching. So the maximum of the rewards in $T^{s}_{\it neg}$ is still
negative, i.e.,
$\ell_{s}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\max\\{r(t)\ \mid\
t\in T^{s}_{\it neg}\\}<0$. Let
$T_{\leq\ell}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{t\in\longrightarrow\
\mid\ r(t)\leq\ell_{s}\\}$ be the subset of transitions with rewards
$\leq\ell_{s}$ in ${\mathcal{M}}^{\prime\prime}$.

Thus, under _every_ strategy, upon visiting $s$ there is a chance
$\geq\delta_{s}$ of seeing a transition in $T_{\leq\ell}$ within the next
$\leq k_{s}$ steps.

Define
${\mathfrak{R}}_{s}^{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\\{\rho\in{\mathfrak{R}}\mid\rho\text{
sees $s$ at least $i$ times}\\}$, so we get
${\mathfrak{R}}_{s}=\bigcap_{i\in\mathbb{N}}{\mathfrak{R}}_{s}^{i}$. We obtain

$\displaystyle\sup_{\sigma^{\prime\prime}}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0}\cap{\mathfrak{R}}_{s})$
$\displaystyle\leq\sup_{\sigma^{\prime\prime}}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\sf
F}{\sf G}\neg T_{\leq\ell}\cap{\mathfrak{R}}_{s})$ set inclusion
$\displaystyle=\sup_{\sigma^{\prime\prime}}\lim_{n\to\infty}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\sf
F}^{\leq n}{\sf G}\neg T_{\leq\ell}\cap{\mathfrak{R}}_{s})$ continuity of
measures
$\displaystyle\leq\sup_{\sigma^{\prime\prime\prime}}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s,\sigma^{\prime\prime\prime}}({\sf
G}\neg T_{\leq\ell}\cap{\mathfrak{R}}_{s})$ $s$ visited after $>n$ steps
$\displaystyle=\sup_{\sigma^{\prime\prime\prime}}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s,\sigma^{\prime\prime\prime}}({\sf
G}\neg T_{\leq\ell}\cap\bigcap_{i\in\mathbb{N}}{\mathfrak{R}}_{s}^{i})$ def.
of ${\mathfrak{R}}_{s}^{i}$
$\displaystyle=\sup_{\sigma^{\prime\prime\prime}}\lim_{i\to\infty}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s,\sigma^{\prime\prime\prime}}({\sf
G}\neg T_{\leq\ell}\cap{\mathfrak{R}}_{s}^{i})$ continuity of measures
$\displaystyle\leq\lim_{i\to\infty}(1-\delta_{s})^{i}=0$ by def. of
${\mathfrak{R}}_{s}^{i}$ and $\delta_{s}$

and thus (14).

From this we obtain
${\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq
0}\cap\overline{\mathtt{Transience}})={\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0}\cap\bigcup_{s\in S}{\mathfrak{R}}_{s})\leq\sum_{s\in
S}{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0}\cap{\mathfrak{R}}_{s})=0$ and thus (13).

From (12) and (13) we obtain that for every $\sigma^{\prime\prime}$ we have

$\displaystyle{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0})$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq
0}\cap\mathtt{Transience})+{\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}({\it
PP}_{\liminf\geq 0}\cap\overline{\mathtt{Transience}})$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}(\mathtt{Transience})+0$
$\displaystyle={\mathcal{P}}_{{\mathcal{M}}^{\prime\prime},s_{0},\sigma^{\prime\prime}}(\mathtt{Transience})$

and thus 2.

###  D.2 Proofs from Section 5.2

In this section we consider infinitely branching MDPs. In the following
theorem we show how to obtain $\varepsilon$-optimal deterministic Markov
strategies for ${\it PP}_{\liminf\geq 0}$. We do this by deriving
$\varepsilon$-optimal MD strategies in $S({\mathcal{M}})$ via a reduction to a
safety objective.

See 5.16

######  Proof D.8.

Let $\varepsilon>0$. We work in $S({\mathcal{M}})$ by encoding the step
counter into the states of ${\mathcal{M}}$. Thus $S({\mathcal{M}})$ is an
acyclic MDP with implicit step counter and corresponding initial state
$s_{0}^{\prime}=(s_{0},0)$.

We consider a general (not necessarily MD) $\varepsilon$-optimal strategy
$\sigma$ for ${\it PP}_{\liminf\geq 0}$ from $s_{0}^{\prime}$ on
$S({\mathcal{M}})$, i.e.,

${\mathcal{P}}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}({\it PP}_{\liminf\geq
0})\geq{\mathtt{val}_{S({\mathcal{M}}),{\it PP}_{\liminf\geq
0}}(s_{0}^{\prime})}-\varepsilon.$ (15)

Define the safety objective $\text{Safety}_{i}$ which is the objective of
never seeing any point reward $<-2^{-i}$. This then allows us to characterize
${\it PP}_{\liminf\geq 0}$ in terms of safety objectives.

${\it PP}_{\liminf\geq 0}=\bigcap_{i\in\mathbb{N}}{\sf F}(\text{Safety}_{i})$
(16)

Now we define the safety objective
$\text{Safety}_{i}^{k}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}{\sf
F}^{\leq k}(\text{Safety}_{i})$ to attain $\text{Safety}_{i}$ within at most
$k$ steps. This allows us to write

${\sf F}(\text{Safety}_{i})=\bigcup_{k\in\mathbb{N}}\text{Safety}_{i}^{k}.$
(17)

By continuity of measures from above we get

$\displaystyle 0$
$\displaystyle=\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left({\sf
F}(\text{Safety}_{i})\cap\bigcap_{k\in\mathbb{N}}\overline{\text{Safety}^{k}_{i}}\right)$
$\displaystyle=\lim_{k\to\infty}\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left({\sf
F}(\text{Safety}_{i})\cap\overline{\text{Safety}^{k}_{i}}\right).$

Hence for every $i\in\mathbb{N}$ and
$\varepsilon_{i}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\varepsilon\cdot
2^{-i}$ there exists $n_{i}$ such that

$\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left({\sf
F}(\text{Safety}_{i})\cap\overline{\text{Safety}^{n_{i}}_{i}}\right)\leq\varepsilon_{i}.$
(18)

Now we can show the following claim.

######  Claim 5.

${\mathcal{P}}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)\geq{\mathtt{val}_{S({\mathcal{M}}),{\it
PP}_{\liminf\geq 0}}(s_{0}^{\prime})}-2\varepsilon.$

######  Proof D.9.

$\displaystyle\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)$
$\displaystyle\geq\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\cap\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)$
$\displaystyle=\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\left(\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\cap\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\right)\cup\left(\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)\right)$
$\displaystyle=\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\cap\left(\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\cup\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\right)\right)$
$\displaystyle=1-\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\cup\left(\overline{\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)\right)$ $\displaystyle\geq
1-\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\overline{\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})}\right)-\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\overline{\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$
$\displaystyle=\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left({\it
PP}_{\liminf\geq
0}\right)-\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\overline{\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$ by (16)
$\displaystyle\geq{\mathtt{val}_{S({\mathcal{M}}),{\it PP}_{\liminf\geq
0}}(s_{0}^{\prime})}-\varepsilon-\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\bigcup_{i\in\mathbb{N}}\overline{\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$ by (15)
$\displaystyle\geq{\mathtt{val}_{S({\mathcal{M}}),{\it PP}_{\liminf\geq
0}}(s_{0}^{\prime})}-\varepsilon-\sum_{i\in\mathbb{N}}\mathcal{P}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma}\left(\overline{\text{Safety}^{n_{i}}_{i}}\cap\bigcap_{k\in\mathbb{N}}{\sf
F}(\text{Safety}_{k})\right)$
$\displaystyle\geq{\mathtt{val}_{S({\mathcal{M}}),{\it PP}_{\liminf\geq
0}}(s_{0}^{\prime})}-\varepsilon-\sum_{i\in\mathbb{N}}\varepsilon_{i}$ by (18)
$\displaystyle={\mathtt{val}_{S({\mathcal{M}}),{\it PP}_{\liminf\geq
0}}(s_{0}^{\prime})}-2\varepsilon$

Let
${\varphi}\stackrel{{\scriptstyle\text{{\tiny{def}}}}}{{=}}\bigcap_{i\in\mathbb{N}}\text{Safety}^{n_{i}}_{i}\subseteq{\it
PP}_{\liminf\geq 0}$. It follows from 5 that

${\mathtt{val}_{S({\mathcal{M}}),{\varphi}}(s_{0}^{\prime})}\geq{\mathtt{val}_{S({\mathcal{M}}),{\it
PP}_{\liminf\geq 0}}(s_{0}^{\prime})}-2\varepsilon.$ (19)

The objective ${\varphi}$ is a safety objective on $S({\mathcal{M}})$.
Therefore, since $S({\mathcal{M}})$ is acyclic, we can apply Lemma 5.7 to
obtain a uniformly $\varepsilon$-optimal MD strategy $\sigma^{\prime}$ for
${\varphi}$. Thus

$\displaystyle{\mathcal{P}}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma^{\prime}}({\it
PP}_{\liminf\geq 0})$
$\displaystyle\geq{\mathcal{P}}_{S({\mathcal{M}}),s_{0}^{\prime},\sigma^{\prime}}({\varphi})$
set inclusion
$\displaystyle\geq{\mathtt{val}_{S({\mathcal{M}}),{\varphi}}(s_{0}^{\prime})}-\varepsilon$
$\sigma^{\prime}$ is $\varepsilon$-opt.
$\displaystyle\geq{\mathtt{val}_{S({\mathcal{M}}),{\it PP}_{\liminf\geq
0}}(s_{0}^{\prime})}-3\varepsilon.$ by (19)

Thus $\sigma^{\prime}$ is a $3\varepsilon$-optimal MD strategy for ${\it
PP}_{\liminf\geq 0}$ in $S({\mathcal{M}})$.

By Remark 5.3 this then yields a $3\varepsilon$-optimal Markov strategy for
${\it PP}_{\liminf\geq 0}$ from $s_{0}$ in ${\mathcal{M}}$, since runs in
${\mathcal{M}}$ and $S({\mathcal{M}})$ coincide wrt. ${\it PP}_{\liminf\geq
0}$.

See 5.17

######  Proof D.10.

We consider the encoded system $A({\mathcal{M}})$ in which both step counter
and reward counter are implicit in the state. Recall that the partial mean
payoffs in ${\mathcal{M}}$ correspond exactly to point rewards in
$A({\mathcal{M}})$. Since $A({\mathcal{M}})$ has an encoded step counter,
Theorem 5.16 gives us $\varepsilon$-optimal MD strategies for ${\it
PP}_{\liminf\geq 0}$ in $A({\mathcal{M}})$. Lemma 5.5 allows us to translate
these strategies back to ${\mathcal{M}}$ with a memory overhead of just a
reward counter and a step counter as required.

See 5.18

######  Proof D.11.

We consider the encoded system $R({\mathcal{M}})$ in which the reward counter
is implicit in the state. Recall that total rewards in ${\mathcal{M}}$
correspond exactly to point rewards in $R({\mathcal{M}})$. We then apply
Theorem 5.16 to $R({\mathcal{M}})$ to obtain $\varepsilon$-optimal MD
strategies for ${\it PP}_{\liminf\geq 0}$ in $S(R({\mathcal{M}}))$. Remark 5.3
allows us to translate these MD strategies back to $R({\mathcal{M}})$ with a
memory overhead of just a step counter. Then we apply Lemma 5.2 to translate
these Markov strategies back to ${\mathcal{M}}$ with a memory overhead of just
a reward counter. Hence $\varepsilon$-optimal strategies for ${\it
TP}_{\liminf\geq 0}$ in ${\mathcal{M}}$ just use a step counter and a reward
counter as required.

######  Remark D.12.

While $\varepsilon$-optimal strategies for mean payoff and total payoff (in
infinitely branching MDPs) have the same memory requirements, the step counter
and the reward counter do not arise in the same way. Both the step counter and
reward counter used in $\varepsilon$-optimal strategies for mean payoff arise
from the construction of $A({\mathcal{M}})$. However, in the case for total
payoff, only the reward counter arises from the construction of
$R({\mathcal{M}})$. The step counter on the other hand arises from the Markov
strategy needed for point payoff in $R({\mathcal{M}})$.

See 5.19

######  Proof D.13.

To obtain the result for ${\it PP}_{\liminf\geq 0}$, we work in
$S({\mathcal{M}})$ and we apply Theorem 5.16 to obtain $\varepsilon$-optimal
MD strategies from every state of $S({\mathcal{M}})$. Since ${\it
PP}_{\liminf\geq 0}$ is a tail objective, Theorem 5.8 yields an MD strategy