bellman optimality equation (BOE)
上一章[[贝尔曼公式]]

Optimal policy

即找到一个policy在任意state都比其他的policy更好。下面是一些问题：

1. 存在性
2. 唯一性
3. 确定性
4. 如何得到
   通过研究bellman optimality equation

BOE定义

贝尔曼最优公式：$$v(s)=\underset{\pi }{\max }\sum _a\pi (a|s)q(s,a),s\in S$$在其中需要先找到最优的policy。
矩阵向量形式就是加上最优的bellman公式的矩阵向量形式$$v=\underset{\pi }{\max }(r_{\pi }+\gamma P_{\pi }v)$$

分析

定义上述公式认为是$v$的一个公式$f(v)$，即可得到$v=f(v)$，其中$[f(v){]}_s={\max }_{\pi }{\sum }_a\pi (a|s)q(s,a),s\in S$.
其中$f(v)$满足下面的收缩映射定理

Contraction mapping theorem

1. Fixed point不动点：对于$x\in X$是$f:X\to X$不动点，要求$f(x)=x$。
   直观理解就是存在一个点经过f映射仍是他自己。
2. Contraction mapping （or contraction function）:如果f是一个收缩映射，那么$$\Vert f(x_1)-f(x_2)\Vert \le \gamma \Vert x_1-x_2\Vert ,其中\gamma \in (0,1)$$直观理解就是收缩。
3. Contraction mapping theorem收缩映射定理：
   对于任意有$x=f(x)$形式的公式，如果$f$是一个收缩映射，则有
   • 存在性：必然存在一个不动点$x^{\ast }$满足$f(x^{\ast })=x^{\ast }$.
   • 唯一性：不动点$x^{\ast }$是唯一的。
   • 求解：迭代求解，对于$x_{k+1}=f(x_k)$，当$k\to \infty$时，$x_k\to x^{\ast }$。
   • 推导没有

求解

直接使用上述constraction mapping theorem进行迭代求解

最优性

没讲证明，单纯陈述了了一个求解Bellman optimality equation得到的$v^{\ast }$对应的策略是${\pi }^{\ast }$。
其中$v^{\ast }\ge v_{\pi },\forall \pi$.
而最优策略Greedy Optimal Policy：$\forall s\in S$，the deterministic greedy 的policy是$${\pi }^{\ast }(a|s)=\{\begin{array}{ll}1& \text{if }a=a^{\ast }(s)\\ 0& \text{if }a\ne a^{\ast }(s)\end{array}$$

利用最优性策略

影响最优策略的因素是什么？$$v(s)=\underset{\pi }{\max }\sum _a\pi (a|s)\left(\sum _{r}p(r\mid s,a)\cdot r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)\cdot v(s^{\prime })\right)$$
由上述贝尔曼最优公式可以看出，影响因素包括：

• 回报设计：r 很直观的影响
• 系统模型：$p(r\mid s,a)$，$p(s^{\prime }\mid s,a)$
• discount rate：$\gamma$， 模型的远见（越大，接近1），短视（越小，接近0）
• 其他参数是未知数，待求

Optimal Policy Invariance
直观说就是对所有的回报r进行仿射变换affine transformation后最终获得的最优策略是相同的。

下一章[[值迭代&策略迭代]]