Markov Decision Process

A Markov decision process (MDP) is the mathematical framework that formalizes sequential decision-making under uncertainty: an agent repeatedly observes a state, picks an action, receives a reward, and moves to a new state according to probabilities that depend only on where it is and what it did. It is the standard problem statement of reinforcement learning, and nearly every algorithm in that field, from Q-learning to policy gradient methods, can be read as a strategy for solving some MDP. The framework earns its place by being narrow enough to analyze exactly and broad enough to describe board games, robot control, inventory management and the turn-by-turn generation of text.

An MDP is specified by five ingredients: a set of states, a set of actions, transition probabilities, a reward function, and a discount factor. The transition function gives the probability of landing in each next state after taking a given action in a given state, and the reward function gives the immediate payoff. The discount factor, a number between zero and one usually written γ, weights future rewards less than immediate ones, which keeps infinite-horizon sums finite and encodes a preference for sooner payoffs. The goal is a policy, a rule mapping states to actions, that maximizes the expected discounted sum of rewards. A policy is judged by its value function, the expected return from each state if the policy is followed from there.

The defining restriction is the Markov property: the next state and reward depend only on the current state and action, not on the longer history that led there. This is a statement about the state description, not about the world, since a rich enough state can always make the process Markov by folding the relevant past into it. A chess position is Markov because the board alone settles what moves are legal; the screen of a single Atari frame is not, because one image hides the velocity of the ball, which is why the 2015 DQN agent from DeepMind stacked four recent frames to restore the property. When even a stacked state cannot capture what matters, the right model is a partially observable MDP (POMDP), where the agent maintains a belief over hidden states.

Richard Bellman's contribution, set out in his 1957 book on dynamic programming, is the recursive structure that makes MDPs solvable: the value of a state equals the best immediate reward plus the discounted value of where that action leads. This Bellman equation turns a problem over entire futures into a local consistency condition, and it underlies value iteration and policy iteration, the classical exact algorithms, the latter developed in Ronald Howard's 1960 work. When the transition probabilities are known and the state space is small, these methods compute the optimal policy directly. When they are not known, as in most real problems, algorithms such as Watkins's 1989 Q-learning approximate the same fixed point from sampled experience instead of a model.

The framework is deceptively easy to misapply, because the hard part is deciding what counts as the state, the reward and the horizon. The curse of dimensionality bites quickly: a state described by many variables has exponentially many configurations, which is why practical systems replace tables with neural networks as function approximators, as DeepMind did for Atari. The reward function can be mis-specified, so the solved MDP is exactly the wrong problem. And the Markov assumption is often silently violated, as when sensors are noisy or other agents adapt to the learner. Multi-agent settings generalize to stochastic games, and cases with a single episode of fixed length are better described by finite-horizon variants.

In language models, the MDP view clarifies what reinforcement learning from human feedback is doing: the state is the prompt plus the tokens generated so far, the action is the next token, and the reward typically arrives only at the end of the response. That sparse, end-of-sequence reward makes credit assignment hard, since it is unclear which token deserved praise. Some work treats the whole response as a single action, as in a contextual bandit, which is an MDP with horizon one, while other work scores intermediate reasoning steps with process rewards. Search methods such as Monte Carlo tree search likewise plan inside an MDP, using the transition model of a game or a learned simulator to look ahead before committing to a move.

Read a Markov decision process as the grammar of decision problems: five symbols, one memory-free assumption and Bellman's recursion are enough to state what it means to act well over time, which is why every reinforcement learning method begins by quietly assuming one.