SARSA时序差分学习方法
什么是SARSA
SARSA算法的全称是State Action Reward State Action,属于时序差分学习算法的一种,其综合了动态规划算法和蒙特卡洛算法,比仅仅使用蒙特卡洛方法速度要快很多。当时序差分学习算法每次更新的动作数为最大步数时,就等价于蒙特卡洛方法。
值函数更新公式的引入:多次试验的平均
SARSA的核心思想在于增量计算。在蒙特卡洛算法中,我们需要对函数进行有效的估计,假设第次试验后值函数为的平均为:
文章图片
其中表示轨迹的起始状态和动作为, 。
【SARSA时序差分学习方法】省却以上公式的中间过程,我们可以将该公式简化为如下:
在该公式中,值函数在第次试验后的值,即次试验的平均等于前次试验再加上一个增量。在该公式中,可以表示成第次试验相对于前次试验的重要性。
值函数更新公式的改进:权重参数的调整
更一般性的,我们可以将权重系数改成一个比较小的正数,由此,以上公式可以被改写成为以下:
其中,增量称为蒙特卡洛误差,表示真实的回报与期望回报之间的差距。
值函数更新公式的改进:累积奖励的计算
在上面的公式中,为一次试验的完整轨迹所得到的总回报,为了提高效率,放宽模型的约束,可以借助动态规划算法来计算,而不需要得到完整的轨迹。
从开始,采样下一步的状态和动作,并得到奖励,然后利用贝尔曼方程来近似估计函数。
文章图片
贝尔曼方程的思想精髓在于动态规划,即当前值的计算依赖于上一时刻的值。对于无最终状态的情况,我们定义了折扣率来重点强调现世的回报。
将以上公式结合,可以得到以下计算公式:
这种策略学习算法称为算法。
通用算法框架:一个示例
一个通用的算法如下所示:
文章图片
SARSA算法框架
该算法的大致逻辑如下:
- 运行完一个回合即一个内循环。
- 运行直到函数收敛即为一个外循环。
- 运行期间动态更新函数,并基于函数更新策略。
推荐阅读
- Dubbo引用服务
- 3.|3. Dubbo服务提供端请求处理流程
- 高校102(上海财经大学|高校102:上海财经大学 专业级差分为3、3、1、1、1)
- 【hexo指南】hexo配置ER图流程图时序图插件
- 从四种时序数据库选型中脱颖而出,TDengine在工控领域边缘侧的应用
- 图论|POJ1364 King 差分约束
- POJ 1364 King 差分约束系统
- POJ|POJ 1364 King 差分约束系统 SPFA
- poj 1364 King 差分约束
- Codeforces Round #531 (Div. 3) E. Monotonic Renumeration(思维+差分数组)