强化学习入门-第二讲--基于模型的强化学习

机器人与信息自动化研究所InstituteofRobotics&AutomaticInformationSystem每周工作报告南开大学机器人与信息自动化研究所强化学习入门第二讲郭宪2017.3.4InstituteofRoboticsandAutomaticInformationSystem强化学习的形式化强化学习目标：max𝜋   𝑅𝜏𝑝𝜋𝜏𝑑𝜏环境机器人观测回报r动作𝑨新的状态S状态转移概率𝑃𝑆𝑡+1|S𝑡,𝑎马尔科夫决策问题(MDP):四元组𝑆,𝐴,𝑃,𝑟策略：常采用随机策略：𝜋:𝑠→𝑢。𝜋𝑢|𝑠累积回报:𝑅𝜏=𝑟𝑇𝑥𝑇+𝑟𝑡𝑥𝑡,𝑢𝑡𝑇−1𝑡=0折扣回报:𝑅=𝛾𝑡𝑟𝑡∞𝑡=0值函数最优策略：**su：𝑠0𝑢0∗𝑠1𝑢1∗⋯𝑠T序贯决策问题InstituteofRoboticsandAutomaticInformationSystem强化学习方法分类序贯决策问题马尔科夫决策过程MDP𝑆,𝐴,𝑃,𝑅,𝛾基于模型的动态规划方法无模型的强化学习方法𝑆,𝐴,𝑃,𝑅,𝛾𝑆,𝐴,𝑃？𝑅？𝛾？策略迭代值迭代策略搜索本节讲基于模型的策略迭代算法和值迭代算法策略搜索offlineonline策略迭代offlineonline值迭代offlineonlineInstituteofRoboticsandAutomaticInformationSystem动态规划动态规划是一类算法：包括离散和连续。动态：蕴含着序列决策规划：蕴含着优化，如线性优化，二次优化或者非线性优化。动态规划可以解决的问题：1.整个优化问题可以分解成多个子优化问题2.子优化问题的解可以被存储和重复利用马尔科夫决策过程（MDP），贝尔曼最优性原理，得到贝尔曼最优化方程：𝜐∗𝑠=max𝑎𝑅𝑠𝑎+𝛾𝑃ss′𝑎𝑠′∈𝑆𝜐∗𝑠′𝑞∗𝑠,𝑎=𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎max𝑎′𝑠′∈𝑆𝑞∗𝑠′,𝑎′动态规划可以解决MDP的问题核心：动态规划通过值函数来迭代构造最优解InstituteofRoboticsandAutomaticInformationSystem策略评估(policyevaluation)给定策略构造值函数：𝜋𝜐𝜋𝑠←𝑠𝑞𝜋𝑠,𝑎←𝑠,𝑎𝜐𝜋𝑠′←𝑠′𝜐𝜋𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝑣𝜋𝑠′𝑠′∈𝑆𝑣𝜋𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑞𝜋𝑠,𝑎𝑞𝜋𝑠,𝑎=𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝑠′∈𝑆𝑣𝜋𝑠′模型已知，方程组中只有值函数是未知数，方程组是线性方程组。未知数的数目等于状态的数目。采用数值迭代算法InstituteofRoboticsandAutomaticInformationSystem策略评估(policyevaluation)𝜐𝜋𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝑣𝜋𝑠′𝑠′∈𝑆𝜐𝑘+1𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝜐𝑘𝑠′𝑠′∈𝑆高斯-赛德尔迭代策略评估算法输入：需要评估的策略状态转移概率回报函数，折扣因子𝜋𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：𝑉𝑠=0Repeatk=0,1,…foreverysdo𝜐𝑘+1𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝜐𝑘𝑠′𝑠′∈𝑆endforUntil𝜐𝑘+1=𝜐𝑘输出：𝜐𝑠一次状态扫描[1][2][3][5][4][6][7][8]InstituteofRoboticsandAutomaticInformationSystem策略评估(policyevaluation)策略评估算法输入：需要评估的策略状态转移概率回报函数，折扣因子𝜋𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：𝑉𝑠=0Repeatk=0,1,…foreverysdo𝜐𝑘+1𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝜐𝑘𝑠′𝑠′∈𝑆endforUntil𝜐𝑘+1=𝜐𝑘输出：𝜐𝑠一次状态扫描状态空间：S={1,2..14}动作空间:{东，南，西，北}回报函数：-1，直到终止状态均匀随机策略：𝜋东|⋅=0.25，    𝜋南|⋅=0.25，    𝜋西|⋅=0.25，   𝜋北|⋅=0.251234567810911121314动作MDPInstituteofRoboticsandAutomaticInformationSystem策略评估算法输入：需要评估的策略状态转移概率回报函数，折扣因子𝜋𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：𝑉𝑠=0Repeatk=0,1,…foreverysdo𝜐𝑘+1𝑠=𝜋𝑎|𝑠𝑎∈𝐴𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝜐𝑘𝑠′𝑠′∈𝑆endforUntil𝜐𝑘+1=𝜐𝑘输出：𝜐𝑠一次状态扫描策略评估(policyevaluation)-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.0K=10.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.00.0K=00.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.7K=20.00.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.4K=30.00.0InstituteofRoboticsandAutomaticInformationSystem策略改进(policyimprovement)计算策略值的目的是为了帮助找到更好的策略，在每个状态采用贪婪策略。𝜋𝑙+1𝑠∈arg  max𝑎   𝑞𝜋𝑙𝑠,𝑎-14-20-22-20-18-20-18-14-20-20-14-22-20-140.00.0𝐾=∞0.00.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.1K=100.00.00.00.0𝜋0均匀策略：𝜋1贪婪策略：𝜐𝜋𝑠←𝑠𝑞𝜋𝑠,𝑎←𝑠,𝑎𝜐𝜋𝑠′←𝑠′𝑞𝜋𝑠,𝑎=𝑅𝑠𝑎+𝛾𝑃𝑠𝑠′𝑎𝑠′∈𝑆𝑣𝜋𝑠′𝑠,𝑎→𝑞𝜋𝑠,𝑎max𝑅𝑠𝑎𝑅𝑠𝑎InstituteofRoboticsandAutomaticInformationSystem策略迭代(policyiteration)V策略评估策略改进𝑉∗𝑉𝜋𝑉=𝑉𝜋𝜋=𝑔𝑟𝑒𝑒𝑑𝑦𝑉Policyimprovement策略迭代算法输入：状态转移概率回报函数，折扣因子𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：初始化策略𝑉𝑠=0输出：Repeatl=0,1,…find𝜋0𝑉𝜋𝑙Policyevaluation𝜋𝑙+1𝑠∈arg  max𝑎   𝑞𝜋𝑙𝑠,𝑎Until𝜋𝑙+1=𝜋𝑙𝜋∗=𝜋𝑙[1][2][3][5][4][6]InstituteofRoboticsandAutomaticInformationSystem值函数迭代策略改进一定要等到值函数收敛吗？当K=1时便进行策略改进，得到值函数迭代算法𝜐∗𝑠=max𝑎𝑅𝑠𝑎+𝛾𝑃ss′𝑎𝑠′∈𝑆𝜐∗𝑠′-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.1K=100.00.00.00.0𝐾=∞0.00.0-14-20-22-20-18-20-18-14-20-20-14-22-20-140.00.0𝜋0均匀策略：𝜋1贪婪策略：输入：状态转移概率回报函数，折扣因子𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：初始化策略𝑠=0输出：𝜋0UntilRepeatl=0,1,…foreverysdo𝜐𝑙+1𝑠=max𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 𝜐𝜐𝑙+1=𝜐𝑙𝜋𝑠=argmax𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 [1][2][3][5][4][6]InstituteofRoboticsandAutomaticInformationSystem值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：初始化策略𝑠=0输出：𝜋0UntilRepeatl=0,1,…foreverysdo𝜐𝑙+1𝑠=max𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 𝜐𝜐𝑙+1=𝜐𝑙𝜋𝑠=argmax𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 值函数迭代算法00X=,,ftXUXtX状态方程：性能指标函数：000,,,,ftfftJxttXttLxtutt最优控制问题：0,min,,,ftfftuVXtXttLxtuttBellman最优性原理：0,min,,,ftfftuVXtXttLxtuttmin,,,,TutUVVLxtuttfxtutttX2.利用变分法，将微分方程转化成变分代数方程，在标称轨迹展开，得到微分动态规划DDP1.将值函数进行离散，进行数值求解。InstituteofRoboticsandAutomaticInformationSystem值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：初始化策略𝑠=0输出：𝜋0UntilRepeatl=0,1,…foreverysdo𝜐𝑙+1𝑠=max𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 𝜐𝜐𝑙+1=𝜐𝑙𝜋𝑠=argmax𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 值函数迭代算法min,,,,TutUVVLxtuttfxtutttX此式是关于值函数的偏微分方程，利用数值算法可进行迭代计算值函数。From胡亚楠博士论文InstituteofRoboticsandAutomaticInformationSystem值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子𝑃𝑠𝑠′𝑎𝑅𝑠𝑎𝛾初始化值函数：初始化策略𝑠=0输出：𝜋0UntilRepeatl=0,1,…foreverysdo𝜐𝑙+1𝑠=max𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 𝜐𝜐𝑙+1=𝜐𝑙𝜋𝑠=argmax𝑎 𝑅𝑠𝑎+ 𝛾𝑃𝑠𝑠′𝑎𝜐𝑙𝑠′𝑠′∈𝑆 值函数迭代算法𝑉𝑋,𝑡=min𝑢∈𝛺𝜙𝑋𝑡𝑓,𝑡𝑓+𝐿𝑥𝑡,𝑢𝑡,𝑡𝑡𝑓𝑡0=min𝑢∈𝛺𝐿𝑥𝜏,𝑢𝜏,𝜏𝑑𝜏+𝑉𝑋+𝛥𝑋,𝑡+𝑑𝑡𝑡0+𝑑𝑡𝑡01,2TTTuuuxxuTTTTTuuxxxxQxuuQuuQxxQuQuuQxQxxQQx*1argm