In Bellman equations we fixed a policy $\pi$ and evaluated it. Here we look for the best policy. The trick is to view the Bellman equations as fixed points of operators on value functions. We follow the assumptions and notation from the previous note.

# Bellman Optimality Operator

For a state $s$, an action $a$ and any vector $v \in \mathbb{R}^{|\mathcal{S}|}$, define the one-step lookahead

$$\begin{equation} F(s, a, v) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s, a)\, v(s') \end{equation}$$

This can be read as take action $a$ in state $s$, collect the immediate reward, and then pretend that $v$ correctly scores wherever you get to. $F$ depends only on the MDP, not on any policy, and plugging in $v = V^\pi$ gives $F(s, a, V^\pi) = Q^\pi(s, a)$

Averaging the lookahead over a policy gives the Bellman operator $T^\pi$:

$$\begin{equation} (T^\pi v)(s) = \sum_{a \in \mathcal{A}} \pi(a \mid s)\, F(s, a, v), \qquad \text{i.e.} \qquad T^\pi v = R^\pi + \gamma P^\pi v \end{equation}$$

The Bellman expectation equation $Eq. 9$ from the previous note is then just $T^\pi V^\pi = V^\pi$. In other words, $V^\pi$ is a fixed point of $T^\pi$.

Taking the best action instead of the average gives the Bellman optimality operator $T$:

$$\begin{equation} (Tv)(s) = \max_{a \in \mathcal{A}} F(s, a, v) = \max_{a \in \mathcal{A}} \Big[R(s, a) + \gamma \sum_{s' \in \mathcal{S}} P(s' \mid s, a)\, v(s')\Big]. \end{equation}$$

There are three properties of the Bellman operator that we will use to show that it has a unique fixed point. For all $v, w \in \mathbb{R}^{|\mathcal{S}|}$:

Proof of (1). An average of $F(s, a, v)$ over actions can't exceed its max, and it equals the max when all the weight is on maximizing actions.

Proof of (2). $P(s' \mid s, a) \ge 0$, so $v \le w$ gives $F(s, a, v) \le F(s, a, w)$ for every $a$, and taking the max over $a$ preserves the inequality.

Proof of (3). For any two functions of $a$, $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$. Applying it to $F(s, \cdot, v)$ and $F(s, \cdot, w)$:

$$\begin{align} |(Tv)(s) - (Tw)(s)| &\le \max_a |F(s, a, v) - F(s, a, w)| \\ &= \gamma \max_a \Big|\sum_{s'} P(s' \mid s, a)\big(v(s') - w(s')\big)\Big| \\ &\le \gamma\, \|v - w\|_\infty. \end{align}$$

Banach fixed point theorem: an operator $H$ on $\mathbb{R}^d$ with $\|H(x) - H(y)\| \le \beta \|x - y\|$ for some $\beta \lt 1$ has exactly one fixed point $x^*$, and iterating $H$ from any starting point converges to it, with $\|H^k(x_0) - x^*\| \le \beta^k \|x_0 - x^*\|$.

By Banach's fixed point theorem, it follows that $T^\pi$ has exactly one fixed point, which must be $V^\pi$, which we call $V^*$.

The main theorem

Theorem. Let $V^*$ be the unique fixed point of $T$, and let $\pi^*$ be greedy with respect to $V^*$. Then,

So $V^*(s) = \max_\pi V^\pi(s)$ in every state, and $\pi^*$ is optimal. With finitely many actions the argmax is never empty, so there is always a deterministic optimal policy.

Proof of (1). Since $\pi^*$ is greedy: $T^{\pi^*} V^* = TV^* = V^*$. So $V^*$ is a fixed point of $T^{\pi^*}$. But $T^{\pi^*}$ has only one fixed point, $V^{\pi^*}$.

Proof of (2). Take any $\pi$. By domination,

$$\begin{equation} V^\pi = T^\pi V^\pi \le T V^\pi. \end{equation}$$

Now if you apply $T$ to both sides repeatedly. Monotonicity keeps the inequality, so $V^\pi \le TV^\pi \le T^2 V^\pi \le \dots \le T^k V^\pi$. By Banach, $T^k V^\pi \to V^*$, hence $V^\pi \le V^*$.

Note that the max is achieved in every state simultaneously by the same policy, which isn't something that surprises me when I first saw this.

The Bellman Optimality Equations

Consider $Q^*(s, a) = F(s, a, V^*)$ for the Q-function of an optimal policy, so that $V^*(s) = \max_a Q^*(s, a)$. From the fixed point equation $V^* = TV^*$ and its counterpart for $Q^*$ we obtain:

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