tag:

Pythonでバンディットアルゴリズム

こんにちは。アイリッジ開発チームのカデナです。

最近、強化学習の勉強をはじめたので、その分野で有名な多腕バンディット問題を紹介していきたいと思います。

多腕バンディット問題

こんな状況を考えてみます。

・5枚のコインA, B, C, D, Eがある
・2000回コインを投げていっぱい表を出したい
・投げる度にコインを選んでよい
・それぞれのコインの表の出る確率は違うって噂
(ここではA, B, C, D, Eそれぞれの表の出る確率が異なっている可能性があって、その確率は誰も知らないとする)

上記のような問題を多腕バンディット問題(Multi-armed bandit problem)といいます。
この記事では、少し遠回りしながら、実装例も含めて説明していこうと思っています。

まずは、アルゴリズムを比較していくため、 データをつくっておきます。
(再現できるようにデータはつくっておきますが、結果は投げた後でしかわからないものとします。)
またプログラムでは簡単のため、コインA, B, C, D, Eそれぞれを0, 1, 2, 3, 4としました。

今回は、A, B, C, D, Eそれぞれの表の出る確率を0.3, 0.4, 0.5 ,0.6, 0.7として試行結果のデータをつくりました。
ずっとコインEを選ぶと、総報酬を最大化できる設定です。

手法1.Greedy Algorithm

バンディット問題に対するひとつの対抗手段としてGreedy Algorithmと呼ばれるものがあります。
名前はかっこいいですが、とても単純で、つぎの2条件からなるアルゴリズムです。

・最初に5枚全て投げて試してみる。
・それ以降は期待値が最も高いコインを選ぶ

実装例を以下に示しましょう。

 
各時点での表が出た割合を見てみます。

 

png

Greedy algorithmの結果が上のようになりました。
最初の段階でコインEの結果が良くなかったために、
コインDを投げ続けるという選択をとってしまっています。

Greedy algorithmの特徴

Greedy algorithmは次のような特徴をもっています。

・最初の段階で珍しいことが起こってしまうと、その後すべての行動に響いてしまう。
・報酬の分散がゼロであれば、効率的

強化学習とは

ちょっとここで強化学習の説明をいれておきます。
強化学習では試行錯誤しながら、総報酬を最大化することが目的です。そのために、基本的に2つのことを考えます。

知識の利用(exploitation)
現時点で、最も表がでそうなコインを投げる。

探索(exploration)
表ばっかりでる夢のコインを探す。そういうコインが見つかれば最終的には得するかもしれない。

強化学習ではトレードオフの関係にある利用と探索をうまいこと混ぜ合わせて、総報酬を最大化していきます。
先ほどの例では探索を十分に行わなかったため、2000回時点での表が出た割合が6割程度にとどまっています。
かといって探索をしすぎてもよくないところが多腕バンディット問題の難しさですね。

手法2. ε-Greedy algorithm

ε-Greedy algorithmはGreedy algorithmを改良したもので、永遠に、ある確率εで探索を続けていくようなアルゴリズムです。

・確率εで探索を行う(ランダムでコインを選ぶ)
・確率1-εで最も良いと思われるコインを選ぶ

Greedy algorithmはε=0のε-Greedy algorithmということになります。
Greedyクラスをもとにして確率εで探索をおこなうように変更してみます。

 
20141225_02

Greedy algorithmのときよりも良い結果が出てきました。(この場合はですが)

ε-Greedy algorithmの特徴

・報酬の分散が大きければ、より多くの探査が必要になるので、Greedy algorithmよりも良い性能を示す
・分散がゼロであれば、無駄な探査が少ない分、Greedy algorithmが良い性能を示す
・εが小さければ良いコインを見つけるのに時間がかかってしまう
・εが大きければ早く良いコインを見つけられるが、その後の探索が無駄になってしまう

手法3. Softmax Action Selection

ε-Greedy algorithmは探索を行う際にランダムにコインを選んでいました。
それに対して、ソフトマックス手法では良いと思われるコインを高確率で選択し、悪いと思われるコインを低確率で選択します。
このアルゴリズムでは温度と呼ばれる正定数tauを設定してすることにより、選択確率を調整していて、次の性質があります。

・温度が高ければ探索中心
・温度が低ければ活用中心

具体的にはGibbs分布と呼ばれる分布を用いて行動aの選択確率を次のように定めます。
exp(Q(a)/tau)/Z (ただし、Zはとりうる行動bについてのexp(Q(b)/tau)のsum)

これをふまえてまた実装してみます。

20141225_03

 
うまくtauを設定できたものはε-Greedy algorithmと同じような結果になっています。(この場合ですが)

Softmax Action Selectionの特徴

・tauの設定が難しい
・確信度が考慮されていない(ε-Greedy algorithmも同様)

まとめ

今回は3つのアルゴリズムを紹介しましたが、 この他にもUCB系アルゴリズムやcontextual banditとよばれる手法があります。 UCB系アルゴリズムでは確信度を考慮し、最適な期待報酬値に漸近していく手法です。
また、contextual banditは線形モデル等のモデルを加味して最適化していくそうなのですが、
僕はまだよくわかってません。

スマートフォン向けサービスを提供しているアイリッジでは、contextual banditについて造詣が深いかたを募集しています。

 
参考:
『強化学習』 著 Richard S.Sutton
強化学習をベイズで理解する

「O2Oまとめ」を運営するアイリッジは、GU、東急電鉄、トリンプなど、様々な企業様の公式アプリを企画・開発させていただいております。
アプリを通じた企業とユーザーとのコミュニケーションツールとして業種を問わず、幅広いシーンでご活用いただいておりますので、お気軽にお問い合わせください。

お電話でのお問い合わせ

TEl:03-6441-2325

営業時間: 平日10:00-19:00


                      

本記事に興味をお持ち頂き、ご質問等含めてディスカッションされたい法人様向けに、無料個別相談会を設けておりますのでお気軽にお申し込みください。

pageTop