title: Q-Learning values get too high
body: <p>I've recently made an attempt to implement a basic Q-Learning algorithm in Golang. Note that I'm new to Reinforcement Learning and AI in general, so the error may very well be mine.</p>
  
  <p>Here's how I implemented the solution to an m,n,k-game environment:
  At each given time <code>t</code>, the agent holds the last state-action <code>(s, a)</code> and the acquired reward for it; the agent selects a move <code>a'</code> based on an Epsilon-greedy policy and calculates the reward <code>r</code>, then proceeds to update the value of <code>Q(s, a)</code> for time <code>t-1</code></p>
  
  <pre><code>func (agent *RLAgent) learn(reward float64) {
      var mState = marshallState(agent.prevState, agent.id)
      var oldVal = agent.values[mState]
  
      agent.values[mState] = oldVal + (agent.LearningRate *
          (agent.prevScore + (agent.DiscountFactor * reward) - oldVal))
  }
  </code></pre>
  
  <p>Note:</p>
  
  <ul>
  <li><code>agent.prevState</code> holds previous state right after taking the action and before the environment responds (i.e. after the agent makes it's move and before the other player makes a move) I use that in place of the state-action tuple, but I'm not quite sure if that's the right approach</li>
  <li><code>agent.prevScore</code> holds the reward to previous state-action</li>
  <li>The <code>reward</code> argument represents the reward for current step's state-action (<code>Qmax</code>)</li>
  </ul>
  
  <p>With <code>agent.LearningRate = 0.2</code> and <code>agent.DiscountFactor = 0.8</code> the agent fails to reach 100K episodes because of state-action value overflow.
  I'm using golang's <code>float64</code> (Standard IEEE 754-1985 double precision floating point variable) which overflows at around <code>±1.80×10^308</code> and yields <code>±Infiniti</code>. That's too big a value I'd say!</p>
  
  <p>Here's the state of a model trained with a learning rate of <code>0.02</code> and a discount factor of <code>0.08</code> which got through 2M episodes (1M games with itself):</p>
  
  <pre><code>Reinforcement learning model report
  Iterations: 2000000
  Learned states: 4973
  Maximum value: 88781786878142287058992045692178302709335321375413536179603017129368394119653322992958428880260210391115335655910912645569618040471973513955473468092393367618971462560382976.000000
  Minimum value: 0.000000
  </code></pre>
  
  <p>The reward function returns:</p>
  
  <ul>
  <li>Agent won: 1</li>
  <li>Agent lost: -1</li>
  <li>Draw: 0</li>
  <li>Game continues: 0.5</li>
  </ul>
  
  <p>But you can see that the minimum value is zero, and the maximum value is too high.</p>
  
  <p>It may be worth mentioning that with a simpler learning method I found in a python script works perfectly fine and feels actually more intelligent! When I play with it, most of the time the result is a draw (it even wins if I play carelessly), whereas with the standard Q-Learning method, I can't even let it win!</p>
  
  <pre><code>agent.values[mState] = oldVal + (agent.LearningRate * (reward - agent.prevScore))
  </code></pre>
  
  <p>Any ideas on how to fix this?
  Is that kind of state-action value normal in Q-Learning?!</p>
  
  <hr>
  
  <p><strong>Update:</strong>
  After reading Pablo's answer and the slight but important edit that Nick provided to this question, I realized the problem was <code>prevScore</code> containing the Q-value of previous step (equal to <code>oldVal</code>) instead of the reward of the previous step (in this example, -1, 0, 0.5 or 1).</p>
  
  <p>After that change, the agent now behaves normally and after 2M episodes, the state of the model is as follows:</p>
  
  <pre><code>Reinforcement learning model report
  Iterations: 2000000
  Learned states: 5477
  Maximum value: 1.090465
  Minimum value: -0.554718
  </code></pre>
  
  <p>and out of 5 games with the agent, there were 2 wins for me (the agent did not recognize that I had two stones in a row) and 3 draws.</p>