UCB1アルゴリズムによるスロット選定

本記事では、UCB1アルゴリズムでスロットを選定する過程を実際に計算しながらアルゴリズムに対する理解を深めていきます。

マルチアームバンディット問題の戦略

機械学習で扱われる探索に関する問題にマルチアームバンディット問題(multi armed bandit problem)というものがあります。

以下のような設定です。

N個のスロットマシンがあり，スロット毎に異なる払い戻しの期待値が設定されている．
期待値が分からない状態で，ある枚数のコインを持っている場合、払い戻し額を最大にするにはどのスロットを選べばよいか

パッと思いつく戦略として以下のようなものがあります。

全てのスロットで一定枚数ずつコインを投下し、払い戻し額の期待値が高かったスロットに残りのコインを全て投入する

この戦略のポイントは、期待値が低いスロットにも調査のためとはいえ一定枚数投入する点です。
調査に時間をかければかけるほど期待値が低いスロットにコインが投入されていき、逆に中途半端な調査で期待値の低いスロットに当たりをつけてしまうと元も子もありません。

UCB1アルゴリズム

そのような際に各スロットの払い戻し額はある一定の確率分布に従っているという仮定に基づき、払い出し額を見ながらその時に最適であると予想されるスロットを選択するアルゴリズムにUCB1というものがあります。*1

i番目のスロットのUCB値を以下の式で計算し、このUCB値が最も大きいスロットにコインを投入します。
${ \displaystyle \bar{x}_i+\sqrt{\frac{2\log{n}}{n_i}} }$

一項目はこれまでにそのスロットから得られた払い戻し額の平均値を表し、二項目のniはそのスロットに既に投下されたコインの枚数、nは全体として投下されたコインの枚数となります。

これは　結果に対する期待値項　と　可能性に対する期待値項　という構造です。
前者は実際の払い戻し額が高ければ、後者は選ばれた回数が少なければ、高い値となります。

UCB1アルゴリズムによる選択過程

問題設定

今回は、A,B,C の３つのスロットの払い戻し額がポアソン分布に従うと仮定します。

平均値1.5のポアソン分布の乱数a

> a <- rpois(100,1.5)
> mean(a)
[1] 1.51
> a
  [1] 0 1 1 4 0 4 4 2 1 0 3 0 0 2 2 1 4 4 0 3 0 2 1 0 0 3 1 1 1 0 1 3 0 2 1 1 0 0 1 1 3 5 7 2 0
 [46] 1 1 1 2 1 1 2 1 0 2 1 0 2 0 0 0 1 3 3 3 3 0 1 1 1 0 2 0 5 2 2 3 1 0 3 1 3 2 2 2 1 2 1 1 2
 [91] 3 1 1 3 0 1 2 0 0 2

これはスロットAの1回目の払い戻しは0、2回目の払い戻しは1...といった意味です。

平均値2.0のポアソン分布の乱数b

> b <- rpois(100,2.0)
> mean(b)
[1] 2.03
> b
  [1] 3 0 0 1 2 4 0 2 0 3 4 1 2 4 1 0 0 2 4 4 0 2 0 1 4 1 3 2 2 1 0 1 2 1 2 1 4 1 0 1 3 2 1 4 3
 [46] 5 2 1 3 3 4 1 1 3 0 1 1 2 0 6 3 1 0 1 1 0 5 5 3 2 4 1 2 1 0 2 3 5 4 0 2 4 3 2 3 5 1 1 1 5
 [91] 1 1 3 1 3 3 2 4 1 2

平均値3.0のポアソン分布の乱数c

> c <- rpois(100,2.5)
> mean(c)
[1] 2.48
> c
  [1] 1 1 0 6 2 4 4 7 4 2 4 3 1 0 2 2 3 0 5 1 2 2 2 0 1 1 5 2 3 2 2 0 3 3 2 5 5 4 3 2 2 0 1 2 1
 [46] 4 0 4 2 3 4 2 1 3 3 3 3 4 1 3 1 0 2 1 6 1 1 3 2 2 6 3 5 3 4 3 1 1 0 3 1 1 2 5 2 2 1 3 1 5
 [91] 0 5 1 4 5 4 3 2 3 3

プロットすると以下のようになります。（赤：スロットA, 緑：スロットB, 青：スロットC）
平均的に見れば、スロットCを指す青色が高くスロットAを指す赤色が低いのですが、UCB1アルゴリズムではそれに対してどのように反応するのでしょうか。
f:id:mtiit:20190323212653p:plain

UCBアルゴリズム

初期状態として、まずはA,B,Cを一度ずつ試したとします。
実際、試行回数が0であればUCBは無限大となるのでこの初期状態となります。

n=3が終了後

それぞれのUCBを計算します。

> mean(a[1:1]) + sqrt(2*log(3)/1)
[1] 1.482304
> mean(b[1:1]) + sqrt(2*log(3)/1)
[1] 4.482304
> mean(c[1:1]) + sqrt(2*log(3)/1)
[1] 2.482304

一度目に最も大きな値が出たスロットBのUCB値が最大です。
よってn=4ではスロットBを選択します。

n=4が終了後

> mean(a[1:1]) + sqrt(2*log(4)/1)
[1] 1.665109
> mean(b[1:2]) + sqrt(2*log(4)/2)
[1] 2.67741
> mean(c[1:1]) + sqrt(2*log(4)/1)
[1] 2.665109

n=5でもスロットBを選択します。
ただし、選ばれなかったAとCのUCB値も、２項目の分母が小さいままなので値が大きくなっていることが分かります。

n=5が終了後

> mean(a[1:1]) + sqrt(2*log(5)/1)
[1] 1.794123
> mean(b[1:3]) + sqrt(2*log(5)/3)
[1] 2.035837
> mean(c[1:1]) + sqrt(2*log(5)/1)
[1] 2.794123

n=6ではスロットCを選択します。

順番にすると、ABCBBCと来ています。

これを100回繰り返した結果は以下となります。

> slot
  [1] "A" "B" "C" "B" "B" "C" "C" "B" "A" "B" "B" "B" "B" "B" "A" "B" "B" "B" "B" "B" "B" "B"
 [23] "B" "B" "B" "B" "B" "B" "B" "B" "B" "B" "B" "B" "B" "B" "B" "C" "C" "C" "C" "C" "C" "C"
 [45] "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C"
 [67] "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C"
 [89] "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C" "C"