3
$\begingroup$

In Sutton & Barto's "Reinforcement Learning: An Introduction", 2nd edition, page 199, they describe the on-policy distribution for episodic tasks in the following box:

enter image description here

I don't understand how this can be done without taking the length of the episode into account. Suppose a task has 10 states, has probability 1 of starting at the first state, then moves to any state uniformly until the episode terminates. If the episode has 100 time steps, then probability of the first state is proportional to $1 + 100\times 1/10$; if it has $1000$ time steps, it will be proportional to $1 + 1000\times 1/10$. However, the formula given would make it proportional to $1 + 1/10$ in both cases. What am I missing?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Let's first assume that there is only one action so that $\pi(a|s) = 1$ for every state - action pair which simplifies the discussion. Now let's consider a case with 100 time steps, 10 states and uniform distribution for starting state $s_0$ with $h(s_0) = 1$. The result would be \begin{align} \eta(s_0) &= 1 + \sum_{i = 0}^9 \eta(s_i) \cdot p(s_0|s_i) =\\ &= 1 + \sum_{i = 0}^9 10 \cdot \frac{1}{10} = 11 \end{align} Now let's consider a case with 1000 time steps where other settings are the same as in the first case. \begin{align} \eta(s_0) &= 1 + \sum_{i = 0}^{9} \eta(s_i) \cdot p(s_0|s_i) =\\ &= 1 + \sum_{i = 0}^{9} 100 \cdot \frac{1}{10} = 101 \end{align} In the first case \begin{equation} \mu(s_0) = \frac{11}{9\cdot 10 + 11} = 0.1089 \end{equation} and in the second case you have \begin{equation} \mu(s_0) = \frac{101}{9\cdot 100 + 101} = 0.1009 \end{equation} so it looks like you are correct that $\mu(s)$ depends on the length of the episode, but they didn't really say that it doesn't. Obviously as the length of the episode increases so will the number of times a certain state was visited so you could say that formula implicitly depends on the number of time steps. If $h(s_i)$ is equal for every state then results would be the same in both cases regardless of number of time steps. Also, as the number of possible states grows very large, as it usually is in real problems, the results would be approaching each other as the number of states grows.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks. I just misread $\eta$ to be a stationary probability distribution and opposed to the average number of times steps at the state. So, really it is the stationary distribution times the episode size, and of course that makes sense. $\endgroup$
    – user118967
    Nov 19, 2019 at 23:06
2
$\begingroup$

You are missing that the expression

$$\sum_{s'} \eta(s')$$

is already a count of the expected length of an episode, and is used in the denominator to scale $\mu(s)$ such that $\sum_{s} \mu(s) = 1$

So the length of the episode is taken into account in the formula.

In practice you don't need to know $\mu(s)$, it can be left unresolved as a theoretical construct. What you care about for the theory to work is that the samples that you train with are drawn with same frequency - this happens automatically if you work with an on-policy algorithm. So the theory can hide the maths that you might need to do in order to determine actual values for $\eta(s)$ or $\mu(s)$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah, yes, thanks. I was reading $\eta$ to be a stationary distribution, not the average number of time steps in the state. $\endgroup$
    – user118967
    Nov 19, 2019 at 23:07

You must log in to answer this question.

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