Python - 強化学習(マルコフ決定過程)のコードリーディング

強化学習のメモ

このQiita記事に従って触っていたものの、コードを前にハテナがいくつか浮かんだので、解釈した結果をメモ。
qiita.com

サンプルコード群 By UC Berkeley
github.com

以下、掲題の通り、マルコフ決定過程のサンプルコードに関する解釈です。
https://github.com/aimacode/aima-python/blob/master/mdp.py

サンプルコードの実行方法

• ドキュメントにある通り

$ python
Python 3.4.6 (default, Feb  8 2017, 16:33:17)
[GCC 4.2.1 Compatible Apple LLVM 8.0.0 (clang-800.0.42.1)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import mdp
>>> print(mdp.__doc__)
Markov Decision Processes (Chapter 17)

First we define an MDP, and the special case of a GridMDP, in which
states are laid out in a 2-dimensional grid.  We also represent a policy
as a dictionary of {state:action} pairs, and a Utility function as a
dictionary of {state:number} pairs.  We then define the value_iteration
and policy_iteration algorithms.
>>> pi = best_policy(sequential_decision_environment, value_iteration(sequential_decision_environment, .01))

>>> sequential_decision_environment.to_arrows(pi)
[['>', '>', '>', '.'], ['^', None, '^', '.'], ['^', '>', '^', '<']]

>>> print_table(sequential_decision_environment.to_arrows(pi))
>   >      >   .
^   None   ^   .
^   >      ^   <

>>> print_table(sequential_decision_environment.to_arrows(policy_iteration(sequential_decision_environment)))
>   >      >   .
^   None   ^   .
^   >      ^   <

>>>

• ファイルから実行するならこんな感じ

from mdp import *

// これは定義済みなので不要ではある。自由にいじって実行結果を確認できる。
sequential_decision_environment = GridMDP([[-0.04, -0.04, -0.04, +1],
    [-0.04, None,  -0.04, -1],
    [-0.04, -0.04, -0.04, -0.04]],
    terminals=[(3, 2), (3, 1)])

pi = best_policy(sequential_decision_environment, value_iteration(sequential_decision_environment, .01))

print_table(sequential_decision_environment.to_arrows(pi))

問題のコードリーディング

この関数が鍵で、
https://github.com/aimacode/aima-python/blob/master/mdp.py#L112

特にここが肝。
https://github.com/aimacode/aima-python/blob/master/mdp.py#L120

以下、自分なり解釈(大学生くらいが分かる言葉で書く。そもそも数学的素養はそこまで高くない)。

  while true:
         U = U1.copy()
         delta = 0
         for s in mdp.states:
              U1[s] = R(s) + gamma * max([sum([p * U[s1] for (p, s1) in T(s, a)])
                                        for a in mdp.actions(s)])
+            # ある地点(state)において実行し得る、各行動について:　for a in mdp.actions(s)
+            # それぞれ実行し(1マスの移動(3方向)を計算し)、その結果得られる各マスとそこへの移動確率のペアをもとに:  for (p, s1) in T(s, a)
+            # 移動先のマスへの移動確率を加重: p * U[s1]
+            # 行動ごと計算していたのを合計し、その中で、もっとも取り得る確率が高いものを選択: max(sum[ ~ in mdp.actions(s)])
+            # 現在地の報酬に、その"取り得る確率"を薄めた(*gammaした)ものを加算し、そのマスの新たな"取り得る確率 = 移動確率"とする。
+            # この処理を、変化率が特定の閾値を切るまで(雑に言うとゼロに近づくまで)繰り返す。
             delta = max(delta, abs(U1[s] - U[s]))
         if delta < epsilon * (1 - gamma) / gamma:
             return U

とりあえず、メモはここまで。
要するに、この例では、とあるマスから次に進む可能性が高いのはどこかを突き止めて行って、
その移動過程や、ゴールにおける報酬(合計スコア)が低い手ほど、評価が落ちていくので
次第により高報酬 = 適切に正解ルートを辿れる手がとれるようになるってことだと理解した。