Delayed Q-learning optimism and update-count bounds

Each successful update decreases one entry by at least ${ϵ}_1$, while every updated entry stays nonnegative and starts at most $V_{\max }$, by [F2]. Therefore the total number of updates is at most $SA{V}_{\max }\mathrm{/}{ϵ}_1\le \kappa$. For two consecutive batch starts $b_j<b_{j+1}$ of one pair, some successful global update occurs in $[b_j,b_{j+1})$: either the earlier batch succeeds, or it fails with $b_j\le t^{\ast }$, or it disables learning and a later global update re-enables it. These intervals are disjoint for that pair. Charging each start after its first to such an update gives at most $1+\kappa$ starts per pair and at most $N$ overall, including unfinished batches.

Condition on a batch-start history at time $k_1$ for pair $(s,a)$ and freeze $V_{k_1}$. The next $m$ potential joint outcomes give targets $X_i=R_i+\gamma V_{k_1}(S_i^{\mathrm{\prime }})\in [0,C_1]$ with common mean $r(s,a)+\gamma P{V}_{k_1}$. By [F1], except with probability $2e^{-2m{ϵ}_1^2\mathrm{/}{C}_1^2}$, their average is within ${ϵ}_1$ of that mean. Also, the fixed targets $X_i^{\ast }=R_i+\gamma V^{\ast }(S_i^{\mathrm{\prime }})$ lie in $[0,C_1]$ and have mean $Q^{\ast }(s,a)$, so their average is within ${ϵ}_1$ of $Q^{\ast }(s,a)$ except with the same probability. By [F5], a finite union over the at most $N$ batch starts and these two error events has failure at most $4N{e}^{-2m{ϵ}_1^2\mathrm{/}{C}_1^2}\le \delta \mathrm{/}2$.

On the event from step 2.1, if a batch begins outside $K_{k_1}$, then $Q_{k_1}(s,a)-[r+\gamma P{V}_{k_1}]>3{ϵ}_1$. During that batch all action values can only decrease, so $V_{k_i}\le V_{k_1}$ at every sample time $k_i$. Its actual target average is therefore at most the frozen-target average, which is at most $r+\gamma P{V}_{k_1}+{ϵ}_1$. The old value minus this average is strictly greater than $2{ϵ}_1$, so the attempted update succeeds.

Initially $Q\ge Q^{\ast }$ by [F3]. Induct over successful updates. Before an update, all current values satisfy $V_{k_i}\ge V^{\ast }$ by the induction hypothesis, so each actual target $R_i+\gamma V_{k_i}(S_i^{\mathrm{\prime }})$ is at least $R_i+\gamma V^{\ast }(S_i^{\mathrm{\prime }})$. Step 2.1 bounds the latter sample mean below by $Q^{\ast }(s,a)-{ϵ}_1$. Adding the update bonus ${ϵ}_1$ leaves the new entry at least $Q^{\ast }(s,a)$; unchanged entries remain optimistic. This proves the all-time optimism claim. The event used above has probability at least $1-\delta \mathrm{/}2\ge 1-\delta$.

Fix a pair $(s,a)$. If $U(s,a)<V^{\ast }(s)$, choose an optimal action $a^{\ast }$ at $s$. On the optimism event, $Q_t(s,a^{\ast })\ge Q^{\ast }(s,a^{\ast })=V^{\ast }(s)$ for every $t$, while the pair's value never increases and therefore stays at most $U(s,a)<V^{\ast }(s)$. It is never selected, so it cannot be updated. If $U(s,a)\ge V^{\ast }(s)$ and the pair is selected, its current value is the greedy maximum and hence at least $V^{\ast }(s)$ by optimism of $a^{\ast }$. If the pair has $n\ge 1$ successful updates, the value immediately before its $n$th update is at most $U(s,a)-(n-1){ϵ}_1$ and at least $V^{\ast }(s)$. Indeed, each of the first $n-1$ updates decreases it by at least ${ϵ}_1$, and if any post-update value were below $V^{\ast }(s)$, the pair could never be selected again. Thus $n\le 1+[U(s,a)-V^{\ast }(s){]}_{+}\mathrm{/}{ϵ}_1$. The same bound holds when $n=0$ and in the first case. Summing over pairs proves the stated bound $G$.

It remains to count visits outside $K_t$. First, a failed attempted update that disables the learning flag must leave the pair inside $K$: since $b>t^{\ast }$, no Q table entry changed after that batch began, so the residual was constant through the batch; if it had been outside at batch start, step 3.1 would have forced success. Consequently a visit outside $K_t$ cannot occur with the flag still disabled: before sampling, [F2] tests $b\le t^{\ast }$, and an outside residual after the failed batch requires a later global update, which re-enables the flag. Now fix an outside visit for a pair while its flag is true. The next attempted batch occurs within at most $m$ visits to that pair. If the batch began outside $K$, step 3.1 makes it successful. If it began inside $K$, the residual became outside by the escape visit after a global update; with the pair's own Q value unchanged, other Q values only decrease, so its Bellman backup can only decrease and its residual remains outside through the attempted batch. Because a global update occurred after that batch began, a failed attempt does not disable the flag. The next attempted batch occurs within at most another $m$ visits and starts outside $K$, so step 3.1 makes it successful. Thus every interval between successive successful updates of this pair, including the initial interval, contains at most $2m$ outside visits. To include a possible final unfinished interval, count only intervals containing an outside visit. If the pair has $n$ successful updates and such an interval remains after the last update, its Q-value at an outside selection is at least $V^{\ast }(s)$ by step 4.1, while its $n$ previous updates have decreased it by at least $n{ϵ}_1$. Hence $n{ϵ}_1\le D(s,a)$ and these $n+1$ intervals number at most $1+D(s,a)\mathrm{/}{ϵ}_1$. If there is no such final interval, the at most $n$ completed intervals have the same bound by step 4.1. An interval with fewer than the $2m$ visits needed for its next success is included in this count; an interval with $2m$ outside visits would force that success by the preceding argument. Summing over pairs therefore gives at most $2mG$.