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$:包含updownleftright
  • 折扣因子$\gamma$:取$0.9$。

值迭代实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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就是每个状态对应的最优价值。

策略提取

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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代表up1代表down2代表left3代表right

总结

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

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

https://zglg.work/reinforcement-learning-zero/8/

作者

AI免费学习网(郭震)

发布于

2024-08-15

更新于

2024-08-16

许可协议

分享转发

交流

更多教程加公众号

更多教程加公众号

加入星球获取PDF

加入星球获取PDF

打卡评论