6.2. Markov Decision Processes

Markov Decision Processes

A Markov Decision Process (MDP) is a probabilistic model for sequential decision-making under uncertainty that satisfies the discrete-time Markov property. It consists of:

• A set of states S and actions A, similar to classical search problems.
• A start state, and possibly terminal states where no further actions are possible.
• A transition function $T(s,a,s^{\prime })=P(s^{\prime }|s,a)$, which specifies the probability of reaching state $s^{\prime }$ from state $s$ when action $a$ is taken.
• A reward function $R(s,a,s^{\prime })$, assigning positive or negative values to transitions, typically giving small step rewards and large terminal rewards.
• An optional discount factor $\gamma \in [0,1]$, which scales weights future rewards down geometrically by a factor ${\gamma }^k$.

The objective in an MDP is to find an optimal policy ${\pi }^{\ast }:S\to A$, a mapping from states to actions that maximizes the total expected discounted reward over time. Unlike deterministic planning, where we seek a fixed action sequence, solving an MDP means computing this optimal policy so the agent can act optimally from any state, not just the start

Two key quantities define optimality in MDPs:

• $V^{\ast }(s)$: the optimal state value, i.e. the expected utility of starting in state $s$ and following the optimal policy thereafter.
• $Q^{\ast }(s,a)$: the optimal Q-value, i.e. the expected utility of starting in $s$, taking action $a$, and then acting optimally.

These satisfy the Bellman optimality equations:
$Q^{\ast }(s,a)={\sum }_{s’}T(s,a,s’)[R(s,a,s’)+\gamma V^{\ast }(s’)]\text{and}{V}^{\ast }(s)={\max }_a{Q}^{\ast }(s,a).$
The Bellman equations express optimal values recursively: the value of a state equals the maximum expected discounted return over all actions. Intuitively, this is equivalent to running expectimax, where Q-states act like chance nodes and state values act like maximizer nodes.

Several dynamic programming algorithms solve the Bellman equations:

• Value iteration iteratively applies Bellman updates until the values converge to the true optimal $V^{\ast }$. It begins with $V_0(s)=0$ (or any arbitrary value) and applies the Bellman backup to all states at each iteration:
  $\forall s\in S,V_{k+1}(s)\leftarrow {\max }_a{\sum }_{s’}T(s,a,s’)[R(s,a,s’)+\gamma V_k(s’)].$
  This process is a contraction mapping with factor $\gamma$, guaranteeing convergence to $V^{\ast }$. This means each iteration brings the values closer to the fixed point $V^{\ast }$, and the difference shrinks geometrically. Once $V^{\ast }$ is found, an optimal policy is obtained via policy extraction:
  ${\pi }^{\ast }(s)=\arg {\max }_a{Q}^{\ast }(s,a).$
  ⠀
• Instead of updating values directly toward optimality, policy iteration alternates between two processes:
  1. Policy evaluation measures how good a policy $\pi$ is by computing $V^{\pi }$ using the Bellman equations for policy evaluation, which yield the linear equation
     $V^{\pi }(s)={\sum }_{s’}T(s,\pi (s),s’)[R(s,\pi (s),s’)+\gamma V^{\pi }(s’)].$
     Alternatively, the process can be executed akin to value iteration for each $V_k^{{\pi }_i}$ by setting $V_0^{{\pi }_i}(s)=0$ (or any arbitrary value) and iterating the Bellman equations until convergence:
     $\forall s\in S,V_{k+1}^{{\pi }_i}(s)\leftarrow {\sum }_{s’}T(s,{\pi }_i(s),s’)[R(s,{\pi }_i(s),s’)+\gamma V_k^{{\pi }_i}(s’)].$
  2. Once the current policy has been evaluated, policy improvement picks actions that look better than the current policy using a one-step greedy lookahead:
     ${\pi }_{i+1}(s)=\arg {\max }_a{\sum }_{s’}T(s,a,s’)[R(s,a,s’)+\gamma V_i^{\pi }(s’)].$
     If ${\pi }_{i+1}={\pi }_i={\pi }^{\ast }$, the policy has converged.

Warning

Examples

One for constructing MDP, one for Q-states, one for solving using value iteration and one for using policy