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