5.4 Sarsa算法

Sarsa算法基于∈-贪婪算法进行选择,然后以如下方式迭代更新Q函数。

其中,表示学习率,表示衰减因子。st 和at 分别表示当前的状态以及采取的动作,st+1 和at+1 分别表示下一个的状态以及采取的动作,rt+1 表示当前状态采取动作后得到的奖励。

Sarsa算法的实现过程使用伪码描述如下:


初始化Q函数
while 没有达到设置的学习次数
{
        初始化状态s0为随机值
        根据∈-贪婪算法选择状态s0对应的动作a0
        while 没有达到设置的学习步长并且s0不是结束状态
        {
                执行行为a0转移到状态s1,得到回报r
                根据∈-贪婪算法选择状态s1对应的动作a1
            更新Q(s0,a0)
                s0=s1  
                a0=a1
        }
}

案例5-1:使用Sarsa算法处理金币问题

在经典的金币问题(见图5-3)中,一共有8个格子,也可以理解有8种状态,选手随机从这8个格子中的一个出发,如果达到7号格子,表明拿到了金币,游戏结束;如果达到6或者8号格子,表明选手死亡,游戏也结束。选手可以在这个8个格子中上下左右移动,但是不允许走出格子。我们尝试使用Sarsa算法来处理这个问题,本例代码在本书对应的GitHub的code/sarsa-gold.py文件。

图5-3 金币问题

我们首先定义一些全局变量,用于保存一些全局需要使用的数据,定义状态空间states和动作空间actions。Q函数是一个二维数组,但是我们通过定义字典的键值形式为state_action,那么就可以把这个二维数组以字典类型变量Q的形式保存,代码如下:


states = [1, 2, 3, 4, 5, 6, 7, 8]
actions = ['n', 'e', 's', 'w']
Q = dict()

定义Sarsa算法涉及的全局系数,比如学习系数alpha,衰减因子gamma以及∈-贪婪算法的epsilon:


alpha=0.1
gamma=0.5
epsilon=0.1

通过遍历状态空间和动作空间,初始化Q函数,全部设置为0:


for s in states:
    for a in actions:
        key = "%d_%s"%(s,a)
        Q[key]=0

假设学习的次数为1000次,每次学习开始的时候,随机设置当前状态s0,并且根据∈-贪婪算法获得对应的动作a0:


for episode in range(100):
    s0 = env.reset()
    a0 = epsilon_greedy(Q,s0,epsilon)

设置一个学习周期内学习步长为20,因为游戏确实比较简单,一次学习过程走20步足够了:


for t in range(20):

使用a0作用于环境,转移到状态s1,得到奖励值reward:


observation, reward, done, info = env.step(a0)
s1=observation

根据∈-贪婪算法获得s1对应的动作a1:


a1 = epsilon_greedy(Q,s1,epsilon)

根据Sarsa算法更新Q函数,并重新设置s0和a0的值:


key0="%d_%s" % (s0, a0)
key1="%d_%s" % (s1, a1)
#更新Q函数
Q[key0] = Q[key0] + alpha * (reward + gamma * Q[key1] - Q[key0])
a0=a1
s0=s1

如果最新状态表明游戏已经结束,完成本次循环:


if done :
     print("Episode finished after {} timesteps ".format(t + 1))
    break

运行程序,发现999次学习过程,拿到金币的次数为711次,其中120次是初始状态就在7,即一开始就拿到金币了,另外有270次初始状态为6或者8,即一开始就结束了,真正玩死的次数为18。


Get Gold 994th Episode finished after 3 timesteps
Get Gold 995th Episode finished after 5 timesteps
Get Gold 996th Episode finished after 3 timesteps
Get Gold 997th Episode finished after 3 timesteps
episode:999 get gold:591 bad luck:270 good luck:120 lose:18