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-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