马尔科夫决策过程
马尔科夫决策过程
贝尔曼方程
贝尔曼方程（Bellman Equation）是动态规划中的一个核心概念，用于解决最优决策问题。贝尔曼方程通过递归的方式，将问题分解为子问题，从而使得最优策略的求解变得可行。贝尔曼方程广泛应用于马尔科夫决策过程（MDP）中，用于计算状态值或行动值。
贝尔曼方程的基本形式
在马尔科夫决策过程中，贝尔曼方程有两种主要形式：状态价值函数形式和行动价值函数形式。
1. 状态价值函数形式
状态价值函数 ( V(s) ) 表示在状态 ( s ) 下，遵循策略 ( \pi ) 所能获得的预期累计奖励。对于一个给定的策略 ( \pi )，贝尔曼方程为：
V π ( s ) = ∑ a ∈ A π ( a ∣ s ) ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a ) + γ V π ( s ′ ) ] V^\pi(s) = \sum_{a \in A} \pi(a \mid s) \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a) + \gamma V^\pi(s') \right] Vπ(s)=a∈A∑π(a∣s)s′∈S∑P(s′∣s,a)[R(s,a)+γVπ(s′)]
其中：
-
π ( a ∣ s ) ：在状态 s 下选择动作 a 的概率 \pi(a \mid s)：在状态 s 下选择动作 a 的概率 π(a∣s)：在状态s下选择动作a的概率
-
P ( s ′ ∣ s , a ) ：在状态 s 下采取动作 a 后转移到状态 s ′ 的概率。 P(s' \mid s, a) ：在状态 s 下采取动作 a 后转移到状态 s' 的概率。 P(s′∣s,a)：在状态s下采取动作a后转移到状态s′的概率。
-
R ( s , a ) ：在状态 s 下采取动作 a 所获得的即时奖励 R(s, a) ：在状态 s 下采取动作 a 所获得的即时奖励 R(s,a)：在状态s下采取动作a所获得的即时奖励
-
γ ：折现因子，用于平衡当前奖励与未来奖励。 \gamma ：折现因子，用于平衡当前奖励与未来奖励。 γ：折现因子，用于平衡当前奖励与未来奖励。
最优状态价值函数 ( V^*(s) ) 是在所有策略中使得状态 ( s ) 下累计奖励最大的价值函数：
V ∗ ( s ) = max a ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a ) + γ V ∗ ( s ′ ) ] V^*(s) = \max_a \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a) + \gamma V^*(s') \right] V∗(s)=amaxs′∈S∑P(s′∣s,a)[R(s,a)+γV∗(s′)]
2. 行动价值函数形式
行动价值函数 ( Q(s, a) ) 表示在状态 ( s ) 下采取动作 ( a ) 后，遵循策略 ( \pi ) 所能获得的预期累计奖励。贝尔曼方程为：
Q π ( s , a ) = ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a ) + γ ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) Q π ( s ′ , a ′ ) ] Q^\pi(s, a) = \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a) + \gamma \sum_{a' \in A} \pi(a' \mid s') Q^\pi(s', a') \right] Qπ(s,a)=s′∈S∑P(s′∣s,a)[R(s,a)+γa′∈A∑π(a′∣s′)Qπ(s′,a′)]
最优行动价值函数 ( Q^*(s, a) ) 是在所有策略中使得在状态 ( s ) 下采取动作 ( a ) 后累计奖励最大的价值函数：
Q ∗ ( s , a ) = ∑ s ′ ∈ S P ( s ′ ∣ s , a ) [ R ( s , a ) + γ max a ′ Q ∗ ( s ′ , a ′ ) ] Q^*(s, a) = \sum_{s' \in S} P(s' \mid s, a) \left[ R(s, a) + \gamma \max_{a'} Q^*(s', a') \right] Q∗(s,a)=s′∈S∑P(s′∣s,a)[R(s,a)+γa′maxQ∗(s′,a′)]
贝尔曼方程的应用
贝尔曼方程在求解最优策略时具有重要作用，特别是在以下方面：
-
价值迭代：
通过反复更新状态价值函数 V ( s ) ，直到收敛到最优值 V ∗ ( s ) ，从而找到最优策略。 通过反复更新状态价值函数 V(s)，直到收敛到最优值 V^*(s) ，从而找到最优策略。 通过反复更新状态价值函数V(s)，直到收敛到最优值V∗(s)，从而找到最优策略。 -
策略迭代：
通过交替进行策略评估（使用贝尔曼方程计算 V π ( s ) ）和策略改进，逐步逼近最优策略 π ∗ 。 通过交替进行策略评估（使用贝尔曼方程计算 V^\pi(s) ）和策略改进，逐步逼近最优策略 \pi^* 。 通过交替进行策略评估（使用贝尔曼方程计算Vπ(s)）和策略改进，逐步逼近最优策略π∗。 -
Q-learning：
强化学习中，通过更新 Q ( s , a ) 的值来逐渐学习最优策略 π ∗ 。 强化学习中，通过更新 Q(s, a) 的值来逐渐学习最优策略 \pi^* 。 强化学习中，通过更新Q(s,a)的值来逐渐学习最优策略π∗。
总结
贝尔曼方程通过递归地定义价值函数，将复杂的决策问题分解为一系列更简单的子问题。这使得在不确定环境中求解最优策略成为可能，是动态规划和强化学习中的关键工具。
马尔科夫决策过程
马尔科夫决策过程（Markov Decision Process, MDP）是马尔科夫过程的一个扩展，主要用于建模在不确定环境中进行决策的过程。MDP广泛应用于强化学习、优化控制等领域，帮助决策者在动态环境中选择最佳策略以最大化长期收益。
马尔科夫决策过程的组成部分
一个典型的马尔科夫决策过程由以下五个元素组成：
-
状态空间（State Space, ( S )）：
- 系统可能处于的所有状态的集合。每个状态代表系统在某一时刻的具体情况。
-
动作空间（Action Space, ( A )）：
- 在每个状态下，决策者可以采取的所有可能行动的集合。
-
**状态转移概率（State Transition Probability, **
P ( s ′ ∣ s , a ) P(s' \mid s, a) P(s′∣s,a)
）：- 系统在采取某一动作 ( a ) 后，从当前状态 ( s ) 转移到下一状态 ( s’ ) 的概率。这个转移概率反映了系统的动态行为。
-
奖励函数（Reward Function, ( R(s, a) )）：
- 奖励函数表示在状态 ( s ) 下执行动作 ( a ) 所得到的即时奖励。奖励可以是正值、负值或零，用于衡量某个行动的短期收益。
-
**策略（Policy, **
π ( a ∣ s ) \pi(a \mid s) π(a∣s)
）：- 策略描述了在每个状态下应该采取哪种行动的规则。策略可以是确定性的（每个状态对应一个唯一的动作）或随机性的（在每个状态下按一定概率选择动作）。
马尔科夫决策过程的目标
MDP 的目标是在不同状态下选择合适的动作，以最大化累计奖励（通常是折现累计奖励），即：
G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + … G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots Gt=Rt+1+γRt+2+γ2Rt+3+…
其中， γ 是折现因子 ( 0 ≤ γ ≤ 1 ），它决定了未来奖励的重要性 其中， \gamma 是折现因子( 0 \leq \gamma \leq 1 ），它决定了未来奖励的重要性 其中，γ是折现因子(0≤γ≤1），它决定了未来奖励的重要性
求解马尔科夫决策过程的方法
求解 MDP 的过程就是寻找最优策略 ，使得在每个状态下累计的期望奖励最大化。常见的求解方法包括：
-
动态规划：
- 利用贝尔曼方程（Bellman Equation）进行递归计算，包括价值迭代（Value Iteration）和策略迭代（Policy Iteration）两种主要方法。
-
蒙特卡罗方法：
- 通过模拟多个轨迹，直接估计每个状态的价值，然后根据这些估计值更新策略。
-
强化学习：
- 在未知环境中，智能体通过与环境的交互学习最优策略，常用的算法有 Q-learning 和 SARSA。
马尔科夫决策过程的应用
MDP 被广泛应用于以下领域：
- 强化学习：用来建模智能体与环境的交互，以学习最优策略。
- 机器人导航：机器人通过选择路径，避免障碍并到达目标。
- 运营管理：在动态环境中优化资源分配和调度。
- 经济决策：建模投资、定价等动态决策问题。
通过马尔科夫决策过程，决策者可以在不确定的环境中制定长期最优策略，以应对复杂的决策问题。