arXiv:2605.11324cs.LGstat.ML2026-05

无需预设误差阈值,高效识别近似最优决策路径。

$\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search

论文配图:$\varepsilon$-Good Action Identification in Fixed-Budget Monte Carlo Tree Search
图 1 · 摘自论文原文
  • 设计不依赖ε的自适应算法,自动适配不同精度需求。
  • 误判概率随采样次数指数下降,速率由跨子树与内子树差距决定。
  • 适用于近似规划场景,尤其适合复杂决策树中的快速策略筛选。

我们研究深度为2的max-min树中固定预算下的最大最小动作识别问题,这是蒙特卡洛树搜索的重要特例。学习者需在有限的T次采样中分配至叶节点,并推荐一个最小叶值最大的子树。为支持近似规划,关注ε-良好子树识别:只要子树最小值在最优最大最小值ε范围内即被接受。本文提出一种ε无关算法,无需输入ε即可对所有合理ε实现实例相关误差界。证明其误识概率以exp(−~Θ(T/H₂(ε)))的速率衰减,其中H₂(ε)同时捕捉了子树间与子树内的间隙。当每子树仅含单个叶节点时,问题退化为标准固定预算最优臂识别,我们的分析恢复了已知的半分法式方法ε-良好保证(差一个加速因子),并首次为成功拒绝法提供ε-良好新保证。下界方面,我们给出互补的正负结果,表明max-min识别具有不同于标准K臂老虎机的难度结构。据我们所知,这是首个针对max-min动作识别的可证明固定预算算法保证。

原文摘要 · Abstract (English)

We study the fixed-budget max-min action identification problem in depth-2 max-min trees, an important special case of Monte Carlo Tree Search. A learner sequentially allocates $T$ samples to leaves and then recommends a subtree whose minimum leaf value is largest. Motivated by approximate planning, we focus on $\varepsilon$-good subtree identification, where any subtree whose min value is within $\varepsilon$ of the optimal maximin value is acceptable. Our main contribution is an $\varepsilon$-agnostic algorithm: it does not require $\varepsilon$ as input, but achieves instance-dependent error bounds for every meaningful $\varepsilon$. We show that the misidentification probability decays as $\exp(-\widetildeΘ(T/H_2(\varepsilon)))$, where $H_2(\varepsilon)$ captures both cross-subtree and within-subtree gaps. When each subtree has a single leaf, the problem reduces to standard fixed-budget best-arm identification, and our analysis recovers, up to accelerating factors, known $\varepsilon$-good guarantees for halving-style methods while giving a new $\varepsilon$-good guarantee for Successive Rejects. On the lower-bound side, we provide complementary positive and negative results showing that max-min identification has a different hardness structure from standard $K$-armed bandits. To our knowledge, this is the first provable fixed-budget algorithmic guarantee for max-min action identification.

强化学习树搜索采样优化近似规划

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。