LoginSignup
8
0

More than 1 year has passed since last update.

株式会社エイアイ・フィールドAdvent Calendar 2021Day 20aifield
@takuyakubo(久保 卓也)in株式会社エイアイ・フィールド

それで、結局どの方法がよいの？（多腕バンディット問題のアルゴリズム比較）

Last updated at Posted at 2021-12-19

はじめに

こんにちは。株式会社エイアイ・フィールドでプロダクト開発をしている久保です。この記事はエイアイ・フィールドアドベントカレンダー2021の20日目の記事です。今までこのアドベントカレンダーで多腕バンディット問題のアルゴリズムの紹介を行ってきました。

今回はこれらのアルゴリズムの比較を行います。今回の実験状況下ではありますが、結果をまとめると

  1. 実装時間があまりなく、コインの枚数も少ない時はepsilon greedy
  2. 無難に行くのであれば、UCB1
  3. コインの枚数が多く、少しでも改善をしたいのであれば、DMED

になります。

問題設定

初回に問題設定を行いましたが、せっかくなのでもう一度問題設定を行います。

今、あなたはカジノに来ています。このカジノでは専用のコインを買い、そのコインをつかってスロットマシンで遊びます。スロットマシンからは当たれば現金が1万円出てくるものとします。（スロットマシンから出たコインではスロットマシンは起動できないものとします）。

さて、さっそくあなたはコインを100枚入手しました。

coin_case.png

このコインをつかって、スロットマシンに挑みます。このカジノには3台のスロットマシンがあり、それぞれ当たる確率が異なることがわかっています。

slot.pngslot.pngslot.png

さて、どのようにプレーをすれば最終的な獲得金額を最大化できるでしょうか？

実験概要

この問題について、数値実験を用いて検証を行いますが、実験をするに際して、「それぞれのスロットマシンはベルヌーイ過程に従い、それぞれのスロットマシンの期待値は、0.3, 0.5, 0.8とします。」

これらは実験をするのに必要であり今回設定を行いますが、実際にプレーするときプレーヤーはこのことを知りようがないということに注意が必要です。

統計学の議論ではしばしばこのような、実験する主体には実験前には（あるいは実験後であっても）知りようのないことを設定することを求められます。この種の設定はよくモデルと呼ばれますが、私は個人的にこの知りようのないことを実験者(人間)の視点と対比して神様視点と呼びます。

job_tantei_woman.pngkamisama.png

設定している数値が人間視点なのか神様視点なのかを常に考えることが大事です。今回で言うと、実験結果やスロットマシンが3台あること、コインが100枚あることが人間視点で、スロットマシンがベルヌーイ過程に従い、それぞれの期待値が0.3, 0.5, 0.8であることが神様視点です1。

これらの設定の下、コインの枚数を増やしながらどのように値が変化するかを調べました。
以下、実験に使ったコードです。

import random
import math
import pandas as pd

# divergenceの計算
def b_divergence(p, q):
  if q == 0:
    if p == 0:
      return 0
    return 100_000_000
  if q == 1:
    if p == 1:
      return 0
    return 100_000_000
  if p == 0:
    return - math.log(1-q)
  if p == 1:
    return - math.log(q)
  return p * math.log(p/q) + (1-p) *  math.log((1-p)/(1 - q))

# 場の準備
class PlayBoard:
  def __init__(self, machines=[], n_machines=3, n_coins=100):
    if machines == []:
      self.reset_machines(n_machines)
    else:
      self.set_machines(machines)
    self.reset_history(n_coins)

  def reset_machines(self, n_machines):
    self.n_machines = n_machines
    self.machine_mu =  [random.random() for _ in range(self.n_machines)]

  def set_machines(self, machine_mu):
    self.n_machines = len(machine_mu)
    self.machine_mu = machine_mu

  def reset_history(self, n_coins):
    self.n_coins = n_coins
    self.reward = 0
    self.score_board = ScoreBoard(len(self.machine_mu))
    self.history = []

  def play(self, arm, detail=True, hist_=True):
    if self.n_coins < 1:
      return
    self.n_coins -= 1
    reward = int( random.random() < self.machine_mu[arm])
    self.record(arm, reward, detail=detail, hist_=hist_)
    return self.n_coins == 0

  def record(self, arm, reward, detail=True, hist_=True):
    self.reward += reward
    if detail:
      self.score_board.count += 1
      score = self.score_board.get_score(arm)
      score.n_tries += 1
      score.reward += reward
      if hist_:
        self.history.append({'count': self.score_board.count, 'reward': self.reward})

class Score:
  def __init__(self, arm):
    self.arm = arm
    self.n_tries = 0
    self.reward = 0

  def get_ucb_score(self, count):
    if self.n_tries == 0:
      return 100_000_000
    return self.reward / self.n_tries + math.sqrt(math.log(count) / 2 / self.n_tries)

  def get_mu_hat(self):
    if self.n_tries == 0:
      return 100_000_000
    return self.reward / self.n_tries

class ScoreBoard:
  def __init__(self, n_scores):
    self.scores = [Score(arm) for arm in range(n_scores)]
    self.count = 0

  def get_score(self, arm):
    return self.scores[arm]

  def select_arm_by(self, scoring):
    if scoring == 'ucb':
      res_ = [
              {'arm': score.arm, 'score': score.get_ucb_score(self.count)}
              for score in self.scores
              ]
    elif scoring == 'mu_hat':
      res_ = [
              {'arm': score.arm, 'score':score.get_mu_hat()}
              for score in self.scores
              ]
    max_arm = max(res_, key=lambda x: x['score'])
    return max_arm['arm']

  def get_max_mu_hat(self):
    return max([score.get_mu_hat() for score in self.scores])

  def judge_dmed(self, arm):
    score = self.get_score(arm)
    return score.n_tries * b_divergence(score.get_mu_hat(), self.get_max_mu_hat()) <= math.log(self.count)

# アルゴリズムたち
def epsilon_greedy(pb, eps = 0.3):
  n_exploration = int(eps * pb.n_coins)
  n_exploitation = pb.n_coins - n_exploration
  for idx in range(n_exploration):
    pb.play(idx % pb.n_machines, hist_=False)
  max_arm =pb.score_board.select_arm_by('mu_hat')
  for _ in range(n_exploitation):
    pb.play(max_arm, detail=False)
  return pb.reward

def ucb1(pb):
  n_coins = pb.n_coins
  ended = False
  for arm in range(pb.n_machines):
     ended = pb.play(arm)
     if ended:
      break
  while not ended:
    arm_ = pb.score_board.select_arm_by('ucb')
    ended = pb.play(arm_)
  return pb.reward

def dmed(pb):
  n_coins = pb.n_coins
  ended = False
  for arm in range(pb.n_machines):
     ended = pb.play(arm)
     if ended:
      break
  this_loop = [arm for arm in range(pb.n_machines)]
  next_loop = []

  while not ended:
    for arm in this_loop:
      ended = pb.play(arm)
      if ended:
        break
      for arm_ in range(pb.n_machines):
        if arm_ in next_loop:
          continue
        if pb.score_board.judge_dmed(arm_):
          next_loop.append(arm_)
    this_loop = next_loop
    next_loop = []
  return pb.reward

# 実験コード
def exam(method, n_tries=100, n_coins=100):
  result = None
  for idx in range(n_tries):
    pb.reset_history(n_coins)
    method(pb)
    if result is None:
      result = pd.DataFrame(pb.history)
    else:
      result = pd.concat([result, pd.DataFrame(pb.history)])
  return result

def exam_eg(eps=0.3, n_tries=100, n_coins=100):
  res_ = []
  for idx in range(n_tries):
    print(idx)
    for jdx in range(n_coins):
      pb.reset_history(jdx)
      res = epsilon_greedy(pb, eps=eps)
      res_.append({'count': jdx, 'reward': res})
  return pd.DataFrame(res_)

実験結果

まず、場を準備し次のコードを実行しました。

pb = PlayBoard([0.3, 0.5, 0.8])
n_tries = 300
n_coins = 5000
df_eg = exam(epsilon_greedy, n_tries=n_tries, n_coins=n_coins)
ax_1 = df_eg.plot.scatter(x='count', y='reward', s=0.1, figsize=(30, 16), label='epsilon greedy')
df_ucb = exam(ucb1, n_tries=n_tries, n_coins=n_coins)
df_ucb.plot.scatter(x='count', y='reward', s=0.1, c='orange', figsize=(30, 16), ax=ax_1, label='ucb1')
df_dmed = exam(dmed, n_tries=n_tries, n_coins=n_coins)
df_dmed.plot.scatter(x='count', y='reward',  s=0.1, c='green', figsize=(30, 16), ax=ax_1, label='dmed')

download.png

これは、コインを5000回使ったときの報酬の増加を表しています。それぞれのアルゴリズムを300回ずつ行いそれを表示してあります。epsilon greedy が青色、UCB1 がオレンジ色、DMED が緑色です。見てわかる通り、オレンジが見えません。これは緑色がオレンジ色と同じような動きをして上書きをしているからです。また、epsilon greedyが下回っているのがわかります。
しかし、ここで少し考えると、epsilon greedyは全体の何割かを先に探索に充てるので、この図による比較はフェアではないことがわかります。例えば、コインが100枚だった時、UCBやDMEDはこの図の通りに読めばよいのですが、epsilon greedyはこの図の中では探索中であり、この通りに読んではいけません。この点も踏まえて比較できるように、次のコードを実行しました。

df_eg_2 = exam_eg(n_tries=n_tries, n_coins=n_coins)
ax_1 = df_eg_2.plot.scatter(x='count', y='reward', s=0.1, figsize=(30, 16), label='epsilon greedy')
df_ucb.plot.scatter(x='count', y='reward', s=0.1, c='orange', figsize=(30, 16), ax=ax_1, label='ucb1')
df_dmed.plot.scatter(x='count', y='reward',  s=0.1, c='green', figsize=(30, 16), ax=ax_1, label='dmed')

注意 このコードをGoogle Colab上で実行すると80分程度かかります。

download.png

結果はこのようになりました。この図ではわかりにくいので、ヒストグラムでコインが100, 200, 400, 800, 1600, 3200, 4999枚の時をプロットしてみましょう。
コードは以下の通りです。

import matplotlib.pyplot as plt
data = []
for count_point in [100, 200, 400, 800, 1600, 3200, 4999]:
  ax_2=df_eg_2.query('count == @count_point').reward.hist(alpha=.5)
  df_ucb.query('count == @count_point').reward.hist(alpha=.5, color='orange', ax=ax_2)
  df_dmed.query('count == @count_point').reward.hist(alpha=.5, color='green', ax=ax_2)
  ax_2.set_title(f'num. of coins = {count_point}')
  plt.show()
  ax_2.clear()
  data.append({
      'count': count_point,
      'esp_greed': df_eg_2.query('count == @count_point').reward.mean(),
      'ucb': df_ucb.query('count == @count_point').reward.mean(),
      'dmed': df_dmed.query('count == @count_point').reward.mean()
  })
df_mean = pd.DataFrame(data)

結果は次のようになりました。ここでもepsilon greedy が青色、UCB1 がオレンジ色、DMED が緑色です。

download.pngdownload.pngdownload.pngdownload.pngdownload.pngdownload.pngdownload.png

期待値もこのようになりました。

image.png

最初100枚のときはDMEDはepsilon greedyにも負けていたのが、最終的に3200枚のあたりでUCB1にも勝っていることがわかります。ここで、5000枚使った時の理想的な手を選び続けたときの平均値は0.8 * 5000 = 4000なので、epsilon greedyは約400、UCBは約22、DMEDは約18改善の余地があることがわかります。なかなかこれ以上の改善は難しいですが、試してみるのも面白いかもしれません（DMEDより良いといわれている手法にIMEDなどがあります）。
これらの結果から、今回の設定、つまり3つのスロットマシンでその平均値が0.3, 0.5, 0.8の状況では、

  1. 実装時間があまりなく、コインの枚数も少ない時はepsilon greedy
  2. 無難に行くのであれば、UCB1
  3. コインの枚数が多く、少しでも改善をしたいのであれば、DMED

となるのではないでしょうか。

おわりに

今回は多腕バンディット問題のアルゴリズムの比較を行いました。初回にも書いた通り、多腕バンディット問題はこのようなスロットマシンの問題だけでなく、もう少し問題を拡張することによって広告配信や推薦、囲碁などのゲーム木探索などにも応用されているます。また、問題の形式を少し変えることによって、デザインにおけるA/Bテストの世界ともつながっていきます。
日本語では本多さんの本がお勧めなのでぜひ読んでみてください。

これまで4回にわたる多腕バンディット問題の入門的な記事も今回で終わりです。ここまでお読みいただきありがとうございました。また機会があれば今度は線形バンディットやその応用である文脈付きバンディットについて書いてみたいと思います。それでは次の機会に。

  1. 「神様なら実験結果とかも含めて全部知っているだろう」と考えるのであれば、胴元視点と言ってもよいです。 ↩

8
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
0