ExampleConstruction: AI-adaptedVerification: AI-generatedPipeline-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.

One-state MDP and normalized diameter

Example

Assume the Axiom of Choice for the path-law and common-average-reward suppliers. Let $S = {s}$ , $A (s) = {a}$ , let the transition return to $s$ with probability one, and let every reward equal $1$ . Then the MDP is communicating, its raw diameter is $D_{0} = 0$ , its normalized diameter is $D = 1$ , its optimal average reward is $1$ , and its unique policy has regret $0$ at every horizon.

Example references

UCRL2 model and diameter: Introduction, Definition 1.

Axiom of Choice: assumed for the cited path-law and common-average-reward results.

Facts & Assumptions

Given: The one-state MDP specified in the Example.

[F1]

Finite MDP with bounded real rewards: transition and reward laws define the finite MDP.

[F2]

Communicating MDP and diameter: $D_{0}$ is the maximum expected hitting time and $D = \max {1, D_{0}}$ .

[F3]

Communicating MDPs have a common optimal average reward: the common optimal average reward is the limit of optimal finite-horizon expected reward per step.

[F4]

Average reward and pathwise regret: regret is $T ρ^{*} - R_{T}$ .

[A1]

The Axiom of Choice: supplies the path-law premise used by [F3] and [F4].

Proof

1.1givenF1F2F3A1construct

The only state reaches itself at time $0$ , so its hitting time is identically $0$ . Hence $D_{0} = 0$ and [F2] gives $D = 1$ . The sole action earns exactly $1$ each step, so its $n$ -step value is $V_{n} (s) = n$ and [F3] gives $ρ^{*} = \lim_{n} V_{n} (s) / n = 1$ .

2.1givenF3F4step 1.1algebra∎

For every horizon $T$ , the realized reward is $R_{T} = T$ . Therefore [F4] gives $Δ_{T} = T \cdot 1 - T = 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

19 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

Thomas Jaksch, Ronald Ortner, and Peter Auer, Near-optimal Regret Bounds for Reinforcement Learning (standard reference, not scraped)