AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-generated

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.

Delayed Q-learning with an admissible heuristic

Definition

Input: A bounded-reward finite discounted MDP interaction, its discount $0 \leq γ < 1$ , an admissible upper heuristic $U$ with cap $V_{\max}$ , an integer batch size $m \geq 1$ , a bonus $0 < ϵ_{1} < 1$ , and a fixed total order on each action set.

Output: At each interaction time $t$ , the selected action $a_{t}$ . The table $Q$ , batch sums, sample counts, batch-start times, learning flags, and global last-update time are internal state; the procedure does not return them as outputs.

Initialize $Q (s, a) = U (s, a)$ , batch sum $B (s, a) = 0$ , sample count $ℓ (s, a) = 0$ , batch start $b (s, a) = 0$ , learning flag $L (s, a) = t r u e$ , and global last-update time $t^{*} = 0$ . For interaction times $t = 1, 2, \dots$ , in current state $s$ , choose an action maximizing $Q (s, \cdot)$ under the fixed tie order, output and take that action $a_{t}$ , then observe reward $r$ and next state $s^{'}$ . If $b (s, a) \leq t^{*}$ , set $L (s, a) = t r u e$ . If $L (s, a)$ is true, set $b (s, a) = t$ when $ℓ (s, a) = 0$ , increment $ℓ (s, a)$ by one, and add $r + γ \max_{c \in A (s^{'})} Q (s^{'}, c)$ to $B (s, a)$ . When $ℓ (s, a) = m$ , set $\overset{ˉ}{B} = B (s, a) / m$ . If $Q (s, a) - \overset{ˉ}{B} \geq 2 ϵ_{1}$ , replace $Q (s, a)$ by $\overset{ˉ}{B} + ϵ_{1}$ and set $t^{*} = t$ . Otherwise set $L (s, a) = f a l s e$ exactly when $b (s, a) > t^{*}$ . In either outcome reset $B (s, a) = 0$ and $ℓ (s, a) = 0$ after a completed batch; if $L (s, a)$ remains false, make no sample or Q update on this visit. Leave all other entries unchanged. Use $s^{'}$ as the current state in the next iteration.

Definition references

Finite discounted MDP interaction and the joint next-state/reward law.

The admissible initialization and value cap.

The one-step reward plus discounted greedy-successor target.

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

Strehl et al., PAC Model-Free Reinforcement Learning.

Szepesvári, Algorithms for Reinforcement Learning.

Depends on

Used by

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)
Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L. Littman, PAC Model-Free Reinforcement Learning (standard reference, not scraped)
Csaba Szepesvári, Algorithms for Reinforcement Learning (standard reference, not scraped)