3
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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 $$

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ Commented Feb 18 at 3:39
  • $\begingroup$ however, i have trouble understanding how do we get to that "After multiple steps you will be left with last two differences" $\endgroup$ Commented Feb 18 at 5:12
  • 1
    $\begingroup$ 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. $\endgroup$
    – vl_knd
    Commented Feb 18 at 10:17
  • $\begingroup$ 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. $\endgroup$ Commented Feb 19 at 3:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – vl_knd
    Commented Feb 19 at 10:54

You must log in to answer this question.

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