Markov Decision Process: A Map for Sequential Decisions

WHY IT EXISTS We often need to make a series of decisions where the outcome of each choice is partly random. Without a formal way to model this, we can only guess at an optimal strategy. An MDP provides the mathematical structure to find a policy that maximizes long-term, cumulative rewards in the face of uncertainty.

THE MENTAL MODEL Think of an MDP as the complete rulebook for a probabilistic board game. You have a set of squares (states), a set of possible moves from each square (actions), and points you get for landing on certain squares (rewards). The key is that when you choose a move, a dice roll determines where you actually land (the transition probability). The goal isn't to win one turn, but to find a policy—a strategy telling you the best move for any square—that maximizes your total score over the entire game.

HOW IT WORKS An MDP is formally defined by a few key components. First, a set of States (S), representing all possible situations an agent can be in. Second, a set of Actions (A), the choices available to the agent. Third, a Transition Model P(s' | s, a), which gives the probability of landing in state s' after taking action a in state s. This captures the uncertainty. Fourth, a Reward Function R(s, a), the immediate value received for taking that action in that state. The 'solution' to an MDP is an optimal policy, denoted π(s), which is a map telling you the best action to take in every possible state to maximize future rewards. This policy is typically found using algorithms like Value Iteration or Policy Iteration.

WHEN TO USE IT Use an MDP for any problem that involves a sequence of decisions with stochastic outcomes. Three places this shows up: first, in reinforcement learning, where an agent learns to navigate an environment like a game or a real-world robot; second, in operations research for problems like inventory control, where you must decide when to reorder stock based on uncertain customer demand; third, in finance, for optimizing trading or investment strategies based on probabilistic market movements.

WHEN NOT TO USE IT The primary limitation is the Markov Property. If the best action depends on the full history of events, not just the current state, a standard MDP is the wrong model. For example, in a card game where you must remember which cards have already been played, a simple state description is insufficient. Additionally, MDPs can become computationally intractable if the number of states or actions is extremely large or continuous, a problem known as the 'curse of dimensionality'.

ONE CANONICAL EXAMPLE Consider a robot on a grid trying to reach a charging station. The states are the robot's coordinates. The actions are 'move North, South, East, West'. The rewards are positive for reaching the charger and negative for hitting an obstacle or for each step taken (to encourage speed). The transitions are probabilistic: commanding the robot to move North might have an 80% chance of success, a 10% chance of veering West, and a 10% chance of veering East due to wheel slippage. The MDP models this entire system, and solving it yields a policy that tells the robot the optimal direction to move from any square on the grid.