RL-赵-(四)-基于模型01：值迭代算法（其中的值不是State Value，通过一步求出）【v₀(随机初始化)➞策略更新/PU➞π₁➞值更新/PE➞v₁➞PU➞π₂➞...】

一、值迭代算法（Value iteration algorithm）

如下，如何求解贝尔曼最优公式（Bellman Optimality Equation）?

v=f(v)=max⁡π(rπ+γPπv) \color{red}{v=f(v)=\max_{\pi}\left(r_\pi\right.+\gamma P_\pi v)}v=f(v)=πmax​(rπ​+γPπ​v)
根据之前的内容，我们知道可以采用压缩映射定理（contraction mapping thcorerin）使用迭代算法求解：

vk+1=f(vk)=max⁡π(rπ+γPπvk),k=1,2,3,... v_{k+1}=f(v_k)=\max_{\pi}(r_\pi+\gamma P_\pi v_k),k=1,2,3,...vk+1​=f(vk​)=πmax​(rπ​+γPπ​vk​),k=1,2,3,...

• 其中初始值v0v_{0}v0​是一个任意值；
• 该算法最终能够发现最优状态值 (optimal state value) 和一个最优策略 (optimal policy) ；
• 该算法被称为值迭代算法（Value iteration）；

1、值迭代算法详细过程

vk+1 = f(vk )=max⁡π(rπ + γPπvk ),k=1,2,3... v_{k+1}\:=\:f(v_k\:)=\max_{\pi}\left(r_\pi\:+\:\gamma P_\pi v_k\:\right),k=1,2,3...vk+1​=f(vk​)=πmax​(rπ​+γPπ​vk​),k=1,2,3...

可以分解为两部：

• Step 1:Policy Update, 这一步是处理等号右侧的优化问题，求解πk+1\pi_{k+1}πk+1​：
  πk+1=argmax⁡π(rπ+γPπvk) \pi_{k+1}=arg\max_{\pi}\left(r_{\pi}\right.+\gamma P_{\pi}\left.v_{k}\right)πk+1​=argπmax​(rπ​+γPπ​vk​)
  其中vkv_kvk​是给定的

• Step 2:Value Update
  vk+1=rπk+1+γPπk+1vk v_{k+1}=r_{\pi_{k+1}}+\gamma P_{\pi_{k+1}}v_kvk+1​=rπk+1​​+γPπk+1​​vk​
  问题：vkv_kvk​是不是一个state value? 当然不是。

  • 从上面公式可以看到，而等式左边是vk+1v_{k+1}vk+1​，等式右边是vkv_k