Sequential Decisions and Markov Decision Processes

When a one-shot decision is not enough

Many operational and strategic problems repeat: maintenance, inventory, pricing, capacity, routing, staffing and resource allocation.

In these problems, an action affects not only the immediate result but also the next state. Skipping maintenance can save cash today while increasing future failure risk. Discounting inventory can reduce stock now but change future demand or availability. A sequential model captures these intertemporal effects.

A Markov decision process is a standard formalism when the current state contains the information needed to predict the distribution of the next state given the chosen action. The Markov assumption is a modelling statement: past history influences the future only through the current state representation. If relevant history has been omitted, the state must be expanded.

Core elements of an MDP

A finite MDP can be described by states, actions, transition probabilities, rewards and a horizon or discount factor.

The reward model should represent the objective, not convenient data. If late delivery has a strategic penalty beyond direct cost, include the relevant consequence or model it as a constraint. If safety limits cannot be traded for profit, a constrained formulation may be more appropriate than a soft penalty.

Policies and value functions

A policy specifies what action to take as a function of state.

The state-value function measures expected future return starting from a state and following a policy. An action-value function measures expected return after taking a particular action and then following the policy. These functions compress long sequences of future possibilities into decision-relevant values.

The equation expresses self-consistency: the value now is immediate reward plus discounted expected value of the next state. This recursive structure enables dynamic programming.

Optimality and the Bellman equation

An optimal policy selects actions that maximise long-run value.

The maximisation occurs inside each state because the best action can differ by condition. A maintenance policy may inspect a healthy machine, repair a degraded machine and replace a failed one. The value function includes future consequences, preventing the rule from choosing only the lowest immediate cost.

Policy evaluation and policy iteration

Exact dynamic programming alternates between evaluating a policy and improving it.

Policy iteration can converge in relatively few improvement steps for many finite problems, but each evaluation can be computationally demanding. Variants use partial evaluation or asynchronous updates to trade precision per iteration for speed.

Value iteration and asynchronous updates

Value iteration applies the Bellman optimality update repeatedly until values converge sufficiently.

Rather than fully evaluating one policy, value iteration repeatedly updates state values toward the optimal fixed point. The resulting value function can then define a greedy policy. Asynchronous variants update selected states rather than sweeping through the entire state space, which can focus computation on important or reachable regions.

Convergence tolerances should be chosen with the action gap in mind. Very precise values are unnecessary if the preferred action is stable across a wide range; more precision is required when competing actions have nearly equal value.

Linear programming and linear-quadratic structure

The source also presents alternative exact solution structures.

Finite discounted MDPs can be formulated as linear programs using Bellman inequalities. This can be useful when integrating with optimisation tooling or constraints. Continuous control problems with linear dynamics and quadratic costs admit special analytical or efficient numerical solutions under their assumptions.

Special structure is valuable because general sequential decision problems can be computationally large. Before applying a generic algorithm, look for monotonicity, convexity, separability or linear-quadratic form that can reduce complexity.

Worked example: preventive maintenance

Consider equipment with healthy, degraded and failed states, with actions to operate, inspect, repair or replace.

Operating a degraded asset may produce immediate output but increase the probability of failure next period. Repair costs cash now while improving the next-state distribution. A one-period cost comparison may favour continued operation; an MDP can show that repair has higher total value because it reduces expected failure cost and downtime.

The model should include only decision-relevant health states and transition probabilities that can be supported by data or engineering judgement. If condition is not fully observable, the problem becomes one of state uncertainty and should use belief-state methods rather than pretending the state is known.

Implementation from model to operating rule

A technically correct method still needs an auditable operating translation.

Before deploying an MDP-derived policy, translate abstract states and actions into observable operating definitions. Specify how the system identifies a state, what happens when data are delayed, which actions are infeasible, and who can override the recommendation. Run the policy side by side with the current rule before allowing automatic control, and compare both immediate outcomes and the future-state distributions they create. A mathematically optimal policy can fail operationally if staff interpret states differently, if transition probabilities changed after the model was built, or if an action takes longer to execute than the model assumes. Treat deployment as part of the decision model rather than a separate software step.

Application checklist

• Use a sequential model when current actions materially alter future states or options.
• Define a state that captures decision-relevant history.
• Specify feasible actions by state.
• Estimate transition probabilities and immediate rewards transparently.
• Choose horizon and discounting with an explicit interpretation.
• Use policy or value iteration when the state space permits exact dynamic programming.
• Check whether special optimisation structure can simplify the problem.
• Validate the policy on realistic trajectories before operational use.