ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

The uninformative heuristic exposes the discount-factor powers

Example

Assume AC. Set $U (s, a) = V_{\max} = (1 - γ)^{- 1}$ for every pair, and let $0 < ϵ < (1 - γ)^{- 1}$ . Then every pair belongs to $E_{ϵ / 4}$ , and $\sum_{s, a} [U (s, a) - V^{*} (s)]_{+} \leq \frac{S A}{1 - γ} .$ Substitution into the proved theorems gives the leading orders $\tilde{O} (S^{2} A / [ϵ^{3} (1 - γ)^{6}])$ for R-MAX and $\tilde{O} (S A / [ϵ^{4} (1 - γ)^{8}])$ for Delayed Q-learning.

Example references

AC required by the invoked PAC-MDP theorems.

The uninformative admissible heuristic and its normalized cap.

The R-MAX high-probability count bound.

The Delayed Q-learning high-probability count bound.

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

Facts & Assumptions

Given: AC, the heuristic and parameter range in the Example, and the two PAC-MDP theorems.

[F1]

Admissible upper heuristic for a discounted MDP: $V^{*} (s) \geq 0$ , $U = V_{\max} = (1 - γ)^{- 1}$ , and $[U - V^{*} (s)]_{+} \leq (1 - γ)^{- 1}$ .

[F2]

PAC-MDP sample complexity of R-MAX: for this heuristic the R-MAX pair count is at most $S A$ and its leading bound is $\tilde{O} (S^{2} A / [ϵ^{3} (1 - γ)^{6}])$ .

[F3]

PAC-MDP sample complexity of Delayed Q-learning: the heuristic gap sum is at most $S A / (1 - γ)$ and its uninformative-heuristic leading bound is $\tilde{O} (S A / [ϵ^{4} (1 - γ)^{8}])$ .

Proof

1.1givenF1algebra

Since $V^{*} (s) \leq (1 - γ)^{- 1} = U (s, a)$ and $ϵ / 4 > 0$ , every pair satisfies $U (s, a) \geq V^{*} (s) - ϵ / 4$ , so $∣ E_{ϵ / 4} ∣ \leq S A$ . Nonnegativity and the value cap give $0 \leq [U (s, a) - V^{*} (s)]_{+} \leq (1 - γ)^{- 1}$ for each pair; summing proves the displayed gap estimate.

2.1givenF1F2F3step 1.1algebra∎

Substitute $∣ E_{ϵ / 4} ∣ \leq S A$ into [F2] and the gap estimate into [F3]. Their uninformative-heuristic cases give exactly the two displayed leading orders; the $\tilde{O}$ notation suppresses the logarithmic factors retained in the theorems.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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