Bandit Algorithm Tor Lattimore Solution to Exercise 23.2

1 min read読了の目安(約1200字

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)}.

の2個目の不等式を証明することです.

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}でチューニングすると,大意の式が得られる.