AI模型强化学习

马尔科夫决策过程

字数统计: 1.8k字   |   阅读时长: 7分

摘要: 马尔科夫决策过程入门

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 OpenAI-Gym入门 中，我们以 CartPole-v1 环境为例学习了 OpenAI Gym 的基本用法。在文章 OpenAI-Gym神经网络策略及其训练 中，我们依然是以 CartPole-v1 为例，学习了策略梯度算法及其实现，并用 Keras 实际训练了一个神经网络策略。

策略梯度(PG)算法直接尝试优化策略来增加奖励，此外还有另一个流行的算法：智能体学习估计每个状态或每个状态中每个动作的预期回报，然后把这些知识用于决定如何行动。为了理解这些算法，我们必须首先学习马尔可夫决策过程。

无记忆随机过程

20世纪初，马尔可夫研究了无记忆的随机过程，称为马尔可夫链。此过程具有固定数量的状态，且在每个步骤中它都从一种状态随机演变到另一种状态。从状态 s 转移到状态 t 的概率是固定的，且仅取决于 (s, t)，而与历史状态无关。

马尔科夫决策过程

马尔科夫决策过程最早是在 1950 年由贝尔曼描述的。类似马尔科夫链，但是有个变化: 在每个步骤中，智能体可以选择几种可能的动作之一，而转移概率取决于所选的动作。一些状态转换会返回一定的奖励(正负都有可能)，智能体的目标是找到一种能够随着时间的推移最大化奖励的策略。例如下图是一个 MDP 的例子，MDP 有三个状态(圆环)，每个步骤有一些可能的离散动作(菱形)，一个离散动作可以以一定概率去到某个状态，并且有可能有奖励。

MDP例子

Bellman 最优方程式

贝尔曼找到一种方法来估计任何状态 s 的最佳状态值，记为 $V^{*}(s)$，此值是智能体在达到状态 s 时平均预期的所有折扣未来奖励的总和。

贝尔曼表明，如果智能体有最佳动作，则适用Bellman最优方程式。这个递归方程式表示，如果智能体采取最佳行动，则当前状态的最佳值等于采取一个最佳行动后平均获得的回报，加上该行动可能导致的所有可能的下一状态的预期最佳值。

其中

由此方程式，我们可以精确估算每个可能状态的最佳状态值。具体算法是首先将所有状态估算值初始化为0，然后用值迭代算法更新状态估算值。

值迭代算法如下，此算法是动态规划的一个例子

Q值

知道最佳状态值对于评估策略很有用，但并不能提供智能体的最佳策略。贝尔曼还发现了一种相似的算法来估算最佳状态动作值(Q值)

状态动作对 （s, a) 的最佳 Q 值，记为 $Q^{*}(s, a)$，是智能体在到达状态 s 选择行动 a 后平均期望获得的折扣未来回报之和，但在看到该动作的结果之前，假设它在该动作之后表现最佳。具体算法是首先将所有Q值初始化为0，然后用Q值迭代算法更新状态估算值。

Q值迭代算法那如下

有了最佳 Q 值，就可以定义最佳策略: 当智能体处于状态 s 时，它应该为该状态选择具有最高 Q 值的动作。

Q 值迭代算法那求 MDP 最佳策略

MDP例子

下面我们将 Q 值迭代算法用用到图示的 MDP，首先定义该 MDP

1
2
3
4
5
6
7
8
9
10
11
12
# 定义 MDP
transition_probabilities = [ # shape 为 [s, a, s']
        [[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]],
        [[0.0, 1.0, 0.0], None, [0.0, 0.0, 1.0]],
        [None, [0.8, 0.1, 0.1], None]
        ]
rewards = [ # shape 为 [s, a, s']
        [[+10, 0, 0], [0, 0, 0], [0, 0, 0]],
        [[0, 0, 0], [0, 0, 0], [0, 0, -50]],
        [[0, 0, 0], [+40, 0, 0], [0, 0, 0]]
        ]
possible_actions = [[0, 1, 2], [0, 2], [1]]

接下来将所有 Q 值初始化为 0，对于不可能的动作，将 Q 值初始化为 -inf

1
2
3
Q_values = np.full((3, 3), -np.inf) # -np.inf 为不可能的行动的 Q
for state, actions in enumerate(possible_actions):
    Q_values[state, actions] = 0.0

接下来是 Q 值迭代算法，对每个状态和每个可能的动作，重复用Q值迭代的公式更新所有 Q 值

1
2
3
4
5
6
7
8
9
10
11
12
13
gamma = 0.90 # 折扣因子
for iteration in range(50):
    Q_prev = Q_values.copy()
    for s in range(3):
        for a in possible_actions[s]:
            Q_values[s, a] = np.sum([
                transition_probabilities[s][a][sp]
                        * (rewards[s][a][sp] + gamma * np.max(Q_prev[sp]))
                        for sp in range(3)
                ])

print("所有 Q 值:\n{}".format(Q_values))
print("对于每个状态，具有最高 Q 值的动作:\n{}".format(np.argmax(Q_values, axis=1)))

所有的 Q 值，以及对于每个状态具有最高 Q 值的动作如下

1
2
3
4
5
6
所有 Q 值:
[[18.91891892 17.02702702 13.62162162]
 [ 0.                -inf -4.87971488]
 [       -inf 50.13365013        -inf]]
对于每个状态，具有最高 Q 值的动作:
[0 0 1]

以上结果提供了 0.9 折扣因子下该 MDP 的最佳策略：在状态 s0，选动作 a0，在状态 s1，选动作 a0，在状态 s2，选动作 a1

Q 值迭代算法那求 MDP 最佳策略的完整代码

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
import numpy as np

# 定义 MDP
transition_probabilities = [ # shape 为 [s, a, s']
        [[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]],
        [[0.0, 1.0, 0.0], None, [0.0, 0.0, 1.0]],
        [None, [0.8, 0.1, 0.1], None]
        ]
rewards = [ # shape 为 [s, a, s']
        [[+10, 0, 0], [0, 0, 0], [0, 0, 0]],
        [[0, 0, 0], [0, 0, 0], [0, 0, -50]],
        [[0, 0, 0], [+40, 0, 0], [0, 0, 0]]
        ]
possible_actions = [[0, 1, 2], [0, 2], [1]]

Q_values = np.full((3, 3), -np.inf) # -np.inf 为不可能的行动的 Q
for state, actions in enumerate(possible_actions):
    Q_values[state, actions] = 0.0

gamma = 0.90 # 折扣因子
for iteration in range(50):
    Q_prev = Q_values.copy()
    for s in range(3):
        for a in possible_actions[s]:
            Q_values[s, a] = np.sum([
                transition_probabilities[s][a][sp]
                        * (rewards[s][a][sp] + gamma * np.max(Q_prev[sp]))
                        for sp in range(3)
                ])

print("所有 Q 值:\n{}".format(Q_values))
print("对于每个状态，具有最高 Q 值的动作:\n{}".format(np.argmax(Q_values, axis=1)))
Share