# nothing 马尔科夫过程：$$\$$ 状态转移概率： $$P\_{ss^\prime} = p\[S\_{t+1}=s^\prime | S\_t =s]$$ R是一个当前状态的奖励，是当前状态转移后的t+1时刻奖励的期望的函数。 累积回报：$$G\_t = R\_{t+1} + \gamma R\_{t+2} + ... = \sum\_{k=0}^\infty \gamma^k R\_{t+k+1}$$ 此时$$G\_t$$是个随机变量，而我们要求得到的累积回报是个确定值，所以我们用累积回报的期望来作为这个确定值。 $$\upsilon\_{}(s)=E\left\[G\_{t}|S\_{t}=s\right]$$ $$=E\_{}\left\[\sum\_{k=0}^{\infty}{\gamma ^{k}}R\_{t+k+1} |S\_{t}=s\right]$$ $$=E\left\[R\_{t+1}+\gamma G\_{t+1}\right|S\_{t}=s]$$ $$=E\left\[R\_{t+1} +\gamma v(S\_{t+1})\right|S\_{t}=s]$$ 由两部分组成：即时奖励期望和下一时刻状态的价值期望。$$Ex = E(Ex)$$ $$R\_{s} \gamma+\sum\_{s'\in S}{P\_{ss'}v(s')}$$ 上面公式的理解： $$E(\gamma G\_{t+1}|S\_t=s) = \gamma \sum\_{S\_{t+1}} E(G\_{t+1}|S\_t,S\_{t+1})P(S\_{t+1}|S\_t)$$ 或这么理解： ![](https://pic3.zhimg.com/80/v2-b58fab43a9968c34b02a7b9ba40a5bef_hd.jpg) 矩阵化求解：$$v = R + \gamma P v$$ ![](https://pic1.zhimg.com/80/v2-071d680f97a7cfc7199f03a700b1f9a2_hd.jpg) ![](https://pic4.zhimg.com/80/v2-ee67be43e30fababfab0fb4820db303f_hd.jpg) 马尔科夫决策过程：$$\$$ ![](https://pic2.zhimg.com/80/v2-2ed239f982a29a08315d2b173a645b26_hd.jpg) $$P\_{ss^\prime}^a$$ R 多了a 策略： $$\pi(a|s)=P\[A\_t=a|S\_t=s]$$ 状态转移概率： $$P\_{ss^\prime} = P\_{ss^\prime}^\pi = \sum\_{a\in A}{\pi(a|s)|P\_{ss^\prime}^a} =\sum\_{a\in A}{P\[A\_t=a|S\_t=s]\[P\[S\_{t+1}=s^\prime|S\_t=s,A\_t=a]}$$ 状态奖励： $$R\_s = R\_s^\pi = \sum\_{a \in A}\pi(a|s) R\_s^a = \sum\_{a \in A} E\[R\_{t+1}|S\_t=s,A\_t=a]P\[A\_a|S\_t=s]$$ 跟当前状态和动作有关 状态值函数： 蒙特卡洛方法： $$V(S\_t) \leftarrow V(S\_t) + \alpha \Bigg \[ G\_t-V(S\_t) \Bigg ]$$ 蒙特卡洛方法要等到事件结束，最后的奖励Gt出来后，才进行值函数更新。 故mc用的是真实的奖励和期望， 而TD方法，策略$$\pi$$下的状态值$$v\_\pi (S\_{t+1})$$未知的，所以在实际中使用的是它的估计值$$v (S\_{t+1})$$ 时间差分： [https://zhuanlan.zhihu.com/p/36254714](https://legacy.gitbook.com/book/json0071/deeplearning/edit) $$V(S\_t) \leftarrow V(S\_t) + \alpha \Bigg \[ R\_{t+1}+\gamma V(S\_{t+1})-V(S\_t) \Bigg ]$$ $$Q(S\_t,A\_t) \leftarrow Q(S\_t,A\_t) + \alpha \Bigg \[ R\_{t+1}+\gamma Q(S\_{t+1},A\_{t+1})-Q(S\_t,A\_t) \Bigg ]$$ 利用e-greedy策略的Q值更新，在线时间差分控制 $$Q(S\_t,A\_t) \leftarrow Q(S\_t,A\_t) + \alpha \Bigg \[ R\_{t+1}+\gamma \max\_a Q(S\_{t+1},a)-Q(S\_t,A\_t) \Bigg ]$$ 利用最大的Q值更新，离线时间差分控制 $$Q(S\_t,A\_t) \leftarrow Q(S\_t,A\_t) + \alpha \Bigg \[ R\_{t+1}+\gamma E\[ Q(S\_{t+1},A\_{t+1})|S\_{t+1}]-Q(S\_t,A\_t) \Bigg ] = Q(S\_t,A\_t) + \alpha \Bigg \[ R\_{t+1}+\gamma \sum\_a \pi(a|S\_{t+1})Q(S\_{t+1},a)-Q(S\_t,A\_t) \Bigg ]$$expected sarsa利用e-greedy策略的期望Q值更新，expected sarsa的收敛方向是sarsa算法的期望收敛方向 多步时间差分： $$V\_{t+n}(S\_t) \leftarrow V\_{t+n-1}(S\_t) + \alpha \Bigg \[ G\_{t:t+n}-V\_{t+n-1}(S\_t) \Bigg ]$$ $$J(\theta)=\mathbb{E}*{\pi*\theta}\[r]=\sum\_{s' \in \cal{S}}p(s'|s,a)\sum\_{a \in \cal{A}} \pi\_\theta(s,a) \cal{R}\_{s,a}$$ $$\nabla\_\theta \pi\_\theta(s,a)=\pi\_\theta(s,a) \frac{\nabla\_\theta \pi\_\theta(s,a)}{\pi\_\theta(s,a)}=\pi\_\theta(s,a) \nabla\_\theta log \pi\_\theta(s,a)$$ $$\nabla\_\theta J(\theta)={\sum\_{s\ \in \cal{S}}p(s'|s,a)\sum\_{a \in \cal{A}} \pi\_\theta(s,a)} \nabla\_\theta log \pi\_\theta(s,a) \cal{R}*{s,a}=\mathbb{E}*{\pi\_\theta}\[\nabla\_\theta log \pi\_\theta(s,a)r]$$ 这个回报函数$$\cal{R}*{s,a}$$很重要，可以设计为$$\sum*{t'=t}^T \gamma^{t'-t} r\_t'$$ ，即是在状态s处采用动作a所希望得到的回报的估计 。由于轨迹之间方差很大，平均一下求期望$$\sum\_{t'=t}^T E\_{\pi\_\theta}\[r(s\_t',a\_t')|s\_t,a\_t]$$ ，这个就是$$Q(s,a)$$ 于是梯度就变成了： $$\nabla\_\theta log \pi\_\theta(s,a)Q(s,a)$$ 回报函数中还可以引入常数项b来减少误差，这个b可以为$$Q(s,a)$$的期望，即是V值函数。这样$$R(s,a) -b$$ 的意义就变成了我们想考察某轨迹在策略网络指导下比平均好多少。 这样就得到了一个新形式：$$A(s,a) - Q(s,a)-V(s)$$ 称之为优势函数，就是指Q值函数比V值函数好多少。 $$Q(s\_t, a\_t)=r(s\_t, a\_t)+E\_{s\_{t+1}}\[V(s\_{t+1})]$$ ，后面这个期望是整条轨迹，可以像TD那样只取一步。于是得到 $$Q(s\_t, a\_t)\approx r(s\_t, a\_t)+V(s\_{t+1})$$ ，最后$$A(s\_t, a\_t)\approx r(s\_t, a\_t)+V(s\_{t+1})-V(s\_t)$$ （对比TD-error）。 这样子，整个系统中有两个网络：策略网络和V值网络。（在DQN中我们是用网络拟合Q值函数，这里只不过换成了V值函数。相似的，V值网络的目标函数同样是TD-error）这就是我们大名鼎鼎的Actor Critic 算法了：Actor ——策略网络，Critic ——V值网络。 流程如下： 1. 运行策略生成样本 2. 利用样本估计V值函数（更新V值网络） 3. 计算优势函数A 4. 根据优势函数A计算梯度（更新策略网络） 为了高效的利用sample出来的数据，可以对数据进行importance sampling： $$E\_{x\sim p}\[f(x)] = \int f(x)p(x)dx \ = \int f(x)\frac{p(x)}{q(x)}q(x)dx\ =E\_{x \sim q}\[f(x)\frac{p(x)}{q(x)}]$$ 为了避免over fitting ，对目标函数增加一个regularizer ： $$J\_{PPO}^{\theta'}(\theta) = J^{\theta'}(\theta) - \beta KL(\theta, \theta') \\$$，但由于$$\theta, \theta'$$ 不是分布，可以采用： $$KL(\theta, \theta') = \frac{1}{K}\sum\_{k=1}^K KL(P\_\theta(a\_k|s\_k), P\_{\theta'}(a\_k|s\_k))\\$$