Q-learning
/ kyoo LURN-ing /
Q-learning is the classic recipe for letting an agent learn the quality of its actions purely by trial and error, without ever being told the rules of its world. Imagine keeping a big notebook with a score for every (situation, action) pair — its Q-value. Every time the agent acts, sees the result, and lands somewhere new, it nudges that one score a little closer to the truth: 'the reward I just got, plus how good the best action looks from where I ended up.' Slowly the whole notebook fills in with accurate numbers.
The clever part is which future it assumes when updating. Q-learning always updates as if it will act optimally from the next state onward — it reaches for the best available action there, regardless of what it actually did next. This is what makes it 'off-policy': it can wander around exploring with random moves, yet still learn the values of the ideal, greedy strategy. Once the notebook is filled, the agent just reads off the highest-scoring action in each state, and that is its optimal policy.
Under reasonable conditions — every state-action pair tried often enough, learning rate decayed properly — tabular Q-learning is proven to converge to the truly optimal values. That's a beautiful guarantee, but it comes with a quiet ceiling: it needs a separate entry for every situation, so it only works when situations are few enough to list. The moment the world has more states than atoms in a chessboard's worth of positions, you can't keep a notebook — which is exactly the gap the deep Q-network was invented to bridge.
An agent in a maze tries 'go right,' gets reward 0, and lands on a square whose best action it currently rates at 9. With learning rate 0.5 and no discount, it updates Q(here, right) toward 0 + 9 = 9, moving it halfway there. Repeat across thousands of episodes and the maze's true values emerge.
Each step nudges one Q-value toward 'reward now + best value next.' Off-policy: it learns the optimal even while exploring randomly.
Q-learning's convergence proof applies to the tabular case — one cell per state-action pair. Replace the table with a neural network (as in DQN) and the guarantees evaporate; training can oscillate or diverge, which is why DQN needed extra tricks like experience replay and a frozen target network just to stay stable.