,机器人与信息自动化研究所,Institute of Robotics&Automatic Information System,每周工作报告 南开大学机器人与信息自动化研究所,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,Institute of Robotics and Automatic Information System,强化学习入门第二讲,郭宪,2017.3.4,强化学习入门第二讲郭宪,1,强化,学习的形式化,强化学习目标：,环境,机器人,观测,回报,r,动作,新的状态,S,状态转移概率,马尔科夫决策问题,(MDP):,四元组,策略：,常采用随机策略：,累积回报,:,折扣,回报,:,值函数,最优策略：,序贯决策问题,强化学习的形式化强化学习目标：环境机器人观测动作新的状态,2,强化,学习方法分类,序贯决策问题,马尔科夫决策过程,MDP,基于模型的,动态规划,方法,无模型的强化学习方法,策略迭代,值,迭代,策略搜索,本节讲基于模型的,策略迭代算法,和,值迭代算法,策略搜索,offline,online,策略迭代,offline,online,值,迭代,offline,online,强化学习方法分类序贯决策问题马尔科夫决策过程 MDP基于模,3,动态规划,动态规划是一类算法：包括离散和连续。,动态,：蕴含着序列决策,规划,：蕴含着优化，如线性优化，二次优化或者非线性优化。,动态规划可以解决的问题：,1.,整个优化问题可以分解成多个子优化问题,2,.,子优化问题的解可以被存储和重复利用,马尔科夫决策过程（,MDP,），贝尔曼最优性原理，得到,贝尔曼最优化方程,：,动态规划可以解决,MDP,的问题,核心：动态规划通过,值函数,来迭代构造最优解,动态规划动态规划是一类算法：包括离散和连续。动态：蕴含着序列,4,策略评估,(policy evaluation),给定策略 构造值函数：,模型已知，方程组中只有值函数是未知数，方程组是线性方程组。未知数的数目等于状态的数目。,采用数值迭代算法,策略评估(policy evaluation)给定策略 构,5,策略评估,(policy evaluation),高斯,-,赛德尔迭代,策略评估,算法,输入：需要评估的策略 状态转移概率 回报函数 ，折扣因子,初始化值函数：,Repeat k=0,1,for,every s,do,Until,输出：,一次状态扫描,1,2,3,5,4,6,7,8,策略评估(policy evaluation)高斯-赛德,6,策略评估,(policy evaluation),策略评估算法,输入：需要评估的策略 状态转移概率 回报函数 ，折扣因子,初始化值函数：,Repeat k=0,1,for,every s,do,Until,输出：,一次状态扫描,状态空间：,S=1,2.14,动作空间,:,东，南，西，北,回报函数：,-1,，直到终止状态,均匀随机策略：,1,2,3,4,5,6,7,8,10,9,11,12,13,14,动作,MDP,策略评估(policy evaluation)策略评估算法输,7,策略评估算法,输入：需要评估的策略 状态转移概率 回报函数 ，折扣因子,初始化值函数：,Repeat k=0,1,for,every s,do,Until,输出：,一次状态扫描,策略评估,(policy evaluation),-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,-1.0,K=1,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,K=0,0.0,-1.7,-2.0,-2.0,-2.0,-2.0,-2.0,-2.0,-1.7,-2.0,-2.0,-1.7,-2.0,-2.0,-1.7,K=2,0.0,0.0,-2.4,-2.9,-3.0,-2.9,-2.9,-3.0,-2.9,-2.4,-2.9,-3.0,-2.4,-3.0,-2.9,-2.4,K=3,0.0,0.0,策略评估算法输入：需要评估的策略 状态转移概率 回报函,8,策略,改进,(policy improvement),计算策略值的目的是为了,帮助找到更好的策略,，在每个状态采用贪婪策略。,-14,-20,-22,-20,-18,-20,-18,-14,-20,-20,-14,-22,-20,-14,0.0,0.0,0.0,0.0,-6.1,-8.4,-9.0,-8.4,-7.7,-8.4,-7.7,-6.1,-8.4,-8.4,-6.1,-9.0,-8.4,-6.1,K=10,0.0,0.0,0.0,0.0,max,策略改进(policy improvement)计算策略值的,9,策略,迭代,(policy,iteration,),策略评估,策略改进,Policy improvement,策略,迭代,算法,输入：状态转移概率 回报函数 ，折扣因子,初始化值函数：初始化策略,输出：,Repeat l=0,1,find,Policy evaluation,Until,1,2,3,5,4,6,策略迭代(policy iteration)策略评估策略改进,10,值函数,迭代,策略改进一定要等到值函数收敛吗？,当,K=1,时便进行策略改进，得到值函数迭代算法,-6.1,-8.4,-9.0,-8.4,-7.7,-8.4,-7.7,-6.1,-8.4,-8.4,-6.1,-9.0,-8.4,-6.1,K=10,0.0,0.0,0.0,0.0,0.0,0.0,-14,-20,-22,-20,-18,-20,-18,-14,-20,-20,-14,-22,-20,-14,0.0,0.0,输入：状态转移概率 回报函数 ，折扣因子,初始化值函数：初始化策略,输出：,Until,Repeat l=0,1,for,every s,do,1,2,3,5,4,6,值函数迭代策略改进一定要等到值函数收敛吗？当K=1时便进行策,11,值函数,迭代与最优控制,输入：状态转移概率 回报函数 ，折扣因子,初始化值函数：初始化策略,输出：,Until,Repeat l=0,1,for,every s,do,值,函数迭代算法,状态方程：,性能指标函数：,最优控制问题：,Bellman,最优性原理：,2.,利用变分法，将微分方程转化成变分代数方程，在标称轨迹展开，得到微分动态规划,DDP,1.,将值函数进行离散，进行数值求解。,值函数迭代与最优控制输入：状态转移概率 回报函数 ，,12,值函数,迭代与最优控制,输入：状态转移概率 回报函数 ，折扣因子,初始化值函数：初始化策略,输出：,Until,Repeat l=0,1,for,every s,do,值,函数迭代算法,此式是关于值函数的偏微分方程，利用数值算法可进行迭代计算值函数。,From,胡亚楠博士论文,值函数迭代与最优控制输入：状态转移概率 回报函数 ，,13,值函数,迭代与最优控制,输入：状态转移概率 回报函数 ，折扣因子,初始化值函数：初始化策略,输出：,Until,Repeat l=0,1,for,every s,do,值,函数迭代算法,贪婪策略：,利用变分法，将微分方程转化,成,变分,代数方程,值函数迭代与最优控制输入：状态转移概率 回报函数 ，,14,微分动态规划,方法,微分动态规划：,1.,前向迭代：给定初始控制序列 正向迭代计算标称轨迹,2.,反向迭代：由代价函数边界条件 反向迭代计算（,1,）,（,2,）,(3),得到,序列,（,1,）,（,3,）,（,2,）,3.,正向迭代新的控制序列：,微分动态规划方法微分动态规划：1.前向迭代：给定初始控制序,15,值函数,迭代与最优控制,输入：状态转移概率 回报函数 ，折扣因子,初始化值函数：初始化策略,输出：,Until,Repeat l=0,1,for,every s,do,值,函数迭代算法,微分动态规划：,1.,前向迭代：给定初始控制序列 正向迭代计算标称轨迹,2.,反向迭代：由代价函数边界条件 反向迭代计算（,1,）,（,2,）,(3),得到,序列,3.,正向迭代新的控制序列：,值函数迭代与最优控制输入：状态转移概率 回报函数 ，,16,基于模型的其他方法,逼近动态规划（逼近值函数）,基于模型的策略搜索（,dynamic,）,异步动态规划,实时动态规划,Guided policy search,基于模型的其他方法逼近动态规划（逼近值函数）,17,