# A Floyd-Warshall Approach to Value Computation in Markov Decision Processes

Aymeric Côme, Éric Fabre, Loïc Hélouët

► To cite this version:

Aymeric Côme, Éric Fabre, Loïc Hélouët. A Floyd-Warshall Approach to Value Computation in Markov Decision Processes. QEST-Formats 2024 - International Conference on Quantitative Evaluation of SysTems, Sep 2024, Calgary, Canada. pp.284-301, 10.1007/978-3-031-68416-6_17. hal-04711531

HAL Id: hal-04711531

https://inria.hal.science/hal-04711531v1

Submitted on 27 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# A Floyd-Warshall Approach to Value Computation in Markov Decision Processes

Aymeric CÔME, Éric FABRE[0000-0001-9008-8234], and Loïc HÉLOUËT[0000-0001-7056-2672]

Univ. Rennes, IRISA, CNRS & INRIA, Rennes, France,
aymeric.come@inria.fr, eric.fabre@inria.fr, loic.helouet@inria.fr

**Abstract.** Value and policy iteration are classical algorithms to maximize the average discounted reward of an MDP. They rely on a breadth-first exploration strategy in the future of each state to update its value and possibly change the action policy at this state. This paper revisits this paradigm and examines a depth-first search strategy. It reformulates the average reward computation as an integral over (future) paths that is better expressed in the formalism of weighted automata. Policy evaluation can then be solved by a Floyd-Warshall algorithm, which gathers at once the rewards along possibly infinite runs. This reformulation opens the way to new approximation schemes for the value function. The same formalism also gives access to other quantities of interest, as the gradient of the average reward with respect to model or policy parameters, or the variance of the reward. The behaviors and performances of this value estimation scheme are illustrated on several benchmarks.

## 1 Introduction

The derivation of optimal policies for Markov Decision Processes (MDP) typically relies on two steps: an *evaluation* step, which assigns a value to every state, estimating its average future reward under the current policy, and the *policy improvement* step, which updates the action taken at each state to favor transitions towards the most rewarding future states. Under a given policy, state values satisfy a linear fix-point equation, which resolution would incur a cubic complexity (in the number of states). More affordable solutions use linear programming or, more commonly, iterative approaches, and estimate the average reward of a state by a breadth first exploration of its future up to some bounded depth and under the current policy (see [11], Chap. 6 for details).

This paper explores a new way to derive the value function of policies in MDPs, favoring a depth first exploration along the most promising runs rooted at each state. Specifically, the computation of state values derives from a vertex elimination technique in the MDP graph. Eliminating a vertex captures in a single step all runs (and circuits) going through this vertex, thus gathering at once the rewards of possibly infinitely many runs. This recursive vertex elimination takes the form of a Floyd-Warshall (FW) procedure.
This FW reinterpretation can be considered as an alternative way to compute
the integral of a reward function over the (stochastic) space of trajectories of the
underlying Markov process, once a policy is fixed. The technique was originally
developed to analyze properties of weighted automata, with transition weights
taken in a semi-ring, and it is extremely versatile: the same algorithm can be
used to compute the value difference of two policies, to compute the gradient of
the value function with respect to parameters of a policy or to parameters of the
MDP, or even to compute the variance of the value function. This is a first advan-
tage of this reformulation. Regarding performances, the FW approach converges
in bounded time to the exact value function, but with the same cubic complexity
as standard techniques that solve Bellman's fixed point equation relating value
and reward. Nevertheless, it opens the way to new approximation schemes for
the value function, as it progressively integrates weights (i.e. rewards) of paths
visiting a growing set of states. Integration could then stop before all states are
included in path descriptions, possibly speeding up the convergence of policy
iteration. This new formulation is evaluated on random instances of standard
models: grid worlds (where the reward lies at a goal state in a maze) and river
swim (where the biggest gain requires to swim up a river stream, which might
not be worth the effort).

The paper is organized as follows. Section 2 introduces notations and recalls
basic results about values and optimal policies in MDPs. Section 3 reformulates
value evaluation for a fixed policy as an integration over trajectories in the
MDP, performed with Floyd-Warshall (FW). It also discusses the versatility of
the path integration approach. Section 4 examines a specific strategy to drive the
FW algorithm, in order to quickly collect the rewards of the most contributing
paths. This progressive integration suggests new approximation schemes and
offers an analogy with the A\* algorithm. Section 5 illustrates the behavior of
the FW approach and compares it to standard value iteration especially w.r.t
convergence to the true value function. Due to limited space, some proofs are
omitted or sketched, but they appear in the extended version [6] of this paper.

## 2 Framework and notations

A finite *Markov Decision Process* (MDP) $M = (S, A, P, R)$ models an environment in which an agent stochastically moves from state to state by choosing actions, and gets feedbacks that will motivate the decision rule followed. $S$ is the (finite) state space of size $N$, $A$ is the finite set of actions available to the agent, $P(s, a, s') = P(s' | s, a)$ is the transition function encoding the probability to move from a state $s$ to a state $s'$ upon choosing action $a$, and $R(s, a) \in \mathbb{R}_+$ is the reward function. The transition probabilities are *Markovian*, i.e., only depend on the current state and not on the history before. For reasons showcased below, the reward is required to be bounded: without loss of generality, it is assumed that $R \in [0, 1]$. The starting state $s_0$ can be sampled from a distribution $\mu_0$ over $S$, but w.l.o.g, we assume $s_0$ to be fixed.

A MDP generates infinite *runs*, i.e. sequences of the form $s_0, a_0, r_0, s_1, a_1, r_1, \dots$
where $r_i = R(s_i, a_i)$ and $P(s_{i+1} | s_i, a_i) > 0$, that depend on action choices of
the agent and on state changes chosen by the environment. A stationary, Markovian and deterministic policy is a map $\pi: S \to A \in \Pi$; it does not depend on time nor on the history of the run, and prescribes one single action rather than a distribution on A. Fixing such a policy $\pi$ for a MDP $M = (S, A, P, R)$ induces a Markov Reward Processes $M_\pi = (S, P_\pi, R_\pi)$, with state space $S$, transition probability $P_\pi(s'|s) = P(s'|s, \pi(s))$ and reward $R_\pi(s) = R(s, \pi(s))$ for any $\pi \in \Pi$, $(s, s') \in S^2$. Then, for a given policy $\pi$, and a discount factor $\gamma \in (0, 1)$, the value of a state $s$ is defined as the expected cumulative discounted reward when starting a run from $s$ and taking actions accordingly to $\pi$:

$$V_{\pi}(s) = \mathbb{E}_{\pi} \left[ \sum_{n=0}^{+\infty} \gamma^{n} r_{n} \mid s_{0} = s \right] \quad (1)$$

The goal is then to find a policy $\pi_*$ that achieves the highest value for starting state $s_0$. We restrict ourselves to Markovian, stationary and deterministic policies, as it is well known that using decision rules from this class is sufficient to achieve optimality in MDPs with finite sets of states and actions ([11], Thm. 9.1.8). Following the definition of optimal policies, we can also define an optimal value $V_*(s)$ for every state $s \in S$, defined as $V_*(s) = V_{\pi_*(s)} = \max_{\pi \in \Pi} V_\pi(s)$. It is interesting to have the value for every state, as the value of one state will depend on the values of its neighbors; that property is formally expressed by the Bellman operator $\mathcal{T}_\pi: \mathbb{R}^N \to \mathbb{R}^N$:

$$\forall V \in \mathbb{R}^N, \forall s \in S \quad \mathcal{T}_\pi(V)(s) = R_\pi(s) + \gamma \sum_{s' \in S} P_\pi(s'|s)V(s') \quad (2)$$

Indeed, a quick calculation shows that $V_\pi$ is a fixed point of $\mathcal{T}_\pi$; and $\mathcal{T}_\pi$ is a $\gamma$-contraction, so that $V_\pi$ is the only fixed point ([11], Thm. 6.2.3). Similarly, $V_*$ is the unique fixed point of the $\gamma$-contraction optimal Bellman operator:

$$\forall s \in S, \quad \mathcal{T}_*(V_*)(s) = \max_{a \in A} \left\{ R(s, a) + \gamma \sum_{s' \in S} P(s'|s, a)V_*(s') \right\} = V_*(s) \quad (3)$$

Given a value function $V \in \mathbb{R}_+^N$, a V-improving policy is a policy $\pi$ such that

$$\forall s \in S, \quad \pi_V(s) = \mathcal{T}_*(V)(s) = \max_{a \in A} \left\{ R(s, a) + \gamma \sum_{s' \in S} P(s'|s, a)V(s') \right\} \quad (4)$$

Obviously, one can obtain a V-improving policy by choosing

$$\forall s \in S, \pi_V(s) \in \arg \max_{a \in A} \left\{ R(s, a) + \gamma \sum_{s' \in S} P(s'|s, a)V(s') \right\} \quad (5)$$

For an optimal policy $\pi_*$ we necessarily have $\pi_{V_*} = \pi_*$. Consequently, searching for the optimal policy can be done by maximizing values.
Let us now consider *policy evaluation* methods to compute the values of a given policy. Firstly, in a finite MDP the fixed point equation (2) can be rewritten in matrix form as:

$$V_{\pi} = R_{\pi} + \gamma P_{\pi} V_{\pi} \iff V_{\pi} = (I_{d} - \gamma P_{\pi})^{-1} R_{\pi} \quad (6)$$

where $(I_d - \gamma P_\pi)$ is invertible due to the discount being strictly less than 1 and $P_\pi$ being a stochastic matrix ([11], Thm 6.1.1). Hence (6) gives a straightforward way to compute $V_\pi$. However, computing $V_\pi$ requires inverting the matrix $(I_d - \gamma P_\pi)$. This can be done in $O(|S|^3)$ with Gauss-Jordan elimination (see [12], Chap.3).

Another way to compute a value vector $V_\pi$ is by *value iteration* (Algorithm 1), i.e., by recursively applying the Bellman operator $\mathcal{T}_\pi$. This strategy is guaranteed to converge, as $V_\pi$ is the unique fixed point of the $\gamma$-contraction $\mathcal{T}_\pi$ ([11], Thm. 6.2.3; [5]). Furthermore, the stopping criterion $\|V_{k+1} - V_k\|_\infty \ge \epsilon^{\frac{1-\gamma}{\gamma}}$ ensures that $\|V_{k+1} - V_*\|_\infty < \epsilon$ ([11], Thm 6.3.1), in other words the estimate is $\epsilon$-optimal.

**Algorithm 1 Value Iteration**

**Input:** MDP $M$, policy $\pi$, error bound $\epsilon > 0$, discount $\gamma$, initial value $V_0 \in \mathbb{R}^N$

**Initialization:** $k = 0$, $V_1 = \mathcal{T}_\pi(V_0)$

**while** $\|V_{k+1} - V_k\|_\infty \ge \epsilon^{\frac{1-\gamma}{\gamma}}$ **do**

$$V_{k+1} = \mathcal{T}_\pi(V_k)$$

Increment $k$

**end while**

**Return:** $V_k$, an $\epsilon$-approximation of $V_\pi$

Now, when searching for optimality, one could use value iteration as well, with $\mathcal{T}_*$ to get an estimate of $V_*$; then, any $V_k$-improving policy is an $\epsilon$-optimal one. However, while being the baseline for policy evaluation, value iteration has been found to not be the most efficient when looking for an optimal policy. Even though several optimisations have been proposed (e.g. Prioritized Sweeping approaches [10]), *policy iteration* [8] is usually preferred, presented in Algorithm 2. The idea is to alternate between improving and evaluating a current policy, until no improvement is possible anymore. It converges in a finite number of steps to an optimal policy ([11], Thm. 6.4.2), and is usually faster than value iteration [14]; it also motivates the search for policy evaluation methods. More specifically, policy iteration with approximate policy evaluation has received a lot of attention ([5, ?, ?, ?]); we will discuss approximation as well in this article.

# 3 Floyd-Warshall Path Integrator

## 3.1 Weighted automata and path integrals

A *semi-ring* $(\mathbb{K}, \oplus, \otimes, \bar{0}, \bar{1})$ is a set $\mathbb{K}$ of “values” such that $(\mathbb{K}, \oplus, \bar{0})$ is a commutative monoid with $\bar{0}$ as neutral element, $(\mathbb{K}, \otimes, \bar{1})$ is a monoid with $\bar{1}$ as neutral element, $\otimes$ distributes over $\oplus$, and $\bar{0}$ is an annihilator for $\otimes$. A common example is the *probability semiring* $(\mathbb{R}^+, +, *, 0, 1)$.
**Algorithm 2 Policy Iteration**

**Input:** MDP M, discount $\gamma$, initial policy $\pi_0 \in \Pi$
**Initialization:** $k = 0, \pi_1 = \emptyset$
**while** $\pi_{k+1} \neq \pi_k$ **do**

[a] **Policy evaluation:** compute the (approximated) value $V_k$ of $\pi_k$

[b] **Policy improvement:** $\pi_{k+1} \in \arg\max_{\pi \in \Pi} \{R_{\pi} + \gamma P_{\pi} V_k\}$ with $\pi_{k+1} = \pi_k$ if possible

A weighted automaton $\mathcal{A}$ over the semi-ring $\mathbb{K}$ is a pair<fnref n="1" /> $\mathcal{A} = (S, w)$ where $S$ is the state set, with two distinguished states, the initial state $s^i$ and the final state $s^f$ assumed to have no successor. The weight function $w: S \times S \to \mathbb{K}$ assigns to each possible transition $(s, s') \in S \times S$ a weight $w(s, s')$ in the semi-ring $\mathbb{K}$. Weighted automata can be used to define stochastic automata [1], with the additional requirement that $\forall s \in S \setminus \{s^f\}, \oplus_{s' \in S} w(s, s') = \bar{1}$. The transition set $T \subseteq S \times S$ of $\mathcal{A}$ is defined as the support of $w$ in $S \times S$, i.e. $t = (s, s') \in T$ iff $w(s, s') \neq \bar{0}$. For clarity, one may use the redundant notation $\mathcal{A} = (S, T, w)$, and for $t = (s, s')$, we denote $s = t^-$, $s' = t^+$ and $w(t)$ for $w(s, s')$. A path in $\mathcal{A}$ is a sequence $\sigma = t_1 \dots t_n$ of transitions, $n > 0$, such that $t_i^+ = t_{i+1}^-$, $0 < i < n$. By extension, $\sigma^- = t_1^-$ and $\sigma^+ = t_n^+$. The weight of path $\sigma = t_1 \dots t_n$ is defined as $w(\sigma) = w(t_1) \otimes \dots \otimes w(t_n)$ and its length $|\sigma|$ as $n$. Path $\sigma$ is a run if $\sigma^- = s^i$, i.e. if the path is rooted at the initial state $s^i$. We denote by $\sigma_1\sigma_2$ the concatenation of two paths, possible whenever $\sigma_1^+ = \sigma_2^-$. Observe that $|\sigma_1\sigma_2| \ge 2$ as paths of length 0 are forbidden. We denote by $\mathcal{P}(s, s')$ the set of paths $\sigma$ such that $\sigma^- = s$, $\sigma^+ = s'$, and by $\mathcal{P}^{(\ge n)}(s, s')$ the set of such paths of length at least $n$. So $\mathcal{P}(s, s') = \mathcal{P}^{(\ge 1)}(s, s')$. Concatenation extends to sets of paths, so one has $\mathcal{P}^{(\ge 2)}(s, s'') = \bigcup_{s' \in S} \mathcal{P}(s, s')\mathcal{P}(s', s'')$, and $\mathcal{P}(s, s'') = (s, s'') \cup \mathcal{P}^{(\ge 2)}(s, s'')$ if transition $(s, s'')$ exists in $\mathcal{A}$, otherwise $\mathcal{P}(s, s'') = \mathcal{P}^{(\ge 2)}(s, s'')$.

We are interested in computing integrals over paths of $\mathcal{A}$ of the form

$$W(s, s') = \bigoplus_{\sigma \in \mathcal{P}(s, s')} w(\sigma) \triangleq W(\mathcal{P}(s, s')) \quad (7)$$

and in particular $W(s^i, s^f)$. With a slight abuse of notation, in the sequel we consider $W$ as a weight operator over sets of paths, with the convention $W(\emptyset) = \bar{0}$, $W(\{\sigma\}) = w(\sigma)$ and for sets of paths $\mathcal{P}_1, \mathcal{P}_2$, $W(\mathcal{P}_1\mathcal{P}_2) = W(\mathcal{P}_1) \otimes W(\mathcal{P}_2)$ and for disjoint sets $W(\mathcal{P}_1 \uplus \mathcal{P}_2) = W(\mathcal{P}_1) \oplus W(\mathcal{P}_2)$. Such integrals have a natural interpretation for stochastic automata. If there is no circuit containing state $s'$, then $s'$ is only met at the end of each path in $\mathcal{P}(s, s')$, and the integral $W(s, s')$ in (7) corresponds to the probability of reaching $s'$ in $\mathcal{A}$ when starting at state $s$. In the general case where circuits around $s'$ exist, $\mathcal{P}(s, s')$ contains all

<footnote n="1">¹ Weighted automata generically assume *labeled* transitions, initial and terminal weights at states. We adopt a simplified setting here.</footnote>
repeated passages through $s'$, and (7) diverges if $s'$ belongs to a bottom strongly connected component (BSCC), i.e. if $s'$ returns to itself with probability one. If $s'$ has an escape towards some $s''$ with no possible return to $s'$, then $W(s, s')$ is the probability to go from $s$ to $s'$ conditionally<fnref n="2" /> to not returning to $s'$. In the sequel, we will always use (7) in settings where the integral converges. For example by assuming that all states have a path towards the terminal state $s'$.

By appropriate choices of the semi-ring, such path integrals give access to various quantities of interest. For instance, in the case of stochastic automata, one may be interested in computing the expected value of a function $f$ over paths connecting two states $s$ and $s'$, i.e.

$$ \mathbb{E}[f(\sigma)|s, s'] = \sum_{\sigma \in \mathcal{P}(s, s')} w(\sigma)f(\sigma) \quad (8) $$

where $w(\sigma)$ is the likelihood of path $\sigma$ and assuming $s'$ is met only at the end of paths in $\mathcal{P}(s, s')$. If function $f$ decomposes as a product over paths by $f(\sigma_1\sigma_2) = f(\sigma_1)f(\sigma_2)$, then (8) immediately derives from (7) by taking $\bar{w}(t) = w(t)f(t)$ instead of $w(t)$ in the definition of transition weights, since one then has $\bar{w}(\sigma_1\sigma_2) = \bar{w}(\sigma_1)\otimes\bar{w}(\sigma_2)$. If function $f$ decomposes additively over paths as $f(\sigma_1\sigma_2) = f(\sigma_1) + f(\sigma_2)$, then (8) typically represents an average path length or duration between states $s$ and $s'$. This can still be captured by expression (7) provided one adopts a more appropriate semi-ring. Specifically, consider as new transition weights the pairs $\bar{w}(t) = (w(t), w(t)f(t))$. In this extended semi-ring, $\oplus$ is the component wise addition with $\bar{0} = (0, 0)$. The product is defined as $(u_1, v_1) \otimes (u_2, v_2) = (u_1u_2, u_1v_2 + u_2v_1)$ with $\bar{1} = (0, 1)$ as unit. This choice entails that

$$ \begin{aligned} \bar{w}(\sigma_1) \otimes \bar{w}(\sigma_2) &= (w(\sigma_1), w(\sigma_1)f(\sigma_1)) \otimes (w(\sigma_2), w(\sigma_2)f(\sigma_2)) \\ &= (w(\sigma_1)w(\sigma_2), w(\sigma_1)w(\sigma_2)(f(\sigma_1) + f(\sigma_2))) \\ &= (w(\sigma_1\sigma_2), w(\sigma_1\sigma_2)f(\sigma_1\sigma_2)) = \bar{w}(\sigma_1\sigma_2) \end{aligned} $$

So applying (7) yields $\bar{W}(s, s') = (\sum_{\sigma \in \mathcal{P}(s, s')} w(\sigma), \sum_{\sigma \in \mathcal{P}(s, s')} w(\sigma)f(\sigma))$. This technique generalizes, and one can actually compute all moments of function $f$ over runs of the stochastic automaton $\mathcal{A}$, for example to derive the standard deviation of $f$ (see [4]). Sec. 3.3 shows how to express the discounted reward in a MDP under the form of (7), and we detail in [6] how to further exploit the semi-ring flexibility to derive related quantities as its variance or its gradient.

## 3.2 Floyd-Warshall recursion

Let $s^1 < s^2 < \dots < s^K$ be some arbitrary ordering of states of $\mathcal{A}$. Let $S_k = \{s^1, \dots, s^k\} \subseteq S$ be the subset of the first $k$ states in $S$ for this ordering, with $0 \le k \le K$. For $s, s' \in S$, let $\mathcal{P}_k(s, s')$ denote the set of paths from $s$ to $s'$ in $\mathcal{A}$

<footnote n="2">² To see this, let $w(s, s') = p$ and assume a self-loop at state $s'$ with $w(s', s') = q$, then $W(s, s') = \frac{p}{1-q}$ where $1-q$ is the probability of definitely leaving $s'$.</footnote>
that only go through states in $S_k$, with the convention that $S_0 = \emptyset$, and $\mathcal{P}_0(s, s')$ is either empty or contains the unique transition from $s$ to $s'$ in $\mathcal{A}$ if it exists. Let us denote

$$W_k(s, s') = \bigoplus_{\sigma \in \mathcal{P}_k(s, s')} w(\sigma) = W(\mathcal{P}_k(s, s')) \quad (9)$$

Then, reconsidering (7), for every pair of states $s, s' \in S$, we have $W_0(s, s') = w(s, s')$ and $W(s, s') = W_K(s, s')$. Furthermore, the set of paths $\mathcal{P}_{k+1}(s, s')$ decomposes as

$$\mathcal{P}_{k+1}(s, s') = \mathcal{P}_k(s, s') \uplus \mathcal{P}_k(s, s^{k+1}) \left[ \biguplus_{n \ge 0} \mathcal{P}_k(s^{k+1}, s^{k+1})^n \right] \mathcal{P}_k(s^{k+1}, s')(10)$$

Applying the weight operator $W$ to this decomposition entails

$$W_{k+1}(s, s') = W_k(s, s') \oplus W_k(s, s^{k+1}) \otimes W_k(s^{k+1}, s^{k+1})^* \otimes W_k(s^{k+1}, s')(11)$$

where the $x^*$ operation in $\mathbb{K}$ is defined by $x^* = \bigoplus_{m \ge 0} x^m$ and the power $x^m$ is naturally defined by $x^0 = \bar{1}$, $x^{m+1} = x \otimes x^m$. Notice that not all semi-rings admit an $x^*$ operation for all $x \ne \bar{1}$ (e.g. $x^*$ is only defined for $x < 1$ in $\mathbb{R}^+$) but it will be the case here for the elements $x$ of interest in our selected semi-rings.

The Floyd-Warshall (FW) algorithm consists in applying recursion (11) for all pairs $s, s' \in S$ to reach the path integral (7) by $W(s, s') = W_K(s, s')$. We shall actually use it to compute only the quantity $W(s, s^f)$, for $s \in S$. Recall that $s^f$ has no successor, therefore it is only met at the end of paths in (7). Notice that thanks to the $x^*$ operation, (11) incorporates at once the contribution of a possibly infinite set of paths between $s$ and $s'$, due to the arbitrary number of loops around state $s^{k+1}$ when this loop exists. In the specific case of a stochastic automaton, $W_k(s^{k+1}, s^{k+1})$ is the probability of returning to $s^{k+1}$ through states in $S_k$. So this quantity is strictly smaller than 1, except if $s^{k+1}$ belongs to a bottom strongly connected component. We reject this situation and assume all states admit at least one path to the terminal state $s^f$. In the probabilistic semi-ring, $W_k(s^{k+1}, s^{k+1})^*$ exists and is equal to $\frac{1}{1-W_k(s^{k+1}, s^{k+1})}$ which is the inverse probability of not returning to $s^{k+1}$ (when only paths through $S_k$ are allowed).

**Remarks.** Notice first that in recursion (11) the choice of $s^{k+1} \in S \setminus S_k$ can be made on the fly at step $k$. Secondly, if one is only interested in the specific value $W(s^i, s^f)$, it is sufficient to perform recursion (11) only for all $s \in S \setminus S_k \cup \{s^i\}$ and $s' \in S \setminus S_k \cup \{s^f\}$ at each step. To see this, let us examine the very first step of the FW algorithm. $W_1(s, s')$ corresponds to the weight of a new direct transition from $s$ to $s'$, and it is non-zero as soon as (i) $(s, s')$ is already a transition in $\mathcal{A}$ or (ii) $s$ and $s'$ are connected through $s^1$, i.e. $(s, s^1) \in T$ and $(s^1, s') \in T$. For pairs $(s, s')$ not satisfying condition (ii), the weight remains unchanged: one has $W_1(s, s') = W_0(s, s') = w(s, s')$. Once $W_1$ is computed, state $s^1$ does not appear in subsequent computations (provided $s^1 \notin \{s^i, s^f\}$). This can be expressed differently: $W_1$ corresponds to the weight function of a new
<figure><img src="image_2.png" /><figcaption>Fig. 1. Floyd Warshall path integration between $s^i$ and $s^f$ in the probabilistic semi-ring, by first eliminating $s^1$, then $s^2$.</figcaption></figure>

automaton $A_1$ with $S \setminus \{s^1\}$ as state set (still for $s^1 \notin \{s^i, s^f\}$). Starting the FW algorithm from $A_1$ instead of $A$ yields the same final integral $W(s^i, s^f)$. So the full FW procedure can be interpreted as a recursive state elimination in $A$, as illustrated in Fig. 1. Finally, if one is interested in all $W(s, s^f)$ for $s \in S$ and not simply in $W(s^i, s^f)$, then (11) must be computed for all $s \in S$ and $s' \in S \setminus S_k \cup \{s^f\}$ at each step $k$.

### 3.3 Expected discounted reward as an integral over paths

Consider MDP $\mathcal{M} = (S, A, P, R)$ and the resulting Markov reward process $\mathcal{M}_\pi = (S, P_\pi, R_\pi)$ induced by policy $\pi$. The weighted automaton $\mathcal{A} = \Phi(\mathcal{M}_\pi, \gamma)$ is built from $\mathcal{M}_\pi$ as follows: $\mathcal{A} = (\bar{S}, w)$ where $\bar{S} = S \uplus \{s^f\}$, and $\forall s, s' \in S, w(s, s') = \gamma P_\pi(s'|s) = \gamma P(s'|s, a = \pi(s))$ and $w(s, s^f) = R_\pi(s) = R(s, a = \pi(s))$. The extra state $s^f$ is an artificial sink, representing the reward collection phase, not to be confused with a target state of the MDP.

**Proposition 1** The expected discounted reward of $\mathcal{M}_\pi$ from the initial state $s_0 = s \in S$, $V_\pi(s)$ given in (1), coincides with the path integral $W(s, s^f)$ defined in (7) for the associated weighted automaton $\mathcal{A} = \Phi(\mathcal{M}_\pi, \gamma)$.

*Proof.* Let $\mathcal{P}^{(n)}(s, s')$ denote paths of length $n$ from $s$ to $s'$ in $\mathcal{A}$, hence $W(s, s') = W(\mathcal{P}(s, s')) = \bigoplus_{n \ge 1} W(\mathcal{P}^{(n)}(s, s'))$. The value function (1) at initial state $s_0 = s$ writes

$$V_{\pi}(s) = \mathbb{E}_{\pi} \left[ \sum_{n \ge 0} \gamma^n r_n | s_0 = s \right] \quad (12)$$

$$ \begin{aligned} & = \sum_{n \ge 0} \gamma^n \mathbb{E}_{\pi} [r_n | s_0 = s] \\ & = \sum_{n \ge 0} \gamma^n \sum_{s' \in S} R_{\pi}(s') P_{\pi}(s_n = s' | s_0 = s) \\ & = \sum_{s' \in S} R_{\pi}(s') \sum_{n \ge 0} \gamma^n P_{\pi}(s_n = s' | s_0 = s) \end{aligned} \quad (13) $$

$$ = \sum_{s' \in S} R_{\pi}(s') \left( \mathbb{1}_{s'=s} + \sum_{n \ge 1} W(\mathcal{P}^{(n)}(s, s')) \right) $$
$$ = R_{\pi}(s) + \sum_{s' \in S} R_{\pi}(s') W(\mathcal{P}(s, s')) \quad (14) $$

$$ = w(s, s^f) + \sum_{s' \in S} W(\mathcal{P}(s, s')) \cdot w(s', s^f) \quad (15) $$

$$ = W \left( (s, s^f) \uplus \bigcup_{s' \in S} \mathcal{P}(s, s') \cdot (s', s^f) \right) \quad (16) $$

$$ = W(\mathcal{P}(s, s^f)) $$

$$ = W(s, s^f) \quad (17) $$

These transforms rely on the fact that the initial converging series only contains positive terms, which can therefore be freely shuffled and reassembled without changing the limit. For clarity, as all computations are performed in $\mathbb{R}^+$, we use the classical sum and product notation instead of semi-ring operations. Relation (14) expresses that the reward of each state $s'$ (under policy $\pi$) contributes to the total performance of policy $\pi$ by a factor which is the (discounted) probability (under $\pi$) of visiting $s'$ from the initial state $s^0 = s$. This coefficient is a sum over a possibly infinite set of runs, which contrasts with iterative methods to estimate $V_{\pi}(s)$ in value iteration or policy iteration, that typically explore runs of bounded depth after $s$ and accumulate $R_{\pi}(s')$ each time $s'$ is met.

As an alternative proof of Prop. 1, notice that the set of paths from $s \in S$ to the sink state $s^f$ also decomposes as

$$ \mathcal{P}(s, s^f) = (s, s^f) \uplus \bigcup_{s' \in S} (s, s') \cdot \mathcal{P}(s', s^f) \quad (18) $$

which differs from the decomposition in (16) as the elementary transitions are connected as a prefix instead of a suffix of path sets. Applying the weight operator to this relation yields

$$ \begin{aligned} W(s, s^f) &= W(\mathcal{P}(s, s^f)) \\ &= w(s, s^f) + \sum_{s' \in S} w(s, s') \cdot W(\mathcal{P}(s', s^f)) \\ &= R_{\pi}(s) + \sum_{s' \in S} \gamma P_{\pi}(s'|s) W(s', s^f) \end{aligned} \quad (19) $$

So the values $W(s, s^f)$ attached to each state $s \in S$ by the Floyd-Warshall procedure form a fixpoint of the Bellman operator. But the latter has a unique fixpoint, which is $V_{\pi}(s)$. ◇

The interest of this reformulation is manifold. First, by definition the value function at state $s$ (see Eq. (12)) involves an infinite sum, or an expectation over infinite paths of the underlying Markov process rooted at $s$. The refactorization trick appearing at Eq. (13) reformulates $V_{\pi}(s)$ as a finite combination of state rewards $R_{\pi}(s')$ with coefficients that result of an integration over possibly many finite paths relating $s'$ to the terminal state $s^f$. They can therefore be obtained
by a Floyd-Warshall procedure. Deriving $V_π$ in this way still has a cubic complexity (in number of states), so there is apparently no gain compared to solving the fixpoint equation $V_π = R_π + γP_πV_π$. We show below that in practice some gains can be achieved.

A second interest relates to possible approximations of the value function. Standard value iteration (Algo. 1) relies on a recursive evaluation of a fixpoint: at step $n$, the value for each state $s$ is estimated by collecting (discounted) rewards on paths rooted at $s$ and of length $n$. The recursion augments this exploration depth to $n + 1$ by considering the estimated value of successors $s'$ of $s$, and transporting it back to $s$ by a (contracting) transition operator. This is thus a breadth first exploration of the future of each state. By contrast, the Floyd-Warshall structure of computations takes the shape of a depth first exploration of paths, as the rewards along unbounded path lengths are collected at once. This suggests approximation schemes that would first explore the most rewarding paths and possibly neglect those leading to rewards that are too far to bring significant extra contribution.

Finally, one can obtain different quantities of interest with this semi-ring approach. For example, we can compute the gradient of the $V_π$ for parametric models/policies [14], or the variance of the discounted reward [13] (see [6] for more details).

# 4 Progressive Floyd-Warshall integration

Relying on Prop. 1, the expected discounted reward of policy $π$ for MDP $\mathcal{M} = (S, A, P, R)$ starting from some specific state $s^i$ can be computed as $W(s^i, s^f)$ in the associated weighted automaton $\mathcal{A} = (\bar{S}, w) = \Phi(\mathcal{M}_π, γ)$. If one further wishes to improve this policy, then $W(s, s^f)$ is also necessary, for every $s \in S$. This section examines a specific strategy to efficiently derive these values. It relies on the interpretation of each step in the Floyd-Warshall procedure as a state elimination, where the next state $s^{k+1}$ to process is selected on the fly.

## 4.1 A progressive algorithm

Let $S_k$ be the set of vertices considered so far at the $k^{th}$ step of recursion, and let $\mathcal{A}_k = (\{s^i, s^f\} \cup S \setminus S_k, T_k, W_k)$ be the weighted automaton at step $k$ defined by weight function $W_k$. We denote by $\partial_k^+(s)$ the set of successors of $s$ in $\mathcal{A}_k$, and by $\partial_k^-(s)$ its set of predecessors:

$$ \partial_k^+(s) = \{s' \in \{s^i, s^f\} \cup S \setminus S_k : s' \neq s, W_k(s, s') \neq \bar{0}\} \quad (20) $$

$$ \partial_k^-(s) = \{s' \in \{s^i, s^f\} \cup S \setminus S_k : s' \neq s, W_k(s', s) \neq \bar{0}\} \quad (21) $$

$s'$ is a neighbor of $s$ in $\mathcal{A}_k$ iff $s' \in \partial_k^-(s) \cup \partial_k^+(s) = \delta_k(s)$. Following remarks 3.2 in Section 3.1, we know that not every weight $W_k(s, s')$ evolves in the recursion step. This gives Algorithm 3 below. Notice that while nodes are progressively removed from the successive $\mathcal{A}_k$, $s^i$ and $s^f$ remain, so the desired result can be
read at the end of the procedure. If the values $W(s, s^f)$ are also desired for all $s \in S$, the update over $s \in \partial_k^-(s^{k+1})$ must be extended to states $s$ that have already been visited and removed, i.e. to $s \in S_k$. The quantity $W(s, s^f)$ is then retrieved as $W_K(s, s^f)$ at the end of the procedure. Symmetrically, if the values $W(s^i, s')$ are desired for all $s' \in S$, the update over $s' \in \partial_k^+(s^{k+1})$ must also apply to $S_k$. Then, when $W_K(s, s^f)$ is computed for all $s \in S$, Algo 3 can be used to evaluate $V_\pi$ in a policy iteration scheme (e.g. in the settings of this paper by calling Algo 3 to compute $V_k$ at line [a] in Algo. 2).

<caption>**Algorithm 3** Progressive Floyd-Warshall computation of $V_\pi(s^i) = W(s^i, s^f)$</caption>

**Input:** weighted automaton $\mathcal{A} = (S, w)$, with $|S| = K$ and distinguished states $s^i, s^f$
**Output:** $W(s^i, s^f)$
**Initialization:** $W_0 = w, S_0 = \emptyset$
**for** $k=0..K-1$ **do**
  select $s^{k+1}$ in $S \setminus S_k$ and set $S_{k+1} = S_k \cup \{s^{k+1}\}$
  set $W_{k+1} = W_k$
  **for all** $s \in \partial_k^-(s^{k+1})$ **do**
    **for all** $s' \in \partial_k^+(s^{k+1})$ **do**
      update $W_{k+1}(s, s')$ by Eq. (11)
      **end for**
    **end for**
  **end for**
  **end for**
  **end for**
  **Return:** $W_K(s^i, s^f)$

The choice of the next state $s^{k+1}$ in the recursion is free and has no impact on the final result. However, observe that $W_k(s^i, s^f)$ remains the initial value $W_0(s^i, s^f)$ until there a path from $s^i$ to $s^f$ passing through states of $S_k$ exists. In order to quickly grasp most rewarding paths for $s^i$, one should therefore choose the next state $s^{k+1}$ to find and integrate new paths from $s^i$ to $s^f$, and at least a first one if state $s^i$ still has reward $W_0(s^i, s^f)$. This motivates structuring the recursion in Algo 3 as a path finder from $s^i$ to $s^f$. Let us define the border at step $k$ as $B_k = \partial_k^+(s^i)$. Taking $s^{k+1} \in B_k$ entails $B_{k+1} = \partial_k(s^{k+1}) \cup B_k \setminus \{s^{k+1}\}$. This choice ensures that the border “progresses” from $s^i$ towards $s^f$, as in Fig. 2.

<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Left: border $B_k$ (in grey) at step $k$. Right: next border $B_{k+1}$ after removal of state/node $s^{k+1} \in B_k$. Weights of edges to the right of the border do not change.</figcaption></figure>
## 4.2 Approximation by early stopping

Value iteration modifies the value of states by iteratively applying a contracting operator to the current value $V_k$. At each step, the value gains decrease, and we have $||V_{k+1} - V_k|| \le \lambda^k ||V_1 - V_0||$. It is hence natural to stop when the computed value is a good enough approximation of $V_*$. In [2], the authors use this observation to stop a Value Iteration scheme used to decide whether the value of a game can exceed a given threshold. Indeed, after a bound on the number of iterations, one can decide whether changes in a strategy can make the value of the game exceed the considered threshold. In this section, we show that the Floyd Warshall approach also give means for early stopping. $W(s^i, s^f)$ can be computed from any intermediate $A_k$ and yields the same value. Observe that in $A_k$, all paths of length at least 2 relating $s^i$ to $s^f$ must go through the border $B_k$. Denoting $P_{A_k}(s, s')$ the set of paths relating $s$ to $s'$ in $A_k$, and assuming an edge already exists from $s^i$ to $s^f$, one has:

$$ P_{A_k}(s^i, s^f) = (s^i, s^f) \uplus \bigcup_{s \in \partial_k^+(s^i)} (s^i, s) P_{A_k}(s, s^f) \quad (22) $$

which entails through the weight operator in $A_k$

$$ W(s^i, s^f) = W_k(s^i, s^f) \oplus \bigoplus_{s \in \partial_k^+(s^i)} W_k(s^i, s) \otimes W(s, s^f) \quad (23) $$

This expression always holds as $W_k(s^i, s^f) = \bar{0}$ if the edge $(s^i, s^f)$ does not exist in $A_k$, and relies on the fact that path integrals computed in $A_k$ and in $A$ coincide. The first term $W_k(s^i, s^f)$ represents the current value of state $s^i$ at step $k$, i.e. the expected reward of the MDP over runs starting at $s^i$ and going through states in $S_k$. This term grows to reach the desired quantity $W(s^i, s^f)$. The second term $\oplus_{s \in \partial_k^+(s^i)} W_k(s^i, s) \otimes W(s, s^f)$ is thus the error to the true value of $s^i$ due to ignoring some runs from $s^i$ to $s^f$ in the depth first graph traversal. Each contribution to the error term decomposes in turn as $g_k(s) = W_k(s_i, s)$, the current expected reward on paths from $s^i$ to state $s$ of the border, which is known at step $k$, and a remaining “reward to come after $s$” $W(s, s^f)$, which is unknown. If one can bound from above this future reward as $W(s, s^f) \le h(s)$, then a stopping criterion can be derived: the Floyd-Warshall procedure can be stopped at step $k$ if the upper bound $\oplus_{s \in \partial_k^+(s^i)} g_k(s) \otimes h(s)$ on the remaining rewards to be collected is negligible compared to the already collected one $W_k(s^i, s^f)$. The reader familiar with the A\* algorithm [7] computing a shortest path between $s^i$ and $s^f$ will notice a striking similarity: $g_k(s)$ resembles the current shortest distance from $s^i$ to node $s$ of the active set, and $h(s)$ resembles the “heuristic” function giving a lower bound on the remaining distance to $s^f$. Even more, the approach can be connected to the use of a heuristic for asynchronous Dynamic Programming in [3], inspired by Learning-Real-Time A\* [9]. An essential difference, however, is that A\* performs computations in the $(\min, +)$ semi-ring.
Nevertheless, this analogy is instructive: $A^*$ is a depth-first search algorithm, guided to the goal $s^f$ by the heuristic function $f$. It selects as next state $s$ to cross the one minimizing $g_k(s) + h(s)$. Here, this suggests a strategy to select $s^{k+1}$: one should pick state $s$ in $\partial_k^+(s^i)$ with the maximal expected contribution $W_k(s^i, s) \otimes h(s)$, in order to favor a quick visit of the most rewarding runs in $\mathcal{A}$. The existence of sharp heuristic functions bounding $W(s, s^f)$ from above is clearly dependent on the MDP domain (see Sec. 5 for examples). However, one has the following result:

**Proposition 2** Let $R_{max}$ be the maximal reward in MDP $\mathcal{M}$ for policy $\pi$, let $\mathcal{A} = \Phi(\mathcal{M}_{\pi}, \gamma)$ be the associated weighted automaton for discount factor $\gamma$. If state $s$ is at least $m$ transitions away from $s^f$ in $\mathcal{A}$, then $W(s, s^f) \le \gamma^{m-1} R_{max}$.

We refer readers to [6] for a proof. This result suggests that taking $h(s) = \gamma^{m-1} R_{max}$ as upper bound on the reward to come will favor the exploration of states $s$ that are the closest to the point $s^f$ where rewards are collected. But again tighter domain specific upper bounds $h(s)$ can exist.

Last, consider an MDP $\mathcal{M}$ and policy $\pi$ such that few states of $S$ bear a non-null reward, and for example $s^i$ is $m$ transitions away from the first state bearing a reward. Then the current value $W_k(s^i, s^f)$ of the accumulated rewards will remain at 0 for the first $k < m$ steps and will only make a sudden jump when $s^f$ is met for the first time. This suggests that the computation of $W(s^i, s^f)$ in $\mathcal{A}$ should not be made starting at $s^i$ and progressively accumulating runs to $s^f$, but conversely starting at $s^f$ to which all rewards point, and progressing backwards to reach $s^i$. Algebraically, this simply corresponds to inverting the orientation of all edges without changing their weight. Doing so, one can propagate the highest $W_k(s, s^f)$, i.e. the most promising accumulated rewards, back to $s^i$. These $W_k(s, s^f)$ are non-null by construction. As upper bound $h(s)$ for $W(s^i, s)$, one has this time $\gamma^m$ if $s$ is at least $m$ transitions away from $s^i$.

# 5 Case study

This section compares Progressive Floyd-Warshall (PFW) with Value Iteration (VI) and Linear Solving (LS). All algorithms have been implemented in Python3³, and we use a discount factor $\gamma = 0.98$ in all cases. We test FW and VI to evaluate the value of the optimal policy $\pi^*$ (calculated beforehand). Note however that PFW and VI can be used in Policy Iteration (line [a] of algorithm 2) to find $\pi^*$, and that PFW can be used for other applications than value computation, as shown in [6].

In our implementation of PFW, the next chosen state $s_{k+1}$ is the state of $B_k$ with the highest current value $W_k(s, s^f)$. As we are interested in the whole value vector $W(s, s^f)$ (needed for policy improvement in Policy Iteration), we update the relevant edges. On the other hand, starting from $V_0(s) = 0$ for all

<footnote n="3">³ Code available at https://gitlab.com/aymcome/phd/-/tree/main/code/FWPI.</footnote>
$s \in S$, we speed up calculus of the new estimate $V_{k+1}$ in VI by looking only at values of direct successors of each state. The algorithms will be compared w.r.t. their runtime in seconds, but also w.r.t. the number of operations. The latter is measured as the number of edges used at every iteration, as a tentative theoretical complexity. For PFW, at each iteration, the number of operations is $|\partial_k^-(s_{k+1}) \times (\partial_k^+(s_{k+1}) \setminus (S_k \cup \{s^f\}))|$, and for VI, $\sum_{s \in S} |\partial_k^+(s)|$. PFW and VI are compared on four standard test cases: GridWorld, RiverSwim, RandomDense and RandomSparse.

**GridWorld** is a 2D maze, with a starting state $s_0$, few goal states with rewards, and walls, which are absorbing states with no predecessor. The four available actions **Up**, **Right**, **Bottom**, **Left** lead to the corresponding adjacent state with a probability 0.7, but might slip to one of the three other adjacents states with a probability 0.3; if there is a wall, the agent stays at the same state. Multiple variants may be used, by default any action taken from a goal state gives the corresponding reward and teleports back to $s_0$ with probability 1. This mechanism hardens the exploration, compared with a shortest-path problem. The GridWorlds we use are randomly generated mazes with $s_0$ being located at the bottom-left corner, and the three goal states (always accessible) at the three other corners with a reward of 1 each; an example can be seen in Figure 4.

<figure><img src="image_4.png" /><figcaption>**Fig. 3.** The RiverSwim MDP of size $L+1$.</figcaption></figure>

**RiverSwim** (a.k.a. Chain MDP), drawn in Figure 3, is another standard example. It simulates a swimmer trying to go upstream. Going right (upstream) is hard, while going left is ensured; and yet the reward at $s_L$ is a hundred times higher than at $s_0$. A policy has to decide between fighting for a high reward or going for the smaller, easier one. Even with a small number of states, backpropagation of the reward is long, making this case study hard to solve.

Finally, **RandomDense** and **RandomSparse** are MDPs with randomly generated transitions and reward locations. Both MDPs have four actions. In the dense case, each state-action pair has a non-zero probability transition towards 70% of the state space, and only 1% in the sparse case. 2% of the state-action pairs (and at least one in the MDP) give a reward of value 1.

Let us first compare the propagation of values in VI and PFW when the two algorithms compute the value for $V_*$. We show snapshots of current state values at three different stages of the procedures, after an almost identical number of operations. VI shows a classical diffusion behavior (Fig. 4, first line) from
<figure><img src="image_5.png" /><figcaption>Fig. 4. Three stages of the VI (upper row) and FW (bottom row) procedures.</figcaption></figure>

the reward states. At each iteration, all states are updated, but the value of some states remain at 0 until the diffusion process reaches them. The diffusion is isotropic from each reward nodes and would progress in growing circles if there were no obstacles in the grid. Notice that the final value is not reached when all nodes have been visited once, since the process converges asymptotically: this breadth first exploration needs more iterations to properly capture the effect of circuits in the underlying state diagram. For the FW procedure (Fig. 4, second line), we used a backwards implementation starting at $s^f$ and progressing towards $s^i$, and the current values $W_k(s, s^f)$ are displayed, although one would only need those of the border to derive the final $W(s^i, s^f)$ representing the performance of policy $\pi$. Nodes of the border are depicted by black dots, and the one selected as the next state to integrate over, $s^{k+1}$, appears as a circled dot. At each step of the recursion, we chose to expand the state $s$ in the border with maximal $W_k(s, s^f)$. With such a strategy, the procedure takes also the shape of an isotropic diffusion of rewards in the grid. Observe however that for similar stages of VI and FW (center), values are higher with FW at nodes that are first hit (nodes of the border), since these values correspond to rewards over all paths within the already colored region (corresponding to $S_k$), whereas VI needs several more iterations to correctly capture the rewards due to the circuits in this region. We provide more insights on the differences in value propagation in [6].

The table 1 below shows experimental results for three algorithms: FW, VI and Linear Solving (LS). LS solve (6) using Gaussian elimination. The algorithms are compared on instances of Gridworld, RiverSwim, RandomDense and
RandomSparse of varying sizes. Since VI is an approximate approach, we compare PFW and LS to instances of VI stopping when current estimate of the value vector is close at 5%, 1% and 0.1% to the optimal value, in infinite norm $|| \cdot ||_{\infty}$.

Though PFW has a theoretical cubic worst case complexity, in practice it seems to require less time and operations than LS, on all selected MDPs. This shows the impact of updating only the necessary edges in $W_k$, hence greatly reducing the number of operations per iteration. In fact, FW is even more efficient than VI in RiverSwim, thanks to the particular structure that keeps a low number of neighboring states throughout the iterations. On the other hand, as the size of the problem increases FW seems to fall off for RandomDense and RandomSparse MDPs: the number of edges scaling with the size quickly builds up the border, meanwhile vertices in GridWorld and RiverSwim never have more than 5 successors. Hence it appears that the Floyd-Warshall approach benefits from more structured environments, Riverswim being a best case. As a final note, FW always is the most efficient for small size MDPs. More discussion is available in [6].

<table><caption>**Table 1.** Runtimes and number of operations (in bold, k# and M# mean $10^3$ and $10^6$ operations respectively) of PFW, VI, and LS. The results are averaged over 10 runs each time.</caption><thead><tr><th>Environment</th><th>Size</th><th>FW</th><th>VI 5%</th><th>VI 1%</th><th>VI 0.1%</th><th>LS</th></tr></thead><tbody><tr><td rowspan="3">GridWorld</td><td>11 x 11</td><td>6.49 ms <b>13586</b> #</td><td>30.3 ms <b>89592</b> #</td><td>45.5 ms <b>133742</b> #</td><td>67.6 ms <b>197023</b> #</td><td>849 ms <b>1771561</b> #</td></tr><tr><td>25 x 25</td><td>412 ms <b>1029</b> k#</td><td>196 ms <b>601</b> k#</td><td>267 ms <b>821</b> k#</td><td>372 ms <b>1148</b> k#</td><td>118000 ms <b>244141</b> k#</td></tr><tr><td>35 x 35</td><td>2.26 s <b>5671</b> k#</td><td>0.424 s <b>1320</b> k#</td><td>0.563 s <b>1754</b> k#</td><td>0.768 s <b>2392</b> k#</td><td>892 s <b>1838266</b> k#</td></tr><tr><td rowspan="3">RiverSwim</td><td>|S| = 100</td><td>5.10 ms <b>10198</b> #</td><td>33.2 ms <b>97148</b> #</td><td>40.3 ms <b>120988</b> #</td><td>52.1 ms <b>154960</b> #</td><td>480 ms <b>1000000</b> #</td></tr><tr><td>|S| = 625</td><td>47.6 ms <b>91.0</b> k#</td><td>217 ms <b>697</b> k#</td><td>264 ms <b>847</b> k#</td><td>330 ms <b>1060</b> k#</td><td>118000 ms <b>244141</b> k#</td></tr><tr><td>|S| = 1225</td><td>69.1 ms <b>117</b> k#</td><td>423 ms <b>1366</b> k#</td><td>514 ms <b>1660</b> k#</td><td>644 ms <b>2079</b> k#</td><td>894000 ms <b>1838266</b> k#</td></tr><tr><td rowspan="3">RandomDense</td><td>|S| = 100</td><td>210 ms <b>498</b> k#</td><td>293 ms <b>1034</b> k#</td><td>449 ms <b>1585</b> k#</td><td>672 ms <b>2376</b> k#</td><td>480 ms <b>1000</b> k#</td></tr><tr><td>|S| = 625</td><td>51.2 s <b>122</b> M#</td><td>11.2 s <b>40.6</b> M#</td><td>17.1 s <b>62.1</b> M#</td><td>25.7 s <b>93.2</b> M#</td><td>118 s <b>244</b> M#</td></tr><tr><td>|S| = 1225</td><td>396 s <b>919</b> M#</td><td>43.0 s <b>156</b> M#</td><td>65.9 s <b>239</b> M#</td><td>98.9 s <b>358</b> M#</td><td>892 s <b>1838</b> M#</td></tr><tr><td rowspan="3">RandomSparse</td><td>|S| = 100</td><td>1.69 ms <b>1503</b> #</td><td>32.5 ms <b>27362</b> #</td><td>48.1 ms <b>39892</b> #</td><td>68.1 ms <b>57873</b> #</td><td>478 ms <b>1000000</b> #</td></tr><tr><td>|S| = 625</td><td>17.6 s <b>45074</b> k#</td><td>0.429 s <b>561</b> k#</td><td>0.658 s <b>861</b> k#</td><td>0.986 s <b>1290</b> k#</td><td>118 s <b>244141</b> k#</td></tr><tr><td>|S| = 1225</td><td>250 s <b>619</b> M#</td><td>1.48 s <b>2.19</b> M#</td><td>2.26 s <b>3.35</b> M#</td><td>3.37 s <b>5.02</b> M#</td><td>892 s <b>1838</b> M#</td></tr></tbody></table>

## 6 Conclusion

This work has proposed a reformulation of the value estimation problem in MDPs as an integral over runs of a weighted automaton, that can be computed by a Floyd-Warshall procedure. This new perspective offers several advantages: it recasts under the same algebraic roof several apparently disconnected problems, as the computation of the gradient of the value, or its variance. But it also opens the way to several strategies to collect run rewards more efficiently, by properly processing cycles and by enabling a depth-first exploration. The first experiments reveal performance gains on some (but not all) benchmarks, and show that this approach could be turned into an approximation scheme for policy iteration. Future work will characterise the problems for which gains are obtained, using heuristics to guide the search towards most impacting runs.
References

1. Balle, B., Mohri, M.: Learning weighted automata. In: Maletti, A. (ed.) Algebraic Informatics - 6th International Conference, CAI 2015, Proceedings. LNCS, vol. 9270, pp. 1–21. Springer (2015). https://doi.org/10.1007/978-3-319-23021-4\"1, https://doi.org/10.1007/978-3-319-23021-4\_1

2. Bansal, S., Chatterjee, K., Vardi, M.Y.: On satisfying in quantitative games. In: Tools and Algorithms for the Construction and Analysis of Systems: TACAS 2021, Proceedings, Part I 27. LNCS, vol. 12651, pp. 20–37. Springer (2021)

3. Barto, A.G., Bradtke, S.J., Singh, S.P.: Learning to act using real-time dynamic programming. Artificial intelligence **72**(1-2), 81–138 (1995). https://doi.org/10.1016/0004-3702(94)00011-0

4. Bazille, H., Fabre, E., Genest, B.: Diagnosability degree of stochastic discrete event systems. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC). pp. 5726–5731 (2017). https://doi.org/10.1109/CDC.2017.826452

5. Bertsekas, D.P.: Dynamic programming and optimal control (1995)

6. Come, A., Fabre, E., Hélouët, L.: A Floyd-Warshall approach to value computation in markov decision processes (extended version). Tech. rep., https://inria.hal.science/hal-04619555 (2024)

7. Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics **4**(2), 100–107 (1968). https://doi.org/10.1109/TSSC.1968.300136

8. Howard, R.A.: Dynamic programming and markov processes (1960), https://api.semanticscholar.org/CorpusID:62124406

9. Korf, R.E.: Real-time heuristic search. Artificial intelligence **42**(2-3), 189–211 (1990). https://doi.org/10.1016/0004-3702(90)90054-4

10. Moore, A.W., Atkeson, C.G.: Prioritized sweeping: Reinforcement learning with less data and less time. Mach. Learn. **13**(1), 103–130 (oct 1993). https://doi.org/10.1023/A:1022635613229, https://doi.org/10.1023/A:1022635613229

11. Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., USA, 1st edn. (1994)

12. Schrijver, A.: Theory of linear and integer programming. Wiley-Interscience series in discrete mathematics and optimization, Wiley (1999)

13. Sobel, M.J.: The variance of discounted markov decision processes. Journal of Applied Probability **19**(4), 794–802 (1982)

14. Sutton, R.S., Barto, A.G.: Reinforcement learning: An introduction. IEEE Transactions on Neural Networks **16**, 285–286 (2005)