Qzero算法介绍

一、为了介绍Qzero算法，先简单介绍一下AlphaZero系列算法：

1. AlphaZero算法： 算法的核心是把MCTS算法与深度强化学习（DRL）结合起来（使用MCTS算法作为RL的policy improvement机制）。为了达到这个目的做了两点改动：

i. 把MCTS算法的四个步骤：Select - Expand - Simulate - Backup 中的第三步Simulate替换成值网络(value head)的 Evaluate。

ii. 把Select使用的算法换成PUCT的变种算法，选择动作的先验概率P(s,a)由策略网络(policy head)给出：

其余的过程与普通的self-play强化学习一样。

2. MuZero算法： 算法的核心是学一个“dynamics model”。“Crucially, our method does not require any knowledge of the game rules or environment dynamics, potentially paving the way towards the application of powerful learning and planning methods to a host of real-world domains for which there exists no perfect simulator.”

MuZero算法只是比AlphaZero算法多学了一个model，为了不跑题，这里就不展开了。“MuZero builds upon AlphaZero’s powerful search and search-based policy iteration algorithms, but incorporates a learned model into the training procedure.”

3. Modified AlphaZero/MuZero 算法：

“Monte-Carlo tree search as regularized policy optimization”

https://arxiv.org/pdf/2007.12509.pdf

最近的进展是 DeepMind 提出的 Modified AlphaZero/MuZero 算法，算法的核心洞察是发现了AlphaZero中PUCT算法与强化学习MPO算法之间的联系，用下式替换了PUCT算法的Select策略：

以提升MCTS（主要在搜索次数少时）的效率。

二、Qzero算法：

策略熵对强化学习中的 explore-exploit 问题有重要的统领作用，不应只限制在model-free 强化学习领域中，为此提出Qzero算法。

Qzero算法的核心洞察是：把熵的概念引入到 model-based 强化学习中，具体做法就是把SQN算法与AlphaZero算法结合起来，以实现强强联合（主要是实现SQN和MCTS这两个policy improvement机制的融合），进一步提高model-based 强化学习的效率。

Qzero算法的流程和AlphaZero算法是相似的，为了方便理解，直接把AlphaZero算法流程图贴出来，在此基础上介绍Qzero算法：

引入熵，最naive的做法是把熵正规化直接加入到AlphaZero算法中。即在MCTS的backup和Learning的backup中，每一个step除了累加环境给的reward，还要加上策略熵：

但是这样做，算法的复杂性反而增加了。

Qzero算法思考的是如何简化算法。在AlphaZero算法中，有value head和policy head两个网络输出，然而这并不是必须的，value和policy之间存在信息冗余。Qzero算法只有一个head，即Q-value head，value和policy均可由Q-value head导出。与SQN算法类似，算法设计遵从 “如无必要，勿增实体” 的原则。

这里沿用我在Sample Factory介绍中对RLSystem各个部分的称谓。

RLSystem = Sampler + Learner = (Simulator + Actor) + Learner.

上图 Figure 1a 为 Actor，1b为Learner， Figure 2 为 Simulator。

Qzero算法总结(相对于AlphaZero的改动)如下：

1. Simulator (MCTS)

select: Softmax policy based on Q-value (SQN)

backup: Q-value update (SQN, SQN n-step/GAE, SQN-CF)

2. Actor

play: Softmax policy based on Q-value (SQN)

3. Learner

learn: Q-value update

training data: i. Simulator output，ii. Actor trajectory (SQN n-step/GAE)

Qzero和AlphaZero算法中都存在类比关系：Simulator select ~ Actor play，Simulator backup ~ Learner learn。在Qzero算法中，这两对类比关系中的操作统一由SQN算法执行，这也是Qzero算法简洁的一个体现。

三、算法理论分析：

略。

等等，我找到了一个相关研究，复制粘贴中。。。

“Maximum Entropy Monte-Carlo Planning”

论文链接：

https://papers.nips.cc/paper/9148-maximum-entropy-monte-carlo-planning.pdf

这项研究可以看做是Qzero算法的Simulator部分的一个特例，论文作者对Simulator (MCTS) 中Q-value update (SQN-CF) 进行了研究，研究中提出的算法MENTS = MCTS + SQN-CF。SQN-CF算法 (SQN with Corrective feedback) 是SQN算法的一个变种，下次有空介绍。

四、总结一下：

AlphaZero只是在MCTS中进行了一次policy improvement，而QZero中有两次policy improvement：一次是在Simulator (MCTS) 中，另一次是在Actor中用Q转化(softmax)成policy时。这两次policy improvement正是Qzero算法的核心。另外，Qzero算法也可以和MuZero算法结合，变成QMuZero算法。

Qzero算法是“熵强化学习”三部曲的最后一部，稍后会对“熵强化学习”进行简单总结。

五、围棋：

回到现实的问题，围棋是model-based RL的重点关注对象。虽然围棋AI已经超过人类，但我对现在的围棋AI还不是很满意：

1. AlphaGo Zero的真实棋力只有3000 (Raw Network)，可以说是棋力不够，算力来凑。

2. 没能学会小学生都会的“扭羊头”。

" Notably, ladder moves, which are easy for human beginners to understand after a few examples, are difficult for the model to learn and never fully mastered. "

3. 官子阶段被广为诟病。(与第4点有关)

4. 训练按照特定的贴目规则，而不是把赢的目数作为reward。这样做会让AI受限于给定的规则，只在乎输赢而不会扩大战果。

有一个有意思的问题是：围棋贴目具体多少是公平的？网上查到：现代大量职业棋手的对局表明现行围棋规则下最合理的贴目是6.5目。AI比人类棋手强，AI的结果会更可靠。可以按输赢的目数作为reward来训练Agent，这样做可以推测贴目具体多少是公平的，得出围棋的公平规则。另外，这样做AI也能学会扩大战果，寸土必争。

欢迎有资源的小伙伴使用Qzero算法跑围棋，象棋等游戏 ：）