強化学習について学んでみた。（その5）

昨日は、n本腕バンディット問題と、「知識利用」と「探査」のバランスの問題について説明した。

今日はn本腕バンディット問題をプログラム（Ruby）で実際に動かしてみる。

正規分布に従う乱数生成器

今回、n本腕バンディット問題のレバー $i \: (i=0, 1, \cdots , n-1)$ の期待値 $E_i$ 、および、レバーを選んだときに得られる報酬は、正規分布に従うとしていた。
けど、そもそも正規分布に従う乱数って、どうやって発生させるの？という話。
一様分布に従う乱数なら、ライブラリを使えば簡単に得られるけれど、正規分布に従う乱数となると、そうはいかなくなる。

ただ、これに関してはボックス＝ミュラー法という方法が知られているので、それを使えばいい。

#====================
# normal_dist_random.rb
#====================

# 正規分布に従った乱数を生成するクラス
class NormalDistRandom
  include Math

  @@random = Random.new

  # 期待値exp, 分散varの正規分布に従った乱数を生成する
  # 乱数生成器を作成する。
  def initialize(exp=0.0, var=1.0)
    @exp = exp
    @var = var
    @values = Array.new(0)
  end

  def get_random
    if @values.size == 0
      # ボックス＝ミュラー法で乱数を生成する
      
      # NOTE
      # Random#randは[0, 1)で値を返すので、
      # (0, 1]に変換する。
      a = 1.0 - @@random.rand
      b = 1.0 - @@random.rand

      z1 = sqrt(-2.0 * log(a)) * cos(2 * PI * b)
      z2 = sqrt(-2.0 * log(a)) * sin(2 * PI * b)

      rand1 = z1 * sqrt(@var) + @exp
      rand2 = z2 * sqrt(@var) + @exp

      @values.push(rand1, rand2)
    end

    return @values.shift
  end
end

n本腕バンディット

次は、n本腕バンディット。

#!/usr/bin/env ruby

#====================
# bandit.rb
#====================

require './normal_dist_random'

class Bandit

  # size: 腕の数
  # reward_exp_avg: 各行動に対する報酬の期待値の平均
  # reward_exp_var: 各行動に対する報酬の期待値の分散
  # reward_var: 各行動に対する報酬の分散
  def initialize(size=10, reward_exp_avg=0.0, reward_exp_var=1.0, reward_var=1.0)
    @size = size
    @rand_generator = Array.new(size, 0)
    @reward_exp = Array.new(size, 0)
    random = NormalDistRandom.new(reward_exp_avg, reward_exp_var)
    size.times do |i|
      reward_exp = random.get_random
      @reward_exp[i] = reward_exp
      @rand_generator[i] = NormalDistRandom.new(reward_exp, reward_var)
    end
  end

  def select(i)
    return @rand_generator[i].get_random
  end

  attr_reader :size, :reward_exp
end

if __FILE__ == $PROGRAM_NAME
  bandit = Bandit.new
  puts "input 0 - #{bandit.size - 1}, or 'q'"
  STDIN.each_line do |c|
    c.chomp!
    case c
    when /[0-9]+/
      puts bandit.select(c.to_i)
    when "q"
      break
    else
      puts "input 0 - #{bandit.size - 1}, or 'q'"
    end
  end
  puts "expected values"
  p bandit.reward_exp
end

これを実行してみると、以下のような感じになる。（※一部改行してある）

$ ./bandit.rb 
input 0 - 9, or 'q'
0
2.908154210870754
0
1.208474499319328
1
1.2987969333009353
2
-0.5757813842060623
3
1.9183866863176764
4
1.4566187515905054
5
-0.55736483571126
6
-0.17264161542423706
7
-0.23987545943307786
8
-0.8639772452265697
9
3.1811560620754022
9
0.6288023462566747
9
1.0495465934069081
3
0.9091850368908269
9
-0.1623391762409872
3
2.1615496118083235
q
expected values
[0.5443914514871356, 1.6051705341328175, -1.370395370227038,
 1.3716181487737478, 0.5654530490587235, -1.1137993320228443,
 -0.11661911804323546, -0.09831199416054974, 0.619652288298645,
 0.4914669743824948]

途中は9がいいのかなと思ったんだけど、急に雲行きが怪しくなったりと、なかなか簡単にはいかないことが分かるかと思う。
最後の正解を見てみると、1を選ぶのが最善だったわけだけど、それは試行錯誤していく中で見つけるしかないわけで。

今日はここまで！