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

2019-10-22 14:59:13 浏览数 (3)

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：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)=πargmax​Vπ(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)=πargmax​Vπ(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 πipi_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′∈S​P(s′∣s,a)Vπ(s′)

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

Policy Imporvement
  • Compute state-action value of a policy πipi_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′∈S​P(s′∣s,a)Vπi​(s′)
  • Compute new policy πi 1pi_{i 1}πi 1​, for all s∈Ssin 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)=aargmax​Qπi​(s,a) ∀s inSforall 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))amax​Qπi​(s,a)≥Qπi​(s,πi​(s))，也就是说，agent要么采取了策略指定的动作，要么采取了经由argmaxargmaxargmax Q function计算得到的更好的动作，从而产生了新的策略。

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

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

  • 假设我们在一个action采取了计算的得到的πi 1(s)pi_{i 1}(s)πi 1​(s)，然后再一直遵循旧的πipi_iπi​。
    • 我们的回报期望总值至少和从头到尾遵循πipi_iπi​一样
  • 但是奇怪的是，新提出的策略将会一直遵循πi 1pi_{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​，在πipi_iπi​是次优的条件下，这个不等式严格成立，其中πi 1pi_{i 1}πi 1​是我们在πipi_iπi​上进行策略优化得到的。

证明过程如下：

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

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

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

没有。πi 1=πipi_{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) gammasum_{s in S}p(s'|s,a)V(s')BV(s)=amax​R(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) gammasum_{s' in S}P(s'|s,a)V_k(s')Vk 1​(s)=amax​R(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) gammasum_{s' in S}P(s' | s,a)V_k(s')πk 1​=aargmax​R(s,a) γ∑s′∈S​P(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) gammasum_{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

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

为了进行策略优化： π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) gammasum_{s' in S}P(s'|s, a) V^{pi_k}(s')πk 1​(s)=aargmax​R(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) gammasum_{s' in S}P(s'|s,a)V_k(s')Vk 1​(s)=amax​R(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) gammasum_{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 也是一个缩减操作符。

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

Bellman backup在折扣因子γ<1gamma < 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) gammasum_{s' in S}P(s'|s,a)V_k(s)Vk​ 1(s)=amax​R(s,a) γ∑s′∈S​P(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) gammasum_{s' in S}P(s'|s)V_k(s')πk 1​(s)=aargmax​R(s,a) γ∑s′∈S​P(s′∣s)Vk​(s′)

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

注意，这里说最优策略不是固定的(独立于时间步)，是在迭代求最优价值的情境下，跟博文开头的最优策略不在一个情境下。

Value vs Policy Iteration

  • 价值迭代
    • 计算的是horizon为k时的最优价值
      • 注意这点可以被用来计算最优策略
  • 策略迭代
    • 计算有限horizon内策略的价值
    • 用于选择另外的更好的策略
    • 策略迭代跟RL里一个非常流行的方法策略梯度关系非常紧密
backup iteration policy state sum

0 人点赞