最近、A/B testingの文脈で出て来るBandit algorithmsのまとめ。

Bandit Algorithms

Bandit Algorithmsは、

①機械学習の中の ②強化学習の中の ③n腕バンディット問題に対する④Algorithm。

①機械学習
- 人間の学習行為を自動化して実現する方法の事。
②強化学習
- 現在の状態を参考にして、行動を決定する方法の事。
③n腕バンディット問題(Multi Armed Bandit Problem)
- 複数のスロットマシンが有った時、利益を最大化するにはどうしたら良いか？という問題
④bandit algorithm
- 既存の状態の観測結果を「活用」して最適な選択をしつつ、（強化学習的な所）
- 一方で、新しい観測結果を導くために「探求」をする（ここがbanditに特有な所）

例

具体的に言うと、例えば、スロットマシンの前でコインを投げて、

表が出たら、過去の経験から、
- 今迄最大の報酬が出たスロットマシンを使う。(これが「活用」)
裏が出たら、今後より多くの報酬を得れるか確かめるために、
- 複数のスロットマシンから、適当にスロットマシンを選ぶ。（これが「探求」）

※これは後述のEpsilon-Greedyアルゴリズムの例。他にも幾つか考え方がある。

活用と探求

なぜ、探求が必要なのか？

今、回してるスロットマシンより、もっと沢山報酬を得られる可能性の高い

別のスロットマシンがあるかもしれないから。

利用のシチュエーション

よく、A/B testingに埋め込まれて使われる。

普通のA/B testingをrandomにAとBを出す実験だとすると、

それと比べて、Bandit Algorithmsは、

実験（探求）をして結果を取りながら、
既知の情報を「活用している」所が違っていて、

A/B testingより優れているとされる。

(要するに、途中で明らかにAが優れてる事が分かったらAばっかり出す所が良い。)

※ちなみに、今年('13)の6月頃に出てきたGoogleのContentExperimentAPIでもbandit algorithms使えるらしい。

情報源

書籍
- オライリー本が翻訳された。
blog
- qiitaの良記事

用語について

ここから、algorithmについて概説していくが、基本用語を整理する。

腕(arm)
- 選択肢の事。それぞれ、何回選択されたか？カウントを取る
報酬(reward)
- ある腕が選択された時に与えられる指標

algorithmについて

オライリー本を読むと、代表的な３種類のalgorithmsが書かれている

Epsilon-Greedy
softmax
UCB1

幾つか共通点があるので、先に概説。

共通点

arm選択メソッド(select_arm)

複数の選択肢から1つ選択する

この中身のロジックは、それぞれ違う。

パラメータが要るもの(Epsilon-Greedy/softmax)と要らない物(UCB1)がある。

報酬を更新するメソッド(update)

これは共通。

毎回、報酬の累計を積み上げて行く。

なので、image的には、ある腕を選択した回数をnとすると、


累計の報酬＝過去(n-1回目)の報酬＋新しい(n回目)の報酬。

※あくまで式のイメージ

ただ、このままだと、累計の報酬がふくれあがるので、n回の回数で割って平均を出す。


報酬の累計の平均 ＝ ( ( ( n - 1) / n ) * 過去の報酬の累計の平均) + ( (1 / n) * 今の報酬 )

Epsilion-Greedyアルゴリズム

Greedy＝貪欲に、現地点で最適な行動を選択する＝＞活用
一方でEpsilionの確率で多くの選択肢からrandomに選択する＝＞探求

BanditBookのgithubサイトにsampleコードがあるのだが、

日本人皆大好きなruby！版が色々おかしいので、直した。

（多分、書くだけ書いて、実行されてなかったっぽい。整理したら、pull req出しておきます！）

# -*- coding:utf-8
class EpsilonGreedy
  def initialize(e, n_arms)
    @epsilon = e
    @counts = Array.new(n_arms, 0)
    @values = Array.new(n_arms, 0.0)
  end

  def reset(n_arms)
    @counts = Array.new(n_arms, 0)
    @values = Array.new(n_arms, 0.0)
  end

  def select_arm
    if rand() > @epsilon
      @values.index(@values.max)
    else
      rand(@values.size)
    end
  end

  def update(chosen_arm, reward)
    n = @counts[chosen_arm] += 1
    value = @values[chosen_arm]
    if n == 0
      @values[chosen_arm] = reward
    else
      new_value = ((n - 1) / n.to_f) * value + (1 / n.to_f) * reward
      @values[chosen_arm] = new_value
    end
    return
  end
end

この使い方もちょっと面倒くさいのだが、rewardを準備して上げる必要がある。

ベルヌーリ腕というのを使うとこんな感じ。

class BernoulliArm
  def initialize(p)
    @p = p
  end

  def draw
    if rand() > @p
      0.0
    else
      1.0
    end
  end
end

arm = BernoulliArm.new(0.2) # 0.2の確率で1のrewardを与える

epsilon = 0.1
n_arms = 3
e = EpsilonGreedy.new(epsilon, n_arms)
10000.times do
  selected = e.select_arm
  reward = arm.draw()
  e.update(selected, reward)
end

puts "腕が選択された回数 " + e.instance_variable_get(:@counts).to_s
puts "報酬の累計の平均 " + e.instance_variable_get(:@values).to_s

これを実行すると、３本の腕の選択された回数と報酬の累計の平均が出て来る。

基本はこういう形。

他のアルゴリズムは、initializeのパラメータと、select_armのロジックが違う。

後で、残り２つのアルゴリズムもrubyソース付きで追記しておく。とりあえずここまで。

lxyuma BLOG

開発関係のメモ

Bandit algorithmsのまとめ