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.

Zero heuristic slack can still require one Delayed Q-learning update

Example

Consider a one-state MDP with $γ = 0$ and actions $a, b$ of deterministic rewards $1, 0$ . Set $U (a) = U (b) = V^{*} (s) = V_{\max} = 1$ , use a tie order selecting $b$ first, and take any integer $m \geq 1$ and $0 < ϵ_{1} < 1 / 2$ . Delayed Q-learning selects $b$ for its first $m$ samples and then lowers $Q (s, b)$ , even though $\sum_{s, a} [U (s, a) - V^{*} (s)]_{+} = 0$ . This shows that the per-pair $+ 1$ successful-update allowance cannot be removed when heuristic slack is zero; with the PAC theorem's prescribed parameters, this allowance produces the additive $S A ϵ (1 - γ)$ term in its simplified bound.

Example references

The admissible heuristic and zero positive slack.

The batch threshold and update bonus.

The corrected per-pair additive term.

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

Facts & Assumptions

Given: The MDP, initialization, tie order, batch size, and bonus in the Example.

[F1]

Delayed Q-learning with an admissible heuristic: a batch updates exactly when the old value minus the sample mean is at least $2 ϵ_{1}$ , replacing it by the sample mean plus $ϵ_{1}$ .

[F2]

Admissible upper heuristic for a discounted MDP: $Q^{*} (s, a) \leq U (s, a)$ and $D (s, a) = [U (s, a) - V^{*} (s)]_{+}$ .

[F3]

PAC-MDP sample complexity of Delayed Q-learning: the count bound includes $S A ϵ (1 - γ)$ in addition to the sum of heuristic slacks.

Proof

1.1givenF1algebra

Initially $Q (s, a) = Q (s, b) = 1$ , so the tie order selects $b$ . Since $γ = 0$ , each of its first $m$ targets is its observed reward $0$ ; no update occurs before the batch completes. At the $m$ th sample the mean is $0$ , so $Q (s, b) - 0 = 1 \geq 2 ϵ_{1}$ and [F1] updates it to $ϵ_{1} < 1$ .

2.1givenF2F3step 1.1algebra∎

The other action remains at value $1$ , so the next greedy action is $a$ . Also $V^{*} (s) = 1$ and both heuristic values equal $1$ , hence every $D (s, a) = 0$ and their sum is zero. The batch of $m$ initial selections is a finite nonzero learning cost despite zero slack. This witnesses the per-pair $+ 1$ successful-update allowance in the theorem's count, which remains when all heuristic slacks vanish and produces the additive $S A ϵ (1 - γ)$ term after parameter substitution.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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