[人工智能]【文献学习】强化学习

参考文献：《机器学习》,周志华（西瓜书）
（今天看书总是走神，干脆总结一下，希望帮自己理清思路。如果碰巧能被大神看到，如有不正确或不严谨之处，万望指教！）

动态规划法

动态规划法是典型的有模型强化学习算法，即模型已知，对任意状态$x$，$x^{\prime }$和动作$a$，在$x$状态下执行动作$a$转移到$x^{\prime }$状态的概率$P_{x\to x^{\prime }}^a$是已知的，该转移所带来的奖赏$R_{x\to x^{\prime }}^a$也是已知的。
在每执行一步策略后就进行值函数的更新。
1.策略评估
$V^{\pi }(x,a)$表示从状态$x$出发，使用策略$\pi$所才来的累积奖赏；$Q^{\pi }(x,a)$表示从状态$x$出发，执行动作a后再使用策略$\pi$带来的累积奖赏。
对于T步累计奖赏有
$V_T^{\pi }={\sum }_{a\in A}\pi (x,a){\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T?1}{T}{V}_{T?1}^{\pi }(x^{\prime }))$
对于$\gamma$折扣累计奖赏有
$V_{\gamma }^{\pi }(x)={\sum }_{a\in A}\pi (x,a){\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(R_{x\to x^{\prime }}^a+\gamma V_{\gamma }^{\pi }(x^{\prime }))$
有了状态值函数V，就能直接计算出状态-动作值函数
$Q_T^{\pi }={\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T?1}{T}{V}_{T?1}^{\pi }(x^{\prime }))$
$Q_{\gamma }^{\pi }(x)={\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(R_{x\to x^{\prime }}^a+\gamma V_{\gamma }^{\pi }(x^{\prime }))$
2.策略改进
立项的策略应能最大化累积奖赏：${\pi }^{?}=\underset{\pi }{\mathrm{argmax}}{\sum }_{x\in X}{V}^{\pi }(x)$
$V_T^{?}(x)={\max }_{a\in A}{\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T?1}{T}{V}_{T?1}^{\pi }(x^{\prime }))$
$V_{\gamma }^{?}(x)={\max }_{a\in A}{\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(R_{x\to x^{\prime }}^a+\gamma V_{\gamma }^{\pi }(x^{\prime }))$
于是：$V^{?}(x)={\max }_{x\in A}{Q}^{{\pi }^{?}}(x,a)$
则最优状态-动作值函数有
$Q_T^{?}(x,a)={\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T?1}{T}{\max }_{a^{\prime }\in A}{Q}_{T?1}^{?}(x^{\prime },a^{\prime }))$
$Q_{\gamma }^{\pi }(x)={\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(R_{x\to x^{\prime }}^a+\gamma {\max }_{a^{\prime }\in A}{Q}_{\gamma }^{?}(x^{\prime },a^{\prime }))$
3.策略迭代与值迭代
策略迭代：策略评估→改进策略→策略评估→改进策略……
值迭代：将策略改进视为值函数的改善，得
$V_T(x)={\max }_{a\in A}{\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(\frac{1}{T}{R}_{x\to x^{\prime }}^a+\frac{T?1}{T}{V}_{T?1}(x^{\prime }))$
$V_{\gamma }^{?}(x)={\max }_{a\in A}{\sum }_{x^{\prime }\in X}{P}_{x\to x^{\prime }}^a(R_{x\to x^{\prime }}^a+\gamma V_{\gamma }(x^{\prime }))$

免模型学习

学习算法不依赖于环境建模
1.蒙特卡洛强化学习
一种直接的策略评估评估替代方法是多次“采样”，然后求取平均累积奖赏来作为期望累积奖赏的近似。
由于模型未知，从V到Q转换困难，估计对象从V转变为Q。
其本质是通过多次尝试后求平均来作为期望累积奖赏的近似，但它在求平均时是“批量处理”进行的，即在一个完整的采样轨迹完成后再对所有状态-动作对进行更新。
此类算法需在完成一个采样轨迹之后再更新策略的值估计。缺点是：未充分利用强化学习任务的MDP结构。
1.1同策略蒙特卡洛学习算法
欲较好地获得值函数的估计，就需要多条不同采样轨迹。
蒙特卡洛方法进行策略评估后，进行策略改进。被评估和被改进的是同一个策略，因此称为“同策略”蒙特卡洛强化学习算法。

同策略蒙特卡洛强化学习算法最终产生的是$?$-贪心策略。
1.2异策略蒙特卡洛学习算法
在策略评估时引入$?$-贪心策略，在策略改进时改进原策略。

2.时序差分学习
结合了动态规划与蒙特卡洛的思路。
将蒙特卡洛强化学习的更新过程增量式进行。设对于状态-动作对$(x,a)$，假设基于$t$个采样已估计出值函数$Q_t^{\pi }(x,a)=\frac{1}{t}{\sum }_{i=1}^t{r}_i$，则在得到第$t+1$个采样$r_{t+1}$时，通过增量求和可得
$Q_{t+1}^{\pi }(x,a)=Q_t^{\pi }(x,a)+\alpha (R_{x\to x^{\prime }}^a+\gamma Q_t^{\pi }(x^{\prime },a^{\prime })+Q_t^{\pi }(x,a))$

Sarsa算法是一个同策略算法，评估与执行均为$?$-贪心策略。
将Sarsa修改为异策略算法，得到Q-学习算法

值函数近似

状态空进连续，有无穷多个状态。直接对连续状态空间的值函数进行学习。假定状态空间为n维实数空间$X={\text{R}}^n$，状态线性函数为：$V_{\mathbf{\theta }}(x)={\mathbf{\theta }}^T\mathbf{x}$
通过上式学得值函数尽可能近似真实值函数$V^{\pi }$，单个样本的更新规则：
$\mathbf{\theta }=\mathbf{\theta }+\alpha (V^{\pi }(\mathbf{x})?V(\mathbf{x}))\mathbf{x}$
借助时序差分学习，基于$V^{\pi }(\mathbf{x})=r+\gamma V^{\pi }({\mathbf{x}}^{\prime })$用当前估计的值函数代替真实值函数，即
$\mathbf{\theta }=\mathbf{\theta }+\alpha (r+\gamma {\mathbf{\theta }}^T{\mathbf{x}}^{\prime }?{\mathbf{\theta }}^T\mathbf{x})\mathbf{x}$

模仿学习

机器能获得人类专家的决策过程返利，从范例中学习，称为“模仿学习”。
1.直接模仿学习
假定获得一批人类专家决策轨迹数据 { τ 1 , τ 2 , . . . , τ m } \{ \tau_1,\tau_2,...,\tau_m\} {τ1?,τ2?,...,τm?}，每条轨迹包含状态和动作序列${\tau }_i=<s_1^i,a_1^i,s_2^i,a_2^i,...,s_{n_i+1}^i>$，其中$n_i$为第i条轨迹中的转移次数。
可利用监督学习来符合人类专家决策轨迹数据的决策。
将轨迹上所有“状态-动作对”抽取出来，构造一个新的数据集合$D$，即吧状态作为特征，动作作为标记，然后对这个新构造出的数据集合D适用分类或回归算法即可学得策略模型。学得的策略可作为机器新型强化学习的处事策略，在通过强化学习方法基于环境反馈进行改进，获得更好策略。
2.逆强化学习
设计奖赏函数困难，从人类专家提供的范例数据中反推出奖赏函数。
基本思想：欲使机器做出与范例一致的行为，等价于在狗哥奖赏函数的环境中求解最优策略，该最优策略所产生的轨迹与范例数据一致。也就是说，我们要寻找某种奖赏函数使范例数据最优，即可使用这个江上寒暑来训练强化学习策略。
假设将行函数能表达为状态特征的线性函数，即$R(\mathbf{x})={\mathbf{w}}^T\mathbf{x}$，策略$\pi$的积累奖赏可写为
${\rho }^{\pi }=\mathbf{w}TE[{\sum }_{t=0}^{+\infty }{\gamma }^t{\mathbf{x}}_t|\pi ]$
即状态向量加权和的期望与系数$\mathbf{w}$的内积。
将向量期望$E[{\sum }_{t=0}^{+\infty }{\gamma }^t{\mathbf{x}}_t|\pi ]$简写为${\bar{\mathbf{x}}}^{\pi }$，可用蒙特卡洛方法通过采样近似期望。可将每条范例轨迹上的状态加权求和再平均，记为${\bar{\mathbf{x}}}^{?}$，于是有：
${\mathbf{w}}^{?}=\underset{w}{\mathrm{argmax}}{\min }_{\pi }{\mathbf{w}}^T({\bar{\mathbf{x}}}^{?}?{\bar{\mathbf{x}}}^{\pi })$
$s.t.||\mathbf{w}||\le 1$