【Python强化学习】动态规划法中策略迭代和值迭代求解冰湖问题实战（图文解释附源码）

本是古典何须时尚 2023-09-30 18:16 10阅读 0赞

> **需要源码请点赞关注收藏后评论区留言私信~~~**

基于值函数优化策略的方法是先求得值函数，然后通过值函数来求得最优策略。相应地，该类算法的迭代过程可分为策略评估阶段和策略改进阶段。

![da58d46881c74ad891d5f0a8c0b88e58.png][]

在策略评估阶段，算法基于当前策略来求得值函数；在策略改进阶段，算法利用当前值函数来更新策略。

## 动态规划法 ##

### 1：策略迭代算法 ###

状态值函数V\_π(s)可以看作动作值函数Q\_π(s,a)在状态处于s时关于动作a的数学期望：

![01ef6953fe044ec9bfbe6f91b55335b1.png][]

π(a│s)是概率表示的策略，也是Q\_π(s,a)发生的概率值。

同样地，动作值函数Q\_π(s,a)可以看作在状态s执行了动作a后，进入到下一状态s^′的立即回报r^′与下一状态的状态值函数的折扣γV\_π(s^′)之和的数学期望：

![61710c86f9274cc6be6f0ad7fc946306.png][]

式中，P\_ss^′^a是状态转移概率，也是r^′+γV\_π(s^′)发生的概率。

代入

![8c2fec2e23ba4f71a33c64ead7823db9.png][]

可得：

![09537133b6be4475a0fbe0833a977870.png][]

称为状态值函数的贝尔曼期望方程。

在五元组〈S,A,P,R,γ〉和策略π(a│s)均为已知的条件下，根据状态值函数的贝尔曼期望方程，可列出由|S|个独立方程组成的方程组。

其中只有|S|个未知数V\_π(s)，因此，可以求解得到在确定策略π时每个状态值函数的值。

可完成基于值函数求解算法中的策略评估任务。

冰湖问题中，假定当前要评估的策略是在所有状态s都执行向左的动作：

π(0│s)=1, π(1│s)=π(2│s)=π(3│s)=0

根据环境模型，执行向左的动作时，状态0只可能转移到状态0、状态0和状态4，不可能到达终点G，因此，R\_0^a=0。

根据V\_π(s)=∑\_a∈A▒\[π(a│s)(R\_s^a+γ∑\_s^′∈S▒P\_ss^′^aV\_π(s^′))\]和主体在冰面上的移动规则，在状态0，可得：

![55619814f71e4f13b381469d653c63cf.png][]

同样地，在其他每个状态都可得到一个独立的方程。将这些方程联立，得到方程组，可以求得各状态的状态值。

利用计算机对方程组的求解，仍然采用迭代法，其迭代关系式为：

![30909fb299c64d48be225a4459d63515.png][]

其中，上标k表示迭代的轮数，并初始化V\_π^0(s)=0。

s^′是s的下一状态，因此，状态值的求解是通过从未来到现在的反向迭代来进行计算的。

在策略改进阶段，要根据指定策略π时各状态值函数V\_π(s)，采用贪心策略来对强化学习主体的策略进行优化。

根据动作值函数与状态值函数的关系式Q\_π(s,a)=∑\_s^′∈S▒P\_ss^′^a(r^′+γV\_π(s^′))，可求得动作值函数Q\_π(s,a)。 因此，在策略改进阶段，基于贪心策略依据下式来得到新策略π^′(s)：

![7e41c5ff76eb43dfaffbe3e9648aaecd.png][]

策略迭代法流程图如下

![29028760780946d6b2d183e700054a29.png][]

实际运行效果如下

![f0dd0eac4b29476592e942d0f05a9dd6.png][]

部分代码如下

n_states = 16 # 状态空间的大小
    n_actions = 4 # 动作空间的大小
    
    # 对确定性策略pi进行评估，即计算状态值函数
    def policy_evaluation(pi, gamma=1.0):
    
        V_table = np.zeros(n_states) # 状态值函数表
        threshold = 1e-10 # 收敛判断阈值
        
        while True:
            pre_V_table = np.copy(V_table)
            for s in range(n_states):
                = sum([ trans_prob * (r + gamma*pre_V_table[next_s])
                                for trans_prob, next_s, r, done in env.P[s][a]])# 环境模型，存储状态s下采取动作a得到的状态转移概率，下一步状态，回报，完成标志
            if (np.sum((np.fabs(pre_V_table - V_table))) <= threshold): # 是否收敛
                break
    
        return V_table
    
    # 基于新的状态值函数对策略进行改进
    def police_improvement(v_table, gamma=1.0):
    
        pi = np.zeros(n_states)
        for s ge(n_actions):
                for next_sr in env.P[s][a]: # 环境模型，存储状态s下采取动作a得到的状态转移概率，下一步状态，回报，完成标志
                    trans_prob, next_s, r, done = next_sr
                    Q_table[a] += (trans_prob * (r + gamma*v_table[next_s]))
            pi[s] = np.argmax(Q_table) # 贪心策略
    
        return pi
    
    # 策略迭代
    def policy_iteration(gamma=1.0):
        
        pi = np.zeros(n_states) # 0初始化策略
    provement(V_table, gamma)
            i += 1
            #print("迭代次数：", i, "\n\tV_table:", V_table, "\n\tpi:", new_pi)
            if (np.all(pi == new_pi)): break # 是否收敛
            pi = new_pi
    
        return pi

### 2：值迭代算法 ###

在策略迭代算法中，在一个迭代周期里，通过计算动作值函数的数学期望来更新状态值函数，而在所谓的值迭代算法中，则是直接取最大动作值函数来更新状态值函数：

![4d33e5f71f104ceb8567850cb17dd750.png][]

与策略迭代算法不同的是，值迭代每次迭代只进行策略评估。当状态值函数收敛后，再进行一次策略改进即可。

流程图如下

# 值迭代
    def value_itration(env, gamma=1.0):
    
        V_table = np.zeros(n_states)
        n_iterations = 10000
        threshold = 1e-10
    
        for i in range(n_iterations):
            pre_V_table = np.copy(V_table)
            for s in range(n_states):
                Q = [] # 状态s的Q值
                for a in range(n_actions):
                    next_s_prob_rewards = [] # 到下一状态的转移概率乘以下一状态的累积回报
                    for next_sr in env.P[s][a]:
                        trans_prob, next_s, r, done = next_sr
                        next_s_prob_rewards.append( ( trans_prob * ( r + gamma*pre_V_table[next_s] ) ) ) # 式8-31
                        Q.append( np.sum( next_s_prob_rewards ) )
                        V_table[s] = max(Q)
            if( np.sum( np.fabs( pre_V_table - V_table ) ) <= threshold ): break
    
        return V_table
    
    best_V_table = value_itration(env=env, gamma=1.0)
    print("最优状态值函数：", best_V_table)
    best_pi = police_improvement(best_V_table, gamma=1.0)
    print("值迭代算法计算最优策略:", best_pi)

定义所有策略中最大的状态值函数为最优状态值函数V^∗(s)： V^∗(s)=max┬πV\_π(s) 同样，可以定义所有策略中最大的动作值函数为最优动作值函数Q^∗(s,a)： Q^∗(s,a)=max┬πQ\_π(s,a) 当采用最优状态值函数时，状态值函数贝尔曼方程称为贝尔曼最优方程，写为：

![4126d160b55f4fd29d5e3953f9cd8334.png][]

在冰湖问题中实际运行结果如下

![4d81670831f546bcad040bae01e4ec42.png][]

部分代码如下

# 值迭代
    def value_itration(env, gamma=1.0):
    
        V_table = np.zeros(n_states)
        n_iterations = 10000
        threshold = 1e-10
    
        for i in range(n_iterations):
            pre_V_table = np.copy(V_table)
            for s in range(n_states):
                Q = [] # 状态s的Q值
                for a in range(n_actions):
                    next_s_prob_rewards = [] # 到下一状态的转移概率乘以下一状态的累积回报
                    for next_sr in env.P[s][a]:
                        trans_prob, next_s, r, done = next_sr
                 ( pre_V_table - V_table ) ) <= threshold ): break
    
        return V_table
    
    best_V_table = value_itration(env=env, gamma=1.0)
    print("最优状态值函数：", best_V_table)
    best_pi = police_improvement(best_V_table, gamma=1.0)
    print("值迭代算法计算最优策略:", best_pi)

**创作不易 觉得有帮助请点赞关注收藏~~~**

[da58d46881c74ad891d5f0a8c0b88e58.png]: https://img-blog.csdnimg.cn/da58d46881c74ad891d5f0a8c0b88e58.png
[01ef6953fe044ec9bfbe6f91b55335b1.png]: https://img-blog.csdnimg.cn/01ef6953fe044ec9bfbe6f91b55335b1.png
[61710c86f9274cc6be6f0ad7fc946306.png]: https://img-blog.csdnimg.cn/61710c86f9274cc6be6f0ad7fc946306.png
[8c2fec2e23ba4f71a33c64ead7823db9.png]: https://img-blog.csdnimg.cn/8c2fec2e23ba4f71a33c64ead7823db9.png
[09537133b6be4475a0fbe0833a977870.png]: https://img-blog.csdnimg.cn/09537133b6be4475a0fbe0833a977870.png
[55619814f71e4f13b381469d653c63cf.png]: https://img-blog.csdnimg.cn/55619814f71e4f13b381469d653c63cf.png
[30909fb299c64d48be225a4459d63515.png]: https://img-blog.csdnimg.cn/30909fb299c64d48be225a4459d63515.png
[7e41c5ff76eb43dfaffbe3e9648aaecd.png]: https://img-blog.csdnimg.cn/7e41c5ff76eb43dfaffbe3e9648aaecd.png
[29028760780946d6b2d183e700054a29.png]: https://img-blog.csdnimg.cn/29028760780946d6b2d183e700054a29.png
[f0dd0eac4b29476592e942d0f05a9dd6.png]: https://img-blog.csdnimg.cn/f0dd0eac4b29476592e942d0f05a9dd6.png
[4d33e5f71f104ceb8567850cb17dd750.png]: https://img-blog.csdnimg.cn/4d33e5f71f104ceb8567850cb17dd750.png
[4126d160b55f4fd29d5e3953f9cd8334.png]: https://img-blog.csdnimg.cn/4126d160b55f4fd29d5e3953f9cd8334.png
[4d81670831f546bcad040bae01e4ec42.png]: https://img-blog.csdnimg.cn/4d81670831f546bcad040bae01e4ec42.png