Bellman Equations | Divin Irakiza

I have been taking an independent reading course on reinforcement learning theory, with Prof Adam Wierman and Yashaswini Murpthy. I have compiled a few notes following Prof R. Srikant's lectures on MDPs and Reinforcement Learning at UIUC.

The Bellman equations solve the policy evaluation problem. Given a policy $\pi$ , how much reward does it collect? We assume finite state, action spaces, and an infinite horizon with discounted rewards.

A Markov Decision Process (MDP) is a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ where

$\mathcal{S}$ : finite set of states
$\mathcal{A}$ : finite set of actions
$P : \mathcal{S} \times \mathcal{A} \to \Delta(\mathcal{S})$ : transition function, $P(s' \mid s, a)$
$R : \mathcal{S} \times \mathcal{A} \to [0, 1]$ : reward for taking action $a$ in state $s$
$\gamma \in [0, 1)$ : discount factor

The objective is the expected discounted total reward $\mathbb{E}\big[\sum_{k=0}^{\infty} \gamma^k R(S_k, A_k)\big]$

A stationary policy, $\pi: \mathcal{S} \to \Delta(\mathcal{A})$ gives a distribution over actions in every state, and we write $a \sim \pi(\cdot \mid s)$ . A deterministic policy is the special case where each $\pi(\cdot \mid s)$ is a point mass, i.e. just a map $\pi : \mathcal{S} \to \mathcal{A}$ .

# Fixing a policy

Uner a fixed stationary policy,

\pi

, the MDP collapses into a Markov Reward Process which is just a DTMC (Discrete Time Markov Chain) with a reward attached to each state. Its transition matrix averages the action-wise transitions over the policy:

\begin{align} P^\pi(s' \mid s) = \mathbb{P}(S_{k+1} = s' \mid S_k = s) &= \mathbb{E}_{A \sim \pi(\cdot \mid s)}\big[P(s' \mid s, A)\big] \\ &= \sum_{a \in \mathcal{A}} \pi(a \mid s)\, P(s' \mid s, a) \end{align}

and its rewards are averaged the same way:

\begin{equation} R^\pi(s) = \mathbb{E}_{A \sim \pi(\cdot \mid s)}\big[R(s, A)\big] = \sum_{a \in \mathcal{A}} \pi(a \mid s)\, R(s, a) \end{equation}

# Value functions

The value function, $V^\pi : \mathcal{S} \to \mathbb{R}$ is the expected discounted reward when we start in $s$ and follow $\pi$ from then on:

\begin{equation} V^\pi(s) = \mathbb{E}\Big[\sum_{k=0}^{\infty} \gamma^k R(S_k, A_k) \;\Big|\; S_0 = s,\ A_k \sim \pi(\cdot \mid S_k)\Big] \end{equation}

Since $R \in [0, 1]$ , each term is at most $\gamma^k$ , so $0 \le V^\pi(s) \le \frac{1}{1 - \gamma}$ and everything is well defined. The terms are also non-negative, so the expectation and the infinite sum can be swapped by Tonelli's theorem, which we do below without comment.

The Q-function, $Q^\pi : \mathcal{S} \times \mathcal{A} \to \mathbb{R}$ is the same quantity, except that we choose the first action ourselves and only follow $\pi$ after that:

\begin{equation} Q^\pi(s, a) = \mathbb{E}\Big[\sum_{k=0}^{\infty} \gamma^k R(S_k, A_k) \;\Big|\; S_0 = s,\ A_0 = a,\ A_k \sim \pi(\cdot \mid S_k) \text{ for } k \ge 1\Big] \end{equation}

Computing $V^\pi$ or $Q^\pi$ for a given $\pi$ is the policy evaluation problem.

# Bellman expectation equations

The value and Q-functions determine each other. $V^\pi$ is $Q^\pi$ with the first action drawn from $\pi$ ,

\begin{align} V^\pi(s) &= \sum_{a \in \mathcal{A}} \pi(a \mid s)\, Q^\pi(s, a) \\ Q^\pi(s, a) &= R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s, a)\, V^\pi(s') \end{align}

$Eq. 7$ holds because of the Markov property and the stationarity of $\pi$ . Once we get to $s'$ , the rest of the trajectory looks exactly like a start from $s'$ , so its expected return is $V^\pi(s')$ . Substituting each identity into the other gives the Bellman expectation equations:

\begin{align} V^\pi(s) &= \sum_{a \in \mathcal{A}} \pi(a \mid s) \Big[R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s, a)\, V^\pi(s')\Big]\\ Q^\pi(s, a) &= R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s, a) \sum_{a' \in \mathcal{A}} \pi(a' \mid s')\, Q^\pi(s', a') \end{align}

Note that the value now is the immediate reward plus the discounted expected value one step later. Observe that $Eq. 8$ is simply:

\begin{align} V^\pi = R^\pi + \gamma P^\pi V^\pi \end{align}