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
$\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$
  • $\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 '15 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 '15 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.