How can we derive the final result? I can understand the first line, but don't know how the absolute term in the summation is replaced with $2\epsilon t$.

https://www.youtube.com/watch?v=LtAt5M_a0dI&list=PL_iWQOsE6TfXxKgI1GgyV1B_Xa0DxE5eH&index=45 enter image description here

I agree with the $$\sum_{s_t}p_{\theta'}(s_t)f(s_t) \geq \sum_{s_t}\big[p_{\theta}(s_t)f(s_t) - |p_{\theta}(s_t) - p_{\theta'}(s_t)|max_{s_t}f(s_t)\big]$$ $$\because \sum_{s_t}p_{\theta}(s_t)f(s_t) = \sum_{s_t}\big(p_{\theta}(s_t) + p_{\theta'}(s_t) - p_{\theta'}(s_t) \big)f(s_t)$$ $$= \sum_{s_t}p_{\theta'}(s_t)f(s_t) + \big(p_{\theta}(s_t) - p_{\theta'}(s_t) \big)f(s_t)$$ $$ \leq \sum_{s_t}p_{\theta'}(s_t)f(s_t) + \big|p_{\theta}(s_t) - p_{\theta'}(s_t) \big|f(s_t)$$ $$ \leq \sum_{s_t}p_{\theta'}(s_t)f(s_t) + \big|p_{\theta}(s_t) - p_{\theta'}(s_t) \big|max_{s_t}f(s_t)$$

so, $$\sum_{s_t}p_{\theta'}(s_t)f(s_t) \geq \sum_{s_t}\big[p_{\theta}(s_t)f(s_t) - |p_{\theta}(s_t) - p_{\theta'}(s_t)|max_{s_t}f(s_t)\big] \geq \sum_{s_t}\big[p_{\theta}(s_t)f(s_t) - 2\epsilon t max_{s_t}f(s_t)\big] = E_{p_{\theta}(s_t)}[f(s_t)] - \sum_{s_t}2\epsilon t max_{s_t}f(s_t)$$

Here is the question. How does the lecture note remove the summation of the epsilon related term? The professor sasy, since all of them are constant (I understand $max_{s_t}f(s_t)$ is also a constant), we can write like that, but $\sum_{t=1}^{10}(t - 1) = 45 = \sum_{t=1}^{10}t - \sum_{t=1}^{10}1 = 55 - 10 = 45$. We don't write $\sum_{t=1}^{10}1 = 1$ because 1 is a constant.

The abiguous part is there is no concrete size of $s_t$ in the summation, but at least I think just removing the summation in front of the epsilon term is weird.

  • 1
    $\begingroup$ I would agree with you here, but I think the "trick" is that the first $\epsilon$ and the second are different, so for example if there are $N$ states (there is finite number of states) then the last sum would be $2 \epsilon_1 t N \max_{s_t} f(s_t)$ but you can replace this with $\epsilon_2 = N\epsilon_1$, and since $\epsilon_1$ can be picked arbitrarily small so will be $\epsilon_2$. I think the final result isn't affected but the process to get it is a bit suspicious here. $\endgroup$
    – Brale
    Jun 25, 2022 at 15:54
  • $\begingroup$ Thank you for your reply! Totally make sense for the finite case ($|s_t | = N$). Do you have any thought for the infinite case as well? So, all of the summation will be replaced with integral, then it's little bit tricky to just say $2\epsilon_1 t N max_{s_t}f(s_t)$. $\endgroup$
    – shashack
    Jun 25, 2022 at 17:24
  • $\begingroup$ I think it wouldn't be even defined in case of infinite number of states. You would have something like $\lim_{(x, y) \rightarrow (0, \infty)} xy$ which isn't defined $\endgroup$
    – Brale
    Jun 26, 2022 at 11:38
  • $\begingroup$ Hmm, I don't understand why you said $lim_{(x,y)}$. $\int_{s_t}p_{\theta'}(s_t)f(s_t) ds_t \geq E_{p_{\theta}(s_t)}[f(s_t)] - \int_{s_t}2\epsilon t max_{s_t}f(s_t) ds_t $ For the last term, it's $\int_{s_t}2\epsilon t max_{s_t}f(s_t) ds_t = 2\epsilon t max_{s_t}f(s_t)\int_{s_t} 1 ds_t$ Do you mean $\int_{s_t} 1 ds_t$ is not even defined? $\endgroup$
    – shashack
    Jun 26, 2022 at 20:55


You must log in to answer this question.