多腕バンディット問題におけるUCB方策を理解する

2020-05-16

多腕バンディット問題における解法の一つであるUCB1方策では以下のスコアを各腕に対して求め、最大のものを選択する。

\[ \overline{x}_j+\sqrt{\frac{2\ln{n}}{n_j}} \tag{1}\label{eq-1} \]

ここで、$\overline{x}_j$は腕$j$に対して観測された平均報酬、$n_j$は腕$j$が選択された回数、$n$は全体の試行回数である。第2項は選択された回数$n_j$が少ないほど大きくなることから、評価が不確かな腕ほど積極的に探索を行う（Optimism in face of uncertainty）。

本エントリでは、この第2項について上記の振る舞い以上の理解を進める。

確率不等式

\eqref{eq-1}式は確率不等式の一種であるヘフディングの不等式に基づいたものであるため、まず確率不等式を学ぶ。確率不等式は、確率の分布に依らない確率の近似的な評価に利用される不等式である。簡単には、稀に発生する事象についての確率の上限を求めることができる。

マルコフの不等式 Markov’s inequality

非負の確率変数$X\geq0$と任意の正数$a > 0$に対して

\[ Pr \left[ X \geq a \right] \leq \frac{E[X]}{a} \tag{2}\label{eq-2} \]

が成り立つ。\eqref{eq-2}をマルコフの不等式と呼ぶ。

この不等式を用いることで、確率変数$X$の実現値が$a$以上になる確率の上限を、確率分布に依らず期待値$E[X]$から求めることができる（ただし$a \leq E[X]$だと実用的な値にならない）。

マルコフの不等式を用いて例えば「期待値が10の確率変数で100以上が出る確率は10%以下」（$Pr \left[ X \geq 100 \right] \leq \frac{10}{100} = 0.1$）などと求めることができる。

証明は

\begin{align} E[X] &= \int_0^\infty x f(x) dx \notag \\ &= \int_0^a x f(x) dx + \int_a^\infty x f(x) dx \notag \\ &\geq \int_a^\infty x f(x) dx \notag \\ &\geq \int_a^\infty a f(x) dx = a \int_a^\infty f(x) dx = a Pr [X \geq a] \notag \\ \end{align}

となる。なお、2行目から3行目は、右辺第1項が$\geq 0$であるため。3行目から4行目は積分区間で最も小さい$a$を使うため。

チェビシェフの不等式 Chebyshev’s inequality

確率変数$X$が期待値$E[X]=\mu$、分散$\sigma^2$を持つとき、任意の正数$a > 0$に対して

\[ Pr \left[ \mid X - \mu \mid \geq a \sigma \right] \leq \frac{1}{a^2} \tag{3}\label{eq-3} \]

が成り立つ。\eqref{eq-3}をチェビシェフの不等式と呼ぶ。

この不等式を用いることで、確率変数$X$の実現値と期待値$\mu$の差が標準偏差$\sigma$の$a$倍以上になる確率の上限を、確率分布に依らず期待値$\mu$と分散$\sigma^2$から求めることができる。

証明は、マルコフの不等式に対して$X = (X-\mu)^2$と$a=a^2\sigma^2$とおいた時、

\[ Pr[(X-\mu)^2 \geq a^2\sigma^2] \leq \frac{E[(X-\mu)^2]}{a^2\sigma^2} = \frac{\sigma^2}{a^2\sigma^2} = \frac{1}{a^2} \\ Pr[\mid X-\mu \mid \geq a\sigma] \leq \frac{1}{a^2} \]

となる。なお、少し工夫して$a=a^2$とすると

\[ Pr[(X-\mu)^2 \geq a^2] \leq \frac{E[(X-\mu)^2]}{a^2} = \frac{\sigma^2}{a^2} \\ Pr[\mid X-\mu \mid \geq a] \leq \frac{\sigma^2}{a^2} \]

のように、確率変数$X$の実現値と期待値$\mu$の差を標準偏差$\sigma$を使わずに表現できる。この場合例えば「期待値が10で標準偏差が5の確率変数で100以上が出る確率は0.31%未満」（$Pr[X-10 \geq 90] \leq \frac{5^2}{90^2} = 0.00308…$）などと求めることができる。

ヘフディングの不等式 Hoeffding’s inequality

独立な$n$個の確率変数$X[a,b]$において平均を$\overline{X}$、期待値を$E\left[\overline{X}\right]$とおいた時、任意の正数$u > 0$に対して

\[ Pr \left[\overline{X}-E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right) \tag{4}\label{eq-4} \]

が成り立つ。\eqref{eq-4}をヘフディングの不等式と呼ぶ。

この不等式を用いることで、n個の確率変数$X$の平均と期待値の誤差が$u$以上になる（すなわち真の期待値を過大評価している）確率の上限を、確率分布に依らずに求めることができる。

同様に真の期待値を過小評価している確率の上限は、

\[ Pr \left[-\overline{X}+E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{\sum_{i=1}^{n}(b_i-a_i)^2}\right) \tag{5}\label{eq-5} \]

であり、真の期待値に対して$u$以上の誤差が生じる確率の上限は\eqref{eq-4}と\eqref{eq-5}を合わせた、

\[ Pr \left[\mid \overline{X}-E\left[\overline{X}\right] \mid \geq u\right] = Pr \left[\overline{X}-E\left[\overline{X}\right] \geq u\right] + Pr \left[-\overline{X}+E\left[\overline{X}\right] \geq u\right] \tag{6}\label{eq-6} \]

となる。

また、確率変数$X[a,b]$で$a=0,b=1$の時、\eqref{eq-4}より

\[ Pr \left[\overline{X}-E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{n}\right) = \exp\left(-2nu^2\right)\tag{7}\label{eq-7} \]

同じく\eqref{eq-5}より

\[ Pr \left[-\overline{X}+E\left[\overline{X}\right] \geq u\right] \leq \exp\left(-\frac{2n^2u^2}{n}\right) = \exp\left(-2nu^2\right)\tag{8}\label{eq-8} \]

である。証明は論文に譲る。

UCB1方策

UCB1方策では、ヘフディングの不等式\eqref{eq-8}を用いて、腕$j$の報酬の期待値の信頼区間の上側の上限である\eqref{eq-1}を求める。 \eqref{eq-1}を再掲する。

\[ \overline{x}_j+\sqrt{\frac{2\ln{n}}{n_j}} \tag{1} \]

腕$j$の報酬の期待値を$x^*_j$とすると\eqref{eq-8}は

\[ Pr \left[x^*_j \geq \overline{x}_j + u\right] \leq \exp\left(-2n_ju^2\right)\tag{9}\label{eq-9} \]

\eqref{eq-9}は真の期待値を過小評価している確率の上限であり、これを試行回数$n$が進むごとに小さくしたいと考える。そこで右辺を$n^{-m}=\frac{1}{n^m}$とすると、

\begin{align} \exp\left(-2n_ju^2\right) &= \frac{1}{n^m} \notag \\ -2n_ju^2 &= \ln{\frac{1}{n^m}} \notag \\ &= \ln{1} - \ln{n^m} \notag \\ &= 0 - m\ln{n} \notag \\ 2n_ju^2 &= m\ln{n} \notag \\ u^2 &= \frac{m\ln{n}}{2n_j} \notag \\ u &= \sqrt{\frac{m\ln{n}}{2n_j}} \notag \end{align}

が得られる。理論限界より$n$回目の試行において$1/n$の確率で各腕が選択する必要があるとされており、これに従えば$m=1$だが、論文では$m=4$としている（すなわち$u = \sqrt{\frac{2\ln{n}}{n_j}}$）。

これを\eqref{eq-9}に代入し

\[ Pr \left[x^*_j \geq \overline{x}_j + \sqrt{\frac{2\ln{n}}{n_j}}\right] \leq \frac{1}{n^4}\tag{10}\label{eq-10} \]

よって$1/n^4$の上限において、\eqref{eq-1}のスコアを用いて報酬の期待値を最も低く見積もっているであろう腕を選択することができる。すなわちOptimism in face of uncertaintyに従う。

THINKING MEGANE