关于
Reinforcement Learning: An introduction 读书笔记
动态规划(DP)方法
当环境已知时，即状态转移概率$(P(s'|s, a))$和回报$(r(s, a))$也知道的情况下，根据HJB方程
$$
V(s) = \max_a \sum_{s'}P(s'|s, a) [r(s, a) + \gamma V(s')]
$$
因为求最大值操作的存在，上述方程是值函数V的非线性方程，所以无法直接求解。
动态规划方法求解值函数方法有两种：值迭代与策略迭代。
采用值迭代的理论依据是非线性方程的迭代求解方法，从HJB方程来看，值函数V可以看做右边非线性算子的不动点，容易验证当$(\gamma<1)$时，该非线性算子是压缩映象，值迭代比收敛于不动点！它也可以看做往前一步的期望值作为目标，进行迭代。
$$
V_{k+1}(s) = \max_a \sum_{s'}P(s'|s, a) [r(s, a) + \gamma V_k(s')]
$$
另一种方法是交替优化策略和值函数，好处是在策略固定时，HJB方程没有max操作，是线性方程！
策略迭代分为两步
策略评估：将选择动作的策略固定，求解策略的值函数，因为策略固定，非线性的HJB方程变成线性方程了！所以可以采用线性方程的所有求解方法进行求解，比如高斯消元法、雅克比迭代法等等。
$$
V^{\pi}(s) = \sum_{s'}P(s'|s, a) [r(s, a) + \gamma V^{\pi}(s')], a=\pi(a|s)
$$
策略提升，对于上述评估出来的值函数，提升策略
$$
\pi'(s) = \arg\max_a Q^{\pi}(s, a) \\
Q^{\pi}(s, a) = r(s, a) + \gamma V^{\pi}(s')
$$
策略提升可以保证值函数序列是单调递增序列！
蒙特卡洛(MC)方法
当环境未知的时候，无法采用动态规划方法求解，需要根据经验数据进行评估。
蒙特卡洛法通过在线学习的方法，将整个动作序列执行至终态，根据实际获得的总回报$(G = \sum_{t=0}^T \gamma^t r(s_t, a_t))$来进行策略评估！当执行多次之后，$(G)$的平均值可以作为该策略下，初始状态s的值函数。这个过程也可以用迭代的方法描述
$$
Q^{\pi}(s, a) \leftarrow Q^{\pi}(s, a) - \alpha[Q^{\pi}(s, a) - G] \\
\alpha = 1/N
$$
该迭代过程可以看做用观测到的回报G作为学习目标的随机梯度下降
$$
J(Q^{\pi}) = \frac{1}{2}\sum_i (Q^{\pi}(s, a) - G_i)^2
$$
蒙特卡洛法的特点，必须等到动作序列执行完毕后，才能进行评估。
但是一个序列可以更新多个状态的值，利用马尔科夫链的性质，从这条链中间任何一个状态开始，都可以得到该状态的一个值函数的采样值！
为了有效地估计出Q函数，对每个状态-动作对都需要产生多个样本，因此初始状态需要随机从可能的状态-动作对中随机选择！
由于所有的初始状态-动作都是随机的，所以初始动作比较无效！但是又不能按照当前的策略选择初始动作，那样将会导致很多状态-动作对没有样本！
为了解决这个问题，可以限制$(\pi(a|s) < 1 - \epsilon + \epsilon/|A(s)|)$，也就是说不让策略只选择最优的动作，还以一定的概率选择其他动作，这样初始动作的选择也可以采用当前最优策略来选了！但是，这样一来，收敛后的策略并不是最优策略了，只是近最优策略！
Importance Sampling
另外一种解决方案是利用采样(Importance Sampling)实现off-policy，也就是评估的策略不是线上运行的策略！前面的方法评估的策略就是线上运行的策略，叫做on-policy方法。
假设评估的策略是$(\pi(a|s))$，而线上运行的策略是$(b(a|s))$，那么对于动作-状态轨迹$(\tau = (A_1, S_2, A_2, ..., S_T))$，两种策略产生该轨迹的概率之比为
$$
\rho_{t:T-1} = \Pi_t^{T-1} \frac{\pi(A_t|S_t)}{b(A_t|S_t)}
$$
那么，根据用策略$(b)$得到的经验数据，可以估计在策略$(\pi)$下的值函数
$$
V(s) = \frac{\sum_{t \in B(s)}\rho_{t:T(t)-1} G_t}{|B(s)|} \\
V(s) = \frac{\sum_{t \in B(s)}\rho_{t:T(t)-1} G_t}{\sum_{t \in B(s)}\rho_{t:T(t)-1}}
$$
$(B(s))$是状态s所处的时间集合。前一种估计无偏但是高方差，后一种有偏但是低方差，但是偏差会随着样本数增加而趋近于0！推荐后一种估计。
时间差分(TD)方法
蒙特卡洛方法需要策略执行到终止状态才能评估策略，TD方法只需要1步！核心思想在于自助法，它对值函数的估计是
$$
G_t = R_{t+1} + \gamma V(S_{t+1})
$$
即用原来的值函数取代了后面所有的回报！并采用常数学习率，
$$
V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]
$$
上述迭代可以看做最小化 $(1/2||G_t - V^ * (S_t)||^2)$ 进行随机梯度下降！
误差项$(\delta_t = G_t - V(S_t))$称作 TD error。
SARSA方法
Sarsa方法就是用TD方法对动作值函数Q(s,a)进行学习！
$$
Q(S_t, A_t) \leftarrow Q(S_t, A_t) - \alpha[R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)]
$$
可以看到，Sarsa方法用到了两个状态和两个动作，这两个动作都是采样自Q函数策略。如果动作选取有探索，那么Q就不是最优解，一般可以随着学习的推进，不断减小探索到某个很小的值，可以得到近最优解。
SARSA可以看做用 $(Q(S_{t+1}, A_{t+1}) )$ 来估计$(V^ * (S_{t+1}))$！
$$
Q^ * (S_t, A_t) = R_{t+1} + \gamma V^ * (S_{t+1}) \approx R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})
$$
Q-learning
也是一种TD学习方法，而且是off-policy，与SARSA不一样的是，它只用到了一个初始动作，不需要根据Q函数策略采样的第二个动作，这是最大的区别！也是Q-learning可以用off-policy学到最优策略的关键！
$$
Q(S_t, A_t) \leftarrow Q(S_t, A_t) - \alpha[R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)]
$$
Q-learning可以看做用 $(\max_a Q(S_{t+1}, a) )$ 来估计$(V^ * (S_{t+1}))$！
$$
Q^ * (S_t, A_t) = R_{t+1} + \gamma V^ * (S_{t+1}) \approx R_{t+1} + \gamma \max_a Q(S_{t+1}, a)
$$
期望SARSA方法
SAESA方法用当前策略的采样动作$(A_{t+1})$的动作值函数近似$(V^ * (s'))$，因此是有偏而且方差很大！
Q-learning则用$(\max_a Q(s', a))$近似$(V^ * (s'))$，也是有偏的方差也大，而且因为取max导致有过高估计的问题。
期望SARSA则用当前Q函数在当前策略下的期望值 $(\sum_{a} \pi(a|s') Q(s', a))$ 近似$(V^ * (s'))$，因为用到期望值，所以可以减少方差！迭代方程是
$$
Q(S_t, A_t) \leftarrow Q(S_t, A_t) - \alpha[R_{t+1} + \gamma \sum_a \pi(a|S_{t+1}) Q(S_{t+1}, a) - Q(S_t, A_t)]
$$
Double Q-learning
解决求max操作的过高估计问题，用两个Q函数，交替学习，每次学习时，用Q2来估计$(V^ * (S_{t+1}))$作为目标，对Q1进行梯度下降
$$
Q_1(S_t, A_t) \leftarrow Q_1(S_t, A_t) - \alpha[R_{t+1} + \gamma Q_2(S_{t+1}, a) - Q_1(S_t, A_t)] \\
a = \arg\max_a Q_1(S_{t+1}, a)
$$
n-step TD方法
在单步TD方法中，指向前看了一步就得出$(V^{\pi} (S_t))$的估计值，实际上也可以看多步，这样可以估计更加准确
$$
G_{t:t+n} = R_{t+1} + ... + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n})
$$
可以看出单步TD方法就是n=1的情况，而蒙特卡洛方法可以看做 $(n \rightarrow \infty)$ 的极限！
n-step TD估计偏差来自于最后一项，用当前的值函数估计最优值函数，因为前面的系数是$(\gamma^n)$是指数衰减的，所以n步TD方法的偏差随指数衰减！
n-step TD方法迭代方程是
$$
V(S_t) \leftarrow V(S_t) + \alpha[G_{t:t+n} - V(S_t)]
$$
SARSA：将SARSA对Q的估计用n步回报替换就可以得到n步SARSA方法
$$
Q(S_t, A_t) \leftarrow Q(S_t, A_t) - \alpha\left( [R_{t+1} + ... + \gamma^{n-1}R_{t+n} + \gamma^n Q(S_{t+n}, A_{t+n})] - Q(S_t, A_t) \right)
$$
Q-learning：同理将Q-learning对Q的估计用n步回报替换就可以得到n步Q-learning方法！
TD($(\lambda)$)方法
基本出发点：将n步回报加权平均作为对回报的估计，距现在越久的权重越小。
$$
G_t^{\lambda} = (1-\lambda)\sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}
$$
可以看出当$(\lambda = 0)$时，就是单步TD方法，当$(\lambda = 1)$时，就是蒙特卡洛方法。
后向更新算法，迭代地利用 TD error进行更新
$$
Z_t(s) = \begin{cases}
\gamma \lambda Z_{t-1}(s), \quad s \neq S_t \\
\gamma \lambda Z_{t-1}(s) + 1, \quad s = S_t
\end{cases} \\
\delta_t = R_{t+2} + \gamma V_t(S_{t+1}) - V_t(S_t) \\
V_t(S_t) \leftarrow V_{t-1}(S_t) + \alpha \delta_t Z_t(S_t)
$$
策略梯度理论
直接建模策略函数
$$
\nabla J(\theta) = \sum_s \mu_{\pi}(s) \sum_a q_{\pi}(s, a) \nabla_{\theta} \pi(a|s,\theta) = E_{\tau \sim \pi_{\theta}} \nabla_{\theta} \pi_{\theta}(\tau) r(\tau)
$$
两种表述，前面一个等式是状态-动作表述，后一个等式是状态-动作序列表述。策略梯度法实际上相当于用回报作为样本权重的极大似然估计。
REINFORCE：蒙特卡罗策略梯度
$$
\nabla J(\theta) = E_{\pi}\left[ \gamma^t\sum_a q_{\pi}(S_t, a) \nabla_{\theta} \pi(a|S_t,\theta) \right] \quad \text{(对状态采样)}\\
= E_{\pi}\left[ \gamma^t q_{\pi}(S_t, A_t) \nabla_{\theta} \log \pi(A_t|S_t,\theta) \right] \quad \text{(对动作采样)}\\
= E_{\pi}\left[ \gamma^t G_t \nabla_{\theta} \log \pi(A_t|S_t,\theta) \right] \quad \text{(用采样的回报替换q函数)}\\
= E_{\pi}\left[ \gamma^t (G_t - V(S_t)) \nabla_{\theta} \log \pi(A_t|S_t,\theta) \right]
$$
等二个等式，用到了关系
$$
Eq_{\pi}(S_t, A_t)\nabla_{\theta} \log \pi(A_t|S_t,\theta) = \sum_a \pi(a|S_t)q_{\pi}(S_t, a)\nabla_{\theta} \log \pi(A_t|S_t,\theta)
$$
最后一个等式是因为被剪掉的部分期望值为0.
因此，可以利用单个样本$((S_t, A_t))$估计策略梯度，得到策略梯度随机梯度上升迭代公式
$$
\theta_{t+1} = \theta_{t} + \alpha \gamma^t G_t \nabla_{\theta} \log \pi(A_t|S_t,\theta_t)
$$
这里的$(G_t)$采用的是单条链的最终回报，所以是用蒙特卡罗法估计策略梯度！
用$(\delta_t = G_t - V(S_t; w))$替换$(G_t)$可以减小梯度估计的方差，并且使用TD方法估计$(G_t = R_{t+1} + \gamma V(S_{t+1}; w))$。这就是 Actor Critic 算法：
$$
\theta_{t+1} = \theta_{t} + \alpha \gamma^t \delta_t \nabla_{\theta} \log \pi(A_t|S_t,\theta_t)
$$
