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-horizon return under a Markov policy

Definition

Let $S$ be a nonempty finite state set, let $A (s)$ be a nonempty finite action set for each $s \in S$ , let $r (s, a) \in [0, 1]$ , and let $P (\cdot ∣ s, a)$ be a probability distribution on $S$ for each admissible pair. A finite-horizon Markov policy of horizon $H \in N$ with $H \geq 1$ is a family of probability distributions $π_{t} (\cdot ∣ s)$ on $A (s)$ for $0 \leq t < H$ . Given an initial state distribution $μ$ , define $d_{0} = μ$ and, for $0 \leq t < H - 1$ ,

$d_{t + 1} (s^{'}) = \sum_{s \in S} \sum_{a \in A (s)} d_{t} (s) π_{t} (a ∣ s) P (s^{'} ∣ s, a) .$

The finite-horizon expected return is

$J_{H} (M, μ, π) = \sum_{t = 0}^{H - 1} \sum_{s \in S} \sum_{a \in A (s)} d_{t} (s) π_{t} (a ∣ s) r (s, a) .$

The same definition applies to a learned model by replacing $r, P$ with its estimated reward and transition tables. It is the expected sum of the $H$ one-step rewards; no discount factor or terminal continuation value is included.

Definition references

A finite learned model supplies finite state/action sets, bounded reward means, and probability transition rows.

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems.

Facts & Assumptions

Given: A finite reward/transition model, an initial probability distribution $μ$ , a positive integer horizon $H$ , and the finite family of policy distributions in the Definition.

[F1]

Finite learned transition and reward models: $S$ and every $A (s)$ are finite and nonempty, $r (s, a) \in [0, 1]$ , and each row $P (\cdot ∣ s, a)$ is a probability distribution.

Verification

Given: The model, initial distribution, horizon, and Markov policy in the Definition.

1.1givenF1algebra

The initial vector $d_{0} = μ$ is a probability distribution. If $d_{t}$ is a probability distribution, every term in the recursion is nonnegative and $\sum_{s^{'} \in S} d_{t + 1} (s^{'}) = \sum_{s \in S} d_{t} (s) \sum_{a \in A (s)} π_{t} (a ∣ s) \sum_{s^{'} \in S} P (s^{'} ∣ s, a) = \sum_{s \in S} d_{t} (s) = 1$ , because each policy and transition row has total mass one by [F1]. Induction proves that every $d_{t}$ is a probability distribution.

2.1givenF1step 1.1algebra∎

Each summand in $J_{H}$ is nonnegative, and at each time $t$ its sum is at most $\sum_{s} d_{t} (s) = 1$ because rewards lie in $[0, 1]$ by [F1]. The $H$ finite time sums therefore define a real number in $[0, H]$ .

Depends on

Finite learned transition and reward models

Used by

Finite-horizon model-predictive control Algorithm
Model exploitation under support shift Definition
Finite-horizon simulation bound for one fixed policy Theorem

Dependency tree · two levels

8 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

Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (standard reference, not scraped)