Tor LattimoreのBandit AlgorithmのExerciseの解答です．間違いがありましたら教えていただけると助かります．
Exercise 23.2
問題は，Theorem 23.2
There exists a universal constants C, C' > 0 such that the regret of SETC satisfies
R_n \leq 3 \|\theta\|_1 + C\sum_{i:\theta_i \ne 0} \frac{\log(n)}{|\theta_i|} \text{ and } R_n \leq 3\|\theta\|_1 + C' \|\theta\|_0\sqrt{n\log(n)}.
の２個目の不等式を証明することです．
Solution
R_nをactionの次元ごとに分解すると，R_n = \sum_{i=1}^dR_{ni}であり，
R_{ni} = n|\theta_i| - \mathrm{E}\Big[\sum_{t=1}^nA_{ti}\theta_i\Big].
本文の証明で，この分解したリグレットは，\theta_i \neq 0の下では以下のように抑えられます．
R_{ni} \leq 3|\theta_i| + \frac{C\log(n)}{|\theta_i|}
\theta_iの絶対値の大きさで二つに分解します．具体的には，\Deltaより大きいものと小さいもので分けると，
R_{n} \leq \sum_{i: |\theta_i| \geq \Delta}R_{ni} + \sum_{i: |\theta_i| < \Delta}R_{ni}
さらに，SETCのアルゴリズムより，真逆の間違え方をしても大きくても2n|\theta_i|のリグレットを被るので，R_{ni} \leq 2n|\theta_i|です．
よって，二つの不等式を合わせると，
R_{n} \leq \sum_{i: |\theta_i| \geq \Delta}\Big(3|\theta_i| + \frac{C\log(n)}{|\theta_i|}\Big) + \sum_{i: |\theta_i| < \Delta} 2n|\theta_i| \leq 3\|\theta\|_1 + \frac{C\|\theta\|_0\log(n)}{\Delta} + 2\|\theta\|_0n\Delta.
ここで，\|\theta\|_0は0でない成分の個数．
最後に\Delta=\sqrt{\log(n)/n}でチューニングすると，大意の式が得られる．
Discussion