Markov decision process

A Markov decision process (MDP) is a mathematical model of sequential decision-making in which an agent’s actions affect both immediate rewards and the states encountered subsequently. It combines a controlled stochastic process with an objective for evaluating decisions over time. Its defining assumption is that the current state and action contain all information needed to determine the distribution of the next state and reward. MDPs provide a foundation for reinforcement learning, decision theory, and stochastic control. (incompleteideas.net)

Mathematical formulation

A discrete-time, discounted MDP is commonly specified by a tuple $(S,A,P,r,\gamma)$ :

$S$ is the set of states.
$A$ is the set of actions, potentially restricted to an admissible subset $A(s)$ in each state.
$P(s'\mid s,a)$ is the probability of entering state $s'$ after choosing action $a$ in state $s$ .
$r(s,a)$ is the expected immediate reward.
$\gamma$ , with $0\leq\gamma<1$ , is a discount factor.

At time $t$ , the agent observes $S_t$ , selects $A_t$ , receives $R_{t+1}$ , and enters $S_{t+1}$ . Rewards may be random; a more detailed model specifies a joint distribution $p(s',r\mid s,a)$ . Some formulations instead use costs, making minimization the objective. Finite MDPs have finite state and action sets, whereas general formulations allow continuous spaces. (incompleteideas.net)

The Markov property means that, conditional on the present state and action, earlier history supplies no additional predictive information:

\Pr(S_{t+1},R_{t+1}\mid S_0,A_0,\ldots,S_t,A_t) = \Pr(S_{t+1},R_{t+1}\mid S_t,A_t).

This is a statement of conditional independence, not a requirement that consecutive states be independent. Whether it holds depends on how the state is defined; omitting relevant information can invalidate it. Under a fixed stationary policy, the state sequence follows a Markov chain. (incompleteideas.net)

Policies and objectives

A policy specifies how actions are selected. A deterministic stationary policy maps each state to an action; a stochastic stationary policy assigns probabilities $\pi(a\mid s)$ . More general policies may depend on time or the full interaction history. The policy is the solution sought, rather than a single action sequence, because decisions must respond to the states actually encountered. (web.mit.edu)

For an infinite-horizon discounted problem, the return is

G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}.

The objective is to maximize its expected value. Discounting weights distant rewards less heavily and guarantees a finite return when rewards are bounded. Finite-horizon problems evaluate rewards over a specified number of steps, while average-reward problems evaluate long-run reward per step. Episodic formulations terminate upon reaching designated terminal states. These criteria need not produce identical optimal policies. (web.stanford.edu)

Value functions and Bellman equations

The state-value function of a policy is

V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s].

Its action-value function $Q^\pi(s,a)$ evaluates taking action $a$ first and following $\pi$ thereafter. For stationary discounted problems, the Bellman expectation equation expresses value recursively:

V^\pi(s)= \sum_a\pi(a\mid s) \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')\right].

It separates immediate reward from the discounted value of future states. For finite models, policy evaluation can consequently be written as a linear system using matrices. (web.stanford.edu)

The optimal value function $V^*(s)=\sup_\pi V^\pi(s)$ satisfies

V^*(s)=\max_{a\in A(s)} \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^*(s')\right].

For finite state and action sets, bounded rewards, and $\gamma<1$ , an optimal deterministic stationary policy exists. Selecting a maximizing action in this equation produces such a policy. The corresponding Bellman operator is a contraction mapping in the maximum norm, giving a unique optimal value function and convergence of repeated updates. (introml.mit.edu)

Solution methods

When transition probabilities and rewards are known, dynamic programming provides standard solution methods. Value iteration repeatedly applies the Bellman optimality update to a value estimate. Policy iteration alternates between evaluating the current policy and improving it by choosing actions with higher expected return. Finite-horizon problems use backward induction from a terminal value; optimal actions may depend on the remaining horizon. Finite discounted MDPs can also be formulated as linear programming problems within mathematical optimization. (introml.mit.edu)

When the model is unknown, reinforcement learning estimates values or policies from interaction data. Model-based methods learn transition and reward models before or alongside planning; model-free methods avoid explicitly constructing those models. Q-learning, for example, estimates optimal action values using sampled transitions. An MDP defines the decision problem, whereas a learning algorithm specifies how its solution is obtained. (see.stanford.edu)

Applications and extensions

Applications include robotics, inventory control, resource allocation, and supply-chain optimization. In an illustrative inventory model, the state records stock and other relevant variables, actions specify replenishment quantities, uncertain demand determines transitions, and rewards represent revenue minus costs. Including relevant demand information in the state is necessary if demand depends on conditions not captured by stock alone. (see.stanford.edu)

Ordinary MDPs assume that the decision-maker observes the state. A partially observable Markov decision process instead supplies observations that may conceal or imperfectly reveal it. A probability distribution over possible states, called a belief state, can serve as the state of an equivalent fully observable decision process. Semi-Markov decision processes allow variable durations between decisions. (cs.cmu.edu)

Large state spaces make exact value tables and exhaustive updates impractical, illustrating the curse of dimensionality. Approximate methods represent values or policies compactly and replace full computations with sampled or restricted ones. Their behavior depends on the approximation method, available data, and the validity of the transition and reward model. (incompleteideas.net)