Levin Tree Search with Context Models

论文地址：https://www.ijcai.org/proceedings/2023/0624.pdf

作者：Laurent Orseau 、 Marcus Hutter 、 Levi H. S. Lelis

机构：Google DeepMind 、阿尔伯塔大学

摘要：Levin 树搜索 (LTS) 是一种利用策略（动作的概率分布）的搜索算法，并提供了在达到目标节点之前进行多少扩展的理论保证（guarantee），这取决于策略的质量。这种保证可以看作损失函数，研究者将其称之为 LTS 损失，从而用来优化表示策略的神经网络（LTS+NN）。 

本文展示了神经网络可以替换成从在线压缩文献中产生参数化的上下文模型（LTS+CM）。本文表明， 在这个新模型下 LTS 损失是凸的，它允许使用标准的凸优化工具，并且在给定的一组解轨迹的在线设置中获得了最优参数的收敛保证 —— 这是神经网络无法提供的保证。

新的 LTS+CM 算法在几个基准上优于 LTS+NN，包括 Sokoban (Boxoban)、The Witness、STP（the 24-Sliding Tile puzzle）基准。

在 STP 基准上的结果表明，两者的差异非常大，即 LTS+NN 无法解决大多数测试实例，而 LTS+CM 在不到一秒内就解决了每个测试实例。此外，LTS+CM 能够学习解决魔方策略，只需要几百个扩展，从而大大改善了之前的机器学习方法。

下表为带有 Budgeted LTS 的上下文模型： 

内容中包含的图片若涉及版权问题，请及时与我们联系删除