Multi-Armed Bandit 問題のテスト

#!/usr/bin/ruby
# -*- coding: utf-8 -*-

include Math

# 勝率
def win_ratio(test, win)        # 試行回数, 勝利回数
  return (test > 0) ? (1.0 * win / test) : 0
end

# UCB1 (Upper Confidence Bound) の計算
#       test:   そのマシンのテスト回数
#       win:    そのうちの勝った回数
#       total:  総試行回数
def calc_ucb1(test, win, total)
  if total == 0 # まだ１つもテストしてない
    return 0
  else
    c = 1       # 期待値の値域によって決まる定数
    if test > 0
      per = win_ratio(test, win)
      return per + c * sqrt(2 * log(total) / test)
    else
      return c * sqrt(2 * log(total) * 1000)    # てきとうにでかい値を掛けておく
    end
  end
end


class Array
  # 配列中の最大値のインデクスを返す
  def max_idx
    n = self.size
    maxi = maxv = nil
    (0...n).each do |i|
      if !maxv || maxv < self[i]
        maxi = i
        maxv = self[i]
      end
    end
    return maxi
  end
end


# それぞれの手を選んだときに勝つ確率（テスト用データ）
Tbl = [0.30, 0.31, 0.29, 0.32, 0.28]

# テスト回数
N = 1000

# プレイアウト（ランダムの手でゲームを進めて勝敗をつける）
def playout(hand)
  # ここではテストで、乱数で決定
  rand < Tbl[hand]
end


# それぞれの手の試行回数、勝利回数
test_data = Tbl.map{ [0, 0] }

# モンテカルロ木探索
N.times do |n|
  ucb1s = test_data.map{|test, win| calc_ucb1(test, win, n)}

  # UCB1 が一番大きな手を選択
  hand = ucb1s.max_idx

  # その手でプレイアウトさせて勝ったかどうかを調べる
  win = playout(hand)

  test_data[hand][0] += 1               # その手の試行回数 +1
  if win
    test_data[hand][1] += 1             # その手の勝利回数 +1
  end
  puts %!hand #{hand}: #{win ? "WIN!" : "lose"}, #{test_data[hand][1]}/#{test_data[hand][0]}!
end

# 勝率が高い順に並べる
order = (0...test_data.size).sort_by {|i| -win_ratio(test_data[i][0], test_data[i][1])}

puts "\n**** Result ****"
order.each do |i|
  test = test_data[i][0]
  win = test_data[i][1]
  printf("hand #{i}: %4d/%4d (%f)\n", win, test, 1.0 * win / test)
end