Answers.Body: <p><em>I think</em> the point here is that Q-learning may learn the optimal policy or value function faster. The optimal policy is to choose actions that are close to the cliff, but, during learning, to behave, you <strong>still</strong> use the <span class="math-container">$\epsilon$</span>-greedy policy which is based on the (near-)optimal value function, so you may occasionally fall off the cliff. SARSA may learn a different value function, which during learning doesn't make the agent fall off the cliff as often. If we were <strong>not</strong> learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-06T15:25:58.593Z
Answers.Text: Can you explain or rephrase the last sentence ? "If we were not learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that). "
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-06T16:13:30.410Z
Answers.Text: @DSPinfinity After learning, Q-learning will not use the $\epsilon$-greedy policy to behave but it will use a deterministic policy derived from $q(s, a)$ that it's learned. That deterministic policy is simply $a^* = \text{argmax}_a q(s, a)$, i.e. it chooses the greedy action. If Q-learning has learned the optimal $q$, then it has also learned the optimal policy. Now, that optimal policy should not take actions that make you fall off the cliff, because that's probably not optimal, but it will take actions that are close to the cliff (because we know that's the optimal policy).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-06T22:22:14.617Z
Answers.Text: This explanation is confusing because in Q-learning  ϵ
  -greedy policy is used to select the action A. Ie,  ϵ-greedy policy is behaviour policy.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T00:37:23.850Z
Answers.Text: @DSPinfinity Yes, $\epsilon$-greedy is used to select actions, but only during learning. Q-learning is a learning algorithm, i.e. it's trying to learn a value function $q$, from which you can derive the policy, which is **not** the behaviour policy you use **during learning**, but is the greedy policy with respect to $q$, i.e. $a^* = \text{argmax} q(s, a)$. So, after learning, you will not be using the $\epsilon$-greedy but $a^* = \text{argmax} q(s, a)$, which is the target policy and it's optimal if the learned $q$ is also optimal, assuming finite MDPs.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T00:46:58.333Z
Answers.Text: So, the reason why you use $\epsilon$-greedy during learning, instead of the target policy, is because, during learning, $q$ is typically not optimal (at least at the beginning of learning), so you need to **explore** (i.e. sometimes randomly choose actions) and sometimes you need to **exploit** (i.e. choose the best action according to your current estimate of $q$). This is one of the most important concepts in RL: **the exploration-exploitation tradeoff**.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T00:46:59.903Z
Answers.Text: So, you can't just use a greedy (deterministic) policy during learning, because $q$ may not be optimal, and you shouldn't use a stochastic policy after learning in finite MDPs if the learned $q$ is optimal, because there's a known result in RL that says that there's at least one optimal policy that is deterministic in finite MDPs. If you don't know the difference between stochastic and deterministic policies, see https://ai.stackexchange.com/q/12274/2444
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-06T13:06:13.383Z
Answers.LastActivityDate: 2024-05-06T13:06:13.383Z
Answers.UserDisplayName: nbro
Body: <p>Sutton-Barto, page 132:</p>
  <p><a href="https://i.sstatic.net/7oXkgG4e.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/7oXkgG4e.png" alt="enter image description here" /></a></p>
  <blockquote>
  <p>The graph to the right shows the
  performance of the Sarsa and Qlearning
  methods with &quot;-greedy action
  selection, &quot; = 0.1. After an
  initial transient, Q-learning learns
  values for the optimal policy, that
  which travels right along the edge
  of the cli↵. Unfortunately, this results
  in its occasionally falling o↵
  the cli↵ because of the &quot;-greedy action
  selection. Sarsa, on the other
  hand, takes the action selection into
  account and learns the longer but
  safer path through the upper part
  of the grid.</p>
  </blockquote>
  <p>SARSA is also using <span class="math-container">$\epsilon$</span>-greedy and hence falling off cliff may happen with the same reasoning done for the Q-learning. I did not understand why this (falling off cliff) does not happen in SARSA.</p>
  
Tags: <reinforcement-learning><sutton-barto>
Title: Why no falling off cliff in SARSA for the example in Sutton-Barto?
UserDisplayName: DSPinfinity
ThreadText: # Why no falling off cliff in SARSA for the example in Sutton-Barto?
  
  (Asked by: username_0 on 2024-05-06)
  
  Sutton-Barto, page 132:
  
  [![enter image description here](https://i.sstatic.net/7oXkgG4e.png)](https://i.sstatic.net/7oXkgG4e.png)
  
  > The graph to the right shows the
  > performance of the Sarsa and Qlearning
  > methods with "-greedy action
  > selection, " = 0.1. After an
  > initial transient, Q-learning learns
  > values for the optimal policy, that
  > which travels right along the edge
  > of the cli↵. Unfortunately, this results
  > in its occasionally falling o↵
  > the cli↵ because of the "-greedy action
  > selection. Sarsa, on the other
  > hand, takes the action selection into
  > account and learns the longer but
  > safer path through the upper part
  > of the grid.
  
  SARSA is also using $\epsilon$-greedy and hence falling off cliff may happen with the same reasoning done for the Q-learning. I did not understand why this (falling off cliff) does not happen in SARSA.
  
  **Tags:** reinforcement-learning, sutton-barto
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-05-06. Score: 3 | Accepted answer
  
  *I think* the point here is that Q-learning may learn the optimal policy or value function faster. The optimal policy is to choose actions that are close to the cliff, but, during learning, to behave, you **still** use the $\epsilon$-greedy policy which is based on the (near-)optimal value function, so you may occasionally fall off the cliff. SARSA may learn a different value function, which during learning doesn't make the agent fall off the cliff as often. If we were **not** learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that).
  
  > **Comments:**
  > **username_0**: Can you explain or rephrase the last sentence ? "If we were not learning, and Q-learning had found the optimal policy, it would always act greedily, so it would not fall off the cliff (assuming the optimal policy doesn't do that). "  
  > **username_1**: @DSPinfinity After learning, Q-learning will not use the $\epsilon$-greedy policy to behave but it will use a deterministic policy derived from $q(s, a)$ that it's learned. That deterministic policy is simply $a^* = \text{argmax}_a q(s, a)$, i.e. it chooses the greedy action. If Q-learning has learned the optimal $q$, then it has also learned the optimal policy. Now, that optimal policy should not take actions that make you fall off the cliff, because that's probably not optimal, but it will take actions that are close to the cliff (because we know that's the optimal policy).  
  > **username_0**: This explanation is confusing because in Q-learning  ϵ -greedy policy is used to select the action A. Ie,  ϵ-greedy policy is behaviour policy.  
  > **username_1**: @DSPinfinity Yes, $\epsilon$-greedy is used to select actions, but only during learning. Q-learning is a learning algorithm, i.e. it's trying to learn a value function $q$, from which you can derive the policy, which is **not** the behaviour policy you use **during learning**, but is the greedy policy with respect to $q$, i.e. $a^* = \text{argmax} q(s, a)$. So, after learning, you will not be using the $\epsilon$-greedy but $a^* = \text{argmax} q(s, a)$, which is the target policy and it's optimal if the learned $q$ is also optimal, assuming finite MDPs.  
  > **username_1**: So, the reason why you use $\epsilon$-greedy during learning, instead of the target policy, is because, during learning, $q$ is typically not optimal (at least at the beginning of learning), so you need to **explore** (i.e. sometimes randomly choose actions) and sometimes you need to **exploit** (i.e. choose the best action according to your current estimate of $q$). This is one of the most important concepts in RL: **the exploration-exploitation tradeoff**.  
  > **username_1**: So, you can't just use a greedy (deterministic) policy during learning, because $q$ may not be optimal, and you shouldn't use a stochastic policy after learning in finite MDPs if the learned $q$ is optimal, because there's a known result in RL that says that there's at least one optimal policy that is deterministic in finite MDPs. If you don't know the difference between stochastic and deterministic policies, see https://ai.stackexchange.com/q/12274/2444  
  
  ---
  
  