* The discounted sum is defined as $\sum{i \in \mathbb{N}} wi \lambda^i$ for a sequence $w0 w1 w2 \cdots$ over $\Sigma$ and discount factor $\lambda$.
* The target discounted-sum problem asks if an infinite sequence exists with a specific discounted sum $t$, given $\lambda$, $\Sigma$, and $t$.
* The study analyzes a probabilistic variant of this problem on Markov chains.
* The event of paths whose discounted sum equals the target and have infinitely many distinct suffix sums has probability zero.
* This structural property allows solving the target discounted-sum problem on Markov chains using automata-theoretic techniques.
* The results are applied to Markov decision processes with target discounted-sum objectives.
* The infimum value and the finite-memory supremum value for these MDPs are computable in pseudo-polynomial time.
* These infimum and supremum values are attained by deterministic finite-memory strategies.

The investigation bridges theoretical control theory (discounted sums) with probabilistic structures (Markov chains) and decision-making frameworks (MDPs). The core insight is that an apparently open existence problem can be resolved by exploiting a measure-theoretic property—the zero probability of paths exhibiting simultaneously desired properties. This suggests that complexity in path existence is often constrained by underlying structural limitations, allowing automata theory to provide a solution pathway rather than requiring exhaustive search over infinite sets.
The transition from static sequence existence (Markov chains) to dynamic optimization (MDPs) is significant because it connects purely mathematical existence proofs to practical computational objectives. Showing that optimal values for discounted sums in MDPs are achievable by deterministic finite-memory strategies implies a strong link between theoretical computability and realizable, tractable policies. The pattern here suggests that problems defined over infinite structures often yield to finite, computable bounds when structured correctly through state-space reduction or automata construction.
What remains is the nature of "pseudo-polynomial time" in this context and how these finite memory strategies map onto real-world strategic decision-making, particularly concerning the trade-off between optimal achievable values (infimum/supremum) and the strategies that realize them. Does this method offer a universal framework for analyzing infinite reward accumulation under uncertainty, or is its utility fundamentally constrained to the specific structure of Markov processes?