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

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

马尔科夫决策过程（MDP）是数学上描述决策问题的一种模型。它被广泛应用于强化学习、运筹学、控制系统和经济学等领域。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，累积奖励可以分为两部分：

1. 当前即时奖励

R_t

。

1. 从下一状态

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 问题需要更多的计算资源和先进的近似方法。

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

• 定义：分布式马尔科夫决策过程（Dec-POMDP）是 POMDP 的一个扩展，处理多个智能体（Agent）同时决策的问题，每个智能体都只有部分可观测的信息。每个智能体的决策不仅会影响自身的奖励，也会影响到其他智能体的状态和奖励。
• 特点：
  • 多智能体环境：多个智能体在同一环境中协作或竞争，每个智能体的决策都依赖于当前的状态和自己的观测。
  • 部分可观测：每个智能体只能获得部分的环境信息，通常不具备完全的全局视角。
• 数学模型：
  • 和 POMDP 相似，但增加了多个智能体，并且每个智能体都有自己的状态、动作和奖励函数。
  • 每个智能体的信念状态更新不仅依赖于自己的动作，还要考虑其他智能体的动作。
• 应用：
  • 适用于多机器人系统、多人游戏、自动驾驶汽车的协同控制等场景。
• 计算难度：
  • Dec-POMDP 比 POMDP 更复杂，因为它涉及多个智能体的协同决策问题。求解一般采用 集中式优化 或 分布式优化。

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

• 定义：分层马尔科夫决策过程（HMDP）是 MDP 的一个扩展，旨在处理具有层级结构的决策问题。它通过将复杂的决策过程分解为更简单的子问题（子任务）来简化决策过程。
• 特点：
  • 任务分解：HMDP 将问题分解成多个层次，每个层次的决策过程都依赖于上一层的结果。高层次的决策负责选择子任务，而低层次的决策负责完成具体任务。
  • 层次化模型：通过引入子任务和状态机的概念，简化了复杂任务的决策过程。
• 数学模型： HMDP 通过引入一个额外的控制层（父层次），高层次的动作选择将决定低层次决策的执行。这种层次化结构使得高层次的智能体可以专注于战略性决策，而低层次的智能体可以专注于执行具体任务。
• 应用：
  • 适用于分层的自动控制系统、机器人系统中的任务规划、复杂游戏中的多阶段决策等。

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

• 定义：在标准的 MDP 中，假设未来的状态仅依赖于当前状态和动作（即满足马尔科夫性质），而非马尔科夫决策过程则没有这种假设，未来的状态不仅依赖于当前状态，还可能依赖于过去的历史状态。
• 特点：
  • 非马尔科夫性质：该变体允许状态转移的概率不再只依赖于当前状态和动作，而是依赖于更长的历史信息（例如过去的状态序列）。
• 应用：
  • 适用于需要考虑历史依赖关系的问题，如某些复杂的经济模型、长期规划问题等。

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

• 定义：在标准的 MDP 中，时间通常是离散的，而在连续时间马尔科夫决策过程（CTMDP）中，时间是连续的，系统状态随着时间的推移而变化。
• 特点：
  • 连续时间：状态变化不再是按离散时间步发生的，而是连续的，这使得模型更加贴近实际的物理系统。
  • 事件触发：通常，状态的变化是由某些事件触发的，而不仅仅是时间步的推进。
• 数学模型：
  • CTMDP 引入了 速率矩阵 和 泊松过程 等概念来描述状态转移的时间依赖性。
• 应用：
  • 适用于需要建模事件驱动型系统、通信网络中的队列系统、工程中的设备维护策略等。

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

• 定义：随机控制过程是一个广义的 MDP 变体，其中系统动态不仅受到决策者的动作影响，还受到外部随机过程（例如环境噪声或外部扰动）的影响。
• 特点：
  • 外部随机扰动：与标准 MDP 不同，随机控制过程假设有额外的环境噪声或外部因素影响系统的状态转移。
• 应用：
  • 适用于金融市场、供应链管理等系统中，其中环境的不确定性和外部因素对决策过程有显著影响。

7.总结

马尔科夫决策过程（MDP）有许多变体，用于解决不同类型的决策问题。除了标准的 MDP 和部分可观测的 POMDP 之外，还有多智能体系统（Dec-POMDP）、分层决策（HMDP）、非马尔科夫系统（NMDP）、连续时间模型（CTMDP）等变体。每种变体都针对不同的应用场景或假设条件进行了优化，以应对更复杂、更不确定的决策问题。

更多强化学习文章，请前往：【强化学习（RL）】专栏