Body: <p>I'm trying to create a simple Dyna-Q agent to solve small mazes, in python. For the Q function, Q(s, a), I'm just using a matrix, where each row is for a state value, and each column is for one of the 4 actions (up, down, left, right).</p>
  
  <p>I've implemented the "real experience" part, which is basically just straightforward SARSA. It solves a moderately hard (i.e., have to go around a few obstacles) mazes in 2000-8000 steps (in the first episode, it will no doubt decrease with more). So I know that part is working reliably.</p>
  
  <p>Now, adding the part that simulates experience based on what it knows of the model to update the Q values more, I'm having trouble. The way I'm doing it is to keep an <code>experiences</code> list (a lot like experience replay), where each time I take real action, I add its (S, A, R, S') to that list. </p>
  
  <p>Then, when I want to simulate an experience, I take a random (S, A, R, S') tuple from that list (David Silver mentions in his lecture (#8) on this that you can either update your transition probability matrix P and reward matrix R by changing their values or just sample from the experience list, which should be equivalent). In my case, with a given S and A, since it's deterministic, R and S' are also going to be the same as the ones I sampled from the tuple. Then I calculate Q(S, A) and max_A'(Q(S', A')), to get the TD error (same as above), and do stochastic gradient descent with it to change Q(S, A) in the right direction.</p>
  
  <p>But it's not working. When I add simulated experiences, it <em>never</em> finds the goal. I've tried poking around to figure out why, and all I can see that's weird is that the Q values continually increase as time goes on (while, without experiences, they settle to correct values).</p>
  
  <p>Does anyone have any advice about things I could try? I've looked at the sampled experiences, the Q values in the experience loop, the gradient, etc... and nothing really sticks out, aside from the Q values growing.</p>
  
  <p>edit: here's the code. The first part (one step TD learning) is working great. Adding the planning loop part screws it up.</p>
  
  <pre><code>def dynaQ(self, N_steps=100, N_plan_steps=5):
  
      self.initEpisode()
      for i in range(N_steps):
          #Get current state, next action, reward, next state
          s = self.getStateVec()
          a = self.epsGreedyAction(s)
          r, s_next = self.iterate(a)
          #Get Q values, Q_next is detached so it doesn't get changed by the gradient
          Q_cur = self.Q[s, a]
          Q_next = torch.max(self.Q[s_next]).detach().item()
          TD0_error = (r + self.params['gamma']*Q_next - Q_cur).pow(2).sum()
          #SGD
          self.optimizer.zero_grad()
          TD0_error.backward()
          self.optimizer.step()
          #Add to experience buffer
          e = Experience(s, a, r, s_next)
          self.updateModel(e)
  
          for j in range(N_plan_steps):
  
              xp = self.experiences[randint(0,len(self.experiences)-1)]
              Q_cur0 = self.Q[xp.s, xp.a]
              Q_next0 = torch.max(self.Q[xp.s_next]).detach().item()
              TD0_error0 = (xp.r + self.params['gamma']*Q_next0 - Q_cur0).pow(2).sum()
  
              self.optimizer.zero_grad()
              TD0_error0.backward()
              self.optimizer.step()
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-10T19:40:08.353Z
Comments.Text: I cannot tell from your description what could be wrong. It may be some part of the implementation that you have not described or even a coding error. Perhaps link your code, in case someone feels like taking a look.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-11T11:39:14.923Z
Comments.Text: I have looked through the code, and cannot see any obvious mistake, although I am only just a beginner with PyTorch. It's a bit unusual to be using full gradient descent with loss functions etc on the tabular version of Q learning. Have you tried just doing `self.Q[x.s, x.a] += self.params['alpha'] * (xp.r + self.params['gamma']*Q_next0 - Q_cur0)` ? That's usually how tabular DynaQ would be formulated . . .
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-11T13:53:09.613Z
Comments.Text: @NeilSlater thanks, I'll try it (that's what I used to do before using torch), but I really don't think it's that -- if I use torch to do the SGD without the experience/planning section, it works great.
Comments.UserDisplayName: GrundleMoof
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-11T14:09:49.020Z
Comments.Text: What optimiser are you using? If you have something more complex than basic SGD it could cause problems - even something simple like momentum.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-11T17:24:22.570Z
Comments.Text: @NeilSlater I'm using RMSProp. I don't pass it any parameters besides the Q matrix to optimize. I just do `self.optimizer = optim.RMSProp([self.Q])`.
Comments.UserDisplayName: GrundleMoof
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-11T17:56:00.963Z
Comments.Text: RMSProp tracks recent gradients and adjusts step sizes depending on what it expects to see on average across recent mini-batches. It might have trouble here, since your gradient is across the whole Q table, you don't use mini-batches, and only one item ever receives a non-zero gradient at a time. That might do odd things where RMSProp starts accumulating all those zeros for "batches" of not-yet visited state/action pairs and then suddenly receives a large update when it is finally visited.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-10-11T17:57:02.230Z
Comments.Text: I still suggest replace your RMSProp-based optimiser with the simpler update I showed in earlier comment, and see if the problem goes away. For a deterministic problem you can set a high value of $\alpha$, maybe even $1$
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning>
Title: Dyna-Q algorithm, having trouble when adding the simulated experiences
UserDisplayName: GrundleMoof
ThreadText: # Dyna-Q algorithm, having trouble when adding the simulated experiences
  
  (Asked by: username_0 on 2018-10-10)
  
  I'm trying to create a simple Dyna-Q agent to solve small mazes, in python. For the Q function, Q(s, a), I'm just using a matrix, where each row is for a state value, and each column is for one of the 4 actions (up, down, left, right).
  I've implemented the "real experience" part, which is basically just straightforward SARSA. It solves a moderately hard (i.e., have to go around a few obstacles) mazes in 2000-8000 steps (in the first episode, it will no doubt decrease with more). So I know that part is working reliably.
  Now, adding the part that simulates experience based on what it knows of the model to update the Q values more, I'm having trouble. The way I'm doing it is to keep an experiences list (a lot like experience replay), where each time I take real action, I add its (S, A, R, S') to that list. 
  Then, when I want to simulate an experience, I take a random (S, A, R, S') tuple from that list (David Silver mentions in his lecture (#8) on this that you can either update your transition probability matrix P and reward matrix R by changing their values or just sample from the experience list, which should be equivalent). In my case, with a given S and A, since it's deterministic, R and S' are also going to be the same as the ones I sampled from the tuple. Then I calculate Q(S, A) and max_A'(Q(S', A')), to get the TD error (same as above), and do stochastic gradient descent with it to change Q(S, A) in the right direction.
  But it's not working. When I add simulated experiences, it never finds the goal. I've tried poking around to figure out why, and all I can see that's weird is that the Q values continually increase as time goes on (while, without experiences, they settle to correct values).
  Does anyone have any advice about things I could try? I've looked at the sampled experiences, the Q values in the experience loop, the gradient, etc... and nothing really sticks out, aside from the Q values growing.
  edit: here's the code. The first part (one step TD learning) is working great. Adding the planning loop part screws it up.
  def dynaQ(self, N_steps=100, N_plan_steps=5):
  
      self.initEpisode()
      for i in range(N_steps):
          #Get current state, next action, reward, next state
          s = self.getStateVec()
          a = self.epsGreedyAction(s)
          r, s_next = self.iterate(a)
          #Get Q values, Q_next is detached so it doesn't get changed by the gradient
          Q_cur = self.Q[s, a]
          Q_next = torch.max(self.Q[s_next]).detach().item()
          TD0_error = (r + self.params['gamma']*Q_next - Q_cur).pow(2).sum()
          #SGD
          self.optimizer.zero_grad()
          TD0_error.backward()
          self.optimizer.step()
          #Add to experience buffer
          e = Experience(s, a, r, s_next)
          self.updateModel(e)
  
          for j in range(N_plan_steps):
  
              xp = self.experiences[randint(0,len(self.experiences)-1)]
              Q_cur0 = self.Q[xp.s, xp.a]
              Q_next0 = torch.max(self.Q[xp.s_next]).detach().item()
              TD0_error0 = (xp.r + self.params['gamma']*Q_next0 - Q_cur0).pow(2).sum()
  
              self.optimizer.zero_grad()
              TD0_error0.backward()
              self.optimizer.step()
  
  **Tags:** reinforcement-learning
  > **Comments:**
  > **username_1**: I cannot tell from your description what could be wrong. It may be some part of the implementation that you have not described or even a coding error. Perhaps link your code, in case someone feels like taking a look.  
  > **username_1**: I have looked through the code, and cannot see any obvious mistake, although I am only just a beginner with PyTorch. It's a bit unusual to be using full gradient descent with loss functions etc on the tabular version of Q learning. Have you tried just doing `self.Q[x.s, x.a] += self.params['alpha'] * (xp.r + self.params['gamma']*Q_next0 - Q_cur0)` ? That's usually how tabular DynaQ would be formulated . . .  
  > **username_0**: @NeilSlater thanks, I'll try it (that's what I used to do before using torch), but I really don't think it's that -- if I use torch to do the SGD without the experience/planning section, it works great.  
  > **username_1**: What optimiser are you using? If you have something more complex than basic SGD it could cause problems - even something simple like momentum.  
  > **username_0**: @NeilSlater I'm using RMSProp. I don't pass it any parameters besides the Q matrix to optimize. I just do `self.optimizer = optim.RMSProp([self.Q])`.  
  > **username_1**: RMSProp tracks recent gradients and adjusts step sizes depending on what it expects to see on average across recent mini-batches. It might have trouble here, since your gradient is across the whole Q table, you don't use mini-batches, and only one item ever receives a non-zero gradient at a time. That might do odd things where RMSProp starts accumulating all those zeros for "batches" of not-yet visited state/action pairs and then suddenly receives a large update when it is finally visited.  
  > **username_1**: I still suggest replace your RMSProp-based optimiser with the simpler update I showed in earlier comment, and see if the problem goes away. For a deterministic problem you can set a high value of $\alpha$, maybe even $1$  
  
  ---
  
  ## 0 answers
  
  