深度学习23-离散优化中的强化学习

### 离散优化中的强化学习

▪  简要讨论离散优化的基础知识。
▪  逐步介绍UCI研究人员Stephen McAleer等人的论文“Solving the Rubik's Cube Without Human Knowledge”（2018, arxiv: 1805.07470），该论文将RL方法应用于魔方的优化问题。
▪  探索我做的实验以重现论文的结果，以及说明将来改进方法的方向。

**选择状态的特定表示形式时，我们还有不同的目标需要实现：**
▪  避免冗余：在极端情况下，我们只需记录每侧每个贴图的颜色即可表示魔方的状态。但是，如果我们计算一下这些组合的数量，能得到66·8 = 648≈2.5×1037，它远大于魔方的状态空间大小，这意味着该表示形式是高度冗余的。例如，它允许魔方的所有面都具有同一种颜色（中间的小方块除外）。如果你想知道我是怎么得到648的，这很简单：魔方有6个侧面，每个侧面都有8个方格（不算中心），所以总共有48个贴图，每个贴图都可以涂上6种颜色中的一种。
▪  内存效率：你很快就会看到，在训练期间以及模型应用期间，我们将需要在计算机内存中保留大量不同的魔方状态，这可能会影响魔方处理的性能。因此，我们希望表示形式尽可能紧凑。
▪  转换的性能：另一方面，我们需要实现应用于状态的所有动作，并且这些动作需要迅速执行。如果我们的表示形式在内存方面非常紧凑（例如，使用位编码），但是要求我们对魔方侧面的每次旋转执行冗长的解包过程，则训练将变得很慢。
▪  NN友好性：并非每个数据表示都适用于NN的输入。这句话不仅适用于我们的示例，也适用于通用机器学习。例如，在NLP中，通常使用词袋或词嵌入；在计算机视觉中，图像从JPEG解码为原始像素；随机森林需要对数据进行大量的特征工程；等等。

**从神经网络的结构上，一个很明显但不是很成功的方法：**
1）向模型提供要解决的魔方的当前状态。
2）从策略输出端开始，执行最优的动作（或从结果分布中进行采样）。
3）将动作应用于魔方。
4）重复该过程，直到达到解决状态。

**从MCTS树中获取旋转路径**

▪  原始方法：到达目标状态后，我们将使用从根状态开始的路径作为解决方案。
▪  BFS方法：到达目标状态后，对MCTS树执行BFS，以查找从根到此状态的最短路径。

**该类的构造函数有许多参数：**
▪  环境名称。
▪  环境状态的类型。
▪  魔方的初始（组装好的）状态的实例。
▪  断言函数，用于检查特定状态是否表示已组装的魔方。对于3×3魔方，这可能看起来是多余的，因为我们可以将它与在initial_state参数中传递的初始状态进行比较，但是，大小为2×2和4×4的魔方可能具有多个最终状态，因此需要一个单独的断言函数来涵盖此类情况。
▪  可应用于状态的动作枚举。
▪  旋转函数，接受状态和动作并返回结果状态。
▪  逆函数，将每个动作映射到其相反的动作。
▪  渲染函数以人类可读的形式表示状态。
▪  编码状态张量的形状。
▪  将紧凑状态表示编码为NN友好形式的函数。

**进一步改进和实验**

▪  更多的输入和网络工程：魔方是一个复杂的东西，因此简单的前馈NN可能不是最佳模型。网络可能会从卷积中受益匪浅。
▪  训练过程中的振荡和不稳定可能是RL的常见问题（步间相关性）的迹象。常用的方法是目标网络，我们可以使用旧版本的神经网络来获取展开值。
▪  带优先级的回放缓冲区可能有助于加速训练。
▪  我的实验表明，样本的权重（与打乱的深度成反比）有助于获得更好的策略，该策略知道如何求解稍微打乱的魔方，但可能会减慢对更深状态的学习。这种加权可能可以自适应，以使其在以后的训练阶段不那么主动。
▪  可以将熵损失添加到训练中以正则化我们的策略。
▪  2×2魔方模型没有考虑到魔方没有中央小方块的事实，因此可以旋转整个魔方。对于2×2魔方，这可能不是很重要，因为状态空间很小，但是对于4×4魔方，相同的观察将会有非常多。
▪  需要进行更多的实验以获得更好的训练和MCTS参数。