[TOC]
https://www.bilibili.com/video/BV1sd4y167NS
笔记丢失了一次
这是补档版本，稍微粗略一点……心态小炸
Optimal Policy
当一个策略，在任意状态都比另一个策略的state value更好（或者相等）
我们就认为这个策略优于另一个策略
当一个策略比所有策略都好，它就是最优策略
Bellman Optimality Equation
$$ \begin{split} v(s) &= {\color{red}\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} \\ &= {\color{red}\max_\pi} \sum_a \pi(a|s) q(s,a), \quad \forall s\in \mathcal{S} \end{split} $$相比于贝尔曼公式，BOE实质上就是多了一个优化问题
- 已知：$p(r|s,a),p(s’|s,a)$
- 未知：$v(s),v(s’)$，需要我们针对不同的$\pi$去计算
- 求解：$\pi$
自然有向量形式：
$$ v = \max_\pi (r_\pi + \gamma P_\pi v) $$Maximization
我们先考虑固定$v$，看看能不能求解$\pi$
$$ v = \max_\pi\sum_a \pi(a|s)q(s,a) $$其中$q(s,a)$自然也是一个已知的量（所有的$v$都可以知道，自然可以算出$q$）
同时有：
$$ \sum_a \pi(a|s) = 1 $$那么本质上$\sum_a \pi(a|s)q(s,a)$是对action value做加权平均
为了最大化这一项，我们肯定需要给最大的$q$最多的权值，也就是1
可以得到策略：选择action最大的行动$a^*$
$$ \pi(a|s) = \begin{cases} 1 & \text{ if } a= a^*\\ 0 & \text{ if } a\neq a^* \end{cases} $$这样我们就能得到原式：
$$ v = \max_\pi\sum_a \pi(a|s)q(s,a) = \max_{a\in \mathcal{A}(s)}q(s,a) \\ \text{where }a^* = \arg \max_a q(s,a) $$只要我们固定$v$，我们肯定就能得到最优策略，自然计算出右边的值
因此右边的值可以直接表示成一个只关于$v$的函数：$v=f(v)$
表达成向量形式：
$$ f(v):=\max_\pi (r_\pi+\gamma P_\pi v) $$搜索一下不动点定理或叫Contraction mapping theorem
基于这个定理，可以证明$f(v)$是符合这个定理的条件的
大概就是：
- 函数具有压缩性：有$\left|v_1-v_2\right | \leq \gamma\left|f(v_1)-f(v_2)\right |$
也就是满足这个条件，就会有
- 必然存在唯一的一个不动点$f(v) =v$
因此，我们可以不断套用$v,f(v),f(f(v)),…$
最后会收敛得到不动点，具体证明略过
实际上的操作就是：
$$ v_{k+1}=f(v_k) =\max_\pi (r_\pi+\gamma P_\pi v_k) $$那么如何证明最后收敛到的结果$v^*$就是最优解呢？
固定$v=v^$，自然可以得到当前的策略$\pi^$
$$ \pi^* = \arg \max_\pi (r_\pi+\gamma P_\pi v^*) $$将$\pi^*$代入：
$$ v^* = \max_\pi (r_\pi+\gamma P_\pi v_*) = r_{\pi^*}+\gamma P_{\pi^*} v^* $$你会发现变成state value的公式了
也就是说$v^$，就是策略$\pi^$的state value
我们考虑策略替换成任意其他的策略$\pi$时：
$$ v^* = r_{\pi^*}+\gamma P_{\pi^*} v^* \geq r_\pi + \gamma P_\pi v^* $$令该策略对应state value的贝尔曼公式：
$$ v = r_{\pi}+\gamma P_{\pi} v $$做一个减法则有：
$$ v^*-v \geq (r_\pi + \gamma P_\pi v^*)-(r_{\pi}+\gamma P_{\pi} v) = \gamma P_\pi(v^*-v) $$令$\Delta = v^*-v$，则有：
$$ \Delta \geq \gamma P_\pi\Delta $$我们只需要把右边的$\Delta$不停代换为$\gamma P_\pi\Delta$：
$$ \Delta \geq \gamma P_\pi\Delta \geq \gamma^2 P_\pi^2\Delta \geq ... \geq \gamma^n P_\pi^n\Delta \geq 0 $$故对于策略$\pi^*$，其state value始终是最大的
因此是最优策略
Analysis
- Change $r\to ar+b$会发生什么？
- 什么都不会发生
- 可以证明 $v’ = av^*+\frac{b}{1-\gamma}I$，所有state value的相对大小没有发生变化
- 自然action value不会有其他选择，policy不改变
- 如何鼓励走最短路径？
- 其实不用一直给agent做-1（损失能量），催促agent
- $\gamma$本身就在催促agent尽快到终点，否则终点的贡献变少了