Answers.Body: <blockquote>
  <p>My guess is that <span class="math-container">$r(s,a)$</span> is the constant so it can be moved out of the summation, leaving <span class="math-container">$r(s,a)\sum_{s'}P^{a}_{ss'} = r(s,a)$</span></p>
  </blockquote>
  <p>Yes, this is the case. More specifically:</p>
  <ul>
  <li><span class="math-container">$r(s,a)$</span> is the <em>expected</em> reward after taking action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>.</li>
  <li>Reward may depend on the state arrived in, <span class="math-container">$s'$</span>, but that is ignored in the equations.</li>
  <li>Reward may vary randomly, but by using the <em>expected</em> reward, this can be ignored.</li>
  </ul>
  <p>The first equations you quote, which sum over <span class="math-container">$s'$</span> but use <span class="math-container">$r(s,a)$</span> inside that sum, are very misleading IMO, since the individual terms may not represent anything meaningful within the MDP. That is the term <span class="math-container">$r(s,a) + \gamma V^*(s')$</span> does not correspond to any part of the trajectory of the agent.</p>
  <p>Although the sum is still mathematically sound, it is more normal to see a different term <span class="math-container">$r(s,a,s')$</span> (the expected reward similar to <span class="math-container">$r(s,a)$</span> but also conditional on <span class="math-container">$s'$</span>) where the expected reward is used inside the sum of next states. The term <span class="math-container">$r(s,a,s') + \gamma V^*(s')$</span> <strong>does</strong> correspond to nodes on the trajectory of the agent. It is the expected future return from <span class="math-container">$s,a$</span> conditional on the state transitioning to <span class="math-container">$s'$</span>.</p>
  <blockquote>
  <p>but is it always the case that <span class="math-container">$r(s,a)$</span> is independent of <span class="math-container">$s'$</span>. I think the reward  of moving from state <span class="math-container">$s$</span> to <span class="math-container">$s'$</span> may vary.</p>
  </blockquote>
  <p>Yes <span class="math-container">$r(s,a)$</span> is independent of <span class="math-container">$s'$</span>. Although individual rewards may vary stochastically, and may depend on <span class="math-container">$s'$</span> too, the term is already the <em>expected</em> reward when taking the action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>. So it already includes any effects of random state transition and random reward. For the Bellman equations to work as written, the expectation needs to be independent of the policy <span class="math-container">$\pi$</span> thus a property of the environment, and this is the case.</p>
  <p>I think both sets of equations are a little bit awkward from using a combination of expected reward, yet summing up expectations over the state transition matrix. I prefer the notation used in second edition of <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">Sutton &amp; Barto's Reinforcement Learning: An Introduction</a>:</p>
  <p><span class="math-container">$$v^*(s) = \text{max}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma v^*(s'))$$</span></p>
  <p>Where <span class="math-container">$p(r, s'|s,a)$</span> is the conditional probability of observing reward <span class="math-container">$r$</span> and next state <span class="math-container">$s'$</span> given initial state <span class="math-container">$s$</span> and action <span class="math-container">$a$</span>. The <span class="math-container">$p(r, s'|s,a)$</span> function replaces the combination of state transition matrices <span class="math-container">$P_{ss'}^a$</span> and the expected reward (either <span class="math-container">$r(s,a)$</span> or <span class="math-container">$r(s,a,s')$</span>). Those objects can be derived from <span class="math-container">$p(r,s'|a,s)$</span> if you want, but personally I find the newer notation easier to follow.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-09-10T07:11:10.433Z
Answers.LastActivityDate: 2021-09-10T09:59:59.533Z
Answers.LastEditDate: 2021-09-10T09:59:59.533Z
Answers.UserDisplayName: Neil Slater
Body: <p>I saw two versions of the optimality equation for <span class="math-container">$V_{*}(s)$</span> and <span class="math-container">$Q_{*}(s,a)$</span>.</p>
  <p>The <strong>first one</strong> is:</p>
  <p><span class="math-container">$$
  V_{*}(s)=\max _{a} \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left(r(s, a)+\gamma V_{*}\left(s^{\prime}\right)\right)
  $$</span></p>
  <p>and</p>
  <p><span class="math-container">$$
  Q_{*}(s, a)=\sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left(r(s, a)+\gamma \max _{a^{\prime}} Q_{*}\left(s^{\prime}, a^{\prime}\right)\right)
  $$</span></p>
  <p>The <strong>second one</strong> is:</p>
  <p><span class="math-container">$$
  V_{*}(s)=\max _{a \in \mathcal{A}}\left(R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P_{s s^{\prime}}^{a} V_{*}\left(s^{\prime}\right)\right)
  $$</span></p>
  <p>and for <span class="math-container">$Q_*$</span></p>
  <p><span class="math-container">$$
  Q_{*}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in \mathcal{S}} P_{s s^{\prime}}^{a} \max _{a^{\prime} \in \mathcal{A}} Q_{*}\left(s^{\prime}, a^{\prime}\right)
  $$</span></p>
  <p>If following distributive property to get from the first to the second expression. Why there is no summation term for the reward, for example, <span class="math-container">$$V_{*}(s) = \max_{a}(\sum_{s'}P^{a}_{ss'}r(s,a)+\gamma\sum_{s'}P^{a}_{ss'}V_{*}(s'))$$</span>?</p>
  <p>My guess is that <span class="math-container">$r(s,a)$</span> is the constant so it can be moved out of the summation, leaving <span class="math-container">$$r(s,a)\sum_{s'}P^{a}_{ss'} = r(s,a).$$</span></p>
  <p>But is it always the case that <span class="math-container">$r(s,a)$</span> is independent of <span class="math-container">$s'$</span>? I think the reward of moving from state <span class="math-container">$s$</span> to <span class="math-container">$s'$</span> may vary.</p>
  
Tags: <reinforcement-learning><reward-functions><bellman-equations><dynamic-programming>
Title: How are these two versions of the Bellman optimality equation related?
UserDisplayName: Kronic
ThreadText: # How are these two versions of the Bellman optimality equation related?
  
  (Asked by: username_0 on 2021-09-10)
  
  I saw two versions of the optimality equation for $V\_{\*}(s)$ and $Q\_{\*}(s,a)$.
  
  The **first one** is:
  
  $$
  V\_{\*}(s)=\max \_{a} \sum\_{s^{\prime}} P\_{s s^{\prime}}^{a}\left(r(s, a)+\gamma V\_{\*}\left(s^{\prime}\right)\right)
  $$
  
  and
  
  $$
  Q\_{\*}(s, a)=\sum\_{s^{\prime}} P\_{s s^{\prime}}^{a}\left(r(s, a)+\gamma \max \_{a^{\prime}} Q\_{\*}\left(s^{\prime}, a^{\prime}\right)\right)
  $$
  
  The **second one** is:
  
  $$
  V\_{\*}(s)=\max \_{a \in \mathcal{A}}\left(R(s, a)+\gamma \sum\_{s^{\prime} \in \mathcal{S}} P\_{s s^{\prime}}^{a} V\_{\*}\left(s^{\prime}\right)\right)
  $$
  
  and for $Q\_\*$
  
  $$
  Q\_{\*}(s, a)=R(s, a)+\gamma \sum\_{s^{\prime} \in \mathcal{S}} P\_{s s^{\prime}}^{a} \max \_{a^{\prime} \in \mathcal{A}} Q\_{\*}\left(s^{\prime}, a^{\prime}\right)
  $$
  
  If following distributive property to get from the first to the second expression. Why there is no summation term for the reward, for example, $$V\_{\*}(s) = \max\_{a}(\sum\_{s'}P^{a}\_{ss'}r(s,a)+\gamma\sum\_{s'}P^{a}\_{ss'}V\_{\*}(s'))$$?
  
  My guess is that $r(s,a)$ is the constant so it can be moved out of the summation, leaving $$r(s,a)\sum\_{s'}P^{a}\_{ss'} = r(s,a).$$
  
  But is it always the case that $r(s,a)$ is independent of $s'$? I think the reward of moving from state $s$ to $s'$ may vary.
  
  **Tags:** reinforcement-learning, reward-functions, bellman-equations, dynamic-programming
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-09-10. Score: 1
  
  > My guess is that $r(s,a)$ is the constant so it can be moved out of the summation, leaving $r(s,a)\sum\_{s'}P^{a}\_{ss'} = r(s,a)$
  
  Yes, this is the case. More specifically:
  
  * $r(s,a)$ is the *expected* reward after taking action $a$ in state $s$.
  * Reward may depend on the state arrived in, $s'$, but that is ignored in the equations.
  * Reward may vary randomly, but by using the *expected* reward, this can be ignored.
  
  The first equations you quote, which sum over $s'$ but use $r(s,a)$ inside that sum, are very misleading IMO, since the individual terms may not represent anything meaningful within the MDP. That is the term $r(s,a) + \gamma V^\*(s')$ does not correspond to any part of the trajectory of the agent.
  
  Although the sum is still mathematically sound, it is more normal to see a different term $r(s,a,s')$ (the expected reward similar to $r(s,a)$ but also conditional on $s'$) where the expected reward is used inside the sum of next states. The term $r(s,a,s') + \gamma V^\*(s')$ **does** correspond to nodes on the trajectory of the agent. It is the expected future return from $s,a$ conditional on the state transitioning to $s'$.
  
  > but is it always the case that $r(s,a)$ is independent of $s'$. I think the reward of moving from state $s$ to $s'$ may vary.
  
  Yes $r(s,a)$ is independent of $s'$. Although individual rewards may vary stochastically, and may depend on $s'$ too, the term is already the *expected* reward when taking the action $a$ in state $s$. So it already includes any effects of random state transition and random reward. For the Bellman equations to work as written, the expectation needs to be independent of the policy $\pi$ thus a property of the environment, and this is the case.
  
  I think both sets of equations are a little bit awkward from using a combination of expected reward, yet summing up expectations over the state transition matrix. I prefer the notation used in second edition of [Sutton & Barto's Reinforcement Learning: An Introduction](http://incompleteideas.net/book/the-book.html):
  
  $$v^\*(s) = \text{max}\_a \sum\_{r,s'} p(r,s'|s,a)(r + \gamma v^\*(s'))$$
  
  Where $p(r, s'|s,a)$ is the conditional probability of observing reward $r$ and next state $s'$ given initial state $s$ and action $a$. The $p(r, s'|s,a)$ function replaces the combination of state transition matrices $P\_{ss'}^a$ and the expected reward (either $r(s,a)$ or $r(s,a,s')$). Those objects can be derived from $p(r,s'|a,s)$ if you want, but personally I find the newer notation easier to follow.
  
  
  ---
  
  