Answers.Body: <p>A quick review of resolving expectations: If you know that a discrete random variable <span class="math-container">$X$</span>, drawn from set <span class="math-container">$\mathcal{X}$</span> has probability distribution <span class="math-container">$p(x) = \mathbf{Pr}\{X=x \}$</span>, then</p>
  <p><span class="math-container">$$\mathbb{E}[X] = \sum_{x \in \mathcal{X}} xp(x)$$</span></p>
  <p>This equation is the core of what is going on when resolving the expectation in your quoted equation.</p>
  <p>Resolving the expectation to show how the value function of a state relates to the possible next rewards and future states means summing up all possible rewards and next states. There are two components to the distribution over the single step involved - the policy <span class="math-container">$\pi(a|s)$</span>, and the state progression <span class="math-container">$P^a_{ss'}$</span>. As they are both independent probabilities, they need to be multiplied to establish the <em>combined</em> probability of any specific trajectory.</p>
  <p>So, looking at only a single trajectory starting from state <span class="math-container">$s$</span>, the trajectory of selecting action <span class="math-container">$a$</span> and ending up in state <span class="math-container">$s'$</span> has a probability of:</p>
  <p><span class="math-container">$$p_{\pi}(a,s'|s) = \pi(a|s) P^a_{ss'}$$</span></p>
  <p>Iterating over <em>all possible</em> trajectories to get the expected value of some function of the end of the trajectory <span class="math-container">$f(s,a,s')$</span> looks like this:</p>
  <p><span class="math-container">$$\mathbb{E}[f(S_t, A_t, S_{t+1})|S_t=s] = \sum_a \pi(a|s)\sum_{s'}P_{ss'}^a f(s,a,s')$$</span></p>
  <p>It is important to note that the sums are <em>nested</em> here, not separately resolved then multiplied. This is standard notation, but you could add some brackets to show it:</p>
  <p><span class="math-container">$$\mathbb{E}[f(S_t, A_t, S_{t+1})|S_t=s] = \sum_a \pi(a|s)\left(\sum_{s'}\left(P_{ss'}^a f(s,a,s')\right)\right)$$</span></p>
  <p>In the equation from the book, <span class="math-container">$f(s,a,s') = R_{ss'}^a + \gamma v_{\pi}(s')$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-10T09:00:00.590Z
Answers.LastActivityDate: 2021-05-10T09:54:06.287Z
Answers.LastEditDate: 2021-05-10T09:54:06.287Z
Answers.UserDisplayName: Neil Slater
Body: <p>The state-value function for a given policy <span class="math-container">$\pi$</span> is given by</p>
  <p><span class="math-container">$$\begin{align} 
  V^{\pi}(s) &amp;=E_{\pi}\left\{r_{t+1}+\gamma r_{t+2}+\gamma^{2} r_{t+3}+\cdots \mid s_{t}=s\right\} \\ 
  &amp;=E_{\pi}\left\{r_{t+1}+\gamma V^{\pi}\left(s_{t+1}\right) \mid s_{t}=s\right\} \tag{4.3}\label{4.3} \\ 
  &amp;=\sum_{a} \pi(s, a) \sum_{s^{\prime}} \mathcal{P}_{s s^{\prime}}^{a}\left[\mathcal{R}_{s s^{\prime}}^{a}+\gamma V^{\pi}\left(s^{\prime}\right)\right] \tag{4.4}\label{4.4}
  \end{align}$$</span></p>
  <p>It is given in section 4.1 of the first edition of Sutton and Barto's book <a href="http://incompleteideas.net/book/ebook/node41.html" rel="nofollow noreferrer">(equations 4.3 and 4.4)</a>.</p>
  <p>I don't understand how equation \ref{4.4} derives from equation \ref{4.3}. How can I get the product in equation \ref{4.4} from the expectation in equation \ref{4.3}?</p>
  
Tags: <reinforcement-learning><math><value-functions><books><expectation>
Title: How is the state-value function expressed as a product of sums?
UserDisplayName: hanugm
ThreadText: # How is the state-value function expressed as a product of sums?
  
  (Asked by: username_0 on 2021-05-10)
  
  The state-value function for a given policy $\pi$ is given by
  
  $$\begin{align}
  V^{\pi}(s) &=E\_{\pi}\left\{r\_{t+1}+\gamma r\_{t+2}+\gamma^{2} r\_{t+3}+\cdots \mid s\_{t}=s\right\} \\
  &=E\_{\pi}\left\{r\_{t+1}+\gamma V^{\pi}\left(s\_{t+1}\right) \mid s\_{t}=s\right\} \tag{4.3}\label{4.3} \\
  &=\sum\_{a} \pi(s, a) \sum\_{s^{\prime}} \mathcal{P}\_{s s^{\prime}}^{a}\left[\mathcal{R}\_{s s^{\prime}}^{a}+\gamma V^{\pi}\left(s^{\prime}\right)\right] \tag{4.4}\label{4.4}
  \end{align}$$
  
  It is given in section 4.1 of the first edition of Sutton and Barto's book [(equations 4.3 and 4.4)](http://incompleteideas.net/book/ebook/node41.html).
  
  I don't understand how equation \ref{4.4} derives from equation \ref{4.3}. How can I get the product in equation \ref{4.4} from the expectation in equation \ref{4.3}?
  
  **Tags:** reinforcement-learning, math, value-functions, books, expectation
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-05-10. Score: 3 | Accepted answer
  
  A quick review of resolving expectations: If you know that a discrete random variable $X$, drawn from set $\mathcal{X}$ has probability distribution $p(x) = \mathbf{Pr}\{X=x \}$, then
  
  $$\mathbb{E}[X] = \sum\_{x \in \mathcal{X}} xp(x)$$
  
  This equation is the core of what is going on when resolving the expectation in your quoted equation.
  
  Resolving the expectation to show how the value function of a state relates to the possible next rewards and future states means summing up all possible rewards and next states. There are two components to the distribution over the single step involved - the policy $\pi(a|s)$, and the state progression $P^a\_{ss'}$. As they are both independent probabilities, they need to be multiplied to establish the *combined* probability of any specific trajectory.
  
  So, looking at only a single trajectory starting from state $s$, the trajectory of selecting action $a$ and ending up in state $s'$ has a probability of:
  
  $$p\_{\pi}(a,s'|s) = \pi(a|s) P^a\_{ss'}$$
  
  Iterating over *all possible* trajectories to get the expected value of some function of the end of the trajectory $f(s,a,s')$ looks like this:
  
  $$\mathbb{E}[f(S\_t, A\_t, S\_{t+1})|S\_t=s] = \sum\_a \pi(a|s)\sum\_{s'}P\_{ss'}^a f(s,a,s')$$
  
  It is important to note that the sums are *nested* here, not separately resolved then multiplied. This is standard notation, but you could add some brackets to show it:
  
  $$\mathbb{E}[f(S\_t, A\_t, S\_{t+1})|S\_t=s] = \sum\_a \pi(a|s)\left(\sum\_{s'}\left(P\_{ss'}^a f(s,a,s')\right)\right)$$
  
  In the equation from the book, $f(s,a,s') = R\_{ss'}^a + \gamma v\_{\pi}(s')$
  
  
  ---
  
  