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.

An inadmissible heuristic can suppress exploration forever

Example

Consider a one-state MDP with $γ = 0$ and actions $a, b$ having deterministic rewards $1, 0$ . Define an extension of the R-MAX procedure by dropping only the input requirement $U (s, a) \geq Q^{*} (s, a)$ and retaining its initialization, tie rule, sampling, empirical-model, and rebuild instructions unchanged. Run this extended procedure with the inadmissible heuristic $U (a) = U (b) = 0$ , supplied scalar $V_{0} = 0$ (so $V_{\max} = 1$ ), tolerance $β = 1 / 2$ , any integer threshold $m \geq 1$ , and a tie order that selects $b$ first. It observes only $b$ , chooses $b$ forever, and is $1 / 2$ -bad at every time.

Example references

The one-state MDP and deterministic rewards.

Unknown action values remain at their heuristic until visited.

Bad-step continuation values and the count.

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

Facts & Assumptions

Given: The MDP, heuristic, tie order, threshold, and explicitly extended procedure in the Example.

[F1]

The extension retains these instructions from R-MAX with an admissible heuristic: a visited pair becomes known after $m$ samples and receives its empirical reward mean; an unvisited pair keeps its heuristic value.

[F2]

Finite discounted MDP with bounded real rewards: the pair $a$ has true optimal action value $Q^{*} (s, a) = 1$ .

[F3]

PAC-MDP sample complexity of exploration: with $γ = 0$ , an action with reward $0$ has zero continuation value and is bad for $ϵ = 1 / 2$ when $V^{*} = 1$ .

Proof

1.1givenF1F2algebra

Initially both action values equal $0$ , so the fixed tie order chooses $b$ . Its next state is the same state and its reward is $0$ . Before the $m$ th observation it remains unknown at value $0$ . Since $γ = 0$ and $β = 1 / 2$ , the sweep count is $L = \max {1, ⌈ \ln 2 ⌉} = 1$ ; on reaching $m$ samples, its empirical reward mean is $0$ and this sweep gives its known backup $0$ , while the unvisited action $a$ still has heuristic value $0$ .

2.1givenF1F2F3step 1.1induction∎

The rebuilt values remain tied at zero, so the tie order again selects $b$ . Induction over subsequent visits shows $a$ is never sampled and the table always has $Q (s, a) = Q (s, b) = 0$ . The heuristic is inadmissible since $U (a) = 0 < 1 = Q^{*} (s, a)$ . At every time the continuation reward is zero, while $V^{*} (s) = 1$ , so $0 < 1 - 1 / 2$ and every time is bad.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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