北大旁听 - 强化学习

强化学习、马尔可夫、蒙特卡洛采样法、SARSA、Q-learning

博客推荐:强化学习总结

1. 强化学习基本概念

概念:agent(智能体)、environment(环境,可观察,有状态)、reward(回报)、observation(观察)、state(环境观察结果)、action(决策,agent学习的东西,当环境会变化时,决策通常表现为概率模型)。

基本概念1

基本概念2

Policy是最终要求取的结果,经常会被表示成Π(a|s),要注意的是Reward表示为短期回报,Value表示为长期回报。

强化学习可以看做是智能体与环境的交互的过程,可以看作是一个马尔可夫决策过程

1.1 马尔可夫

马尔可夫

马尔可夫轨迹

马尔可夫理论

正因为这套理论,当Policy稳定时,强化学习得以训练。

1.2 回合(Episode)

回合

1.3 目标

目标

这里的Π(θ)(a|s)就是Policy,强化学习的最终目标。

1.4 基本途径

  • Value based,关注点是找到最优奖励总和,这一类方法最多;
  • Policy based,关注点是找到最优策略;
  • Action based,关注点是每一步的最优行动。

2. 基于值的强化学习方法

2.1 Value函数定义

我们对策略的调整,总是基于以下两个回报的对比:

  • 当前状态下,智能体按照现有策略执行动作,所能获得的平均回报(期望);
  • 当前状态下,智能体在选择某个动作a的前提下,所能获得的平均回报(期望)。

举例:高考,一个是按已有的状态考北大,一个是说考清华就给1000w的前提下做决策。

定义Value函数

具体Value函数定义

2.2 Bellman方程

bellman方程

这个式子和反向传播的链式法则一样,知道后面的reward和state就可以往前去算了(动态规划)。

bellman方程2

2.3 计算值函数的方法

Value计算方法

MDP已知:Policy完全可见,但大多数情况下MDP是未知的。在时许差分学习方法中常用的就是SARSA、Q-learning。

2.3.1 策略迭代方法(最笨的方法,阐述了强化学习最基本的逻辑)

策略迭代方法

2.3.2 值迭代算法

值迭代算法

简单,容易收敛,可能没有策略迭代法准确,是典型的动态规划算法。

以上两种方法都是基于模型的强化学习方法,实际上就是动态规划算法,但由于

  • 要求模型已知,即要给出马尔可夫决策过程的状态转移概率p和奖励函数r,这个要求很难满足;
  • 效率问题,很多问题的状态数量和动作数量非常多。

导致这种方法不实用,如果模型未知,Q函数可以通过采样来进行计算,这就是蒙特卡洛方法。

2.3.4 蒙特卡洛采样方法

蒙特卡洛方法

greedy-method

首先构造一个概率,然后按概率随机选择A中的动作,再使用蒙特卡洛采样法。

但仍然存在问题:需要拿到完整轨迹,才能评估并更新模型,效率低。为了不拿到完整轨迹,就使用到了时序差分学习方法。

蒙特卡洛问题解决方法

对于最后一个式子的解释:是办法二和办法一公式的叠加,就是对Q-hat(加hat是因为是估算的)的更新过程,括号内的代表真实回报和期望回报的差距,真实回报的计算方法就是当前回报加上之前用计算过的回报来近似的回报。

2.3.5 时序查分学习方法 - SARSA算法

sarsa算法

中途选择动作e-greedy是因为想跳转到所有状态上。

只要Q(s, a)收敛了,Policy就稳定了。

这实际上是一个很保守的算法,每个episode都会看一下下一步动作并更新参数,所以遇到比较危险的aciton时,会绕开不敢走。

2.3.6 Q-Learning

Q-Learning

比SARSA算法更“虎”,直接选择真实回报最大的action来更新Q,学的快。

所以应该虎了吧唧的先把事情做完,再去修改……(雾……

2.3.7 Q-Learning示例

如何定义一个环境:

  • 一定要给出所有状态;
  • 一定要确定reward。

示例

开始执行Q-Learning算法,目的是要让Q收敛(无论怎么运行Q不再变化):

  • 从任意一个状态S开始,尝试做不同的动作。比如说从房间1开始;
  • 从R中看出1能做动作3、5,但在Q中3和5的概率都是0,所以就随机选择;
  • 假设执行动作a,随机选择了5;Q(1, 5) = R(1, 5) + α(max{Q(5)[0, 0, 0]}) - 0 = 100(假设α=0.8);
  • 假设初始状态为3,则可能走1、2、4,假设随机跳转到1;
  • 则Q(3, 1) = R(3, 1) + α(max{Q(1)[0, 100]}) - 0 = 80;

经过很多轮后,矩阵Q收敛:

示例2

则可以确定Policy,处于0的时候选4、1的时候选5、2的时候选3、3的时候选1或4、4的时候选5、5的时候选5。

2.3.8 Q-Learning的问题

Q-Learning的问题

所以这就是Deep Q-Learning登场的时候了,用来模拟Q(状态转换矩阵)。给一个S,一个A就可以输出Q。

2.3.9 Deep Q-Learning

Deep Q-Learning

目标:用一个网络实现Q函数。

两个问题:

  • 真实值和期望值同的一个网络计算,使得网络很难收敛;
  • 样本之间有很强的相关性,模型容易陷入局部最优(local optima)。

解决办法:

  • 搞两个一样的网络,在一个时间段内固定目标网络中的参数,来稳定学习目标(Freezing Target,常用,就像共振一样);
  • 搞一个经验池,由agent最近的经历组成的数据集,训练时,随机提取历史样本代替当前样本用来训练(Experience Replay);

这是标准的训练方法。

Deep Q-Learning训练方法

2.4 总结

基于值的强化学习方法总结