Pipeline-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.

Average-reward regret and UCRL2 — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-adaptedVerification: AI-generatedOpen item page →

A noncommunicating MDP can have state-dependent average reward

Example

Assume the Axiom of Choice for the path laws in the communicating-MDP definition. Let $S = {0, 1}$ and let each state have one action. Both states are absorbing. The reward is always $0$ in state $0$ and always $1$ in state $1$ . The MDP is not communicating, and its long-run average reward is $0$ from initial state $0$ and $1$ from initial state $1$ .

Example references

Communicating-MDP hypothesis: Introduction, Definition 1; §2.

Communicating MDP and diameter: defines finite expected hitting between every ordered state pair.

Axiom of Choice: assumed for the policy path laws in that definition.

Facts & Assumptions

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

[F1]

Finite MDP with bounded real rewards: transitions and rewards are fixed conditional on the current state and action.

[F2]

Communicating MDP and diameter: communication requires finite optimal expected hitting time for every ordered pair.

[A1]

The Axiom of Choice: supplies the path-law convention used in [F2].

Proof

1.1givenF1construct

Starting from either state, the chain remains there at every time. From state $0$ every cumulative reward is $0$ , so its average is $0$ ; from state $1$ every cumulative reward over $T$ steps is $T$ , so its average is $1$ .

2.1givenF1F2A1step 1.1algebra∎

No policy can leave either absorbing state. In particular, starting from $0$ there is no policy that reaches $1$ with finite expected hitting time, so [F2] says the communicating condition fails. The distinct averages show why the theorem's communication hypothesis matters.

ExampleConstruction: AI-adaptedVerification: AI-generatedOpen item page →

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$ .

ExampleConstruction: AI-adaptedVerification: AI-generatedOpen item page →

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.

Sources

Thomas Jaksch, Ronald Ortner, and Peter Auer, Near-optimal Regret Bounds for Reinforcement Learning