## 4 DG-Moss
### The Upper Bound of the DM-MOSS Regret  
In this section, we provide the upper bound of the regret of DG-MOSS. **Lemma 1**. : _Chernoff-Hoeffding inequality_  
_Let \(X_{1},X_{2},\cdots,X_{n}\) be independent and identically distributed random variables with values on the interval \([0,1]\), and let \(S_{n}=\sum_{i=1}^{n}X_{i}\). For all \(r>0\), \(a=0\), \(b=1\), we have_  
\[P(S_{n}-\mathbb{E}(S_{n})\geq r)\leq\exp\biggl{(}-\frac{2r^{2}}{\sum_{i=1}^{n }(b-a)^{2}}\biggr{)}\]  
_and_  
\[P(\mathbb{E}(S_{n})-S_{n}\geq r)\leq\exp\biggl{(}-\frac{2r^{2}}{\sum_{i=1}^{n }(b-a)^{2}}\biggr{)}\]  
**Theorem 1**. : _DG-MOSS satisfies supremum \(\mathbb{E}[R(T)]\leq P_{1}*48.28\sqrt{TK}+(K-1)P_{1}+1\), where \(P_{1}\) is a probability, and \(0<P_{1}<1\). The supremum is selected from all sets of \(K\) probability distributions on the interval \([0,1]\)._  
Proof. : Without loss of generality, we assume that the true optimal arm is \(arm1\), \(a^{*}=a^{*}\left(\theta^{0}\right)=1\), \(P_{1}\) and \(P_{2}\) are probability parameters, and we rewrite the expected regret \(\mathbb{E}[R(T)]\) in Equation (1) as follows:  
\[\mathbb{E}[R(T)]=\left[\sum_{t=1}^{T}\left(u_{1}^{0}-u_{a(t)}^{0}\right) \right]=P_{1}*\underset{i=1,\cdots K}{max}\mathbb{E}\sum_{t=1}^{T}\left(u_{1} ^{0}-u_{a(t)}^{0}\right)+P_{2}*1 \tag{2}\]  
Let \(K\geq 2\) be the number of actions (or arms) and \(T\geq K\) be the time horizon. The algorithm follows at each time step \(t\in[1,\cdots T]\). \[\text{Let }R_{T}=P_{1}*\underset{i=1,\cdots k}{max}\sum_{t=1}^{T}\left(u_{1}^{0} -u_{a(t)}^{0}\right).\]We assume \(u_{1}\geq u_{2}\geq\cdots\geq u_{k}\), and \(\triangle_{k}=u_{1}-u_{k}\). By [PERSON]'s identity [28], we have \(B_{T}=P_{1}*\mathbb{E}\sum_{k}\triangle_{k}T_{k}(T)\) for an arm \(k\). Then, we define its index value \(V_{k,s}\) as  
\[V_{k,s}=\hat{X}_{k,s}+c*\sqrt{\frac{\Big{(}max\Big{(}\log\frac{T}{k_{s}}\Big{)},0\Big{)}}{s}} \tag{3}\]  
where \(\hat{X}_{k,s}\) is the empirical mean of arm \(k\) after \(s\) pulled of this arm. Tightly upper bounding \(B_{T}\) is difficult because of the heavy dependence on the random variables \(T_{k}(T)\). For an arm \(k_{0}\), to decouple the arms, we introduce the key thresholds \(z_{k}=u_{1}-\frac{\triangle_{k}}{2}\) for \(k_{0}\leq k\leq K+1\) and \(z_{k_{0}}=+\infty\). By defining  
\[Z=\underset{1\leq s\leq T}{min}V_{1,s} \tag{4}\]  
\[W_{j,k}=\mathbb{I}_{z\in\big{(}z_{j+1},z_{j}\big{)}}\triangle_{k}T_{k}(T). \tag{5}\]  
we obtain  
\[\underset{k=k_{0}+1}{\overset{K}{\sum}}\triangle_{k}T_{k}(T)=\underset{k=k_{0 }+1}{\overset{K}{\sum}}\underset{j=k_{0}}{\overset{K}{\sum}}W_{j,k}= \underset{j=k_{0}}{\overset{K}{\sum}}\underset{k=k_{0}+1}{\overset{j}{\sum}} W_{j,k}+\underset{j=k_{0}}{\overset{K}{\sum}}\underset{k=j+1}{\overset{K}{ \sum}}W_{j,k}. \tag{6}\]  
The Abel transformation was proposed by Norwegian mathematician [PERSON] in the 19 th century. Given a function \(f(x)\)and a real number \(y\), the [PERSON] transformation can be defined as \(F(y)=\int_{y}^{\infty}f(x)\frac{dx}{\sqrt{x^{2}-y^{2}}}\). \(F(y)\)is the Abel transformation of function \(f(x)\). By using an Abel transformation in Equation (6), we have  
\[\underset{j=k_{0}}{\overset{K}{\sum}}\underset{k=k_{0}+1}{\overset{j}{\sum} }W_{j,k}\leq\underset{j=k_{0}}{\overset{K}{\sum}}\mathbb{I}_{z\in\big{(}z_{j +1},z_{j}\big{)}}T\triangle_{j}=T\triangle_{k_{0}}+T\underset{j=k_{0}+1}{ \overset{K}{\sum}}\mathbb{I}_{z<z_{j}}\big{(}\triangle_{j}-\triangle_{j-1} \big{)}. \tag{7}\]  
To bound the second sum of Equation (7), we adopt the stopping times \(\tau_{k}=min\big{\{}t:B_{k,t}<z_{k}\big{\}}\) and remark that, in the process, by the definition of DG-MOSS, we have \(\big{\{}Z\geq z_{k}\big{\}}\subset\{T_{k}(T)\leq\tau_{k}\big{\}}\).