PAC-MDP sample complexity of Delayed Q-learning

If $ϵ=0$, apply [F7] to obtain both stated endpoint branches. No finite sample-size or positive bonus is defined by substituting zero into the later formulas. For the remainder assume $ϵ>0$.

If $ϵ\ge V_{\max }$, then [F3] and nonnegativity of continuation values imply no bad step. Otherwise $\eta =ϵ\mathrm{/}4<V_{\max }\mathrm{/}4$ and $\eta (1-\gamma )<1$. The displayed batch size is the lemma threshold [F1] with internal failure parameter $\delta \mathrm{/}2$, so with probability at least $1-\delta \mathrm{/}2$ all Q-values are optimistic and the update/escape count is at most $\zeta$.

Extend $V_t$ to the state set of $M_t$ by setting ${\tilde{V}}_t(s)=V_t(s)$ on original states and ${\tilde{V}}_t({\mathrm{\perp }}_{s,a})=Q_t(s,a)$ at each added sink. Extend ${\pi }_t$ by the unique sink action. Both the sink's policy value and its Bellman backup at ${\tilde{V}}_t$ equal $Q_t(s,a)$ by [F4], so the sink residual is zero. At an original state $s$, let $a={\pi }_t(s)$. If $(s,a)\mathrm{\notin }{K}_t$, its backup at ${\tilde{V}}_t$ is exactly $Q_t(s,a)=V_t(s)$ by [F4]. If $(s,a)\in K_t$, the definition of $K_t$ gives $Q_t(s,a)\le r(s,a)+\gamma {\sum }_{s^{\mathrm{\prime }}}P(s^{\mathrm{\prime }}\mid s,a)V_t(s^{\mathrm{\prime }})+3{ϵ}_1$. Hence on the entire expanded state set, ${\tilde{V}}_t\le T_{M_t}^{{\pi }_t}{\tilde{V}}_t+3{ϵ}_1$. Subtract the policy Bellman equation [F5] and set $\mathrm{\Delta }={\max }_x[{\tilde{V}}_t(x)-V_{M_t}^{{\pi }_t}(x){]}_{+}$. Nonnegative stochastic transition rows give $\mathrm{\Delta }\le \gamma \mathrm{\Delta }+3{ϵ}_1$, hence on the original states $V_t-V_{M_t}^{{\pi }_t}\le 3{ϵ}_1\mathrm{/}(1-\gamma )=\eta$.

The residual sets $K_t$ are history-measurable and change only after a Q update; they satisfy the stability condition of [F2]. By [F6], the Q table remains in $[0,V_{\max }]$. Step 1.2 supplies optimism and the count bound; step 1.3 supplies policy accuracy. Apply [F2] with $\rho =\delta \mathrm{/}2$. Since $4\eta =ϵ$, it gives $\mathbb{P}(N_{ϵ}\le HM)\ge 1-\delta$.

From the definitions, $G=[{\sum }_{s,a}D(s,a)+\mathrm{\mid }D\mathrm{\mid }{ϵ}_1]\mathrm{/}{ϵ}_1\le [{\sum }_{s,a}D(s,a)+SA{ϵ}_1]\mathrm{/}{ϵ}_1$, where $\mathrm{\mid }D\mathrm{\mid }={\sum }_s\mathrm{\mid }A(s)\mathrm{\mid }\le SA$, $m=O((1+\gamma V_{\max }{)}^2{ϵ}_1^{-2}\ln (16N\mathrm{/}\delta ))$, and $M=O((V_{\max }\mathrm{/}\eta )(mG+\ln (2\mathrm{/}\delta )))$. Also $H=O((1-\gamma {)}^{-1}\ln (1\mathrm{/}[\eta (1-\gamma )]))$: for $0<\gamma <1$, the function $x-1-\ln x$ has its minimum $0$ at $x=1$, so $-\ln \gamma \ge 1-\gamma$. Substituting ${ϵ}_1=ϵ(1-\gamma )\mathrm{/}12$ and $\eta =ϵ\mathrm{/}4$ into $H(V_{\max }\mathrm{/}\eta )mG$ gives a constant multiple of $\frac{V_{\max }(1+\gamma V_{\max }{)}^2[{\sum }_{s,a}D(s,a)+SAϵ(1-\gamma )]}{{ϵ}^4(1-\gamma {)}^4}\ln \frac{16N}{\delta }\ln \frac{1}{\eta (1-\gamma )}$. The remaining $H(V_{\max }\mathrm{/}\eta )\ln (2\mathrm{/}\delta )$ term is bounded by the same expression up to logarithmic factors because $m\ge 1$ and $G\ge \mathrm{\mid }D\mathrm{\mid }\ge 1$. For the uninformative heuristic, $\sum D\le SA\mathrm{/}(1-\gamma )$ and $1+\gamma V_{\max }=(1-\gamma {)}^{-1}$; substitution yields $\tilde{O}(SA\mathrm{/}[{ϵ}^4(1-\gamma {)}^8])$.

Put $\bar{V}=(1-\gamma {)}^{-1}$ and ${\overline{ϵ}}_1=ϵ(1-\gamma )\mathrm{/}12$. Admissibility gives $0\le D(s,a)\le V_{\max }\le \bar{V}$, and hence $C_1=1+\gamma V_{\max }\le \bar{V}$, $\kappa \le \bar{\kappa }$, $N\le \bar{N}$, $m\le \bar{m}$, $G\le \bar{G}$, $\zeta \le \bar{\zeta }$, $q\ge \bar{q}$, and $H=\bar{H}$. If $ϵ\ge V_{\max }$, then $N_{ϵ}=0$. Otherwise $M\le \bar{M}$, so step 2.1 proves the uniform bound. All barred quantities depend only on $S,A,ϵ,\delta ,\gamma$, as required by the Definition.