Answers.Body: <p><strong>Question 1</strong></p>
  <p>The taylor expansion of <span class="math-container">$\frac{1}{1-\gamma}$</span> at <span class="math-container">$\gamma= 0$</span> is as follows</p>
  <p><span class="math-container">$$\frac{1}{1-\gamma} = 1 + \gamma + \gamma^2 + \dots$$</span></p>
  <p>When you multiply by <span class="math-container">$1-\gamma$</span> you get</p>
  <p><span class="math-container">$$ 1 = (1-\gamma)(1 + \gamma + \gamma^2 + \dots)$$</span></p>
  <p>Which can be equivalently written as</p>
  <p><span class="math-container">$$1 = (1-\gamma)\sum_\limits{i=0}^{\infty}\gamma^i$$</span></p>
  <p>Hence we can see that by multiplying the coefficients by <span class="math-container">$(1-\gamma)$</span> we get a weighted sum of transition probabilities</p>
  <hr />
  <p><strong>Question 2</strong></p>
  <p>Multiplying by <span class="math-container">$(1-\lambda)$</span> is to cancel out the normalisation term which was included in the definition of the discounted distribution of the states. Partially expanding out your expressions for the discounted reward you get this</p>
  <p><span class="math-container">$$ J(\pi) = \frac{1}{1-\gamma}\sum_\limits{s}E_
  {a\sim\pi,s'\sim P}[R(s,a,s')]\cdot\left((1-\gamma)\sum_\limits{t=0}^{\infty}\gamma^tP(s_t=s|\pi)\right)$$</span></p>
  <p>The discounted return form is usually denoted</p>
  <p><span class="math-container">$$J(\pi) = E[\sum\gamma^iR_i(s,a,s')]$$</span></p>
  <p>Where you notice the discounting terms aren't normalised which motivates cancelling it out</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-04T15:56:37.837Z
Answers.Text: So from what I understand you are saying that $(1-\gamma)$ is used to normalize (i.e., get the sum of values to be equal to 1) and $(\frac{1}{1-\gamma})$ is used to cancel that normalization?
Answers.UserDisplayName: josealeixo.pc
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-04T16:35:09.280Z
Answers.Text: precisely that.
Answers.UserDisplayName: quest ions
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-04T14:59:47.707Z
Answers.LastActivityDate: 2021-03-04T14:59:47.707Z
Answers.UserDisplayName: quest ions
Body: <p>In the appendix of the Constrained Policy Optimization (CPO) paper (<a href="https://arxiv.org/abs/1705.10528" rel="nofollow noreferrer">Arxiv</a>), the authors denote the <em>discounted future state distribution</em> <span class="math-container">$d^\pi$</span> as:</p>
  <p><span class="math-container">$$d^\pi(s) = (1-\gamma) \sum_{t=0}^\infty{\gamma^t P(s_t = s \vert \pi)}\tag1$$</span></p>
  <p>and the <em>discounted total reward</em> <span class="math-container">$J(\pi)$</span> as:</p>
  <p><span class="math-container">$$J(\pi) = \frac{1}{1-\gamma} E_{\substack{s\sim d^\pi \\ a \sim \pi \\ s' \sim P}}[R(s,a,s')]\tag2$$</span></p>
  <p>I have two questions regarding these equations.</p>
  <p><strong>Question 1</strong></p>
  <p>Intuitively, I understand that <span class="math-container">$d^\pi(s)$</span> returns the discounted probability of landing on state <span class="math-container">$s$</span> when executing policy <span class="math-container">$\pi$</span>.</p>
  <p>I understand that the summation part of <span class="math-container">$(1)$</span> results in values that are greater than <span class="math-container">$1$</span>, and are, therefore, not fit for a probability distribution. But I do not understand why the value that results from this is multiplied by <span class="math-container">$(1-\gamma)$</span>.</p>
  <p>I have read in <a href="https://ai.stackexchange.com/questions/11888/intuition-behind-gamma-discounted-state-frequency">this question</a> that &quot;<span class="math-container">$(1−\gamma)$</span> normalizes all weights introduced by γ so that they are summed to <span class="math-container">$1$</span>&quot;. I have confirmed that this is true, but I don't understand why.</p>
  <p>I tested this with a simple example:</p>
  <p>Suppose there is are only two states <span class="math-container">$s_A$</span> and <span class="math-container">$s_B$</span> and the probabilty of landing on <span class="math-container">$s_A$</span> is <span class="math-container">$0.4$</span> and on <span class="math-container">$s_B$</span> is <span class="math-container">$0.6$</span>, independently of the previous state or action taken (therefore, independently of the policy <span class="math-container">$\pi$</span>). Also suppose we set the maximum number of time steps <span class="math-container">$t_{max} = 1000$</span> (to make the equation easy to compute) and <span class="math-container">$\gamma = 0.9$</span>.</p>
  <p>Then:</p>
  <p><span class="math-container">$$d^\pi(s_A) = (1-0.9) \sum_{t=0}^{1000} 0.9^t \cdot 0.4 \approx (1-0.9) \cdot 4$$</span></p>
  <p>and</p>
  <p><span class="math-container">$$d^\pi(s_B) \approx (1-0.9) \cdot 6$$</span></p>
  <p>So indeed if we sum them and multiply by <span class="math-container">$(1-\gamma)$</span> we get:</p>
  <p><span class="math-container">$$(1-0.9)\cdot(4+6) = 1$$</span></p>
  <p><strong>Q</strong>: My question is why does multiplying by <span class="math-container">$(1-\gamma)$</span> normalize to <span class="math-container">$1$</span>? And what does <span class="math-container">$(1-\gamma)$</span> represent in this context?</p>
  <p><strong>Question 2</strong></p>
  <p>Similarly, I can't understand the use of <span class="math-container">$\frac{1}{1-\gamma}$</span> in <span class="math-container">$(2)$</span>.</p>
  <p><strong>Q</strong>: How does multiplying the expected value of the reward function by <span class="math-container">$\frac{1}{1-\gamma}$</span> result in the discounted reward, instead of multiplying by <span class="math-container">$\gamma$</span>? What does <span class="math-container">$\frac{1}{1-\gamma}$</span> represent?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-08T10:25:48.907Z
Comments.Text: Please, next time, **ask only one question per post**, even if you have related questions. If you have more than 1 question, ask each of them in their separate post.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><reward-functions><constrained-optimization>
Title: Intuition behind $1-\gamma$ and $\frac{1}{1-\gamma}$ for calculating discounted future state distribution and discounted reward
UserDisplayName: josealeixo.pc
ThreadText: # Intuition behind $1-\gamma$ and $\frac{1}{1-\gamma}$ for calculating discounted future state distribution and discounted reward
  
  (Asked by: username_0 on 2021-03-04)
  
  In the appendix of the Constrained Policy Optimization (CPO) paper ([Arxiv](https://arxiv.org/abs/1705.10528)), the authors denote the *discounted future state distribution* $d^\pi$ as:
  
  $$d^\pi(s) = (1-\gamma) \sum\_{t=0}^\infty{\gamma^t P(s\_t = s \vert \pi)}\tag1$$
  
  and the *discounted total reward* $J(\pi)$ as:
  
  $$J(\pi) = \frac{1}{1-\gamma} E\_{\substack{s\sim d^\pi \\ a \sim \pi \\ s' \sim P}}[R(s,a,s')]\tag2$$
  
  I have two questions regarding these equations.
  
  **Question 1**
  
  Intuitively, I understand that $d^\pi(s)$ returns the discounted probability of landing on state $s$ when executing policy $\pi$.
  
  I understand that the summation part of $(1)$ results in values that are greater than $1$, and are, therefore, not fit for a probability distribution. But I do not understand why the value that results from this is multiplied by $(1-\gamma)$.
  
  I have read in [this question](https://ai.stackexchange.com/questions/11888/intuition-behind-gamma-discounted-state-frequency) that "$(1−\gamma)$ normalizes all weights introduced by γ so that they are summed to $1$". I have confirmed that this is true, but I don't understand why.
  
  I tested this with a simple example:
  
  Suppose there is are only two states $s\_A$ and $s\_B$ and the probabilty of landing on $s\_A$ is $0.4$ and on $s\_B$ is $0.6$, independently of the previous state or action taken (therefore, independently of the policy $\pi$). Also suppose we set the maximum number of time steps $t\_{max} = 1000$ (to make the equation easy to compute) and $\gamma = 0.9$.
  
  Then:
  
  $$d^\pi(s\_A) = (1-0.9) \sum\_{t=0}^{1000} 0.9^t \cdot 0.4 \approx (1-0.9) \cdot 4$$
  
  and
  
  $$d^\pi(s\_B) \approx (1-0.9) \cdot 6$$
  
  So indeed if we sum them and multiply by $(1-\gamma)$ we get:
  
  $$(1-0.9)\cdot(4+6) = 1$$
  
  **Q**: My question is why does multiplying by $(1-\gamma)$ normalize to $1$? And what does $(1-\gamma)$ represent in this context?
  
  **Question 2**
  
  Similarly, I can't understand the use of $\frac{1}{1-\gamma}$ in $(2)$.
  
  **Q**: How does multiplying the expected value of the reward function by $\frac{1}{1-\gamma}$ result in the discounted reward, instead of multiplying by $\gamma$? What does $\frac{1}{1-\gamma}$ represent?
  
  **Tags:** reinforcement-learning, reward-functions, constrained-optimization
  > **Comments:**
  > **username_1**: Please, next time, **ask only one question per post**, even if you have related questions. If you have more than 1 question, ask each of them in their separate post.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-03-04. Score: 3 | Accepted answer
  
  **Question 1**
  
  The taylor expansion of $\frac{1}{1-\gamma}$ at $\gamma= 0$ is as follows
  
  $$\frac{1}{1-\gamma} = 1 + \gamma + \gamma^2 + \dots$$
  
  When you multiply by $1-\gamma$ you get
  
  $$ 1 = (1-\gamma)(1 + \gamma + \gamma^2 + \dots)$$
  
  Which can be equivalently written as
  
  $$1 = (1-\gamma)\sum\_\limits{i=0}^{\infty}\gamma^i$$
  
  Hence we can see that by multiplying the coefficients by $(1-\gamma)$ we get a weighted sum of transition probabilities
  
  ---
  
  **Question 2**
  
  Multiplying by $(1-\lambda)$ is to cancel out the normalisation term which was included in the definition of the discounted distribution of the states. Partially expanding out your expressions for the discounted reward you get this
  
  $$ J(\pi) = \frac{1}{1-\gamma}\sum\_\limits{s}E\_
  {a\sim\pi,s'\sim P}[R(s,a,s')]\cdot\left((1-\gamma)\sum\_\limits{t=0}^{\infty}\gamma^tP(s\_t=s|\pi)\right)$$
  
  The discounted return form is usually denoted
  
  $$J(\pi) = E[\sum\gamma^iR\_i(s,a,s')]$$
  
  Where you notice the discounting terms aren't normalised which motivates cancelling it out
  
  > **Comments:**
  > **username_0**: So from what I understand you are saying that $(1-\gamma)$ is used to normalize (i.e., get the sum of values to be equal to 1) and $(\frac{1}{1-\gamma})$ is used to cancel that normalization?  
  > **username_2**: precisely that.  
  
  ---
  
  