当前位置: 首页 > news >正文

1.2 马尔可夫决策过程(Markov Decision Process, MDP)

定义

强化学习(Reinforcement Learning, RL)方法适用于智能体(agent)以离散时间步与环境交互的问题(@fig-agentenv)。
在时间 \(t\),智能体处于状态 \(s_t\),并决定执行一个动作 \(a_t\)。在下一时刻,它进入新的状态 \(s_{t+1}\),并获得奖励 \(r_{t+1}\)
在一般情况下,状态转移和奖励都是随机的(即执行相同动作后到达不同状态的概率不同)。
智能体的目标是在长期内最大化获得的累计奖励。

rl-agent

这些问题被形式化为马尔可夫决策过程(MDP),定义为六元组:

\[<\mathcal{S}, \mathcal{A}, p_0, \mathcal{P}, \mathcal{R}, \gamma> \]

对于一个有限MDP,有:

  1. 状态空间 \(\mathcal{S} = \{ s_i\}_{i=1}^N\),每个状态满足马尔可夫性质。

  2. 动作空间 \(\mathcal{A} = \{ a_i\}_{i=1}^M\)

  3. 初始状态分布 \(p_0(s_0)\),表示智能体最有可能从哪些状态开始。

  4. 状态转移概率函数

    \[\begin{aligned}\mathcal{P}: \mathcal{S} \times \mathcal{A} \rightarrow & P(\mathcal{S}) \\p(s' | s, a) & = P (s_{t+1} = s' | s_t = s, a_t = a) \end{aligned} \]

  5. 期望奖励函数

    \[\begin{aligned}\mathcal{R}: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow & \Re \\r(s, a, s') &= \mathbb{E} (r_{t+1} | s_t = s, a_t = a, s_{t+1} = s') \end{aligned} \]

  6. 折扣因子 \(\gamma \in [0, 1]\)

在深度强化学习(Deep RL)中,状态空间与动作空间可以是无限的,但我们先讨论有限MDP。

智能体的行为序列称为轨迹(trajectory)回合(episode)

\[\tau = (s_0, a_0, s_1, a_1, \ldots, s_T, a_T) \]

每个转移 \((s_t, a_t, s_{t+1})\) 以概率 \(p(s'|s,a)\) 发生,并产生奖励 \(r(s,a,s')\)
回合型任务中,时间跨度 \(T\) 有限;在持续型任务中,\(T\) 无限。


马尔可夫性质(Markov Property)

智能体的状态应包含做出决策所需的全部信息。
例如,一个机器人导航任务中,状态可能包括所有传感器读数、位置、与其他物体的相对位置等。
在棋类游戏中,棋盘的布局通常足以表示状态。

马尔可夫性质:未来与过去无关,只依赖当前状态。

形式化定义:

\[ p(s_{t+1}|s_t, a_t) = p(s_{t+1}|s_t, a_t, s_{t-1}, a_{t-1}, \dots s_0, a_0) \]

也就是说,只要当前状态定义完整,就不需要整个历史记录。
若问题不满足马尔可夫性质(例如观测部分缺失),RL算法可能不收敛。

这类问题称为部分可观测马尔可夫决策过程(POMDP)
观测 \(o_t\) 来自观测空间 \(\mathcal{O}\),且满足 \(p(o_t | s_t)\)
由于观测不是马尔可夫的,解决POMDP通常需要完整的观测历史 \(h_t = (o_0, a_0, ..., o_t, a_t)\)
这时循环神经网络(RNN)可用于帮助记忆历史。


奖励与回报(Rewards and Returns)

与bandit问题类似,我们关注期望奖励

\[r(s, a, s') = \mathbb{E} (r_{t+1} | s_t = s, a_t = a, s_{t+1} = s') \]

bandit-example

奖励可分为:

  • 稀疏奖励(Sparse rewards):仅在关键事件(如胜利、失败、到达目标)时非零;
  • 密集奖励(Dense rewards):每个时间步都提供奖励(如速度、距离、能耗等)。

稀疏奖励更难学习。

sparse-dense

MDP经历状态序列:

\[s_0 \rightarrow s_1 \rightarrow \ldots \rightarrow s_T \]

并获得奖励序列:

\[r_1 \rightarrow r_2 \rightarrow \ldots \rightarrow r_T \]

rl-sequence

在MDP中,我们希望最大化回报(return)

\[R_t = \sum_{k=0}^\infty \gamma^k \, r_{t+k+1} \]

其中 \(\gamma\)折扣因子(discount factor),表示未来奖励的现值。
\(\gamma\) 越小,智能体越短视;\(\gamma\) 越大,越远见。

decayinggamma

  • 对于回合型任务

    \[R_t = \sum_{k=0}^{T} r_{t+k+1} \]

  • 对于持续型任务

    \[R_t = \sum_{k=0}^{\infty} \gamma^k \, r_{t+k+1} \]


为什么要看长期奖励?

某状态 \(s_1\) 下两个动作:

  • \(a_1\):暂时无奖励,但未来可获 \(10\)
  • \(a_2\):立即获得 \(1\)

\(\gamma\) 大,\(a_1\) 更优;若 \(\gamma\) 小,\(a_2\) 更优。
因此,\(\gamma\) 决定了智能体的行为倾向。


策略(Policy)

智能体在状态 \(s\) 下选择动作 \(a\) 的概率称为策略 \(\pi\)

\[\pi(s, a) = P(a_t = a | s_t = s) \]

策略可以是确定性随机性的,且满足:

\[\sum_{a \in \mathcal{A}(s)} \pi(s, a) = 1 \]

目标是找到最优策略 \(\pi^*\),最大化长期期望回报:

\[\pi^* = \text{argmax}_\pi \, \mathbb{E}_{\tau \sim \rho_\pi} [R(\tau)] \]


价值函数(Value Functions)

强化学习的核心思想之一是:
评估每个状态或动作的好坏程度。

状态价值函数

\[V^{\pi}(s) = \mathbb{E}_{\rho_\pi} \left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t=s \right] \]

动作价值函数(Q函数)

\[Q^{\pi}(s, a) = \mathbb{E}_{\rho_\pi} \left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t=s, a_t=a \right] \]

\(Q\) 值反映在状态 \(s\) 下执行动作 \(a\) 的期望回报。


贝尔曼方程(Bellman Equations)

\(V\)\(Q\) 的关系

\[V^{\pi}(s) = \sum_{a} \pi(s, a) Q^{\pi}(s, a) \]

即:若策略确定,则 \(V\) 等于该动作的 \(Q\) 值;若随机,则是加权平均。

并且有递推关系:

\[R_t = r_{t+1} + \gamma R_{t+1} \]

取期望得:

\[Q^{\pi}(s, a) = \mathbb{E}_{s'}[r(s,a,s') + \gamma V^{\pi}(s')] \]


贝尔曼方程形式

\[V^{\pi}(s) = \sum_{a} \pi(s,a) \sum_{s'} p(s'|s,a)[r(s,a,s') + \gamma V^{\pi}(s')] \]

\[Q^{\pi}(s,a) = \sum_{s'} p(s'|s,a)[r(s,a,s') + \gamma \sum_{a'} \pi(s',a') Q^{\pi}(s',a')] \]

这些递归方程是强化学习的理论基础。


最优贝尔曼方程(Optimal Bellman Equations)

存在最优策略 \(\pi^*\),定义最优状态值与动作值:

\[V^*(s) = \max_\pi V^{\pi}(s), \quad Q^*(s,a) = \max_\pi Q^{\pi}(s,a) \]

此时:

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

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


动态规划(Dynamic Programming, DP)

gpi-scheme

强化学习通常分为两步循环:

  1. 策略评估(Policy Evaluation):计算给定策略的 \(V^\pi\)\(Q^\pi\)
  2. 策略改进(Policy Improvement):基于价值函数更新策略。

这种循环称为广义策略迭代(GPI)
动态规划(DP)是其一种精确实现方式。

矩阵形式解法

设:

\[\mathcal{P}^\pi_{ss'} = \sum_a \pi(s,a)p(s'|s,a), \quad \mathcal{R}^\pi_s = \sum_a \pi(s,a) \sum_{s'} p(s'|s,a)r(s,a,s') \]

则贝尔曼方程写为:

\[\mathbf{V}^\pi = \mathbf{R}^\pi + \gamma \mathcal{P}^\pi \mathbf{V}^\pi \]

解为:

\[\mathbf{V}^\pi = (\mathbb{I} - \gamma \mathcal{P}^\pi)^{-1} \mathbf{R}^\pi \]

但矩阵求逆复杂度高(\(\mathcal{O}(n^{2.37})\)),因此用迭代法近似。


策略迭代(Policy Iteration)

反复执行:

  1. 策略评估(使用贝尔曼方程更新 \(V\));
  2. 策略改进(基于 \(V\) 选择贪婪动作):

\[\pi(s) \leftarrow \text{argmax}_a \sum_{s'} p(s'|s,a)[r(s,a,s') + \gamma V(s')] \]

收敛后得到最优策略。


价值迭代(Value Iteration)

为加速收敛,将策略评估与改进交替进行:

\[V_{k+1}(s) = \max_a \sum_{s'} p(s'|s,a)[r(s,a,s') + \gamma V_k(s')] \]

即直接将贝尔曼最优方程转化为更新规则。
\(V\) 收敛时,即得最优值函数 \(V^*\)


总结

策略迭代与价值迭代均基于贝尔曼方程广义策略迭代(GPI)
求解最优策略需:

  • 了解环境动态 \(p(s'|s,a)\)\(r(s,a,s')\)
  • 足够的计算资源;
  • 满足马尔可夫性质。

时间复杂度约为 \(\mathcal{O}(N^2 M)\)
由于状态空间通常极大(如围棋约有 \(10^{170}\) 种状态),经典动态规划仅适用于小规模问题。

http://www.hskmm.com/?act=detail&tid=26293

相关文章:

  • 博弈论dp复习笔记
  • 10.7阅读笔记
  • 如果你的微信支付界面出现“摇一摇”,说明你的隐私正在泄露
  • 多线程和网络总结
  • 8.RV1126-OPENCV 视频中添加LOGO - 指南
  • 学习记录:响应式系统、文件通知与游戏输入机制的异同
  • oppoR9m刷Linux系统: 制作 scatter.txt 和 导出手机preloader
  • 详细介绍:ASR技术(自动语音识别)深度解析
  • 1.1 采样问题 Sampling and Bandits
  • 10.7 NOIP 模拟赛 T2. 中心极限定理
  • 【题解】10.6 国庆中秋 提高组 热身赛
  • UCB-CS70_离散数学_个人笔记:至少和至多 - Zeeh
  • 几个重要的偏微分方程
  • 虚拟机器人学习自然语言指令技术解析
  • 题解:换乘旅行
  • 2025企业级AI数据防泄漏指南:精准选型与核心指标全景透视
  • 感觉你是那种
  • 鲜花:不会说明你有抑郁症1
  • 【比赛记录】2025CSP-S模拟赛59
  • 使用 C 语言实现英文数字验证码识别系统
  • APlayer的配置方法和相关资料整理(已完成)
  • 详细介绍:目标检测任务的评估指标mAP50和mAP50-95
  • 一些有一定趣味性的杂题
  • 用 Haskell 实现英文数字验证码识别
  • 深入解析:Day43 Python打卡训练营
  • 用 Perl 实现验证码图像识别
  • 实用指南:【结构型模式】代理模式
  • cnblog Test
  • 云数据仓库十年架构演进与技术突破
  • 20251007 模拟测 总结