Let us consider the second case. Let $u \in V_{\text{Max}}$, we say that $u \xrightarrow{w} v \in E$ is an improving edge if $\text{val}^{\sigma}(u) < \delta(\text{val}^{\sigma}(v), w)$. Given a set of improving edges $S$ (for each $u \in V_{\text{Max}}$, $S$ contains at most one outgoing edge of $u$), we write $\sigma[S]$ for the strategy

$$ \sigma[S](u) = \begin{cases} e & \text{if there exists } e = u \xrightarrow{w} v \in S, \\ \sigma(v) & \text{otherwise.} \end{cases} $$

Strategy improvement algorithms depend on the following two principles:

* **Progress**: updating a strategy using improving edges is a strict improvement,

* **Optimality**: a strategy which does not have any improving edges is optimal.

Let us write $\sigma \le \sigma'$ if for all vertices $v$ we have $\text{val}^{\sigma}(v) \le \text{val}^{\sigma'}(v)$, and $\sigma < \sigma'$ if additionally $\neg(\sigma' \le \sigma)$.

**The algorithm.** The pseudocode of the algorithm is given in Algorithm 4.5.

<caption>**Algorithm 4.5:** The strategy improvement algorithm for discounted payoff games.</caption>

**Data:** A discounted payoff game $\mathcal{G}$
Choose an initial strategy $\sigma_0$ for Max
**for** $i = 0, 1, 2, \dots$ **do**
    Compute $\text{val}^{\sigma_i}$ and the set of improving edges
    **if** $\sigma_i$ does not have improving edges **then**
        **return** $\sigma_i$
    Choose a non-empty set $S_i$ of improving edges
    $\sigma_{i+1} \leftarrow \sigma_i[S_i]$

**An example** Let us consider the discounted payoff game of Figure 4.2 with $\lambda = 0.5$, and start from the strategy $\sigma(v_0) = v_0 \xrightarrow{5} v_4$ and $\sigma(v_2) = v_2 \xrightarrow{1} v_2$.

We compute $\text{val}^{\sigma}$ by solving the linear program:

$$
\begin{array}{lll}
\text{maximise} & x_0 + x_1 + x_2 + x_3 + x_4 & \\
\text{subject to} & x_0 = (1-\lambda) \cdot 5 + \lambda \cdot x_4 & \\
& x_1 \le (1-\lambda) \cdot 0 + \lambda \cdot x_0 & \\
& x_1 \le (1-\lambda) \cdot 2 + \lambda \cdot x_2 & \\
& x_2 = (1-\lambda) \cdot 1 + \lambda \cdot x_2 & \\
& x_3 \le (1-\lambda) \cdot (-2) + \lambda \cdot x_0 & \\
& x_3 \le (1-\lambda) \cdot (-1) + \lambda \cdot x_1 & \\
& x_4 \le (1-\lambda) \cdot (-2) + \lambda \cdot x_0 & \\
& x_4 \le (1-\lambda) \cdot 2 + \lambda \cdot x_4 &
\end{array}
$$

Feeding this linear program to a solver we obtain the solution

$$ \vec{x} = \left( \frac{8}{3}, \frac{4}{3}, 1, \frac{1}{6}, \frac{1}{3} \right). $$
The only improving edge is $v_2 \xrightarrow{4} v_3$, so we iterate with the strategy $\sigma'$ defined by $\sigma'(v_0) = v_0 \xrightarrow{5} v_4$ and $\sigma'(v_2) = v_2 \xrightarrow{4} v_3$. The new vector of values found by solving the new linear program is

$$ \vec{x}' = \left( \frac{8}{3}, \frac{4}{3}, \frac{25}{12}, \frac{1}{6}, \frac{1}{3} \right), $$

which is the (unique) fixed point of $\mathcal{O}^{\mathcal{G}}$.

**Proof of correctness.** We now prove the two principles: progress and optimality.

**Lemma 42 (Progress for the strategy improvement algorithm for discounted payoff games).** Let $\sigma$ a strategy and $S$ a set of improving edges. We let $\sigma'$ denote $\sigma[S]$. Then $\sigma < \sigma'$.

*Proof.* Let $\tau, \tau'$ optimal positional strategies in $\mathcal{G}[\sigma]$ and $\mathcal{G}[\sigma']$. As in the proof of Theorem 44, letting $Q, \vec{c}, Q', \vec{c}'$ and the respective matrices and cost vectors described by the pairs of strategies $(\sigma, \tau)$ and $(\sigma', \tau')$, we have

$$ \mathrm{val}^{\sigma} = (1-\lambda) \cdot \vec{c} + \lambda \cdot Q \cdot \mathrm{val}^{\sigma} \quad \text{and} \quad \mathrm{val}^{\sigma'} = (1-\lambda) \cdot \vec{c}' + \lambda \cdot Q' \cdot \mathrm{val}^{\sigma'}. $$

Therefore:

$$ \mathrm{val}^{\sigma'} - \mathrm{val}^{\sigma} = \lambda \cdot Q' \cdot (\mathrm{val}^{\sigma'} - \mathrm{val}^{\sigma}) + \underbrace{\lambda \cdot (Q' - Q) \cdot \mathrm{val}^{\sigma} + (1-\lambda) \cdot (\vec{c}' - \vec{c})}_{=\vec{\delta}}. $$

So:

$$ (I - \lambda \cdot Q') \cdot (\mathrm{val}^{\sigma'} - \mathrm{val}^{\sigma}) = \vec{\delta}. $$

Since $Q'$ is a positive matrix with coefficients in $\{0,1\}$, the series $\sum_i \lambda^i \cdot Q^{ii}$ converges, which shows that $I - \lambda \cdot Q'$ is invertible of inverse $\sum_{i=0}^{\infty} \lambda^i \cdot Q^{ii}$. In particular, the inverse $(I - \lambda Q')^{-1}$ has only non-negative coefficients, and its diagonal coefficients are positive. Therefore, to show that $\mathrm{val}^{\sigma'} - \mathrm{val}^{\sigma} = (I - \lambda \cdot Q')^{-1} \cdot \vec{\delta}$ is non-negative with at least one positive coefficient, it suffices to show that $\vec{\delta}$ is non-negative with at least one positive coefficient. Let $u \in V$:

* If $u \in V_{\mathrm{Max}}$, let $\sigma(u) = u \xrightarrow{w} v$ and $\sigma'(u) = u \xrightarrow{w'} v'$, we have

$$ \delta_u = \lambda \cdot (\mathrm{val}^{\sigma}(v') - \mathrm{val}^{\sigma}(v)) + (1-\lambda)(w' - w). $$

If $\sigma(u) = \sigma'(u)$, then $\delta_u = 0$. Otherwise, $\delta_u > 0$ by definition of an improving edge.

* If $u \in V_{\mathrm{Min}}$, let $\tau(u) = u \xrightarrow{w} v$ and $\tau'(u) = u \xrightarrow{w'} v'$, we have

$$ \delta_u = \lambda \cdot (\mathrm{val}^{\sigma}(v') - \mathrm{val}^{\sigma}(v)) + (1-\lambda)(w' - w). $$

By definition of $\tau$ we have $\mathrm{val}^{\sigma}(u) = \delta(\mathrm{val}^{\sigma}(v), w) \le \delta(\mathrm{val}^{\sigma}(v'), w')$. This implies $\lambda \cdot \mathrm{val}^{\sigma}(v) + (1-\lambda) \cdot w \le \lambda \cdot \mathrm{val}^{\sigma}(v') + (1-\lambda) \cdot w'$, so $\delta_u \ge 0$.
☐

**Lemma 43** (Optimality for the strategy improvement algorithm for discounted payoff games). Let $\sigma$ be a strategy that has no improving edges, then $\sigma$ is optimal.

*Proof.* Let $\sigma$ be a strategy that has no improving edges. We claim that $\text{val}^{\sigma}$ is a fixed point of $\mathcal{O}^{\mathcal{G}}$, which implies that $\text{val}^{\sigma} = \text{val}^{\mathcal{G}}$, meaning that $\sigma$ is optimal. Since $\text{val}^{\sigma}$ is a fixed point of $\mathcal{O}^{\mathcal{G}[\sigma]}$, for $u \in V_{\text{Min}}$ we have $\text{val}^{\sigma}(u) = \min\{\delta(\text{val}^{\sigma}(v), w) : u \xrightarrow{w} v \in E\}$.

The fact that $\sigma$ has no improving edges reads: for all $u \in V_{\text{Max}}$, for all $u \xrightarrow{w'} v' \in E$, $\delta(\text{val}^{\sigma}(v'), w') \le \delta(\text{val}^{\sigma}(v), w)$ where $\sigma(u) = u \xrightarrow{w} v$. Since $\text{val}^{\sigma}(u) = \delta(\text{val}^{\sigma}(v), w)$, this implies that $\text{val}^{\sigma}(u) = \max\{\delta(\text{val}^{\sigma}(v'), w) : v \xrightarrow{w} v' \in E\}$. The two equalities above witness that $\text{val}^{\sigma}$ is the unique fixed point of $\mathcal{O}^{\mathcal{G}}$. ☐

The value iteration and strategy improvement algorithms are incomparable:

* the value iteration algorithm has a runtime pseudo-polynomial, and more precisely polynomial with respect to the number of vertices and the binary encoding of the weights of the arena, but exponential with respect to the binary encoding of $\lambda$,

* the strategy improvement algorithm has a runtime exponential with respect to the number of vertices, but polynomial with respect to the binary encoding of $\lambda$ and the weights of the arena.

**Reducing mean payoff games to discounted payoff games**

Recall that Corollary 8 states that the mean payoff value $\text{val}^{\mathcal{G}}(v)$ is a rational number with denominator at most $n$. The minimal distance between two such rational numbers is $\frac{1}{n-1} - \frac{1}{n} = \frac{1}{n(n-1)}$, implying that a $\frac{1}{2n(n-1)}$ approximation $\beta$ of $\text{val}^{\mathcal{G}}(v)$ is enough to apply a rounding procedure finding the only such rational in the interval $[\beta - \frac{1}{2n(n-1)}, \beta + \frac{1}{2n(n-1)}]$. By interpreting the mean payoff game as a discounted payoff game with a nicely chosen $\lambda$, we are able to find such a good approximation:

**Theorem 47** (Discounted payoff approximation). Let $\mathcal{G}$ a mean payoff game. Let $\lambda \in (0, 1)$, we define $\mathcal{G}_{\lambda}$ the discounted payoff game obtained from $\mathcal{G}$. We let $\text{val}$ denote the mean payoff values and $\text{val}_{\lambda}(v)$ the discounted payoff values with $\lambda$ as discount factor. Then

$$ \|\text{val} - \text{val}_{\lambda}\|_{\infty} \le (1 - \lambda) \cdot 2n \cdot W. $$

*Proof.* Let $u \in V$. We prove the inequality $\text{val}_{\lambda}(u) - \text{val}^{\mathcal{G}}(u) \ge -(1 - \lambda) \cdot 2n \cdot W$ by reasoning on Max's strategies: a similar reasoning on Min's strategies allows one to obtain the other inequality $\text{val}_{\lambda}(u) - \text{val}^{\mathcal{G}}(u) \le (1 - \lambda) \cdot 2n \cdot W$.

Let $\sigma, \tau$ a pair of optimal positional strategies for the mean payoff game. The play starting from $u$ consistent with $\sigma$ and $\tau$ is a finite prefix and a simple cycle, hence the sequence of weights is:

$$ \rho = w_0, w_1, \dots, w_{k-1}, (w_k, \dots, w_{\ell})^{\omega}, $$
with $k, \ell \le n$. Note that $\text{val}^{\mathcal{G}}(u) = \frac{1}{\ell-k+1} \sum_{i=k}^{\ell} w_i$. Playing $\sigma$ in the discounted payoff game, we obtain that $\text{val}_{\lambda}(u) \ge \text{DiscountedPayoff}(\rho)$. We now compute precisely $\text{DiscountedPayoff}(\rho)$:

$$ (1 - \lambda) \cdot \sum_{i=0}^{k-1} \lambda^i \underbrace{w_i}_{\ge -W} + (1 - \lambda) \cdot \lambda^k \cdot \sum_{m=0}^{\infty} \lambda^{(\ell-k+1)m} \sum_{i=0}^{\ell-k} \lambda^i w_{k+i} $$

The first term is greater than or equal to $-(1 - \lambda^k) \cdot W$, and the second term is equal to

$$ \frac{(1 - \lambda) \cdot \lambda^k}{1 - \lambda^{\ell-k+1}} \sum_{i=0}^{\ell-k} \lambda^i \cdot w_{k+i}. $$

By shifting all weights by $W$, we can rewrite the sum as:

$$ \sum_{i=0}^{\ell-k} \lambda^i \cdot w_{k+i} = \sum_{i=0}^{\ell-k} \lambda^i \cdot (w_{k+i} + W) - W \cdot \sum_{i=0}^{\ell-k} \lambda^i $$

By using the fact that $w_{k+i} + W$ is non-negative and $\lambda^i \ge \lambda^{\ell-k}$, we obtain

$$ \begin{aligned} \sum_{i=0}^{\ell-k} \lambda^i \cdot w_{k+i} &\ge \lambda^{\ell-k} \cdot \sum_{i=0}^{\ell-k} (w_{k+i} + W) - W \cdot \frac{1 - \lambda^{\ell-k+1}}{1 - \lambda} \\ &= \lambda^{\ell-k} \sum_{i=0}^{\ell-k} w_{k+i} + (\ell - k + 1) \cdot \lambda^{\ell-k} \cdot W - W \cdot \frac{1 - \lambda^{\ell-k+1}}{1 - \lambda} \end{aligned} $$

Therefore, since $\text{val}^{\mathcal{G}}(u) = \frac{1}{\ell-k+1} \sum_{i=k}^{\ell} w_i$, we obtain

$$ \sum_{i=0}^{\ell-k} \lambda^i \cdot w_{k+i} \ge \lambda^{\ell-k} \cdot (\ell - k + 1) \cdot (\text{val}^{\mathcal{G}}(u) + W) - W \cdot \frac{1 - \lambda^{\ell-k+1}}{1 - \lambda}. $$

Together with the first term, we have

$$ \text{DiscountedPayoff}(\pi) \ge -W + \frac{(1 - \lambda) \cdot (\ell - k + 1)}{1 - \lambda^{\ell-k+1}} \cdot \lambda^{\ell} \cdot (\text{val}^{\mathcal{G}}(u) + W) $$

Since $\frac{1-\lambda^{\ell-k+1}}{1-\lambda} = \sum_{i=0}^{\ell-k} \lambda^i < \ell - k + 1$ and $\text{val}^{\mathcal{G}}(u) + W \ge 0$, we have

$$ \text{DiscountedPayoff}(\pi) \ge -W + \lambda^{\ell} \cdot (\text{val}^{\mathcal{G}}(u) + W) $$

Finally, since $\ell \le n$ we have $\lambda^{\ell} \ge \lambda^n > 1 - n \cdot (1 - \lambda)$, using the fact that $\frac{1-\lambda^n}{1-\lambda} = \sum_{i=0}^{n-1} \lambda^i < n$. Therefore, using again $\text{val}^{\mathcal{G}}(u) \le W$,

$$ \begin{aligned} \text{DiscountedPayoff}(\pi) &\ge -W + (1 - n \cdot (1 - \lambda)) \cdot (\text{val}^{\mathcal{G}}(u) + W) \\ &= -n \cdot (1 - \lambda) \cdot (W + \text{val}^{\mathcal{G}}(u)) + \text{val}^{\mathcal{G}}(u) \\ &\ge -2n \cdot (1 - \lambda) \cdot W + \text{val}^{\mathcal{G}}(u) \end{aligned} $$

We obtain

$$ \text{val}_{\lambda}(u) - \text{val}^{\mathcal{G}}(u) \ge -2n(1 - \lambda) \cdot W. $$

□
A direct corollary of Theorem 47 is an algorithm for computing the mean payoff values: picking $\lambda = 1 - \frac{1}{4n^2(n-1)W}$, we obtain a good enough approximation of the mean payoff values by solving the associated discounted payoff game. From a complexity point of view, this value iteration algorithm runs in polynomial time in the size of the arena, but exponential with respect to the representation of $\lambda$.

The previous reductions implies an improved theoretical complexity for mean payoff and parity games.

**Corollary 11 (Complexity).** *Solving mean payoff games and parity games is in UP ∩ coUP.*

*Proof.* The reduction from mean payoff to discounted payoff games allows to lift the UP ∩ coUP complexity of Theorem 44. Moreover, the reduction of Theorem 40 implies the same complexity for parity games. □

**4.5 Shortest path games**

The quantitative objective Sup generalises the qualitative objective Reach by stating numerical preferences on the target. Another quantitative extension of the reachability objective is to quantify the cost of a path towards the target: we define the quantitative objective ShortestPath over the set of colours $C = \mathbb{Z} \cup \{\text{Win}\}$ by

$$ \text{ShortestPath}(\rho) = \begin{cases} \sum_{i=0}^{k-1} \rho_i & \text{for } k \text{ the first index such that } \rho_k = \text{Win}, \\ \infty & \text{if } \rho_k \neq \text{Win for all } k. \end{cases} $$

We interpret the weights as costs and Min is trying to reach the target with the smallest possible cost. Note that we use the same abusive terminology as for the shortest path graph problem: the *cost* of a path is the sum of the weights along it (until the first occurrence of Win) and we are looking for a path of minimal cost, hence not necessarily the shortest in number of edges.

We fix a shortest path game $\mathcal{G}$. Without loss of generality we assume that Win appears only in a sink. Recall that by definition:

$$ \text{val}^{\mathcal{G}}(u) = \sup_{\sigma} \inf_{\tau} \text{ShortestPath}(\pi_{\sigma, \tau}^{v}). $$

Hence for a vertex $u$ there are three possibilities:

* $\text{val}^{\mathcal{G}}(u) = \infty$, meaning that Min cannot ensure to reach Win,

* $\text{val}^{\mathcal{G}}(u) \in \mathbb{Z}$, meaning that Min can ensure to reach Win with a finite cost (bounded from below),

* $\text{val}^{\mathcal{G}}(u) = -\infty$, meaning that Min can ensure to reach Win with arbitrarily negative cost.

Note that if all weights are one, then $\text{val}^{\mathcal{G}}$ is the rank defined in the attractor computation, see Section 2.1.

Detecting whether $\text{val}^{\mathcal{G}}(u) = \infty$ is easy:
<figure><img src="image_39.png" /></figure>

**Figure 4.4:** An example of a shortest path game with negative weights where Min does not have an optimal strategy. Indeed $val_G^>(v_0) = -\infty$ since for any $k$, Min has a strategy ensuring that ShortestPath is $-k$ by using $k$ times the self loop $-1$ before Win. However, if Min never sees Win the outcome is $\infty$.

**Lemma 44 (Detection of $\infty$ values).** Let $\mathcal{G}$ a shortest path game and $u$ a vertex. Then $val_{\mathcal{G}}^>(u) < \infty$ if and only if $u \in W_{\text{Min}(\text{Reach}(\text{Win}))}$. Consequently, if $val_{\mathcal{G}}^>(u) < \infty$, then $val_{\mathcal{G}}^>(u) \le nW$.

*Proof.* The first equivalence is clear. For the second statement, consider a positional strategy ensuring Reach(Win), it ensures to reach Win within at most $n$ steps, hence incurs a cost bounded by $n$ times the largest weight. $\square$

Before moving to algorithms, let us illustrate two difficulties:

* As illustrated in Figure 4.4, Min does not have optimal strategies in general.

* As illustrated in Figure 4.5, even if Min has an optimal strategy, it may not be positional.

We discuss Figure 4.5, which is a shortest path game where Min has an optimal strategy, but it cannot be made positional. First, Min has two positional strategies: $\tau_1(v_0) = v_0 \xrightarrow{-1} v_1$ and $\tau_2(v_0) = v_0 \xrightarrow{0} v_2$. Strategy $\tau_1$ does not ensure to reach the target, since Max can enforce the cycle $v_0 \xrightarrow{0} v_1 \xrightarrow{0} v_0$ forever and obtain payoff $\infty$. Strategy $\tau_2$ guarantees a payoff of 0. However, Min can be smarter by threatening Max. If Min plays once $\tau_1$, and then switches to $\tau_2$, he guarantees a payoff of $-1$. Doing so twice, he guarantees a payoff of $-2$. This reasoning is valid for playing up to 50 times $\tau_1$, showing to Min can ensure a payoff of $-50$. However it is not valid beyond: against the strategy that plays 51 times $\tau_1$, Max's optimal decision is to stop the game with $v_1 \xrightarrow{-50} v_2$, ensuring a payoff of $-50$. Indeed and more generally (as we will see), Max has a positional optimal strategy, which is to choose $v_1 \xrightarrow{-50} v_2$ right from the beginning.

**Detection of $-\infty$ values using mean payoff games**

We call 'detecting $-\infty$ values in shortest path games' the following decision problem: given a shortest path game $\mathcal{G}$ and a vertex $u$, do we have $val_{\mathcal{G}}^>(u) = -\infty$?

**Theorem 48 (Detection of $-\infty$ values using mean payoff games).** Detecting $-\infty$ values in shortest path games is polynomial time equivalent to solving mean payoff games.

We construct two simple reductions.
<figure><img src="image_40.png" /><figcaption>Figure 4.5: A shortest path game where Min needs memory to play optimally.</figcaption></figure>

**Lemma 45.** Let $\mathcal{G}$ a shortest path game, and $\mathcal{G}'$ the mean payoff game obtained from $\mathcal{G}$ by replacing the self loop with Win by a self loop with 0. Assume that for all vertices $u$ we have $\text{val}^\mathcal{G}(u) \neq \infty$. Then for all vertices $u$, we have $\text{val}^\mathcal{G}(u) = -\infty$ if and only if $\text{val}^\mathcal{G'}(u) < 0$. As a consequence, if $\text{val}^\mathcal{G}(u) > -\infty$, then $\text{val}^\mathcal{G}(u) \geq -nW$.

Note that as stated in Lemma 44, detecting vertices with value $\infty$ can be done in polynomial time, hence it does not reduce the generality of the reduction.

*Proof.* Let us fix $\sigma$ an optimal positional strategy for Max in the mean payoff game $\mathcal{G}'$. Since for all vertices $u$ we have $\text{val}^\mathcal{G}(u) \neq \infty$, thanks to Lemma 44 there exists a strategy $\sigma_0$ which ensures $\text{ShortestPath} \leq nW$ from all vertices.

Assume that $\text{val}^\mathcal{G}(u) = -\infty$. Let $\tau_M$ a strategy ensuring $\text{ShortestPath} < -nW$, and look at a play consistent with $\sigma$ and $\tau_M$. It contains necessarily a negative cycle, implying that $\sigma$ does not ensure $\text{MeanPayoff} \geq 0$. Since $\sigma$ is optimal, this implies that $\text{val}^\mathcal{G'} < 0$.

For the converse implication, assume now that $\text{val}^\mathcal{G'}(u) < 0$. This implies that all cycles consistent with $\sigma$ are negative. Consequently, for all paths consistent with $\sigma$, the sum of the weights diverges to $-\infty$. Let us fix $M$, and consider the strategy $\sigma_M$ which plays like $\sigma$ until the sum of the weights reaches below $M - nW$, and then switches to $\sigma_0$. This strategy ensures $\text{ShortestPath} \leq M$. Thus $\text{val}^\mathcal{G}(u) = -\infty$.

We now explain how it follows that if $\text{val}^\mathcal{G}(u) > -\infty$, then $\text{val}^\mathcal{G}(u) \geq -nW$. Since the optimal positional strategy $\sigma$ ensures $\text{MeanPayoff} \geq 0$, it also ensures that the sum of the weights remains larger than $-nW$ at all times. $\square$

**Lemma 46.** Let $\mathcal{G}$ a mean payoff game. We construct $\mathcal{G}'$ a shortest path game where after each edge, Min has a choice to stop the game with colour Win. Then for all vertices $u$ in the original game $\mathcal{G}$, we have $\text{val}^\mathcal{G}(u) < 0$ if and only if $\text{val}^\mathcal{G'}(u) = -\infty$.

*Proof.* Note that Min can ensure to reach Win from anywhere, so Min has a strategy to reach Win, implying that for all $u$ we have $\text{val}^\mathcal{G'}(u) \neq \infty$.

Let $\mathcal{G}''$ the mean payoff obtained from $\mathcal{G}'$ as in Lemma 45, we have that $\text{val}^\mathcal{G'}(u) = -\infty$ if and only if $\text{val}^\mathcal{G}''(v) < 0$. To conclude, it only remains to show that $\text{val}^\mathcal{G}(u) < 0$ if and only if $\text{val}^\mathcal{G}''(u) < 0$. The game $\mathcal{G}''$ is exactly as $\mathcal{G}$, except that anytime Min can
stop the game and settle for a mean payoff of 0. Hence when asking whether the mean payoff value is < 0, this option is not relevant. □

## A value iteration algorithm for shortest path games

**Theorem 49** (Half-positional determinacy in shortest path games). *Shortest path games are half-positionally determined over finite arenas.*

This half-positional determinacy result will follow from the correctness of a value iteration algorithm, which works for shortest path games where no vertices has value $-\infty$. Thanks to the above, this can be computed and removed from the game. We say that such a game is normalised. Note that it is enough to prove half-positional determinacy for normalised games, since on the vertices having value $-\infty$ the strategy of Max is irrelevant.

**Theorem 50** (Value iteration algorithm). *There exists a value iteration algorithm for computing the value function of normalised shortest path games in pseudo-polynomial time and space.*

Our first lemma shows the existence of optimal strategies.

**Lemma 47** (Optimal strategies). *Let $\mathcal{G}$ be a normalised shortest path game, then there exists an optimal strategy for Min.*

*Proof.* Thanks to the assumption that the game is normalised and Lemma 45, the values are lower bounded by $-nW$, which implies that the infimum is indeed a minimum. □

Figure 4.4 shows that the assumption that the game is normalised in Lemma 47 is necessary.

We follow the high-level presentation of value iteration algorithms given in Section 1.9. Let us define $Y = \mathbb{Z} \cup \{-\infty, \infty\}$ equipped with the natural order and the function $\delta: Y \times (\mathbb{Z} \cup \{\text{Win}\}) \to Y$ by

$$ \delta(x, w) = \begin{cases} 0 & \text{if } w = \text{Win}, \\ x+w & \text{if } w \in \mathbb{Z}. \end{cases} $$

We let $F_V$ be the lattice of functions $\mu: V \to Y$ equipped with the componentwise order induced by $Y$. Note that $\delta$ is monotonic, it induces the monotonic operator $\mathcal{O}^{\mathcal{G}}: F_V \to F_V$ defined by:

$$ \mathcal{O}^{\mathcal{G}}(\mu)(u) = \begin{cases} \max\{\delta(\mu(v), w) : u \xrightarrow{w} v \in E\} & \text{if } u \in V_{\text{Max}}, \\ \min\{\delta(\mu(v), w) : u \xrightarrow{w} v \in E\} & \text{if } u \in V_{\text{Min}}. \end{cases} $$

Thanks to Theorem 4, the operator $\mathcal{O}^{\mathcal{G}}$ has a greatest fixed point which is also the greatest post-fixed point of $\mathcal{O}^{\mathcal{G}}$. Recall that a post-fixed point of $\mathcal{O}^{\mathcal{G}}$ is a function $\mu \in F_V$ such that $\mathcal{O}^{\mathcal{G}}(\mu) \ge \mu$, it is also called a progress measure. Unfolding the definitions, for all vertices $u$, we have

$$ \exists u \xrightarrow{w} v \in E, \quad \mu(u) \le \delta(\mu(v), w) \quad \text{if } u \in V_{\text{Max}}, $$

$$ \forall u \xrightarrow{w} v \in E, \quad \mu(u) \le \delta(\mu(v), w) \quad \text{if } u \in V_{\text{Min}}. $$
**Lemma 48** (Shortest path values as greatest fixed point). Let $\mathcal{G}$ be a normalised shortest path game, then $\text{val}^{\mathcal{G}}$ is the greatest fixed point of $\mathcal{O}^{\mathcal{G}}$.

*Proof.* We show two properties:

* $\text{val}^{\mathcal{G}}$ is a progress measure;

* $\text{val}^{\mathcal{G}}$ is larger than the greatest fixed point of $\mathcal{O}^{\mathcal{G}}$.

Since the greatest fixed point of $\mathcal{O}^{\mathcal{G}}$ is also the greatest progress measure, the first item implies that it is larger than $\text{val}^{\mathcal{G}}$, and the second item states the converse inequality.

The first item is a routine verification, which follows from two properties (see Lemma 8).

* For all $\rho$ sequences of weights, we have

$$ \text{ShortestPath}(w \cdot \rho) = \delta(\text{ShortestPath}(\rho), w). $$

* The function $\delta$ is monotonic and continuous.

We now show the second item: $\text{val}^{\mathcal{G}}$ is larger than or equal to the greatest fixed point of $\mathcal{O}^{\mathcal{G}}$. For this, we consider a fixed point $\mu$ of $\mathcal{O}^{\mathcal{G}}$, and argue that $\text{val}^{\mathcal{G}} \ge \mu$. To this end, we extract from $\mu$ a strategy $\sigma$ for Max, and show that $\text{val}^{\sigma} \ge \mu$; since we know that $\text{val}^{\mathcal{G}} \ge \text{val}^{\sigma}$, this implies $\text{val}^{\mathcal{G}} \ge \mu$. We define $\sigma$ as an argmax strategy:

$$ u \in V_{\text{Max}} : \sigma(u) \in \operatorname{argmax} \left\{ \delta(\mu(v), w) : u \xrightarrow{w} v \in E \right\}. $$

Let us define the graph $G = \mathcal{G}[\sigma]$, by definition of $\sigma$ for all edges $u \xrightarrow{w} v$ in $G$ we have $\mu(u) \le \delta(\mu(v), w)$. We claim that this implies that for all paths $\rho$ from $u$ in $G$, we have $\text{ShortestPath}(\rho) \ge \mu(u)$. If $\text{ShortestPath}(\rho) = \infty$, this is clear, so let us consider the finite case, and proceed by induction on the length $k$ of the path before reaching Win. This is clear for $k = 0$, since both values are 0. Let us assume that it holds for $k$ and show that it also does for $k + 1$. Let us write $\rho_0 = u \xrightarrow{w} v$. By the property above, we have $\mu(u) \le \delta(\mu(v), w) = \mu(v) + w$. Hence

$$ \sum_{i=0}^{k} \rho_i = w + \sum_{i=1}^{k} \rho_i \ge w + \mu(v) \ge \mu(u), $$

where the first inequality is by induction hypothesis for the path $\rho_1 \dots \rho_{k-1}$ from $v$. This concludes the induction. $\square$

Lemma 48 does not immediately yield a value iteration algorithm because the lattice $Y$ is infinite. However, let us note that by half-positional determinacy, the value of a vertex is either $\infty, -\infty$, or in $[-nW, nW]$. Hence we can equivalently define $Y = [-nW, nW] \cup \{-\infty, \infty\}$ and $\delta: Y \times (\mathbb{Z} \cup \{\text{Win}\}) \to Y$ by

$$ \delta(x, w) = \begin{cases} 0 & \text{if } w = \text{Win}, \\ x+w & \text{if } w \in \mathbb{Z} \text{ and } x+w \in [-nW, nW], \\ \infty & \text{if } w \in \mathbb{Z} \text{ and } x+w > nW, \\ -\infty & \text{if } w \in \mathbb{Z} \text{ and } x+w < -nW. \end{cases} $$
It is clear that the greatest fixed points for both operators coincide thanks to the remark above, and now that we have a finite lattice we can use the generic monotonic fixed point computation (see Theorem 4) to compute $val_\mathcal{G}^\mathcal{G}$, which yields a pseudo-polynomial time and space algorithm.

## Shortest path games with non-negative weights

**Theorem 51** (Polynomial time algorithm for shortest path games with non-negative weights). There exists an algorithm for computing the values in shortest path games with non-negative weights running in time $O(m+n\log(n))$.

In the case where all weights are non-negative, the value iteration algorithm can be made much more efficient, and in particular in polynomial time. To understand this, let us start by noting that the one-player case where only Min has moves is the classical shortest path problem (towards Win) for graphs. We extend Dijkstra's algorithm, see Algorithm 4.6 for the pseudocode.

Let us denote by $S_i$, $\mu_i(u)$, $\mu_i(u \xrightarrow{w} v)$ the values in iteration $i$. We define the invariants satisfied by the algorithm.

1. $\mu_i(u)$ is value of $u$ in the shortest path game $\mathcal{G}_i$ obtained by replacing $u \xrightarrow{w} v$ with $u \xrightarrow{\infty} v$ if both $u$ and $v$ are still in $S_i$;

2. $\min\{\mu_i(u) : u \in S_i\} \geq \max\{val_\mathcal{G}^\mathcal{G}(u) : u \notin S_i\}$.

The second invariant generalises the greedy property of Dijkstra's algorithm.

Since the weight of every edge in $\mathcal{G}_i$ is non-increasing, the values $val_\mathcal{G}_i(u)$ are also non-increasing. The invariants show imply that $\mu_i(u) = val_\mathcal{G}_i(u)$ for all $u \in S_i$ and $\mu_i(u) = val_\mathcal{G}(u)$ for all $u \notin S_i$. We refer to [KBB+08] for the detailed proofs of the invariants. A careful analysis, using (minimum) Fibonacci heaps, as in Dijkstra's algorithm, allows one to obtain an overall complexity $O(m+n\log(n))$.

## 4.6 Total payoff games

Recall that the total payoff objective is defined by

$$ \text{TotalPayoff}(\rho) = \limsup_k \sum_{i=0}^{k-1} \rho_i. $$

Contrary to the shortest path objective, total payoff games do not include a reachability objective. In particular, all plays will be infinite and their payoff is the superior limit of the partial sums: we need this superior limit since partial sums might not have a limit (consider for instance the sequence of weights $1, -1, 1, -1, 1, \dots$ whose partial sums alternate between 1 and 0).

It is easy to show that solving total payoff games is in $NP \cap coNP$: they are positionally determined, and the one-player games can be solved in polynomial time using
**Algorithm 4.6:** A polynomial time algorithm for shortest path games with non-negative weights.

**Data:** A shortest path game with non-negative weights.

**Function Init() :**

```
for u ∈ V do
    [ µ(u) ← ∞

for u ∈ VMin do
    if ∃u $\xrightarrow{Win}$ v ∈ E then
        [ µ(u) ← 0
        Add u to S

for u ∈ VMax do
    if ∀u $\xrightarrow{Win}$ v ∈ E then
        [ µ(u) ← 0
        Add u to S

else
    for u $\xrightarrow{w}$ v ∈ E do
        [ µ(u $\xrightarrow{w}$ v) ← ∞
```

**Function Main() :**

```
Init ()
repeat
    Extract v ∈ argmin{µ(v) : v ∈ S}
    for u $\xrightarrow{w}$ v ∈ E do
        if u ∈ VMin and µ(u) > δ(µ(v), w) then
            [ µ(u) ← δ(µ(v), w)
            Update µ(u) in S
        if u ∈ VMax and µ(u $\xrightarrow{w}$ v) > µ(v) then
            [ µ(u $\xrightarrow{w}$ v) ← µ(v)
            x ← max{µ(u $\xrightarrow{w'}$ v') : u $\xrightarrow{w'}$ v' ∈ E}
            if µ(u) > x then
                [ µ(u) ← x
                Update µ(u) in S
        until S is empty
    return µ
```
<figure><img src="image_41.png" /><figcaption>Figure 4.6: A total payoff game</figcaption></figure>

shortest paths algorithms. However, constructing a value iteration is not easy. A natural attempt is to define the following operator:

$$ \mathcal{O}^{\mathcal{G}}(\mu)(u) = \begin{cases} \max\{\mu(v) + w : u \xrightarrow{w} v \in E\} & \text{if } u \in V_{\text{Max}}, \\ \min\{\mu(v) + w : u \xrightarrow{w} v \in E\} & \text{if } u \in V_{\text{Min}}. \end{cases} $$

One can show that the value function is indeed a fixed point of $\mathcal{O}^{\mathcal{G}}$. But it is neither the greatest nor the least fixed point. Consider for example the total payoff game represented in Figure 4.6. The fixed points of $\mathcal{O}^{\mathcal{G}}$ are $(a, a+1, a+2)$ with $a \in \mathbb{R} \cup \{\pm\infty\}$: in particular, the greatest fixed point is $(+\infty, +\infty, +\infty)$ and the least fixed point is $(-\infty, -\infty, -\infty)$. However, the value function is $(0, 1, 2)$.

We obtain a pseudo-polynomial time algorithm by reduction to a shortest path game of pseudo-polynomial size.

**Theorem 52** (A reduction from total payoff games to shortest path games). Let $\mathcal{G}$ a total payoff game, we can construct a shortest path game $\mathcal{G}'$ such that for all vertices $u$ from $\mathcal{G}$, we have $\text{val}^{\mathcal{G}}(u) = \text{val}^{\mathcal{G}'}(u)$. The game $\mathcal{G}'$ has size pseudo-polynomial in the size of $\mathcal{G}$.

*Proof.* Let us fix $K = n \cdot ((2n-1) \cdot W + 1)$. The game $\mathcal{G}'$ consists in $K$ consecutive copies of $\mathcal{G}$. In each copy, after each move, Min can offer Max the following alternative: either the game stops and reaches Win, or we move to the next copy. For the chosen $K$, one can show that the values of $\mathcal{G}$ coincide with the values of the first copy of $\mathcal{G}'$.

Instead of explicitly constructing $\mathcal{G}'$, we can run the value iteration algorithm for shortest path games in each copy, improving the space complexity of the algorithm. $\square$

## Bibliographic references

This chapter has been the occasion to start revealing a ladder of reductions going from parity games through mean payoff games and to discounted payoff games. In Chapter 6, the last reduction from discounted payoff games to simple stochastic games will complete this chain of reductions.

**Mean payoff games.** Mean payoff games have been first studied by Ehrenfeucht and Mycielski in [EM79] where positional determinacy is shown. The one-player variants had already been studied by Karp [Kar78]. It is much later that Zwick and Paterson [ZP96] first obtained the pseudo-polynomial value iteration algorithm to solve
them, while introducing discounted payoff games (that had been first studied in a prob-
abilistic setting as will be studied in Chapter 5 and Chapter 6). The NP and coNP upper
bound, together with strategy improvement algorithm, is due to Pure [Pur95].

The first-cycle games theorem is due to Aminof and Rubin [AR17], who fixed a
flaw in the proof of Björklund, Sandberg and Vorobyov [BSV04] of positional deter-
minacy for mean payoff games. The fairly mixing theorem is due to Gimbert and
Zielonka [GZ04].

**Strategy improvement algorithms.** There are several strategy improvement algo-
rithms for computing the mean payoff values. Björklund and Vorobyov [BV07] con-
structed one such algorithm for computing the energy values, presented via the notion
of *longest shortest path problem*. A more direct approach was construct by Filar and
Vrieze [FV96], involving a pair of values, called gain and bias. Strategy improve-
ment methods (for parity games or payoff games) are very closely related to the sim-
plex method for solving linear programs, see for instance [ABGJ14]. Lifshits and
Pavlov [LP07] develop yet another strategy improvement algorithm for mean payoff
games using potential reduction techniques, which were originally described by Gal-
lai [Gal58] in the context of networks-related problems, and also developed by Gur-
vich, Karzanov, and Khachiyan [GKK88] in the context of mean payoff games. This
has been further explored, see for instance [Ohl22].

Energy games.

**Value iteration algorithm.** The value iteration algorithm for energy games has been developed by Brim, Chaloupka, Doyen, Gentilini, and Raskin [BCD<sup>+</sup>11]. Comin and Rizzi [CR17] have shown how to adapt the algorithm to compute optimal strategies as well with a running time $O(n^2mW)$. This removes the $\log(n)+\log(W)$ term due to binary search.

**Shortest path games.** As we have seen, computing the values for shortest path games can be done in polynomial time when weights are non-negative, this has been proved by Khachiyan and coauthors [KBB<sup>+</sup>08]. No polynomial solution is known for the general case. The best known at the time this chapter is written is a polynomial time fragment consisting of *divergent shortest path games* [BGMR17] in which the arena does not contain any cycle with total weight 0: this a priori weak property indeed partitions the strongly connected components of the arena into the ones where all cycles are positive, and the ones where all cycles are negative; in each of these components, it is shown why the value iteration algorithm converges in polynomial time. Theorem 48 shows the equivalence between mean payoff games and detecting vertices of values $-\infty$ in shortest path games. It is open whether solving shortest path games where no vertices have value $-\infty$ can be done in polynomial time.

**Total payoff games.** The analysis of total payoff games and shortest path games is due to [BGHM17].
# Part II

## Stochastic
<figure><img src="image_42.png" /></figure>
MARKOV
DECISION PROCESSES

<figure><img src="image_43.png" /></figure>
Chapter 5

# Markov Decision Processes

PETR NOVOTNÝ

In this chapter we study Markov decision processes (MDPs), a standard model for decision making under uncertainty. MDPs are also called ‘1½-player games’, since they can be viewed as a game in which only one player makes strategic choices, while the other player, which we call Nature, behaves according to some fixed probabilistic model. The chapter surveys the basic notions pertaining to MDPs, and algorithms for the following MDP-related problems:

• positive and almost-sure reachability and safety,

• discounted payoff,

• mean payoff in strongly connected MDPs,

• decomposition of MDPs into maximal end-components (MECs),

• reductions of general mean payoff MDPs, Büchi MDPs, and parity MDPs to general reachability MDPs (via the MEC decomposition),

• solving general reachability in MDPs.

## Notations

We write vectors in boldface: $\vec{x}, \vec{y}$, etc. For a vector $\vec{x}$ indexed by a set $I$ (i.e. $\vec{x} \in \mathbb{R}^I$) we denote by $\vec{x}_i$ the value of the component whose index is $i \in I$.

A (discrete) *probability distribution* over a finite or countably infinite set $A$ is a function $f: A \to [0, 1]$ such that $\sum_{a \in A} f(a) = 1$. The *support* of such a distribution $f$ is the set of all $a \in A$ with $f(a) > 0$. A distribution $f$ is called *Dirac* if its support has size 1. We denote by $\mathcal{D}(A)$ the set of all probability distributions over $A$.
We also deal with probabilities over uncountable sets of events. This is accomplished via the standard notion of a *probability space*.

**Definition 8 (Probability space).** A probability space is a triple $(S, \mathcal{F}, \mathbb{P})$ where

• $S$ is a non-empty set of events (so called sample space).

• $\mathcal{F}$ is a sigma-algebra over $S$, i.e. a collection of subsets of $S$ that contains the empty set $\emptyset$ and that is closed under complementation and countable unions. The members of $\mathcal{F}$ are called $\mathcal{F}$-measurable sets.

• $\mathbb{P}$ is a probability measure on $\mathcal{F}$, i.e. a function $\mathbb{P}: \mathcal{F} \to [0, 1]$ such that:

1. $\mathbb{P}(\emptyset) = 0$;

2. for all $A \in \mathcal{F}$ it holds $\mathbb{P}(S \setminus A) = 1 - \mathbb{P}(A)$; and

3. for all countable sequences of pairwise disjoint sets $A_1, A_2, \dots \in \mathcal{F}$ (i.e., $A_i \cap A_j = \emptyset$ for all $i \neq j$) we have $\sum_{i=1}^{\infty} \mathbb{P}(A_i) = \mathbb{P}(\bigcup_{i=1}^{\infty} A_i)$.

A random variable in the probability space $(S, \mathcal{F}, \mathbb{P})$ is an $\mathcal{F}$-measurable function $X: \Omega \to \mathbb{R} \cup \{-\infty, \infty\}$, i.e., a function such that for every $a \in \mathbb{R} \cup \{-\infty, \infty\}$ the set $\{\omega \in \Omega | X(\omega) \le a\}$ belongs to $\mathcal{F}$. We denote by $\mathbb{E}[X]$ the *expected value* of a random variable $X$ (see Chapter 5 in [Bil95] for a formal definition).

We first give a syntactic notion of an MDP which is an analogue of the notion of an arena for games.

**Definition 9 (MDP).** A Markov decision process is a tuple $(V, E, \Delta, c)$. The meaning of $V$, $E$, and $c$ is the same as for games, i.e. $V$ is a finite set of vertices, $E \subseteq V \times V$ is a set of edges and $c: E \to C$ a mapping of edges to a set of colours. However, the meaning of $\Delta$ is now different: $\Delta$ is a partial probabilistic transition function of type $\Delta: V \times A \to \mathcal{D}(E)$, such that the support of $\Delta(v, a)$ only contains edges outgoing from $v$. We usually write $\Delta(v' | v, a)$ as a shorthand for $\Delta(v, a)((v, v'))$, i.e. the probability of transitioning from $v$ to $v'$ under action $a$.

We also stipulate that for each edge $(v_1, v_2)$ there exists an action $a \in A$ such that $\Delta(v_2 | v_1, a) > 0$. Edges not satisfying this can be always removed without changing the semantics of the MDP, which is defined below. We denote by $p_{\min}$ the smallest non-zero edge probability in a given MDP, i.e. $p_{\min} = \min\{x > 0 \mid \exists u, v \in V, a \in A \text{ s.t. } x = \Delta(v | u, a)\}$.

We denote by $E_C$ the set of edges coloured by $C$. Also, for MDPs where $C$ is some set of numbers, we use $\max_C$ to denote the number $\max_{e \in E} |c(e)|$. In the setting of MDPs it is technically convenient to encode regular objectives (Reachability, Büchi, ...) by colours on *vertices* as opposed to edges. Hence, when discussing these objectives, we assume that the colouring function $c$ has the type $V \to C$.

**Plays and strategies in MDPs** The way in which a play is generated in an MDP is similar to games, but now encompasses a certain degree of randomness. There is a single player, say Max, who controls all the vertices. Max's interaction with the 'world' described by an MDP is probabilistic. One reason is the stochasticity of the
transition function, the other is the fact that in MDP settings, it is usually permitted
for Max to use randomised strategies. Formally, a randomised strategy is a function
$\sigma: E^* \to \mathcal{D}(A)$, which to each finite play assigns a probability distribution over actions.
We typically shorten $\sigma(\pi)(a)$ to $\sigma(a | \pi)$.

In this section, we will refer to randomised strategies simply as ‘strategies’. The strategies known from the game setting will be called *deterministic strategies*. Formally, a deterministic strategy can be viewed as a special type of a randomised strategy which always selects a Dirac distribution over the edges. We shorten ‘memoryless randomised/deterministic’ to *MR* and *MD*, respectively.

Now a play in an MDP is produced as follows: in each step, when the finite play produced so far (i.e. the history of the game token’s movement) is $\pi$, Max chooses an action $a$ randomly according to the distribution $\sigma(\pi)$. Then, an edge outgoing from $\text{last}(\pi)$ is chosen randomly according to $\Delta(\text{last}(\pi), a)$ and the token is pushed along the selected edge. As shown below, this intuitive process can be formalized by constructing a special probability space whose sample space consists of infinite plays in the MDP.

**Formal semantics of MDPs** Formally, to each MDP $\mathcal{M}$, each (Max 's) strategy $\sigma$ in $\mathcal{M}$, and each initial vertex $v_0$ we assign a probability space $(S_{\mathcal{M}}, \mathcal{F}_{\mathcal{M}}, \mathbb{P}_{\mathcal{M},v_0}^{\sigma})$. To explain the individual components, we need the notion of a cylinder set. A *basic cylinder* determined by a finite play $\pi$ is the set of all infinite plays in $\mathcal{M}$ having $\pi$ as a prefix. Now the above probability space consists of the following components:

• $S_{\mathcal{M}}$ is the set of all infinite plays in $\mathcal{M}$;

• $\mathcal{F}_{\mathcal{M}}$ is the Borel sigma-algebra over $\Omega_{\mathcal{M}}$; this is the smallest sigma-algebra containing all the basic cylinder sets determined by finite plays in $\mathcal{M}$. The sets in $\mathcal{F}_{\mathcal{M}}$ are called *events*. Note that the smallest sigma-algebra of the desired property is guaranteed to exist, since an intersection of an arbitrary number of sigma-algebras is again a sigma algebra.

• $\mathbb{P}_{\mathcal{M},v_0}^{\sigma}$ is the unique probability measure arising from the *cylinder construction* detailed below. We use $\mathbb{E}_{\mathcal{M},v_0}^{\sigma}$ to denote the *expectation operator* associated to the measure $\mathbb{P}_{\mathcal{M},v_0}^{\sigma}$.

Since the sample space $S_{\mathcal{M}}$ is uncountable, we construct the probability measure by first specifying a probability of certain simple sets of runs and then using an appropriate *measure-extension theorem* to extend the probability measure, in a unique way, to all sets in $\mathcal{F}_{\mathcal{M}}$. The standard cylinder construction proceeds as follows: for each finite play $\pi$ we define the probability $p(\pi)$ such that

• for an empty play $\varepsilon$ we put $p(\varepsilon) = 1$;

• for a non-empty play $\pi = \pi_0 \cdots \pi_k$ initiated in $v_0$ we put

$$p(\pi) = p(\pi_{<k}) \cdot \left( \sum_{a \in A} \sigma(a | \pi_{<k}) \cdot \Delta(\text{last}(\pi) | \text{last}(\pi_{<k}), a) \right),$$

where we use the convention that $\text{last}(\pi_{<0}) = v_0$;
• for all other $\pi$ we have $p(\pi) = 0$.

Now using an appropriate measure-extension theorem (such as Hahn-Kolmogorov theorem [Ros06, Corollary 2.5.4 and Proposition 2.5.7], or Carathéodory theorem [ADD00, Theorem 1.3.10]) one can show that there is a unique probability measure $P_{\mathcal{M},v_0}^{\sigma}$ on $\mathcal{F}_{\mathcal{M}}$ such that for every cylinder set $Cyl(\pi)$ determined by some finite play $\pi$ we have $P_{v_0}^{\sigma}(Cyl(\pi)) = p(\pi)$. (Abusing the notation, we write $P_{\mathcal{M},v_0}^{\sigma}(\pi)$ for the probability of this cylinder set). There are some intermediate steps to be performed before an extension theorem can be applied, and we omit these due to space constraints. Full details on the cylinder construction can be found, e.g. in [ADD00, Nov15].

While the construction of the probability measure $P_{\mathcal{M},v_0}^{\sigma}$ might seem a bit esoteric, in the context of MDP verification we do not usually need to be concerned with all the delicacies behind the associated probability space. The sets of plays that we work with typically arise from the basic cylinder sets by means of countable unions, intersections, and simple combinations thereof; such sets by definition belong to the sigma-algebra $\mathcal{F}_{\mathcal{M}}$, and their probabilities can be inferred using basic probabilistic reasoning. Nevertheless, one should keep in mind that all the probabilistic argumentation rests on solid formal grounds.

In the standard MDP literature [Put05], the plays are often defined as alternating sequence of vertices and actions. Here we stick to the edge-based definition inherited from deterministic games. Still, we would sometimes like to speak about quantities such as 'probability that action $a$ is taken in step $i'$. To this end, we introduce, for each strategy $\sigma$, each action $a$, and each $i \ge 0$, a random variable $A_{a,i}^{\sigma}$ such that $A_{a,i}^{\sigma}(\pi) = \sigma(\pi_{<i})(a)$. It is easy to check that $E_{v}^{\sigma}[A_{a,i}^{\sigma}]$ is the probability that action $a$ is played in step $i$ when using strategy $\sigma$.

**Objectives in MDPs** Similarly to plays, the notions of both qualitative and quantitative objectives are inherited from the non-stochastic world of games. However, since plays in MDPs are generated stochastically, even for a fixed strategy $\sigma$ there is typically no single infinite play that would constitute the outcome of $\sigma$. A concrete $\sigma$ might yield different outcomes, depending on the results of random events during the interaction with the MDP. Hence, we need a more general way of evaluating strategies in MDPs.

In the game setting, a qualitative objective was given as a set $\Omega \subseteq C^\omega$. In the MDP setting, we require that such $\Omega$ is measurable in the sense that the set $c^{-1}(\Omega) = \{\pi \in S_{\mathcal{M}} | c(\pi) \in \Omega\}$ belongs to $\mathcal{F}_{\mathcal{M}}$. We can then talk about a probability that the produced play satisfies $\Omega$. For instance, for a colour $c$ the objective $\mathit{Reach}(c)$ is indeed measurable, since $c^{-1}(\Omega)$ can be written as a countable union of all basic cylinders that are determined by finite plays ending in a vertex coloured by $c$. Indeed, all the qualitative objectives studied in previous chapters can be shown measurable in a similar way, and we encourage the reader to prove this as an exercise. Hence, the expression $P_{\mathcal{M},v_0}^{\sigma}(\mathit{Reach}(c))$ denotes the probability that a vertex of colour $c$ is reached when using strategy $\sigma$ from vertex $v_0$. Naturally, Max aims at maximizing this probability. We refer to Max as "she", and in subsequent chapters when studying two-player stochastic games the opponent Min will be "he".
The situation is more complex for quantitative objectives. As shown in the previous chapter, when working with quantitative objectives, the set of colours C is typically the set of real numbers (or a subset thereof), and the quantitative objective is given by an 'aggregating function' $f: C^\omega \to R$, which can be extended into a function $\tilde{f}: E^\omega \to R$ by putting $\tilde{f}(\pi) = f(c(\pi_0)c(\pi_1)\cdots)$. In the MDP setting, we require that $\tilde{f}$ is $\mathcal{F}_M$-measurable, which means that for each $x \in R$ the set $\{\pi \in E^\omega | f(c(\pi_0)c(\pi_1)\cdots) \le x\}$ belongs to $\mathcal{F}_M$ (again this holds for all the objectives studied in the previous chapters). Then there are two ways in which we can define the expected payoff achieved by strategy $\sigma$ from a vertex $v$. First, we can treat $\tilde{f}$ as a random variable in the probability space $(S_M, \mathcal{F}_M, \mathbb{P}_{M,v}^\sigma)$. Then the *play-based payoff* of $\sigma$ from $v$, which we denote by $\text{p-Payoff}_f(v, \sigma)$, is the expected value of this random variable, i.e. $\text{p-Payoff}_f(v, \sigma) = \mathbb{E}_v^\sigma[\tilde{f}]$. That is, we compute the expected payoff over all plays. This approach summarizes also qualitative objectives: For such an objective $\Omega$ we can consider an *indicator* random variable $\mathbf{1}_\Omega$, such that $\mathbf{1}_\Omega(\pi) = 1$ of $\pi \in \Omega$ and $\mathbf{1}_\Omega(\pi) = 0$ otherwise. Then $\mathbb{P}_{M,v}^\sigma(\Omega) = \mathbb{E}_{M,v}^\sigma[\mathbf{1}_\Omega] = \text{p-Payoff}_{\mathbf{1}_\Omega}(v, \sigma)$.

The second approach to quantitative objectives in MDPs, common e.g. in the operations research literature, is step-based: for each time step $i$ we compute the expected one-step reward (i.e. colour) encountered in that step and then aggregate these one-step expectations. Formally, the *step-based payoff* of $\sigma$ from $v$ is $\text{s-Payoff}_f(v, \sigma) = f(\mathbb{E}_v^\sigma[c(\pi_0)]\mathbb{E}_v^\sigma[c(\pi_1)]\cdots)$, where for each $i$ we treat the expression $c(\pi_i)$ as a random variable returning the colour (i.e. a number) which labels the $i$-th edge of the randomly produced play (recall here that we index edges from 0).

Depending on the concrete quantitative objective and on the shape of $\sigma$, the path-and-step-based payoffs from a given vertex might or might not be equal. Nevertheless, in this chapter we study only objectives for which these two semantics yield the *same optimization criteria*: no matter which of the two semantics we use, the optimal values will be the same and strategy that is optimal w.r.t. one of the semantics is also optimal for the other one. Hence, we will fix the play-based approach as the default one, writing just $\text{Payoff}_f(v, \sigma)$ instead of $\text{p-Payoff}_f(v, \sigma)$. We will prove the equivalence with step-based payoff where necessary. Also, we will drop the subscript $f$ when the payoff function is known from the context.

**Optimal strategies and decision problems** Let us fix an MDP $\mathcal{M}$ and an objective given by a random variable $f$. The value of a vertex $v \in V$ is the number $\text{val}(v) = \sup_\sigma \text{Payoff}_f(v, \sigma)$. We let $\text{val}(\mathcal{M})$ denote the $|V|$-dimensional vector whose component indexed by $v$ equals $\text{val}(v)$.

We say that a strategy $\sigma$ is $\varepsilon$-optimal in $v$, for some $\varepsilon \ge 0$, if $\text{Payoff}_f(v, \sigma) \ge \text{val}(v) - \varepsilon$. A 0-optimal strategy is simply called optimal.

For qualitative objectives, there are additional modes of objective satisfaction. Given such an objective $\Omega$, we say that a strategy $\sigma$ is *almost-surely winning* from $v$ if $\mathbb{E}_{\mathcal{M},v}^\sigma[\mathbf{1}_\Omega] = 1$, i.e. if the run produced by $\sigma$ falls into $\Omega$ with probability 1. We also say that $\sigma$ is *positively winning* from $v$ if $\mathbb{E}_{\mathcal{M},v}^\sigma[\mathbf{1}_\Omega] > 0$. For strategies that are winning in the non-stochastic game sense, i.e. that *cannot* produce a run not belonging to $\Omega$, are usually called *surely winning* to distinguish them from the above concepts. We denote by $W_{>0}(\mathcal{M}, \Omega)$ and $W_1(\mathcal{M}, \Omega)$ the sets of all vertices of $\mathcal{M}$ from which there exists
a positively or almost-surely winning strategy for the objective $\Omega$, respectively.

The problems pertaining to the existence of almost-surely or positively winning strategy are often called qualitative problems in the MDP literature, while the notion quantitative problems covers the general notion of optimizing the expectation of some random variable. We do not use such a nomenclature here so as to avoid confusion with qualitative vs. quantitative objectives as defined in Chapter 1. Instead, we will refer directly to, e.g. ‘almost-sure reachability’ while using the term ‘optimal reachability’ to refer to the expectation-maximization problem.

## 5.1 Positive and almost-sure reachability and safety in MDPs

We start our study of algorithmic problems for MDPs with the reachability objectives: we write Reach(Win) for Win a set of colours. By a small abuse, we also write Win for the set of vertices of colours Win.

**Positive reachability** Analogously to attractor computations in reachability games (cf. Section 2.1), we define a one-step positive probability predecessor operator Pre$_{>0}$ as follows: for $U \subseteq V$ we put

$$ \mathrm{Pre}_{>0}(U) = \{v \in V \mid \exists a \in A, \exists u \in U : \Delta(u \mid v, a) > 0\}. $$

We define an operator $\mathcal{P}_{>0}$ on subsets of vertices: for $X \subseteq V$ we have

$$ \mathcal{P}_{>0}(X) = \mathrm{Win} \cup \mathrm{Pre}_{>0}(X). $$

We note that this operator is monotonic when equipping the powerset of vertices with the inclusion preorder: if $X \subseteq X'$ then $\mathcal{P}_{>0}(X) \subseteq \mathcal{P}_{>0}(X')$. Hence Theorem 4 applies: this operator has a least fixed point computed by the following sequence: we let $X_0 = \emptyset$ and $X_i = \mathcal{P}_{>0}(X_{i-1})$. This constructs a sequence $(X_i)_{i \in \mathbb{N}}$ of non-decreasing subsets of $V$. Considering the graph induced by the MDP, it is see to see that $X_i$ is the set of vertices from which a vertex of Win is reachable via a finite play of length at most $i-1$. Hence the sequence stabilises after at most $n-1$ steps.

We have the following simple characterization of the positively winning set:

**Theorem 53 (Characterisation of the positively winning set).** Let $\mathcal{M}$ an MDP. Then the positively winning region $W_{>0}(\mathcal{M}, \mathrm{Reach}(\mathrm{Win}))$ is the least fixed point of the operator $\mathcal{P}_{>0}$. Consequently, a vertex $v$ belongs to $W_{>0}(\mathcal{M}, \mathrm{Reach}(\mathrm{Win}))$ if and only if there exists a (possibly empty) finite play from $v$ to a vertex of colour Win. Moreover, there exists a uniform memoryless deterministic strategy that is positively winning from every vertex in $W_{>0}(\mathcal{M}, \mathrm{Reach}(\mathrm{Win}))$.

*Proof.* Let us write $X_0 = \emptyset$ and $X_{i+1} = \mathcal{P}_{>0}(X_i)$, thanks to Theorem 4 this sequence of subsets of states converges to the least fixed point $X_\infty$ of $\mathcal{P}_{>0}$. Since it is non-decreasing, the sequence is stationary and is reached after at most $n$ iterations, meaning $X_n = X_\infty$. To simplify notations let us write $W_{>0} = W_{>0}(\mathcal{M}, \mathrm{Reach}(\mathrm{Win}))$. We show two properties:
* For all $i$, we have $X_i \subseteq W_{>0}$.

* $W_{>0}$ is a pre-fixed point of $\mathcal{P}_{>0}$.

The first property implies that $X_\infty \subseteq W_{>0}$, and the second the converse implication.

We prove the first property by induction on $i$. The case $i=0$ is clear. Let $v \in X_{i+1}$, either $v \in \text{Win}$ and then it is in $W_{>0}$, or $v$ in $\text{Pre}_{>0}(X_i)$. Choosing the action witnessing that inclusion yields a positive probability to land in $X_i$. By induction hypothesis, $X_i \subseteq W_{>0}$. Hence we have constructed a strategy winning positively from $v$, implying that $v \in W_{>0}$.

We now prove the second property: $W_{>0} \subseteq \text{Win} \cup \text{Pre}_{>0}(W_{>0})$. Let $v \in W_{>0}$, by definition either $v \in \text{Win}$ or there exists an action which yields a positive probability of winning, implying that $v \in \text{Pre}_{>0}(W_{>0})$.

So far we have proved that $W_{>0}$ is the least fixed point of $\mathcal{P}_{>0}$. We conclude the proof by constructing a memoryless deterministic strategy $\sigma$ positively winning from all of $W_{>0}$. For a vertex $v \in W_{>0}$, let $\text{rank}(v)$ be the smallest $i$ such that $v \in X_i$. For each $v \in W_{>0}$, either $v \in \text{Win}$ or there exists an action $a$ and vertex $u$ such that $\Delta(u|v,a) > 0$ and $\text{rank}(u) < \text{rank}(v)$. Define $\sigma(v) = a$. A simple induction on the rank shows that $\sigma$ is positively winning from every vertex of $W_{>0}$. $\square$

As for complexity, we can focus on the problem of determining whether a given vertex belongs to $W_{>0}(\mathcal{M}, \text{Reach}(\text{Win}))$.

**Corollary 12 (Complexity of deciding positive reachability).** *The problem of deciding whether a given vertex of a given MDP belongs to $W_{>0}(\mathcal{M}, \text{Reach}(\text{Win}))$ is NL-complete. Moreover, the set $W_{>0}(\mathcal{M}, \text{Reach}(\text{Win}))$ can be computed in linear time.*

*Proof.* Theorem 53 gives a blueprint for a logspace reduction from this problem to the $s$-$t$-connectivity problem for directed graphs, and vice versa. The latter problem is well known to be NL-complete [Sav70]. Moreover, the set of states from which a target colour is reachable can be computed by a simple graph search (e.g. by BFS), hence in linear time. $\square$

**Almost-sure safety** We define the almost-sure predecessor operator $\text{Pre}_{=1}$: for $X \subseteq V$ we have

$$ \text{Pre}_{=1}(X) = \{v \in V \mid \exists a \in A, \forall t \in V : \Delta(t \mid v, a) > 0 \Rightarrow t \in X\}. $$

It is clearly monotonic: if $X \subseteq X'$, then $\text{Pre}_{=1}(X) \subseteq \text{Pre}_{=1}(X')$. One might be tempted to mimic the positive reachability case in order to solve the almost-sure reachability case: compute the least fixed point of the monotonic $X \mapsto \text{Win} \cup \text{Pre}_{=1}(X)$ and hope that it yields $W_{=1}(\mathcal{M}, \text{Reach}(\text{Win}))$. But this is not correct: consider an MDP with two vertices, $u, v$, the latter one being coloured by Win. We have only one action $a$: in $v$, the action self loops on $v$, while in $u$ playing the action either moves us to $v$ or leaves us in $u$, both options having probability $\frac{1}{2}$. The probability that we never reach $v$ from $u$ is equal to $\lim_{n \to \infty} (\frac{1}{2})^n = 0$, and hence $W_{=1}(\mathcal{M}, \text{Reach}(\text{Win})) = \{u, v\}$. However, the least fixed of the operator above is $\{v\}$, excluding $u$. Note that there indeed exists
an infinite play which can be generated by the strategy and which never visits $v$, but the probability of generating such a play is 0.

Let us define the operator $P_{=1}$ on subsets of vertices: for $X \subseteq V$ we have

$$P_{=1}(X) = \mathrm{Win} \cap \mathrm{Pre}_{=1}(X).$$

Clearly $P_{=1}$ is monotonic.

**Lemma 49** (Characterization of the almost-sure safety winning region). Let $\mathcal{M}$ an MDP. Then the almost-sure safety winning region $W_{=1}(\mathcal{M}, \mathrm{Safe}(\mathrm{Win}))$ is the greatest fixed point of the operator $P_{=1}$. Moreover, there exists a memoryless deterministic strategy that is almost-surely winning from every vertex of $W_{=1}(\mathcal{M}, \mathrm{Safe}(\mathrm{Win}))$.

*Proof.* Let us write $X_0 = V$ and $X_{i+1} = P_{=1}(X_i)$, thanks to Theorem 4 this sequence of subsets of states converges to the greatest fixed point $X_\infty$ of $P_{=1}$. Since it is non-increasing, the sequence is stationary and is reached after at most $n$ iterations, meaning $X_n = X_\infty$. To simplify notations let us write $W_{=1} = W_{=1}(\mathcal{M}, \mathrm{Safe}(\mathrm{Win}))$. We show two properties:

* For all $i$, we have $W_{=1} \subseteq X_i$.

* $W_{=1}$ is a post-fixed point of $P_{=1}$.

The first property implies that $W_{=1} \subseteq X_\infty$, and the second the converse implication.

We prove the first property by induction on $i$. The case $i=0$ is clear. Let $v \in W_{=1}$. Clearly we must have that $v \in \mathrm{Win}$. Since $v \in W_{=1}$, there exists an action ensuring to stay in $W_{=1}$ with probability 1. By induction hypothesis $v \in X_i$, so this implies that $v \in P_{=1}(X_i)$.

We now prove the second property: $W_{=1} \supseteq \mathrm{Win} \cap \mathrm{Pre}_{=1}(W_{=1})$. Let $v \in \mathrm{Win} \cap \mathrm{Pre}_{=1}(W_{=1})$, there exists an action ensuring to win with probability 1, implying that $v \in W_{=1}$.

So far we have proved that $W_{=1}$ is the greatest fixed point of $P_{=1}$. We conclude the proof by constructing a memoryless deterministic strategy $\sigma$ almost-surely winning from all of $W_{=1}$. For a vertex $v \in W_{=1}$, there exists an action $a$ such that if $\Delta(u|v, a) > 0$ then $u \in W_{=1}$. Define $\sigma(v) = a$. Clearly $\sigma$ is almost-surely winning from every vertex of $W_{=1}$. $\square$

<caption>**Algorithm 5.1:** An algorithm computing $W_{=1}(\mathcal{M}, \mathrm{Safe}(\mathrm{Win}))$</caption>

**Data:** An MDP $\mathcal{M}$, a colour $\mathrm{Win}$
$X \leftarrow V$;
**repeat**
| $X' \leftarrow X$;
| $X \leftarrow \mathrm{Win} \cap \mathrm{Pre}_{=1}(X)$
**until** $X' = X$;
**return** $X$
**Corollary 13 (Complexity of the almost-sure safety winning set).** The problem of deciding whether a given vertex of a given MDP belongs to $W_{=1}(\mathcal{M}, \text{Safe}(\text{Win}))$ can be solved in strongly polynomial time, together with a memoryless deterministic strategy which is almost-surely winning for all vertices in $W_{>0}(\mathcal{M}, \text{Safe}(\text{Win}))$.

Algorithm 5.1 computes the set $W_{=1}(\mathcal{M}, \text{Safe}(\text{Win}))$ in strongly polynomial time.

*Proof.* The algorithm makes at most linearly many iterations, each of which has at most linear complexity. Hence, the complexity is at most quadratic. The strong polynomiality is testified by the fact that the algorithm only tests whether a probability of a given transition is positive or not, and the exact values of positive probabilities are irrelevant. □

**Almost-sure reachability** With almost-sure safety solved, we can now solve almost-sure reachability. Consider the one-step almost-sure safety operator $\text{Safe}_{=1}$ acting on sets of vertices:

$$ \text{Safe}_{=1}(X) = X \cap \text{Pre}_{=1}(X). $$

This operator gives rise to the notion of a closed set, which is important for the study of safety objectives in MDPs.

**Definition 10 (Closed set in an MDP).** A set $X$ of vertices is closed if $\text{Safe}_{=1}(X) = X$. The sub-MDP of an MDP $\mathcal{M}$ induced by the closed subset $X$ is the MDP $\mathcal{M}_X = (X, E_X, \Delta_X, c_X)$ defined as follows:

* $E_X$ is obtained from $E$ by removing edges incident to a vertex from $V \setminus X$;

* $\Delta_X$ is obtained from $\Delta \subseteq V \times A \times \mathcal{D}(E)$ by removing all triples $(v, a, f)$ where either $v \notin X$ or where the support of $f$ is not contained in $X$;

* $c_X$ is a restriction of $c$ to $X$.

We denote by $\text{Cl}(\mathcal{M})$ the set of all closed sets in $\mathcal{M}$.

One can show that a set is closed if Max has a strategy ensuring that she stays in the set forever.

**Algorithm 5.2: An algorithm computing $W_{=1}(\mathcal{M}, \text{Reach}(\text{Win}))$**

**Data:** An MDP $\mathcal{M}$, a colour Win

W $\leftarrow$ V repeat

| W' $\leftarrow$ W Z $\leftarrow$ W$_{>0}(\mathcal{M}_W, \text{Reach}(\text{Win}))$ W $\leftarrow$ W$_{=1}(\mathcal{M}_W, \text{Safe}(W \setminus Z))$

until W' $\neq$ W;

return W; // A positive winning strategy in $\mathcal{M}_W$ is now almost-surely winning from W in $\mathcal{M}$.

The pseudocode for solving almost sure reachability is given in Algorithm 5.2. Note that in the first iteration, the algorithm computes the set $W_{=1}(\mathcal{M}, \text{Safe}(Z))$ where
$Z = W_{>0}(\mathcal{M}, \text{Reach}(\text{Win}))$. We might be tempted to think that this set already equals $W_1(\mathcal{M}, \text{Reach}(\text{Win}))$, but this is not the case. To see this, consider an MDP with three states $u, v, t$ and two actions $a, b$ such that $t$ is coloured by Win, both actions self loop in $v$ and $t$, and $\Delta(t|u, a) = \Delta(v|u, a) = \frac{1}{2}$ while $\Delta(u|u, b) = 1$. Then $W_1(\mathcal{M}, \text{Reach}(\text{Win})) = \{t\}$, but $W_1(\mathcal{M}, \text{Safe}(W_{>0}(\mathcal{M}, \text{Reach}(\text{Win})))) = \{u, t\}$. However, iterating the computation works, as shown in the following theorem.

**Theorem 54** (Algorithm for the almost-sure reachability winning set). *The problem of deciding whether a given vertex of a given MDP belongs to $W_1(\mathcal{M}, \text{Reach}(\text{Win}))$ can be solved in strongly polynomial time, together with a memoryless deterministic strategy which is almost-surely winning for all vertices in $W_{>0}(\mathcal{M}, \text{Reach}(\text{Win}))$.*

The pseudocode is given in Algorithm 5.2.

*Proof.* Since the set $W$ can only decrease in each iteration, the algorithm terminates. We prove that upon termination, $W$ equals $W_1(\mathcal{M}, \text{Reach}(\text{Win}))$.

We start with the $\subseteq$ direction. We have $W \subseteq W_{>0}(\mathcal{M}_W, \text{Reach}(\text{Win}))$. By Theorem 53 there exists an MD strategy $\sigma$ in $\mathcal{M}_W$ which is positively winning from each vertex of $W$. We show that the same strategy is also almost-surely winning from each vertex of $W$ in $\mathcal{M}_W$ and thus also from each vertex of $W$ in $\mathcal{M}$, which also proves the second part of the theorem. Let $v$ be any vertex of $W$ and denote $|W|$ by $\ell$. Since $\sigma$ is memoryless, it guarantees that a vertex of Win is reached with a positive probability in at most $\ell$ steps (see also the construction of $\sigma$ in the proof of Theorem 53), and since it is also deterministic, it guarantees that the probability $p$ of reaching Win in at most $\ell$ steps is at least $p_{\min}^{\ell}$, where $p_{\min}$ is the smallest non-zero edge probability in $\mathcal{M}_W$. Now imagine that $\ell$ steps have elapsed and we have not yet reached Win. This happens with a probability at most $(1-p_{\min}^{\ell})$. However, even after these $\ell$ steps we are still in $W$, since $\sigma$ is a strategy in $\mathcal{M}_W$. Hence, the probability that we do not reach Win within the first $2\ell$ steps is bounded by $(1-p_{\min}^{\ell})^2$. To realize why this is the case, note that any finite play $\pi$ of length $2\ell$ can be split into two halves, $\pi'$, $\pi''$ of length $\ell$, and then $\mathbb{P}_v^{\sigma}(\text{Cyl}(\pi)) = \mathbb{P}_v^{\sigma}(\text{Cyl}(\pi')) \cdot \mathbb{P}_{\text{last}(\pi')}^{\sigma}(\text{Cyl}(\pi''))$ (here we use the fact that $\sigma$ is memoryless). Using this and some arithmetic, one can show that, denoting $\text{Avoid}_i$ the set of all plays that avoid the vertices of Win in steps $\ell \cdot (i-1)$ to $\ell \cdot (i) - 1$, it holds

$$ \mathbb{P}_v^{\sigma}(\text{Avoid}_1 \cap \text{Avoid}_2) \le \mathbb{P}_v^{\sigma}(\text{Avoid}_1) \cdot \max_{u \in W \setminus \text{Win}} \mathbb{P}_u^{\sigma}(\text{Avoid}_1) \le (1-p_{\min}^{\ell})^2. $$

One can then continue by induction to show that $\mathbb{P}_v^{\sigma}(\bigcap_{i=1}^j \text{Avoid}_i) \le (1-p_{\min}^{\ell})^j$, and hence

$$ \mathbb{P}_v^{\sigma}(\text{Reach}(\text{Win})) = 1 - \mathbb{P}_v^{\sigma}(\bigcap_{i=1}^{\infty} \text{Avoid}_i) \le 1 - \lim_{j \to \infty} (1-p_{\min}^{\ell})^j = 1 - 0 = 1. $$

Now we prove the $\supseteq$ direction. Denote $X = W_1(\mathcal{M}, \text{Reach}(\text{Win}))$. We prove that $W \supseteq X$ is an invariant of the iteration. Initially this is clear. Now assume that this holds before an iteration takes place. It is easy to check that $X$ is closed, so $\mathcal{M}_X$ is well-defined. We prove that $X \subseteq W_1(\mathcal{M}_W, \text{Safe}(W \setminus Z))$, where $Z$ is defined during the iteration. A strategy in $\mathcal{M}$ that reaches Win with probability 1 must never
## 5.1. POSITIVE AND ALMOST-SURE REACHABILITY AND SAFETY IN MDPS187

visit a vertex from $V \setminus X$ with a positive probability. Hence, each such strategy can be viewed also as a strategy in $\mathcal{M}_X$. It follows that $X = W_{=1}(\mathcal{M}_X, \text{Reach}(\text{Win})) = W_{>0}(\mathcal{M}_X, \text{Reach}(\text{Win})) \subseteq W_{>0}(\mathcal{M}_W, \text{Reach}(\text{Win})) = Z$, the middle inclusion following from induction hypothesis. Now by Lemma 49 and Corollary 13, we have that the set $W_{=1}(\mathcal{M}_W, \text{Safe}(W \setminus Z))$ is the largest closed set contained in $Z$. But $X$ is also closed, and as shown above, it is contained in $Z$. Hence, $X \subseteq W_{=1}(\mathcal{M}_W, \text{Safe}(W \setminus Z))$.

The complexity follows from Corollary 12 and Corollary 13; and also from the fact that the main loop must terminate in $\le |V|$ steps. The strong polynomiality again follows from the algorithm being oblivious to precise probabilities. □

We also have a complementary hardness result.

**Theorem 55 (Complexity of the almost-sure reachability winning set).** *The problem of determining whether a given vertex of a given MDP belongs to $W_{=1}(\mathcal{M}, \text{Reach}(\text{Win}))$ is P-complete.*

*Proof.* We proceed by a reduction from the circuit value problem (CVP). An instance of CVP is a directed acyclic graph $\mathcal{C}$, representing a boolean circuit: each internal node represents either an OR gate or an AND gate, while each leaf node is labelled by true or false. Each internal node is guaranteed to have exactly two children. Each node of $\mathcal{C}$ evaluates to a unique truth value: the value of a leaf is given by its label and the value of an internal node $v$ is given by applying the logical operator corresponding to the node to the truth values of the two children of $v$, the evaluation proceeding in a backward topological order. The task is to decide whether a given node $w$ of $\mathcal{C}$ evaluates to true. CVP was shown to be P-hard (under logspace reductions) in [Lad75]. In [CDH10a], the following logspace reduction from CVP to almost-sure reachability in MDPs is presented: given a boolean circuit $\mathcal{C}$, construct an MDP $\mathcal{M}_\mathcal{C}$ whose vertices correspond to the gates of $\mathcal{C}$. There are two actions, call them left and right. In each vertex corresponding to an OR gate $g$, the left action transitions with probability 1 to the vertex representing the left child of $g$, and similarly for the action right and the right child. In a vertex corresponding to an AND gate $g$, both actions behave the same: the transition into each of the two children of $g$ with probability $\frac{1}{2}$. Vertices corresponding to leafs have self loop as the only outgoing edges, and moreover, they are coloured with the respective labels in $\mathcal{C}$. It is easy to check that a gate of $\mathcal{C}$ evaluates to true if and only if the corresponding vertex belongs to $W_{=1}(\mathcal{M}_\mathcal{C}, \text{Reach}(\text{true}))$. □

**Positive safety** We conclude this section by a discussion of positive safety.

**Theorem 56 (Algorithm for the positive safety winning set).** Let $\mathcal{M}_{\bar{W}_{in}}$ be an MDP obtained from $\mathcal{M}$ by changing all Win-coloured vertices to sinks (i.e. all actions in these vertices are self loops). Then

$$W_{>0}(\mathcal{M}, \text{Safe}(\text{Win})) = W_{>0}(\mathcal{M}_{\bar{W}_{in}}, \text{Reach}(W_{=1}(\mathcal{M}_{\bar{W}_{in}}, \text{Safe}(\text{Win}))))$$

In particular, the set $W_{>0}(\mathcal{M}, \text{Safe}(\text{Win}))$ can be computed in a strongly polynomial time and there exists a memoryless deterministic strategy, computable in strongly polynomial time, that is positively winning from every vertex of $W_{>0}(\mathcal{M}, \text{Safe}(\text{Win}))$.
*Proof.* Clearly $W_{>0}(\mathcal{M}, \text{Safe}(\text{Win})) = W_{>0}(\mathcal{M}_{\text{Win}}, \text{Safe}(\text{Win}))$ and $W_{=1}(\mathcal{M}, \text{Safe}(\text{Win})) = W_{=1}(\mathcal{M}_{\text{Win}}, \text{Safe}(\text{Win}))$; and moreover the corresponding winning strategies easily transfer between the two MDPs (for a safety objective, the behaviour after visiting a Win-coloured state is inconsequential). Hence, putting $Z = W_{=1}(\mathcal{M}_{\text{Win}}, \text{Safe}(\text{Win}))$, it is sufficient to show that $W_{>0}(\mathcal{M}_{\text{Win}}, \text{Safe}(\text{Win})) = W_{>0}(\mathcal{M}_{\text{Win}}, \text{Reach}(Z))$

The $\supseteq$ inclusion is clear as well as the construction of the witnessing MD strategy (in the vertices of that are outside of Z, we behave as the positively winning MD strategy for reaching Z, while inside Z we behave as the almost-sure winning strategy for Safe(Win)).

For the other inclusion, let $X = V \setminus W_{>0}(\mathcal{M}_{\text{Win}}, \text{Reach}(Z))$. We prove that $X \subseteq V \setminus W_{>0}(\mathcal{M}_{\text{Win}}, \text{Safe}(\text{Win}))$. Assign ranks to vertices inductively as follows: each vertex coloured by Win gets rank 0. Now if ranks $\le i$ have been already assigned, then a vertex $v$ is assigned rank $i+1$ if it does not already have a lower rank but for all actions $a \in A$ there exists a vertex $u$ of rank $\le i$ s.t. $\Delta(u | v, a) > 0$. Then each vertex in $X$ is assigned a finite rank: indeed, the set of vertices without a rank is closed and does not contain Win-coloured vertices, hence it is contained in Z. Now fix any strategy $\sigma$ starting in a vertex $v \in X$. By definition of $X$, $\sigma$ never reaches Z and hence never visits an unranked state. At the same time, whenever $\sigma$ is in a ranked state, there is, by definition of ranks, a probability at least $p_{\min}$ (the minimal edge probability in $\mathcal{M}$) of transitioning to a lower-ranked state in the next step. Hence, in every moment, the probability of $\sigma$ reaching a Win-coloured state within the next $|V|$ steps is at least $p_{\min}^{|V|}$. By a straightforward adaptation of the second part of the proof of Theorem 54, $\sigma$ eventually visits Win with probability 1. Since $\sigma$ was arbitrary, this shows that $v \notin W_{>0}(\mathcal{M}_{\text{Win}}, \text{Safe}(\text{Win}))$.

The complexity follows from the results on positive reachability and almost-sure safety. $\square$

## 5.2 Discounted payoff in MDPs

In this section, we consider MDPs with edges coloured by rational numbers and with the objective DiscountedPayoff. We start the chapter by proving that using the play-based semantics for the discounted payoff objective yields no loss of generality.

**Lemma 50 (Equivalence of the definitions for discounted payoffs).** In a discounted payoff MDP, for each strategy $\sigma$ and each vertex $v$ we have

$$p\text{-Payoff}(v, \sigma) = s\text{-Payoff}(v, \sigma).$$

*Proof.* We have

$$ \begin{align*} \text{p-Payoff}(v, \sigma) &= \mathbb{E}_{v}^{\sigma}[(1-\lambda) \lim_{k \to \infty} \sum_{i=0}^{k-1} \lambda^{i} c(\pi_{i})] = (1-\lambda) \lim_{k \to \infty} \mathbb{E}_{v}^{\sigma}[\sum_{i=0}^{k-1} \lambda^{i} c(\pi_{i})] \\ &= (1-\lambda) \lim_{k \to \infty} \sum_{i=0}^{k-1} \lambda^{i} \mathbb{E}_{v}^{\sigma}[c(\pi_{i})] = \text{s-Payoff}(v, \sigma). \end{align*} $$
Here, the last equality on the first line follows from the dominated convergence theorem [ADD00, Theorem 1.6.9] and the following equality comes from the linearity of expectation. (To apply the domination convergence theorem, we use the fact that for each $k$ we have $\text{DiscountedPayoff}^k(\pi) \le \max_c$.) $\square$

Optimal values and memoryless optimality

In this subsection we give a characterization of the value vector $\text{val}(\mathcal{M})$ and prove that there always exists a memoryless deterministic strategy that is optimal in every vertex. Our exposition follows (in a condensed form) the one in [Put05], the techniques being somewhat similar to the ones in the previous chapter.

We define an operator $\mathcal{O}: \mathbb{R}^V \to \mathbb{R}^V$ as follows: each vector $\vec{x}$ is mapped to a vector $\vec{y} = \mathcal{O}(\vec{x})$ such that:

$$ \vec{y}_v = \max_{a \in A} \sum_{u \in V} \Delta(u | v, a) \cdot ((1 - \lambda) \cdot c(v, u) + \lambda \cdot \vec{x}_u). $$

**Lemma 51 (Contraction mapping).** *The operator $\mathcal{O}$ is a contraction mapping. Hence, $\mathcal{O}$ has a unique fixed point $\vec{x}^*$ in $\mathbb{R}^V$, and $\vec{x}^* = \lim_{k \to \infty} \mathcal{O}^k(\vec{x})$, for any $\vec{x} \in \mathbb{R}^V$.*

*Proof.* The proof proceeds by a computation analogous to the one in the first half of the proof of Lemma 38; we just need to reason about actions rather than edges (and of course, use the formula defining $\mathcal{O}$ instead of the one for games). The second part follows from the Banach fixed point theorem. $\square$

We aim to prove that $\text{val}(\mathcal{M})$ is the unique fixed point $\vec{x}^*$ of $\mathcal{O}$. We start with an auxiliary definition.

**Definition 11 (Safe actions).** Let $\vec{x} \in \mathbb{R}^V$. We say that an action $a$ is $\vec{x}$-safe in a vertex $v$ if

$$ a = \arg\max_{a' \in A} \sum_{u \in V} \Delta(u | v, a') \cdot ((1 - \lambda) \cdot c(v, u) + \lambda \cdot \vec{x}_u). \quad (5.1) $$

A strategy $\sigma$ is $\vec{x}$-safe, if for each play $\pi$ ending in a vertex $v$, all actions that are selected with a positive probability by $\sigma$ for $\pi$ are $\vec{x}$-safe in $v$.

Given a strategy $\sigma$ we define $\vec{x}^\sigma$ to be the vector such that $\vec{x}_v^\sigma = \text{p-Payoff}(v, \sigma)$. For memoryless strategies, $\vec{x}^\sigma$ can be computed efficiently as follows: Each memoryless strategy $\sigma$ defines a linear operator $\mathcal{O}^\sigma$ which maps each vector $\vec{x} \in \mathbb{R}^V$ to a vector $\vec{y} = \mathcal{O}^\sigma(\vec{x})$ such that

$$ \vec{y}_v = \sum_{a \in A} \sigma(a | v) \cdot \left( \sum_{u \in V} \Delta(u | v, a) \cdot ((1 - \lambda) \cdot c(v, u) + \lambda \cdot \vec{x}_u) \right). $$

**Lemma 52 (Operator using a fixed strategy).** Let $\sigma$ be a memoryless strategy using rational probabilities. Then the operator $\mathcal{O}^\sigma$ has a unique fixed point, which is equal to $\vec{x}^\sigma$ and which can be computed in polynomial time.
*Proof.* The operator $\mathcal{O}^{\sigma}$ can be seen as an instantiation of $\mathcal{O}$ in an MDP where there is no choice, since the action probabilities are chosen according to $\sigma$. Lemma 51 shows that $\bar{x}^{\sigma}$ is a fixed point of $\mathcal{O}^{\sigma}$. Since $\mathcal{O}^{\sigma}$ is again a contraction, it has a unique fixed point; and since it is linear, the fixed point can be computed in polynomial time, e.g. by Gaussian elimination (in its polynomial bit-complexity variant known as Bareiss algorithm [Bar68]). $\square$

We now prove that there is a memoryless strategy ensuring outcome given by the fixed point of $\mathcal{O}$. Hence, the fixed point gives a lower bound on the values of vertices.

**Lemma 53** (Any fixed point induces an MD strategy). Let $\bar{x}^*$ be the unique fixed point of $\mathcal{O}$. Then there exists an MD strategy that is $\bar{x}^*$-safe. Moreover, for each $\bar{x}^*$-safe memoryless strategy it holds that $p$-Payoff$(v, \sigma) = \bar{x}_v^*$ for each $v \in V$.

*Proof.* Note that for each $\bar{x} \in \mathbb{R}^V$ and each $v \in V$ there always exists at least one action that is $\bar{x}$-safe in $v$. Hence, there is a memoryless deterministic strategy which in each $v$ chooses an arbitrary (but fixed) action that is $\bar{x}^*$-safe in $v$.

Now let $\sigma$ be an arbitrary $\bar{x}^*$-safe memoryless strategy. By Lemma 52, the vector $\bar{x}^{\sigma}$ is the unique fixed point of $\mathcal{O}^{\sigma}$. But since $\sigma$ is $\bar{x}^*$-safe, $\bar{x}^*$ is also a fixed point of $\mathcal{O}^{\sigma}$. Hence, $\bar{x}^* = \bar{x}^{\sigma}$. $\square$

It remains to prove that $\bar{x}^*$ gives, for each vertex, an upper bound on the expected discounted payoff achievable by any strategy from that vertex. We introduce some additional notation to be used in the proof of the next lemma, as well as in some later results: namely, we denote by DiscountedPayoff$^{(k)}(\pi)$ the discounted payoff accumulated during the first $k$ steps of $\pi$, i.e. the number $(1 - \lambda) \sum_{i=0}^{k-1} \lambda^i c(\pi_i)$. The following lemma can be proved by an easy induction.

**Lemma 54** (Properties of the sequence of iterates). For each $k \ge 0$ and each vertex $v$ we have

$$ \sup_{\sigma} \mathbb{E}_{v}^{\sigma}[\text{DiscountedPayoff}^{(k)}] = (\mathcal{O}^{k}(\vec{0}))_{v} $$

(here $\vec{0}$ is a $|V|$-dimensional vector of zeroes).

The previous lemma is used to prove the required upper bound on $\text{val}(v)$.

**Lemma 55** (Upper bound on the optimal value). For each vertex $v$ it holds $\text{val}(v) \le \bar{x}_v^*$, where $\bar{x}^*$ is the unique fixed point of $\mathcal{O}$.

*Proof.* We have DiscountedPayoff$(\pi) = \lim_{k \to \infty} \text{DiscountedPayoff}^{(k)}(\pi)$ (for each $\pi$) and hence, by dominated convergence theorem we have $\mathbb{E}_{v}^{\sigma}[\text{DiscountedPayoff}] = \lim_{k \to \infty} \mathbb{E}_{v}^{\sigma}[\text{DiscountedPayoff}^{(k)}]$. Hence,

$$ \begin{aligned} \text{val}(v) &= \sup_{\sigma} \mathbb{E}_{v}^{\sigma}[\text{DiscountedPayoff}] \\ &= \sup_{\sigma} \lim_{k \to \infty} \mathbb{E}_{v}^{\sigma}[\text{DiscountedPayoff}^{(k)}] \end{aligned} \qquad (5.2) $$

It remains to prove that the RHS of Equation (5.2) is not greater than $\bar{x}^* = \lim_{k \to \infty} \mathcal{O}^k(\vec{0}) = \lim_{k \to \infty} \sup_{\sigma} \mathbb{E}_{v}^{\sigma}[\text{DiscountedPayoff}^{(k)}]$ (the last inequality follows by Lemma 54).
It suffices to show that for each $\sigma'$ we have $\lim_{k \to \infty} \mathbb{E}_{\sigma'}^{\sigma'} \text{DiscountedPayoff}^{(k)}] \le \lim_{k \to \infty} \sup_{\sigma} \mathbb{E}_{\sigma'}^{\sigma'} [\text{DiscountedPayoff}^{(k)}]$. But this immediately follows from the fact that the inequality holds for each concrete $k$. $\square$

The following theorem summarizes the results.

**Theorem 57** (Characterisation of the optimal values). *The vector of values $\text{val}(\mathcal{M})$ in a discounted sum MDP $\mathcal{M}$ is the unique fixed point $\vec{x}^*$ of the operator $\mathcal{O}$. Moreover, there exists a memoryless deterministic strategy that is optimal in every vertex.*

*Proof.* The characterisation of $\text{val}(\mathcal{M})$ follows directly from Lemmata 53 and 55. The MD optimality follows from Lemma 53. $\square$

In the rest of this section we discuss several algorithms for computing the values and optimal strategies in discounted payoff MDPs.

## Value iteration

The value iteration algorithm works in the same way as in the case of discounted payoff games: we simply iterate the operator $\mathcal{O}$. We know that $\text{val}(\mathcal{M}) = \lim_{k \to \infty} \mathcal{O}^k(\vec{0})$, and hence, iterating $\mathcal{O}$ yields an approximation of $\text{val}(\mathcal{M})$. The iteration might not reach the fixed point (i.e. $\text{val}(\mathcal{M})$) in a finite number of steps, but we can provide simple bounds on the precision of the approximation.

**Lemma 56** (Properties of the iterates). *For each $k \in \mathbb{N}$, $\|\text{val}(\mathcal{M}) - \mathcal{O}^k(\vec{0})\|_{\infty} \le \lambda^k \max_c$.

*Proof.* This follows immediately from Lemma 54 and from the fact that for each play $\pi$, $\sum_{i=k}^{\infty} \lambda^i \cdot c(\pi_i) \le \frac{1}{1-\lambda} \cdot \lambda^k \max_c$. $\square$

Similar analysis can be applied to strategies induced by the approximate vectors.

**Lemma 57** (Relating iterates and optimal strategies). *Let $\varepsilon > 0$ be arbitrary and let*

$$k(\varepsilon) = \left\lfloor \frac{\log_2 \left( \frac{\varepsilon(1-\lambda)}{4\max_c} \right)}{\log_2(\lambda)} \right\rfloor.$$

Then, every $\mathcal{O}^{k(\varepsilon)}(\vec{0})$-safe memoryless strategy is $\varepsilon$-optimal in every vertex.

*Proof.* Let $\sigma$ be any $\mathcal{O}^{k(\varepsilon)}(\vec{0})$-safe memoryless strategy and let $\mathcal{O}^{\sigma}$ be the corresponding operator. We have that

$$\begin{aligned} \|\text{val}(\mathcal{M}) - \vec{x}^{\sigma}\|_{\infty} &= \|\text{val}(\mathcal{M}) - \mathcal{O}^{k(\varepsilon)}(\vec{0}) + \mathcal{O}^{k(\varepsilon)}(\vec{0}) - \vec{x}^{\sigma}\|_{\infty} \\ &\le \|\text{val}(\mathcal{M}) - \mathcal{O}^{k(\varepsilon)}(\vec{0})\|_{\infty} + \|\mathcal{O}^{k(\varepsilon)}(\vec{0}) - \vec{x}^{\sigma}\|_{\infty}. \end{aligned} \quad (5.3)$$

The first term in Equation (5.3) is $\le \varepsilon/2$ by the choice of $k(\varepsilon)$ and Lemma 56. We prove that the second term in Equation (5.3) is also bounded by $\varepsilon/2$. Note that we have
$\vec{x}^{\sigma} = \mathcal{O}^{\sigma}(\vec{x}^{\sigma})$ (as was already proved in Lemma 53) and $\mathcal{O}(\mathcal{O}^{k(\varepsilon)}(\vec{0})) = \mathcal{O}^{\sigma}(\mathcal{O}^{k(\varepsilon)}(\vec{0}))$ (since $\sigma$ is $\mathcal{O}^{k(\varepsilon)}(\vec{0})$-safe). Using this we get

$$
\begin{align*}
\| \mathcal{O}^{k(\varepsilon)}(\vec{0}) - \vec{x}^{\sigma} \|_{\infty} &= \| \mathcal{O}^{k(\varepsilon)}(\vec{0}) - \mathcal{O}^{k(\varepsilon)+1}(\vec{0}) + \mathcal{O}^{k(\varepsilon)+1}(\vec{0}) - \vec{x}^{\sigma} \|_{\infty} \\
&\le \| \mathcal{O}^{k(\varepsilon)}(\vec{0}) - \mathcal{O}^{k(\varepsilon)+1}(\vec{0}) \|_{\infty} + \| \mathcal{O}^{k(\varepsilon)+1}(\vec{0}) - \vec{x}^{\sigma} \|_{\infty} \\
&= \| \mathcal{O}^{k(\varepsilon)}(\vec{0}) - \mathcal{O}^{k(\varepsilon)+1}(\vec{0}) \|_{\infty} + \| \mathcal{O}^{\sigma}(\mathcal{O}^{k(\varepsilon)}(\vec{0})) - \mathcal{O}^{\sigma}(\vec{x}^{\sigma}) \|_{\infty} \\
&\le \| \mathcal{O}^{k(\varepsilon)}(\vec{0}) - \mathcal{O}^{k(\varepsilon)+1}(\vec{0}) \|_{\infty} + \lambda \cdot \|( \mathcal{O}^{k(\varepsilon)}(\vec{0}) ) - \vec{x}^{\sigma} \|_{\infty}
\end{align*}
$$

Re-arranging yields $\|\mathcal{O}^{k(\varepsilon)}(\vec{0}) - \vec{x}^{\sigma}\|_{\infty} \le \frac{1}{1-\lambda} \cdot \|\mathcal{O}^{k(\varepsilon)}(\vec{0}) - \mathcal{O}^{k(\varepsilon)+1}\|_{\infty}$.

It follows from Lemma 56 that $\|\mathcal{O}^{k(\varepsilon)}(\vec{0}) - \mathcal{O}^{k(\varepsilon)+1}(\vec{0})\|_{\infty} \le 2 \cdot \lambda^{k(\varepsilon)} \max|c| \le \frac{(1-\lambda)\varepsilon}{2}$, the last inequality holding by the choice of $k(\varepsilon)$. Plugging this into the formula above yields $\|\mathcal{O}^{k(\varepsilon)}(\vec{0}) - \vec{x}^{\sigma}\|_{\infty} \le \frac{\varepsilon}{2}$, as required. $\square$

Using a value-gap result (similar to the game case, but proved using a different technique), one can show that sufficiently precise iterates can be used to compute an *optimal* strategy. This is summarized in the following lemma due to [Tse90].

**Lemma 58** (Sufficiently many iterates yield an optimal strategy). *Let $d$ be the least common multiple of denominators of the following numbers: $\lambda$, all transition probabilities, and all edge colourings in $\mathcal{M}$. Next, let $\varepsilon^* = \frac{1}{d^{(3|V|+3) \cdot |V|/2}}$. Then, any $\mathcal{O}^{k(\varepsilon^*)}(\vec{0})$-safe memoryless deterministic strategy is optimal in every vertex.*

*Proof.* Let $\sigma^*$ be any MD optimal strategy (it is guaranteed to exist by Theorem 57). By the same theorem, we have that $\text{val}(\mathcal{M}) = \mathcal{O}^{\sigma}(\text{val}(\mathcal{M}))$. By the definition of $\mathcal{O}^{\sigma}$, we can write the above equation as $\text{val}(\mathcal{M}) = (1-\lambda)\cdot\vec{c} + \lambda \cdot P \cdot \text{val}(\mathcal{M})$, where $\vec{c}$ is a vector whose each component is a sum of several terms, each term being a product of an edge colour and of a transition probability; and $P$ is a matrix containing transition probabilities. Multiplying the equation by $d^3$ yields $d^3 \text{val}(\mathcal{M}) = d^3(1-\lambda)\cdot\vec{c} + d^3 \lambda \cdot P \cdot \text{val}(\mathcal{M})$. Since this equation has a unique fixed point (due to $\mathcal{O}^{\sigma}$ being a contraction), the matrix $A = d^3(I - \lambda P)$ (where $I$ is the unit matrix) is regular, and moreover, composed of integers (ue to the choice of $d$). By Cramer's rule, each entry of $\text{val}(\mathcal{M})$ is equal to $\text{det}(B)/\text{det}(A)$, where $B$ is a matrix obtained by replacing some column of $A$ with $d^3(1-\lambda)\vec{c}$ (which is again an integer vector, due to the multiplication by $d^3$). Hence, each entry of $\text{val}(\mathcal{M})$ is a rational number with denominator $\text{det}(A)$. Hadamard's inequality [Gar07] implies $|\text{det}(A)| \le d^3|V|^{|V|/2}$.

Now let $\sigma$ be any $\mathcal{O}^{k(\varepsilon^*)}(\vec{0})$-safe MD strategy. By Lemma 57, $\sigma$ is $\varepsilon^*$-optimal. We prove that all actions used by $\sigma$ are $\vec{x}^*$-safe, which means that $\sigma$ is optimal by Lemma 53. Assume that in some vertex $v$ the strategy $\sigma$ uses action $a$ that is not $\vec{x}^*$-safe. Denote $\vec{y} = \mathcal{O}^{\sigma}(\vec{x}^*)$. We have $|\vec{y}_v - \vec{x}_v^*| > 0$, since otherwise $a$ would be $\vec{x}^*$-safe. But then we can obtain a lower bound on the difference by investigating the bitsize of the numbers
involved:

$$
\begin{align*}
|\vec{y}_v - \vec{x}_v^*| &= \left| \frac{d^3}{d^3} \vec{y}_v - \frac{d^3}{d^3} \vec{x}_v^* \right| \\
&= \frac{1}{d^3} \left| \sum_{u \in V} \underbrace{d \cdot \Delta(u | v, a)}_{\text{integer}} \cdot \underbrace{(d^2(1-\lambda) \cdot c(u, v))}_{\text{integer}} + \underbrace{d^2 \cdot \lambda \cdot \vec{x}_u^* - d^3 \vec{x}^*}_{\text{int. multiples of } 1/\det(A)} \right| \\
&\geq \frac{1}{d^3 \cdot \det(A)} \geq \frac{1}{d^{(3|V|+3)} \cdot |V|^{\frac{|V|}{2}}}
\end{align*}
$$

Now put $\vec{z} = \mathcal{O}^{\sigma}(\mathcal{O}^{k(\epsilon)}(\vec{0}))$. We have the following (using, on the first line, the fact that $|a+b| \ge |a| - |b|$):

$$
\begin{align*}
|\vec{z}_v - \vec{x}_v^*| &= |\vec{z}_v - \mathcal{O}^{\sigma}(\vec{x}^*)_v + \mathcal{O}^{\sigma}(\vec{x}^*)_v - \vec{x}_v^*| \ge |\mathcal{O}^{\sigma}(\vec{x}^*)_v - \vec{x}_v^*| - |\vec{z}_v - \mathcal{O}^{\sigma}(\vec{x}^*)_v| \\
&\ge \frac{1}{d^{(3|V|+3)} \cdot |V|^{\frac{|V|}{2}}} - |\mathcal{O}^{\sigma}(\mathcal{O}^{k(\epsilon)}(\vec{0}))_v - \mathcal{O}^{\sigma}(\vec{x}^*)_v| \quad \text{(as shown above)} \\
&\ge \frac{1}{d^{(3|V|+3)} \cdot |V|^{\frac{|V|}{2}}} - |\mathcal{O}^{\sigma}(\mathcal{O}^{k(\epsilon^*)}(\vec{0}) - \vec{x}^*)_v| \quad \text{(since } \mathcal{O}^{\sigma} \text{ is linear)} \\
&\ge \epsilon^* - \lambda \cdot \|\mathcal{O}^{k(\epsilon^*)}(\vec{0}) - \vec{x}^*\|_{\infty} > \epsilon^* - \frac{\epsilon^*}{2} \quad \text{(Lemma 56)} \\
&= \frac{\epsilon^*}{2}.
\end{align*}
$$

In particular, it must hold that $\vec{z}_v < \vec{x}_v^*$. Otherwise we would have $\mathcal{O}^{k(\epsilon^*)+1}(\vec{0})_v \ge \mathcal{O}^{\sigma}(\mathcal{O}^{k(\epsilon^*)}(\vec{0}))_v \ge \vec{x}_v^* + \frac{\epsilon^*}{2}$, a contradiction with $\mathcal{O}^{k(\epsilon^*)+1}(\vec{0})$ being an $\frac{\epsilon^*}{4}$-approximation of $\vec{x}^*$ (by Lemma 56 and the choice of $k(\epsilon^*)$).

At the same time, $|\mathcal{O}(\mathcal{O}^{k(\epsilon^*)}(\vec{0}))_v - \vec{x}^*| \le \frac{\epsilon^*}{4}$, due to the choice of $k(\epsilon^*)$. Since $\vec{z}_v \le \vec{x}_v^*$, we get $\vec{z}_v < \vec{x}_v^* - \frac{\epsilon^*}{2} \le \mathcal{O}(\mathcal{O}^{k(\epsilon^*)}(\vec{0}))_v$, a contradiction with $\sigma$ being $\mathcal{O}^{k(\epsilon^*)}(\vec{0})$-safe. $\square$

**Corollary 14** (Complexity of discounted payoff MDPs with a fixed discount factor). *An optimal MD strategy in discounted payoff MDPs with a fixed discount factor can be computed in polynomial time.*

*Proof.* The number $1/\epsilon^*$, where $\epsilon^*$ is from Lemma 58, has bitsize polynomial in the size of the MDP when the discount factor is fixed. Hence, the number $k(\epsilon^*)$ defined as in Lemma 57 has a polynomial magnitude, so it suffices to perform only polynomially many iterations. Since each iteration requires polynomially many arithmetic operations that involve only summation and multiplication by a constant, the result follows. $\square$

## Strategy improvement, linear programming, and (strongly) polynomial time

The strategy (or policy) improvement (also called strategy/policy iteration in the literature) for MDPs works similarly as for games, see Algorithm 5.3. In the algorithm, we
use $\mathbb{O}_{a,v}(\bar{x})$ as a shortcut for $\sum_{u \in V} \Delta(u | v, a) ((1 - \lambda) \cdot c(v, u) + \lambda \cdot \bar{x}_u)$. The computation of $\bar{x}^{\sigma_i}$ uses Lemma 52.

<caption>**Algorithm 5.3:** An algorithm computing an optimal MD strategy in a discounted MDP</caption>

**Data:** A discounted payoff MDP $\mathcal{M}$
$i \leftarrow 0$;
$\sigma_i \leftarrow$ arbitrary MD strategy;
**repeat**
> compute $\bar{x}^{\sigma_i} = (\mathbb{E}_{v \in V}^{\sigma_i}[\text{DiscountedPayoff}])_{v \in V}$;
> **foreach** $v \in V$ **do**
> > Improve($v$) $\leftarrow \sigma_i(v)$;
> > **foreach** $a \in A$ **do**
> > > **if** $\mathbb{O}_{a,v}(\bar{x}^{\sigma_i}) > \mathbb{O}_{a,\text{Improve}(v)}(\bar{x}^{\sigma_i})$ **then** Improve($v$) $\leftarrow a$;
> > $\sigma_{i+1}(v) \leftarrow$ Improve($v$)
> > $i \leftarrow i+1$
> **until** $\sigma_i = \sigma_{i-1}$;
> **return** $\sigma_i$

**Theorem 58 (Strategy improvement for discounted MDPs).** The strategy improvement algorithm for discounted MDPs terminates in a finite (and at most exponential) number of steps and returns an optimal MD strategy.

*Proof.* First we need to show that whenever $\sigma_{i+1} \neq \sigma_i$, then $\bar{x}^{\sigma_{i+1}} \geq \bar{x}^{\sigma_i}$ and $\bar{x}^{\sigma_{i+1}} \neq \bar{x}^{\sigma_i}$ (we write this by $\bar{x}^{\sigma_{i+1}} \succ \bar{x}^{\sigma_i}$). So fix some $i$ s.t. an improvement is performed in the $i$-th iteration of the repeat-loop. We have $\mathbb{O}_{\sigma_{i+1}}(\bar{x}^{\sigma_i}) \succ \mathbb{O}_{\sigma_i}(\bar{x}^{\sigma_i}) = \bar{x}^{\sigma_i}$, i.e. $\mathbb{O}_{\sigma_{i+1}}(\bar{x}^{\sigma_i}) - \bar{x}^{\sigma_i} \succ 0$. Let $P, \vec{c}$ be the matrix and vector such that the equation $\bar{x} = \mathbb{O}_{\sigma_{i+1}}(\bar{x})$ can be written as $\bar{x} = (1-\lambda)\cdot\bar{c} + \lambda \cdot P \cdot \bar{x}$. Since the equation $\bar{x} = \mathbb{O}_{\sigma_{i+1}}(\bar{x})$ has a unique fixed point (as $\mathbb{O}_{\sigma_{i+1}}$ is a contraction), the matrix $I-\lambda P$ is invertible. Then $\mathbb{O}_{\sigma_{i+1}}(\bar{x}^{\sigma_i}) - \bar{x}^{\sigma_i} \succ 0$ can be written as $(1-\lambda)\bar{c} + (\lambda P - I)\bar{x}^{\sigma_i} \succ 0$, or equivalently $\bar{x}^{\sigma_i} \prec (1-\lambda)\bar{c} \cdot (I - \lambda P)^{-1}$. But the RHS of this inequality is equal to the fixed point of $\mathbb{O}_{\sigma_{i+1}}$, i.e. to $\bar{x}^{\sigma_{i+1}}$.

Now there are only finitely (exponentially) many MD strategies and since $\bar{x}^{\sigma_{i+1}} \succ \bar{x}^{\sigma_i}$, we have that no strategy is considered twice. Hence, the algorithm eventually terminates. Upon termination, there is no improving action, so the algorithm has found a strategy $\sigma$ whose value vector $\bar{x}^{\sigma}$ is the fixed point of $\mathbb{O}$. Such a strategy is optimal by Theorem 57. $\square$

While each of the steps (1).–(4.) can be performed in polynomial time, the worst-case number of iterations is exponential [HDJ12]. However, the algorithm has nice properties in the case when the discount factor is fixed, as we’ll see below. It is also intimately connected to the linear programming approach.

We can indeed aim to directly solve the equation $\bar{x} = \mathbb{O}(\bar{x})$, thus obtaining the fixed point of $\mathbb{O}$, by using a suitable LP. While the operator $\mathbb{O}$ is not in itself linear, solving the equation can be encoded into a linear program. The main idea can be described as follows: given some numbers $y, z$, the solution $\bar{x}$ to the equation $x = \max\{y, z\}$ is
exactly the smallest solution to the set of inequalities $x \ge y$, $x \ge z$. Hence, to solve the equation $\vec{x} = \mathbb{O}(\vec{x})$, we set up the following linear program $\mathcal{L}_{disc}$ with variables $x_v$, $v \in V$.

$$ \begin{array}{ll} \text{minimize} & \sum_{v \in V} x_v \\ \text{subject to} & x_v \ge \sum_{u \in V} \Delta(u | v, a) \cdot ((1 - \lambda) \cdot c(v, u) + \lambda \cdot x_u) \quad \text{for all } v \in V \text{ and } a \in A. \end{array} $$

**Lemma 59 (Properties of the linear program).** The linear program $\mathcal{L}_{disc}$ has a unique optimal solution $\vec{x}$ that satisfies $\vec{x} = \text{val}(\mathcal{M})$.

*Proof.* Let $\vec{x}^* = \text{val}(\mathcal{M})$ be the unique fixed point of $\mathbb{O}$. Clearly setting $x_v = \vec{x}_v^*$ yields a feasible solution of $\mathcal{L}_{disc}$. We show that $\vec{x}^*$ is actually an optimal solution, by proving that for each feasible solution $\vec{x}$ it holds $\vec{x} \ge \vec{x}^*$. (This also shows the uniqueness, since it says that an optimal solution is the infimum of the set of all feasible solutions.) First, note that for any feasible solution $\vec{x}$ it holds $\mathbb{O}(\vec{x}) \le \vec{x}$, by the construction of $\mathcal{L}_{disc}$. Next, if $\vec{x}$ is a feasible solution, then $\mathbb{O}(\vec{x})$ is also a feasible solution; otherwise, there would be some $v$ and $a \in A$ such that

$$ \begin{aligned} \mathbb{O}(\vec{x})_v &< \sum_{u \in V} \Delta(u | v, a) \cdot ((1 - \lambda) \cdot c(v, u) + \lambda \cdot \mathbb{O}(\vec{x})_u) \\ &\le \sum_{u \in V} \Delta(u | v, a) \cdot ((1 - \lambda) \cdot c(v, u) + \lambda \cdot \vec{x}_u) \le \mathbb{O}(\vec{x})_v. \end{aligned} $$

Here, the first inequality on the second line follows from $\mathbb{O}(\vec{x}) \le \vec{x}$, while the second inequality follows from the definition of $\mathbb{O}$. But $\mathbb{O}(\vec{x})_v < \mathbb{O}(\vec{x})_v$ is an obvious contradiction. So $\mathbb{O}(\vec{x})$ is indeed a feasible solution and by applying the argument above, we get $\mathbb{O}^2(\vec{x}) \le \mathbb{O}(\vec{x})$. By a simple induction, $\mathbb{O}^{i+1}(\vec{x}) \le \mathbb{O}^i(\vec{x}) \le \vec{x}$ for each $i \ge 0$. Hence, also $\vec{x}^* = \lim_{i \to \infty} \mathbb{O}^i(\vec{x}) \le \vec{x}$ (the first equality comes from Lemma 51). $\square$

Linear programming can be solved in polynomial time (Theorem 2). Hence, we get the following.

**Theorem 59 (Properties of discounted payoff MDPs).** The following holds for discounted payoff MDPs:

1. The value of each vertex as well as an MD optimal strategy can be computed in polynomial time.

2. The problem whether the value of a given vertex $v$ is at least a given constant (say 1) is P-complete (under logspace reductions). The hardness result holds even for a fixed discount factor.

*Proof.* (1.) The first part comes directly from Lemma 59. Once the optimal value vector $\text{val}(\mathcal{M})$ is computed, we can choose any $\text{val}(\mathcal{M})$-safe MD strategy as the optimal one (Lemma 53).

(2.) Let $\lambda$ be the fixed discount factor. We show the lower bound, by extending the reduction from the CVP problem used for almost-sure reachability. First, we transform the input circuit into an MDP in the same way as in the reachability case, and we let
v be the vertex corresponding to a gate we wish to evaluate. Assume, for a while, that each path from v to a target state has the same length $l$. Then we simply assign reward $\frac{1}{(1-\lambda)\cdot\lambda^{l-1}}$ to each edge entering a target state, and 0 to all other edges. It is easy to check that the value of v in the resulting discounted MDP is equal to the value of v in the reachability MDP. If the reachability MDP $\mathcal{M}$ does not have the ‘uniform path length’ property, we modify it by producing $|V|$ copies of itself so that each new vertex carries, apart from the original name, an index from $\{1, \dots, n\}$. The transition function in the new MDP mimics the original one, but from vertices with index $j < n$ we transition to the appropriate vertices of index $j + 1$. The target vertices in the new MDP are those vertices of index $n$ that correspond to a target vertex of the original MDP (this does not break down the reduction, as target vertices in the original vertices can be assumed to have no outgoing edges other than self loops). This new MDP has the desired property and can be produced in a logarithmic space. $\square$

The previous theorem shows that discounted payoff MDPs can be solved in polynomial time even if the discount factor is not fixed (i.e., it is taken as a part of the input). This is an important difference from the 2-player setting. However, the proof, resting on polynomial-time solvability of linear programming, leaves opened a question whether the discounted payoff MDPs be solved in strongly polynomial time. An answer was provided by Ye [Ye11]: already the classic simplex algorithm of Dantzig solves $\mathcal{L}_{disc}$ in a strongly polynomial time in MDPs with a fixed discount factor. Formally, Ye proved that the number of iterations taken by the simplex method is bounded by $\frac{|V|^2 \cdot (|A|-1)}{1-\lambda} \cdot \log(\frac{|V|^2}{1-\lambda})$, with each iteration requiring $\mathcal{O}(|V|^2 \cdot |A|)$ arithmetic operations. This has also an impact on the strategy improvement method: it can be shown that strategy improvement in discounted MDPs is really just a ‘re-implementation’ of the simplex algorithm using a different syntax. Hence, the strongly polynomial complexity bound for a fixed discount factor holds there as well.

**Theorem 60** (Discounted payoff MDPs with a fixed discount factor). For MDPs with a fixed discount factor, the value of each vertex as well as an optimal MD strategy can be computed in a strongly polynomial time.

## 5.3 Mean payoff in MDPs: General properties and linear programming

We will use the $\liminf$ variant of mean payoff:

$$ \text{MeanPayoff}^{-}(\pi) = \liminf_{n} \frac{1}{n} \sum_{i=0}^{n-1} c(\pi_i) $$

In particular, the play-based expected mean payoff achieved by $\sigma$ from v is defined as p-Payoff($v, \sigma$) = $E_v^\sigma[\text{MeanPayoff}^{-}]$, while for the step-based counterpart we have s-Payoff($v, \sigma$) = $\liminf_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} E_v^\sigma[c(\pi_i)]$.

The use of $\liminf$ is natural in the formal verification setting: taking the $\liminf$ rather than $\limsup$ emphasizes the worst-case behaviour along a play. However, all the
results in this section hold also for lim sup-based mean payoff, though some proofs are more complex. See the bibliographic remarks for more details.

In general, s-Payoff(v, σ) can be different from p-Payoff(v, σ). However, we have the following simple consequence of the dominated convergence theorem:

**Lemma 60.** Let U be the set of all plays π for which $\lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} [c(\pi_i)]$ is undefined. If $v_0, \sigma$ are such that $\mathbb{P}_{v_0}^{\sigma}(U) = 0$, then s-Payoff($v_0, \sigma$) = p-Payoff($v_0, \sigma$).

In particular, for any finite-memory strategy σ, the two values coincide, since applying such a strategy turns an MDP into a finite Markov chain where the existence of the limit can be inferred using decomposition into strongly connected components and applying the Ergodic theorem. We will show that in our case of finite-state MDPs, the two approaches coincide not only at the levels of finite-memory strategies, but also as optimality criteria: that is, no matter which of the two semantics we use, the optimal values are the same and a strategy that is optimal w.r.t. one of the semantics is also optimal for the other one. We caution the reader that such a result does not automatically transfer to more complex settings, such as infinite-state MDPs or multi-objective optimization.

To simplify the subsequent notation, we define the *expected one-step reward* of a vertex-action pair $(v, a)$ to be the number $\sum_{w \in V} \Delta(w | v, a) \cdot c(v, w)$. Overloading the notation, we denote this quantity by $c(v, a)$.

In mean payoff MDPs, a crucial role is played by the linear program $\mathcal{L}_{mp}$ defined in Equation (5.4). The variables are $x_{(v,a)}$ for $v \in V$ and $a \in A$.

$$ 
\begin{array}{ll}
\text{maximise} & \displaystyle\sum_{v \in V, a \in A} x_{(v,a)} \cdot c(v, a) \\
\text{subject to} & \displaystyle\sum_{u \in V, a \in A} x_{(u,a)} \cdot \Delta(v | u, a) = \sum_{a \in A} x_{v,a} & \text{for all } v \in V \\
& \displaystyle\sum_{v \in V, a \in A} x_{v,a} = 1 & \text{for all } v \in V, a \in A \\
& x_{v,a} \ge 0 & \text{for all } v \in V, a \in A
\end{array}
\qquad (5.4) $$

Let us name the equations:

$$ \sum_{u \in V, a \in A} x_{(u,a)} \cdot \Delta(v | u, a) = \sum_{a \in A} x_{v,a} \quad \text{for all } v \in V \qquad (5.5) $$

$$ \sum_{v \in V, a \in A} x_{v,a} = 1 \quad \text{for all } v \in V, a \in A \qquad (5.6) $$

$$ x_{v,a} \ge 0 \quad \text{for all } v \in V, a \in A \qquad (5.7) $$

There is a correspondence between feasible solutions of $\mathcal{L}_{mp}$ and the strategies in the corresponding MDP. Intuitively, in a solution corresponding to a strategy σ, the value of a variable $x_{v,a}$ describes the expected frequency with which σ visits v and plays a upon such a visit. These frequencies must obey the *flow constraints* Equation (5.5) and must represent a probability distribution, which is ensured by Equation (5.6) and Equation (5.7). The objective function then represents the expected
mean payoff. Of high importance is also the linear program which is dual to $\mathcal{L}_{mp}$. This dual program, denoted $\mathcal{L}_{mp}^{dual}$, is defined in Section 5.3. (For a refresher on linear programming and duality, see Section 1.2).

$$ \begin{array}{ll} \text{minimize} & g \\ \text{subject to} & g - c(v, a) + \sum_{u \in V} \Delta(u | v, a) \cdot y_u \ge y_v \quad \text{for all } v \in V, a \in A \end{array} $$

A feasible solution of $\mathcal{L}_{mp}$ is a vector $\vec{x} \in \mathbb{R}^{V \times A}$ s.t. setting $x_{(v,a)} = \vec{x}_{(v,a)}$ for all $(v,a)$ satisfies the constraints in $\mathcal{L}_{mp}$. A feasible solution of $\mathcal{L}_{mp}^{dual}$ is a tuple $(g, \vec{y})$, where $g \in \mathbb{R}$ (using the same notation for the number and the variable should not cause confusion here) and $\vec{y} \in \mathbb{R}^V$ s.t. setting the corresponding variables to numbers prescribed by $g$ and $\vec{y}$ satisfies the constraints.

The variable $g$ in $\mathcal{L}_{mp}^{dual}$ is often called gain while the vector of y-variables is called bias. This is because it provides information on how much does the payoff (under some strategy) accumulated up to a certain step deviate from the estimate provided by the mean payoff value of that strategy. This is illustrated in the following lemma, which forms the first step of our analysis.

**Lemma 61 (Properties of feasible solutions).** Let $(g, \vec{y})$ be a feasible solution of $\mathcal{L}_{mp}^{dual}$ and let $Y^{(i)}$, where $i \ge 0$, be a random variable such that $Y^{(i)}(\pi) = \vec{y}_{In(\pi_i)}$. Then for each strategy $\sigma$, each vertex $v_0$, and each $n \ge 0$ it holds $E_{v_0}^{\sigma}[\sum_{i=0}^{n-1} c(\pi_i)] \le n \cdot g - \vec{y}_{v_0} + E_{v_0}^{\sigma}[Y^{(n)}]$.

*Proof.* By induction on $n$. For $n = 0$, both sides are equal to 0. Now assume that the inequality holds for some $n \ge 0$. By the induction hypothesis

$$ E_{v_0}^{\sigma}[\sum_{i=0}^{n} c(\pi_i)] = E_{v_0}^{\sigma}[\sum_{i=0}^{n-1} c(\pi_i)] + E_{v_0}^{\sigma}[c(\pi_n)] \le n g - \vec{y}_{v_0} + E_{v_0}^{\sigma}[Y^{(n)}] + E_{v_0}^{\sigma}[c(\pi_n)] \quad (5.8) $$

We now obtain a bound for the third term on the RHS of Equation (5.8). In the following, we denote by $\Pi_n$ the set of all plays of length $n$. Then we have

$$ \begin{align*} E_{v}^{\sigma}[Y^{(n)}] &= \sum_{v \in V} \vec{y}_{v} \cdot \mathbb{P}_{v_0}^{\sigma}(\ln(\pi_n) = v) = \sum_{v \in V} \vec{y}_{v} \cdot \left( \sum_{\substack{\pi' \in \Pi_n \\ \text{last}(\pi') = v}} \mathbb{P}_{v_0}^{\sigma}(\pi')} \right) \\ &= \sum_{v \in V} \vec{y}_{v} \cdot \left( \sum_{\substack{\pi' \in \Pi_n \\ \text{last}(\pi') = v}} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \underbrace{(\sum_{a \in A} \sigma(a | \pi'))}_{=1} \right) \\ &= \sum_{v \in V} \vec{y}_{v} \cdot \left( \sum_{\substack{\pi' \in \Pi_n \\ \text{last}(\pi') = v}} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi') \right) \\ &\le \sum_{v \in V} \sum_{a \in A} (g - c(v, a) + \sum_{u \in V} \Delta(u | v, a) \cdot \vec{y}_u) \cdot \left( \sum_{\substack{\pi' \in \Pi_n \\ \text{last}(\pi') = v}} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi') \right) \end{align*} $$
$$
\begin{align*}
&= g \cdot \underbrace{\sum_{v \in V} \sum_{\pi' \in \Pi_n} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi')}_{\substack{\text{last}(\pi')=v \\ \text{last}(\pi')=v}} \cdot \underbrace{\sum_{a \in A} \sum_{\pi' \in \Pi_n} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi') \cdot c(v, a)}_{\substack{\text{last}(\pi')=v \\ \text{last}(\pi')=v}} \\
&= \underbrace{- \sum_{v \in V} \sum_{\pi' \in \Pi_n} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi') \cdot c(v, a)}_{\substack{\text{last}(\pi')=v \\ \text{last}(\pi')=v}} + \underbrace{\sum_{v, u \in V} \sum_{\pi' \in \Pi_n} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi') \cdot \Delta(u | v, a) \cdot \bar{y}_u}_{\substack{\text{last}(\pi')=v \\ \text{last}(\pi')=v}} \\
&= \underbrace{\sum_{v_0 \in V} \sum_{\pi' \in \Pi_n} \mathbb{P}_{v_0}^{\sigma}(\pi') \cdot \sigma(a | \pi') \cdot \Delta(u | v, a) \cdot \bar{y}_u}_{\substack{\text{last}(\pi')=v \\ \text{last}(\pi')=v}}
\end{align*}
$$

The first inequality follows from Section 5.3.

Plugging this into Equation (5.8) yields the desired $\mathbb{E}_{v_0}^{\sigma}[\sum_{i=0}^{n} c(\pi_i)] \le (n+1)g - \bar{y}_{v_0} + \mathbb{E}_{v_0}^{\sigma}[Y^{(n+1)}]$. $\square$

**Corollary 15** (Feasible solutions imply upper bounds). Let $g$ be the objective value of some feasible solution of $\mathcal{L}_{mp}^{\text{dual}}$. Then for every strategy $\sigma$ and every vertex $v_0$ it holds $\text{s-Payoff}(v_0, \sigma) \le \text{s-Payoff}(v_0, \sigma) \le g$.

*Proof.* Let $(g, \vec{y})$ be any feasible solution of $\mathcal{L}_{mp}^{\text{dual}}$. By Lemma 61 we have, for every $n \ge 0$, that $\mathbb{E}_{v_0}^{\sigma}[\frac{1}{n}\sum_{i=0}^{n-1} c(\pi_i)] \le g - \frac{\bar{y}_{v_0}}{n} + \frac{1}{n}\mathbb{E}_{v_0}^{\sigma}[Y^{(n)}]$. Since $\bar{y}_{v_0}$ is a constant and $|\mathbb{E}_{v_0}^{\sigma}[Y^{(n)}]|$ is bounded by the constant $\max_{v \in V} |\bar{y}_v|$ that is independent of $n$, the last two terms on the RHS vanish as $n$ goes to $\infty$. Hence, we also have that $\text{s-Payoff}(v_0, \sigma) = \lim \inf_{n \to \infty} \mathbb{E}_{v_0}^{\sigma}[\frac{1}{n}\sum_{i=0}^{n-1} c(\pi_i)] \le g$. It remains to show that we have $\text{p-Payoff}(v_0, \sigma) \le \text{s-Payoff}(v_0, \sigma)$, but this immediately follows from the Fatou's lemma [ADD00, Theorem 1.6.8]. $\square$

**Corollary 16** (Existence of optimal solutions for the linear programs). Both the linear programs $\mathcal{L}_{mp}$ and $\mathcal{L}_{mp}^{\text{dual}}$ have a feasible solution. Hence, both have an optimal solution and the optimal values of the objective functions in these programs are equal.

*Proof.* One can easily construct a feasible solution for $\mathcal{L}_{mp}^{\text{dual}}$ by setting all the y-variables to 0 and $g$ to $\max_c$. By the duality theorem for linear programming, to show that also $\mathcal{L}_{mp}$ has feasible solution it suffices to show that the objective function of $\mathcal{L}_{mp}^{\text{dual}}$ is bounded from below. But this follows from Corollary 15, since there is at least one strategy $\sigma$ giving us the lower bound (in particular, the objective function is bounded from below by $-\max_c$). The second part follows immediately by linear programming duality. $\square$

## 5.4 Mean payoff optimality in strongly connected MDPs

As shown in the previous section, the optimal solution of any of the programs $\mathcal{L}_{mp}$, $\mathcal{L}_{mp}^{\text{dual}}$ gives us an upper bound on the optimal value. In this sub-section we show that
in strongly connected MDPs: a) a value of every vertex is the same; b) from a solution of $\mathcal{L}_{mp}$ one can extract a memoryless deterministic strategy $\sigma$ whose expected mean payoff is well defined (i.e., the preconditions of Lemma 60 are satisfied)) and equal to the objective value of the solution. Moreover, if the solution in question is optimal, then $\sigma$ is optimal for both p-Payoff- and s-Payoff-semantics.

**Definition 12** (Strongly connected MDPs). An MDP is strongly connected if for each pair of vertices $u, v$ there exists a strategy which, when starting in $u$, reaches $v$ with a positive probability.

For the rest of this section we fix an optimal solution $\bar{\bar{x}}_{v,a}$ of $\mathcal{L}_{mp}$. We denote by $S$ the set of all vertices for which there exists action $a$ s.t. $\bar{\bar{x}}_{v,a} > 0$. From the shape of $\mathcal{L}_{mp}$ it follows that $S$ is non-empty and closed, and hence we can consider a sub-MDP $\mathcal{M}_S$ induced by $S$. In $\mathcal{M}_S$ we then define a memoryless randomized strategy $\sigma$ by putting

$$ \sigma(a | v) = \frac{\bar{\bar{x}}_{(v,a)}}{\sum_{b \in A} \bar{\bar{x}}_{(v,b)}}. $$

Fixing a strategy $\sigma$ yields a Markov chain $\mathcal{M}_S^\sigma$. Markov chain can be viewed as an MDP with a single action (and hence, with no non-determinism). $\mathcal{M}_S^\sigma$ in particular can be viewed an MDP with the same vertices, edges, and colouring as $\mathcal{M}_S$, but with a single action (as non-determinism was already resolved by $\sigma$). The probability of transitioning from a vertex $u$ to a vertex $v$ in a Markov chain is denoted by $P_{u,v}$. In $\mathcal{M}_S^\sigma$ we have $P_{u,v} = \sum_{a \in A} \Delta(v | u, a) \cdot \sigma(a | u)$, the right-hand side being computed in the original MDP $\mathcal{M}$. Both $\mathcal{M}_S$ and $\mathcal{M}_S^\sigma$ have the same sets of plays and for each initial vertex, the probability measure induced by $\sigma$ in $\mathcal{M}$ equals the probability measure arising (under the unique policy) in $\mathcal{M}_S^\sigma$. Hence, to prove anything about $\sigma$ it suffices to analyse $\mathcal{M}_S^\sigma$.

**A refresher on Markov chains.** We review some fundamental notions of Markov chain theory [Nor98]. A Markov chain that is strongly connected is called *irreducible*. The one-step transition probabilities in a Markov chain can be arranged into a square matrix $P$, which has one row and one column for each vertex. The cell in the row corresponding to a vertex $u$ and in the column corresponding to a vertex $v$ bears the value $P_{u,v}$ defined above. An easy induction shows that the matrix $P^k$ contains $k$-step transition probabilities. That is, the probability of being in $v$ after $k$ steps from vertex $u$ is equal to the $(u, v)$-cell of $P^k$, which we denote by $P_{u,v}^{(k)}$.

A vertex $u$ of a Markov chain is *recurrent* if, when starting from $u$, it is revisited infinitely often with probability 1. On the other hand, if the probability that $u$ is revisited only finitely often is one, then the vertex is *transient*. It is known [Nor98, Theorem 1.5.3] that each vertex of a finite Markov chain is either recurrent or transient, and that these two properties can be equivalently characterized as follows: vertex $u$ is recurrent if and only if $\sum_{k=0}^\infty P_{u,u}^{(k)} = \infty$, otherwise it is transient.

An invariant distribution in a Markov chain with a vertex set $V$ is a $|V|$-dimensional non-negative row vector $\bar{z}$ which adds up to 1 and satisfies $\bar{z} \cdot P = \bar{z}$.

The following lemma holds for arbitrary finite Markov chains.
**Lemma 62** (Invariant distributions witness recurrent states). Let $\bar{z}$ be an invariant distribution and $v$ a vertex such that $\bar{z}_v > 0$. Then $v$ is recurrent.

*Proof.* Let $n$ be the number of vertices in the chain and $p_{\min}$ the minimum non-zero entry of $P$. Assume, for the sake of contradiction, that $v$ is transient. We show that in such a case, for each vertex $u$ it holds $\lim_{k \to \infty} P_{u,v}^{(k)} = 0$. For $u = v$ this is immediate, since the sum $\sum_{k=0}^{\infty} P_{v,v}^{(k)}$ converges for transient $v$. Otherwise, let $f_{u,v,i}$ be the probability that a play starting in $u$ visits $v$ for the first time in exactly $i$ steps. Then $P_{u,v}^{(k)} = \sum_{i=0}^{k} f_{u,v,i} \cdot P_{v,v}^{(k-i)}$. Now when starting in a vertex from which $v$ is reachable with a positive probability, at least one of the following events happens with probability $\ge p_{\min}^n$ in the first $n$ steps: either we reach a vertex from which $v$ is not reachable with positive probability, or we reach $v$. If neither of the events happens, we are, after $n$ steps, still in a vertex from which $v$ can be reached with a positive probability. In such a case, the argument can be inductively repeated (analogously to the proof of Theorem 54) to show that $f_{u,v,i} \le (1-p_{\min}^n)^{\lfloor \frac{i}{n} \rfloor} \le (1-p_{\min}^n)^{\frac{i-n}{n}}$.

Since $\sum_{k=0}^{\infty} P_{v,v}^{(k)}$ converges, for each $\varepsilon > 0$ there exists $j_{\varepsilon}$ such that $\sum_{i=j_{\varepsilon}}^{\infty} P_{v,v}^{(i)} < \frac{\varepsilon}{2}$. Similarly, there exists $\ell_{\varepsilon}$ such that

$$ \sum_{i=\ell_{\varepsilon}}^{\infty} (1-p_{\min}^{n})^{\frac{i-n}{n}} = \frac{(1-p_{\min}^{n})^{\frac{\ell_{\varepsilon}}{n}}}{\left(1-(1-p_{\min}^{n})^{\frac{1}{n}}\right) \cdot (1-p_{\min}^{n})} < \frac{\varepsilon}{2}, $$

and hence $\sum_{i=\ell_{\varepsilon}}^{\infty} f_{u,v,i} < \frac{\varepsilon}{2}$.

Now we put $m_{\varepsilon} = \max\{j_{\varepsilon}, \ell_{\varepsilon}\}$. For any $k \ge 2m_{\varepsilon}$ we have $P_{u,v}^{(k)} = \sum_{i=0}^{k} f_{u,v,i} \cdot P_{v,v}^{(k-i)} \le \sum_{i=m_{\varepsilon}}^{k} f_{u,v,i} + \sum_{i=0}^{m_{\varepsilon}} P_{v,v}^{(k-i)} \le \sum_{i=m_{\varepsilon}}^{k} f_{u,v,i} + \sum_{i=m_{\varepsilon}}^{k} P_{v,v}^{(i)} < \varepsilon$ (note that all the series involved are non-negative). This proves that $P_{u,v}^{(k)}$ vanishes in the limit.

Finally, we derive the contradiction. Since $\bar{z}$ satisfies $\bar{z} \cdot P = \bar{z}$, we also have $\bar{z} \cdot P^k = \bar{z}$ for all $k$. Hence, the $v$-component of $\bar{z} \cdot P^k$ is equal to $\bar{z}_v > 0$. But as shown above, the $v$-column of $P^k$ converges to the all-zero vector as $k \to \infty$, so also $(\bar{z} \cdot P^k)_v$ vanishes in the limit, a contradiction. $\square$

**Towards the optimality of $\sigma$.** We now turn back to the chain $M_S^\sigma$, where the memoryless strategy $\sigma$ is obtained from the optimal solution of $\mathcal{L}_{mp}$. In general, $M_S^\sigma$ does not have to be irreducible. Hence, we use the following lemma and its corollary to extract an irreducible sub-chain, to which we can apply known results of Markov chain theory.

**Lemma 63** (Invariant distributions witness recurrent MDPs). Let $\bar{z}$ be a vector such that for each $v \in S$ it holds $\bar{z}_v = \sum_{a \in A} \bar{x}_{v,a}$. Then $\bar{z}$ is an invariant distribution of $M_S^\sigma$. Consequently, all vertices of $M_S^\sigma$ are recurrent.

*Proof.* The first part follows directly from the fact that $\bar{x}_{v,a}$ is a feasible solution of $\mathcal{L}_{mp}$. The second part follows from Lemma 62 and from the fact that $\bar{z}$ is positive (by the definition of $S$). $\square$
**Corollary 17** (Extraction of strongly connected components). The set $S$ can be partitioned into subsets $S_1, S_2, \dots, S_m$ such that each $S_i$ induces a strongly connected sub-chain of $\mathcal{M}_S^\sigma$.

*Proof.* Let $v \in S$ be arbitrary and let $U_v \subseteq S$ be the set of all vertices reachable with positive probability from $v$ in $\mathcal{M}_S^\sigma$. Then $v$ is reachable (in $\mathcal{M}_S^\sigma$) with positive probability from each $u \in U_v$: otherwise, there would be a positive probability of never revisiting $v$, a contradiction with each vertex being recurrent in $\mathcal{M}_S^\sigma$ (Lemma 63). Hence, $U_v$ induces a strongly connected 'sub-MDP' (or sub-chain) of $\mathcal{M}_S^\sigma$. It is easy to show that if $U_v \neq U_w$ for some $v \neq w$, then the two sets must be disjoint. $\square$

Hence, we can extract from $S$ a set $Q$ inducing a strongly-connected sub-chain of $\mathcal{M}_S^\sigma$, which we denote $\mathcal{M}_Q^\sigma$. The set $Q$ also induces a strongly connected sub-MDP of $\mathcal{M}$ denoted by $\mathcal{M}_Q$. The chain $\mathcal{M}_Q^\sigma$ arises by fixing, in $\mathcal{M}_Q$, a strategy formed by a restriction of $\sigma$ to $Q$. We use the following powerful theorem to analyse $\mathcal{M}_Q^\sigma$.

**Theorem 61** (Ergodic theorem). In a strongly connected Markov chain (with a finite set of vertices $V$) there exists a unique invariant distribution $\vec{z}$. Moreover, for every vector $\vec{h} \in \mathbb{R}^V$ the following equation holds with probability 1:

$$ \lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} \vec{h}_{In(\pi_i)} = \sum_{v \in V} \vec{z}_v \cdot \vec{h}_v. $$

(In particular, the limit is well-defined with probability 1).

We refer to Theorem 1.10.2 in [Nor98] for a proof of the Ergodic theorem.

We can use the Ergodic theorem to show that the expected mean payoff achieved by $\sigma$ in $\mathcal{M}_Q$ matches the optimal value of $\mathcal{L}_{mp}$, in a very strong sense: the probability of a play having a mean payoff equal to this optimal value is 1 under $\sigma$.

**Theorem 62.** Let $\sigma_Q$ be the restriction of $\sigma$ to $Q$. Then for every $v \in Q$ it holds that $\mathbb{P}_{\mathcal{M}_{Q,v}}^{\sigma_Q}(\text{MeanPayoff}^- = r^*) = 1$, where $r^*$ is the optimal value of $\mathcal{L}_{mp}$.

*Proof.* Let $\vec{w} \in \mathbb{R}^{V \times A}$ be a vector such that $\vec{w}_{(v,a)} = \bar{\vec{x}}_{(v,a)}/\sum_{(q,a) \in Q \times A} \bar{\vec{x}}_{(q,a)}$ for every $(v,a) \in Q \times A$, and $\vec{w}_{(v,a)} = 0$ for all other $(v,a)$. We claim that $\vec{w}$ is also an optimal solution of $\mathcal{L}_{mp}$.

To prove feasibility, note that setting $\vec{w}_{(v,a)} = 0$ for each $v \in V \setminus Q$ does not break the constraints Equation (5.5). This is because $Q$ induces a strongly connected sub-chain of $\mathcal{M}_S^\sigma$, and hence there are no $v \in V$, $u \in V \setminus Q$ such that $\bar{\vec{x}}_{(u,a)} \cdot \Delta(v|u,a) > 0$. Next, Equation (5.5) is invariant w.r.t. multiplication of variables by a constant, so normalizing the remaining values preserves Equation (5.5) and ensures that Equation (5.6) holds.

To prove optimality, assume that the objective value of $\vec{w}$ is smaller than $r^*$. Then we can mirror the construction from the previous paragraph and produce a feasible solution $\hat{\vec{w}}_{(v,a)}$ whose $(Q \times A)$-indexed components are zero and the rest are normalized components of $\bar{\vec{x}}$. Then $r^*$ is a convex combination of the objective values of $\vec{w}$ and $\hat{\vec{w}}$, so $\hat{\vec{w}}$ must have a strictly larger value than $r^*$, a contradiction with the latter's optimality.
We now plug $\vec{w}$ into the ergodic theorem as follows: As in Lemma 63, it easy to prove that setting $\vec{z}_v = \sum_{a \in A} \vec{w}_{(v,a)}$ yields an invariant distribution. Now put $\vec{h}_v = \sum_{a \in A} \sigma(a | v) \cdot c(v, a) (= \sum_{w \in V} P_{v,w} \cdot c(v, w))$. From the Ergodic theorem we get that $\lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} \vec{h}_{\ln(\pi_i)}$ almost-surely exists and equals

$$
\begin{align}
\sum_{v \in Q} \vec{z}_v \cdot \vec{h}_v &= \sum_{v \in V} \left( \left( \sum_{d \in A} \vec{w}_{(v,d)} \right) \cdot \left( \sum_{a \in A} \sigma(a | v) \cdot c(v, a) \right) \right) \nonumber \\
&= \sum_{v \in Q} \left( \left( \frac{\sum_{d \in A} \vec{\bar{x}}_{(v,d)}}{\sum_{\substack{q \in Q \\ b \in A}} \vec{\bar{x}}_{(q,b)}} \right) \cdot \left( \frac{\sum_{a \in A} \vec{\bar{x}}_{(v,a)} \cdot c(v, a)}{\sum_{d \in A} \vec{\bar{x}}_{(v,d)}} \right) \right) \nonumber \\
&= \frac{1}{\sum_{\substack{q \in Q \\ b \in A}} \vec{\bar{x}}_{(q,b)}} \cdot \sum_{\substack{v \in Q \\ a \in A}} \vec{\bar{x}}_{(v,a)} \cdot c(v, a) = \sum_{\substack{v \in Q \\ a \in A}} \vec{w}_{(v,a)} \cdot c(v, a) = r^*. \tag{5.9}
\end{align}
$$

It remains to take a step from the left-hand side of Equation (5.9) towards the mean payoff. To this end, we construct a new Markov chain $\mathcal{M}'_Q$ from $\mathcal{M}_Q$ by 'splitting' every edge $(u, v)$ with a new dummy vertex $d_{u,v}$ (i.e., $d_{u,v}$ has one edge incoming from $u$ with probability $P_{u,v}$ and one edge outgoing to $v$ with probability 1). In $\mathcal{M}'_Q$ we define a vector $\vec{h}'$ s.t. for each vertex $d_{u,v}$ the vector $\vec{h}'$ has the $d_{u,v}$-component equal to $c(u, v)$, while the components corresponding to the original vertices are zero. It is easy to check that $\mathcal{M}'_Q$ is strongly connected and that it has an invariant distribution $\vec{z}'$ defined by $\vec{z}'_v = \vec{z}_v/2$ for $v$ in $Q$ and $\vec{z}'_{d_{u,v}} = \frac{\vec{z}_u \cdot P_{u,v}}{2}$ for $(u, v)$ an edge of $\mathcal{M}_Q$. Also, by easy induction, for each play $\pi$ of length $n$ in $\mathcal{M}_Q$ it holds $\frac{1}{n} \sum_{i=0}^{n-1} c(\pi_i) = \frac{1}{n} \sum_{i=0}^{2n-1} \vec{h}'_{\ln(\pi_i)}$, where $\pi'$ is the unique play in $\mathcal{M}'_Q$ obtained from $\pi$ by splitting edges with appropriate dummy vertices. Hence,

$$
\lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} c(\pi_i) = 2 \cdot \lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} \vec{h}'_{\ln(\pi_i)}, \quad (5.10)
$$

provided that both limits exist. By the ergodic theorem applied to $\mathcal{M}'_Q$, we have that
the RHS limit in Equation (5.10) is defined with probability 1 and equal to

$$
\begin{align*}
& \underbrace{\sum_{v \in Q} \vec{z}'_v \cdot \vec{h}'_v}_{=0} + \sum_{u,v \in Q} \vec{z}'_{d_{u,v}} \cdot \vec{h}'_{d_{u,v}} \\
&= \frac{1}{2} \sum_{u \in Q} \vec{z}_u \cdot \left( \sum_{v \in Q} P_{u,v} \cdot c(u,v) \right) \\
&= \frac{1}{2} \sum_{u \in Q} \vec{z}_u \cdot \vec{h}_u = \frac{r^*}{2},
\end{align*}
$$

the last equality being shown above. Plugging this into Equation (5.10) yields that if a
limit on the LHS (i.e., the mean payoff of a play) is well-defined with probability 1, then
it is equal to $r^*$ also with probability 1. But if there was a set $L$ of positive probability in
$\mathcal{M}_Q$ with $\lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} c(\pi_i)$ undefined for each $\pi \in L$, by splitting the plays in $L$ we
would obtain a positive-probability set of plays in $\mathcal{M}_Q'$ in which $\lim_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} \vec{h}'_{\ln(\pi_i)}$ is also undefined, a contradiction with the Ergodic theorem. $\square$

So far, we have constructed an optimal strategy $\sigma_Q$ but only on the part $Q$ of the original MDP $\mathcal{M}$. To conclude the construction, we define a memoryless strategy $\sigma^*$ in $\mathcal{M}$ as follows: we fix a memoryless deterministic strategy $\sigma_{=1}$ that is winning, from each vertex of $\mathcal{M}$, for the objective of almost-sure reaching of $Q$ (such a strategy exists since $\mathcal{M}$ is strongly connected, see also Theorem 54). Then we put $\sigma^*(v) = \sigma_{=1}(v)$ if $v \notin Q$ and $\sigma^*(v) = \sigma_Q(v)$ otherwise. Hence, starting in any vertex, $\sigma^*$ eventually reaches $Q$ with probability 1 and then it starts behaving as $\sigma_Q$. The optimality of such a strategy follows from the prefix independence of mean payoff, as argued in the next theorem.

**Theorem 63** (Prefix independence of mean payoff). For any sequence of numbers $c_0, c_1, \dots$ and any $k \in \mathbb{N}$ it holds $\liminf_{n \to \infty} \frac{1}{n} \sum_{i=0}^{n-1} c_i = \liminf_{m \to \infty} \frac{1}{m} \sum_{i=0}^{m-1} c_{k+i}$. As a consequence, for every vertex $v$ in $\mathcal{M}$ it holds $\mathbb{P}_{\mathcal{M}_Q, v}^{\sigma_Q}(\text{MeanPayoff}^- = r^*) = 1$, where $r^*$ is the optimal value of $\mathcal{L}_{mp}$. Hence, $\mathbb{E}_v^{\sigma^*}[\text{MeanPayoff}^-] = r^*$.

*Proof.* We have

$$ \liminf_{n \to \infty} \frac{c_0 + \dots + c_{n-1}}{n} = \liminf_{n \to \infty} \left( \underbrace{\frac{k}{n} \cdot \frac{c_0 + \dots + c_{k-1}}{k}}_{\text{vanishes for } n \to \infty} + \underbrace{\frac{n-k}{n} \cdot \frac{c_k + \dots + c_{n-1}}{n-k}}_{\to 1 \text{ for } n \to \infty} \right) \\ = \liminf_{m \to \infty} \frac{c_k + \dots + c_{k+m-1}}{m}. $$

A similar argument holds for $\limsup$.

With probability 1, a play has an infinite suffix consisting of plays from $\mathcal{M}_Q^\sigma$, and thus also $\text{MeanPayoff}^-$ and $\text{MeanPayoff}^+$ determined by this suffix. By Theorem 62, these quantities are equal to $r^*$ with probability 1. $\square$

The following theorem summarizes the computational aspects.

**Theorem 64** (Complexity of solving strongly connected mean payoff MDPs). In a strongly connected mean payoff MDP, one can compute, in polynomial time, a memoryless randomized strategy which is optimal from every vertex, as well as the (single) optimal value of every vertex.

*Proof.* We obtain, in polynomial time, an optimal solution of $\mathcal{L}_{mp}$, with the optimal objective value being the optimal value of every vertex (Theorem 63). We then use this optimal solution $\bar{x}$ to construct the strategy $\sigma$ and the Markov chain $\mathcal{M}_S^\sigma$. From this chain we extract a strongly connected subset of vertices $Q$ (in polynomial time, by a simple graph reachability analysis). With the subset in hand, we can construct strategies $\sigma_Q$ and $\sigma_{=1}$, all polynomial-time computations (see Theorem 54). These two strategies are then combined to produce the optimal strategy $\sigma^*$. $\square$
**Deterministic optimality in strongly connected MDPs**

It remains to prove that we can actually compute a memoryless deterministic strategy that is optimal in every vertex. Looking back at the construction that resulted in Theorem 64, we see that the optimal strategy $\sigma^*$ might be randomized because the computed optimal solution $\bar{\bar{x}}$ of $\mathcal{L}_{mp}$ can contain two components $(v, a)$, $(v, b)$ with $a \neq b$ and both $\bar{\bar{x}}_{(v,a)}$ and $\bar{\bar{x}}_{(v,b)}$ being positive. To prove memoryless deterministic optimality, we will show that there is always an optimal solution which yields a deterministic strategy, and that such a solution can be obtained in polynomial time.

The previous section implicitly defined two mappings: First, a mapping $\Psi$, which maps every solution $\bar{x}$ of $\mathcal{L}_{mp}$ to a memoryless strategy in some sub-MDP of $\mathcal{M}$, by putting $\Psi(\bar{x}) = \sigma$ where $\sigma(a | v) = \bar{x}_{(v,a)} / \sum_{b \in A} \bar{x}_{(v,b)}$. Second, mapping $\Xi$, which maps each memoryless strategy $\sigma$ that induces a strongly connected Markov chain to a solution $\Xi(\sigma)$ of $\mathcal{L}_{mp}$ such that $\Xi(\sigma)_{(v,a)} = \bar{z}_v \cdot \sigma(a | v)$, where $\bar{z}$ is the unique invariant distribution of the chain induced by $\sigma$.

**Lemma 64** (Correspondence between solutions and strategies). Let $X$ be the set containing exactly those solutions $\bar{x}$ of $\mathcal{L}_{mp}$ for which the strategy $\Psi(\bar{x})$ induces a strongly connected Markov chain. Then the mappings $\Psi$ and $\Xi$ are bijections between $X$ and the set of all memoryless strategies in some sub-MDP of $\mathcal{M}$ that induce a strongly connected Markov chain.

*Proof*. A straightforward computation shows that $\Xi \circ \Psi$ and $\Psi \circ \Xi$ are identity functions on the respective sets. $\square$

**Definition 13** (Pure solutions). A solution $\bar{x}$ of $\mathcal{L}_{mp}$ is pure if for every vertex $v$ there is at most one action a such that $\bar{x}_{(v,a)} > 0$.

The following lemma follows from the way in which strategies $\sigma$ and $\sigma^*$ were constructed in the previous sub-section.

**Lemma 65** (Solutions of the linear programs). Let $\bar{\bar{x}}$ be a pure optimal solution of $\mathcal{L}_{mp}$ and denote $S = \{v \in V \mid \exists a \text{ s.t. } \bar{\bar{x}}_{(v,a)} > 0\}$. Then the strategy $\sigma = \Psi(\bar{\bar{x}})$ is an MD strategy in $\mathcal{M}_S$. Hence, in such a case, the strategy $\sigma^*$ constructed from $\sigma$ as in Theorem 64 is an optimal MD strategy in $\mathcal{M}$.

It remains to show how to find a pure optimal solution of $\mathcal{L}_{mp}$. To this end we exploit some fundamental properties of linear programs.

A linear program is in the standard (or equational) form if its set of constraints can be expressed as $A \cdot \bar{x} = \bar{b}$, $\bar{x} \ge 0$, where $\bar{x}$ is a vector of variables, $\bar{b}$ is a non-negative vector, and $A$ is a matrix of an appropriate dimension. In this notation, all the vectors are column vectors, i.e. $A$ has one column per each variable. Note that $\mathcal{L}_{mp}$ is a program in the standard form. A feasible solution $\bar{x}$ of such a program is basic if the columns of $A$ corresponding to variables whose value is positive in $\bar{x}$ form a linearly independent set of vectors. Since the maximal number of linearly independent columns equals the maximal number of linearly independent rows (a number called a *rank* of $A$), we know that each basic feasible solution has at most as many positive entries as there are rows of $A$.
The next two lemmas prove some fundamental properties of basic feasible solutions.

**Lemma 66** (Properties of basic feasible solutions: uniqueness). *Assume that a linear program in a standard form has two basic feasible solutions $\vec{x}, \vec{x}'$ such that both solutions have the same set of non-zero components, and the cardinality of this set equals the number of equality constraints in the program. Then $\vec{x} = \vec{x}'$.*

*Proof*. Write $A \cdot \vec{x} = \vec{b}$ the equational constraints of the LP. If $\vec{x}$ is a basic feasible solution, then it solves the equation $A_N \cdot \vec{x}_N = \vec{b}$, where $A_N$ ($N$ stands for ‘non-zero’) is obtained from $A$ by removing all columns corresponding to zero components of $\vec{x}$, and $\vec{x}_N$ is obtained from $\vec{x}$ by removing all zero components.

Since $\vec{x}$ has as many non-zero components as there are rows of $A$, it follows that $A_N$ is a square matrix. Since $\vec{x}$ is a basic solution, $A_N$ is regular (its columns are linearly independent) and $\vec{x} = A_N^{-1} \cdot \vec{b}$ is uniquely determined by $A_N$. Repeating the same argument for $\vec{x}'$ yields $\vec{x}' = A_N^{-1} \cdot \vec{b} = \vec{x}$. $\square$

**Lemma 67** (Properties of basic feasible solutions). *If a linear program in a standard form has an optimal solution, then it has also a basic optimal solution. Moreover, a basic optimal solution can be found in polynomial time.*

*Sketch*. The existence of a basic optimal solution is a well-known linear programming fact, e.g. the standard simplex algorithm works by traversing the set of basic feasible solutions until it finds an optimal one [Mat07]. For computing an optimal basic solution, we can use one of the polynomial-time interior-point methods for linear programming, such as the path-following method [Kar84, Gon92]. While these methods work by traversing the interior of the polyhedron of feasible solutions, they converge, in polynomial time, to a point that is closer to the optimal basic solution than to all the other basic solutions. By a process called *purification*, such a point can be then converted to the closest basic solution, i.e. to the optimal one [Gon92]. $\square$

**Theorem 65** (Complexity of computing optimal deterministic strategies in strongly connected mean payoff MDPs). *One can find, in polynomial time, an optimal deterministic strategy in a given strongly connected mean payoff MDP.*

*Proof*. First, we use Lemma 67 to find a basic optimal solution $\vec{x}$ of $\mathcal{L}_{mp}$. We check if it is pure. If yes, we are done. Otherwise, there is $v \in V$ and two distinct actions $a, b$ such that $\vec{x}_{(v,a)} > 0$ and $\vec{x}_{(v,b)} > 0$. Let $S = \{v \in V \mid \exists a \text{ s.t. } \vec{x}_{(v,a)} > 0\}$. By Corollary 17, we can partition $S$ into several subsets, each of which induces a strongly connected sub-MDP of $\mathcal{M}$. Let $Q$ be a class of this partition containing $v$. We have that the optimal mean payoff value of every vertex in $\mathcal{M}_Q$ is the same as in $\mathcal{M}$. This is because, as in the beginning of the proof of Theorem 62, we can transform $\vec{x}$ into another optimal solution of the same value as $\vec{x}$ which has non-zero entries only for components indexed by $(q, a)$ with $q \in Q$. All these computations can be easily implemented in polynomial time.

We argue that $Q$ is a strict subset of $V$. Indeed, assume that $Q = V$. Then $\vec{x}$ induces a randomized strategy $\sigma$ in $\mathcal{M}$. Moreover, since $\vec{x}$ is a basic solution, it has at most $|V| + 1$ positive entries, and since it is non-pure, it must have exactly $n + 1$ positive
entries, i.e. Lemma 66 is applicable to $\bar{x}$, since $\mathcal{L}_{mp}$ has exactly $|V| + 1$ constraints. Now we define a new strategy $\sigma'$ in $\mathcal{M}$ by slightly changing the behaviour in $v$. To this end, choose some $\varepsilon > 0$ and put $\sigma'(a | v) = \sigma(a | v) - \varepsilon$ and $\sigma'(b | v) = \sigma(b | v) + \varepsilon$; we choose $\varepsilon$ small enough so that both quantities are still non-zero. The chain $\mathcal{M}^{\sigma'}$ is still strongly connected. Now let $\bar{x}' = \Xi(\sigma')$. Then $\bar{x}'$ is a solution of $\mathcal{L}_{mp}$ which is still basic, with a set of non-zero components being the same as in $\bar{x}$. At the same time, $\bar{x}' \neq \bar{x}$, since $\sigma \neq \sigma'$ and $\Xi$ is a bijection (Lemma 64). But this is a contradiction with Lemma 66.

Hence, $\mathcal{M}_Q$ is a strict sub-MDP of $\mathcal{M}$ in which the value of every vertex is the same as in the original MDP. We can perform a recursive call of the aforementioned computation on $\mathcal{M}_Q$ (compute basic optimal solution of $\mathcal{L}_{mp}$, check purity, possibly extract and recurse on a sub-MDP). The depth of recursion is bounded by $|V|$, so the running time is polynomial. Since each sub-MDP obtained during the recursion is non-empty, and the size of the MDPs decreases, the recursion must eventually terminate with a basic optimal solution (in some sub-MDP $\mathcal{M}'$) that is pure. This yields a memoryless deterministic strategy in $\mathcal{M}'$ whose value is equal to the optimal value in $\mathcal{M}$. Such a strategy can be extended to whole $\mathcal{M}$ by solving almost sure reachability to $\mathcal{M}'$, as described in the previous sub-section. $\square$

## 5.5 End components

To solve mean payoff optimization in general MDPs, as well as general optimization problems for $\omega$-regular objectives, we need to introduce a crucial notion of an *end component*.

**Definition 14.** An end component (EC) of an MDP is any set $M$ of vertices having the following two properties:

* For each $u \in M$ there exists an action $a$ that is $M$-safe in $u$, i.e. satisfies that for all vertices $v$ with $\Delta(v|u,a) > 0$ it holds $v \in M$.

* For each pair of distinct vertices $u, v \in M$ there is a path from $u$ to $v$ visiting only the states from $M$.

In other words, $M$ is an EC of $\mathcal{M}$ if and only if $M$ is a closed set and the sub-MDP $\mathcal{M}_M$ is strongly connected.

From the player's point of view, the following property of ECs is important.

**Lemma 68.** Let $M$ be an EC and $v \in M$. Then there is an MD strategy $\sigma$ which, when starting in a vertex inside $M$, never visits a vertex outside of $M$ and at the same time ensures that with probability one, the vertex $v$ is visited infinitely often. Moreover, $\sigma$ can be computed in polynomial time.

*Proof.* From Theorem 54 we know that we can compute, in polynomial time, an MD strategy $\sigma$ in the sub-MDP $\mathcal{M}_M$ ensuring that $v$ is reached with probability 1 from any initial vertex in $M$. Indeed, this is because $M = W_{>0}(\mathcal{M}_M, \text{Reach}(v))$, due to the second condition in the definition of a MEC. Since $M$ is closed, this strategy never leaves $M$.
Whenever, the strategy leaves $v$, it guarantees that we return to $v$ with probability 1. Hence, for each $k$, the probability of event $V_k$ — visiting $v$ at least $k$ times — is 1. Since $V_{k+1} \subseteq V_k$, it follows that also the probability of $\bigcap_{i=1}^\infty V_i$ is equal to 1, which is what we aimed to prove. $\square$

The main reason for introducing ECs is that they are crucial for understanding the limiting behaviour of MDPs.

**Definition 15.** We denote by $\text{Inf}(\pi)$ the set of vertices that appear infinitely often along a play $\pi$.

**Lemma 69.** For any $v_0$ and $\sigma$ it holds $\mathbb{P}_{v_0}^{\sigma}(\{\pi \mid \text{Inf}(\pi) \text{ is an EC}\}) = 1$.

*Proof.* Assume the converse. Then in some MDP there is a set of vertices $X$ which is not an EC but satisfies $\mathbb{P}_{v_0}^{\sigma}(\text{Inf} = X) > 0$. Since $X$ is not an EC, there is a vertex $v \in X$ in which any (even randomized) choice of action results in leaving $X$ with probability at least $p_{\min} > 0$ (recall that $p_{\min}$ is the smallest non-zero edge probability in the MDP).

Let $\text{Stay}_k$ be the set of plays in $\{\text{Inf} = X\}$ which, from step $k$ on, never visit a vertex outside of $X$. Since $\{\text{Inf} = X\} = \bigcup_{i=1}^{\infty} \text{Stay}_i$, by union bound we get $\mathbb{P}_{v_0}^{\sigma}(\text{Stay}_k) > 0$ for some $k_0 \in \mathbb{N}$. Let $\text{Vis}_j$ denote the set of all plays in $\text{Stay}_k$ that visit $v$ at least $j$ times after the step $k_0$. Since $\text{Stay}_{k_0} \subseteq \{\text{Inf} = X\}$, we have $\text{Stay}_{k_0} \cap \text{Vis}_j = \text{Stay}_{k_0}$ for each $j$. But an easy induction shows that $\mathbb{P}_{v_0}^{\sigma}(\text{Stay}_{k_0} \cap \text{Vis}_{j+1}) \le \mathbb{P}_{v_0}^{\sigma}(\{\text{In}(\pi_{k_0}) \in X\}) \cdot p_{\min}^j$, since every visit to $v$ brings a risk at least $p_{\min}$ of falling out of $X$. The latter number converges to zero, so $\mathbb{P}_{v_0}^{\sigma}(\text{Stay}_{k_0}) = \lim_{j \to \infty} \mathbb{P}_{v_0}^{\sigma}(\text{Stay}_{k_0}) = \lim_{j \to \infty} \mathbb{P}_{v_0}^{\sigma}(\text{Stay}_{k_0} \cap \text{Vis}_{j+1}) = 0$, a contradiction. $\square$

In general, there can be exponentially many end components in an MDP (e.g. for a complete underlying graph and one action per edge, each subset of vertices is an EC). However, we can usually restrict to analysing maximal ECs.

**Definition 16.** An end component $M$ is a maximal end component (MEC) if no other end-component $M'$ is a superset of $M$. We denote by $\text{MEC}(M)$ the set of all MECs of $M$.

If two ECs have a non-empty intersection, then their union is again an EC. Hence, every EC is contained in exactly one MEC, and the total number of MECs is bounded by $|V|$, since two distinct MECs must be disjoint. Moreover, the decomposition of an MDP into MECs can be computed in polynomial time.

**Theorem 66.** The set of all MECs in a given MDP can be computed in polynomial time.

*Proof.* There are several known algorithms, a simple one is pictured in Algorithm 5.4. Each iteration goes as follows: we first take the underlying directed graph of the MDP and find its strongly connected components using some of the well-known polynomial algorithms [CLRS09]. We identify the bottom SCCs, i.e. those from which there is no outgoing edge in the graph. It is easy to see that each such SCC must form a MEC of $\mathcal{M}$, and conversely, each MDP has at least one MEC that is also a bottom SCC of its underlying graph. Moreover, for each such bottom SCC $B$ we compute the random
<caption>**Algorithm 5.4:** Algorithm for MEC decomposition of an MDP.</caption>

**Data:** An MDP $\mathcal{M}$
    List $\leftarrow \emptyset$; // List of found MECs
    $G \leftarrow (V, E)$; // The underlying graph of $\mathcal{M}$

**while** $G$ is non-empty do
    Decompose $G$ into strongly connected components;
    $R \leftarrow \emptyset$; // The list of vertices to remove.
    **foreach** bottom SCC $B$ of $G$ do
        $B$ is a MEC of $\mathcal{M}$, add it to List;
        $R \leftarrow R \cup (V \setminus W_{=1}(\mathcal{M}, \text{Safe}(V \setminus B)));$ // Schedule removal
        of vertices from which $B$ cannot be avoided in $\mathcal{M}$.
    remove vertices in $R$ from $G$ along with adjacent edges
    **return** List

attractor of $B$, i.e. the set of vertices of $\mathcal{M}$ from which $B$ cannot be avoided under any
strategy. To this end, we compute, in polynomial time, the almost-surely winning set
$W_{=1}(\mathcal{M}, \text{Safe}(V \setminus B))$ which is the largest largest (w.r.t. set inclusion) subset of $V$ from
which the player can ensure to stay in $V \setminus B$ forever (i.e. the complement of the random
attractor of $B$). The computation can be done in polynomial time by Corollary 13). No
vertex of the random attractor of $B$ can belong to a MEC different from $B$: such a MEC
would be disjoint from $B$ but the player could not force avoiding $B$ from within this
MEC, a contradiction with MEC being a closed set. Hence, all MECs of $\mathcal{M}$ which
are not a bottom SCC of $G$ are subsets of $W_{=1}(\mathcal{M}, \text{Safe}(V \setminus B)) \subseteq V \setminus R$, so we can
remove all vertices in $R$ from the graph and continue to the next iteration (note that
removing vertices in $R$ from $\mathcal{M}$ again yields a MDP, since the complement of $R$ is an
intersection of closed sets, and thus again a closed set). The main loop performs at
most $|V|$ iterations, which yields the polynomial complexity. $\square$

**5.6 Reductions to optimal reachability**

The MEC decomposition can be used to reduce several optimization problems (includ-
ing general mean payoff optimization) to optimizing reachability probability. Recall
that in the optimal reachability problem, we are given an MDP $\mathcal{M}$ (with coloured
vertices) and a colour Win $\in C$. The task is to find a strategy $\sigma$ that maximizes
$\mathbb{P}_{v_0}^{\sigma}(\text{Reach}(Win))$, the probability of reaching a vertex coloured by Win. The main
result on reachability MDPs, which we prove in Section 5.7, is as follows:

**Theorem 67 (Solving reachability MDPs).** In reachability MDPs, the value of each vertex is rational and computable in polynomial time. Moreover, we can compute, in polynomial time, a memoryless deterministic strategy that is optimal in every vertex.
**From optimal Büchi to reachability**

In Büchi MDPs, the vertices are assigned colours from the set $\{1,2\}$ and our aim is to
find a strategy maximizing $\mathbb{P}_{v_0}^{\sigma}(\text{Buchi})$, i.e. maximizing the probability that a vertex
coloured by 2 is visited infinitely often. We say that a MEC $\mathcal{M}$ of a Büchi MDP is *good*
if it contains a vertex coloured by 2.

**Theorem 68** (Solving Büchi MDPs). In Büchi MDPs, the value of each vertex is rational and computable in polynomial time. Moreover, we can compute, in polynomial time, a memoryless deterministic strategy that is optimal in every vertex.

*Proof.* Let $\mathcal{M}_b$ be a Büchi MDP and let $\mathcal{M}_r$ be a reachability MDP obtained from $\mathcal{M}_b$ by repainting each vertex belonging to a good MEC with the colour Win. Note that $\mathcal{M}_r$ can be computed in polynomial time by performing the MEC decomposition of $\mathcal{M}_b$ (Algorithm 5.4) and checking goodness of each MEC.

We prove that the value of each vertex in $\mathcal{M}_b$ is equal to the value of the corre-
sponding vertex in $\mathcal{M}_r$.

First, fix any $\sigma$ and $v_0$ (due to equality of underlying graphs, we can view these as
a strategy/initial vertex both in $\mathcal{M}_b$ and $\mathcal{M}_r$). By Lemma 69, the probability of visiting
infinitely often a vertex outside of a MEC is 0. Hence, the probability of visiting
infinitely often a vertex coloured by 2 (in $\mathcal{M}_b$) is the same as the probability of visiting
infinitely often a vertex coloured by 2 which belongs to (a necessarily good) MEC,
which is in turn bounded from above by the probability that $\sigma$ visits (in $\mathcal{M}_r$) a vertex
coloured by Win.

Conversely, let $\sigma^*$ be the MD reachability-optimal strategy in $\mathcal{M}_r$ (which exists by Theorem 67). We construct a strategy $\sigma$ in $\mathcal{M}_b$ which achieves, in every vertex, the same Büchi-value as the reachability value achieved in that vertex by $\sigma^*$ in $\mathcal{M}_r$. Outside of any good MEC, $\sigma$ behaves exactly as $\sigma^*$. Inside a good MEC $\mathcal{M}$, $\sigma$ behaves as the MD strategy from Lemma 68, ensuring that some fixed vertex in $\mathcal{M}$ of colour 2 is almost-surely visited infinitely often. Since $\sigma$ is stitched together from MD strategies on non-overlapping domains, it is memoryless deterministic and it ensures that once a good MEC is reached, the Büchi condition is satisfied almost-surely.

The construction of $\sigma$ in the aforementioned paragraph is effective: given the opti-
mal strategy $\sigma^*$ for reachability, $\sigma$ can be constructed in polynomial time. $\square$

**From optimal parity to optimal reachability**

In parity MDPs, the vertices are labelled by colours from the set $\{1, \dots, d\}$ (w.l.o.g. we
stipulate that $d \le |V|$) and the goal is to find a strategy maximizing $\mathbb{P}_{v_0}^{\sigma}(\text{Parity})$, i.e.
maximizing the probability that the largest priority appearing infinitely often along a
play is even.

**Theorem 69** (Solving parity MDPs). In Parity MDPs, the value of each vertex is rational and computable in polynomial time. Moreover, we can compute, in polynomial time, a memoryless deterministic strategy that is optimal in every vertex.

*Proof.* Let $\mathcal{M}_p$ be a parity MDP. We will proceed similarly to Theorem 68, construct-
ing a reachability MDP $\mathcal{M}_r$ with the same underlying graph as $\mathcal{M}_p$.
To this end, let $\mathcal{M}_i$ be the largest sub-MDP of $\mathcal{M}_p$ containing only the vertices of priority $\le i$. Formally, we set $V_i = W_{=1}(\mathcal{M}_p, \text{Safe}(c^{-1}({i+1, \dots, d})))$ and define $\mathcal{M}_i$ to be the sub-MDP induced by $V_i$ (note that $\mathcal{M}_i$ might be empty). We say that a vertex of $\mathcal{M}_p$ is $i$-good if it is contained in some MEC $\mathcal{M}$ of $\mathcal{M}_i$ such that the largest vertex priority inside $\mathcal{M}$ is equal to $i$. We say that a vertex is even-good if it is $i$-good for some even $i$. We set up a reachability MDP $\mathcal{M}_r$ by taking $\mathcal{M}_p$ and re-colouring each its even-good vertex with colour Win. To do this, we need to compute, for each even priority $i$, the MDP $\mathcal{M}_i$ and its MEC-decomposition. This can be done in polynomial time (Algorithm 5.4).

We again prove that the value of every vertex in $\mathcal{M}_p$ is equal to the value of the corresponding vertex in $\mathcal{M}_r$.

Let $\sigma$ and $v_0$ be arbitrary. By Lemma 69, $\mathbb{P}_{\mathcal{M}_{p,v_0}}^{\sigma}(\text{Parity})$ is equal to the probability that $\text{Inf}(\pi)$ is an EC in which the largest priority is even. But each such EC is also an EC of some $\mathcal{M}_i$ with even $i$, and thus is also contained in a MEC of a $\mathcal{M}_i$ in which the largest priority is $i$. Hence, $\mathbb{P}_{\mathcal{M}_{p,v_0}}^{\sigma}(\text{Parity}) \le \mathbb{P}_{\mathcal{M}_{r,v_0}}^{\sigma}(\text{Reach}(\text{Win}))$.

Conversely, let $\sigma^*$ be the MD reachability-optimal strategy in $\mathcal{M}_r$. We construct an MD strategy $\sigma$ in $\mathcal{M}_p$ as follows: in a vertex $v$ which is not even-good, $\sigma$ behaves as $\sigma^*$. For a vertex $v$ that is even-good, we identify the smallest even $i$ such that $v$ is $i$-good. This means that $v$ belongs to some MEC $\mathcal{M}$ of $\mathcal{M}_i$ in which the largest priority is $i$. By Lemma 68, we can compute, in polynomial time, an MD strategy $\sigma_M$ which ensures that the largest-priority vertex in $(\mathcal{M}_i)_M$ is visited infinitely often, and we set $\sigma(v)$ to $\sigma_M(v)$. Note that given $\sigma^*$, the strategy $\sigma$ can be constructed in polynomial time. It remains to show that $\mathbb{P}_{\mathcal{M}_{p,v_0}}^{\sigma}(\text{Parity}) \ge \mathbb{P}_{\mathcal{M}_{r,v_0}}^{\sigma^*}(\text{Reach}(\text{Win}))$.

By the construction of $\sigma$, once we reach a vertex which is $i$-good for some even $i$, all the following vertices will be $j$-good for some even $j \le i$. From this and from Lemma 69 it follows that $\mathbb{P}_{\mathcal{M}_{r,v_0}}^{\sigma^*}(\text{Reach}(\text{Win}))$ is equal to the probability that $\sigma$ produces a play $\pi$ with the following property: $\exists i$ even such that all but finitely many vertices on $\pi$ are $i$-good but are not $j$-good for any even $j < i$. This can be in turn rephrased as the probability that $\text{Inf}(\pi)$ is an EC whose all vertices are $i$-good for some even $i$ but none of them is $j$-good for an even $j < i$; we call such an EC $i$-definite. But within such an EC, $\sigma$ forever behaves as $\sigma_M$ for some MEC $\mathcal{M}$ of $\mathcal{M}_i$ in which the maximal priority is $i$. Hence, once an $i$-definite EC is reached, the strategy almost-surely ensures that priority $i$ is visited infinitely often and ensures that no larger priority is ever visited. It follows that $\mathbb{P}_{\mathcal{M}_{r,v_0}}^{\sigma^*}(\text{Reach}(\text{Win})) = \mathbb{P}_{\mathcal{M}_{p,v_0}}^{\sigma}(\text{inf}(\pi)$ is $i$-definite for even $i) = \mathbb{P}_{\mathcal{M}_{p,v_0}}^{\sigma}(\text{Parity}). \quad \square$

## From general mean payoff to optimal reachability

We already know how to solve strongly connected mean payoff MDPs. We now combine this result with MEC decomposition to reduce the general (not strongly connected) mean payoff optimization to MDP reachability.

We start with a strengthening of Theorem 63.

**Lemma 70.** Let $\mathcal{M}$ be a strongly connected mean payoff MDP and $r^*$ the value of each of its vertices. Then, for each $\sigma$ and $v_0$ we have $\mathbb{P}_{v_0}^{\sigma}(\text{MeanPayoff}^- > r^*) = 0$.
**Proof.** Assume that the statement is not true. Then there exist $\sigma, v_0$ as well as numbers $\varepsilon, \delta > 0$ and $n_0 \in \mathbb{N}$ s.t. the probability of the following set of plays $X_{\varepsilon,n_0}$ is at least $\delta$: a play $\pi$ belongs to $X_{\varepsilon,n_0}$ if for every $n \ge n_0$ it holds $\frac{1}{n}\sum_{i=0}^{n-1}c(\pi_i) \ge x^* + \varepsilon$. We construct a new strategy $\sigma'$, which proceeds in a series of episodes. Every episode starts in $v_0$, and for the first $n_0$ steps of the, episode $\sigma'$ mimics $\sigma$. After that, it checks, in every step $n$, whether the payoff accumulated since the start of the episode is at least $n \cdot (r^* + \varepsilon)$. If this holds, we mimic $\sigma$ for one more step. If the inequality is violated, we immediately ‘restart’, i.e. return to $v_0$ (can be performed with probability 1 due to the MDP being strongly connected) and once in $v_0$, start a new episode which mimics $\sigma$ from the beginning. By our assumption, the probability of not performing a reset in a given episode is at least $\delta > 0$. Hence, with probability 1 we witness only finitely many resets, after which we produce a play whose suffix has mean payoff at least $r^* + e$. By prefix independence of mean payoff (Theorem 63), $\mathbb{E}_{v_0}[\text{MeanPayoff}^-] \ge r^* + \varepsilon$, a contradiction. $\square$

We will need to strengthen the previous lemma so that it applies not only to strongly connected MDPs, but also to MECs in some larger MDPs. The strengthening is performed in the following two lemmas. The first lemma says that once we exit a MEC, with some positive probability we will never return.

**Lemma 71.** Let $M$ be a MEC of an MDP $\mathcal{M}$ and let $v \in M$, $a \in A$ be such that $a$ is not $M$-safe in $v$. Then there exists $t$ s.t. $\Delta(t | v, a) > 0$ and $t \notin W_{=1}(\mathcal{M}, \text{Reach}(M))$.

**Proof.** Assume that $a$ is not $M$-safe in $v$ and that all $t$'s with $\Delta(t | v, a) > 0$ belong to $W_{=1}(\mathcal{M}, \text{Reach}(M))$. Fix the MD strategy $\sigma$ which is almost-surely winning for reaching $M$ from each vertex of $W_{=1}(\mathcal{M}, \text{Reach}(M))$ (Theorem 54). For each $t$ s.t. $\Delta(t | v, a) > 0$, let $M_t$ denote the set of vertices which can be (with a positive probability) visited under $\sigma$. Put $M' = M \cup (\bigcup_{t \in V, \Delta(t|v,a)>0} M_t)$. Then $M'$ is closed, since $M$ is closed and since for every $u$ in some $M_t$ there exists an action (the one selected by $\sigma$ for $u$) under which we surely stay in $M_t$. Moreover, the $M'$-induced sub-MDP is strongly connected: each $t$ with $\Delta(t | v, a) > 0$ is reachable from within $M$ (through $v$) and thus each vertex in some $M_t$ is reachable from $M$. In turn, from each vertex in some $M_t$ (where $\Delta(t | v, a) > 0$) we can reach $M$ without leaving $M_t$, due to the definition of $\sigma$. Hence, $M'$ is a MEC which strictly contains $M$, a contradiction with the maximality of $M$. $\square$

Given a play $\pi$ and strategy $\sigma$, we define a *slice* of $\sigma$ as a strategy $\sigma_{\pi_-}$ such that for each $\pi'$ starting in last($\pi$) it holds $\sigma_{\pi_-}(\pi') = \sigma(\pi\pi')$, while on other plays $\sigma_{\pi_-}$ just mimics $\sigma$.

**Lemma 72.** Let $M$ be a MEC of $\mathcal{M}$ and $r^*$ the mean payoff value of every vertex in the strongly connected sub-MDP induced by $M$. Then the set $E$ of all plays that have $\text{Inf}(\pi) \subseteq M$ and at the same time mean payoff greater than $r$ has probability zero under any strategy $\sigma$.

**Proof.** Assume, for contradiction, that there is a strategy $\sigma$ and $\delta > 0$ such that the probability of $E$ under $\sigma$ is at least $\delta$. Note that we do not immediately have a contradiction with Lemma 70, since $\sigma$ might leave $M$ (and then return back).
We say that a play $\pi$ cheats in step $i$ if it is inside $M$ in $i$-th step and outside of $M$ in the next step (which can only be caused by an $M$-unsafe action being played). From Lemma 71 we have that there is $p > 0$ s.t. upon every exit from $M$ we return with probability at most $(1-p)$. Hence, the probability that a play cheats infinitely often is 0. It follows that there is $k \in \mathbb{N}$ s.t. $\mathbb{P}_{v_0}^{\sigma}(\pi$ cheats after $\ge k$ steps) $\le (\delta \cdot p_{\min})/4$, where $p_{\min}$ is the smallest non-zero edge probability in $\mathcal{M}$.

Whenever we are in some $v \in M$ and play an action that is not $M$-safe in $v$, this results into a cheat with probability at least $p_{\min}$. Thus, the total probability that this happens after at least $k$ steps, i.e. the quantity

$$q = \sum_{i \ge k} \sum_{v \in M} \sum_{a \text{ not } M\text{-safe in } v} \mathbb{E}_{v_0}^{\sigma} [A_{a,i}^{\sigma} \cdot \mathbf{1}_{\text{Out}(\pi_i)=v}], \quad (5.11)$$

is bounded by $\mathbb{P}_{v_0}^{\sigma}(\pi$ cheats after more than $k$ steps)/$p_{\min} \le \delta/4$.

Let's go back to $E$ now. On each play in $E$ there is a step $i$ from which on the play stays in $M$ forever: we say that the play is $i$-definite and we denote by $E_k$ the set of all $i$-definite plays in $E$. By union bound, there is $\ell \in \mathbb{N}$, $\ell \ge k$ s.t. $\mathbb{P}_{v_0}^{\sigma}(E_\ell) \ge \delta/2$.

We define a new strategy $\sigma'$ as follows: on each play prefix, $\sigma'$ by default mimics $\sigma$, except for the case when at least $\ell$ steps have elapsed, the current vertex $v$ is in $M$, and $\sigma$ prescribes to play, with positive probability, an action which is not $M$ safe in $v$. In such a case, $\sigma$ is overridden and we play any action that is $M$-safe in $v$ instead (after which we return to simulating $\sigma$, until the override kicks in again). The probability that such an override happens is bounded by the quantity $q$ from Equation (5.11), and hence by $\delta/4$. Since $\mathbb{P}_{v_0}^{\sigma}(E_\ell) \ge \delta/2$, at least half the measure of $E_\ell$ stays untouched by the overrides; hence $\mathbb{P}_{v_0}^{\sigma'}(E_\ell) \ge \delta/4$.

We are ready to apply the final argument. There are only finitely many plays of length $\ell$. Hence, by union bound, there is a play $\pi$ of length $\ell$ such that $\mathbb{P}_{v_0}^{\sigma'}(E_\ell \cap \text{Cyl}(\pi)) > 0$. Consider the strategy $\sigma'_{\pi_-}$. Starting in last($\pi$), we have that $\sigma'_{\pi_-}$ never leaves $M$, due to the overrides in $\sigma'$. Hence, $\sigma'_{\pi_-}$ can be seen as a strategy in the strongly connected MDP $\mathcal{M}_M$. Now consider the set $E' = \{\pi' | \pi' \ni \pi'' \in E \text{ s.t. } \pi'' = \pi\pi'\}$. Then $\mathbb{P}_{\text{last}(\pi)}^{\sigma'_{\pi_-}}(E') = \mathbb{P}_{v_0}^{\sigma'}(E_\ell \cap \text{Cyl}(\pi)) > 0$; but due to the prefix independence of mean payoff, all plays in $E'$ have payoff $> r^*$, a contradiction with Lemma 70. $\square$

**Theorem 70.** In mean payoff MDPs, the value of each vertex is rational and computable in polynomial time. Moreover, we can compute, in polynomial time, a memoryless deterministic strategy that is optimal in every vertex.

*Proof.* First, note that we can w.l.o.g. restrict to MDPs in which each edge is coloured by a number between 0 and 1. To see this, let $\mathcal{M}$ be an MDP and $a, b$ any two numbers, with $a$ non-negative. We can construct an MDP $\mathcal{M}'$ by re-colouring each edge $(u, v)$ of $\mathcal{M}$ with colour $a \cdot c(u, v) + b$, where $c$ is the original colouring in $\mathcal{M}$. It is then easy to see that for each strategy $\sigma$ it holds $\mathbb{E}_{\mathcal{M},v_0}^{\sigma}[\text{MeanPayoff}^-] = (\mathbb{E}_{\mathcal{M}',v_0}^{\sigma'}[\text{MeanPayoff}^-]/a) - b$, so a strategy optimizing the mean payoff in $\mathcal{M}'$ is also optimal in $\mathcal{M}$. Hence, we always can re-scale the colouring into the unit interval while preserving the optimization criterion.

So now let $\mathcal{M}_{mp}$ be a mean payoff MDP with edge-colouring $c$. We construct, in polynomial time, a new reachability MDP $\mathcal{M}_r$ as follows: first, we compute the MEC
decomposition of $\mathcal{M}_{mp}$ (Algorithm 5.4). Let $M_1, \dots, M_k$ be all the resulting MECs. For each MEC $M_i$ we compute the optimal mean payoff value $r_i^*$ in the sub-MDP induced by $M_i$ (which is shared by all vertices of this sub-MDP, by Theorem 63), along with the corresponding memoryless deterministic optimal strategy. We already know how to do this in polynomial time (Theorems 64 and 65). Now we add new vertices $v_{good}$, $v_{bad}$, both with self loops, and edges incoming to these vertices from each vertex that belongs to some MEC of $\mathcal{M}_{mp}$. The vertex $v_{good}$ is the only vertex coloured by Win in $\mathcal{M}_r$. Finally, we add a new action fin which behaves as follows: For each vertex $v$ belonging to a MEC $M_i$ we set $\Delta(v_{good} | v, fin) = r_i^*$ and $\Delta(v_{bad} | v, fin) = 1 - r_i^*$. In a non-MEC vertex $v$, we put $\Delta(v, fin) = \Delta(v, a)$ for some $a \in A$, $a \neq fin$, so that no new behaviour is introduced in these vertices.

We show that for any original vertex (i.e. all vertices but $v_{good}, v_{bad}$) the optimal values in both MDPs are the same and the optimal strategies are easily transferable from one MDP to the other.

First, let $\sigma$ be an $\varepsilon$-optimal strategy in $\mathcal{M}_{mp}$. We have

$$ 
\begin{aligned}
\mathbb{E}_{v_0}^{\sigma}[\text{MeanPayoff}^{-}] &= \sum_{i=1}^{k} \mathbb{E}_{v_0}^{\sigma}[\text{MeanPayoff}^{-} \cdot \mathbf{1}_{\text{Inf} \subseteq M_i}] \\
&\le \sum_{i=1}^{k} \mathbb{E}_{v_0}^{\sigma}[r_i^* \cdot \mathbf{1}_{\text{Inf}=M_i}] \\
&= \sum_{i=1}^{k} r_i^* \cdot \mathbb{P}_{v_0}^{\sigma}(\text{Inf} = M_i)
\end{aligned}
$$

Here the first equation follows from Lemma 69 and the subsequent inequality from Lemma 72. Moreover, for each $i$ there is a number $n_0^i$ such that the probability of all plays that stay inside $M_i$ in all the steps from $n_0^i$ to infinity is at least $\mathbb{P}_{v_0}^{\sigma}(\text{Inf} \subseteq M_i) - \frac{\varepsilon}{k}$. Let $n_0 = \max_{1 \le i \le k} n_0^i$.

We construct a reachability strategy $\sigma_r$ which mimics $\sigma$ for the first $n_0$ steps. After $n_0$ steps it performs a switch: if the current vertex is in some $M_i$ we immediately play the action fin, otherwise we start to behave arbitrarily. We have

$$ 
\begin{aligned}
\mathbb{P}_{v_0}^{\sigma_r}(\text{Reach}(\text{Win})) &\ge \sum_{i=1}^{k} r_i^* \cdot \mathbb{P}_{v_0}^{\sigma_r}(\text{last}(\pi_{\le n_0}) \in M_i) \\
&\ge \sum_{i=1}^{k} r_i^* \cdot \mathbb{P}_{v_0}^{\sigma}(\text{Inf} \subseteq M_i) - \varepsilon \\
&\ge \mathbb{E}_{v_0}^{\sigma}[\text{MeanPayoff}^{-}] - \varepsilon.
\end{aligned}
$$

This is the last equality shown in the previous paragraph. Since $\sigma$ is $\varepsilon$-optimal for mean payoff, $\mathbb{P}_{v_0}^{\sigma_r}(\text{Reach}(\text{Win}))$ is at most $2\varepsilon$ away from the mean payoff value of $v$. Since $\varepsilon > 0$ was chosen arbitrarily, we get that the reachability value in $\mathcal{M}_r$ is at least as large as the mean payoff value in $\mathcal{M}_{mp}$.

Conversely, let $\sigma^*$ be the optimal MD strategy in $\mathcal{M}_r$. We say that $\sigma^*$ ends in a vertex $v$ if $\sigma^*(v) = fin$. We can assume that if $\sigma^*$ ends in some $v \in M_i$ then it ends in all vertices of $M_i$. This is because whenever $\sigma^*$ ends in some vertex $v \in M_i$, the reachability value of $v$ must be equal to $r_i^*$, otherwise playing fin would not be optimal here. But the optimal reachability value in every vertex of a given MEC is the same (due to Lemma 68), so if playing fin is optimal in some vertex of $M_i$, it is optimal in all such vertices. Now we can define an MD strategy $\sigma_{mp}$ in $\mathcal{M}_{mp}$ to initially mimic $\sigma^*$, and upon encountering any MEC $M_i$ in which $\sigma^*$ ends, immediately switch to the MD strategy that is optimal in the mean payoff sub-MDP $\mathcal{M}_i$. We have $\mathbb{E}_{v_0}^{\sigma_{mp}}[\text{MeanPayoff}^{-}] = \sum_{i=1}^{k} \mathbb{P}_{v_0}^{\sigma^*}(\text{end in } M_i) \cdot r_i^* = \mathbb{P}_{v_0}^{\sigma^*}(\text{Reach}(\text{Win}))$. Since $\sigma^*$
as well as the optimal strategies in all $M_i$ can be computed in polynomial time (Theorems 65 and 67), we get the result. $\square$

## 5.7 Optimal reachability

In this final section, we prove Theorem 67. The proof bears many similarities to the methods for discounted MDPs, hence we only sketch the process and point out the key differences. Throughout the section we assume that targets are sinks, i.e. that a vertex coloured by Win has only a self loop as the single outgoing edge. Modifying an MDP to accommodate this does not influence reachability probabilities in any way.

Consider the reachability operator $\mathcal{R}: [0, 1]^V \to [0, 1]^V$ such that for $\vec{y} = \mathcal{R}(\vec{x})$ it holds

$$ \vec{y}_v = \begin{cases} \max_{a \in A} \sum_{u \in V} \Delta(u | v, a) \cdot x_u & c(v) \neq \text{Win} \\ 1 & c(v) = \text{Win.} \end{cases} $$

**Lemma 73.** For each initial vector $\vec{x}$, the limit $\lim_{k \to \infty} \mathcal{R}^k(\vec{x})$ exists. Moreover, if $\vec{x} \le \mathcal{R}(\vec{x})$, then the limit is equal to the least fixed point of $\mathcal{R}$ that is greater than or equal to $\vec{x}$; if $\mathcal{R}(\vec{x}) \le \vec{x}$, then the limit is equal to the greatest fixed point of $\mathcal{R}$ that is less than or equal to $\vec{x}$.

*Proof.* The existence of the limit follows from the monotonicity of $\mathcal{R}$. In addition, it can be easily checked that the set $[0, 1]^V$ is a directed complete partial order and that $\mathcal{R}$ is a Scott-continuous operator on this set. Hence, the result follows from the Kleene's theorem (see also Tarski-Kantorovich principle). $\square$

We denote by $\text{Reach}^k(\text{Win})$ the set of all plays that reach Win within the first $k$ steps. Clearly, for each $\sigma$ and $v_0$ we have $\lim_{k \to \infty} \mathbb{P}_{v_0}^{\sigma}(\text{Reach}^k(\text{Win})) = \mathbb{P}_{v_0}^{\sigma}(\text{Reach}(\text{Win}))$.

**Lemma 74.** For each $k \in \mathbb{N}$ and $v \in V$, $\mathcal{R}^k(\vec{0})_v = \sup_{\sigma} \mathbb{P}_v^{\sigma}(\text{Reach}^k(\text{Win}))$. In particular, the vector $\vec{x}^* = \lim_{k \to \infty} \mathcal{R}^k(\vec{0})$ is the least fixed point of $\mathcal{R}$ and it is equal to the vector of reachability values.

*Proof.* The first part can be proved by a straightforward induction, the second part follows by Lemma 73 and a simple limiting argument. $\square$

Similarly to Definition 11 we say that an action $a$ is $\vec{x}$-safe in $v$ if it holds that $a = \arg\max_{a' \in A} \sum_{u \in V} \Delta(u | v, a') \cdot \vec{x}_u$. Recall that a strategy $\sigma$ is $\vec{x}$-safe if all actions selected in a vertex with non-zero probability are $\vec{x}$-safe in that vertex.

**Lemma 75.** Let $\vec{x}^*$ be as in Lemma 74. Next, let $Z^{(n)}$ be a random variable which for a given time step $n$ looks at the current vertex $v$ after $n$ steps and returns the value $\vec{x}_v^*$. Then for every $\vec{x}^*$-safe strategy $\sigma$ it holds $\mathbb{E}_{v_0}^{\sigma}[Z^{(n)}] = \vec{x}_v^*$. Moreover, it holds $\mathbb{E}_{v_0}^{\sigma}[Z^{(n)} \cdot \mathbf{1}_{c(Out(\pi_n))=Win}] = \mathbb{P}_{v_0}^{\sigma}(\text{Reach}^n(\text{Win}))$.

*Proof.* By an easy induction on $n$, using the fact that target states are sinks. $\square$
Now an analogue of Lemma 53 does not hold for reachability: a strategy playing
only $\bar{x}^*$-safe actions might not be optimal (indeed, it might not reach Win at all). In-
stead, we proceed as follows: Let $\mathcal{M}^*$ be an MDP in which we 'disable', in each state
$v$, all actions that are not $\bar{x}^*$-safe in $v$. This can be formally done by adding a new
non-target sink vertex *sink*, an edge from each original vertex to *sink*, and stipulating
that each action *a* that is disabled in a vertex *v* chooses, when played in *v* in $\mathcal{M}^*$, the
edge leading to *sink* with probability 1.

**Lemma 76.** The vectors of reachability values val($\mathcal{M}$) and val($\mathcal{M}^*$) are equal. In particular, $W_{>0}(\mathcal{M}, \text{Reach}(\text{Win})) = W_{>0}(\mathcal{M}^*, \text{Reach}(\text{Win}))$.

*Proof.* Let $\bar{x}^*$ again denote the vector of optimal values in $\mathcal{M}$. If all actions in $\mathcal{M}$ are $\bar{x}^*$-safes, then the lemma clearly holds. Otherwise there is some $\delta \in (0, 1)$ such that for each action $a$ that is not $\bar{x}^*$-safe in some vertex $v$ it holds $\sum_{u \in V} \Delta(u | v, a) \cdot \bar{x}_u \le \bar{x}_v^* - \delta$.

Let $\epsilon \in (0, \delta)$ be arbitrary and fix an $\epsilon$-optimal strategy $\sigma$ in $\mathcal{M}$. We will show that there is a $(2\epsilon/\delta)$-optimal strategy $\sigma'$ which only uses $\bar{x}^*$-safe actions. Since $\epsilon$ can be chosen arbitrarily close to 0, this shows that $\bar{x}^*$-safe strategies can get arbitrarily close to the value, hence $\text{val}(\mathcal{M}^*) = \text{val}(\mathcal{M})$.

The strategy $\sigma'$ initially mimics $\sigma$ up to the first point in time when an action
that is not $\bar{x}^*$-safe in the current vertex is to be selected. At this point $\sigma'$ switches to
behave as any $\bar{x}^*$-safe strategy. To analyse the value achieved by $\sigma'$, we need to bound
the probability of the event *NonSafe* that the switch occurs. By the same reasoning
as in Lemma 75, we can show that for all *n* it holds $\mathbb{P}_{v_0}^{\sigma}(\text{Reach}^n(\text{Win})) \le \mathbb{E}_{v_0}^{\sigma}[Z^{(n)}] \le$
$\bar{x}_{v_0}^* - \delta \cdot \mathbb{P}_{v_0}^{\sigma}(\text{NonSafe}^{(n)})$, where *NonSafe*$(n)$ is the probability that a switch occurs in the
first *n* steps. By taking *n* to the limit we get $\mathbb{P}_{v_0}^{\sigma}(\text{Reach}(\text{Win})) \le \bar{x}_{v_0}^* - \delta \cdot \mathbb{P}_{v_0}^{\sigma}(\text{NonSafe})$.
At the same time $\bar{x}_{v_0}^* - \epsilon \le \mathbb{P}_{v_0}^{\sigma}(\text{Reach}(\text{Win}))$. Combining these two inequalities yields
$\mathbb{P}_{v_0}^{\sigma}(\text{NonSafe}) \le \frac{\epsilon}{\delta}$. Now clearly $\mathbb{P}_{v_0}^{\sigma'}(\text{Reach}(\text{Win})) \ge \bar{x}_{v_0}^* - \epsilon - \mathbb{P}_{v_0}^{\sigma'}(\text{NonSafe}) \ge \bar{x}_{v_0}^* -$
$\epsilon - \epsilon/\delta \ge \bar{x}_{v_0}^* - 2\epsilon/\delta$. $\square$

**Lemma 77.** Given the vector $\bar{x}^*$ of optimal reachability values, we can compute, in polynomial time, the optimal MD reachability strategy in $\mathcal{M}$.

*Proof.* Given $\bar{x}^*$, we construct the MDP $\mathcal{M}^*$ and compute the winning strategy $\sigma$ for positive reachability in $\mathcal{M}^*$. We already know that $\sigma$ can be taken memoryless and computed in polynomial time (Theorem 53). We claim that $\sigma$ is an optimal reachability strategy in $\mathcal{M}$. By Lemma 76 it suffices to show that $\sigma$ is optimal in $\mathcal{M}^*$. Let $W$ be the winning region for positive reachability in $\mathcal{M}^*$. Since $\sigma$ is memoryless, with probability 1 we reach either Win or a vertex of value 0 (from which we cannot return to $W$ anymore); in other words, for almost all plays $\pi$ we have that $\mathbf{1}_{\text{Out}(\pi_n) \in W}$ eventually equals $\mathbf{1}_{c(\text{Out}(\pi_n))=\text{Win}}$. Hence, using Lemma 75 we get $\bar{x}_{v_0}^* = \lim_{n \to \infty} \mathbb{E}_{v_0}^{\sigma}[Z^{(n)}] = \mathbb{E}_{v_0}^{\sigma}[\lim_{n \to \infty} Z^{(n)}] = \mathbb{E}_{v_0}^{\sigma}[\lim_{n \to \infty} Z^{(n)} \cdot \mathbf{1}_{\text{Out}(\pi_n) \in W}] = \mathbb{E}_{v_0}^{\sigma}[\lim_{n \to \infty} Z^{(n)} \cdot \mathbf{1}_{c(\text{Out}(\pi_n))=\text{Win}}] = \mathbb{P}_{v_0}^{\sigma}(\text{Reach}(\text{Win}))$. Here, the third equality holds since $\bar{x}_v^*$ is zero for $v \notin W$, while the swapping of expectations and limits can be performed due to the dominated convergence theorem. $\square$

To finish the proof of Theorem 67, it remains to prove that the vector of optimal
values $\bar{x}^*$ can be computed in polynomial time. We again employ linear programming
and define the linear program $\mathcal{L}_{reach}$ with variables $x_v, v \in V$.
$$
\begin{array}{ll}
\text{minimise} & \sum_{v \in V} x_v \\
\text{subject to} & x_v = 1 & \text{if } c(v) = \text{Win} \\
& x_v = 0 & \text{if } v \notin W_{>0}(\mathcal{M}, \text{Reach}(\text{Win})) \\
& x_v \ge \sum_{u \in V} \Delta(u | v, a) \cdot x_u & \text{for all other } v \in V, a \in A.
\end{array}
$$

**Lemma 78.** The linear program $\mathcal{L}_{reach}$ in Section 5.7 has a unique optimal solution $\bar{\bar{x}}$
such that $\bar{\bar{x}} = \bar{x}^*$.

*Proof.* Clearly $\bar{x}^*$ is a feasible solution of $\mathcal{L}_{reach}$. Similarly to Lemma 59 we prove that each feasible solution $\bar{x}$ of $\mathcal{L}_{reach}$ satisfies $\bar{x} \ge \bar{x}^*$. We can proceed analogously to Lemma 59, just replacing the operator $\emptyset$ with $\mathcal{R}$. The proof can be mimicked up to the point where we get that $\lim_{k \to \infty} \mathcal{R}^k(\bar{x}) \le \bar{x}$ (the limit exists by Lemma 73). Since $\mathcal{R}(\bar{x}) \le \bar{x}$ for each feasible solution $\bar{x}$, from Lemma 73 we get that the limit is a fixed point of $\mathcal{R}$, and in hence it is greater or equal to the least fixed point of $\mathcal{R}$, i.e. $\bar{x}^*$ (Lemma 74). Hence, also $\bar{x} \ge \lim_{k \to \infty} \mathcal{R}^k(\bar{x}_0) \ge \bar{x}^*$. $\square$

Lemmata 77 and 78 give us Theorem 67.

**Bibliographic references**

There is a broad field of study related to Markov decision processes, with a history
going as far as 1950's [Bel57]. It is beyond the scope of this chapter to provide a com-
prehensive overview of the related literature. Nonetheless, in this section we provide
pointers to the most significant works connected to our techniques as well as to works
that can serve as a starting point for a further study.

One of the most widely used references for MDP-related research is the textbook
by Puterman [Put05]. The textbook views MDPs from an operations research point-
of-view, focusing on finite-horizon, discounted, total-reward, and average reward (an
alternative name for mean payoff) objectives. Regular objectives fall outside of the
book's focus, though reachability can be viewed as a special case of the "positive
bounded total reward" objectives studied in the book. An in-depth study of the textbook
will impart to its reader the knowledge of many useful techniques for MDP analysis,
though a reader who is a newcomer to MDPs might feel somewhat intimidated by its
sheer volume and generality. In this chapter, we follow Puterman's exposition mainly
in the discounted payoff, albeit in a rather condensed form.

For mean payoff MDPs, [Put05] follows similar blueprint as in the discounted case: first characterizing the optimal values via a suitable optimality equation and then deriving the value iteration, strategy improvement, and linear programming methods from this characterization. We use the linear programming as our foundational stone, focusing on the relationship between strategies and feasible solutions of the program. We note that value and strategy iteration for mean payoff MDPs come with super-polynomial lower bounds, see, e.g. [Fea10a, Fea10b], or [Put05], where it is shown that strategy improvement converges at least as fast as value iteration.

Also, [Put05] makes the initial analysis of mean payoff MDPs in the context of unichain MDPs, and then extends to arbitrary MDPs, with strongly connected MDPs
treated as a special case of the latter. While unichain is an important theoretical concept, in the context of formal methods and automata it is preferable to work with strongly connected MDPs. We also note that all the results in the mean payoff sections hold also for MeanPayoff$^+$. Almost all of the proofs are the same, with an important exception of Corollary 15, where Fatou's lemma cannot be used to prove that p-Payoff($v_0$, $\sigma$) $\le$ s-Payoff($v_0$, $\sigma$). Instead, we could use martingale techniques here. Martingales are an important concept in probability theory [Wil91], with applications e.g. in analysis of infinite-state MDPs and stochastic games [BBEK11]. We can use martingales to strengthen Lemma 61 by showing that the probability of $\sum_{i=0}^{n-1} c(\pi_i) \ge \sqrt{n} \cdot E_{v_0}^{\sigma} [\sum_{i=0}^{n-1} c(\pi_i)]$ converges (with an exponential rate of decay) to 0 as $n \to \infty$, which allows us to prove the required bound for lim sup.

The notion of a (M)EC as well as many techniques we use in the EC section are due to de Alfaro, whose thesis [dA97] details the evolution of the concept and its relation to similar notions. The algorithm for MEC decomposition is taken from [CH11], where more advanced algorithms as well as use of MECs in parity MDPs are discussed.

For an overview of literature related to verification of temporal properties in MDPs, we refer the reader to the monograph [BK08].

MDPs are also used as a prime model in reinforcement learning (RL), one of the classical yet rapidly evolving sub-fields of AI. For RL-centric view of MDPs, we point the reader towards the textbooks [SB18, Ber07a].
<figure><img src="image_44.png" /></figure>

# STOCHASTIC GAMES

<figure><img src="image_45.png" /></figure>

<figure><img src="image_46.png" /></figure>

<figure><img src="image_47.png" /></figure>

<figure><img src="image_48.png" /></figure>

<figure><img src="image_49.png" /></figure>
Chapter 6

# Stochastic Games

NATHALIE BERTRAND, PATRICIA BOUYER-DECITRE, NATHANAËL FIJALKOW, MATEUSZ SKOMRA

In this chapter, we introduce and review results on stochastic games with two players. On the one hand, they extend 2-player games with random vertices; on the other hand, they extend Markov decision processes with a second player.

When equipped with a simple reachability objective, the objective of Max is to maximise the probability to reach the target. Most of the chapter focuses on stochastic games with reachability objectives. We show uniform positional determinacy in Section 6.1, using a fixed point characterisation of the values. Section 6.2 deals with a number of normalisation steps that are often useful when constructing algorithms for stochastic games. This immediately yields a value iteration algorithm, discussed in Section 6.3, and with a bit more work a strategy improvement algorithm, defined in Section 6.4. We construct two algorithms based on permutations of random vertices in Section 6.5, and conclude in Section 6.6 showing that many other stochastic games reduce to stochastic games with reachability objectives.

## Notations

There are two classical models for stochastic arenas, which we present now. In this chapter, we will use the first one: using random vertices. We present it first, and then quickly introduce the second one and explain why they are equivalent.

### The model with random vertices

Let us first define stochastic arenas.

**Definition 17** (Stochastic arenas). A stochastic arena is $\mathcal{A} = (G, V_{\text{Max}}, V_{\text{Min}}, V_{\text{Random}}, \delta)$ where
<figure><img src="image_50.png" /><figcaption>Figure 6.1: Example of a stochastic arena: circle nodes are controlled by Max, square nodes by Min, and triangle nodes are random.</figcaption></figure>

* $G$ is a graph over the set of vertices $V$ and $V = V_{\text{Max}} \uplus V_{\text{Min}} \uplus V_{\text{Random}}$ partitions the vertices into those controlled by Max, Min, and random vertices.

* $\delta: V_{\text{Random}} \to \mathcal{D}(E)$ is the probabilistic transition function.

**Definition 18 (Stochastic games).** Let $\mathcal{A}$ a stochastic arena. A qualitative stochastic game is $\mathcal{G} = (\mathcal{A}, W)$ with $W \subseteq \text{Paths}_{\omega}$ a qualitative condition, and a quantitative stochastic game is $\mathcal{G} = (\mathcal{A}, f)$ with $f: \text{Paths}_{\omega} \to \mathbb{R} \cup \{\pm\infty\}$ a quantitative condition.

Most of the chapter will be devoted to stochastic reachability games, which are induced by Reach(Win). For simplicity we assume that Win is a sink (meaning a single vertex with a self-loop), the general case where Win is a subset of edges can be easily reduced to this case. The following definitions are natural extensions of the ones given in Chapter 1 for the stochastic setting.

A strategy for Max is a function $\sigma: \text{Paths} \to \mathcal{D}(E)$, and similarly for Min. Note that a strategy is allowed to randomise over its actions. A pure strategy does not use randomisation: $\sigma: \text{Paths} \to E$, and a positional strategy does not use memory: $\sigma: V_{\text{Max}} \to \mathcal{D}(E)$.

When a pair of strategies $(\sigma, \tau)$ and an initial vertex $u$ is fixed, we obtain a stochastic process: we write $\mathbb{P}_{\sigma, \tau}^u$ for the probability measure on infinite plays. For instance, for $W$ a condition, we write $\mathbb{P}_{\sigma, \tau}^u(W)$ for the probability that the infinite path satisfies $W$ when Max plays $\sigma$, Min plays $\tau$, and we start from $u$. Note that we are implicitly assuming that $W$ is measurable. For $f: \text{Paths}_{\omega} \to \mathbb{R} \cup \{\pm\infty\}$, we write $\mathbb{E}_{\sigma, \tau}^u(f)$ for the expectation of $f$.

Let us consider a qualitative stochastic game $\mathcal{G} = (\mathcal{A}, W)$. The value for Max in $\mathcal{G}$ from $u$ is defined as $\text{val}_{\text{Max}}^{\mathcal{G}}(u) = \sup_{\sigma} \inf_{\tau} \mathbb{P}_{\sigma, \tau}^{u}(W)$, and symmetrically the value for Min is $\text{val}_{\text{Min}}^{\mathcal{G}}(u) = \inf_{\sigma} \sup_{\tau} \mathbb{P}_{\sigma, \tau}^{u}(W)$. Clearly enough, $\text{val}_{\text{Max}}^{\mathcal{G}}(u) \le \text{val}_{\text{Min}}^{\mathcal{G}}(u)$.

Let us now consider a quantitative stochastic game $\mathcal{G} = (\mathcal{A}, f)$. The value for Max in $\mathcal{G}$ from $u$ is defined as $\text{val}_{\text{Max}}^{\mathcal{G}}(u) = \sup_{\sigma} \inf_{\tau} \mathbb{E}_{\sigma, \tau}^{u}(f)$, and symmetrically the value for Min is $\text{val}_{\text{Min}}^{\mathcal{G}}(u) = \inf_{\sigma} \sup_{\tau} \mathbb{E}_{\sigma, \tau}^{u}(f)$. Clearly enough, $\text{val}_{\text{Max}}^{\mathcal{G}}(u) \le \text{val}_{\text{Min}}^{\mathcal{G}}(u)$.

We say that the game is determined if $\text{val}_{\text{Max}}^{\mathcal{G}}(u) = \text{val}_{\text{Min}}^{\mathcal{G}}(u)$, and in that case define the value of $u$ in $\mathcal{G}$ as $\text{val}^{\mathcal{G}}(u)$. A strategy $\sigma$ is optimal from $u$ if $\text{val}^{\sigma}(u) = \text{val}^{\mathcal{G}}(u)$, and simply optimal if it is optimal from all vertices.
We say that the qualitative Ω is positionally determined if for all games with objective Ω, for all vertices v, there exists a pair of optimal positional strategies. We add the adjective purely to indicate that the strategy is pure, and uniformly to express that the same strategy can be used from all vertices. We define as expected the notion of half-positionally determined qualitative objective, and similarly for quantitative objectives.

**Remark 10.** For stochastic reachability games we also often assume that the probabilistic transition function is

$$ \delta : V_{\text{Random}} \to \mathcal{D}(V), $$

and similarly strategies are functions $\sigma, \tau: V \to V$.

Back to the example in Figure 6.1, let us consider the stochastic reachability game $\mathcal{G} = (\mathcal{A}, \mathcal{Reach}(\{v_7\}))$. Assume that Max and Min play the following pure positional strategies: $\sigma(v_0) = v_1$, $\sigma(v_2) = v_3$, $\sigma(v_5) = v_5$ and $\tau(v_6) = v_5$. Under such a strategy profile, starting in $v_0$, the probability to reach $v_7$ is $\mathbb{P}_{\sigma, \tau}^{v_0}(\mathcal{Reach}(\{v_7\})) = \frac{2}{3}$. One can show that both strategies are optimal, and $\text{val}_{\text{Max}}^{\mathcal{G}}(v_0) = \text{val}_{\text{Min}}^{\mathcal{G}}(v_0) = \frac{2}{3}$.

## The model with explicit actions

We now introduce a second model for stochastic arenas, using the notion of actions. This is the natural extension of the model used in Chapter 5 to two-player games. We let A be a (finite) set of actions, which is the set of choices the players can make at each step of the game.

**Definition 19 (Stochastic arenas and games – explicit actions).** A stochastic arena with explicit actions is $\mathcal{A} = (G, V_{\text{Max}}, V_{\text{Min}}, V_{\text{Random}}, \Delta)$ where

* $G$ is a graph over the set of vertices $V$ and $V = V_{\text{Max}} \cup V_{\text{Min}}$,

* $\Delta: A \to \mathcal{D}(E)$ maps actions to distributions of edges.

All notions are adapted (or extended from Chapter 5) in a natural way: for instance a strategy is a function $\sigma: \text{Paths} \to \mathcal{D}(A)$.

The transformations between the two models are transparent. The key difference is that the model with random vertices allows us to naturally define a parameter: the number of random vertices, which will be important in Section 6.5. A different parameter arises in the model with actions: the number of actions. At the end of the day, the choice of models is a matter of taste and technical convenience.

## 6.1 Fixed point characterisation and positional determinacy

In the same way as Martin's theorem implies (determinacy for (essentially) all (non-stochastic) games we consider in this book, the following theorem by Maitra and Sudderth establishes determinacy for stochastic games:
**Theorem 71** (Determinacy of stochastic games with bounded quantitative objectives). *Stochastic games with bounded measurable quantitative objectives are determined.*

Thanks to this theorem, the value is well defined in all games we consider.

**Theorem 72** (Pure positional determinacy for stochastic reachability games). *Stochastic reachability games are uniformly purely positionally determined.*

Note that Theorem 72 does not make any assumption on the game.

Before giving the proof of Theorem 72, we establish two preliminary results. Let $\mathcal{G}$ a stochastic reachability game. Let $Y$ the set of functions $\mu: V \to [0, 1]$, it is a lattice when equipped with the componentwise order. We define the operator $\mathcal{O}^{\mathcal{G}}: Y \to Y$ by:

$$ \mathcal{O}^{\mathcal{G}}(\mu)(u) = \begin{cases} 1 & \text{if } u \in \text{Win}, \\ \max\{\mu(v) : u \to v \in E\} & \text{if } u \in V_{\text{Max}}, \\ \min\{\mu(v) : u \to v \in E\} & \text{if } u \in V_{\text{Min}}, \\ \sum_{v \in V} \delta(u)(v) \cdot \mu(v) & \text{if } u \in V_{\text{Random}}. \end{cases} $$

Since $\mathcal{O}^{\mathcal{G}}$ is monotonic, it has a least fixed point, which is also the least pre-fixed point.

**Theorem 73.** Let $\mathcal{G}$ a stochastic reachability game. Then $\mathcal{G}$ is determined and the least fixed point of $\mathcal{O}^{\mathcal{G}}$ computes the values of $\mathcal{G}$. Furthermore, any uniform pure positional strategy $\tau$ for Min that satisfies

$$ u \in V_{\text{Min}} : \tau(u) \in \operatorname{argmin} \{ \operatorname{val}^{\mathcal{G}}(v) : u \to v \in E \} $$

is optimal.

*Proof.* To begin, let us recall that thanks to Kleene fixed point theorem (Theorem 4), the least fixed point of $\mathcal{O}^{\mathcal{G}}$ is computed as follows:

$$ \forall u \in V, \mu_0(u) = 0 \quad ; \quad \mu_{k+1} = \mathcal{O}^{\mathcal{G}}(\mu_k). $$

We have $\mu_0 \le \mu_1 \le \dots$, and since $\mathcal{O}^{\mathcal{G}}$ preserves suprema, $\mu^* = \lim_k \mu_k$ is the least fixed point of $\mathcal{O}^{\mathcal{G}}$. The crux here is to understand what are the values $\mu_k$ for $k = 0, 1, \dots$. Let us define the truncated reachability objective:

$$ \text{Reach}_{\le k}(\text{Win}) = \{ \pi : \exists i \le k, \pi_i = \text{Win} \}. $$

A simple induction on $k$ shows that $\mu_{k+1}$ is the values for $\text{Reach}_{\le k}$ in $\mathcal{G}$ and that both players have optimal deterministic strategies for $\text{Reach}_{\le k}$. For any $\varepsilon > 0$, let $k$ be such that $\|\mu_{k+1} - \mu^*\|_{\infty} \le \varepsilon$ and let $\sigma$ be an optimal strategy of Max for $\text{Reach}_{\le k}$. Then, for any $u$ and any strategy $\tau$ of Min we have $\mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}(\text{Win})) \ge \mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}_{\le k}(\text{Win})) \ge \mu^*(u) - \varepsilon$, so $\text{val}_{\text{Max}}^{\mathcal{G}}(u) \ge \mu^*(u)$.

To prove that $\text{val}_{\text{Min}}^{\mathcal{G}}(u) \le \mu^*(u)$, consider any pure positional strategy $\tau$ for Min that satisfies

$$ u \in V_{\text{Min}} : \tau(u) \in \operatorname{argmin} \{ \mu^*(v) : u \to v \in E \}. $$

Let $\sigma$ be any strategy of Max. We prove by induction that for all $k$, the following holds:

$$ \forall \sigma, \mathbb{E}_{\sigma, \tau}^{u}[\mu^*(\pi_k)] \le \mu^*(u). $$
6.1. FIXED POINT CHARACTERISATION AND POSITIONAL DETERMINACY225

<figure><img src="image_51.png" /><figcaption>Figure 6.2: An example of a game where some argmax strategy is not optimal.</figcaption></figure>

In words, if we consider the distribution of vertices obtained after $k$ steps, then the expectation of $\mu^*$ on that distribution is smaller than or equal to $\mu^*(u)$. This is clear for $k=0$, with the inequality being an equality. For $k > 0$, we show that for any vertex $u$ we have $\mathbb{E}_{\sigma, \tau}^u[\mu^*(\pi_1)] \le \mu^*(u)$: this is the one-step special case of the property above. We distinguish four cases:

* if $u = \text{Win}$, this is clear.

* if $u \in V_{\text{Max}}$, then for all $u \to v \in E$ we have $\mu^*(v) \le \mu^*(u)$, implying the property.

* if $u \in V_{\text{Min}}$, then for $\tau(u) = u \to v$ we have $\mu^*(v) = \mu^*(u)$, implying the property.

* if $u \in V_{\text{Random}}$, then $\sum_{v \in V} \delta(u)(v) \cdot \mu^*(v) = \mu^*(u)$, again implying the property.

To do the induction step for higher $k$, note that for every $v$ the conditional expected value $\mathbb{E}_{\sigma, \tau}^u[\mu^*(\pi_{k+1}) | \pi_1 = v]$ is equal to $\mathbb{E}_{\sigma', \tau}^v[\mu^*(\pi_k)] \le \mu^*(v)$ for some $\sigma'$, which gives $\mathbb{E}_{\sigma, \tau}^u[\mu^*(\pi_{k+1})] \le \sum_v \mathbb{E}_{\sigma, \tau}^u(\pi_1 = v)\mu^*(v) = \mathbb{E}_{\sigma, \tau}^u[\mu^*(\pi_1)] \le \mu^*(u)$ as claimed. In particular, for any $\sigma$ and any $k$ we get

$$ \mathbb{P}_{\sigma, \tau}^{u}(\text{Reach}_{\le k}(\text{Win})) \le \mathbb{E}_{\sigma, \tau}^{u}[\mu^{*}(\pi_{k})] \le \mu^{*}(u), $$

because $\mu^*(\text{Win}) = 1$ and $\mu^* \ge 0$. Taking the limit when $k$ goes to infinity, this yields $\mathbb{P}_{\sigma, \tau}^u(\text{Reach}(\text{Win})) \le \mu^*(u)$. Since $\sigma$ was arbitrary, we get $\text{val}_{\text{Min}}^g(u) \le \mu^*(u)$, which implies that $\mu^*$ is the value of the game and that the strategy $\tau$ is optimal. $\square$

Let us raise an important point here: the set of values does not directly imply a pair of pure and positional optimal strategies. It is very tempting to define them as follows

$$ u \in V_{\text{Max}} : \sigma(u) \in \underset{\text{argmax}}{\{\text{val}^g(v) : u \to v \in E\}}, $$

$$ u \in V_{\text{Min}} : \tau(u) \in \underset{\text{argmin}}{\{\text{val}^g(v) : u \to v \in E\}}. $$

and to claim that they are optimal. The optimality of $\tau$ follows from Theorem 73, but $\sigma$ may not be optimal, as shown in Figure 6.2. In that example, all vertices have value 1, but the strategy $\sigma(v_0) = v_1$ is not optimal, although it can be obtained by the definition above. Some notion of progress is missing: the optimal strategy must make progress towards the target. Note that this example is actually not a stochastic game: the optimality claim for $\sigma$ already fails for (non-stochastic) reachability games.

To construct optimal pure and positional strategies for Max, we need to be more precise. Let us fix $0 < \lambda < 1$ and consider the quantitative objective

$$ \text{QuantitativeReach}(\rho) = \begin{cases} 0 & \text{if } \rho_i \neq \text{Win for all } i, \\ \lambda^i & \text{for } i \text{ the first index such that } \rho_i = \text{Win.} \end{cases} $$
It refines the reachability objective by quantifying the number of steps required to reach Win. A stochastic reachability game can be naturally interpreted as a limit of stochastic quantitative reachability games when $\lambda \to 1$. We now extend Theorem 73 to quantitative games. Let $Y$ be the set of functions $\mu: V \to [0, 1]$. We define the operator $\mathcal{O}^{\mathcal{G}}: Y \to Y$ by:

$$ \mathcal{O}^{\mathcal{G}}(\mu)(u) = \begin{cases} 1 & \text{if } u \in \text{Win}, \\ \lambda \cdot \max\{\mu(v) : u \to v \in E\} & \text{if } u \in V_{\text{Max}}, \\ \lambda \cdot \min\{\mu(v) : u \to v \in E\} & \text{if } u \in V_{\text{Min}}, \\ \lambda \cdot \sum_{v \in V} \delta(u)(v) \cdot \mu(v) & \text{if } u \in V_{\text{Random}}. \end{cases} $$

Since $\mathcal{O}^{\mathcal{G}}$ is monotonic, it has a least fixed point, which is also the least pre-fixed point.

**Theorem 74.** Let $\mathcal{G}$ a stochastic quantitative reachability game. Then $\mathcal{G}$ is uniformly purely positionally determined, $\mathcal{O}^{\mathcal{G}}$ has a unique fixed point, and this point computes the values of $\mathcal{G}$. Furthermore, any uniform pure positional strategies $\sigma, \tau$ that satisfy

$$ \begin{aligned} \forall u \in V_{\text{Max}}: & \quad \sigma(u) \in \operatorname*{argmax}\{\text{val}^{\mathcal{G}}(v) : u \to v \in E\}, \\ \forall u \in V_{\text{Min}}: & \quad \tau(u) \in \operatorname*{argmin}\{\text{val}^{\mathcal{G}}(v) : u \to v \in E\}. \end{aligned} $$

are optimal.

*Proof.* Let us define the quantitative objective $\text{QuantitativeReach}_{\le k}$:

$$ \text{QuantitativeReach}_{\le k}(\rho) = \begin{cases} 0 & \text{if } \rho_i \ne \text{Win for all } i \le k, \\ \lambda^i & \text{for } i \le k \text{ the first index such that } \rho_i = \text{Win}. \end{cases} $$

Let $\mu^*$ be any fixed point of $\mathcal{O}^{\mathcal{G}}$ and take any pure positional strategy $\sigma$ such that $\sigma(u) \in \operatorname*{argmax}\{\mu^*(v) : u \to v \in E\}$ for all $u$. We prove by induction that for all $k \ge 1$, the following holds:

$$ \forall \tau, \mathbb{E}_{\sigma, \tau}^{u}[\lambda^k \mu^*(\pi_k) + (1-\lambda) \sum_{i=1}^{k} \lambda^{i-1} \text{QuantitativeReach}_{\le k-i}(\pi_i)] \ge \mu^*(u). $$

To shorten the notation, we write $\text{QR}$ instead of $\text{QuantitativeReach}$. To prove the claim for $k=1$ we distinguish four cases:

* if $u = \text{Win}$, then $\mu^*(u) = 1$.

* if $u \in V_{\text{Max}}$, then for $\sigma(u) = u \to v$ we have $\mu^*(v) = \lambda^{-1}\mu^*(u)$.

* if $u \in V_{\text{Min}}$, then for all $u \to v \in E$ we have $\mu^*(v) \ge \lambda^{-1}\mu^*(u)$.

* if $u \in V_{\text{Random}}$, then $\sum_{v \in V} \delta(u)(v) \cdot \mu^*(v) = \lambda^{-1}\mu^*(u)$.

Therefore $\mathbb{E}_{\sigma, \tau}^{u}[\lambda\mu(\pi_1) + (1-\lambda)\text{QR}_{\le 0}(\pi)] \ge \mu^*(u)$ for all $u$. To prove the induction step, note that the claimed inequality is satisfied as equality if $u \in \text{Win}$. Otherwise, for every $v$ there is $\tau'$ such that $\mathbb{E}_{\sigma, \tau'}^{u}[\mu(\pi_{k+1}) | \pi_1 = v] = \mathbb{E}_{\sigma, \tau'}^{v}[\mu(\pi_k)], \mathbb{E}_{\sigma, \tau'}^{u}[\text{QR}_{\le 0}(\pi) | \pi_1 = v] = 0$, and

$$ \mathbb{E}_{\sigma, \tau}^{u}[\text{QR}_{\le j}(\pi) | \pi_1 = v] = \lambda \mathbb{E}_{\sigma, \tau'}^{v}[\text{QR}_{\le j-1}(\pi)] $$