Answers.Body: <p><strong>Update: I rewrote the first part due to major mistake in the first version</strong></p>
  
  <p>Notice: The notation <span class="math-container">$P^k$</span> from Eq.<span class="math-container">$(20)$</span> and <span class="math-container">$(21)$</span> in the paper does not mean the kth power of some <span class="math-container">$P$</span>. Instead, <span class="math-container">$P^k$</span> should be thought as the <span class="math-container">$k$</span> step transition probability of a non-homogeneous Markov chain. </p>
  
  <ol>
  <li>According to the CPO paper, the discounted future state distribution is defined as
  <span class="math-container">$$
  d_\pi(s)=(1-\gamma)\sum_{k=0}^\infty \gamma^kProb(s_k=s|\pi,s_0)\mu(s_0)\tag{1}
  $$</span>
  Consider function form. Let <span class="math-container">$Prob_{\pi,k}$</span> denote the <span class="math-container">$k$</span> step probability transition operator induced by <span class="math-container">$\pi$</span>; here <span class="math-container">$\pi$</span> can be a hierarchical policy, <span class="math-container">$k$</span> can be larger than <span class="math-container">$c$</span>. 
  <span class="math-container">$$
  d_\pi=(1-\gamma)\sum_{k=0}^\infty \gamma^kProb_{\pi,k}\mu\tag{2}
  $$</span>
  Now apply the similar definition as Eq.<span class="math-container">$(20)$</span> and <span class="math-container">$(21)$</span> in the paper, let <span class="math-container">$P^k_\pi$</span> denote the <span class="math-container">$k$</span> step transition probability of the non-homogeneous Markov chain induced by the low level policy, with <span class="math-container">$k$</span> smaller or equal to <span class="math-container">$c$</span>. 
  <span class="math-container">\begin{align}
  d_\pi&amp;=(1-\gamma)\sum_{m=0}^\infty\gamma^{mc}\sum_{k=0}^{c-1}\gamma^kP^k_\pi(P^c_\pi)^m\mu\\
  &amp;=(1-\gamma)\sum_{k=0}^{c-1}\gamma^kP^k_\pi(\sum_{m=0}^\infty\gamma^{mc}(P^c_\pi)^m)\mu\\
  &amp;=(1-\gamma)A_\pi(I-\gamma^cP^c)^{-1}\mu\tag{3}
  \end{align}</span>
  which is exactly the form of Eq.<span class="math-container">$(22)$</span> and <span class="math-container">$(23)$</span> in the paper, with <span class="math-container">$A_\pi$</span> defined similar as Eq.<span class="math-container">$(24)$</span> and <span class="math-container">$(25)$</span>.</li>
  <li>The "every-<span class="math-container">$c$</span>-step discounted state frequency" builds on <span class="math-container">$(3)$</span>, but it lumps the <span class="math-container">$c$</span> steps into one "high level" step where the discount factor is <span class="math-container">$\gamma^c$</span> and the transition operator is <span class="math-container">$P_\pi^c$</span>. Starting with <span class="math-container">$(3)$</span>, replace <span class="math-container">$c$</span> with 1, we get the "every one step future state distribution"
  <span class="math-container">$$
  d_\pi=(1-\gamma)(I-\gamma P_\pi)^{-1}\mu\tag{4}
  $$</span>
  Then replace <span class="math-container">$\gamma$</span> and <span class="math-container">$P_\pi$</span> in <span class="math-container">$(4)$</span> with <span class="math-container">$\gamma^c$</span> and <span class="math-container">$P_\pi^c$</span>, we get the "every-<span class="math-container">$c$</span>-step discounted state frequency", or "every-<span class="math-container">$c$</span>-step future state distribution"
  <span class="math-container">$$
  d_\pi^c=(1-\gamma^c)(I-\gamma^c P_\pi^c)^{-1}\mu\tag{5}
  $$</span>
  By the way, I read your blogpost on this paper. It's very helpful for me, thank you!</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-02T03:48:29.087Z
Answers.Text: Thanks for answering, your second explanation is great:-). But I'm sorry that I cannot follow your first reasoning exactly. Would you mind explaining how you compute the normalizing term $(1-\gamma^cP_\pi^c)^{-1}$? Furthermore, I'm confused about "the meaning of $(4)$ is the same as $(1)$". Do you suggest state distribution in c steps is the same as that in infinite steps? BTW, I'm glad my blog helps:)
Answers.UserDisplayName: Maybe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-02T22:22:13.730Z
Answers.Text: For the derivation of the normalizing term, please see my updated answer. As for my comment "the meaning of $(4)$ is the same as $(1)$", I mean intuitively they roughly refer to the same concept and play the same role as in expressing the discounted value function. But I agree, this comment is misleading, so I deleted it... Hope this update is helpful...
Answers.UserDisplayName: Zhiyu Zhang
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-03T05:09:46.840Z
Answers.Text: Thanks for your proof. I think I asked the wrong question yesterday. $\tilde d_\pi$ in your update is essentially $d_\pi$ defined in (1) and it is the state distribution in the infinite horizon. Thanks to you, I think I've found what I missed before. I originally thought using $d_\pi$ to express state distribution carried out by low-level policies is inappropriate since the low-level policies usually have a finite horizon. But I did not realize $\pi$ here actually denotes the whole hierarchical policy. That clears all my doubts. Thank you :-)
Answers.UserDisplayName: Maybe
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-07-01T23:53:15.383Z
Answers.LastActivityDate: 2019-07-11T01:59:00.557Z
Answers.LastEditDate: 2019-07-11T01:59:00.557Z
Answers.UserDisplayName: Zhiyu Zhang
Body: <p>At the appendix A of paper "<a href="https://arxiv.org/abs/1810.01257" rel="nofollow noreferrer">near-optimal representation learning for hierarchical reinforcement learning</a>", the authors express the <span class="math-container">$\gamma$</span>-discounted state visitation frequency <span class="math-container">$d$</span> of policy <span class="math-container">$\pi$</span> as</p>
  
  <p><span class="math-container">$$
  d=(1-\gamma)A_\pi(I-\gamma^cP_\pi^c)^{-1}\mu\tag 1
  $$</span></p>
  
  <p>I've simplifed the notation for easy reading, hoping it does not introduce any error. In the above definition, <span class="math-container">$P_\pi^c$</span> the <span class="math-container">$c$</span>-step transition matrix under the policy <span class="math-container">$\pi$</span>, i.e., <span class="math-container">$P_{\pi}^c=P_\pi(s_{c}|s_0)$</span>, <span class="math-container">$\mu$</span> a Dirac <span class="math-container">$\delta$</span> distribution centered at start state <span class="math-container">$s_0$</span> and 
  <span class="math-container">$$
  A_\pi=I+\sum_{k=1}^{c-1}\gamma^kP_\pi^k\tag 2
  $$</span>
  They further give the every-<span class="math-container">$c$</span>-steps <span class="math-container">$\gamma$</span>-discounted state frequency of <span class="math-container">$\pi$</span> as
  <span class="math-container">$$
  d^c_\pi=(1-\gamma^c)(I-\gamma^cP_\pi^c)^{-1}\mu\tag 3
  $$</span>
  To my best knowledge, <span class="math-container">$A_\pi$</span> seems to be the unnormalized <span class="math-container">$\gamma$</span>-discounted state frequency, but I cannot really make sense of the rest.
  I'm hoping that someone can shed some light on these definitions.</p>
  
  <h2>Update</h2>
  
  <p>Thank @Philip Raeisghasem for pointing out the paper <a href="https://arxiv.org/abs/1705.10528" rel="nofollow noreferrer">CPO</a>. Here's what I've gotten from that.
  Applying the sum of the geometric series to Eq.<span class="math-container">$(2)$</span>, we have
  <span class="math-container">$$
  A={(I-\gamma^cP_\pi^c)(I-\gamma P_\pi)^{-1}}\tag4
  $$</span>
  Plugging Eq.<span class="math-container">$(4)$</span> back into Eq.<span class="math-container">$(1)$</span>, we get the same result as Eq.<span class="math-container">$(18)$</span> in the CPO paper:
  <span class="math-container">$$
  d=(1-\gamma)(I-\gamma P_\pi)^{-1}\mu\tag 5
  $$</span>
  where <span class="math-container">$(1-\gamma)$</span> normalizes all weights introduced by <span class="math-container">$\gamma$</span> so that they are summed to one. However, I'm still confused. Here are the questions I have</p>
  
  <ol>
  <li>Eq.<span class="math-container">$(5)$</span> indicates Eq.<span class="math-container">$(1)$</span> is the state frequency in the infinite horizon. But I do not understand why we have it in the hierarchical policy. To my best knowledge, policies here are low-level, which means they are only valid in a short horizon (<span class="math-container">$c$</span> steps, for example). Computing state frequency in the infinite horizon here seems confusing.</li>
  <li>What should I make of <span class="math-container">$d_\pi^c$</span> defined in Eq.<span class="math-container">$(3)$</span>, originally from Eqs.<span class="math-container">$(26)$</span> and <span class="math-container">$(27)$</span> in the paper? The authors define them as every-<span class="math-container">$c$</span>-steps <span class="math-container">$\gamma$</span>-discounted state frequencies of policy <span class="math-container">$\pi$</span>. But I do not see why it is the case. To me, they are more like the consequence of Eq.<span class="math-container">$(30)$</span> in the paper.</li>
  </ol>
  
  <p>Sorry if anyone feels that this update makes this question too broad. This is kept since I'm not so sure whether I can get a satisfactory answer without these questions.
  Any partial answer will be sincerely appreciated. Thanks in advance.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-19T09:27:53.967Z
Comments.Text: See the appendix of [Constrained Policy Optimization](https://arxiv.org/pdf/1705.10528.pdf). I imagine these equations build on that and are a consequence of a [geometric series](https://en.wikipedia.org/wiki/Geometric_series) of matrices. I don't have a full proof/explanation, but I look forward to anyone who does.
Comments.UserDisplayName: Philip Raeisghasem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-20T01:29:02.857Z
Comments.Text: Thank @PhilipRaeisghasem. I've updated the question according to the resources you provided
Comments.UserDisplayName: Maybe
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-20T02:41:50.127Z
Comments.Text: I think your update made the question too broad. Try to limit your post to a single question. In this case, removing the update would suffice.
Comments.UserDisplayName: Philip Raeisghasem
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-20T03:11:34.843Z
Comments.Text: Sorry, I thought I just elaborated my confusion since my updated questions were all related to the same topic. I'm not so sure if I can get a sufficient answer if I remove those questions
Comments.UserDisplayName: Maybe
Tags: <reinforcement-learning>
Title: Intuition behind $\gamma$-discounted state frequency
UserDisplayName: Maybe
ThreadText: # Intuition behind $\gamma$-discounted state frequency
  
  (Asked by: username_0 on 2019-04-19)
  
  At the appendix A of paper "[near-optimal representation learning for hierarchical reinforcement learning](https://arxiv.org/abs/1810.01257)", the authors express the $\gamma$-discounted state visitation frequency $d$ of policy $\pi$ as
  
  $$
  d=(1-\gamma)A\_\pi(I-\gamma^cP\_\pi^c)^{-1}\mu\tag 1
  $$
  
  I've simplifed the notation for easy reading, hoping it does not introduce any error. In the above definition, $P\_\pi^c$ the $c$-step transition matrix under the policy $\pi$, i.e., $P\_{\pi}^c=P\_\pi(s\_{c}|s\_0)$, $\mu$ a Dirac $\delta$ distribution centered at start state $s\_0$ and
  $$
  A\_\pi=I+\sum\_{k=1}^{c-1}\gamma^kP\_\pi^k\tag 2
  $$
  They further give the every-$c$-steps $\gamma$-discounted state frequency of $\pi$ as
  $$
  d^c\_\pi=(1-\gamma^c)(I-\gamma^cP\_\pi^c)^{-1}\mu\tag 3
  $$
  To my best knowledge, $A\_\pi$ seems to be the unnormalized $\gamma$-discounted state frequency, but I cannot really make sense of the rest.
  I'm hoping that someone can shed some light on these definitions.
  
  ## Update
  
  Thank @username_1 for pointing out the paper [CPO](https://arxiv.org/abs/1705.10528). Here's what I've gotten from that.
  Applying the sum of the geometric series to Eq.$(2)$, we have
  $$
  A={(I-\gamma^cP\_\pi^c)(I-\gamma P\_\pi)^{-1}}\tag4
  $$
  Plugging Eq.$(4)$ back into Eq.$(1)$, we get the same result as Eq.$(18)$ in the CPO paper:
  $$
  d=(1-\gamma)(I-\gamma P\_\pi)^{-1}\mu\tag 5
  $$
  where $(1-\gamma)$ normalizes all weights introduced by $\gamma$ so that they are summed to one. However, I'm still confused. Here are the questions I have
  
  1. Eq.$(5)$ indicates Eq.$(1)$ is the state frequency in the infinite horizon. But I do not understand why we have it in the hierarchical policy. To my best knowledge, policies here are low-level, which means they are only valid in a short horizon ($c$ steps, for example). Computing state frequency in the infinite horizon here seems confusing.
  2. What should I make of $d\_\pi^c$ defined in Eq.$(3)$, originally from Eqs.$(26)$ and $(27)$ in the paper? The authors define them as every-$c$-steps $\gamma$-discounted state frequencies of policy $\pi$. But I do not see why it is the case. To me, they are more like the consequence of Eq.$(30)$ in the paper.
  
  Sorry if anyone feels that this update makes this question too broad. This is kept since I'm not so sure whether I can get a satisfactory answer without these questions.
  Any partial answer will be sincerely appreciated. Thanks in advance.
  
  **Tags:** reinforcement-learning
  
  > **Comments:**
  > **username_1**: See the appendix of [Constrained Policy Optimization](https://arxiv.org/pdf/1705.10528.pdf). I imagine these equations build on that and are a consequence of a [geometric series](https://en.wikipedia.org/wiki/Geometric_series) of matrices. I don't have a full proof/explanation, but I look forward to anyone who does.  
  > **username_0**: Thank @username_1. I've updated the question according to the resources you provided  
  > **username_1**: I think your update made the question too broad. Try to limit your post to a single question. In this case, removing the update would suffice.  
  > **username_0**: Sorry, I thought I just elaborated my confusion since my updated questions were all related to the same topic. I'm not so sure if I can get a sufficient answer if I remove those questions  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-07-01. Score: 1 | Accepted answer
  
  **Update: I rewrote the first part due to major mistake in the first version**
  
  Notice: The notation $P^k$ from Eq.$(20)$ and $(21)$ in the paper does not mean the kth power of some $P$. Instead, $P^k$ should be thought as the $k$ step transition probability of a non-homogeneous Markov chain.
  
  1. According to the CPO paper, the discounted future state distribution is defined as
     $$
     d\_\pi(s)=(1-\gamma)\sum\_{k=0}^\infty \gamma^kProb(s\_k=s|\pi,s\_0)\mu(s\_0)\tag{1}
     $$
     Consider function form. Let $Prob\_{\pi,k}$ denote the $k$ step probability transition operator induced by $\pi$; here $\pi$ can be a hierarchical policy, $k$ can be larger than $c$.
     $$
     d\_\pi=(1-\gamma)\sum\_{k=0}^\infty \gamma^kProb\_{\pi,k}\mu\tag{2}
     $$
     Now apply the similar definition as Eq.$(20)$ and $(21)$ in the paper, let $P^k\_\pi$ denote the $k$ step transition probability of the non-homogeneous Markov chain induced by the low level policy, with $k$ smaller or equal to $c$.
     \begin{align}
     d\_\pi&=(1-\gamma)\sum\_{m=0}^\infty\gamma^{mc}\sum\_{k=0}^{c-1}\gamma^kP^k\_\pi(P^c\_\pi)^m\mu\\
     &=(1-\gamma)\sum\_{k=0}^{c-1}\gamma^kP^k\_\pi(\sum\_{m=0}^\infty\gamma^{mc}(P^c\_\pi)^m)\mu\\
     &=(1-\gamma)A\_\pi(I-\gamma^cP^c)^{-1}\mu\tag{3}
     \end{align}
     which is exactly the form of Eq.$(22)$ and $(23)$ in the paper, with $A\_\pi$ defined similar as Eq.$(24)$ and $(25)$.
  2. The "every-$c$-step discounted state frequency" builds on $(3)$, but it lumps the $c$ steps into one "high level" step where the discount factor is $\gamma^c$ and the transition operator is $P\_\pi^c$. Starting with $(3)$, replace $c$ with 1, we get the "every one step future state distribution"
     $$
     d\_\pi=(1-\gamma)(I-\gamma P\_\pi)^{-1}\mu\tag{4}
     $$
     Then replace $\gamma$ and $P\_\pi$ in $(4)$ with $\gamma^c$ and $P\_\pi^c$, we get the "every-$c$-step discounted state frequency", or "every-$c$-step future state distribution"
     $$
     d\_\pi^c=(1-\gamma^c)(I-\gamma^c P\_\pi^c)^{-1}\mu\tag{5}
     $$
     By the way, I read your blogpost on this paper. It's very helpful for me, thank you!
  
  > **Comments:**
  > **username_0**: Thanks for answering, your second explanation is great:-). But I'm sorry that I cannot follow your first reasoning exactly. Would you mind explaining how you compute the normalizing term $(1-\gamma^cP_\pi^c)^{-1}$? Furthermore, I'm confused about "the meaning of $(4)$ is the same as $(1)$". Do you suggest state distribution in c steps is the same as that in infinite steps? BTW, I'm glad my blog helps:)  
  > **username_2**: For the derivation of the normalizing term, please see my updated answer. As for my comment "the meaning of $(4)$ is the same as $(1)$", I mean intuitively they roughly refer to the same concept and play the same role as in expressing the discounted value function. But I agree, this comment is misleading, so I deleted it... Hope this update is helpful...  
  > **username_0**: Thanks for your proof. I think I asked the wrong question yesterday. $\tilde d_\pi$ in your update is essentially $d_\pi$ defined in (1) and it is the state distribution in the infinite horizon. Thanks to you, I think I've found what I missed before. I originally thought using $d_\pi$ to express state distribution carried out by low-level policies is inappropriate since the low-level policies usually have a finite horizon. But I did not realize $\pi$ here actually denotes the whole hierarchical policy. That clears all my doubts. Thank you :-)  
  
  ---
  
  