How does The MDP Framework work?

Almost every RL problem is modeled as a Markov Decision Process (MDP). An MDP has five components: Symbol Name Description S States All possible situations the agent can be in A Actions All possible moves the agent can take P(s' s,a) Transition R(s,a) Reward Immediate reward for taking

RL Fundamentals: MDP, Bellman Equation, and Value Functions

.rl-series-nav{margin:2rem 0;padding:1.5rem;border:1px solid #e2e8f0;border-radius:10px;background:#f8fafc}.rl-series-nav h4{margin:0 0 .8rem;color:#6c5ce7;font-size:1.1rem}.rl-series-nav ul{list-style:none;padding:0;margin:0}.rl-series-nav li{padding:.3rem 0}.rl-series-nav a{color:#4a5568;text-decoration:none;font-size:.9rem}.rl-series-nav a:hover{color:#6c5ce7}.rl-series-nav .current{font-weight:700;color:#6c5ce7}

Reinforcement Learning Series

→ Part 1: RL Fundamentals — MDP, Bellman, Value Functions
Part 2: From Q-Learning to DQN
Part 3: Policy Gradient and Actor-Critic
Part 4: PPO — Why It Powers ChatGPT and Game AI
Part 5: SAC — Mastering Continuous Control

This is the first article in a 5-part Reinforcement Learning series. By the end of this series, you’ll understand and implement algorithms from basic Q-Learning to PPO and SAC.

Series Overview:
– Part 1: RL Basics (You are here)
– Part 2: From Q-Learning to DQN
– Part 3: Policy Gradient Methods
– Part 4: PPO — The Industry Standard
– Part 5: SAC — Mastering Continuous Control

What is Reinforcement Learning?

Reinforcement Learning (RL) is a type of machine learning where an agent learns to make decisions by interacting with an environment. Unlike supervised learning where you have labeled data, RL agents learn from trial and error — they take actions, observe results, and adjust their behavior to maximize cumulative reward.

Think of it like training a dog. You don’t show the dog 10,000 labeled images of “sit.” Instead, the dog tries different things, and you reward the behavior you want. Over time, the dog learns which actions lead to treats.

Agent → Action → Environment → (Next State, Reward) → Agent learns

The MDP Framework

Almost every RL problem is modeled as a Markov Decision Process (MDP). An MDP has five components:

Symbol	Name	Description
S	States	All possible situations the agent can be in
A	Actions	All possible moves the agent can take
P(s’	s,a)	Transition
R(s,a)	Reward	Immediate reward for taking action a in state s
γ	Discount factor	How much the agent values future rewards (0 to 1)

The Markov property means the future depends only on the current state, not the history. This simplifies things enormously.

# A simple MDP example: GridWorld
# States: grid positions (row, col)
# Actions: up, down, left, right
# Reward: -1 per step, +10 at goal, -10 at trap

import numpy as np

class GridWorld:
    def __init__(self, size=4):
        self.size = size
        self.state = (0, 0)  # Start top-left
        self.goal = (size-1, size-1)  # Goal bottom-right
        self.trap = (1, 1)  # Trap in middle

        # Actions: 0=up, 1=down, 2=left, 3=right
        self.actions = {
            0: (-1, 0), 1: (1, 0),
            2: (0, -1), 3: (0, 1)
        }

    def reset(self):
        self.state = (0, 0)
        return self.state

    def step(self, action):
        dr, dc = self.actions[action]
        r = max(0, min(self.size-1, self.state[0] + dr))
        c = max(0, min(self.size-1, self.state[1] + dc))
        self.state = (r, c)

        if self.state == self.goal:
            return self.state, 10.0, True
        if self.state == self.trap:
            return self.state, -10.0, True
        return self.state, -1.0, False

Enjoying this article? Get more like it delivered to your inbox. Subscribe to the newsletter

Policy and Value Functions

Two core concepts drive every RL algorithm:

Policy (π)

A policy is the agent’s strategy — it maps states to actions.

Deterministic policy: π(s) = a (always picks one action)
Stochastic policy: π(a|s) = probability of taking action a in state s

The goal of RL is to find the optimal policy π* that maximizes expected cumulative reward.

Value Function (V)

The state-value function V(s) tells us how good it is to be in state s under policy π:

V_π(s) = E[R_t + γR_{t+1} + γ²R_{t+2} + ... | S_t = s]

In plain English: “Starting from state s, if I follow policy π, what’s my expected total (discounted) reward?”

Action-Value Function (Q)

The action-value function Q(s, a) tells us how good it is to take action a in state s:

Q_π(s, a) = E[R_t + γR_{t+1} + γ²R_{t+2} + ... | S_t = s, A_t = a]

This is the foundation of Q-Learning, which we’ll cover in Part 2.

The Bellman Equation

The Bellman equation is the recursive relationship that makes RL solvable. Instead of computing infinite sums, it breaks the value into immediate reward + discounted future value:

V(s) = R(s, a) + γ · V(s')

Or more precisely for the optimal value:

V*(s) = max_a [ R(s,a) + γ · Σ P(s'|s,a) · V*(s') ]

This says: “The value of a state is the best action’s immediate reward plus the discounted value of where you end up.”

def value_iteration(env, gamma=0.99, threshold=1e-6):
    """Find optimal values using the Bellman equation."""
    V = np.zeros((env.size, env.size))

    while True:
        delta = 0
        for r in range(env.size):
            for c in range(env.size):
                if (r, c) == env.goal or (r, c) == env.trap:
                    continue

                old_v = V[r, c]
                values = []

                for action in range(4):
                    env.state = (r, c)
                    next_state, reward, done = env.step(action)
                    nr, nc = next_state
                    future = 0 if done else V[nr, nc]
                    values.append(reward + gamma * future)

                V[r, c] = max(values)
                delta = max(delta, abs(old_v - V[r, c]))

        if delta < threshold:
            break

    return V

Discount Factor (γ): Why It Matters

The discount factor γ (gamma) controls how much the agent cares about future rewards:

γ value	Behavior
γ = 0	Greedy — only cares about immediate reward
γ = 0.5	Balanced — moderate future consideration
γ = 0.99	Far-sighted — values long-term strategy
γ = 1.0	No discounting (can diverge in infinite tasks)

In practice, most algorithms use γ = 0.99 or γ = 0.995.

# Visualize how gamma affects cumulative reward
# Reward of 1.0 received at each future time step

gammas = [0.5, 0.9, 0.99]
steps = 50

for gamma in gammas:
    total = sum(gamma**t for t in range(steps))
    print(f"γ={gamma}: Total value of 1/step for {steps} steps = {total:.2f}")

# γ=0.5:  Total value = 2.00
# γ=0.9:  Total value = 9.95
# γ=0.99: Total value = 39.50

Exploration vs. Exploitation

One of the biggest challenges in RL: should the agent exploit what it already knows (pick the best-known action) or explore new actions that might be better?

ε-Greedy Strategy

The simplest solution — with probability ε, take a random action; otherwise, take the best-known action:

import random

def epsilon_greedy(Q, state, epsilon=0.1):
    """Choose action using epsilon-greedy strategy."""
    if random.random() < epsilon:
        return random.randint(0, 3)  # Random action (explore)
    else:
        return int(np.argmax(Q[state]))  # Best known action (exploit)

A common pattern is to decay ε over time — explore a lot early on, then gradually shift to exploitation as the agent learns:

epsilon = max(0.01, 1.0 - episode / 500)  # Decay from 1.0 to 0.01

Putting It All Together: GridWorld Solver

Let’s combine everything into a complete example that solves GridWorld using value iteration and extracts the optimal policy:

import numpy as np

class GridWorld:
    def __init__(self, size=4):
        self.size = size
        self.goal = (size-1, size-1)
        self.trap = (1, 1)
        self.actions = {0: (-1,0), 1: (1,0), 2: (0,-1), 3: (0,1)}
        self.state = (0, 0)

    def reset(self):
        self.state = (0, 0)
        return self.state

    def step(self, action):
        dr, dc = self.actions[action]
        r = max(0, min(self.size-1, self.state[0] + dr))
        c = max(0, min(self.size-1, self.state[1] + dc))
        self.state = (r, c)
        if self.state == self.goal:
            return self.state, 10.0, True
        if self.state == self.trap:
            return self.state, -10.0, True
        return self.state, -1.0, False

def solve_gridworld():
    env = GridWorld(size=4)
    gamma = 0.99
    V = np.zeros((env.size, env.size))
    action_names = ['↑', '↓', '←', '→']

    # Value Iteration
    for _ in range(1000):
        delta = 0
        for r in range(env.size):
            for c in range(env.size):
                if (r, c) in [env.goal, env.trap]:
                    continue
                old_v = V[r, c]
                values = []
                for a in range(4):
                    env.state = (r, c)
                    ns, reward, done = env.step(a)
                    future = 0 if done else V[ns[0], ns[1]]
                    values.append(reward + gamma * future)
                V[r, c] = max(values)
                delta = max(delta, abs(old_v - V[r, c]))
        if delta < 1e-8:
            break

    # Extract optimal policy
    policy = np.full((env.size, env.size), ' ', dtype='U2')
    for r in range(env.size):
        for c in range(env.size):
            if (r, c) == env.goal:
                policy[r, c] = '★'
                continue
            if (r, c) == env.trap:
                policy[r, c] = '✕'
                continue
            values = []
            for a in range(4):
                env.state = (r, c)
                ns, reward, done = env.step(a)
                future = 0 if done else V[ns[0], ns[1]]
                values.append(reward + gamma * future)
            policy[r, c] = action_names[np.argmax(values)]

    print("Optimal Values:")
    print(np.round(V, 1))
    print("nOptimal Policy:")
    for row in policy:
        print(' '.join(f'{x:>2}' for x in row))

solve_gridworld()
# Output:
# Optimal Values:
# [[ 4.9  3.9  5.8  6.9]
#  [ 5.9 -10.   6.9  7.9]
#  [ 6.9  7.9  7.9  8.9]
#  [ 7.9  8.9  9.   10. ]]
#
# Optimal Policy:
#  →  ↓  ↓  ↓
#  ↓  ✕  ↓  ↓
#  →  →  →  ↓
#  →  →  →  ★

The agent learns to navigate around the trap and reach the goal — purely from trial-and-error value estimation.

Key Takeaways

RL = learning from interaction, not labeled data
MDP provides the mathematical framework (states, actions, rewards, transitions)
Value functions estimate how good states/actions are
Bellman equation makes value computation tractable through recursion
Exploration vs. exploitation is the fundamental RL tradeoff

What’s Next

In Part 2, we’ll move from tabular methods to Q-Learning and then scale up with Deep Q-Networks (DQN) — the algorithm that first beat human experts at Atari games. We’ll implement both from scratch with PyTorch.

FAQ

What’s the difference between RL and supervised learning?

Supervised learning needs labeled input-output pairs (like images with labels). RL has no labels — the agent discovers good behavior through rewards received after taking actions. The feedback is delayed and sparse, making RL fundamentally harder but applicable to sequential decision problems.

When should I use RL instead of other ML approaches?

Use RL when your problem involves sequential decisions where actions affect future states — robotics control, game playing, resource allocation, or trading. If you have a static dataset with clear labels, supervised learning is simpler and more efficient. RL shines when the optimal strategy requires planning multiple steps ahead.

Why not just set the discount factor to 1.0?

With γ=1.0, the sum of future rewards can diverge to infinity in continuing (non-episodic) tasks, making value functions undefined. Even in episodic tasks, γ=1.0 makes learning slower because the agent weighs distant rewards equally to immediate ones. Using γ=0.99 provides numerical stability while still valuing long-term outcomes.

Did you find this helpful?

Your support keeps this blog running and ad-free content coming.

☕ Buy me a coffee