Alphabeta MathHow 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 noncommunicating MDP can have state-dependent average reward
Example
Assume the Axiom of Choice for the path laws in the communicating-MDP definition. Let and let each state have one action. Both states are absorbing. The reward is always in state and always in state . The MDP is not communicating, and its long-run average reward is from initial state and from initial state .
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.
Finite MDP with bounded real rewards: transitions and rewards are fixed conditional on the current state and action.
Communicating MDP and diameter: communication requires finite optimal expected hitting time for every ordered pair.
The Axiom of Choice: supplies the path-law convention used in [F2].
Proof
Starting from either state, the chain remains there at every time. From state every cumulative reward is , so its average is ; from state every cumulative reward over steps is , so its average is .
No policy can leave either absorbing state. In particular, starting from there is no policy that reaches with finite expected hitting time, so [F2] says the communicating condition fails. The distinct averages show why the theorem's communication hypothesis matters.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
13 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)