从零实现赌徒问题的策略迭代与值迭代算法1. 问题描述与建模赌徒问题是一个经典的马尔可夫决策过程(MDP)示例它描述了一个赌徒在不确定环境中进行决策的过程。在这个问题中赌徒每次可以选择下注一定金额以一定概率赢得或输掉这笔赌注。我们的目标是找到在不同资金状态下最优的下注策略。1.1 问题形式化定义让我们首先将赌徒问题形式化为一个MDP状态空间(S)赌徒当前持有的资金金额s ∈ {0, 1, 2, ..., 100}动作空间(A)在状态s时可用的下注金额a ∈ {1, 2, ..., min(s, 100-s)}转移概率以概率p赢得赌注以概率1-p输掉赌注奖励函数仅在达到100美元时获得1奖励其他情况奖励为0class GamblerProblem: def __init__(self, goal100, win_prob0.4): self.goal goal self.win_prob win_prob self.states np.arange(goal 1) self.terminal_states [0, goal]1.2 MDP的核心组件马尔可夫决策过程由以下几个核心组件构成状态转移矩阵描述从一个状态执行某个动作后转移到新状态的概率策略从状态到动作的映射决定在每种状态下采取什么动作价值函数评估在特定状态下遵循特定策略的长期回报状态转移公式 P(s|s,a) { win_prob if s s a 1-win_prob if s s - a 0 otherwise }2. 策略迭代算法实现策略迭代是一种经典的动态规划方法用于求解MDP的最优策略。它通过交替进行策略评估和策略改进来逐步优化策略。2.1 策略评估策略评估阶段计算给定策略下的状态价值函数。我们使用迭代策略评估方法通过反复应用Bellman期望方程来收敛到真实价值函数。def policy_evaluation(self, policy, theta1e-8): V np.zeros(self.goal 1) V[self.goal] 1.0 # 达到目标时的奖励 while True: delta 0 for s in self.states[1:self.goal]: v V[s] a policy[s] # Bellman方程更新 V[s] self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] delta max(delta, abs(v - V[s])) if delta theta: break return V2.2 策略改进在策略改进阶段我们基于当前价值函数贪婪地选择动作即选择能够最大化下一状态价值的动作。def policy_improvement(self, V): policy np.zeros(self.goal 1, dtypeint) for s in self.states[1:self.goal]: possible_actions np.arange(1, min(s, self.goal - s) 1) # 计算每个动作的期望回报 action_returns [self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] for a in possible_actions] # 选择最优动作 policy[s] possible_actions[np.argmax(action_returns)] return policy2.3 完整策略迭代流程将策略评估和策略改进交替进行直到策略不再变化def policy_iteration(self, max_iter1000): # 初始化随机策略 policy np.random.randint(1, self.goal//2, sizeself.goal 1) for s in self.states[1:self.goal]: policy[s] np.random.randint(1, min(s, self.goal - s) 1) for _ in range(max_iter): V self.policy_evaluation(policy) new_policy self.policy_improvement(V) if np.array_equal(policy, new_policy): break policy new_policy return policy, V3. 值迭代算法实现值迭代是另一种求解MDP的方法它直接优化价值函数而不需要显式地维护策略。3.1 值迭代核心思想值迭代的核心是反复应用Bellman最优方程V(s) maxₐ [r(s,a) γΣₛ P(s|s,a)V(s)]与策略迭代不同值迭代在每次更新时都选择最优动作而不是遵循固定策略。def value_iteration(self, theta1e-8): V np.zeros(self.goal 1) V[self.goal] 1.0 while True: delta 0 for s in self.states[1:self.goal]: v V[s] possible_actions np.arange(1, min(s, self.goal - s) 1) # 计算每个动作的期望回报并取最大值 action_returns [self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] for a in possible_actions] V[s] max(action_returns) delta max(delta, abs(v - V[s])) if delta theta: break # 从最优价值函数中提取策略 policy self.extract_policy(V) return policy, V3.2 从价值函数提取策略在值迭代收敛后我们可以从最优价值函数中提取出最优策略def extract_policy(self, V): policy np.zeros(self.goal 1, dtypeint) for s in self.states[1:self.goal]: possible_actions np.arange(1, min(s, self.goal - s) 1) action_returns [self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] for a in possible_actions] policy[s] possible_actions[np.argmax(action_returns)] return policy4. 算法比较与可视化分析4.1 收敛速度比较我们比较两种算法在不同参数下的收敛速度算法类型平均迭代次数计算复杂度内存需求策略迭代10-20O(n²k)O(n)值迭代50-100O(n²)O(n)注n表示状态数量k表示策略迭代次数4.2 最优策略可视化让我们可视化两种算法得到的最优策略import matplotlib.pyplot as plt def plot_policy(policy, title): plt.figure(figsize(10, 5)) plt.bar(range(len(policy)), policy, width1.0) plt.title(title) plt.xlabel(Capital) plt.ylabel(Optimal Stake) plt.show() # 比较不同赢率下的策略 for p in [0.4, 0.5, 0.6]: gp GamblerProblem(win_probp) pi_policy, _ gp.policy_iteration() vi_policy, _ gp.value_iteration() plot_policy(pi_policy, fPolicy Iteration (p{p})) plot_policy(vi_policy, fValue Iteration (p{p}))4.3 实际应用中的选择建议策略迭代适合策略空间较小的情况需要精确策略评估的场景可以容忍较长的单次迭代时间值迭代适合状态空间较大的问题需要快速获得近似解的情况当策略评估成本过高时在实际项目中我发现值迭代通常更容易实现且收敛性更稳定特别是在状态空间较大的情况下。而策略迭代在策略变化不大时收敛非常快但每次迭代的计算成本较高。
用Python玩转赌徒问题：手把手教你实现MDP的策略迭代与值迭代（附完整代码）
从零实现赌徒问题的策略迭代与值迭代算法1. 问题描述与建模赌徒问题是一个经典的马尔可夫决策过程(MDP)示例它描述了一个赌徒在不确定环境中进行决策的过程。在这个问题中赌徒每次可以选择下注一定金额以一定概率赢得或输掉这笔赌注。我们的目标是找到在不同资金状态下最优的下注策略。1.1 问题形式化定义让我们首先将赌徒问题形式化为一个MDP状态空间(S)赌徒当前持有的资金金额s ∈ {0, 1, 2, ..., 100}动作空间(A)在状态s时可用的下注金额a ∈ {1, 2, ..., min(s, 100-s)}转移概率以概率p赢得赌注以概率1-p输掉赌注奖励函数仅在达到100美元时获得1奖励其他情况奖励为0class GamblerProblem: def __init__(self, goal100, win_prob0.4): self.goal goal self.win_prob win_prob self.states np.arange(goal 1) self.terminal_states [0, goal]1.2 MDP的核心组件马尔可夫决策过程由以下几个核心组件构成状态转移矩阵描述从一个状态执行某个动作后转移到新状态的概率策略从状态到动作的映射决定在每种状态下采取什么动作价值函数评估在特定状态下遵循特定策略的长期回报状态转移公式 P(s|s,a) { win_prob if s s a 1-win_prob if s s - a 0 otherwise }2. 策略迭代算法实现策略迭代是一种经典的动态规划方法用于求解MDP的最优策略。它通过交替进行策略评估和策略改进来逐步优化策略。2.1 策略评估策略评估阶段计算给定策略下的状态价值函数。我们使用迭代策略评估方法通过反复应用Bellman期望方程来收敛到真实价值函数。def policy_evaluation(self, policy, theta1e-8): V np.zeros(self.goal 1) V[self.goal] 1.0 # 达到目标时的奖励 while True: delta 0 for s in self.states[1:self.goal]: v V[s] a policy[s] # Bellman方程更新 V[s] self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] delta max(delta, abs(v - V[s])) if delta theta: break return V2.2 策略改进在策略改进阶段我们基于当前价值函数贪婪地选择动作即选择能够最大化下一状态价值的动作。def policy_improvement(self, V): policy np.zeros(self.goal 1, dtypeint) for s in self.states[1:self.goal]: possible_actions np.arange(1, min(s, self.goal - s) 1) # 计算每个动作的期望回报 action_returns [self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] for a in possible_actions] # 选择最优动作 policy[s] possible_actions[np.argmax(action_returns)] return policy2.3 完整策略迭代流程将策略评估和策略改进交替进行直到策略不再变化def policy_iteration(self, max_iter1000): # 初始化随机策略 policy np.random.randint(1, self.goal//2, sizeself.goal 1) for s in self.states[1:self.goal]: policy[s] np.random.randint(1, min(s, self.goal - s) 1) for _ in range(max_iter): V self.policy_evaluation(policy) new_policy self.policy_improvement(V) if np.array_equal(policy, new_policy): break policy new_policy return policy, V3. 值迭代算法实现值迭代是另一种求解MDP的方法它直接优化价值函数而不需要显式地维护策略。3.1 值迭代核心思想值迭代的核心是反复应用Bellman最优方程V(s) maxₐ [r(s,a) γΣₛ P(s|s,a)V(s)]与策略迭代不同值迭代在每次更新时都选择最优动作而不是遵循固定策略。def value_iteration(self, theta1e-8): V np.zeros(self.goal 1) V[self.goal] 1.0 while True: delta 0 for s in self.states[1:self.goal]: v V[s] possible_actions np.arange(1, min(s, self.goal - s) 1) # 计算每个动作的期望回报并取最大值 action_returns [self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] for a in possible_actions] V[s] max(action_returns) delta max(delta, abs(v - V[s])) if delta theta: break # 从最优价值函数中提取策略 policy self.extract_policy(V) return policy, V3.2 从价值函数提取策略在值迭代收敛后我们可以从最优价值函数中提取出最优策略def extract_policy(self, V): policy np.zeros(self.goal 1, dtypeint) for s in self.states[1:self.goal]: possible_actions np.arange(1, min(s, self.goal - s) 1) action_returns [self.win_prob * V[s a] (1 - self.win_prob) * V[s - a] for a in possible_actions] policy[s] possible_actions[np.argmax(action_returns)] return policy4. 算法比较与可视化分析4.1 收敛速度比较我们比较两种算法在不同参数下的收敛速度算法类型平均迭代次数计算复杂度内存需求策略迭代10-20O(n²k)O(n)值迭代50-100O(n²)O(n)注n表示状态数量k表示策略迭代次数4.2 最优策略可视化让我们可视化两种算法得到的最优策略import matplotlib.pyplot as plt def plot_policy(policy, title): plt.figure(figsize(10, 5)) plt.bar(range(len(policy)), policy, width1.0) plt.title(title) plt.xlabel(Capital) plt.ylabel(Optimal Stake) plt.show() # 比较不同赢率下的策略 for p in [0.4, 0.5, 0.6]: gp GamblerProblem(win_probp) pi_policy, _ gp.policy_iteration() vi_policy, _ gp.value_iteration() plot_policy(pi_policy, fPolicy Iteration (p{p})) plot_policy(vi_policy, fValue Iteration (p{p}))4.3 实际应用中的选择建议策略迭代适合策略空间较小的情况需要精确策略评估的场景可以容忍较长的单次迭代时间值迭代适合状态空间较大的问题需要快速获得近似解的情况当策略评估成本过高时在实际项目中我发现值迭代通常更容易实现且收敛性更稳定特别是在状态空间较大的情况下。而策略迭代在策略变化不大时收敛非常快但每次迭代的计算成本较高。
