4
$\begingroup$

in Sutton's book Reinforcement Learning: An Introduction Chapter 9, how to drive the formula for "The on-policy distribution in episodic tasks" as flow? enter image description here

that h(s) denotes the probability that an episode begins in each state s, and let η(s) denote the number of time steps spent, on average, in state s in a single episode. Time is spent in a state s if episodes start in s, or if transitions are made into s from a preceding state ¯s in which time is spent:

$\endgroup$

3 Answers 3

3
$\begingroup$

Yeah I couldn't see that in one step either. How about this:

$$ \begin{align} \eta(s) &= \mathbb{E}\left[\sum_{t=0}^{\infty}\mathbf{1}(S_{t}=s)\right]\\ &= \sum_{t=0}^{\infty}\mathbb{P}\left(S_{t}=s\right)\\ &= \mathbb{P}(S_{0}=s)+\sum_{t=1}^{\infty}\mathbb{P}\left(S_{t}=s\right)\\ &= h(s)+\sum_{t=1}^{\infty}\sum_{s'}p(s|s')\mathbb{P}\left(S_{t-1}=s'\right)\\ &= h(s)+\sum_{s'}p(s|s')\sum_{t=1}^{\infty}\mathbb{P}\left(S_{t-1}=s'\right)\\ &= h(s)+\sum_{s'}p(s|s')\eta(s')\\ &= h(s)+\sum_{s',a}\eta(s')\pi(a\mid s')p(s|s',a) \end{align} $$

$\endgroup$
1
$\begingroup$

it sort of follows from the definitions of an MDP. The equation simply says that the number of visits to a state $s$ is the sum of the probability of starting in state $s$ and the probability of moving to state $s$ from state $\hat{s}$.

$p(s|\hat{s},a)$ denotes the probability of moving into state $s$ conditional on being in state $\hat{s}$ and performing action $a$. It is essentially a model of the environment where the next state ($s$) can be predicted from the current state ($\hat{s}$) and the currently performed action which is determined by the policy ($\pi(a|\hat{s})$), which determines from the the probability of performing action $a$ given in state $\hat{s}$.

$\endgroup$
0
$\begingroup$

my understanding of this is:

$$ \eta(s) = \text{expected number of times you start the episode in s} + \text{expected number of times that states transition into s} $$

i think the first term, $h(s)$, is a bit confusing, since it's actually implies that you will spend at 1 time step in $s$. So this term is actually an expected value, rather than just the probability.

Following this understanding, the derivation for this equation becomes much more natural. The second term is simply calculating the expected value using the state transitional probability, $p(s | \bar{s}, a)$, and the policy probability,$ \pi(a | \bar{s}) $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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