RL 学习笔记 #3 值迭代和策略迭代

本文最后更新于：2024年12月5日 下午

在上一节中，我们介绍了贝尔曼最优公式，这里将介绍求解 BOE 的首个 model-based 的算法：值迭代（Value Iteration）和策略迭代（Policy Iteration）。此外，我们还将讨论它们的变种之一：截断策略迭代（Truncated Policy Iteration）。

值迭代 | Value Iteration

上一节中，我们将贝尔曼最优公式整理为递归形式： \[ v_*(s) = \max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_*(s') \right] \] 值迭代（Value Iteration）直接利用递归性，通过不断迭代逼近最优状态值函数 \(v_*(s)\)。整个算法可以概括为： \[ v^{(k+1)}=f\left(v^{(k)}\right)=\max _\pi\left(r_\pi+\gamma P_\pi v^{(k)}\right), \quad k=1,2,3 \ldots \] 因此这个算法理论上需要包含两个主要步骤：

  • 策略更新（PU）：\(\pi^{(k+1)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v^{(k)}\right)\)
  • 状态更新（VU）：\(v^{(k+1)}=r_{\pi^{(k+1)}}+\gamma P_{\pi^{(k+1)}} v^{(k)}\)

而策略 \(\pi\) 更新的时候由于使用了贪心选择，这两个步骤可以合并简化，直接使用最优的动作价值去更新状态价值： \[ v^{(k+1)}(s) = \max_a q^{(k+1)}(s,a) \]

值得一提的是，贪心更新策略 \(\pi\) 也带来了一个有趣的现象：越靠近目标区域的状态越先变好。直观上就是因为 \(\pi\) 依赖于其他状态，而当其他状态都不好的时候无从更新，只有接近目标区域的状态有明确的优化方向。

具体步骤

  1. 初始化值函数：设定初始值 \(v^{(0)}(s)\)，通常初始化为全零或任意常数。

  2. 迭代更新值函数： 对于每个状态 \(s\)，根据贝尔曼最优公式更新 \(v(s)\)： \[ v^{(k+1)}(s) = \max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v^{(k)}(s') \right] \]

  3. 判断收敛： 检查值函数更新是否足够小（例如 \(\lVert v^{(k+1)} - v^{(k)} \rVert_\infty < \epsilon\)），若收敛则停止迭代并输出 \(v^{(k+1)}\)。

  4. 推导策略： 一旦得到收敛的值函数 \(v_*(s)\)，通过以下方式获得对应的最优策略 \(\pi^*\)： \[ \pi^*(s) = \arg\max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_*(s') \right] \]

伪代码实现

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
def value_iteration(states, actions, transition_probs, rewards, gamma, epsilon):
    """
    states: list of all states
    actions: list of all actions
    transition_probs: function p(s', r | s, a)
    rewards: function r(s, a, s')
    gamma: discount factor
    epsilon: convergence threshold
    """
    v = {s: 0 for s in states}  # Initialize value function
    while True:
        delta = 0
        new_v = v.copy()
        for s in states:
            new_v[s] = max(
                sum(p * (r + gamma * v[s_next]) for p, r, s_next in transition_probs(s, a)) \
                for a in actions[s]	# Calculate q-table
            ) 	# Update v = max (q)
            delta = max(delta, abs(new_v[s] - v[s]))
        v = new_v
        if delta < epsilon:  # Check convergence
            break
    # Derive the optimal policy
    policy = {s: max(actions, key=lambda a: sum(p * (r + gamma * v[s_next]) \
                                                for p, r, s_next in transition_probs(s, a))) \
              for s in states}
    return v, policy

策略迭代 | Policy Iteration

策略迭代是另一种求解 BOE 的方法，核心思想是交替优化策略和状态值函数，直到收敛到最优策略 \(\pi^*\)。

与值迭代不同的是，策略迭代先初始化一个随机策略，再交替进行以下两个主要步骤：

  • 策略评估（PE）：\(v_{\pi^{(k)}}=r_{\pi^{(k)}}+\gamma P_{\pi^{(k)}} v_{\pi^{(k)}}\)
  • 策略改进（PI）：\(\pi^{(k+1)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v_{\pi^{(k)}}\right)\)

这里有四个问题需要回答：

  • 在 PE 步骤如何求解状态值？
    • 在上一节有介绍，已知策略时可以通过矩阵形式直接求解精确解，也可以利用 Bootstrap 迭代法。
    • 注意：如果采用 Bootstrap 迭代法，实际上我们是在整个大的策略迭代中又嵌套了一个小的迭代！
  • 在 PI 步骤如何确保新策略好于旧策略？
    • 可以证明：对于任何 \(k\)，有 \(v_{\pi^{(k+1)}} \ge v_{\pi^{(k)}}\)。证明过程略。
  • 这个算法为什么能到达最优策略？
    • 可以证明收敛性：\(\{v_{\pi^{(k)}}\}^{\infty}_k \to v^*\)。证明过程略。
  • 策略迭代和值迭代有什么关系？
    • 策略迭代的收敛性证明是基于值迭代的收敛性。
    • 这两种算法是截断策略迭代（Truncated Policy Iteration）的两个极端表现。

具体步骤

  1. 初始化策略： 随机初始化一个初始策略 \(\pi^{(0)}\)。

  2. 策略评估： 在当前策略 \(\pi^{(k)}\) 下，通过求解以下线性方程组来获得状态值函数 \(v_{\pi^{(k)}}(s)\)： \[ v_{\pi^{(k)}}(s) = \sum_a \pi^{(k)}(a \mid s) \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_{\pi^{(k)}}(s') \right] \]

    • 当状态空间较小时，可以直接解线性方程组；

    • 对于较大的问题，可以使用 Bootstrap 迭代逼近的方法。

  3. 策略改进： 基于更新后的值函数 \(v_{\pi^{(k)}}\)，贪心更新策略： \[ \pi^{(k+1)}(s) = \arg\max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v_{\pi^{(k)}}(s') \right] \]

  4. 检查收敛： 如果策略不再变化，即 \(\pi^{(k+1)} = \pi^{(k)}\)，则算法结束，\(\pi^{(k)}\) 即为最优策略；否则返回步骤 2。

伪代码实现

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
def policy_iteration(states, actions, transition_probs, rewards, gamma, epsilon):
    v = {s: 0 for s in states}  # Initialize value function
    policy = {s: actions[0] for s in states}  # Initialize policy
    
    while True:
        # Policy evaluation
        while True:
            delta = 0
            new_v = v.copy()
            for s in states:
                a = policy[s]
                new_v[s] = sum(p * (r + gamma * v[s_next]) for p, r, s_next in transition_probs(s, a))
                delta = max(delta, abs(new_v[s] - v[s]))
            v = new_v
            if delta < epsilon:  # Check convergence
                break
        
        # Policy improvement
        stable = True
        for s in states:
            best_action = max(actions, key=lambda a: sum(p * (r + gamma * v[s_next]) \
                                                         for p, r, s_next in transition_probs(s, a)))
            if best_action != policy[s]:
                policy[s] = best_action
                stable = False
        if stable:  # Check if policy is stable
            break

    return v, policy

截断策略迭代 | Truncated Policy Iteration

截断策略迭代（Truncated Policy Iteration）是值迭代和策略迭代的一般化推广，旨在权衡收敛速度与计算效率。如果将两个算法对齐：

StepsPolicy IterationValue IterationComments
(1) Policy\(\pi^{(0)}\)N/A
(2) Value\(v_{\pi^{(0)}}=r_{\pi^{(0)}}+\gamma P_{\pi^{(0)}} v_{\pi^{(0)}}\)\(\textcolor{red}{v^{(0)}:=v_{\pi^{(0)}}}\)人为赋予 VI 的相同初始值，便于比较
(3) Policy\(\pi^{(1)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v_{\pi^{(0)}}\right)\)\(\pi^{(1)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v^{(0)}\right)\)这一步的操作和结果一模一样
(4) Value\(\textcolor{blue}{v_{\pi^{(1)}}=r_{\pi^{(1)}}+\gamma P_{\pi^{(1)}} v_{\pi^{(1)}}}\)\(\textcolor{blue}{v^{(1)}=r_{\pi^{(1)}}+\gamma P_{\pi^{(1)}} v^{(0)}}\)由 \(v_{\pi^{(1)}}\ge v^{(0)}\) 得 \(v_{\pi^{(1)}}\ge v^{(1)}\)
(5) Policy\(\pi^{(2)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v_{\pi^{(1)}}\right)\)\(\pi^{(2)} = \arg\max _\pi\left(r_\pi+\gamma P_\pi v^{(1)}\right)\)接下来差距越变越大
............

可以看到，关键的分歧在于 (4) Value 步骤时，策略迭代采用的是一个内嵌迭代去多次更新了状态值，而值迭代只采用一次更新得到了新状态值。

那么，在这二者之间，是否存在一个中间结果？截断策略迭代应运而生，其主要特点是对策略评估（PE）过程进行截断。减少了内嵌迭代的计算开销，相较于策略迭代更高效。

关于截断策略迭代的收敛性证明，直观上可以用 VI 和 PI 两条曲线的夹逼来解释。具体证明过程略去。

具体步骤

  1. 初始化策略： 随机初始化一个策略 \(\pi^{(0)}\)。

  2. 截断的策略评估： 在当前策略 \(\pi^{(k)}\) 下，迭代更新值函数 \(v^{(k)}(s)\)，但仅进行有限次迭代（如 \(n\) 次），而非完全收敛。

  3. 策略改进： 基于截断后的值函数 \(v^{(k)}(s)\)，更新策略： \[ \pi^{(k+1)}(s) = \arg\max_a \left[ \sum_r p(r \mid s, a) r + \gamma \sum_{s'} p(s' \mid s, a) v^{(k)}(s') \right] \]

  4. 判断收敛： 如果策略 \(\pi^{(k+1)} = \pi^{(k)}\)，则停止；否则返回步骤 2。

伪代码实现

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
def truncated_policy_iteration(states, actions, transition_probs, rewards, gamma, epsilon, k):
    v = {s: 0 for s in states}  # Initialize value function
    policy = {s: actions[0] for s in states}  # Initialize policy

    while True:
        # Truncated policy evaluation (k iterations)
        for _ in range(k):
            new_v = v.copy()
            for s in states:
                a = policy[s]
                new_v[s] = sum(p * (r + gamma * v[s_next]) for p, r, s_next in transition_probs(s, a))
            v = new_v

        # Policy improvement
        stable = True
        for s in states:
            best_action = max(actions, key=lambda a: sum(p * (r + gamma * v[s_next]) \
                                                         for p, r, s_next in transition_probs(s, a)))
            if best_action != policy[s]:
                policy[s] = best_action
                stable = False
        if stable:  # Check if policy is stable
            break

    return v, policy

算法比较

算法优点缺点适用场景
值迭代通过单个过程即可直接逼近最优值函数，简单、直接，适用于小规模问题收敛速度较慢，尤其是当状态空间较大或 \(\gamma\) 接近 1 时，每次迭代的更新量可能变得很小状态空间较小、对精度要求较高
策略迭代收敛速度快，通常只需几轮策略更新即可收敛每轮策略评估计算量大，尤其是在状态空间很大时，可能成为瓶颈中小规模问题、对速度要求较高
截断策略迭代权衡了值迭代和策略迭代的优缺点，减少了策略评估的计算开销，相较于策略迭代更高效收敛速度可能略低于完整的策略迭代大规模问题、需要减少计算开销

以上三种算法是强化学习中的经典方法，为后续的 Model-Free 算法奠定了重要的基础。

学习笔记 > 强化学习
#RL
RL 学习笔记 #3 值迭代和策略迭代
https://hwcoder.top/RL-Note-3
作者
Wei He
发布于
2024年12月3日
许可协议