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.

A random reward separates pathwise and expected regret

Example

Assume the Axiom of Choice for the path-law and common-average-reward suppliers. Let there be one state and one action, with deterministic self-transition and independent Bernoulli $(1 / 2)$ rewards. This MDP is communicating. Then $ρ^{*} = 1 / 2$ . At horizon $T = 1$ , pathwise regret equals $1 / 2$ when the reward is $0$ and equals $- 1 / 2$ when the reward is $1$ , although expected regret is $0$ .

Example references

UCRL2 pathwise regret convention: §2, accumulated reward and pathwise-regret definition (PDF lines 134–138).

Communicating MDP and diameter: defines the one-state communicating condition.

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

Facts & Assumptions

Given: The one-state MDP and Bernoulli reward law in the Example.

[F1]

Finite MDP with bounded real rewards: the reward has conditional mean $1 / 2$ and lies in $[0, 1]$ .

[F2]

Communicating MDPs have a common optimal average reward: the sole action's optimal average reward is its mean $1 / 2$ .

[F3]

Average reward and pathwise regret: $Δ_{1} = ρ^{*} - ρ_{1}$ and $E Δ_{1} = ρ^{*} - E ρ_{1}$ .

[F4]

Communicating MDP and diameter: a one-state MDP is communicating because its only hitting time is zero.

[A1]

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

Proof

1.1givenF1F2F4A1construct

The only state reaches itself at time $0$ , so [F4] says the MDP is communicating. The unique action has expected reward $1 / 2$ at each time, so its finite-horizon value is $V_{n} = n / 2$ . By [F2], $ρ^{*} = \lim_{n} V_{n} / n = 1 / 2$ .

2.1givenF1F3A1step 1.1algebra∎

If $ρ_{1} = 0$ , then [F3] gives $Δ_{1} = 1 / 2$ ; if $ρ_{1} = 1$ , it gives $Δ_{1} = - 1 / 2$ . Both outcomes have probability $1 / 2$ , so $E Δ_{1} = (1 / 2) (1 / 2) + (1 / 2) (- 1 / 2) = 0$ . Thus the random pathwise regret is not the constant expected regret.

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)