Policy Evaluation
本章主要解决如何在缺少MDP模型内部的转移函数的情况下进行Policy Evaluation。主要的方法为动态规划、蒙特卡洛（Monte Carlo Policy Evaluation）方法以及Temporal Difference（TD）。
首先回顾一下价值迭代用到的方法：
其中$V_k^{\pi}(s)$是在策略$\pi$下的$k$-horizon value的精确值；而当$k$足够大的时候又是Infinite horizon value的估计值。Policy Evaluation的核心在于以下的数学期望表达式：策略$\pi$下的状态-价值=当前状态下Return值的数学期望。
使用动态规划的Evaluation方法利用了公式：
使用这个递推表达式有以下的约束和drawback：首先是公式中的$P(s’|s, \pi(s))$需要MDP Model $M$的具体条件转化概率矩阵；第二使用Bootstrapping方法要求整个过程是马尔科夫的（也就是和状态历史无关）。事实上在绝大部分情况下我们的agent都是不知道自己所处环境的状态转移关系$P$以及奖励模型$R$的，也就是这章要讲的Model-free Policy Evaluation。
Monte Carlo Policy Evaluation
Policy Evaluation的目标是：对任意状态$s$，计算$V^{\pi}(s)=E_\pi[G_t|s_t=s]$。最简单的想法就是在当前的环境中能够进行采样，对每个采样的轨迹（trajectory）进行奖励的求和并对总体平均，这样就是一个对于$G_t$的estimate。该方法是一个通用方法，它不需要马尔科夫假设作为支撑，但它也只能被用于episodic MDP上，也就是说每个trajectory必须要有terminate的时候。通常MC方法都采用增量式的更新模式。
First-Visit MC & Every-Time MC
First-Visit MC方法仅仅更新一个新采样Episode中第一次看到的状态的价值函数，这种方法是$V^\pi$的无偏估计。Every-Time MC方法每一次在sample中看到状态都会进行更新，虽然它是$V^\pi$的有偏估计，但是它依旧是一个consistent estimator并且比First-Visit MC具有更好的均方误差（MSE）。
Variant of Every-Time MC
在Incremental MC方法当中需要维护一个数组$N(s)$来记录每个状态被访问更新的次数。定义$G_{i,t}$是在第$i$个episode的第$t$个time step的return值，我们将更新状态价值函数的表达式进行一些改写，将后面的项数看作是增量部分，那么$N(s)$就是每一次sample时更新的步幅，可以用$\alpha$表示：
当$\alpha={1\over N(s)}$时，更新的方法和Every-Visit MC相同。
当$\alpha\gt {1\over N(s)}$时，倾向于忘记之前的data sample，而对最近的sample较为敏感。这种更新策略对于Non-stationary domain的问题比较有效。
Key Limitations of MC
- 首先MC是一个high-variance的方法，通常需要大量的sampled data才能够解决这个问题。
- 需要Episodic Setting，轨迹必须终结。
Temporal Difference Learning
TD-learning是一个结合了MC方法和DP方法的Policy Evaluation策略，它采用了bootstrapping的思想，能够支持Infinite-Horizon的问题以及能够做到在每个step取得tuple $(s,a,r,s’)$后都直接进行更新。
MC方法中，我们用来更新价值的公式为：
我们知道$G$是状态价值函数的estimate，要拿到这个值必须要在episode结束之后。观察Bellman Equation的后半部分，这里的形式是利用MDP model的状态转移概率来写出精确的数学期望，但是在sampling的时候后面的部分会以sample的形式作为下一个状态和reward返回给agent，因此我们可以这个estimate来对Return值$G$进行bootsrappinng
我们将TD error定义为更新的数值：
Evaluating Algorithms
比较DP/MC/TD三个方法的性质：
| DP | MC | TD | |
|---|---|---|---|
| Support Model-Free? | T | T | |
| Support Non-episodic? | T | T | |
| Support Non-Markov? | T | ||
| Unbiasd Estimate? | T (First-Visit MC) |
评价RL算法的重要指标：是否是Biased Estimate？更新的方差大小？数据效率和计算效率？
MC可以是无偏估计（取决于具体状态函数的更新形式），但该方法具有较高的variance；优点是即便在Function Approximation也能够收敛。
TD虽然是一个有偏估计，但是却有更小的variance，TD(0)只保证在Tabular Representation下收敛，而不保证在Function Approximation能够收敛。
Batch MC & Batch TD
Batch solution for finite dataset是一种离线算法，能够提高data efficiency。对于已经sample得到的K个episodes，使用MC或TD算法对这K个episodes进行resample并更新参数即可构成该离线算法。
课程例举了一个实例来说明Batch MC和Batch TD的最终优化结果是不同的。
课程中认为Batch MC是收敛于min MSE，分析如下：给定一个确定的episode set，我们可以算出什么时候Batch MC的更新为0，也就是说最终每个状态的价值值会收敛到sample出的batch的该状态的平均Return值。这和优化min MSE的结果是相同的（优化函数的导数为0）。
而对于Batch TD(0)方法来说，它最终converge到的是“DP policy $V^\pi$ for the MDP with the maximum likelihood model estimates”.极大似概率的MDP model为以下：
也就是说在给定的sample集上我们能够根据频率构建出关于MDP model的一个估计（利用如上公式），Batch TD(0)收敛到的点就是这个估计的DP policy。同样的分析最终的收敛点为：
而我们知道等式右边的平均项其实就是reward和带状态转移概率的价值函数的估计。
Some Important Properties
对于TD和MC方法，更新的时间复杂度关于episode长度$L$来说都是$O(L)$。MC比较TD来说它的data efficiency更高一些，但是TD利用了马尔科夫性质。当我们解决具有马尔科夫性质的问题时，利用这个性质往往会比较有帮助。关于为什么TD利用了马尔科夫性质，我的理解是下面的近似替换表达式认为在当前time step的return value = 当前的immediate reward + 下一状态的state value是历史无关的，只和当前状态有关。
*MC Off-Policy Evaluation
当前的policy evaluation都是基于sampling的，是on-policy的方法，on-policy简单来说就是在线跑算法并且在线evaluate。所以本章研究的是如何利用现有的data进行policy evaluation。现在formulate MC Off-Policy Evaluation的问题。
- Aim - estimate value of policy $\pi_1$, $V^{\pi_1}(s)$, givein episodes generated under behavior policy $\pi_2$.
- $s_1, a_1, r_1, s_2, a_2, r_2, \ldots$ where the actions are sampled from $\pi_2$
- If $\pi_2$ is stochastic, can often use it to estimate the value of an alternative policy (formal conditions to follow)
- No requirement that have a model nor that state is Markov.
Off-policy evaluation存在的主要问题就是两个不同的policy产生出episode和reward的distribution不同。重要性采样（Importance Sampling）的目标是估计一个函数$f(x)$在某一个概率分布$p(x)$下的数学期望，但是现在只有从另一个分布$q(s)$采样出的数据点$x_1,x_2,\ldots,x_n$。首先我们可以很容易地求出这个函数在$q(s)$上的数学期望。
假设$h_j$为所有sample点中的第$j$条轨迹：
那么根据马尔科夫假设以及乘法原理，得出这条轨迹出现的概率为每个状态转移的乘积：
虽然整体问题是Model-Free的环境，但从上式得知，导致两个不同的policy分布的地方仅仅在于这策略本身决定action的部分。所以我们容易求出两个策略下轨迹的概率比值，从而得出需要的近似，其中$G(h_j)$为轨迹$h_j$的return value。
问题：课程中说这个推导过程不需要马尔科夫假设。但是上面将概率写成了只和当前状态相关的概率连乘积不是已经用到了马尔科夫假设了吗？需要进一步思考和验证。