[RL Notes] 通过最优价值函数获得最优策略

Author: nex3z 2019-10-19

  得到了最优价值函数之后，可以进一步得到最优策略。

1. 已知最优状态价值函数

　　只要我们知道了最优价值函数 $v_*$ 和 MDP 的动态特性 $p(s’, r | s, a)$，就可以很容易地得到最优策略。由贝尔曼最优方程

$$\begin{equation} v_*(s) = \max_{a} \sum_{s’} \sum_{r} p(s’, r | s, a) \big[ r + \gamma v_*(s’) \big] \tag{1} \end{equation}$$

对于每一个状态 $s$，都存在一个或多个动作可以在贝尔曼最优方程的条件下产生最大的价值。只要在每个状态都选择最大化 $\sum\limits_{s’} \sum\limits_{r} p(s’, r | s, a) \big[ r + \gamma v_*(s’) \big]$ 的动作，即

$$\begin{equation} \pi_*(s) = \underset{a}{\arg\max} \sum_{s’} \sum_{r} p(s’, r | s, a) \big[ r + \gamma v_*(s’) \big] \tag{2} \end{equation}$$

这个策略就是一个最优策略。对于最优价值函数 $v_*$，任何贪心策略都是最优策略。

　　式 $(2)$ 可以表示为图 1 的形式，要计算式 $(2)$ 中的 $\sum\limits_{s’} \sum\limits_{r} p(s’, r | s, a) \big[ r + \gamma v_*(s’) \big]$，只需要知道下一步可能的状态 $s’$ 及对应的收益 $r$ 即可。

　　举例来说，如图 2 所示，在某个状态下有 $A_1$、$A_2$、$A_3$ 三个动作，每个动作对应两个后续状态。

要找到最优动作，只需要向后观察一步。例如对于动作 $A_1$，它有两个可能的后续状态，由于我们已知 $v_*$ 和 $p(s’, r | s, a)$，就可以计算 $\sum\limits_{s’} \sum\limits_{r} p(s’, r | s, A_1) \big[ r + \gamma v_*(s’) \big]$，假设为 $5$；类似地，可以计算 $A_2$ 和 $A_3$ 对应的值为 $10$ 和 $7$，此时只要选择能带来最大状态价值的动作即可，即 $A_2$。

2. 已知最优动作状态价值函数

　　如果已知最优动作状态价值函数 $q_*(s, a)$，要找到最优策略就更加简单，只需在每个状态选择最大化 $q_*(s, a)$ 的动作即可

$$\begin{equation} \pi_*(s) = \underset{a}{\arg\max} q_*(s, a) \tag{3} \end{equation}$$

式 $(3)$ 可以表示为图 3 的形式。

　　因为从 $q_*(s, a)$ 就可以直接得到状态 $s$ 下执行动作 $a$ 并按最优策略进行决策的期望回报，相当于保存了上文通过 $v_*$ 和 $p(s’, r | s, a)$ 进行单步搜索的结果，也就不需要知道 MDP 的动态特性 $p(s’, r | s, a)$。

3. 一个例子

　　在前文的例子中，对于如图 1(a) 所示的 MDP，计算了采用随机策略的状态价值函数如图 1(b) ，计算采用最优策略的状态价值函数如图 1(c) 所示。

　　在图 1(a) 中，在状态 $A$ 可以选择向上、下、左、右四个方向移动。向上和向左移动都会返回状态 $A$ 并得到收益 $0$；向右移动会进入状态 $B$ 并得到收益 $5$；向下移动回进入状态 $C$ 并获得收益 $0$。本例中令 $\gamma = 0.7$，有

$$\begin{align} &p(A, 0 | A, \uparrow) \big[ 0 + \gamma v_*(A) \big] = 1 \times (0 + 0.7 * 16.67) = 11.67 \\ &p(A, 0 | A, \leftarrow) \big[ 0 + \gamma v_*(A) \big] = 1 \times (0 + 0.7 * 16.67) = 11.67 \\ &p(B, 5 | A, \rightarrow) \big[ 5 + \gamma v_*(B) \big] = 1 \times (5 + 0.7 * 16.67) = 16.67 \\ &p(C, 0 | A, \downarrow) \big[ 0 + \gamma v_*(C) \big] = 1 \times (0 + 0.7 * 11.67) = 8.17 \\ \end{align}$$

将上面结果代入式 $(1)$ 可以验证状态 $A$ 的最优状态价值 $v_*(A) = 16.67$，代入式 $(2)$ 可得最优策略 $\pi_*(A) = \rightarrow$，即向右移动。通过相同的步骤，可以得到最优策略如图 2 所示。