バンディットアルゴリズムをライトに解説

f:id:takarotoooooo:20201214110014p:plain

こんにちは！ dely開発部の高松です。

この記事は「dely #1 Advent Calendar 2020」の16日目の記事です。

昨日はクラシルのUIデザイナーをされているymdskoさんの「UIデザイナーとして働く私が就活生に戻ったら絶対やること5つ」でした。是非こちらもご覧ください。

「dely #1 Advent Calendar 2020」 adventar.org

「dely #2 Advent Calendar 2020」もありますので、是非そちらもご覧ください。 adventar.org

さて、いきなりですが質問です。

目の前にそれぞれ決められた一定の確率で報酬を得ることができるボタンが4つあります。合計で1000回ボタンを押して、4つの内どれが一番当たる確率が高いボタンかを検証してみてください。
なお、1000回ボタンを押したことで得た報酬は全て差し上げます。

さあ、どうしましょう。

4つ全てのボタンを250回ずつ押して、一番当たりの多いボタンを探しますか？

きっと一番当たる確率が高いボタンは見つかりますが、その分確率の低いボタンもたくさん押しているので、実はもっと多くの報酬が得られたかもしれません。

では、それぞれ100回ずつ押してみて、その時点で一番当たりが多かったボタンを残りの600回押しますか？

100回押した時点で一番当たる確率が高いボタンが本当に一番当たる確率が高いボタンなのでしょうか。

このように、最適な選択肢を探しつつ、その間に得られる報酬を最大にする決定問題をバンディット問題と呼び、この問題に対するアルゴリズムが今回紹介するバンディットアルゴリズムです。

実際どのように選択をするのか

今回はバンディットアルゴリズムのUCB(Upper Confidence Bound)という方策をご紹介します。

UCB方策は、期待値の高い選択肢を選ぶ一方で、それまで施行数が少ない選択肢を優先的に選択されるようにする方策です。

具体的には下記の数式にて算出される値が一番大きい選択肢を逐次選んでいきます。

$\mu + \sqrt{ \dfrac{2\times{\log{N}}}{n} }$

記号	意味
$\mu$	選択肢の期待値
$N$	全選択肢の選択回数の合計
$n$	その選択肢の選択回数

期待値というのはその選択肢を1回選ぶことでどれくらいの報酬が得られるかを表した値です。今回の例で言えば、その時点でより当たりが出ているボタンほど期待値が高いということになります。

各選択肢の期待値に下記の補正項が上乗せされています。

$\sqrt{ \dfrac{2\times{\log{N}}}{n} }$

上の式は、総選択数 N に対して、選択数 n が少ない選択肢ほど値が高くなるようになっています。
この補正項のおかげで、他の選択肢に対して検証ができていない選択肢が優先的に選ばれることになります。

検証してみる

今回は、全ての選択肢を同じ回数施行するいわゆるA/Bテストを行った場合とUCB方策のバンディットアルゴリズムを用いて施行を行った場合を比較します。

class Arm
  attr_accessor :name              # 選択肢名
  attr_accessor :num_of_run        # 施行回数
  attr_accessor :num_of_conversion # 報酬獲得回数
  attr_accessor :unit_reward       # 1回分の報酬（今回は固定で1）
  attr_accessor :probability       # 報酬が得られる確率

  def initialize(
    name, 
    unit_reward: 1, 
    probability: 1.0, 
    num_of_run: 1, 
    num_of_conversion: 0
  )
    @name = name
    @num_of_run = num_of_run
    @num_of_conversion = num_of_conversion
    @unit_reward = unit_reward
    @probability = probability
  end

  def run!
    self.num_of_run += 1
    return false unless (1..100).to_a.sample(probability * 100).include?(1)

    self.num_of_conversion += 1
    return true
  end

  def total_reward
    unit_reward * num_of_conversion
  end

  def expectation
    total_reward / num_of_run.to_f
  end

  def ucb_weight(total_num_of_run)
    Math.sqrt(
      (2 * Math.log(total_num_of_run)) / num_of_run.to_f
    )
  end

  def upper_confidence_bounce(total_num_of_run)
    expectation + ucb_weight(total_num_of_run)
  end
end

class ArmSelector
  attr_accessor :arms        # 選択肢Armの配列
  attr_accessor :select_type # 選択方法

  def initialize(arms, select_type: 'ab')
    @arms = arms
    @select_type = select_type
  end
  def select
    case select_type
    when 'ab'
      return arms.sort_by { |arm| arm.num_of_run }.first
    when 'ucb'
      unverified_arm = arms.find { |arm| arm.num_of_run == 0 }
      return unverified_arm if unverified_arm
      total_num_of_run = arms.map(&:num_of_run).sum
      sorted_arms = arms.sort_by do |arm|
        arm.upper_confidence_bounce(total_num_of_run)
      end
      sorted_arms.last
    end
  end
end

上記のコードを基に逐次選択される過程を表したのが下記です。

今回は説明を簡単にするために、a, b, c, dの選択肢はそれぞれ一定の確率で当たり（当たりなら1、ハズレなら0）が出るような形とし、 a < b < c < d の順で確率が大きいとします。

左が全ての選択肢を同じ回数施行した際の検証です。
右が上でご紹介したUCB方策のバンディットアルゴリズムを用いた検証です。

グラフの紫のバーが施行回数、緑のバーが報酬を得た回数、黄色の点がその時点の選択肢の期待値を表しています。

左は全ての選択肢を同じ回数施行するので、確率に基づいて選択肢「d」の報酬を得た回数が一番大きくなっているのがわかります。

一方バンディットアルゴリズムの方は選択肢毎に施行回数が違っています。
施行を始めたばかりは、期待値にばらつきが出るので全ての選択肢を満遍なく施行しますが、ある程度施行を重ねると選択肢「d」が多く選択されていくのがわかります。
また、一番期待値の低いと思われる選択肢「a」に対しても、完全に施行されなくなるわけではなく、頻度は少なくなるものの施行が続いていることもわかります。

そして、同じ試行回数で報酬を得られた回数を比較するとバンディットアルゴリズムの方がより多く報酬を得られました。

このように、バンディットアルゴリズムを用いることでより多くの報酬を得ることを確認できました。

まとめ

バンディットアルゴリズムは、選択を続け報酬を得るプロセスに於いてその報酬の合計を最大にするためのアルゴリズムです。
今回比較にも利用したA/Bテストと呼ばれる「最適椀識別」のように特定の選択肢を見つけることが主の目的ではありません。

今回は時間が足りず紹介出来ませんでしたが、バンディットアルゴリズムにて最適な選択肢を誤識別する様なシチュエーションも存在します。

また、今回はUCB方策を例に取りご紹介しましたが、他にも様々な選択方法が存在します。
こちらもまた時間があれば紹介できればと思います。

今回のこの記事が少しでもバンディットアルゴリズムの理解の助けになると嬉しいです。

さいごに

dely ではエンジニアを絶賛募集中です！ご興味ある方はこちらのリンクからお気軽にエントリーください！

join-us.dely.jp

さらに、定期的に TechTalk というイベントを通じて、クラシルで利用している技術や開発手法、組織に関する情報も発信しております。
ノウハウの共有だけでなく、クラシルで働くエンジニアがどんな想いを持って働いているのかや、働く人の雰囲気を感じていただけるイベントになっていますので、ぜひお気軽にご参加ください！

bethesun.connpass.com