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$ Apr 19, 2019 at 9:27
  • $\begingroup$ Thank @PhilipRaeisghasem. I've updated the question according to the resources you provided $\endgroup$
    – Maybe
    Apr 20, 2019 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$ Apr 20, 2019 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, 2019 at 3:11

1 Answer 1


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, 2019 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$ Jul 2, 2019 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, 2019 at 5:09

You must log in to answer this question.

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