强化学习基本知识

强化学习基础知识强化学习基础知识 作为人工智能领域 机器学习 Machine Learnig 热点研究内容之一的强化学习 Reinforcement Learning RL 旨在通过在无外界 教师 参与的情况下 智能体 Agent 自 身通过不断地与环境交互 试错 根据反馈评价信号调整动作 得到最优的策略以适应环 境 一 一 Markov 决策过程 决策过程 MDP 强化学习的来源是马尔科夫决策过程 M Markov 性的意思是 x 取 x 1 x 2 x 3 x n 所得到 x n m 的分布与 x 只取 x n 所得到的 x n m 的分布相同 既是说未来状态的分布只与当前状态有关 而与过去状态无关 无 后效性 若转移概率函数 P s a s 和回报函数 r s a s 与决策时间 t 无关 即不随时间 t 的变 化而变化 则 MDP 称为平稳 MDP 当前状态 s 所选取的动作是由策略 h 决定 S A 0 1 A s 在状态 s 下用策略 所选取的动作 动作后的结果是由值函数以评估 它是由 Bellman 公式得到 折扣因子 1 0 值函数 UuSs sVsasPasRashsV 动作 状态值函数 SsAa asQsasPasRasQ 对于确定性策略 有 一个状态转移概率 ssQsV 对于不确定性策略 有 多个状态转移概率 Aa asQassV 强化学习的最终目的是找到最优策略 选择值函数最大的动作 最优值函数 max Ss sVsasPasRsV 或者 最优动作 状态值函数 Ss asQsasPasRasQ max 或者 兼而有之 为了避免局部最优需要进行随机探索 为了逼近既定目标需要抽取最优策略 所以算 法中存在一个探索与利用的平衡 达到平衡有两种方法 策略和 Boltzmann 分布方法 平衡离散域 greedy 对于电磁微阀控制 s 当前四个微阀状态 a 操作四个微阀的动作 0 为关闭 1 为开启 s 动作后微阀的新状态 P s a s 状态 s 调控微阀使其达到新状态 s 的概率 在调控后这个状态的累计奖赏值 sV 本次动作的立即奖赏值 根据各点温度及标准差的计算评估得到 asR s a 调节微阀的各种策略 二 基于模型的动态规划算法二 基于模型的动态规划算法 动态规划是一个多阶段的决策问题 在最优决策问题中 常规动态规划算法主要分为下 面四类 第一类是线性规划法第一类是线性规划法 根据 Bellman 方程将值函数的求取转化为一个线性规划问题 线性规划方程包含 S 个变量 S A 个不等式约束 其计算复杂度为多项式时间 Ss Ss AaSssVsasPasRsVts sV max 第二类是策略迭代第二类是策略迭代 仍然是基于 Bellman 最优方程的算法 通过策略评估与策略迭代 的交替进行来求取最优策略 策略迭代分为策略评估和策略改进两部分 在评估部分 对于一个给定的策略 根 k 据 Bellman 公式求解和 对于评估部分 用贪婪策略得到改进的策略 sV k asQ k 1 k 第三类是值函数迭代法第三类是值函数迭代法 其本质为有限时段的动态规划算法在无限时段上的推广 是 一种逐次逼近算法 将 Bellman 公式改写为 就 Ss t Aa t SssVsasRsasPsV 1 max 可跳过策略改进步骤 直接用迭代法逼近最优值函数 V 从而求取最优策略 第四类是广义策略迭代法第四类是广义策略迭代法 综合了策略迭代和值迭代方法特点 广义策略评估是策略评估与策略改进相结合的学习过程 策略评估总是试图让策略和 相应的值函数一致 而策略改进总是破坏策略评估得到的一致性 最终策略和值函数都不 再变化是迭代结束 下图在两个维度上 两条线表示 描述了广义策略迭代的逼近过程 学习的最终目的是获得最优策略 具体的学习过程可以在值函数唯独和策略策略维度上灵 活的变化 值函数迭代方法只在值函数维度上工作 而策略迭代方法在值函数维度和策略 维度上交叉进行 许多动态规划与强化学习算法的思想都来源于广义策略迭代 初始状态 决策 1 决策 2 决策 n 结束状态 三 模型未知的强化学习三 模型未知的强化学习 对于求解模型未知的 MDP 问题 通常有如下 3 类解决思路 第一类是学习 MDP 的相 关模型 然后用动态规划算法予以求解 此类方法称为间接强化学习 第二类方法不需要 估计 MDP 的模型 直接利用采样对值函数或策略函数进行评估 此类方法成为直接强化学 习算法 第三类是前两类方法的混合 1 蒙特卡罗方法蒙特卡罗方法 蒙特卡洛方法是一种以部分估计整体 利用随机数来解决问题的方法 其通过统计模 拟或抽样以获得问题的近似解 该方法只是用于场景中存在终止状态的任务 MC 策略评 估主要是利用大数定律 以各个状态的回报值的样本平均来估计值函数 最终发现最优策 略 Re sturnaveragesV 得到的回报金额已赋给第一次访问的 s 也可以将每次访问到终止状态的回报平均 T s 后赋予给 s 的值函数 鉴于 MC 策略评估只有在只有在无穷次迭代时才能精确计算 因此有人提出了改 Q V VV Vgreedy V 进策略 在一幕赋值完成后将用贪婪算法来更新以得到改进策略 这样有利于维 k Q 1 k 持探索与利用的平衡 也提高了的精确度 Q maxarg asQs Aa 但是面对着以上方法只利用不探索的缺陷将贪婪策略进行的改进 引入了基于 贪 婪策略的在线 MC 控制策略 主要做了两个改动 第一个是将初始策略用 贪婪策略来选 择 第二个是利用 贪婪策略来进行策略更新 即对于每一个 Aa 1 aaA aaA as max 1 asQasQ A asQasssQ Aa AaAa 在线策略 MC 控制算法中 产生样本的行为策略核和进行 Q 值估计的评估策略是 同一策略 而在离线策略学习中两者是独立的 评估策略用 贪婪策略进行改进 而行 为策略可以根据具体情况灵活设计 蒙特卡罗学习方法优点是不必依赖于马尔科夫决策过程 在模型未知时也能选择出感 兴趣的状态以求其值函数 而不必遍历所有值函数 2 时间差分时间差分 TD 算法算法 时间差分指的是对同一个变量在连续两个时刻观测到的值的差异 假设在时刻 t 系 统的状态 st的值函数表示为 V st rt为在当前状态下根据某种动作选择策略采取动作 at后 使得状态发生变化转移至新状态 st 1时得到的即时奖赏 状态 st下新的值函数的估计值 1 ttt sVrsV 那么 时刻 t 的时间差分为 1tttt sVsVr TD 方法通过预测每个动作的长期结果来给先前动作赋予奖励或惩罚 即依赖于后续 状态的值函数来更新先前状态值函数的自举方法 主要应用于预测问题 只向后追踪一步的预测问题 TD 0 的迭代公式为 0 1 表示学习率因子 1ttttttt sVsVrsVsVsV 追踪多步的预测问题 TD 的迭代公式为 1tttttttt sesVsVrsVsVsV 为状态的资格迹 对某一特定状态 其资格迹随状态被访问次数的增加而增 t se 加 该状态对整体的影响越大 资格迹定义方式分为增量型和替代型两类 3 Q 学习和学习和 sarsa 学习学习 Q 学习不同于 TD 时序差分算法在于它用状态 动作值函数 Q s a 作为评估函数 而不是 值函数 V s 它只需采取 贪心策略选择动作而无需知道模型就可以保证收敛 是目前最 有效的强化学习算法 在 Q 学习中 Q 都是估计值而不是实际值 是从不同动作的估计值中选择最大 Q 值函数 进行更新 相对于 Q 学习利用模拟 Q 值进行迭代的离线学习 SARSA 学习更像是一种在线 学习 是严格根据策略实时更新 行为决策与值函数迭代是同时进行的 它们之间的区别是更新 Q s a 时 一个用的是根据以往经验预测的最优策略 一个用 的是当前实际动作状态值函数 Q learning max 1 asQasQrasQasQ tt a ttttt Sarsa 1 asQasQrasQasQ ttttttt 4 Q 学习的优化方法学习的优化方法 当传统的强化学习的问题空间 S A 变得庞大的时候 有两个严重的问题影响了强化学 习的实用性 其一是速率问题 S A 数据量庞大 因此强化学习算法常常收敛较慢 其二是复用问题 无论是值函数 V s 还是动作值函数 Q s a 或者是策略 强化学习的结 果总是依赖于 S A 的具体表示 这意味着只要问题略微改变 以前的学习结果就变得毫无用 处 但对于某些实际问题 由于训练代价较高 学习结果的可复用性是非常重要的 这两方面激励了强化学习的迁移 迁移学习就是复用过去的学习经验和结果以加速对 于新任务的学习 传统的强化学习方法适于处理小规模的离散状态或离散动作学习任务而不能求解连续 状态空间和连续动作空间的问题 1 Dyna Q 学习学习 对于环境复杂 信息量大 必须快速学习的情况 例如矿井下的线路规划 Q 学习学 习效率会很低 它需要采集环境中的 足够多 的状态动作对和相应值函数才能收敛 所 花费时间过长 不能及时指定路线 针对这个问题 提出了改进策略 将 Dyna 学习框架加入到 Q 学习中可以利用少许真 实数据建立环境估计模型 然后用规划法产生虚拟样本并更新值函数 这样可以以增加计 算复杂度来降低时间复杂度 Dyna Q 学习与 Q 学习算法过程的区别是真实样本 T 不仅要更新值函数 策略函数 还要更新环境的估计模型 P 模型训练好便可产生虚拟样本自行更新 转在线为离线 集 试错于认知 将得鱼变成了得渔 提高了学习效率 但要处理好学习与规划的平衡问题 2 最小二乘时间差分最小二乘时间差分 Q 算法 算法 LSTDQ Q 学习的查找表形式只适用于求解小规模 离散空间问题 而对于实际大规模或连续 空间问题 智能体不能遍历所有状态 而用最小二乘法策略迭代法即可解决 它主要通过 估计值来逼近动作值函数 其矩阵描述形式为 asQ Q 其中 表示大小为 S A k 的基函数矩阵 T AS TTT asasas 1 1 通过最小二乘不动点逼近法来学习参数 有 RPI 1 其中 P 是大小为 S A S 的矩阵 P s a s P s a s 大小为 S A S 矩阵 sass 输出或 T Aa ass maxarg 最小二乘策略迭代框架如下 3 解决维数灾难的方法解决维数灾难的方法 高维空间训练形成的分类器 相当于在低维空间的一个复杂的非线性分类器 这种分 类器过多的强调了训练集的准确率甚至于对一些错误 异常的数据也进行了学习 而正确的 数据却无法覆盖整个特征空间 维数越多 接近球心样本越稀疏 这导致训练数据量严重 不足 要是这时产生一个错误的新数据就会在预测时产生极大的误差 这种现象称之为过 拟合 同时也是维灾难的直接体现 动态规划问题的维数是指各阶段状态变量的维数 当状态变量的维数增加时 其计算 量会呈指数性增长 产生过拟合使 Q 学习难以收敛 对新数据也缺乏泛化能力