LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

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.

Value stability under empirical model error

Statement

Let $M_{1}$ and $M_{2}$ be bounded-reward finite discounted MDPs on the same finite state set $S$ and the same admissible action sets, with common discount $0 \leq γ < 1$ . Write $r_{i}, P_{i}, V_{i}^{π}, V_{i}^{*}$ for their mean rewards, transition laws, stationary-policy values, and optimal values. Suppose $0 \leq V_{i}^{π} (s), V_{i}^{*} (s) \leq V$ for every state, model index $i$ , and stationary policy $π$ , and that for every admissible pair $∣ r_{1} (s, a) - r_{2} (s, a) ∣ \leq α, ∥ P_{1} (\cdot ∣ s, a) - P_{2} (\cdot ∣ s, a) ∥_{1} \leq β .$ For finite vectors, $∥ v ∥_{\infty} = \max_{s \in S} ∣ v (s) ∣$ and $∥ p ∥_{1} = \sum_{s \in S} ∣ p (s) ∣$ . Then every common stationary policy and the optimal values satisfy $∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty} \leq \frac{α + γ V β}{1 - γ}, ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty} \leq \frac{α + γ V β}{1 - γ} .$ There is also a trap-model form that does not assume a tight cap for the second model: for $W > 0$ , suppose all stationary-policy and optimal values in $M_{1}$ are at most $2 W$ , all rewards in $M_{2}$ lie in $[0, 1]$ , and $γ β \leq (1 - γ) / 2$ . Then every common stationary policy and the optimal values satisfy $∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty} \leq \frac{2 (α + 2 γ W β)}{1 - γ}, ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty} \leq \frac{2 (α + 2 γ W β)}{1 - γ} .$

Statement references

Finite discounted MDPs, rewards, and transition laws.

Stationary and optimal Bellman fixed-point equations.

Strehl, Li, and Littman, Reinforcement Learning in Finite MDPs: PAC Analysis.

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: The two MDPs, common state/action/discount data, the uniform reward and transition error bounds, and the common value cap $V$ in the Statement.

[F1]

Well-defined discounted values and optimal Bellman fixed points: each stationary value solves its policy Bellman equation, and each optimal value is the unique fixed point of its optimality Bellman operator.

[F2]

Every nonempty finite set of reals has a maximum and a minimum: a maximum over each nonempty finite action set is attained.

[F3]

Laws of finite sums and finite products: finite weighted sums preserve inequalities and satisfy the triangle inequality.

[A1]

Finite discounted MDP with bounded real rewards: rewards in $M_{2}$ lie in $[0, 1]$ , so its stationary and optimal discounted values are at most $(1 - γ)^{- 1}$ .

Proof

1.1givenF1F3algebra

Fix a stationary policy $π$ and put $d = ∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty}$ . Subtract its two Bellman equations. For each state, split the transition term as $P_{1} (V_{1}^{π} - V_{2}^{π}) + (P_{1} - P_{2}) V_{2}^{π}$ . The first part has absolute value at most $d$ because $P_{1}$ is a probability vector; the second is at most $V ∥ P_{1} - P_{2} ∥_{1} \leq V β$ because $0 \leq V_{2}^{π} \leq V$ . Averaging over the common policy's action distribution and using the reward error gives $∣ V_{1}^{π} (s) - V_{2}^{π} (s) ∣ \leq α + γ d + γ V β$ . Taking the maximum over states and rearranging yields the first bound.

1.2givenF1F2F3algebra

Put $d = ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty}$ . For any state and action, the two optimal Bellman backup entries differ by at most $α + γ d + γ V β$ , by the same transition splitting and the cap on $V_{2}^{*}$ . For finite lists $(x_{a}), (y_{a})$ , $∣ \max_{a} x_{a} - \max_{a} y_{a} ∣ \leq \max_{a} ∣ x_{a} - y_{a} ∣$ : each $x_{a} \leq y_{a} + m$ and $y_{a} \leq x_{a} + m$ for $m = \max_{a} ∣ x_{a} - y_{a} ∣$ . Thus the optimal Bellman equations in [F1] imply $d \leq α + γ d + γ V β$ . Rearranging proves the second bound.

2.1givenF1F3A1step 1.1algebra

Under the additional trap-model hypotheses, fix $π$ and put $d = ∥ V_{1}^{π} - V_{2}^{π} ∥_{\infty}$ . Bellman subtraction as in step 1.1 gives $d \leq α + γ d + γ β ∥ V_{2}^{π} ∥_{\infty}$ . By [A1] and the triangle inequality, $∥ V_{2}^{π} ∥_{\infty} \leq ∥ V_{1}^{π} ∥_{\infty} + d \leq 2 W + d$ . Hence $(1 - γ - γ β) d \leq α + 2 γ W β$ . Since $γ β \leq (1 - γ) / 2$ , the left coefficient is at least $(1 - γ) / 2$ , yielding $d \leq 2 (α + 2 γ W β) / (1 - γ)$ .

3.1givenF1F2F3A1step 1.2step 2.1algebra∎

For optimal values, use the finite-maximum inequality from step 1.2 in the Bellman subtraction. It gives $d = ∥ V_{1}^{*} - V_{2}^{*} ∥_{\infty} \leq α + γ d + γ β ∥ V_{2}^{*} ∥_{\infty}$ . Again [A1] and the triangle inequality give $∥ V_{2}^{*} ∥_{\infty} \leq 2 W + d$ . The same rearrangement as step 2.1 proves the optimal-value bound.

Depends on

Used by

Adaptive empirical-model accuracy for R-MAX Lemma

Dependency tree · two levels

39 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

Alexander L. Strehl, Lihong Li, and Michael L. Littman, Reinforcement Learning in Finite MDPs: PAC Analysis (standard reference, not scraped)
Csaba Szepesvári, Algorithms for Reinforcement Learning (standard reference, not scraped)