LA-MCTS：利用蒙特卡洛树搜索学习黑盒优化的搜索空间划分

论文原文：Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search

LA-MCTS

高维黑盒优化有广泛的应用场景，但仍然是一个难以解决的挑战性问题。这类问题的目标是在没有显式公式的情况下，找到函数 $f(x)$ 的最大值 $x^*$。

核心挑战有：

1. 传统的贝叶斯优化在高维空间（ $>20$ 维）中效率极低，且容易在搜索空间的边界进行无效的过度探索。
2. 简单的贪婪搜索策略容易陷入局部最优解。
3. 对搜索空间静态划分（如均匀切分）不依赖于目标函数的实际分布，不够智能。

因此本文提出了 LA-MCTS,这是一种元算法，旨在解决高维优化问题。
主要思路：

1. 学习划分
   • 不使用固定规则，而是根据样本数据学习如何划分空间。
   • 使用 SVM 学习非线性的决策边界。
2. 树搜索
   • 使用蒙特卡洛树搜索来平衡探索（去未知区域）和利用（去高分区域）。
   • 动态选择最有希望的子区域。
3. 局部采样
   • 在选定的叶子节点（小区域）内，使用现有的优化器（如 TuRBO 或 BO）进行精细搜索。

搜索过程

算法通过迭代构建搜索树，初始全部配置空间构成树的根节点。

1. 检查当前的搜索树。如果某个叶子节点（区域）里积累的样本数量超过了一个阈值 $\theta$，说明这个区域需要被细分了。

2. 生成潜在动作。在这个节点包含的所有样本 $(x, f(x))$ 中，根据函数值 $f(x)$ 将它们聚类成“好”（高值）和“坏”（低值）两堆。训练一个 SVM 分类器来区分这两堆样本。SVM 画出一条非线性边界作为切分边界。

3. 执行分裂：
   父节点分裂为左右两个子节点。选择一个 $\operatorname{ucb}$ 值较大的节点。

4. 采样与反向传播 ：直到确定一个足够小的搜索区域，使用 TuRBO 或 BO 进行采样，利用获得的函数真实值进行反向传播，更新叶子节点到根节点路径上的 $n_j$ 和 $v_j$ 。

反复执行这个递归过程（每次都从根节点开始），直到搜索次数或者搜索时间达到预设上限，或者达到满意的分数时，停止并报告当前的最优解。

UCB (Upper Confidence Bound)

$\operatorname{ucb}$ （置信区间上界）是统计学和强化学习（特别是多臂老虎机问题和蒙特卡洛树搜索）中用来解决 “探索与利用” 两难困境的一种经典算法策略，具体地，

$$\operatorname{ucb}_j = \frac{v_j}{n_j} + 2C_p \sqrt{\frac{2\log(n_p)}{n_j}}$$

其中：

• $\frac{v_j}{n_j}$：代表利用。即该节点目前的平均表现（平均函数值）。
• 后面带根号的项：代表探索。$n_j$ 是该节点被访问的次数，$n_p$ 是父节点的访问次数。如果一个节点被访问得很少（$n_j$ 很小），这一项的值就会很大，从而提高该节点的得分。
• $C_p$：这是一个超参数，用来控制探索的程度。

SVM （支持向量机）

SVM 的目标是找到一个超平面 $w^\top x+b=0$ 将两类数据分开。

定义数据为 $(x,y)$ ，$x$ 为空间中的一个点，$y$ 根据数据的分类取值为 $1$ 或 $-1$ 。我们利用一个二次规划算法找出用来拟合边界的点（支持向量）。这些点的 $\alpha_i>0$，它们通常更加靠近划分的边界。

非线性边界的情况下可以使用核技巧来升维，研究中使用了径向基函数核 (RBF Kernel) $K(x, y) = \exp(-\gamma ||x - y||^2)$ ，这是最常用也最强大的核函数，可以拟合出任意复杂形状的边界，例如环形、不规则形状等，本质相当于把向量升维到了无限维的空间里。

训练好 SVM 之后，我们有这样一个公式为这个点打分：

$$f(x_{new}) = \sum_{i=1}^{n} (\alpha_i \cdot y_i \cdot K(x_i, x_{new})) + b$$

$Score$ 的正负性即为我们分类的结果。