nothing

马尔科夫过程：$<S,P>$

状态转移概率： $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)$

或这么理解：

矩阵化求解：$v = R + \gamma P v$

马尔科夫决策过程：$<S,A,P,R,\gamma>$

https://zhuanlan.zhihu.com/p/35134789

$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]$ 跟当前状态和动作有关

状态值函数：

蒙特卡洛方法： https://zhuanlan.zhihu.com/p/33387269

$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

$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算法的期望收敛方向 https://zhuanlan.zhihu.com/p/36254714

https://zhuanlan.zhihu.com/p/33426502

多步时间差分：https://zhuanlan.zhihu.com/p/37340768

$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]$

https://zhuanlan.zhihu.com/p/36390206

这个回报函数$\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))\\$

https://zhuanlan.zhihu.com/p/39624504

https://zhuanlan.zhihu.com/p/38185553

https://github.com/google/dopamine