Lecture 4: Value Iteration and Policy Iteration Algorithm

本课程中第一次正式介绍强化学习算法，且是一个model-based算法

很重要

下节课将介绍model-free的算法

Part 1: Value iteration algorithm

Value iteration

先回顾一下

• How to solve the Bellman optimality equation?

• In the last lecture, we know that the contraction mapping theorem suggest an iterative algorithm:

where can be arbitrary随机的

• this algorithm is called value iteration

---

The algorithm

can be decomposed to two steps.

• Step 1: policy update. This step is to solve

where is given.

• Step 2: value update

注意这里的不是state value的意义，他就是值，类似不动点的那个迭代算法的感觉，也因此这个算法叫值迭代算法(value iteration algorithm)，当趋向无穷，趋近state value

接下来，我们要学习 elementwise form 来使用这个 algorithm

• Matrix-vector form is useful for theoretical analysis
• Elementwise form is useful for implementation

Value iteration algorithm - Elementwise form

• Step 1: Policy update

The elementwise form of

is

the optimal policy solving the above optimization problem is

where . is called a greedy policy, since it simply selects the greatest q-value

• Step 2: Value update

The elementwise form of

is

Since is greedy, the above equation is simply

Procedure summary

greedy policy new value

• 当 还没收敛的时候:
  • 遍历每一个状态空间的 :
    • 遍历这个状态下所有的 (不只是策略里有的action):
      • 算出 q-value:
    • 找到哪一个 对应的是最大的 :
    • 把找到的 的概率在策略中更新为 1
    • 把这个 的state value更新成这个的action value

Example

看到下面这个表格，要理解意思是，我们得到后，要能求出对应的，实际写代码的时候这个表格的形式是不必要的，这里只是展示更直观一点

Part 2: Policy iteration algorithm

The algorithm leads to a sequence

PE = policy evaluation, PI = policy improvement

Questions:

1. policy evaluation中，如何求解state value

在贝尔曼公式中已经详细介绍过了

• Closed-form solution:

• Iterative solution:

• Policy iteration is an iterative algorithm with another iterative algorithm embedded in the policy evaluation step. Policy evaluation 是 policy iteration 这个算法的一步，而这一步又依赖于一个迭代的算法

2. policy improvement中，为什么新的policy 比 好

3. 为什么这个迭代算法最后得到的是最优 policy

一定会随着迭代越来越好，但他能不能收敛到最优的那个值需要数学上的证明

4. 这个 policy iteration algorithm 和前面讲的 value iteration algorithm 什么关系？我这个很想知道这个

后面会详细讲，policy iteration 和 value iteration 实际上是 truncated policy iteration 算法的两个极端

Policy iteration algorithm - Elementwise form

Step 1: Policy evaluation

• Matrix-vector form:
• Elementwise form:

当大到收敛时暂停

Step 2: Policy improvement

上一步我们找到了，这一步我们就要更新

• Matrix-vector form:
• Elementwise form

Here, is the action value under policy . Let

Then, the greedy policy is

我是真的讲不清和value iteration的区别在哪里，如果我看懂了会在后面再写的

Implementation

Simple example

看这步感觉有点知道迭代是何意味了，其实就是一种解法，你也可以直接算

Part 3 Truncated policy iteration algorithm

应该是一个能把上面两个algorithm统一起来的一般化的推广

Compare value iteration and policy iteration

这两个算法是非常类似的，但tmd区别到底是什么，要把关键点出来

---

关注第4步，这里是两个算法差异所在

妈的，绝了，关键在于更新策略的频率

Truncated policy iteration - Pseudocode

和policy iteration algorithm框架完全一样，就是迭代次数有截断而不是等到收敛了再截断

之后会关心这个迭代次数怎么选择会产生什么影响

三种算法收敛速度的比较