今日読んだ部分では確率的バンディット問題のアルゴリズムの一つであるUCBという手法について，アルゴリズムと定理，その証明を紹介しています．
２章 Stochastic Bandits: Fundamental Results
2.2 Upper Confidence Bound (UCB) Strategies
ここでは報酬$X$の確率分布は次のモーメントについての条件を満たすとする． どんな$\lambda$に対しても，$$\ln\mathbb{E}e^{\lambda(X-\mathbb{E}[X])}\le\psi(\lambda)~and~\ln\mathbb{E}e^{\lambda(\mathbb{E}[X]-X)}\le\psi(\lambda)\tag{2.2}$$ をみたす凸関数$\psi$が存在する． 例えば，$X\in[0,1]$のとき，$\psi(\lambda)=\frac{\lambda^2}{8}$とすると，ヘフディングの補題となる．
ここでは確率的マルチアームバンディット問題に対して「不確かなときは楽観的に」の原則に基づき取り組む． そうするために，式(2.2)を用いて固定の信頼水準のときのアームの平均の上界を構築し，最も良さそうなアームを選ぶ． 凸解析からLegendre–Fenchel transform（フェンシル変換）を導入する． 凸関数$\psi$のフェンシル変換は$$\psi^*(\epsilon)=\sup_{\lambda\in\mathbb{R}}(\lambda\epsilon-\psi(\lambda)).$$ 例として，$x>0$にたいして，$\psi(x)=e^x$ならば，$\psi^*(x)=x\ln x-x$． $\psi(x)=\frac{1}{p}|x|$ならば，$\psi^*(x)=\frac{1}{q}|x|$が$\frac{1}{p}+\frac{1}{q}=1$が成り立つような$1< p,q<\infty$に対して成り立つ．
アーム$i$を$s$回引いたときに得られる報酬の標本平均を$\hat{u}_{i,s}$とする．報酬は独立同分布から得られるので$\hat{\mu}_{i,s}=\frac{1}{s}\sum_{t=1}^sX_{i,t}$となる． マルコフの不等式を使って，式(2.2)から$$\mathbb{P}(\mu_{i}-\hat{\mu}_{i,s}>\epsilon)\le e^{-s\psi^*(\epsilon)}\tag{2.3}$$を得る．
マルコフの不等式を使って，式(2.2)から$\mathbb{P}(\mu_{i}-\hat{\mu}_{i,s}>\epsilon)\le e^{-s\psi^*(\epsilon)}$を得る．
式を眺めていただけだと得られなかったので，手を動かしてみる． まず，母平均が$\mu_i=\mathbb{E}_s[X_{i,s}]$であることと，標本平均が$\hat{\mu}_{i,s}=\frac{1}{s}\sum_{t=1}^sX_{i,t}$であることを用いて，$$\mathbb{P}(\mu_{i}\hat{\mu}_{i,s}>\epsilon)=\mathbb{P}\left(\mathbb{E}_s[X_{i,s}]-\frac{1}{s}\sum_{t=1}^sX_{i,s}>\epsilon\right)$$ と書き換える．次に，式(2.2)に寄せていくために自然対数の底$e$の肩に乗せる．$$\mathbb{P}\left(\mathbb{E}_s[X_{i,s}]-\frac{1}{s}\sum_{t=1}^sX_{i,s}>\epsilon\right)=\mathbb{P}\left(e^{\lambda\left(s\mathbb{E}_s[X_{i,s}]-\sum_{t=1}^sX_{i,s}\right)}>e^{s\epsilon\lambda}\right)$$ ここで，マルコフの不等式$\mathbb{P}(X\ge a)\le\frac{\mathbb{E}(X)}{a}$を用いる． $$\mathbb{P}\left(e^{\lambda\left(s\mathbb{E}_s[X_{i,s}]-\sum_{t=1}^sX_{i,s}\right)}>e^{s\epsilon\lambda}\right)\le\frac{\mathbb{E}[e^{\lambda\left(s\mathbb{E}_s[X_{i,s}]-\sum_{t=1}^sX_{i,s}\right)}]}{e^{s\epsilon\lambda}}.$$ ここで，$$\frac{\mathbb{E}[e^{\lambda\left(s\mathbb{E}_s[X_{i,s}]-\sum_{t=1}^sX_{i,s}\right)}]}{e^{s\epsilon\lambda}}=\frac{\mathbb{E}[e^{\lambda\left(\sum_{t=1}^s\mathbb{E}_s[X_{i,s}-X_{i,s}]\right)}]}{e^{s\epsilon\lambda}}.$$ 式(2.2)が使える形になったので，使うと$$\frac{\mathbb{E}[e^{\lambda\left(\sum_{t=1}^s\mathbb{E}_s[X_{i,s}-X_{i,s}]\right)}]}{e^{s\epsilon\lambda}}\le e^{s(\psi(\lambda)-\epsilon\lambda)}.$$ 上界で抑えて，フェンシル変換を用いると $$e^{s(\psi(\lambda)-\epsilon\lambda)}\le e^{-s(\sup_{\lambda}(\epsilon\lambda)-\psi(\lambda))}\le e^{-s\psi^*(\epsilon)}$$ となり，ほしかった式(2.3)が出てくる．
また，式(2.2)の右側を使うことで，$\mathbb{P}(\hat{\mu}_{i,s}-\mu_{i}>\epsilon)\le e^{-s\psi^*(\epsilon)}$を得ることもできる．
言い換えれば，少なくとも$1-\delta$の確率で，$$\hat{\mu}_{i,s}+(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{\delta}\right)>\mu_{i}$$がなりたつ．
少なくとも$1-\delta$の確率で，$\hat{\mu}_{i,s}+(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{\delta}\right)>\mu_{i}$がなりたつ．
手を動かして確認してみる．少なくとも$1-\delta$の確率で成り立つということは式(2.3)の右辺が$\delta$であるということである． $\delta=e^{-s\psi^*(\epsilon)}$とおくと，$$\delta=e^{-s\psi^*(\epsilon)}\iff \psi^*(\epsilon)=\frac{1}{s}\ln\frac{1}{s}\iff\epsilon=(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{s}\right).$$ これを式(2.3)の左辺の逆を取ったもの代入すると$\hat{\mu}_{i,s}+(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{\delta}\right)>\mu_{i}$が得られる．
また，式(2.2)の右側を使うことで，$\mu_{i}+(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{\delta}\right)\ge\hat{\mu}_{i,s}$を得ることもできる．
本題に戻る．
これを用いて，入力パラメータ$\alpha>0$にたいして$(\alpha,\psi)$-UCBという戦略を考える． 時刻$t$において，次のアームを選ぶ． $$I_t\in\rm arg\max_{i=1,\dots,K}\left[\hat{\mu}_{i,T_i(t-1)}+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_{i}(t-1)}\right)\right].$$ ここで，本にはないが，説明で使うために$\overline{\mu}_i=\hat{\mu}_{i,T_i(t-1)}+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_{i}(t-1)}\right)$をUCB用いたスコアと呼ぶことにする． これは$s$を$t-1$回までにアームを引いた回数$s=T_i(t-1)$とし，$\delta$を$\delta=1/t^\alpha$とすることに等しい． $\delta=1/t^\alpha$であることから，最初はガバガバな確率で母平均の上界を標本平均から構築し，試行を繰り返すごとに引き締まった確率になっていくことがわかる．
Theorem 2.1 $(\alpha,\psi)$-UCBの擬リグレット
報酬分布が式(2.2)を満たすと仮定する．$\alpha>2$を用いた$(\alpha,\psi)$-UCBは$$\overline{R}_n\le\sum_{i:\Delta_i>0}\left(\frac{\alpha\Delta_i}{\psi^*(\Delta_i/2)}\ln n+\frac{\alpha}{\alpha-2}\right)$$を満たす．
報酬が$[0,1]$の値を取る場合，式(2.2)で$\psi(\lambda)=\frac{\lambda^2}{8}$とするとヘフディングの補題となり，$\psi^*(\epsilon)=2\epsilon^2$となる． そして，擬リグレットの上界は$$\overline{R}_n\le\sum_{i:\Delta_i>0}\left(\frac{2\alpha}{\Delta_i}\ln n+\frac{\alpha}{\alpha-2}\right)\tag{2.4}$$となる． この重要な特殊化した$(\alpha,\psi)$-UCBの例を$\alpha$-UCBと呼ぶ．
証明
はじめに，$I_t=i$ならば，以下の３つの不等式のうち少なくとも１つは成り立つ． $$\hat{\mu}_{i^*,T_{i^*}(t-1)}+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_{i^*}(t-1)}\right)\le\mu^*\tag{2.5}$$ $$\hat{\mu}_{i,T_{i}(t-1)}>\mu_i+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_{i}(t-1)}\right)\tag{2.6}$$ $$T_i(t-1)<\frac{\alpha\ln t}{\psi^*(\Delta_i/2)}\tag{2.7}$$
$I_t=i$ならば，以下の３つの不等式のうち少なくとも１つは成り立つ．
このあと，３つの式がどれも成り立たないと仮定しきたとき，アルゴリズムが矛盾するということが示されて，３つのうち少なくとも１つは成り立つことが示される． しかし，これらの式がどこから降ってきたのかわからないので，考えてみる．
アーム$i$が引かれたとき，次の３つの場合が考えられる．（信頼区間の上界と下界はUCBスコアを導入する際に導出してある．）
-
最適なアームの標本平均が下ブレすぎて，信頼区間の下界の下にある場合
最適なアームアーム$i^*$について，信頼区間の下界について$\hat{\mu}_{i,s}>\mu_{i}-(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{\delta}\right)$が成り立っていない場合は式(2.5)そのものとなる． -
引いたアームの標本平均が上ブレ過ぎて，信頼区間の上界の上にある場合
引いたアーム$i$について，信頼区間の上界について$\hat{\mu}_{i,s}\le\mu_{i}+(\psi^*)^{-1}\left(\frac{1}{s}\ln\frac{1}{\delta}\right)$が成り立っていない場合は式(2.6)そのものとなる． -
引いたアームと最適なアームの信頼区間がともに正しい（標本平均が信頼区間の中に入っている）場合
このとき，UCBスコアについて，$\overline{\mu}_{i^*}>\mu^*$，$\overline{\mu}_{i}>\mu_i$が成り立っている． また，（アーム$i$が引かれたので）$\overline{\mu}_i\ge\overline{\mu}_{i^*}$が成り立っている． これらをあわせて$$\overline{\mu}_{i}=\hat{\mu}_i+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_i(t-1)}\right)>\mu_{i^*}$$が成り立つ． これに$\hat{\mu}_i+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_i(t-1)}\right)>\mu_i$を用いて，$\hat{\mu}_i$を消去すると， $$2(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_i(t-1)}\right)>\mu_{i^*}-\mu_i=\Delta_i$$を得る． 逆関数をもとにもどすと，$T_i(t-1)<\frac{\alpha\ln t}{\psi^*(\Delta_i/2)}$が得られる．
３つの式が全て偽であった場合を考える． $$\hat{\mu}_{i^*,T_{i^*,}(t-1)}+(\psi)^*\left(\frac{\alpha\ln t}{T_{i^*}(t-1)}\right)>\mu^*$$ $$=\mu_i-\Delta_i$$ $$\ge\mu_i+2(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_i(t-1)}\right)$$ $$\ge\hat{\mu}_{i,T_i(t-1)}+2(\psi^*)^{-1}\left(\frac{\alpha\ln t}{T_i(t-1)}\right)$$ となる．これはUCBスコアが最適アームのほうが大きくなり，$I_t\not=i$であることを示していて矛盾する．
言い換えれば，擬リグレットのバウンドを証明するためには$u=\lceil\frac{\alpha\ln n}{\psi^*(\Delta_i/2)}\rceil$とおいたとき， $$\mathbb{E}T_i(n)=\mathbb{E}\sum_{t=1}^n\mathbb{1}_{I_t=i}\le u+\mathbb{E}\sum_{t=u+1}^{n}\mathbb{1}_{I_t=i~and~(2.7)~is~false}$$ 式(2.7)が成り立たないとき，式(2.5)または式(2.6)が成り立つので，アーム$i$を引いたことを省略して書くと， $$\le u+\mathbb{E}\sum_{t=u+1}^{n}\mathbb{1}_{(2.5)~or~(2.6)~is~true}$$ 指示関数の期待値は確率になるので， $$=u+\sum_{t=u+1}^{n}\mathbb{P}((2.5)~is~true)+\mathbb{P}((2.6)~is~true)$$
ここで，$$\mathbb{P}((2.5)~is~true)\le\mathbb{P}\left(\exists s\in\{1,\dots,t\}:\hat{u}_{i^*,s}+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{s}\right)\le\mu^*\right)$$ ユニオンバウンドを使って， $$\le\sum_{s=1}^t\mathbb{P}\left(\hat{u}_{i^*,s}+(\psi^*)^{-1}\left(\frac{\alpha\ln t}{s}\right)\le\mu^*\right)$$ $t$回目の試行のとき$\delta=\frac{1}{t^\alpha}$であったので， $$\le\sum_{s=1}^t\frac{1}{t^\alpha}=\frac{1}{t^{\alpha-1}}$$ が成り立つ．式(2.6)についても同様の上界が求められる． シンプルな計算によって，証明が得られる．
シンプルな計算によって，証明が得られる．
手を動かして確認してみる．
今までに得られた結果より， $$\mathbb{E}T_i(n)\le\frac{\alpha\ln n}{\psi^*(\Delta_i/2)}+2\sum_{t=u+1}^{n}\frac{1}{t^{\alpha-1}}$$ $$\le\frac{\alpha\ln n}{\psi^*(\Delta_i/2)}+2\sum_{t=u+1}^{\infty}\frac{1}{t^{\alpha-1}}$$ 短冊を考えて $$\le\frac{\alpha\ln n}{\psi^*(\Delta_i/2)}+2\int_{t=u}^{\infty}\frac{1}{t^{\alpha-1}}dt$$ 積分を解いて $$\le\frac{\alpha\ln n}{\psi^*(\Delta_i/2)}+\frac{2}{-(\alpha-2)}\left[\frac{1}{t^{\alpha-2}}\right]_{u}^\infty=\frac{\alpha\ln n}{\psi^*(\Delta_i/2)}+\frac{2}{u^{\alpha-2}(\alpha-2)}$$
ここまで正しければ， $$\frac{2}{u^{\alpha-2}(\alpha-2)}\le\frac{\alpha}{\Delta_i(\alpha-2)}$$ がでてくるはずなのですが，わかりませんでした(´・ω・｀)．