Average reward and pathwise regret

Assume the Axiom of Choice for the path laws and conditional-expectation constructions used by the common-average-reward result. For a finite communicating MDP, let ${\rho }^{\ast }$ denote the common optimal average reward. The existence and independence of this value from the initial state are proved in the immediately cited theorem. Under any policy, write $R_T={\sum }_{t=1}^T{\rho }_t$ for the realized cumulative reward over the first $T$ interactions. The pathwise regret is the random variable ${\mathrm{\Delta }}_T=T{\rho }^{\ast }-R_T$. Its expected regret is $\mathbb{E}[{\mathrm{\Delta }}_T]=T{\rho }^{\ast }-\mathbb{E}[R_T]$. The pathwise random variable and its expectation are distinct objects.

Bounded-reward MDP: supplies the realized reward sequence ${\rho }_t$ and its finite-horizon path law.

Communicating MDP and diameter: supplies the model class for which ${\rho }^{\ast }$ is defined.

Common optimal average reward: its limit exists and is independent of the initial state.

Expectation: defines expected regret.

Expectation linearity: gives the displayed expected-regret identity.

UCRL2 regret convention: §2, the paper defines regret from the realized cumulative reward (PDF lines 134–138).

Average-reward regret treatment: Chapter 10.3.1, printed p. 223.

Axiom of Choice: assumed for the path laws and conditional expectations in the common-average-reward result.