TheoremStatement: 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 simulation bound for one fixed policy

Statement

Let $M = (S, (A (s))_{s \in S}, r, P)$ and $\hat{M} = (S, (A (s))_{s \in S}, \hat{r}, \hat{P})$ be finite models on a common nonempty finite state set and common nonempty finite action sets, with $r, \hat{r} \in [0, 1]$ and probability transition rows. Fix a horizon $H \geq 1$ , a common initial state law $μ$ , and one possibly time-dependent randomized Markov policy $π = (π_{t})_{t = 0}^{H - 1}$ . Let $d_{t}$ and ${\hat{d}}_{t}$ be the state occupancies under $M$ and $\hat{M}$ , respectively, starting from $d_{0} = {\hat{d}}_{0} = μ$ . Define

$C_{H}^{π} = {(s, a) : d_{t} (s) π_{t} (a ∣ s) > 0 or {\hat{d}}_{t} (s) π_{t} (a ∣ s) > 0 for some 0 \leq t < H} .$

Suppose $∣ r (s, a) - \hat{r} (s, a) ∣ \leq ϵ_{r}$ and $TV (P (\cdot ∣ s, a), \hat{P} (\cdot ∣ s, a)) \leq ϵ_{p}$ for every $(s, a) \in C_{H}^{π}$ , where $TV (p, q) = \frac{1}{2} \sum_{s^{'}} ∣ p (s^{'}) - q (s^{'}) ∣$ . Then

$∣ J_{H} (M, μ, π) - J_{H} (\hat{M}, μ, π) ∣ \leq H ϵ_{r} + (\binom{H}{2}) ϵ_{p} .$

The guarantee concerns this fixed policy and the stated reachable pairs; it does not bound the policy selected by optimizing the learned model.

Statement references

The finite models share a state-action domain, bounded expected rewards, and probability transition rows; model errors use uniform reward error and total variation.

Finite-horizon Markov-policy occupancies and returns are defined by a finite recursion and sum.

Facts & Assumptions

Given: The finite models, common law, horizon, fixed policy, reachable-pair error bounds, and notation in the Statement.

[F1]

Finite learned transition and reward models: every transition row is a probability distribution on the common finite state set, and both reward means lie in $[0, 1]$ .

[F2]

Finite-horizon return under a Markov policy: each model's state occupancy is propagated by the policy-weighted transition row, and its return is the sum of the policy-weighted expected rewards for times $0$ through $H - 1$ .

[F3]

One-step total-variation propagation under a fixed policy: if transition-row total-variation error is at most $ϵ_{p}$ on all pairs with positive learned state-action occupancy under a policy row, then the next-state total-variation distance is at most the current distance plus $ϵ_{p}$ .

[F4]

Half- $ℓ^{1}$ formula for total variation on a countable space: on the finite state set, total variation is one half of the sum of absolute mass differences.

[F5]

The triangle inequality: for real $u, v$ , $∣ u + v ∣ \leq ∣ 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.

Proof

Given: The two finite models, common initial law, fixed policy, and error bounds from the Statement.

1.1givenF1F2F3algebra

At time $0$ , $TV (d_{0}, {\hat{d}}_{0}) = 0$ . If $0 \leq t < H - 1$ , every pair with ${\hat{d}}_{t} (s) π_{t} (a ∣ s) > 0$ belongs to $C_{H}^{π}$ , so its transition rows satisfy [F3]. Applying [F3] to the policy at time $t$ gives $TV (d_{t + 1}, {\hat{d}}_{t + 1}) \leq TV (d_{t}, {\hat{d}}_{t}) + ϵ_{p}$ . Induction yields $TV (d_{t}, {\hat{d}}_{t}) \leq t ϵ_{p}$ for every $0 \leq t < H$ .

2.1givenF1F2F4F5step 1.1algebra

For a fixed time $t$ , set $g_{t} (s) = \sum_{a} π_{t} (a ∣ s) r (s, a)$ and ${\hat{g}}_{t} (s) = \sum_{a} π_{t} (a ∣ s) \hat{r} (s, a)$ . These functions lie in $[0, 1]$ by [F1]. For $x_{s} = d_{t} (s) - {\hat{d}}_{t} (s)$ , one has $\sum_{s} x_{s} = 0$ ; by [F4] the total positive mass and total negative mass of $(x_{s})$ both equal $TV (d_{t}, {\hat{d}}_{t})$ . Since $0 \leq g_{t} (s) \leq 1$ , it follows that $∣ \sum_{s} x_{s} g_{t} (s) ∣ \leq TV (d_{t}, {\hat{d}}_{t})$ . Also, every pair with ${\hat{d}}_{t} (s) π_{t} (a ∣ s) > 0$ lies in $C_{H}^{π}$ , so $∣ \sum_{s, a} {\hat{d}}_{t} (s) π_{t} (a ∣ s) (r (s, a) - \hat{r} (s, a)) ∣ \leq ϵ_{r}$ . Decomposing the difference of the two time- $t$ expected rewards and applying [F5] gives an absolute difference at most $t ϵ_{p} + ϵ_{r}$ by step 1.1.

3.1F2F6step 2.1algebra∎

By [F2], the return difference is the sum of the $H$ timewise expected-reward differences. The finite-sum triangle inequality [F6] and step 2.1 therefore give $∣ J_{H} (M, μ, π) - J_{H} (\hat{M}, μ, π) ∣ \leq \sum_{t = 0}^{H - 1} (t ϵ_{p} + ϵ_{r}) = H ϵ_{r} + \frac{H (H - 1)}{2} ϵ_{p} = H ϵ_{r} + (\binom{H}{2}) ϵ_{p}$ . The arithmetic sum evaluates to $H (H - 1) / 2$ .

Depends on

Used by

Dependency tree · two levels

20 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)
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, second-edition-in-progress (standard reference, not scraped)