§3, discounted case (p. 447) — the min-plus products B_j are the cheapest discounted j-arc walks

Let $0<\beta<1$, and let $B_j=A\otimes\beta A\otimes\cdots\otimes\beta^{j-1}A$ be the min-plus product of the scaled cost matrices of a finite deterministic Markov decision process ($B_0$ the min-plus identity). For all $j\ge0$ and states $u,v$:

1. $(B_j)_{uv}=+\infty$ if and only if there is no walk with $j$ arcs from $u$ to $v$;
2. otherwise $(B_j)_{uv}$ is a real number, and it is the least discounted length

over all $j$-arc walks $W=(w_0=u,e_0,w_1,\dots,e_{j-1},w_j=v)$, the minimum being attained.

This is what makes the matrix products compute "the shortest discounted path" with a prescribed number of arcs; the arcs of a walk may repeat nodes, and parallel decisions contribute their cheapest one.

Formalization Note The paper says "the $(u,v)$th entry of $B_j$ is the length of the shortest path with $j$ arcs from $u$ to $v$" in the sense of the discounted length (the $t$-th arc weighted by $\beta^t$). We define $B_j$ as the matrix product and state its walk interpretation here. Entries are in Tropical (WithTop ℝ); trop ⊤ is $+\infty$.