Q-Learning

Summary

Watkins and Dayan give the classic convergence proof for tabular Q-learning. They frame Q-learning as both model-free reinforcement learning and asynchronous dynamic programming: the agent improves estimates of action values from sampled transitions without first learning an explicit transition model.

This is a partial ingest based on the full extracted text, focused on the update rule, convergence theorem, proof idea, and later wiki connections.

Key Claims

• Q-learning can learn optimal action values in a finite controlled Markov process without knowing the transition probabilities or expected rewards.
• The learned action-value function Q*(x,a) is enough to recover an optimal stationary policy by choosing an action that maximizes Q*(x,a) in each state.
• Under bounded rewards, tabular representation, repeated sampling of every state-action pair, and Robbins-Monro-style learning-rate conditions, Q-learning converges to the optimal action values with probability 1.
• The method is an incremental dynamic-programming procedure: it updates one or more sampled action values using a bootstrap target rather than solving the full model.
• The paper sketches extensions to undiscounted absorbing tasks and to updates of multiple Q-values per iteration, while noting that the proof does not immediately cover every later variant such as TD(lambda)-style multi-step updates.

Methods / Formalism

• The environment is a finite controlled Markov process. At step n, the agent observes state x_n, chooses action a_n, receives reward r_n, and transitions to y_n.
• The optimal state value satisfies the dynamic-programming equation

$$V^{\ast }(x)=\underset{a}{\max }\left(R_x(a)+\gamma \sum _y{P}_{xy}[a]V^{\ast }(y)\right).$$

• For a policy pi, the action value Q^pi(x,a) is the expected discounted return after taking action a in state x and following pi thereafter. The optimal action values satisfy V*(x)=max_a Q*(x,a).
• The tabular Q-learning update is

$$Q_n(x,a)=(1-{\alpha }_n)Q_{n-1}(x,a)+{\alpha }_n\left[r_n+\gamma \underset{b}{\max }{Q}_{n-1}(y_n,b)\right]$$

when (x,a)=(x_n,a_n), and leaves all other entries unchanged.

• The convergence theorem assumes bounded rewards, 0 < alpha_n < 1, every state-action pair sampled infinitely often, sum_i alpha_{n_i(x,a)} = infinity, and sum_i alpha_{n_i(x,a)}^2 < infinity.
• See Q-Learning Convergence for the action-replay-process proof schema.

Evidence / Experiments

• This is a theory note rather than an empirical benchmark paper.
• The evidence is the convergence proof. The core construction is an artificial action-replay process built from the history of sampled transitions and learning rates.
• The proof shows that this replay process has the learner’s current Q-values as its optimal action values and that, with probability 1, its estimated transition and reward behavior converges to the real Markov process.

Connections

• Grounds Q-Learning as a standalone concept and strengthens Temporal Difference Learning with the original tabular convergence result.
• Helps interpret modern deep TD work such as Gallici2025 - Simplifying Deep Temporal Difference Learning: later neural methods inherit the update shape but not the tabular convergence assumptions.
• Connects to Value Decomposition Networks because VDN-style cooperative MARL uses Q-learning losses over factored team values.
• Provides background for Reward Machines, where tabular Q-learning variants can regain convergence under product-state or counterfactual-update constructions.

Open Questions

• Which parts of the tabular convergence theorem survive function approximation, replay buffers, target networks, and off-policy data reuse?
• How should safe-RL shields or action masks be analyzed when they alter the visitation condition needed for tabular convergence?
• When does a learned abstraction preserve enough Markov structure for Q-learning-style guarantees to remain meaningful?

Citation

Watkins, Christopher J. C. H., and Peter Dayan. 1992. “Q-Learning.” Machine Learning 8: 279-292.