At the appendix A of paper "near-optimal representation learning for hierarchical reinforcement learning", 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.


Thank @Philip Raeisghasem for pointing out the paper CPO. 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.

  • $\begingroup$ See the appendix of Constrained Policy Optimization. I imagine these equations build on that and are a consequence of a geometric series of matrices. I don't have a full proof/explanation, but I look forward to anyone who does. $\endgroup$ – Philip Raeisghasem Apr 19 '19 at 9:27
  • $\begingroup$ Thank @PhilipRaeisghasem. I've updated the question according to the resources you provided $\endgroup$ – Maybe Apr 20 '19 at 1:29
  • $\begingroup$ 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. $\endgroup$ – Philip Raeisghasem Apr 20 '19 at 2:41
  • $\begingroup$ 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 $\endgroup$ – Maybe Apr 20 '19 at 3:11

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!
  • $\begingroup$ 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:) $\endgroup$ – Maybe Jul 2 '19 at 3:48
  • $\begingroup$ 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... $\endgroup$ – Zhiyu Zhang Jul 2 '19 at 22:22
  • $\begingroup$ 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 :-) $\endgroup$ – Maybe Jul 3 '19 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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