この記事はJubatus Advent Calendar 8日目の記事です．

今日は多腕バンディット問題(Multi-Armed Bandit problem)と，この問題を解くためのjubatusのエンジン"jubabandit"について解説します．

多腕バンディット問題とは

多腕バンディット問題とは，報酬の期待値が未知の選択肢が複数与えられて，その中から1個の選択肢を選んでは報酬を観測，1個の選択肢を選んでは報酬を観測... という試行を繰り返して，得られる報酬を最大化する問題です．この時，選択しなかった選択肢についての情報を得ることができないのが特徴です．

あまりピンとこない方も多いと思うので，例を挙げて説明します．

今，スロットマシンが3台あるとします．
このスロットマシンはそれぞれ当たりを出す確率が設定されていて，当たりならコインを1枚, 外れなら何も出さないものとします．
このスロットマシンを好きな選び方で100回プレイ出来るとします．例えばAのスロットマシンだけを100回プレイしても良いですし，順番に1回ずつ回してAを34回，Bを33回，Cを33回というプレイの仕方でも良いです．この時，どういう戦略でスロットマシンをプレイしていけば一番多くコインの枚数を得られるでしょうか．

スロットマシンに設定されている確率が分かれば当たる確率の高いマシンだけを100回プレイすれば良いのですが，プレイヤーからは設定されている確率を直接知る方法はありません．したがって，何回かプレイして，その結果を見て，徐々に当たりやすいマシンにあたりをつけていきます．
プレイヤーは1度のプレイでスロットマシンを1つ選びます．そうすると選んだスロットマシンが当たったか外れたか，という情報が得られます．この情報を元にプレイヤーはスロットマシンについての情報を更新します．今の設定で言えば，何回プレイして何回当たりが出たかです．更新された情報を見て，プレイヤーは次に選ぶスロットマシンを決めます．このプレイを繰り返して最終的に得られるコインの枚数の最大化を目指します．この問題は多腕バンディット問題の1つと言えます．

今の例を，節の最初の文に当てはめると，報酬 = コインの枚数，選択肢 = スロットマシン，報酬の期待値 = スロットマシンが当たりを出す確率ということです．当たる確率が未知のスロットマシンが複数あって，その中から1個のスロットマシンを選んでは当たったかどうか観測する．という試行を繰り返して，得られるコインの枚数を最大化する．ちなみに，バンディット問題の文脈では選択肢のことを腕(arm)と言いますが，これはスロットマシンのレバーから来ているそうです．

多腕バンディット問題では知識の探索(explore)と活用(exploit)のトレードオフを解くのが目的となります．
知識とは各選択肢の情報のことを指し，上記の例ではスロットマシンを何回プレイして何回当たりが出たか，ということなどです．
知識が少ない選択肢はそれだけ情報が不確かなので，より情報を確実にするため積極的に選んだ方が良いこともあります．この，知識を獲得するために選択肢を選ぶのが知識の探索になります．
一方で，今ある知識に基づいて最良の選択肢を選んだ方が良いこともあります．この，現状最良だとわかっている選択肢を選ぶことが，知識の活用です．

情報が不確かなうちは探索が多い方が良いですが，探索ばかりしていると無駄な選択肢も選んでしまうことになります．しかし，探索が不十分なまま活用を続けると，間違った選択肢を選び続けてしまう恐れがあります．
多腕バンディット問題ではこのバランスをうまくとるために様々なアルゴリズムが開発されています．

jubabanditの紹介

前置きが長くなりましたが，jubatusに実装されているバンディットのエンジン"jubabandit"について解説していきます．このエンジンは 0.7.0で実装されました．現在実装されているアルゴリズムはepsilon-greedy, softmax, UCB1,Thompson sampling, Exp3の5種です．

jubabanditの使い方

まずはjubabanditの使い方を見ていきます．

サーバの起動

初めにjubabanditサーバを起動します．サーバの起動にはconfigファイルが必要となります．
jubabanditサーバに与えるconifgは下記のようなjsonです．

{
 "method": "epsilon_greedy",
 "parameter": {
    "assume_unrewarded" : false,
    "epsilon" : 0.3
  }
}

methodにはjubabanditで用いるアルゴリズムの名前を指定，parameterにはmethodに必要なパラメータ設定を書きます．assume_unrewardedはarmの情報を更新するタイミングを調整するパラメータですが，後述します．

$ jubabandit -f config.json

適当に動かしてみる

ここからはpythonのクライアントを使ってインタラクティブにjubabannditを操作してみます．
上記のようなスロットマシンを3台動かしているというストーリーで操作していきます．
なお，得られた報酬については適当に決めています．

$ python
>>> import jubatus
# まずはjubatusクライアントオブジェクトを作ります
>>> c = jubatus.Bandit("localhost", 9199, "bandit")
# 次にarm(=選択肢)をjubabanditサーバに登録していきます．
# ここではA, B, Cの3つのarmを登録します
>>> c.register_arm("A")
True
>>> c.register_arm("B")
True
>>> c.register_arm("C")
True
# jubabanditサーバに次はどのarmを選べば良いか聞きます．
# このとき誰に対してarmを選ぶかの指定が必要です．
# ここではplayer_1に対して選んでもらいます．
>>> c.select_arm("player_1")
'A'
# Aという結果が返ってきました．
# player_1はjubabanditの言うとおり，Aを選びました．
# しかし報酬は0でした．
# 得られた報酬をjubabanditに教えて，armの情報を更新します．
# 誰の，どのarmに報酬をいくら登録するか指定します．
>>> c.register_reward("player_1", "A", 0.0)
True
# 次にどのarmを選ぶべきか聞いてみます．
>>> c.select_arm("player_1")
'A'
# 再度Aを選んだものの報酬が0だったので，報酬をjubatusに登録します．
>>> c.register_reward("player_1", "A", 0.0)
True
# 次にどのarmを選ぶべきか聞いてみます．
>>> c.select_arm("player_1")
'C'
# 今度はCが返ってきました．
# Cを選んだところ，報酬が1得られました．
# この情報をjubabanditに登録します．
>>> c.register_reward("player_1", "C", 1.0)
True
# 次にどのarmを選ぶべきか聞いてみます．
>>> c.select_arm("player_1")
'C'
...
(中略)
...
# 最後にarmの状態をみてみましょう．
# trial_countがそのarmが選ばれた回数，weightが得られた報酬です．
>>> c.get_arm_info("player_1")
{'B': arm_info{trial_count: 5, weight: 1.0}, 'A': arm_info{trial_count: 9, weight: 2.0}, 'C': arm_info{trial_count: 20, weight: 8.0}}

assume_unrewarded オプションについて

サーバの設定項目の中でassume_unrewardedというパラメータがありました．これはarmが選ばれた回数(trial_count)をどのタイミングでインクリメントするかに関わるパラメータです．このオプションがfalseの場合，armの情報はupdate_rewardの発行時にのみ更新されます．

# A, Bの2つのarmが登録されているとする
>>> c.select_arm("player_1")
'A'
# この時のarm_info
# {'B': arm_info{trial_count: 0, weight: 0.0}, 
#  'A': arm_info{trial_count: 0, weight: 0.0}}

>>> c.select_arm("player_1")
'A'
# この時のarm_info
# {'B': arm_info{trial_count: 0, weight: 0.0}, 
#  'A': arm_info{trial_count: 0, weight: 0.0}}
>>> c.register_reward("player_1", "A", 1.0)
True
# この時のarm_info
# {'B': arm_info{trial_count: 0, weight: 0.0}, 
#  'A': arm_info{trial_count: 1, weight: 1.0}}
# register_rewardの発行で初めてtrial_count, weightが更新される

armの選択に対してすぐに報酬の有無が返ってきて，報酬の登録ができる場合や同じarmの状態で何度も選択を行いたい場合などはこちらの方が良いです．

assume_unrewarded オプションがTrueの場合armのtrial_countはselect_armの実行時にインクリメントされます．armの選択後，報酬が明に与えられない場合などに便利になります．

# A, Bの2つのarmが登録されているとする
>>> c.select_arm("player_1")
'A'
# この時のarm_info
# {'B': arm_info{trial_count: 0, weight: 0.0}, 
#  'A': arm_info{trial_count: 1, weight: 0.0}}
# Aのtrial_countが増えている

>>> c.select_arm("player_1")
'A'
# この時のarm_info
# {'B': arm_info{trial_count: 0, weight: 0.0}, 
#  'A': arm_info{trial_count: 2, weight: 0.0}}
# Aのtrial_countが増えている

>>> c.register_reward("player_1", "A", 1.0)
True
# この時のarm_info
# {'B': arm_info{trial_count: 0, weight: 0.0}, 
#  'A': arm_info{trial_count: 2, weight: 1.0}}
# Aのweightのみが増えている

なお，select_armの発行直後に報酬0を登録するようにすれば，このオプションとほぼ同等な機能は実現できます．

jubabanditに実装されているアルゴリズム

jubabanditに実装されているアルゴリズムを簡単に紹介していきます

epsilon-greedy

epsilon-greedyは最も単純なアルゴリズムです．このアルゴリズムでは確率$\epsilon$で全ての選択肢からランダムで1つの選択肢を選び，確率1 - $\epsilon$ で現在最も報酬の期待値が高い選択肢を選びます．

jubabanditでこのアルゴリズムを使う場合は，configを以下のように書きます．
epsilonがパラメータです．

{
 "method": "epsilon_greedy",
 "parameter": {
    "assume_unrewarded" : false,
    "epsilon" : 0.1
  }
}

softmax

softmaxはソフトマックス関数を使って，armの選択確率を決める方法です．
arm Aの選択確率は以下の式に従って決められます．

$$
p_{r_A} = \frac{e^\frac{r_A}{\tau}}{\sum_{k \in arm}e^\frac{r_k}{\tau}}
$$

$r_k$はarm kの現在の報酬の期待値，$\tau$はパラメータです．$\tau$が大きいほど，ランダムに近い動きをします．
jubabanditの設定ファイルは以下のようになります．

{
 "method": "softmax",
 "parameter": {
    "assume_unrewarded" : false,
    "tau" : 0.05
  }
}

UCB1

ucb1はUpper Confidence Bound (信頼上限という意味)を用いる方法です．この方法では，現在の期待値に加え，その推定値がどの程度信頼できるものなのか，を加味して選択するarmを決めます．以下の式で求められるスコアが最大となるarmを選択します．

$$
r_A + \sqrt\frac{2\ln{n}}{n_A}
$$

ここで$r_k$ はarm Aの期待値，$n_k$はarm Aが選択された回数，$n$はこれまでにarmの選択が行われた総数です．
第2項が信頼上限に相当します．式を見てわかる通り，これまでに選ばれた回数が少ないarmほど第2項が大きくなります．

jubabanditの設定ファイルは以下の通りです．ucb1には設定するパラメータがありません．

{
 "method": "ucb1",
 "parameter": {
    "assume_unrewarded" : false
  }
}

Thompson sampling

Thompson samplingはベイズ推定に基づいて，選択するarmを決定していく方法です．
この方法はjkomiyama さんにpull-reqを送っていただきました．
こちらに解説ブログもあります．

Thompson samplingでは，各armの事後確率に従って乱数を生成し，最大の乱数を生成したarmを選択します．
Jubatusに実装されているThompson samplingでは報酬がベルヌーイ分布(すなわち{0, 1}で与えられる)に従うとして，事前分布，事後分布にBeta分布を使っています．
下記の分布から乱数を生成しています．

$$
Be (\alpha_k + 1, \beta_k + 1)
$$

ここで$\alpha_k$はこれまでにarm kが得た報酬，$\beta_k$はarm kが選ばれたけど報酬を得られなかった回数です．

jubabanditのコンフィグは以下のようになります．Thompson samplingもパラメータ不要です．

{
 "method": "ts",
 "parameter": {
    "assume_unrewarded" : false
  }
}

Exp3

Exp3は多腕バンディット問題のうち，敵対的バンディット(adversarial bandit)用のアルゴリズムです．敵対的バンディットでは，こちらのarmの選択に応じて，相手が報酬の設定を変えてくることを想定します．

Exp3法では以下のようにarm Aが選ばれる確率を決めます．

$$
p_A = (1 - \gamma) \frac{w_A}{\sum_{k \in arm}w_k} + \frac{\gamma}{K}
$$

ここで，w_Aはarm Aの重み，$K$はarmの総数，$\gamma$はパラメータです．
重みの更新は以下のように行われます．


\bar{X} = \frac{X}{p_A} \\

w_{A} = w_A e^{\frac{\gamma \bar{X}}{K}}

ここでXはarm Aが得た報酬です．Exp3の重みの更新では報酬の推定量$\bar{X}$ を求めています．このため，選ばれる確率が低いarmほど高い報酬が得られるような仕組みになっています．

jubabanditの設定ファイルは以下のようになります．パラメータgammaを設定する必要があります．

{
 "method": "exp3",
 "parameter": {
    "assume_unrewarded" : false,
    "gamma": 0.1
  }
}

おわりに

本記事では多腕バンディット問題とjubabanditについて解説しました．
あまり実行例には触れていませんが，jubatus-exampleに例があったり，カジュアルトークで扱ったりしていますので，そちらも合わせてご覧いただければと思います．
さて，明日は誰が何を書いてくれるか非常に楽しみです．