AI模型强化学习

MDP的动态规划解法-策略迭代和价值迭代

字数统计: 2.6k字   |   阅读时长: 10分
,

摘要: MDP 假设下的动态规划

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

在文章 强化学习环境框架-从一个迷宫环境看MDP的要点 中，我们总结了强化学习的基本概念，以及作为强化学习机制的 MDP，并且以 grid 为例实现了 MDP 环境的代码框架。

有了 MDP 环境之后，我们就要解决如何在其中选择最优行动的问题，也就是 MDP 环境的代码框架中的 agent.policy 方法的实现，具体来说就是价值的计算方法(价值近似)和基于价值近似的行动选择方法(策略)。

当 MDP 环境的迁移函数 transit_func 和奖励函数 reward_func 已知的时候，就可以使用动态规划法来求解。

这种基于迁移函数和奖励函数来学习行动的方法称为基于模型的学习方法。

当不知道迁移函数和奖励函数的情况下，也可以使用这种基于模型的学习方法对这两种函数进行推算，后面我们有机会再探究这种用法。此外，也可以使用无模型的学习方法，这块同样后面再探究。

本文主要解决当迁移函数和奖励函数已知的时候如何用动态规划法来学习行动。

贝尔曼方程

使用动态规划求解最有行动有两大类方法

  1. 价值迭代: 一个是基于动态规划的价值近似的学习
  2. 策略迭代: 一个是基于动态规划的策略的学习

具体来说就是价值的计算方法(价值近似)和基于价值近似的行动选择方法(策略)。

不论使用那种方法，首先都要解决一个价值的定义和计算的问题。这块可以参考 价值的定义与计算-贝尔曼方程。

在解决了价值的定义与计算之后，我们就要解决价值迭代和策略迭代的问题。

下面我们以 强化学习环境框架-从一个迷宫环境看MDP的要点 的 MDP 环境为例，具体看价值迭代和策略迭代是怎么做的。

价值迭代

基于价值的方法，思路是计算出各个状态下的价值，然后迁移到价值最大的状态。

利用动态规划计算各个状态下的价值的方法称为价值迭代。

在 价值的定义与计算-贝尔曼方程 的末尾，我们提到再用贝尔曼方程计算价值时，多次迭代可以提高值的精度，这正是价值迭代。公式如下

其中 $v_{i+1}$ 是用前一次的计算结果 $v_{i}$ 得到的。判断是否已经接近正确值，只需要判断前后两次的差值 $|V_{i+1}(s) - V_{i}(s)|$ 是否小于某个阈值。如果小于某个阈值，就不再更新。

策略迭代

基于策略的方法，思路是智能体根据策略选择行动。策略可以根据状态输出行动概率，由行动概率来计算价值(期望值)。根据策略计算价值，为了让价值最大化而更新策略。

不断重复以上过程可以提高价值近似和策略的精度，这个过程称为策略迭代。

价值迭代和策略迭代的实现

基类

首先我们定义一个基类，这个基类定义了一些基本的方法，价值迭代和策略迭代都在继承此基类的基础上进行。

注意这里的 env 是基于 强化学习环境框架-从一个迷宫环境看MDP的要点 中的 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
class Planner():
    def __init__(self, env):
        self.env = env
        self.log = []

    def initialize(self):
        self.env.reset()
        self.log = []

    def plan(self, gamma=0.9, threshold=0.0001):
        raise Exception("Planner have to implements plan method.")

    def transitions_at(self, state, action):
        transition_probs = self.env.transit_func(state, action)
        for next_state in transition_probs:
            prob = transition_probs[next_state]
            reward, _ = self.env.reward_func(next_state)
            yield prob, next_state, reward

    def dict_to_grid(self, state_reward_dict):
        grid = []
        for i in range(self.env.row_length):
            row = [0] * self.env.column_length
            grid.append(row)
        for s in state_reward_dict:
            grid[s.row][s.column] = state_reward_dict[s]

        return grid

plan 方法是价值迭代和策略迭代都要实现的方法。

transitions_at 是迁移函数 $T(s’|s,a)$ 的代码实现。输入状态和行动的组合，得到下一次迁移后的状态、迁移概率。通过奖励函数可以得到迁移后的状态对应的奖励。

价值迭代的实现

首先将 V[s] 初始化为零，然后持续更新，直至更新的幅度 delta 小于 threshold。

对各种状态下的各种行动计算对应的价值，找到最大值进行更新。

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
class ValueIterationPlanner(Planner):
    def __init__(self, env):
        super().__init__(env)

    def plan(self, gamma=0.9, threshold=0.0001):
        self.initialize()
        actions = self.env.actions
        V = {}
        for s in self.env.states:
            # 初始化各种状态的期望奖励
            V[s] = 0

        while True:
            delta = 0
            self.log.append(self.dict_to_grid(V))
            for s in V:
                if not self.env.can_action_at(s):
                    continue
                expected_rewards = []
                for a in actions:
                    r = 0
                    for prob, next_state, reward in self.transitions_at(s, a):
                        r += prob * (reward + gamma * V[next_state])
                    expected_rewards.append(r)
                max_reward = max(expected_rewards)
                delta = max(delta, abs(max_reward - V[s]))
                V[s] = max_reward

            if delta < threshold:
                break

        V_grid = self.dict_to_grid(V)
        return V_grid

策略迭代的实现

我们重点关注与价值迭代不一样的地方。

  • initialize 对 policy(策略)进行初始化。
  • policy 是一个两层的嵌套字典，保存不同状态下的各个行动的行动概率，policy[s][a] 表示状态为 s 时，采取行动 a 的概率。
  • estimate_by_policy 实现通过策略计算价值，计算过程与 ValueIterationPlanner 的 plan 中大致一样。不一样的地方在于乘以 action_prob 的部分：价值迭代一定会选择价值最大时的行动，所以选择概率为 1，而策略迭代基于策略概率性地选择行动。返回 V，V[s] 为状态 s 的期望奖励。
  • estimate_by_policy 得到的结果用于策略的评价, 基于策略评价，得到价值。plan 进行上述的评价。

plan 用 estimate_by_policy 的所得结果计算各种行动的价值(奖励)，也就是公式 r += prob * (reward + gamma * V[next_state])，价值最高的行动为 best_action，具体为 best_action = take_max_action(action_rewards)。

如果基于当前策略计算得到的 policy_action 和 best_action 不一样，就选择 best_action 来更新策略，如果不执行更新，说明策略已经达到最优，更新停止。

当策略更新时，价值的值也会被更新。因此从整体看，价值的计算(estimate_by_policy) 和策略的更新(policy[s][a] 更新为新值)会不断反复。这种互相更新是策略迭代的核心，由此，价值近似(V, 字典)和策略(policy, 二维嵌套字典) 二者被学习。

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
class PolicyIterationPlanner(Planner):

    def __init__(self, env):
        super().__init__(env)
        self.policy = {}

    def initialize(self):
        super().initialize()
        self.policy = {}
        actions = self.env.actions
        states = self.env.states
        for s in states:
            self.policy[s] = {}
            for a in actions:
                # 初始化策略
                # 一开始时各种行动的概率都是一样的
                self.policy[s][a] = 1 / len(actions)

    def estimate_by_policy(self, gamma, threshold):
        V = {}
        for s in self.env.states:
            # 初始化各种状态的期望奖励
            V[s] = 0

        while True:
            delta = 0
            for s in V:
                expected_rewards = []
                for a in self.policy[s]:
                    action_prob = self.policy[s][a]
                    r = 0
                    for prob, next_state, reward in self.transitions_at(s, a):
                        r += action_prob * prob * \
                             (reward + gamma * V[next_state])
                    expected_rewards.append(r)
                value = sum(expected_rewards)
                delta = max(delta, abs(value - V[s]))
                V[s] = value
            if delta < threshold:
                break

        return V

    def plan(self, gamma=0.9, threshold=0.0001):
        self.initialize()
        states = self.env.states
        actions = self.env.actions

        def take_max_action(action_value_dict):
            return max(action_value_dict, key=action_value_dict.get)

        while True:
            update_stable = True
            # 在当前的策略下估计期望奖励
            V = self.estimate_by_policy(gamma, threshold)
            self.log.append(self.dict_to_grid(V))

            for s in states:
                # 在当前的策略下得到行动
                policy_action = take_max_action(self.policy[s])

                # 与其他行动比较
                action_rewards = {}
                for a in actions:
                    r = 0
                    for prob, next_state, reward in self.transitions_at(s, a):
                        r += prob * (reward + gamma * V[next_state])
                    action_rewards[a] = r
                best_action = take_max_action(action_rewards)
                if policy_action != best_action:
                    update_stable = False

                # 更新策略（设置 best_action prob=1, otherwise=0 (贪婪)）
                for a in self.policy[s]:
                    prob = 1 if a == best_action else 0
                    self.policy[s][a] = prob

            if update_stable:
                # 如果策略没有更新，则停止迭代
                break

        # 将字典转换为二维数组
        V_grid = self.dict_to_grid(V)
        return V_grid

总结

本文我们解决了 强化学习环境框架-从一个迷宫环境看MDP的要点 中价值定义中的连个问题，即

  1. 需要知道将来的立即奖励的值
  2. 这个值必须能够通过计算得到

第 1 个问题通过递归的方式解决，第 2 个问题通过引入概率(期望值)的方式解决。解决这两个问题时用到了贝尔曼方程。

注意，在动态规划法的实现中，我们完全没有用到智能体的信息。智能体不用移动，只需要依靠环境信息即可找到最优的策略。要达成这种不移动智能体的模拟，需要迁移函数和奖励函数已知。

基于模型的方法和无模型的方法

无需智能体实际移动，通过迁移函数和奖励函数来学习行动策略的方法为基于模型的方法。如果实际移动智能体的成本太大，或者环境中很容易产生噪声，那么基于模型的方法是好选择，但是需要对迁移函数和奖励函数进行适当建模。

无模型方法通过实际使智能体移动，根据所获得的经验来学习行动策略。无模型方法的一个优点是适用于没有迁移函数和奖励函数的环境。

一般无模型方法用的更多，因为迁移函数和奖励函数已知的情况不常见。

最近深度学习起来以后，能够建模的情况增加，因此针对基于模型的方法的研究也躲起来了。如果能够使用无模型方法，则可以实现比无模型方法更高的学习效率。

基于模型的方法和无模型方法可以同时使用。

Share