Answers.Body: <p>The relation is actually
  <span class="math-container">$$
  G_{\text{asc}} \leq G \leq G_{\text{dec}}
  $$</span>
  Without loss of generality, we can say that the sequence <span class="math-container">$r_0, r_1, .., r_n = G_{\text{dec}}$</span> is already sorted in descending order.</p>
  <p>Then we know, that
  <span class="math-container">$$
  r_0 \geq r_1 .. \geq r_n
  $$</span>
  Lets look at the difference <span class="math-container">$G_{\text{dec}} - G$</span>:
  <span class="math-container">$$
  G_{\text{dec}} - G = r_0 - r_i + \gamma(r_1 - r_j) .. 
  $$</span>
  Let <span class="math-container">$\delta_{kj} = (r_k - r_j)$</span> and lets note, that there always exists a sequence of differences of rewards, weighted by gammas:
  <span class="math-container">$$
  \gamma^k \delta_{kj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm} + \gamma^m \delta_{mk}
  $$</span>
  It important, that it starts with <span class="math-container">$\delta_{kj}$</span> and ends with <span class="math-container">$\delta_{mk}$</span>, take note of the circular nature of the indexes!</p>
  <p>Without loss of generality we can assume, that <span class="math-container">$r_k$</span> is the largest element. Then <span class="math-container">$\gamma^k$</span> is also the largest and <span class="math-container">$\delta_{kj} \geq 0$</span>. Then we can say, that
  <span class="math-container">\begin{align*}
  \gamma^k \delta_{kj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm} + \gamma^m \delta_{mk} &amp; \geq \\
  \text{(I change }\gamma^k\text{ to }\gamma^m\text{ at first difference)} &amp; \\
  \gamma^m \delta_{kj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm} + \gamma^m \delta_{mk} &amp; = \\
  \text{(Now we can combine }\gamma^m \delta_{kj}\text{ and }\gamma^m \delta_{mk}\text{ )} &amp; \\
  \gamma^m \delta_{mj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm}&amp;\\
  \end{align*}</span>
  So at the end, for sequence, where <span class="math-container">$r_k$</span> is the largest element we get:
  <span class="math-container">$$
  \gamma^k \delta_{kj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm} + \gamma^m \delta_{mk} \geq \gamma^m \delta_{mj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm}
  $$</span>
  But the resulting sequence is reduced by one element! Now we can repeat the same procedure(*):</p>
  <ol>
  <li>Find the biggest element.</li>
  <li>Look at the <span class="math-container">$\delta$</span>s that contains it and combine them.</li>
  </ol>
  <p>After multiple steps you will be left with last two differences:
  <span class="math-container">$$
  \gamma^k \delta_{kj} + \gamma^j \delta_{ji} + ... + \gamma^p \delta_{pm} + \gamma^m \delta_{mk} \geq \gamma^v \delta_{vw} + \gamma^w \delta_{wv}
  $$</span>
  Just as before, without loss of generality we can assume, that <span class="math-container">$r_v$</span> is the biggest element, then
  <span class="math-container">$$
  \gamma^v \delta_{vw} + \gamma^w \delta_{wv} \geq \gamma^w \delta_{vw} + \gamma^w \delta_{wv} = 0
  $$</span>
  So, in other words we have:
  <span class="math-container">\begin{align*}
  G_{\text{dec}} - G &amp;= r_0 - r_i + \gamma(r_1 - r_j) .. \\
  &amp;= (\gamma^k \delta_{kj} + ... + \gamma^m \delta_{mk}) + (\gamma^a \delta_{ac} + ... + \gamma^b \delta_{bc}) + ...\\
  &amp; \geq  0 + 0 + ...
  \end{align*}</span>
  And then
  <span class="math-container">$$
  G_{\text{dec}} - G \geq 0 \rightarrow G_{\text{dec}} \geq G
  $$</span></p>
  <p>For proof of <span class="math-container">$
  G_{\text{asc}} - G \leq 0$</span>, the logic is exactly the same, but all the signs are inversed. We have then
  <span class="math-container">$$G_{\text{dec}} \geq G$$</span>
  <span class="math-container">$$G_{\text{asc}} \leq G$$</span>
  Or in other words
  <span class="math-container">$$
  G_{\text{asc}} \leq G \leq G_{\text{dec}}
  $$</span></p>
  <hr />
  <p><strong>Update</strong></p>
  <p><em>Example of reduction of series of differences:</em></p>
  <p>Without loss of generality, we can say that the sequence <span class="math-container">$G_{\text{dec}} = r_0, r_1, r_2, r_3, r_4, r_5$</span> is already sorted in descending order. Let <span class="math-container">$G = r_5, r_3, r_0, r_1, r_2, r_4$</span> be (pseudo)random shuffle of <span class="math-container">$G_{\text{dec}}$</span>. We can re-write the difference as:
  <span class="math-container">\begin{align*}
  G_{\text{dec}} - G &amp; = \gamma^0 \delta_{05} + \gamma^1 \delta_{13} + \gamma^2 \delta_{20} + \gamma^3 \delta_{31} + \gamma^4 \delta_{42} + \gamma^5 \delta_{54} \\
   &amp; = \gamma^0 \delta_{05} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} + \gamma^2 \delta_{20} + \gamma^1 \delta_{13} +  \gamma^3 \delta_{31}\\
   &amp; = (\gamma^0 \delta_{05} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} + \gamma^2 \delta_{20}) + (\gamma^1 \delta_{13} +  \gamma^3 \delta_{31})\\
  \end{align*}</span></p>
  <p>Lets take a look at two sums in parentheses:</p>
  <ul>
  <li><p><span class="math-container">$(\gamma^0 \delta_{05} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} + \gamma^2 \delta_{20})$</span></p>
  </li>
  <li><p><span class="math-container">$(\gamma^1 \delta_{13} + \gamma^3 \delta_{31})$</span></p>
  </li>
  </ul>
  <p>Then, by the procedure I have noted with ( * ) in the explanation, we have:
  <span class="math-container">\begin{align*}
  \gamma^0 \delta_{05} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} + \gamma^2 \delta_{20} &amp; \geq\\
  \gamma^2 \delta_{05} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} + \gamma^2 \delta_{20} &amp; =\\
  \gamma^2 \delta_{25} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} &amp; \geq\\
  \gamma^4 \delta_{25} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} &amp; =\\
  \gamma^4 \delta_{45} + \gamma^5 \delta_{54} &amp; \geq \\
  \gamma^5 \delta_{45} + \gamma^5 \delta_{54} &amp; = 0 \\
  \end{align*}</span>
  And
  <span class="math-container">\begin{align*}
  \gamma^1 \delta_{13} + \gamma^3 \delta_{31} &amp; \geq \\
  \gamma^3 \delta_{13} + \gamma^3 \delta_{31} &amp; = 0\\
  \end{align*}</span></p>
  <p>Then, its clear that
  <span class="math-container">$$
  G_{\text{dec}} - G = (\gamma^0 \delta_{05} + \gamma^5 \delta_{54}  + \gamma^4 \delta_{42} + \gamma^2 \delta_{20}) + (\gamma^1 \delta_{13} +  \gamma^3 \delta_{31}) \geq 0
  $$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-18T03:39:38.420Z
Answers.Text: This is brilliant! i was thinking this might could also be interpreted as a selection sort, after every sorting, the more ordered sequence gets a increment greater or equal than 0 than the less ordered sequence. But your answer is way more mathematical and authentic
Answers.UserDisplayName: juicyliberty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-18T05:12:30.990Z
Answers.Text: however, i have trouble understanding how do we get to that "After multiple steps you will be left with last two differences"
Answers.UserDisplayName: juicyliberty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-18T10:17:02.997Z
Answers.Text: By "step" I mean reducing the sum of differences by one difference. @juicyliberty I added an example of what it looks like to make it clearer. Hope it helps.
Answers.UserDisplayName: vl_knd
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-19T03:04:24.697Z
Answers.Text: Thank you so much! this sure make things clearer, but actually it is the "circular nature of the indexes" that really bothers me, i want to make sure that "there always exsist a sequence that starts with starts with δkj and ends with δmk", which ensures that the reduction of series of differences can be safely executed. Are there any resources or materials explaining this kind of concept, i'm no expert in mathmatics unfortunately. i'm really sorry for not making my question clearer.
Answers.UserDisplayName: juicyliberty
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-19T10:54:54.053Z
Answers.Text: While Im not fully sure how to give a rigorous proof to this, I feel like you can find a solution in graph theory. You can imagine something like a directed graph, where nodes are rewards and edges are given by the $\delta_{ij}$. So if $\delta_{ij}$ is present in $G_{\text{des}} - G$, then you have an edge $ij$ in the graph. We can say, that each node will have two edges - one outgoing and one incoming. Just from this I think you can conclude that it will consist of non-intersecting rings, which is equivalent to the statement we are trying to proof.
Answers.UserDisplayName: vl_knd
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-02-15T14:49:22.590Z
Answers.LastActivityDate: 2024-02-18T16:27:30.737Z
Answers.LastEditDate: 2024-02-18T16:27:30.737Z
Answers.UserDisplayName: vl_knd
Body: <p>Let's say from time step <span class="math-container">$t$</span>, the agent interact with the environment for <span class="math-container">$n$</span> steps, and gets a reward seuqence <span class="math-container">$R = (r_{t}, r_{t+1}, \cdots , r_{t+n})$</span></p>
  <p>Now we respectively sort the reward sequence <span class="math-container">$R$</span> in both <strong>ascending order and decending order</strong> to get <span class="math-container">$R_{asc}$</span> and <span class="math-container">$R_{dec}$</span>. By the definition of the <strong>cumulative discounted reward</strong> which is:</p>
  <p><span class="math-container">$G_{t}=r_{t}+\gamma\cdot r_{t+1}+\gamma^{2}\cdot r_{t+2}+\cdots=\sum_{k=0}^{\infty}\gamma^{k}\cdot r_{t+k}$</span></p>
  <p>We compute the <strong>cumulative discounted reward</strong> of these three reward sequences <span class="math-container">$R, R_{asc}, R_{dec}$</span>, and get <span class="math-container">$G, G_{asc}, G_{dec}$</span></p>
  <p>What is the result of comparing these numbers <span class="math-container">$G, G_{asc}, G_{dec}$</span>? Based on my understanding of the idea of discounted reward, my intuition says <span class="math-container">$G_{asc} &lt; G &lt; G_{dec}$</span>. If that is the case, how do i prove this?</p>
  
Tags: <reinforcement-learning><rewards>
Title: How does changing the order of a sequence of rewards affect the cumulative discounted reward
UserDisplayName: juicyliberty
ThreadText: # How does changing the order of a sequence of rewards affect the cumulative discounted reward
  
  (Asked by: username_0 on 2024-02-11)
  
  Let's say from time step $t$, the agent interact with the environment for $n$ steps, and gets a reward seuqence $R = (r\_{t}, r\_{t+1}, \cdots , r\_{t+n})$
  
  Now we respectively sort the reward sequence $R$ in both **ascending order and decending order** to get $R\_{asc}$ and $R\_{dec}$. By the definition of the **cumulative discounted reward** which is:
  
  $G\_{t}=r\_{t}+\gamma\cdot r\_{t+1}+\gamma^{2}\cdot r\_{t+2}+\cdots=\sum\_{k=0}^{\infty}\gamma^{k}\cdot r\_{t+k}$
  
  We compute the **cumulative discounted reward** of these three reward sequences $R, R\_{asc}, R\_{dec}$, and get $G, G\_{asc}, G\_{dec}$
  
  What is the result of comparing these numbers $G, G\_{asc}, G\_{dec}$? Based on my understanding of the idea of discounted reward, my intuition says $G\_{asc} < G < G\_{dec}$. If that is the case, how do i prove this?
  
  **Tags:** reinforcement-learning, rewards
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2024-02-15. Score: 2 | Accepted answer
  
  The relation is actually
  $$
  G\_{\text{asc}} \leq G \leq G\_{\text{dec}}
  $$
  Without loss of generality, we can say that the sequence $r\_0, r\_1, .., r\_n = G\_{\text{dec}}$ is already sorted in descending order.
  
  Then we know, that
  $$
  r\_0 \geq r\_1 .. \geq r\_n
  $$
  Lets look at the difference $G\_{\text{dec}} - G$:
  $$
  G\_{\text{dec}} - G = r\_0 - r\_i + \gamma(r\_1 - r\_j) ..
  $$
  Let $\delta\_{kj} = (r\_k - r\_j)$ and lets note, that there always exists a sequence of differences of rewards, weighted by gammas:
  $$
  \gamma^k \delta\_{kj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm} + \gamma^m \delta\_{mk}
  $$
  It important, that it starts with $\delta\_{kj}$ and ends with $\delta\_{mk}$, take note of the circular nature of the indexes!
  
  Without loss of generality we can assume, that $r\_k$ is the largest element. Then $\gamma^k$ is also the largest and $\delta\_{kj} \geq 0$. Then we can say, that
  \begin{align\*}
  \gamma^k \delta\_{kj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm} + \gamma^m \delta\_{mk} & \geq \\
  \text{(I change }\gamma^k\text{ to }\gamma^m\text{ at first difference)} & \\
  \gamma^m \delta\_{kj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm} + \gamma^m \delta\_{mk} & = \\
  \text{(Now we can combine }\gamma^m \delta\_{kj}\text{ and }\gamma^m \delta\_{mk}\text{ )} & \\
  \gamma^m \delta\_{mj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm}&\\
  \end{align\*}
  So at the end, for sequence, where $r\_k$ is the largest element we get:
  $$
  \gamma^k \delta\_{kj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm} + \gamma^m \delta\_{mk} \geq \gamma^m \delta\_{mj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm}
  $$
  But the resulting sequence is reduced by one element! Now we can repeat the same procedure(\*):
  
  1. Find the biggest element.
  2. Look at the $\delta$s that contains it and combine them.
  
  After multiple steps you will be left with last two differences:
  $$
  \gamma^k \delta\_{kj} + \gamma^j \delta\_{ji} + ... + \gamma^p \delta\_{pm} + \gamma^m \delta\_{mk} \geq \gamma^v \delta\_{vw} + \gamma^w \delta\_{wv}
  $$
  Just as before, without loss of generality we can assume, that $r\_v$ is the biggest element, then
  $$
  \gamma^v \delta\_{vw} + \gamma^w \delta\_{wv} \geq \gamma^w \delta\_{vw} + \gamma^w \delta\_{wv} = 0
  $$
  So, in other words we have:
  \begin{align\*}
  G\_{\text{dec}} - G &= r\_0 - r\_i + \gamma(r\_1 - r\_j) .. \\
  &= (\gamma^k \delta\_{kj} + ... + \gamma^m \delta\_{mk}) + (\gamma^a \delta\_{ac} + ... + \gamma^b \delta\_{bc}) + ...\\
  & \geq 0 + 0 + ...
  \end{align\*}
  And then
  $$
  G\_{\text{dec}} - G \geq 0 \rightarrow G\_{\text{dec}} \geq G
  $$
  
  For proof of $
  G\_{\text{asc}} - G \leq 0$, the logic is exactly the same, but all the signs are inversed. We have then
  $$G\_{\text{dec}} \geq G$$
  $$G\_{\text{asc}} \leq G$$
  Or in other words
  $$
  G\_{\text{asc}} \leq G \leq G\_{\text{dec}}
  $$
  
  ---
  
  **Update**
  
  *Example of reduction of series of differences:*
  
  Without loss of generality, we can say that the sequence $G\_{\text{dec}} = r\_0, r\_1, r\_2, r\_3, r\_4, r\_5$ is already sorted in descending order. Let $G = r\_5, r\_3, r\_0, r\_1, r\_2, r\_4$ be (pseudo)random shuffle of $G\_{\text{dec}}$. We can re-write the difference as:
  \begin{align\*}
  G\_{\text{dec}} - G & = \gamma^0 \delta\_{05} + \gamma^1 \delta\_{13} + \gamma^2 \delta\_{20} + \gamma^3 \delta\_{31} + \gamma^4 \delta\_{42} + \gamma^5 \delta\_{54} \\
  & = \gamma^0 \delta\_{05} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} + \gamma^2 \delta\_{20} + \gamma^1 \delta\_{13} + \gamma^3 \delta\_{31}\\
  & = (\gamma^0 \delta\_{05} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} + \gamma^2 \delta\_{20}) + (\gamma^1 \delta\_{13} + \gamma^3 \delta\_{31})\\
  \end{align\*}
  
  Lets take a look at two sums in parentheses:
  
  * $(\gamma^0 \delta\_{05} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} + \gamma^2 \delta\_{20})$
  * $(\gamma^1 \delta\_{13} + \gamma^3 \delta\_{31})$
  
  Then, by the procedure I have noted with ( \* ) in the explanation, we have:
  \begin{align\*}
  \gamma^0 \delta\_{05} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} + \gamma^2 \delta\_{20} & \geq\\
  \gamma^2 \delta\_{05} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} + \gamma^2 \delta\_{20} & =\\
  \gamma^2 \delta\_{25} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} & \geq\\
  \gamma^4 \delta\_{25} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} & =\\
  \gamma^4 \delta\_{45} + \gamma^5 \delta\_{54} & \geq \\
  \gamma^5 \delta\_{45} + \gamma^5 \delta\_{54} & = 0 \\
  \end{align\*}
  And
  \begin{align\*}
  \gamma^1 \delta\_{13} + \gamma^3 \delta\_{31} & \geq \\
  \gamma^3 \delta\_{13} + \gamma^3 \delta\_{31} & = 0\\
  \end{align\*}
  
  Then, its clear that
  $$
  G\_{\text{dec}} - G = (\gamma^0 \delta\_{05} + \gamma^5 \delta\_{54} + \gamma^4 \delta\_{42} + \gamma^2 \delta\_{20}) + (\gamma^1 \delta\_{13} + \gamma^3 \delta\_{31}) \geq 0
  $$
  
  > **Comments:**
  > **username_0**: This is brilliant! i was thinking this might could also be interpreted as a selection sort, after every sorting, the more ordered sequence gets a increment greater or equal than 0 than the less ordered sequence. But your answer is way more mathematical and authentic  
  > **username_0**: however, i have trouble understanding how do we get to that "After multiple steps you will be left with last two differences"  
  > **username_1**: By "step" I mean reducing the sum of differences by one difference. @juicyliberty I added an example of what it looks like to make it clearer. Hope it helps.  
  > **username_0**: Thank you so much! this sure make things clearer, but actually it is the "circular nature of the indexes" that really bothers me, i want to make sure that "there always exsist a sequence that starts with starts with δkj and ends with δmk", which ensures that the reduction of series of differences can be safely executed. Are there any resources or materials explaining this kind of concept, i'm no expert in mathmatics unfortunately. i'm really sorry for not making my question clearer.  
  > **username_1**: While Im not fully sure how to give a rigorous proof to this, I feel like you can find a solution in graph theory. You can imagine something like a directed graph, where nodes are rewards and edges are given by the $\delta_{ij}$. So if $\delta_{ij}$ is present in $G_{\text{des}} - G$, then you have an edge $ij$ in the graph. We can say, that each node will have two edges - one outgoing and one incoming. Just from this I think you can conclude that it will consist of non-intersecting rings, which is equivalent to the statement we are trying to proof.  
  
  ---
  
  