DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-generated

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.

Episodic returns, temporal-difference errors, and policy support

Definition

Let a finite MDP have $0 \leq γ < 1$ and let $S_{†} \subseteq S$ be a set of terminal states. Form an absorbing extension with reward alphabet $R^{†} = R \cup {0}$ : from each nonterminal state retain the original joint reward-transition law, and from each terminal state use the deterministic transition back to that state with reward zero. Assume AC for the path laws defining policy values. For a stationary policy $σ$ , an episode starting from $s$ ends at its first hitting time $T = \inf {n \geq 0 : S_{n} \in S_{†}}$ ; require $T < \infty$ almost surely under every policy used. The return from time $t < T$ is

G_{t} = \sum_{k = t}^{T - 1} γ^{k - t} R_{k + 1},

and $G_{T} = 0$ . This equals the infinite discounted return of the absorbing extension, whose state value is $V^{σ} (s) = E_{σ, s} [G_{0}]$ .

For a state-value estimate $V_{n}$ , the state temporal-difference error on a transition is $δ_{n}^{V} = R_{n + 1} + γ V_{n} (S_{n + 1}) - V_{n} (S_{n})$ . For an action-value estimate $Q_{n}$ , the sampled-action Sarsa error is $δ_{n}^{S a r s a} = R_{n + 1} + γ Q_{n} (S_{n + 1}, A_{n + 1}) - Q_{n} (S_{n}, A_{n})$ , and the greedy Q-learning error is $δ_{n}^{Q} = R_{n + 1} + γ \max_{b \in A (S_{n + 1})} Q_{n} (S_{n + 1}, b) - Q_{n} (S_{n}, A_{n})$ . In each error, the continuation term is defined as zero when $S_{n + 1}$ is terminal.

In off-policy prediction, $μ$ denotes the behavior policy generating episodes and $π$ the target policy whose value is estimated. Target support means $π (a ∣ s) > 0$ implies $μ (a ∣ s) > 0$ for every state-action pair that can be visited. For a behavior-generated episode, the state-return likelihood ratio from time $t$ is

Λ_{t : T - 1} = \prod_{k = t}^{T - 1} \frac{π (A_{k} ∣ S_{k})}{μ (A_{k} ∣ S_{k})} .

Each denominator is positive on the observed behavior path. When estimating a value conditional on an already fixed action $A_{t}$ , the first factor begins at time $t + 1$ .

Definition references

The finite joint reward-transition law and stationary Markov policies.

The action-state-reward trajectory law and its finite-prefix probabilities.

The infinite discounted return, its path-law expectation, and its boundedness for bounded rewards.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.

Depends on

Used by

Dependency tree · two levels

29 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

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (standard reference, not scraped)
Han-Dong Yang, Optimal Control and Reinforcement Learning, Chapter 2: Value-based Reinforcement Learning (standard reference, not scraped)