当前位置：首页 > news >正文

04-动态规划

news 2025/7/3 11:59:06

动态规划（Dynamic Programming, DP）

1. 理论基础

动态规划是一类用于求解最优决策问题的算法。在强化学习中，动态规划用于已知环境模型（即已知MDP的状态转移概率和奖励函数）的情况下，通过迭代计算状态值函数或动作值函数，找到最优策略。

2. 价值函数与贝尔曼方程

状态值函数：V^π(s) 表示在状态s下，按照策略π行动后能获得的期望累积奖励。
动作值函数：Q^π(s, a) 表示在状态s下采取动作a，后续按照策略π行动的期望累积奖励。
贝尔曼方程：
```
V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s,a) [ R(s,a) + γ V^π(s') ]
```
该方程描述了当前状态的价值等于所有可能动作和转移的加权期望。

3. 价值迭代（Value Iteration）

3.1 算法原理

价值迭代通过反复更新状态值函数，逐步逼近最优值函数V*。

每次迭代根据贝尔曼最优方程更新：

V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a) [ R(s,a) + γ V_k(s') ]

收敛后，最优策略为：

π*(s) = argmax_a Σ_{s'} P(s'|s,a) [ R(s,a) + γ V*(s') ]

3.2 伪代码

初始化 V(s) = 0
重复：对每个状态 s：V_new(s) = max_a Σ_{s'} P(s'|s,a) [ R(s,a) + γ V(s') ]如果所有状态的 V_new(s) 与 V(s) 差异足够小，则停止否则 V(s) ← V_new(s)

3.3 流程图（可用Mermaid或维基百科图片）

推荐图片：Value iteration
引用：
[外链图片转存中…(img-DTzm8Ovw-1751461173012)]

3.4 价值迭代Python代码示例

import numpy as np# 假设有4个状态和2个动作
num_states = 4
num_actions = 2
gamma = 0.9
theta = 1e-4# 随机初始化转移概率P和奖励R
P = np.random.rand(num_states, num_actions, num_states)
P = P / P.sum(axis=2, keepdims=True)
R = np.random.rand(num_states, num_actions)V = np.zeros(num_states)while True:delta = 0for s in range(num_states):v = V[s]V[s] = max(sum(P[s, a, s_next] * (R[s, a] + gamma * V[s_next]) for s_next in range(num_states))for a in range(num_actions))delta = max(delta, abs(v - V[s]))if delta < theta:break# 计算最优策略
policy = np.zeros(num_states, dtype=int)
for s in range(num_states):policy[s] = np.argmax([sum(P[s, a, s_next] * (R[s, a] + gamma * V[s_next]) for s_next in range(num_states))for a in range(num_actions)])print("最优状态值函数:", V)
print("最优策略:", policy)

4. 策略迭代（Policy Iteration）

4.1 算法原理

策略迭代交替进行"策略评估"和"策略改进"两个步骤，直到策略收敛。
策略评估：在当前策略下，计算每个状态的值函数。
策略改进：对每个状态，选择能带来最大值的动作，更新策略。

4.2 伪代码

初始化任意策略 π(s)
重复：1. 策略评估：对所有 s，计算 V^π(s)2. 策略改进：对所有 s，π_new(s) = argmax_a Σ_{s'} P(s'|s,a) [ R(s,a) + γ V^π(s') ]如果 π_new = π，则停止，否则 π ← π_new

4.3 流程图（可用Mermaid或维基百科图片）

推荐图片：Policy iteration
引用：

4.4 策略迭代Python代码示例

import numpy as npnum_states = 4
num_actions = 2
gamma = 0.9
theta = 1e-4P = np.random.rand(num_states, num_actions, num_states)
P = P / P.sum(axis=2, keepdims=True)
R = np.random.rand(num_states, num_actions)policy = np.zeros(num_states, dtype=int)
V = np.zeros(num_states)is_policy_stable = False
while not is_policy_stable:# 策略评估while True:delta = 0for s in range(num_states):v = V[s]a = policy[s]V[s] = sum(P[s, a, s_next] * (R[s, a] + gamma * V[s_next]) for s_next in range(num_states))delta = max(delta, abs(v - V[s]))if delta < theta:break# 策略改进is_policy_stable = Truefor s in range(num_states):old_action = policy[s]action_values = [sum(P[s, a, s_next] * (R[s, a] + gamma * V[s_next]) for s_next in range(num_states))for a in range(num_actions)]policy[s] = np.argmax(action_values)if old_action != policy[s]:is_policy_stable = Falseprint("最优状态值函数:", V)
print("最优策略:", policy)