今日読んだ部分では確率的バンディット問題の分布がベルヌーイだったときの下界を出しています
２章 Stochastic Bandits: Fundamental Results
2.3 Lower Bound
前の節の結果が確率分布がベルヌーイのとき改善できないということを示す．
$p,q\in[0,1]$に対して，パラメータが$p$のベルヌーイ分布とパラメータが$q$のベルヌーイ分布のカルバック・ライブラーダーバージェンスを$$k(p,q)=p\ln\frac{p}{q}+(1-p)\ln\frac{1-p}{1-q}$$と定義する．
Theorem 2.2 (Distribution-dependent lower bound). どんなベルヌーイからの報酬の分布の集合，$\Delta_i>0$となるアーム$i$，$a>0$に対しても，$\mathbb{E}T_i(n)=\mathcal{o}(n^a)$を満たすような戦略を考える． どんなベルヌーイからの報酬の分布の集合に対してもいかが成り立つ． $$\lim_{n\rightarrow+\infty}\inf\frac{\overline{R}_n}{\ln n}\ge\sum_{i:\Delta_i>0}\frac{\Delta_i}{kl(\mu_i,\mu^*)}.$$
式(2.4)の結果と比較するために左側からはPinskerの不等式，右側からは$\ln x\le x-1$を用いて， $$2(p-q)^2\le kl(p,q)\le\frac{(p-q)^2}{q(1-q)}$$を用いる．
証明
証明は３つのステップから構成される．かんたんのためアームが２つのときのみを考える．
First step: Notations
一般性を損なうことなく，アーム１を最適なアーム，アーム２を最適でないアームとする．つまり，$\mu_2<\mu_1<1$とする． また，$\epsilon>0$とする．$x\mapsto kl(\mu_2,x)$は連続であるため，$$kl(\mu_2,\mu_2')\le(1+\epsilon)kl(\mu_2,\mu_1)\tag{2.9}$$を満たすような$\mu_2'\in(\mu_1,1)$を見つけることができる（アーム１より優れたアーム）．
アーム２のパラメータを$\mu_2'$に置き換えた修正されたバンディットに対して積分したとき，$\mathbb{E}'$，$\mathbb{P}'$と記す． もとのバンディット問題と修正されたバンディット問題に対しての予測者の振る舞いを比較したい． 特に，予測者が２つの問題を区別できない確率が十分に大きいことを証明したい． そして，仮説により，良い予測者がいるという事実を用いて，アーム２が最適である．修正されたバンディット問題に対してアルゴリズムはあまり多くの失敗はしないことを知っている． 言い換えれば，最適なアームが試行される回数についての下界を知っている． この理由のため，もとの問題でアーム２が試行される回数の下界が暗に示される．
ここで，報酬の表記法を変えて，アーム２から$n$回引いたときに得られる確率変数列を$X_{2,1},\dots,X_{2,n}$と記す．（つまり，$s$回目に引いた報酬を$X_{2,s}$とする．） $s\in\{1,\dots,n\}$に対して， $$\hat{kl}_s=\sum_{t=1}^s\ln\frac{\mu_2X_{2,t}+(1-\mu_2)(1-X_{2,t})}{\mu_2’X_{2,t}+(1-\mu_2')(1-X_{2,t})}$$ $X_{2.s}$はパラメータが$\mu_2$であるベルヌーイ分布からi.i.d.にサンプルされているので，もとのバンディットについて，$\hat{kl}_{T_2(n)}$は（正規化されていない）$n$ステップ目での$kl(\mu_2,\mu_2')$の経験的な推定量になっている．（sステップ目で報酬は（アーム２を引いたとき）＋（アーム２を引かなかったとき）＝$\mu_2X_{2,t}+(1-\mu_2)(1-X_{2,t})$） もう一つの重要な性質は次のようなものだ． $X_{2,1},\dots,X_{2,n}$によって生成される完全加法族のどんな事象$A$に対しても，以下のchange-of-measure identityが成り立つ． $$\mathbb{P}'(A)=\mathbb{E}[\mathbb{1}_A\exp(-\hat{kl}_{T_2(n)})]\tag{2.10}$$
元のバンディット問題と修正されたバンディット問題の予測者の振る舞いを結びつけるために，次の事象を導入する． $$C_n=\left\{T_2(n)<\frac{1-\epsilon}{kl(\mu_2,\mu_2')}\ln(n)~and~\hat{kl}_{T_2(n)}\le\left(1-\frac{\epsilon}{2}\right)\ln(n)\right\}\tag{2.11}$$
Second step: $P(C_n) = \mathcal{o}(1)$
式(2.10)と式(2.11)により $$\mathbb{P}'(C_n)=\mathbb{E}\mathbb{1}_{C_n}\exp(-\hat{kl}_{T_2(n)})\ge e^{-(1-\epsilon/2)\ln(n)}\mathbb{P}(C_n)$$ かんたんのために$$f_n=\frac{1-\epsilon}{kl(\mu_2,\mu_2')}\ln(n)$$ を導入する．
式(2.11)とマルコフの不等式$\mathbb{P}(|X|\ge a)\le\frac{\mathbb{E}(|X|)}{a}$を用いて， $$\mathbb{P}(C_n)\le n^{(1-\epsilon/2)}\mathbb{P}'(C_n)\le n^{(1-\epsilon/2)}\mathbb{P}'(T_2(n)< f_n)\le n^{(1-\epsilon/2)}\frac{\mathbb{E}[n-T_2(n)]}{n-f_n}$$
修正されたバンディット問題のアーム２は唯一の最適なアームである． これによって，どんなバンディット問題，どんな最適でないアーム$i$，任意の$a>0$に対して，戦略は$\mathbb{E}T_i(n)=\mathcal{o}(n^a)$を満たす． よって， $$P(C_n)\le n^{1-\epsilon/2}\frac{\mathbb{E}'[n-T_2(n)]}{n-f_n}=\mathcal{o}(1)$$
Third step: $\mathbb{P}(T_2(n) < f_n) = \mathcal{o}(1)$
$$\mathbb{P}(C_n)\ge\mathbb{P}\left(T_2(n)< f_n~and~\max_{s\le f_n}\hat{kl}_s\le\left(1-\frac{1}{\epsilon}\right)\ln(n)\right)$$ これが成り立つのは右辺のほうが，式(2.11)の右側の事象が起きる確率が減るためだと思われる($T_2(n)< f_n$のため)． $$=\mathbb{P}\left(T_2(n)< f_n~and~\frac{kl(\mu_2,\mu_2')}{(1-\epsilon)\ln(n)}\max_{s\le f_n}\hat{kl}_s\le\frac{1-\epsilon/2}{1-\epsilon}kl(\mu_2,\mu_2')\right)\tag{2.12}$$ これは右側の事象を両辺$f_n$でわった．
次の大数の強法則の最大バージョンを使う． 正の平均$\mu>0$をもつ，独立な実数の確率変数のどんな列$(X_t)$に対しても， $$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{t=1}^nX_t\mu ~almost~surely$$ が成り立つ．これにより $$\lim_{n\rightarrow\infty}\frac{1}{n}\max_{s=1,\dots,n}\sum_{t=1}^sX_t\mu ~almost~surely$$ が成り立つことがわかる．
$kl(\mu_2,\mu_2')>0$と$\frac{1-\epsilon/2}{1-\epsilon}>1$であるから， $$\lim_{n\rightarrow\infty}\mathbb{P}\left(\frac{kl(\mu_2,\mu_2')}{(1-\epsilon)\ln(n)}\max_{s\le f_n}\hat{kl}_s\le\frac{1-\epsilon/2}{1-\epsilon}kl(\mu_2,\mu_2')\right)=1$$ (KLダイバージェンスは正であるから両辺から符号を変えずに消せる＋左辺のみ$1/\ln n$で減少)
これによって，second stepの結果と式(2.12)から， $$\mathbb{P}(T_2(n)< f_n)=\mathcal{o}(1)$$ ($\mathbb{P}(C_n)$は$\mathcal{o}(1)$であるのに，下から抑えている条件の右側は1に収束していく．このため，左側の条件が$\mathcal{o}(1)$になるしかない．)
$f_n=\frac{1-\epsilon}{kl(\mu_2,\mu_2')}\ln(n)$と式(2.9)を用いて， $$\mathbb{E}T_2(n)\ge(1+\mathcal{o}(1))\frac{1-\epsilon}{1+\epsilon}\frac{\ln(n)}{kl(\mu_2,\mu_1)}$$ これを擬リグレットの定義に入れると題意を得る．
最後の$n$回までにアーム２を引く回数の期待値の下界で$(1+\mathcal{o}(1))$が出てくるのがどうやるのかわからなかった(´・ω・｀)
手を動かしてみる．
$\mathbb{P}(T_2(n)< f_n)=\mathcal{o}(1)$であるから$\mathbb{P}(T_2(n)\ge f_n)=1-\mathcal{o}(1)$である． マルコフの不等式$\mathbb{P}(|X|\ge a)\le\frac{\mathbb{E}(|X|)}{a}$を使って，$\frac{\mathbb{E}T_2(n)}{f_n}\ge\mathbb{P}(T_2(n)\ge f_n)=1-\mathcal{o}(1)$ となり， $$\mathbb{E}T_2(n)\ge(1-\mathcal{o}(1))\frac{1-\epsilon}{1+\epsilon}\frac{\ln(n)}{kl(\mu_2,\mu_1)}$$ が得られる．
他の文献を見ても下界の定数部分のオーダは$1-\mathcal{o}(1)$となっているので，元論文のタイポかもしれない