いものやま。

雑多な知識の寄せ集め

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

技術 AI 強化学習 Ruby

昨日は方策反復について説明し、実際にプログラムも書いてみた。

今日はもう一つのアルゴリズムについて説明する。

価値反復

方策反復の場合、方策評価の中で何度もスイープを行うので、方策改善が行われるまでに時間がかかる。
なら、1回スイープを行うごとに方策改善が出来ないか、というのが、もう一つのアルゴリズムの基本的な考え方となる。

スイープを行うごとに方策改善を行うのだから、つまり、方策評価で

 { \displaystyle
V^{(k+1)}_s = \sum_{s' \in \mathcal{S}} \mathcal{P}^{\pi(s)}_{ss'} \left( \mathcal{R}^{\pi(s)}_{ss'} + \gamma V^{(k)}_{s'} \right)
}

と更新していたところを、

 { \displaystyle
V^{(k+1)}_s = \mathop{\mbox{max}}_{a \in \mathcal{A}(s)} \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \left( \mathcal{R}^a_{ss'} + \gamma V^{(k)}_{s'} \right)
}

で更新することになる。
（方策はスイープ毎に \pi(s) = \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^{(k)}_{s'} \right)と更新されるので）

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

  1. 初期化
    1. すべての s \in \mathcal{S}について、 V_s \in \mathbb{R}を任意の値で初期化。
  2. 方策評価（&方策改善）
    1. 以下を繰り返す：
      1. \Delta \leftarrow 0
      2. 各 s \in \mathcal{S}について：
        1. v \leftarrow V_s
        2. V_s \leftarrow \mathop{\mbox{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. \Delta \leftarrow \mbox{max} \left\{ \Delta, \left| V_s - v \right| \right\}
      3. \Delta \lt \varepsilon（ \varepsilonは十分小さい正の定数）なら、繰り返しを終了。
  3. 方策出力
    1. 方策 \piを次のように出力：
      \pi(s) = \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)

このアルゴリズムは、価値反復（value iteration）と呼ばれている。
（これはおそらく、アルゴリズムが状態価値の更新だけを行っているように見えるからだと思う）

Rubyによる実装

昨日のレンタカー問題を、価値反復で解いてみる。

価値反復

昨日のコードに加えて、次のコードを用意する。

#!/usr/bin/env ruby

#====================
# value_iteration_method.rb
#====================

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

module RentalCarProblem
  # 価値反復法
  class ValueIterationMethod
    def initialize(value, policy, verbose=false)
      @value = value
      @policy = policy
      @verbose = verbose
    end

    attr_reader :value, :policy

    @@delta_max = 0.1

    # 価値反復法を行う
    def execute
      i = 0
      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_policy, new_value = @value.get_most_valuable_move(x, y, *((-MOVE_MAX..MOVE_MAX).to_a))

            @value.set(x, y, new_value)
            @policy.set(x, y, new_policy)

            delta = [delta, (new_value - old_value).abs].max
          end
        end

        if @verbose
          puts "Value_#{i}"
          @value.print
          puts "Policy_#{i}"
          @policy.print
        end

        if delta < @@delta_max
          break
        else
          i += 1
        end
      end
    end
  end
end

if __FILE__ == $PROGRAM_NAME
  include RentalCarProblem

  value = StatusValue.new
  policy = Policy.new
  value_iteration = ValueIterationMethod.new(value, policy, true)

  value_iteration.execute

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

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

実行例

これを実行すると、次のような感じ。

$ ./value_iteration_method.rb
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.0   0.2   1.0   2.6   5.9  10.0  16.8  23.2  30.7  37.1  42.4  47.1  49.8  51.1  51.7  52.0  52.1  52.1  52.1  52.1
01 |   0.0   0.3   1.1   2.8   6.3  10.6  17.7  24.4  32.1  38.8  44.2  49.2  52.0  54.4  55.8  56.5  56.8  57.0  57.1  57.1  57.1
02 |   0.3   1.0   3.0   6.7  11.3  18.8  26.0  34.0  41.2  46.6  51.9  55.1  57.1  58.8  59.6  60.1  60.4  60.6  60.8  60.8  60.8
03 |   1.0   2.9   6.6  12.1  20.2  28.0  36.5  44.6  50.3  56.1  59.9  62.4  64.0  65.1  65.9  66.5  67.0  67.3  67.5  67.4  66.8
04 |   2.9   6.7  12.2  20.4  28.8  39.8  49.0  55.8  61.9  66.8  70.1  72.4  74.2  75.5  76.5  77.3  77.8  78.1  78.1  77.4  75.4
05 |   6.9  12.6  21.2  30.0  41.4  51.4  60.8  69.2  75.2  79.6  82.8  85.2  87.1  88.5  89.6  90.4  90.8  90.8  90.0  87.7  85.4
06 |  13.2  22.3  31.6  43.6  54.4  64.4  74.0  81.0  86.2  90.9  94.4  97.1  99.1 100.7 101.8 102.7 103.2 103.1 102.1  99.3  93.3
07 |  23.3  33.0  46.0  57.5  68.6  79.0  86.9  93.3  99.0 103.3 106.5 109.0 110.9 112.4 113.4 114.0 114.0 112.7 110.6 107.4 100.7
08 |  34.2  47.9  59.9  72.6  83.7  92.1 100.4 106.8 111.6 115.3 118.2 120.3 122.0 123.1 123.8 124.1 123.8 122.3 118.3 113.4 106.2
09 |  48.9  61.2  75.6  87.2  97.4 106.7 113.5 118.7 123.0 126.7 129.5 131.6 133.2 134.3 134.8 134.4 132.5 129.8 125.3 118.3 110.5
10 |  62.1  77.1  88.9 101.4 111.1 118.7 125.7 130.9 134.9 137.9 140.2 141.9 143.0 143.4 143.7 143.1 140.7 136.0 130.9 122.4 114.0
11 |  73.4  90.3 103.5 113.6 123.7 131.0 136.5 141.5 145.3 148.2 150.3 151.9 152.8 153.0 152.1 150.4 147.5 141.5 135.7 126.0 117.1
12 |  83.4 101.9 116.0 126.2 134.9 142.3 147.6 151.6 154.8 157.5 159.4 160.7 161.4 161.3 159.9 156.9 153.5 146.8 139.9 129.2 119.7
13 |  92.8 112.5 127.3 137.8 145.5 152.7 157.8 161.6 164.3 166.3 167.8 168.9 169.2 168.7 166.9 162.9 158.8 151.4 143.6 132.3 122.0
14 | 101.8 122.7 138.0 148.6 156.0 162.6 167.5 170.9 173.4 175.1 176.1 176.4 176.4 175.5 173.1 168.5 163.5 155.5 146.8 135.0 123.9
15 | 110.6 132.5 148.2 158.9 166.2 171.9 176.5 179.7 181.9 183.4 184.0 183.9 183.0 181.6 178.8 173.6 167.6 159.1 149.6 137.3 125.3
16 | 119.0 141.8 158.0 168.7 175.8 180.7 185.1 188.0 189.9 191.0 191.3 190.8 189.2 187.2 183.8 178.0 171.3 162.2 151.8 139.0 126.0
17 | 127.0 150.8 167.3 178.0 184.9 189.4 193.2 195.8 197.4 198.2 198.1 197.1 195.0 192.1 188.3 181.9 174.3 164.7 153.1 139.9 125.3
18 | 134.6 159.2 176.0 186.8 193.5 197.7 200.7 203.1 204.3 204.7 204.2 202.8 200.2 196.4 192.0 185.1 176.3 166.2 153.0 139.4 122.5
19 | 141.7 167.1 184.2 195.0 201.5 205.4 207.7 209.6 210.5 210.5 209.6 207.7 204.6 199.7 194.7 187.3 176.7 166.1 150.5 136.7 116.8
20 | 148.3 174.4 191.8 202.5 208.9 212.5 214.5 215.3 215.7 215.3 214.0 211.6 207.9 202.5 195.7 187.8 175.9 163.7 147.7 131.0 108.2
----------------------------------------------------------------------------------------------------------------------------------
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 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5
01 |  1  0  0 -1 -1 -1 -2 -2 -3 -3 -4 -4 -4 -5 -5 -5 -5 -5 -5 -5 -5
02 |  1  1  0  0  0 -1 -1 -2 -2 -3 -3 -3 -4 -4 -4 -4 -4 -4 -4 -4 -4
03 |  2  1  1  0  0  0 -1 -1 -1 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2 -2
04 |  2  2  1  1  0  0  0  0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
05 |  3  2  2  2  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0 -1 -1
06 |  3  3  3  2  2  1  1  1  1  0  0  0  0  0  0  0  0  0  0  0  0
07 |  4  4  3  3  2  2  2  1  1  1  1  1  1  1  1  1  1  1  0  0  0
08 |  4  4  4  3  3  3  2  2  2  2  2  2  2  2  2  1  1  1  1  0  0
09 |  5  5  4  4  3  3  3  3  2  2  2  2  2  2  2  2  2  1  1  0  0
10 |  5  5  5  4  4  3  3  3  3  3  3  3  3  3  2  2  2  1  1  0  0
11 |  5  5  5  4  4  4  4  3  3  3  3  3  3  3  3  2  2  2  1  0  0
12 |  5  5  5  5  4  4  4  4  3  3  3  3  3  3  3  2  2  2  1  1  0
13 |  5  5  5  5  4  4  4  4  4  4  3  3  3  3  3  3  2  2  1  1  0
14 |  5  5  5  5  5  4  4  4  4  4  4  3  3  3  3  3  2  2  1  1  0
15 |  5  5  5  5  5  4  4  4  4  4  4  4  3  3  3  3  2  2  1  1  0
16 |  5  5  5  5  5  4  4  4  4  4  4  4  4  3  3  3  2  2  1  1  0
17 |  5  5  5  5  5  5  4  4  4  4  4  4  4  3  3  3  2  2  1  1  0
18 |  5  5  5  5  5  5  4  4  4  4  4  4  4  3  3  3  2  2  1  1  0
19 |  5  5  5  5  5  5  5  4  4  4  4  4  4  4  3  3  2  2  1  1  0
20 |  5  5  5  5  5  5  5  5  4  4  4  4  4  4  3  3  3  2  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.5   1.7   4.2   9.3  16.1  26.9  37.8  52.5  65.4  80.2  92.3 101.6 108.6 114.0 118.3 121.6 124.1 126.0 127.3
01 |   0.1   0.5   1.7   4.4   9.6  16.7  27.8  38.9  53.9  67.0  81.9  94.2 107.3 117.4 124.9 130.7 135.1 138.5 141.1 143.1 144.4
02 |   0.5   1.7   4.6  10.0  17.3  28.7  40.2  55.5  69.0  84.0  96.6 109.5 120.2 130.8 138.6 144.4 148.8 152.2 154.8 156.6 157.8
03 |   1.6   4.5   9.8  18.1  29.9  41.8  57.4  71.5  86.6  99.7 112.4 123.1 133.5 142.9 150.6 156.3 160.6 163.9 166.3 168.0 169.0
04 |   4.4   9.7  17.8  29.6  43.0  59.8  74.5  89.8 103.8 116.2 127.5 137.3 145.8 154.1 161.8 167.3 171.4 174.4 176.6 178.0 178.6
05 |   9.6  17.7  29.6  42.9  59.9  75.6  93.7 108.5 120.9 133.2 142.8 151.4 158.6 165.2 172.3 177.6 181.3 184.1 185.9 187.0 187.3
06 |  17.7  29.7  43.0  60.3  76.0  94.6 110.0 126.3 139.4 150.1 159.0 166.6 173.3 178.8 183.4 187.3 190.7 193.1 194.6 195.3 195.1
07 |  29.6  43.2  60.7  76.7  95.7 111.7 128.3 142.2 155.4 166.4 175.3 182.8 189.1 194.4 198.8 202.2 204.5 205.2 203.1 203.0 202.4
08 |  43.1  60.8  77.1  96.6 113.1 130.3 144.9 158.5 170.3 180.5 189.3 196.5 202.5 207.5 211.5 214.5 216.3 216.3 213.3 209.9 208.8
09 |  60.3  77.2  96.9 113.6 131.8 146.9 161.4 173.8 184.7 194.3 202.2 208.9 214.4 219.0 222.5 225.0 226.2 225.6 221.9 215.8 214.2
10 |  76.7  96.4 113.8 132.4 147.8 163.6 176.5 188.5 198.7 207.2 214.7 221.0 226.1 230.1 233.1 234.6 235.1 233.8 229.4 222.3 217.8
11 |  90.9 113.4 132.1 148.6 164.7 178.5 191.4 202.0 211.8 219.9 226.6 232.1 236.7 240.3 242.7 243.7 243.2 241.3 236.1 228.2 219.8
12 | 103.7 128.3 148.4 164.6 179.7 192.9 205.0 215.2 224.0 231.6 237.8 242.9 246.8 249.6 251.5 251.9 250.5 248.0 242.1 233.3 223.7
13 | 115.8 142.1 163.1 179.7 193.7 206.7 217.8 227.6 235.6 242.6 248.3 252.9 256.3 258.5 259.6 259.4 257.1 253.9 247.4 237.4 226.0
14 | 127.5 155.2 177.0 193.7 206.9 219.6 229.9 239.2 246.7 252.9 258.1 262.2 265.1 266.8 266.9 266.1 263.2 258.8 251.6 239.8 226.9
15 | 138.9 167.9 190.2 207.0 219.9 231.8 241.4 250.2 257.2 262.7 267.1 270.7 273.0 274.2 273.7 271.7 268.2 261.9 254.1 240.7 225.8
16 | 149.8 180.1 202.8 219.6 232.1 243.3 252.4 260.3 266.8 271.8 275.6 278.3 279.9 280.4 279.4 276.0 271.3 263.5 253.4 239.5 219.8
17 | 160.2 191.6 214.8 231.5 243.7 253.9 262.6 269.4 275.3 279.8 283.1 285.1 285.9 285.0 283.1 279.0 271.0 262.6 248.2 233.0 211.3
18 | 169.9 202.4 226.0 242.5 254.4 263.4 271.7 277.9 282.6 286.0 288.5 290.0 290.1 288.5 284.5 278.4 269.8 255.9 241.2 218.7 197.7
19 | 178.8 212.1 236.0 252.5 264.0 272.3 278.8 284.4 288.6 291.4 293.0 293.2 291.6 288.4 283.5 274.6 262.5 247.2 226.2 204.0 175.4
20 | 186.1 220.2 244.2 260.5 271.5 279.4 285.1 289.3 292.2 293.8 294.1 293.5 291.2 286.1 277.0 266.8 250.9 231.3 208.2 180.7 145.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 -5 -5 -5 -5 -5 -5 -5 -5 -5
03 |  2  1  1  0  0  0 -1 -1 -2 -2 -3 -3 -4 -5 -5 -5 -5 -5 -5 -5 -5
04 |  2  2  1  1  0  0  0 -1 -1 -2 -2 -3 -4 -5 -5 -5 -5 -5 -5 -5 -5
05 |  3  2  2  1  1  0  0  0 -1 -1 -1 -2 -2 -4 -5 -5 -5 -5 -5 -5 -5
06 |  3  3  2  2  1  1  1  0  0  0  0 -1 -1 -1 -1 -5 -5 -5 -5 -5 -5
07 |  4  3  3  3  2  2  1  1  0  0  0  0  0  0  0  0  0  0 -1 -5 -5
08 |  4  4  3  3  3  2  2  1  1  0  0  0  0  0  0  0  0  0  0 -5 -5
09 |  5  4  4  4  3  3  2  2  1  1  1  1  0  0  0  0  0  0  0 -1 -5
10 |  5  5  4  4  3  3  3  2  2  1  1  1  1  1  1  1  0  0  0 -1 -5
11 |  5  5  5  4  4  3  3  3  2  2  2  2  1  1  1  1  0  0  0 -1 -3
12 |  5  5  5  5  4  4  3  3  2  2  2  2  2  1  1  1  0  0  0 -1 -2
13 |  5  5  5  5  4  4  3  3  3  2  2  2  2  2  1  1  1  0  0 -1 -2
14 |  5  5  5  5  5  4  3  3  3  2  2  2  2  2  2  1  1  0  0 -1 -1
15 |  5  5  5  5  5  4  4  3  3  3  2  2  2  2  2  1  1  0  0  0 -1
16 |  5  5  5  5  5  4  4  3  3  3  3  3  2  2  2  2  1  1  0  0 -1
17 |  5  5  5  5  5  4  4  4  3  3  3  3  3  3  2  2  2  1  1  0  0
18 |  5  5  5  5  5  4  4  4  4  4  3  3  3  3  3  2  2  1  1  0  0
19 |  5  5  5  5  5  5  4  4  4  4  4  4  4  3  3  3  2  2  1  1  0
20 |  5  5  5  5  5  5  5  5  5  5  4  4  4  4  4  3  3  2  2  1  0
-------------------------------------------------------------------

〜省略〜

Value_14
----------------------------------------------------------------------------------------------------------------------------------
   |    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.8 271.6 287.6 302.7
02 |   0.7   2.2   5.9  12.7  22.0  36.8  52.5  73.4  93.8 116.1 138.4 159.6 181.7 202.0 222.0 241.5 259.9 277.5 294.2 310.1 324.9
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.6 229.9 249.4 267.8 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 394.9
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.8 338.3 352.6 365.7 377.6 388.1 396.9 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 398.9 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.0 419.7
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.2 403.3 412.1 417.4 421.0 421.7 418.0
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.5 400.0 409.8 417.9 423.8 425.7 422.0 414.9 402.3
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 423.9 416.8 404.2 384.3
16 | 178.1 216.3 246.9 271.6 292.3 310.6 327.4 343.2 358.1 371.8 384.6 396.0 405.8 413.9 419.8 422.1 422.0 415.3 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.0 413.4 404.2 385.2 364.0 329.2
18 | 203.9 245.1 276.9 301.5 321.5 338.6 353.9 367.8 380.6 392.0 401.8 409.9 415.9 418.2 418.1 411.5 402.4 383.4 362.3 329.2 296.1
19 | 215.2 257.6 289.9 314.4 333.8 350.2 364.6 377.6 389.3 399.5 407.9 413.9 416.2 416.1 409.6 400.5 381.6 360.6 327.7 294.6 250.8
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.1
----------------------------------------------------------------------------------------------------------------------------------
Policy_14
-------------------------------------------------------------------
   | 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.8 271.6 287.6 302.7
02 |   0.7   2.2   5.9  12.7  22.0  36.8  52.5  73.4  93.8 116.1 138.4 159.6 181.7 202.0 222.0 241.5 259.9 277.5 294.2 310.1 324.9
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.6 229.9 249.4 267.8 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 394.9
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.8 338.3 352.6 365.7 377.6 388.1 396.9 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 398.9 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.0 419.7
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.2 403.3 412.1 417.4 421.0 421.7 418.0
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.5 400.0 409.8 417.9 423.8 425.7 422.0 414.9 402.3
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 423.9 416.8 404.2 384.3
16 | 178.1 216.3 246.9 271.6 292.3 310.6 327.4 343.2 358.1 371.8 384.6 396.0 405.8 413.9 419.8 422.1 422.0 415.3 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.0 413.4 404.2 385.2 364.0 329.2
18 | 203.9 245.1 276.9 301.5 321.5 338.6 353.9 367.8 380.6 392.0 401.8 409.9 415.9 418.2 418.1 411.5 402.4 383.4 362.3 329.2 296.1
19 | 215.2 257.6 289.9 314.4 333.8 350.2 364.6 377.6 389.3 399.5 407.9 413.9 416.2 416.1 409.6 400.5 381.6 360.6 327.7 294.6 250.8
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.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 -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
-------------------------------------------------------------------

最終的に方策反復と同様の結果が得られていることが分かると思う。
（なお、やっぱりめっちゃ時間かかる・・・）

今日はここまで！

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本（ソフトカバー）
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る