【強化学習】Sarsa + Sarsa-lambda（Sarsa（λ））アルゴリズムの詳細

Sarsa Sarsa Lambda Algorithm Detail

Sarsaアルゴリズムの決定部分はQ学習と同じであるため、上記のQ学習式に基づいて次のコンテンツが引き続き導出されます。 Qlearningと非常によく似ているため、説明するのにあまりスペースを費やすことはありません。

1.アルゴリズムのアイデア

Sarsaアルゴリズムの意思決定部分はQlearningと同じであり、意思決定はQテーブルの形式で行われます。大きい方のアクション値がQテーブルで選択され、報酬と罰と引き換えに環境に適用されます。つまり、選択として計算されたQ値に基づいて、アクションの基礎となる2つの違いは次のとおりです。動作の更新基準は異なります。 Sarsaは、推定した最大Q推定値を選択しませんが、推定Q値を直接選択します。

2.動作の更新

たとえば、ジョブを作成する状態s1を実行してから、最大の潜在的な報酬をもたらすアクションa2を選択します。これにより、ジョブs2を作成し続ける状態になります。このステップでは、 Q学習を使用している場合、s2で選択されたアクションが最大の報酬をもたらすかどうかを確認しますが、本当に決定したい場合は、必ずしも最大の報酬をもたらすアクションを選択する必要はありません。このステップでのQ学習は見積もりの​​み次のアクション値。そしてサルサは実践的な学校です、彼はそれをするように言いました、s2ステップで推定された行動はまた行われるべき次の行動です。したがって、Q（s1、a2）の実際の計算値は、少し変更されます。 maxQを削除します 、代わりに私たちは本当にs2にいます a2の選択されたQ値 。最後に、Q学習と同様に、現実と推定の間のギャップを見つけ、QテーブルのQ（s1、a2）を更新します。

次の式で両者の違いを観察できます。

Q学習の更新式

Q∗に+1（（s）。←∑s'P（（s'|s、に）。（（R（（s、に、s'）。+cmにバツに'Q∗（（s'、に'）。）。 Q k + 1 ∗（s）←∑ s′P（s ′| s、a）（R（s、a、s′）+γma x a′Q ∗（s ′、a′））

サルサの更新された式

Q∗に+1（（s）。←∑s'P（（s'|s、に）。（（R（（s、に、s'）。+cQ∗（（s'、に'）。）。 Q k + 1 ∗（s）←∑ s′P（s ′| s、a）（R（s、a、s′）+γQ∗（s ′、a′））

サルサは物事を行うことについて話しているので、私たちは彼をポリシーに基づいて呼び、オンラインで学び、彼が何をしているのかを学びます。サルサはかなり保守的です、彼は危険から遠ざかることを選びます、宝物を手に入れることは二次的です、それを保ちなさいあなた自身の人生は王様です。これがSarsaメソッドの使用の違いです。
Q学習は言われていますが、必ずしも行われるとは限らないため、オフポリシー、オフライン学習とも呼ばれます。また、maxQがあるため、Q学習も特に勇敢なアルゴリズムです。このパスがどれほど危険であっても、成功への最も近いパスを常に選択してください。

3. Sarsa-lamda：Sarsaを高速化する方法

Sarsaは、Sarsa（0）であるワンステップ更新メソッドです。これは、このステップが行動規範を直接更新するのを待つためです。このアイデアのこの継続が、このステップの後で、別のステップを実行してから更新する場合、彼をSarsa（1）と呼ぶことができます。同様に、ラウンドが完了するのを待って1回更新すると、たとえば、このラウンドでnステップを実行した場合、Sarsa（n）と呼ばれます。このプロセスを統合するために、選択したいステップ数をラムダ値に置き換えます。これがSarsa（λ）の原点です。 SarsaとQlearningはどちらも、各報酬報酬が取得された後に報酬を取得する前のステップのみを更新します。Sarsa（λ）は報酬を取得する最初のλステップです。 λは[0、1]にあり、
lambda = 0の場合、Sarsa-lambdaはSarsaのシングルステップ更新であり、報酬が取得される前に経験した最後のステップのみです。ラムダ= 1の場合、サルサラムダはラウンドアップデートになります。アップデートは報酬の前にすべてのステップを取得することであり、アップデートの力はすべてのステップで同じです。ラムダが0から1の間の場合、値が大きいほど、報酬を取得するステップが大きいほど、更新の強度が大きくなります。このように、シングルステップの更新に限定する必要はありません。一度に更新できるのは最新のステップのみであり、関連するすべてのステップをより効率的に更新できます。
Sarsa（λ）アルゴリズムの擬似コード

4.アルゴリズムの実装

# off-policy class QLearningTable(RL): def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9): super(QLearningTable, self).__init__(actions, learning_rate, reward_decay, e_greedy) def learn(self, s, a, r, s_): self.check_state_exist(s_) q_predict = self.q_table.loc[s, a] if s_ != 'terminal': q_target = r + self.gamma * self.q_table.loc[s_, :].max() # next state is not terminal else: q_target = r # The next state is over self.q_table.loc[s, a] += self.lr * (q_target - q_predict) # update # on-policy class SarsaTable(RL): def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9): super(SarsaTable, self).__init__(actions, learning_rate, reward_decay, e_greedy) # Indicates inheritance def learn(self, s, a, r, s_, a_): self.check_state_exist(s_) q_predict = self.q_table.loc[s, a] if s_ != 'terminal': q_target = r + self.gamma * self.q_table.loc[s_, a_] # q_target is based on the selected a_ instead of the maximum value of Q(s_) else: q_target = r # If s_ is a terminator self.q_table.loc[s, a] += self.lr * (q_target - q_predict) # Update q_table # backward eligibility traces class SarsaLambdaTable(RL): def __init__(self, actions, learning_rate=0.01, reward_decay=0.9, e_greedy=0.9, trace_decay=0.9): super(SarsaLambdaTable, self).__init__(actions, learning_rate, reward_decay, e_greedy) # backward view, eligibility trace. self.lambda_ = trace_decay self.eligibility_trace = self.q_table.copy() def check_state_exist(self, state): if state not in self.q_table.index: # append new state to q table to_be_append = pd.Series( [0] * len(self.actions), index=self.q_table.columns, name=state, ) self.q_table = self.q_table.append(to_be_append) # also update eligibility trace self.eligibility_trace = self.eligibility_trace.append(to_be_append) def learn(self, s, a, r, s_, a_): # This part is the same as Sarsa self.check_state_exist(s_) q_predict = self.q_table.ix[s, a] if s_ != 'terminal': q_target = r + self.gamma * self.q_table.ix[s_, a_] else: q_target = r error = q_target - q_predict # Start to be different here: # For the experienced state-action, we let him +1, proving that he is an indispensable part of getting reward self.eligibility_trace.ix[s, a] += 1 # Q table update self.q_table += self.lr * error * self.eligibility_trace # With time decay the value of eligibility trace, the farther away from getting reward, the smaller his 'indispensability' self.eligibility_trace *= self.gamma * self.lambda_