Answers.Body: <p>On doing some research on why this problem might be occurring, I delved into some statistics of the environment. Interestingly, after a small number of episodes (~20), the agent always chooses to take only one action (this has been mentioned in the question too). Also, the Q values of the state-action pairs do not change a lot after just about 20 episodes. Same is the case for policy of environment, as may be expected.</p>
  
  <p>The problem is that, although all the individual updates are being done correctly, the following scenario occurs.</p>
  
  <p>The update equation used is the following :-</p>
  
  <pre><code>Q(s1, a1) &lt;- r1 + gamma * Q(s2, a2)
  </code></pre>
  
  <p>Now, any update to function approximator means that the Q value changes not just for the updated (state, action) pair, but for all (state, action) pairs. How much it changes for any specific (state, action) pairs is another issue. Now, since our function approximator is altered, next time we use the previous equation for updating any other state, we use the following equation :-</p>
  
  <pre><code>Q(s3, a3) &lt;- r3 + gamma * Q(s4, a4)
  </code></pre>
  
  <p>But since Q has itself been changed, the target value of the record 3 changes. This is not desirable. Over time, all the changes cancel each other and Q value remains roughly the same. </p>
  
  <p>By using something known as the target function approximator(target network), we can maintain an older version of function approximator, which is used to get the Q-value of next state-action pair while the time of update. This helps avoid the problem and can be used to solve the environment.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-22T19:07:28.870Z
Answers.LastActivityDate: 2018-12-22T19:07:28.870Z
Answers.UserDisplayName: Vaibhav Gupta
Answers.Body: <p>One possible cause of SARSA with a linear approximator failing to learn a good policy for the Mountain Car problem is that you are not encoding the environment state, the position and velocity.</p>
  
  <p>In David Silver's Lecture 6 that you mention in your question, he describes the state encoding, which in this case is a tile coding, here: <a href="https://youtu.be/UoPei5o4fps?t=3626" rel="nofollow noreferrer">https://youtu.be/UoPei5o4fps?t=3626</a>.</p>
  
  <p>This coarse coding is described in more detail in the Sutton and Barto book, Reinforcement Learning: An Introduction (<a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">http://incompleteideas.net/book/the-book.html</a>), in Chapter 9, where different state encodings for linear approximators are described, and Chapter 10, where the Mountain Car problem is discussed.</p>
  
  <p>In my experience, using a tile coding worked in combination with a linear function to solve the Mountain Car task. Using no encoding did not work.</p>
  
  <p>The following plot shows the max q-values (the policy) when using Sarsa with no encoding. The points are colored with the corresponding action of the max q-value to more clearly show the policy the agent will follow.</p>
  
  <p><a href="https://i.sstatic.net/VG9oW.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/VG9oW.png" alt="Sarsa q-values with no encoding"></a></p>
  
  <p>This planar policy produces an average score of -200.0 per episode, averaged over 100 episodes.</p>
  
  <p>Contrast that policy with the following graph of q-values produced by using Sarsa in combination with a tile encoding.</p>
  
  <p><a href="https://i.sstatic.net/Nbb3V.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Nbb3V.png" alt="Sarsa q-values with tile encoding"></a></p>
  
  <p>The policy of this agent scores -102.9 per episode, averaged over 100 episodes. It might be hard to see in the graph, but it has the characteristic "spiral" of the learned graph from Figure 10.1 of the Sutton and Barto book.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-23T06:18:01.717Z
Answers.Text: That is true. David Silver does mention a coarse coding approach. You mentioned that tile coding worked nicely for you. I would like to ask you if you used SARSA, or Q-Learning. I mean did you make changes in-place, or did you keep a copy separately for calculating Q-value of next state while updating?
Answers.UserDisplayName: Vaibhav Gupta
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-23T22:06:04.927Z
Answers.Text: I used Q-Learning (but I did not use a separate target network). I haven't tried SARSA yet. If you want to see all the messy details of my implementation, take a look at https://github.com/todddeluca/learning_reinforcement_learning/tree/master/exp20181220.  Cheers.
Answers.UserDisplayName: todddeluca
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-23T00:24:12.767Z
Answers.LastActivityDate: 2018-12-27T00:32:30.690Z
Answers.LastEditDate: 2018-12-27T00:32:30.690Z
Answers.UserDisplayName: todddeluca
Body: <p>I am learning Reinforcement Learning from the lectures from David Silver. I finished lecture 6 and went on to try SARSA with linear function approximator for MountainCar-v0 environment from OpenAI.</p>
  
  <p>A brief explanation of the MountainCar-v0 environment. The state is denoted by two features, position, and velocity. There are three actions for each state, accelerate forwards, don't accelerate, accelerate backward. The goal of the agent is to learn how to climb a mountain. The engine of the car is not strong enough to power directly to the top. So speed has to be built up by oscillating in the cliff.</p>
  
  <p>I have used a linear function approximator, written by myself. I am attaching my code here for reference :-</p>
  
  <pre><code>    class LinearFunctionApproximator:
        ''' A function approximator must have the following methods:-
            constructor with num_states and num_actions
            get_q_value
            get_action
            fit '''
  
        def __init__(self, num_states, num_actions):
          self.weights = np.zeros((num_states, num_actions))
          self.num_states = num_states
          self.num_actions = num_actions
  
        def get_q_value(self, state, action):
          return np.dot( np.transpose(self.weights), np.asarray(state) )[action]
  
        def get_action(self, state, eps):
          return randint(0, self.num_actions-1) if uniform(0, 1) &lt; eps else np.argmax( np.dot(np.transpose(self.weights), np.asarray(state)) )
  
        def fit(self, transitions, eps, gamma, learning_rate):
          ''' Every transition in transitions should be of type (state, action, reward, next_state) '''
          gradient = np.zeros_like(self.weights)
          for (state, action, reward, next_state) in transitions:
            next_action = self.get_action(next_state, eps)
            g_target = reward + gamma * self.get_q_value(next_state, next_action)
            g_predicted = self.get_q_value(state, action)
            gradient[:, action] += learning_rate * (g_target - g_predicted) * np.asarray(state)
  
          gradient /= len(transitions)
          self.weights += gradient
  </code></pre>
  
  <p>I have tested the gradient descent, and it works as expected. After every epoch, the mean squared error between current estimate of Q and TD-target reduces as expected.</p>
  
  <p>Here is my code for SARSA :-</p>
  
  <pre><code>def SARSA(env, function_approximator, num_episodes=1000, eps=0.1, gamma=0.95, learning_rate=0.1, logging=False):
  
    for episode in range(num_episodes):
      transitions = []
  
      state = env.reset()
      done = False
  
      while not done:
        action = function_approximator.get_action(state, eps)
        next_state, reward, done, info = env.step(action)
        transitions.append( (state, action, reward, next_state) )
        state = next_state
  
      for i in range(10):
        function_approximator.fit(transitions[::-1], eps, gamma, learning_rate)
  
      if logging:
        print('Episode', episode, ':', end=' ')
        run_episode(env, function_approximator, eps, render=False, logging=True)
  </code></pre>
  
  <p>Basically, for every episode, I fit the linear function approximator to the current TD-target. I have also tried running fit just once per episode, but that also does not yield any winning episode. Fitting 10 times ensures that I am actually making some progress towards the TD-target, and also not overfitting.</p>
  
  <p>However, after running over 5000 episodes, I do not get a single episode where the reward is greater than -200. Eventually, the algorithm choses one action, and somehow the Q-value of other actions is always lesser than this action.</p>
  
  <pre><code># Now, let's see how the trained model does
  env = gym.make('MountainCar-v0')
  num_states = 2
  num_actions = env.action_space.n
  
  function_approximator = LinearFunctionApproximator(num_states, num_actions)
  
  num_episodes = 2000
  eps = 0
  SARSA(env, function_approximator, num_episodes=num_episodes, eps=eps, logging=True)
  </code></pre>
  
  <p>I want to be more clear about this. Say action 2 is the one which is the action which gets selected always after say 1000 episodes. Action 0 and action 1 have somehow, for all states, have their Q-values reduced to a level which is never reached by action 2. So for a particular state, action 0 and action 1 may have Q-values of -69 and -69.2. The Q-value of action 2 will never drop below -65, even after running the 5000 episodes.</p>
  
Tags: <reinforcement-learning><gradient-descent>
Title: SARSA won't work for linear function approximator for MountainCar-v0 in OpenAI environment. What are the possible causes?
UserDisplayName: Vaibhav Gupta
ThreadText: # SARSA won't work for linear function approximator for MountainCar-v0 in OpenAI environment. What are the possible causes?
  
  (Asked by: username_0 on 2018-12-18)
  
  I am learning Reinforcement Learning from the lectures from David Silver. I finished lecture 6 and went on to try SARSA with linear function approximator for MountainCar-v0 environment from OpenAI.
  
  A brief explanation of the MountainCar-v0 environment. The state is denoted by two features, position, and velocity. There are three actions for each state, accelerate forwards, don't accelerate, accelerate backward. The goal of the agent is to learn how to climb a mountain. The engine of the car is not strong enough to power directly to the top. So speed has to be built up by oscillating in the cliff.
  
  I have used a linear function approximator, written by myself. I am attaching my code here for reference :-
  
  ```
      class LinearFunctionApproximator:
        ''' A function approximator must have the following methods:-
            constructor with num_states and num_actions
            get_q_value
            get_action
            fit '''
  
        def __init__(self, num_states, num_actions):
          self.weights = np.zeros((num_states, num_actions))
          self.num_states = num_states
          self.num_actions = num_actions
  
        def get_q_value(self, state, action):
          return np.dot( np.transpose(self.weights), np.asarray(state) )[action]
  
        def get_action(self, state, eps):
          return randint(0, self.num_actions-1) if uniform(0, 1) < eps else np.argmax( np.dot(np.transpose(self.weights), np.asarray(state)) )
  
        def fit(self, transitions, eps, gamma, learning_rate):
          ''' Every transition in transitions should be of type (state, action, reward, next_state) '''
          gradient = np.zeros_like(self.weights)
          for (state, action, reward, next_state) in transitions:
            next_action = self.get_action(next_state, eps)
            g_target = reward + gamma * self.get_q_value(next_state, next_action)
            g_predicted = self.get_q_value(state, action)
            gradient[:, action] += learning_rate * (g_target - g_predicted) * np.asarray(state)
  
          gradient /= len(transitions)
          self.weights += gradient
  
  ```
  
  I have tested the gradient descent, and it works as expected. After every epoch, the mean squared error between current estimate of Q and TD-target reduces as expected.
  
  Here is my code for SARSA :-
  
  ```
  def SARSA(env, function_approximator, num_episodes=1000, eps=0.1, gamma=0.95, learning_rate=0.1, logging=False):
  
    for episode in range(num_episodes):
      transitions = []
  
      state = env.reset()
      done = False
  
      while not done:
        action = function_approximator.get_action(state, eps)
        next_state, reward, done, info = env.step(action)
        transitions.append( (state, action, reward, next_state) )
        state = next_state
  
      for i in range(10):
        function_approximator.fit(transitions[::-1], eps, gamma, learning_rate)
  
      if logging:
        print('Episode', episode, ':', end=' ')
        run_episode(env, function_approximator, eps, render=False, logging=True)
  
  ```
  
  Basically, for every episode, I fit the linear function approximator to the current TD-target. I have also tried running fit just once per episode, but that also does not yield any winning episode. Fitting 10 times ensures that I am actually making some progress towards the TD-target, and also not overfitting.
  
  However, after running over 5000 episodes, I do not get a single episode where the reward is greater than -200. Eventually, the algorithm choses one action, and somehow the Q-value of other actions is always lesser than this action.
  
  ```
  # Now, let's see how the trained model does
  env = gym.make('MountainCar-v0')
  num_states = 2
  num_actions = env.action_space.n
  
  function_approximator = LinearFunctionApproximator(num_states, num_actions)
  
  num_episodes = 2000
  eps = 0
  SARSA(env, function_approximator, num_episodes=num_episodes, eps=eps, logging=True)
  
  ```
  
  I want to be more clear about this. Say action 2 is the one which is the action which gets selected always after say 1000 episodes. Action 0 and action 1 have somehow, for all states, have their Q-values reduced to a level which is never reached by action 2. So for a particular state, action 0 and action 1 may have Q-values of -69 and -69.2. The Q-value of action 2 will never drop below -65, even after running the 5000 episodes.
  
  **Tags:** reinforcement-learning, gradient-descent
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2018-12-22. Score: 1 | Accepted answer
  
  On doing some research on why this problem might be occurring, I delved into some statistics of the environment. Interestingly, after a small number of episodes (~20), the agent always chooses to take only one action (this has been mentioned in the question too). Also, the Q values of the state-action pairs do not change a lot after just about 20 episodes. Same is the case for policy of environment, as may be expected.
  
  The problem is that, although all the individual updates are being done correctly, the following scenario occurs.
  
  The update equation used is the following :-
  
  ```
  Q(s1, a1) <- r1 + gamma * Q(s2, a2)
  
  ```
  
  Now, any update to function approximator means that the Q value changes not just for the updated (state, action) pair, but for all (state, action) pairs. How much it changes for any specific (state, action) pairs is another issue. Now, since our function approximator is altered, next time we use the previous equation for updating any other state, we use the following equation :-
  
  ```
  Q(s3, a3) <- r3 + gamma * Q(s4, a4)
  
  ```
  
  But since Q has itself been changed, the target value of the record 3 changes. This is not desirable. Over time, all the changes cancel each other and Q value remains roughly the same.
  
  By using something known as the target function approximator(target network), we can maintain an older version of function approximator, which is used to get the Q-value of next state-action pair while the time of update. This helps avoid the problem and can be used to solve the environment.
  
  
  ---
  
  ### Answer by username_1 on 2018-12-23. Score: 2
  
  One possible cause of SARSA with a linear approximator failing to learn a good policy for the Mountain Car problem is that you are not encoding the environment state, the position and velocity.
  
  In David Silver's Lecture 6 that you mention in your question, he describes the state encoding, which in this case is a tile coding, here: <https://youtu.be/UoPei5o4fps?t=3626>.
  
  This coarse coding is described in more detail in the Sutton and Barto book, Reinforcement Learning: An Introduction (<http://incompleteideas.net/book/the-book.html>), in Chapter 9, where different state encodings for linear approximators are described, and Chapter 10, where the Mountain Car problem is discussed.
  
  In my experience, using a tile coding worked in combination with a linear function to solve the Mountain Car task. Using no encoding did not work.
  
  The following plot shows the max q-values (the policy) when using Sarsa with no encoding. The points are colored with the corresponding action of the max q-value to more clearly show the policy the agent will follow.
  
  [![Sarsa q-values with no encoding](https://i.sstatic.net/VG9oW.png)](https://i.sstatic.net/VG9oW.png)
  
  This planar policy produces an average score of -200.0 per episode, averaged over 100 episodes.
  
  Contrast that policy with the following graph of q-values produced by using Sarsa in combination with a tile encoding.
  
  [![Sarsa q-values with tile encoding](https://i.sstatic.net/Nbb3V.png)](https://i.sstatic.net/Nbb3V.png)
  
  The policy of this agent scores -102.9 per episode, averaged over 100 episodes. It might be hard to see in the graph, but it has the characteristic "spiral" of the learned graph from Figure 10.1 of the Sutton and Barto book.
  
  > **Comments:**
  > **username_0**: That is true. David Silver does mention a coarse coding approach. You mentioned that tile coding worked nicely for you. I would like to ask you if you used SARSA, or Q-Learning. I mean did you make changes in-place, or did you keep a copy separately for calculating Q-value of next state while updating?  
  > **username_1**: I used Q-Learning (but I did not use a separate target network). I haven't tried SARSA yet. If you want to see all the messy details of my implementation, take a look at https://github.com/username_1/learning_reinforcement_learning/tree/master/exp20181220.  Cheers.  
  
  ---
  
  