強化学習：ノート9 - クッキーの日記

読んでいる本（出典）：強化学習 : Richard S.Sutton, Andrew G.Barto, 三上貞芳, 皆川雅章 : 本 : Amazon.co.jp

今日読んだページ： 93～98ページ
以下、自分の解釈・感想・雑談。

今日から4章。4章は強化学習問題の解き方その1：動的計画法（DP）。

（3章の復習）そもそも強化学習問題って何？それを解くって何？その指針は？
- 強化学習問題とは、エージェントが環境から「状態」と「報酬」を受け取って、それを受けて環境に対して「行動」して、環境からまた次の「状態」と「報酬」を受け取って…とやっていく中でどうすれば「収益（総報酬）」が最大になるでしょうか、という問題。
- それを解くとは、最適な方策（状態から行動への写像）を求めること。
- その指針は、最適な価値関数（状態からその状態の価値への写像）を何らかの方法で求めればよい。
  そして、ある状態の価値を最大にする行動に非ゼロの確率を割り当てる方策 $\pi(s, a)$ を構成すればよい。

DP はその適用条件や計算量から実用的ではない（え、いまから勉強するのに…）。ただし、以降の実用的な解法を理解する上で重要（94ページ）。

有限マルコフ決定過程については、まず何らかの方策を決めておけば、その状態価値関数を逐次的な方法で求めることはできる（反復方策評価：95～97ページ）。

97ページの例 4.1 を計算してみる。
- 4×4の格子世界において、上下左右のどのセル（＝状態）に動くか判断するエージェントがいる。上下左右に完全にランダムに動く方策について、反復方策評価を行う。
  - 端のセルで格子世界の外に出ていくような行動を選んだ場合、次の状態ではそのセルに留まる。
  - 一番左上のセルと一番右下のセルは終端状態。
  - 毎ステップごとに-1の報酬が得られる（つまり、早く終端状態に到達してほしい）。
- 以下のコードで教科書100ページと同じ数値が得られる。
  - この例では3ステップ目で、最適方策を与える価値関数が得られる。つまり、どのセルからスタートしても、状態価値関数がより高いセルに動けば最短経路で一番左上または一番右下のセルに到達できる。

V <- data.frame(
  label=c( 1, 2, 3,  4, 5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 99),
  value=c( 0, 0, 0,  0, 0,  0,  0,  0,  0,   0,  0,  0,  0,  0,  0),
     up=c( 1, 2, 3, 99, 1,  2,  3,  4,  5,   6,  7,  8,  9, 10, NA),
   down=c( 5, 6, 7,  8, 9, 10, 11, 12, 13,  14, 99, 12, 13, 14, NA),
  right=c( 2, 3, 3,  5, 6,  7,  7,  9, 10,  11, 11, 13, 14, 99, NA),
   left=c(99, 1, 2,  4, 4,  5,  6,  8,  8,   9, 10, 12, 12, 13, NA)
)

Update <- function(V, sweep=FALSE) {
  value <- V$value
  for (i in 1:(nrow(V)-1)) { # 終端状態は更新しない
    u <- -1 + V$value[V$label==V$up[[i]]]
    d <- -1 + V$value[V$label==V$down[[i]]]
    r <- -1 + V$value[V$label==V$right[[i]]]
    l <- -1 + V$value[V$label==V$left[[i]]]
    if (sweep) {
      V$value[[i]] <- 0.25 * (u + d + r + l) # その場更新する
    } else {
      value[[i]] <- 0.25 * (u + d + r + l) # その場更新しない
    }
  }
  if (!sweep) {
    V$value <- value
  }
  return(V)
}

print(matrix(c(0, V$value), ncol=4)) # 教科書と同じ配置で出力するために行列にしただけ
for (i in 1:3) {
  V <- Update(V)
  print(matrix(c(0, V$value), ncol=4))
}

     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    0    0    0    0
[3,]    0    0    0    0
[4,]    0    0    0    0
     [,1] [,2] [,3] [,4]
[1,]    0   -1   -1   -1
[2,]   -1   -1   -1   -1
[3,]   -1   -1   -1   -1
[4,]   -1   -1   -1    0
      [,1]  [,2]  [,3]  [,4]
[1,]  0.00 -1.75 -2.00 -2.00
[2,] -1.75 -2.00 -2.00 -2.00
[3,] -2.00 -2.00 -2.00 -1.75
[4,] -2.00 -2.00 -1.75  0.00
        [,1]    [,2]    [,3]    [,4]
[1,]  0.0000 -2.4375 -2.9375 -3.0000
[2,] -2.4375 -2.8750 -3.0000 -2.9375
[3,] -2.9375 -3.0000 -2.8750 -2.4375
[4,] -3.0000 -2.9375 -2.4375  0.0000

格子世界って何…。