机器算法验证 - 为什么马尔可夫决策过程（MDP）中的最优策略独立于初始状态？ - 吾爱随笔录

为什么马尔可夫决策过程（MDP）中的最优策略独立于初始状态？

机器算法验证机器学习强化学习

2022-04-19 04:07:21

我正在关注 CS229 上的强化学习讲义（可以参考我在这个问题中使用的符号）：

http://cs229.stanford.edu/notes/cs229-notes12.pdf

我对以下段落有疑问：

在此处输入图像描述

我的具体问题是，为什么具有对所有州都是最优策略的属性？我猜他没有在笔记上证明这一点，因为这对他来说很明显，但为什么这是真的？在某处有证据吗？或者有人至少知道一些直观的论据吗？ $\pi^*$

我只是很惊讶，因为它看起来很反直觉，特别是因为第 4 页上定义了最优值函数的方式。

它定义：

最优值函数：

V^{*} (s) = \underset{π}{m a x} V^{π} (s)

$V^*(s) = \underset{\pi}{max} \ V^{\pi}(s)$

我理解它的方式是，它是可以通过使用任何策略获得的折扣奖励的最佳预期总和。然而，它似乎是 s 的函数，并且对于每个 s，我们在上最大化。那么，为什么我们不会为每个状态 $\pi$ $\pi$

有关与我的问题相关的更多符号，请阅读以下内容（或阅读第 4 页，或从我链接的注释的第 4 页到第 1 页）：

回想一下价值函数是什么：

V^{π} (s) = E [R (s_{0}) + γ R (s_{1}) + γ^{2} R (s_{2}) + \dots ∣ s_{0} = s; π]

$V^{\pi}(s) = E[R(s_0) +\gamma R(s_1) + \gamma^2R(s_2) + \cdots \mid s_0 = s ; \pi]$

这是从状态 s 开始并根据给定的策略采取行动时的预期折扣奖励总和（注意不是 rv，而是将状态映射到行动的“固定”参数）。 $\pi$ $\pi$

在 CS229 注释的第 4 页上，它定义了以下数量：

因此，我们可以用这个“最佳”值函数重写贝尔曼方程：

V^{*} (s) = R (s) + \underset{a \in A}{m a x} γ \sum_{s^{'} \in S} P_{s a} (s^{'}) V^{*} (s^{'})

$V^*(s) = R(s) + \underset{a \in A}{max} \ \gamma\sum_{s' \in S} P_{sa}(s')V^*(s')$

这表示状态 s 的最佳价值函数是初始奖励加上最大化我们加权未来收益的行动的奖励。即加上现在做最好的事情的回报，这将使我们在未来得到最好的回报。

从中我们看到，我们可以通过根据上面的等式“提取”每个状态的最佳动作来获得最佳策略：

π^{*} (s) = \underset{a \in A}{a r g m a x} \sum_{s^{'} \in S} P_{s a} (s^{'}) V^{*} (s^{'})

$\pi^*(s) = \underset{a \in A}{argmax}\sum_{s' \in S} P_{sa}(s')V^*(s')$

它指出，对于我们拥有的任何状态和每个政策： $\pi$

V^{*} (s) = V^{π^{*}} (s) \geq V^{π} (s)

$V^*(s) = V^{\pi^*}(s) \geq V^{\pi}(s)$

4个回答

说最优策略独立于初始状态的论点背后的直觉如下：

最优策略由一个函数定义，该函数为每个可能的状态选择一个动作，并且不同状态下的动作是独立的。

正式地说，对于未知的初始分布，最大化的价值函数如下（不以初始状态为条件）

$v^\pi = E[ R(s_0,a_0) + \gamma R(s_1,a_1) + ... | \pi ]$

因此，最优策略是最大化的策略，其中是定义为的向量，V^\pi 是具有V的定义与您的定义相同。因此最优策略是以下优化的解决方案 $v^\pi=x_0^T V^\pi$ $x_0$ $x_0(s)=Prob[s_0=s]$ $V^\pi$ $V^\pi (s)$ $\pi ^*$

$\max_{\pi} x_0^T V^\pi = \max_{\pi} \sum _{s} x_0(s)V^\pi (s)= \sum _{s} x_0(s) \max_{a\in A_s}V^\pi (s)= \sum _{s} x_0(s)V^* (s)$

其中是状态处可用的操作集。请注意，第三个等式仅有效，因为并且我们可以通过选择不同状态下的独立动作来分离决策策略。换句话说，如果例如在上存在约束（例如，如果优化只在保证的策略中搜索），那么该参数不再有效并且最优策略是初始分布。 $A_s$ $s$ $x_0(s)\geq 0$ $x_t$ $x_t \leq d$ $t>0$

有关更多详细信息，您可以查看以下 arXiv报告：“Finite-Horizon Markov Decision Processes with State Constraints”，作者 Mahmoud El Chamie，Behcet Acikmese

为什么具有对所有状态都是最优策略的性质？ $π^∗$

这实际上是由于环境的马尔可夫属性。马尔可夫属性指出，导致状态的先前状态和动作的历史不会影响和。所以在任何状态下，该状态的最优策略只能考虑而不考虑它是如何达到的。 $s$ $R(s)$ $P_{sa}(s')$ s $\forall a: R(s, a), P_{sa}(s')$ s

我已经有一段时间没有深入研究细节了，但如果你举个实际例子，对我来说对所有状态都有效，这似乎非常直观。 $π^∗$

解决迷宫的情况是其中之一：代理（可能随机定位）在迷宫中，并试图摆脱它。只有当它找到出口（第一张图片）时，它才会得到奖励。通过奖励的经验和传播，它将学习从任何位置选择什么路径（第二张图像）。所以最优策略确实为任何位置（状态）提供了最佳方向（动作）选择。

当然，仍然需要通过数学进行更彻底的解释；-)

学习了奖励的一条已解决路径迷宫解决了

在我看来，任何达到最优值的策略都是最优策略。由于给定 MDP 的最优值函数是唯一的，这个最优值函数实际上定义了策略空间上的一个等价类，即那些值最优的那些实际上是等价的。换句话说，尽管最优策略可能彼此不同（对于给定的状态，它们可能采取不同的动作序列来实现相同的最优值），但它们的价值函数是相同的。从这个意义上说，无论你在哪个状态，由于这个状态的最优值是一样的，所以达到这个最优值的策略本质上是一样的，都是这个状态下的最优策略。

其它你可能感兴趣的问题

上一篇关于gam的一些问题下一篇如何计算 Precision & Recall 的置信区间（来自信号检测矩阵）？