DefinitionDefinition: Literature-sourcedProof: AI-generatedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Finite stochastic shortest-path problems

Definition

Let a finite MDP have nonempty finite state set $S$ and finite nonempty action sets $A (s)$ . A finite stochastic shortest-path problem consists of that MDP, a nonempty goal set $G \subseteq S$ , and a constant $c_{\min} > 0$ with the following properties. Each goal $g \in G$ has exactly one available action $a_{g}$ , and its joint reward-transition law satisfies $p (g, 0 ∣ g, a_{g}) = 1$ (so $0 \in R$ ). For every $s \notin G$ and every $a \in A (s)$ , the expected reward satisfies $r (s, a) \leq - c_{\min}$ . Define the one-step expected cost by $c (s, a) = - r (s, a)$ off $G$ and $c (g, a) = 0$ at goals. A stationary Markov policy $π$ is proper if, from every initial state, the finite-step probabilities of not having reached $G$ tend to $0$ : with $q_{0} (s) = 1_{s \notin G}$ and

$q_{n + 1} (s) = \sum_{a \in A (s)} π (a ∣ s) \sum_{s^{'} \in S} P (s^{'} ∣ s, a) q_{n} (s^{'}) (s \notin G), q_{n + 1} (g) = 0 (g \in G),$

properness means $q_{n} (s) \to 0$ for every $s \in S$ . The problem need not have a proper policy unless that is separately assumed.

Definition references

A finite MDP has finite states and actions, a joint reward/transition law, and derived expected rewards and transition probabilities.

Barto, Bradtke, and Singh, “Learning to Act Using Real-Time Dynamic Programming”.

Facts & Assumptions

Given: A finite MDP, nonempty goal set $G$ , absorbing zero-reward dummy actions at goals, and the strict negative expected-reward bound on every nonglobal state-action pair in the Definition.

[F1]

Finite Markov decision process with joint reward-transition law: each $A (s)$ is finite and nonempty; $P (\cdot ∣ s, a)$ is a probability distribution obtained by marginalizing the joint reward-transition law, and $r (s, a)$ is its expected one-step reward.

Verification

Given: The finite MDP data and a stationary Markov policy $π$ .

1.1givenF1algebra

The expected costs $c (s, a) = - r (s, a)$ are finite because the reward alphabet is finite and the joint row is a probability mass by [F1]. The stated reward bound gives $c (s, a) \geq c_{\min} > 0$ off $G$ , and the dummy action at each goal has cost $0$ .

2.1givenF1step 1.1algebra∎

By [F1], every row $P (\cdot ∣ s, a)$ is a probability distribution, and every policy row $π (\cdot ∣ s)$ is a probability distribution. Thus the recursion defining $q_{n + 1}$ is a finite sum of nonnegative terms. If $0 \leq q_{n} \leq 1$ , then $0 \leq q_{n + 1} (s) \leq \sum_{a} π (a ∣ s) \sum_{s^{'}} P (s^{'} ∣ s, a) = 1$ off $G$ , while $q_{n + 1} (g) = 0$ on $G$ . Since $q_{0} \in [0, 1]^{S}$ , induction shows every $q_{n}$ is well-defined and lies in $[0, 1]^{S}$ .

Depends on

Finite Markov decision process with joint reward-transition law

Used by

Trial-based real-time dynamic programming Algorithm
RTDP need not visit every state reachable under an optimal policy Counterexample
Asynchronous value iteration for finite positive-cost shortest paths Lemma
Finite positive-cost stochastic shortest-path value Theorem
RTDP convergence on recurrently backed states Theorem

Dependency tree · two levels

12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Andrew G. Barto, Steven J. Bradtke, and Satinder P. Singh, Learning to Act Using Real-Time Dynamic Programming (standard reference, not scraped)