Chapter 2: Markov Decision Process Fundamentals

2.1 Introduction to MDPs

The Markov Decision Process (MDP) provides the mathematical foundation for reinforcement learning. An MDP formalizes sequential decision-making in stochastic environments where outcomes are partly random and partly under the control of a decision maker.

The Markov Property

The key assumption of MDPs is the Markov property: the future is independent of the past given the present.

P(sₜ₊₁ | sₜ, aₜ, sₜ₋₁, aₜ₋₁, ..., s₀, a₀) = P(sₜ₊₁ | sₜ, aₜ)

"The future depends only on the present, not the past"

This means the current state captures all relevant information from the history. The agent doesn't need to remember the entire sequence of past states and actions.

2.2 State Value Functions

The state value function V^π(s) is the expected return starting from state s and following policy π thereafter:

V^π(s) = E_π[Gₜ | Sₜ = s]
       = E_π[Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + ... | Sₜ = s]
       = E_π[Σ γᵏRₜ₊ᵏ₊₁ | Sₜ = s]

Bellman Equation for V^π

The value function satisfies a recursive relationship:

V^π(s) = Σ_a π(a|s) Σ_s' P(s'|s,a) [R(s,a,s') + γV^π(s')]

In words:
V(s) = Expected immediate reward + Discounted value of next state

2.3 Action Value Functions

The action value function (Q-function) gives the expected return from taking action a in state s and following policy π thereafter:

Q^π(s,a) = E_π[Gₜ | Sₜ = s, Aₜ = a]
         = E_π[Rₜ₊₁ + γV^π(Sₜ₊₁) | Sₜ = s, Aₜ = a]

Relationship Between V and Q

// From V to Q
Q^π(s,a) = Σ_s' P(s'|s,a) [R(s,a,s') + γV^π(s')]

// From Q to V
V^π(s) = Σ_a π(a|s) Q^π(s,a)

// For deterministic policy
V^π(s) = Q^π(s, π(s))

2.4 Optimal Value Functions

The optimal state value function V*(s) is the maximum value achievable from state s:

V*(s) = max_π V^π(s)

Q*(s,a) = max_π Q^π(s,a)

Bellman Optimality Equation

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

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

2.5 Optimal Policies

An optimal policy π* achieves the maximum expected return from every state:

π*(s) = argmax_a Q*(s,a)
      = argmax_a Σ_s' P(s'|s,a) [R(s,a,s') + γV*(s')]

Properties of Optimal Policies

• There always exists at least one optimal policy (may not be unique)
• All optimal policies share the same optimal value function V*
• Optimal policies are deterministic (though stochastic ones may exist)
• If we know Q*, the optimal policy is trivial to extract

2.6 Policy Evaluation

Policy evaluation computes V^π for a given policy π. We can solve the Bellman equation iteratively:

def policy_evaluation(policy, env, gamma=0.99, theta=1e-6):
    """
    Evaluate a policy in an MDP.

    Args:
        policy: π(a|s) - policy to evaluate
        env: MDP environment
        gamma: discount factor
        theta: convergence threshold
    """
    V = {s: 0 for s in env.states}

    while True:
        delta = 0
        for s in env.states:
            v = V[s]

            # Bellman update
            V[s] = sum(
                policy[s][a] * sum(
                    env.P[s][a][s_next] * (
                        env.R[s][a][s_next] + gamma * V[s_next]
                    )
                    for s_next in env.states
                )
                for a in env.actions
            )

            delta = max(delta, abs(v - V[s]))

        if delta < theta:
            break

    return V

Matrix Form

For a deterministic policy, we can write the Bellman equation in matrix form:

V^π = R^π + γP^π V^π

Solving directly:
V^π = (I - γP^π)^(-1) R^π

where:
- V^π is a vector of values for all states
- R^π is the expected immediate reward vector
- P^π is the transition matrix under policy π

2.7 Policy Improvement

Given V^π, we can construct a better policy by acting greedily:

def policy_improvement(V, env, gamma=0.99):
    """
    Improve policy based on value function.
    """
    policy = {}

    for s in env.states:
        # Compute Q-values for all actions
        q_values = {}
        for a in env.actions:
            q_values[a] = sum(
                env.P[s][a][s_next] * (
                    env.R[s][a][s_next] + gamma * V[s_next]
                )
                for s_next in env.states
            )

        # Greedy action selection
        best_action = max(q_values, key=q_values.get)
        policy[s] = best_action

    return policy

2.8 Policy Iteration

Policy iteration alternates between policy evaluation and policy improvement until convergence:

def policy_iteration(env, gamma=0.99):
    """
    Find optimal policy using policy iteration.

    1. Initialize policy arbitrarily
    2. Repeat until convergence:
        - Policy Evaluation: Compute V^π
        - Policy Improvement: π' ← greedy(V^π)
    """
    # Initialize random policy
    policy = {s: random.choice(env.actions) for s in env.states}

    while True:
        # Policy Evaluation
        V = policy_evaluation(policy, env, gamma)

        # Policy Improvement
        new_policy = policy_improvement(V, env, gamma)

        # Check convergence
        if new_policy == policy:
            break

        policy = new_policy

    return policy, V

Convergence Guarantee

Policy iteration is guaranteed to converge to the optimal policy in a finite number of iterations (bounded by |A|^|S|).

2.9 Value Iteration

Value iteration combines policy evaluation and improvement into a single update:

def value_iteration(env, gamma=0.99, theta=1e-6):
    """
    Find optimal value function using value iteration.

    V(s) ← max_a Σ_s' P(s'|s,a)[R + γV(s')]
    """
    V = {s: 0 for s in env.states}

    while True:
        delta = 0
        for s in env.states:
            v = V[s]

            # Bellman optimality update
            V[s] = max(
                sum(
                    env.P[s][a][s_next] * (
                        env.R[s][a][s_next] + gamma * V[s_next]
                    )
                    for s_next in env.states
                )
                for a in env.actions
            )

            delta = max(delta, abs(v - V[s]))

        if delta < theta:
            break

    # Extract optimal policy
    policy = policy_improvement(V, env, gamma)

    return policy, V

Policy Iteration vs Value Iteration

2.10 Practical Example: Grid World

class GridWorld:
    def __init__(self, size=5):
        self.size = size
        self.states = [(i,j) for i in range(size) for j in range(size)]
        self.actions = ['up', 'down', 'left', 'right']
        self.goal = (size-1, size-1)

    def transition(self, state, action):
        """Return next state given current state and action."""
        i, j = state

        if action == 'up':
            next_state = (max(0, i-1), j)
        elif action == 'down':
            next_state = (min(self.size-1, i+1), j)
        elif action == 'left':
            next_state = (i, max(0, j-1))
        elif action == 'right':
            next_state = (i, min(self.size-1, j+1))

        return next_state

    def reward(self, state, action, next_state):
        """Return reward for transition."""
        if next_state == self.goal:
            return 100  # Goal reward
        else:
            return -1   # Step penalty

# Solve GridWorld
env = GridWorld(size=5)
optimal_policy, V_optimal = value_iteration(env, gamma=0.9)

print("Optimal Value Function:")
for i in range(env.size):
    for j in range(env.size):
        print(f"{V_optimal[(i,j)]:6.2f}", end=" ")
    print()

print("\nOptimal Policy:")
for i in range(env.size):
    for j in range(env.size):
        action = optimal_policy[(i,j)]
        symbol = {'up':'↑', 'down':'↓', 'left':'←', 'right':'→'}[action]
        print(symbol, end=" ")
    print()