马尔科夫决策过程

马尔科夫决策过程

贝尔曼方程

贝尔曼方程（Bellman Equation）是动态规划中的一个核心概念，用于解决最优决策问题。贝尔曼方程通过递归的方式，将问题分解为子问题，从而使得最优策略的求解变得可行。贝尔曼方程广泛应用于马尔科夫决策过程（MDP）中，用于计算状态值或行动值。

贝尔曼方程的基本形式

在马尔科夫决策过程中，贝尔曼方程有两种主要形式：状态价值函数形式和行动价值函数形式。

1. 状态价值函数形式

状态价值函数 ( V(s) ) 表示在状态 ( s ) 下，遵循策略 ( \pi ) 所能获得的预期累计奖励。对于一个给定的策略 ( \pi )，贝尔曼方程为：
$$V^{\pi }(s)=\sum _{a\in A}\pi (a\mid s)\sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)\left[R(s,a)+\gamma V^{\pi }(s^{\prime })\right]$$
其中：

• $$\pi (a\mid s)：在状态s下选择动作a的概率$$

• $$P(s^{\prime }\mid s,a)：在状态s下采取动作a后转移到状态s^{\prime }的概率。$$

• $$R(s,a)：在状态s下采取动作a所获得的即时奖励$$

• $$\gamma ：折现因子，用于平衡当前奖励与未来奖励。$$

最优状态价值函数 ( V^*(s) ) 是在所有策略中使得状态 ( s ) 下累计奖励最大的价值函数：

$$V^{\ast }(s)=\underset{a}{\max }\sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)\left[R(s,a)+\gamma V^{\ast }(s^{\prime })\right]$$

2. 行动价值函数形式

行动价值函数 ( Q(s, a) ) 表示在状态 ( s ) 下采取动作 ( a ) 后，遵循策略 ( \pi ) 所能获得的预期累计奖励。贝尔曼方程为：

$$Q^{\pi }(s,a)=\sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)\left[R(s,a)+\gamma \sum _{a^{\prime }\in A}\pi (a^{\prime }\mid s^{\prime })Q^{\pi }(s^{\prime },a^{\prime })\right]$$
最优行动价值函数 ( Q^*(s, a) ) 是在所有策略中使得在状态 ( s ) 下采取动作 ( a ) 后累计奖励最大的价值函数：

$$Q^{\ast }(s,a)=\sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)\left[R(s,a)+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })\right]$$

贝尔曼方程的应用

贝尔曼方程在求解最优策略时具有重要作用，特别是在以下方面：

1. 价值迭代：
   $$通过反复更新状态价值函数V(s)，直到收敛到最优值V^{\ast }(s)，从而找到最优策略。$$

2. 策略迭代：
   $$通过交替进行策略评估（使用贝尔曼方程计算V^{\pi }(s)）和策略改进，逐步逼近最优策略{\pi }^{\ast }。$$

3. Q-learning：
   $$强化学习中，通过更新Q(s,a)的值来逐渐学习最优策略{\pi }^{\ast }。$$

总结

贝尔曼方程通过递归地定义价值函数，将复杂的决策问题分解为一系列更简单的子问题。这使得在不确定环境中求解最优策略成为可能，是动态规划和强化学习中的关键工具。

马尔科夫决策过程

马尔科夫决策过程（Markov Decision Process, MDP）是马尔科夫过程的一个扩展，主要用于建模在不确定环境中进行决策的过程。MDP广泛应用于强化学习、优化控制等领域，帮助决策者在动态环境中选择最佳策略以最大化长期收益。

马尔科夫决策过程的组成部分

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

1. 状态空间（State Space, ( S )）：

   • 系统可能处于的所有状态的集合。每个状态代表系统在某一时刻的具体情况。

2. 动作空间（Action Space, ( A )）：

   • 在每个状态下，决策者可以采取的所有可能行动的集合。

3. **状态转移概率（State Transition Probability, **
   $$P(s^{\prime }\mid s,a)$$
   ）：

   • 系统在采取某一动作 ( a ) 后，从当前状态 ( s ) 转移到下一状态 ( s’ ) 的概率。这个转移概率反映了系统的动态行为。

4. 奖励函数（Reward Function, ( R(s, a) )）：

   • 奖励函数表示在状态 ( s ) 下执行动作 ( a ) 所得到的即时奖励。奖励可以是正值、负值或零，用于衡量某个行动的短期收益。

5. **策略（Policy, **
   $$\pi (a\mid s)$$
   ）：

   • 策略描述了在每个状态下应该采取哪种行动的规则。策略可以是确定性的（每个状态对应一个唯一的动作）或随机性的（在每个状态下按一定概率选择动作）。

马尔科夫决策过程的目标

MDP 的目标是在不同状态下选择合适的动作，以最大化累计奖励（通常是折现累计奖励），即：

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots$$

$$其中，\gamma 是折现因子(0\le \gamma \le 1），它决定了未来奖励的重要性$$

求解马尔科夫决策过程的方法

求解 MDP 的过程就是寻找最优策略 ，使得在每个状态下累计的期望奖励最大化。常见的求解方法包括：

1. 动态规划：

   • 利用贝尔曼方程（Bellman Equation）进行递归计算，包括价值迭代（Value Iteration）和策略迭代（Policy Iteration）两种主要方法。

2. 蒙特卡罗方法：

   • 通过模拟多个轨迹，直接估计每个状态的价值，然后根据这些估计值更新策略。

3. 强化学习：

   • 在未知环境中，智能体通过与环境的交互学习最优策略，常用的算法有 Q-learning 和 SARSA。

马尔科夫决策过程的应用

MDP 被广泛应用于以下领域：

• 强化学习：用来建模智能体与环境的交互，以学习最优策略。
• 机器人导航：机器人通过选择路径，避免障碍并到达目标。
• 运营管理：在动态环境中优化资源分配和调度。
• 经济决策：建模投资、定价等动态决策问题。

通过马尔科夫决策过程，决策者可以在不确定的环境中制定长期最优策略，以应对复杂的决策问题。