# How to prove that $V^\star$ is optimal if and only if it satisfies the Bellman equation?

## The Question

I'd like to prove that a function $$V$$ (like in reinforcement learning) is optimal iff it satisfies the bellman equation. A lot of places online reference this fact, but none prove it. For formal details, see the following section, with the theorem at the end.

## Formal definitions

In reinforcement learning, a value function $$V$$ is used to derive a policy: $$\pi_{V}\left(a\mid s\right)=\begin{cases} 1 & a=\underset{a'}{\mathrm{argmax}}Q^{\pi_{V}}\left(s,a\right)\\ 0 & otherwise \end{cases}$$ where $$Q^{\pi_{V}}\left(s,a\right)=r\left(s,a\right)+\gamma\underset{s'\sim p\left(s'\mid s,a\right)}{\mathbb{E}}\left[V\left(s'\right)\right]$$ (here $$r$$ is the reward function and $$p$$ is the transition probability from a state to another based on the action)

a policy $$\pi^\star$$ is called optimal if $$\pi^{\star}=\underset{\pi}{\mathrm{argmax}}\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}\cdot r\left(s_{t},a_{t}\right)\mid s_{0}=s\right]$$ where $$s$$ is the initial state, and the expectation is over the transition probability under the assumption of following the policy $$p$$.

We also say that $$V$$ is optimal if $$pi_{V}$$ is optimal.

The Theorem I want to prove is that a function $$V^\star$$ is optimal if and only if it satisfies the Bellman equation:

$$V^{\star}\left(s\right)=\max_{a}r\left(s,a\right)+\gamma\mathbb{E}\left[V^{\star}\left(s'\right)\right]$$

• I'll just give you a few tips. 1. To prove something of the form "A if and only if B", you need to prove 2 things: If A then B AND if B then A. 2. You need to know the definition of an optimal value function. How is an optimal value function different from a non-optimal one? But you also need to know the definition of a value function (in general).
– nbro
Commented Apr 29, 2023 at 18:39
• I believe there is a proof in the David Silver's RL course, or the Sutton & Barto RL book Commented Apr 29, 2023 at 19:20
• Your definition of a policy above is circular, and also you need to first differentiate Bellman equation with its optimality equation version. Commented Apr 29, 2023 at 20:32
• @mohottnad where is the circularity? Commented Apr 30, 2023 at 8:06
• @nbro haven't I defined what an optimal policy is? A non-optimal one is a policy with a smaller reward expectation Commented Apr 30, 2023 at 8:08

A friend of mine showed me the following "post", and the proof is actually quite short.

They prove that $$\lim_{k\to\infty}V_{k}=V^{\star}$$ where $$V_k$$ is defined in the post. Now if the original $$V$$ satisfies the bellman equation already, it means that $$\lim_{k\to\infty}V_{k}=V$$ and therefore $$V^{\star}=V$$. The other direction is of course easy.