Value-based Method

Dynamic Programming

假设我们知道状态转移概率， bootstrapped 更新：
确定性策略：


简化：

NOTE：函数是评价在状态下采取不同动作好坏的函数 ，函数是评价当前状态的好坏，此时已经选取了一个了（动作已经确定了）。一般情况下是选当前策略的平均动作（average action），因此又可以定义为

策略迭代

策略迭代

值迭代

值迭代

NOTE：其中值迭代算法的第二步就是在进行策略的更新，选取当前状态下可以获得最大收益的动作，由于该策略是确定性的，因此，此时值函数的更新应该就是。换句话说在值迭代算法中第二步值函数的更新就等价为是策略的更新。

Question

• 为什么说 Q-learning 是 off-policy ？
  因为Q-learning学习（近似）的是Q函数，因此在收集数据的时候，策略可以是任意的。

• 为什么要在策略中加入探索？
  如果转移概率已知就不需要加入探索，直接采用原始值迭代算法即可。但是很多情况是转移概率分布不知道的，这时就需要使用样本去估计下一个状态的转移，因此这个时候如果探索的不充分，将导致较大的估计误差，最终使得我们估计出来的Q函数是次优的。

• Fitted Q-iteration 能保证收敛吗？
  只要是拟合的Q迭代都不能保证收敛性。因为Q迭代算子是关于无穷范数（‘max’范数）的一个压缩，Q函数拟合算子则是关于l2范数的一个压缩，然而这两个算子同时作用时不是任何范数的压缩，因此收敛性不能保证。
  推而广之，任何同时用到Q函数拟合、Q迭代算子的地方，算法的收敛性都不能保证（e.g 使用了值函数的Actor-Critic算法）