title: Unbounded increase in Q-Value, consequence of recurrent reward after repeating the same action in Q-Learning
body: <p>I'm in the process of development of a simple Q-Learning implementation over a trivial application, but there's something that keeps puzzling me.</p>
  
  <p>Let's consider the standard formulation of Q-Learning</p>
  
  <pre><code>Q(S, A) = Q(S, A) + alpha * [R +  MaxQ(S', A') - Q(S, A)]
  </code></pre>
  
  <p>Let's assume there's this state <code>K</code> that has two possible actions, both awarding our agent rewards <code>R</code> and <code>R'</code> by <code>A</code> and <code>A'</code>. </p>
  
  <p>If we follow an almost-totally-greedy approach (let's say we assume a 0.1 epsilon), I'll at first randomly choose one of the actions, for instance <code>A</code>. The next time, I'll probably (90% of the times) choose again <code>A</code> and that will cause that Q(K, A) keeps growing and growing, being true the case that even if by chance I try <code>A'</code>, as probably its reward is on the same magnitude as that of A, we'll have gotten into a situation where it's practically impossible to "recover" from our first guess, during the rest of the learning.</p>
  
  <p>I guess this must not be so, otherwise the agent would basically not learn -- it'd be just follow a simple recipe : do everything as you did your first time.</p>
  
  <p>Am I missing something? I know I can tweak the alpha value (generally, decreasing it over time), but that in no way improves our situation.</p>