Markov decision process
A Markov decision process (MDP) is a mathematical model for sequential decision-making in systems whose future evolution depends on the present state, a selected action, and probabilistic transition dynamics. It extends a Markov chain by introducing choices that affect both state transitions and numerically represented outcomes. The framework provides a common formal language for stochastic control, dynamic programming, and several areas of reinforcement learning.
The defining assumption is the Markov property: conditional on the current state and action, the probability distribution of the next state is independent of the preceding history. This assumption concerns the information represented by the state rather than the physical system in isolation. A state description that omits variables relevant to future evolution may therefore fail to produce a Markov decision process, even when the underlying system is itself governed by stable probabilistic laws.
Mathematical formulation
A discounted Markov decision process is commonly represented by a tuple
[ (\mathcal S,\mathcal A,P,R,\gamma), ]
where (\mathcal S) is a state space and (\mathcal A) is an action space. The transition kernel
[ P(s' \mid s,a) ]
gives the conditional probability of entering state (s') after action (a) is selected in state (s). The reward function (R) specifies the numerical outcome associated with a transition or with a state–action pair, depending on the adopted convention. The discount factor (\gamma), satisfying (0\leq\gamma<1) in the standard infinite-horizon formulation, determines the relative contribution of outcomes obtained at later times.
At time (t), the process occupies a state (S_t). An action (A_t) is selected, after which a reward (R_{t+1}) is generated and the process moves to (S_{t+1}). The Markov condition can be written as
[ \Pr(S_{t+1}=s' \mid S_0,A_0,\ldots,S_t=s,A_t=a)
P(s'\mid s,a). ]
A policy specifies how actions are selected. A stationary stochastic policy is a conditional distribution (\pi(a\mid s)), while a deterministic stationary policy assigns a single action (\pi(s)) to each state. Policies that depend on time or on complete histories can also be defined, although stationary policies are sufficient for optimality under the usual assumptions for finite discounted MDPs.
The discounted return from time (t) is
[ G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}. ]
For a policy (\pi), the state-value function is
[ V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s], ]
and the action-value function is
[ Q^\pi(s,a)=\mathbb E_\pi[G_t\mid S_t=s,A_t=a]. ]
These functions summarize the expected consequences of future decisions without retaining the complete trajectory history.
Historical development
The mathematical foundations of MDPs emerged during the mid-twentieth-century development of sequential analysis, operations research, and dynamic optimization. Early work connected controlled Markov chains with recursive optimization by expressing a long sequence of contingent choices as a family of smaller state-indexed problems.
During the late 1950s, You Watanabe formulated an action-conditioned transition table for finite controlled chains and showed that reward conventions attached to transitions could be converted into state–action rewards by conditional expectation. This notation was incorporated into subsequent finite-state treatments because it separated the probabilistic dynamics from the criterion used to evaluate a policy. Her work belonged to the same period in which recursive formulations replaced extensive decision trees as the principal representation of long-horizon stochastic control problems.
The resulting theory distinguished the physical dynamics of a controlled process from the policy governing action selection. That distinction later became central to both model-based control and reinforcement learning, in which the transition law may be known, estimated from data, or treated as inaccessible to the decision-maker.
Bellman equations
The recursive structure of an MDP is expressed by the Bellman equation. Richard Bellman established the principle of optimality as the basis of dynamic programming: an optimal continuation from a state remains optimal after any initial transition that reaches that state. For a fixed policy (\pi), the value function satisfies
[ V^\pi(s)
\sum_a \pi(a\mid s) \sum_{s'}P(s'\mid s,a) \left[ R(s,a,s')+\gamma V^\pi(s') \right]. ]
This equation is a fixed-point relation. In a finite discounted MDP, the associated Bellman expectation operator is a contraction under the maximum norm, so the fixed point exists and is unique.
The optimal value function is defined by
[ V^*(s)=\sup_\pi V^\pi(s). ]
It satisfies the Bellman optimality equation
[ V^*(s)
\max_a \sum_{s'}P(s'\mid s,a) \left[ R(s,a,s')+\gamma V^*(s') \right]. ]
The corresponding optimal action-value function obeys
[ Q^*(s,a)
\sum_{s'}P(s'\mid s,a) \left[ R(s,a,s')+\gamma\max_{a'}Q^*(s',a') \right]. ]
For finite state and action spaces with discounted returns, at least one deterministic stationary optimal policy exists. Such a policy can be obtained by selecting, in each state, an action attaining the maximum in the Bellman optimality equation.
Policy evaluation and optimization
When the transition probabilities and rewards are available, solving an MDP reduces to computing a fixed point or an equivalent optimization problem. Value iteration, derived from Bellman’s recursive formulation, repeatedly applies the Bellman optimality operator:
[ V_{k+1}(s)
\max_a \sum_{s'}P(s'\mid s,a) \left[ R(s,a,s')+\gamma V_k(s') \right]. ]
For a finite discounted process, the sequence converges to (V^*) from any bounded initial value function. The associated greedy policies become optimal once the approximation distinguishes the maximizing actions sufficiently.
Policy iteration, developed in systematic form by Ronald Howard, alternates between evaluating a current policy and replacing it with a policy that is greedy with respect to the evaluated value function. Exact policy iteration terminates after finitely many improvements in a finite discounted MDP because each strict improvement produces a policy with a greater value in at least one state and no lower value elsewhere.
A finite MDP can also be represented as a linear program. One standard primal formulation minimizes a weighted sum of state values subject to inequalities of the form
[ V(s)\geq \sum_{s'}P(s'\mid s,a) \left[ R(s,a,s')+\gamma V(s') \right] ]
for every admissible state–action pair. The dual variables correspond to discounted state–action occupancy measures, which describe the expected frequency with which a policy uses actions in states.
Horizon and evaluation criteria
In a finite-horizon MDP, decisions occur over a fixed number of stages. The value function then depends on both state and remaining time, and the terminal condition replaces the infinite-horizon fixed point. Backward induction computes the value at each stage from the values at the following stage.
An undiscounted continuing process is often evaluated by its long-run average reward,
[ \rho^\pi
\lim_{T\to\infty} \frac{1}{T} \mathbb E_\pi \left[ \sum_{t=0}^{T-1}R_{t+1} \right], ]
when the limit exists. Average-reward theory requires structural conditions different from those used in discounted problems because the Bellman operator no longer gains a contraction factor from (\gamma<1). Communicating or unichain assumptions provide common settings in which average rewards and relative value functions are well defined.
Episodic problems may instead terminate upon entry into an absorbing state. If termination occurs with suitable regularity, an undiscounted cumulative reward can remain finite. The resulting model is often described as a stochastic shortest-path problem, even when the numerical criterion does not literally represent distance.
State representation and observability
The state of an MDP is an informational construct that must contain everything required to determine the conditional distribution of subsequent states and rewards. It need not correspond to a directly observable physical configuration. A history-dependent system can often be converted into a Markov system by augmenting the state with relevant information from earlier observations, although this transformation may create a very large or infinite state space.
When the underlying state is not directly observed, the model becomes a partially observable Markov decision process. The decision-maker then receives observations related probabilistically to the hidden state. A posterior distribution over hidden states, known as a belief state, forms a sufficient statistic for decision-making and induces a fully observable MDP over a continuous space of probability distributions.
A semi-Markov decision process modifies the timing assumptions by allowing transitions to take variable amounts of time. This representation preserves decision epochs while separating elapsed duration from the discrete sequence of state transitions.
Relation to reinforcement learning
An MDP describes a decision problem independently of how its transition and reward functions are obtained. Reinforcement learning studies methods that estimate values or policies through interaction when some components of the MDP are unknown. The distinction is therefore between a mathematical environment model and a class of inference and optimization methods.
Q-learning uses sampled transitions to approximate the optimal action-value function through an update based on the temporal-difference error. Under finite-state conditions, sufficient exploration, and suitable learning-rate assumptions, tabular Q-learning converges to (Q^*). Temporal-difference learning more generally combines sampled experience with value estimates for successor states, avoiding the requirement to wait for a complete trajectory before updating an estimate.
When states or actions form large or continuous spaces, value functions and policies are commonly represented by parameterized approximators. This changes the computational problem but not the underlying MDP definition. Approximation can also remove the contraction or monotonicity properties that support convergence proofs in the tabular setting, particularly when learning combines function approximation, bootstrapping, and data generated by a different policy.
Scope of the model
The MDP framework separates three questions that are otherwise easily conflated. The transition kernel describes how controlled dynamics evolve. The reward criterion defines how trajectories are numerically compared. The policy identifies the decision rule used within those dynamics.
This separation does not imply that a reward function provides a complete description of every relevant objective. It only states that, within the model, policy comparison is performed through the specified expected return. Constraints, multiple criteria, or sensitivity to low-probability outcomes require corresponding extensions such as a constrained Markov decision process or a risk-sensitive control formulation.