Chapter 4 DP

上一章的 two forms of the Bellman optimality equation：

or

1 Policy Evaluation

update rule:

vk$v_k$ 收敛到vπ$v_{\pi }$ .

常规的update使用两个数组来存放old和new values，这是two-array version；

还有一种是使用一个数组，直接在原有的array上更新，这是in-place version；

虽然第二种看起来不正规，但是有更快的收敛速度，因为它使用新更新的数据。

2 Policy Improvement

我们首先明确一点：每个policy π$\pi$都对应自己的value function——vπ$v_{\pi }$，我们为policy计算value function是为了找到更好的policy。

那么问题来了，我们怎么知道在当前policy下，在状态s下采取某个行动a=π(s)$a=\pi (s)$ 是最优的呢？一种检验的方法就是采取另外一个行动a≠π(s)$a\ne \pi (s)$，计算value function和vπ(s)$v_{\pi }(s)$相比。

value function之前提到过：

policy improvement theorem：

如果对所有的状态s有：

那么就有：

证明如下：

greedy policy：

如果vπ=vπ′$v_{\pi }=v_{{\pi }^{\prime }}$，那么π$\pi$和π′${\pi }^{\prime }$ 都是最优策略。

3 Iteration

3.1 Policy Iteration

a sequence of monotonically improving policies and value functions:

这种找到最优策略的方式就是Policy Iteration。

Policy Iteration Algorithm：

3.2 Value Iteration

policy iteration 的缺点是它需要在policy evaluation后才能更新策略，这非常耗时。

value iteration改进了这种缺点，不再关于a求和，而是取max

value iteration：

Value Iteration Algorithm：

3.3 Asynchronous Dynamic Programming

之前的DP方法的缺点是每一次sweep都要在整个状态集合上进行操作。

Asynchronous DP 可以以任意的顺序更新状态的value。

3.4 Iteration Summary：GPI

Generalized Policy Iteration

Policy iteration有两个同时的交互的过程——policy evaluation和policy improvement。

在policy iteration中，这两个过程是交替的，一个完成才能开始另一个，但这不必要；

在value iteration中，这两个过程是结合在一起的；

在Asynchronous DP中，这两个过程是交错的，可以不按顺序。

我们用一个名词——generalized policy iteration (GPI)来形容整体的思想。

Each process drives the value function or policy toward one of the lines representing a solution to one of the two goals. The goals interact because the two lines are not orthogonal. Driving directly toward one goal causes some movement away from the other goal. Inevitably, however, the joint process is brought closer to the overall goal of optimality.

4 Efficiency of DP

A DP method is guaranteed to find an optimal policy in polynomial time even though the total number of (deterministic) policies is kn$k^n$.

On problems with large state spaces, asynchronous DP methods are often preferred.