RL1 Preliminaries
1.1 概述
懒的说了,自己百度一下什么都有,或者去看AI世界大入门去
懒的说了,自己百度一下什么都有,或者去看AI世界大入门去
对于天气预报而言,今天是否下雨只取决于前一天的天气情况,无关于前2345...n天的情况。这就是MP(马尔可夫性质,下文简称MP)
换句话来说,一个随机过程在给定现在状态及所有过去状态情况下,其未来状态的条件概率分布仅依赖于当前状态。给出公式如下
此处假设随机变量为一个随机过程。公式代表的含义指需要看每个p的后半部分**(|xxx)**,意思就是前面的都不用看,看个t就行。
MP也可以描述为给定当前状态时,将来的状态与过去状态是条件独立的。如果某一个过程满足马尔可夫性质,那么未来的转移与过去的是独立的,它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。
策略最简单的表示是查找表(look-up table),即表格型策略(tabular policy)。使用查找表的强化学习方法称为表格型方法(tabular method),如蒙特卡洛、Q学习和Sarsa。本章通过最简单的表格型方法来讲解如何使用基于价值的方法求解强化学习问题。(reference:https://datawhalechina.github.io/easy-rl/#/chapter3/chapter3)
基于此,本文介绍三种常用方法,Q表格(Q-table), 时序差分(temporal difference),蒙特卡洛(MC),Sarsa
并稍微给出免模型,有模型,同策略,异策略的定义
直接与环境互动,不考虑环境内的数学公式,特点是通过反复试错来改进策略,但是模拟次数需要很多

当马尔可夫决策过程的模型未知或者模型很 大时,我们可以使用免模型强化学习的方法。免模型强化学习方法没有获取环境的状态转移和奖励函数,而是让智能体与环境进行交互,采集大量的轨迹数据,智能体从轨迹中获取信息来改进策略,从而获得更多的奖励。
先构建虚拟环境,在其中训练后在将模型放在真实环境中执行,特点是学习速度快(虚拟环境可以理解为概率论中的先验知识),但是极度依赖模型的准确性

策略迭代和价值迭代都需要得到环境的转移和奖励函数,所以在这个过程中,智能体没有与环境进行交互。在很多实际的问题中,马尔可夫决策过程的模型有可能是未知的,也有可能因模型太大不能进行迭代的计算,比如雅达利游戏、围棋、控制直升飞机、股票交易等问题,这些问题的状态转移非常复杂。
Q表格可以这样理解,在一个5*5的网格中,每一个网格都会记录最佳策略,当agent走到这步的时候,就可以直接通过查表的方式去决定自己的策略。其实和动态规划的思想差不多。baseline如下
| 动作\状态 | s1 | S2 |
|---|---|---|
| a1 | q_value | q_value |
| a2 | q_value | q_value |
| a3 | q_value | q_value |
q值代表在某个状态下采取某个动作,未来预期能获得的累积奖励总和。初始化一般都可以默认为0
Q表格很好用,但是action和state很多都情况下就太大了,这就是未来会介绍到的DQN算法。当然,本文不介绍,而是介绍几种常见的计算q_value的办法
当然在此之前,我们还需要了解一下同策略和异策略
本文介绍三种算法,简单说就是蒙特卡洛方法 (Monte Carlo, MC),时序差分方法 (Temporal Difference, TD)和SARSA。其中Q-learning和SARSA都是TD的具体实现方法
一句话,**就是大数仿真模拟然后求平均值。**采样大量的轨迹,计算所有轨迹的真实回报,然后计算平均值。
让agent先完整的完成一个回合,然后记录下从某个状态开始到结束所拿到的所有奖励
算法流程
第一个很简单,直接平均就ok了,第二个是增量更新法,也是最常用的一种办法,
是学习率,是误差,决定其收敛,大于0说明鼓励这个动作,小于0说明惩罚这个动作
假设存在这样的一个迷宫
| 起点 | 空地 |
|---|---|
| 陷阱 | 终点 |
Reward:到达终点+10,陷阱-10,移动一步-1
,使用增量更新法,init all q_value in Q table are 0
只模拟三步
| 局数 | 路径 | Gt计算 | Q表更新 |
|---|---|---|---|
| 1 | (1,1) -> (2,1) | -1 + -10 =-11 | Q((1,1), 下) |
| 2 | (1,1) -> (1,2) -> (2, 2) | -1 + 10 =9 -1 - 1 + 10 = 8 | Q((1,2), 下) Q((1,1), 右) |
| 3 | (1,1) -> (1,2) -> (1,1) -> (2,2) | -1 * 4 + 10 =6 | Q((1,1), 右) |
如果是Q table的话,就是这样的
| a\s | (1, 1) | (1, 2) | (2, 1) | (2, 2) |
|---|---|---|---|---|
| 上 | ? | ? | ? | ? |
| 下 | ? | ? | ? | ? |
| 左 | ? | ? | ? | ? |
| 右 | ? | ? | ? | ? |
如果遇见一个坐标是之前计算过的,务必不要忘记使用增量更新法
依旧是一种填表的方法,不同的是TD不需要等一局结束(不需要注意)每走n不就更新一次Q表(也就是TD(n))
以最简单的TD(0)为例,核心公式为
为目前(最好的翻译是以前)这个格子的分数(旧预测),就是TD目标(TD target)
**时序差分误差(TD error)**就是,可以用更新来逼近真实的回报
还是以迷宫为例,只不过这次初始化的是V Table
| 局数 | 路径 | TD error | V值 |
|---|---|---|---|
| 1 | (1, 1) -> (2, 1) | -1 + 1*0 - 0 = -1 | V(1,1) = -0.5 |
| 2 | (1,1) -> (1,2) -> (2, 2) | step1: -1 + 1*0 - (-0.5) = -0.5 step2: -1+10 - 0 = 9 | step1: V(1, 1) = -0.5 + 0.5(-0.5) =-0.75 step2: V(1, 2) = 0 +0.5(9) = 4.5 |
| 3 | (1, 1) -> (1,2) -> (2, 2) | step1: -1 +1*4.5 - (-0.75) =4.25 step2: -1+10-4.5=4.5 | step1: V(1,1) = -0.75 + 0.5(4.25)=1.375 step2: V(1,2) = 4.5+0.5(4.5)=6.75 |
V值在确定TD error的情况下,可以直接简化计算,即
此处还需要引入一个重要概念,V表是有局限性的,尤其是针对model-free的情况,因为V表没有动作a,意思就是不知道应该如何计算状态转移概率,所以这不是一种Q-Table的传统算法。当然,后续的Q-learning和SARSA就是两种计算V表然后再计算Q表的算法了