Adaptive empirical-model accuracy for R-MAX

Apply [F1] to each pair with reward and transition tolerance $b$. For ${\delta }_0=\delta \mathrm{/}(4SA)$, the transition threshold is $\sqrt{S\mathrm{/}m}+\sqrt{2\ln (1\mathrm{/}{\delta }_0)\mathrm{/}m}\le b$: its squared numerator is at most $2S+4\ln (1\mathrm{/}{\delta }_0)\le 4(S+L_0)$, while $m\ge 8(S+L_0)\mathrm{/}{b}^2$. The reward failure is at most $2e^{-2m{b}^2}\le {\delta }_0$ because $2m{b}^2\ge 16(S+L_0)\ge \ln (2\mathrm{/}{\delta }_0)$. By [F6], the finite union over reward and transition events for at most $SA$ pairs has failure probability at most $2SA{\delta }_0=\delta \mathrm{/}2$.

The Bellman operator of ${\widehat{M}}_K$ is exactly the operator in [F5], with unknown backup $U$. Its fixed point and zero-initialized sweeps lie in $[0,(1-\gamma {)}^{-1}]$. The contraction estimate in [F3] gives error at most ${\gamma }^L\mathrm{/}(1-\gamma )$. For $0<\gamma <1$, $\ln \gamma \le -(1-\gamma )$, so the stated $L$ makes this error at most $\beta$; when $\gamma =0$, one sweep is exact. The initial table $U$ is the exact fixed point for the empty known set. Thus the action-value approximation bound holds after every rebuild.

For a fixed known set $K$, the true trap model has every stationary-policy and optimal value at most $2V_{\max }$. Indeed, until the first outside-$K$ pair its path is a true-MDP path, whose expected nonnegative prefix is at most $V^{\ast }(s)\le V_{\max }$; after that pair its absorbing continuation is at most $U(s,a)\le V_{\max }$. The empirical trap model has all rewards in $[0,1]$. Also $\gamma b\le (1-\gamma )\mathrm{/}2$, since $\gamma b\mathrm{/}(1-\gamma )=\gamma \eta \mathrm{/}(64V_{\max })<1\mathrm{/}256$. Apply the trap-model form of [F2] with $W=V_{\max }$ and $\alpha =\beta =b$. The value error for each policy and the optimum is at most $2b(1+2\gamma V_{\max })\mathrm{/}(1-\gamma )=\eta (1+2\gamma V_{\max })\mathrm{/}(32V_{\max })\le 3\eta \mathrm{/}32<\eta \mathrm{/}8$.

Let $V_{M_K}^{\ast }$ and $V_{{\widehat{M}}_K}^{\ast }$ denote the trap-model optima. For every state, the true Bellman backup at $V^{\ast }$ on a known pair is $Q^{\ast }(s,a)$, and on an unknown pair the trap backup is $U(s,a)\ge Q^{\ast }(s,a)$. Hence $T_{M_K}^{\ast }{V}^{\ast }\ge V^{\ast }$. The operator preserves coordinatewise order because its transition weights are nonnegative; its iterates from $V^{\ast }$ therefore increase. Contraction makes these iterates converge to the unique fixed point, so $V_{M_K}^{\ast }\ge V^{\ast }$. Step 2.1 gives $V_{{\widehat{M}}_K}^{\ast }\ge V_{M_K}^{\ast }-\eta \mathrm{/}8$. Since $\mathrm{\parallel }{Q}_t-Q_{{\widehat{M}}_K}^{\ast }{\mathrm{\parallel }}_{\mathrm{\infty }}\le \beta$, $V_t\ge V_{{\widehat{M}}_K}^{\ast }-\beta \ge V^{\ast }-(\eta \mathrm{/}8+\beta )\ge V^{\ast }-\eta$.

For each state $s$, the action chosen by ${\pi }_t$ satisfies $Q_{{\widehat{M}}_K}^{\ast }(s,{\pi }_t(s))\ge V_{{\widehat{M}}_K}^{\ast }(s)-2\beta$: its optimal action value is at least its estimated value minus $\beta$, while the estimated maximum is at least the optimal maximum minus $\beta$. Thus $T_{{\widehat{M}}_K}^{{\pi }_t}{V}_{{\widehat{M}}_K}^{\ast }\ge V_{{\widehat{M}}_K}^{\ast }-2\beta$. Subtracting the policy Bellman equation and taking the maximum positive difference yields $V_{{\widehat{M}}_K}^{\ast }-V_{{\widehat{M}}_K}^{{\pi }_t}\le 2\beta \mathrm{/}(1-\gamma )$. Comparing the same policy in $M_K$ by step 2.1 and using $V_t\le V_{{\widehat{M}}_K}^{\ast }+\beta$ gives $V_t-V_{M_K}^{{\pi }_t}\le \beta +2\beta \mathrm{/}(1-\gamma )+\eta \mathrm{/}8\le 5\eta \mathrm{/}16<\eta$, because $\beta =\eta (1-\gamma )\mathrm{/}16$.

On the event just proved, an outside-$K_t$ pair with $U(s,a)<V^{\ast }(s)-\eta$ cannot be selected: its current value is still $Q_t(s,a)=U(s,a)$, whereas $V_t(s)\ge V^{\ast }(s)-\eta$. Thus every escape pair lies in $E_{\eta }$. By [F5], each such pair is selected outside the known set at most $m$ times and causes one rebuild. Summing over $E_{\eta }$ proves the complexity bound.