Answers.Body: <p>You are missing that the expression </p>
  
  <p><span class="math-container">$$\sum_{s'} \eta(s')$$</span></p>
  
  <p>is already a count of the expected length of an episode, and is used in the denominator to scale <span class="math-container">$\mu(s)$</span> such that <span class="math-container">$\sum_{s} \mu(s) = 1$</span></p>
  
  <p>So the length of the episode <em>is</em> taken into account in the formula.</p>
  
  <p>In practice you don't need to know <span class="math-container">$\mu(s)$</span>, 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 <span class="math-container">$\eta(s)$</span> or <span class="math-container">$\mu(s)$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T23:07:23.877Z
Answers.Text: Ah, yes, thanks. I was reading $\eta$ to be a stationary distribution, not the average number of time steps in the state.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T10:29:32.290Z
Answers.LastActivityDate: 2019-11-19T10:29:32.290Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>Let's first assume that there is only one action so that <span class="math-container">$\pi(a|s) = 1$</span> 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 <span class="math-container">$s_0$</span> with <span class="math-container">$h(s_0) = 1$</span>. The result would be
  <span class="math-container">\begin{align}
  \eta(s_0) &amp;= 1 + \sum_{i = 0}^9 \eta(s_i) \cdot p(s_0|s_i) =\\
  &amp;= 1 + \sum_{i = 0}^9 10 \cdot \frac{1}{10} = 11
  \end{align}</span>
  Now let's consider a case with 1000 time steps where other settings are the same as in the first case.
  <span class="math-container">\begin{align}
  \eta(s_0) &amp;= 1 + \sum_{i = 0}^{9} \eta(s_i) \cdot p(s_0|s_i) =\\
  &amp;= 1 + \sum_{i = 0}^{9} 100 \cdot \frac{1}{10} = 101
  \end{align}</span>
  In the first case
  <span class="math-container">\begin{equation}
  \mu(s_0) = \frac{11}{9\cdot 10 + 11} = 0.1089
  \end{equation}</span>
  and in the second case you have
  <span class="math-container">\begin{equation}
  \mu(s_0) = \frac{101}{9\cdot 100 + 101} = 0.1009
  \end{equation}</span>
  so it looks like you are correct that <span class="math-container">$\mu(s)$</span> 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 <span class="math-container">$h(s_i)$</span> 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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T23:06:03.243Z
Answers.Text: 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.
Answers.UserDisplayName: user118967
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-19T06:21:29.397Z
Answers.LastActivityDate: 2019-11-19T06:21:29.397Z
Answers.UserDisplayName: Brale
Body: <p>In <a href="http://incompleteideas.net/book/the-book-2nd.html" rel="nofollow noreferrer">Sutton &amp; Barto's "Reinforcement Learning: An Introduction", 2nd edition</a>, page 199, they describe the on-policy distribution for episodic tasks in the following box:</p>
  
  <p><a href="https://i.sstatic.net/lf1Q3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lf1Q3.png" alt="enter image description here"></a></p>
  
  <p>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 <span class="math-container">$1 + 100\times 1/10$</span>; if it has <span class="math-container">$1000$</span> time steps, it will be proportional to <span class="math-container">$1 + 1000\times 1/10$</span>. However, the formula given would make it proportional to <span class="math-container">$1 + 1/10$</span> in both cases. What am I missing?</p>
  
Tags: <reinforcement-learning><sutton-barto><episodic-tasks><on-policy-distribution>
Title: In the on-policy state distribution for episodic tasks, why don't we take into account the length of the episode?
UserDisplayName: user118967
ThreadText: # In the on-policy state distribution for episodic tasks, why don't we take into account the length of the episode?
  
  (Asked by: username_0 on 2019-11-19)
  
  In [Sutton & Barto's "Reinforcement Learning: An Introduction", 2nd edition](http://incompleteideas.net/book/the-book-2nd.html), page 199, they describe the on-policy distribution for episodic tasks in the following box:
  
  [![enter image description here](https://i.sstatic.net/lf1Q3.png)](https://i.sstatic.net/lf1Q3.png)
  
  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?
  
  **Tags:** reinforcement-learning, sutton-barto, episodic-tasks, on-policy-distribution
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2019-11-19. Score: 3 | Accepted answer
  
  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.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  ### Answer by username_1 on 2019-11-19. Score: 2
  
  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)$
  
  > **Comments:**
  > **username_0**: Ah, yes, thanks. I was reading $\eta$ to be a stationary distribution, not the average number of time steps in the state.  
  
  ---
  
  