8 强化学习从零学教程系列之动态规划之值迭代算法

在上一篇教程中，我们探讨了动态规划的基本思想和框架，为我们后续学习强化学习打下了坚实的基础。在本篇中，我们将深入了解动态规划的一种具体实现——值迭代算法。这一算法在解决马尔可夫决策过程（MDP）中的最优策略时，提供了一种有效的计算手段。

值迭代算法概述

值迭代算法是一种在给定状态空间和动作空间的条件下，通过递归地更新状态价值，从而逐步收敛到最优值函数的动态规划方法。值迭代不仅可以用于求解最优价值函数，还能获取最优策略。

算法步骤

值迭代算法的主要步骤如下：

1. 初始化：为所有状态初始化一个任意的价值函数，通常是将所有状态的价值设为0。
2. 更新价值函数：根据贝尔曼方程更新每个状态的价值函数：
   $$
   V_{i+1}(s) = \max_{a \in A} \sum_{s’ \in S} P(s’|s, a)[R(s, a, s’) + \gamma V_i(s’)]
   $$
   其中，$V_i(s)$ 是状态$s$ 在第$i$次更新时的价值，$P(s’|s, a)$ 是在状态$s$下采取动作$a$后转移到状态$s’$的概率，$R(s, a, s’)$ 是在此转移中获得的奖励，$\gamma$ 是折扣因子。
3. 收敛判断：不断迭代更新价值函数，直到价值函数的变化小于定义好的阈值（如0.01）。
4. 获取策略：依据最终的价值函数，推导出最优策略：
   $$
   \pi^*(s) = \arg \max_{a \in A} \sum_{s’ \in S} P(s’|s, a)[R(s, a, s’) + \gamma V(s’)]
   $$

示例：网格世界

为更好地理解值迭代算法，我们通过一个简化的示例——网格世界来说明。

问题描述

假设我们有一个$4 \times 4$的网格世界，智能体在每个状态（网格单元）中可以选择向上、向下、向左或向右移动。目标是使智能体尽快到达目标状态（右下角），并且每次移动都要消耗$1$的奖励。目标状态的奖励为$0$，其他状态的奖励均为$-1$。

设置参数

• 状态空间$S$：包含所有的$16$个网格。
• 动作空间$A$：包含up、down、left、right。
• 折扣因子$\gamma$：取$0.9$。

值迭代实现

import numpy as np

# 定义环境参数
grid_size = 4
num_actions = 4
gamma = 0.9
theta = 0.01

# 定义奖励结构
R = -np.ones((grid_size, grid_size))
R[3, 3] = 0  # 目标状态的奖励

# 定义状态转移概率（简单处理，假设概率为1）
def get_next_states(s, a):
    x, y = s
    if a == 0: # up
        return max(x-1, 0), y
    elif a == 1: # down
        return min(x+1, grid_size-1), y
    elif a == 2: # left
        return x, max(y-1, 0)
    elif a == 3: # right
        return x, min(y+1, grid_size-1)

# 值迭代函数
def value_iteration():
    V = np.zeros((grid_size, grid_size))
    while True:
        delta = 0
        for x in range(grid_size):
            for y in range(grid_size):
                v = V[x, y]
                V[x, y] = max(sum(1 * (R[get_next_states((x, y), a)] + gamma * V[get_next_states((x, y), a)]))
                               for a in range(num_actions))
                delta = max(delta, abs(v - V[x, y]))
        if delta < theta:
            break
    return V

# 运行值迭代
V = value_iteration()
print(V)

在以上代码中，我们通过一个简单的数组V来维持各状态的价值。每次我们都会更新状态价值，直到所有状态的价值收敛。最终返回的V就是每个状态对应的最优价值。

策略提取

一旦获取到最终的价值函数，我们可以根据上述策略公式，从每个状态推导出最优策略。

def extract_policy(V):
    policy = np.zeros((grid_size, grid_size), dtype=int)
    for x in range(grid_size):
        for y in range(grid_size):
            best_action = None
            best_value = float('-inf')
            for a in range(num_actions):
                next_state = get_next_states((x, y), a)
                value = R[next_state] + gamma * V[next_state]
                if value > best_value:
                    best_value = value
                    best_action = a
            policy[x, y] = best_action
    return policy

# 提取最优策略
policy = extract_policy(V)
print(policy)

在策略提取的过程中，我们遍历每个状态，选择能够带来最大价值的动作，并形成最终的policy。每个动作可以用数字表示，比如0代表up，1代表down，2代表left，3代表right。

总结

本文详细介绍了值迭代算法的工作机制，并通过实践案例展示了如何在一个简单的网格世界中实现它。值迭代是动态规划的重要组成部分，广泛应用于强化学习中。掌握了这一算法后，我们将在下一篇教程中进一步探讨动态规划的另一个经典算法——策略迭代算法。希望大家能在实践中不断探索并深化对强化学习的理解！