Agents Multi Agent Systems And Rl
Q-Learning Fundamentals
Chapter 4's value iteration requires knowing the MDP's full transition model P(s'|s,a) and reward function R(s,a,s') in advance — but in most real problems, the
Jr Codex AI Notes
Level: Advanced Prerequisites: Chapter 4 Time to complete: ~30 minutes
Table of Contents
- The Problem Value Iteration Doesn't Solve
- Q-Values — Action-Values Instead of State-Values
- The Q-Learning Update Rule
- The Q-Learning Algorithm
- A Complete Worked Example
- Why Q-Learning Is "Model-Free"
- From Tables to Neural Networks — a Bridge to Deep RL
- Summary & Next Steps
1. The Problem Value Iteration Doesn't Solve
Chapter 4's value iteration requires knowing the MDP's full transition model P(s'|s,a) and reward function R(s,a,s') in advance — but in most real problems, the agent doesn't know these ahead of time; it only discovers rewards by actually trying actions and observing what happens, exactly as Chapter 3 described.
Value Iteration (Ch.4) Q-Learning (this chapter)
───────────────────────────── ─────────────────────────────
Requires the FULL transition Learns directly from
model and reward function EXPERIENCE — trial and
to be known IN ADVANCE error, exactly as
Chapter 3 described,
("model-based" — you have a but now for STATE-BASED
complete map of the world) problems (Chapter 4)
("model-free" — no map
needed at all, Section 6)
─────────────────────────────────────────
2. Q-Values — Action-Values Instead of State-Values
Chapter 4 tracked V(s) — the value of being in a state. Q-learning tracks Q(s, a) — the value of taking a specific action in a specific state, which turns out to be exactly what's needed when the transition model isn't known in advance.
Q(s, a) — Reading It
─────────────────────────────────────────
Q(s, a) = the expected total discounted reward from taking
action a in state s, and then acting OPTIMALLY
from then on
Once Q is known for EVERY (state, action) pair, the best
action in any state is simply:
best_action(s) = argmax_a Q(s, a)
─────────────────────────────────────────
# A Q-table: one entry per (state, action) pair
q_table = {}
def get_q(q_table, state, action):
return q_table.get((state, action), 0.0) # default: no information yet
def best_action(q_table, state, actions):
return max(actions, key=lambda a: get_q(q_table, state, a))3. The Q-Learning Update Rule
Q-learning updates its estimate of Q(s,a) after every single experienced transition — no need to wait for, or even know, the full transition model.
The Q-Learning Update Rule
─────────────────────────────────────────
Q(s,a) ← Q(s,a) + α [ r + γ max_a' Q(s',a') − Q(s,a) ]
│ │ │ │ │
│ │ │ │ └── OLD estimate
│ │ │ └── best possible value from the NEXT state
│ │ └── the REWARD actually just received
│ └── LEARNING RATE (how much to trust this new info)
└── the CURRENT estimate, being nudged toward a better one
─────────────────────────────────────────
def q_learning_update(q_table, state, action, reward, next_state, actions, alpha=0.1, gamma=0.9):
old_q = get_q(q_table, state, action)
best_next_q = max(get_q(q_table, next_state, a) for a in actions)
# THIS is the Bellman equation (Ch.4), applied incrementally to a SAMPLE
# of experience, rather than requiring the full transition model
td_target = reward + gamma * best_next_q
td_error = td_target - old_q
q_table[(state, action)] = old_q + alpha * td_error
return q_tableConnecting Directly to Chapter 4's Bellman Equation
─────────────────────────────────────────
Bellman equation (Ch.4): V(s) = max_a Σ P(s'|s,a)[R + γV(s')]
REQUIRES summing over ALL possible
next states, weighted by their
KNOWN probabilities
Q-learning update (here): uses just ONE SAMPLED experience
(the actual s', r that happened)
as a STAND-IN for that full sum —
over MANY repeated visits, this
sampling approach converges to
the SAME correct values, without
ever needing to know the true
probabilities directly
─────────────────────────────────────────
4. The Q-Learning Algorithm
Combining Chapter 3's epsilon-greedy exploration strategy with Section 3's update rule into a complete learning algorithm:
import random
class QLearningAgent:
def __init__(self, actions, alpha=0.1, gamma=0.9, epsilon=0.1):
self.actions = actions
self.alpha = alpha
self.gamma = gamma
self.epsilon = epsilon
self.q_table = {}
def choose_action(self, state):
if random.random() < self.epsilon:
return random.choice(self.actions) # EXPLORE (Chapter 3)
return best_action(self.q_table, state, self.actions) # EXPLOIT
def learn(self, state, action, reward, next_state):
self.q_table = q_learning_update(
self.q_table, state, action, reward, next_state,
self.actions, self.alpha, self.gamma
)
def train(self, environment, episodes=1000):
for episode in range(episodes):
state = environment.reset()
done = False
while not done:
action = self.choose_action(state)
next_state, reward, done = environment.step(action)
self.learn(state, action, reward, next_state)
state = next_state5. A Complete Worked Example
Reusing Chapter 4's grid-world MDP, but now learning purely from experience rather than the known transition model:
class GridWorldEnvironment:
"""A simulated environment the agent interacts with step by step (no visible transition model)."""
def __init__(self):
self.reset()
def reset(self):
self.state = (1, 0) # start at bottom-left
return self.state
def step(self, action):
moves = {"up": (-1,0), "down": (1,0), "left": (0,-1), "right": (0,1)}
dr, dc = moves[action]
row, col = self.state
new_row = max(0, min(1, row + dr))
new_col = max(0, min(1, col + dc))
self.state = (new_row, new_col)
if self.state == (0, 1):
return self.state, 10, True # reached the GOAL
elif self.state == (1, 1):
return self.state, -10, True # fell into the TRAP
else:
return self.state, -1, False # small step cost, episode continues
env = GridWorldEnvironment()
agent = QLearningAgent(actions=["up", "down", "left", "right"], epsilon=0.2)
agent.train(env, episodes=2000)
# After training, inspect the learned policy
for state in [(0,0), (1,0)]:
best = best_action(agent.q_table, state, agent.actions)
print(f"Learned best action at {state}: {best}")What Just Happened
─────────────────────────────────────────
The agent NEVER saw the transition model or reward function
directly (unlike Chapter 4's value_iteration, which took
them as explicit arguments) — it discovered good behavior
PURELY by repeatedly acting in the environment, observing
rewards, and updating its Q-table.
After enough episodes, agent.q_table converges to values
very close to Chapter 4's value-iteration solution for the
SAME underlying grid world — two different algorithms,
arriving at the same optimal answer, one requiring a known
model and one requiring only experience.
─────────────────────────────────────────
6. Why Q-Learning Is "Model-Free"
Model-Based vs Model-Free RL
─────────────────────────────────────────
Model-Based (Ch.4's value iteration): requires knowing
P(s'|s,a) and R(s,a,s')
IN ADVANCE — then computes
the optimal policy through
direct calculation
Model-Free (Q-learning): learns Q(s,a) directly
from EXPERIENCE, without
ever explicitly modeling
the environment's
dynamics — appropriate
when the transition
model is UNKNOWN or too
complex to specify by hand
─────────────────────────────────────────
This distinction determines which real-world problems each technique fits: value iteration works well when you can precisely specify the environment (like a board game with known rules); Q-learning is essential when the environment is too complex or unknown to model explicitly upfront (like a robot learning to walk, where the exact physics are impractical to specify by hand) — the agent must learn by doing.
7. From Tables to Neural Networks — a Bridge to Deep RL
The q_table dictionary in this chapter works for small, discrete state spaces — but grows impossibly large for complex environments (imagine trying to enumerate every possible pixel configuration of a video game screen as a "state").
The Scaling Problem
─────────────────────────────────────────
Grid world: a handful of (row, col) states — a table works fine
A video game screen: millions of possible pixel configurations
— a table would need an ASTRONOMICAL number of entries,
most of which would NEVER be visited even once
─────────────────────────────────────────
Deep Q-Networks (DQN) — the Solution
─────────────────────────────────────────
Instead of a TABLE, use a NEURAL NETWORK (full depth in the
Deep Learning Notes) to APPROXIMATE Q(s,a) — the network
takes a state as input (even raw pixels) and outputs
estimated Q-values for each possible action.
This is EXACTLY what DeepMind's famous Atari-playing AI
(2013) and, later, AlphaGo (Module 1, Ch.2's history) used
— this chapter's tabular Q-learning update rule, but with a
neural network standing in for the table.
─────────────────────────────────────────
This is a clean, concrete example of Module 1, Chapter 3's symbolic/sub-symbolic distinction dissolving in practice — Q-learning itself is a classical, symbolic-adjacent algorithm (an explicit update rule, Chapter 3-4's reasoning), but scaling it to real-world complexity requires the sub-symbolic, learned function approximation covered in the Deep Learning notes. Full Deep RL techniques (DQN and beyond) are covered there, building directly on the tabular foundations established in this chapter.
8. Summary & Next Steps
Key Takeaways
- Q-learning tracks the value of state-action pairs
Q(s,a)rather than states alone, and updates its estimates from actual experienced transitions rather than requiring a known transition model. - The Q-learning update rule is the Bellman equation (Chapter 4) applied incrementally to sampled experience, converging to the correct values over many repeated visits without ever needing the true transition probabilities.
- Q-learning is "model-free" — appropriate exactly when the environment's dynamics are unknown or too complex to specify explicitly, unlike Chapter 4's model-based value iteration.
- Tabular Q-learning doesn't scale to environments with enormous or continuous state spaces; Deep Q-Networks replace the table with a neural network function approximator — the technique behind DeepMind's Atari-playing AI and a foundational bridge to the Deep Learning notes' reinforcement learning content.
Module 5 Complete — Next Module
You now have the complete agent-and-learning toolkit: agent architectures from reflex to learning, multi-agent systems and game theory, and the full reinforcement learning arc from bandits through MDPs to Q-learning. Module 6 shifts from "how to build AI" to a critical companion question: "how do we build it responsibly?" — covering bias, fairness, explainability, safety, and governance.
Concept Check
- Why does Q-learning not need to know the environment's transition model in advance, unlike value iteration?
- What specific problem does the Q-learning update rule replace the full Bellman sum with, and why does it still converge correctly?
- Why does tabular Q-learning break down for environments like video games, and what's the Deep Learning notes' solution to that problem?
Next Chapter
→ Module 6: AI Ethics, Safety & Society
Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index