# Reinforcement Learning (RL) how to obtain $p(s',r|s,a)$

I am trying to study the book Reinforcement Learning: An Introduction (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.

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...

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$$

• Thank you for your answer, but I must admit that I still do not understand how to solve this exercise. – MrYouMath Oct 21 '18 at 15:47
• @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. – Neil Slater Oct 21 '18 at 16:00
• I will add one row as an example – Neil Slater Oct 21 '18 at 16:00
• @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. – Neil Slater Oct 21 '18 at 16:48
• @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 . . .\}$ – Neil Slater Oct 21 '18 at 17:01

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).

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).

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}$$

• 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). – Neil Slater Jul 29 at 10:32

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 Neil Slater 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{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}$$$$

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.