CS5446 3. Bellman optimal equation
·
Gnosnay
Notes for CS5446 Reinforcement Learning.
什么是 optimal policy
如何比较两个策略哪个更好？我们使用 state value 来比较。
$$ v_{\pi_1}(s) \geq v_{\pi_2}(s), \forall s \in \mathcal{S} $$如果一个策略的 state value 大于另一个策略的 state value，那么这个策略就比另一个策略好。
optimal policy ($\pi^*$ ) 就是使得 state value 最大的 policy。
Bellman optimal equation
$$ v(s) = \blue{\max_{\pi}} \sum_{a \in \mathcal{A}(s)} \blue{ \pi(a|s) } \Big( \sum_{r} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) v_\pi(s') \Big) $$它相对于 bellman equation 的区别在于，多了一个找到 $\max_{\pi}$ 的步骤。因此我们需要找到一个算法来求解这个 $\pi$ .
这里我们有一系列的问题：
- 这个 $v(s)$ 有解吗？这里的解是指是否能找到一个策略 $\pi^*$ 使得 $v(s)$ 最大
- 这个解是否唯一？
- 怎么进行求解？
- 这个最优公式的意义是什么？
证明
对于前三个问题，我们都可以用 Contraction mapping theorem 来进行回答。
$$ v(s) = \blue{\max_{\pi}} \sum_{a \in \mathcal{A}(s)} \blue{ \pi(a|s) } \Big( \sum_{r} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) v_\pi(s') \Big) $$我们假设这个最佳策略($\pi^*$ )存在，那么这个式子中的蓝色的部分就是确定性的。这个策略我们可以这么描述：
$$ \pi^{*}(a|s) = \begin{cases} 1 & \text{if } a = a^{*}, \\ 0 & \text{otherwise} \end{cases} $$其中 $a^*$ 是使得 $q(s,a)$ 最大的 action。也就是最优动作（$a^* = \arg \max_{a} q(s,a)$ ）。
一定策略确定，那么贝尔曼最优公式可以写成：
$$ \begin{aligned} v_{*}(s) &= \blue{\max_{\pi}} \sum_{a \in \mathcal{A}(s)} \blue{ \pi(a|s) } \Big( \sum_{r} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) v_\pi(s') \Big) \\ &= \blue{\max_{a}} \Big( \sum_{r} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) \blue{v_{*}(s')} \Big) \end{aligned} $$这一步可能比较跳跃。不求甚解可以记住结论。
这是一个递归定义，这个式子可以写成一个函数 $f(v)$ 的形式：
$$ f(v)(s) = \max_{a} \Big( \sum_{r} p(r|s,a)r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s,a) v(s') \Big) $$这里的思路是我们固定 v 的值，然后来求解 pi 所以可以做这步的简化。
简化后的式子是一个 contraction mapping。那么我们可以得出以下结论：
- $\pi^{*}$ 是一定存在的（Contraction mapping theorem）
- $\pi^{*}$ 不一定唯一，但是 $v^{*}$ 是唯一的
- $\pi^{*}$ 是 deterministic 的
- $\pi^{*}$ 的求解可以通过迭代法来求解, 因为这是一个 contraction mapping。
分析
$$ \blue{v(s)} = \max_{\pi} \sum_{a \in \mathcal{A}(s)} \blue{ \pi(a|s) } \Big( \sum_{r} \red{ p(r|s,a)r} + \red{\gamma} \sum_{s' \in \mathcal{S}} \red{ p(s'|s,a)} \blue{v(s') } \Big) $$这个式子中红色的部分是已知量（dynamic model），蓝色的部分是未知量（state value）。求解这个式子就是求解式子中的蓝色部分。
一般来说我们能控制的部分就是 $r$ 和 $\gamma$ 。这里有一些性质即：
- $\gamma \in [0,1]$ 表示未来的奖励对当前奖励的折扣, 越大越重视未来的奖励
- $r$ 是奖励函数，我们也可以通过控制奖励函数来改变行为
- 贝尔曼最优公式中重要的是相对奖励。比如如果我们对奖励函数进行线性变化，那么最优策略是不会变的。
- 由于 $\gamma$ 的存在，远期奖励会打折扣，那么近期的无意义的行为会影响最终的奖励。因此在优化过程中近期无意义的行为会被逐渐淘汰。