Markov decision process

• 1. Introduction

  ›

  A Markov decision process asks a deceptively simple question: when you cannot be certain what will happen next, how do you make the best sequence of choices? The mathematical model known as the MDP emerged from operations research in the 1950s, and it has since reached into ecology, economics, healthcare, telecommunications, and the field now called reinforcement learning. At its core, the framework captures three things that make decision-making genuinely hard. It handles cause and effect. It manages uncertainty and nondeterminism. And it keeps the decision maker aimed at an explicit goal. The framework takes its name from the Russian mathematician Andrey Markov, whose work on chain processes forms the structural backbone of the model. But where a Markov chain simply describes how a system moves between states on its own, a Markov decision process adds a decision maker who can steer those transitions. The questions that follow are not abstract: How do you define what counts as a good outcome when rewards arrive over time? What happens when you can only see part of the world? And what do you do when you cannot even write down the rules of the environment, only experience them?

• 2. States, Actions, and Rewards

  ›

  Every Markov decision process is defined as a 4-tuple: a state space, an action space, a transition probability function, and a reward. The state space can be discrete or continuous, stretching across possibilities as varied as the set of real numbers. The action space describes what choices are available, and this set too can be discrete or continuous. The transition function captures the probability that taking a particular action in a particular state at a given time will lead to a specific next state. The reward is the immediate payoff received after an action moves the system from one state to another; it is, in general, a random variable. A classic illustration from control theory is the Pole-Balancing model. In that example, the state is a tuple of four quantities: pole angle, angular velocity, the position of the cart, and its speed. The available actions are simply applying a force to the left or to the right. The reward equals one if the pole is still upright after the transition, and zero otherwise. What ties all four components together is the policy: a function, potentially probabilistic, that maps every state to an action. Once a policy is fixed, the decision process collapses into something simpler. The choices at each state are fully determined, and the system behaves like an ordinary Markov chain.

• 3. Finding the Optimal Policy

  ›

  Choosing a policy that is merely good is not the goal. The objective is to maximize a cumulative function of the random rewards, and the standard formulation uses an expected discounted sum over a potentially infinite time horizon. The discount factor must satisfy certain mathematical conditions and is usually set close to one, with the exact value linked to a chosen discount rate. A lower discount factor makes the decision maker comparatively short-sighted, giving less weight to rewards that arrive further in the future. A stricter alternative is the finite-horizon or step-return objective, which considers only the first steps of the process with each reward weighted equally. That formulation is more common in learning theory. A policy that maximizes either objective is called an optimal policy. A given MDP may have more than one distinct optimal policy. Because of the Markov property, any optimal policy can be expressed as a function of the current state alone. When the discount factor is deterministic, a unique fixed point exists that satisfies the Bellman equation; unrolling that recursion demonstrates that the corresponding policy is simultaneously optimal across all states. Even when the policy is probabilistic, any such non-deterministic policy is dominated by a deterministic one.

• 4. Algorithms for Solving MDPs

  ›

  Dynamic programming provides the standard family of algorithms for finite state and action MDPs where the transition probabilities and reward functions are given explicitly. Each algorithm maintains two arrays indexed by state: one holding real-valued estimates, and one holding the current best action for each state. The two steps, a value update and a policy update, are repeated across all states until the estimates stop changing. Value iteration, also called backward induction, avoids storing the policy explicitly during the update. It starts from an initial guess and repeatedly computes improved estimates until the values converge, a process guaranteed to terminate by the Banach fixed-point theorem. Lloyd Shapley's 1953 paper on stochastic games already contained value iteration as a special case, though this connection was recognized only later. Policy iteration, by contrast, was invented by Howard to optimize Sears catalogue mailing, a problem he had previously handled with value iteration. It interleaves a linear system solve with a nonlinear improvement step, and it has a definite stopping condition: the algorithm halts as soon as two consecutive improvement steps produce the same policy. Policy iteration can be faster than value iteration when the action space is significantly larger than the state space, but it is usually slower when the number of possible states is large. A hybrid called modified policy iteration repeats the value update several times before each policy update. A fourth variant, prioritized sweeping, concentrates computation on states where estimates changed recently or on states near a point of particular interest.

• 5. Complexity and Computational Limits

  ›

  Algorithms that find optimal policies in time polynomial in the size of the problem representation exist for finite MDPs, placing decision problems based on MDPs in the computational complexity class P. The practical difficulty is not in the algorithm's behavior but in the representation itself. Because of the curse of dimensionality, the size of the problem representation is often exponential in the number of state and action variables. This growth limits exact solution techniques to problems that can be stated compactly. Online planning methods such as Monte Carlo tree search can find useful solutions in larger problems. In theory, it is possible to construct online planning algorithms that find a policy arbitrarily close to optimal without any computational complexity dependence on the size of the state space. The type of simulator or model available for a particular MDP determines which solution algorithms can even be applied. Dynamic programming requires an explicit transition model. Monte Carlo tree search requires a generative model, or an episodic simulator that can be copied at any state. Most reinforcement learning algorithms require only an episodic simulator, which yields trajectories of states, actions, and rewards without needing to represent the full transition distribution.

• 6. Extensions and Variations

  ›

  A standard Markov decision process assumes the decision maker can observe the full state before acting. When that assumption breaks down, the problem becomes a partially observable Markov decision process, or POMDP. A separate family of extensions introduces constraints. Constrained Markov decision processes, known as CMDPs, differ from standard MDPs in three fundamental ways: multiple costs can be incurred after each action rather than one, dynamic programming does not apply and linear programming is the required solution method, and the final policy depends on the starting state. The method of Lagrange multipliers applies to CMDPs, and several Lagrangian-based algorithms have been developed. One recent application of CMDPs is motion planning in robotics. Continuous-time MDPs extend the framework to settings where decisions can be made at any moment rather than at discrete steps, making them better suited to systems whose dynamics are described by ordinary differential equations. They apply to queueing systems, epidemic processes, and population processes. When the state and action spaces are continuous in a continuous-time setting, the optimal criterion can be found by solving the Hamilton-Jacobi-Bellman partial differential equation. At the most abstract level, category theory offers yet another interpretation: a Markov decision process can be encoded as a functor from a free monoid with generating set equal to the action space into the Kleisli category of the Giry monad, and generalizing from monoids to arbitrary categories yields what researchers call a context-dependent Markov decision process.

• 7. Reinforcement Learning and Automata

  ›

  Reinforcement learning tackles MDPs in the hardest possible setting: transition probabilities and rewards are unknown, and the agent can only learn by interacting with the environment. The central challenge is sample efficiency, meaning minimizing the number of interactions needed to find a policy close to optimal. Because the process is stochastic, learning the exactly optimal policy from a finite number of samples is, in general, impossible. The practical solution is Q-learning, which maintains an array indexed by state-action pairs. Experience takes the form of tuples recording which state the agent was in, which action it tried, and which state and reward resulted. The array is updated directly from this experience without needing an explicit transition model. A related approach is learning automata, first surveyed in detail by Narendra and Thathachar in 1974. Learning automata were originally described as finite-state automata. Like Q-learning, the method can operate when probabilities and rewards are unknown, but it omits the memory of Q-values entirely and instead updates action probabilities directly. It carries a rigorous proof of convergence. The terminology used across these fields is not uniform. Researchers in economics and optimization tend to speak of actions, rewards, and values, and use the symbol beta or gamma for the discount factor. Engineers and navigation researchers use controls, costs, and cost-to-go, with alpha as the discount symbol. The two streams share the same underlying mathematics; only the vocabulary and sign conventions differ.