Reinforcement Learning and Q-Learning

Reinforcement Learning (RL) is a paradigm where an agent learns to make sequences of decisions in an environment to maximize its cumulative long-term reward.

Markov Decision Processes (MDP)

An MDP provides a formal mathematical framework for modeling decision-making under uncertainty, defined by:

• States ($S$): The set of all possible environmental states.
• Actions ($A$): The set of actions available to the agent.
• Transition Probability $P(s' | s, a)$: The probability of transition to state $s'$ given action $a$ in state $s$.
• Reward Function $R(s, a, s')$: The immediate reward received after transitioning.

The Bellman Optimality Equation

The objective is to find a policy $\pi(s)$ that maximizes the expected discounted return $G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$, where $\gamma \in [0, 1)$ is the discount factor.

The optimal action-value function $Q^*(s, a)$ satisfies the Bellman Optimality Equation:

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

Q-Learning (Model-Free Control)

When transition probabilities $P(s'|s,a)$ are unknown, the agent learns $Q$-values through experience using temporal difference updates:

$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, and $r$ is the immediate reward.

Deep Q-Networks (DQN)

In large state spaces, we replace the lookup table $Q(s, a)$ with a neural network $Q(s, a; \theta)$ parameterized by weights $\theta$. We train the network by minimizing the loss against a target value:

$y = r + \gamma \max_{a'} Q(s', a'; \theta^{-})$

where $\theta^{-}$ represents the weights of a separate target network updated periodically to stabilize training. We use an Experience Replay Buffer to store state transitions, breaking sample correlation and stabilizing updates.

Example: Q-Learning Update Step

The following example demonstrates a single Q-learning update step:

# Hyperparameters
alpha = 0.1
gamma = 0.9

q_value = 2.0
reward = 1.0
max_future_q = 3.0

# Temporal difference update
td_target = reward + gamma * max_future_q
new_q = q_value + alpha * (td_target - q_value)

print(f"Updated Q-value: {new_q:.4f}")

Updated Q-value: 2.1700

Exercise

Test your understanding of the discount factor parameter:

Dimensional Complexity

Tabular Q-learning is limited to small discrete environments. Continuous, high-dimensional spaces require deep neural network function approximators (DQNs).

References & Further Reading

• Géron, A. (2022). Hands-On Machine Learning (3rd ed.). O’Reilly Media.