Although I know that SARSA is on-policy while Q-learning is off-policy, when looking at their formulas it's hard (to me) to see any difference between these two algorithms.
According to the book Reinforcement Learning: An Introduction (by Sutton and Barto). In the SARSA algorithm, given a policy, the corresponding action-value function Q (in the state s and action a, at timestep t), i.e. Q(st, at), can be updated as follows
Q(st, at) = Q(st, at) + α*(rt + γ*Q(st+1, at+1) - Q(st, at))
On the other hand, the update step for the Q-learning algorithm is the following
Q(st , a t ) = Q(st , a t ) + α*(rt + γ*max a Q( st+1 , a) - Q( st , a t ))
これは次のようにも書ける。
Q(s t , a t ) = (1 - α) * Q(s t , a t ) + α * (r t + γ*max a Q(s t+1 , a))
ここで、γ(ガンマ)は割引係数であり、rtはタイムステップtで環境から受け取る報酬です。
これら2つのアルゴリズムの違いは、SARSAは次のポリシー値のみを検索するのに対し、Q学習は次の最大政策の価値?
TLDR(そして私自身の答え)
私が最初にこの質問をして以来、この質問に答えてくれた皆さんに感謝します。githubリポジトリQ学習を試してみて、違いが何なのかを経験的に理解しました。次に最善の行動を選択するアルゴリズムの観点からは、平均、最大または最高実装方法に応じてアクションが異なります。
もう一つの大きな違いはいつこの選択が起こっている(例:オンライン対オフライン) とそれが学習にどのように/なぜ影響するかについて説明します。2019 年にこの記事を読んでいて、実践的な人であれば、RL のおもちゃの問題で遊ぶのが違いを理解する最良の方法でしょう。
最後に重要注目すべきは、ストン&バルトとウィキペディアの両方が、しばしば混ざった、混乱したまたは間違っているに関する定型的な表現次の状態の最良/最大のアクションと報酬:
r(t+1)
実際には
r(t)
ベストアンサー1
私もこの部分を学習していたときに非常に混乱したので、違いが明確になるように R.Sutton と AGBarto の 2 つの疑似コードを組み合わせました。
青いボックスは、2 つのアルゴリズムが実際に異なる部分を強調表示しています。数字は、後で説明するより詳細な違いを強調表示しています。
要約:
| | SARSA | Q-learning |
|:-----------:|:-----:|:----------:|
| Choosing A' | π | π |
| Updating Q | π | μ |
ここで、π は ε 貪欲ポリシー (例: ε > 0 で探索あり)、μ は貪欲ポリシー (例: ε == 0、探索なし) です。
Q 学習では、次のアクション A' の選択と Q の更新に異なるポリシーが使用されています。つまり、別のポリシー μ に従いながら π を評価しようとしているため、オフポリシー アルゴリズムです。
対照的に、SARSA は常に π を使用するため、オンポリシー アルゴリズムになります。
より詳しい説明:
2 つの間の最も重要な違いは、各アクションの後に Q がどのように更新されるかです。SARSA は、A' がそこから抽出されるので、ε 貪欲ポリシーに正確に従って Q' を使用します。対照的に、Q 学習は次のステップですべての可能なアクションの最大 Q' を使用します。これにより、ε = 0 の貪欲ポリシーに従っているように見えます。つまり、この部分では探索は行われません。
ただし、実際にアクションを実行するときは、Q 学習は依然として ε 貪欲ポリシーから実行されたアクションを使用します。これが、「Choose A ...」が繰り返しループ内にある理由です。
Q 学習のループ ロジックに従うと、A' は依然として ε 貪欲ポリシーからのものになります。