2. Markov decision processes for control engineers

For a control engineer, a Markov decision process (MDP) is best understood as a discrete-time stochastic system with a decision input and a cumulative performance objective. It is the formal bridge between classical state-space control and reinforcement learning: the same plant model, the same state and input variables, and the same notion of an optimal trajectory, but with a cost (or reward) accumulated over time rather than a fixed terminal objective. This section builds the MDP from the control engineer's perspective, then connects it to the Bellman operators and to optimal control.

2.1 The MDP Tuple in Control Terms

An MDP is defined by the tuple (S, A, P, c, γ). In control language:

• S — the state space, e.g. joint angles and velocities of a manipulator, or the position and velocity of a vehicle.
• A — the action (input) space, e.g. motor torques, throttle and steering commands.
• P(s' | s, a) — the transition kernel, the stochastic counterpart of the discrete-time dynamics x_{k+1} = f(x_k, u_k).
• c(s, a) — the stage cost, e.g. tracking error squared plus control effort.
• γ ∈ [0, 1) — the discount factor, which trades off immediate versus future cost.

The key difference from deterministic optimal control is that P is a conditional distribution, not a function. Process noise, model uncertainty, and unmodeled disturbances are all absorbed into this kernel. A control engineer who writes x_{k+1} = A x_k + B u_k + w_k with w_k ~ N(0, Σ) has already defined a transition kernel: P(s' | s, a) = N(A s + B a, Σ).

2.2 Transition Kernels and the Markov Property

The Markov property states that the next state depends only on the current state and action, not on the full history. For a control engineer this is exactly the state-space assumption: the state is a sufficient statistic for the future. If the plant has unmodeled dynamics or delayed measurements, the Markov property fails unless the state is augmented (e.g. adding a delay line or an integral term).

Two kernel representations are common in practice:

• Density form p(s' | s, a) — used for continuous states, e.g. Gaussian process noise.
• Tabular form P(s' | s, a) — used for discretized or inherently discrete systems, e.g. a grid-world or a finite-state machine.

When the state is continuous, the transition kernel is often implemented as a simulator: given (s, a), sample s'. This is the same simulator used in model-based control, but now it is queried by a learning algorithm rather than by a trajectory optimizer.

2.3 Cost-to-Go and the Value Functions

The cost-to-go from state s under policy π is the expected discounted sum of future costs:

V^π(s) = E[ Σ_{k=0}^{∞} γ^k c(s_k, a_k) | s_0 = s, a_k ~ π(·|s_k) ]

The action-value function is the same quantity conditioned on the first action:

Q^π(s, a) = c(s, a) + γ E_{s'~P}[ V^π(s') ]

For a control engineer, V^π is the closed-loop performance index of the policy π, and Q^π is the performance index of taking action a now and following π afterwards. The optimal value functions V* and Q* satisfy the Bellman optimality equations:

V*(s) = min_a [ c(s, a) + γ E_{s'~P}[ V*(s') ] ]
Q*(s, a) = c(s, a) + γ E_{s'~P}[ min_{a'} Q*(s', a') ]

These are the stochastic counterparts of the Hamilton–Jacobi–Bellman (HJB) equation. In continuous time, the HJB equation is a partial differential equation; in discrete time with a finite or discretized state space, it becomes the Bellman equation above.

2.4 Bellman Operators

The Bellman operators turn the optimality equations into fixed-point problems. Define the policy evaluation operator T^π and the optimality operator T*:

(T^π V)(s) = c(s, π(s)) + γ E_{s'~P}[ V(s') ]
(T* V)(s)  = min_a [ c(s, a) + γ E_{s'~P}[ V(s') ] ]

Both operators are γ-contractions in the sup-norm: ||T V1 - T V2||_∞ ≤ γ ||V1 - V2||_∞. By the Banach fixed-point theorem, each has a unique fixed point, and value iteration V_{k+1} = T V_k converges to it geometrically at rate γ. This is the theoretical guarantee behind value iteration, policy iteration, and many RL algorithms.

For a control engineer, the contraction property has a practical meaning: the discount factor controls how fast the value function forgets distant future costs. A small γ (e.g. 0.9) makes the fixed point easy to reach but biases the policy toward short-term performance; a large γ (e.g. 0.99 or 0.999) gives a long planning horizon but slows convergence and increases variance in learning.

2.5 Connection to Optimal Control

The MDP framework generalizes several classical optimal control formulations:

The linear-quadratic regulator is the canonical example where the MDP is solved exactly. For s_{k+1} = A s_k + B a_k + w_k, c(s, a) = s^T Q s + a^T R a, and w_k ~ N(0, Σ), the optimal value function is quadratic: V*(s) = s^T P s + const, where P solves the discrete algebraic Riccati equation. The optimal policy is linear: a = -K s. This is the ground truth against which RL algorithms on linear systems are often benchmarked.

MPC, by contrast, solves a finite-horizon optimization at each step and applies only the first input. It approximates V* by truncating the horizon, which is equivalent to using a terminal cost that stands in for the infinite tail. Understanding this connection helps explain why MPC can be sample-efficient but requires a model, while RL can learn without a model but typically needs more interaction data.

2.6 A Worked Example: Discrete-Time Double Integrator

Consider a double integrator with state s = [p, v]^T, input a, and discretization step Δt = 0.1 s:

A = [[1, Δt], [0, 1]],  B = [[0.5 Δt^2], [Δt]]
c(s, a) = p^2 + 0.1 v^2 + 0.01 a^2
γ = 0.99

If we discretize p and v onto a grid (e.g. p ∈ [-2, 2] in 41 points, v ∈ [-2, 2] in 41 points) and a onto 11 points, we obtain a tabular MDP with 1681 states and 11 actions. Value iteration with the Bellman operator T* converges in a few hundred sweeps. The resulting greedy policy π(s) = argmin_a Q*(s, a) approximates the LQR solution; the residual error is due to state and action discretization.

This example is small enough to run on a laptop and is a useful sanity check before moving to function approximation. If value iteration diverges or oscillates, the usual causes are: γ ≥ 1, an incorrect transition kernel (e.g. missing the Δt scaling), or a cost function that is not positive definite.

2.7 What to Watch For

• Discounting vs. average cost: if the task is continuing and performance is measured per step, the average-cost formulation may be more appropriate than discounting.
• State augmentation: if the Markov property is violated, add the missing variables (delays, integrals, disturbances) to the state rather than hoping the learner will compensate.
• Cost scaling: the relative magnitude of c(s, a) and γ determines the effective planning horizon; normalize costs so that V* is of order 1 for numerical stability.
• Continuous vs. discrete: the Bellman operators are defined for both, but the contraction proof and the implementation differ. For continuous states, function approximation replaces the table.

The diagram above summarizes the MDP loop and the Bellman backup that connects the transition kernel, the stage cost, and the value function. The plant and policy interact through state and action, the stage cost is accumulated, and the Bellman operator propagates value backward through the transition kernel. The dashed arrow from the Bellman operator back to the policy represents policy improvement, which is the second half of policy iteration. The optimal control box on the left reminds us that the same fixed point can be reached through HJB, LQR, or MPC, depending on the structure of the problem.

With the MDP formalism in place, the next step is to choose how to represent the value function and how to solve the Bellman equation in practice. For small discrete problems, tabular value iteration is sufficient. For continuous control, function approximation, temporal-difference learning, and policy gradient methods become necessary. The Bellman operators defined here remain the theoretical anchor for all of them.