Claim 4  \(\mathbb {E}_a[T_{x,a}^-] \le \mathbb {E}_\textrm {unif}[T_{x,a}^-] + O\left(\frac{K\Delta }{\epsilon } \sqrt{\mathbb {E}_{\textrm {unif}}[T^-_{x,a}]}\right)\) .
[Claim 4]  With standard arguments from [1]}, because \(0\le T_{x,a}^-\le \frac{K}{\epsilon }\) , we have
\(&\mathbb {E}_a[T_{x,a}^-] - \mathbb {E}_{\textrm {unif}}[T_{x,a}^-] \\ &\le \frac{K}{\epsilon } \Vert \mathbb {P}_a - \mathbb {P}_{\textrm {unif}}\Vert _1 \\&\le \frac{K}{\epsilon }\sqrt{\frac{1}{2}\text{KL}(\mathbb {P}_a, \mathbb {P}_\textrm {unif})} \\&= \frac{K}{\epsilon }\sqrt{\frac{1}{2}\sum _{t=1}^{K/\epsilon -1} \mathbb {P}_\textrm {unif}[(s_{t}, a_{t})=(x,a)] \text{KL}\left(\text{Multi}\left(\frac{1-\epsilon }{2}, \frac{1-\epsilon }{2}, \epsilon \right), \text{Multi}\left(\frac{1-\epsilon +\Delta }{2}, \frac{1-\epsilon -\Delta }{2}, \epsilon \right)\right)} \\&\le O\left(\frac{K}{\epsilon }\sqrt{\sum _{t=1}^{K/\epsilon }\mathbb {P}_\textrm {unif}[(s_t,a_t)=(x,a)] \times \frac{\Delta ^2}{1-\epsilon }} \right) \\&= O\left(\frac{K\Delta }{\epsilon } \sqrt{\mathbb {E}_{\textrm {unif}}[T^-_{x,a}]}\right).\) 
