Value-Based Methods

Value iteration is powerful but has a critical limitation: it requires complete knowledge of the environment's dynamics—the transition probabilities $P(s'|s,a)$ and reward function $R(s,a)$. In most real-world scenarios, we don't have this luxury. A robot doesn't know the exact physics of its environment. A game-playing agent doesn't have access to the opponent's strategy. A trading algorithm can't predict market dynamics.

Q-learning, introduced by Chris Watkins in 1989, revolutionized reinforcement learning by showing how to learn optimal behavior directly from experience, without ever constructing a model of the environment. This model-free approach learns action-values (Q-values) by interacting with the environment and observing the consequences of actions.

Remarkably, Q-learning is proven to converge to optimal Q-values under mild conditions—it effectively performs value iteration by sampling, using each observed transition as an incremental update toward the true value.

Recall the Bellman optimality equation for Q-values:

$$Q^(s, a) = R(s, a) + \gamma \sum_{s'} P(s' | s, a) \max_{a'} Q^(s', a')$$

Value iteration computes this exactly by iterating:

$$Q_{k+1}(s, a) = R(s, a) + \gamma \sum_{s'} P(s' | s, a) \max_{a'} Q_k(s', a')$$

But this requires knowing $P(s'|s,a)$—the transition dynamics. What if we could approximate this expectation using samples instead?

The Monte Carlo Baseline

One approach is Monte Carlo estimation: complete entire episodes, compute actual returns $G_t = \sum_{k=0}^\infty \gamma^k r_{t+k+1}$, then average:

$$Q(s, a) \leftarrow \text{Average}(G_t \text{ for all visits to } (s, a))$$

This works but has drawbacks:

• Must wait for episode completion (no learning mid-episode)
• High variance in return estimates
• Doesn't work for continuing (non-episodic) tasks

The Temporal Difference Idea

What if we could bootstrap—use current estimates to improve themselves? This is the core of temporal difference (TD) learning:

Instead of waiting for the true return $G_t$, we use a one-step lookahead:

$$G_t \approx r_{t+1} + \gamma \max_{a'} Q(s_{t+1}, a')$$

This is called the TD target. It combines the observed immediate reward with our current estimate of future value. As our estimates improve, so does the target.

Why Bootstrapping Works

The TD target $r + \gamma \max_{a'} Q(s', a')$ is a biased estimator of $Q^*(s, a)$ because it uses our current (imperfect) estimate. But it has much lower variance than Monte Carlo returns because it doesn't accumulate randomness over the entire trajectory.

The bias-variance trade-off generally favors TD methods in practice, especially when function approximation is involved.

Q-learning is an off-policy TD control algorithm. Let's unpack both terms:

• TD: Uses bootstrapped targets rather than full returns
• Off-policy: The policy being improved (target policy) differs from the policy generating behavior (behavior policy)

The Update Rule

After observing transition $(s, a, r, s')$:

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

Let's dissect each component:

The Complete Algorithm

Q-Learning (Tabular):

1. Initialize $Q(s, a)$ arbitrarily for all $s \in S$, $a \in A$
2. Initialize $Q(s_{terminal}, \cdot) = 0$ for all terminal states
3. For each episode:
   • Initialize state $s$
   • Repeat for each step:
     • Choose action $a$ from $s$ using policy derived from $Q$ (e.g., $\epsilon$-greedy)
     • Take action $a$, observe reward $r$ and next state $s'$
     • Update: $Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s, a)]$
     • $s \leftarrow s'$
   • Until $s$ is terminal

One of Q-learning's remarkable properties is its convergence guarantee: under appropriate conditions, Q-learning converges to $Q^*$ with probability 1.

Main Convergence Theorem

Theorem (Watkins & Dayan, 1992): Q-learning converges to $Q^*$ as $t \to \infty$ with probability 1, provided:

1. The state and action spaces are finite
2. All state-action pairs are visited infinitely often
3. The learning rates $\alpha_t(s, a)$ satisfy:
   • $\sum_{t=0}^\infty \alpha_t(s, a) = \infty$ (rates sum to infinity)
   • $\sum_{t=0}^\infty \alpha_t(s, a)^2 < \infty$ (rates are square-summable)
4. The rewards are bounded

Condition (2) is called the exploration requirement. Condition (3) is the Robbins-Monro condition—the rates must decrease slowly enough to reach any value, but fast enough to damp oscillations.

Proof Sketch

The proof relies on stochastic approximation theory, particularly results on convergence of random iterative processes. Key steps:

1. Express as Stochastic Fixed-Point Iteration

Rewrite the Q-learning update as: $$Q_{t+1}(s, a) = (1 - \alpha_t) Q_t(s, a) + \alpha_t F_t(Q_t)$$

where $F_t(Q) = r_t + \gamma \max_{a'} Q(s_{t+1}, a')$ is a noisy sample of the Bellman operator $T^*$.

2. Show Contraction Property

The expected update direction points toward $Q^$: $$\mathbb{E}[F_t(Q) | s, a] = (T^ Q)(s, a)$$

Since $T^$ is a $\gamma$-contraction, the expected update pulls $Q$ toward $Q^$.

3. Apply Stochastic Approximation Results

With the Robbins-Monro conditions, the noise from sampling averages out over time, and the iterates converge to the fixed point $Q^*$.

Understanding the Exploration Requirement

The condition "all state-action pairs visited infinitely often" is crucial and often misunderstood.

Why it's necessary: Q-learning only updates Q(s, a) when (s, a) is actually experienced. If some pairs are never visited, their Q-values remain at initialization—potentially arbitrarily wrong.

How to satisfy it: Exploration strategies like ε-greedy ensure all actions have positive probability at all states. As long as ε > 0 remains fixed, any (s, a) reachable from the initial state distribution will eventually be visited infinitely often.

The practical trade-off: We want ε to decay for better exploitation, but too-fast decay violates the exploration requirement. Decaying ε to zero means convergence isn't guaranteed—but practically, the policy may still be approximately optimal.

The exploration-exploitation dilemma is a fundamental challenge in RL: exploit current knowledge to maximize immediate reward, or explore to discover potentially better strategies?

ε-Greedy Exploration

The simplest strategy: with probability ε choose uniformly random action, otherwise choose greedy action.

$$\pi_\epsilon(a|s) = \begin{cases} 1 - \epsilon + \epsilon/|A| & \text{if } a = \arg\max_{a'} Q(s, a') \ \epsilon/|A| & \text{otherwise} \end{cases}$$

Advantages: Simple, guaranteed exploration, works well empirically Disadvantages: Wastes exploration on clearly bad actions, treats all non-greedy actions equally

ε Decay Schedules

Typical schedules reduce ε over time as the agent learns:

Linear decay: $\epsilon_t = \max(\epsilon_{min}, \epsilon_0 - t \cdot \delta)$

Exponential decay: $\epsilon_t = \max(\epsilon_{min}, \epsilon_0 \cdot \rho^t)$

Inverse decay: $\epsilon_t = \epsilon_0 / (1 + t \cdot \delta)$

The choice of schedule depends on the problem. Faster decay means less exploration and potentially getting stuck at suboptimal policies. Slower decay wastes time exploring well-understood regions.

Softmax (Boltzmann) Exploration

Instead of treating non-greedy actions equally, softmax weights actions by their Q-values:

$$\pi(a|s) = \frac{e^{Q(s,a)/\tau}}{\sum_{a'} e^{Q(s,a')/\tau}}$$

The temperature parameter τ controls exploration:

• High τ → uniform distribution (exploration)
• Low τ → peaked at max Q (exploitation)
• τ → 0 → greedy policy

Advantage over ε-greedy: Doesn't waste exploration on obviously bad actions. If Q(s, a₁) >> Q(s, a₂), softmax rarely chooses a₂.

Disadvantage: Requires choosing τ appropriately; sensitive to Q-value scale.

Q-learning and SARSA (covered in the next page) represent two fundamental approaches to TD control. Understanding their difference illuminates a core design choice in RL.

The Key Difference

Q-learning update: $$Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma \max_{a'} Q(s', a') - Q(s, a)]$$

SARSA update: $$Q(s, a) \leftarrow Q(s, a) + \alpha [r + \gamma Q(s', a') - Q(s, a)]$$

Notice: Q-learning uses $\max_{a'}$ (optimal action), SARSA uses $a'$ (actual next action taken).

This difference defines:

• Q-learning: Off-policy—learns optimal Q* regardless of behavior policy
• SARSA: On-policy—learns Q for the policy being followed

The Cliff Walking Example

Consider a gridworld with a cliff: the agent must traverse from start to goal near a dangerous edge. Stepping off the cliff gives -100 reward.

Q-learning learns the optimal path along the cliff edge because it evaluates actions assuming optimal future behavior (no accidents). But when actually executing ε-greedy, exploration near the cliff is deadly.

SARSA learns a safer path away from the cliff because it accounts for the exploratory policy's probability of accidentally stepping off. The learned Q-values reflect actual ε-greedy performance, not optimal performance.

This illustrates a fundamental trade-off:

• Q-learning: Optimal in the limit, but risky during learning
• SARSA: Suboptimal in the limit, but safer during learning

Q-learning has a systematic flaw: maximization bias. The max operator in the TD target causes systematic overestimation of Q-values.

The Problem

Consider a state where all actions have true value Q*(s, a) = 0. Due to noise from limited samples, our estimates will scatter around 0: some above, some below.

Q-learning's target uses $\max_{a'} Q(s', a')$. This selects the highest (most positive error) estimate, biasing the target upward. Over time, this bias compounds, leading to systematic overestimation.

Example: State s has 10 actions, all with true value 0. If Q-estimates are N(0, 1), then $\mathbb{E}[\max_a Q] \approx 1.54$ — significantly positive despite true value being 0.

Double Q-Learning

Double Q-learning (Van Hasselt, 2010) maintains two Q-tables, $Q_A$ and $Q_B$, and decouples action selection from value estimation:

1. Use $Q_A$ to select the best action: $a^* = \arg\max_a Q_A(s', a)$
2. Use $Q_B$ to evaluate it: $Q_B(s', a^*)$
3. Update: $Q_A(s, a) \leftarrow Q_A(s, a) + \alpha[r + \gamma Q_B(s', a^*) - Q_A(s, a)]$
4. With 50% probability, swap roles of $Q_A$ and $Q_B$

Since $Q_B$ is independent of the selection made by $Q_A$, the positive-bias-selects-positive-error loop is broken.

Empirical Results

Double Q-learning converges to the correct values where standard Q-learning overshoots. In environments with many actions or noisy rewards, the difference is dramatic:

Double Q-learning's unbiased estimates translate to better policies, faster convergence, and more stable learning in practice.

Successfully applying Q-learning requires careful attention to hyperparameters, initialization, and potential failure modes.

Learning Rate Selection

The learning rate α controls the trade-off between stability and adaptability:

• Too high (α → 1): Q-values oscillate wildly, never converging
• Too low (α → 0): Learning is extremely slow, may not adapt to non-stationarity
• Sweet spot (α ≈ 0.1–0.5): Balances responsiveness with stability

For non-stationary environments, a small constant α is often better than decaying rates, as it allows tracking changing dynamics.

Hyperparameter Sensitivity

Rule of thumb: Start with α = 0.1, γ = 0.99, ε decaying from 1.0 to 0.01 over ~90% of training. Adjust based on observed learning curves.

Tabular Q-learning cannot scale to large or continuous state spaces. With 1000 states and 10 actions, we store 10,000 values. With a million states, 10 million. For continuous states (robot joint angles, pixel observations), tabular representation is impossible.

Function approximation replaces the Q-table with a parameterized function $Q(s, a; \theta)$ that generalizes across states:

$$Q(s, a; \theta) \approx Q^*(s, a)$$

Neural networks are the most powerful function approximators, leading to Deep Q-Networks (DQN).

The DQN Innovation

Naively applying neural networks to Q-learning fails due to:

1. Correlated samples: Sequential experience is highly correlated, violating i.i.d. assumptions
2. Non-stationary targets: The TD target changes as Q changes, destabilizing learning

DQN solutions:

• Experience replay: Store transitions in a buffer, sample mini-batches randomly for training (breaks correlation)
• Target networks: Use a separate, slowly-updated network for TD targets (stabilizes targets)

These innovations, combined with deep neural networks, enabled DQN to achieve superhuman performance on Atari games in 2015—a landmark in AI.

Q-learning is a foundational algorithm that enables learning optimal behavior directly from experience. Let's consolidate the key insights:

What's next: While Q-learning is off-policy (learning Q* while following any exploratory policy), sometimes we want to learn the value of the policy we're actually following. The next page introduces SARSA, Q-learning's on-policy cousin, which learns Q^π for the behavior policy π.