蒙特卡洛树搜索UCB公式中包含对数与平方根的设计原因是什么

UCB（置信上界）公式的标准形式为：
UCB = Q(s,a) + c * sqrt( ln(N(s)) / N(s,a) )
其中Q(s,a)是动作a的平均历史收益，c是探索系数，N(s)是当前父节点s的总访问次数，N(s,a)是动作a被选中的次数。
两个项的设计都来自多臂赌博机问题的理论推导，核心目的是平衡探索（试未被充分选择的动作）和利用（选当前看起来收益最高的动作），保证算法最终能收敛到最优策略：

平方根项的作用 #

平方根项的理论基础是霍夫丁不等式（Hoeffding's Inequality），该不等式给出了样本均值和真实期望的偏差上界：对于取值范围在[0,1]的随机变量，采样n次后，样本均值和真实值的偏差超过阈值的概率，和1/√n成正比。
这个项的直观意义非常明确：

• 当某个动作a被选中的次数N(s,a)越少，我们对它的真实收益估计越不准，平方根项的值就越大，公式会给这个动作更高的优先级，鼓励去探索它的真实收益。
• 当动作a被选中的次数足够多时，平方根项会逐渐趋近于0，算法会主要参考平均收益Q(s,a)来做选择，进入利用阶段。

对数项的作用 #

对数项里的N(s)是当前父节点的总访问次数，设计成对数形式有两个核心原因：

1. 避免探索权重增长过快：如果用线性的N(s)代替ln(N(s))，探索项会随着总访问次数的增加快速膨胀，导致算法后期始终在探索，没法收敛到最优动作。对数是增长极慢的函数，保证总访问量很高的时候，探索项也不会过度影响选择。
2. 保证理论收敛性：多臂赌博机的理论证明中，只有用对数项才能保证算法的累积遗憾（和一直选最优动作的收益差）是次线性增长的，也就是当总尝试次数趋近于无穷时，算法选中次优动作的概率会趋近于0，最终一定能找到最优动作。如果去掉对数项或者换成其他增长更快的函数，都没法满足这个收敛要求。

内容的提问来源于stack exchange，提问作者Marco Romano