通过重根机制让搜索效率指数级提升，适配多种智能体任务。
Exponential Speedups by Rerooting Levin Tree Search
- 在每个节点启动独立的LTS搜索，按权重分配计算资源。
- 最优情况下，搜索时间从T降至O(q×T^(1/q))，实现指数加速。
- 可学习重根策略，适用于多领域自主决策任务。
Levin树搜索（LTS）是一种针对确定性环境的搜索算法，利用用户指定的策略引导搜索过程，并对找到解节点所需的搜索步数（节点访问次数）提供形式化保证。本文提出新算法√LTS（读作根-LTS），其隐式地在搜索树的每个节点启动一个LTS搜索。每个搜索由（用户定义或学习得到的）重根器分配权重，搜索资源按权重比例分配。该重根机制隐式将搜索空间分解为子任务，带来显著加速。我们证明，√LTS所需的节点访问次数与最优子任务分解相当，代价是与重根器不确定性相关的因子。若原LTS耗时T，最优情况下有q个重根点时，√LTS仅需时间O(q×T^(1/q))。重根器可基于数据学习，预期√LTS可广泛应用于各类领域。
原文摘要 · Abstract (English)
Levin Tree Search (LTS) (Orseau et al., 2018) is a search algorithm for deterministic environments that uses a user-specified policy to guide the search. It comes with a formal guarantee on the number of search steps (node visits) for finding a solution node that depends on the quality of the policy. In this paper, we introduce a new algorithm, called $\sqrt{\text{LTS}}$ (pronounce root-LTS), which implicitly starts an LTS search rooted at every node of the search tree. Each LTS search is assigned a rerooting weight by a (user-defined or learnt) rerooter, and the search effort is shared between all LTS searches proportionally to their weights. The rerooting mechanism implicitly decomposes the search space into subtasks, leading to significant speedups. We prove that the number of node visits that $\sqrt{\text{LTS}}$ takes is competitive with the best decomposition into subtasks, at the price of a factor that relates to the uncertainty of the rerooter. If LTS takes time $T$, in the best case with $q$ rerooting points, $\sqrt{\text{LTS}}$ only takes time $O(q\sqrt[q]{T})$. Like the policy, the rerooter can be learnt from data, and we expect $\sqrt{\text{LTS}}$ to be applicable to a wide range of domains.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。