RL的原理-3-贝尔曼最优公式

1.贝尔曼最优公式#

  贝尔曼最优公式（Bellman Optimality Equations）描述了在最优策略下，状态值函数和动作值函数之间的关系。

  对于状态值函数$v_{*}(s)$，贝尔曼最优公式表示为：

$$v_{*}(s) =\max_{\pi} \sum_{a} \pi(a|s) \sum_{r} p(r | s, a)r+ \gamma \sum_{s'} p(s' | s, a) v_{*}(s'), \forall s \in S$$ $$=max_{pi} \sum_{a} \pi(a|s) q_{*}(s, a), \forall s \in S$$

  其向量形式为：

$$\mathbf{v_{*}} = \max_{\pi} \left( \mathbf{R^{\pi}} + \gamma \mathbf{P^{\pi}} \mathbf{v_{*}} \right)$$

2. 不动点与Contraction Mapping theorem#

2.1 不动点#

  在数学中，不动点（fixed point）是指在某个映射下保持不变的点。具体来说，给定一个映射$f: X \to X$，如果存在一个点$x^* \in X$，使得$f(x^*) = x^*$，那么$x^*$就是$f$的不动点。

  简单表示就是$f(x)=x$的解。

2.2 收缩映射#

  收缩映射（contraction mapping）是指在一个度量空间中，将任意两个点之间的距离缩小的映射。具体来说，给定一个度量空间$(X, d)$，如果存在一个常数$0 \leq k < 1$，使得对于任意的$x, y \in X$，都有$d(f(x), f(y)) \leq k \cdot d(x, y)$，那么$f$就是一个收缩映射。

  可以举个例子，比如函数$f(x) = \frac{1}{2}x$在实数集上是一个收缩映射，因为对于任意的$x, y \in \mathbb{R}$，都有：

$$|f(x) - f(y)| = \left|\frac{1}{2}x - \frac{1}{2}y\right| = \frac{1}{2}|x - y|$$

2.3 Contraction Mapping Theorem#

  收缩映射定理（Contraction Mapping Theorem）指出，在一个完备度量空间中，任何收缩映射都有且只有一个不动点。换句话说，如果$f: X \to X$是一个收缩映射，那么存在唯一的$x^* \in X$，使得$f(x^*) = x^*$。

3.贝尔曼最优公式求解#

  由于贝尔曼最优公式是一个收缩映射，根据收缩映射定理，我们可以保证通过反复应用贝尔曼最优公式，最终会收敛到唯一的最优状态值函数$v_{*}(s)$。

迭代算法

  具体来说，我们可以从一个初始的状态值函数$v_0(s)$开始，反复应用贝尔曼最优公式，得到一系列的状态值函数$v_1(s), v_2(s), ...$。随着迭代次数的增加，这些状态值函数将逐渐逼近最优状态值函数$v_{*}(s)$。

$$v_{k+1}(s) = f(v_k(s)) = \max_{\pi} \left( \mathbf{R^{\pi}} + \gamma \mathbf{P^{\pi}} \mathbf{v_k} \right)$$

4.一些性质#

  在公式中什么是已知的呢？

• Reward : $r$
• System model : $p(s' | s, a),p(r|s,a)$
• Discount factor : $\gamma$

  我们得到的最优策略与设置的reward、discount factor（即公式中的$\gamma$）等有关。

  当$\gamma \to 1$时，智能体更加关注长期奖励；当$\gamma \to 0$时，智能体更加关注短期奖励。而且$\gamma$也会使得智能体选择最短路径。