## 4 DG-Moss
### The Upper Bound of the DM-MOSS Regret
Let \(X_{t}\) denote the reward obtained by \(arm1\), when it is pulled for the \(t\)-th time. The random variables \(X_{1},X_{2},\cdots,X_{n}\) are independent and identically distributed. Using [PERSON]'s inequality in Lemma 1 for any \(x>0\) and \(n\geq 1\), we have  
\[\mathbb{P}\bigg{(}\exists s\in\{1,\cdots,n\},\sum\limits_{t=1}^{s}\left( \mu_{1}-X_{t}\right)>x\bigg{)}\leq exp\bigg{(}-\frac{2x^{2}}{n}\bigg{)} \tag{16}\]  
With \(z_{k}=\mu_{1}-\triangle_{k}/2\) and \(\mu\mapsto\mathbb{P}(Z<\mu_{1}-\mu/2)\) satisfying a non-increasing function, we get  
\[\begin{split}&\sum\limits_{k=k_{0}+1}^{K}\mathbb{P}(Z  
We use a stripping parameter \(s\) with the form \(\frac{1}{2^{\ell+1}}f(u)\leq s\leq\frac{1}{2^{\ell}}f(u):\)  
\[ \begin{array}{l}\mathbb{P}\bigg{(}\exists 1\leq s\leq f(u):\sum\limits_{t=1}^{s} \left(\mu_{1}-X_{t}\right)>\sqrt{s\log\left(\frac{T}{Ks}\right)}\bigg{)}\\ \leq\sum\limits_{\ell_{0}}^{+\infty}\mathbb{P}\bigg{(}\exists\frac{1}{2^{\ell +1}}f(u)\leq s\leq\frac{1}{2^{\ell}}f(u):\sum\limits_{t=1}^{s}\left(\mu_{1}-X _{t}\right)>\sqrt{\frac{f(u)}{2^{\ell+1}}\log\left(\frac{T2^{\ell}}{Kf(u)} \right)}\bigg{)}\\ \leq\sum\limits_{\ell=0}^{+\infty}exp\left(-2\frac{f(u)\frac{1}{2^{\ell+1}} \log\left(\frac{T2^{\ell}}{Kf(u)}\right)}{f(u)\frac{1}{2^{\ell}}}\right)= \sum\limits_{\ell=0}^{+\infty}\frac{Kf(u)}{T}\frac{1}{2^{\ell}}=2\frac{Kf(u) }{T}\end{array}  \tag{19}\]  
Next, let us integrate \(f(u)\):  
\[\int_{\delta_{0}}^{1}f(u)du=\Bigg{[}\frac{8\log\left(e\sqrt{T/K}u\right)}{u} \Bigg{]}_{1}^{\delta_{0}}\leq\frac{17e^{-1/16}}{2}\sqrt{T/K} \tag{20}\]  
We use a stripping parameter again with the form \(2^{\ell}\,f(u)\leq s\leq 2^{\ell+1}\,f(u)\), and set \(\omega(u)=2^{\ell+1}\,f(u):\sum\limits_{t=1}^{s}\left(\mu_{1}-X_{t}\right)>2^ {\ell-1}\,f(u)u\). \[ \begin{array}{l}\mathbb{P}\bigg{(}\exists s\in\{\lceil f(u)\rceil,\cdots,T \}:\sum\limits_{t=1}^{s}\left(\mu_{1}-X_{t}\right)>\frac{su}{2}\bigg{)}\\ \leq\sum\limits_{\ell=0}^{+\infty}\mathbb{P}\bigg{(}\exists 2^{\ell}\,f(u) \leq s\leq\omega(u)\bigg{)}\leq\sum\limits_{\ell=0}^{+\infty}exp\bigg{(}-2 \frac{\left(2^{\ell-1}\,f(u)u\right)^{2}}{f(u)^{2\ell+1}}\bigg{)}=\sum\limits _{\ell=0}^{+\infty}exp\left(-2^{\ell}\,f(u)u^{2}\,/4\right)\\ \leq\sum\limits_{\ell=0}^{+\infty}exp\big{(}-(\ell+1)f(u)u^{2}\,/4\big{)}= \frac{1}{exp(f(u)u^{2}\,/4)-1}\end{array}  \tag{21}\]  
From the choice of \(f(u)\), we finally use the upper bounded by \(\frac{1}{\frac{1}{\ln^{2}/K-1}}\). When we integrate this quantity again, we can obtain  
\[\int_{\delta_{0}}^{1}\frac{1}{\frac{1}{\ln^{2}/K-1}}du\leq \frac{1}{2}\log\bigg{(}\frac{e^{1/16}+1}{e^{1/16}-1}\bigg{)}\sqrt{ \frac{K}{T}} \tag{22}\]  
Eventually, we have a conclusion  
\[ \begin{array}{l}T\sum\limits_{k=k_{0}+1}^{K}\mathbb{P}(Z<z_{k})(\bigtriangleup _{k}-\bigtriangleup_{k-1})\\ \leq T\big{(}\delta_{0}-\bigtriangleup_{k_{0}}\big{)}+\Big{(}17e^{-1/16}+ \frac{1}{2}\log\left(\frac{e^{1/16}+1}{e^{1/16}-1}\right)\Big{)}\sqrt{TK} \leq T\big{(}\delta_{0}-\bigtriangleup_{k_{0}}\big{)}+17.8\sqrt{TK}\end{array}  \tag{23}\]  
Combining (9), (15) and (23), we obtain  
\[\frac{1}{P_{1}}R_{T}\leq 48.28\sqrt{TK}+K\]  
From Algorithm 3, \(P_{1}+P_{2}=1\), \(0<P_{1}<1\) and \(0<P_{2}<1\), we obtain the upper bound of the regret value from Equation (2)  
\[R_{T}+P_{2}*1\leq R_{T}+(1-P_{1})\leq P_{1}*48.28\sqrtThe probability \(0<P_{1}<1\), \(\mathbb{E}[R(T)]\) is bounded regardless of the value of \(P_{1}\). Therefore, we conclude that the DG-MOSS algorithm has an upper bound of the regret value, so this algorithm is stable. The proof of the upper bound of DG-MOSS confirms that the actions selected based on DG-MOSS satisfy this theorem, providing a solid theoretical basis for recommendation for small and medium-sized datasets.