24/8/15算法笔记 dp策略迭代 价值迭代

1. 策略迭代：

   • 策略迭代从某个策略开始，计算该策略下的状态价值函数。
   • 它交替进行两个步骤：策略评估（Policy Evaluation）和策略改进（Policy Improvement）。
   • 在策略评估阶段，计算给定策略下每个状态的期望回报。
   • 在策略改进阶段，尝试找到一个更好的策略，该策略对于每个状态选择最优动作。
   • 这个过程一直进行，直到策略收敛，即不再有改进的空间。

2. 价值迭代：

   • 价值迭代直接迭代状态价值函数，而不是策略。
   • 它从任意状态价值函数开始，然后迭代更新每个状态的价值，直到收敛。
   • 在每次迭代中，对所有状态使用贝尔曼最优性方程（Bellman Optimality Equation）来更新其价值。
   • 价值迭代通常比策略迭代更快收敛到最优价值函数。

3. 收敛性：

   • 策略迭代保证在有限次迭代后收敛到最优策略和最优价值函数。
   • 价值迭代也保证收敛，但收敛速度可能因问题而异。

4. 计算复杂度：

   • 策略迭代可能需要多次策略评估，每次评估都涉及对所有状态的操作，因此在某些情况下可能比较慢。
   • 价值迭代每次迭代只更新一次所有状态的价值，但可能需要更多次迭代才能收敛。

5. 适用性：

   • 策略迭代在策略空间较大或状态转移概率较复杂时可能更有效。
   • 价值迭代适用于状态空间较大且容易计算贝尔曼最优性方程的情况。

6. 实现方式：

   • 策略迭代通常使用循环，外部循环负责策略评估，内部循环负责策略改进。
   • 价值迭代使用单一循环，每次迭代更新所有状态的价值。

策略迭代：

#获取一个格子的状态
def get_state(row,col):if row !=3:return'ground'if row ==3 and col ==0:return 'ground'if row==3 and col==11:return 'terminal'return 'trap'
get_state(0,0)

地图上有平地，陷阱，终点

#在一个格子里做动作
def move(row,col,action):#如果当前已经在陷阱或者终点，则不能执行任何动作，反馈都是0if get_state(row,col)in['trap','terminal']:return row,col,0#向上if action==0:row-=1#向下if action ==1:row+=1#向左if action==2:col-=1#向右if action==3:col+=1#不允许走到地图外面去row = max(0,row)row = min(3,row)col =max(0,col)col =min(11,col)#是陷阱的话，奖励是-100，否则都是-1#这样强迫了机器尽快结束游戏，因为每走一步都要扣一分#结束最好是以走到终点的形式，避免被扣100分reward = -1if get_state(row,col)=='trap':reward -=100return row,col,reward

import numpy as np#初始化每个格子的价值
values = np.zeros([4,12])#初始化每个格子下采用动作的概率
pi = np.ones([4,12,4])*0.25values,pi[0]

#Q函数，求state,action的分数
#计算在一个状态下执行动作的分数
def get_qsa(row,col,action):#当前状态下执行动作，得到下一个状态和rewardnext_row,next_col,reward = move(row,col,action)#计算下一个状态分数，取values当中记录的分数即可，0.9是折扣因子value = values[next_row,next_col]*0.9#如果下个状态是终点或者陷阱，则下一个状态分数为0if get_state(next_row,next_col)in ['trap','terminal']:value = 0#动作的分数本身就是reward,加上下一个状态的分数return value + reward
get_qsa(0,0,0)

-1.0

#策略评估
def get_values():#初始化一个新的values,重新评估所有格子的分数new_values = np.zeros([4,12])#遍历所有格子for row in range(4):for col in range(12):#计算当前格子4个动作分别的分数action_value = np.zeros(4)#遍历所有动作for action in range(4):action_value[action] = get_qsa(row,col,action)#每个动作的分数和它的概率相乘action_value *=pi[row,col]#最后这个格子的分数，等于该格子下所有动作的分数求和new_values[row,col] = action_value.sum()return new_values
get_values()

#策略提升函数
def get_pi():#重新初始化每个格子下采用动作的概率，重新评估new_pi = np.zeros([4,12,4])#遍历所有格子for row in range(4):for col in range(12):#计算当前格子4个动作分别的分数action_value = np.zeros(4)#遍历所有动作for action in range(4):action_value[action] = get_qsa(row,col,action)#计算当前状态下，达到最大分数的动作有几个count = (action_value == action_value.max()).sum()#让这些动作均分概率for action in range(4):if action_value[action]==action_value.max():new_pi[row,col,action] = 1/countelse:new_pi[row,col,action]=0return new_pi
get_pi()

#循环迭代策略评估和策略提升，寻找最优解
for _ in range(10):for _ in range(100):values = get_values()pi = get_pi()
values,pi

#打印游戏，方便测试
def show(row,col,action):graph=['','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','2','2','2','2','2',   '2','2','2','2','2','1']action = {0:'上',1:'下',2:'左',3:'右'}[action]graph[row*12+col] = actiongraph=' '.join(graph)for i in range(0,4*12,12):print(graph[i:i+12])show(1,1,0)

#测试函数
from IPython import display
import timedef test():#起点在0,0row = 0col = 0#最多玩N步for _ in range(200):#选择一个动作action = np.random.choice(np.arange(4),size = 1,p=pi[row,col])[0]#打印这个动作display.clear_output(wait = True)time.sleep(1)show(row,col,action)#执行动作row,col,reward = move(row,col,action)#获取当前状态，如果状态是终点或者掉到陷阱则终止if get_state(row,col) in ['trap','terminal']:break
test()

价值迭代算法：

def get_values():#初始化一个新的values，重新评估所有格子的分数new_values = np.zeros([4,12])#遍历所有格子for row in range(4):for col in range(12):#计算当前格子4个动作分别的分数action_value = np.zeros(4)#遍历所有动作for action in range(4):action_value[action] = get_qsa(row,col,action)"""和策略迭代算法唯一的不同点"""#求每一个格子的分数，等于该格子下所有动作的最大分数new_values[row,col] = action_value.max()return new_values
get_values()