Q-Learning

Definition

Q-learning is an off-policy temporal-difference control algorithm that learns an optimal action-value function directly from sampled transitions. In the tabular discounted case, the update for a sampled transition (x,a,r,y) is

$$Q(x,a)\leftarrow (1-\alpha )Q(x,a)+\alpha \left[r+\gamma \underset{b}{\max }Q(y,b)\right].$$

Why It Matters

Q-learning is one of the foundational bridges between dynamic programming and reinforcement learning. It separates optimal action-value learning from explicit model estimation: if the learner can estimate Q*(x,a), it can act greedily without knowing the transition matrix. Many later value-based methods, including deep Q-networks, reward-machine learners, and cooperative value-decomposition methods, inherit this update shape while changing the representation and data regime.

Formalism / Key Objects

• Environment: finite controlled Markov process with state x, action a, reward r, transition to y, and discount factor gamma.
• Optimal value relation:

$$V^{\ast }(x)=\underset{a}{\max }{Q}^{\ast }(x,a).$$

• Greedy policy extraction: choose any action a satisfying Q*(x,a)=max_b Q*(x,b).
• Tabular convergence conditions from Watkins1992 - Q-Learning include bounded rewards, infinite visitation of every state-action pair, discrete action-value representation, and learning rates with infinite sum but finite sum of squares.
• Q-Learning Convergence records the action-replay-process proof structure.

Connections

• Temporal Difference Learning is the broader bootstrapping family; Q-learning is one off-policy control member.
• Value Decomposition Networks use Q-learning-style team-value TD losses in cooperative MARL.
• Reward Machines often use Q-learning over a product of environment state and automaton state.
• Safe Reinforcement Learning can wrap Q-learning with shields or action masks, but those interventions may change visitation assumptions.

Common Confusions

• Q-learning is model-free, but its convergence proof still assumes a Markov process and tabular state-action values.
• The classic theorem is not a blanket guarantee for neural-network Q-learning.
• Off-policy means the update targets the greedy optimal value even if behavior during exploration is not greedy.

Key Sources

• Watkins1992 - Q-Learning
• Gallici2025 - Simplifying Deep Temporal Difference Learning