EXPLAINER

Markov Decision Processes

conceptfreshness: stablesources not yet verified

A Markov decision process is the mathematical framework for sequential decision-making under uncertainty that underlies reinforcement learning.

Short answer: An MDP = states, actions, transition probabilities, rewards and a discount factor, with the Markov property: the next state depends only on the current state and action. Solving it means finding a policy with maximum expected return.

What is it?

An MDP is the rulebook for a decision game: where you can be (states), what you can do (actions), what happens as a result (probabilistic transitions), and what you earn (rewards). The goal is a plan that earns the most over time.

Also known as: MDP, Bellman equation, POMDP, value function, Q function, markov property, discount factor, policy and value.

Technical definition

Tuple (S, A, P, R, γ). Value functions V^π(s) and Q^π(s,a) satisfy Bellman equations; optimal policies satisfy Bellman optimality. Exact methods (value/policy iteration) need a known model and small state spaces; RL estimates from samples. Partial observability generalises to POMDPs. Real systems often violate the Markov assumption unless the state includes sufficient history.

Entity type: concept · Freshness class: stable.

When should I use it?

Foundational for designing or analysing RL problems.

Implementation patterns

  • Encode history in the state when the environment is partially observable.
  • Model the reward carefully.
  • Use value iteration on small known models.

Technologies and frameworks

Commonly associated: Gymnasium environments, dynamic programming, POMDP solvers. Names are examples of what exists, not recommendations, and projects change quickly.

Practical guide

  1. List states, actions, rewards.
  2. Check whether the state is sufficient.
  3. Choose exact or sample-based solving.
  4. Verify with a simple case you can compute by hand.

Common failure modes

  • State omits information needed to be Markov.
  • Discount factor poorly chosen.
  • Reward misses the true objective.

Troubleshooting

  • Policy behaves inconsistently — Add history or memory to the state.
  • Agent myopic or reckless — Revisit discount factor and reward design.

Contrasted with

  • Reinforcement Learning — RL is the learning problem; an MDP is the mathematical model it is usually posed in.

Questions this page answers

  • What is a Markov decision process?
  • What is the Bellman equation?
  • What is the difference between an MDP and a POMDP?
  • What is a value function?

Typical goals: learn the formal basis of RL; model a sequential decision problem.

Sources and verification

Status: not independently verified. This entry was authored on 2026-10-06 from general technical knowledge, without live checking of the sources below. Treat every source as a lead to confirm (identifier, title, authorship, current version) before publication or citation.

Freshness class: stable — Core ideas that change slowly (maths, classic algorithms). Re-review yearly.

Canonical sources (unverified leads):

  • Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed., 2018) — incompleteideas.net/book
  • Puterman, Markov Decision Processes (1994) — locator to be identified