いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。(その8)

昨日はグリーディ法と \varepsilonグリーディ法を扱った。

今日はn本腕バンディット問題に対する別のアルゴリズムを考えていく。

ソフトマックス法

 \varepsilonグリーディ法では、探査を行うために、 \varepsilonの確率でランダムに行動を選択していた。

もう一つ、探査を行うための方法として、推定される行動の価値の比率に応じて行動を選択するという方法が考えられる。
すなわち、推定される行動の価値から、価値が高そうな行動はより選ばれやすく、価値が低そうな行動は選ばれにくく(けど、全く選ばれないわけではないように)なる確率にしたがって行動を選択する。
そうすれば、基本的には価値が高いと思われる行動が選ばれ、たまに他の行動の探査も行われるようになる。

このようなアルゴリズムを、ソフトマックス法(ソフトマックス行動選択)と呼ぶ。

ソフトマックス法の具体的な方策(ポリシー) \pi_tの一つは、次のようになる。

 { \displaystyle
\pi_t(a) = \frac{\textstyle e^{Q_{t-1}(a) \left/ \tau \right.}}{\textstyle \sum_{a' \in \mathcal{A}} e^{Q_{t-1}(a') \left/ \tau \right.}}
}

上記の \tau \: (\gt 0)は温度と呼ばれる学習パラメータで、温度が高ければすべての行動がほぼ同じ確率で起こるようになり、低くなれば推定される行動の価値の高い行動が選ばれやすくなる(そして、 \tau \rightarrow 0のとき、グリーディ法と一致することになる)。

Rubyによる実装

上記のソフトマックス法をRubyで実装してみると、以下のような感じ。
 \TeXに影響が出るので、シンタックスハイライトはなし)

#====================
# 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クラスを使って走らせると、次のような感じ。
(上から順に、グリーディ法、 \varepsilonグリーディ法( \varepsilon = 0.1)、ソフトマックス法( \tau = 0.2))

$ ./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件) を見る