<p>A friend of mine showed me the following &quot;<a href="https://yuanz.web.illinois.edu/teaching/IE498fa19/lec_16.pdf" rel="nofollow noreferrer">post</a>&quot;, and the proof is actually quite short.</p>
<p>They prove that <span class="math-container">$$\lim_{k\to\infty}V_{k}=V^{\star}$$</span> where <span class="math-container">$V_k$</span> is defined in the post. Now if the original <span class="math-container">$V$</span> satisfies the bellman equation already, it means that <span class="math-container">$$\lim_{k\to\infty}V_{k}=V$$</span> and therefore <span class="math-container">$V^{\star}=V$</span>. The other direction is of course easy.</p>

CC BY-SA 4.0
2023-05-08T14:43:53.773Z
2023-05-08T14:43:53.773Z
snatchysquid
<h2>The Question</h2>
<hr />
<p>I'd like to prove that a function <span class="math-container">$V$</span> (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.</p>
<h2>Formal definitions</h2>
<hr />
<p>In reinforcement learning, a value function <span class="math-container">$V$</span> is used to derive a policy: <span class="math-container">$$\pi_{V}\left(a\mid s\right)=\begin{cases}
1 &amp; a=\underset{a'}{\mathrm{argmax}}Q^{\pi_{V}}\left(s,a\right)\\
0 &amp; otherwise
\end{cases}$$</span> where <span class="math-container">$$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]$$</span> (here <span class="math-container">$r$</span> is the reward function and <span class="math-container">$p$</span> is the transition probability from a state to another based on the action)</p>
<p>a policy <span class="math-container">$\pi^\star$</span> is called optimal if <span class="math-container">$$\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]$$</span> where <span class="math-container">$s$</span> is the initial state, and the expectation is over the transition probability under the assumption of following the policy <span class="math-container">$p$</span>.</p>
<p>We also say that <span class="math-container">$V$</span> is optimal if <span class="math-container">$pi_{V}$</span> is optimal.</p>
<p><strong>The Theorem</strong> I want to prove is that a function <span class="math-container">$V^\star$</span> is optimal <strong>if and only if</strong> it satisfies the Bellman equation:</p>
<p><span class="math-container">$$V^{\star}\left(s\right)=\max_{a}r\left(s,a\right)+\gamma\mathbb{E}\left[V^{\star}\left(s'\right)\right]$$</span></p>

CC BY-SA 4.0
2023-04-29T18:39:09.427Z
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
CC BY-SA 4.0
2023-04-29T19:20:19.220Z
I believe there is a proof in the David Silver's RL course, or the Sutton & Barto RL book
Luca Anzalone
CC BY-SA 4.0
2023-04-29T20:32:21.490Z
Your definition of a policy above is circular, and also you need to first differentiate Bellman equation with its optimality equation version.
cinch
CC BY-SA 4.0
2023-04-30T08:06:52.657Z
@mohottnad where is the circularity?
snatchysquid
CC BY-SA 4.0
2023-04-30T08:08:03.903Z
@nbro haven't I defined what an optimal policy is? A non-optimal one is a policy with a smaller reward expectation
snatchysquid
<reinforcement-learning><proofs><value-functions><bellman-equations>
How to prove that $V^\star$ is optimal if and only if it satisfies the Bellman equation?
snatchysquid
# How to prove that $V^\star$ is optimal if and only if it satisfies the Bellman equation?

(Asked by: username_0 on 2023-04-29)

## 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]$$

**Tags:** reinforcement-learning, proofs, value-functions, bellman-equations

> **Comments:**
> **username_1**: 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).  
> **username_2**: I believe there is a proof in the David Silver's RL course, or the Sutton & Barto RL book  
> **username_3**: Your definition of a policy above is circular, and also you need to first differentiate Bellman equation with its optimality equation version.  
> **username_0**: @mohottnad where is the circularity?  
> **username_0**: @username_1 haven't I defined what an optimal policy is? A non-optimal one is a policy with a smaller reward expectation  

---

## 1 answers

### Answer by username_0 on 2023-05-08. Score: 0 | Accepted answer

A friend of mine showed me the following "[post](https://yuanz.web.illinois.edu/teaching/IE498fa19/lec_16.pdf)", 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.


---

