はじめに
活用と探索をいい具合にバランスしつつ, 報酬を最大化することを目標とする多腕バンディット問題は, web広告の最適化などへの応用が期待されることから大きな注目を集めています. この分野に関してはこれまでにいくつかの素晴らしい記事が存在しますが, その理論解析に踏み込んだものはありませんでした. 本記事では, 有名なアルゴリズムを例にして, バンディットアルゴリズムの理論解析の雰囲気をさらってみます.
目次
定式化
まずは(確率的)多腕バンディット問題を定式化します. 定式化に関しては, こちらの記事で非常にわかりやすくまとめられているため, ここでは簡単に記述します.
多腕バンディット問題では, playerに対してarmと呼ばれるいくつかの行動の選択肢が与えられます. 各armは報酬と呼ばれる未知の確率分布に従う確率変数と対応付けられています. playerは, 各時刻にいずれかのarmを選択してそのarmに紐づく報酬の実現値を観測します. このような試行を繰り返すうちに, 各armの報酬が従う確率分布のパラメータを推定(探索)しながら, 同時に得られる報酬を最大化すること(活用)がplayerの目標です.
今, armの集合をとし, ある時刻にあるarm から観測される報酬は, 区間に値をとる確率変数に独立に従うとします. また, arm を選択することで得られる期待報酬を と表記します.
このとき, 多腕バンディット問題では次のように定義される期待累積リグレット(以降, リグレット)を考えます.
ここで, 総試行回数を, 時刻において選択されるarmを, 最適なarmとの期待報酬のgapを, 全ての試行が終了した時点においてarm を選択した回数をとしました. リグレットは, 最適な固定戦略 を取ることで得られる期待累積報酬と playerの取る戦略 によって得られる期待累積報酬の差の合計だと解釈できます. これは, 達成し得た最大の報酬からの後悔の量と言えるのでリグレットと名付けられています.
playerはリグレットを最小化することを目指します. また, armの選択を出力するアルゴリズム (player) が達成するリグレットの上界を導出することが主要な理論的興味になります. ちなみにLai et al. (1985)によると, 期待リグレットの理論限界はであることが知られており, アルゴリズムにはこの理論限界を達成していて欲しいということになります.
Upper Confidence Boundアルゴリズム
多腕バンディット問題の中でとてもよく知られたアルゴリズムに, Upper Confidence Bound (UCB) アルゴリズムというものがあります. これは, ある時刻においてそれまでに観測された報酬によって推定される期待報酬の上側信頼区間が最大になるarmを選択するアルゴリズムになります. 上側信頼区間を推定する際の有意水準は時刻に対して程度に設定されることが多いので今回はそれに従います.
期待報酬の上側信頼区間が最大になるarmを選択するという方針の解釈は決して難しくないと思いますが, 具体的なアルゴリズムはどのように構成すれば良いのでしょうか? 実は, 以前の記事で紹介したHoeffding's ineqを活用することでこの方針を実現するアルゴリズムを導くことができます.
ここで, 時刻の試行が終了した時点においてarm を選択した回数をとして, 時刻における選択前までの観測報酬を用いて各armの期待報酬の推定量を次のように構築します. と言っても, ただ観測報酬を平均しているだけです.
この推定量が真の期待報酬を大きく過小評価してしまう確率はHoeffding's ineqを用いて次のように評価できます.
右辺をとおいて変形を加えると,
よって, Hoeffding's ineqを用いることにより各armの有意水準がでの上側信頼区間の上界を得ることができました.
これに従い, UCBアルゴリズムは次のように定義されるUCBスコアが最大になるようなarmを各時刻において選択するようなアルゴリズムになっています.
擬似コードは次の通りです.
リグレット上界の導出
さて, 本章では前章で紹介したUCBアルゴリズムが達成するリグレットの上界を導きます. しかしここでは, UCBアルゴリズムが理論限界を達成することを示すため簡易なリグレット上界の導出を採用します.
以降一般性を失うことなく, であるとします. armの期待報酬の推定が大きく外れる場合とそうでない場合に場合分けする方針をとります. まず, 次の2つの事象とを考えます.
- :
- :
つまり, は時刻におけるあるarmの期待報酬の推定がそこまで大きくならないという事象のこと.
は時刻における最適なarmの期待報酬の推定がそこまで小さくならないという事象のことです.
まず, の補事象が起こる確率を評価します.
同様に, です. よってunion boundを用いれば,
です.
次に, 事象が共に成り立つ場合を考えます. まず, 最適ではないarmが選択されるのは, 次の不等式が成り立つ場合です.
今, 事象が成り立っているので, 両辺にを足せば,
です. これを用いれば,
です. について整理すると,
を得ます. 最終的には,
よって,
というリグレットの上界が導かれます.
これによりUCBアルゴリズムのリグレット上界は悪くてものオーダーです.
Lai et al. (1985)における理論限界はでしたので, 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.