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

PAC-MDP sample complexity of exploration

Definition

Assume AC, fix a bounded-reward finite discounted MDP, an initial state, and a learning algorithm whose behavior is a history-dependent policy. At time $t \geq 1$ , let $h_{t}$ be the observed history ending at state $s_{t}$ . The continuation behavior $A_{t}$ is the tail of the algorithm's action kernels after $h_{t}$ , and $V^{A_{t}} (h_{t})$ is the expected discounted return of the continuation process generated from that fixed history by those tail kernels. Set $S = ∣ S ∣$ and $A = \max_{s \in S} ∣ A (s) ∣$ . For $ϵ \geq 0$ , the $ϵ$ -bad-step count is $N_{ϵ} = # {t \geq 1 : V^{A_{t}} (h_{t}) < V^{*} (s_{t}) - ϵ},$ where the count may be infinite. For $ϵ > 0$ and $0 < δ < 1$ , a PAC-MDP bound is a specified finite function $B (S, A, ϵ, δ, γ)$ such that, for every MDP with these finite state/action sizes and every initial state, $P (N_{ϵ} \leq B (S, A, ϵ, δ, γ)) \geq 1 - δ$ . This definition does not require the bad steps to precede a permanent stopping time.

For each fixed $t$ , the finite-horizon continuation values are measurable functions of $h_{t}$ : recursively, they are finite sums and integrals of nonnegative product-measurable functions against the behavior and MDP kernels. The kernel-integration theorem applies at each recursion, and the infinite-horizon value is the increasing limit of these finite-horizon values. Hence the bad-time sets and the extended count $N_{ϵ}$ are measurable, so the displayed probability is defined.

Definition references

Finite discounted MDPs, history-dependent behaviors, and observed histories with Borel reward coordinates.

The discounted return and optimal value are well-defined, with an optimal deterministic stationary policy.

AC is used for the countable trajectory law.

Integration of a nonnegative product-measurable function against a probability kernel is measurable in the history parameter.

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

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

Depends on

Used by

Dependency tree · two levels

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