UCRL2 for finite communicating MDPs

Assume the Axiom of Choice for the interaction path law. The learner is given a finite nonempty state set $\mathcal{S}$, a finite nonempty action set $A(s)$ for each $s\in \mathcal{S}$, the observed initial state $s_1\in \mathcal{S}$, a horizon $T\ge 1$, a confidence parameter $\delta \in (0,1)$, and fixed orders of the states and each state's actions. Let $S=\mathrm{\mid }\mathcal{S}\mathrm{\mid }$ and $A={\max }_{s\in \mathcal{S}}\mathrm{\mid }A(s)\mathrm{\mid }$. Its unknown environment is a finite communicating MDP on $\mathcal{S}$ and these action sets with rewards in $[0,1]$; the transition kernel, reward laws, and their means are not inputs to the learner. At interaction $t$, the learner observes the current state $S_t$, chooses an admissible action, and then observes the realized reward ${\rho }_t$ and next state $S_{t+1}$.

Initialize $t=1$ and $S_1=s_1$. At the start $t_k$ of episode $k$, let $N_k(s,a)$ be the total number of visits to $(s,a)$ before $t_k$. If $N_k(s,a)>0$, let ${\widehat{r}}_k(s,a)$ be the mean of the rewards observed on those visits and ${\widehat{P}}_k(\cdot \mid s,a)$ their empirical next-state law. If $N_k(s,a)=0$, set ${\widehat{r}}_k(s,a)=0$ and set ${\widehat{P}}_k(\cdot \mid s,a)$ to the point mass at the first state in the fixed state order. Put $n_k(s,a)=\max \{1,N_k(s,a)\}$ and $b_k^r(s,a)=\sqrt{\frac{7\log (2SA{t}_k\mathrm{/}\delta )}{2n_k(s,a)}},b_k^p(s,a)=\sqrt{\frac{14S\log (2A{t}_k\mathrm{/}\delta )}{n_k(s,a)}}\mathrm{.}$ Set ${\tilde{r}}_k(s,a)=\min \{1,{\widehat{r}}_k(s,a)+b_k^r(s,a)\}$. Run extended value iteration with these estimates/radii and tolerance $1\mathrm{/}\sqrt{t_k}$, obtaining a stationary deterministic policy ${\pi }_k$. Set every within-episode count $v_k(s,a)=0$ and execute the following loop. While $t\le T$, observe $S_t$, choose $a_t={\pi }_k(S_t)$, observe ${\rho }_t$ and $S_{t+1}$, increment $v_k(S_t,a_t)$ and the all-history count for $(S_t,a_t)$, record this reward/transition observation, and retain the observed next state as the current state for the next interaction. Increment $t$ by one. End the episode immediately after an interaction when its pair's count reaches $v_k(s,a)=\max \{1,N_k(s,a)\}$, where $N_k$ remains the episode-start count; if $t\le T$, begin the next episode, otherwise terminate. All action and transition-vector ties use the fixed orders.

Extended value iteration: specifies the optimistic confidence-set Bellman updates and stopping rule.

Bounded-reward finite MDP: specifies the environment's reward and transition laws.

Communicating MDP and diameter: specifies the environment class.

UCRL2: §3, Figure 1.

Extended Value Iteration: §3.1.2, Figure 2 and equation (5).

Independent UCRL2 treatment: Chapter 10.3.1, printed pp. 224–228.

Finite EVI termination: proves that each positive-tolerance planning call returns.

Axiom of Choice: assumed for the interaction path law.