Markov Decision Processes: Bellman Equations, Dynamic Programming, and Q-Learning

A Markov Decision Process (MDP) provides the formal mathematical framework for modeling decision-making in environments where outcomes are partly random and partly under the control of a decision-maker (agent). MDPs form the theoretical foundation of Reinforcement Learning (RL), dynamic control theory, robotic path planning, and autonomous trading systems.

This guide provides rigorous technical coverage of the MDP 5-tuple, the Markov Property Invariant, the Bellman Optimality Equations, Dynamic Programming Solvers (Value and Policy Iteration), and model-free Temporal Difference (Q-Learning).

1. Quick-Reference: MDP Solution Paradigms

+-----------------------------------------------------------------------------------------------------------------------+
|                                           MDP RESOLUTION METHODOLOGIES                                                |
+-----------------------------------------------------------------------------------------------------------------------+
| Method                 | Model Requirements                     | Convergence Guarantee      | Computational Complexity|
+------------------------+----------------------------------------+----------------------------+------------------------+
| Value Iteration        | Model-Based (Known P(s'|s,a), R)       | Guaranteed Optimal V*(s)   | O(|S|^2 |A|) per iter  |
| Policy Iteration       | Model-Based (Known transition dynamics)| Guaranteed exact in K steps| O(|S|^3 + |S|^2 |A|)   |
| Monte Carlo Methods    | Model-Free (Sampling episode rollouts) | Unbiased sample convergence| High sample variance   |
| Temporal Difference (Q)| Model-Free (Online step-by-step updates)| Asymptotic to Q*(s, a)     | O(1) per transition    |
| Deep Q-Networks (DQN)  | Model-Free (Neural function approx)    | Empirical (Target networks)| Gradient Backprop      |
+-----------------------------------------------------------------------------------------------------------------------+

2. The Formal MDP Definition and The Markov Invariant

An MDP is defined by the 5-tuple (S, A, P, R, \gamma):

1. S: The set of all valid environment states.
2. A: The set of actions available to the agent.
3. P(s' \mid s, a): The transition probability function P(S_{t+1} = s' \mid S_t = s, A_t = a).
4. R(s, a, s'): The reward function E[R_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s'].
5. \gamma \in [0, 1): The discount factor ensuring convergence over infinite horizons.

The Markov Property Invariant

The future state depends solely on the current state and action, independent of historical trajectories:

3. The Bellman Optimality Equations

The expected cumulative discounted return from state s under optimal policy \pi^* is governed by the recursive Bellman Optimality Equations:

Optimal State-Value Function V^*(s):

Optimal Action-Value Function Q^*(s, a):

4. Model-Free Reinforcement Learning: Q-Learning

When the true transition probabilities P(s' \mid s, a) are unknown, the agent learns Q^*(s, a) directly through trial-and-error interactions using the off-policy Q-Learning Temporal Difference Update:

where lpha \in (0, 1] is the learning rate.

import numpy as np

def q_learning(env, num_episodes=1000, alpha=0.1, gamma=0.99, epsilon=0.1):
    Q = np.zeros((env.num_states, env.num_actions))
    for episode in range(num_episodes):
        state = env.reset()
        done = False
        while not done:
            if np.random.rand() < epsilon:
                action = np.random.choice(env.num_actions)
            else:
                action = np.argmax(Q[state, :])
            next_state, reward, done = env.step(action)
            td_target = reward + gamma * np.max(Q[next_state, :]) * (not done)
            Q[state, action] += alpha * (td_target - Q[state, action])
            state = next_state
    return Q

References

1. Bellman, R. (1957). Dynamic Programming. Princeton University Press.
2. Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
3. Watkins, C. J., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3-4), 279-292.