Proving a function satisfying Bellman's equation is optimal

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.

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^{V}\left(s,a\right)\\ 0 & \text{otherwise} \end{cases}$$ where $$Q^{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]$$

• The proof is too long to be given here: I suggest reading up on Reinforcement Learning by Sutton and Barto. Long story short, the bellman operator $B(F)\mathbb{E}[R(s, a) + \gamma F]$ ($F \in R^n$)forms a contraction mapping on the Banach space of $(R^n, ||.||_{\inf})$, which has the fixed point stated in your question. Commented May 7, 2023 at 22:10
• @cybershiptrooper could you perhaps point me to an existing proof? I tried looking at RL by Sutton and Barto, but I didn't find a proof there, only "explanations" Commented May 8, 2023 at 4:17
• drive.google.com/file/d/1X2a5HTZ1uVz66PAz_o2S6ItkAKROAIMO/… Commented May 8, 2023 at 5:52
• drive.google.com/file/d/13RsweuRjplu7bm0sRoJMOpldy4HN4skP/view Commented May 8, 2023 at 5:52

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.
• why they proved the limit obtained by applying the bellman optimal operator is $V_{*}$ the optimal value function? Commented Sep 24, 2023 at 3:50
• Sorry. In the post you mentioned, it is stated that $\lim{\cal T^*}^k V = V_{*}$, but actually they didn't show any proof of this fact. What I mean is that the banach theorem states that this limit converges, but why it converges to $V_{*}$? Commented Sep 24, 2023 at 15:33
• @piero they did prove that - Theorem 4 (which relies on previous theorems). [Note that $V_{k}$ is defined to be the result of repeatedly applying $\mathcal{T}$] Commented Sep 24, 2023 at 15:52
• it says "note that $V_{*}$ is a fixed point of $\cal T$", tha is my concern, because it was not proven. Also, I see that they $\textbf{assumed}$ $V_{*}$ satisfies the bellman optimality equation before, in this case it will obviously be a fixed point, but as I am saying it is not proved. Commented Sep 24, 2023 at 16:01