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

昨日は方策改善について説明した。

今日は、方策評価と方策改善を使って実際に学習を進めていく方法について。

方策反復

方策評価でまず方策の評価を行ったら、次に方策改善で方策の改善を行う。
そしたら、今度は改善された方策で再び方策評価を行い、さらに方策改善を行う・・・
というのを繰り返せば、繰り返すごとに方策は改善されていって、最後には最適方策へたどり着くことが予想される。
このような手法は、方策反復（policy iteration）と呼ばれている。

具体的には、以下のようなアルゴリズムになる。

初期化
1. すべての $s \in \mathcal{S}$ について、 $V_s \in \mathbb{R}$ と $\pi(s) \in \mathcal{A}(s)$ を任意に初期化する。
方策評価
1. 以下を繰り返す：
  1. $\Delta \leftarrow 0$
  2. 各について：
    1. $v \leftarrow V_s$
    2. $V_s \leftarrow \sum_{s' \in \mathcal{S}} \mathcal{P}^{\pi(s)}_{ss'} \left( \mathcal{R}^{\pi(s)}_{ss'} + \gamma V_{s'} \right)$
    3. $\Delta \leftarrow \mbox{max} \left\{ \Delta, \left| V_s - v \right| \right\}$
  3. $\Delta \lt \varepsilon$ （ $\varepsilon$ は十分小さい正の定数）なら、繰り返しを終了。
方策改善
1. $updated \leftarrow \mbox{false}$
2. 各について：
  1. $old \leftarrow \pi(s)$
  2. $\pi(s) \leftarrow \mathop{\mbox{arg max}}_{a \in \mathcal{A}(s)} \sum_{s' \in \mathcal{S}} \mathcal{P}^{a}_{ss'} \left( \mathcal{R}^{a}_{ss'} + \gamma V_{s'} \right)$
  3. $old \neq \pi(s)$ なら、 $updated \leftarrow \mbox{true}$
3. $updated$ がtrueなら、2. 方策評価へ戻る。
  そうでなければ、終了。

レンタカー問題

具体的なプログラムがどうなるのかを例示するために、本に載っているレンタカー問題を取り上げる。

この問題は、レンタカーの営業所間で夜の間に何台レンタカーを移動させればいいかを考える問題で、状況は以下の通り：

レンタカーの営業所が2ヶ所ある。（それぞれ、第1営業所、第2営業所とする）
各営業所に置かれているレンタカーの台数は、0〜20台。（返却されて20台を超えた場合、超えた分は第1、第2営業所以外に移動されるとする）
レンタカーを1台貸し出すと、10ドルの支払いを受ける。
レンタカーが営業所にない場合、貸し出せない。
レンタカーは、返却日の翌日に再び貸し出し可能になる。
レンタル要求台数と返却台数は、ポアソン分布に従う。
すなわち、期待値が $\lambda$ 台のとき、 $n$ 台レンタル要求される/返却される確率は、 $\frac{\lambda^{n}}{n!}e^{-\lambda}$ となる。
レンタル要求台数の期待値は、第1営業所が3台、第2営業所が4台。
返却台数の期待値は、第1営業所が3第、第2営業所が2台。
夜のうちに営業所間でレンタカーを最大5台まで移動することが出来る。
1台移動させるごとに2ドルかかる。

例題とするには、ちょっとややこしいと思うんだけどね（＾＾；
何はともあれ、このような状況のときに、営業所にあるレンタカーの台数に応じて、夜の間に何台レンタカーを移動べきかを考える、というのがこの問題の趣旨。

この問題を考えていくために、

状態は、各営業所の1日の営業終了時のレンタカー台数
行動は、夜の間に移動させるレンタカー台数（第1→第2の移動をプラスとする）
割引率は0.9とする
レンタカーを一切移動させないという方策からスタートする

として、Rubyでプログラムを組んでいく。

Rubyによる実装

定数

まずは定数を定義しておく。

#====================
# rental_car_problem.rb
#====================

module RentalCarProblem
  # レンタカーは最大20台まで
  RENTAL_CAR_MAX = 20

  # 移動は最大5台まで
  MOVE_MAX = 5
end

状態価値

次に、状態価値。

#====================
# status_value.rb
#====================

require './rental_car_problem'

module RentalCarProblem
  class StatusValue
    # 状態価値の初期値は0
    def initialize
      @value = Array.new((0..RENTAL_CAR_MAX).size) do
        Array.new((0..RENTAL_CAR_MAX).size, 0.0)
      end
    end

    def get(x, y)
      @value[x][y]
    end

    def set(x, y, new_value)
      @value[x][y] = new_value
    end

    @@print_header = "   |" + "    %02d" * (0..RENTAL_CAR_MAX).size
    @@print_bar = "----" + "------" * (0..RENTAL_CAR_MAX).size
    @@print_format = "%02d |" + " %5.1f" * (0..RENTAL_CAR_MAX).size

    def print
      puts @@print_bar
      puts sprintf @@print_header, *((0..RENTAL_CAR_MAX).to_a)
      puts @@print_bar
      (0..RENTAL_CAR_MAX).each do |i|
        puts sprintf @@print_format, i, *((0..RENTAL_CAR_MAX).map {|j| @value[i][j]})
      end
      puts @@print_bar
    end

    # 状態(x, y)からmoveだけ動かしたときの状態価値を計算する
    # moveが不正な場合、例外を投げる
    def value_of_move(x, y, move)
      value = 0.0

      # まず、moveだけ車を移動させる
      # これが次の日に各営業所にある車の台数
      # ただし、値が不正なら、例外を投げる
      next_x_start = x - move
      next_y_start = y + move
      if (next_x_start < 0) || (next_x_start > RENTAL_CAR_MAX) ||
         (next_y_start < 0) || (next_y_start > RENTAL_CAR_MAX)
        raise "move is invalid."
      end

      # 第1で貸し出せるのは、0〜next_x_startまで
      # 第2で貸し出せるのは、0〜next_y_startまで
      (0..next_x_start).each do |x_rental|
        (0..next_y_start).each do |y_rental|
          x_rest = next_x_start - x_rental
          y_rest = next_y_start - y_rental
          # 第1に返される台数は、0〜(RENTAL_CAR_MAX - x_rest)まで
          # 第2に返される台数は、0〜(RENTAL_CAR_MAX - y_rest)まで
          (0..(RENTAL_CAR_MAX - x_rest)).each do |x_return|
            (0..(RENTAL_CAR_MAX - y_rest)).each do |y_return|
              probability = (
                x_rental_probability(x_rental) *
                y_rental_probability(y_rental) *
                x_return_probability(x_return) *
                y_return_probability(y_return))
              reward = (x_rental + y_rental) * 10 - move.abs * 2
              next_x = next_x_start - x_rental + x_return
              next_y = next_y_start - y_rental + y_return
              value += probability * (reward + 0.9 * @value[next_x][next_y])
            end
          end
        end
      end

      return value
    end

    def get_most_valuable_move(x, y, *move_list)
      move_value_hash = move_list.each_with_object(Hash.new) do |move, hash|
        begin
          hash[move] = value_of_move(x, y, move)
        rescue
          # 不正な移動の場合、処理をスキップ
        end
      end

      highest_value = move_value_hash.values.max
      most_valuable_move = move_value_hash.key(highest_value)

      return most_valuable_move, highest_value
    end

    private

    # 期待値がexpectでのポアソン分布の確率P(X=n)を返す
    def poisson(n, expect)
      if n > 0
        (expect ** n) * (Math.exp(-expect)) / (1..n).inject(:*)
      else
        Math.exp(-expect)
      end
    end

    # 第1営業所の貸出数がnになる確率を返す
    def x_rental_probability(n)
      poisson(n, 3)
    end

    # 第2営業所の貸出数がnになる確率を返す
    def y_rental_probability(n)
      poisson(n, 4)
    end

    # 第1営業所の返却数がnになる確率を返す
    def x_return_probability(n)
      poisson(n, 3)
    end

    # 第2営業所の返却数がnになる確率を返す
    def y_return_probability(n)
      poisson(n, 2)
    end
  end
end

移動したときの価値や、最も価値の高い行動を返すメソッドも用意してある。

方策

そして、方策。

#====================
# policy.rb
#====================

require './rental_car_problem'

module RentalCarProblem
  class Policy
    # 方策の初期値は0（移動しない）
    def initialize
      @policy = Array.new((0..RENTAL_CAR_MAX).size) do
        Array.new((0..RENTAL_CAR_MAX).size, 0)
      end
    end

    def get(x, y)
      return @policy[x][y]
    end

    def set(x, y, move)
      @policy[x][y] = move
    end

    @@print_header = "   |" + " %02d" * (0..RENTAL_CAR_MAX).size
    @@print_bar = "----" + "---" * (0..RENTAL_CAR_MAX).size
    @@print_format = "%02d |" + " %2d" * (0..RENTAL_CAR_MAX).size

    def print
      puts @@print_bar
      puts sprintf @@print_header, *((0..RENTAL_CAR_MAX).to_a)
      puts @@print_bar
      (0..RENTAL_CAR_MAX).each do |i|
        puts sprintf @@print_format, i, *((0..RENTAL_CAR_MAX).map {|j| @policy[i][j]})
      end
      puts @@print_bar
    end
  end
end

方策反復

最後に、方策反復。

#!/usr/bin/env ruby

#====================
# policy_iteration_method.rb
#====================

require './rental_car_problem'
require './status_value'
require './policy'

module RentalCarProblem
  # 方策反復法
  class PolicyIterationMethod
    def initialize(value, policy, verbose=false)
      @value = value
      @policy = policy
      @verbose = verbose
    end

    attr_reader :value, :policy

    def execute
      i = 0
      loop do
        evaluate_policy
        if @verbose
          puts "Value_#{i}"
          @value.print
        end

        improved = improve_policy
        if @verbose
          puts "Policy_#{i}"
          @policy.print
        end

        if improved
          i += 1
        else
          break
        end
      end
    end

    private

    @@delta_max = 0.1

    # 方策policyで方策評価を行う
    def evaluate_policy
      loop do
        delta = 0.0

        (0..RENTAL_CAR_MAX).each do |x|
          (0..RENTAL_CAR_MAX).each do |y|
            old_value = @value.get(x, y)
            new_value = @value.value_of_move(x, y, policy.get(x, y))

            delta = [delta, (new_value - old_value).abs].max
            @value.set(x, y, new_value)
          end
        end

        if delta < @@delta_max
          break
        end

        @value.print if @verbose
      end
    end

    # 状態価値valueを使って方策改善を行う
    # 改善された場合trueを返す
    def improve_policy
      policy_improved = false

      (0..RENTAL_CAR_MAX).each do |x|
        (0..RENTAL_CAR_MAX).each do |y|
          old_policy = @policy.get(x, y)

          new_policy, max_value = @value.get_most_valuable_move(x, y, *((-MOVE_MAX..MOVE_MAX).to_a))

          if old_policy != new_policy
            policy_improved = true
            @policy.set(x, y, new_policy)
          end
        end
      end

      return policy_improved
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  include RentalCarProblem

  value = StatusValue.new
  policy = Policy.new
  policy_iteration = PolicyIterationMethod.new(value, policy, true)

  policy_iteration.execute

  puts "最適状態価値関数"
  policy_iteration.value.print

  puts "最適方策"
  policy_iteration.policy.print
end

実行例

実行すると、以下のような感じ。

$ ./policy_iteration_method.rb
----------------------------------------------------------------------------------------------------------------------------------
   |    00    01    02    03    04    05    06    07    08    09    10    11    12    13    14    15    16    17    18    19    20
----------------------------------------------------------------------------------------------------------------------------------
00 |   0.0   0.0   0.2   0.5   0.9   1.3   1.6   1.8   1.9   2.0   2.0   2.0   2.0   2.0   2.0   2.0   2.0   2.0   2.0   1.9   1.9
01 |   0.0   0.3   1.1   2.5   4.4   6.2   7.6   8.6   9.1   9.4   9.5   9.6   9.6   9.6   9.6   9.6   9.6   9.6   9.5   9.3   8.8
02 |   0.1   0.9   3.0   6.7  11.3  15.7  19.1  21.5  22.9  23.7  24.1  24.3  24.4  24.4  24.4  24.5  24.4  24.4  24.1  23.5  22.3
03 |   0.2   1.7   5.5  12.0  20.0  27.7  33.8  38.1  40.8  42.4  43.3  43.9  44.2  44.4  44.5  44.6  44.5  44.4  43.9  42.8  40.5
04 |   0.4   2.5   8.0  17.2  28.4  39.2  48.1  54.5  58.7  61.3  63.0  64.1  64.8  65.2  65.5  65.7  65.7  65.5  64.8  63.0  59.5
05 |   0.5   3.2  10.0  21.2  34.9  48.3  59.4  67.5  73.2  77.0  79.5  81.2  82.3  83.1  83.6  83.9  84.0  83.7  82.8  80.4  75.7
06 |   0.6   3.6  11.2  23.8  39.2  54.3  67.0  76.6  83.4  88.2  91.5  93.8  95.4  96.5  97.2  97.7  97.9  97.6  96.5  93.6  88.0
07 |   0.6   3.9  12.0  25.3  41.7  58.0  71.8  82.4  90.1  95.6  99.6 102.4 104.4 105.9 106.9 107.5 107.8 107.5 106.3 103.1  96.7
08 |   0.6   4.0  12.4  26.2  43.2  60.1  74.6  85.9  94.3 100.4 104.9 108.2 110.6 112.3 113.5 114.3 114.7 114.5 113.2 109.7 102.8
09 |   0.7   4.1  12.6  26.7  44.0  61.4  76.3  88.1  97.0 103.5 108.4 112.0 114.7 116.7 118.1 119.1 119.6 119.4 118.0 114.4 107.2
10 |   0.7   4.1  12.8  27.0  44.5  62.1  77.4  89.5  98.6 105.5 110.7 114.5 117.5 119.7 121.3 122.4 123.0 122.9 121.5 117.7 110.2
11 |   0.7   4.1  12.8  27.1  44.8  62.5  78.0  90.3  99.7 106.8 112.1 116.2 119.3 121.7 123.4 124.6 125.3 125.3 123.9 120.0 112.4
12 |   0.7   4.1  12.9  27.2  44.9  62.8  78.4  90.8 100.3 107.5 113.1 117.3 120.5 123.0 124.9 126.2 126.9 126.9 125.5 121.7 113.9
13 |   0.7   4.1  12.9  27.2  45.0  62.9  78.5  91.0 100.7 108.0 113.6 118.0 121.3 123.9 125.8 127.2 128.0 128.0 126.7 122.8 114.9
14 |   0.7   4.1  12.9  27.2  45.0  62.9  78.5  91.1 100.8 108.1 113.8 118.2 121.6 124.3 126.3 127.7 128.6 128.6 127.3 123.4 115.5
15 |   0.7   4.1  12.8  27.1  44.8  62.6  78.3  90.8 100.5 107.9 113.6 118.0 121.5 124.2 126.2 127.7 128.6 128.7 127.3 123.4 115.5
16 |   0.7   4.1  12.7  26.8  44.3  61.9  77.4  89.8  99.4 106.8 112.5 117.0 120.5 123.2 125.2 126.7 127.7 127.8 126.5 122.6 114.7
17 |   0.6   4.0  12.4  26.1  43.2  60.3  75.4  87.6  97.0 104.3 110.0 114.4 117.9 120.6 122.6 124.2 125.1 125.3 124.0 120.2 112.4
18 |   0.6   3.8  11.8  24.8  40.9  57.2  71.6  83.2  92.3  99.4 104.9 109.3 112.7 115.4 117.5 119.0 119.9 120.1 118.9 115.2 107.7
19 |   0.6   3.5  10.8  22.6  37.2  52.1  65.2  76.0  84.5  91.2  96.5 100.7 104.0 106.6 108.6 110.1 111.1 111.3 110.2 106.7  99.7
20 |   0.5   3.1   9.3  19.4  31.9  44.7  56.1  65.6  73.2  79.4  84.3  88.2  91.4  93.9  95.8  97.3  98.3  98.5  97.5  94.4  88.1
----------------------------------------------------------------------------------------------------------------------------------

〜省略〜

Value_0
----------------------------------------------------------------------------------------------------------------------------------
   |    00    01    02    03    04    05    06    07    08    09    10    11    12    13    14    15    16    17    18    19    20
----------------------------------------------------------------------------------------------------------------------------------
00 |   0.0   0.1   0.3   0.8   1.5   2.2   3.0   3.6   4.2   4.7   5.2   5.6   6.0   6.3   6.6   6.8   7.0   7.2   7.2   7.0   6.5
01 |   0.1   0.5   1.8   4.1   7.1  10.5  13.7  16.6  19.1  21.3  23.3  25.0  26.6  28.1  29.3  30.4  31.3  31.9  31.9  31.0  28.8
02 |   0.2   1.4   4.6  10.2  17.5  25.4  32.9  39.6  45.5  50.6  55.2  59.4  63.1  66.5  69.5  72.1  74.2  75.5  75.5  73.4  68.1
03 |   0.4   2.5   8.1  17.7  30.1  43.4  55.9  67.2  77.1  85.9  93.7 100.8 107.2 113.0 118.2 122.7 126.3 128.6 128.7 125.0 115.9
04 |   0.6   3.6  11.5  24.7  41.7  59.9  77.2  92.7 106.6 118.9 130.0 140.0 149.2 157.4 164.9 171.4 176.6 180.0 180.1 174.9 162.1
05 |   0.7   4.5  14.0  30.0  50.5  72.4  93.4 112.5 129.7 145.0 159.0 171.7 183.4 193.9 203.4 211.8 218.5 222.9 223.2 216.8 200.9
06 |   0.8   5.0  15.7  33.5  56.3  80.9 104.6 126.3 146.0 163.8 180.1 195.1 208.8 221.3 232.6 242.6 250.7 256.0 256.5 249.2 230.8
07 |   0.9   5.4  16.7  35.6  59.9  86.1 111.7 135.3 156.8 176.6 194.7 211.5 226.9 241.0 253.7 265.0 274.3 280.4 281.1 273.2 253.1
08 |   0.9   5.6  17.2  36.8  62.0  89.3 116.1 141.0 163.9 185.0 204.5 222.6 239.3 254.6 268.6 280.9 291.0 297.8 298.8 290.5 269.1
09 |   0.9   5.7  17.6  37.5  63.2  91.2 118.7 144.5 168.3 190.4 210.8 229.9 247.5 263.7 278.5 291.6 302.5 309.7 311.0 302.4 280.1
10 |   0.9   5.7  17.7  37.9  63.9  92.3 120.2 146.5 170.9 193.5 214.6 234.3 252.5 269.3 284.7 298.3 309.6 317.2 318.6 309.9 287.1
11 |   0.9   5.8  17.8  38.1  64.2  92.8 120.9 147.5 172.1 195.0 216.4 236.3 254.9 272.0 287.6 301.5 313.0 320.8 322.3 313.6 290.5
12 |   0.9   5.8  17.8  38.1  64.2  92.8 121.0 147.5 172.2 195.1 216.5 236.4 254.9 272.1 287.7 301.6 313.1 320.9 322.3 313.6 290.5
13 |   0.9   5.7  17.8  37.9  64.0  92.3 120.3 146.6 171.0 193.7 214.8 234.4 252.7 269.5 284.9 298.5 309.8 317.4 318.8 310.1 287.2
14 |   0.9   5.7  17.6  37.6  63.3  91.3 118.9 144.7 168.5 190.6 211.1 230.1 247.8 264.0 278.8 291.9 302.8 310.0 311.2 302.7 280.4
15 |   0.9   5.6  17.3  36.9  62.2  89.5 116.3 141.3 164.2 185.3 204.9 222.9 239.6 255.0 268.9 281.3 291.4 298.2 299.2 290.9 269.4
16 |   0.9   5.5  16.8  35.8  60.2  86.5 112.0 135.7 157.3 177.0 195.2 212.0 227.4 241.5 254.3 265.5 274.8 280.8 281.6 273.6 253.4
17 |   0.9   5.2  16.0  34.0  57.0  81.6 105.3 127.1 146.8 164.7 181.0 196.0 209.7 222.2 233.5 243.5 251.6 256.8 257.3 249.9 231.4
18 |   0.8   4.8  14.7  31.2  52.0  74.2  95.3 114.6 131.7 147.2 161.2 174.0 185.7 196.3 205.8 214.2 220.9 225.3 225.5 218.9 202.7
19 |   0.7   4.2  12.9  27.1  45.0  63.9  81.7  97.6 111.8 124.3 135.7 145.9 155.2 163.6 171.2 177.8 183.1 186.5 186.5 181.0 167.5
20 |   0.6   3.5  10.5  21.9  36.2  51.1  64.9  77.2  87.9  97.4 105.8 113.4 120.3 126.5 132.0 136.9 140.7 143.1 143.0 138.7 128.4
----------------------------------------------------------------------------------------------------------------------------------
Policy_0
-------------------------------------------------------------------
   | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
00 |  0  0 -1 -1 -2 -2 -2 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5
01 |  1  0  0 -1 -1 -1 -2 -2 -3 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5 -5 -5
02 |  1  1  0  0  0 -1 -1 -2 -2 -2 -3 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5
03 |  2  1  1  0  0  0 -1 -1 -1 -2 -2 -2 -3 -3 -3 -4 -4 -4 -4 -5 -5
04 |  2  2  1  1  1  0  0  0 -1 -1 -1 -2 -2 -2 -3 -3 -3 -3 -4 -4 -4
05 |  3  2  2  2  1  1  0  0  0  0 -1 -1 -1 -2 -2 -2 -2 -3 -3 -3 -4
06 |  3  3  3  2  2  1  1  1  0  0  0  0 -1 -1 -1 -1 -2 -2 -2 -3 -3
07 |  4  4  3  3  2  2  2  1  1  1  0  0  0  0  0 -1 -1 -1 -2 -2 -3
08 |  5  4  4  3  3  3  2  2  2  1  1  1  0  0  0  0  0 -1 -1 -2 -3
09 |  5  5  4  4  4  3  3  3  2  2  2  1  1  1  1  0  0  0 -1 -2 -2
10 |  5  5  5  5  4  4  4  3  3  3  2  2  2  2  1  1  0  0 -1 -1 -2
11 |  5  5  5  5  5  5  4  4  4  3  3  3  3  2  2  1  1  0  0 -1 -2
12 |  5  5  5  5  5  5  5  5  4  4  4  4  3  3  2  2  1  0  0 -1 -1
13 |  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  1  1  0  0 -1
14 |  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  2  2  1  0  0 -1
15 |  5  5  5  5  5  5  5  5  5  5  5  5  5  4  3  3  2  1  1  0 -1
16 |  5  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  2  2  1  0  0
17 |  5  5  5  5  5  5  5  5  5  5  5  5  5  5  4  3  3  2  1  1  0
18 |  5  5  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  2  2  1  0
19 |  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  4  3  3  2  1  0
20 |  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  2  1  0
-------------------------------------------------------------------

〜省略〜

Value_1
----------------------------------------------------------------------------------------------------------------------------------
   |    00    01    02    03    04    05    06    07    08    09    10    11    12    13    14    15    16    17    18    19    20
----------------------------------------------------------------------------------------------------------------------------------
00 |   0.0   0.1   0.6   2.2   5.4  11.9  20.3  34.9  50.0  70.0  89.8 107.9 132.8 152.4 170.6 188.0 204.8 221.1 237.0 252.2 266.6
01 |   0.1   0.7   2.3   5.6  12.2  20.8  35.7  51.0  71.3  91.3 109.5 134.6 154.2 172.4 196.0 214.5 232.1 249.2 265.5 281.2 295.9
02 |   0.6   2.2   5.8  12.6  21.3  36.5  52.0  72.6  92.7 111.0 136.3 155.9 174.2 197.9 216.4 234.1 253.8 270.9 287.2 302.7 317.1
03 |   2.1   5.6  12.2  22.4  37.3  53.0  73.9  94.2 112.6 138.0 157.7 176.0 199.9 218.3 236.0 255.8 272.9 289.2 304.6 319.8 333.7
04 |   5.4  11.9  21.8  36.5  52.0  75.2  95.6 114.1 139.8 159.5 177.8 201.8 220.2 237.9 257.8 274.8 291.1 306.6 321.8 335.7 348.0
05 |  11.5  21.3  35.7  51.0  73.9  94.2 119.5 141.5 161.3 179.7 203.7 222.2 239.9 259.7 276.8 293.1 308.6 323.8 337.7 350.0 361.0
06 |  20.7  34.9  50.0  72.6  92.7 117.8 139.8 159.5 185.9 205.6 224.1 241.8 261.7 278.8 295.1 310.6 325.8 339.7 352.0 363.0 371.3
07 |  34.0  49.0  71.3  91.3 116.2 138.0 157.7 184.0 203.7 222.2 245.8 263.7 280.8 297.1 312.6 327.8 341.7 353.9 365.0 373.3 381.2
08 |  48.0  70.0  89.8 114.6 136.3 156.0 182.1 201.8 220.3 243.8 261.7 278.8 298.8 314.8 329.8 343.7 355.9 367.0 375.3 383.2 389.2
09 |  68.8  88.4 112.9 134.6 154.2 180.2 199.9 218.3 241.9 259.7 276.8 296.8 312.8 327.8 341.7 357.5 369.0 377.3 385.2 391.2 391.0
10 |  87.5 111.3 132.8 152.4 178.3 197.9 216.4 239.9 257.8 274.8 294.9 310.8 325.8 339.7 355.5 367.0 380.0 387.2 393.2 392.9 395.6
11 | 104.0 131.1 155.1 176.4 196.0 214.5 237.9 255.8 272.9 292.9 308.8 323.8 337.7 353.6 365.0 378.0 385.2 395.2 394.9 397.6 397.9
12 | 119.0 148.7 174.5 196.9 217.2 236.0 253.8 270.9 290.9 306.8 321.8 335.7 351.6 363.0 376.0 383.2 393.2 401.4 399.5 399.9 385.5
13 | 133.3 165.2 192.2 215.3 235.7 254.5 272.1 288.9 304.8 319.8 333.7 349.6 361.0 374.0 381.2 391.3 399.4 397.6 401.8 387.3 383.2
14 | 147.3 181.0 209.0 232.5 252.8 271.3 288.5 304.7 320.0 334.4 347.6 359.0 372.0 379.3 389.3 397.4 395.6 399.9 401.2 385.0 376.7
15 | 161.0 196.5 225.3 248.8 269.0 286.9 303.5 319.1 333.6 347.2 359.5 370.0 377.3 387.3 395.5 393.7 398.0 399.3 383.2 378.5 364.2
16 | 174.4 211.5 241.0 264.6 284.3 301.7 317.6 332.3 346.0 358.7 370.0 379.3 385.3 393.5 391.8 396.0 397.4 381.3 376.7 366.0 332.6
17 | 187.3 225.9 256.0 279.6 298.9 315.6 330.7 344.5 357.2 368.8 378.9 386.9 391.5 389.8 394.1 395.4 379.5 374.9 364.2 331.0 311.7
18 | 199.5 239.5 270.1 293.6 312.5 328.5 342.7 355.5 367.1 377.4 386.1 392.6 395.5 392.2 393.5 377.6 373.0 362.4 329.4 310.1 280.4
19 | 210.5 251.7 282.8 306.1 324.5 339.7 352.9 364.7 375.0 383.9 391.0 395.8 396.8 391.6 375.8 371.2 360.7 327.7 308.5 278.9 237.7
20 | 219.5 261.5 292.8 315.9 333.6 347.9 360.2 370.7 379.7 387.0 392.3 395.1 394.1 386.9 369.4 358.9 326.1 307.0 277.5 236.4 186.0
----------------------------------------------------------------------------------------------------------------------------------
Policy_1
-------------------------------------------------------------------
   | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
00 |  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
01 |  1  0  0 -1 -1 -2 -2 -2 -3 -3 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5
02 |  1  1  0  0 -1 -1 -1 -2 -2 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5 -5 -5
03 |  2  1  1  0  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -4 -4 -4 -5 -5 -5
04 |  2  2  1  1  0  0  0 -1 -1 -2 -2 -2 -3 -3 -3 -3 -3 -4 -4 -4 -4
05 |  3  2  2  1  1  0  0  0 -1 -1 -1 -2 -2 -2 -2 -2 -3 -3 -3 -3 -4
06 |  3  3  2  2  1  1  1  0  0  0 -1 -1 -1 -1 -1 -2 -2 -2 -2 -3 -4
07 |  4  3  3  2  2  2  1  1  0  0  0  0  0  0 -1 -1 -1 -1 -2 -3 -4
08 |  4  4  3  3  3  2  2  1  0  0  0  0  0  0  0  0  0 -1 -2 -3 -3
09 |  5  4  4  4  3  3  2  1  1  0  0  0  0  0  0  0  0 -1 -2 -2 -3
10 |  5  5  5  4  4  3  2  2  1  1  0  0  0  0  0  0  0 -1 -1 -2 -3
11 |  5  5  5  5  4  3  3  2  2  1  0  0  0  0  0  0  0  0 -1 -2 -3
12 |  5  5  5  5  4  4  3  3  2  1  0  0  0  0  0  0  0  0 -1 -2 -3
13 |  5  5  5  5  5  4  4  3  2  1  1  0  0  0  0  0  0  0 -1 -2 -2
14 |  5  5  5  5  5  5  4  3  2  2  1  1  1  1  1  0  0  0 -1 -1 -2
15 |  5  5  5  5  5  5  4  3  3  2  2  2  2  2  1  1  0  0  0 -1 -1
16 |  5  5  5  5  5  5  4  4  3  3  3  3  3  2  2  1  1  0  0  0 -1
17 |  5  5  5  5  5  5  5  4  4  4  4  4  3  3  2  2  1  1  0  0  0
18 |  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  1  0  0
19 |  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  1  0
20 |  5  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  0
-------------------------------------------------------------------

〜省略〜

Value_3
----------------------------------------------------------------------------------------------------------------------------------
   |    00    01    02    03    04    05    06    07    08    09    10    11    12    13    14    15    16    17    18    19    20
----------------------------------------------------------------------------------------------------------------------------------
00 |   0.0   0.1   0.7   2.2   5.5  12.0  20.9  35.2  50.5  70.8  90.9 112.9 134.9 155.0 173.8 191.8 209.1 225.9 242.2 257.7 272.5
01 |   0.1   0.7   2.3   5.7  12.3  21.5  36.0  51.5  72.1  92.4 114.5 136.7 157.8 179.8 200.1 219.1 237.4 254.9 271.6 287.7 302.7
02 |   0.7   2.2   5.9  12.7  22.0  36.8  52.5  73.4  93.8 116.2 138.4 159.6 181.7 202.0 222.0 241.5 260.0 277.5 294.3 310.1 325.0
03 |   2.1   5.7  12.3  22.6  37.6  53.6  74.7  95.3 117.8 140.1 161.5 183.6 203.9 224.0 243.5 261.9 279.5 296.5 312.9 328.3 342.6
04 |   5.5  12.0  22.0  36.8  53.9  76.0  96.7 119.4 141.9 163.3 185.5 205.8 225.9 245.5 263.9 281.5 298.5 314.9 330.3 344.6 357.7
05 |  11.6  21.5  36.0  52.9  74.7  95.8 121.0 143.6 165.1 187.4 207.7 227.9 247.4 265.9 283.4 300.5 316.9 332.3 346.6 359.7 371.6
06 |  20.9  35.2  51.9  73.4  94.4 119.4 141.9 167.0 189.3 209.7 229.9 249.4 267.9 285.4 302.5 318.9 334.3 348.6 361.7 373.6 384.1
07 |  34.4  50.8  72.1  92.9 117.8 140.1 165.1 187.4 210.7 231.8 251.4 269.8 287.4 304.5 320.9 336.3 350.6 363.7 375.6 386.1 395.0
08 |  49.8  70.8  91.5 116.2 138.4 163.3 185.5 208.8 230.0 251.3 270.9 289.2 306.5 322.9 338.3 352.6 365.7 377.6 388.1 397.0 404.1
09 |  69.6  90.0 114.5 136.7 161.5 183.6 206.9 228.0 249.4 269.3 288.6 306.5 323.3 339.2 354.1 367.7 379.6 390.1 399.0 406.1 411.4
10 |  88.6 112.9 134.9 159.6 181.7 204.9 226.1 247.4 267.3 286.6 305.1 322.5 338.8 354.0 368.2 381.1 392.1 400.9 408.1 413.4 417.1
11 | 105.5 133.2 157.8 179.8 203.0 224.1 245.4 265.3 284.6 303.1 320.6 337.4 353.0 367.5 380.9 392.9 402.9 410.1 415.4 419.1 419.8
12 | 121.0 151.4 177.8 201.1 222.2 243.4 263.4 282.6 301.1 318.6 335.4 351.2 366.1 379.8 392.3 403.3 412.1 417.4 421.0 421.7 418.1
13 | 135.7 168.4 196.3 220.2 241.5 261.4 280.6 299.1 316.6 333.4 349.2 364.1 377.8 390.5 402.0 411.8 419.3 423.0 423.7 420.0 413.0
14 | 150.2 184.9 213.8 238.2 259.4 278.6 297.1 314.6 331.4 347.2 362.1 375.8 388.6 400.0 409.8 417.9 423.8 425.7 422.0 414.9 402.4
15 | 164.3 200.8 230.7 255.2 276.3 295.1 312.6 329.4 345.2 360.1 373.8 386.6 398.0 407.8 415.9 421.8 424.1 424.0 416.9 404.3 384.3
16 | 178.1 216.3 246.9 271.6 292.3 310.6 327.4 343.3 358.1 371.8 384.6 396.0 405.8 413.9 419.8 422.1 422.0 415.4 406.1 386.1 362.3
17 | 191.4 231.1 262.4 287.1 307.4 325.2 341.3 356.1 369.8 382.6 394.0 403.8 411.9 417.8 420.2 420.1 413.4 404.3 385.2 364.1 329.2
18 | 203.9 245.1 276.9 301.5 321.5 338.6 353.9 367.8 380.6 392.0 401.9 409.9 415.9 418.2 418.1 411.5 402.4 383.4 362.4 329.3 296.1
19 | 215.2 257.6 289.9 314.4 333.8 350.2 364.6 377.6 389.3 399.5 408.0 413.9 416.2 416.2 409.6 400.5 381.6 360.6 327.7 294.7 250.9
20 | 224.4 267.8 300.2 324.4 343.2 358.8 372.3 384.2 394.6 403.4 410.2 414.3 414.2 407.7 398.6 379.8 358.9 326.1 293.2 249.6 196.2
----------------------------------------------------------------------------------------------------------------------------------
Policy_3
-------------------------------------------------------------------
   | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
00 |  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
01 |  1  0  0 -1 -1 -2 -2 -2 -3 -3 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5
02 |  1  1  0  0 -1 -1 -1 -2 -2 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5 -5 -5
03 |  2  1  1  0  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -4 -4 -5 -5 -5 -5
04 |  2  2  1  1  0  0  0 -1 -1 -2 -2 -2 -3 -3 -3 -3 -4 -4 -4 -4 -5
05 |  3  2  2  1  1  0  0  0 -1 -1 -1 -2 -2 -2 -2 -3 -3 -3 -3 -4 -4
06 |  3  3  2  2  1  1  1  0  0  0 -1 -1 -1 -1 -2 -2 -2 -2 -3 -3 -4
07 |  4  3  3  2  2  2  1  1  0  0  0  0  0 -1 -1 -1 -1 -2 -2 -3 -4
08 |  4  4  3  3  3  2  2  1  0  0  0  0  0  0  0  0 -1 -1 -2 -3 -4
09 |  5  4  4  4  3  3  2  1  1  0  0  0  0  0  0  0  0 -1 -2 -3 -3
10 |  5  5  5  4  4  3  2  2  1  1  0  0  0  0  0  0  0 -1 -2 -2 -3
11 |  5  5  5  5  4  3  3  2  2  1  0  0  0  0  0  0  0 -1 -1 -2 -3
12 |  5  5  5  5  4  4  3  3  2  1  1  0  0  0  0  0  0  0 -1 -2 -3
13 |  5  5  5  5  5  4  4  3  2  2  1  1  0  0  0  0  0  0 -1 -2 -2
14 |  5  5  5  5  5  5  4  3  3  2  2  1  1  1  1  0  0  0 -1 -1 -2
15 |  5  5  5  5  5  5  4  4  3  3  2  2  2  2  1  1  0  0  0 -1 -1
16 |  5  5  5  5  5  5  5  4  4  3  3  3  3  2  2  1  1  0  0  0 -1
17 |  5  5  5  5  5  5  5  5  4  4  4  4  3  3  2  2  1  1  0  0  0
18 |  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  1  0  0
19 |  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  1  0
20 |  5  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  0
-------------------------------------------------------------------
最適状態価値関数
----------------------------------------------------------------------------------------------------------------------------------
   |    00    01    02    03    04    05    06    07    08    09    10    11    12    13    14    15    16    17    18    19    20
----------------------------------------------------------------------------------------------------------------------------------
00 |   0.0   0.1   0.7   2.2   5.5  12.0  20.9  35.2  50.5  70.8  90.9 112.9 134.9 155.0 173.8 191.8 209.1 225.9 242.2 257.7 272.5
01 |   0.1   0.7   2.3   5.7  12.3  21.5  36.0  51.5  72.1  92.4 114.5 136.7 157.8 179.8 200.1 219.1 237.4 254.9 271.6 287.7 302.7
02 |   0.7   2.2   5.9  12.7  22.0  36.8  52.5  73.4  93.8 116.2 138.4 159.6 181.7 202.0 222.0 241.5 260.0 277.5 294.3 310.1 325.0
03 |   2.1   5.7  12.3  22.6  37.6  53.6  74.7  95.3 117.8 140.1 161.5 183.6 203.9 224.0 243.5 261.9 279.5 296.5 312.9 328.3 342.6
04 |   5.5  12.0  22.0  36.8  53.9  76.0  96.7 119.4 141.9 163.3 185.5 205.8 225.9 245.5 263.9 281.5 298.5 314.9 330.3 344.6 357.7
05 |  11.6  21.5  36.0  52.9  74.7  95.8 121.0 143.6 165.1 187.4 207.7 227.9 247.4 265.9 283.4 300.5 316.9 332.3 346.6 359.7 371.6
06 |  20.9  35.2  51.9  73.4  94.4 119.4 141.9 167.0 189.3 209.7 229.9 249.4 267.9 285.4 302.5 318.9 334.3 348.6 361.7 373.6 384.1
07 |  34.4  50.8  72.1  92.9 117.8 140.1 165.1 187.4 210.7 231.8 251.4 269.8 287.4 304.5 320.9 336.3 350.6 363.7 375.6 386.1 395.0
08 |  49.8  70.8  91.5 116.2 138.4 163.3 185.5 208.8 230.0 251.3 270.9 289.2 306.5 322.9 338.3 352.6 365.7 377.6 388.1 397.0 404.1
09 |  69.6  90.0 114.5 136.7 161.5 183.6 206.9 228.0 249.4 269.3 288.6 306.5 323.3 339.2 354.1 367.7 379.6 390.1 399.0 406.1 411.4
10 |  88.6 112.9 134.9 159.6 181.7 204.9 226.1 247.4 267.3 286.6 305.1 322.5 338.8 354.0 368.2 381.1 392.1 400.9 408.1 413.4 417.1
11 | 105.5 133.2 157.8 179.8 203.0 224.1 245.4 265.3 284.6 303.1 320.6 337.4 353.0 367.5 380.9 392.9 402.9 410.1 415.4 419.1 419.8
12 | 121.0 151.4 177.8 201.1 222.2 243.4 263.4 282.6 301.1 318.6 335.4 351.2 366.1 379.8 392.3 403.3 412.1 417.4 421.0 421.7 418.1
13 | 135.7 168.4 196.3 220.2 241.5 261.4 280.6 299.1 316.6 333.4 349.2 364.1 377.8 390.5 402.0 411.8 419.3 423.0 423.7 420.0 413.0
14 | 150.2 184.9 213.8 238.2 259.4 278.6 297.1 314.6 331.4 347.2 362.1 375.8 388.6 400.0 409.8 417.9 423.8 425.7 422.0 414.9 402.4
15 | 164.3 200.8 230.7 255.2 276.3 295.1 312.6 329.4 345.2 360.1 373.8 386.6 398.0 407.8 415.9 421.8 424.1 424.0 416.9 404.3 384.3
16 | 178.1 216.3 246.9 271.6 292.3 310.6 327.4 343.3 358.1 371.8 384.6 396.0 405.8 413.9 419.8 422.1 422.0 415.4 406.1 386.1 362.3
17 | 191.4 231.1 262.4 287.1 307.4 325.2 341.3 356.1 369.8 382.6 394.0 403.8 411.9 417.8 420.2 420.1 413.4 404.3 385.2 364.1 329.2
18 | 203.9 245.1 276.9 301.5 321.5 338.6 353.9 367.8 380.6 392.0 401.9 409.9 415.9 418.2 418.1 411.5 402.4 383.4 362.4 329.3 296.1
19 | 215.2 257.6 289.9 314.4 333.8 350.2 364.6 377.6 389.3 399.5 408.0 413.9 416.2 416.2 409.6 400.5 381.6 360.6 327.7 294.7 250.9
20 | 224.4 267.8 300.2 324.4 343.2 358.8 372.3 384.2 394.6 403.4 410.2 414.3 414.2 407.7 398.6 379.8 358.9 326.1 293.2 249.6 196.2
----------------------------------------------------------------------------------------------------------------------------------
最適方策
-------------------------------------------------------------------
   | 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
-------------------------------------------------------------------
00 |  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
01 |  1  0  0 -1 -1 -2 -2 -2 -3 -3 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5 -5
02 |  1  1  0  0 -1 -1 -1 -2 -2 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5 -5 -5
03 |  2  1  1  0  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -4 -4 -5 -5 -5 -5
04 |  2  2  1  1  0  0  0 -1 -1 -2 -2 -2 -3 -3 -3 -3 -4 -4 -4 -4 -5
05 |  3  2  2  1  1  0  0  0 -1 -1 -1 -2 -2 -2 -2 -3 -3 -3 -3 -4 -4
06 |  3  3  2  2  1  1  1  0  0  0 -1 -1 -1 -1 -2 -2 -2 -2 -3 -3 -4
07 |  4  3  3  2  2  2  1  1  0  0  0  0  0 -1 -1 -1 -1 -2 -2 -3 -4
08 |  4  4  3  3  3  2  2  1  0  0  0  0  0  0  0  0 -1 -1 -2 -3 -4
09 |  5  4  4  4  3  3  2  1  1  0  0  0  0  0  0  0  0 -1 -2 -3 -3
10 |  5  5  5  4  4  3  2  2  1  1  0  0  0  0  0  0  0 -1 -2 -2 -3
11 |  5  5  5  5  4  3  3  2  2  1  0  0  0  0  0  0  0 -1 -1 -2 -3
12 |  5  5  5  5  4  4  3  3  2  1  1  0  0  0  0  0  0  0 -1 -2 -3
13 |  5  5  5  5  5  4  4  3  2  2  1  1  0  0  0  0  0  0 -1 -2 -2
14 |  5  5  5  5  5  5  4  3  3  2  2  1  1  1  1  0  0  0 -1 -1 -2
15 |  5  5  5  5  5  5  4  4  3  3  2  2  2  2  1  1  0  0  0 -1 -1
16 |  5  5  5  5  5  5  5  4  4  3  3  3  3  2  2  1  1  0  0  0 -1
17 |  5  5  5  5  5  5  5  5  4  4  4  4  3  3  2  2  1  1  0  0  0
18 |  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  1  0  0
19 |  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  1  0
20 |  5  5  5  5  5  5  5  5  5  5  5  5  5  4  4  3  3  2  2  1  0
-------------------------------------------------------------------

なお、Rubyなので、けっこう時間がかかる（＾＾；
（というか、毎回確率を計算しているのがよくない感じか・・・→（追記）確率をキャッシュするようにしたら、大分速くなった）

本だともっと際に寄る感じになっているけれど、これはおそらく方策評価の終了判定に使う $\varepsilon$ の値が本だともっと小さいのだと思う。
（自分の書いたプログラムだと0.1としている）
この値をもっと小さくすれば本と同じような結果になると思うけど、その分時間もかかるので、Rubyだとちょっと大変かな。

今日はここまで！