2
$\begingroup$

I am reading the book titled "Reinforcement Learning: An Introduction" (by Sutton and Barto). I am at chapter 5, which is about Monte Carlo methods, but now I am quite confused.

There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?

I understood that one of the main benefits of MC over Dynamic Programming (DP) is that one does not need to have a model of the state-transition probability for a system. Or is this only the case for on-policy MC?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?

It is not needed for calculation. It must be included in the theory, to compare the correct probability of each trajectory (on-policy vs off-policy). However, the state transition probabilities are then also shown to cancel out exactly, so there is no requirement to know what the values are.

State transition probabilities are irrelevant to probability ratios between identical trajectories where the policy varies but the environment does not. Which is the case for off-policy learning.

This is all explained on the relevant pages of the book, but replicating here for completeness. If your trajectory is from steps $m$ to $n$ and called $\tau = (s_m, a_m, r_{m+1}, s_{m+1}, a_{m+1}, r_{m+2} . . . r_{n}, s_n)$, then the probability of seeing that trajectory under two different policies $\pi(a|s)$ and $b(a|s)$ is:

$$p(\tau|\pi) = (\prod_{i=m}^{n-1} \pi(a_i|s_i))(\prod_{j=m+1}^{n} p(s_j, r_j|s_{j-1},a_{j-1}))$$

$$p(\tau|b) = (\prod_{i=m}^{n-1} b(a_i|s_i))(\prod_{j=m+1}^{n} p(s_j, r_j|s_{j-1},a_{j-1}))$$

You can clearly see that the second product in both cases is the same, and cancels out in the ratio:

$$\frac{p(\tau|\pi)}{p(\tau|b)} =\frac{\prod_{i=m}^{n-1} \pi(a_i|s_i)}{\prod_{i=m}^{n-1} b(a_i|s_i)}$$

So it doesn't matter what $p(s', r|s, a)$ actually is, just that it exists and is not allowed to change in theory between the on-policy and off-policy cases. Or in other words, that the environment is a consistent MDP.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you Neil. You are write, I should have continued reading (although i am going through this chapter already several times) But concerning the requirement for this being the case (both stp canceling each other out) This is true for stationary MDPs? So for any dynamic environment where this changes over time, the learned policy (assuming it was perfect at the end of training) might degenerate over time? $\endgroup$
    – Manuel Pasieka
    Nov 16, 2018 at 14:21
  • $\begingroup$ @ManuelPasieka: Yes if the MDP changes the values may be incorrect later on (when you try to use the target policy). However, that would also have at least some affects on most learning algorithms. If non-stationarity of the environment is a real concern in a problem you are looking at, then you need to be careful applying most RL techniques. $\endgroup$
    – Neil Slater
    Nov 16, 2018 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .