多腕バンディットアルゴリズムのリグレット解析

はじめに

活用と探索をいい具合にバランスしつつ, 報酬を最大化することを目標とする多腕バンディット問題は, web広告の最適化などへの応用が期待されることから大きな注目を集めています. この分野に関してはこれまでにいくつかの素晴らしい記事が存在しますが, その理論解析に踏み込んだものはありませんでした. 本記事では, 有名なアルゴリズムを例にして, バンディットアルゴリズムの理論解析の雰囲気をさらってみます.

目次

定式化

まずは(確率的)多腕バンディット問題を定式化します. 定式化に関しては, こちらの記事で非常にわかりやすくまとめられているため, ここでは簡単に記述します.

多腕バンディット問題では, playerに対してarmと呼ばれるいくつかの行動の選択肢が与えられます. 各armは報酬と呼ばれる未知の確率分布に従う確率変数と対応付けられています. playerは, 各時刻にいずれかのarmを選択してそのarmに紐づく報酬の実現値を観測します. このような試行を繰り返すうちに, 各armの報酬が従う確率分布のパラメータを推定(探索)しながら, 同時に得られる報酬を最大化すること(活用)がplayerの目標です.

今, armの集合を \mathcal{A} = \{1, ..., a , ..., K \}とし, ある時刻 tにあるarm  aから観測される報酬は, 区間 [0, 1]に値をとる確率変数 X_{a, t}に独立に従うとします. また, arm  aを選択することで得られる期待報酬を \mathbb{E} \left[ X_{a, t} \right] = \mu_{a} と表記します.

このとき, 多腕バンディット問題では次のように定義される期待累積リグレット(以降, リグレット)を考えます.


\begin{aligned}
R (T) 
& = \mathbb{E} \left[ \max_{a \in \mathcal{A}} \sum_{t = 1}^T  X_{a, t} - X_{a(t), t}  \right] \\
& =  \sum_{a = 1}^K \Delta_{a} \mathbb{E} \left[ T_a \right]
\end{aligned}


ここで, 総試行回数を T, 時刻 tにおいて選択されるarmを a(t), 最適なarmとの期待報酬のgapを \Delta_a , 全ての試行が終了した時点においてarm  aを選択した回数を T_aとしました. リグレットは, 最適な固定戦略  a^{*} = \arg \max_{ a \in \mathcal{A}} \mu_{a} を取ることで得られる期待累積報酬と playerの取る戦略  \{ a(t) : t = 1, 2, ..., T \} によって得られる期待累積報酬の差の合計だと解釈できます. これは, 達成し得た最大の報酬からの後悔の量と言えるのでリグレットと名付けられています.

playerはリグレット R(T)を最小化することを目指します. また, armの選択を出力するアルゴリズム (player) が達成するリグレットの上界を導出することが主要な理論的興味になります. ちなみにLai et al. (1985)によると, 期待リグレットの理論限界は \Omega (\log T)であることが知られており, アルゴリズムにはこの理論限界を達成していて欲しいということになります.

Upper Confidence Boundアルゴリズム

多腕バンディット問題の中でとてもよく知られたアルゴリズムに, Upper Confidence Bound (UCB) アルゴリズムというものがあります. これは, ある時刻においてそれまでに観測された報酬によって推定される期待報酬の上側信頼区間が最大になるarmを選択するアルゴリズムになります. 上側信頼区間を推定する際の有意水準は時刻 tに対して t^{- \alpha}程度に設定されることが多いので今回はそれに従います.

期待報酬の上側信頼区間が最大になるarmを選択するという方針の解釈は決して難しくないと思いますが, 具体的なアルゴリズムはどのように構成すれば良いのでしょうか? 実は, 以前の記事で紹介したHoeffding's ineqを活用することでこの方針を実現するアルゴリズムを導くことができます.

ここで, 時刻 tの試行が終了した時点においてarm  aを選択した回数を T_{a, t}として, 時刻 tにおける選択前までの観測報酬を用いて各armの期待報酬の推定量を次のように構築します. と言っても, ただ観測報酬を平均しているだけです.


\begin{aligned}
\hat{\mu}_{ a, T_{a, t - 1} } = \frac{1}{ T_{a, t - 1} } \sum_{s=1}^{t-1} \mathbb{I} \{ a(t) = a \} X_{a, s}
\end{aligned}


この推定量が真の期待報酬 \mu_aを大きく過小評価してしまう確率はHoeffding's ineqを用いて次のように評価できます.


\begin{aligned}
\mathbb{P} \left( \mu_a - \hat{\mu}_a \geqq \epsilon \right) \leqq  \exp \left( - 2 T_{a, t - 1} \epsilon^2 \right)
\end{aligned}


右辺を t^{-\alpha}とおいて変形を加えると,


\begin{aligned}
\mathbb{P} \left( \mu_a < \hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t - 1}}  } \right) > 1 - t^{- \alpha}
\end{aligned}


よって, Hoeffding's ineqを用いることにより各armの有意水準 t^{- \alpha}での上側信頼区間の上界を得ることができました. これに従い, UCBアルゴリズムは次のように定義されるUCBスコアが最大になるようなarmを各時刻において選択するようなアルゴリズムになっています.


\begin{aligned}
UCB_{a, t} = \hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t - 1)}{2 T_{a, t - 1}} }
\end{aligned}


擬似コードは次の通りです.

f:id:usaito:20190501053314p:plain

リグレット上界の導出

さて, 本章では前章で紹介したUCBアルゴリズムが達成するリグレットの上界を導きます. しかしここでは, UCBアルゴリズムが理論限界を達成することを示すため簡易なリグレット上界の導出を採用します.

以降一般性を失うことなく,  a^* = 1であるとします. armの期待報酬の推定が大きく外れる場合とそうでない場合に場合分けする方針をとります. まず, 次の2つの事象 A_t B_tを考えます.

  •  A_t:  \hat{\mu}_{ a, T_{a, t} } \leqq \mu_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} }
  •  B_t:  \hat{\mu}_{ 1, T_{1, t} } \geqq \mu_1 -  \sqrt{ \frac{\alpha \log (t)}{2 T_{1, t}} }

つまり,  A_tは時刻 tにおけるあるarmの期待報酬の推定がそこまで大きくならないという事象のこと.  B_tは時刻 tにおける最適なarmの期待報酬の推定がそこまで小さくならないという事象のことです. まず,  A_tの補事象が起こる確率を評価します.


\begin{aligned}
\mathbb{P} \left( A_t^c \right) 
& = \mathbb{P} \left(  \hat{\mu}_{ a, T_{a, t} } -  \mu_a  >   \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} } \right) \\
& \leqq t^{- \alpha} \quad \because Hoeffding's \: ineq 
\end{aligned}


同様に,  \mathbb{P} \left( B_t^{c} \right) \leqq  t^{- \alpha}  です. よってunion boundを用いれば,


\begin{aligned}
\sum_{t = 1}^T  \mathbb{E} \left[ \mathbb{I} \{ A_t^c \cup B_t^c \} \right]  
& \leqq \sum_{t = 1}^T \left(  \mathbb{E} \left[ \mathbb{I} \{ A_t^c \} \right] + \mathbb{E} \left[ \mathbb{I} \{ B_t^c \} \right]   \right) \\
& \leqq 2 \sum_{t = 1}^T t^{- \alpha} \\
& \leqq  2 \left( 1 + \int_1^{\infty} x^{-\alpha} dx \right)  \\
& = \frac{2 \alpha}{\alpha - 1}
\end{aligned}


です.

次に, 事象 A_t, B_tが共に成り立つ場合を考えます. まず, 最適ではないarmが選択されるのは, 次の不等式が成り立つ場合です.


\begin{aligned}
\hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} } > \hat{\mu}_1 +  \sqrt{ \frac{\alpha \log (t)}{2 T_{1, t}} }
\end{aligned}


今, 事象 A_tが成り立っているので, 両辺に \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} }を足せば,


\begin{aligned}
\hat{\mu}_{ a, T_{a, t} } + \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} } \leqq \mu_a +  \sqrt{ \frac{2 \alpha \log (t)}{ T_{a, t}} }
\end{aligned}


です. これを用いれば,


\begin{aligned}
\mu_1 
&  \leqq \hat{\mu}_{ 1, T_{a, t} } +  \sqrt{ \frac{\alpha \log (t)}{2 T_{1, t}} } \quad \because B_t \\
& \leqq  \hat{\mu}_a +  \sqrt{ \frac{\alpha \log (t)}{2 T_{a, t}} }  \\
& \leqq \mu_a +  \sqrt{ \frac{2 \alpha \log (t)}{ T_{a, t}} }
\end{aligned}


です.  T_{a, t}について整理すると,


\begin{aligned}
T_{a, t}  \leqq 2 \Delta_a^{-2} \log (t) \leqq  2 \Delta_a^{-2} \log (T) 
\end{aligned}


を得ます. 最終的には,


\begin{aligned}
\mathbb{E} \left[ T_a \right] 
& \leqq  2  \left (   \Delta_a^{-2} \log (T)  +  \frac{\alpha}{\alpha - 1}\right)
\end{aligned}


よって,


\begin{aligned}
R(T)
& = \sum_{a \neq 1} \Delta_{a} \mathbb{E} \left[ T_a \right] \\
&=  \sum_{a \neq 1} \Delta_{a} \left(  \mathbb{E} \left[ \mathbb{I} \{ A_t \cap B_t \} \right]   +  \mathbb{E} \left[ \mathbb{I} \{ A_t^c \cup B_t^c \} \right]  \right) \\
& \leqq  2 \sum_{a \neq 1}   \left (   \frac{ \log (T) }{\Delta_a } +  \frac{\alpha}{\alpha - 1} \Delta_a \right)
\end{aligned}


というリグレットの上界が導かれます. これによりUCBアルゴリズムのリグレット上界は悪くても \mathcal{O} (\log T)のオーダーです. Lai et al. (1985)における理論限界は \Omega(\log T)でしたので, UCBアルゴリズムは理論限界と同様のオーダーを達成することがわかりました.

さいごに

今回は, 単純にarmの報酬のみから次に選択するarmを出力するようなアルゴリズムを構成する問題を扱いました. しかし, 実際のweb広告などではuserやarmのcontextに報酬の確率分布のパラメータが依存すると考えるのが自然です. このようなcontextに依存するような問題設定を文脈付きバンディット問題などと呼びます. 文脈付きバンディット問題に関しては, 以前Qiitaに紹介記事を書きましたが, 理論解析には触れられていませんでした. 近いうちに本ブログで, 文脈付きバンディット問題の理論にも触れたいと思っています.

また毎度のことですが, 私の誤解で誤った記述をしてしまっている可能性が大いにあります. 誤りを見つけた場合はご指摘いただけると幸いです.

参考

[Jamison (2017)] Kevin Jamieson. Stochastic Multi-armed bandits, regret minimization. URL: https://courses.cs.washington.edu/courses/cse599i/18wi/resources/lecture3/lecture3.pdf
[Lai et al. (1985)] T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math., 6(1):4–22, March 1985.
[本多, 中村 (2016)] 本多淳也, 中村篤祥. バンディット問題の理論とアルゴリズム. 講談社 機械学習プロフェッショナルシリーズ, 2016.