标题： 基于强化学习的非局部蒙特卡罗方法 显示英文标题

标题： Nonlocal Monte Carlo via Reinforcement Learning

摘要： 优化组合优化问题的复杂成本函数是一个跨学科和应用领域的长期挑战。 当采用基于马尔可夫链蒙特卡洛（MCMC）的传统算法家族，如模拟退火或并行温度法时，假设输入上的温度分布是均匀的（平衡的）。 这种与实例无关的方法在重叠间隙性质成立时，对于接近计算相变的最难基准测试被证明是无效的。 在这些情况下，传统的MCMC难以解除刚性变量，逃出次优吸引盆地，并采样高质量且多样的解决方案。 为了缓解这些挑战，提出了非平衡非局部蒙特卡洛（NMC）算法，该算法利用不均匀的温度分布，从而在不损害其开发的情况下加速配置空间的探索。 在这里，我们使用深度强化学习（RL）来训练NMC的非局部转移策略，这些策略之前是通过现象学设计的。 我们证明，该求解器仅通过观察配置空间探索的能量变化作为RL奖励，以及局部最小能量景观几何作为RL状态即可进行训练。 我们进一步表明，训练后的策略在残余能量、求解时间和解决方案多样性指标方面优于标准的基于MCMC的和非局部模拟退火方法，在硬均匀随机和无标度随机4-SAT基准测试中表现更佳。 显示英文摘要

摘要： Optimizing or sampling complex cost functions of combinatorial optimization problems is a longstanding challenge across disciplines and applications. When employing family of conventional algorithms based on Markov Chain Monte Carlo (MCMC) such as simulated annealing or parallel tempering, one assumes homogeneous (equilibrium) temperature profiles across input. This instance independent approach was shown to be ineffective for the hardest benchmarks near a computational phase transition when the so-called overlap-gap-property holds. In these regimes conventional MCMC struggles to unfreeze rigid variables, escape suboptimal basins of attraction, and sample high-quality and diverse solutions. In order to mitigate these challenges, Nonequilibrium Nonlocal Monte Carlo (NMC) algorithms were proposed that leverage inhomogeneous temperature profiles thereby accelerating exploration of the configuration space without compromising its exploitation. Here, we employ deep reinforcement learning (RL) to train the nonlocal transition policies of NMC which were previously designed phenomenologically. We demonstrate that the resulting solver can be trained solely by observing energy changes of the configuration space exploration as RL rewards and the local minimum energy landscape geometry as RL states. We further show that the trained policies improve upon the standard MCMC-based and nonlocal simulated annealing on hard uniform random and scale-free random 4-SAT benchmarks in terms of residual energy, time-to-solution, and diversity of solutions metrics.