昨日はグリーディ法とグリーディ法を扱った。
今日はn本腕バンディット問題に対する別のアルゴリズムを考えていく。
ソフトマックス法
グリーディ法では、探査を行うために、の確率でランダムに行動を選択していた。
もう一つ、探査を行うための方法として、推定される行動の価値の比率に応じて行動を選択するという方法が考えられる。
すなわち、推定される行動の価値から、価値が高そうな行動はより選ばれやすく、価値が低そうな行動は選ばれにくく(けど、全く選ばれないわけではないように)なる確率にしたがって行動を選択する。
そうすれば、基本的には価値が高いと思われる行動が選ばれ、たまに他の行動の探査も行われるようになる。
このようなアルゴリズムを、ソフトマックス法(ソフトマックス行動選択)と呼ぶ。
ソフトマックス法の具体的な方策(ポリシー)の一つは、次のようになる。
上記のは温度と呼ばれる学習パラメータで、温度が高ければすべての行動がほぼ同じ確率で起こるようになり、低くなれば推定される行動の価値の高い行動が選ばれやすくなる(そして、のとき、グリーディ法と一致することになる)。
Rubyによる実装
上記のソフトマックス法をRubyで実装してみると、以下のような感じ。
(に影響が出るので、シンタックスハイライトはなし)
#==================== # softmax_method.rb #==================== class SoftmaxMethod @@random = Random.new # size: n本腕バンディット問題のサイズ # temperature: 温度(学習パラメータ) # stepsize: nil以外を指定した場合、ステップサイズとして扱う def initialize(size=10, temperature=0.1, stepsize=nil) @size = size @temperature = temperature @stepsize = stepsize @values = Array.new(size, 0.0) @times = Array.new(size, 0) @weights = Array.new(size, 1.0) end # ソフトマックス法で腕を選ぶ。 # -- # 各腕の重みをexp(values[i]/temperature)とし、 # 重みに従った確率で腕を選ぶ。 # -- # 価値が高いほど、重みが大きくなるので選ばれやすい。 # ただし、温度が高い場合、重みは相対的に小さくなり、 # 他の行動が選ばれる可能性も高くなる。 def select weight_total = @weights.inject(0.0, :+) rand = @@random.rand * weight_total selected = 0 @size.times do |i| if rand <= @weights[i] selected = i break else rand -= @weights[i] end end return selected end # 得られた報酬を反映し、学習する。 # -- # selected: 選んだ腕 # value: 得られた報酬 def reflect(selected, value) @times[selected] += 1 stepsize = @stepsize ? @stepsize : (1.0 / @times[selected]) @values[selected] += stepsize * (value - @values[selected]) @weights[selected] = Math.exp(@values[selected] / @temperature) end attr_reader :size, :temperature, :values, :weights end
ちょっと分かりにくいかもしれないのが、
weight_total = @weights.inject(0.0, :+)
というコード。
Enumerable#inject(init, sym)はリストの畳込み計算を行うメソッドで、initに初期値、symに畳込みに使うメソッドのシンボルを指定すると、リストの最初の項目から順に、これまでの計算結果(一番最初は初期値)と現在の項目について指定されたメソッドを適用し、新たな計算結果とするということを繰り返してくれる。
なので、これで配列の合計値が計算出来る。
(Rubyだと整数の足し算(+)もメソッドで、そのシンボルは:+となる。Cool!)
これを昨日のTestRunnerクラスを使って走らせると、次のような感じ。
(上から順に、グリーディ法、グリーディ法()、ソフトマックス法())
$ ./test_runner.rb ------------------------------- time reward avg. optimality ------------------------------- 100 0.565949 0.335155 200 0.619599 0.366926 300 0.584962 0.346414 400 0.563125 0.333482 500 0.551482 0.326587 600 0.566153 0.335276 700 0.597292 0.353716 800 0.597354 0.353753 900 0.586898 0.347561 1000 0.583982 0.345834 1100 0.580169 0.343576 1200 0.586426 0.347281 1300 0.588007 0.348218 1400 0.585714 0.346860 1500 0.587253 0.347771 1600 0.589223 0.348938 1700 0.591222 0.350121 1800 0.584263 0.346001 1900 0.588309 0.348396 2000 0.593327 0.351368 ------------------------------- ------------------------------- time reward avg. optimality ------------------------------- 100 1.220985 0.723067 200 1.370641 0.811693 300 1.401869 0.830187 400 1.428741 0.846100 500 1.466581 0.868508 600 1.466817 0.868648 700 1.485362 0.879631 800 1.489367 0.882003 900 1.481916 0.877590 1000 1.483326 0.878425 1100 1.471355 0.871336 1200 1.477749 0.875122 1300 1.486057 0.880043 1400 1.472135 0.871798 1500 1.476511 0.874389 1600 1.472649 0.872102 1700 1.468288 0.869520 1800 1.467992 0.869344 1900 1.468679 0.869751 2000 1.479261 0.876018 ------------------------------- ------------------------------- time reward avg. optimality ------------------------------- 100 0.780590 0.462265 200 1.258699 0.745401 300 1.433147 0.848709 400 1.469399 0.870178 500 1.509892 0.894157 600 1.563799 0.926081 700 1.572051 0.930968 800 1.562559 0.925347 900 1.571594 0.930698 1000 1.580078 0.935721 1100 1.591995 0.942779 1200 1.599730 0.947359 1300 1.614864 0.956322 1400 1.606241 0.951216 1500 1.606286 0.951242 1600 1.608835 0.952752 1700 1.611022 0.954047 1800 1.605856 0.950988 1900 1.612302 0.954804 2000 1.614708 0.956230 -------------------------------
もちろん、レバーの当たり外れの分布によって結果は変わってくるけど、ソフトマックス法も結果が改善されていっているのが分かるかと思う。
今日はここまで!
- 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
- 出版社/メーカー: 森北出版
- 発売日: 2000/12/01
- メディア: 単行本(ソフトカバー)
- 購入: 5人 クリック: 76回
- この商品を含むブログ (29件) を見る