# Intuition behind $\gamma$-discounted state frequency

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.

## Update

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.

• 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. – Philip Raeisghasem Apr 19 at 9:27
• Thank @PhilipRaeisghasem. I've updated the question according to the resources you provided – Maybe Apr 20 at 1:29
• 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. – Philip Raeisghasem Apr 20 at 2:41
• 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 – Maybe Apr 20 at 3:11

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