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

昨日はn本腕バンディット問題の行動の価値について考えた。

今日は、それを使って具体的なアルゴリズムを考えていく。

グリーディ法

一番最初に思いつく方法は、現在の推定される行動の価値の中で、最も価値の高い行動を選ぶという方法。
すなわち、 $t$ 回目に選ぶ行動を $a_t$ とするとき、

とする。
（※ $Q_t$ については、添え字 $t$ の扱いが本と1つズレていることに注意）

こういった方法を、グリーディ法（貪欲法）と呼ぶ。

$\varepsilon$ グリーディ法

グリーディ法の場合、常に「今のところ一番良さげなレバー」しか選ばないので、つまり「知識利用」のみを行って、「探査」は行わないことになる。

それだと推定される行動の価値が改善されていかない可能性があるので、 $\varepsilon \: (0 \lt \varepsilon \lt 1)$ の確率で、ランダムに行動を選択するような方法も考えてみる。
このような方法を、 $\varepsilon$ グリーディ法と呼ぶ。

$\varepsilon$ グリーディ法の方策（ポリシー） $\pi_t: \mathcal{A} \rightarrow [0, 1$ ]は、次のように表されることになる：

Rubyによる実装

グリーディ法、および、 $\varepsilon$ グリーディ法をRubyで実装してみると、次のような感じ。
（※シンタックスハイライトを入れると、Markdownのパーサによって $\TeX$ の表記が崩れるようなので、入れてない）

#====================
# 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
-------------------------------

前者がグリーディ法による結果、後者が $\varepsilon$ グリーディ法（ $\varepsilon = 0.1$ ）による結果。
グリーディ法だと最適性がほとんど改善されていないのに対し、 $\varepsilon$ グリーディ法だと最適性がだいぶ改善されていることが分かると思う。