思想
- 将可能状态转移过程用状态树表示
- 从初始状态开始抽样，逐步扩展树中节点
- 父节点可以利用子节点的模拟结果
- 选择-扩展-模拟-回溯
选择策略
需要考虑：
- 对尚未充分了解的节点的探索
- 对有较大希望节点的利用
UCB
function UCB1
for each 拉杆j:
访问该拉杆并记录收益
end for
while 尚未达到访问次数限制 do:
计算每个拉杆的 UCB1 信心上界 I_j
访问信心上界最大的拉杆
end while
- 是获得回报的均值
- 是访问总次数
- 是该拉杆访问次数
- 为一个超参数
MCTS
每次选择应用 UCB 算法，对选中节点进行扩展（标准 MCTS 一次扩展一个节点），然后进行 rollout，最后将结果回传更新，重复直到时间限制耗尽。
问题
计算复杂度高，方差大，缺少先验知识，探索较为盲目