Optimistic exploration and PAC-MDP sample complexity — Examples

Since $\gamma =0$, every reward after the next reward has coefficient zero. Thus the controller continuation value at time $t$ is exactly the deterministic reward of its action at $t$, while the optimal value is $V^{\ast }=1$.

At exactly the indices $1,\dots ,n,n+2$, the chosen action is $b$, so its continuation value is $0<1-1\mathrm{/}2$ and each of those times is bad by [F2]. At every other time it chooses $a$ and has value $1$, so that time is not bad. There are $n+1$ bad indices, and $n+2$ is bad after the good index $n+1$.

Initially both action values equal $0$, so the fixed tie order chooses $b$. Its next state is the same state and its reward is $0$. Before the $m$th observation it remains unknown at value $0$. Since $\gamma =0$ and $\beta =1\mathrm{/}2$, the sweep count is $L=\max \{1,\lceil \ln 2\rceil \}=1$; on reaching $m$ samples, its empirical reward mean is $0$ and this sweep gives its known backup $0$, while the unvisited action $a$ still has heuristic value $0$.

The rebuilt values remain tied at zero, so the tie order again selects $b$. Induction over subsequent visits shows $a$ is never sampled and the table always has $Q(s,a)=Q(s,b)=0$. The heuristic is inadmissible since $U(a)=0<1=Q^{\ast }(s,a)$. At every time the continuation reward is zero, while $V^{\ast }(s)=1$, so $0<1-1\mathrm{/}2$ and every time is bad.

Since $V^{\ast }(s)\le (1-\gamma {)}^{-1}=U(s,a)$ and $ϵ\mathrm{/}4>0$, every pair satisfies $U(s,a)\ge V^{\ast }(s)-ϵ\mathrm{/}4$, so $\mathrm{\mid }{E}_{ϵ\mathrm{/}4}\mathrm{\mid }\le SA$. Nonnegativity and the value cap give $0\le [U(s,a)-V^{\ast }(s){]}_{+}\le (1-\gamma {)}^{-1}$ for each pair; summing proves the displayed gap estimate.

Substitute $\mathrm{\mid }{E}_{ϵ\mathrm{/}4}\mathrm{\mid }\le SA$ into [F2] and the gap estimate into [F3]. Their uninformative-heuristic cases give exactly the two displayed leading orders; the $\tilde{O}$ notation suppresses the logarithmic factors retained in the theorems.

Initially $Q(s,a)=Q(s,b)=1$, so the tie order selects $b$. Since $\gamma =0$, each of its first $m$ targets is its observed reward $0$; no update occurs before the batch completes. At the $m$th sample the mean is $0$, so $Q(s,b)-0=1\ge 2{ϵ}_1$ and [F1] updates it to ${ϵ}_1<1$.

The other action remains at value $1$, so the next greedy action is $a$. Also $V^{\ast }(s)=1$ and both heuristic values equal $1$, hence every $D(s,a)=0$ and their sum is zero. The batch of $m$ initial selections is a finite nonzero learning cost despite zero slack. This witnesses the per-pair $+1$ successful-update allowance in the theorem's count, which remains when all heuristic slacks vanish and produces the additive $SAϵ(1-\gamma )$ term after parameter substitution.