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

PAC-MDP sample complexity of R-MAX

Statement

Let $M$ be a bounded-reward finite discounted MDP, write $S = ∣ S ∣$ and $A = \max_{s} ∣ A (s) ∣$ , and fix $0 \leq ϵ < (1 - γ)^{- 1}$ , $0 < δ < 1$ , and an admissible heuristic with normalized cap $V_{\max}$ . At $ϵ = 0$ , if $V^{*} (s) = 0$ at every state then $N_{0} = 0$ ; no finite zero-tolerance extension holds uniformly over this class: already at $γ = 0$ , every fixed finite legal sample threshold $m$ and value-iteration tolerance $β$ admits an admissible one-state example for R-MAX with $N_{0} = \infty$ with positive probability. This does not assert failure for every fixed heuristic or model. The parameter formulas below are evaluated only when $ϵ > 0$ . Assume now $ϵ > 0$ . If $ϵ \geq V_{\max}$ , then $N_{ϵ} = 0$ . Otherwise put $η = ϵ / 4, b = \frac{η (1 - γ)}{64 V_{\max}}, m = ⌈ \frac{8 (S + \ln (16 S A / δ))}{b^{2}} ⌉, β = \frac{η (1 - γ)}{16},$ and run R-MAX with sample threshold $m$ and value-iteration tolerance $β$ . Let $E_{η} = {(s, a) : U (s, a) \geq V^{*} (s) - η}$ and $ζ = (m + 1) ∣ E_{η} ∣$ . Define $q = η / (4 V_{\max})$ , and define $H$ and $M$ by $H = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [η (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} M = ⌈ \frac{2 (ζ + 1) + 2 \ln (2 / δ)}{q} ⌉ .$ Then $P (N_{ϵ} \leq H M) \geq 1 - δ$ . For the uninformative heuristic $U (s, a) = V_{\max} = (1 - γ)^{- 1}$ , the bound is $\tilde{O} (S^{2} A / [ϵ^{3} (1 - γ)^{6}])$ , where $\tilde{O}$ suppresses logarithmic factors.

For every $ϵ > 0$ , a bound uniform over all MDPs and admissible heuristics with these $S, A, γ$ is obtained by setting $\overset{ˉ}{V} = \frac{1}{1 - γ}, \overset{ˉ}{b} = \frac{ϵ (1 - γ)^{2}}{256}, \overset{ˉ}{m} = ⌈ \frac{8 (S + \ln (16 S A / δ))}{{\overset{ˉ}{b}}^{2}} ⌉, \overset{ˉ}{q} = \frac{ϵ (1 - γ)}{16}, \overset{ˉ}{ζ} = (\overset{ˉ}{m} + 1) S A,$ and $\overset{ˉ}{H} = {\begin{cases} 1, & γ = 0, \\ \max {1, ⌈ \ln (1 / [(ϵ / 4) (1 - γ)]) / (- \ln γ) ⌉}, & 0 < γ < 1, \end{cases} \overset{ˉ}{M} = ⌈ \frac{2 (\overset{ˉ}{ζ} + 1) + 2 \ln (2 / δ)}{\overset{ˉ}{q}} ⌉ .$ Then $P (N_{ϵ} \leq \overset{ˉ}{H} \overset{ˉ}{M}) \geq 1 - δ$ . This bound depends only on $S, A, ϵ, δ, γ$ .

Statement references

The full zero-tolerance boundary, including admissible algorithm failures and the zero-value success case.

The bad-timestep count and the uniform PAC-MDP meaning of a bound.

Admissibility, the cap, and the reward-scale normalization.

R-MAX's known-set updates and finite value-iteration approximation.

Simultaneous optimism, model accuracy, policy accuracy, and update/escape count.

The high-probability conversion from update/escape counts to bad steps.

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

Szepesvári, Algorithms for Reinforcement Learning.

Facts & Assumptions

Given: The MDP, heuristic, parameters, R-MAX algorithm, and bad-step count in the Statement.

[F1]

Adaptive empirical-model accuracy for R-MAX: with the stated $m$ and $β$ , the simultaneous optimism and model/policy accuracy conditions hold with probability at least $1 - δ / 2$ , and updates plus escapes total at most $(m + 1) ∣ E_{η} ∣$ .

[F2]

Escape-event reduction for optimistic greedy learning: if those conditions hold with failure probability at most $ρ$ , then taking $B = W = V_{\max}$ and $Q_{c} = (1 - γ)^{- 1}$ gives $N_{4 η} \leq H M$ with failure probability at most $2 ρ$ for the displayed $H, M$ .

[F3]

Admissible upper heuristic for a discounted MDP: $0 \leq V^{*} (s) \leq V_{\max}$ and $U (s, a) \leq V_{\max}$ .

[F4]

The zero-tolerance boundary of PAC-MDP exploration: at zero tolerance the all-zero-optimal-value case has no bad steps; fixed finite legal R-MAX parameters admit an admissible one-state model with infinitely many zero-bad steps, with failure probability exceeding any prescribed confidence tolerance.

Proof

1.1givenF4cases

If $ϵ = 0$ , apply [F4] to obtain both stated endpoint branches. No finite sample-size or positive bonus is defined by substituting zero into the later formulas. For the remainder assume $ϵ > 0$ .

1.2givenF1F2F3algebra

If $ϵ \geq V_{\max}$ , then $V^{*} (s) - ϵ \leq 0$ for every state and every continuation value is nonnegative, so no time is counted. Assume now $ϵ < V_{\max}$ . The stated $η$ satisfies $0 < η < V_{\max} / 4$ and $η (1 - γ) < 1$ . Apply [F1] with confidence parameter $δ / 2$ ; its sample threshold is exactly the displayed $m$ . On its event, R-MAX has the hypotheses of [F2] with $ζ = (m + 1) ∣ E_{η} ∣$ .

1.3givenF1F2algebra

For the uninformative heuristic, $∣ E_{η} ∣ \leq S A$ and $V_{\max} = (1 - γ)^{- 1}$ . The displayed $b$ gives $m = O ((S + \ln (S A / δ)) V_{\max}^{} / [η^{2} (1 - γ)^{2}])$ . Also $H = O ((1 - γ)^{- 1} \ln (1 / [η (1 - γ)]))$ , since $- \ln γ \geq 1 - γ$ for $0 < γ < 1$ , and $M = O ((V_{\max} / η) (ζ + \ln (2 / δ)))$ . Using $ζ \leq (m + 1) S A$ and $η = ϵ / 4$ yields $\tilde{O} (S^{2} A / [ϵ^{3} (1 - γ)^{6}])$ .

2.1step 1.2F2algebra

Take $ρ = δ / 2$ in [F2]. Since $4 η = ϵ$ , the theorem gives $P (N_{ϵ} \leq H M) \geq 1 - δ$ .

3.1givenF1F2F3step 2.1algebra∎

Put $\overset{ˉ}{V} = (1 - γ)^{- 1}$ . Since $V_{\max} \leq \overset{ˉ}{V}$ and $∣ E_{η} ∣ \leq S A$ , the instance parameters satisfy $b \geq \overset{ˉ}{b}$ , $m \leq \overset{ˉ}{m}$ , $ζ \leq \overset{ˉ}{ζ}$ , and $q \geq \overset{ˉ}{q}$ , while the truncation horizon is $H = \overset{ˉ}{H}$ . If $ϵ < V_{\max}$ , then $M \leq \overset{ˉ}{M}$ and step 2.1 yields the uniform bound. If $ϵ \geq V_{\max}$ , then $N_{ϵ} = 0$ . Thus the displayed $\overset{ˉ}{H} \overset{ˉ}{M}$ is a finite PAC-MDP bound in the sense of the Definition.

Depends on

Used by

The uninformative heuristic exposes the discount-factor powers Example

Dependency tree · two levels

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