Q-learning

Inside the paper

The problem

An agent in an unfamiliar Markov environment must find good actions without knowing the reward and transition rules in advance. It was unclear under which conditions an incremental learning rule would reliably find optimal action values.

The idea

The paper studies a tabular rule that updates the value of an action from the immediate reward and the best estimated value of the next state. It proves convergence under explicit conditions on experience and learning rates.

How it works

• For each state and action, keep a table entry estimating the discounted return from taking that action and acting optimally afterward.
• After a transition, adjust the entry for the action taken toward the reward plus the discounted maximum entry at the next state.
• Choose an action with the highest table value when exploiting the learned estimates; the training sequence must also sample every state and action repeatedly.
• The proof constructs an artificial action-replay process from past transitions and connects its optimal values to the table entries.

What it showed

The theorem establishes convergence with probability one for finite, discrete environments with bounded rewards, sufficient repeated sampling and appropriate diminishing learning rates. The discussion sketches extensions to absorbing environments and multiple updates, while noting that the proof does not directly cover multi-step versions.

Read it for

Read Section 2 for the update and theorem, then the card-game explanation at the start of Section 3 for the proof strategy. The technical appendix can wait until you want the full argument.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.