max k-armed banditとは？

はじめに

multi-armed banditは近年，広告・記事推薦やモンテカルロ木探索などに盛んに応用されてきているため，耳にすることが増えてきました．
一般的には，複数個の選択肢（Arm）の中から，得られる報酬の期待値が高いものを選ぶ，ということが目的とされることが多いです．
しかし，この分野の中には，得られる報酬の最大値が高くなるようにArmの選択回数をallocateする，という一風変わったmax k-armed banditという問題設定があります．

この記事では，max k-armed banditの問題設定の紹介と，文献¹で示された最適戦略の理論解析について解説をしたいと思います．

max k-armed bandit

max k-armed banditでは，通常のmulti-armed banditと同様に，$k$個のArmの中から一つを選んで報酬を観測することを繰り返します．
各Armからの報酬は何らかの確率分布に従ってサンプルされます．

max k-armed banditにおける目的は，全部で$N$回Armを選択するときに得られる報酬の最大値を最大化することです．
これは言い換えると，報酬を最大化するために$N$回のArm選択をどのように各アームに割り振るか，という問題になります：

\max \max_{i=1}^k \max_{j=1}^{n_i} R_j(D_i),\\
where \sum_{i=1}^{k}n_i=N

ここで，$R_j(D_i)$は報酬が確率分布$D_i$に従うようなArm $i$を$j$回目に選択したときに得られる報酬を表しています．

max k-armed banditの応用先

max k-armed banditは，探索アルゴリズムを最適化問題に複数回適用するときに現れる問題設定です．
NP困難な最適化問題の近似解を得るためにヒューリスティクスなアルゴリズムが使われることがよくありますが，アルゴリズムが出力する解は問題によって異なります．
さらに，アルゴリズムが確率的な操作を含んでいる場合には，同じアルゴリズムを同じ問題に適用したとしても出力される解が異なることがあります．

アルゴリズムを適用するたびに結果が異なるので，安定していい解を得るためには，複数回アルゴリズムを問題に適用する必要があります．
ここで重要なのが，「どのアルゴリズムが一番良い解を得ることができるのか」ということを考えた上で適用するアルゴリズムを決定する，ということです．

この問題は，アルゴリズム=Armであり，出力される解の性能=報酬，とみなすことで，「最高の性能の解が得られるようにアルゴリズムを選択する」という目的を持つmax k-armed banditとして考えることができます．

最適戦略の理論解析

文献¹では，各Armの報酬分布にある仮定を置くと，「max k-armed banditにおける最適なArm選択戦略は最適なArmを他のArmよりもdouble exponentiallyな回数だけ引く必要がある」ということが理論的に証明されています．

ここからは，その証明の解説を行います．

報酬分布の仮定

証明のために，各Armの報酬がGumbel分布に従うと仮定します．
Gumbel分布は，以下のような確率密度関数，および累積分布関数を持ちます．

P(Z\leq z) = G(z) = \exp\left(-\exp\left(-\left(\frac{z-b}{a}\right)\right)\right),\\
P(Z=z) = \frac{1}{a}\exp\left(-\left(\frac{z-b}{a}\right)\right)\exp\left(-\exp\left(-\left(\frac{z-b}{a}\right)\right)\right)

ここで，$a$はscaleパラメータ，$b$はlocationパラメータと呼ばれます．

定理

各Armの報酬分布がGumbel分布であるとき，観測された中で最良のArmを
以下の回数だけ引く必要がある．

N-(k-1)m^{\ast}\sim \Theta(\exp(\exp(cm^{\ast})))

ただし，$m^{\ast}$は最良のArm以外の$k-1$個のArmを引く回数，$c$は定数を表しています．

証明

Max 2-armed bandit case

まず，簡単のためArmが２つしか存在しない場合における証明を行い，その後，$k$個のArmがある場合へと一般化します．

まず，ある分布からの$N$個の報酬$\{X_1,\cdots,X_N\}$の中の最大値が$x$となる確率は，以下のように表せます．

P(\max(X_i)=x)=NP(X=x)P(X\leq x)^{N-1}

報酬がGumbel分布に従うと仮定したので，この式は，さらに以下のように展開できます．

\begin{align}
P(\max(X_i)=x)&= \frac{N}{a}\exp\left(-\frac{x-b}{a}\right)\exp\left(-\exp\left(\frac{x-b}{a}\right)\right)\exp\left(-(N-1)\exp\left(-\frac{x-b}{a}\right)\right)\\
&= \frac{1}{a}\exp\left(-\frac{x-b-a\ln N}{a}\right)\exp\left(-\exp\left(-\frac{x-b-a\ln N}{a}\right)\right)
\end{align}

この式もまたGumbel分布の確率密度関数となっていることがわかります．
したがって，$N$個の報酬中の最大値はscaleパラメータが$a_{\mathrm{max}}=a$，locationパラメータが$b_{\mathrm{max}}=b+a\ln N$のGumbel分布に従います．

さて，Arm $1$がArm $2$より良い，すなわち最良なArmであるとし，観測された中で最良のArmから$N-n$個，二番目のArmから$n$個ずつ報酬をサンプルするとしましょう．
「最良であるArm」とは，以下の式で表される$N$個の報酬中の最大値の期待値が最大であるArmのことを指します．

b_i+0.5772a_i+a_i\ln N

最良でないArmを引いたことによる損失を最良なArmを$N$回ピッタリ引いたときの期待値からの差分として定義すると，以下のように場合分けすることで求めることができます．

1. 観測された中で最良のArmが真に最良のArmである場合，最良なArmを$n$回分引けなかったことによって損失が生じます： $a_1(\ln N -\ln (N-n))$
2. 観測された中で最良のArmが真に最良のArmでない場合，二番目に良いArmを$N-n$回分，一番目に良いArmを$n$回分引くことになります． 前者による報酬の最大値の期待値は$b_2+0.5772a_2+a_2\ln (N-n)$，後者による報酬の最大の期待値は$b_1+0.5772a_1+a_1\ln n$となります． したがって，この場合における損失は，以下のように求まります： $\min\{a_1(\ln N -\ln n), (b_1-b_2)+0.5772(a_1-a_2)+a_1\ln N -a_2\ln (N-n)\}$． この損失は最良のArmを$n$回引いたときと二番目に良いArmを$N-n$回引いたときの報酬の最大値の期待値が等しいときに最大となり，その値は$a_1(\ln N -\ln n)$となります． これが最悪のケースでの損失となるため，以降ではこの損失を用いて議論を進めます．

つづいて，観測された中で最良のArmが実際には二番目に良いArmである確率を$q$とすると，損失の期待値は以下のように表せます．

\begin{align}
l(N) &= q(a_1(\ln N -\ln n))+(1-q)(a_1(\ln N -\ln (N-n)))\\
&= q(a_1(\ln (N-n)- \ln n)) + a_1(\ln N - \ln (N-n))
\end{align}

$M_b$を最良と思われるArm，$M_w$を二番目に良いと思われるArmとすると，確率$q$は，「$M_b$からの$N$個の報酬の最大値の期待値が，$M_w$からの$N$個の報酬の最大値の期待値よりも低くなる確率」と言い換えることができます．
Gumbel分布のパラメータの推定値$\tilde{a}=\frac{s\sqrt{6}}{\pi}$と$\tilde{b}=\bar{X}-0.5772\tilde{a}$を用いると，$q$を以下のように定義できます．

\begin{align}
q(n) &= P((\tilde{b}_b+0.5772\tilde{a}_b+\tilde{a}_b\ln N)<(\tilde{b}_w+0.5772\tilde{a}_w+\tilde{a}_w\ln N)\\
&= P\left(\left(\bar{X}_b+\frac{s_b\sqrt{6}}{\pi}\ln N\right)<\left(\bar{X}_w+\frac{s_w\sqrt{6}}{\pi}\ln N\right)\right)\\
&= P\left(\bar{X}_b-\bar{X}_w<(s_w-s_b)\frac{\sqrt{6}}{\pi}\ln N\right)
\end{align}

ここで，$\bar{X}$と$s$はサンプル平均と標準偏差を表しています．

中心極限定理より，$\bar{X}_b$は平均$\mu_b$，分散$\frac{\sigma^2_b}{N-n}$の正規分布に近づき，$\bar{X}_w$は平均$\mu_w$，分散$\frac{\sigma^2_w}{n}$の正規分布に近づきます．
さらに正規分布の再生性より，$\bar{X}_b-\bar{X}_w$も平均$\mu_b-\mu_w$，分散$\frac{\sigma^2_b}{N-n}+\frac{\sigma^2_w}{n}$の正規分布に近づきます．
このことと，

\int_{-\infty}^{-x}\frac{1}{\sqrt{2\pi}}e^{-t^2/2}dt = \int_{x}^{\infty}\frac{1}{\sqrt{2\pi}}e^{-t^2/2}dt \leq \int_{x}^{\infty}\frac{t}{x}\frac{1}{\sqrt{2\pi}}e^{-t^2/2}dt = \frac{e^{-x^2/2}}{x\sqrt{2\pi}}

が成り立つことを用いると，$N$と$n$が十分に大きいとき，$q(n)$に関して以下の式が成り立ちます．

\begin{align}
q(n)&\lesssim \frac{1}{\sqrt{2\pi}}\frac{\exp(-x^2/2)}{x},\\
x&=\frac{(\mu_b-\mu_w)+\frac{\sqrt{6}}{\pi}\ln (N)\left(\frac{\sigma_b}{\sqrt{N-n}}-\frac{\sigma_w}{\sqrt{n}}\right)}{\sqrt{\frac{\sigma^2_b}{N-n}+\frac{\sigma^2_w}{n}}}
\end{align}

さらに，$N$が$n$に比べて十分に大きいとき，

x\sim \frac{(\mu_b-\mu_w)\sqrt{n}-\frac{\sigma_w\sqrt{6}}{\pi}\ln N}{\sigma_w}

とみなせます．

損失$l(n)$を最小にする$n$が最適な$n$ですので，この$n$を求めましょう．
そのために，$l(n)$を$n$に関して微分します．

\begin{align}
\frac{dl}{dn} &= \frac{dq}{dn}(a_1(\ln (N-n)-\ln n)) - q(n)\left(\frac{a_1}{N-n}+\frac{a_1}{n}\right)+\frac{a_1}{N-n},\\
\frac{dq}{dn}&\lesssim -q(n)\frac{x^2+1}{x}\frac{dx}{dn},\\
\frac{dx}{dn}&= \frac{\mu_b-\mu_w}{2\sigma_w\sqrt{n}}
\end{align}

最適な$n$は$\frac{dl}{dn}=0$を満たすはずなので，$n$に関して以下の制約式を導出することができます．

\frac{dl}{dn}=0 \lesssim \frac{a_1}{N-n}-q(n)\frac{a_1N}{N-n}-q(n)\frac{x^2+1}{x}\frac{dx}{dn}(a_1(\ln(N-n)-\ln n))

さらに式変形すると，

\ln (N-n)-\ln n\lesssim \frac{(1-q(n)N)x}{(N-n)q(n)\frac{dx}{dn}(x^2+1)}

が得られます．
ここで，$q(n)$は$n$が増加すると指数関数的に減少することと，$\frac{x}{x^2+1}\leq \frac{1}{x}$であることを用いると，

\begin{align}
\ln (N-n)-\ln n &\lesssim \frac{1}{(N-n)q(n)\frac{dx}{dn}x}\\
&\lesssim \frac{\sigma_w\sqrt{8\pi}\sqrt{n}}{(N-n)(\mu_b-\mu_w)}\exp\left(\frac{(\mu_b-\mu_w-\frac{\sigma_w\sqrt{6}}{\pi\sqrt{n}}\ln N)^2 n}{2\sigma^2_w}\right)
\end{align}

が得られます．

これを整理すると，

N-n\lesssim \exp\left(\ln (n)+\exp\left(\frac{(\mu_b-\mu_w-\frac{\sigma_w\sqrt{6}}{\pi\sqrt{n}}\ln N)^2 n}{2\sigma^2_w}+\ln \left(\frac{\sigma_w\sqrt{8\pi}\sqrt{n}}{(N-n)(\mu_b-\mu_w)}\right)\right)\right)

となります．

この式では$(\ln(N))^2$が支配的であり，それ以外の部分を無視して考えると，

N-n \sim \Theta(\exp(\exp(cn)))

となります．
これでArmが二つしかない場合について証明をすることができました．
次は$k$個のArmがある場合へと一般化します．

Max k-armed bandit case

k個のArmがある場合，最悪のケースでの損失は最良のArm以外の$k-1$個のArmが同じ報酬分布を持つときに発生します．
このケースにおいては，$k-1$個のArmのそれぞれについて考える必要はなく，まとめて一つのArmとしてみなすことができます．
そのようにみなすことで，Armは最良のArmと$k-1$個のArmがひとかたまりになったArmの二つと考えることができるので，二つのArmにおける証明と同じ議論をすることができます．

従って，$k-1$個のArmを合わせて$m^{\ast}(k-1)$回引いたとすると，$n=m^{\ast}(k-1)$とすることで最良のArmを引く回数$N-m^{\ast}(k-1)$に関して，以下の式が成り立ちます．

N-m^{\ast}(k-1) \sim \Theta(\exp(\exp(cm^{\ast})))

おわりに

max k-armed banditはあまり研究が行われていない分野ですが，アルゴリズム選択など応用先はありそうなので個人的に注目しています．
今回の証明では報酬分布にGumbel分布を仮定しましたが，これはかなり強い仮定で，実際の問題では報酬がGumbel分布に従うとみなせることはおそらく少ないでしょう．
そこで，報酬分布に関する仮定を弱めた上で理論的解析を行う研究も出てきています．
そちらもそのうち紹介できるといいなと考えています．

読んでくださりありがとうございました．

---

1. The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection ↩