比UCT做得更好：树木中的有理蒙特卡罗抽样

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
UCT是蒙特卡罗树抽样(MCTS)的一种最先进的算法，它是基于UCB的多臂强盗问题(MAB)的一种最小化累积遗憾的抽样策略。然而，MCTS与MAB的不同之处在于，只有最终的选择而不是所有的手臂牵拉才会带来回报，也就是说，与累积遗憾相反的简单遗憾必须最小化。本文旨在将元推理技术应用于MCTS中，这是一项重要的工作。我们首先介绍了一种简单遗憾比UCB低的多武装强盗策略，以及一种MCTS算法，该算法结合了累积和简单遗憾最小化，并优于UCT。我们还开发了一个基于信息完美值的短视版本的松散抽样方案。给出了策略的有限时间和渐近分析，并对算法进行了实证比较。
---
英文标题：
《Doing Better Than UCT: Rational Monte Carlo Sampling in Trees》
---
作者：
David Tolpin, Solomon Eyal Shimony
---
最新提交年份：
2012
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  UCT, a state-of-the art algorithm for Monte Carlo tree sampling (MCTS), is based on UCB, a sampling policy for the Multi-armed Bandit Problem (MAB) that minimizes the accumulated regret. However, MCTS differs from MAB in that only the final choice, rather than all arm pulls, brings a reward, that is, the simple regret, as opposite to the cumulative regret, must be minimized. This ongoing work aims at applying meta-reasoning techniques to MCTS, which is non-trivial. We begin by introducing policies for multi-armed bandits with lower simple regret than UCB, and an algorithm for MCTS which combines cumulative and simple regret minimization and outperforms UCT. We also develop a sampling scheme loosely based on a myopic version of perfect value of information. Finite-time and asymptotic analysis of the policies is provided, and the algorithms are compared empirically.
---
PDF链接：
https://arxiv.org/pdf/1108.3711

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：蒙特卡罗 蒙特卡 Minimization Intelligence Presentation algorithm 应用 旨在 最小化 方案