常见的离散分布和连续分布

常见的离散分布有伯努利分布，二项分布，泊松分布，几何分布，多项分布。

伯努利分布

定义

伯努利实验是单次随机试验，只有成功和失败两种结果。它服从的分布叫做伯努利分布，伯努利分布也叫两点分布或者$0-1$分布。

概率密度函数

期望和方差

二项分布

定义

如果某个试验是伯努利试验，事件A在一次试验中发生的概率是$p$，现在独立的重复该试验$n$次，用$X$表示事件A在发生的次数，$X=i$的所有的可能取值为$0,1,\cdots,n$。$X$所服从的分布就叫二项分布，它的计算公式如下：
$$P(X=i|\theta)= \begin{pmatrix}n\\ i\end{pmatrix}p^i(1-p)^{n-i}$$
二项分布有两个条件，一个是独立的进行$n$次试验，相互之间互不干扰，一个是同分布，即所有试验中A发生的概率都是相等的。

概率密度函数

期望和方差

几何分布和负二项分布

定义

概率密度函数

期望和方差

多项分布

定义

如果把事件A的取值推广到多个，而不是两个，独立进行$n$次实验，求$X=i$的所有可能的取值就是一个多项分布。比如掷骰子$100$次，出现$50$次$1$，$30$次$2$和$20$次$3$的概率就是一个多项分布。
多项分布的计算公式如下：
$$P(x_1,x_2,\cdots, x_k; n, p_1,p_2, \cdots,p_k) = \frac{n!}{x_1!\cdots x_k!}p_1^{x_1}\cdots p_k^{x_k},\sum_{i=1}^{k}p_i = 1$$

概率密度函数

期望和方差

泊松分布

定义

概率密度函数

期望和方差

Gamma函数

Gamma函数的定义：
$$\Gamma(x) = \int_0^{\infty}t^{x-1}e^{-t}dt$$
通过分部积分，可以推导出来这个函数有如下的性质：
$$\Gamma(x+1) = x\Gamma(x)$$
可以证明，$\Gamma(x)$函数是阶乘在实数集合上的扩展：
$$\Gamma(n) = (n-1)!$$
只不过这里是$(n-1)!$，而不是$n!$。事实上，如果把$t^{x-1}$替换成$t^x$就能得到$\Gamma(n) = n!$，但是欧拉不知道为什么，还是使用了$t^{x-1}$。

Beta分布

定义

我们常用的贝叶斯估计，是将先验概率转化为了后验概率。。比如说抛硬币，我们通常假设硬币是公平的，也就是说正面向上的概率是$0.5$，这个先验概率就是$0.5$，然后根据观测到的事件将先验概率转化为后验概率。
这里的先验分布我们取得是一个值，如果不取一个值，而是选择一个分布呢？比如Beta分布：
$$f(\theta;\alpha, \beta) = \frac{1}{B(\alpha, \beta)}\theta^{\alpha-1}(1-\theta)^{\beta-1},\alpha\gt 0,\beta\gt 0, x\in \left[0,1\right]$$
其中，$\frac{1}{B(\alpha, \beta)} = \frac{\Gamma(\alpha+\beta)}{\Gamma(\alpha)\Gamma(\beta)}$

然后使用贝叶斯推断，得到一个后验概率分布。Beta分布有一个神奇的特点就是使用贝叶斯推断得到的后验概率也是一个Beta分布，这个特点叫做共轭分布，接下来就会介绍。

特点

Beta分布可以表示各种各种的曲线，从而也能表示各种各样的先验分布。

均值和方差

Beta分布的均值是$\frac{\alpha}{\alpha+\beta}$。

共轭先验分布

在贝叶斯概率理论中，如果后验概率和先验概率服从相同类型的分布，那么先验分布和后验分布被叫做共轭分布。同时，先验分布叫做似然函数的共轭先验分布。
Beta分布就是一个共轭分布，但是有一个前提，就是数据符合二项分布的时候，参数的先验和后验都可以是Beta分布，也称Beta分布是二项分布的共轭先验分布，似然函数是二项分布。

证明Beta分布是二项分布的共轭先验分布

已知条件：先验是Beta分布，数据服从二项分布
根据贝叶斯公式，后验概率的计算公式如下：
$$P(\theta|data) = \frac{P(data|\theta)P(\theta)}{P(data)} \propto P(data|\theta)P(\theta)$$
而$P(data|\theta)$可以根据似然函数的定义来计算$L(\theta|data) = P(data|\theta)$，又因为数据服从二项分布，有$P(data|\theta) \propto \theta^z(1-\theta)^{n-z}$，而Beta分布有$P(\theta) = Beta(\theta;\alpha,\beta) \propto \theta^{(\alpha-1)}(1-\theta)^{\beta-1}$，而$P(data)$与$\theta$无关，所以
$$P(\theta|data) \propto P(data|\theta)P(\theta) = \theta^{z+\alpha-1}(1-\theta)^{\beta+n-z-1}$$
也就是说后验分布服从Beta$(\alpha+z, \beta+n-z)$，得证。

狄利克雷分布

定义

参考文献

1.http://bloglxm.oss-cn-beijing.aliyuncs.com/lda-LDA数学八卦.pdf
2.https://zhuanlan.zhihu.com/p/49267988

概率

概率，反映随机事件出现的可能性（likelihood)大小。随机事件是指在相同条件下，可能出现也可能不出现的事件。

频率学派vs贝叶斯学派

频率学派和贝叶斯学派在探讨不确定性这件事的出发点不同。
频率学派认为世界是确定的，直接为事件本身建模，某件事情发生的可能性是固定的。给定频率的取值空间，频率学派相信其中只有一个值是真实的概率，而我们要做的就是找出这个值。于是就有了最大似然估计和置信区间等等，这些方法表示的有多大可能性找到这个值。

而贝叶斯学派并不是从事件本身出发的，他们认为世界是不确定的，从观察者角度出发，观察者获得的信息不同，世界是不确定的。贝叶斯学派认为频率学派中的随机事件只是观察者不知道结果，随机性指的是观察者猜测结果的可能性，是不断变化的。频率学派的概率描述的是事件本身，而贝叶斯学派的概率描述的是观测者看到新的观测之后对某个观测的猜测。
贝叶斯学派认为这个参数的取值空间中，任意一个参数都有可能是模型实用的值，只是取值概率不同而已。他们通过先验分布和后验分布这样的概念，找到参数取某个值的概率。最大后验估计就是贝叶斯学派参数估计的常用方法，写出关于$\theta$的函数，然后令偏导等于$0$即可。原来我有个问题，就是先验分布是一个分布，而为什么最大后验求出来的是一个值，这是因为这个分布也是$\theta$的函数，求导之后，解$\theta$就是一个值啊。。后验分布是一个分布，而最大后验估计求出来的是一个$\theta$的取值。

先验，后验，似然，条件概率

先验和后验

假设的概率，或者给出的概率。
比如给出一个硬币，求随机投掷一次正面向上的概率。。在不知道任何其他条件的情况下，我们假设它是公平的，这就是一个先验。然后随机投掷了十次，发现十次正面都是向上的，显然，这个硬币不是公平的，根据这个事件我们可以修改这个硬币正面向上的概率，这时候得到的概率就是后验概率。

似然

用$\theta$表示一个随机过程的参数，观测到的事件是$O$。$P(O|\theta)$是这件事发生的概率。然而，在现实生活中，我们常常是不知道$\theta$的，我们只能根据观测到的$O$，计算$P(\theta|O)$。而估计$P(\theta|O)$最常用的方法就是最大似然估计，即寻找使得当前观测$O$出现概率最大化的参数。似然的定义是给定观测$O$关于未知参数$\theta$的函数：
$$L(\theta|O) = P(O|\theta)$$
$L(\theta|O)$被称为似然，左面是似然，右面是概率密度（函数）。这两个函数从定义上来说是完全不同的对象，前者是$\theta$的函数，后者是$O$的函数，这里的等号意思是函数值相等，而不是两个函数本身就是同一个函数。

条件概率

似然就是一种条件概率。

参数估计方法

最大似然估计，贝叶斯估计和最大后验估计

最大似然估计

最大似然估计是频率学派的观点，它的基本思想是参数$\theta$是客观存在的，只是未知而已。它的目标是调整模型参数使得样本出现的概率最大化，求得的参数就是待估计参数。
用公式表示如下所示：
$$L(\theta|x) = f(x|\theta) = f(x_1, \cdots, x_n|\theta) = \prod_{i=1}^n f(x_i|\theta)$$
$$\hat{\theta}_{mle} = \arg \max_{\theta} L(\theta|x)$$

贝叶斯估计

贝叶斯估计是贝叶斯学派的观点，它的基本思想是参数$\theta$是随机的，也是个随机变量，因此只能根据样本估计参数$\theta$的分布。贝叶斯估计可以看作是，在假定$\theta$服从某个先验分布前提下，根据样本信息去校正先验分布，得到后验分布。由于后验分布是一个条件分布，通常我们取后验分布的期望作为参数的估计值。
用公式表示如下所示：
$$\pi(\theta|x) = \frac{f(x|\theta)\pi(\theta)}{m(x)} = \frac{f(x|\theta)\pi(\theta)}{\int f(x|\theta)\pi(\theta) d(\theta)} $$
$$\hat{\theta}_{be} = \mathbb{E}\left[ \pi(\theta|x)\right]$$

最大后验估计

而最大后验估计是贝叶斯估计的一种实现。最大后验估计的基本思想采样了极大似然估计的思想，最大后验估计的目标是调整模型参数使得样本出现的后验概率最大，和最大似然估计的区别是加了一个先验分布。
$$\hat{\theta}_{map} = \arg \max_{\theta} \pi(\theta|x) = \arg \max_{\theta} \frac{f(x|\theta)\pi(\theta)}{m(x)} = \arg\max_{\theta}f(x|\theta)\pi(\theta)$$
对其同取$\log$，得到：
$$\hat{\theta}_{map} = \arg\max_{\theta}f(x|\theta)\pi(\theta) =\arg\max_{\theta}(\log f(x|\theta) + \log \pi(\theta)) $$
所以MAP可以看成带有正则化项的MLE。

贝叶斯分类器（朴素贝叶斯）和参数估计（贝叶斯估计等）的关系

参数估计（贝叶斯估计等）用来求解贝叶斯分类器（朴素贝叶斯）的参数。

参考文献

1.陈希孺《概率论与统计》
2.https://www.zhihu.com/question/20587681/answer/41436978
3.https://zhuanlan.zhihu.com/p/40024110

n-step Bootstrapping

这章要介绍的n-step TD方法，将MC和one-step TD用一个统一的框架整合了起来。在一个任务中，两种方法可以无缝切换。n-step方法生成了一系列方法，MC在一头，one-step在另一头。最好的方法往往不是MC也不是one-step TD。One-step TD每隔一个timestep进行bootstrapping，在许多需要及时更新变化的问题，这种方法很有用，但是一般情况下，经历了长时间的稳定变化之后，bootstrap的效果会更好。N-step TD就是将one-step TD方法中time interval的one改成了n。N-step方法的idea和eligibility traces很像，eligibility traces同时使用多个不同的time intervals进行bootstarp。

n-step TD Prediction

对于使用采样进行policy evaluation的方法来说，不断使用policy $\pi$生成sample episodes，然后估计$v_{\pi}$。MC方法用的是每一个episode中每个state的return进行更新，即无穷步reward之和。TD方法使用每一个state执行完某一个action之后的下一个reward加上下一个state的估计值进行更新。N-step方法使用的是每一个state接下来n步的reward之和加上第n步之后的state的估计值。相应的backup diagram如下所示：

n-step方法还是属于TD方法，因为n-step的更新还是基于时间维度上不同estimate的估计进行的。

n-step updates are still TD methods because they still chagne an erlier estimate based on how it differs from a later estimate. Now the later estimate is not one step later, but n steps later。

正式的，假设$S_t$的estimated value是基于state-reward sequence $S_t, R_{t+1}, S_{t+1}, R_{t+2}, \cdots, R_T,S_T$得到的。
MC方法更新基于completer return：
$$G_T = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{T-t-1}R_T \tag{1}$$
one-step TD更新基于one-step return：
$$G_{t:t+1} = R_{t+1}+ \gamma V_t(S_{t+1}) \tag{2}$$
two-step TD更新基于two-step return：
$$G_{t:t+2} = R_{t+1}+ \gamma V_t(S_{t+1}) + \gamma^2 V_{t+1}(S_{t+2}) \tag{3}$$
n-step TD更新基于n-step return：
$$G_{t:t+n} = R_{t+1}+ \gamma V_t(S_{t+1}) + \gamma^2 V_{t+1}(S_{t+2}) +\cdots + \gamma^{n-1} R_{t+n} + \gamma^n V_{t+n-1}(S_{t+n}), n\ge1, 0\le t\le T-n \tag{4}$$
所有的n-step方法都可以看成使用n steps的rewards之和加上$V_{t+n-1}(S_{t+n})$近似其余项的rewards近似return。如果$t+n \ge T$时，$T$步以后的reward以及estimated value当做$0$，相当于定义$t+n \ge T$时，$G_{t:t+1} = G_t$。
当$n > 1$时，只有在$t+n$时刻之后，$R_{t+n},S_{t+n}$也是已知的，所以不能使用real time的算法。使用$t+n-1$时刻的$V$近似估计$V_{t+n-1}(S_{t+n})$，将n-step return当做n-step TD的target，得到的更新公式如下：
$$V_{t+n}(S_t) = V_{t+n-1} (S_t) + \gamma(G_{t:t+n} - V_{t+n-1}(S_{t}))\tag{5}$$
当更新$V_{t+n}(S_t)$时，所有其他states的$V$不变，用公式来表示是$V_{t+n}(s) = V_{t+n-1}(s), \forall s\neq S_t$。在每个episode的前$n-1$步中，不进行任何更新，为了弥补这几步，在每个episode结束以后，即到达terminal state之后，仍然继续进行更新，直到下一个episode开始之前，依然进行updates。完整的n-step TD算法如下：

n-step TD prediction伪代码

n-step TD估计$V\approx v_{\pi}$
输入：一个policy $\pi$
算法参数：step size $\alpha \in (0, 1]$，正整数$n$
随机初始化$V(s), \forall s\in S$
Loop for each episode
$\qquad$初始化 $S_0 \neq terminal$
$\qquad$$T\leftarrow \infty$
$\qquad$Loop for $t=0, 1, 2, \cdots:$
$\qquad$ IF $t\lt T$, THEN
$\qquad\qquad$ 根据$\pi(\cdot|S_t)$执行action
$\qquad\qquad$ 接收并记录$R_{t+1}, S_{t+1}$
$\qquad\qquad$ 如果$S_{t+1}$是terminal ，更新$T\leftarrow t+1$
$\qquad$ END IF
$\qquad$ $\tau \leftarrow t - n + 1, \tau$是当前更新的时间
$\qquad$ If $\tau \ge 0$, then
$\qquad\qquad$ $G\leftarrow \sum_{i=\tau+1}^{min(\tau+n, T)} \gamma^{i-\tau -1} R_i$
$\qquad\qquad$ 如果$\tau+n \lt T$，那么$G\leftarrow G+ \gamma^n V(S_{\tau+n})$
$\qquad\qquad$ $V(S_{\tau}) \leftarrow V(S_{\tau}) +\alpha [G-V(S_{\tau})]$
$\qquad$ End if
Until $\tau = T-1$
n-step return有一个重要的属性叫做error reduction property，在最坏的情况下，n-step returns的期望也是一个比$V_{t+n-1}$更好的估计：
$$max_{s}|\mathbb{E}_{\pi}\left[G_{t:t+n}|S_t = s\right]- v_{\pi}(s)| \le \gamma^n max_s | V_{t+n-1}(s)-v_{\pi}(s)| \tag{6}$$
所以所有的n-step TD方法都可以收敛到真实值，MC和one-step TD是其中的一种特殊情况。

n-step Sarsa

介绍完了prediction算法，接下来要介绍的就是control算法了。因为TD方法是model-free的，所以，还是要估计action value function。上一章介绍了one-step Sarsa，这一章自然介绍一下n-step Sarsa。n-step Sarsa的backup图如下所示：

就是将n-step TD的state换成state-action就行了。定义action value的n-step returns如下：
$$G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+1} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n Q_{t+n-1}(S_{t+n},A_{t+n}), n\ge 1, 0\le t\le T-n\tag{7}$$
如果$t+n\ge T$，那么$G_{t:t+n} = G_t$。
完整的$n$-step Sarsa如下所示：

n-step Sarsa算法伪代码

n-step Sarsa算法，估计$Q\approx q_{*}$
随机初始化$Q(s,a),\forall s\in S, a\in A$
初始化$\pi$是相对于$Q$的$\epsilon$-greedy policy，或者是一个给定的不变policy
算法参数：step size $\alpha \in (0,1], \epsilon \gt 0$，一个正整数$n$
Loop for each episode
$\qquad$初始化$S_0\neq$ terminal
$\qquad$ 选择action $A_0= \pi(\cdot| S_0)$
$\qquad$ $T\leftarrow \infty$
$\qquad$ Loop for $t=0,1,2,\cdots$
$\qquad\qquad$ If $t\lt T$,then:
$\qquad\qquad\qquad$ 采取action $A_t$，
$\qquad\qquad\qquad$ 接收rewared $R_{t+1}$以及下一个state $S_{t+1}$
$\qquad\qquad$ 如果$S_{t+1}$是terminal，那么
$\qquad\qquad$ $T\leftarrow t+1$
$\qquad\qquad$ 否则选择$A_{t+1} = \pi(\cdot|S_{t+1})$
$\qquad\qquad$End if
$\qquad\qquad$ $\tau \leftarrow t-n+1$
$\qquad\qquad$ If $\tau \ge 0$
$\qquad\qquad\qquad$ $G\leftarrow \sum_{i=\tau +1}^{min(\tau+n, T)} \gamma^{i-\tau -1} R_i$
$\qquad\qquad\qquad$ If $\tau+n \le T$,then
$\qquad\qquad\qquad$ $G\leftarrow G+\gamma^n Q(S_{\tau+n}, A_{\tau+n})$
$\qquad\qquad\qquad$ $Q(S_{\tau}, Q_{\tau}) \leftarrow Q(S_{\tau}, Q_{\tau}) + \alpha \left[G-Q(S_{\tau}, Q_{\tau})\right]$
$\qquad\qquad$End if
$\qquad$ Until $\tau =T-1$

n-step Expected Sarsa

n-step Expected Sarsa的n-step return定义为：
$$G_{t:t+n} = R_{t+1} +\gamma R_{t+1} + \cdots +\gamma^{n-1} R_{t+n} + \gamma^n \bar{V}_{t+n-1}(S_{t+n}) \tag{8}$$
其中$\bar{V}_t(s) = \sum_{a}\pi(a|s) Q_t(s,a), \forall s\in S$
如果$s$是terminal，它的期望是$0$。

n-step Off-policy Learning

Off-policy算法使用behaviour policy采样的内容得到target policy的value function，但是需要使用他们在不同policy下采取某个action的relavtive probability。在$n$-step方法中，我们感兴趣的只有对应的$n$个actions，所以最简单的off-policy $n$-step TD算法，$t$时刻的更新可以使用importance sampling ratio $\rho_{t:t+n-1}$：
$$V_{t+n}(S_t) = V_{t+n-1} S_t + \alpha \rho_{t:t+n-1}\left[G_{t:t+n} - V_{t+n-1}(S_t)\right], 0\le t\le T \tag{9}$$
$\rho_{t:t+n-}$计算的是从$A_t$到$A_{t+n-1}$这$n$个action在behaviour policy和target policy下的relative probability，计算公式如下：
$$\rho_{t:h} = \prod_{k=t}^{min(h, T-1)} \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \tag{10}$$
如果$\pi(A_k|S_k) = 0$，那么对应的$n$-step return对应的权重就应该是$0$，如果policy $pi$下选中某个action的概率很大，那么对应的return就应该比$b$下的权重大一些。因为在$b$下出现的概率下，很少出现，所以权重就该大一些啊。如果是on-policy的话，importance sampling ratio一直是$1$，所以公式$9$可以将on-policy和off-policy的$n$-step TD概括起来。同样的，$n$-step的Sarsa的更新公式也可以换成：
$$Q_{t+n}(S_t,A_t) = Q_{t+n-1}(S_t,A_t) + \alpha \rho_{t+1:t+n}\left[G_{t:t+n} - Q_{t+n-1} (S_t,A_t)\right], 0\le t\le T \tag{11}$$
公式$11$中的importance sampling ratio要比公式$9$中计算的晚一步。这是因为我们是在更新一个state-action pair，我们并不关心有多大的概率选中这个action，我们现在已经选中了它，importance sampling只是用于后续actions的选择。这个解释也让我理解了为什么Q-learning和Sarsa为什么没有使用importance sampling。完整的伪代码如下。

Off-policy $n$-step Sarsa 估计$Q$

输入：任意的behaviour policy $b$, $b(a|s)\gt 0, \forall s\in S, a\in A$
随机初始化$Q(s,a), \forall s\in S, a\in A$
初始化$\pi$是相对于$Q$的greedy policy
算法参数：步长$\alpha \in (0,1]$，正整数$n$
Loop for each episode
$\qquad$初始化$S_0\neq terminal$
$\qquad$选择并存储$A_0 \sim b(\cdot|S_0)$
$\qquad T\leftarrow \infty$
$\qquad$Loop for $t=0,1,2,\cdots$
$\qquad\qquad$IF $t\lt T$,then
$\qquad\qquad\qquad$执行action $A_t$，接收$R_{t+1}, S_{t+1}$
$\qquad\qquad\qquad$如果$S_{t+1}$是terminal，那么$T\leftarrow t+1$
$\qquad\qquad\qquad$否则选择并记录$A_{t+1} \sim b(\cdot| S_{t+1})$
$\qquad\qquad$END IF
$\qquad\qquad \tau \leftarrow t-n +1$ (加$1$表示下标是从$0$开始的)
$\qquad\qquad$ IF $\tau \ge 0$
$\qquad\qquad\qquad \rho \leftarrow \prod_{i=\tau+1}^{min(\tau+n,T)} \frac{\pi(A_i|S_i)}{b(A_i|S_i)}$ （计算$\rho_{\tau+1:\tau+n}$，这里是不是写成了Expected Sarsa公式）
$\qquad\qquad\qquad G\leftarrow \sum_{i=\tau+1}^{min(\tau+n, T)}\gamma^{i-\tau -1}R_i$ （计算$n$个reward, $R_{\tau+1}+\cdots+R_{\tau+n}$）
$\qquad\qquad\qquad$如果$\tau+n \lt T$，$G\leftarrow G + \gamma^n Q(S_{\tau+n},A_{\tau+n})$ （因为没有$Q(S_T,A_T)$）
$\qquad\qquad\qquad Q(S_{\tau}, A_{\tau}) \leftarrow Q(S_{\tau}, A_{\tau})+\alpha \rho \left[G-Q(S_{\tau}, A_{\tau})\right]$（计算$Q(S_{\tau+n},A_{\tau+n})$）
$\qquad\qquad\qquad$确保$\pi$是相对于$Q$的greedy policy
$\qquad\qquad$ END IF
$\qquad$Until $\tau = T-1$
上面介绍的算法是$n$-step的Sarsa，计算importance ratio使用的$\rho_{t+1:t+n}$，$n$-step的Expected Sarsa计算importance ratio使用的是$\rho_{t+1:t+n-1}$，因为在估计$\bar{V}_{t+n-1}$时候，考虑到了last state中所有的actions。

$n$-step Tree Backup算法

这一章介绍的是不适用importance sampling的off-policy算法，叫做tree-backup algorithm。如下图所示，是一个$3$-step的tree-backup diaqgram。
沿着中间这条路走，有三个sample states和rewards以及两个sample actions。在旁边的是没有被选中的actions。对于这些没有选中的actions，因为没有采样，所以使用bootstrap计算target value。因为它的backup diagram有点像tree，所以就叫做tree backup upadte。或者更精确的说，backup update使用的是所用tree的叶子结点action value的估计值进行计算的。非叶子节点的action对应的是采样的action，不参与更新，所有叶子节点对于target的贡献都有一个权重正比于它在target policy下发生的概率。在$S_{t+1}$处的除了$A_{t+1}$之外所有action权重是$\pi(a|S_{t+1})$，$A_{t+1}$一点贡献没有；在$S_{t+2}$处所有没有被选中的action的权重是$\pi(A_{t+1}|S_{t+1})\pi(a’|S_{t+2})$；在$S_{t+3}$处所有没有被选中的action的权重是$\pi(A_{t+1}|S_{t+1})\pi(A_{t+2}|S_{t+2})\pi(a’’|S_{t+3})$
one-step Tree backup 算法其实就是Expected Sarsa：
$$G_{t:t+1} = R_{t+1} + \gamma \sum_a\pi(a|S_{t+1})Q(a, S_{t+1}), t\lt T-1 \tag{12}$$
two-step Tree backup算法return计算公式如下：
\begin{align*}
G_{t:t+2} &= R_{t+1} + \gamma \sum_{a\neq A_{t+1}}\pi(a|S_{t+1})Q(a, S_{t+1}), t\lt T-1$ + \gamma\pi(A_{t+1}|S_{t+1})(R_{t+2} + \sum_{a} \pi(a|S_{t+2})Q(a, S_{t+2})\\
&=R_{t+1} + \gamma \sum_{a\neq A_{t+1}}\pi(a|S_{t+1})Q(a, S_{t+1}), t\lt T-1$ + \gamma\pi(A_{t+1}|S_{t+1})G_{t+1:t+2}, t \lt T-2
\end{align*}
下面的形式给出了tree-backup的递归形式如下：
$$G_{t:t+n} = R_{t+1} + \gamma \sum_{a\neq A_{t+1}}\pi(a|S_{t+1})Q(a,S_{t+1}) + \gamma\pi(A_{t+1}|S_{t+1}) G_{t+1:t+n}, n\ge 2, t\lt T-1, \tag{13}$$
当$n=1$时除了$G_{T-1:t+n} = R_T$，其他的和式子$12$一样。使用这个新的target代替$n$-step Sarsa中的target就可以得到$n$-step tree backup 算法。
完整的算法如下所示：

$n$-step Tree Backup 算法

随机初始化$Q(s,a),\forall s\in S, a\in A$
初始化$\pi$是相对于$Q$的$\epsilon$-greedy policy，或者是一个给定的不变policy
算法参数：step size $\alpha \in (0,1], \epsilon \gt 0$，一个正整数$n$
Loop for each episode
$\qquad$初始化$S_0\neq$ terminal
$\qquad$ 根据$S_0$随机选择action $A_0$
$\qquad$ $T\leftarrow \infty$
$\qquad$ Loop for $t=0,1,2,\cdots$
$\qquad\qquad$ If $t\lt T$,then:
$\qquad\qquad\qquad$ 采取action $A_t$，
$\qquad\qquad\qquad$ 接收rewared $R_{t+1}$以及下一个state $S_{t+1}$
$\qquad\qquad$ 如果$S_{t+1}$是terminal，那么
$\qquad\qquad$ $T\leftarrow t+1$
$\qquad\qquad$ 根据$S_{t+1}$随机选择action $A_{t+1}$
$\qquad\qquad$End IF
$\qquad\qquad$ $\tau \leftarrow t-n+1$
$\qquad\qquad\qquad$ IF $\tau+n\ge T$ then
$\qquad\qquad\qquad\qquad G\leftarrow R_T$
$\qquad\qquad\qquad$ ELSE
$\qquad\qquad\qquad\qquad G\leftarrow R_{t+1}+\gamma \sum_a\pi(a|S_{t+1})Q(a, S_{t+1})$
$\qquad\qquad\qquad$ END IF
$\qquad\qquad\qquad$Loop for $k = min(t, T-1)$ down $\tau+1$
$\qquad\qquad\qquad G\leftarrow R_k+\gamma^n\sum_{a\neq A_k}\pi(a|S_k)Q(a, S_k) + \gamma \pi(A_k|S_k) G$
$\qquad\qquad\qquad$ $Q(S_{\tau}, Q_{\tau}) \leftarrow Q(S_{\tau}, Q_{\tau}) + \alpha \left[G-Q(S_{\tau}, Q_{\tau})\right]$
$\qquad\qquad$End if
$\qquad$ Until $\tau =T-1$

$n$-step $Q(\sigma)$

现在已经讲了$n$-step Sarsa，$n$-step Expected Sarsa，$n$-step Tree Backup，$4$-step的一个backup diagram如下所示。它们其实有很多共同的特性，可以用一个框架把它们统一起来。
具体的算法就不细说了。

参考文献

1.《reinforcement learning an introduction》第二版
2.https://stats.stackexchange.com/questions/335396/why-dont-we-use-importance-sampling-for-one-step-q-learning

代码解析

参考文献

简介

本文主要介绍了deterministic policy gradient算法。它属于policy gradient的一种，只不过是将stochastic policy改成了deterministic policy，和stochastic policy一样，deterministic policy也有相应的deterministic policy gradient theorem。
实际上deterministic policy gradient是action value function的gradient的期望，这让deterministic policy gradient比stochastic policy gradient要更efficiently。还介绍了保证足够的exploration的off-policy actor-critic算法学习determinitic target policy。

stochastic policy gradient vs deterministic policy gradiet

sotchastic policy gradient

Policy gradient的basic idea是用参数化的probability distribution $\pi_\theta(a|s) = \mathbb{P}\left[a|s,\theta\right]$表示policy，在state $s$处根据$\theta$表示的policy $\pi$随机选择action $a$。Policy gradient通过对policy 进行采样，根据stochastic policy gradient theorem近似计算$J$相对于参数$\theta$的累计梯度然后调整policy的参数$\theta$朝着使$J$更大的方向移动。

deterministic policy gradient

用$a=\mu_\theta(s)$表示deterministic policy，根据stochastic policy gradient theorm，很容易想到是否有deterministic policy gardient theorem，即朝着使得cumulative reward更大的方向更新policy的参数。deterministic policy gradient证明了deterministic policy gradient是存在的，可以使用action value function的梯度近似得到。在某些情况下，deterministic policy gradient还可以看成stochastic policy gradient的特殊情况。

spg vs dpg

spg和dpg的区别和联系

1. spg和dpg的第一个显著区别就是积分的space是不同的。Spg中policy gradient是在action和state spaces上进行积分的，而dpg的policy gradient仅仅在state space上进行积分。因此，计算spg需要更多samples，尤其是action spaces维度很高的情况下。
2. 为了充分explore整个state和action space，需要使用stochastic policy。而在使用deterministic policy时，为了确保能够持续的进行explore，就需要使用off-policy的算法了，behaviour policy使用stochastic policy进行采样，target policy是deterministic policy。作者使用deterministic policy gradient推导出了一个off-policy的actor-critic方法，使用可导的function approximators估计action values，然后利用这个function的梯度更新policy的参数，同时为了确保policy gradient没有bias，使用而来compatible function。

stochastic policy gradient theorem

详细的介绍可以查看policy gradient。spg的基本想法就是朝着$J$的梯度方向更新policy的参数。对$J(\pi_{\theta})$对$\theta$求导，得到：
\begin{align*}
\nabla_{\theta} J(\pi_{\theta})&=\int_S\rho^{\pi} (s) \int_A\nabla_\theta\pi_\theta (a|s)Q^{\pi} (s,a) dads \tag{1}\\
&=\mathbb{E}_{s\sim \rho^{\pi} , a\sim \pi_\theta}\left[\nabla_\theta \log\pi_\theta(a|s)Q^{\pi} (s,a)\right] \tag{2}
\end{align*}
这就是policy gradient theorem。从这个theorem中，我们得到了一个有用的信息，state distribution $\rho\pi(s)$取决于policy parameters。我们计算$J$关于$\theta$的梯度时，需要计算statedistribution，很难实现，policy gradient theorem消去了对$\rho^{\pi} $的依赖，具有很重要的实用价值。同时利用log derivative trick将performance gradient的估计变成了一个期望，可以通过sampling估计。这个方法中需要使用$Q^{\pi} (s,a)$，估计$Q$不同方法就是不同的算法。比如最简单的使用sample return $G_t$估计$Q^{\pi} (s, a)$，就是REINFORCE算法。

stochastic actor-critic 算法

Actor-critic是一个基于policy gradient theorem的结构，包含policy和value function两个部分。Actors通过stochastic gradient ascent调整stochastic policy $\pi_\theta(s)$的参数$\theta$；同时critic用一个action-value function $Q^w (s,a)$近似$Q^\pi (s,a)$, $w$是function approximation的参数。Critic一般使用policy evaluation方法进行学习，比如使用td和mc等估计action value function $Q^w (s,a)\approx Q^\pi (s,a)$。一般来说，使用$Q^w (s,a)$代替真实的$Q^\pi (s,a)$会引入bias，但是，如果function approximator是compatible，即满足以下两个条件，就会是无偏的：

1. $Q^w (s,a) = \nabla_\theta \log\pi_\theta(a|s)^T w$
2. 参数$w$最小化mse: $\epsilon^2 (w)=\mathbb{E}_{s\sim \rho^\pi ,a\sim \pi_\theta}\left[(Q^w (s, a)-Q^\pi (s,a))^2 \right]$，这样就没有bias了，即：
   $$\nabla_\theta J(\pi_\theta)=\mathbb{E}_{s\sim \rho^\pi, a\sim \pi_\theta}\left[\nabla_\theta \log\pi_\theta(a|s)Q^w (s,a)\right] \tag{3}$$

直观上来说，条件1说的是compatible function approximators是stochastic policy梯度$\nabla_\theta \log\pi_\theta(a|s)$的线性features，条件2需要满足$Q^w (s,a)$是$Q^\pi (s,a)$的linear regression soulution。在实际应用中，条件2会放宽，使用如TD之类policy evaluation算法更efficiently的估计value function。事实上，如果条件1和2都满足的话，整个算法等价于没有使用critic，和REINFORCE算法很像。

off-policy actor critic

在off-policy设置中，performance objective通常改成target policy的value function在behaviour policy的state distribution上进行平均，用$\beta(a|s)$表示behaviour policy：
\begin{align*}
J_\beta(\pi_\theta) &= \int_S\rho^\beta (s) V^\pi (s)ds\tag{4}\\
&=\int_S\int_A\rho^\beta (s)\pi_\theta(a|s)Q^\pi (s,a)dads \tag{5}\\
\end{align*}
对其求导和近似，得到：
\begin{align*}
\nabla_\theta J_\beta(\pi_\theta) &\approx \int_S\int_A\rho^\beta (s)\nabla_\theta\pi_\theta(a|s) Q^\pi (s,a)dads\tag{6} \\
&=\mathbb{E}_{s\sim \rho\beta, a\sim \beta}\left[\frac{\pi_\theta(a|s)}{\beta_\theta(a|s)}\nabla_\theta \log\pi_\theta(a|s) Q^\pi (s,a) \right]\tag{7}
\end{align*}
这个近似去掉了一项：$\nabla_\theta Q^\pi (s,a)$，已经有人证明去掉这一项之后仍然会收敛到局部最优。Off-policy actor-critic算法使用behaviour policy $\beta$生成trajectories，critic off-policy的从那些trajectories中估计state value function $V^v (s)\approx v^\pi (s)$。actor使用sgd从这些trajectories中off policy的更新policy paramters $\theta$，同时使用TD-error估计$Q^\pi (s,a)$。actor和critic都是用importance sampling ratio $\frac{\pi_\theta(a|s)}{\beta_\theta(a|s)}$。

action value gradients

绝大多数的model-free rl算法都属于GPI，迭代的policy evaluation和policy improvement。在contious action spaces中，greedy policy improvement是不可行的，因为在每一步都需要计算一个全局最大值。一个替代的方法是让policy朝着$Q$的gradient方向移动，而不是全局最大化$Q$。具体而言，对每一个访问到的state $s$，policy parameters $\theta^{k+1} $的更新正比于$\nabla_{\theta} Q^{ {\mu}^k } (s, \mu_{\theta}(s) )$。每一个state给出一个不同的方向，可以使用state distribution $\rho^{\mu} (s)$求期望，对最终的方向进行平均：
$$\theta^{k+1} = \theta^k + \alpha \mathbb{E}_{s\sim \rho^{ {\mu}^k } }\left[\nabla_\theta Q^{ {\mu}^k } (s, \mu_{\theta}(s))\right] \tag{8}$$
通过使用chain rule，我们可以看到policy improvement可以被分解成action-value对于action的gradient和policy相对于policy parameters的gradient：
$$\theta_{k+1} = \theta^k + \alpha \mathbb{E}_{s\sim \rho^{ {\mu}^k } }\left[\nabla_{\theta}\mu_{\theta}(s)\nabla_a Q^{ {\mu}^k } (s,a)|_{a=\mu_\theta(s_0)}\right] \tag{9}$$
按照惯例来说，$\nabla_{\theta}\mu_{\theta}(s)$是一个jacobian matrix，每一列是policy的$dth$ action对$\theta$的gradient $\nabla_\theta\left[\mu_\theta(s)\right]_d$。如果改变了policy，state distribution　$\rho^{\mu} $也会改变。如果不考虑distribution的变化的话，这个方法是保证收敛的。不过幸运的是，已经有人证明了和sgd一样，有deterministic policy gradient theorem，不需要计算state distributiond的gradient即可更新参数。

deterministic policy gradient theorem

新的术语定义

• $\rho_0(s)$：初始状态分布
• $\rho^{\mu} (s\rightarrow s’, k)$：在policy $\mu$下从state $s$出发经过$k$步到达$s’$的概率。
• $\rho^{\mu} (s’)$：带有折扣因子的状态分布，定义为：
  $$\rho^{\mu} (s’) = \int_S \sum_{k=0}^{\infty} \gamma^{k} \rho_0(s) \rho^{\mu} (s\rightarrow s’, k)ds\tag{10}$$

证明

deterministic policy定义为：$\mu_\theta: S\rightarrow A, \theta \in \mathbb{R}^n $。定义performance objective $J(\mu_\theta) =\mathbb{E}\left[G_0|\mu\right]$，将performance objective写成expectation如下：
\begin{align*}
J(\mu_\theta) & = \int_S\rho^\mu (s) G_0 ds\tag{11}\\
&= \mathbb{E}_{s\sim \rho^\mu }\left[G_0\right] \tag{12}
\end{align*}
给出deterministic policy gradient theorem：
假设MDP满足以下条件，即$\nabla_\theta\mu_\theta(s)$和$\nabla_a Q^\mu (s,a)$存在，那么deterministic policy gradient存在，
\begin{align*}
\nabla_\theta J(\mu_\theta) &= \int_S\rho^\mu (s) \nabla_\theta\mu_\theta(s)\nabla_aQ^\mu (s,a)|_{a=\mu_\theta(s)}ds\tag{13}\\
&=\mathbb{E}_{s\sim \rho^\mu }\left[\nabla_\theta\mu_\theta(s)\nabla_aQ^\mu (s,a)|_{a=\mu_\theta(s)}\right] \tag{14}
\end{align*}
证明：
\begin{align*}
\nabla_{\theta}V^{\mu} (s) & = \nabla_{\theta} Q^{\mu} (s, \mu(s))\tag{15}\\
& = \nabla_{\theta} \left( R(s,\mu(s)) + \int_S \gamma p(s’|s,\mu(s))V^{\mu} (s’) ds’ \right)\tag{16}\\
& = \nabla_{\theta}\mu(s) \nabla_a R(s,a)|_{a=\mu(s)} + \nabla_{\theta}\int_S \gamma p(s’|s,\mu(s))V^{\mu} (s’) ds’\tag{17}\\
& = \nabla_{\theta}\mu(s) \nabla_a R(s,a)|_{a=\mu(s)} + \int_S \gamma \left(p(s’|s,\mu(s))\nabla_{\theta} V^{\mu} (s’) + \nabla_{\theta}\mu(s)\nabla_a p(s’|s, a)|_{a=\mu(s)} V^{\mu} (s’) \right) ds’\tag{18}\\
& = \nabla_{\theta}\mu(s) \nabla_a \left( R(s,a) + \nabla_{\theta}\mu(s)\nabla_a p(s’|s, a)|_{a=\mu(s)} V^{\mu} (s’)ds’ \right) |_{a=\mu(s)} + \int_S \gamma p(s’|s,\mu(s))\nabla_{\theta} V^{\mu} (s’) ds’\tag{19}\\
& = \nabla_{\theta}\mu(s) \nabla_a Q^{\mu}(s,a) |_{a=\mu(s)} + \int_S \gamma p(s\rightarrow s’, 1, \mu(s))\nabla_{\theta} V^{\mu} (s’) ds’\tag{20}\\
& = \nabla_{\theta}\mu(s) \nabla_a Q^{\mu}(s,a) |_{a=\mu(s)}\\
&\qquad+ \int_S \gamma p(s\rightarrow s’, 1, \mu) \left(\nabla_{\theta}\mu(s’) \nabla_a Q^{\mu} (s’, a’) |_{a’ = \mu(s’)} + \int_S \gamma p(s’ \rightarrow s^{’’}, 1, \mu(s’) ) \nabla_{\theta} V^{\mu} (s’’) ds^{’’} \right) ds’ \tag{21}\\
& = \nabla_{\theta}\mu(s) \nabla_a Q^{\mu}(s,a) |_{a=\mu(s)}\\
&\qquad + \int_S \gamma p(s\rightarrow s’, 1, \mu) \nabla_{\theta}\mu(s’) \nabla_a Q^{\mu} (s’, a’) |_{a’ = \mu(s’)}ds’ \\
&\qquad + \int_S \gamma p(s\rightarrow s’, 1, \mu) \int_S \gamma p(s’ \rightarrow s^{’’}, 1, \mu(s’) )\nabla_{\theta} V^{\mu} (s’)ds^{’’} ds’ \tag{22}\\
& = \nabla_{\theta}\mu(s) \nabla_a Q^{\mu}(s,a) |_{a=\mu(s)}\\
&\qquad + \int_S \gamma p(s\rightarrow s’, 1, \mu) \nabla_{\theta}\mu(s’) \nabla_a Q^{\mu} (s’, a’) |_{a’ = \mu(s’)} ds’\\
&\qquad + \int_S \gamma^2 p(s\rightarrow s’, 2, \mu)\nabla_{\theta} V^{\mu} (s’) ds’ \tag{23}\\
& = \int_S \sum_{t=0}^{\infty} \gamma^t p(s\rightarrow s’, t, \mu)\nabla_{\theta} \mu(s’)\nabla_{a} Q^{\mu} (s’, a)|_{a=\mu(s’)} ds’ \tag{24}\\
\end{align*}
所以：
\begin{align*}
\nabla_{\theta} J(\mu) & = \nabla_{\theta} \int_S \rho_0(s) V^{\mu} (s) ds \tag{25}\\
& = \int_S \rho_0(s) \nabla_{\theta} V^{\mu} (s) ds \tag{26}\\
& = \int_S\int_S \sum_{t=0}^{\infty} \gamma^t\rho_0(s) p(s\rightarrow s’, t, \mu)\nabla_{\theta} \mu(s’)\nabla_{a} Q^{\mu} (s’, a)|_{a=\mu(s’)} ds’ ds\tag{27}\\
& = \int_S\rho^{\mu} (s) \nabla_{\theta} \mu(s)\nabla_{a} Q^{\mu} (s, a)|_{a=\mu(s)} ds\tag{28}\\
& = \mathbb{E}_{s\sim \rho^\mu}\left[ \nabla_{\theta}\mu(s)\nabla_{a} Q^{\mu} (s, a)|_{a=\mu(s)} \right]\tag{30}\\
\end{align*}
公式$(25)$到公式$(26)$是因为$\rho_0(s_0)$和$\mu$无关。。

spg的limit

dpg实际上可以看成是spg的一个特殊情况。如果使用deterministic policy $\mu_\theta:S\rightarrow A$和variance parameter $\sigma$表示某些stochastic policy $\pi_{\mu_{\theta,\sigma}}$，比如$\sigma = 0$时，$\pi_{\mu_{\theta, 0}} \equiv \mu_\theta$，当$\sigma \rightarrow 0$时，stochastic policy gradient收敛于deterministic policy gradient。
考虑一个stochastic policy $\pi_{\mu_{\theta,\sigma}}$让$\pi_{\mu_{\theta,\sigma}}(s,a)=v_\sigma(\mu_\theta(s),a)$，其中$\sigma$是控制方差的参数，并且$v_\sigma$满足条件B.1，以及MDP满足条件A.1和A.2，那么
$$\lim_{\sigma\rightarrow 0}\nabla_\theta J(\pi_{\mu_{\theta, \sigma}}) = \nabla_\theta J(\mu_\theta) \tag{31} $$
其中左边的gradient是标准spg的gradient，右边是dpg的gradient。这就说明spg的很多方法同样也是适用于dpg的。

deterministic actor-critic

接下来使用dpg theorem推导on-policy和off-policy的actor-critic算法。从最简单的on-policy update开始，使用Sarsa critic，然后介绍off-policy算法，使用Q-learning critic介绍核心思想。这些算法在实践中可能会有收敛问题，因为function approximator引入了biases，off-policy引入了不稳定性，可以使用compatiable function approximation的方法以及gradient td learning解决这些问题。

on-policy deterministic actor-critic

使用deterministic behaviour policy不能确保足够的exploration，会产生suboptimal solutions。但是我们还是要首先介绍on-policy actor-critic算法，它对于我们理解算法背后的核心思路很有用。尤其是在环境有噪音，即使使用deterministic behaviour policy也能够保证充足的exploration时。
和stochastic actor-critic一样。deterministic actor-critic也由actor和critic两部分组成，actor使用梯度下降调整$\mu(s)$的参数$\theta$，critic使用policy evaluation方法估计$Q^w (s,a) \approx Q^{\mu} (s, a)$指导actor的更新。比如critic使用Sarsa估计action value：
\begin{align*}
\delta_t & = R_{t+1} + \gamma Q^w (s_{t+1}, a_{t+1}) - Q^w(s_t, a_t) \tag{32}\\
w_{t+1} & = w_t + \alpha_w \delta_t \nabla_w Q^w (s_t,a_t)\tag{33}\\
\theta_{t+1} & = \theta_t + \alpha_{\theta} \nabla_{\theta} \mu_{\theta}(s_t) \nabla_a Q^w(s_t, a_t)|_{a=\mu(s)} \tag{34}\\
\end{align*}

off-policy deterministic actor-critic

考虑off-policy actor-critic方法。目标函数是使用behaviour policy对target policy的value function求期望：
\begin{align*}
J_{\beta}(\mu) & = \int_S \rho^{\beta}(s) V^{\mu} (s) ds\\
& = \int_S \rho^{\beta} (s) Q^{\mu} (s, \mu(s,a) ) ds \tag{35}\\
\end{align*}
求梯度是：
\begin{align*}
\nabla_{\theta}J_{\beta}(\theta) & \approx \int_S\rho^\beta (s) \nabla_{\theta}\mu(s)\nabla_{a} Q^{\mu} (s, a) ds \\
& = \mathbb{E}_{s\sim \rho^\beta }\left[ \nabla_{\theta}\mu(s)\nabla_{a} Q^{\mu} (s, a)|_{a=\mu(s)} \right]\tag{36}\\
\end{align*}
critic使用Q-learning更新action value function：
\begin{align*}
\delta_t & = R_{t+1} + \gamma Q^w (s_{t+1}, \mu_{\theta}(s_{t+1})) - Q^w(s_t, a_t) \tag{37}\\
w_{t+1} & = w_t + \alpha_w \delta_t \nabla_w Q^w (s_t,a_t)\tag{38}\\
\theta_{t+1} & = \theta_t + \alpha_{\theta} \nabla_{\theta} \mu_{\theta}(s_t) \nabla_a Q^w(s_t, a_t)|_{a=\mu(s)} \tag{39}\\
\end{align*}
在stochastic off-policy actor-critic中，actor和critic都使用了importance sampling，而在deterministic off policy actor-critic中，deterministic去掉了对actions的积分，所以避免了actor的importance sampling，使用one step Q-learning去掉了critic中的importance sampling。

总结

Deterministic policy gradient比stochastic policy gradient要好，尤其是high dimensional tasks上。此外，dpg不需要消耗更多的计算资源。还有就是对于一些应用，有可导的policy，但是没有办法加noise，这种情况下dpg更合适。
目标函数：

stochastic policy gradient theorem:

具体证明可以见policy gradient。
\begin{align*}
J(\pi_\theta) & = \int_S\rho^{\pi} (s)\int_A\pi(s,a) R(s,a) da ds \tag{40}\\
& = \mathbb{E}_{s\sim \rho^{\pi} , a\sim \pi_{\theta}} \left [R(s,a) \right]\tag{41}\\
\end{align*}

\begin{align*}
\nabla_{\theta}J(\pi_\theta) & = \int_S\rho^{\pi} (s)\int_A \nabla\pi(s,a) Q^{\pi} (s,a) da ds\tag{42}\\
& = \mathbb{E}_{s\sim \rho^{\pi} , a\sim \pi_{\theta}} \left [\log \nabla_{\theta} \pi(a|s)Q^{\pi} (s,a) \right]\tag{43}\\
\end{align*}

stochastic off-policy actor-crtic

具体证明可以参考Linear off-policy actor-critic。
\begin{align*}
J(\pi_\theta) & = \int_S\rho^{\beta}(s) V^{\pi} (s) ds\tag{44}\\
& = \int_S \int_A\rho^{\beta}(s) \pi(a|s) Q^{\pi} (s, a) ds\tag{45}\\
\end{align*}

\begin{align*}
\nabla_{\theta}J(\pi_\theta) & \approx \int_S\int_A\rho^{\pi} (s) \nabla_{\theta} \pi_{\theta}(s,a) Q^{\pi} (s,a) da ds\tag{46}\\
& = \mathbb{E}_{s\sim \rho^{\beta}, a\sim \beta} \left[ \frac{\pi_{\theta}(a|s) }{\beta_{\theta}(a|s) } \nabla_{\theta}\log \pi_{\theta}(s,a) Q^{\pi} (s,a) \right]\tag{47}\\
\end{align*}

deterministic policy gradient theorem:

具体证明见本文上半部分。但是我还有一些疑问，在stochastic policy gradient theorem中，$p(s’, r|s, a)$是$a$的函数，$a = \pi(s)$，所以$p(s’,r|s, a)$不应该也是$\theta$的函数吗？
\begin{align*}
J(\mu_{\theta}) & = \int_S\rho^{\mu} (s) R(s, \mu_{\theta}(s)) da ds\tag{48}\\
& = \mathbb{E}_{s\sim \rho^{\mu} } \left[R(s, \mu_{\theta}(s) \right]\tag{49}\\
\end{align*}

\begin{align*}
\nabla_{\theta} J(\mu_\theta) & = \int_S\rho^{\mu} (s)\nabla_{\theta}\mu_{\theta}(s) \nabla_a Q^{\mu} (s, a)|_{\mu_{\theta}(s)} da ds\tag{50}\\
& = \mathbb{E}_{s\sim \rho^{\mu} (s)} \left[ \nabla_{\theta}\mu_{\theta}(s) \nabla_a Q^{\mu} (s, a)|_{\mu_{\theta}(s)} \right]\tag{51}\\
\end{align*}

deterministic off-policy actor-critic

具体证明可以参考Linear off-policy actor-critic。
\begin{align*}
J_{\beta}(\mu_\theta) & = \int_S\rho^{\beta} (s) V^{\mu} (s) ds\tag{52}\\
& = \int_S\rho^{\beta} (s) Q^{\mu} (s, \mu_{\theta}(s)) ds\tag{53}\\
\end{align*}
\begin{align*}
\nabla_{\theta} J_{\beta} (\mu_\theta) & \approx \int_S\rho^{\beta} (s)\nabla_{\theta}\mu_{\theta}(a|s) \nabla_a Q^{\mu} (s, a) ds\tag{54}\\
& = \mathbb{E}_{s\sim \rho^{\beta}}\left[\nabla_{\theta}\mu_{\theta}(a|s) \nabla_a Q^{\mu} (s, a) \right]\tag{55}\\
\end{align*}

参考文献

Policy Gradient
1.https://arxiv.org/pdf/1509.02971.pdf
2.http://www0.cs.ucl.ac.uk/staff/d.silver/web/Publications_files/deterministic-policy-gradients.pdf

Distributed Tensorflow

这篇文章主要介绍如何创建cluster of tensorflow serves，并且将一个computation graph分发到这个cluster上。

Cluster和Server

简介

tensorflow中，一个cluster是一系列参与tensorflow graph distriuted execution的tasks。每个task和一个tensorflow server相关联，这个server可能包含一个"master"用来创建session，或者"worker"用来执行图中的op。一个cluster可以被分成更多jobs，每一个job包含一个或者更多个tasks。
为了创建一个cluster，需要给每一个task指定一个server。每一个task都运行在不同的devices上。在每一个task上，做以下事情：

1. 创建一个tf.train.ClusterSpec描述这个cluster的所有tasks，这对于所有的task都是一样的。
2. 创建一个tf.train.Server，需要的参数是tr.train.ClusterSpec，识别local task使用job name和task index。

创建一个tf.train.ClusterSpec

下面的表格中给出了两个cluster的示例。传入的参数是一个dictionary，key是job的name，value是该job的所有可用devices。第二列对应的task的scope name。

为每一个task创建一个tf.train.Server instance

tf.train.Server对象包含local devices的集合，和其他tasks的connections

参考文献

1.https://github.com/tensorflow/examples/blob/master/community/en/docs/deploy/distributed.md

Coordinator

简介

这个类用来协调多个thread同时工作，同时停止。常用的方法有：

• should_stop()：如果满足thread停止条件的话，返回True
• request_stop()：请求thread停止，调用该方法后，should_stop()返回True
• join()：等待所有的threads停止。

理解

其实我觉得这个类的作用好像没有那么大，或者我没有用到这种场景。反正就是满足thread的终止条件时，调用request_stop()函数，让should_stop()返回True。

代码示例

代码地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import tensorflow as tf
import time
import random
import threading

n = 0

def add(index):
    global n
    while not coord.should_stop():
    #while True:
        if n > 10:
            print(index, " done")
            coord.request_stop()
            #break
        print("before A, thread ", index, n)
        n += 1
        print("after A, thread ", index, n)
        time.sleep(random.random())
        print("before B, thread ", index, n)
        n += 1
        print("after B, thread ", index, n)
    
if __name__ == "__main__":
    with tf.Session() as sess:
        coord = tf.train.Coordinator()

        jobs = []
        for i in range(2):
            jobs.append(threading.Thread(target=add, args=(i,)))

        for j in jobs:
            j.start()

        coord.join(jobs)
        print("Hello World!")

参考文献

1.https://wiki.jikexueyuan.com/project/tensorflow-zh/how_tos/threading_and_queues.html

tf.one_hot

一句话介绍

返回一个one-hot tensor

API

1
2
3
4
5
6
7
8
9

tf.one_hot(
    indices,    # 每一个one-hot向量不为0的维度
    depth,  # 指定每一个one-hot向量的维度
    on_value=None,  # indices上取该值
    off_value=None,     #其他地方取该值
    axis=None,
    dtype=None,
    name=None
)

代码示例

1
2
3
4
5
6
7
8
9
10
11
12

import tensorflow as tf

indices = [1, 1, 1]
depth = 5

result = tf.one_hot(indices, depth)

sess = tf.Session()
print(sess.run(result))
# [[0. 1. 0. 0. 0.]
#  [0. 1. 0. 0. 0.]
#  [0. 1. 0. 0. 0.]]

参考文献

1.https://www.tensorflow.org/api_docs/python/tf/one_hot

python slice index

±–±--±–±--±–±--+
| P | y | t | h | o | n |
±–±--±–±--±–±--+
0 1 2 3 4 5 6
-6 -5 -4 -3 -2 -1

start和stop

1
2
3
4

a[start:stop]   # 从start到stop-1的所有items
a[start:]   # 从start到array结尾的所有items
a[:stop]   # 从开始到stop-1的所有items
a[:]   # 整个array的copy

step

1

a[start:stop:step]   # 从start，每次加上step，不超过stop，step默认为1

负的start和stop

1
2
3

a[-1]   # array的最后一个item
a[-2:]   # array的最后两个items
a[:-2]   # 从开始到倒数第三个的所有items

负的step

1
2
3
4

a[::-1]   # 所有元素，逆序
a[1::-1]    # 前两个元素，逆序
a[:-3:-1]   # 后两个元素，逆序
a[-3::-1]   # 除了最后两个元素，逆序

这里加一些自己的理解，其实就是倒着数而已，包含第一个:前面的，不包含两个:之间的。

参考文献

1.https://stackoverflow.com/a/509297/8939281
2.https://stackoverflow.com/a/509295/8939281

expand_dims

在数组的某个维度增加一个为1的维度。

代码示例

代码地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import numpy as np


a = np.ones([2, 3, 4])
print(a.shape)

a1 = np.expand_dims(a, 0)
print(a1.shape)

a2 = np.expand_dims(a, 1)
print(a2.shape)

a3 = np.expand_dims(a, 2)
print(a3.shape)

a4 = np.expand_dims(a, 3)
print(a4.shape)

newaxis

简介

newaxis就是None的一个alias

1
2

>>> np.newaxis is None
True

用途

常用于slicing。用于给数组增加一个维度。

代码示例

代码地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

a = np.ones((2, 3, 4))
print(a.shape)
(2, 3, 4)

a1 = a[np.newaxis]
print(a1.shape)
(1, 2, 3, 4)

a2 = a[:, np.newaxis]
print(a2.shape)
(2, 1, 3, 4)

a3 = a[:, :, np.newaxis]
print(a3.shape)
(2, 3, 1, 4)

a4 = a[:, :, :, np.newaxis]
print(a4.shape)
(2, 3, 4, 1)

a5 = a[:, :, np.newaxis, np.newaxis, :]
print(a5.shape)
(2, 3, 1, 1, 4)

参考文献

1.https://stackoverflow.com/questions/29241056/how-does-numpy-newaxis-work-and-when-to-use-it