1
$\begingroup$

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.

Example 3.3

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

$\endgroup$
3
$\begingroup$

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$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.