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.

R-MAX 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 sample threshold $m \geq 1$ , a value-iteration error tolerance $0 < β < (1 - γ)^{- 1}$ , and a fixed total order on each finite action set. Write $\ln$ for the natural logarithm.

Output: At each interaction time $t$ , the selected action $a_{t}$ . The action-value table $Q$ , known set, sample lists, and empirical model are internal state; the procedure does not return $Q$ as an output.

Initialize each pair as unknown, set $Q (s, a) = U (s, a)$ , and give each pair an empty list of observed rewards and next states. For interaction times $t = 1, 2, \dots$ , in the current state choose a maximizing action using the fixed tie order, output and take that action $a_{t}$ , and observe reward $R_{t + 1}$ and next state $S_{t + 1}$ . If the pair is unknown, append this observation until its list has length $m$ . When it reaches $m$ , mark the pair known, set its empirical reward to the sample mean and its empirical transition law to the sample frequencies. Rebuild all action values by setting the working table $Q^{(0)} (s, a) = 0$ , then for $j = 0, \dots, L - 1$ setting $Q^{(j + 1)} = H_{K} Q^{(j)}$ , and finally replacing $Q$ by $Q^{(L)}$ , for the operator $H_{K} Q (s, a) = {\begin{cases} \hat{r} (s, a) + γ \sum_{s^{'}} \hat{P} (s^{'} ∣ s, a) \max_{b \in A (s^{'})} Q (s^{'}, b), & (s, a) \in K, \\ U (s, a), & (s, a) \notin K, \end{cases}$ where $K$ is the current known set and $L = \max ⁣ {1, ⌈ \frac{\ln (1 / [β (1 - γ)])}{1 - γ} ⌉} .$ Pairs and their samples are never removed from $K$ or discarded. After processing the observation and any rebuild, use the observed $S_{t + 1}$ as the current state in the next iteration. The algorithm specifies no computational-time bound.

Definition references

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

Admissible upper heuristic and normalized reward-scale cap.

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

Szepesvári, Algorithms for Reinforcement Learning.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed..

Depends on

Used by

An inadmissible heuristic can suppress exploration forever Example
Adaptive empirical-model accuracy for R-MAX Lemma
PAC-MDP sample complexity of R-MAX Theorem
The zero-tolerance boundary of PAC-MDP exploration Theorem

Dependency tree · two levels

10 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)
Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (standard reference, not scraped)