An Optimal Computing Budget Allocation Tree Policy for Monte Carlo Tree Search
We analyze a tree search problem with an underlying Markov decision process, in which the goal is to identify the best action at the root that achieves the highest cumulative reward. We present a new tree policy that optimally allocates a limited computing budget to maximize a lower bound on the probability of correctly selecting the best action at each node. Compared to widely used Upper Confidence Bound (UCB) tree policies, the new tree policy presents a more balanced approach to manage the exploration and exploitation trade-off when the sampling budget is limited. Furthermore, UCB assumes that the support of reward distribution is known, whereas our algorithm relaxes this assumption. Numerical experiments demonstrate the efficiency of our algorithm in selecting the best action at the root.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Stochastic Firefighter Problem
The dynamics of infectious diseases spread is crucial in determining their risk and offering ways to contain them. We study sequential vaccination of individuals in networks. In the original (deterministic) version of th…
Optimal Policy Learning under Budget and Coverage Constraints
We study optimal policy learning under combined budget and minimum coverage constraints. We show that the problem admits a knapsack-type structure and that the optimal policy can be characterized by an affine threshold r…
Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling
In crowd labeling, a large amount of unlabeled data instances are outsourced to a crowd of workers. Workers will be paid for each label they provide, but the labeling requester usually has only a limited amount of the bu…
Decision MakingMarketing Budget Allocation with Offline Constrained Deep Reinforcement Learning
We study the budget allocation problem in online marketing campaigns that utilize previously collected offline data. We first discuss the long-term effect of optimizing marketing budget allocation decisions in the offlin…
Deep Reinforcement LearningMarketingreinforcement-learningReinforcement LearningTRACE: A Unified Rollout Budget Allocation Framework for Efficient Agentic Reinforcement Learning
Reinforcement learning with verifiable rewards (RLVR) is a promising approach for enhancing reasoning and agentic behavior in large language models. However, rollout-intensive policy optimization is often limited by insu…
Reinforcement Learning