Escape-event reduction for optimistic greedy learning

Fix a history at time $t$ at which the current optimism and policy-accuracy inequalities in the Statement hold, and let $W_t$ be the event that before $H$ transitions elapse the algorithm updates some Q-value or selects a pair outside $K_t$. If $W_t$ does not occur, the greedy policy and known set remain fixed, every selected pair is in $K_t$, and the true interaction and $M_t$ have the same transition/reward kernels along these $H$ steps by [F1]. The expected truncated returns therefore agree on $W_t^c$. On $W_t$, stop the coupling at the first update or outside-pair selection. The common prefix cancels. At any history, the true continuation value is at most $B$ by [F2]. In $M_t$, before the first outside pair a policy follows a true-MDP prefix; its expected nonnegative prefix is at most $B$, since continuing that policy in the true MDP can only add nonnegative rewards. After the first outside pair its dedicated sink contributes exactly $Q_t(s,a)\le W$ by [F1] and the Statement. Thus every policy value in $M_t$, including its continuation after the stopping history, is at most $B+W=C$. Since both continuation values are nonnegative, their absolute difference is at most $C$, and the expected loss contributed by $W_t$ is at most $C\mathbb{P}(W_t\mid h_t)$.

The known-model policy's infinite return exceeds its $H$-step truncated return by at most ${\gamma }^H\mathrm{/}(1-\gamma )\le \eta$, by the definition of $H$; for $\gamma =0$ the tail is zero. The true return is at least its truncated return because rewards are nonnegative. Combining step 1.1 with the assumed policy accuracy and optimism gives $V^{A_t}(h_t)\ge V_t(s_t)-2\eta -C\mathbb{P}(W_t\mid h_t)\ge V^{\ast }(s_t)-3\eta -C\mathbb{P}(W_t\mid h_t)$. Therefore, if $t$ is counted by $N_{4\eta }$, then $\mathbb{P}(W_t\mid h_t)>\eta \mathrm{/}C\ge q$.

Construct trials by starting at the first bad time not already covered by a previous trial window, running that window for $H$ transitions, and then waiting for the next bad time. The starts are stopping times: each bad-time test and current inequality is history measurable. For the continuation-value test, finite-horizon continuation values are measurable by recursive kernel integration using [F7], and the discounted continuation value is their increasing limit. The windows are disjoint. At a trial start satisfying the two current optimism and accuracy inequalities, its conditional chance of containing an update or escape is at least $q$ by step 2.1; this statement conditions only on its starting history, not on the future simultaneous good event. Every such success occurs at a distinct update/escape time, so on the simultaneous complexity event there are at most $\zeta$ successes. Each trial window contains at most $H$ bad times, and there are no bad times between a completed window and the next trial start.

Write ${\tau }_i$ for the successive trial starts, setting ${\tau }_i=\mathrm{\infty }$ when no such start exists. For $i\le M$, set $X_i=1$ if ${\tau }_i=\mathrm{\infty }$ or either current optimism/accuracy inequality fails at its start; otherwise let $X_i$ indicate an update or escape during its window. Use the stopped-history sigma-algebra at ${\tau }_i$, with the full path sigma-algebra on $\{{\tau }_i=\mathrm{\infty }\}$. It contains every earlier window outcome. On the first two cases $X_i=1$; in the remaining case step 2.1 gives conditional success probability at least $q$. Thus $\mathbb{E}[X_i\mid {\mathcal{F}}_{{\tau }_i}]\ge q$ without conditioning on the simultaneous future good event. Since $e^{-\lambda X_i}=1-(1-e^{-\lambda })X_i$, [F5] and induction give $\mathbb{E}[e^{-\lambda {\sum }_{i=1}^M{X}_i}]\le (1-q(1-e^{-\lambda }){)}^M\le e^{-Mq\mathrm{/}2}$ for $\lambda =\ln 2$. Applying [F6] to this nonnegative exponential yields $\mathbb{P}({\sum }_{i=1}^M{X}_i\le \zeta )\le e^{(\zeta +1)\ln 2-Mq\mathrm{/}2}\le \rho$ by the definition of $M$. If more than $M$ bad-time trials occurred while the simultaneous optimism, accuracy and complexity event held, the first $M$ starts would be finite and every $X_i$ would be its actual update/escape indicator, so their sum would be at most $\zeta$. This has probability at most $\rho$. Adding the probability at most $\rho$ that the simultaneous assumptions fail proves that, with probability at least $1-2\rho$, there are at most $M$ trials and hence at most $HM$ bad times.