Answers.Body: <h3>Bellman Expectation Equations</h3>
  <p>Let's first look at the definition of the value functions.</p>
  <p>The state-value function <span class="math-container">$V^\pi(s_t)$</span> is defined as the expected return <span class="math-container">$G_t=\sum_{t'=t} \gamma^{t-t'} r_{t'}$</span> we get from state <span class="math-container">$s_t$</span>, and then following the policy <span class="math-container">$\pi$</span> until termination:
  <span class="math-container">$$\begin{align} 
  V^\pi(s_t) 
  &amp;= \mathbb{E}_\pi\big[r_t + \gamma r_{t+1} + \gamma^2 r_{t+2}+\cdots\mid s_t\big] \\
  &amp;= \mathbb{E}_\pi\big[G_t\mid s_t\big] \\
  &amp;= \mathbb{E}_\pi\big[r_t + \gamma G_{t+1}\mid s_t] \\
  &amp;= \mathbb{E}_\pi\big[r_t + \gamma V^\pi(s_{t+1})\mid s_t] 
  \end{align}$$</span></p>
  <ul>
  <li>Basically, we get a recursive equation in which <span class="math-container">$V^\pi(s_t)$</span>, at the current time <span class="math-container">$t$</span>, is defined as the immediate reward <span class="math-container">$r_t=r(s_t,a_t)$</span> plus the discounted state-value of the next timestep <span class="math-container">$t+1$</span>.</li>
  </ul>
  <p>Now, the definition of the action-value function, <span class="math-container">$Q^\pi(s_t,a_t)$</span> is similar in that we start from state <span class="math-container">$s$</span>, but take action <span class="math-container">$a$</span>, and then follow <span class="math-container">$\pi$</span>:
  <span class="math-container">$$\begin{align}
  Q^\pi(s_t,a_t) 
  &amp;= \mathbb{E}_\pi\big[G_t\mid s_t,a_t\big] \\
  &amp;= \mathbb{E}_\pi\big[r_t + \gamma Q^\pi(s_{t+1}, a_{t+1})\mid s_t,a_t] \\
  \end{align}$$</span></p>
  <p>Turns out that these two value functions are related, in the sense that one can be written in terms of the other: such relationship is depicted by the <strong>backup diagrams</strong>.</p>
  <p><a href="https://i.sstatic.net/o7UWV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/o7UWV.png" alt="enter image description here" /></a></p>
  <ul>
  <li>For the <span class="math-container">$V$</span>-function, the root of the backup tree is a state <span class="math-container">$s$</span> whose leaves are <em>all</em> the possible actions <span class="math-container">$a\in A$</span>.</li>
  <li>When computing <span class="math-container">$V^\pi(s)$</span> we need to consider all the leaves, i.e. the action-values. This is done by averaging their values and weighting by the probability of that action to occur (thus computing an <em>expectation</em>), which is provided by the policy. So, the diagram on the left provides a first relationship:
  <span class="math-container">$$\begin{align}
  V^\pi(s)
  &amp;=\mathbb{E}_\pi\big[Q^\pi(s,a)\big]\\
  &amp;= \sum_{a\in A}\pi(a\mid s) Q^\pi(s,a)
  \end{align}$$</span></li>
  <li>If we further expand the diagram (right) by executing a given action in the env, we experience a reward <span class="math-container">$r$</span>, landing in a new state <span class="math-container">$s'\in S$</span>. But we still need to reason in &quot;expectation&quot;, this time starting from an action node. Stating that the Q-value can be written in terms of the state-value as follows:
  <span class="math-container">$$\begin{align}
  Q^\pi(s,a)
  &amp;=r(s,a) + \gamma\sum_{s'\in S}p(s'\mid s,a) V^\pi(s')
  \end{align}$$</span></li>
  <li>where <span class="math-container">$p(s'\mid s, a)$</span> is the probability (determined by the environment) of transitioning to next state <span class="math-container">$s'$</span> by tacking action <span class="math-container">$a$</span> in the current state <span class="math-container">$s$</span>.</li>
  </ul>
  <p>A similar diagrams exists for <span class="math-container">$Q$</span>, except that we start from an action. Now we can substitute the new equations to compute both <span class="math-container">$V$</span> and <span class="math-container">$Q$</span> functions:
  <span class="math-container">$$\begin{align}
  V^\pi(s) &amp;= \sum_{a\in A}\pi(a\mid s)\Big(r(s,a) + \gamma\sum_{s'\in S} p(s'\mid s,a) V^\pi(s') \Big)\\
  Q^\pi(s,a)
  &amp;=r(s,a) + \gamma\sum_{s'\in S}p(s'\mid s,a) \sum_{a'\in A}\pi(a'\mid s') Q^\pi(s',a')
  \end{align}$$</span></p>
  <p>The last two equations allow to estimate both value functions in terms of them selves, instead the previous ones in terms of each other. Being able to compute such functions allow to evaluate the goodness of a policy <span class="math-container">$\pi$</span>, know also as <em>policy evaluation</em>.</p>
  <h3>Bellman Optimality Equations</h3>
  <p>The expectation equations can be modified to obtain the optimal value functions: the key idea is to take the <span class="math-container">$\max$</span> instead of the expectations. In general we have:
  <span class="math-container">$$\begin{align}
  V^\star(s) &amp;= \max_\pi V^\pi(s) \\
  Q^\star(s,a) &amp;= \max_\pi Q^\pi(s,a)
  \end{align}$$</span></p>
  <p>Considering the previous relationships between <span class="math-container">$V$</span> and <span class="math-container">$Q$</span>, we can write:
  <span class="math-container">$$\begin{align}
  V^\star(s) 
  &amp;= \max_\pi V^\pi(s) \\
  &amp;= \max_a Q^\star(s,a) \\
  &amp;= \max_a r(s,a) + \gamma \sum_{s'\in S}p(s'\mid s,a) V^\star(s')
  \end{align}$$</span></p>
  <p>In a similar way is possible to rewrite <span class="math-container">$Q^\star$</span> too. In general these formulas are explained by the following backup diagrams:</p>
  <p><a href="https://i.sstatic.net/75K1D.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/75K1D.png" alt="enter image description here" /></a></p>
  <ul>
  <li>This is the optimal backup diagram for <span class="math-container">$V^\star$</span>, a similar one exists for <span class="math-container">$Q^\star$</span>.</li>
  <li>Notice that the <span class="math-container">$\max$</span> is only taken over actions (that replaces <span class="math-container">$\sum_{a\in A}\pi(a\mid s)$</span> in the expectation eq.), and not over states. For the states we still consider an expectation but computed accordingly to the transition probability, i.e. <span class="math-container">$\sum_{s'\in S}p(s'\mid s, a)$</span>.</li>
  </ul>
  <blockquote>
  <p>Is it correct that <span class="math-container">$V^\pi(s)=\max_{a\in A}Q^\pi(s,a)$</span>?</p>
  </blockquote>
  <p>If you're doing policy evaluation no. Because <span class="math-container">$V^\pi(s)$</span> is the value <em>averaged</em> over actions, not the maximum which is useful for policy improvement instead: i.e. to derive the best action that the policy should take in <span class="math-container">$s$</span>, which turns out to improve the current policy and so <span class="math-container">$V^\pi$</span> since it's an action that <em>exploits</em>.</p>
  <p>Reference: David Silver's RL course.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-23T20:44:22.407Z
Answers.LastActivityDate: 2023-05-23T20:44:22.407Z
Answers.UserDisplayName: Luca Anzalone
Answers.Body: <p>There's no way to prove in general for any policy <span class="math-container">$\pi$</span> you always have <span class="math-container">$ V^\pi(s) = \max_{a \in A} Q^\pi(s,a) $</span> since there's no <span class="math-container">$\max$</span> operator on the left hand side and semantically there could exist averaging relationship over actions between them <em>if</em> your <span class="math-container">$\pi$</span> is a stochastic policy, but not <span class="math-container">$\max$</span> relationship.</p>
  <p>For you main concern, here's the steps from your definition of <span class="math-container">$V^*(s), Q^*(s)$</span> and define optimal policy <span class="math-container">$$\pi^* = \arg \max_\pi (\sum_{a\in A}\pi(a | s) Q^\pi(s,a)) $$</span>, then we have:
  <span class="math-container">$$\begin{align}  V^*(s) 
  &amp;= \max_\pi V^\pi(s) \\
   &amp;= \max_\pi (\sum_{a\in A}\pi(a | s) Q^\pi(s,a)) \\
   &amp;= \sum_{a\in A}\pi^*(a | s) Q^{\pi^*}(s,a) \end{align}$$</span></p>
  <p>In case an optimal policy <span class="math-container">$\pi^*$</span> is deterministic, we have <span class="math-container">$\pi^*(a | s) = \begin{cases} 1,  a=a^*(s) \\ 0,  a \neq a^*(s) \end{cases}$</span>, where <span class="math-container">$$a^*(s)=\arg \max_a Q^{\pi^*}(s,a)$$</span>, thus we further have:
  <span class="math-container">$$\begin{align} V^*(s) 
   &amp;= Q^{\pi^*}(s,a^*) \\
   &amp;= \max_{a \in A} Q^{\pi^*}(s,a) \end{align}$$</span></p>
  <p>Finally note if <span class="math-container">$\pi^*$</span> is deterministic, <span class="math-container">$$Q^{\pi^*}(s,a)=\max_\pi Q^\pi (s,a)=Q^*(s,a)$$</span>, so you arrive at <span class="math-container">$$V^*(s) = \max_{a \in A} Q^*(s,a) $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-05-24T23:42:06.277Z
Answers.LastActivityDate: 2023-05-25T00:05:17.933Z
Answers.LastEditDate: 2023-05-25T00:05:17.933Z
Answers.UserDisplayName: cinch
Body: <p>In <a href="https://medium.com/intro-to-artificial-intelligence/relationship-between-state-v-and-action-q-value-function-in-reinforcement-learning-bb9a988c0127" rel="nofollow noreferrer">here</a> it says that: (is it correct?)</p>
  <p><span class="math-container">$$V^\pi = \sum_{a \in A}\pi(a|s)*Q^\pi(s,a)$$</span></p>
  <p>And we have:</p>
  <p><span class="math-container">$$ V^*(s) = max_\pi V^\pi(s)$$</span></p>
  <p>Also:</p>
  <p><span class="math-container">$$ V^*(s) = max_a Q^*(s, a) $$</span></p>
  <p>Can someone demonstrate to me step by step how we got from <span class="math-container">$ V^*(s) = max_\pi V^\pi(s)$</span> to <span class="math-container">$ V^*(s) = max_a Q^*(s, a) $</span> ?</p>
  <p>And is it correct that <span class="math-container">$ V^\pi(s) = max_{a \in A} Q^\pi(s,a) $</span> ?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-31T17:13:50.620Z
Comments.Text: Are you still having conceptual trouble for your two questions?
Comments.UserDisplayName: cinch
Tags: <reinforcement-learning><value-functions><bellman-equations>
Title: How do we get the optimal value-function?
UserDisplayName: Ness
ThreadText: # How do we get the optimal value-function?
  
  (Asked by: username_0 on 2023-05-22)
  
  In [here](https://medium.com/intro-to-artificial-intelligence/relationship-between-state-v-and-action-q-value-function-in-reinforcement-learning-bb9a988c0127) it says that: (is it correct?)
  
  $$V^\pi = \sum\_{a \in A}\pi(a|s)\*Q^\pi(s,a)$$
  
  And we have:
  
  $$ V^\*(s) = max\_\pi V^\pi(s)$$
  
  Also:
  
  $$ V^\*(s) = max\_a Q^\*(s, a) $$
  
  Can someone demonstrate to me step by step how we got from $ V^\*(s) = max\_\pi V^\pi(s)$ to $ V^\*(s) = max\_a Q^\*(s, a) $ ?
  
  And is it correct that $ V^\pi(s) = max\_{a \in A} Q^\pi(s,a) $ ?
  
  **Tags:** reinforcement-learning, value-functions, bellman-equations
  > **Comments:**
  > **username_1**: Are you still having conceptual trouble for your two questions?  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2023-05-23. Score: 1
  
  ### Bellman Expectation Equations
  
  Let's first look at the definition of the value functions.
  
  The state-value function $V^\pi(s\_t)$ is defined as the expected return $G\_t=\sum\_{t'=t} \gamma^{t-t'} r\_{t'}$ we get from state $s\_t$, and then following the policy $\pi$ until termination:
  $$\begin{align}
  V^\pi(s\_t)
  &= \mathbb{E}\_\pi\big[r\_t + \gamma r\_{t+1} + \gamma^2 r\_{t+2}+\cdots\mid s\_t\big] \\
  &= \mathbb{E}\_\pi\big[G\_t\mid s\_t\big] \\
  &= \mathbb{E}\_\pi\big[r\_t + \gamma G\_{t+1}\mid s\_t] \\
  &= \mathbb{E}\_\pi\big[r\_t + \gamma V^\pi(s\_{t+1})\mid s\_t]
  \end{align}$$
  
  * Basically, we get a recursive equation in which $V^\pi(s\_t)$, at the current time $t$, is defined as the immediate reward $r\_t=r(s\_t,a\_t)$ plus the discounted state-value of the next timestep $t+1$.
  
  Now, the definition of the action-value function, $Q^\pi(s\_t,a\_t)$ is similar in that we start from state $s$, but take action $a$, and then follow $\pi$:
  $$\begin{align}
  Q^\pi(s\_t,a\_t)
  &= \mathbb{E}\_\pi\big[G\_t\mid s\_t,a\_t\big] \\
  &= \mathbb{E}\_\pi\big[r\_t + \gamma Q^\pi(s\_{t+1}, a\_{t+1})\mid s\_t,a\_t] \\
  \end{align}$$
  
  Turns out that these two value functions are related, in the sense that one can be written in terms of the other: such relationship is depicted by the **backup diagrams**.
  
  [![enter image description here](https://i.sstatic.net/o7UWV.png)](https://i.sstatic.net/o7UWV.png)
  
  * For the $V$-function, the root of the backup tree is a state $s$ whose leaves are *all* the possible actions $a\in A$.
  * When computing $V^\pi(s)$ we need to consider all the leaves, i.e. the action-values. This is done by averaging their values and weighting by the probability of that action to occur (thus computing an *expectation*), which is provided by the policy. So, the diagram on the left provides a first relationship:
    $$\begin{align}
    V^\pi(s)
    &=\mathbb{E}\_\pi\big[Q^\pi(s,a)\big]\\
    &= \sum\_{a\in A}\pi(a\mid s) Q^\pi(s,a)
    \end{align}$$
  * If we further expand the diagram (right) by executing a given action in the env, we experience a reward $r$, landing in a new state $s'\in S$. But we still need to reason in "expectation", this time starting from an action node. Stating that the Q-value can be written in terms of the state-value as follows:
    $$\begin{align}
    Q^\pi(s,a)
    &=r(s,a) + \gamma\sum\_{s'\in S}p(s'\mid s,a) V^\pi(s')
    \end{align}$$
  * where $p(s'\mid s, a)$ is the probability (determined by the environment) of transitioning to next state $s'$ by tacking action $a$ in the current state $s$.
  
  A similar diagrams exists for $Q$, except that we start from an action. Now we can substitute the new equations to compute both $V$ and $Q$ functions:
  $$\begin{align}
  V^\pi(s) &= \sum\_{a\in A}\pi(a\mid s)\Big(r(s,a) + \gamma\sum\_{s'\in S} p(s'\mid s,a) V^\pi(s') \Big)\\
  Q^\pi(s,a)
  &=r(s,a) + \gamma\sum\_{s'\in S}p(s'\mid s,a) \sum\_{a'\in A}\pi(a'\mid s') Q^\pi(s',a')
  \end{align}$$
  
  The last two equations allow to estimate both value functions in terms of them selves, instead the previous ones in terms of each other. Being able to compute such functions allow to evaluate the goodness of a policy $\pi$, know also as *policy evaluation*.
  
  ### Bellman Optimality Equations
  
  The expectation equations can be modified to obtain the optimal value functions: the key idea is to take the $\max$ instead of the expectations. In general we have:
  $$\begin{align}
  V^\star(s) &= \max\_\pi V^\pi(s) \\
  Q^\star(s,a) &= \max\_\pi Q^\pi(s,a)
  \end{align}$$
  
  Considering the previous relationships between $V$ and $Q$, we can write:
  $$\begin{align}
  V^\star(s)
  &= \max\_\pi V^\pi(s) \\
  &= \max\_a Q^\star(s,a) \\
  &= \max\_a r(s,a) + \gamma \sum\_{s'\in S}p(s'\mid s,a) V^\star(s')
  \end{align}$$
  
  In a similar way is possible to rewrite $Q^\star$ too. In general these formulas are explained by the following backup diagrams:
  
  [![enter image description here](https://i.sstatic.net/75K1D.png)](https://i.sstatic.net/75K1D.png)
  
  * This is the optimal backup diagram for $V^\star$, a similar one exists for $Q^\star$.
  * Notice that the $\max$ is only taken over actions (that replaces $\sum\_{a\in A}\pi(a\mid s)$ in the expectation eq.), and not over states. For the states we still consider an expectation but computed accordingly to the transition probability, i.e. $\sum\_{s'\in S}p(s'\mid s, a)$.
  
  > Is it correct that $V^\pi(s)=\max\_{a\in A}Q^\pi(s,a)$?
  
  If you're doing policy evaluation no. Because $V^\pi(s)$ is the value *averaged* over actions, not the maximum which is useful for policy improvement instead: i.e. to derive the best action that the policy should take in $s$, which turns out to improve the current policy and so $V^\pi$ since it's an action that *exploits*.
  
  Reference: David Silver's RL course.
  
  
  ---
  
  ### Answer by username_1 on 2023-05-24. Score: 0
  
  There's no way to prove in general for any policy $\pi$ you always have $ V^\pi(s) = \max\_{a \in A} Q^\pi(s,a) $ since there's no $\max$ operator on the left hand side and semantically there could exist averaging relationship over actions between them *if* your $\pi$ is a stochastic policy, but not $\max$ relationship.
  
  For you main concern, here's the steps from your definition of $V^\*(s), Q^\*(s)$ and define optimal policy $$\pi^\* = \arg \max\_\pi (\sum\_{a\in A}\pi(a | s) Q^\pi(s,a)) $$, then we have:
  $$\begin{align} V^\*(s)
  &= \max\_\pi V^\pi(s) \\
  &= \max\_\pi (\sum\_{a\in A}\pi(a | s) Q^\pi(s,a)) \\
  &= \sum\_{a\in A}\pi^\*(a | s) Q^{\pi^\*}(s,a) \end{align}$$
  
  In case an optimal policy $\pi^\*$ is deterministic, we have $\pi^\*(a | s) = \begin{cases} 1, a=a^\*(s) \\ 0, a \neq a^\*(s) \end{cases}$, where $$a^\*(s)=\arg \max\_a Q^{\pi^\*}(s,a)$$, thus we further have:
  $$\begin{align} V^\*(s)
  &= Q^{\pi^\*}(s,a^\*) \\
  &= \max\_{a \in A} Q^{\pi^\*}(s,a) \end{align}$$
  
  Finally note if $\pi^\*$ is deterministic, $$Q^{\pi^\*}(s,a)=\max\_\pi Q^\pi (s,a)=Q^\*(s,a)$$, so you arrive at $$V^\*(s) = \max\_{a \in A} Q^\*(s,a) $$
  
  
  ---
  
  