前言

你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdown的基本语法知识。

Analysis

Q1.

分析：给出的条件实际上是Lecture2里提到的General Analysis的弱化版本，在Lecture中，实际上规定了在每一个时间步t，对当前时间步任意状态$s_t$都有${\pi }_{\theta }(a_t\ne {\pi }^{\ast }(s_t)|s_t)\le ϵ$，而在这个问题中，该条件弱化为了对任意时间步、任意状态的期望，这实际上是两个期望，一个是对时间的平均（也可以理解为期望），另一个是对每个时间下状态的期望。根据下面的Hint，提示我们大概要构造期望，并用到一个和概率有关的union bound不等式，下面我们来求解。

首先我们模仿Lecture的内容，对于一个时间步骤$t$，我们任取一个状态$s_t$，为了方便后面的书写，我们先定义一个概率，即截至t时间步内，策略${\pi }_{\theta }$与最优策略完全相同的概率:
$$p_{correct}=(1-Pr(\bigcup _{t=1}^t{\pi }_{\theta }(a_t)\ne {\pi }^{\ast }(a_t)))\text{\hspace{1em}(1)}$$
从而得到以下概率表示，这实际上是Lecture的公式的变形。
$$p_{{\pi }_{\theta }}(s_t)=p_{correct}{p}_{{\pi }^{\ast }}(s_t)+(1-p_{correct})p_{wrong}(s_t)\text{\hspace{1em}(2)}$$
因此，采用与Lecture中相同的方式，我们可以得到：
$$|p_{{\pi }_{\theta }}(s_t)-p_{{\pi }^{\ast }}(s_t)|=(1-p_{correct})|p_{wrong}(s_t)-p_{{\pi }^{\ast }}(s_t)|\text{\hspace{1em}(3)}$$
这里我们就已经得到了一个初步的表达式了，根据绝对值的性质，证明结论里的常数2已经凑出来了（$|p_{wrong}(s_t)-p_{{\pi }^{\ast }}(s_t)|\le 2$)。我们先将这个搁置一边，这里我们先尝试分析$p_{correct}$，根据Hint2有
$$p_{correct}\ge 1-\sum _{t=1}^{t}Pr({\pi }_{\theta }(a_t)\ne {\pi }^{\ast }(a_t))=1-\sum _{t=1}^{t}p(s_t){\pi }_{\theta }(a_t\ne {\pi }^{\ast }(s_t)|s_t)\text{\hspace{1em}(4)}$$
从而我们就得到:
$$|p_{{\pi }_{\theta }}(s_t)-p_{{\pi }^{\ast }}(s_t)|\le (\sum _{t=1}^{t}p(s_t){\pi }_{\theta }(a_t\ne {\pi }^{\ast }(s_t)|s_t))|p_{wrong}(s_t)-p_{{\pi }^{\ast }}(s_t)|\text{\hspace{1em}(5)}$$
如果左右对这时，再利用前文提到的前置条件，并取t=T即可得到。
不过说实话，这里其实存在一些细节问题，比如eq4的化简中，实际上暗含着一个状态序列$(s_1,s_2,..,s_t)$，也就是说，实际上我们是假定了这个序列是前取好的。最后一步对状态求和的过程中，我不确定这种提前取好的序列是否能说的通。这里对于结果有异议的同学，或许可以想一下这个思路。对任何一个时间步t，实际上如果我们取遍其$s_t$，那么都应该是等于期望的，因此最后一步的求和可能能解释的通是一个期望。

Q2.

（1）如果reward只取决于$s_t$，则可以化简为:
$$J(\pi )=\sum _{i=1}^T{E}_{p_{\pi (s_t)}}r(s_t)=E_{p_{\pi (s_T)}}r(s_T)$$
因此，有：
$$J({\pi }^{\ast })-J({\pi }_{\theta })=E_{p_{{\pi }^{\ast }(s_T)}}r(s_T)-E_{p_{{\pi }_{\theta }(s_T)}}r(s_T)\le 2ϵT{R}_{max}=\mathcal{O}(Tϵ)$$
(2)同理，因为有求和，所以是$\mathcal{O}(T^2ϵ)$

Code

待更新