RL的原理-4-值迭代与策略迭代

1.值迭代(Value Iteration)#

  值迭代是一种通过反复应用贝尔曼最优公式来计算最优状态值函数和最优策略的方法。就是在rl-3中提到的贝尔曼最优公式的求解。

  值迭代的基本思想是从一个初始的状态值函数$v_0$开始，反复应用贝尔曼最优公式，得到一系列的状态值函数$v_1, v_2, ...$。随着迭代次数的增加，这些状态值函数将逐渐逼近最优状态值函数$v_{*}$。

$$v_{k+1} =f(v_k) = \max_{\pi} \left( r_{\pi} + \gamma \mathbf{P_{\pi}} v_k \right)$$

1.1 算法步骤（Matrix form）#

1. 策略更新(policy update)：对于当前的状态值函数$v_k$，计算对应的策略$\pi_k$。

$$\pi_{k+1}= argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_k)$$

2. 值更新(value update)：使用贝尔曼最优公式更新状态值函数$v_{k+1}$。

$$v_{k+1} = r_{\pi_{k+1}} + \gamma \mathbf{P_{\pi_{k+1}}} v_k$$

1.2 算法步骤（Element-wise form）#

1. 策略更新(policy update)

$$\pi_{k+1}(s) = argmax_{a} \sum \pi(a|s) (\sum_{r} p(r | s, a)r+ \gamma \sum_{s'} p(s' | s, a) v_k(s')), \forall s \in S$$

  然后最大的动作就是当前状态下的最优动作,这是一个贪心的过程。

$$\pi_{k+1}(s) = argmax_{a} q_{k}(a, s), \forall s \in S$$ $$\pi_{k+1}(a|s)= \begin{cases} 1 & a=a^*_{k}(s) \\ 0 & a \ne a^*_{k}(s) \end{cases}$$

2. 值更新(value update)

$$v_{k+1}(s) = \sum_{a} \pi_{k+1}(a|s) (\sum_{r} p(r | s, a)r+ \gamma \sum_{s'} p(s' | s, a) v_k(s')), \forall s \in S$$ $$v_{k+1}(s) = \max_{a} q_{k}(a,s)$$

1.3例子#

  我们会有一个q-value的表格，然后通过上面的步骤不断更新q-value表格，直到收敛为止。

q-value	$a_{1}$	$a_{2}$	$a_{3}$	…
$S_{1}$	$-1+\gamma v({s1})$	$0+\gamma v({s3})$	$0+\gamma v({s1})$
$S_{2}$	…
$S_{3}$	…
…	…

  通过之前的式子知道$v_{k+1}(s) = \max_{a} q_{k}(a,s)$，所以每次更新v-value的时候，就是取q-value表格中每一行的最大值。这里的每次更新是所有状态都会进行更新。

  在执行的时候让$v_{k}=0$，设定个初值上面的表格就是具体的数了，然后就可以不断迭代，直到收敛为止。

2.策略迭代(Policy Iteration)#

  最开始有一个策略$\pi_0$，任意的就行，然后通过策略评估计算出对应的状态值函数$v_{\pi_0}$，然后进行策略迭代。

2.1 算法步骤（Matrix form）#

1. 策略评估(Policy Evaluation)：对于当前的策略$\pi_k$，计算对应的状态值函数$v_{\pi_k}$。

$$v_{\pi_k} = r_{\pi_k} + \gamma \mathbf{P_{\pi_k}} v_{\pi_k}$$

2. 策略改进(Policy Improvement)：使用贝尔曼最优公式更新策略$\pi_{k+1}$。

$$\pi_{k+1}= argmax_{\pi}(r_{\pi} + \gamma P_{\pi} v_{\pi_k})$$

2.2 算法步骤（Element-wise form）#

  在这里每次迭代都是更新所有状态选择的策略。

1. 策略评估(Policy Evaluation)

  这里也是迭代的过程，通过不断迭代计算出对应的状态值函数$v_{\pi_k}$。

$$v_{\pi_k}^{(j+1)}(s) = \sum_{a} \pi_k(a|s) (\sum_{r} p(r | s, a)r+ \gamma \sum_{s'} p(s' | s, a) v_{\pi_k}^{(j)}(s')), \forall s \in S$$

2. 策略改进(Policy Improvement)

$$\pi_{k+1}(s) = argmax_{a} \sum \pi(a|s) (\sum_{r} p(r | s, a)r+ \gamma \sum_{s'} p(s' | s, a) v_{\pi_k}(s')), \forall s \in S$$

3.截断迭代（Truncated Iteration）#

  当$j=1$时，就会变成值迭代(Value Iteration)，所以值迭代可以看作是策略迭代的一种特殊情况，而在实际中，策略迭代中的策略评估过程不可能进行无限次的策略评估，所以实际应用时也是截断的。