Q-learning

Temporal-difference learning told you how good a situation was. Chris Watkins's 1989 Cambridge thesis told you what to do about it. Q-learning keeps a table of values, one for each state and each action available in it, and updates each entry towards the reward received plus the best value available from the next state. The agent can behave however it likes while learning, exploring, making mistakes, and the table still converges to the values of the optimal policy. Watkins and Peter Dayan published the convergence proof in 1992.

The algorithm is simple enough to write on an index card and general enough to apply to anything that can be described as states, actions and rewards. Through the 1990s it was used on small problems, elevators, network routing, games with a few thousand states, because the table grew with the world.

Replacing the table with a neural network was the obvious extension and the unstable one, and it took until 2013 for DeepMind to make it work. Their deep Q-network learned to play Atari games from pixels using Watkins's update rule with a convolutional network as the table, and the paper that described it was the founding document of deep reinforcement learning.