Answers.Body: <p>The function <span class="math-container">$r(s,a,s')$</span> gives the <em>expected</em> reward in each scenario, but not the distribution of rewards that lead to values <span class="math-container">$r_{search}$</span> and <span class="math-container">$r_{wait}$</span> </p>
  
  <p>The text explains that reward is <span class="math-container">$+1$</span> for each can found, and that different distributions of numbers of cans are expected when waiting as opposed to searching. However, it does not give any description of the actual distributions, just summarises them as the two expected rewards, and suggests <span class="math-container">$r_{search} \gt r_{wait}$</span></p>
  
  <p>You have two main ways to answer the exercise:</p>
  
  <ol>
  <li><p>Invent some parameters for the distributions of <span class="math-container">$r_{search}$</span> and <span class="math-container">$r_{wait}$</span> in order to split up single values of <span class="math-container">$p(s'|s,a)$</span> into multiple values of <span class="math-container">$p(s', r|s,a)$</span>. E.g you could decide that <span class="math-container">$r_{search}$</span> consists of <span class="math-container">$0  \eta_0 + 1  \eta_1 + 2 \eta_2 + 3 \eta_3$</span> where <span class="math-container">$\eta_0, \eta_1, \eta_2, \eta_3$</span> are probabilities that sum to <span class="math-container">$1$</span> - each row that currently has <span class="math-container">$r_{search}$</span> as the output of <span class="math-container">$r(s,a,s')$</span> would then split into 4 rows with reward 0, 1, 2, 3 to complete the new table . . . <span class="math-container">$r_{wait}$</span> would need a different set of parameters.</p></li>
  <li><p>Ignore the details of the distribution, move column <span class="math-container">$r(s,a,s′)$</span> to the left and call it <span class="math-container">$r$</span>, changing <span class="math-container">$p(s|s,a)$</span> to <span class="math-container">$p(s', r|s,a)$</span>. It might be all that's expected given the lack of information.</p></li>
  </ol>
  
  <p>My personal opinion is that the authors want you to think about solution 1 - the only issue is that it requires you to invent some new parameters that were not provided. The ones I name are only a suggestion, they do not represent a specific "correct" answer in terms provided by the book, because the book omits those details.</p>
  
  <p>As an example to start with, if you start solution 1, and use parameters as I have labelled them, you will end up with a first row looking like this:</p>
  
  <p><span class="math-container">$s\qquad \qquad a\qquad  \qquad  s'\qquad  \qquad   r \qquad       p(s', r| s, a)$</span>
  <span class="math-container">$high  \qquad \quad search  \qquad  high  \qquad \quad   0  \qquad   \alpha \eta_0$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-03T10:14:01.567Z
Answers.Text: I think 2. is highly likely.
Answers.UserDisplayName: stoic-santiago
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T13:49:42.323Z
Answers.Text: Hi Neil. For your solution 2, could you please elaborate why would we call $r(s,a,s')$ as $r$? Since for all we know, $r(s,a,s')$ could be a real number (say $3.5$) and hence it would not be in $\mathcal{R}$?
Answers.UserDisplayName: Slim Shady
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T17:07:47.117Z
Answers.Text: @SlimShady: It's not correct notation, but the MDP is underspecified in the question, so it does not seem too important to focus on that.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T15:47:47.220Z
Answers.Text: Thank you for your answer, but I must admit that I still do not understand how to solve this exercise.
Answers.UserDisplayName: MrYouMath
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T16:00:20.713Z
Answers.Text: @MrYouMath: Sorry I don't want to post a fully worked solution online, as it is important to complete the exercises alone to gain understanding, and some university courses will use the book. You can obtain solutions for each chapter (for the non-coding exercises) if you attempt all the exercises in the chapter then email the author with your work.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T16:00:44.537Z
Answers.Text: I will add one row as an example
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T16:39:02.680Z
Answers.Text: I think the authors just want me to set up the linear equation from my edit and then solve them (which I will not do because it is too tedious). This will be a system of 48 linear equation with exactly 48 unknowns. The parameters $\eta_i$ do not make sense to me at the moment.
Answers.UserDisplayName: MrYouMath
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T16:48:40.070Z
Answers.Text: @MrYouMath: No it is not possible to solve that at all because you don't have enough data to write out the simultaneous equations. You don't even know for certain that there are 48 - like the params I suggest you would have to decide what the size of $\mathcal{R}$ is arbitrarily.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T16:49:59.093Z
Answers.Text: I realized that now :D. Why do you think that $|\mathcal{R}|$ is not fixed? I would think that it is $4$.
Answers.UserDisplayName: MrYouMath
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T17:01:25.277Z
Answers.Text: @MrYouMath: I guess you think $\mathcal{R}$ is $\{-3, 0, r_{search}, r_{wait}\}$ then? I explain why that is not the case in this answer. You are confusing *expected* reward values as returned by $r(s,a,s')$ with the possible reward values  in $\mathcal{R}$, which could be $\{-3, 0, 1, 2, 3, 4, 5 . . .\}$
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T17:07:59.100Z
Answers.Text: Now, that is confusing ...
Answers.UserDisplayName: MrYouMath
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-10-21T15:06:07.403Z
Answers.LastActivityDate: 2018-10-21T16:19:46.897Z
Answers.LastEditDate: 2018-10-21T16:19:46.897Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>At first, like Neil Slater says, I thought this could only be solved using the expected rewards instead of actual rewards, or else there wasn't enough information to solve it. But now I think there might be a way to solve this question. Here is my thinking on this problem (I would be curious for anyone's thoughts, as I am working through this book myself).</p>
  
  <p>I think the key part is where the book says:</p>
  
  <blockquote>
    <p>Each can collected by the robot counts as a unit reward, whereas a reward of <span class="math-container">$-3$</span> results whenever the robot has to be rescued.</p>
  </blockquote>
  
  <p>This means that the reward set is actually <span class="math-container">$\mathcal R = \{0, 1, -3\}$</span> (we assume that in each timestep, the robot can only collect one can).</p>
  
  <p>Now using <span class="math-container">$$r(s,a,s') = \sum_r r \frac{p(s',r\mid s,a)}{p(s'\mid s,a)} \tag{3.6}$$</span> and <span class="math-container">$$p(s'\mid s,a) = \sum_r p(s',r\mid s,a)\tag{3.4}$$</span> it seems possible to solve for all the probabilities. I'll do an example for <span class="math-container">$(s,a,s') = (\mathtt{high}, \mathtt{search}, \mathtt{high})$</span> and leave the rest to you (I haven't actually done the rest, since this does seem rather tedious).</p>
  
  <p>Equation 3.6 gives <span class="math-container">$$r_\mathtt{search} = 0\cdot \frac{p(s', 0 \mid s,a)}{\alpha} + 1\cdot \frac{p(s', 1 \mid s,a)}{\alpha} -3\cdot \frac{p(s', -3 \mid s,a)}{\alpha}$$</span> Since <span class="math-container">$p(s', -3 \mid s,a) = 0$</span> (it's impossible for the robot to have to be rescued, since we started in the "high" state), we get <span class="math-container">$p(s', 1 \mid s,a) = \alpha r_\mathtt{search}$</span>.</p>
  
  <p>Now equation 3.4 gives <span class="math-container">$$\alpha = p(s', 0 \mid s,a) + p(s', 1 \mid s,a) + p(s', -3 \mid s,a)$$</span> which solves to <span class="math-container">$p(s', 0 \mid s,a) = \alpha - \alpha r_\mathtt{search}$</span>.</p>
  
  <p>So the first two rows of the table will look like:</p>
  
  <p><span class="math-container">$$\begin{array}{cccc|c}
  s&amp; a &amp; s' &amp; r &amp; p(s',r\mid s,a)\\ \hline
  \mathtt{high} &amp; \mathtt{search} &amp; \mathtt{high} &amp; 1 &amp; \alpha r_\mathtt{search}\\
  \mathtt{high} &amp; \mathtt{search} &amp; \mathtt{high} &amp; 0 &amp; \alpha (1- r_\mathtt{search})
  \end{array}$$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T10:32:15.877Z
Answers.Text: This matches my answer option 1, where your assumption "in each timestep, the robot can only collect one can" sets the distribution behind $r_{search}$ to specific simple distribution ($r_{search}$ is also in that case the probability of finding a single can by searching).
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-01T07:11:09.443Z
Answers.LastActivityDate: 2020-03-01T07:11:09.443Z
Answers.UserDisplayName: IssaRice
Answers.Body: <p>In the announced problem, most of the transitions aren't possible, so most the terms of equations (3.3) and (3.4) from the book will end up being 0.</p>
  
  <p>In my understanding,</p>
  
  <p><span class="math-container">$$
  \begin{align}
  p(s'= high | s = high, a = search) &amp;= \sum_{r \in \{0, -3, r_{search}, r_{wait}\}} p(s'=high, r | s = high, a = search) \\
  &amp;= p(s'=high, r =0 | s = high, a = search) \\
  &amp;+p(s'=high, r = -3 | s = high, a = search) \\
  &amp;+p(s'=high, r = r_{search}| s = high, a = search) \\
  &amp;+p(s'=high, r = r_{wait} | s = high, a = search)
  \end{align}
  $$</span></p>
  
  <p>The problem states that if the agent has high batteries and it chooses to search, then there is no chance that it ends up having a negative reward (<span class="math-container">$r= -3$</span>), thus its transition probability is 0 by definition: <span class="math-container">$p(s'=high, r = -3 | s = high, a = search) = 0$</span>.</p>
  
  <p>Applying the same logic to all other terms, we get,
  <span class="math-container">$$
  \begin{align}
  p(s'= high | s = high, a = search) &amp;= \sum_{r \in \{0, -3, r_{search}, r_{wait}\}} p(s'=high, r | s = high, a = search) \\
  &amp;= p(s'=high, r = r_{search}| s = high, a = search) \\
  &amp;= \alpha
  \end{align}
  $$</span></p>
  
  <p>It looks weird. I not 100% sure that that's the solution, because the question would not make much of sense (the table would've been quite the same).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-16T15:43:55.533Z
Answers.LastActivityDate: 2019-04-16T15:49:36.083Z
Answers.LastEditDate: 2019-04-16T15:49:36.083Z
Answers.UserDisplayName: Gigi
Answers.Body: <blockquote>
    <p>This means that the reward set is actually R={0,1,−3} (we assume that in each timestep, the robot can only collect one can).</p>
  </blockquote>
  
  <p>@riceissa While I agree with the rest of your demonstration, I wouldn't assume that the robot can only collect 0 or 1 can. As Neil Slater suggest, I think the robot could pick any number of cans between 0 and N.</p>
  
  <p>Below is how I solve the problem for the more general case, assuming specific values for <span class="math-container">$s',s, a$</span>. This generalization encompasses @riceissa answer.</p>
  
  <hr>
  
  <p>Let :</p>
  
  <ul>
  <li><span class="math-container">$S_t=s'=\texttt{high}$</span></li>
  <li><span class="math-container">$S_{t-1}=s=\texttt{high}$</span></li>
  <li><span class="math-container">$A_{t-1}=a=\texttt{search}$</span> </li>
  </ul>
  
  <p>We have the following equality : 
  <span class="math-container">$$r_{search}=\sum_{r \in R}r\cdot\frac{p(s', r|s, a)}{p(s'|s, a)}$$</span>
  For these values of <span class="math-container">$s', s, a$</span> we also have:</p>
  
  <ul>
  <li><span class="math-container">$p(s'|s,a)=\alpha$</span>.</li>
  <li><span class="math-container">$p(s', -3|s,a)=0$</span></li>
  </ul>
  
  <p>Writing <span class="math-container">$\eta_r:=p(s',r|s,a)$</span> and for <span class="math-container">$R=\{0, 1, 2, \dots,N\}$</span> (we omit <span class="math-container">$r=-3$</span> since the proba is 0 for this case) we have then:</p>
  
  <p><span class="math-container">\begin{align*} 
  r_{\texttt{search}}&amp;=\sum_{r=0}^N r\cdot\frac{\eta_r}{\alpha}\\
  r_{\texttt{search}}\cdot\alpha&amp;=\sum_{r=0}^N r\cdot\eta_r\\
  r_{\texttt{search}}\cdot\alpha&amp;=i\cdot\eta_i + \sum_{\substack{r=0 \\ r\neq i}}^N r\cdot\eta_r\\
  i\cdot\eta_i&amp;= r_{\texttt{search}}\cdot\alpha- \sum_{\substack{r=0 \\ r\neq i}}^N r\cdot\eta_r
  \end{align*}</span></p>
  
  <p>For <span class="math-container">$i\neq 0$</span> : </p>
  
  <p><span class="math-container">$$\eta_i= \frac{1}{i}\cdot\left(r_{\texttt{search}}\cdot\alpha- \sum_{\substack{r=0 \\ r\neq i}}^N r\cdot\eta_r\right)$$</span></p>
  
  <p>For <span class="math-container">$i=0$</span>, we use that fact that 
  <span class="math-container">\begin{align*}
  \alpha&amp;=p(s'|s,a)=\sum_{r=0}^N p(s',r|s,a)=\sum_{r=0}^N\eta_r\\
  &amp;\Rightarrow\eta_0=\alpha - \sum_{r&gt;0} \eta_r
  \end{align*}</span></p>
  
  <p>So substituting <span class="math-container">$\eta_r$</span> by its probability formula we end up having, for these specific values of <span class="math-container">$s', s, a$</span> : </p>
  
  <p><span class="math-container">\begin{equation}
      \begin{cases}
        p(s',i|s,a)= \frac{1}{i}\cdot\left(r_{\texttt{search}}\cdot\alpha- \sum_{\substack{r=0 \\ r\neq i}}^N r\cdot p(s',r|s,a)\right) &amp; \texttt{$\forall i \in [1,N]$}\\
        p(s',0|s,a)=\alpha -\sum_{r&gt;0} p(s',r|s,a) &amp; \texttt{if $i=0$}
      \end{cases}    
  \end{equation}</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-26T13:10:16.807Z
Answers.Text: it doesn't make sense for $i=0$. Could you clarify how you got the "$\Rightarrow \eta_0=\alpha-\sum_{r>0}\eta_r$" part?
Answers.UserDisplayName: Slim Shady
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-04T22:00:35.907Z
Answers.LastActivityDate: 2020-06-05T15:30:41.970Z
Answers.LastEditDate: 2020-06-05T15:30:41.970Z
Answers.UserDisplayName: Etienne Kintzler
Answers.Body: <p>My understanding is that it will be the same as p(s' | s, a) for any s, a, s', r combination.</p>
  <p>The reward r(s, a, s') is already defined in terms of s, a, s'.</p>
  <p>Since p(s', r| s, a) = p(r|s', a, s)* p(s'| a, s). For each case the p(r | s', a, s) is equal to 1 by definition. Thus, the column for p(s', r| a, s) = p(s'| s, a)</p>
  <p>For instance,</p>
  <p>If,
  S= high, A=search and S'=High, then the reward is always alpha.</p>
  <p>p(r=alpha| s=high, a = search , s'=high) = 1 (you always get that reward for this case) etc.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-29T03:33:49.027Z
Answers.LastActivityDate: 2020-07-29T03:33:49.027Z
Answers.UserDisplayName: prwl_nght
Body: <p>I am trying to study the book <a href="http://incompleteideas.net/book/bookdraft2018jan1.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a> (Sutton &amp; Barto, 2018). In chapter 3.1 the authors state the following exercise</p>
  <blockquote>
  <p><em>Exercise 3.5</em> Give a table analogous to that in Example 3.3, but for <span class="math-container">$p(s',r|s,a)$</span>. It should have columns for <span class="math-container">$s$</span>, <span class="math-container">$a$</span>, <span class="math-container">$s'$</span>, <span class="math-container">$r$</span>, and <span class="math-container">$p(s',r|s,a)$</span>, and a row for every 4-tupel for which <span class="math-container">$p(s',r|s,a)&gt;0$</span>.</p>
  </blockquote>
  <p>The following table and graphical representation of the Markov Decision Process is given on the next page.</p>
  <p><a href="https://i.sstatic.net/5xt43.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5xt43.png" alt="Example 3.3" /></a></p>
  <p>I tried to use <span class="math-container">$p(s'\cup r|s,a)=p(s'|s,a)+p(r|s,a)-p(s' \cap r|s,a)$</span> but without a significant progress because I think this formula does not make any sense as <span class="math-container">$s'$</span> and <span class="math-container">$r$</span> are not from the same set. How is this exercise supposed to be solved?</p>
  <h3>Edit</h3>
  <p>Maybe this exercise intends to be solved by using</p>
  <p><span class="math-container">$$p(s'|s,a)=\sum_{r\in \mathcal{R}}p(s',r|s,a)$$</span></p>
  <p>and</p>
  <p><span class="math-container">$$r(s,a,s')=\sum_{r\in \mathcal{R}}r\dfrac{p(s',r|s,a)}{p(s|s,a)}$$</span></p>
  <p>and</p>
  <p><span class="math-container">$$\sum_{s'\in\mathcal{S}}\sum_{r\in\mathcal{R}}p(s',r|s,a)=1$$</span></p>
  <p>the resulting system is a linear system of 30 equation with 48 unknowns. I think I am missing some equations...</p>
  
Tags: <reinforcement-learning><sutton-barto><probability-theory><transition-model>
Title: How do compute the table for $p(s',r|s,a)$ (exercise 3.5 in Sutton & Barto's book)?
UserDisplayName: MrYouMath
ThreadText: # How do compute the table for $p(s',r|s,a)$ (exercise 3.5 in Sutton & Barto's book)?
  
  (Asked by: username_0 on 2018-10-21)
  
  I am trying to study the book [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/bookdraft2018jan1.pdf) (Sutton & Barto, 2018). In chapter 3.1 the authors state the following exercise
  
  > *Exercise 3.5* Give a table analogous to that in Example 3.3, but for $p(s',r|s,a)$. It should have columns for $s$, $a$, $s'$, $r$, and $p(s',r|s,a)$, and a row for every 4-tupel for which $p(s',r|s,a)>0$.
  
  The following table and graphical representation of the Markov Decision Process is given on the next page.
  
  [![Example 3.3](https://i.sstatic.net/5xt43.png)](https://i.sstatic.net/5xt43.png)
  
  I tried to use $p(s'\cup r|s,a)=p(s'|s,a)+p(r|s,a)-p(s' \cap r|s,a)$ but without a significant progress because I think this formula does not make any sense as $s'$ and $r$ are not from the same set. How is this exercise supposed to be solved?
  
  ### Edit
  
  Maybe this exercise intends to be solved by using
  
  $$p(s'|s,a)=\sum\_{r\in \mathcal{R}}p(s',r|s,a)$$
  
  and
  
  $$r(s,a,s')=\sum\_{r\in \mathcal{R}}r\dfrac{p(s',r|s,a)}{p(s|s,a)}$$
  
  and
  
  $$\sum\_{s'\in\mathcal{S}}\sum\_{r\in\mathcal{R}}p(s',r|s,a)=1$$
  
  the resulting system is a linear system of 30 equation with 48 unknowns. I think I am missing some equations...
  
  **Tags:** reinforcement-learning, sutton-barto, probability-theory, transition-model
  
  
  ---
  
  ## 5 answers
  
  ### Answer by username_1 on 2018-10-21. Score: 3
  
  The function $r(s,a,s')$ gives the *expected* reward in each scenario, but not the distribution of rewards that lead to values $r\_{search}$ and $r\_{wait}$
  
  The text explains that reward is $+1$ for each can found, and that different distributions of numbers of cans are expected when waiting as opposed to searching. However, it does not give any description of the actual distributions, just summarises them as the two expected rewards, and suggests $r\_{search} \gt r\_{wait}$
  
  You have two main ways to answer the exercise:
  
  1. Invent some parameters for the distributions of $r\_{search}$ and $r\_{wait}$ in order to split up single values of $p(s'|s,a)$ into multiple values of $p(s', r|s,a)$. E.g you could decide that $r\_{search}$ consists of $0 \eta\_0 + 1 \eta\_1 + 2 \eta\_2 + 3 \eta\_3$ where $\eta\_0, \eta\_1, \eta\_2, \eta\_3$ are probabilities that sum to $1$ - each row that currently has $r\_{search}$ as the output of $r(s,a,s')$ would then split into 4 rows with reward 0, 1, 2, 3 to complete the new table . . . $r\_{wait}$ would need a different set of parameters.
  2. Ignore the details of the distribution, move column $r(s,a,s′)$ to the left and call it $r$, changing $p(s|s,a)$ to $p(s', r|s,a)$. It might be all that's expected given the lack of information.
  
  My personal opinion is that the authors want you to think about solution 1 - the only issue is that it requires you to invent some new parameters that were not provided. The ones I name are only a suggestion, they do not represent a specific "correct" answer in terms provided by the book, because the book omits those details.
  
  As an example to start with, if you start solution 1, and use parameters as I have labelled them, you will end up with a first row looking like this:
  
  $s\qquad \qquad a\qquad \qquad s'\qquad \qquad r \qquad p(s', r| s, a)$
  $high \qquad \quad search \qquad high \qquad \quad 0 \qquad \alpha \eta\_0$
  
  > **Comments:**
  > **username_0**: Thank you for your answer, but I must admit that I still do not understand how to solve this exercise.  
  > **username_1**: @username_0: Sorry I don't want to post a fully worked solution online, as it is important to complete the exercises alone to gain understanding, and some university courses will use the book. You can obtain solutions for each chapter (for the non-coding exercises) if you attempt all the exercises in the chapter then email the author with your work.  
  > **username_1**: I will add one row as an example  
  > **username_0**: I think the authors just want me to set up the linear equation from my edit and then solve them (which I will not do because it is too tedious). This will be a system of 48 linear equation with exactly 48 unknowns. The parameters $\eta_i$ do not make sense to me at the moment.  
  > **username_1**: @username_0: No it is not possible to solve that at all because you don't have enough data to write out the simultaneous equations. You don't even know for certain that there are 48 - like the params I suggest you would have to decide what the size of $\mathcal{R}$ is arbitrarily.  
  > **username_0**: I realized that now :D. Why do you think that $|\mathcal{R}|$ is not fixed? I would think that it is $4$.  
  > **username_1**: @username_0: I guess you think $\mathcal{R}$ is $\{-3, 0, r_{search}, r_{wait}\}$ then? I explain why that is not the case in this answer. You are confusing *expected* reward values as returned by $r(s,a,s')$ with the possible reward values  in $\mathcal{R}$, which could be $\{-3, 0, 1, 2, 3, 4, 5 . . .\}$  
  > **username_0**: Now, that is confusing ...  
  > **username_2**: I think 2. is highly likely.  
  > **username_3**: Hi username_1. For your solution 2, could you please elaborate why would we call $r(s,a,s')$ as $r$? Since for all we know, $r(s,a,s')$ could be a real number (say $3.5$) and hence it would not be in $\mathcal{R}$?  
  > **username_1**: @username_3: It's not correct notation, but the MDP is underspecified in the question, so it does not seem too important to focus on that.  
  
  ---
  
  ### Answer by username_4 on 2020-03-01. Score: 2
  
  At first, like username_1 username_1 says, I thought this could only be solved using the expected rewards instead of actual rewards, or else there wasn't enough information to solve it. But now I think there might be a way to solve this question. Here is my thinking on this problem (I would be curious for anyone's thoughts, as I am working through this book myself).
  
  I think the key part is where the book says:
  
  > Each can collected by the robot counts as a unit reward, whereas a reward of $-3$ results whenever the robot has to be rescued.
  
  This means that the reward set is actually $\mathcal R = \{0, 1, -3\}$ (we assume that in each timestep, the robot can only collect one can).
  
  Now using $$r(s,a,s') = \sum\_r r \frac{p(s',r\mid s,a)}{p(s'\mid s,a)} \tag{3.6}$$ and $$p(s'\mid s,a) = \sum\_r p(s',r\mid s,a)\tag{3.4}$$ it seems possible to solve for all the probabilities. I'll do an example for $(s,a,s') = (\mathtt{high}, \mathtt{search}, \mathtt{high})$ and leave the rest to you (I haven't actually done the rest, since this does seem rather tedious).
  
  Equation 3.6 gives $$r\_\mathtt{search} = 0\cdot \frac{p(s', 0 \mid s,a)}{\alpha} + 1\cdot \frac{p(s', 1 \mid s,a)}{\alpha} -3\cdot \frac{p(s', -3 \mid s,a)}{\alpha}$$ Since $p(s', -3 \mid s,a) = 0$ (it's impossible for the robot to have to be rescued, since we started in the "high" state), we get $p(s', 1 \mid s,a) = \alpha r\_\mathtt{search}$.
  
  Now equation 3.4 gives $$\alpha = p(s', 0 \mid s,a) + p(s', 1 \mid s,a) + p(s', -3 \mid s,a)$$ which solves to $p(s', 0 \mid s,a) = \alpha - \alpha r\_\mathtt{search}$.
  
  So the first two rows of the table will look like:
  
  $$\begin{array}{cccc|c}
  s& a & s' & r & p(s',r\mid s,a)\\ \hline
  \mathtt{high} & \mathtt{search} & \mathtt{high} & 1 & \alpha r\_\mathtt{search}\\
  \mathtt{high} & \mathtt{search} & \mathtt{high} & 0 & \alpha (1- r\_\mathtt{search})
  \end{array}$$
  
  > **Comments:**
  > **username_1**: This matches my answer option 1, where your assumption "in each timestep, the robot can only collect one can" sets the distribution behind $r_{search}$ to specific simple distribution ($r_{search}$ is also in that case the probability of finding a single can by searching).  
  
  ---
  
  ### Answer by username_5 on 2019-04-16. Score: 1
  
  In the announced problem, most of the transitions aren't possible, so most the terms of equations (3.3) and (3.4) from the book will end up being 0.
  
  In my understanding,
  
  $$
  \begin{align}
  p(s'= high | s = high, a = search) &= \sum\_{r \in \{0, -3, r\_{search}, r\_{wait}\}} p(s'=high, r | s = high, a = search) \\
  &= p(s'=high, r =0 | s = high, a = search) \\
  &+p(s'=high, r = -3 | s = high, a = search) \\
  &+p(s'=high, r = r\_{search}| s = high, a = search) \\
  &+p(s'=high, r = r\_{wait} | s = high, a = search)
  \end{align}
  $$
  
  The problem states that if the agent has high batteries and it chooses to search, then there is no chance that it ends up having a negative reward ($r= -3$), thus its transition probability is 0 by definition: $p(s'=high, r = -3 | s = high, a = search) = 0$.
  
  Applying the same logic to all other terms, we get,
  $$
  \begin{align}
  p(s'= high | s = high, a = search) &= \sum\_{r \in \{0, -3, r\_{search}, r\_{wait}\}} p(s'=high, r | s = high, a = search) \\
  &= p(s'=high, r = r\_{search}| s = high, a = search) \\
  &= \alpha
  \end{align}
  $$
  
  It looks weird. I not 100% sure that that's the solution, because the question would not make much of sense (the table would've been quite the same).
  
  
  ---
  
  ### Answer by username_6 on 2020-06-04. Score: 1
  
  > This means that the reward set is actually R={0,1,−3} (we assume that in each timestep, the robot can only collect one can).
  
  @riceissa While I agree with the rest of your demonstration, I wouldn't assume that the robot can only collect 0 or 1 can. As username_1 username_1 suggest, I think the robot could pick any number of cans between 0 and N.
  
  Below is how I solve the problem for the more general case, assuming specific values for $s',s, a$. This generalization encompasses @riceissa answer.
  
  ---
  
  Let :
  
  * $S\_t=s'=\texttt{high}$
  * $S\_{t-1}=s=\texttt{high}$
  * $A\_{t-1}=a=\texttt{search}$
  
  We have the following equality :
  $$r\_{search}=\sum\_{r \in R}r\cdot\frac{p(s', r|s, a)}{p(s'|s, a)}$$
  For these values of $s', s, a$ we also have:
  
  * $p(s'|s,a)=\alpha$.
  * $p(s', -3|s,a)=0$
  
  Writing $\eta\_r:=p(s',r|s,a)$ and for $R=\{0, 1, 2, \dots,N\}$ (we omit $r=-3$ since the proba is 0 for this case) we have then:
  
  \begin{align\*}
  r\_{\texttt{search}}&=\sum\_{r=0}^N r\cdot\frac{\eta\_r}{\alpha}\\
  r\_{\texttt{search}}\cdot\alpha&=\sum\_{r=0}^N r\cdot\eta\_r\\
  r\_{\texttt{search}}\cdot\alpha&=i\cdot\eta\_i + \sum\_{\substack{r=0 \\ r\neq i}}^N r\cdot\eta\_r\\
  i\cdot\eta\_i&= r\_{\texttt{search}}\cdot\alpha- \sum\_{\substack{r=0 \\ r\neq i}}^N r\cdot\eta\_r
  \end{align\*}
  
  For $i\neq 0$ :
  
  $$\eta\_i= \frac{1}{i}\cdot\left(r\_{\texttt{search}}\cdot\alpha- \sum\_{\substack{r=0 \\ r\neq i}}^N r\cdot\eta\_r\right)$$
  
  For $i=0$, we use that fact that
  \begin{align\*}
  \alpha&=p(s'|s,a)=\sum\_{r=0}^N p(s',r|s,a)=\sum\_{r=0}^N\eta\_r\\
  &\Rightarrow\eta\_0=\alpha - \sum\_{r>0} \eta\_r
  \end{align\*}
  
  So substituting $\eta\_r$ by its probability formula we end up having, for these specific values of $s', s, a$ :
  
  \begin{equation}
  \begin{cases}
  p(s',i|s,a)= \frac{1}{i}\cdot\left(r\_{\texttt{search}}\cdot\alpha- \sum\_{\substack{r=0 \\ r\neq i}}^N r\cdot p(s',r|s,a)\right) & \texttt{$\forall i \in [1,N]$}\\
  p(s',0|s,a)=\alpha -\sum\_{r>0} p(s',r|s,a) & \texttt{if $i=0$}
  \end{cases}
  \end{equation}
  
  > **Comments:**
  > **username_3**: it doesn't make sense for $i=0$. Could you clarify how you got the "$\Rightarrow \eta_0=\alpha-\sum_{r>0}\eta_r$" part?  
  
  ---
  
  ### Answer by username_7 on 2020-07-29. Score: 0
  
  My understanding is that it will be the same as p(s' | s, a) for any s, a, s', r combination.
  
  The reward r(s, a, s') is already defined in terms of s, a, s'.
  
  Since p(s', r| s, a) = p(r|s', a, s)\* p(s'| a, s). For each case the p(r | s', a, s) is equal to 1 by definition. Thus, the column for p(s', r| a, s) = p(s'| s, a)
  
  For instance,
  
  If,
  S= high, A=search and S'=High, then the reward is always alpha.
  
  p(r=alpha| s=high, a = search , s'=high) = 1 (you always get that reward for this case) etc.
  
  
  ---
  
  