Basics of Reinforcement Learning (part 1)
  2025-04-09 2025-04-09 12:36      3.2k Words

定义及符号

  • 马尔可夫性质（Markov property）：一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态。马尔可夫性质也可以描述为给定当前状态时，将来的状态与过去状态是条件独立的。以离散过程为例，随机变量 构成一个随机过程，这些随机变量的所有可能取值的集合被称为状态空间（state space），则

  • 马尔可夫链（Markov chain）：离散时间的马尔可夫过程。是最简单的的马尔可夫过程，其状态也是有限的。

  • 范围（horizon）：一个回合的长度，即每个回合最大的时间步。

  • 策略：

    • 确定性策略：
    • 随机性策略：

  • 运动轨迹 (trajectory, episodes, rollouts)：agent 和 environment 做一系列的交互后得到 state, action, reward 序列。

    • agent 和 environment 交互 T 次：
      • 是初始时智能体所处的状态，它只与环境有关。
    • 当 agent 在某个 下采取 时，转移到某个状态 也分确定性和随机性；
      • 确定性：
      • 随机性：

马尔可夫奖励过程

  • 状态转移矩阵（state transition matrix）：, .
  • 马尔可夫奖励过程（Markov reward process, MRP）：是马尔可夫链加上奖励函数。
  • 奖励（reward）函数：
    • 在某一次交互中，实际得到的奖励，可能是随机的；
    • 奖励函数 表示在状态 下采取动作 转移到状态 后所获得的期望奖励；即 是奖励的期望值函数，。
    • 实际奖励 一般被视为条件概率分布下的随机变量；，一般简写为 ，这是简化符号，省略了随机性，即会默认 R 是一个 deterministic 函数；
    • 奖励与策略无关。
  • 回报（return）：奖励的逐步叠加。
  • 状态价值函数（state-value function）：定义了状态的价值，是回报的期望。

  • 贝尔曼方程（Bellman equation）：.

贝尔曼方程的推导，在上述状态价值函数的说明中已经体现，重点在于第 4 行到第 5 行的推导和变换。此处需要使用全期望公式。

马尔可夫决策过程

相对于马尔可夫奖励过程，马尔可夫决策过程多了决策（决策是指动作），其他的定义与马尔可夫奖励过程的是类似的。

  • 状态转移矩阵变为：.
  • 策略：根据状态决定采取怎样的动作。.

假如已知马尔可夫决策过程和策略 ，马尔可夫决策过程与马尔可夫奖励过程关系如下：

下图为两者的对比备份图（backup）： 每一个空心圆圈代表一个状态，每一个实心圆圈代表一个状态-动作对。

马尔科夫决策过程相比马尔可夫奖励过程，多了一层决策。值得注意的是：当智能体当前状态以及智能体当前采取的动作决定过后，智能体进入未来的状态其实也是一个概率分布。

马尔可夫决策过程的价值函数表达为：.

动作价值函数（action-value function），即在某一个状态采取某一个动作，它有可能得到的回报的一个期望。

基于策略分布，对动作价值函数改写：
式

对动作价值函数进行贝尔曼方程推导：

式

根据式-1和式-2，或者根据备份图，可以得到贝尔曼期望方程：

核心概念

  • 策略评估
    已知：（1）马尔可夫决策过程 ；（2）采取的策略 。计算价值函数 的过程。

  • 预测
    预测是指给定一个马尔可夫决策过程（）以及一个策略 ，计算它的价值函数，也就是计算每个状态的价值。

  • 控制
    控制（搜索最佳策略）的输入是马尔可夫决策过程 ；输出是最佳价值函数（optimal value function） 和最佳策略（optimal policy） 。
    控制就是我们去寻找一个最佳的策略，然后同时输出它的最佳价值函数以及最佳策略。

示例说明

示例-1

绿色圆圈为状态，黄色圆圈为动作。

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
S = ["s1", "s2", "s3", "s4", "s5"]  # 状态集合
A = ["保持s1", "前往s1", "前往s2", "前往s3", "前往s4", "前往s5", "概率前往"]  # 动作集合
# 状态转移函数
P = {
    P(s1 | s1, 保持s1): 1.0,
    P(s2 | s1, 前往s2): 1.0,
    P(s1 | s2, 前往s1): 1.0,
    P(s3 | s2, 前往s3): 1.0,
    P(s4 | s3, 前往s4): 1.0,
    P(s5 | s3, 前往s5): 1.0,
    P(s5 | s4, 前往s5): 1.0,
    P(s2 | s4, 概率前往): 0.2,
    P(s3 | s4, 概率前往): 0.4,
    P(s4 | s4, 概率前往): 0.4,
}
# 奖励函数
R = {
    R(s1, 保持s1): -1,
    R(s1, 前往s2): 0,
    R(s2, 前往s1): -1,
    R(s2, 前往s3): -2,
    R(s3, 前往s4): -2,
    R(s3, 前往s5): 0,
    R(s4, 前往s5): 10,
    R(s4, 概率前往): 1,
}
gamma = 0.5  # 折扣因子
MDP = (S, A, P, R, gamma)

# 策略1,随机策略
Pi_1 = {
    pi(保持s1 | s1): 0.5,
    pi(前往s2 | s1): 0.5,
    pi(前往s1 | s2): 0.5,
    pi(前往s3 | s2): 0.5,
    pi(前往s4 | s3): 0.5,
    pi(前往s5 | s3): 0.5,
    pi(前往s5 | s4): 0.5,
    pi(概率前往 | s4): 0.5,
}
# 策略2
Pi_2 = {
    "s1-保持s1": 0.6,
    "s1-前往s2": 0.4,
    "s2-前往s1": 0.3,
    "s2-前往s3": 0.7,
    "s3-前往s4": 0.5,
    "s3-前往s5": 0.5,
    "s4-前往s5": 0.1,
    "s4-概率前往": 0.9,
}

假设现在采用策略 Pi_1，将 MDP 转换成 MRP，如下：

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
# 转化后的 MRP 的状态转移矩阵
# 以 s4 为例：
p(s5|s4) = pi(前往s5 | s4)*P(s5 | s4, 前往s5) = 0.5
p(s4|s4) = pi(概率前往 | s4)*P(s4 | s4, 概率前往) = 0.5*0.4 = 0.2
p(s3|s4) = pi(概率前往 | s4)*P(s3 | s4, 概率前往) = 0.5*0.4 = 0.2
p(s2|s4) = pi(概率前往 | s4)*P(s2 | s4, 概率前往) = 0.5*0.2 = 0.1
p(s1|s4) = 0: s4 没法一步转移到 s1

如此便可得出：
P_from_mdp_to_mrp = [
            s1   s2   s3   s4   s5
P(.|s1)    [0.5, 0.5, 0.0, 0.0, 0.0],
p(.|s2)    [0.5, 0.0, 0.5, 0.0, 0.0],
p(.|s3)    [0.0, 0.0, 0.0, 0.5, 0.5],
p(.|s4)    [0.0, 0.1, 0.2, 0.2, 0.5],
p(.|s5)    [0.0, 0.0, 0.0, 0.0, 1.0],
]

# 马尔可夫决策过程 -> 马尔可夫奖励过程
R_from_mdp_to_mrp = {
    R(s1) = -0.5 = 0.5*-1 + 0.5*0 = pi(保持s1 | s1)*R(s1, 保持s1) + pi(前往s2 | s1)*R(s1, 前往s2)
    R(s2) = -1.5 = 0.5*-1 + 0.5*-2 = pi(前往s1 | s2)*R(s2, 前往s1) + pi(前往s3 | s2)*R(s2, 前往s3)
    R(s3) = -1.0 = 0.5*-2 + 0.5*0 = pi(前往s4 | s3)*R(s3, 前往s4) + pi(前往s5 | s3)*R(s3, 前往s5)
    R(s4) = 5.5 = 0.5*10 + 0.5*1 = pi(前往s5 | s4)*R(s4, 前往s5) + pi(概率前往 | s4)*R(s4, 概率前往)
    R(s5) = 0
}

# MDP 中每个状态价值分别为：
 [[-1.22555411]
 [-1.67666232]
 [ 0.51890482]
 [ 6.0756193 ]
 [ 0.        ]]

蒙特卡洛方法（Monte-Carlo methods）

对于一个马尔可夫决策过程采用 MC 估计，已知策略为 ，

步骤如下：

  1. 采用策略 采样若干条序列，第 i 条序列：；
  2. 对每条序列的每个时间步 t 的状态 s 进行操作：

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 对所有采样序列计算所有状态的价值
def MC(episodes, V, N, gamma):
    for episode in episodes:
        G = 0
        for i in range(len(episode) - 1, -1, -1):  # 一个序列从后往前计算
            (s, a, r, s_next) = episode[i]
            G = r + gamma * G
            N[s] = N[s] + 1
            V[s] = V[s] + (G - V[s]) / N[s]

timestep_max = 20
# 采样 1000 次
# 采样结果示例：
# [('s1', '前往s2', 0, 's2'), ('s2', '前往s3', -2, 's3'), ('s3', '前往s5', 0, 's5')]
# [('s4', '概率前往', 1, 's4'), ('s4', '前往s5', 10, 's5')]
# [('s2', '前往s3', -2, 's3'), ('s3', '前往s4', -2, 's4'), ('s4', '前往s5', 10, 's5')]
episodes = sample(MDP, Pi_1, timestep_max, 1000)
gamma = 0.5
V = {"s1": 0, "s2": 0, "s3": 0, "s4": 0, "s5": 0}
N = {"s1": 0, "s2": 0, "s3": 0, "s4": 0, "s5": 0}
MC(episodes, V, N, gamma)
print("使用蒙特卡洛方法计算MDP的状态价值为\n", V)
# {'s1': -1.228923788722258, 's2': -1.6955696284402704, 's3': 0.4823809701532294, 's4': 5.967514743019431, 's5': 0}

最优策略

问题：如果只有马尔可夫决策过程，如何找到最佳策略，进而得到最优价值函数。

对于给定马尔可夫决策过程，至少存在一个策略比其他所有策略都好或者不差于。这个策略就是最优策略，最优策略可能有多个，都记为：

对应的最优状态价值函数为：

最佳策略使得每个状态的价值函数都取得最大值。所以如果我们可以得到一个最佳价值函数，就可以认为某个马尔可夫决策过程的环境可解。在这种情况下，最佳价值函数是一致的，环境中可达到的上限的值是一致的，但这里可能有多个最佳策略，多个最佳策略可以取得相同的最佳价值。

搜索最佳策略有两种常用的方法：策略迭代和价值迭代。寻找最佳策略的过程就是马尔可夫决策过程的控制过程。马尔可夫决策过程控制就是去寻找一个最佳策略使我们得到一个最大的价值函数值。

贝尔曼最优方程

贝尔曼最优方程表明：最佳策略下的一个状态的价值必须等于在这个状态下采取最好动作得到的回报的期望。当马尔可夫决策过程满足贝尔曼最优方程的时候，整个马尔可夫决策过程已经达到最佳的状态。

代入到贝尔曼方程中：

策略迭代

包含两步：

  • 策略评估，即给定当前的策略函数来估计状态价值函数。
  • 策略提升。

策略迭代算法如下：

随机初始化策略和价值函数策略评估循环对每个状态对于每个状态策略提升

价值迭代

策略迭代中，每一轮的策略提升都需要当前轮的策略评估完成，如此需要较大的计算量。可能出现这样的情况：虽然状态价值函数还没有收敛，但是不论接下来怎么更新状态价值，策略提升得到的都是同一个策略。

即基于：

价值迭代算法流程：
随机初始化对每个状态对于每个状态

时序差分

基于动态规划的算法如：策略迭代和价值迭代，都需要马尔可夫决策过程已知。但是在大部分场景，马尔可夫决策过程的状态转移分布未知，agent 需要通过与环境的交互，采样数据来学习，属于无模型的强化学习。

无模型的强化学习不需要事先知道环境的奖励函数和状态转移函数。

同时，根据策略学习分为在线和离线：

  • 在线策略学习：使用在当前策略下采样得到的样本进行学习，一旦策略被更新，当前的样本就被放弃了。
  • 离线策略学习：使用经验回放池将之前采样得到的样本收集起来再次利用。因此，离线策略学习往往能够更好地利用历史数据，并具有更小的样本复杂度（算法达到收敛结果需要在环境中采样的样本数量），这使其被更广泛地应用。

时序差分是一种用来估计一个策略的价值函数的方法，结合了蒙特卡洛和动态规划算法。

蒙特卡洛方法对价值函数的增量更新方式：

在前面介绍的蒙特卡洛方法中，需要等整个序列结束之后才能计算这一次的 ，而时序差分只需要当前步结束后即可计算。具体来说，时序差分算法用当前获得的奖励加上下一个状态的价值估计来作为在当前状态会获得的回报，即：

使用 代替 ，原因参考上面介绍的 V(s) 的定义和推导。

附录

A. 随机变量是一个 mapping，函数也是一个 mapping，两者的区别是什么？

思考…

B.1 条件概率的加法规则：

B.2 联合条件概率分解

C. 全期望公式（law of iterated expectations, LIE）

如果 是样本空间的有限或可数的划分（partition），则全期望公式可定义为：

连续情况的积分表示：

将期望展开，则：

参考