AI Notes
Introduction to RL. Agents, environments, rewards, MDP. RL fundamentals 2024.
Introduction
Within the broader landscape of machine learning, reinforcement learning occupies a unique position. While supervised learning requires labeled examples and unsupervised learning finds patterns in unlabeled data, reinforcement learning operates in a fundamentally different paradigm: an agent learns by taking actions in an environment and receiving reward signals that indicate how well it is performing. There is no dataset of correct input-output pairs. Instead, the agent must discover which actions lead to the most cumulative reward through its own experience.
Position in Machine Learning
| Input | (x, y) pairs — features and correct labels |
| Goal: Learn f(x) | y |
| Examples | Image classification, spam detection, price prediction |
| Input | x only — no labels |
| Goal | Discover structure (clusters, distributions, representations) |
| Examples | Customer segmentation, topic modeling, anomaly detection |
| Input | (state, action, reward, next_state) from interaction |
| Goal: Learn policy π(s) | a that maximizes cumulative reward |
| Examples | Game playing, robot control, resource optimization |
| Key difference | RL deals with SEQUENTIAL decisions where |
Core Algorithm: Q-Learning
Q-Learning Algorithm
Initialize Q-table: Q(s, a) = 0 for all state-action pairs
For each episode
s = initial state
While not terminal
Choose action a using ε-greedy on Q(s, ·)
Take action a, observe reward r and next state s'
Update: Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]
s ← s'
Parameters
α = learning rate (0.1): How much to update toward new estimate
γ = discount factor (0.99): How much to value future rewards
ε = exploration rate (0.1 → 0): Probability of random action
Worked Example: Cliff Walking
| Grid world | 4×12, start at bottom-left, goal at bottom-right |
| All other steps | reward -1 |
| Optimal path | Go up, traverse top row, come down to goal |
| Total reward for optimal path | -13 (13 steps) |
Deep Q-Networks (DQN)
When state space is too large for a table (e.g., Atari game pixels):
Replace Q-table with neural network
Q(s, a; θ) ≈ true Q-value
DQN Architecture
Input: Game screen (84×84×4 stacked frames)
Conv layers: Extract visual features
Dense layers: Map features to Q-value per action
Output: Q(s, left), Q(s, right), Q(s, fire), ...
Key innovations
1. Experience Replay:
Store transitions (s, a, r, s') in replay buffer
Train on random batches (breaks correlation between consecutive samples)
2. Target Network:
Separate network for computing target Q-values
Updated slowly (every 10K steps)
Stabilizes training (target doesn't change with every update)
DQN Loss
L = (r + γ max_a' Q_target(s', a') - Q(s, a; θ))²
Policy Gradient Methods
| 3. Update | θ ← θ + α Σ_t ∇log π_θ(a_t|s_t) × G_t |
| Intuition | Increase probability of actions that led to high reward |
| Episode 1: Actions [left, left, right] | total reward = 5 |
| Episode 2: Actions [right, right, left] | total reward = 2 |
| Update | Make [left, left, right] pattern more likely |
Actor-Critic Methods
Combine value-based and policy-based approaches
Actor: Policy network π_θ(a|s) — chooses actions
Critic: Value network V_φ(s) — evaluates states
Training
1. Actor takes action a in state s
2. Observe reward r and next state s'
3. Critic computes advantage: A = r + γV(s') - V(s)
(Was this action better or worse than average?)
4. Update actor: θ ← θ + α ∇log π_θ(a|s) × A
5. Update critic: φ ← φ - α ∇(r + γV(s') - V_φ(s))²
Advantage of actor-critic
- Lower variance than pure policy gradient (REINFORCE)
- More stable than pure value methods in continuous spaces
- PPO and A3C are actor-critic variants used in practice
Multi-Armed Bandit: Simplified RL
| Scenario | Choose between k slot machines, each with unknown payout |
| Machine 1 | Average payout $3.2 (unknown to agent) |
| Machine 2 | Average payout $5.1 (unknown to agent) |
| Machine 3 | Average payout $2.8 (unknown to agent) |
| Pull 1: Try machine 1 | get $4 → Q(1) = 4.0 |
| Pull 2: Try machine 2 | get $6 → Q(2) = 6.0 |
| Pull 3: Try machine 3 | get $2 → Q(3) = 2.0 |
| Pull 4: ε=0.1, random | machine 1 → get $3 → Q(1) = 3.5 |
| Pull 5: Exploit best | machine 2 → get $5 → Q(2) = 5.5 |
RL vs Supervised Learning
| Aspect | Supervised Learning | Reinforcement Learning |
|---|---|---|
| Feedback | Correct answer given | Reward signal (delayed, scalar) |
| Data | Static dataset | Generated by interaction |
| Goal | Minimize prediction error | Maximize cumulative reward |
| Decisions | Independent | Sequential (affect future) |
| Exploration | Not needed | Critical for learning |
| Credit assignment | Direct (label per input) | Temporal (which action caused reward?) |
Summary
Reinforcement learning addresses the fundamental challenge of sequential decision-making under uncertainty. From Q-learning tables to Deep Q-Networks to policy gradient methods, the field offers a progression of techniques for increasingly complex problems. Its unique characteristics, including delayed rewards, the exploration-exploitation tradeoff, and the credit assignment problem, make it both challenging and powerful. RL has achieved superhuman performance in games, enabled agile robotic control, and now plays a crucial role in aligning large language models with human preferences.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Reinforcement Learning Basics.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, machine, learning, reinforcement, reinforcement learning basics
Related Artificial Intelligence Topics