Compute the Optimal Policy & the Optimal Value 计算最佳策略和计算最佳价值

Steve Wang

发布于 2019-10-22 14:59:13

9920

发布于 2019-10-22 14:59:13

文章被收录于专栏：从流域到海域从流域到海域

本文链接：https://blog.csdn.net/Solo95/article/details/102500566

MDP Control

在这节内容里我们不讨论如何学习策略，我们仅仅探讨计算最佳策略。计算最佳策略和计算最佳价值都属于MDP Control。

计算最佳策略 π∗(s)=argmaxπVπ(s)\pi^*(s)=\mathop{argmax}\limits_{\pi} V^\pi(s)π∗(s)=πargmaxVπ(s)
存在一个独一无二的最优价值函数
在一个有限horizon内MDP的最优策略是确定的

最后一条是一个非常好的原因，能够解答为什么我们仅仅关注确定性策略就已经足够解决问题。

火星小车可以移动。

那么一共有多少个确定性策略?

272^727 计算公式∣A∣∣s∣|A|^{|s|}∣A∣∣s∣

MDP的最优策略永远是独一无二的吗？

不是的。因为可能存在两个不同的动作由相同的价值函数。在上面这个例子中，最优价值函数是独一无二的，虽然可以有多个最优策略，但这些策略计算出来的价值的最大值是一样的。同时，我们假定在所有的状态下所有的动作都是能够进行的。虽然在现实世界，这可能并不成立。在很多实际例子中，一些动作是指定在某些状态下才能执行的。

总结下来：

计算最佳策略 π∗(s)=argmaxπVπ(s)\pi^*(s)=\mathop{argmax}\limits_{\pi} V^\pi(s)π∗(s)=πargmaxVπ(s)
存在一个独一无二的最优价值函数
在一个有限horizon内MDP的最佳策略(哪怕agent永远在行动)
- 确定的(Deterministic)
- 固定不动的(Stationary, does not depend on tims step)
- 独一无二的？不需要非得是独一无二的，可能有多个状态-动作对拥有相同的最佳价值。

策略搜索

一个选项是使用搜索去计算最佳策略
确定性策略的数量是∣A∣∣S∣|A|^{|S|}∣A∣∣S∣
策略迭代通常比暴力枚举更高效

MDP Policy Iteration(PI)

(下面是是一个算法，Markdown代码模式无法输入公式，所以写成这样)

Set i = 0
Initialize π0(s)\pi_0(s)π0(s) randomly for all states s
While i==0i == 0i==0 or ∥πi−πi−1∥>0\|\pi_i-\pi_{i-1}\|>0∥πi−πi−1∥>0 (L1L_1L1-norm, measures if the policy changed for any state):
- Vπi←MDPV^{\pi_i} \leftarrow MDPVπi←MDP V function policy evaluation of πi\pi_iπi
- πi+1←\pi_{i+1} \leftarrowπi+1← Policy improvement
- i = i + 1

New Dedinition: State-Action Value Q

为了定义我们如何改进一个策略，我们定义状态-动作价值 Q。

在之前的叙述中，我们使用如下notation描述状态-动作价值: Vπ(s)V^\pi(s)Vπ(s) 即，采用策略π\piπ时在状态s下的动作价值。这里我们定义新的概念，同时也定义了Q函数。

一个策略的状态-动作价值是： Qπ(s,a)=R(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)Q^\pi(s, a) = R(s, a) + \gamma \sum_{s' \in S}P(s'|s,a)V^\pi(s')Qπ(s,a)=R(s,a)+γ∑s′∈SP(s′∣s,a)Vπ(s′)

它的直观理解是，我先采取动作a，然后再遵循策略π\piπ。

Policy Imporvement

Compute state-action value of a policy πi\pi_iπi
- For s in S and a in A:
  - Qπi(s,a)=R(s,a)+γ∑s′∈SP(s′∣s,a)Vπi(s′)Q^{\pi_i}(s, a) = R(s, a) + \gamma \sum_{s' \in S}P(s'|s,a)V^{\pi_i}(s')Qπi(s,a)=R(s,a)+γ∑s′∈SP(s′∣s,a)Vπi(s′)
Compute new policy πi+1\pi_{i+1}πi+1, for all s∈Ss\in Ss∈S
- πi+1(s)=argmaxaQπi(s,a)\pi_{i+1}(s) =\mathop{argmax}\limits_{a}Q^{\pi_i}(s,a)πi+1(s)=aargmaxQπi(s,a) ∀s inS\forall s \ in S∀s inS

上面的等式中，maxaQπi(s,a)≥Qπi(s,πi(s))\mathop{max}\limits_{a} Q^{\pi_i}(s, a)\geq Q^{\pi_i}(s, \pi_i(s))amaxQπi(s,a)≥Qπi(s,πi(s))，也就是说，agent要么采取了策略指定的动作，要么采取了经由argmaxargmaxargmax Q function计算得到的更好的动作，从而产生了新的策略。

如果采用梯度下降的策略迭代方法，跟其他深度学习方法一样，会有局部最优值的问题，但是目前的情景下不会遇到这样的情况。

更进一步理解优化(改进)步骤：

假设我们在一个action采取了计算的得到的πi+1(s)\pi_{i+1}(s)πi+1(s)，然后再一直遵循旧的πi\pi_iπi。
- 我们的回报期望总值至少和从头到尾遵循πi\pi_iπi一样
但是奇怪的是，新提出的策略将会一直遵循πi+1\pi_{i+1}πi+1

改进步骤将会单调递增地改进策略价值。

为什么？

Momotonic Improvement in Policy Value

定义(Definition)： Vπ1≥Vπ2:Vπ1(s)≥Vπ2(s),∀s∈SV^{\pi_1}\geq V^{\pi_2}: V^{\pi_1}(s) \geq V^{\pi_2}(s), \forall s \in SVπ1≥Vπ2:Vπ1(s)≥Vπ2(s),∀s∈S

命题(Proposition): Vπi+1≥VπiV^{\pi_{i+1}}\geq V^{\pi_i}Vπi+1≥Vπi，在πi\pi_iπi是次优的条件下，这个不等式严格成立，其中πi+1\pi_{i+1}πi+1是我们在πi\pi_iπi上进行策略优化得到的。

证明过程如下：

证明思路总结如下：不等式右边按定义展开，然后再构造另一个不等式，这个不等式的右边可以展开成一个迭代过程，刚好等于Vπi+1(s)V^{\pi_{i+1}(s)}Vπi+1(s)。

回顾前述内容策略优化的过程：

如果策略不发生改变了，策略有再次发生改变的可能性吗？

没有。πi+1=πi\pi_{i+1}=\pi_{i}πi+1=πi

有策略迭代次数的最大值吗？

有，如前面提到的∥A∥∥S∥\|A\|^{\|S\|}∥A∥∥S∥

博主在学习TD Learning之后回来补充一点：这其实就是Q-Learining。

MDP: Computing Optimal Policy and Optimal Value

策略迭代计算最优价值和最优策略
价值迭代是另外一种技术：
- 思想：在本轮(this episode)中，从状态s开始还剩下k步，这维持了一个最优值。
- 迭代地以类似方式思考后面的轮次。

这和策略地带的不同之处在于：在策略迭代中，你总是都有一个策略，并且你知道它的价值，只是这个策略可能不是很好。在价值迭代中，你总是知道策略中的最优价值，但是你仅仅需要执行k步才能得到。

Bellman Equation and Bellman Backup Operators

一个策略的价值函数必须满足Bellman Equation: Vπ(s)=Rπ(s)+γ∑s′∈SPπ(s′∣s)Vπ(s′)V^\pi(s)=R^\pi(s) + \gamma \sum_{s' \in S}P^\pi(s'|s)V^\pi(s')Vπ(s)=Rπ(s)+γs′∈S∑Pπ(s′∣s)Vπ(s′)

Bellman backup operator
- 应用于一个价值函数
- 返回一个新的价值函数
- 尽可能的提升价值 BV(s)=maxaR(s,a)+γ∑s∈Sp(s′∣s,a)V(s′)BV(s) = \mathop{max}\limits_{a}R(s,a)+\gamma\sum_{s \in S}p(s'|s,a)V(s')BV(s)=amaxR(s,a)+γs∈S∑p(s′∣s,a)V(s′)

有时我们会使用BV来表示Bellman Operator，意思是，在每次迭代，你取就的V值代入上式的右边计算新的V值。

Value Iteration (VI)

算法表示如下：

Set k = 1
Initialize V0(s)=0V_0(s)=0V0(s)=0 for all states s
Loop until [finite horizon, convergence]:
- For each state s
  - Vk+1(s)=maxaR(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s′)V_{k+1}(s) = \mathop{max}\limits_{a}R(s,a)+\gamma\sum_{s' \in S}P(s'|s,a)V_k(s')Vk+1(s)=amaxR(s,a)+γs′∈S∑P(s′∣s,a)Vk(s′)
- View as Bellman backup on value function Vk+1=BVkV_{k+1} = BV_{k}Vk+1=BVk πk+1=argmaxaR(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s′)\pi_{k+1}=\mathop{argmax}\limits_{a}R(s,a) + \gamma\sum_{s' \in S}P(s' | s,a)V_k(s')πk+1=aargmaxR(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s′)

初始化为零时有意义的，因为相当于第一次迭代的时候最优值是一个动作的即时回报，然后把它备份，进行下一次迭代，如如此往复。

Policy Iteration as Bellman Operations

一个特定策略的Bellman backup operator BπB^\piBπ被定义为： BπV(s)=Rπ(s)+γ∑s′∈SPπ(s′∣s)V(s)B^\pi V(s) = R^\pi(s)+\gamma\sum_{s' \in S}P^\pi(s'|s)V(s)BπV(s)=Rπ(s)+γs′∈S∑Pπ(s′∣s)V(s)

策略迭代等同于计算BπB^\piBπ的不动点。

为了进行策略迭代，重复应用operator直到V停止变化。 Vπ=BπBπ...BπVV^\pi=B^\pi B^\pi...B^\pi VVπ=BπBπ...BπV

所以你可以通过固定策略来初始化Bellman operator。

Policy Iteration as Bellman Operation

为了进行策略优化： πk+1(s)=argmaxaR(s,a)+γ∑s′∈SP(s′∣s,a)Vπk(s′)\pi_{k+1}(s)=\mathop{argmax}\limits_{a}R(s,a) + \gamma\sum_{s' \in S}P(s'|s, a) V^{\pi_k}(s')πk+1(s)=aargmaxR(s,a)+γs′∈S∑P(s′∣s,a)Vπk(s′)

Going back to value Iteration(VI)

算法表示如下：

Set k = 1
Initialize V0(s)=0V_0(s)=0V0(s)=0 for all states s
Loop until [finite horizon, convergence]:
- For each state s
  - Vk+1(s)=maxaR(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s′)V_{k+1}(s) = \mathop{max}\limits_{a}R(s,a)+\gamma\sum_{s' \in S}P(s'|s,a)V_k(s')Vk+1(s)=amaxR(s,a)+γs′∈S∑P(s′∣s,a)Vk(s′)
- Equivalently, in Bellman backup notation
  - Vk+1=BVkV_{k+1}=BV_{k}Vk+1=BVk

To extract optimal policy if can act for k+1 more steps, π(s)=argmaxR(s,a)+γ∑s′∈SP(s′∣s,a)Vk+1(s′)\pi(s)=\mathop{argmax}R(s,a)+\gamma\sum_{s' \in S}P(s'|s,a)V_{k+1}(s')π(s)=argmaxR(s,a)+γs′∈S∑P(s′∣s,a)Vk+1(s′)

Contration Operator

补充一点缩减(Contration)方面的知识。

定义O是一个操作符，并且∣X∣|X|∣X∣表示x的任何形式的norm
如果∣OV−OV′∣≤∣V−V′∣|OV-OV'|\leq |V-V'|∣OV−OV′∣≤∣V−V′∣，那么O就是一个缩减操作符

Will Value Iteration Converge？

Bellman backup 也是一个缩减操作符。

是的，如果折扣因子γ<1\gamma < 1γ<1，整个过程会以1的概率结束在一个终止状态。

Bellman backup在折扣因子γ<1\gamma < 1γ<1时会缩减。

如果把Ballman backup应用到两个不同的价值函数，两个函数的距离在应用Bellman Equation后会减小。

证明如下，有兴趣的话你可以看看。

Value Iteration for Finite Horizon

Vk=V_k=Vk=optimal value if making k more decisions πk=\pi_k=πk=optimal policy if making k more decisions

Initialize V0(s)=0V_0(s)=0V0(s)=0 for all state s
For k=1 : H
- For each state s Vk+1(s)=maxaR(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s)V_k+1(s)=\mathop{max}\limits_{a}R(s,a)+\gamma\sum_{s' \in S}P(s'|s,a)V_k(s)Vk+1(s)=amaxR(s,a)+γ∑s′∈SP(s′∣s,a)Vk(s) πk+1(s)=argmaxaR(s,a)+γ∑s′∈SP(s′∣s)Vk(s′)\pi_{k+1}(s)=\mathop{argmax}\limits_{a}R(s,a)+\gamma\sum_{s' \in S}P(s'|s)V_k(s')πk+1(s)=aargmaxR(s,a)+γ∑s′∈SP(s′∣s)Vk(s′)

这个算法跟之前讲过的一样，只是限定了迭代到H次，即horizon大小。