What Are Markov Decision Processes?

Markov decision processes are mathematical models of sequential decision making under uncertainty, in which an agent repeatedly observes a state, chooses an action, receives a reward, and transitions stochastically to a new state. They extend Markov processes by adding a controller: where an ordinary Markov chain evolves on its own, an MDP lets the actions taken at each step shape the transition distribution. The formulation is credited to Richard Bellman and to Ronald Howard's work in the 1950s and 1960s, and it now serves as the standard formal foundation for stochastic dynamic programming, operations research control problems, and reinforcement learning.

The defining assumption is the Markov property: the distribution over the next state and reward depends on the current state and action alone, and not on the earlier history. That assumption is what makes the problem tractable, because it allows the value of a decision to be expressed recursively rather than as an integral over entire trajectories.

Formal Definition and the Bellman Equations

An MDP is written as a tuple consisting of a state space, an action space, a transition kernel giving the probability of the next state given the current state and action, a reward function, and, for infinite-horizon problems, a discount factor between zero and one. A policy maps states to actions, deterministically or stochastically, and the value function of a policy gives the expected discounted sum of future rewards from each state. Bellman's insight was that the optimal value function satisfies a fixed-point equation: the value of a state equals the best over actions of the immediate reward plus the discounted expected value of the successor state. Because the associated operator is a contraction under discounting, that fixed point is unique and iterative schemes converge to it geometrically. The chapter on reinforcement learning and Markov decision processes by van Otterlo and Wiering develops this apparatus in detail, from finite-horizon backward induction through the discounted infinite-horizon case.

Solution Methods

When the transition and reward functions are known, the problem is one of planning rather than learning. Value iteration applies the Bellman optimality operator repeatedly until the value estimates converge, then reads off a greedy policy. Policy iteration alternates between evaluating the current policy, which requires solving a linear system, and improving it greedily, and it terminates in a finite number of steps for finite MDPs. Linear programming provides a third exact route, minimizing a weighted sum of state values subject to Bellman inequality constraints, which makes duality arguments and constraint handling natural. All three methods scale poorly with the size of the state space, the difficulty Bellman named the curse of dimensionality, so practical work relies on function approximation, state aggregation, factored representations, or sampling-based search such as Monte Carlo tree search. Lecture material such as Sutton's treatment of MDPs and dynamic programming lays out these algorithms alongside their convergence conditions.

Extensions and Reinforcement Learning

When the model is unknown, the agent must estimate values from experience, which is the reinforcement learning setting. Temporal-difference methods including Q-learning and SARSA update value estimates from single transitions and converge to the optimal values under standard step-size and exploration conditions, while policy gradient and actor-critic methods optimize a parameterized policy directly. Several extensions relax the base assumptions. Partially observable MDPs replace direct state access with noisy observations and a belief state, which restores the Markov property at the cost of a continuous belief space. Constrained MDPs add budget or safety constraints; semi-Markov and average-reward formulations handle variable timing and undiscounted objectives; and multi-agent extensions model several controllers at once. A unified framework connecting reinforcement learning and optimal control surveys how these traditions describe the same underlying sequential decision problem in different notations.

Applications

Markov decision processes are applied in fields including:

• Robot motion planning and autonomous navigation under uncertainty
• Inventory control, queueing, and maintenance scheduling in operations research
• Wireless resource allocation, power control, and network routing
• Clinical treatment policy design and medical decision analysis
• Energy systems, including storage dispatch and demand response
• Game playing, recommendation, and dialogue systems trained by reinforcement learning