策略迭代算法

动态规划与强化学习算法解析：策略迭代与价值迭代

分类：自动推断

标签：动态规划，强化学习，策略迭代，价值迭代

日期：2025年4月8日

核心观点总结

动态规划是一种将复杂问题分解为更小子问题的方法，适用于已知环境动态的 model-based 方法。其在强化学习中的应用主要体现在策略迭代和价值迭代两种算法中。策略迭代通过交替进行策略评估和策略提升来获得最优策略，而价值迭代则直接更新状态价值函数。

重点段落

动态规划的基本思想：通过分解问题并保存子问题的解来避免重复计算。
💡 启发点：此方法特别适用于已知环境动态的情况。
策略迭代的过程：通过策略评估和策略提升交替进行，逐步逼近最优策略。
✅ 操作步骤：
- 策略评估：计算当前策略的状态价值函数。
- 策略提升：基于状态价值函数改进策略。
价值函数的计算公式：
$V^{π} (s) = \sum_{a \in A} π (a | s) (r (s, a) + γ \sum_{s^{'} \in S} p (s^{'} | s, a) V^{π} (s^{'}))$
策略评估和提升的终止条件：当当前迭代与上一轮的状态价值函数差小于阈值 $$\epsilon$$ 时，可以停止策略评估。
价值迭代的方法：直接通过更新状态价值函数来求解最优策略。

class PolicyIteration:
    """策略迭代算法"""
    
    def __init__(self, env, theta, gamma):
        self.env = env
        self.v = [0] * (self.env.ncol * self.env.nrow)  # 状态价值函数初始化
        self.pi = [
            [0.25, 0.25, 0.25, 0.25]  # 均匀随机策略（四个动作）
            for _ in range(self.env.ncol * self.env.nrow)
        ]
        self.theta = theta  # 策略评估收敛阈值
        self.gamma = gamma  # 折扣因子

    def policy_evaluation(self):
        """策略评估（预测）"""
        cnt = 1
        while True:
            max_diff = 0
            new_v = [0] * (self.env.ncol * self.env.nrow)
            
            for s in range(self.env.ncol * self.env.nrow):
                qsa_list = []
                for a in range(4):  # 四个动作方向
                    qsa = 0
                    for p, next_state, r, done in self.env.P[s][a]:
                        qsa += p * (
                            r + self.gamma * self.v[next_state] * (1 - done)
                        )
                    qsa_list.append(self.pi[s][a] * qsa)
                    
                new_v[s] = sum(qsa_list)
                max_diff = max(max_diff, abs(new_v[s] - self.v[s]))
                
            self.v = new_v
            if max_diff < self.theta:
                break
            cnt += 1
            
        print(f"策略评估完成（共迭代{cnt}轮）")
        return self.v

    def policy_improvement(self):
        """策略改进（控制）"""
        new_pi = []
        for s in range(self.env.nrow * self.env.ncol):
            q_values = []
            for a in range(4):
                qsa = 0
                for p, next_state, r, done in self.env.P[s][a]:
                    qsa += p * (
                        r + self.gamma * self.v[next_state] * (1 - done)
                    )
                q_values.append(qsa)
            
            max_q = max(q_values)
            optimal_actions = [i for i, q in enumerate(q_values) if q == max_q]
            new_pi.append([
                1/len(optimal_actions) if a in optimal_actions else 0 
                for a in range(4)
            ])
            
        print("策略提升完成")
        self.pi = new_pi
        return self.pi

    def policy_iteration(self):
        """策略迭代主循环"""
        while True:
            self.policy_evaluation()
            old_pi = [row.copy() for row in self.pi]
            self.policy_improvement()
            if old_pi == self.pi:
                break
        return self.pi

常见错误

⚠ 在动态规划中，错误地假设环境动态未知会导致算法无法正常运作。

个人见解 [思考]

在实际应用中，如何选择策略迭代与价值迭代？
动态规划如何在非静态环境中有效应用？
有哪些方法可以降低动态规划的计算复杂度？

行动清单

进一步研究动态规划在不同类型问题中的应用。
探索如何在不完全已知环境中应用动态规划。
实施代码示例以加深对算法过程的理解。

📈趋势预测

随着计算能力的提升和更多复杂环境模拟器的开发，动态规划将在更多实际应用中得到广泛使用。

后续追踪

研究动态规划在随机环境中的扩展。
探讨结合深度学习的方法以提升动态规划的效率。

来源：原始内容来自于某强化学习教程。