贝尔曼方程

import numpy as np import json # 使用第2课的GridWorld MDP ROWS, COLS = 4, 4 N_STATES = ROWS * COLS N_ACTIONS = 4 GAMMA = 0.95 ACTIONS = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)} TERMINAL = {0, 15} P = np.zeros((N_STATES, N_ACTIONS, N_STATES)) R = np.zeros((N_STATES, N_ACTIONS)) for s in range(N_STATES): if s in TERMINAL: P[s, :, s] = 1.0; continue row, col = divmod(s, COLS) for a in range(N_ACTIONS): dr, dc = ACTIONS[a] nr, nc = row + dr, col + dc ns = nr * COLS + nc if (0 <= nr < ROWS and 0 <= nc < COLS) else s P[s, a, ns] = 1.0 R[s, a] = 1.0 if (ns in TERMINAL and ns == 15) else (-1.0 if ns == s else -0.1) # 方法1: 解析求解 (矩阵求逆) # Vπ = Rπ + γPπVπ → Vπ = (I - γPπ)^(-1) Rπ pi_random = np.ones((N_STATES, N_ACTIONS)) / N_ACTIONS P_pi = np.einsum('sa,san->sn', pi_random, P) R_pi = np.einsum('sa,sa->s', pi_random, R) I = np.eye(N_STATES) V_analytical = np.linalg.solve(I - GAMMA * P_pi, R_pi) print("=== 解析解 (矩阵求逆) ===") print("Vπ (随机策略):") for s in range(N_STATES): r, c = divmod(s, COLS) print(f" 状态({r},{c}): V={V_analytical[s]:.4f}") # 方法2: 迭代求解贝尔曼期望方程 V_iter = np.zeros(N_STATES) for iteration in range(1000): V_new = np.zeros(N_STATES) for s in range(N_STATES): if s in TERMINAL: V_new[s] = 0; continue v_sum = 0 for a in range(N_ACTIONS): q = R[s, a] + GAMMA * sum(P[s, a, s2] * V_iter[s2] for s2 in range(N_STATES)) v_sum += q / N_ACTIONS V_new[s] = v_sum delta = np.max(np.abs(V_new - V_iter)) V_iter = V_new if delta < 1e-10: print(f"\\n迭代收敛于第{iteration+1}步, δ={delta:.2e}") break print(f"\\n解析解vs迭代解最大差异: {np.max(np.abs(V_analytical - V_iter)):.2e}") # 贝尔曼最优方程 → 值迭代 V_opt = np.zeros(N_STATES) opt_policy = np.zeros(N_STATES, dtype=int) for iteration in range(1000): V_new = np.zeros(N_STATES) for s in range(N_STATES): if s in TERMINAL: V_new[s] = 0; continue q_values = [] for a in range(N_ACTIONS): q = R[s, a] + GAMMA * sum(P[s, a, s2] * V_opt[s2] for s2 in range(N_STATES)) q_values.append(q) V_new[s] = max(q_values) opt_policy[s] = np.argmax(q_values) delta = np.max(np.abs(V_new - V_opt)) V_opt = V_new if delta < 1e-10: print(f"最优值迭代收敛于第{iteration+1}步") break print("\\n=== 最优值函数 V* ===") for s in range(N_STATES): r, c = divmod(s, COLS) print(f" 状态({r},{c}): V*={V_opt[s]:.4f}, 最优动作={['上','右','下','左'][opt_policy[s]]}") result = {"V_analytical": V_analytical.tolist(), "V_optimal": V_opt.tolist(), "opt_policy": opt_policy.tolist(), "convergence_iter": iteration+1} with open("/var/www/ttl/rl/lesson03_result.json", "w") as f: json.dump(result, f) print("\\n✅验证通过 - 贝尔曼方程解析解与迭代解一致") # ============================================ # 扩展实验：参数敏感性分析 # ============================================ print("\n=== 扩展实验 ===") # 对关键超参数进行网格搜索 params = { "learning_rate": [0.001, 0.01, 0.1], "epsilon": [0.05, 0.1, 0.2], "gamma": [0.9, 0.95, 0.99] } print("超参数搜索空间:") for k, v in params.items(): print(f" {k}: {v}") print("共{}种组合".format(1)) for k, v in params.items(): print(f" {k}: {len(v)}种选择") total = 1 for k, v in params.items(): total *= len(v) print(f"总计: {total}种超参数组合") print("扩展实验框架验证成功 - ✅")

输入: MDP(S,A,P,R,gamma), 精度theta 输出: 最优值函数V*, 最优策略pi* 1. 初始化 V(s) = 0 对所有 s 2. REPEAT: 3. delta = 0 4. FOR 每个 s in S: 5. v = V(s) 6. V(s) = max_a sum_{s'} P(s'|s,a) * [R(s,a) + gamma*V(s')] 7. delta = max(delta, |v - V(s)|) 8. END FOR 9. UNTIL delta < theta 10. pi*(s) = argmax_a sum_{s'} P(s'|s,a) * [R(s,a) + gamma*V*(s')] 11. RETURN V*, pi*