Markov Decision Processes Without The Math Anxiety
You’ve just watched your random agent bounce between two positions in LineWorld, never reaching the goal. It picks left, then right, then left, then right — stuck in an infinite loop, making no progress. You refresh the notebook, run it again, and the same thing happens. The agent has no memory, no structure, no way to think about the future. It’s like a toddler who keeps reaching for the cookie jar in the same way, even though it burned them last time.
What’s missing? The agent needs a framework — a way to model the world so it can make smarter choices. It needs to know: where am I? What can I do? What happens if I do it? And how good is that outcome, really?
That framework is called a Markov Decision Process (MDP). By the end of this article, you’ll be able to describe any reinforcement learning problem as an MDP, and you’ll write code that turns a random walker into a goal-seeking agent.
Let’s start by seeing the problem one more time — the ‘before’ picture.
import numpy as np
class LineWorld:
"""A simple 1D world with 5 positions. Goal is at position 4."""
def __init__(self):
self.n_states = 5
self.goal_state = 4
self.current_state = 0
def step(self, action):
"""Take an action: 0 = left, 1 = right. Returns (next_state, reward, done)."""
if action == 0: # left
self.current_state = max(0, self.current_state - 1)
else: # right
self.current_state = min(self.n_states - 1, self.current_state + 1)
reward = 1 if self.current_state == self.goal_state else 0
done = (self.current_state == self.goal_state)
return self.current_state, reward, done
def reset(self):
self.current_state = 0
return self.current_state
# Run a random agent in LineWorld
np.random.seed(42)
env = LineWorld()
state = env.reset()
print("Starting random agent in LineWorld...")
print(f"Goal is at position {env.goal_state}")
print()
for t in range(20):
action = np.random.choice([0, 1]) # random action
next_state, reward, done = env.step(action)
action_name = "left" if action == 0 else "right"
print(f"Step {t+1}: State {state} -> {action_name} -> State {next_state}, Reward {reward}")
state = next_state
if done:
print("\nReached goal! (But it was pure luck)")
break
print("\nThe random agent never learns. It needs a model of the world.")When you run that, you’ll see the agent bouncing around randomly. It might accidentally reach the goal once in a while, but it can’t repeat that success. It has no idea what actions lead to good outcomes.
What Is a Markov Decision Process? (The Intuition First)
Remember the toddler-and-cookie-jar story from Part 1? Let’s revisit it. A toddler wants a cookie from a jar on the counter. The toddler’s world has:
- States: where the hand is (near jar, far from jar, on the hot stove)
- Actions: reach left, reach right, grab
- Transitions: reaching left moves the hand left, but with some randomness — the hand might slip
- Rewards: cookie = +10, burn = -10, nothing = 0
- Discount: a cookie now is better than a cookie in 10 seconds
That’s an MDP. It’s just a way of writing down the rules of the game. The MDP doesn’t tell the agent what to do. It just describes the world the agent lives in.
Formally, an MDP is a tuple: (S, A, P, R, γ). Let’s break that down:
- S: The set of all possible states. “Where the hand is.”
- A: The set of all possible actions. “What the toddler tries.”
- P: Transition probabilities. “What actually happens.” For example, reaching right might move the hand right 80% of the time, but 20% of the time it slips.
- R: Rewards. “The cookie or the burn.”
- γ (gamma): Discount factor. “A cookie now is better than a cookie in 10 seconds.”
Here’s the key idea: the Markov property. The future depends only on the current state, not on the whole history. Think of it as the agent having amnesia — it only remembers where it is right now, not how it got there. This makes the problem tractable. You don’t need to remember everything — just the current state.
Let’s see what an MDP looks like in code.
class MDP:
"""A simple MDP with states, actions, transitions, and rewards."""
def __init__(self, states, actions, transition_probs, rewards, gamma=0.9):
self.states = states
self.actions = actions
self.transition_probs = transition_probs # dict: state -> action -> [(prob, next_state, reward)]
self.rewards = rewards
self.gamma = gamma
def print_transition_table(self):
"""Print the transition table in plain English."""
print("Transition Table:")
print("=" * 60)
for state in self.states:
for action in self.actions:
print(f" From state '{state}', if you {action}:")
for prob, next_state, reward in self.transition_probs[state][action]:
print(f" {prob*100:.0f}% chance -> state '{next_state}', reward {reward}")
print()
# Define a simple 2-state MDP: 'near jar' and 'far from jar'
states = ['near jar', 'far from jar']
actions = ['reach', 'wait']
# Transition probabilities: for each state and action, list of (probability, next_state, reward)
transition_probs = {
'near jar': {
'reach': [(0.8, 'near jar', 10), (0.2, 'far from jar', 0)], # 80% get cookie, 20% miss
'wait': [(1.0, 'near jar', 0)] # waiting does nothing
},
'far from jar': {
'reach': [(0.5, 'near jar', 0), (0.5, 'far from jar', 0)], # 50% get closer
'wait': [(1.0, 'far from jar', 0)] # waiting does nothing
}
}
rewards = {
('near jar', 'reach'): 10, # Getting the cookie
('near jar', 'wait'): 0,
('far from jar', 'reach'): 0,
('far from jar', 'wait'): 0
}
mdp = MDP(states, actions, transition_probs, rewards, gamma=0.9)
mdp.print_transition_table()When you run that, you’ll see the rules of the toddler’s world written out clearly. From ‘near jar’, reaching gets you the cookie 80% of the time. From ‘far from jar’, reaching gets you closer 50% of the time. The MDP is just a description of the world.
The Five Ingredients: States, Actions, Transitions, Rewards, and Discount
Now let’s name each ingredient formally and use a richer example: a 3×4 grid world with stochastic movement. This is the classic example from the GeeksforGeeks tutorial.
Imagine a robot in a 3×4 grid. The robot can move up, down, left, or right. But the movement is stochastic — when the robot tries to go up, it actually goes up 80% of the time, left 10%, and right 10%. The goal is a +1 reward, a fire pit is -1, and every other step costs -0.04 (to encourage speed).
import numpy as np
class GridWorldMDP:
"""A 3x4 grid world with stochastic movement."""
def __init__(self, gamma=0.9):
self.gamma = gamma
self.rows = 3
self.cols = 4
self.states = [(r, c) for r in range(self.rows) for c in range(self.cols)]
# Remove blocked state (1, 1)
self.states.remove((1, 1))
self.actions = ['up', 'down', 'left', 'right']
# Define terminal states
self.terminal_states = [(0, 3), (1, 3)] # goal and fire pit
# Build transition probabilities
self.transition_probs = {}
for state in self.states:
self.transition_probs[state] = {}
for action in self.actions:
self.transition_probs[state][action] = self._get_transitions(state, action)
# Define rewards
self.rewards = {}
for state in self.states:
for action in self.actions:
self.rewards[(state, action)] = self._get_reward(state)
def _get_transitions(self, state, action):
"""Return list of (prob, next_state, reward) for a given state and action."""
r, c = state
# Define the intended direction and the two perpendicular directions
if action == 'up':
intended = (r-1, c)
perp1 = (r, c-1)
perp2 = (r, c+1)
elif action == 'down':
intended = (r+1, c)
perp1 = (r, c+1)
perp2 = (r, c-1)
elif action == 'left':
intended = (r, c-1)
perp1 = (r+1, c)
perp2 = (r-1, c)
elif action == 'right':
intended = (r, c+1)
perp1 = (r-1, c)
perp2 = (r+1, c)
# Check if the intended move is valid (within bounds and not blocked)
def is_valid(pos):
r, c = pos
if r < 0 or r >= self.rows or c < 0 or c >= self.cols:
return False
if (r, c) == (1, 1): # blocked state
return False
return True
# If the intended move is invalid, stay in place
if not is_valid(intended):
intended = state
if not is_valid(perp1):
perp1 = state
if not is_valid(perp2):
perp2 = state
# Return transitions with probabilities
reward = self._get_reward(state)
return [(0.8, intended, reward), (0.1, perp1, reward), (0.1, perp2, reward)]
def _get_reward(self, state):
"""Return the reward for being in a state."""
if state == (0, 3): # goal
return 1.0
elif state == (1, 3): # fire pit
return -1.0
else:
return -0.04 # small penalty for each step
def print_transition_table(self, state, action):
"""Print transitions for a specific state and action."""
print(f"From state {state}, action '{action}':")
for prob, next_state, reward in self.transition_probs[state][action]:
print(f" {prob*100:.0f}% -> {next_state}, reward {reward:.2f}")
# Create the grid world MDP
np.random.seed(42)
grid_mdp = GridWorldMDP(gamma=0.9)
print("Grid World MDP")
print(f"Number of states: {len(grid_mdp.states)}")
print(f"Actions: {grid_mdp.actions}")
print(f"Terminal states: {grid_mdp.terminal_states}")
print(f"Discount factor: {grid_mdp.gamma}")
print()
# Show transitions for a specific state
grid_mdp.print_transition_table((0, 0), 'up')
print()
grid_mdp.print_transition_table((0, 0), 'right')When you run that, you’ll see the stochastic nature of the world. From state (0,0), trying to go ‘up’ actually goes up 80% of the time, but left 10% and right 10%. The MDP captures all the uncertainty the agent faces.
The Markov Property: Why the Past Doesn’t Matter (and When It Does)
This is the hardest part. The Markov property says: the future depends only on the current state, not on how you got there. Formally:
P(s_{t+1} | s_t, a_t) = P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, …)
In plain English: the probability of the next state given the current state and action is the same as the probability given the entire history. The agent doesn’t need to remember anything except where it is right now.
But here’s the catch: this is a huge assumption, and it’s often wrong in real life. Imagine a robot navigating a room. If it has no memory of where it’s been, it might get stuck in a loop forever. In an MDP, we pretend the state captures everything relevant. That’s why RL practitioners engineer features — to make the state Markovian.
Let’s see what happens when the Markov property doesn’t hold.
import numpy as np
class MarkovianEnvironment:
"""A simple environment where the next state depends only on the current state."""
def __init__(self):
self.state = 0
self.n_states = 5
def step(self, action):
"""Next state depends only on current state and action."""
if action == 0: # left
self.state = max(0, self.state - 1)
else: # right
self.state = min(self.n_states - 1, self.state + 1)
reward = 1 if self.state == 4 else 0
return self.state, reward
def reset(self):
self.state = 0
return self.state
class NonMarkovianEnvironment:
"""An environment where the next state depends on the last two states."""
def __init__(self):
self.state = 0
self.last_state = 0
self.n_states = 5
def step(self, action):
"""Next state depends on current state AND the previous state."""
# This creates a pattern: if we just moved left, moving right has different effect
if self.last_state < self.state: # We just moved right
if action == 0: # Try to go left
self.state = max(0, self.state - 2) # Move extra left
else:
self.state = min(self.n_states - 1, self.state + 1)
else: # We just moved left or stayed
if action == 0:
self.state = max(0, self.state - 1)
else:
self.state = min(self.n_states - 1, self.state + 2) # Move extra right
reward = 1 if self.state == 4 else 0
self.last_state = self.state
return self.state, reward
def reset(self):
self.state = 0
self.last_state = 0
return self.state
# Compare performance of a simple policy in both environments
np.random.seed(42)
def run_policy(env, policy, steps=100):
"""Run a policy (mapping from state to action) for a given number of steps."""
state = env.reset()
total_reward = 0
for _ in range(steps):
action = policy(state)
next_state, reward = env.step(action)
total_reward += reward
state = next_state
return total_reward
# Simple policy: always go right
always_right = lambda s: 1
markov_env = MarkovianEnvironment()
non_markov_env = NonMarkovianEnvironment()
markov_reward = run_policy(markov_env, always_right, 100)
non_markov_reward = run_policy(non_markov_env, always_right, 100)
print(f"Markovian environment: {markov_reward} rewards in 100 steps")
print(f"Non-Markovian environment: {non_markov_reward} rewards in 100 steps")
print()
print("In the non-Markovian environment, the agent can't learn effectively")
print("because the next state depends on the history, not just the current state.")When you run that, you’ll see the agent performs worse in the non-Markovian environment. The simple “always go right” policy works perfectly in the Markovian case but fails in the non-Markovian one because the environment’s behavior depends on the last two states, not just the current one.
For now, assume the Markov property holds. We’ll deal with non-Markovian environments later in the series.
Policies: The Agent’s Strategy
Now we have a world (the MDP). The agent needs a strategy to navigate it. A policy is just a rule that tells the agent what to do in each state. It can be deterministic (always go up in state (0,0)) or stochastic (80% go up, 20% go left).
Formally, a policy π(a|s) is the probability of taking action a in state s. A policy, together with the MDP, defines a Markov chain — the agent’s behavior is completely determined.
import numpy as np
class Policy:
"""A policy that maps states to actions."""
def __init__(self, mdp, action_map=None):
self.mdp = mdp
if action_map is None:
# Random policy: uniform over actions
self.action_map = {state: None for state in mdp.states}
else:
self.action_map = action_map
def get_action(self, state):
"""Return an action for a given state."""
if self.action_map[state] is None:
# Random policy
return np.random.choice(self.mdp.actions)
else:
# Deterministic policy
return self.action_map[state]
def simulate_episode(self, max_steps=50):
"""Simulate one episode and return the total reward."""
state = (0, 0) # Start state
total_reward = 0
for _ in range(max_steps):
if state in self.mdp.terminal_states:
break
action = self.get_action(state)
# Sample next state from transition probabilities
transitions = self.mdp.transition_probs[state][action]
probs = [t[0] for t in transitions]
next_states = [t[1] for t in transitions]
rewards = [t[2] for t in transitions]
idx = np.random.choice(len(transitions), p=probs)
state = next_states[idx]
total_reward += rewards[idx]
return total_reward
# Create grid world MDP (reusing the class from earlier)
class GridWorldMDP:
def __init__(self, gamma=0.9):
self.gamma = gamma
self.rows = 3
self.cols = 4
self.states = [(r, c) for r in range(self.rows) for c in range(self.cols)]
self.states.remove((1, 1))
self.actions = ['up', 'down', 'left', 'right']
self.terminal_states = [(0, 3), (1, 3)]
self.transition_probs = {}
for state in self.states:
self.transition_probs[state] = {}
for action in self.actions:
self.transition_probs[state][action] = self._get_transitions(state, action)
self.rewards = {}
for state in self.states:
for action in self.actions:
self.rewards[(state, action)] = self._get_reward(state)
def _get_transitions(self, state, action):
r, c = state
if action == 'up':
intended = (r-1, c)
perp1, perp2 = (r, c-1), (r, c+1)
elif action == 'down':
intended = (r+1, c)
perp1, perp2 = (r, c+1), (r, c-1)
elif action == 'left':
intended = (r, c-1)
perp1, perp2 = (r+1, c), (r-1, c)
elif action == 'right':
intended = (r, c+1)
perp1, perp2 = (r-1, c), (r+1, c)
def is_valid(pos):
r, c = pos
if r < 0 or r >= self.rows or c < 0 or c >= self.cols:
return False
if (r, c) == (1, 1):
return False
return True
if not is_valid(intended):
intended = state
if not is_valid(perp1):
perp1 = state
if not is_valid(perp2):
perp2 = state
reward = self._get_reward(state)
return [(0.8, intended, reward), (0.1, perp1, reward), (0.1, perp2, reward)]
def _get_reward(self, state):
if state == (0, 3):
return 1.0
elif state == (1, 3):
return -1.0
else:
return -0.04
# Create MDP and policies
np.random.seed(42)
mdp = GridWorldMDP(gamma=0.9)
# Random policy
random_policy = Policy(mdp)
# Heuristic policy: always move toward the goal (0, 3)
heuristic_map = {
(0, 0): 'right',
(0, 1): 'right',
(0, 2): 'right',
(1, 0): 'up',
(1, 2): 'up',
(2, 0): 'up',
(2, 1): 'right',
(2, 2): 'right',
(2, 3): 'up'
}
heuristic_policy = Policy(mdp, heuristic_map)
# Simulate episodes
print("Simulating episodes...")
print()
random_rewards = []
heuristic_rewards = []
for _ in range(100):
random_rewards.append(random_policy.simulate_episode())
heuristic_rewards.append(heuristic_policy.simulate_episode())
print(f"Random policy: average reward = {np.mean(random_rewards):.2f}")
print(f"Heuristic policy: average reward = {np.mean(heuristic_rewards):.2f}")
print()
print("The heuristic policy does much better because it has a strategy.")
print("But it's still not optimal — it doesn't account for the stochastic movement.")When you run that, you’ll see the heuristic policy outperforms the random one. But it’s still not optimal because it doesn’t account for the stochastic movement. A truly optimal policy would balance the risk of slipping with the reward of reaching the goal.
Value Functions: How Good Is a State (or an Action)?
The agent needs to evaluate its situation. A value function tells you how much total reward you can expect from a given state, assuming you follow a particular policy. It’s like a GPS that shows you how far you are from the goal.
There are two kinds of value functions:
- State-value function V^π(s): The expected total discounted reward starting from state s and following policy π.
- Action-value function Q^π(s, a): The expected total discounted reward starting from state s, taking action a, then following policy π.
Think of it this way: V tells you how good a state is. Q tells you how good an action is in a state. If V(state 5) = 8.2, that means from state 5, you can expect about 8.2 points of total discounted reward if you follow the policy. If Q(state 5, ‘up’) = 9.1, then moving up from state 5 is a better bet than the average action in that state.
Let’s estimate V by Monte Carlo simulation.
import numpy as np
class GridWorldMDP:
def __init__(self, gamma=0.9):
self.gamma = gamma
self.rows = 3
self.cols = 4
self.states = [(r, c) for r in range(self.rows) for c in range(self.cols)]
self.states.remove((1, 1))
self.actions = ['up', 'down', 'left', 'right']
self.terminal_states = [(0, 3), (1, 3)]
self.transition_probs = {}
for state in self.states:
self.transition_probs[state] = {}
for action in self.actions:
self.transition_probs[state][action] = self._get_transitions(state, action)
self.rewards = {}
for state in self.states:
for action in self.actions:
self.rewards[(state, action)] = self._get_reward(state)
def _get_transitions(self, state, action):
r, c = state
if action == 'up':
intended = (r-1, c)
perp1, perp2 = (r, c-1), (r, c+1)
elif action == 'down':
intended = (r+1, c)
perp1, perp2 = (r, c+1), (r, c-1)
elif action == 'left':
intended = (r, c-1)
perp1, perp2 = (r+1, c), (r-1, c)
elif action == 'right':
intended = (r, c+1)
perp1, perp2 = (r-1, c), (r+1, c)
def is_valid(pos):
r, c = pos
if r < 0 or r >= self.rows or c < 0 or c >= self.cols:
return False
if (r, c) == (1, 1):
return False
return True
if not is_valid(intended):
intended = state
if not is_valid(perp1):
perp1 = state
if not is_valid(perp2):
perp2 = state
reward = self._get_reward(state)
return [(0.8, intended, reward), (0.1, perp1, reward), (0.1, perp2, reward)]
def _get_reward(self, state):
if state == (0, 3):
return 1.0
elif state == (1, 3):
return -1.0
else:
return -0.04
class Policy:
def __init__(self, mdp, action_map=None):
self.mdp = mdp
if action_map is None:
self.action_map = {state: None for state in mdp.states}
else:
self.action_map = action_map
def get_action(self, state):
if self.action_map[state] is None:
return np.random.choice(self.mdp.actions)
else:
return self.action_map[state]
def compute_value_function(mdp, policy, gamma, num_episodes=1000, max_steps=50):
"""Estimate V^π by Monte Carlo simulation."""
# Initialize returns for each state
returns = {state: [] for state in mdp.states}
for _ in range(num_episodes):
state = (0, 0) # Start state
episode_states = []
episode_rewards = []
for _ in range(max_steps):
if state in mdp.terminal_states:
break
action = policy.get_action(state)
transitions = mdp.transition_probs[state][action]
probs = [t[0] for t in transitions]
next_states = [t[1] for t in transitions]
rewards = [t[2] for t in transitions]
idx = np.random.choice(len(transitions), p=probs)
episode_states.append(state)
episode_rewards.append(rewards[idx])
state = next_states[idx]
# Compute discounted returns for each state in the episode
G = 0
for t in range(len(episode_states) - 1, -1, -1):
G = episode_rewards[t] + gamma * G
returns[episode_states[t]].append(G)
# Average the returns for each state
V = {}
for state in mdp.states:
if returns[state]:
V[state] = np.mean(returns[state])
else:
V[state] = 0.0
return V
# Create MDP and heuristic policy
np.random.seed(42)
mdp = GridWorldMDP(gamma=0.9)
heuristic_map = {
(0, 0): 'right',
(0, 1): 'right',
(0, 2): 'right',
(1, 0): 'up',
(1, 2): 'up',
(2, 0): 'up',
(2, 1): 'right',
(2, 2): 'right',
(2, 3): 'up'
}
heuristic_policy = Policy(mdp, heuristic_map)
# Compute value function
V = compute_value_function(mdp, heuristic_policy, gamma=0.9, num_episodes=1000)
print("State-Value Function V^π (heuristic policy):")
print("=" * 40)
for r in range(3):
row_str = ""
for c in range(4):
state = (r, c)
if state == (1, 1):
row_str += " BLOCK "
elif state in V:
row_str += f" {V[state]:6.2f} "
else:
row_str += " TERM "
print(row_str)
print()
print("Interpretation:")
print(" State (0,3) is the goal — V is highest there.")
print(" State (1,3) is the fire pit — V is lowest there.")
print(" States far from the goal have negative V because")
print(" it takes many steps to reach the goal, incurring penalties.")When you run that, you’ll see the value function for the heuristic policy. States near the goal have high values. States far away have low (negative) values because the agent incurs a -0.04 penalty for each step. The fire pit has a very negative value because it ends the episode with -1 reward.
The Bellman Equation: The One Formula You Actually Need
This is the heart of the article. The Bellman equation is a recursive relationship that says: the value of a state equals the immediate reward plus the discounted value of the next state. It’s the foundation of every RL algorithm.
Think of it like planning a road trip. The value of being in Chicago is: the fun you have in Chicago tonight, plus the discounted value of wherever you go next (New York or Denver).
Here’s the Bellman equation for V^π:
V^π(s) = Σ_a π(a|s) [ R(s, a) + γ Σ_{s’} P(s’|s, a) V^π(s’) ]
In plain English: The value of state s under policy π equals: the average over actions of (the immediate reward for that action, plus the discounted average value of the next state).
This is the hardest part of the article. Take a deep breath. We’ll walk through it step by step with code.
import numpy as np
class GridWorldMDP:
def __init__(self, gamma=0.9):
self.gamma = gamma
self.rows = 3
self.cols = 4
self.states = [(r, c) for r in range(self.rows) for c in range(self.cols)]
self.states.remove((1, 1))
self.actions = ['up', 'down', 'left', 'right']
self.terminal_states = [(0, 3), (1, 3)]
self.transition_probs = {}
for state in self.states:
self.transition_probs[state] = {}
for action in self.actions:
self.transition_probs[state][action] = self._get_transitions(state, action)
self.rewards = {}
for state in self.states:
for action in self.actions:
self.rewards[(state, action)] = self._get_reward(state)
def _get_transitions(self, state, action):
r, c = state
if action == 'up':
intended = (r-1, c)
perp1, perp2 = (r, c-1), (r, c+1)
elif action == 'down':
intended = (r+1, c)
perp1, perp2 = (r, c+1), (r, c-1)
elif action == 'left':
intended = (r, c-1)
perp1, perp2 = (r+1, c), (r-1, c)
elif action == 'right':
intended = (r, c+1)
perp1, perp2 = (r-1, c), (r+1, c)
def is_valid(pos):
r, c = pos
if r < 0 or r >= self.rows or c < 0 or c >= self.cols:
return False
if (r, c) == (1, 1):
return False
return True
if not is_valid(intended):
intended = state
if not is_valid(perp1):
perp1 = state
if not is_valid(perp2):
perp2 = state
reward = self._get_reward(state)
return [(0.8, intended, reward), (0.1, perp1, reward), (0.1, perp2, reward)]
def _get_reward(self, state):
if state == (0, 3):
return 1.0
elif state == (1, 3):
return -1.0
else:
return -0.04
class Policy:
def __init__(self, mdp, action_map=None):
self.mdp = mdp
if action_map is None:
self.action_map = {state: None for state in mdp.states}
else:
self.action_map = action_map
def get_action(self, state):
if self.action_map[state] is None:
return np.random.choice(self.mdp.actions)
else:
return self.action_map[state]
def bellman_update(mdp, policy, V, gamma, state):
"""Compute the right-hand side of the Bellman equation for a single state."""
total = 0
action = policy.get_action(state)
# For each possible outcome of taking this action
for prob, next_state, reward in mdp.transition_probs[state][action]:
total += prob * (reward + gamma * V[next_state])
return total
def value_iteration(mdp, policy, gamma, theta=0.0001):
"""Repeatedly apply the Bellman update until V converges."""
V = {state: 0.0 for state in mdp.states}
while True:
delta = 0
for state in mdp.states:
if state in mdp.terminal_states:
continue
v = V[state]
V[state] = bellman_update(mdp, policy, V, gamma, state)
delta = max(delta, abs(v - V[state]))
if delta < theta:
break
return V
# Create MDP and heuristic policy
np.random.seed(42)
mdp = GridWorldMDP(gamma=0.9)
heuristic_map = {
(0, 0): 'right',
(0, 1): 'right',
(0, 2): 'right',
(1, 0): 'up',
(1, 2): 'up',
(2, 0): 'up',
(2, 1): 'right',
(2, 2): 'right',
(2, 3): 'up'
}
heuristic_policy = Policy(mdp, heuristic_map)
# Compute V using Bellman updates (value iteration)
V_bellman = value_iteration(mdp, heuristic_policy, gamma=0.9)
print("Value Function from Bellman Equation (value iteration):")
print("=" * 40)
for r in range(3):
row_str = ""
for c in range(4):
state = (r, c)
if state == (1, 1):
row_str += " BLOCK "
elif state in V_bellman:
row_str += f" {V_bellman[state]:6.2f} "
else:
row_str += " TERM "
print(row_str)
print()
print("These values should be close to the Monte Carlo estimates.")
print("The Bellman equation gives us a way to compute V exactly,")
print("without running thousands of simulations.")When you run that, you’ll see the value function computed by the Bellman equation. It should be close to the Monte Carlo estimate from the previous section. The Bellman equation is more efficient because it doesn’t require simulation — it just iterates the equation until convergence.
Solving an MDP: Value Iteration in Action
Now we put it all together. Value iteration is an algorithm that finds the optimal policy by repeatedly updating the value function until it converges. It’s the simplest way to solve an MDP.
Here’s the algorithm:
- Start with V = 0 for all states.
- Repeatedly apply the Bellman optimality update: V(s) = max_a [ R(s, a) + γ Σ_{s’} P(s’|s, a) V(s’) ]
- Stop when the change is small.
The optimal policy can be extracted from the converged V: π*(s) = argmax_a [ R(s, a) + γ Σ_{s’} P(s’|s, a) V*(s’) ]
import numpy as np
class GridWorldMDP:
def __init__(self, gamma=0.9):
self.gamma = gamma
self.rows = 3
self.cols = 4
self.states = [(r, c) for r in range(self.rows) for c in range(self.cols)]
self.states.remove((1, 1))
self.actions = ['up', 'down', 'left', 'right']
self.terminal_states = [(0, 3), (1, 3)]
self.transition_probs = {}
for state in self.states:
self.transition_probs[state] = {}
for action in self.actions:
self.transition_probs[state][action] = self._get_transitions(state, action)
self.rewards = {}
for state in self.states:
for action in self.actions:
self.rewards[(state, action)] = self._get_reward(state)
def _get_transitions(self, state, action):
r, c = state
if action == 'up':
intended = (r-1, c)
perp1, perp2 = (r, c-1), (r, c+1)
elif action == 'down':
intended = (r+1, c)
perp1, perp2 = (r, c+1), (r, c-1)
elif action == 'left':
intended = (r, c-1)
perp1, perp2 = (r+1, c), (r-1, c)
elif action == 'right':
intended = (r, c+1)
perp1, perp2 = (r-1, c), (r+1, c)
def is_valid(pos):
r, c = pos
if r < 0 or r >= self.rows or c < 0 or c >= self.cols:
return False
if (r, c) == (1, 1):
return False
return True
if not is_valid(intended):
intended = state
if not is_valid(perp1):
perp1 = state
if not is_valid(perp2):
perp2 = state
reward = self._get_reward(state)
return [(0.8, intended, reward), (0.1, perp1, reward), (0.1, perp2, reward)]
def _get_reward(self, state):
if state == (0, 3):
return 1.0
elif state == (1, 3):
return -1.0
else:
return -0.04
def value_iteration_optimal(mdp, gamma, theta=0.0001):
"""Value iteration to find the optimal value function and policy."""
V = {state: 0.0 for state in mdp.states}
while True:
delta = 0
for state in mdp.states:
if state in mdp.terminal_states:
continue
v = V[state]
# Bellman optimality update: take the max over actions
max_value = float('-inf')
for action in mdp.actions:
action_value = 0
for prob, next_state, reward in mdp.transition_probs[state][action]:
action_value += prob * (reward + gamma * V[next_state])
max_value = max(max_value, action_value)
V[state] = max_value
delta = max(delta, abs(v - V[state]))
if delta < theta:
break
# Extract optimal policy
policy = {}
for state in mdp.states:
if state in mdp.terminal_states:
policy[state] = 'terminal'
continue
best_action = None
best_value = float('-inf')
for action in mdp.actions:
action_value = 0
for prob, next_state, reward in mdp.transition_probs[state][action]:
action_value += prob * (reward + gamma * V[next_state])
if action_value > best_value:
best_value = action_value
best_action = action
policy[state] = best_action
return V, policy
def simulate_optimal_policy(mdp, policy, max_steps=50):
"""Simulate one episode with the optimal policy."""
state = (0, 0)
total_reward = 0
for _ in range(max_steps):
if state in mdp.terminal_states:
break
action = policy[state]
transitions = mdp.transition_probs[state][action]
probs = [t[0] for t in transitions]
next_states = [t[1] for t in transitions]
rewards = [t[2] for t in transitions]
idx = np.random.choice(len(transitions), p=probs)
state = next_states[idx]
total_reward += rewards[idx]
return total_reward
# Create MDP and run value iteration
np.random.seed(42)
mdp = GridWorldMDP(gamma=0.9)
V_opt, policy_opt = value_iteration_optimal(mdp, gamma=0.9)
print("Optimal Value Function:")
print("=" * 40)
for r in range(3):
row_str = ""
for c in range(4):
state = (r, c)
if state == (1, 1):
row_str += " BLOCK "
elif state in V_opt:
row_str += f" {V_opt[state]:6.2f} "
else:
row_str += " TERM "
print(row_str)
print()
print("Optimal Policy (arrows):")
print("=" * 40)
arrow_map = {'up': '↑', 'down': '↓', 'left': '←', 'right': '→', 'terminal': 'G'}
for r in range(3):
row_str = ""
for c in range(4):
state = (r, c)
if state == (1, 1):
row_str += " BLOCK "
elif state in policy_opt:
row_str += f" {arrow_map[policy_opt[state]]} "
else:
row_str += " TERM "
print(row_str)
print()
# Simulate episodes with optimal policy
rewards = []
for _ in range(100):
rewards.append(simulate_optimal_policy(mdp, policy_opt))
print(f"Optimal policy: average reward = {np.mean(rewards):.2f}")
print("The optimal policy guides the agent to the goal efficiently,")
print("avoiding the fire pit and accounting for stochastic movement.")When you run that, you’ll see the optimal policy as arrows on the grid. The agent knows exactly what to do in each state. Compare this to the random agent from the beginning — it’s a completely different level of intelligence.
What We Learned and Where We’re Going
You’ve gone from watching a random agent stuck in a loop to designing a mathematical framework that captures the essence of decision-making under uncertainty. Let’s recap what you’ve learned:
- MDP tuple (S, A, P, R, γ): A complete description of the world the agent lives in.
- Markov property: The future depends only on the current state, not on the history.
- Policy: The agent’s strategy — a mapping from states to actions.
- Value functions (V and Q): How good a state or action is under a given policy.
- Bellman equation: A recursive relationship that lets you compute how good each state is.
- Value iteration: The algorithm that finds the best strategy.
An MDP is just a way of writing down the rules of the game. The Bellman equation is a recursive relationship that lets you compute how good each state is. Value iteration is the algorithm that finds the best strategy.
But here’s the catch: value iteration works only if you know the transition probabilities and rewards. In real RL, the agent doesn’t know them — it has to learn from experience. That’s what we’ll cover in Part 4: Q-learning.
In the next article, we’ll tackle the hardest part: what happens when the agent doesn’t know the transition probabilities or rewards? That’s where Q-learning comes in — and we’ll build it from scratch.
Check Your Understanding
Remember: What are the five components of an MDP tuple?
Understand: Explain in your own words why the Markov property is important for making RL problems tractable.
Apply: Given a 2×3 grid world with a goal at (0,2) and a penalty at (1,2), define the states, actions, and transition probabilities (assume 80% intended direction, 10% each perpendicular).
Analyze: Compare the Monte Carlo estimate of the value function with the Bellman equation estimate. Why might they differ slightly?
Evaluate: The heuristic policy we used was “always move toward the goal.” Why isn’t this optimal in a stochastic environment?
Create: Design an MDP for a simple game of your choice (e.g., a robot vacuum cleaning a room). Define the states, actions, transition probabilities, and rewards.
Related articles
- What Is Reinforcement Learning, Really? Agents, Environments, and Rewards Explained — Part 1 of this series, where we introduced the agent-environment-reward loop.
- Multi-Armed Bandits: The Simplest Reinforcement Learning Problem That Actually Matters — Part 2 of this series, where we explored the explore-exploit tradeoff.
Apply What You Learned is for Supporter and Insider subscribers.
Subscribe to unlock the exercises on this post.
See plansRelated articles
- Python Engineering Under review
Five Frameworks One Estimator Decomposing An Ipw T
Before any framework, we state the real, concrete goal. This is the shared target all five designs must hit.
- Python Engineering Under review
Managing Python Environments Pip Conda And Venv Fi
try: import pandas as pd print(f"pandas version: {pd.__version__}") except ImportError: print("pandas is not installed! Run: pip install pandas")
- Python Engineering Under review
Speeding Up Python With Numba Jit Compilation With
data = [random.random() for _ in range(10_000_000)]
- Python Engineering Under review
SQLAlchemy for Data Scientists: Querying Databases Without Raw SQL Strings
Picture this: You're a data scientist, and you've just spent three hours building a beautiful data pipeline in a Jupyter notebook. You've got your SQL queries working perfectly in your local SQLite database.
Looking for something else?
Search every article by title, summary or topic.