Artificial Intelligence

Agents Multi Agent Systems And Rl

Markov Decision Processes

Chapter 3's multi-armed bandit had no state — every choice was independent of the last. A Markov Decision Process (MDP) extends this with state, directly buildi

JrCodex·8 min read

Jr Codex AI Notes

Level: Advanced Prerequisites: Chapter 3 Time to complete: ~30 minutes

Table of Contents

  1. Adding State to Reinforcement Learning
  2. Formal Definition of an MDP
  3. Policies
  4. The Value of a State
  5. The Bellman Equation
  6. Value Iteration
  7. A Worked Example: Grid World
  8. Summary & Next Steps

1. Adding State to Reinforcement Learning

Chapter 3's multi-armed bandit had no state — every choice was independent of the last. A Markov Decision Process (MDP) extends this with state, directly building on Module 4, Chapter 4's Markov chains — now with the agent's own actions influencing which state comes next, and rewards attached to transitions.

Markov Chain (Module 4, Ch.4)          Markov Decision Process (this chapter)
─────────────────────────────         ─────────────────────────────
  States transition on their OWN,        The AGENT chooses ACTIONS
  no agent involved                        that INFLUENCE which state
                                             comes next

  P(next_state | current_state)              P(next_state | current_state, ACTION)

  No rewards                                   Each transition has an
                                                 associated REWARD
─────────────────────────────         ─────────────────────────────

2. Formal Definition of an MDP

The Five Components of an MDP
─────────────────────────────────────────
  States (S):        all possible situations the agent can be in
  Actions (A):          all actions the agent can take
  Transition Model (P):    P(s' | s, a) — probability of reaching
                             state s' after taking action a in state s
  Reward Function (R):       R(s, a, s') — the reward received for
                                this specific transition
  Discount Factor (γ):          how much FUTURE rewards are valued
                                  relative to IMMEDIATE ones (0 to 1)
─────────────────────────────────────────

class MDP:
    def __init__(self, states, actions, transition_model, reward_fn, discount=0.9):
        self.states = states
        self.actions = actions
        self.transition_model = transition_model      # (state, action) -> {next_state: probability}
        self.reward_fn = reward_fn                       # (state, action, next_state) -> reward
        self.discount = discount
 
    def get_transitions(self, state, action):
        return self.transition_model.get((state, action), {})

This is a direct generalization of Module 2, Chapter 1's SearchProblem — states and actions are the same idea, but transitions are now probabilistic (an action might not deterministically lead to one outcome), and every transition carries a reward rather than just a cost.

3. Policies

A policy, written π(s), specifies which action the agent takes in each state — the object an MDP-solving algorithm is ultimately trying to find the best version of.

# A policy is simply a mapping from state to action
policy = {
    "state_A": "move_right",
    "state_B": "move_up",
    "state_C": "move_left",
}
 
def follow_policy(policy, state):
    return policy[state]
Policy vs Plan (Module 3, Ch.5)
─────────────────────────────────────────
  A PLAN (Module 3) is a fixed SEQUENCE of actions —
  appropriate for deterministic environments where you can
  predict exactly what happens next.

  A POLICY is a mapping from EVERY state to an action —
  necessary in STOCHASTIC environments (Module 1, Ch.4's
  environment classification), since the agent might end up
  in any of several states after an action and needs to know
  what to do NO MATTER which one it lands in.
─────────────────────────────────────────

4. The Value of a State

The value of a state under a given policy is the expected total (discounted) reward the agent will accumulate starting from that state and following the policy thereafter — directly extending Module 4, Chapter 5's expected utility to a multi-step, sequential setting.

Why Discounting Future Rewards?
─────────────────────────────────────────
  γ (gamma) close to 1:   future rewards matter almost as
                            much as immediate ones — a
                            "patient" agent

  γ (gamma) close to 0:      only immediate rewards matter much
                                — a "short-sighted" agent

  Discounting also ensures the total value stays FINITE even
  for an infinitely long sequence of rewards, and reflects a
  real-world intuition: a reward received SOONER is generally
  worth more than the SAME reward received much later.
─────────────────────────────────────────

def calculate_return(rewards, discount):
    """Total DISCOUNTED return from a sequence of rewards."""
    total = 0
    for t, reward in enumerate(rewards):
        total += (discount ** t) * reward
    return total
 
rewards_received = [10, 5, 2, 1]
print(calculate_return(rewards_received, discount=0.9))      # 10 + 4.5 + 1.62 + 0.729 = 16.85
print(calculate_return(rewards_received, discount=0.5))      # 10 + 2.5 + 0.5 + 0.125 = 13.125 — future valued less

5. The Bellman Equation

The Bellman equation expresses a state's value recursively — in terms of the immediate reward plus the (discounted) value of whatever state comes next — the mathematical heart of MDP-solving.

The Bellman Equation
─────────────────────────────────────────
  V(s) = max_a  Σ P(s'|s,a) [ R(s,a,s') + γ V(s') ]
           │       │              │            │
           │       │              │            └── discounted value of NEXT state
           │       │              └── immediate reward for this transition
           │       └── weighted by transition PROBABILITY
           └── choose the ACTION that maximizes this expression

  "The value of a state = the best possible IMMEDIATE reward,
  plus the discounted value of wherever you end up next."
─────────────────────────────────────────

def bellman_update(mdp, state, values):
    """Compute the updated value of ONE state, using current value estimates for all states."""
    best_value = float("-inf")
    for action in mdp.actions:
        transitions = mdp.get_transitions(state, action)
        expected_value = sum(
            prob * (mdp.reward_fn(state, action, next_state) + mdp.discount * values[next_state])
            for next_state, prob in transitions.items()
        )
        best_value = max(best_value, expected_value)
    return best_value

This recursive structure is exactly the dynamic-programming pattern from Module 4, Chapter 4's Viterbi algorithm — a state's value is built from the values of states that follow it, rather than solved from scratch each time.

6. Value Iteration

Value iteration solves the Bellman equation by repeatedly applying it to every state until the values stop changing (converge) — a direct, practical algorithm for finding the optimal policy.

def value_iteration(mdp, iterations=100, tolerance=0.001):
    values = {s: 0.0 for s in mdp.states}      # start with all values at 0
 
    for i in range(iterations):
        new_values = {}
        max_change = 0
        for state in mdp.states:
            new_values[state] = bellman_update(mdp, state, values)
            max_change = max(max_change, abs(new_values[state] - values[state]))
        values = new_values
 
        if max_change < tolerance:
            print(f"Converged after {i+1} iterations")
            break
 
    return values
 
def extract_policy(mdp, values):
    """Once values have converged, extract the BEST action for each state."""
    policy = {}
    for state in mdp.states:
        best_action, best_value = None, float("-inf")
        for action in mdp.actions:
            transitions = mdp.get_transitions(state, action)
            expected_value = sum(
                prob * (mdp.reward_fn(state, action, next_state) + mdp.discount * values[next_state])
                for next_state, prob in transitions.items()
            )
            if expected_value > best_value:
                best_action, best_value = action, expected_value
        policy[state] = best_action
    return policy
Value Iteration, Conceptually
─────────────────────────────────────────
  Start:      every state's value = 0 (no information yet)
  Iterate:      repeatedly apply the Bellman equation to
                  EVERY state, using the PREVIOUS iteration's
                  values for "what happens next"
  Converge:        values stabilize once they accurately
                     reflect the TRUE expected long-term reward
                     from each state
  Extract policy:     once values are accurate, the best ACTION
                        per state follows directly
─────────────────────────────────────────

7. A Worked Example: Grid World

The classic MDP teaching example — an agent navigating a small grid, with one good terminal state and one bad one.

# A simple 2x2 grid: states are (row, col). Terminal states: (0,1)=+10, (1,1)=-10
states = [(0,0), (0,1), (1,0), (1,1)]
actions = ["up", "down", "left", "right"]
 
def move(state, action):
    row, col = state
    moves = {"up": (-1,0), "down": (1,0), "left": (0,-1), "right": (0,1)}
    dr, dc = moves[action]
    new_row, new_col = max(0, min(1, row+dr)), max(0, min(1, col+dc))
    return (new_row, new_col)
 
transition_model = {}
for state in states:
    if state in [(0,1), (1,1)]:      # terminal states — no outgoing transitions
        continue
    for action in actions:
        next_state = move(state, action)
        transition_model[(state, action)] = {next_state: 1.0}      # deterministic movement
 
def reward_fn(state, action, next_state):
    if next_state == (0,1):
        return 10
    elif next_state == (1,1):
        return -10
    return -1      # small cost per step, encouraging efficiency (same idea as Ch.3's reward design)
 
grid_mdp = MDP(states, actions, transition_model, reward_fn, discount=0.9)
optimal_values = value_iteration(grid_mdp)
optimal_policy = extract_policy(grid_mdp, optimal_values)
 
print("Optimal values:", optimal_values)
print("Optimal policy:", optimal_policy)      # shows the best action from every non-terminal state

This complete, small example ties every concept in this chapter together: states, actions, a transition model, a reward function, the Bellman equation, value iteration's convergence, and a final extracted policy — the exact recipe scales up (with more sophisticated algorithms) to far larger, real MDPs.

8. Summary & Next Steps

Key Takeaways

  • A Markov Decision Process extends Module 4's Markov chains with agent-chosen actions and rewards attached to each transition — the formal framework underlying sequential reinforcement learning.
  • A policy maps every state to an action; unlike a fixed plan (Module 3), a policy is necessary because stochastic environments can lead to any of several states after an action.
  • The Bellman equation recursively defines a state's value as the best achievable immediate reward plus the discounted value of whatever state follows — the same dynamic-programming principle behind Viterbi (Module 4, Chapter 4).
  • Value iteration solves the Bellman equation by repeatedly updating every state's value until convergence, then extracts the optimal policy directly from the converged values.

Concept Check

  1. Why is a policy necessary in a stochastic environment, rather than a fixed action sequence (plan)?
  2. What does the discount factor γ control, and what happens with γ close to 0 versus close to 1?
  3. How does the Bellman equation express a state's value recursively, and why does that enable value iteration to work?

Next Chapter

→ Chapter 5: Q-Learning Fundamentals

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index