Q-Learning算法实现“Frozen Lake”游戏

这一节将使用 Q-Learning 算法玩“Frozen Lake”游戏。使用的版本是“FrozenLake8X8- V0”,是“8×8”大小的,只有默认的“有风”模式,如图 1 所示。
“FrozenLake8×8-V0”游戏示意图
图 1:“FrozenLake8×8-V0”游戏示意图

图 1 中“S”代表“起始位置”,“G”代表“目标位置”,“F”代表“冰面”,“H”代表“冰窟窿”。该游戏一共有 64(8×8)个状态,每个状态下有四个可以执行的动作(“左移”“下移”“右移”和“上移”)。当智能体到达目标位置后,会得到奖励值 1,其他位置奖励值都为 0。

需要注意的是,如果智能体处在边界状态,例如开始状态“S”,此时采取向边界外移动的动作“左”或“上”都是合法的,只是智能体的状态不发生改变(除非受风的影响,状态改变)。另外,当智能体移动到“H”或“G”状态后,游戏结束。

首先导入所需要的包,并初始化一些相关的参数:
import gym
import numpy as np
import random as rd

#注册游戏环境
env = gym.make('FrozenLake8x8-v0')
#定义Q值表,初始值设为0
Q = np.zeros([env.observation_space. n,env.action_space.n])
#设置学习参数
learningRate = 0.85
discountFactor = 0.95
#定义一个数组,用于保存每一回合得到的奖励
rewardList = []

第 6 行代码的作用是注册一个游戏环境,传入的参数是要注册的游戏名称,这里注册的是“FrozenLake8x8-v0”游戏,也可以换成其他游戏,例如后面会用到的“CartPole-v1”和“Acrobot-v1”。

第 8 行代码定义了 Q 值表,并将初始值设为 0。其中“env.observation_space.n”和“env.action_space.n”分别是“FrozenLake8x8-v0”这个游戏的状态空间和动作空间,其值分别为 64 和 4,所以该 Q 值表的大小为 64×4。

第 10 行和第 11 行代码设置了学习参数,“learningRate”和“discountFactor”分别是 Q-Learning 算法中更新 Q 值的公式中的学习率和折扣因子。

第 13 行代码定义了一个数组“rewardList”用来保存每个回合得到的累积奖励,“FrozenLake8x8-v0”游戏只有在智能体到达目标位置后才会得到奖励值 1,其余状态的奖励值均为 0,所以在所有回合都结束后,将“rewardList”数组的元素值相加,其值即为所有回合中成功到达目标位置的回合数,用该值除以“rewardList”数组的长度就可以得到成功率(成功到达目标位置的回合数/总的回合数)。

接下来实现 Q-Learning 算法的核心部分:
def train():
    for i_episodes in range(20000):
    #重置游戏环境
    s = env.reset()
    i = 0
    # 学习 Q-Table
    while i < 2000:
        i += 1
        #使用带探索(ε贪心算法)的策略选择动作
        a = epsilon_greedy(Q, s, i_episodes)
        #执行动作,并得到新的环境状态、奖励等
        observation, reward, done, info = env.step(a)
        #更新Q值表
        Q[s, a] = (1-learningRate) * Q[s, a] + learningRate * ( reward + discountFactor * np.max(Q[observation,:]))
        s = observation
        if done:
            break

这部分代码实现了对 Q 值表的学习,这里一共执行了 20000个 回合。第 4 行代码是重置游戏环境,此时智能体位于开始位置。第 7 行代码设置循环的目的,是确保智能体能够走到游戏结束状态(智能体可能到达了目标位置,也可能掉进了“冰窟窿”)。

第 10 行代码使用了带探索的策略(ε 贪心算法)来选取动作,“epsilon_greedy”函数的实现稍后介绍。第 12 行代码执行了前一步选择的动作,并得到相应的反馈信息,其中,“observation”是执行这个动作后得到的新的环境状态,“reward”是执行这个动作后得到的奖励,“done”是一个布尔类型的数据,当“done”的值为True 时代表游戏结束。“info”是用于调试程序的诊断信息。

第 14 行代码就是 Q-Learning 算法中对于 Q 值的更新,算法中更新 Q 值的公式为:

Q(s, a)←Q(s, a)+α[R+γmax(Q(s', a'))-Q(s, a)]     式 1

将式 1 稍作变换即为:

Q(s, a)←(1-a)*Q(s, a)+α[R+γmax(Q(s', a'))]       式 2


第 15 行代码更新了当前的环境状态,第 16 行代码判断一个回合的游戏是否结束。接下来再看如何使用带探索的策略来选择动作,即如何对环境进行探索。代码如下:
def epsilon_greedy(q_table, s, num_episodes):
    rand_num = rd.randint(0, 20000)
    if rand_num > num_episodes:
        #随机选择一个动作
        action = rd.randint(0, 3)
    else :
        #选择一个最优的动作
        action = np.argmax(q_table[s, :])
    return action
这里使用 ε 贪心搜索方法来对环境进行探索,ε 贪心搜索以概率 ε 从所有可能的动作中随机选取一个动作(即对环境进行探索),以 1−ε 的概率选择已知的最好的动作(即当前状态下,Q 值最大的那个动作)。

需要注意的是,对于环境的探索应主要集中在学习 Q 值表的开始阶段,随着 Q 值表的完善,我们应更注重对于 Q 值表的使用。所以,初期,ε 的值应更大一些(即注重对环境的探索),随后逐渐减小ε的值(即注重对于 Q 值表的使用)。

第 2 行代码生成一个介于 0 到 20000 之间(包括 0 和 20000)的随机整数“rand_num”,“num_episodes”是当前的回合数(一共有 20000 个回合,标号从 0 到 19999),当“rand_num”的值大于当前的回合数“num_episodes”时,从所有合法动作中随机选择一个动作,否则选择一个最优的动作。

当“num_episodes”的值很小时,“rand_num”的值大于“num_episodes”的概率更大,而随着回合数的增加,“rand_num”的值小于“num_episodes”的概率变得更大,从而实现ε的值随着回合数的增加而递减。

第 5 行代码随机选择了一个动作,0 到 3 分别对应动作“左移”“下移”“右移”和“上移”。第 8 行代码选择了当前状态 s 下最优的动作。

还有一种简单的方法也可以实现对环境的探索,不需要“epsilon_greedy”函数,直接把“a = epsilon_greedy(Q, s, i_episodes)”这行代码改为如下形式:
a = np.argmax(Q[s, :] + np.random.randn(1, env.action_space.n) * (1. /(i_episodes + 1)))

这里我们通过给当前状态的 Q 值(4 个动作对应 4 个 Q 值)分别加上一个随机数来影响动作的选择,由于随机数的原因,当前动作的选择也具有了随机性,另外给随机数乘上了一个折扣率,并且随着回合数的增加,折扣率越来越小,这个随机数对于动作选择的影响也越来越小,从而实现对环境的探索。

接下来写一个测试函数,利用学到的 Q 值表来玩“FrozenLake8×8-v0”游戏。
def test():
    for i_episodes in range(100):
        #重置游戏环境
        s = env.reset()
        i = 0
        total_reward = 0
        while i < 500:
            i += 1
            #选择一个动作
            a = np.argmax(Q[s, :])
            #执行动作,并得到新的环境状态、奖励等
            observation, reward, done, info = env.step(a)
            #可视化游戏画面(重绘一帧画面)
            env.render()
            #计算当前回合的总奖励值
            total_reward += reward
            s = observation
            if done:
                break
        rewardList.append(total_reward)
在测试代码中,我们一共玩了 100 个回合,其中使用了一个参数“total_reward”来统计每一回合得到的累积奖励,当智能体掉进“冰窟窿”或者到达目标位置后,一回合的游戏结束,此时“total_reward”的值分别为 0 和 1。

最后执行完整的程序:
train()
test()
print("Final Q-Table Values: ")
print(Q)
print("Success rate: " + str(sum(rewardList)/len(rewardList)))

在第 4 行代码中我们输出了最终的 Q 值表,是一张 16×4 的表,其中行代表状态(从状态 1 到状态 64,对应图 1,状态从上到下、从左至右进行编号),列代表动作(下标 0 到 3 分别对应动作“左移”“下移”“右移”“上移”)。在第 5 行代码,我们用成功到达目标位置的回合数“sum(rewardList)”除以总的回合数“len(rewardList)”得到了智能体玩“FrozenLake8x8-v0”游戏的成功率。