how to proof decaying ε-greedy algorithm has a s logarithmic asymptotic total regret? David silver point out that the decaying ε-greedy algorithm has a logarithmic asymptotic total regret in his lecture https://www.davidsilver.uk/wp-content/uploads/2020/03/XX.pdf, however no proof is given out. Can anybody explains how such regret is obtained?
 A: Here's an informal proof sketch;
On non-explore round $t \leq T$, what is the probability we take a suboptimal action $a \neq a^*$?
Let $\hat \mu(a; n)$ denote the random empirical average of $n$ samples from action $a$, and $n_t(a)$ denote the random number of times we have taken action $a$ up to round $t$. We have;
\begin{align}
\Pr(a_t = a \mid \text{non explore}) 
&= \Pr(\hat \mu(a; n_t(a)) > \hat \mu(a^*; n_t(a^*)))
\\
&\leq \Pr(\hat \mu(a; k_t) - \hat \mu(a^*; k_t) > 0), 
\end{align}
where $k_t := c\log t /d^2$. This follows since in expectation (and actually with high probability) each action is explored $k_t$ times till round $t$. Now the empirical sub-optimality r.v. $\hat \mu(a; k_t) - \hat \mu(a^*; k_t)$ has expectation $-\Delta(a)$, and by Hoeffding's inequality we can deduce
\begin{align}
\Pr(\hat \mu(a; k_t) - \hat \mu(a^*; k_t) > 0) 
&= \Pr(\hat \mu(a; k_t) - \hat \mu(a^*; k_t) - (-\Delta(a)) > \Delta(a)) 
\\
&\leq e^{-\Delta(a)^2 k_t}
=e^{-\Delta(a)^2 c \log t/ d^2}
\leq \frac{1}{t^c}.
\end{align}
Hence, choosing $c=2$ we bound the number of (non-explore) suboptimal action plays by a constant (note the exploration schedule is where the logarithmic factor comes from).
A formal proof can be found in Auer et al. '02.
In addition, similar arguments are made in a more didactic manner in Slivkins '19 (although not for this specific algorithm).
