Artificial Intelligence & Data Science is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Markov decision processes

Markov decision processes (MDPs) formalise sequential decision making under uncertainty using states, actions, transition probabilities and rewards; they underpin dynamic programming and reinforcement learning methods such as value iteration and policy iteration.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

MDPs give a precise mathematical model for problems where an agent makes a sequence of decisions and receives (possibly random) rewards. Engineers use MDPs to design controllers, plan actions for robots, schedule resources, and as the foundation for reinforcement learning algorithms (see Reinforcement learning basics and Q-learning in the course list).

Key ideas

Start from first principles and define each term before using it.

  • Markov decision process (MDP): a tuple (S, A, P, R, γ) where S is a set of states, A is a set of actions, P is the transition probability function, R is the reward function, and γ is the discount factor. We assume decisions occur at discrete time steps t = 0, 1, 2, ...

  • State (s): a complete description of the situation at a time step. The MDP assumes the Markov property: the probability distribution of the next state and reward depends only on the current state and chosen action, not on earlier history.

  • Action (a): a choice available to the agent when in a state s. The set A(s) denotes available actions in state s.

  • Transition probability: P(s' | s, a) is the probability of moving to state s' when action a is taken in state s. Assumption commonly used: finite state and action spaces for exam questions, though theory extends to infinite/continuous spaces. For each s and a, ∑_{s'} P(s'|s,a) = 1.

  • Reward (r): the scalar immediate feedback received after a transition. We treat reward units as reward units (r.u.). R(s, a, s') is the expected reward for that transition.

  • Policy (π): a rule to choose actions. A deterministic policy π(s) returns a single action for each state. A stochastic policy π(a | s) gives a probability distribution over actions in each state.

  • Return (G_t): the (discounted) sum of future rewards from time t: G_t = ∑{k=0}^{∞} γ^k R{t+k+1}, where 0 ≤ γ ≤ 1. If γ < 1 and rewards are bounded, the return converges almost surely.

  • Value function of a policy (V^π): the expected return starting in state s and following policy π: V^π(s) = Eπ[G_t | S_t = s]. Define the action-value function Q^π(s, a) = Eπ[G_t | S_t = s, A_t = a].

  • Bellman expectation equation (for a fixed policy π): it decomposes the value function into immediate reward plus discounted value of the next state. Under the MDP assumptions, V^π(s) = ∑{a} π(a | s) ∑{s'} P(s' | s, a) [ R(s, a, s') + γ V^π(s') ]. Derivation normally given in exams: start from definition of V^π(s) = Eπ[R_{t+1} + γ G_{t+1} | S_t = s] and use law of total expectation on A_t and S_{t+1}.

  • Bellman optimality equation: defines the optimal value function V* = max_π V^π. For all s, V*(s) = max_{a} ∑{s'} P(s' | s, a) [ R(s, a, s') + γ V*(s') ]. The optimal action-value function satisfies Q*(s, a) = ∑{s'} P(s' | s, a) [ R(s, a, s') + γ max_{a'} Q*(s', a') ]. The derivation uses the principle of optimality: an optimal policy achieves the maximum at each step, and future choices remain optimal.

  • Dynamic programming algorithms (assume known P and R):

    • Policy evaluation: solve the linear system given by the Bellman expectation equation for V^π (exact for finite states), or iteratively compute V^π ← T^π V^π until convergence.
    • Policy improvement: given V^π, compute a new greedy policy π'(s) = argmax_a ∑_{s'} P(s' | s, a) [ R(s, a, s') + γ V^π(s') ]. If π' ≠ π, repeat.
    • Policy iteration: alternate evaluation and improvement until policy is stable; for finite discounted MDPs with 0 ≤ γ < 1 it converges to an optimal policy in finitely many iterations.
    • Value iteration: apply the Bellman optimality backup iteratively: V_{k+1}(s) = max_a ∑_{s'} P(s' | s, a) [ R(s, a, s') + γ V_k(s') ] until V_k converges; then extract policy by greedification.
  • Contraction and convergence: the Bellman operator (both T^π and T*) is a γ-contraction under the sup norm for 0 ≤ γ < 1, which guarantees unique fixed points and convergence of iterative methods. For γ = 1, additional conditions (e.g., episodic tasks, proper policies) are required.

  • Diagram to draw for an exam (describe exactly): draw a directed graph with three circles labeled S1, S2, S3 (states). From S1, illustrate two actions: for action a, draw two arrows labeled a — one to S2 with probability 0.8 and reward +5, and one to S3 with probability 0.2 and reward 0 (so probabilities for action a sum to 1); for action b, draw a single arrow labeled b from S1 to S3 with probability 1 and reward 0. From S2 draw a single arrow to S3 with probability 1 and reward +10. Mark S3 as a terminal state (double circle). Add a small table with P(s'|s,a) and R(s,a,s') for the shown transitions. This diagram is enough to illustrate transitions, probabilities and rewards.

Formulas

G_t = Σ_{k=0}^{∞} γ^k R_{t+k+1} — G_t is return from time t; γ is discount factor (unitless); R_t in reward units (r.u.). Applies to discounted infinite-horizon returns.

V^π(s) = Eπ[G_t | S_t = s] — V^π(s) is expected return from state s under policy π (r.u.).

Q^π(s,a) = Eπ[G_t | S_t = s, A_t = a] — action-value function under policy π (r.u.).

V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ V^π(s') ] — Bellman expectation equation. Applies for any policy π in an MDP.

Q^π(s,a) = Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ Σ_{a'} π(a'|s') Q^π(s',a') ] — Bellman expectation equation for action values.

V*(s) = max_a Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ V*(s') ] — Bellman optimality equation. Applies when V* exists; unique when 0 ≤ γ < 1 and finite states.

Q*(s,a) = Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ max_{a'} Q*(s',a') ] — optimal action-value Bellman equation.

V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a) [ R(s,a,s') + γ V_k(s') ] — value iteration update (unit: r.u.).

V = (I - γ P^π)^{-1} r^π — matrix solution for policy evaluation in finite MDPs: P^π is the state transition matrix under π, r^π is expected immediate reward vector under π, I identity. Applies when (I - γ P^π) is invertible (true if γ < 1 in finite MDPs).

Worked examples

Example 1 — Policy evaluation (solve linear system). Finite MDP: S = {s1, s2}, deterministic policy π with actions fixed so transitions and rewards are:

  • From s1 → s2 with reward 5 r.u.
  • From s2 → s1 with reward 2 r.u. Take γ = 0.9. Step 1: Write Bellman equations for V^π: V(s1) = 5 + 0.9 V(s2) V(s2) = 2 + 0.9 V(s1) Step 2: Solve algebraically. Substitute V(s1) into second: V(s2) = 2 + 0.9 (5 + 0.9 V(s2)) = 2 + 4.5 + 0.81 V(s2) = 6.5 + 0.81 V(s2) So (1 - 0.81) V(s2) = 6.5 → 0.19 V(s2) = 6.5 → V(s2) = 6.5 / 0.19 = 34.2105263158 r.u. Then V(s1) = 5 + 0.9 * 34.2105263158 = 5 + 30.7894736842 = 35.7894736842 r.u. Final answers: V(s1) = 35.7894736842 r.u., V(s2) = 34.2105263158 r.u. (These are high because the agent cycles and collects rewards indefinitely; check arithmetic if needed.)

Example 2 — Value iteration and optimal policy. MDP: S = {s1, s2, s3}, s3 is terminal (V(s3)=0). Actions:

  • In s1: action a → s2 with reward 0; action b → s3 with reward 5.
  • In s2: only action c → s3 with reward 10. Take γ = 0.9. Initialize V0(s) = 0 for all s. Iteration 1: V1(s1) = max{ a: 0 + 0.9*V0(s2) = 0, b: 5 + 0.9*V0(s3) = 5 } = 5 V1(s2) = 10 + 0.9*V0(s3) = 10 V1(s3) = 0 Iteration 2: V2(s1) = max{ a: 0 + 0.9*V1(s2) = 0.9*10 = 9, b: 5 } = 9 V2(s2) = 10 (unchanged) Converged values (after one more check): V*(s1)=9 r.u., V*(s2)=10 r.u., V*(s3)=0 r.u. Optimal policy: at s1 choose a (because 9 > 5); at s2 choose c. Final answer: V(s1)=9 r.u., V(s2)=10 r.u., policy π*(s1)=a, π*(s2)=c.**

Common mistakes

  • Using γ = 1 without checking boundedness or episodic termination; iterative methods may not converge.
  • When doing policy evaluation algebraically, sign or substitution errors in solving linear equations (check arithmetic carefully).
  • Confusing transition probabilities P(s'|s,a) with immediate rewards R(s,a,s').
  • In value iteration, greedifying too early (extract policy before convergence) can lead to incorrect policy if values not converged sufficiently.

For your exam

Typical question types and what full-marks answers include:

  • Definitions: define MDP, Markov property, policy, value function; give units where appropriate. Full marks require formal tuple (S,A,P,R,γ) and clear statement of Markov property.
  • Short notes: explain Bellman expectation and optimality equations; include derivation steps. Full marks need the equations plus short derivation using law of total expectation.
  • Derivations: show policy evaluation linear system and solve; or prove contraction property of Bellman operator (outline: sup-norm, use γ factor). Include assumptions (finite states or γ < 1).
  • Numericals: small MDPs requiring value iteration or policy iteration. Show all iterations, state values with units, and final greedy policy.
  • Diagrams: draw state graph with arrows, label actions, transition probabilities, immediate rewards, mark terminal states. Full marks for clear labels and a small accompanying P and R table.
  • Programs (rare): implement value iteration or policy iteration in Python; include stopping tolerance and print final policy and values.

Quick check

  1. What does the Bellman optimality equation compute?
  2. Why do we require γ < 1 for guaranteed convergence in infinite-horizon discounted MDPs?
  3. In policy iteration, what two steps are alternated and why do they converge for finite MDPs?

Answers: 1) The maximum expected return V*(s) achievable from state s (optimal value). 2) Because the Bellman operator is a γ-contraction in sup-norm when γ < 1, ensuring unique fixed point and convergence of iterative methods; with γ = 1 convergence needs extra conditions. 3) Policy evaluation (compute V^π) and policy improvement (make π greedy wrt V^π); they converge because each improvement produces a policy that is at least as good and finite MDPs have finite policy space so iteration terminates.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?