MISC

強化学習 - 価値反復法

#未分類

Uは各状態の期待価値の配列。それぞれの状態で最適な行動を実行する前提での状態価値を求める。Rは即時報酬、Tはsのときaによって次のs1に遷移する確率のタプル。gammaは割引率。deltaは、直近のU[s]と1回前のU[s]の差。ただし全てのsの中で最も大きな差を最終的なdeltaとしているので、全てのsにおいて、前回計算時とほぼ変化がなくなったらループを終了させている。あと、ゴール（即時報酬＋１）と、ゲームオーバー（即時報酬ー１）においては、次のアクションをなしに設定しているようだ。この2つの状態sのときには、mdp.actions(s)が空を返すので、毎回R(s)の値がU1[s]に格納されている。

def value_iteration(mdp, epsilon=0.001):
    U1 = {s: 0 for s in mdp.states}
    R, T, gamma = mdp.R, mdp.T, mdp.gamma
    while True:
        U = U1.copy()
        delta = 0
        for s in mdp.states:
            sum_list = []
            for a in mdp.actions(s):
                t = T(s, a)
                tmp = []
                for p, s1 in t:
                    tmp.append(p * U[s1])
                sumnum = sum(tmp)
                sum_list.append(sumnum)
            maxnum = max(sum_list)
            U1[s] = R(s) + gamma * maxnum


            delta = max(delta, abs(U1[s] - U[s]))
        epseps = epsilon * (1 - gamma) / gamma
        if delta < epseps:
            return U

Rは、