Q-Learning — Section 8: Decision Making Under Uncertainty

Q-learning estimates the optimal action-value function $Q^*(s, a)$ purely from experience, without ever modeling $P(s' | s, a)$ or $R(s, a)$ .

Update rule

After taking action $a$ in state $s$ , observing reward $r$ and next state $s'$ :

Q(s, a) \leftarrow Q(s, a) + \alpha \left[r + \gamma \max_{a'} Q(s', a') - Q(s, a)\right]

$\alpha$ is the learning rate. The bracketed term is the TD error — the difference between current $Q$ and the bootstrap target $r + \gamma \max Q(s', \cdot)$ .

Why max in the target

The target uses $\max_{a'} Q(s', a')$ — the value of acting optimally next, regardless of what the agent actually does. This is what makes Q-learning off-policy: you can learn the optimal Q-function while behaving according to some other policy (e.g., random exploration). Compare to SARSA, which uses $Q(s', a')$ for whatever $a'$ was actually taken — on-policy.

Convergence

Tabular Q-learning converges to $Q^*$ with probability 1 if:

All state-action pairs are visited infinitely often.
Learning rate $\alpha$ satisfies Robbins-Monro: $\sum \alpha = \infty$ and $\sum \alpha^2 < \infty$ .
Bounded rewards.

In practice you use a small constant or slowly decaying $\alpha$ and exploration strategies that visit every state-action pair sufficiently often.

Exploration

A greedy policy w.r.t. current $Q$ may never explore — you'd never visit suboptimal actions and so never learn their values. Standard fix: $\epsilon$ -greedy — pick the greedy action with probability $1 - \epsilon$ , a random action with probability $\epsilon$ . Decay $\epsilon$ over training.

More sophisticated: UCB-based exploration, Boltzmann (softmax over Q-values), intrinsic motivation (count-based bonuses).

Function approximation: deep Q-learning

When the state space is huge or continuous, you can't tabulate Q. Replace the table with a neural network: $Q_\theta(s, a)$ approximates $Q^*(s, a)$ . Train $\theta$ by minimizing TD error.

This is the basic idea of DQN (Mnih et al., 2015), which played Atari from pixels. Required tricks to make it stable:

Experience replay: store transitions in a buffer, sample minibatches randomly. Decorrelates updates.
Target network: a delayed copy of $Q$ used to compute the bootstrap target. Reduces the chasing-its-own-tail dynamics.

Q-learning generalizes far past Atari. AlphaZero is conceptually MCTS guided by a learned value network — a richer cousin of Q-learning at the algorithmic level.