一文学习什么是马尔科夫决策过程（Markov Decision Process, MDP）、以及它的变体POMDP、Dec_POMDP等

马尔科夫决策过程（MDP）是数学上描述决策问题的一种模型。它被广泛应用于强化学习、运筹学、控制系统和经济学等领域。MDP 用来解决带有不确定性和动态性的序列决策问题。

不去幼儿园

2007人浏览 · 2024-12-17 08:00:00

不去幼儿园 · 2024-12-17 08:00:00 发布

📢本篇文章是博主强化学习（RL）领域学习时，用于个人学习、研究或者欣赏使用，并基于博主对相关等领域的一些理解而记录的学习摘录和笔记，若有不当和侵权之处，指出后将会立即改正，还望谅解。文章分类在👉强化学习专栏：

【强化学习】- 【强化学习基础】（14）---《马尔科夫决策过程（Markov Decision Process, MDP）、以及它的变体POMDP、Dec_POMDP》

马尔科夫决策过程（Markov Decision Process, MDP）、以及它的变体POMDP、Dec_POMDP

什么是马尔科夫决策过程（Markov Decision Process, MDP）

2. 状态值函数 V(s) 的Bellman方程

3. 状态-动作值函数 (Q(s, a)) 的Bellman方程

1. 部分可观测马尔科夫决策过程（POMDP）

2. 分布式马尔科夫决策过程（Dec-POMDP）

3. 分层马尔科夫决策过程（Hierarchical Markov Decision Process, HMDP）

4. 非马尔科夫决策过程（Non-Markov Decision Process, NMDP）

5. 连续时间马尔科夫决策过程（Continuous-time MDP, CTMDP）

6. 随机控制过程（Stochastic Control Process）

7.总结

什么是马尔科夫决策过程（Markov Decision Process, MDP）

1. 定义

一个马尔科夫决策过程由以下五元组组成：

状态空间（States, S）：系统所能处于的所有可能状态的集合。
动作空间（Actions, A）：在某个状态下可以采取的所有可能动作的集合。
状态转移概率（Transition Probability, P）：给定当前状态 s 和动作 a ，转移到下一状态 ( s' ) 的概率： P(s'|s, a)
奖励函数（Reward Function, R）：采取动作 a 后从状态 s 转移到状态 s' 所获得的即时奖励： R(s, a, s')
折扣因子（Discount Factor, γ）：控制未来奖励的重要性，值域为 ( 0-1 )。

2. 特性

马尔科夫性质：当前状态 s_t 已经包含了所有必要的信息，因此状态转移概率仅依赖于当前状态和动作，而与过去的状态无关：

$P(s_{t+1}|s_t, a_t, s_{t-1}, a_{t-1}, \dots) = P(s_{t+1}|s_t, a_t)$

比如下图状态3到状态4的转移概率只和状态3当前的状态和采取的动作有关，和状态1、2无关。

策略（Policy, π）：决策规则，用于描述在状态 s 下采取动作 a 的概率： π(a|s)

3. 目标

MDP 的目标是通过一个最优策略 ( π^* ) 最大化期望累积奖励 $G_t$ ，通常定义为：

其中 $r_{t+k+1}$ 是 $t+k+1$ 时刻的奖励。

Bellman方程的推导过程

Bellman方程是动态规划（Dynamic Programming）的核心思想在马尔科夫决策过程（MDP）中的体现。以下是推导Bellman方程的详细过程，适用于状态值函数 $V(s)$ 和状态-动作值函数 $Q(s, a)$ 。

1. 背景假设

目标是最大化累积折扣奖励：

$G_t = \sum_{k=0}^\infty \gamma^k R_{t+k+1}$

其中：

$R_{t+k+1}$ ：表示从时间 $t+k+1$ 开始的即时奖励。
$\gamma \in [0, 1]$ ：折扣因子，用于控制未来奖励的权重。

我们引入状态值函数 V(s) 和状态-动作值函数 Q(s, a)：

状态值函数： $V(s) = \mathbb{E}[G_t | S_t = s]$
状态-动作值函数： $Q(s, a) = \mathbb{E}[G_t | S_t = s, A_t = a]$

2. 状态值函数 V(s) 的Bellman方程

对于任意状态 s，累积奖励可以分为两部分：

当前即时奖励 $R_t$ 。
从下一状态 $S_{t+1}$ 开始的未来累积奖励。

因此： $V(s) = \mathbb{E}[R_t + \gamma G_{t+1} | S_t = s]$

根据马尔科夫性质（状态转移仅依赖于当前状态和动作）：

$V(s) = \max_a \mathbb{E}[R(s, a, s') + \gamma V(s') | S_t = s, A_t = a]$

展开期望值的形式：

$[V(s) = \max_a \sum_{s'} P(s'|s, a) \left[ R(s, a, s') + \gamma V(s') \right]$

这就是 Bellman期望方程。

3. 状态-动作值函数 (Q(s, a)) 的Bellman方程

类似地，对于状态-动作值函数：

$Q(s, a) = \mathbb{E}[R_t + \gamma G_{t+1} | S_t = s, A_t = a]$

下一时刻的奖励由下一状态 (S_{t+1}) 的状态值函数决定：

$Q(s, a) = \mathbb{E}[R(s, a, s') + \gamma V(s') | S_t = s, A_t = a]$

将状态值函数 (V(s')) 替换为动作值函数的最大值：

$Q(s, a) = \sum_{s'} P(s'|s, a) \left[ R(s, a, s') + \gamma \max_{a'} Q(s', a') \right]$

这就是 Bellman最优方程。

4. Bellman方程的意义

递归定义：Bellman方程是递归定义的，可以通过动态规划逐步求解最优值函数。
动态规划求解：
- 值迭代（Value Iteration）：反复更新 V(s))或 Q(s, a) 直到收敛。
- 策略迭代（Policy Iteration）：在策略评估和策略改进之间交替更新。

[Python] 值迭代算法实现

强化学习项目代码我已经放入GitCode里面，可以通过下面链接跳转：🔥

【强化学习】算法库

后续相关单智能体强化学习算法也会不断在【强化学习】项目里更新，如果该项目对你有所帮助，请帮我点一个星星✨✨✨✨✨，鼓励分享，十分感谢！！！

若是下面代码复现困难或者有问题，也欢迎评论区留言。

"""《值迭代算法项目》
    时间：2024.12
    作者：不去幼儿园
"""
import numpy as np  # 引入NumPy库，用于数组操作

# 定义状态和动作的集合
states = ['s1', 's2']  # 状态空间，包含两个状态s1和s2
actions = ['a1', 'a2']  # 动作空间，包含两个动作a1和a2

# 定义状态转移概率，P(s'|s, a)
P = {  
    # 从状态s1通过动作a1转移到新状态的概率
    ('s1', 'a1'): [('s1', 0.8), ('s2', 0.2)],
    ('s1', 'a2'): [('s1', 0.5), ('s2', 0.5)],
    # 从状态s2通过动作a1或a2转移到新状态的概率
    ('s2', 'a1'): [('s1', 0.4), ('s2', 0.6)],
    ('s2', 'a2'): [('s1', 0.3), ('s2', 0.7)],
}

# 定义奖励函数R(s, a, s')
rewards = {  
    ('s1', 'a1', 's1'): 5,  # 从s1通过a1转移到s1的奖励
    ('s1', 'a1', 's2'): 10,  # 从s1通过a1转移到s2的奖励
    ('s1', 'a2', 's1'): 0,  # 从s1通过a2转移到s1的奖励
    ('s1', 'a2', 's2'): 15,  # 从s1通过a2转移到s2的奖励
    ('s2', 'a1', 's1'): 10,  # 从s2通过a1转移到s1的奖励
    ('s2', 'a1', 's2'): 5,  # 从s2通过a1转移到s2的奖励
    ('s2', 'a2', 's1'): 5,  # 从s2通过a2转移到s1的奖励
    ('s2', 'a2', 's2'): 10,  # 从s2通过a2转移到s2的奖励
}

# 初始化
gamma = 0.9  # 折扣因子，控制未来奖励的重要性
V = {s: 0 for s in states}  # 初始化值函数，所有状态的值初始为0
threshold = 1e-4  # 设定收敛阈值，判断值函数是否收敛

# 值迭代主循环
while True:
    delta = 0  # 记录值函数的最大变化量，用于判断是否收敛
    for s in states:  # 遍历所有状态
        v = V[s]  # 当前状态的旧值
        # 计算当前状态在所有可能动作下的值，并选择最大的动作值
        V[s] = max(
            sum(p * (rewards.get((s, a, s_next), 0) + gamma * V[s_next])
                for s_next, p in P[(s, a)])  # 使用Bellman方程计算值
            for a in actions  # 遍历所有动作
        )
        delta = max(delta, abs(v - V[s]))  # 更新值函数变化的最大值
    if delta < threshold:  # 当值函数变化小于阈值时，认为收敛，退出循环
        break

# 输出结果
print("Optimal Value Function:")
for s in states:
    print(f"V({s}) = {V[s]:.2f}")  # 格式化输出每个状态的最优值函数

[Notice] 代码逻辑的详细说明

定义状态和动作空间：

states 和 actions 定义了问题的状态和动作集合。

定义状态转移概率和奖励函数：

P 描述了每个状态下通过某一动作转移到其他状态的概率分布。

rewards 描述了从某个状态通过某一动作转移到目标状态时所获得的奖励值。

初始化：

所有状态的值函数初始值设为0。

折扣因子 gamma 控制未来奖励的权重（值越接近1，未来奖励越重要）。

值迭代主循环：

遍历每个状态，计算在当前策略下的最优值。

使用 Bellman 方程更新值函数，直到值函数的变化小于阈值 threshold。

输出结果：

打印最终收敛后的最优值函数 V(s) 。

由于博文主要为了介绍相关算法的原理和应用的方法，缺乏对于实际效果的关注，算法可能在上述环境中的效果不佳或者无法运行，一是算法不适配上述环境，二是算法未调参和优化，三是没有呈现完整的代码，四是等等。上述代码用于了解和学习算法足够了，但若是想直接将上面代码应用于实际项目中，还需要进行修改。

马尔科夫决策过程（MDP）的变种

马尔科夫决策过程（MDP）是一个用来解决带有不确定性和动态性的决策问题的数学模型。除了 部分可观测马尔科夫决策过程（POMDP）之外，还有许多其他类型的 MDP 变体，它们在不同的假设和应用场景下对标准 MDP 做了扩展或修改。以下是几种常见的 MDP 变体的详细介绍：

1. 部分可观测马尔科夫决策过程（POMDP）

定义：Partially Observable Markov Decision Process，POMDP 是 MDP 的一种扩展，允许在每个时刻只有部分观察到系统的状态，而不能完全获取当前的状态。这是通过引入一个“观察”变量来实现的。
特点：
- 部分可观测：相比于标准 MDP，POMDP 假设决策者无法直接观测到环境的完整状态，只能通过某些观察来推断当前状态。
- 信念状态：由于无法直接知道当前的状态，POMDP 使用信念状态（Belief State），即一个概率分布，表示对系统状态的认知。这需要根据历史观察来更新信念状态。
数学模型：一个 POMDP 由五元组 $\langle S, A, O, P, R \rangle$ 组成，其中：
- S是状态空间，表示系统可能的所有状态。
- A 是动作空间，表示决策者可以选择的所有动作。
- O 是观察空间，表示决策者可以观测到的所有可能的观察。
- P(s'|s, a) 是状态转移概率，给定当前状态 s 和动作 a，转移到下一状态 s' 的概率。
- R(s, a) 是即时奖励函数，给定当前状态 s 和动作 a，获得的即时奖励。
由于 POMDP 需要在不完全信息下做决策，问题的求解比标准的 MDP 要复杂得多，通常需要使用方法如 粒子滤波 或 贝叶斯滤波 来近似信念状态。

部分可观测的马尔科夫过程（POMDP）与状态控制问题的联系

POMDP 变体允许在部分可观测的环境下进行决策，而不像 MDP 那样假设状态是完全可观测的。因此，POMDP 更适用于现实世界中的许多问题，如机器人定位、自动驾驶、健康诊断等。

POMDP 主要难点：高计算复杂度：由于信念空间的高维性，解决 POMDP 问题需要更多的计算资源和先进的近似方法。