LemmaStatement: AI-adaptedProof: 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.

One-step total-variation propagation under a fixed policy

Statement

Let $S$ be a finite nonempty set, let $A (s)$ be finite and nonempty for each $s \in S$ , and let $P (\cdot ∣ s, a)$ and $\hat{P} (\cdot ∣ s, a)$ be probability distributions on $S$ for each admissible pair. For distributions $u, v$ on $S$ , write $TV (u, v) = \frac{1}{2} \sum_{x \in S} ∣ u (x) - v (x) ∣$ . Let $π (\cdot ∣ s)$ be a probability distribution on $A (s)$ for each state. Define the induced transition rows

$K^{π} (s, x) = \sum_{a \in A (s)} π (a ∣ s) P (x ∣ s, a), {\hat{K}}^{π} (s, x) = \sum_{a \in A (s)} π (a ∣ s) \hat{P} (x ∣ s, a) .$

If $d$ and $\hat{d}$ are probability distributions on $S$ and, for some $ϵ \geq 0$ ,

$TV (P (\cdot ∣ s, a), \hat{P} (\cdot ∣ s, a)) \leq ϵ$

whenever $\hat{d} (s) > 0$ and $π (a ∣ s) > 0$ , then

$TV (d K^{π}, \hat{d} {\hat{K}}^{π}) \leq TV (d, \hat{d}) + ϵ .$

Here $d K^{π}$ and $\hat{d} {\hat{K}}^{π}$ are the next-state distributions obtained by applying the indicated transition rows.

Statement references

Total variation is the event-supremum distance on probability laws.

For finite discrete laws, total variation is one half of the sum of absolute mass differences.

Facts & Assumptions

Given: The finite state/action sets, true and estimated transition rows, policy rows, state distributions, and row-error bound in the Statement.

[F1]

Finite learned transition and reward models: each true and learned transition row is a probability distribution on the same finite state set; its total-variation error is the half- $ℓ^{1}$ distance.

[F2]

Measure kernel and probability kernel: a probability kernel has probability-measure sections and measurable event sections; on finite discrete spaces each row table is a probability kernel.

[F3]

Total variation distance for probability laws and Half- $ℓ^{1}$ formula for total variation on a countable space: on finite discrete $S$ , $TV (u, v) = \frac{1}{2} \sum_{x} ∣ u (x) - v (x) ∣$ and this equals the supremum of event-probability differences.

[F4]

Total variation duality, kernel contraction, and coupling bound: applying one probability kernel to two input probability laws cannot increase their total-variation distance.

[F5]

Basic properties of the absolute value: absolute value is nonnegative and $∣ u v ∣ = ∣ u ∣ ∣ v ∣$ for real $u, v$ .

[F6]

Triangle inequality for finite sums: for every finite initial segment, the absolute value of a sum of reals is at most the sum of their absolute values.

[F7]

Laws of finite sums and finite products: finite sums obey additivity and recursion, so finite repeated sums may be expanded using the field laws.

[F8]

The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form: sums over a finite set are independent of enumeration and invariant under bijective reindexing.

Proof

1.1givenF1F2F4algebra

For each state $s$ , the policy mixture $K^{π} (s, \cdot)$ is a probability distribution because it is a convex combination of the probability rows $P (\cdot ∣ s, a)$ ; the same holds for ${\hat{K}}^{π}$ . The state set is finite discrete, so both row tables are probability kernels by [F2]. Applying [F4] to the common kernel $K^{π}$ gives $TV (d K^{π}, \hat{d} K^{π}) \leq TV (d, \hat{d})$ .

1.2givenF1F3F5F6F7F8algebra

Enumerate the finite set $D$ of admissible state-action pairs. For each $x \in S$ , the finite-sum triangle inequality [F6] and absolute-value product formula [F5] give $TV (\hat{d} K^{π}, \hat{d} {\hat{K}}^{π}) = \frac{1}{2} \sum_{x \in S} ∣ \sum_{(s, a) \in D} \hat{d} (s) π (a ∣ s) (P (x ∣ s, a) - \hat{P} (x ∣ s, a)) ∣ \leq \frac{1}{2} \sum_{x \in S} \sum_{(s, a) \in D} \hat{d} (s) π (a ∣ s) ∣ P (x ∣ s, a) - \hat{P} (x ∣ s, a) ∣$ . The finite sums over $S$ and $D$ can be interchanged: enumerate both sets, expand by additivity [F7], and use the coordinate-swap bijection with enumeration invariance [F8]. This gives $\sum_{s \in S} \hat{d} (s) \sum_{a \in A (s)} π (a ∣ s) \frac{1}{2} \sum_{x \in S} ∣ P (x ∣ s, a) - \hat{P} (x ∣ s, a) ∣ \leq ϵ$ . The last inequality uses the row bound on every positive-weight pair; zero-weight terms vanish, and the weights sum to $\sum_{s} \hat{d} (s) \sum_{a} π (a ∣ s) = 1$ because both rows are probability distributions.

2.1F5F6step 1.1step 1.2algebra∎

For every $x \in S$ , write $d K^{π} (x) - \hat{d} {\hat{K}}^{π} (x) = [d K^{π} (x) - \hat{d} K^{π} (x)] + [\hat{d} K^{π} (x) - \hat{d} {\hat{K}}^{π} (x)]$ . The scalar triangle inequality [F5], summed over finite $S$ using [F6], gives $TV (d K^{π}, \hat{d} {\hat{K}}^{π}) \leq TV (d K^{π}, \hat{d} K^{π}) + TV (\hat{d} K^{π}, \hat{d} {\hat{K}}^{π})$ . Steps 1.1 and 1.2 bound the right side by the claim.

Depends on

Used by

Finite-horizon simulation bound for one fixed policy Theorem

Dependency tree · two levels

40 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)