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

强化学习入门第二讲郭宪2017.3.4强化学习的形式化强化学习目标：

环境机器人观测回报r动作

新的状态S状态转移概率

马尔科夫决策问题(MDP):四元组

策略：常采用随机策略：

累积回报:

折扣回报:

值函数最优策略：

序贯决策问题强化学习方法分类序贯决策问题马尔科夫决策过程MDP

基于模型的动态规划方法无模型的强化学习方法

策略迭代值迭代策略搜索本节讲基于模型的策略迭代算法和值迭代算法策略搜索offlineonline策略迭代offlineonline值迭代offlineonline动态规划动态规划是一类算法：包括离散和连续。动态：蕴含着序列决策规划：蕴含着优化，如线性优化，二次优化或者非线性优化。动态规划可以解决的问题：1.整个优化问题可以分解成多个子优化问题2.子优化问题的解可以被存储和重复利用马尔科夫决策过程（MDP），贝尔曼最优性原理，得到贝尔曼最优化方程：

动态规划可以解决MDP的问题核心：动态规划通过值函数来迭代构造最优解策略评估(policyevaluation)给定策略构造值函数：

模型已知，方程组中只有值函数是未知数，方程组是线性方程组。未知数的数目等于状态的数目。采用数值迭代算法策略评估(policyevaluation)

高斯-赛德尔迭代策略评估算法输入：需要评估的策略状态转移概率回报函数，折扣因子

初始化值函数：

Repeatk=0,1,…

foreverysdo

Until

输出：

一次状态扫描[1][2][3][5][4][6][7][8]策略评估(policyevaluation)策略评估算法输入：需要评估的策略状态转移概率回报函数，折扣因子

初始化值函数：

Repeatk=0,1,…

foreverysdo

Until

输出：

一次状态扫描状态空间：S={1,2..14}动作空间:{东，南，西，北}回报函数：-1，直到终止状态均匀随机策略：

1234567810911121314动作MDP策略评估算法输入：需要评估的策略状态转移概率回报函数，折扣因子

初始化值函数：

Repeatk=0,1,…

foreverysdo

Until

输出：

一次状态扫描策略评估(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.0策略改进(policyimprovement)计算策略值的目的是为了帮助找到更好的策略，在每个状态采用贪婪策略。

-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

max

策略迭代(policyiteration)策略评估策略改进

Policyimprovement策略迭代算法输入：状态转移概率回报函数，折扣因子

初始化值函数：初始化策略

输出：Repeatl=0,1,…

find

Policyevaluation

Until

[1][2][3][5][4][6]值函数迭代策略改进一定要等到值函数收敛吗？当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.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

输入：状态转移概率回报函数，折扣因子

初始化值函数：初始化策略

输出：

UntilRepeatl=0,1,…

foreverysdo

[1][2][3][5][4][6]值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子

初始化值函数：初始化策略

输出：

UntilRepeatl=0,1,…

foreverysdo

值函数迭代算法状态方程：性能指标函数：最优控制问题：Bellman最优性原理：2.利用变分法，将微分方程转化成变分代数方程，在标称轨迹展开，得到微分动态规划DDP1.将值函数进行离散，进行数值求解。值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子

初始化值函数：初始化策略

输出：

UntilRepeatl=0,1,…

foreverysdo

值函数迭代算法此式是关于值函数的偏微分方程，利用数值算法可进行迭代计算值函数。From胡亚楠博士论文值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子

初始化值函数：初始化策略

输出：

UntilRepeatl=0,1,…

foreverysdo

值函数迭代算法

贪婪策略：

利用变分法，将微分方程转化成变分代数方程微分动态规划方法微分动态规划：1.前向迭代：给定初始控制序列正向迭代计算标称轨迹2.反向迭代：由代价函数边界条件反向迭代计算（1）,（2）,(3)得到

序列

（1）（3）（2）3.正向迭代新的控制序列：值函数迭代与最优控制输入：状态转移概率回报函数，折扣因子

初始化值函数：初始化策略

输出：

UntilRepeatl=0,1,…

foreverysdo

值函数迭代算法微分动态规划：1.前向迭代：给定初始控制序