The zero-tolerance boundary of PAC-MDP exploration

For clause1, choose an integer $T>2B$ by [F5] and choose $0<d<\min \{1\mathrm{/}2,(1-2\delta )\mathrm{/}T\}$. Define two one-state models $M_{+},M_{-}$ whose action means are respectively $(1\mathrm{/}2+d,1\mathrm{/}2)$ and $(1\mathrm{/}2,1\mathrm{/}2+d)$, with Bernoulli rewards, discount zero, and common heuristic $1$. Their unique optimal actions are respectively $a,b$, and [F2] verifies their model and heuristic conditions.

For clause2 use the stated R-MAX model, and let $E$ be the event that its first $m$ rewards from $a$ are all zero. Its action means are $p,p\mathrm{/}2$, so $a$ is uniquely optimal and [F2] verifies admissibility.

For clause3 the action means are $1,1-{ϵ}_1$, so $a$ is uniquely optimal, the gap is ${ϵ}_1>0$, and [F2] verifies all model and heuristic conditions.

Couple the two length-$T$ histories of step 1.1 recursively. At equal histories draw the same action with the learning rule’s common action probabilities. For that action let $r_{+},r_{-}$ be its two means, and assign reward-pair probabilities $\min (r_{+},r_{-})$ to $(1,1)$, $1-\max (r_{+},r_{-})$ to $(0,0)$, $[r_{+}-r_{-}{]}_{+}$ to $(1,0)$, and $[r_{-}-r_{+}{]}_{+}$ to $(0,1)$. These weights are nonnegative, sum to one, have the desired Bernoulli marginals, and disagree with probability $d$. After histories differ, use the product of the two prescribed action/reward laws. Give each child its parent weight times its conditional probability. At each node [F4] shows that the child weights sum to its parent weight, so induction from root weight one normalizes the finite coupling. Summing over the other component at each extension gives the prescribed action and Bernoulli reward marginals; induction over rounds therefore verifies each marginal is the learning rule’s actual length-$T$ law by [F3]–[F4].

Until $a$ becomes known, R-MAX always selects $a$, since both unknown values are $1$ and its tie order favors $a$. On $E$, the first rebuild sets its value to zero while $b$ remains unknown at $1$. It therefore selects $b$ for $m$ observations, then the two frozen empirical means are $0,p\mathrm{/}2$. All later rebuilds and actions retain those means, so $b$ is selected forever. By [F1], all those later times are zero-bad. The first $m$ draws from $a$ have their Bernoulli law conditionally at each visit, hence $\mathbb{P}(E)=(1-p{)}^m$ and $E\subseteq \{N_0=\mathrm{\infty }\}$.

Delayed Q-learning initially ties at $1$ and selects $b$. Every target in its first batch is $1-{ϵ}_1$, since the discount is zero. The old value minus the mean is ${ϵ}_1<2{ϵ}_1$, so the batch fails and no value changes. Its start time is positive while $t^{\ast }=0$, so the flag becomes false. No other action is ever selected, no global update occurs, and the flag remains false. Induction gives $Q(a)=Q(b)=1$ and action $b$ forever. Its value is $1-{ϵ}_1<1=V^{\ast }$, so [F1] gives $N_0=\mathrm{\infty }$.

In the coupling of step 2.1, the probability that the first history disagreement occurs at a specified round is at most $d$, since its preceding equal histories have total probability at most one. Thus the chance of any disagreement by round $T$ is at most $Td$: sum the nonnegative weights of those disjoint first-disagreement events using [F3]–[F4]. Let $C$ be their complement, so $\mathbb{P}(C)\ge 1-Td$.

For the final assertion of clause2, fix $0<\delta <1$ and choose $p=(1-\delta )\mathrm{/}(2m)\in (0,1)$. Among the first $m$ rewards from $a$, the event of at least one reward equal to one has probability at most $mp$, by summing their indicator weights. Consequently $(1-p{)}^m\ge 1-mp=(1+\delta )\mathrm{/}2>\delta$. Step 2.2 proves the claimed failure probability.

Suppose both models from step 1.1 had $\mathbb{P}(N_0\le B)\ge 1-\delta$. The same is then true for the zero-bad count restricted to the first $T$ rounds, in each marginal of the finite coupling. The probability that both restricted counts are at most $B$ and $C$ occurs is at least $1-2\delta -Td>0$, by summing weights of the three complementary events as in [F3]–[F4]. On $C$, the two histories and hence their current action distributions coincide at every round. If $z$ is the probability of $a$, the two mean-reward deficits are respectively $d(1-z)$ and $dz$. Since $0\le z\le 1$ and $d>0$, at least one deficit is strictly positive. Thus the two restricted zero-bad counts sum to at least $T>2B$, contradicting that both are at most $B$. At least one model must satisfy $\mathbb{P}(N_0>B)>\delta$.

Step 4.1 proves clause1; steps 2.2 and3.2 prove clause2; step 2.3 proves clause3. For clause4, [F1] gives $0\le V^{A_t}(h_t)\le V^{\ast }(s_t)=0$, so no time is zero-bad. These statements establish all endpoint branches without assigning zero to a positive-tolerance denominator.