Q-Learning (Off-Policy)

Q-Learning is a temporal-difference off-policy control algorithm that learns the optimal action-value function $Q^*$ directly, with update $Q(s,a) \leftarrow Q(s,a) + \alpha\left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right]$, where $\alpha$ is the learning rate, $r$ the immediate reward, $\gamma$ the discount factor, $s'$ the resulting next state, and $\max_{a'} Q(s',a')$ the greedy maximum over next-state actions (the target), the whole bracket being the TD error.It is off-policy: the behavior policy (how actions are sampled, e.g. $\varepsilon$-greedy) is separated from the target policy (what is learned, greedy $\max$) — experience collected under any exploratory policy is used to optimize the greedy target $\pi(s) = \arg\max_a Q(s,a)$.Tabular convergence requires every $(s,a)$ visited infinitely often and step sizes satisfying the Robbins-Monro conditions $\sum_t \alpha_t = \infty,\; \sum_t \alpha_t^2 < \infty$ (e.g. $\alpha_t = 1/t$), giving $Q \to Q^*$.

model-free off-policy learning with known rewards — navigation, games, action optimization in recommendations; it is also the foundation of deep RL: DQN replaces the table with a network plus replay and target networks, and Double-DQN fixes the max overestimation of this algorithm.

on-policy methods (e.g. SARSA) learn the value of the behavior policy itself and must explore under the current policy; Q-Learning's $\max$ operator points the TD target at the optimal policy, so historical experience from any behavior policy can be reused for faster learning, reaching $Q^*$ with one-step updates — the theoretical origin of off-policy learning (offline RL, experience replay).

Write the Q-learning update in full and explain α, γ, the max term, and the TD error.

Why is Q-Learning off-policy? What are its behavior and target policies?

Convergence conditions for tabular Q-learning? What are the Robbins-Monro step-size conditions?

The overestimation problem caused by the max operator? How does Double Q-Learning fix it?

Q-Learning vs SARSA? How do they behave differently in the Cliff Walking environment?