【强化学习】06 —— 基于无模型的强化学习（Control）

Model-free control
Optimise the value function of an unknown MDP

简介

继续上一讲的内容【强化学习】05 —— 基于无模型的强化学习（Prediction）

在生活中，我们会遇见许多可以被建模成MDP的问题：

对于大部分真实世界中的问题，模型可以分为两类：

• MDP模型是已知的，但是规模太大，只能通过采样进行
• MDP模型是未知的，只能通过在经验中进行采样

本章还会引入一组概念：在线策略学习和离线策略学习。通常来说，在线策略学习要求使用在当前策略下采样得到的样本进行学习，一旦策略被更新，当前的样本就被放弃了，就好像在水龙头下用自来水洗手；而离线策略学习使用经验回放池将之前采样得到的样本收集起来再次利用，就好像使用脸盆接水后洗手。因此，离线策略学习往往能够更好地利用历史数据，并具有更小的样本复杂度（算法达到收敛结果需要在环境中采样的样本数量），这使其被更广泛地应用。

在线策略学习(On-policy)

• “Learn on the job”
• 利用策略$\pi$的经验采样不断改进策略$\pi$

离线策略学习(Off-policy)

• “Look over someone’s shoulder”
• 利用另外一个策略$\mu$不断改进策略$\pi$

On-policy Monte-Carlo Control

我们在动态规划算法(【强化学习】04 ——动态规划算法)那一讲中介绍了策略迭代的过程，从一个起始的价值函数出发，follow一个策略$\pi$，经过不断的策略评估与策略提升，最后使得策略收敛到最优的策略${\pi }^{\ast }$。

基于状态价值函数$V(s)$的策略提升需要MDP模型：

$${\pi }^{\prime }(s)=\underset{a\in \mathcal{A}}{\mathrm{argmax}}{\mathcal{R}}_s^a+{\mathcal{P}}_{s{s}^{\prime }}^{a}V(s^{\prime })$$

但是对于无模型的强化学习，我们是无法得知奖励函数${\mathcal{R}}_s^a$以及状态转移函数${\mathcal{P}}_{s{s}^{\prime }}^a$，因此需要基于动作价值函数进行贪婪策略提升：$${\pi }^{\prime }(s)=\underset{s\in \mathcal{A}}{\mathrm{argmax}}Q(s,a)$$

同样地，基于动作价值函数的策略迭代过程如下图所。对于策略评估部分，可以采用Monte-Carlo策略评估，使得$Q=q_{\pi }$,之后利用贪婪策略进行提升。

不过单纯的用贪婪算法进行策略提升会存在局部最优解的问题，因为贪婪算法不能很好地权衡探索 Exploration和利用 Exploitation，因此得到的策略很有可能是次优的。下面用一个例子说明：

如下图所示，开启左边的门的期望奖励是4，而右边的是2。但是若一次开启左边的门得到的奖励是0，而右边始终可以获得奖励，采用贪婪策略很容易会使得我们去选择开启右边的门，虽然这样始终能获得奖励，但是是非最优的。

很容易想到【强化学习】02—— 探索与利用中采用$ϵ-greedy$的策略： π ( a ∣ s ) = { ϵ / m + 1 − ϵ i f   a ∗ = a r g m a x   Q ( s , a ) ϵ / m o t h e r w i s e \left.\pi(a|s)=\left\{ϵ/m+1−ϵif a∗=argmax Q(s,a)ϵ/motherwise

\right.\right. π(a∣s)={ϵ/m+1−ϵϵ/m​if a∗=argmax Q(s,a)otherwise​

• 所有$m$个动作均以非零概率进行尝试
• 以$1-ϵ$ 的概率选择贪心动作
• 以$ϵ$的概率选择任意动作

这里涉及到一个定理，去证明对于任意的$ϵ-greedy$策略$\pi$，关于$Q_{\pi }$的$ϵ-greedy$策略${\pi }^{\prime }$是策略$\pi$的提升，即$V_{{\pi }^{\prime }}(s)\ge V_{\pi }(s)$ Q π ( s , π ′ ( s ) ) = ∑ a ∈ A π ′ ( a ∣ s ) Q π ( s , a ) = ϵ / m ∑ a ∈ A Q π ( s , a ) + ( 1 − ϵ ) max ⁡ a ∈ A Q π ( s , a ) ≥ ϵ / m ∑ a ∈ A Q π ( s , a ) + ( 1 − ϵ ) ∑ a ∈ A π ( a ∣ s ) − ϵ / m 1 − ϵ Q π ( s , a ) = ∑ a ∈ A π ( a ∣ s ) Q π ( s , a ) = v π ( s ) Qπ(s,π′(s))=∑a∈Aπ′(a|s)Qπ(s,a)=ϵ/m∑a∈AQπ(s,a)+(1−ϵ)maxa∈AQπ(s,a)≥ϵ/m∑a∈AQπ(s,a)+(1−ϵ)\textcolorred∑a∈Aπ(a|s)−ϵ/m1−ϵQπ(s,a)=∑a∈Aπ(a|s)Qπ(s,a)=vπ(s)

Qπ​(s,π′(s))​=a∈A∑​π′(a∣s)Qπ​(s,a)=ϵ/ma∈A∑​Qπ​(s,a)+(1−ϵ)a∈Amax​Qπ​(s,a)≥ϵ/ma∈A∑​Qπ​(s,a)+(1−ϵ)a∈A∑​1−ϵπ(a∣s)−ϵ/m​Qπ​(s,a)=a∈A∑​π(a∣s)Qπ​(s,a)=vπ​(s)​

也可以在每经历一个Episode之后就策略评估或策略提升。

• 策略评估部分采用 Monte-Carlo策略评估，不过要注意$Q\approx Q_{\pi }$（当前的策略估计不一定能够收敛到$Q_{\pi }$，如果直接采用贪婪策略，则无法探索到其他可能会带来更高价值的动作，从而使得结果次优）
• 策略提升采用$ϵ-greedy$策略提升

GLIE

基于$ϵ-greedy$算法，我们其实只能得到近似的$Q\approx Q_{\pi }$，因为该算法没有一个终止条件，会导致其一直在探索。

因此我们必须关注以下两个方面：

• 一方面我们不想丢掉任何更好信息和状态；
• 另一方面随着我们策略的改善我们最终希望能终止于某一个最优策略，因为事实上最优策略不应该包括一些随机行为选择。

因此，我们希望得到一个这样的学习方法：

1. 在学习开始时有足够的探索；
2. 最终得到的策略没有探索，是一个确定性的策略。

于是我们将引入GLIE算法

Greedy in the Limit with Infinite Exploration (GLIE),在有限的时间内进行无限可能的探索

Definition
1. 所有已经经历的状态行为对（state-action pair）会被无限次探索 ${\lim }_{k\to \infty }{N}_k(s,a)=\infty$
2. 策略最终要趋向于贪婪策略（因为要达到最优策略）。${\lim }_{k\to \infty }{\pi }_k(a|s)=1(a=\underset{a^{\prime }\in \mathcal{A}}{\mathrm{argmax}}{Q}_k(s,a^{\prime }))$
Example：设计类似于双曲函数的策略。${ϵ}_k=1/k$,$k$为探索的Episode数目,那么该Ɛ贪婪蒙特卡洛控制就具备GLIE特性。

基于GLIE的蒙特卡洛控制流程如下：

• 对于给定策略$\pi$，采样第$k$个Episode: { S 1 , A 1 , R 2 , . . . , S T } ∼ π \{S_1,A_1,R_2,...,S_T\}\sim\pi {S1​,A1​,R2​,...,ST​}∼π
• 对于该Episode里出现的每一个状态行为对$S_t$和$A_t$,更其计数和$Q$函数：$$\begin{array}{rl}& N(S_t,A_t)\leftarrow N(S_t,A_t)+1\\ & Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\frac{1}{N(S_t,A_t)}\left(G_t-Q(S_t,A_t)\right)\end{array}$$
• 基于新的$Q$函数改善以如下方式改善策略：$$\begin{array}{rl}ϵ& \leftarrow 1/k\\ \pi & \leftarrow ϵ\text{-greedy}(Q)\end{array}$$

定理：GLIE蒙特卡洛控制能收敛至最优的状态行为价值函数。

MC vs. TD Control

• 时许差分(TD)相比于蒙特卡洛(MC)的优点
  • 基于不完整episode进行学习
  • 在线学习
  • 拥有更低的方差
• 因此可以考虑将TD用于Control之中
  • 使用TD来更新$Q(s,a)$
  • 使用$ϵ-greedy$ 策略提升算法
  • 每一个时间步长更新状态-动作价值函数

On-policy Temporal Difference Control

本章接下来将要讲解无模型的强化学习中的两大经典算法：Sarsa 和 Q-learning，它们都是基于时序差分（temporal difference，TD）的强化学习算法。

Sarsa

SARSA（State-Action-Reward-State-Action）是一种基于值函数的强化学习算法，用于解决马尔可夫决策过程（MDP）中的控制问题。SARSA算法同时考虑当前的状态和动作，以及下一步的状态和动作来决定以后的行为,是一个(状态-动作-奖励-状态-动作)$⟨S,A,R,S^{\prime },A^{\prime }⟩$五元组。

在SARSA算法中，智能体按照一定的策略（如ε-greedy策略）选取动作，并根据环境的反馈（奖励信号）更新值函数。SARSA算法的更新规则为：
$$Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma Q(s^{\prime },a^{\prime })-Q(s,a)]$$

使用SARSA的在线策略控制

每个时间步长：
• 策略评估：$Q(s,a)\leftarrow Q(s,a)+\alpha [r+\gamma Q(s^{\prime },a^{\prime })-Q(s,a)]$,$Q\approx Q_{\pi }$
• 策略改进：$\epsilon -greedy$策略改进

Sarsa伪代码：

注：在线策略时序差分控制（on-policy TD control）使用当前策略进行动作
采样。即，SARSA算法中的两个“A”都是由当前策略选择的，这也保证了数据分布的一致性。

Example1 Windy Gridworld

有一股侧风从格栅中间向上吹过。标准动作为（上，下，左，右）。但在中间区域，有一股自下而上的风，会使得原本的动作发生改变，风的强度标注在栅格下方的数字。例如，如果你是目标G右侧的一个单元格，那么向左侧的动作会将你带到目标上方的单元格。

• 每步的奖励 = -1，直到智能体抵达目标网格
• 无折扣因子

训练结果如下图所示：

可以看到，随着训练的进行，Sarsa训练一个Episode所用的时间越来越少，即，达到目标的速度越来越快。

Forward View Sarsa(λ)

类似TD(λ)，$Q^{\lambda }$组合了所有的$Q_t^{(n)}$，并且赋上了相应的权值$(1-\lambda ){\lambda }^{n-1}$,累计奖励为：$$Q_t^{\lambda }=(1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{Q}_t^{(n)}$$使用下式进行更新：
$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha \left(Q^{\lambda }-Q(S_t,A_t)\right)$$

这就是Forward View Sarsa(λ)，使用它更新Q价值需要遍历完整的Episode，我们同样可以反向理解Sarsa(λ).

Backward View Sarsa(λ)

类似于Backward View TD(λ)，引入Eligibility Trace的概念，不同的是这次的E值针对的不是一个状态，而是一个状态行为对： E 0 ( s , a ) = 0 E t ( s , a ) = γ λ E t − 1 ( s , a ) + 1 ( S t = s , A t = a ) E0(s,a)=0Et(s,a)=γλEt−1(s,a)+1(St=s,At=a)

E0​(s,a)Et​(s,a)​=0=γλEt−1​(s,a)+1(St​=s,At​=a)​
Q值更新$$\begin{array}{rl}{\delta }_t& =R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)\\ Q(s,a)& \leftarrow Q(s,a)+\alpha {\delta }_t{E}_t(s,a)\end{array}$$

Sarsa(λ) Gridworld Example
下图则用了格子世界的例子具体解释了Sarsa和Sarsa(λ)算法区别,详细解释请参考《强化学习》第五讲 不基于模型的控制

Sarsa 代码

LearningRL/Hands-on-RL/Sarsa_Cliff_Walking.py

部分结果(部分算法波动性较大)

Off-Policy Learning

什么是离线策略学习

• 使用目标策略$\pi (a|s)$进行值函数评估（$V^{\pi }(s)or{Q}^{\pi }(s,a)$）
• 用行为策略$\mu (a|s)$收集数据（行为策略可以是未知的）。 { S 1 , A 1 , R 2 , . . . , S T } ∼ μ \{S_1,A_1,R_2,...,S_T\}\sim\mu {S1​,A1​,R2​,...,ST​}∼μ

使用离线策略学习的重要性

• 平衡探索 Exploration和利用 Exploitation
• 通过观察人类或其他智能体学习策略
• 重用旧策略所产生的经验
• 遵循探索策略时学习最优策略
• 遵循一个策略时学习多个策略

重要性采样Importance Sampling

当用行为策略$\mu (a|s)$所收集的数据去学习另一个策略（估计一个不同分布的期望）时，可以用到重要性采样（Importance Sampling）。于是有以下公式：
E x ∼ p [ f ( x ) ] = ∫ x p ( x ) f ( x ) d x = ∫ x q ( x ) p ( x ) q ( x ) f ( x ) d x = E x ∼ q [ p ( x ) q ( x ) f ( x ) ] Ex∼p[f(x)]=∫xp(x)f(x)dx=∫xq(x)p(x)q(x)f(x)dx=Ex∼q[p(x)q(x)f(x)]

Ex∼p​[f(x)]​=∫x​p(x)f(x)dx=∫x​q(x)q(x)p(x)​f(x)dx=Ex∼q​[q(x)p(x)​f(x)]​$x\sim p$表示采样到的$x$服从$p$分布。将每个实例的权重重新分配为$\beta (x)=\frac{p(x)}{q(x)}$从而满足在$q$中采样得到的$x$也满足$x\sim p$.

使用重要性采样的离线策略蒙特卡洛

• 使用策略𝜇产生的累计奖励评估策略$\pi$
• 根据两个策略之间的重要性比率（importance ratio）对累计奖
  励$G_t$加权
  对每个片段乘以重要性比率，最后再连乘
  { s 1 , a 1 , r 2 , s 2 , a 2 , . . . , s T } ∼ μ G t π / μ = π ( a t ∣ s t ) μ ( a t ∣ s t ) π ( a t + 1 ∣ s t + 1 ) μ ( a t + 1 ∣ s t + 1 ) . . . π ( a T ∣ s T ) μ ( a T ∣ s T ) G t {s1,a1,r2,s2,a2,...,sT}∼μGπ/μt=π(at|st)μ(at|st)π(at+1|st+1)μ(at+1|st+1)...π(aT|sT)μ(aT|sT)Gt
  {s1​,a1​,r2​,s2​,a2​,...,sT​}∼μGtπ/μ​=μ(at​∣st​)π(at​∣st​)​μ(at+1​∣st+1​)π(at+1​∣st+1​)​...μ(aT​∣sT​)π(aT​∣sT​)​Gt​​
• 最后更新值函数以逼近修正的累计奖励值
  $$V(s_t)\leftarrow V(s_t)+\alpha \left(G_t^{\pi /\mu }-V(s_t)\right)$$
• 注意：
  • 无法在𝜋非零而𝜇为零时使用重要性采样
  • 重要性采样将显著增大方差（variance）

使用重要性采样的离线策略时序差分

• 使用策略𝜇产生的时序差分目标评估策略𝜋

• 根据重要性采样对时序差分目标𝑟 + 𝛾𝑉(𝑠′)加权

• 仅需要一步来进行重要性采样修正
  V ( S t ) ← V ( S t ) + α ( π ( A t ∣ S t ) μ ( A t ∣ S t ) ( R t + 1 + γ V ( S t + 1 ) ) − V ( S t ) ) V(St)←V(St)+α(\textcolorredπ(At|St)μ(At|St)(Rt+1+γV(St+1))−V(St))

  ​V(St​)←V(St​)+α(μ(At​∣St​)π(At​∣St​)​(Rt+1​+γV(St+1​))−V(St​))​

• 具有比蒙特卡洛重要性采样更低的方差

• 策略仅需在单步中被近似

Q-Learning

• Q-Learning无需重要性采样
• 根据行为策略选择动作$a_t\sim \mu (\cdot |s_t)$
• 根据目标策略选择后续动作$a_{t+1}^{\prime }\sim \pi (\cdot |s_t)$
• 用$a_{t+1}^{\prime }$去更新$Q(s_t,a_t)$
  $$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha (r_{t+1}+\gamma \boxed{Q(s_{t+1},a_{t+1}^{\prime })}-Q(s_t,a_t))$$
• 允许行为策略和目标策略都进行改进
• 目标策略𝜋可以是关于𝑄(𝑠, 𝑎)的贪心策略$$\pi (s_{t+1})=\arg \underset{a\prime }{\max }Q(s_{t+1},a\prime )$$
• 行为策略𝜇是关于𝑄(𝑠, 𝑎)的ε-贪心策略
• Q-学习目标函数可以简化为
  $$\begin{array}{rl}{r}_{t+1}+\gamma Q(s_{t+1},a_{t+1}^{\prime })& =r_{t+1}+\gamma Q(s_{t+1},\arg \underset{a_{t+1}^{\prime }}{\max }Q(s_{t+1},a_{t+1}^{\prime }))\\ & =r_{t+1}+\gamma \underset{a_{t+1}^{\prime }}{\max }Q(s_{t+1},a_{t+1}^{\prime })\end{array}$$
• Q-学习更新方式
  $$Q(s_t,a_t)\leftarrow Q(s_t,a_t)+\alpha (r_{t+1}+\gamma \underset{a_{t+1}^{\prime }}{\max }Q(s_{t+1},a_{t+1}^{\prime })-Q(s_t,a_t))$$
• 定理：Q-学习控制收敛到最优状态-动作值函数$$Q(s,a)\to Q^{\ast }(s,a)$$
• 
• 收敛性证明

Q-learnig versus Sarsa

• Sarsa
  • 对于 Sarsa，它的更新公式必须使用来自当前策略采样得到的五元组$⟨S,A,R,S^{\prime },A^{\prime }⟩$，因此它是在线策略学习方法；
• Q-learnig
  • 使用四元组$⟨S,A,R,S^{\prime }⟩$来更新$Q(s,a)$.该四元组并不需要一定是当前策略采样得到的数据，也可以来自行为策略，因此它是离线策略算法。

Q-learning的伪代码

class Qlearning():
    def __init__(self, env, gamma, alpha, epsilon, numOfEpisodes, numOfActions=4):
        self.env = env
        self.gamma = gamma
        self.alpha = alpha
        self.epsilon = epsilon
        self.numOfEpisodes = numOfEpisodes
        self.numOfActions = numOfActions
        # 初始化Q(s, a)表
        self.Q_table = np.zeros([self.env.nrows * self.env.ncols, numOfActions])

    # Choose A from S using policy derived from Q (e.g., epsilon-greedy)
    def ChooseAction(self, state):
        if np.random.random() < self.epsilon:
            action = np.random.randint(self.numOfActions)
        else:
            action = np.argmax(self.Q_table[state])
        return action

    def QlearningRun(self):
        # 记录每一条序列的回报
        returnList = []
        # 显示10个进度条
        for i in range(10):
            # tqdm的进度条功能
            with tqdm(total=int(self.numOfEpisodes / 10), desc='Iteration %d' % i) as pbar:
                # 每个进度条的序列数
                for episode in range(int(self.numOfEpisodes / 10)):
                    # initialize state
                    state = self.env.Reset()
                    done = False
                    episodeReward = 0
                    # Loop for each step of episode:
                    while not done:
                        # Choose A from S using policy derived from Q (e.g., epsilon-greedy)
                        action = self.ChooseAction(state)
                        # Take action A, observe R, S'
                        stateprime, reward, done = self.env.Step(action)
                        episodeReward += reward
                        # Update
                        TD_error = reward + self.gamma * self.Q_table[stateprime].max() \
                                 - self.Q_table[state, action]
                        self.Q_table[state,action] += self.alpha * TD_error
                        state = stateprime
                    returnList.append(episodeReward)
                    if (episode + 1) % 10 == 0:  # 每10条序列打印一下这10条序列的平均回报
                        pbar.set_postfix({
                            'episode':
                                '%d' % (self.numOfEpisodes / 10 * i + episode + 1),
                            'return':
                                '%.3f' % np.mean(returnList[-10:])
                        })
                    pbar.update(1)
        return returnList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

Q-learning算法最终收敛得到的策略为：
^ooo ovoo ovoo ^ooo ^ooo ovoo ooo> ^ooo ^ooo ooo> ooo> ovoo 
ooo> ooo> ooo> ooo> ooo> ooo> ^ooo ooo> ooo> ooo> ooo> ovoo 
ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ooo> ovoo 
^ooo **** **** **** **** **** **** **** **** **** **** EEEE 
1
2
3
4
5

seed = 0时的对比

十次训练平均：

可以看到在当前的参数设置下，Q-learning的奖励回报略低于Sarsa。

参考

[1] 伯禹AI
[2] https://www.deepmind.com/learning-resources/introduction-to-reinforcement-learning-with-david-silver
[3] 动手学强化学习
[4] Reinforcement Learning