1 minute read

Bellman Optimal Equation

Optimal policy

定义：如果$v_{\pi^} (s) \geq v_{\pi}(s), \forall s \in \mathcal{S}$ ，那么称 $\pi^$为最优策略

Bellman optimality equation

\[\begin{aligned} v(s) &= \max_\pi \sum_a \pi (a|s) \left( \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v(s')\right ), \quad \forall s \in \mathcal{S} \\ &= \max_\pi \sum_a \pi (a|s) q(s,a) \end{aligned}\]

在Bellman公式中，$\pi$ 是给定的，而在最优公式中不是。

其中：

  • $p(r s,a)$和$p(s’ s,a)$是给定的
  • $v(s)$和$v(s’)$是未知的并且是所要求解的

类似Bellman公式，可以得到Bellman最优公式的矩阵向量形式： \(v = \max_\pi (r_\pi + \gamma P_\pi v)\)

求解一般式

对于式子： \(\begin{aligned} v(s) &= \max_\pi \sum_a \pi (a|s) \left( \sum_r p(r|s,a)r + \gamma \sum_{s'} p(s'|s,a)v(s')\right ), \quad \forall s \in \mathcal{S} \\ &= \max_\pi \sum_a \pi (a|s) q(s,a) \end{aligned}\) 因为$\sum_a \pu(a|s) = 1$，所以有 \(\max_\pi \sum_a \pi(a|s) q(s,a) = \max_{a \in \mathcal{A}(a)} q(s,a)\)

即$v(s)$ 为$q(s,a)$的最大值，其中，策略的权重如下（$a^*$就是最优策略对应的action）： \(\pi(a | s) = \begin{cases} 1 & a = a^* \\ 0 & a \ne a^* \end{cases}\)

求解矩阵向量式

令 \(f(v) := \max_\pi (r_\pi + \gamma P_\pi v)\) 那么Bellman最优公式就变成了 \(v = f(v)\) 其中$f(v)$是一个向量， \([f(v)]_s = \max_\pi \sum_a \pi(a|s)q(s,a), \quad s \in \mathcal{S}\)

解的存在性：用到压缩映射原理（省略）

$f(v)$ 是一个压缩映射，满足 \(|| f(v_1) - f(v_2) || \leq \gamma || v_1 - v_2||\) 因此Bellman公式存在唯一解 $v^*$

解的最优性

若$v_$是$v = \max_\pi (r_\pi + \gamma P_\pi v)$的唯一解，且对于任意的 $v_\pi$ 满足式子$v_\pi = r_\pi + \gamma P_\pi v_\pi$，都有$v^ \geq v_\pi, \forall \pi$

最优的策略$\pi^*$如下： \(\pi^*(a|s) = \begin{cases} 1 & a = a^*(s) \\ 0 & a \neq a^*(s) \end{cases}\)

You May Also Enjoy