蒙特卡罗方法

在有模型的强化学习方法中,我们拥有环境的完整描述(例如状态转移概率 P 和奖励 R),因此,可以使用动态规划的方法求解策略。然而在实际情况中,我们很少会有这么详细的环境信息(例如“Frozen Lake”游戏),这时就需要智能体自己去探索环境,并寻找策略。我们称这种情况为无模型(Model-free)的强化学习方法。这也是强化学习问题中最常使用的方法。

蒙特卡罗方法(Monte Carlo Methods)又称为统计模拟方法,是无模型强化学方法,通过前面的学习,我们知道实际上 Q 值函数(动作- 价值函数)其实就是一个期望,可以直接使用采样来代替期望。蒙特卡罗方法的思想是:对于某个随机事件,可以通过重复实验来得到该随机事件发生的概率,以此频率来近似替代该事件发生的概率。具体思路如下。

1.策略估计和策略改进

在策略迭代算法中的策略估计部分,由于中间动作(或状态)的奖励 R 是已知的,所以只要按照当前策略走一遍,就可以得到当前状态的价值。而在无模型的强化学习方法中,由于不知道中间动作(或状态)的奖励,所以如果想要知道某个状态的价值,就需要从这个状态出发,按照当前策略,走完多个回合并得到多个累积奖励,然后计算多个累积奖励的平均值作为当前状态的价值,即用采样去逼近真实的值。

以“Frozen Lake”游戏为例,如图 1 所示。
从S2 状态出发的多条路线的累积奖励
图 1:从 S2 状态出发的多条路线的累积奖励

假设以 S2 状态为例,从 S2 状态出发直到终止状态,可以有多条路径,每条路径都可以得到一个累积奖励,将所有累积奖励的平均值作为当前状态 S2 的状态价值,即 V(S2)=((-0.5)+(-0.5)+2+(-0.3)+2)/5=0.54。

仔细观察图 1 会发现,例如第二条路径,S2 状态和 S3 状态都被访问了两次。根据计算每条路径的累积奖励的方式不同,蒙特卡罗方法可以分为两种:First-Visit Monte Carlo 和 Every-Visit Monte Carlo。

在 First-Visit Monte Carlo 方法中,不管一个状态被访问了多少次,在计算累积奖励的时候只考虑第一次的访问。而在 Every-Visit Monto Carlo 方法中,如果一个状态被多次访问,则在计算累积奖励的时候,每一次的访问都会被考虑在内。 

目前我们只考虑了状态的价值,同样的方法可以得到状态-动作价值(Q 值):在状态 S 下采取动作 a,之后遵循当前策略 π 获得的累计期望奖励就是 Qπ(s, a) 的价值。

在得到 Q 值函数后,策略改进的方法就和前面策略迭代方法中的策略改进方法一样,即利用当前的 Q 值函数更新策略(策略就是采取具有最大 Q 值的那个动作),如果更新后的策略与之前的策略一致,则说明已经收敛,策略求解结束,否则继续执行策略估计。蒙特卡罗算法如下所示:

Initialization:
    Initial a polic π
    For s in S:
    For a in A:
        Initial Q(s, a) and Return(s, a)
        c (s, a)=0
For i in range(k):
    Generate an episode using π
    For each state s appearing in the episode:
        G←the return that follows the first occurrence of s
        Q(st,at) = (c(st, at) *Q (st,at) +G)/(c(st, at) +1)
        c(st, at)++
    end for
    update policy π(s) =argmaxQ(s, a)
end for

2.环境探索

在策略估计的时候还存在一个问题,我们想通过计算策略 π 下,从状态 S 出发的多个路径的平均累积奖励,然而,一旦确定了这个策略 π,那么每次采取的动作必然有 at=π(st),能够采取的动作也就确定了,所以不管走多少个回合,路径都是一样的,如此一来就没法进行策略估计了。此时需要环境探索,常用的方式有 ε 贪心(ε- Greedy)搜索。

ε 贪心搜索方法具体过程是:首先初始一个概率 ε,在进行策略估计的时候,以 ε 的概率随机选择一个动作,以 1-ε 的概率去根据当前的策略选择动作。考虑到刚开始进行策略估计的时候,应该更注重对环境的探索,而随着策略慢慢地改进,则应该更注重策略的利用。所以,初始的 ε 值较大,随着策略的不断改进,慢慢减小 ε 的值。

3.确定性的和非确定性的环境状态

“Frozen Lake”游戏有“无风”和“有风”两种游戏模式。“无风”模式下,游戏环境是确定的,即智能体执行一个动作(例如右移或下移)后,到达的下一个状态是确定的,并且得到的奖励也是确定的,而在“有风”模式下,环境状态则不确定了。

蒙特卡罗算法考虑的是非确定性的环境状态,所以采用取平均值的方式,希望能够近似替代真实的状态价值。如果是确定性的环境状态的话,就可以省去取平均值的操作,直接赋值为 Q(st, at) =G。

4.在策略和离策略

在策略(On-policy)和离策略(Off-policy)是强化学习问题中常见的两个概念。在智能体进行策略估计的时候,需要使用一些办法来进行环境的探索,如 ε 贪心搜索。在这种情况下,我们学到的策略π其实是带探索的策略;而如果在进行策略改进的时候,也使用该策略的话,则会导致我们最终得到的策略也是带探索的策略。策略估计和策略改进都用的是这种带探索的策略,这种情况称为在策略。

然而我们更希望最终智能体学到的策略是不带探索的,尽管在策略评估的时候避免不了使用带有探索的策略,但是在策略改进的时候,我们可以有一些方法抵消掉探索对策略的影响。只在策略估计的时候使用带探索的策略,而在策略改进的时候只考虑不带探索的策略,这种情况称为离策略。在蒙特卡罗方法中,我们可以使用重要性采样(Importance Sampling)技术实现离策略的算法。