Communicating MDP and diameter

Assume the Axiom of Choice for the policy path laws used in the expectations below. For a finite MDP with bounded rewards, a policy assigns a probability distribution on $A(s)$ to each finite observed history ending in state $s$, with each action probability a measurable function of the history; deterministic policies are included. For states $x,y$, start at $S_0=x$ and define ${\tau }_y=\inf \{t\ge 0:S_t=y\}$, with ${\tau }_y=+\mathrm{\infty }$ if $y$ is never hit. This is an extended nonnegative measurable random variable because $\{{\tau }_y\le n\}={\bigcup }_{t=0}^n\{S_t=y\}$. Take the expectation and the infimum over policies in $[0,+\mathrm{\infty }]$. The MDP is communicating if ${\inf }_{\pi }{\mathbb{E}}_x^{\pi }[{\tau }_y]<\mathrm{\infty }$ for every ordered pair $(x,y)$. Its raw diameter is $D_0={\sup }_{x,y}{\inf }_{\pi }{\mathbb{E}}_x^{\pi }[{\tau }_y]$ in $[0,+\mathrm{\infty }]$, and its normalized diameter is $D=\max \{1,D_0\}$ in the extended order. Since $S$ is finite, $D_0$ is finite for every communicating MDP. Thus a one-state MDP has $D_0=0$ and $D=1$.

Bounded-reward finite-MDP model: state, action, transition, reward, and path-law conventions.

Finite MDP policy convention: actions are selected from the finite nonempty statewise action sets.

Expectation: defines the expected hitting time.

Extended real line: provides the order used when a target may never be hit.

Extended completeness: provides the extended infimum.

Axiom of Choice: assumed for policy path laws.

UCRL2 diameter convention: Introduction, Definition 1; §2.