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

Admissible upper heuristic for a discounted MDP

Definition

For a bounded-reward finite discounted MDP, an admissible upper heuristic is a function $U : D \to [0, V_{0}]$ such that $Q^{*} (s, a) \leq U (s, a)$ for every admissible pair and a supplied scalar satisfies $0 \leq V_{0} \leq (1 - γ)^{- 1}$ . Define the effective reward-scale cap $V_{\max} = \max {1, V_{0}}$ . Then $U (s, a) \leq V_{\max} \leq (1 - γ)^{- 1}$ . The floor at $1$ is part of this convention because an observed reward can lie anywhere in $[0, 1]$ , even when the heuristic values are all smaller than $1$ .

Definition references

The finite state-action domain and bounded real rewards.

Optimal action values and the geometric discounted-value cap.

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

Szepesvári, Algorithms for Reinforcement Learning.

Depends on

Used by

Delayed Q-learning with an admissible heuristic Algorithm
R-MAX with an admissible heuristic Algorithm
Known-state/action MDP with prescribed absorbing values Definition
The uninformative heuristic exposes the discount-factor powers Example
Zero heuristic slack can still require one Delayed Q-learning update Example
Adaptive empirical-model accuracy for R-MAX Lemma
Delayed Q-learning optimism and update-count bounds Lemma
PAC-MDP sample complexity of Delayed Q-learning Theorem
PAC-MDP sample complexity of R-MAX Theorem
The zero-tolerance boundary of PAC-MDP exploration Theorem

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)