Markov Decision Processes and Bellman Equations, machine learning lesson

A warehouse robot can work or recharge. Working pays more now, but it can drain the battery and make later steps less productive, so the better action depends on where it leads and not only on its immediate reward. A bandit, whose actions never change the situation, cannot describe this. This lesson specifies the problem as a Markov decision process, measures long-run reward by the discounted return, computes the value of a fixed policy from the Bellman expectation equation, and checks that policy against the Bellman optimality equation. The robot and all its numbers are constructed for illustration.

Key terms

Markov decision process

Definition A finite Markov decision process, or MDP, consists of a finite set $\mathcal{S}$ of states, a finite nonempty set $\mathcal{A}(s)$ of actions for each state $s$ , transition probabilities and rewards. At each step $t = 0, 1, 2, \dots$ the agent observes the state $S_t$ and chooses an action $A_t$ in $\mathcal{A}(S_t)$ , and then it receives a reward $R_{t+1}$ and moves to the next state $S_{t+1}$ . The transition probability

\begin{aligned} &p(s' \mid s, a) \\[0.4em] &\quad = P(S_{t+1} = s' \mid \\[0.4em] &\qquad S_t = s, A_t = a) \end{aligned}

is the probability of moving to state $s'$ when action $a$ is taken in state $s$ , the same at every step. For each pair $(s, a)$ these numbers are nonnegative and add to $1$ over $s'$ . On this page the reward of a step is a fixed number $r(s, a)$ that depends only on the current state and action and is received on the transition. More general MDPs let the reward depend on the next state or be random, and then $r(s, a)$ denotes the expected reward. The Markov property is the assumption that, given the current state and action, the next state and reward do not depend on anything earlier. For every history $H_t$ of earlier states, actions and rewards that has positive probability,

\begin{aligned} &P(S_{t+1} = s' \mid S_t = s, \\[0.4em] &\qquad A_t = a,\ H_t) \\[0.4em] &\quad = p(s' \mid s, a), \end{aligned}

and the same holds for the reward.

In plain words An MDP is the complete rulebook of a sequential decision problem. It says what the agent observes, what it can do, what each choice pays and how likely each next state is. Unlike in a bandit, an action changes the next state and with it the rewards available later. The Markov property says that the current state carries everything about the past that matters for what happens next. It is an assumption about the chosen description of the state, not a fact about the world, and a description that leaves out something relevant can break it. The reward also defines the goal. An agent that maximizes reward pursues exactly what the reward measures, which need not include costs, safety or effects on people that the reward leaves out.

Example A constructed warehouse robot has the states charged and low and the actions work and recharge. The table gives the reward and the next-state probabilities for every state and action.

State	Action	Reward	Next state charged	Next state low
charged	work	$5$	$0.5$	$0.5$
charged	recharge	$0$	$1$	$0$
low	work	$1$	$0$	$1$
low	recharge	$-1$	$1$	$0$

The probabilities in each row add to $1$ . The reward $-1$ for recharging from low is a modeled cost, not a measured amount of money. If the chance of running low after work also rose with the number of consecutive work steps, for example through heat, the current state and action would no longer fix the next-state probabilities, and this two-state model would break the Markov property. Adding the missing information, such as a temperature level, to the state could restore it.

Policy

Definition A policy $\pi$ assigns to each state $s$ a probability distribution over the actions in $\mathcal{A}(s)$ . On this page a policy depends only on the current state, so at every step and whatever happened earlier,

\begin{aligned} &P(A_t = a \mid S_t = s) \\[0.4em] &\quad = \pi(a \mid s). \end{aligned}

A deterministic policy puts probability $1$ on one action in each state. Together with the MDP and the distribution of the starting state, a policy fixes the probability of every trajectory $S_0, A_0, R_1, S_1, A_1, R_2, \dots$ . For instance, the first two states and actions are $s_0, a_0, s_1, a_1$ with probability

\begin{aligned} &P(S_0 = s_0)\, \pi(a_0 \mid s_0) \\[0.4em] &\quad \times p(s_1 \mid s_0, a_0) \\[0.4em] &\quad \times \pi(a_1 \mid s_1). \end{aligned}

In plain words A policy is the agent’s decision rule. It decides which actions appear in the data and, through the transitions, which states are visited. Data collected under one policy describe that policy’s trajectories, consecutive steps depend on each other, and actions the policy never takes leave no outcomes at all. A random split of logged steps into training and test rows cannot reveal what another action would have done, or which states a different policy would reach.

Example The policy $\pi_1$ works when charged and recharges when low. Starting charged, one possible trajectory works and drops to low, which has probability $0.5$ , then recharges and returns to charged with probability $1$ , then works again. Its first three rewards are $5$ , $-1$ and $5$ . A stochastic policy might instead recharge from low with probability $0.8$ and work with probability $0.2$ . A policy that always works never produces a recharge step, so its data say nothing about the reward or the transitions of recharging.

Discounted return

Definition For a discount factor $\gamma$ , the return from step $t$ is the next reward plus $\gamma$ times the reward after it, plus $\gamma^2$ times the one after that, and so on,

G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}.

A continuing task, which never ends, assumes bounded rewards, $\lvert R_t \rvert \le R_{\max}$ , and $0 \le \gamma < 1$ . Then the series converges and $\lvert G_t \rvert \le R_{\max}/(1 - \gamma)$ . In an episodic task, which ends when it reaches a terminal state at step $T$ , the sum stops with the reward $R_T$ and all later rewards count as $0$ . There $\gamma = 1$ is also allowed when every episode ends within a bounded number of steps. In both cases the return satisfies, at every step $t$ of a continuing task and every step before the end of an episode,

G_t = R_{t+1} + \gamma G_{t+1},

with $G_T = 0$ at the end of an episode.

In plain words The return adds up all future rewards, each weighted by how far ahead it comes. With $\gamma = 0$ only the next reward counts, and with $\gamma$ close to $1$ distant rewards count almost as much as near ones, so the choice of $\gamma$ is part of the objective. The return is a random variable. One run of the process gives one realized value, and another run from the same state can give a different one. Neither a familiar value of $\gamma$ nor a large total reward shows that the objective captures every real consequence.

Example The robot task never ends, so it uses $\gamma = 0.5$ . Its rewards lie between $-1$ and $5$ , so every return lies between $-2$ and $10$ . Along the trajectory of the policy example, with rewards $5$ , $-1$ and $5$ , the first three terms of the return are $5$ , $0.5 \times (-1) = -0.5$ and $0.25 \times 5 = 1.25$ , and

5 - 0.5 + 1.25 = 5.75 .

This is a partial sum along one realized path. The full return adds $\gamma^3 G_3 = 0.125\, G_3$ , which depends on how the path continues, so it lies between $5.5$ and $7$ .

Value function

Definition For a policy $\pi$ in an MDP with bounded rewards and $0 \le \gamma < 1$ , or in an episodic task as above, the state-value function of $\pi$ is

V^{\pi}(s) = E_{\pi}[G_t \mid S_t = s],

the expected return when the process is in state $s$ and the agent follows $\pi$ from then on. The action-value function

\begin{aligned} &Q^{\pi}(s, a) = E_{\pi}[G_t \mid \\[0.4em] &\qquad S_t = s, A_t = a] \end{aligned}

is the expected return when the agent takes action $a$ in state $s$ and follows $\pi$ afterward. Neither depends on $t$ , because the MDP and the policy are the same at every step. The two are linked by $V^{\pi}(s) = \sum_a \pi(a \mid s)\, Q^{\pi}(s, a)$ , and a terminal state has value $0$ .

In plain words A value is an average over all the paths a policy can produce from a state, weighted by their probabilities, and not the return of one path. Values belong to a policy, so changing the policy changes them. Three kinds of numbers need to be kept apart. A reward is paid on one step, a value is an expected discounted total, and an action probability is part of the policy.

Example The policy that always recharges keeps a charged robot charged with reward $0$ on every step, so its value at charged is $0$ . From low it pays $-1$ once and then $0$ forever, so its value at low is $-1$ . The policy that always works keeps a low robot low with reward $1$ on every step, so with $\gamma = 0.5$ its value at low is

\begin{aligned} &1 + 0.5 + 0.25 + \cdots \\[0.4em] &\quad = \frac{1}{1 - 0.5} = 2 . \end{aligned}

For the always-recharge policy, the action value of working at low is $1 + 0.5 \times (-1) = 0.5$ , since the robot stays low and then follows that policy. It is larger than the policy’s own value $-1$ at low, so a better first action exists there.

Bellman expectation equation

Definition Let $\pi$ be a policy in a finite MDP with $0 \le \gamma < 1$ . For every state $s$ and action $a$ ,

\begin{aligned} &Q^{\pi}(s, a) = r(s, a) \\[0.4em] &\quad + \gamma \sum_{s'} p(s' \mid s, a) \\[0.4em] &\qquad \times V^{\pi}(s'), \end{aligned}

and $V^{\pi}(s) = \sum_a \pi(a \mid s)\, Q^{\pi}(s, a)$ . Substituting the first equation into the second gives one linear equation for each state, the Bellman expectation equation for $V^{\pi}$ . It follows from $G_t = R_{t+1} + \gamma G_{t+1}$ and the Markov property, which make the expected return after a move to $s'$ equal to $V^{\pi}(s')$ . The value function $V^{\pi}$ is the unique solution of this system. It can also be approached by synchronous updates. Starting from any values $V_0$ , each sweep computes $V_{k+1}(s)$ for every state from the right sides of these equations, with the previous values $V_k(s')$ in place of $V^{\pi}(s')$ . The sweeps converge to $V^{\pi}$ , because each one multiplies the largest error over the states by a factor of at most $\gamma$ .

In plain words The value of a state is the expected immediate reward plus the discounted expected value of wherever the policy leads next. The policy is fixed, so the equation averages over its actions with their probabilities and over the next states with their transition probabilities, and nothing is maximized. Solving it requires the transition probabilities and rewards. An exact solution for an inaccurate model describes the model and not the real system, and when only sampled transitions are available the values must be learned from experience, as in temporal-difference learning.

Example Take the policy $\pi_1$ , which works when charged and recharges when low, with $\gamma = 0.5$ , and write $V_C$ and $V_L$ for its values at charged and low. The equations are

\begin{aligned} V_C &= 5 + \tfrac12 \bigl(\tfrac12 V_C + \tfrac12 V_L\bigr), \\[0.4em] V_L &= -1 + \tfrac12 V_C . \end{aligned}

The first averages the two possible next states, and the second has a certain next state. Substituting the second into the first gives $V_C = 4.75 + \tfrac38 V_C$ , so $\tfrac58 V_C = 4.75$ . Hence $V_C = 7.6$ and $V_L = -1 + 3.8 = 2.8$ . Starting instead from the values $(0, 0)$ at (charged, low), the synchronous updates give $(5, -1)$ and then $(6, 1.5)$ , each computed from the previous pair only. Their largest errors $7.6$ , $3.8$ and $1.6$ shrink by at least half at every sweep.

Bellman optimality equation

Definition In a finite MDP with $0 \le \gamma < 1$ , the optimal value function $V^*(s) = \max_{\pi} V^{\pi}(s)$ is the largest value any policy achieves from state $s$ . With

\begin{aligned} &Q^*(s, a) = r(s, a) \\[0.4em] &\quad + \gamma \sum_{s'} p(s' \mid s, a) \\[0.4em] &\qquad \times V^*(s'), \end{aligned}

the Bellman optimality equation states that for every state $s$

V^*(s) = \max_{a} Q^*(s, a),

and $V^*$ is the unique solution of these equations. A policy is optimal, with $V^{\pi} = V^*$ in every state, exactly when in every state it gives all its probability to actions that attain this maximum, so some deterministic policy is optimal. Written for action values alone, the equation reads

\begin{aligned} &Q^*(s, a) = r(s, a) \\[0.4em] &\quad + \gamma \sum_{s'} p(s' \mid s, a) \\[0.4em] &\qquad \times \max_{a'} Q^*(s', a'). \end{aligned}

In plain words The expectation equation averages over the actions of a fixed policy, while the optimality equation takes the best action in each state. An action with a worse immediate reward can still be best if it leads to better states. The maximum runs over the agent’s actions only. The next state is still averaged with its transition probabilities, because the environment decides where the process goes. Optimal means optimal for the stated rewards and discount factor, and a different reward definition can lead to a different optimal policy.

Example At the values $V_C = 7.6$ and $V_L = 2.8$ of $\pi_1$ , the four action values are as follows, where $5.2 = 0.5 \times 7.6 + 0.5 \times 2.8$ is the expected next value after working while charged.

State	Action	Action value
charged	work	$5 + 0.5 \times 5.2 = 7.6$
charged	recharge	$0 + 0.5 \times 7.6 = 3.8$
low	work	$1 + 0.5 \times 2.8 = 2.4$
low	recharge	$-1 + 0.5 \times 7.6 = 2.8$

In each state the largest action value equals the value of $\pi_1$ , so these values satisfy the optimality equation, the optimal values are $7.6$ and $2.8$ , and $\pi_1$ is optimal. At low, recharging pays $-1$ now, less than the $1$ of working, yet it is the better action. The other three deterministic policies agree. Working in both states gives the values $22/3 \approx 7.33$ at charged and $2$ at low, recharging at charged and working at low gives $0$ and $2$ , and recharging in both states gives $0$ and $-1$ , so none beats $\pi_1$ in either state.

Check yourself

An episode gives the rewards $2$ , $0$ and $3$ and then reaches a terminal state. Find its return from the start with $\gamma = 0.8$ . Then explain why the continuing robot task cannot use $\gamma = 1$ with the policy $\pi_1$ .

Show the answer

The episode ends after the third reward, so the sum has three terms,

\begin{aligned} G_0 &= 2 + 0.8 \times 0 \\[0.4em] &\quad + 0.8^2 \times 3 \\[0.4em] &= 3.92 . \end{aligned}

Under $\pi_1$ the robot earns $5$ at every step in charged and $-1$ at every step in low, and every step in low is followed by a step in charged. With $\gamma = 1$ the rewards along every path therefore add up to infinity, and the values are not finite numbers. The Bellman expectation equations $V_C = 5 + \tfrac12 V_C + \tfrac12 V_L$ and $V_L = -1 + V_C$ then have no solution at all, since substituting the second into the first gives $0 = 4.5$ . A task that never ends needs $0 \le \gamma < 1$ .

In some state the policy’s action pays reward $1$ and leads to a state with value $4$ with probability $\tfrac34$ and to a state with value $10$ with probability $\tfrac14$ . With $\gamma = 0.5$ , compute the Bellman expectation backup for this state. A classmate uses the larger next value $10$ , because the Bellman optimality equation takes a maximum. What is wrong?

Show the answer

The expected next value is $0.75 \times 4 + 0.25 \times 10 = 5.5$ , so the backup is

1 + 0.5 \times 5.5 = 3.75 .

The classmate’s value $1 + 0.5 \times 10 = 6$ is wrong in both equations. The environment, not the agent, decides which next state occurs, so both the expectation and the optimality equation average over next states with their transition probabilities. The maximum in the optimality equation runs over the actions available in the current state.

A company logs a year of steps of the robot under the policy that always works, splits the logged steps at random into training and test rows, and wants to estimate the value of $\pi_1$ . What can these data show, and what would be needed?

Show the answer

The policy $\pi_1$ recharges whenever the robot is low, but the logs contain no recharge steps, so they hold no information about the reward or the next state after recharging. No split of the rows can create those outcomes. The logs also reflect the states that always working produces. Working while low keeps the robot low, so after the first few steps nearly every logged step is in low, a distribution that $\pi_1$ would not produce. Consecutive steps of one trajectory are also dependent, so a random split places closely related steps in both parts.

The data can estimate what working does, for example the value of always working, which is $2$ at low. To evaluate $\pi_1$ the data must include recharge actions taken in the low state, for example from a policy that sometimes explores, or the transitions must come from a model whose assumptions are trusted. The best evidence is to run $\pi_1$ itself and measure its returns.

Markov Decision Processes and Bellman Equations

Key terms

Markov decision process

Policy

Discounted return

Value function

Bellman expectation equation

Bellman optimality equation

Check yourself

How this lesson connects

Builds on

Used later in