# Markov Decision Process

A Markov decision process (MDP) is a mathematical framework for modeling sequential decision-making under uncertainty, defined by states, actions, transition probabilities, and rewards. It underpins reinforcement learning and stochastic dynamic programming.

A Markov decision process (MDP) is a mathematical model for sequential decision making when outcomes are uncertain. It is a type of stochastic decision process, often solved using methods of stochastic dynamic programming. Originating from operations research in the 1950s, MDPs have since gained recognition in fields such as ecology, economics, healthcare, telecommunications, and [reinforcement learning](https://www.wikiprompt.org/wiki/machine-learning). In reinforcement learning, the MDP framework models the interaction between a learning agent and its environment, characterized by states, actions, and rewards, providing a simplified representation of key elements of [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) challenges, including cause and effect, uncertainty, and explicit goals.

The name derives from its connection to Markov chains, developed by Russian mathematician Andrey Markov. The "Markov" property refers to the underlying structure where state transitions depend only on the current state and action, not on prior history. The process is called a "decision process" because it involves making decisions that influence these transitions, extending Markov chains into decision-making under uncertainty.

## Formal Definition

An MDP is typically defined as a 4-tuple \((S, A, P_a, R_a)\), where:

- \(S\) is the state space, which may be discrete or continuous (e.g., the set of real numbers).
- \(A\) is the action space, with \(A_s\) denoting the set of actions available from state \(s\). This set may also be discrete or continuous.
- \(P_a(s, s')\) is the transition probability that action \(a\) in state \(s\) at time \(t\) leads to state \(s'\) at time \(t+1\). For discrete states, \(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\). For continuous state spaces, the probability is defined via an integral, often with respect to the Lebesgue measure.
- \(R_a(s, s')\) is the immediate reward (or expected reward) received after taking action \(a\) to transition from \(s\) to \(s'\). The reward is generally a random variable.

A policy function \(\pi\) is a (potentially probabilistic) mapping from state space to action space, specifying which action to take in each state.

## Optimization Objective

The goal in an MDP is to find a policy \(\pi\) that maximizes a cumulative function of random rewards, typically the expected discounted sum over an infinite horizon: \(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\), where \(\gamma \in [0, 1)\) is a discount factor. Once a policy is fixed, the MDP behaves like a Markov chain, as the action in each state is determined by \(\pi(s)\).

Common solution methods include dynamic programming techniques such as value iteration and policy iteration, which compute optimal value functions or policies. These methods are foundational in [reinforcement-learning](https://www.wikiprompt.org/wiki/reinforcement-learning) algorithms like Q-learning and SARSA.

## Applications

MDPs are widely applied across domains. In economics, they model optimal consumption and investment decisions. In healthcare, they guide treatment planning under uncertainty, such as chronic disease management. In telecommunications, they optimize resource allocation and network routing. In ecology, they inform conservation strategies for species management. In [machine-learning](https://www.wikiprompt.org/wiki/machine-learning), MDPs are central to reinforcement learning, enabling agents to learn from interaction with environments, as seen in robotics, game playing, and autonomous systems.

## Relationship to Reinforcement Learning

Reinforcement learning (RL) uses the MDP framework to formalize the agent-environment interaction. In RL, the agent does not know the transition probabilities or reward functions in advance; instead, it learns an optimal policy through trial and error, using samples from the environment. This distinguishes RL from classical MDP solving, which assumes known model parameters. Modern RL, including deep reinforcement learning, combines MDPs with [neural-network](https://www.wikiprompt.org/wiki/neural-network) function approximators to handle large state spaces, as demonstrated in applications like game playing and autonomous driving.

## Extensions and Variations

Several extensions address limitations of the basic MDP. Partially observable Markov decision processes (POMDPs) handle situations where the agent cannot directly observe the full state. Factored MDPs exploit structure in state variables to improve scalability. Multi-agent MDPs extend the framework to multiple decision makers with interacting objectives. These variations retain the core Markov property while adapting to more complex real-world problems.

## Historical Context

The formalization of MDPs is attributed to Richard Bellman in the 1950s, who also developed dynamic programming. Andrey Markov's earlier work on stochastic processes provided the theoretical foundation. Since then, MDPs have become a cornerstone of operations research and artificial intelligence, influencing both theoretical and applied work in sequential decision making.

---
Source: https://www.wikiprompt.org/wiki/markov-decision-process
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-09T02:00:35.826809+00:00