## 4 DG-Moss
### The Upper Bound of the DM-MOSS Regret
Because once we choose the \(\tau_{k}\)-th arm \(k\), its index is always lower than that of \(arm1\), and we can safely come to the following conclusion:  
\[\underset{j=k_{0}}{\overset{K}{\sum}}\underset{k=j+1}{\overset{K}{\sum}}W_{ j,k}=\underset{k=k_{0}+1}{\overset{K}{\sum}}\underset{j=k_{0}}{\overset{K}{ \sum}}W_{j,k}=\underset{k=k_{0}+1}{\overset{K}{\sum}}\mathbb{I}_{Z\geq z_{k} }\triangle_{k}T_{k}(T)\leq\underset{k=k_{0}+1}{\overset{K}{\sum}}\tau_{k} \triangle_{k}. \tag{8}\]  
By combining (6) and (7) with (8) and adding the expectation, we can obtain Equation (9). \[P(\mathbb{E}(S_{n})-S_{n}\geq r)\leq\exp\biggl{(}-\frac{2r^{2}}{\sum_{i=1}^{n }(b-a)^{2}}\biggr{)}\]0  
Let \(\delta_{0}=e^{1/16}\sqrt{\frac{K}{T}}\) and set \(k_{0}\) to meet the condition \(\triangle_{k_{0}}\leq\delta_{0}\leq\triangle_{k_{0}}+1\). Bounding \(\mathbb{E}_{\tau_{k}}\) needs \(k_{0}+1\leq k\leq K\). Let \(\log_{+}(x)=max(\log{(x)},0)\). When \(\ell_{0}\in\mathbb{N}\), we obtain  
\[ \begin{split}&\mathbb{E}_{\tau_{k}}-\ell_{0}=\underset{\ell=0}{ \overset{+\infty}{\sum}}\mathbb{P}(\tau_{k}>\ell)-\ell_{0}\leq\underset{\ell= \ell_{0}}{\overset{+\infty}{\sum}}\mathbb{P}(\tau_{k}>\ell)=\underset{\ell= \ell_{0}}{\overset{+\infty}{\sum}}\mathbb{P}(\forall_{t}\leq\ell,B_{k,t}>z_{ k})\\ &\leq\underset{\ell=\ell_{0}}{\overset{+\infty}{\sum}}\mathbb{P} \Big{(}\hat{X}_{k,t}-\mu_{k}\geq\frac{\triangle_{k}}{2}-c*\sqrt{\frac{\log_{+} (T/K)}{\ell}}\Big{)}\end{split}  \tag{10}\]Now, let us assign a value \(\left\lceil 8\log\left(\frac{T}{K}\triangle_{k}^{2}\right)/\triangle_{k}^{2}\right\rceil\) to \(\ell_{0}\), where \(\lceil x\rceil\) is the smallest integer larger than \(x\). For \(\ell\geq\ell_{0}\), because \(k>k_{0}\), we have \(\ell\geq\triangle_{k}^{-2}\), and \(8\)\(\log_{+}\left(T/K\ell\right)\leq\ell\triangle_{k}^{2}\). Therefore:  
\[\frac{\triangle_{k}}{2}-\sqrt{\frac{\log_{+}\left(T/K\ell\right)}{\ell}}\geq \frac{\triangle_{k}}{2}-\frac{\triangle_{k}}{\sqrt{8}}=m\triangle_{k} \tag{11}\]  
where \(m=\frac{1}{2}-\frac{c}{\sqrt{8}}\) and \(c\) is the parameter from Equation (3). By using [PERSON]'s inequality [29] in Lemma 1 and Equation (10), we obtain:  
\[ \begin{split}&\mathbb{E}_{\tau_{k}}-\ell_{0}\leq\sum\limits_{\ell= \ell_{0}}^{+\infty}\mathbb{P}\bigg{(}\underset{k,\ell}{\overset{\wedge}{X}}- \mu_{k}\geq m\triangle_{k}\bigg{)}\\ &\leq\underset{\ell=\ell_{0}}{\overset{+\infty}{\underset{\ell= \ell_{0}}{\sum}}exp\left(-2\ell(m\triangle_{k})^{2}\right)}=\frac{exp\left(-2 \ell_{0}(m\triangle_{k})^{2}\right)}{1-exp\left(-2(m\triangle_{k})^{2}\right)} \leq\frac{1}{1-exp\left(-2m^{2}\triangle_{k}^{2}\right)}\end{split}  \tag{12}\]  
By substituting \(\ell_{0}\) with \(\left\lceil 8\log\left(\frac{T}{K}\triangle_{k}^{2}\right)/\triangle_{k}^{2}\right\rceil\) in Equation (12), we obtain:  
\[\triangle_{k}\mathbb{E}\tau_{k}\leq\triangle_{k}\bigg{(}1+\frac{8\log\left( \frac{T}{K}\triangle_{k}^{2}\right)}{\triangle_{k}^{2}}\bigg{)}+\frac{ \triangle_{k}}{1-exp\left(-2m^{2}\triangle_{k}^{2}\right)}\leq 1+8\frac{\log \left(\frac{T}{K}\triangle^{2}\right)}{\triangle_{k}}+\frac{1}{2m^{2}(1-m^{2}) \triangle_{k}} \tag{13}\]  
Because for any \(x\geq 0\), we have \(1-exp\left(-x\right)\geq x-x^{2}/2\), we obtain  
\[\frac{1}{1-exp\left(-2m^{2}\triangle_{k}^{2}\right)}\leq\frac{1}{2m^{2}\ \triangle_{k}^{2}-2m^{4}\triangle_{k}^{4}}\leq\frac{1}{2m^{2}\ \triangle_{k}^{2}\left(1-m^{2}\right)} \tag{14}\]  
This is a convention to check whether \(\frac{2}{\sqrt{\frac{T}{K}}}\) is the maximum of \(x\mapsto x^{-1}\log\left(\frac{T}{K}x^{2}\right)\) when using \(\triangle_{k}\geq e^{1/16}\sqrt{K/T}\), and we finally have  
\[K\underset{k>k_{0}}{\overset{\wedge}{\underset{k}{\sum}}}\triangle_{k}\mathbb{ E}\tau_{k}\leq K+\Bigg{(}\frac{16}{e}+\frac{e^{-1/16}}{-\frac{4}{\Delta}+ \frac{e^{3}}{2\sqrt{8}}-\frac{e^{2}}{\sqrt{8}}+\frac{e}{\sqrt{8}}}\Bigg{)} \sqrt{T}K\leq K+28.28\sqrt{T}K \tag{15}\]  
Thus, \(T\underset{k=k_{0}+1}{\overset{\wedge}{\underset{k}{\sum}}}\mathbb{P}(Z<z_{k })(\triangle_{k}-\triangle_{k-1})\) is bounded.