昨日はn本腕バンディット問題の行動の価値について考えた。
今日は、それを使って具体的なアルゴリズムを考えていく。
グリーディ法
一番最初に思いつく方法は、現在の推定される行動の価値の中で、最も価値の高い行動を選ぶという方法。
すなわち、回目に選ぶ行動をとするとき、
とする。
(※については、添え字の扱いが本と1つズレていることに注意)
こういった方法を、グリーディ法(貪欲法)と呼ぶ。
グリーディ法
グリーディ法の場合、常に「今のところ一番良さげなレバー」しか選ばないので、つまり「知識利用」のみを行って、「探査」は行わないことになる。
それだと推定される行動の価値が改善されていかない可能性があるので、の確率で、ランダムに行動を選択するような方法も考えてみる。
このような方法を、グリーディ法と呼ぶ。
グリーディ法の方策(ポリシー)]は、次のように表されることになる:
Rubyによる実装
グリーディ法、および、グリーディ法をRubyで実装してみると、次のような感じ。
(※シンタックスハイライトを入れると、Markdownのパーサによっての表記が崩れるようなので、入れてない)
#==================== # greedy_method.rb #==================== class GreedyMethod @@random = Random.new # size: n本腕バンディット問題のサイズ # epsilon: グリーディではなくランダムに選択する確率 # stepsize: nil以外を指定した場合、ステップサイズとして扱う def initialize(size=10, epsilon=0.0, stepsize=nil) @size = size @epsilon = epsilon @stepsize = stepsize @times = Array.new(size, 0) @values = Array.new(size, 0.0) end # グリーディ法で腕を選ぶ。 # -- # epsilonの確率で、ランダムに選択を行う。 # そうでない場合、最も価値が高いと推定される行動を選ぶ。 def select if @@random.rand < @epsilon return @@random.rand(@size) else max_value = @values.max return @values.find_index(max_value) end end # 得られた報酬を反映し、学習する。 # -- # selected: 選んだ腕 # value: 得られた報酬 def reflect(selected, value) @times[selected] += 1 stepsize = @stepsize ? @stepsize : (1.0 / @times[selected]) @values[selected] += stepsize * (value - @values[selected]) end attr_reader :size, :epsilon, :values end
それと、何度も繰り返して実行するために、以下のコードを用意した。
#!/usr/bin/env ruby #==================== # test_runner.rb #==================== # n本腕バンディット問題について、 # 特定のアルゴリズムを使って # 指定された回数の試行を行うクラス class TestRunner def initialize(bandit, method) @bandit = bandit @method = method @count = 0 @total_reward = 0 end # 指定された回数、試行を行う。 def exec(count) count.times do selected_arm = @method.select reward = @bandit.select(selected_arm) @total_reward += reward @method.reflect(selected_arm, reward) end @count += count end # 得られた報酬の平均を返す。 def average return (@total_reward * 1.0) / @count rescue 0.0 end # 報酬の期待値の最大値を返す。 def max_exp return @bandit.reward_exp.max end # 最適度を返す。 def optimality return self.average / self.max_exp end attr_reader :count, :total_reward end if __FILE__ == $PROGRAM_NAME require './bandit' require './greedy_method' size = 10 bandit = Bandit.new(size) greedy = TestRunner.new(bandit, GreedyMethod.new(size)) epsilon_greedy = TestRunner.new(bandit, GreedyMethod.new(size, 0.1)) [greedy, epsilon_greedy].each do |runner| puts "-------------------------------" puts " time reward avg. optimality" puts "-------------------------------" 20.times do |i| runner.exec(100) puts sprintf "%6d %11f %11f", runner.count, runner.average, runner.optimality end puts "-------------------------------" end end
これを実行したときの出力例は、以下。
$ ./test_runner.rb ------------------------------- time reward avg. optimality ------------------------------- 100 1.353143 0.739957 200 1.519433 0.830891 300 1.512373 0.827031 400 1.540366 0.842339 500 1.548200 0.846623 600 1.550186 0.847708 700 1.520141 0.831279 800 1.530093 0.836721 900 1.536885 0.840435 1000 1.540360 0.842335 1100 1.533432 0.838547 1200 1.527967 0.835559 1300 1.515530 0.828757 1400 1.525599 0.834263 1500 1.530191 0.836774 1600 1.535999 0.839951 1700 1.543579 0.844096 1800 1.544897 0.844816 1900 1.546161 0.845507 2000 1.548740 0.846918 ------------------------------- ------------------------------- time reward avg. optimality ------------------------------- 100 1.322562 0.723234 200 1.542951 0.843752 300 1.576506 0.862101 400 1.615745 0.883559 500 1.616947 0.884216 600 1.643590 0.898786 700 1.650623 0.902632 800 1.667683 0.911961 900 1.691079 0.924755 1000 1.688600 0.923399 1100 1.668986 0.912674 1200 1.667869 0.912063 1300 1.667196 0.911694 1400 1.671232 0.913902 1500 1.671193 0.913881 1600 1.680036 0.918716 1700 1.685295 0.921592 1800 1.685142 0.921509 1900 1.682836 0.920248 2000 1.680047 0.918722 -------------------------------
前者がグリーディ法による結果、後者がグリーディ法()による結果。
グリーディ法だと最適性がほとんど改善されていないのに対し、グリーディ法だと最適性がだいぶ改善されていることが分かると思う。
ただ、レバーの当たり外れの分布によって、この結果はやや変わってくる。
グリーディ法でも、最初に見つけた良さげなレバーが一番いいレバーだった場合、探査を行うグリーディ法よりもずっと最適性が高くなることもある。
けれど、そうなる可能性は(特に腕の本数が多くなるほど)低いので、平均すればグリーディ法の方がいい結果になりやすい。
とはいえ、に近づけると、今度は探査ばかりやっていて、ほぼ毎回ランダムにレバーを選択することになってしまうので、やはり性能は下がってしまう。
なので、やはりこのバランスが難しいということになる。
今日はここまで!
- 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
- 出版社/メーカー: 森北出版
- 発売日: 2000/12/01
- メディア: 単行本(ソフトカバー)
- 購入: 5人 クリック: 76回
- この商品を含むブログ (29件) を見る