关于贝尔曼方程与动态规划的一份介绍

🕗 发布于 2024-12-10 09:04 机器学习 学习 人工智能 python

在强化学习（RL）中，贝尔曼方程与动态规划（DP）发挥着重要的作用，它们可以帮助我们理解并解决 agent 在如何在环境中做出最优决策。在这篇文章中，我将分别介绍贝尔曼方程以及动态规划算法，具体将包括贝尔曼方程的推导、用处与具体例子，以及 DP 算法的基本概念、用处与实例等内容。

一、贝尔曼方程

1.1 方程推导

首先，我们知道，贝尔曼方程是描述在一个决策过程中，当前状态的价值可以通过立即获得的奖励和下一状态的预期价值来递归计算的一种数学表达式。也就是说：它提供了一种方式来将未来的奖励折现到现在，并通过这种递归关系来评估不同状态或动作的好坏。下面来看它的推导：

贝尔曼方程的推导依赖马尔可夫决策过程（MDP）的基本假设，即未来的状态只依赖于当前的状态和采取的动作，而不受之前状态的影响。

先来看假设部分：

对于环境部分，我们将之假设为可以建模为一个马尔可夫决策过程（MDP），由五元组 (S,A,P,R,γ) 定义，其中 S 是状态空间，A 是动作空间，P 是状态转移概率矩阵，R 是奖励函数，γ 是折扣因子（0≤γ<1）。

然后我们开始推导：

对于给定的策略 π，状态价值函数 $V^{\pi }(s)$ 可以定义为从状态 s 开始，遵循策略 π 所能获得的预期回报。这个预期回报是立即奖励与未来所有奖励的折现和。所以有：

$V^{\pi }=E_{\pi}[G_t|S_t=s]$

其中， $G_t$ 是从时间步 t 开始的总折现奖励，即：

$G_t=R_{t+1}+\gamma R_{t+2}+\gamma ^2R_{t+3}+...$

同时，根据马尔可夫性质，上述式子还可以写为：

$V^{\pi} = \sum_a \pi (a|s)\sum_{{s}',r}P({s}'|s,a)[r+\gamma max_{{s}'}Q^{*}({s}',{a}')]$

这便是贝尔曼期望方程，它表示了状态价值函数如何通过未来的状态价值递归地表达出来。

然后，对于一个最优策略 $\pi^*$ ，我们希望找到一个策略，使得对于所有的状态 s，都能最大化 $V^{\pi}(s)$ 。因此，最优状态价值函数 $V^*(s)$ 应该满足以下条件：

$V^*(s)=max_{\pi}V^{\pi}(s)$

所以，我们可以得到贝尔曼最优方程：

$V^*(s)=max_{a}\sum_{{s}',r}P({s}'|s,a)[r+\gamma V^*({s}')]$

此时，如果我们考虑—状态价值函数 $Q^*(s,a)$ ，则有：

$Q^*(s,a)=\sum _{{s}',r}P({s}'|s,a)[r+\gamma max_{{a}'}Q^*({s}',{a}')]$

这意味着，在任何给定状态下，最优动作-状态价值函数 $Q^*(s,a)$ 是立即奖励加上从下一个状态开始的最大预期未来奖励的折现值。

1.2 用处

贝尔曼方程定义了最优价值函数 $V^*(s)$ 和 $Q^*(s,a)$ ，这可以帮助指导我们找到最优策略——即能够最大化长期奖励的策略。这是强化学习的核心目标之一。同时，贝尔曼方程也为多种强化学习提供了理论框架，无论是基于模型的方法还是无模型的方法，都在某种程度上依赖于贝尔曼方程来推导其更新规则。

1.3 具体例子

假设我们有一个4x4的网格世界，智能体可以在四个方向上移动：上、下、左、右。每个动作的成功率为100%，并且每次移动都会得到一个小的负奖励（例如 -0.04），以鼓励快速到达目标。有两个特殊的状态：

终止状态 A：位于 (1, 1)（即第一行第一列），当智能体进入此状态时，它会立即获得 +1 的奖励并结束幕。

终止状态 B：位于 (4, 4)（即第四行第四列），当智能体进入此状态时，它会立即获得 +1 的奖励并结束幕。

所有其他非终止状态的价值初始化为零，折扣因子 γ=1（即不考虑未来奖励的折现）

对于这个环境中任意一个非终止状态 s，如果我们采用随机策略（即在每个状态下等概率地选择四个方向中的任何一个），那么该状态的价值 V(s) 可以用贝尔曼期望方程来计算：

因为策略是均匀随机的，所以有 $\pi (a|s)=0.25$ ，那么整合所有信息，贝尔曼方程就变为：

$V(s)=\sum _a0.25(-0.04+V({s}'))$

具体地，如果我们要计算 s(2,2) 的价值时，我们可以有如下式子：

$V((2,2))=0.25\cdot [-0.04+V((1,2))]+0.25\cdot [-0.04+V((3,2))]+0.25\cdot [-0.04+V((2,1))]+0.25\cdot [-0.04+V((2,3))]$

我们可以通过这个图像来更直观地理解，图像如下：

二、动态规划（DP）

2.1 基本概念

在RL中，贝尔曼方程是DP算法的理论基础，就是说DP算法是利用它来开发出一系列迭代方法来逼近或精确求解这些价值函数。具体地有四个方面，分别是策略评估、策略改进、策略迭代与价值迭代。详细来说，策略评估（Policy Evaluation）是使用贝尔曼期望方程来计算给定策略 π 下的状态价值函数 $V^{\pi}(s)$ 或动作-状态价值函数 $Q^{\pi}(s,a)$ ，通过不断更新每个状态的价值直到收敛。

而策略改进（Policy Improvement） 则是根据贝尔曼最优性方程来选择在每个状态下最大化 $Q^*(s,a)$ 的动作，从而改进策略。

至于策略迭代（Policy Iteration） 则是结合策略评估和策略改进两个步骤，形成一个迭代的过程，重复这两个步骤直到策略不再改变或达到某个终止条件。

然后是价值迭代（Value Iteration） 直接应用贝尔曼最优性方程来更新状态价值函数，假设已经找到了最优策略，并根据该方程更新价值函数，直到收敛。这种方法不需要显式地存储和更新策略，而是在每一步都隐式地选择最优动作。

此外，还有广义策略迭代（Generalized Policy Iteration, GPI），不过GPI并不是一种具体的算法，而是一种描述策略评估与策略改进之间关系的概念。它指出，在实际应用中，策略评估和策略改进不一定严格分开，而是可以在任何程度上同时发生。例如，某些情况下可能会交替进行少量的评估和改进，或者甚至是一边评估一边改进。

最后来说一下异步DP算法（Asynchronous Dynamic Programming, ADP），它是传统的DP算法的一种变种，也就是说，在传统的DP算法中，我们是需要更新或遍历完所有的价值函数的，但是异步DP算法不同，它允许我们更自由地去选择那些状态去更新，或随机选择状态去更新，这样可以帮助我们更快实现价值函数的收敛。

2.2 用处

在RL中，DP算法的用处十分广泛，比如它可以帮助我们求解有限且完全已知的MDP、辅助探索与利用的平衡（在某些情况下，DP算法可以帮助agent更好地了解哪些动作更有潜力，从而在探索未知选项和利用已知信息之间做出更好的权衡），还是启发式搜索与近似方法的基础等。

2.3 具体例子

具体题目还是如 3.3 中的那样，还是一个 4x4 的网格世界，我们可以根据DP算法写出代码如下：

import numpy as np

# 定义网格大小和终止状态
GRID_SIZE = 4
TERMINAL_STATES = {(1,1): +1, (4,4): -1}  # 终止状态及其奖励
REWARD = -0.04  # 每一步的小负奖励
GAMMA = 1.0    # 折扣因子

# 初始化价值函数为零
V = np.zeros((GRID_SIZE, GRID_SIZE))

# 定义可能的动作：上、下、左、右
ACTIONS = ['up', 'down', 'left', 'right']

# 定义动作的映射，用于更新位置
ACTION_MAP = {
    'up': (-1, 0),
    'down': (1, 0),
    'left': (0, -1),
    'right': (0, 1)
}

# 定义一个辅助函数来检查是否越界
def is_valid_state(state):
    x, y = state
    return 0 <= x < GRID_SIZE and 0 <= y < GRID_SIZE

# 实现价值迭代算法
def value_iteration(V, gamma=GAMMA, reward=REWARD, threshold=1e-4):
    while True:
        delta = 0
        for x in range(GRID_SIZE):
            for y in range(GRID_SIZE):
                if (x, y) in TERMINAL_STATES:
                    continue
                v = V[x, y]
                new_value = float('-inf')
                for action in ACTIONS:
                    dx, dy = ACTION_MAP[action]
                    next_x, next_y = x + dx, y + dy
                    if not is_valid_state((next_x, next_y)):
                        next_x, next_y = x, y  # 如果越界，则保持原地不动
                    new_value = max(new_value, reward + gamma * V[next_x, next_y])
                V[x, y] = new_value
                delta = max(delta, abs(v - V[x, y]))
        if delta < threshold:
            break
    return V

# 执行价值迭代并输出最终的价值函数
V_optimal = value_iteration(V)

# 输出最终的价值函数
print("Optimal Value Function:")
print(V_optimal)

# 提取最优策略
policy = {}
for x in range(GRID_SIZE):
    for y in range(GRID_SIZE):
        if (x, y) in TERMINAL_STATES:
            policy[(x, y)] = 'TERMINAL'
            continue
        best_action = None
        best_value = float('-inf')
        for action in ACTIONS:
            dx, dy = ACTION_MAP[action]
            next_x, next_y = x + dx, y + dy
            if not is_valid_state((next_x, next_y)):
                next_x, next_y = x, y  # 如果越界，则保持原地不动
            value = REWARD + GAMMA * V_optimal[next_x, next_y]
            if value > best_value:
                best_value = value
                best_action = action
        policy[(x, y)] = best_action

# 输出最优策略
print("\nOptimal Policy:")
for x in range(GRID_SIZE):
    row_policy = [policy[(x, y)] for y in range(GRID_SIZE)]
    print(row_policy)

其输出为：

Optimal Value Function:
[[-0.08 -0.04 -0.08 -0.12]
 [-0.04  0.   -0.04 -0.08]
 [-0.08 -0.04 -0.08 -0.12]
 [-0.12 -0.08 -0.12 -0.16]]

Optimal Policy:
['down', 'down', 'down', 'down']
['right', 'TERMINAL', 'left', 'left']
['up', 'up', 'up', 'up']
['up', 'up', 'up', 'up']

此上

原文地址：https://blog.csdn.net/2301_79096986/article/details/144343222

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：麦肯锡报告 | 2023年科技趋势采纳水平：成熟技术与新兴技术的平衡发展
下一篇：java的23种设计模式使用场景

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14