How do compute the table for $p(s',r|s,a)$ (exercise 3.5 in Sutton & Barto's book)?

Question

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

Answer 1

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$

Answer 2

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

Answer 3

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 4

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

Answer 5

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.