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 learned transition and reward models

Definition

Let the true environment be a finite Markov decision process with nonempty finite state set $S$ , nonempty finite action sets $A (s)$ , a finite reward alphabet contained in $[0, 1]$ , and joint next-state/reward probabilities $p (s^{'}, ρ ∣ s, a)$ . Write $D = {(s, a) : s \in S, a \in A (s)}$ , and let $r (s, a)$ and $P (s^{'} ∣ s, a)$ be the expected reward and next-state probabilities obtained by summing this joint law. A finite learned model on the same state and action sets consists of estimates $\hat{r} : D \to [0, 1]$ and probability distributions $\hat{P} (\cdot ∣ s, a)$ on $S$ for every $(s, a) \in D$ . The estimated transition table is a probability kernel on the finite discrete spaces.

For each $(s, a) \in D$ , define the reward error $e_{r} (s, a) = ∣ r (s, a) - \hat{r} (s, a) ∣$ and transition error

$e_{P} (s, a) = \frac{1}{2} \sum_{s^{'} \in S} ∣ P (s^{'} ∣ s, a) - \hat{P} (s^{'} ∣ s, a) ∣ .$

For any subset $C \subseteq D$ , define $ϵ_{r} (C) = \max_{(s, a) \in C} e_{r} (s, a)$ and $ϵ_{P} (C) = \max_{(s, a) \in C} e_{P} (s, a)$ when $C \neq \emptyset$ , and set both quantities to $0$ when $C = \emptyset$ . These are uniform expected-reward and total-variation errors on $C$ ; the learned model definition makes no accuracy assertion.

Definition references

The true finite MDP has finite states, state-specific finite nonempty actions, and a joint next-state/reward law whose marginals define the expected reward and transition probabilities.

A probability kernel assigns a probability measure to every input and has measurable event sections; finite discrete tables satisfy this condition.

Total variation of two probability laws is the supremum of their event-probability difference, with no half-factor in that supremum convention.

On a finite or countable discrete space, total variation equals one half of the sum of the absolute singleton-mass differences.

Sutton and Barto, Reinforcement Learning: An Introduction.

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

Facts & Assumptions

Given: A finite MDP with nonempty finite $S$ and $A (s)$ , reward alphabet contained in $[0, 1]$ , joint masses $p (s^{'}, ρ ∣ s, a)$ , and proposed estimates $\hat{r}$ and $\hat{P}$ satisfying the Definition.

[F1]

Finite Markov decision process with joint reward-transition law: each joint row $p (\cdot, \cdot ∣ s, a)$ is a probability mass function; $r (s, a) = \sum_{s^{'}, ρ} ρ p (s^{'}, ρ ∣ s, a)$ and $P (s^{'} ∣ s, a) = \sum_{ρ} p (s^{'}, ρ ∣ s, a)$ .

[F2]

Measure kernel and probability kernel: a probability kernel has probability-measure sections and measurable event sections; on finite discrete input and output spaces every event section is measurable.

[F3]

Total variation distance for probability laws and Half- $ℓ^{1}$ formula for total variation on a countable space: total variation is the event-supremum distance and, on finite discrete $S$ , equals $\frac{1}{2} \sum_{s^{'}} ∣ P (s^{'}) - Q (s^{'}) ∣$ .

[F4]

Every nonempty finite set of reals has a maximum and a minimum: every nonempty finite set of real numbers has an attained maximum.

[F5]

The triangle inequality: for real $u, v$ , $∣ u + v ∣ \leq ∣ u ∣ + ∣ v ∣$ .

[F6]

Basic properties of the absolute value: $∣ u ∣ \geq 0$ and $∣ - u ∣ = ∣ u ∣$ for every real $u$ .

Verification

Given: The finite MDP, the estimated transition and reward table, and the definitions and finite-set hypotheses in the Definition.

1.1givenF1F2algebra

For each pair $(s, a)$ , $P (s^{'} ∣ s, a) \geq 0$ and $\sum_{s^{'}} P (s^{'} ∣ s, a) = \sum_{s^{'}, ρ} p (s^{'}, ρ ∣ s, a) = 1$ by [F1]. Thus every true transition row is a probability law. The proposed $\hat{P}$ rows have this property by the Given condition. Since the spaces are finite and discrete, [F2] makes both transition tables probability kernels. The reward alphabet lies in $[0, 1]$ , so its probability-weighted finite sum $r (s, a)$ also lies in $[0, 1]$ , as does $\hat{r} (s, a)$ by assumption.

2.1givenF3F4F5F6step 1.1algebra∎

For each pair, $∣ P (s^{'} ∣ s, a) - \hat{P} (s^{'} ∣ s, a) ∣ \leq P (s^{'} ∣ s, a) + \hat{P} (s^{'} ∣ s, a)$ by [F5] and [F6]. Summing over $s^{'}$ gives at most $2$ , so $0 \leq e_{P} (s, a) \leq 1$ ; also $0 \leq e_{r} (s, a) \leq 1$ because both rewards lie in $[0, 1]$ . By [F3], the displayed half-sum is exactly the library total-variation convention on $S$ . The set $D$ and each $C \subseteq D$ are finite; therefore [F4] gives attained maxima when $C$ is nonempty, and the empty-set convention defines the remaining case. All model errors in the Definition are consequently well-defined.

Depends on

Used by

Finite-horizon model-predictive control Algorithm
Tabular Dyna-Q with a deterministic last-observation model Algorithm
Finite-horizon return under a Markov policy Definition
Model exploitation under support shift Definition
A small transition error accumulates over longer rollouts Example
An inaccurate model can give the exact return on behavior support Example
One-step total-variation propagation under a fixed policy Lemma
Ensemble disagreement is not calibrated uncertainty by definition Remark
Finite-horizon simulation bound for one fixed policy Theorem

Dependency tree · two levels

27 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, second-edition-in-progress (standard reference, not scraped)
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (standard reference, not scraped)