0
$\begingroup$

I would like to know why:

$\left| \sum\limits_{t=0}^\infty \delta^tr(s_t,a_t)\right|\le \sum\limits_{t=0}^\infty \delta^t|r(s_t,a_t)|$

where:

$\delta \in (0,1)$ and is a $r(s_t,a_t)$ is a real valued function and is bounded.

My text states that the above is a consequence of the Cauchy-Schwarz inequality, but it is not immediately clear to me why it is true. So, I tried to prove it by starting from the Cauchy-Schwarz inequality:

$\begin{align} \left(\sum\limits_{i=0}^n a_ib_i\right)^2 \le \left(\sum\limits_{i=0}^n a_i^2\right) \left(\sum\limits_{i=0}^nb_i^2\right) \end{align}$

Taking square roots on both sides, I can get: $$ \left| \sum\limits_{i=0}^n a_ib_i \right| \le \left(\sum\limits_{i=0}^n a_i^2\right)^\frac{1}{2} \left(\sum\limits_{i=0}^nb_i^2\right)^\frac{1}{2} \le \left(\sum\limits_{i=0}^n a_i^2\right) \left(\sum\limits_{i=0}^nb_i^2\right)$$

Now, I don't know what else I can do to get $\left(\sum\limits_{i=0}^n a_i|b_i|\right)$

$\endgroup$

1 Answer 1

1
$\begingroup$

I would think that Hölder's inequality is more appropriate here. The sequence $t \mapsto r(s_t,a_t)$ is in $l_\infty$ and the sequence $t \mapsto \delta^t$ is in $l_1$ hence the sequence $t \mapsto \delta^t r(s_t,a_t)$ is in $l_1$.

Here is a direct proof:

Let $S_n = \sum\limits_{t=0}^n \delta^tr(s_t,a_t)$, and suppose $|r(s_t,a_t)| \le B$.

The triangle inequality gives (suppose $n \ge m$): $|S_n-S_m| = \left| \sum\limits_{t=m+1}^n \delta^tr(s_t,a_t)\right|\le \sum\limits_{t=m+1}^n \delta^t |r(s_t,a_t)| \le B\sum\limits_{t=m+1}^n \delta^t \le B { \delta^{m+1} \over 1 -\delta}$. It follows from this that $S_n$ is Cauchy and so we have $S_n \to S$ for some $S$.

We have $|S_n| = \left| \sum\limits_{t=0}^n \delta^tr(s_t,a_t)\right|\le \sum\limits_{t=0}^n \delta^t |r(s_t,a_t)| \le \sum\limits_{t=0}^\infty \delta^t |r(s_t,a_t)| \ $, taking limits gives the desired result.

$\endgroup$
2
  • $\begingroup$ Could you please show me how to apply the triangle inequality to get $ \left| \sum\limits_{t=m+1}^n \delta^tr(s_t,a_t)\right|\le \sum\limits_{t=m+1}^n \delta^t |r(s_t,a_t)|$? I do know that the triangle inequality states that $|S_n-S_m| \le |S_n| - |S_m|$ but I am not sure how to apply it in the case that the left hand side is a summation. $\endgroup$
    – mauna
    Apr 14, 2015 at 18:21
  • $\begingroup$ Let $x_t = \delta^tr(s_t,a_t)$, then $|S_n-S_m| = |x_n+x_{n-1}+\cdots + x_{m+1}| \le |x_n|+\cdots+|x_{m+1}|$. $\endgroup$
    – copper.hat
    Apr 14, 2015 at 18:36

You must log in to answer this question.

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