強化学習シリーズ8:モデルなしのタイミング差分法

1.計算式の変更
モンテカルロ法の計算式は以下の通りである:q i=r 0+γ r 1 i + γ 2 r 2 i . . . q^i = r_0+\gamma r^i_1+\gamma ^2r^i_2... qi=r0​+γr1i​+γ2r2i​... Q i=Q i−1+1 i(q i−Q i−1)Q^i=Q^{i−1}+frac{1}{i}(q^i−Q^{i−1})Qi=Qi−1+i 1(qi−Qi−1)q i q^i qiは長期的なリターンを計算するため、分散が大きい.ここではタイミング差分法を用いてQ Qを計算し,分散問題を低減する.式は、q i=r i−1+γ π Q i − 1 q^i=r^{i-1}+\gamma\pi Q^{i-1} qi=ri−1+γπQi−1 Q i = Q i − 1 + 1 i ( q i − Q i − 1 ) Q^i=Q^{i-1}+\frac{1}{i}(q^i-Q^{i-1}) Qi=Qi−1+i1​(qi−Qi−1)
SARSはサンプリング戦略の次の時間のQ Q Qを用いてサンプリングq q q値を推定し,on−policyアルゴリズムである.SARSでは,戦略πpiπはサンプリング時に用いられる戦略を採用している.Q−Liarningは新しい戦略の次の時間のQを用いてサンプリングq q q値を推定し,off−policyアルゴリズムである.この新しい戦略は一般的に使われている.ϵ\epsilon ϵ-greedyポリシー.Q-learningはq q qを計算する際にポリシーに最適max⁡maxポリシーを使用し、実際のインタラクションの値の代わりに最適価値行動を使用するため、値関数に「過大推定」の問題が発生する.また、最適ポリシーを使用すると、q q値の一部が永遠に更新されないため、ポリシーにランダム要素を加える必要がある.ϵ\epsilon ϵ探求に使われていますQ−Liarningでは2つのモデルに関連した:1つのモデルをサンプリングに用い,一連のs s,a a a,q qを得た.1つのモデルを計算に用い,更新ポリシーのためのq q値を得た.ここでの2つのモデルはそれぞれBehavior NetworkとTarget Networkと呼ばれています.変動を低減するために、Target Networkのポリシーは、一定の回数後にBehavior Networkから更新されるまで一定の期間保持されるように設定できます.
2.コード実装

class SARSA(object):
    def __init__(self, epsilon=0.0):
        self.epsilon = epsilon

    def sarsa_eval(self, agent, env):
        #sarsa
        state = env.reset()
        prev_state = -1
        prev_act = -1
        while True:
            act = agent.play(state, self.epsilon)
            next_state, reward, terminate, _ = env.step(act)
            if prev_act != -1:
                #every visit
                return_val = reward + agent.gamma * (0 if terminate else agent.value_q[state][act])
                agent.value_n[prev_state][prev_act] += 1
                agent.value_q[prev_state][prev_act] += (return_val - \
                    agent.value_q[prev_state][prev_act]) / \
                    agent.value_n[prev_state][prev_act]
            prev_act = act  
            prev_state = state
            state = next_state
            if terminate:
                break

    def policy_improve(self, agent):
        new_policy = np.zeros_like(agent.pi)
        for i in range(1, agent.s_len):
            new_policy[i] = np.argmax(agent.value_q[i,:])
        if np.all(np.equal(new_policy, agent.pi)):
            return False
        else:
            agent.pi = new_policy
            return True

    # monte carlo
    def sarsa(self, agent, env):
        for i in range(10):
            for j in range(2000):
                self.sarsa_eval(agent, env)
            self.policy_improve(agent)

class QLearning(object):
    def __init__(self, epsilon=0.0):
        self.epsilon = epsilon

    def q_learn_eval(self, agent, env):
        state = env.reset()
        prev_state = -1
        prev_act = -1
        while True:
            act = agent.play(state, self.epsilon)
            next_state, reward, terminate, _ = env.step(act)
            if prev_act != -1:
                return_val = reward + agent.gamma * (0 if terminate else np.max(agent.value_q[state,:]))
                agent.value_n[prev_state][prev_act] += 1
                agent.value_q[prev_state][prev_act] += (return_val - \
                    agent.value_q[prev_state][prev_act]) / \
                    agent.value_n[prev_state][prev_act]
            prev_act = act  
            prev_state = state
            state = next_state
            if terminate:
                break
                
    def policy_improve(self, agent):
        new_policy = np.zeros_like(agent.pi)
        for i in range(1, agent.s_len):
            new_policy[i] = np.argmax(agent.value_q[i,:])
        if np.all(np.equal(new_policy, agent.pi)):
            return False
        else:
            agent.pi = new_policy
            return True

    # q learning
    def q_learning(self, agent, env):
        for i in range(10):
            for j in range(3000):
                self.q_learn_eval(agent, env)
            self.policy_improve(agent)

アルゴリズムの効果を見て、ポリシー評価フェーズの反復回数を3000回に調整します.

ladders info:
{18: 31, 99: 58, 17: 40, 92: 37, 72: 37, 12: 55, 21: 52, 44: 82, 6: 31, 98: 56, 31: 6, 58: 99, 40: 17, 37: 72, 55: 12, 52: 21, 82: 44, 56: 98}
Timer MonteCarlo COST:14.503098726272583
return_pi=22
SARSA COST:17.623368978500366
return_pi=61
Q Learning COST:33.774227142333984
return_pi=90

ladders info:
{72: 57, 29: 17, 57: 72, 62: 20, 84: 75, 28: 8, 75: 84, 51: 69, 68: 6, 53: 31, 20: 62, 17: 29, 49: 84, 8: 28, 69: 51, 6: 68, 31: 53}
Timer MonteCarlo COST:4.651626825332642
return_pi=64
SARSA COST:5.257284879684448
return_pi=34
Q Learning COST:8.114835023880005
return_pi=67

全体的にはQ Learningが最も長く、効果も最高です.