斯坦福吴恩达《机器学习》--增强学习
增强学习和控制
在监督学习中,算法旨在模仿训练样本中标记为y的真实结果,每个输入样本x都对应着明确的目标输出y.然而,对于许多需要连续决策或控制的任务,直接为算法提供明确标签变得具有挑战性.例如,在一个四足机器人行走的任务中,起初我们不清楚如何操作机器人使其前进,也不知道如何通过反馈机制将其行为与成功状态联系起来.
在强化学习中,我们将奖励函数作为评估标准来衡量动作的好坏.具体而言,当四足机器人向前行走时我们将给予正向奖励而向后退或摔倒时则给予负面奖励.通过不断优化这些奖励信号强化学习算法将能够识别出能够获得最大奖励的操作序列.
1.MDP
MDP是一个元组（S，A，Psa，\gamma，R），S是状态集，A是状态集，Psa是处于状态s采用动作a的状态转移概率，是折现因子，R是SA的奖励函数。
MDP过程如下：初始状态s_0，采用动作a_0，按照Ps0a0转移到状态s_1，之后采取动作a_1，按照Ps1a1转移到状态s_2，如下图所示：
得到的奖励如下：
对于奖励函数只和状态有关的情况：
增强学习的目标是最大化奖励：
在时间t时刻的即时奖励应乘以折现因子\gamma^t；为了最大化总奖励，在决策过程中应尽量优先获取正值。策略函数\pi是从状态空间S到动作空间A的映射关系；给定状态s时的动作a由策略函数π确定；价值函数V(s)表示在状态s下的预期未来累积奖励
对于给定的策略，价值函数V^\pi满足Bellman等式：
由现时奖励与未来奖励按折扣率衰减两部分构成的价值函数V^\pi(s)中包含两个关键组成部分：即现时奖励R(s)与未来奖励按折扣率衰减后的总和。其中未来奖励的部分可视为从新状态s'出发的价值期望（Es’~Ps(s)[V^\pi(s')]），并在其基础上乘以折扣因子γ以反映未来的不确定性或时间偏好。这一过程遵循一定的概率分布规律（遵循概率分布Psa）。
基于贝尔曼方程的方法可用来求解MDP中的价值函数。针对状态数有限的状态空间模型而言，在每个状态s都对应一个贝尔曼方程（Belleman equation），这些方程共同构成了关于价值函数的一个线性方程组（linear system of equations）。通过求解该线性系统即可获得相应的价值函数。
在马尔可夫决策过程中（Markov decision process），最佳策略所对应的最优价值函数定义为：最大化所有可能策略下相应状态下累积回报值的最大值。
最佳价值函数的Bellman等式如下：
最佳策略定义如下：
该最佳策略π在所有实际状态下表现一致,由此可知,在任何起始状态下都采用同一的最佳策略
2.价值迭代和策略迭代
对于有限状态的MDP，我们讨论两种解法，价值迭代和策略迭代。
价值迭代方法如下：
在循环中进行状态更新采用两种方式：第一种是同步更新模式，在每次迭代前计算所有状态下新的V(s)值之后才同步更新；第二种是异步更新模式，在遍历完所有状态后才对单个状态的V(s)进行更新。
策略迭代法按照以下步骤进行：
- 初始化一个随机的策略π；
- 重复以下步骤直到收敛：
a. 根据当前策略计算价值函数Vπ(s)，即求解贝尔曼方程；
b. 根据价值函数改进当前策略π； - 得到最优策略。
在步骤(a)中对价值函数进行计算时，请参考前文所述的具体方法：每个状态对应的贝尔曼方程构成了一个线性方程组。针对规模较小的马尔可夫决策过程（MDP）来说，策略迭代算法通常具有较高的收敛速度；然而，在面对规模较大的MDP问题，则会导致较为复杂的计算负担
3.MDP学习模型
在已知状态转移概率及奖励函数的情况下讨论MDP及其求解方法。但在现实应用中，在许多情况下需要根据观测到的数据来计算这些未知的状态转移概率及奖励函数。例如以下是一系列实验数据：
其中si(j)为第j次实验第i时刻的状态，ai(j)为采取的行动。转移概率如下：
对于未曾访问过的状态s, 可以认为其转移概率矩阵Psa(s')设定为其状态空间大小|S|的倒数；类似的, 当奖励函数R未知时, 可基于平均值计算得到奖励函数值；随后采用价值迭代法与策略迭代法相结合的方式来进行MDP模型的求解过程
4.连续状态的MDP
上述讨论主要局限于其状态空间为有限维的马尔可夫决策过程（MDP），随后转而探讨状态空间无限的情形。如车辆运行状态、直升机运作模式等实例说明该理论的应用前景。
4.1 离散化
最基本的方式是通过采用离散化手段使用前文所述的方法来实现计算过程。比如对于2D状态来说，可以通过网格离散化来进行处理：
4.2 价值函数近似
4.2.1 使用模型或仿真器
基于现有理论假设我们建立了一个MDP模型或仿真平台，并进而研究并实现价值函数的近似算法。简而言之，在这个过程中，默认将仿真器视为一个黑箱系统，在给定任一状态s_t和动作a_t，并通过预设的状态转移概率矩阵P来推导出下一个状态s_{t+1}。
存在多种途径用于获取上述模型。其中一种方式是通过物理仿真实现；另一种方式则是利用已有的MDP数据训练出该模型。
应用学习算法预测st+1为st和at的函数。
4.2.2 Fitted value iteration
这一部分还未完全搞清楚，后续整理。
欢迎关注微信公众号“翰墨知道”，获取及时更新
