Q-Learning - Value-Based RL

Introduction

Q-Learning is one of the most important and widely studied algorithms in reinforcement learning. Developed by Chris Watkins in 1989, it allows an agent to learn the optimal action-value function (Q-function) without needing a model of the environment. The Q-function tells the agent how much total future reward it can expect by taking a specific action in a specific state and then behaving optimally thereafter. Once the Q-function is learned, the optimal policy is simply to choose the action with the highest Q-value in each state.

The Q-Function

Example

Q(s, a) = Expected cumulative discounted reward when: - Starting in state s - Taking action a - Then following optimal policy forever after Q*(s, a) = r(s,a) + γ × max_a' Q*(s', a') This is the Bellman optimality equation for Q-values. It says: optimal Q = immediate reward + discounted best future value

The Q-Learning Algorithm

Algorithm	Q-Learning (Tabular)
Initialize	Q(s, a) = 0 for all states s and actions a
Set	learning rate α (e.g., 0.1), discount γ (e.g., 0.99), exploration ε (e.g., 0.1)
With probability ε	random action (explore)
With probability 1-ε	a = argmax_a Q(s, a) (exploit)

Worked Example: Taxi Problem

States	(taxi_row, taxi_col, passenger_location, destination)
Actions	{North, South, East, West, Pickup, Dropoff}
Rewards	+20 for successful dropoff, -10 for illegal pickup/dropoff, -1 per step
ε-greedy: random action	East
Taxi learns: go to passenger	pickup → go to destination → dropoff

Why Q-Learning is "Off-Policy"

Off-policy	The update rule uses max_a' Q(s', a'), NOT the action
Behavior policy (what agent does)	ε-greedy (explores randomly)
Target policy (what agent learns)	greedy (always take best action)
SARSA update	Q(s,a) ← Q(s,a) + α[r + γ Q(s', a') - Q(s,a)]

Convergence Guarantees

Code example

Q-Learning converges to Q* (optimal Q-function) if:
  1. All state-action pairs visited infinitely often
  2. Learning rate α satisfies: Σ α = ∞ AND Σ α² < ∞
     (e.g., α_t = 1/t)
  3. Environment is stationary (rewards and transitions don't change)

In practice, fixed α (e.g., 0.1) works well for non-stationary problems
but sacrifices convergence guarantee.

Convergence speed depends on:
  - State-action space size (exponential in state dimensions)
  - Reward structure (sparse rewards slow learning)
  - Exploration strategy (better exploration → faster convergence)

Exploration Strategies for Q-Learning

Decay	ε = max(0.01, ε × 0.995) each episode
End	ε ≈ 0.01 (mostly greedy, tiny exploration)
τ high	uniform random (explore)
τ low	nearly greedy (exploit)

Limitations of Tabular Q-Learning

Problem	State space explosion
Chess: ~10^47 states	cannot store Q-table
Atari games: 84×84×4 pixels	256^(84×84×4) possible frames
Robot control: Continuous joint angles	infinite states
1. State discretization	Bin continuous values (loses precision)
2. Function approximation	Neural network approximates Q
3. Feature engineering	Hand-craft compact state representation
Train by minimizing	(r + γ max Q(s', a'; θ⁻) - Q(s, a; θ))²

Q-Learning Variants

Double Q-Learning

Problem: Standard Q-learning overestimates Q-values

(max over noisy estimates is biased high)

Solution: Use one network to SELECT action, another to EVALUATE it

Q(s,a) ← r + γ Q₂(s', argmax_a' Q₁(s', a'))

Prioritized Experience Replay

Replay experiences with high TD error more often

(Surprising experiences are more informative)

Priority ∝ |TD error| + small constant

Dueling DQN

Split Q into state value V(s) and advantage A(s,a):

Q(s,a) = V(s) + A(s,a) - mean(A)

Learns state value separately from action advantages

Summary

Q-Learning provides a principled method for learning optimal behavior through interaction with an environment. Its off-policy nature allows the agent to explore freely while converging to the optimal policy. The algorithm is simple to implement in tabular form, and its extension to function approximation (DQN) enables application to complex, high-dimensional problems. Understanding Q-Learning deeply, including its convergence properties, exploration strategies, and limitations, forms the basis for all modern value-based reinforcement learning methods.

Introduction

The Q-Function

Example

The Q-Learning Algorithm

Algorithm	Q-Learning (Tabular)
Initialize	Q(s, a) = 0 for all states s and actions a
Set	learning rate α (e.g., 0.1), discount γ (e.g., 0.99), exploration ε (e.g., 0.1)
With probability ε	random action (explore)
With probability 1-ε	a = argmax_a Q(s, a) (exploit)

Worked Example: Taxi Problem

States	(taxi_row, taxi_col, passenger_location, destination)
Actions	{North, South, East, West, Pickup, Dropoff}
Rewards	+20 for successful dropoff, -10 for illegal pickup/dropoff, -1 per step
ε-greedy: random action	East
Taxi learns: go to passenger	pickup → go to destination → dropoff

Why Q-Learning is "Off-Policy"

Off-policy	The update rule uses max_a' Q(s', a'), NOT the action
Behavior policy (what agent does)	ε-greedy (explores randomly)
Target policy (what agent learns)	greedy (always take best action)
SARSA update	Q(s,a) ← Q(s,a) + α[r + γ Q(s', a') - Q(s,a)]

Convergence Guarantees

Code example

Q-Learning converges to Q* (optimal Q-function) if:
  1. All state-action pairs visited infinitely often
  2. Learning rate α satisfies: Σ α = ∞ AND Σ α² < ∞
     (e.g., α_t = 1/t)
  3. Environment is stationary (rewards and transitions don't change)

In practice, fixed α (e.g., 0.1) works well for non-stationary problems
but sacrifices convergence guarantee.

Convergence speed depends on:
  - State-action space size (exponential in state dimensions)
  - Reward structure (sparse rewards slow learning)
  - Exploration strategy (better exploration → faster convergence)

Exploration Strategies for Q-Learning

Decay	ε = max(0.01, ε × 0.995) each episode
End	ε ≈ 0.01 (mostly greedy, tiny exploration)
τ high	uniform random (explore)
τ low	nearly greedy (exploit)

Limitations of Tabular Q-Learning

Problem	State space explosion
Chess: ~10^47 states	cannot store Q-table
Atari games: 84×84×4 pixels	256^(84×84×4) possible frames
Robot control: Continuous joint angles	infinite states
1. State discretization	Bin continuous values (loses precision)
2. Function approximation	Neural network approximates Q
3. Feature engineering	Hand-craft compact state representation
Train by minimizing	(r + γ max Q(s', a'; θ⁻) - Q(s, a; θ))²

Q-Learning Variants

Double Q-Learning

Problem: Standard Q-learning overestimates Q-values

(max over noisy estimates is biased high)

Solution: Use one network to SELECT action, another to EVALUATE it

Q(s,a) ← r + γ Q₂(s', argmax_a' Q₁(s', a'))

Prioritized Experience Replay

Replay experiences with high TD error more often

(Surprising experiences are more informative)

Priority ∝ |TD error| + small constant

Dueling DQN

Split Q into state value V(s) and advantage A(s,a):

Q(s,a) = V(s) + A(s,a) - mean(A)

Learns state value separately from action advantages

Q-Learning - Value-Based RL

Introduction

The Q-Function

The Q-Learning Algorithm

Worked Example: Taxi Problem

Why Q-Learning is "Off-Policy"

Convergence Guarantees

Exploration Strategies for Q-Learning

Limitations of Tabular Q-Learning

Q-Learning Variants

Double Q-Learning

Prioritized Experience Replay

Dueling DQN

Summary

Continue learning this concept

Q-Learning - Value-Based RL

Introduction

The Q-Function

The Q-Learning Algorithm

Worked Example: Taxi Problem

Why Q-Learning is "Off-Policy"

Convergence Guarantees

Exploration Strategies for Q-Learning

Limitations of Tabular Q-Learning

Q-Learning Variants

Double Q-Learning

Prioritized Experience Replay

Dueling DQN

Summary

Continue learning this concept