This algorithm was proposed by Watkins (in Learning from delayed rewards, Watkins C.I.C.H., Ph.D. Thesis, University of Cambridge, 1989; and further analyzed in Watkins C.I.C.H., Dayan P., Technical Note Q-Learning, Machine Learning 8, 1992) as a more efficient alternative to SARSA. The main feature of Q-learning is that the TD update rule is immediately greedy with respect to the Q(s_t+1, a) function:

The key idea is to compare the current Q(s_t, a_t) value with the maximum Q value achievable when the agent is in the successor state. In fact, as the policy must be GLIE, the convergence speed can be increased by avoiding wrong estimations due to the selection of a Q value that won't be associated with the final action. By choosing the maximum Q value, the algorithm will move towards the optimal solution faster than SARSA, and also, the convergence proof is less restrictive. In fact, Watkins and Dayan (in the aforementioned papers) proved that, if |r_i| < R, the learning rate α ∈ [0, 1[ (in this case, α must be always smaller than 1) with the same constraints imposed for SARSA (Σα = ∞ and Σα² < ∞), then the estimated Q function converges with probability 1 to the optimal one:

As discussed for SARSA, the conditions on the rewards and the learning rate can be managed by employing a clipping function and a temporal decay, respectively. In almost all deep Q-learning applications, these are extremely important factors to guarantee the convergence; therefore, I invite the reader to consider them whenever the training process isn't able to converge to an acceptable solution. 

The complete Q-learning algorithm (with an optional forced termination of the episode) is:

1. Set an initial deterministic random policy, π(s)
2. Set the initial value array, Q(s, a) = 0 ∀ s ∈ S and ∀ a ∈ A
3. Set the number of episodes, N_episodes
4. Set a maximum number of steps per episode, N_max
5. Set a constant, α (α = 0.1)
6. Set a constant, γ (γ = 0.9)
7. Set an initial exploration factor, ε⁽⁰⁾ (ε⁽⁰⁾ = 1.0)
8. Define a policy to let the exploration factor ε decay (linear or exponential)
9. Set a counter, e = 0
10. For i = 1 to N_episodes:
    
    1. Observe the initial state, s_i
    2. While s_j is non-terminal and e < N_max:
       1. e += 1
       2. Select the action, a_t = π(s_i), with an exploration factor ε^(e)
       3. Observe the transition (a_t, s_i) → (s_j, r_ij)
       4. Select the action, a_t+1 = π(s_j), with an exploration factor ε^(e)
       5. Update the Q(s_t, a_t) function (if s_j is terminal, set Q(s_t+1, a_t+1) = 0) using max_a Q(s_t+1, a)
       6. Set s_i = s_j