在连续领域中进行不确定性规划对于自主系统至关重要，但计算需求较高。树基搜索方法如蒙特卡洛树搜索（MCTS）仍然受到欢迎，但其分支结构在最坏情况下可能导致采样预算随着前瞻深度呈指数增长。对于树形结构，连续状态或动作空间尤其具有挑战性，因为规划者必须决定在无限分支层次中何处进行搜索。
我们提出了图稀疏采样（GSS），这是一种在线规划算法，它在多个候选决策之间共享采样的未来，而不是为每个候选动作单独采样后续。这种无分支图结构暴露了大量适合GPU处理的批次，同时使用启发式方法来集中计算。我们证明了GSS的有限样本性能保证，涵盖全秩或低秩生成模拟器，通过平滑备份，以及离散或采样的连续动作空间。
在适当的重叠、规律性和动作覆盖条件下，这些界限与规划地平线具有多项式依赖性，形式化了何时共享未来能够避免树形稀疏采样的指数地平线依赖性。我们展示了连续控制模拟，其中GSS在长地平线下显著优于基于树的规划器，或实现接近最佳性能，支持无分支图规划作为在线控制的互补设计原则。
博主点评： 图稀疏采样（GSS）算法为解决连续MDP规划中的计算复杂性提供了新的思路，通过共享采样数据来优化计算效率，极大地提升了长时间预测的性能，展示了图结构在在线控制中的潜力。其理论证明为该方法的有效性提供了坚实基础，值得深度关注与研究。