Q-Learning and Value-Based Reinforcement Learning

Table of Contents

• 1. The MDP Framework
• 2. Value Functions
  • 2.1 State-Value and Action-Value Functions
  • 2.2 Bellman Consistency Equations
• 3. Optimal Value Functions
  • 3.1 The Bellman Optimality Equations
  • 3.2 The Bellman Operator Is a Contraction
• 4. Value Iteration
• 5. Q-Learning: Stochastic Approximation of Value Iteration
  • 5.1 The Update Rule
  • 5.2 Convergence
  • 5.3 SARSA: On-Policy TD
• 6. The Deadly Triad and Deep Q-Learning
  • 6.1 The Deadly Triad
  • 6.2 DQN
  • 6.3 Double DQN: Fixing Overestimation
• 7. Scope and Limitations
• References

1. The MDP Framework 🎯

Q-learning operates inside the Markov Decision Process (MDP) formalism. An MDP is a tuple \((\mathcal{S}, \mathcal{A}, P, r, \gamma)\):

• \(\mathcal{S}\): state space
• \(\mathcal{A}\): action space
• \(P(s' \mid s, a)\): transition kernel — probability of reaching \(s'\) from \((s,a)\)
• \(r(s, a)\): bounded reward function
• \(\gamma \in [0, 1)\): discount factor

A policy \(\pi: \mathcal{S} \to \Delta(\mathcal{A})\) maps states to distributions over actions. The agent’s goal is to find the policy \(\pi^*\) that maximizes expected discounted return from every state simultaneously.

The Markov property — \(s_{t+1} \perp s_{0:t-1}, a_{0:t-1} \mid s_t, a_t\) — is the assumption that the current state contains all information relevant to the future. This is what makes value functions well-defined.

2. Value Functions 📐

2.1 State-Value and Action-Value Functions

For a fixed policy \(\pi\), define:

State-value function: \[V^\pi(s) = \mathbb{E}_\pi\!\left[\sum_{t=0}^\infty \gamma^t r(s_t, a_t) \;\bigg|\; s_0 = s\right]\]

Action-value function (Q-function): \[Q^\pi(s, a) = \mathbb{E}_\pi\!\left[\sum_{t=0}^\infty \gamma^t r(s_t, a_t) \;\bigg|\; s_0 = s,\, a_0 = a\right]\]

The Q-function conditions on a specific first action \(a\), then follows \(\pi\) thereafter. The two functions are related by:

\[V^\pi(s) = \mathbb{E}_{a \sim \pi(\cdot|s)}\!\left[Q^\pi(s, a)\right] = \sum_a \pi(a \,|\, s)\,Q^\pi(s, a)\]

The Q-function is the more useful object for control: given \(Q^\pi\), improving the policy is trivial — just act greedily. Given only \(V^\pi\), you need the model \(P\) to compute \(\mathbb{E}[V^\pi(s')]\) and evaluate actions.

2.2 Bellman Consistency Equations

\(Q^\pi\) satisfies a self-consistency (Bellman) equation. Expanding the return by peeling off the first step:

\[Q^\pi(s, a) = \mathbb{E}_{s' \sim P(\cdot|s,a)}\!\left[r(s,a) + \gamma\,V^\pi(s')\right] = \mathbb{E}_{s'}\!\left[r(s,a) + \gamma\sum_{a'}\pi(a'|s')\,Q^\pi(s',a')\right]\]

Define the Bellman operator for policy \(\pi\):

\[(\mathcal{T}^\pi Q)(s,a) = \mathbb{E}_{s'}\!\left[r(s,a) + \gamma\sum_{a'}\pi(a'|s')\,Q(s',a')\right]\]

Then \(Q^\pi\) is the unique fixed point \(\mathcal{T}^\pi Q^\pi = Q^\pi\).

3. Optimal Value Functions 🔑

3.1 The Bellman Optimality Equations

Define the optimal value functions:

\[V^*(s) = \max_\pi V^\pi(s), \qquad Q^*(s,a) = \max_\pi Q^\pi(s,a)\]

These exist and are unique for discounted MDPs (by compactness of the policy space and linearity of the value functional in \(\pi\) for fixed \(s,a\)). They satisfy the Bellman optimality equations:

\[Q^*(s,a) = \mathbb{E}_{s' \sim P(\cdot|s,a)}\!\left[r(s,a) + \gamma\,\max_{a'}\,Q^*(s',a')\right]\]

\[V^*(s) = \max_a\,\mathbb{E}_{s'}\!\left[r(s,a) + \gamma\,V^*(s')\right]\]

Key structural fact: Any policy \(\pi^*\) satisfying \(\pi^*(s) \in \arg\max_a Q^*(s,a)\) is optimal. Once \(Q^*\) is known, deriving the optimal policy requires no further computation — just a greedy table lookup.

3.2 The Bellman Operator Is a Contraction

Define the Bellman optimality operator:

\[(\mathcal{T}Q)(s,a) = \mathbb{E}_{s'}\!\left[r(s,a) + \gamma\,\max_{a'}\,Q(s',a')\right]\]

Theorem. \(\mathcal{T}\) is a contraction on \((\ell^\infty(\mathcal{S} \times \mathcal{A}), \|\cdot\|_\infty)\) with factor \(\gamma\):

\[\|\mathcal{T}Q - \mathcal{T}Q'\|_\infty \leq \gamma\,\|Q - Q'\|_\infty\]

Proof. For any \((s,a)\):

\[|(\mathcal{T}Q)(s,a) - (\mathcal{T}Q')(s,a)| = \gamma\,\left|\mathbb{E}_{s'}\!\left[\max_{a'}Q(s',a') - \max_{a'}Q'(s',a')\right]\right|\]

Use the fact that \(|\max_a f(a) - \max_a g(a)| \leq \max_a |f(a) - g(a)|\) and linearity of expectation:

\[\leq \gamma\,\mathbb{E}_{s'}\!\left[\max_{a'}\left|Q(s',a') - Q'(s',a')\right|\right] \leq \gamma\,\|Q - Q'\|_\infty\]

Taking the sup over \((s,a)\) gives \(\|\mathcal{T}Q - \mathcal{T}Q'\|_\infty \leq \gamma\|Q-Q'\|_\infty\). \(\square\)

By Banach’s fixed-point theorem: \(Q^*\) is the unique fixed point of \(\mathcal{T}\), and for any initialization \(Q_0\):

\[\|Q_k - Q^*\|_\infty \leq \gamma^k\,\|Q_0 - Q^*\|_\infty\]

convergence is geometric in \(k\) with rate \(\gamma\).

4. Value Iteration 🔄

Value iteration is the direct application of the Bellman operator: start from any \(Q_0\) and iterate \(Q_{k+1} = \mathcal{T}Q_k\). Explicitly, for all \((s,a)\):

\[Q_{k+1}(s,a) = \sum_{s'} P(s'|s,a)\left[r(s,a) + \gamma\,\max_{a'} Q_k(s',a')\right]\]

By the contraction theorem, this converges to \(Q^*\) geometrically. The greedy policy \(\pi_{k+1}(s) = \arg\max_a Q_{k+1}(s,a)\) converges to \(\pi^*\).

Requirement: computing \(\mathcal{T}Q_k\) requires summing over all \(s'\) weighted by \(P(s'|s,a)\) — the transition model. Value iteration is a model-based planning algorithm.

Complexity: each sweep costs \(O(|\mathcal{S}|^2 |\mathcal{A}|)\) — feasible for small tabular MDPs, intractable for large or continuous state spaces.

5. Q-Learning: Stochastic Approximation of Value Iteration 💡

Q-learning removes the model requirement by replacing the exact expectation in \(\mathcal{T}\) with a single sampled transition.

5.1 The Update Rule

Given a transition \((s, a, r, s')\) observed from the environment:

\[Q(s,a) \leftarrow Q(s,a) + \alpha_t\,\underbrace{\bigl[r + \gamma\max_{a'} Q(s',a') - Q(s,a)\bigr]}_{\delta_t\;:\;\text{TD error}}\]

The TD error \(\delta_t\) is a noisy estimate of \((\mathcal{T}Q)(s,a) - Q(s,a)\): if \(\delta_t > 0\), \(Q(s,a)\) was too pessimistic about \((s,a)\) given this transition; if \(\delta_t < 0\), too optimistic. The update moves \(Q(s,a)\) in the direction of the one-sample Bellman target \(r + \gamma\max_{a'} Q(s',a')\).

Off-policy. The update uses \(\max_{a'} Q(s',a')\) — the greedy action — regardless of what the behavior policy (the policy used to collect the transition) actually did. This makes Q-learning off-policy: data can come from any distribution over \((s,a)\) pairs (e.g., a replay buffer, a random policy, a human demonstrator) as long as it covers all \((s,a)\).

Contrast with SARSA. SARSA replaces \(\max_{a'} Q(s',a')\) with \(Q(s', a'_\text{behavior})\), where \(a'_\text{behavior} \sim \pi_\text{behavior}(\cdot|s')\) is the action actually taken next. This makes SARSA on-policy — it evaluates the behavior policy rather than the greedy policy.

5.2 Convergence

Theorem (Watkins & Dayan, 1992). Tabular Q-learning with learning rates \(\{\alpha_t\}\) converges to \(Q^*\) almost surely, provided:

1. Exploration: every \((s,a)\) pair is visited infinitely often
2. Robbins–Monro: \(\sum_t \alpha_t(s,a) = \infty\) and \(\sum_t \alpha_t(s,a)^2 < \infty\) for all \((s,a)\)
3. Bounded rewards: \(|r| \leq r_\text{max} < \infty\)

The Robbins–Monro condition (e.g., \(\alpha_t = 1/t\)) ensures the updates are large enough to eventually correct any initialization, but small enough that noise averages out. The proof uses stochastic approximation theory (Borkar, Tsitsiklis): the Q-learning update is an asynchronous stochastic version of value iteration, and the noise (from single-sample transitions) has conditional mean zero given \(Q_t\).

5.3 SARSA: On-Policy TD

For completeness, SARSA (State-Action-Reward-State-Action) uses the actual next action in the target:

\[Q(s,a) \leftarrow Q(s,a) + \alpha\bigl[r + \gamma Q(s', a') - Q(s,a)\bigr], \quad a' \sim \pi(\cdot|s')\]

SARSA converges to \(Q^{\pi}\) for the current behavior policy \(\pi\). If \(\pi\) is \(\epsilon\)-greedy and \(\epsilon \to 0\), SARSA converges to \(Q^*\) — but more slowly than Q-learning because it evaluates the exploratory policy, not the greedy one.

6. The Deadly Triad and Deep Q-Learning ⚠️

6.1 The Deadly Triad

Tabular Q-learning converges because \(Q(s,a)\) for each \((s,a)\) is an independent parameter — updating one doesn’t change others. With function approximation \(Q_\phi(s,a)\) (e.g., a neural network), updating the parameters \(\phi\) changes \(Q_\phi\) at all \((s,a)\) simultaneously. Three ingredients combine to cause potential divergence:

1. Function approximation. \(Q_\phi\) is a smooth function of \(\phi\); a gradient step on one \((s,a)\) moves \(Q_\phi\) at nearby states too. The update is no longer a local table write.

2. Bootstrapping. The TD target \(r + \gamma\max_{a'} Q_\phi(s',a')\) depends on \(Q_\phi\) itself. You are fitting \(Q_\phi\) toward a target that moves as \(\phi\) moves — chasing a moving goalposts. The semi-gradient update:

\[\phi \leftarrow \phi + \alpha\,\delta_t\,\nabla_\phi Q_\phi(s,a)\]

does not gradient-descend any fixed loss — \(\delta_t\) depends on \(\phi\), but the gradient is taken only through \(Q_\phi(s,a)\), not through the target. This is not a true gradient step.

3. Off-policy training. Replay buffer samples come from policies different from \(\pi_\text{greedy}\), creating a mismatch between the distribution the function approximator is trained on and the distribution it’s evaluated on.

Any two of these three are benign; all three together can cause divergence (Baird’s counterexample demonstrates this for linear function approximation).

6.2 DQN

DQN (Mnih et al., 2015) stabilizes deep Q-learning with two engineering interventions:

Experience replay. Store transitions \((s,a,r,s')\) in a replay buffer \(\mathcal{B}\). Sample mini-batches uniformly at random for gradient updates. This breaks temporal correlations (which destabilize SGD) and allows data reuse.

Target network. Maintain a target network \(Q_{\phi^-}\) with parameters \(\phi^-\) frozen for \(k\) steps. Use \(Q_{\phi^-}\) for the Bellman target:

\[\mathcal{L}(\phi) = \mathbb{E}_{(s,a,r,s') \sim \mathcal{B}}\!\left[\bigl(r + \gamma\max_{a'} Q_{\phi^-}(s',a') - Q_\phi(s,a)\bigr)^2\right]\]

This is a proper least-squares regression problem (for the \(k\) steps the target is frozen). Every \(k\) steps, \(\phi^- \leftarrow \phi\).

The target network slows the bootstrap feedback loop — the goalposts move, but slowly. Neither intervention is theoretically principled; both are empirical stabilizers. DQN still provably can diverge on some MDPs.

6.3 Double DQN: Fixing Overestimation

Q-learning has a systematic overestimation bias. The issue: the target uses \(\max_{a'} Q_\phi(s',a')\), which is the maximum over noisy estimates. For independent noise \(\eta_{a'}\):

\[\mathbb{E}\!\left[\max_{a'} (Q^*(s',a') + \eta_{a'})\right] \geq \max_{a'} Q^*(s',a')\]

(the expectation of the max exceeds the max of the expectations). The bias grows with \(|\mathcal{A}|\) and the noise magnitude.

Double DQN (van Hasselt et al., 2016) decouples action selection from action evaluation:

\[\text{target} = r + \gamma\,Q_{\phi^-}\!\!\left(s',\,\underbrace{\arg\max_{a'} Q_\phi(s',a')}_{\text{online net selects action}}\right)\]

The online network \(Q_\phi\) selects the greedy action; the target network \(Q_{\phi^-}\) evaluates it. Since these are different networks with different noise, the maximum is no longer over correlated estimates — the bias shrinks substantially.

7. Scope and Limitations 🗺️

Q-learning and value-based RL have a specific niche; they are not the universal RL framework.

Works well when: - Action space is discrete and small enough to enumerate (\(\arg\max\) must be computable) - Good exploration is achievable - A replay buffer can be maintained (off-policy is a feature, not a bug)

Fails or struggles when: - Continuous actions: \(\arg\max_a Q_\phi(s,a)\) over continuous \(\mathcal{A}\) requires a nested optimization loop. DDPG and TD3 sidestep this by learning a separate actor network \(\mu_\psi(s) \approx \arg\max_a Q_\phi(s,a)\) — making them actor-critic methods, not pure Q-learning. - High-dimensional state + function approximation + off-policy: the deadly triad. Convergence is not guaranteed. - Reward shaping sensitivity: the greedy policy is sensitive to small errors in \(Q_\phi\). Policy gradient methods, which optimize a smoother objective, can be more robust. - Long horizon / sparse reward: the \(\gamma^T\) discounting means distant rewards contribute negligibly. Reward shaping or hierarchical methods are needed.

The broader RL landscape (for context):

Value-based methods remain the standard for discrete-action problems (Atari, board games, combinatorial optimization). Policy gradient and actor-critic methods dominate continuous control (robotics, locomotion, LLM post-training).

References