Answers.Body: <p>So, we've got these Bellman equations for optimal <span class="math-container">$V^*$</span> and <span class="math-container">$Q^*$</span>:
  <span class="math-container">$$ V^*(s) = \max_a\left[R(s,a) + \gamma \sum_{s'}T(s',s,a)V^*(s')\right]\qquad (1)$$</span>
  <span class="math-container">$$Q^*(s,a) = R(s,a) + \gamma \sum_{s'}T(s',s,a)\max_{a'}Q^*(s',a')\qquad (2)$$</span>
  Taking <span class="math-container">$\max_a$</span> over <span class="math-container">$(2)$</span>:
  <span class="math-container">$$\max_a Q^*(s,a) = \max_a\left[R(s,a) + \gamma \sum_{s'}T(s',s,a)\max_{a'}Q^*(s',a')\right]$$</span>
  We see that this is equivalent to <span class="math-container">$(1)$</span> if we denote <span class="math-container">$V^*(s) = \max_aQ^*(s,a)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-12-11T18:23:55.307Z
Answers.LastActivityDate: 2022-12-11T18:23:55.307Z
Answers.UserDisplayName: Kostya
Body: <p>In some RL notes, I encountered the following equation, which I am trying to prove:
  <span class="math-container">$$
  V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s, a),\forall s \in S
  $$</span></p>
  <p>Here is my attemption:</p>
  <p>Firstly, I only need to prove &quot;<span class="math-container">$\geq$</span>&quot; as &quot;<span class="math-container">$\leq$</span>&quot; is obvious.</p>
  <p>Suppose that <span class="math-container">$\exists S_0 \subset S$</span> such that <span class="math-container">$\forall s_0 \in S_0,V^{\pi^*}(s_0) &lt; \max_{a \in A}Q^{\pi^*}(s_0, a)$</span>.(W.L.G, soppose there is only single state <span class="math-container">$s_0 \in S_0$</span>), i want to construct a new policy <span class="math-container">$\pi_{\text{new}}$</span> to derive the contradiction to <span class="math-container">$V^{\pi^*}(s) \geq V^{\pi}(s), \forall s \in S$</span> and all policy <span class="math-container">$\pi$</span>.</p>
  <p>I'm trying to create the following policy:</p>
  <p><span class="math-container">$$\pi_{\text{new}}(a\vert s)=\begin{cases}
  1&amp; s=s_0,a=\text{argmax}_{a\in A}Q^{\pi^*}(s_0,a)\\
  0&amp; s=s_0, a\neq \text{argmax}_{a\in A}Q^{\pi^*}(s_0,a) \\
  \pi^*(a\vert s)&amp; s \in S - s_0
  \end{cases}
  $$</span></p>
  <p>Next, I want to show
  <span class="math-container">$$
  V^{\pi_{\text{new}}}(s_0) = \max_{a\in A}Q^{\pi^*}(s_0, a)
  $$</span>
  And thus <span class="math-container">$V^{\pi_{\text{new}}}(s_0) &gt; V^{\pi^*}(s_0)$</span> to get contradiction. But when I derived it, I encountered some trouble as follow:
  <span class="math-container">$$
  V^{\pi_{\text{new}}}(s_0) = \sum_{a \in A}\pi_{\text{new}}(a \vert s_0)Q^{\pi_{\text{new}}}(s_0, a) = Q^{\pi_{\text{new}}}(s_0, \text{argmax}_{a\in A}Q^{\pi^*}(s_0, a)) \overset{?}{=} \max_{a \in A}Q^{\pi^*}(s_0, a)
  $$</span></p>
  <p>I guess the last equation holds, but I can't find a way to prove it. Because the policy changed. Could you please help me?</p>
  
Tags: <reinforcement-learning><proofs><bellman-equations>
Title: Why $V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s,a),\forall s \in S$ in reinforcement learning?
UserDisplayName: vincen
ThreadText: # Why $V^{\pi^*}(s) = \max_{a \in A}Q^{\pi^*}(s,a),\forall s \in S$ in reinforcement learning?
  
  (Asked by: username_0 on 2022-11-05)
  
  In some RL notes, I encountered the following equation, which I am trying to prove:
  $$
  V^{\pi^\*}(s) = \max\_{a \in A}Q^{\pi^\*}(s, a),\forall s \in S
  $$
  
  Here is my attemption:
  
  Firstly, I only need to prove "$\geq$" as "$\leq$" is obvious.
  
  Suppose that $\exists S\_0 \subset S$ such that $\forall s\_0 \in S\_0,V^{\pi^\*}(s\_0) < \max\_{a \in A}Q^{\pi^\*}(s\_0, a)$.(W.L.G, soppose there is only single state $s\_0 \in S\_0$), i want to construct a new policy $\pi\_{\text{new}}$ to derive the contradiction to $V^{\pi^\*}(s) \geq V^{\pi}(s), \forall s \in S$ and all policy $\pi$.
  
  I'm trying to create the following policy:
  
  $$\pi\_{\text{new}}(a\vert s)=\begin{cases}
  1& s=s\_0,a=\text{argmax}\_{a\in A}Q^{\pi^\*}(s\_0,a)\\
  0& s=s\_0, a\neq \text{argmax}\_{a\in A}Q^{\pi^\*}(s\_0,a) \\
  \pi^\*(a\vert s)& s \in S - s\_0
  \end{cases}
  $$
  
  Next, I want to show
  $$
  V^{\pi\_{\text{new}}}(s\_0) = \max\_{a\in A}Q^{\pi^\*}(s\_0, a)
  $$
  And thus $V^{\pi\_{\text{new}}}(s\_0) > V^{\pi^\*}(s\_0)$ to get contradiction. But when I derived it, I encountered some trouble as follow:
  $$
  V^{\pi\_{\text{new}}}(s\_0) = \sum\_{a \in A}\pi\_{\text{new}}(a \vert s\_0)Q^{\pi\_{\text{new}}}(s\_0, a) = Q^{\pi\_{\text{new}}}(s\_0, \text{argmax}\_{a\in A}Q^{\pi^\*}(s\_0, a)) \overset{?}{=} \max\_{a \in A}Q^{\pi^\*}(s\_0, a)
  $$
  
  I guess the last equation holds, but I can't find a way to prove it. Because the policy changed. Could you please help me?
  
  **Tags:** reinforcement-learning, proofs, bellman-equations
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-12-11. Score: 0
  
  So, we've got these Bellman equations for optimal $V^\*$ and $Q^\*$:
  $$ V^\*(s) = \max\_a\left[R(s,a) + \gamma \sum\_{s'}T(s',s,a)V^\*(s')\right]\qquad (1)$$
  $$Q^\*(s,a) = R(s,a) + \gamma \sum\_{s'}T(s',s,a)\max\_{a'}Q^\*(s',a')\qquad (2)$$
  Taking $\max\_a$ over $(2)$:
  $$\max\_a Q^\*(s,a) = \max\_a\left[R(s,a) + \gamma \sum\_{s'}T(s',s,a)\max\_{a'}Q^\*(s',a')\right]$$
  We see that this is equivalent to $(1)$ if we denote $V^\*(s) = \max\_aQ^\*(s,a)$.
  
  
  ---
  
  