Approximately Optimal Approximate Reinforcement Learning

Problems with Approximate Value Function Method and Gradient Policy Method

有三个问题:

1. 是否有一个每一步都提升的表现 / 度量
2. 验证这个表现 / 度量是否提升有多难
3. 在有限步更新后表现有多少改进

不论是值函数方法还是策略梯度都存在这些问题

Approximate Value Function Method

Exact Value Function Method, 指 policy iteration, value iteration 等方法

通过计算 , 然后得到确定性策略 , 使得

重复计算 直至其收敛

这类方法可以保证值函数的收敛

Approximate Value Function Method, 指 DQN 等方法

使用近似器逼近

如果有一个近似器 , 并定义其误差:

令 是基于这个近似器改进的策略, 那么有这样一个保证:

这也好理解, 每一步 与 的误差通过 累积成

与 误差也是

所以 与 误差不超过

这个界说明改进不超过

但是没有保证每一步都一定有改进, 也没有收敛时间的保证

Policy Gradient Method

策略梯度是保证每一步有改进的

但是判断梯度方向比较困难, 即出现问题 2

考虑一个一维随机游走问题, 向左 / 右的概率不等, 那么到达坐标轴上某一点 的时间是关于 指数级的

而采用 on-policy 意味着也要指数级的时间到达终点, 才能完成一次策略更新, 从而得到梯度方向

尽管可以使用重要性采样来改成 off-policy, 但是如果根据某个 off-policy 的轨迹走到终点, 那么重要性权重也会变成指数级

同时梯度可能会降到特别小, 持续很长一段时间, 导致了问题 3

这一点 原文 有例子

Approximately Optimal RL

---

参考:

1. Approximately Optimal Approximate Reinforcement Learning