Ergodic Annealing

Carlo Baldassi, Fabio Maccheroni, Massimo Marinacci, Marco PirazziniarXiv 2020 · arXiv

Abstract

Traditional optimization algorithms, such as Simulated Annealing, rely on the assumption that the cost of every possible action is known. However, in many real-world scenarios—from network routing to logistics—costs are hidden or stochastic. This paper introduces Ergodic Annealing, a novel framework that solves NP-hard problems when the cost function is unknown and must be learned through experience. By replacing the standard Metropolis engine with the reinforcement learning-inspired "Macau Algorithm," the authors demonstrate that an agent can simultaneously learn a landscape and find its global optimum with near-perfect efficiency.

The Challenge of Unknown Costs

In classic combinatorial optimization, a Decision Maker (DM) seeks to minimize a known utility function. In practice, the DM often faces an exploration-exploitation trade-off: they must spend resources to discover the payoffs of different actions while simultaneously trying to select the best one. For instance, a cloud service provider routing data across a network does not know the exact latency of a path until data is actually transmitted.

Figure 1: A comparison between traditional optimization with known edge weights (left) and the problem addressed here, where costs are unknown and represented by question marks (right).

Methodology: From Metropolis to Macau

The researchers propose a two-step evolution of the classic Simulated Annealing (SA) algorithm:

  1. The Macau Algorithm: This variation of the Metropolis Algorithm does not require a fixed utility function. Instead, it maintains a running empirical average of the payoffs observed each time it visits a state. Decisions to transition to new states are based on these current best estimates.
  2. Ergodic Annealing: This applies a "temperature" schedule to the Macau Algorithm. Just as SA gradually narrows its focus from broad exploration to local exploitation, Ergodic Annealing cools the system to freeze the agent into an optimal configuration as its knowledge of the landscape improves.

The core of this approach is the Ergodic Conjecture. The authors posit that despite the agent's imperfect and constantly changing knowledge, the long-run frequency of the states visited will eventually converge to the same optimal distribution as if the costs were known from the start.

Empirical Performance

The algorithm was benchmarked against two classic NP-hard problems: the Directed Steiner Tree (DST) and the Traveling Salesman Problem (TSP).

In the DST experiments, Ergodic Annealing reached the exact same final configuration as the "all-knowing" Simulated Annealing in 32.2% of cases, with an average cost difference of only 4.66%. In the TSP benchmarks, the performance was even more striking: Ergodic Annealing performed at least as well as standard SA on 99.5% of the test graphs, with an average absolute deviation of only 1.90%.

Figure 2: Visual comparison of the optimal "backbone" paths identified by traditional Simulated Annealing (left) and Ergodic Annealing (right). The paths are nearly identical despite the latter starting with zero knowledge.

Key Insights and Future Work

A significant finding is the Efficiency of Ignorance: the agent does not need to map the entire landscape to find the global optimum. It only needs to accurately estimate the payoffs of the most promising alternatives. This allows the algorithm to focus its learning efforts where they matter most, significantly speeding up the search process compared to pure statistical mapping.

While the results are robust, future work remains to provide a rigorous mathematical proof for the Ergodic Conjecture across all classes of cost functions. Additionally, scaling the algorithm to extremely high-dimensional spaces or environments with high variance in payoffs may require more sophisticated annealing schedules to prevent the system from "freezing" into sub-optimal states too early.

Summary updated

Abstract

Simulated Annealing is the crowning glory of Markov Chain Monte Carlo Methods for the solution of NP-hard optimization problems in which the cost function is known. Here, by replacing the Metropolis engine of Simulated Annealing with a reinforcement learning variation -- that we call Macau Algorithm -- we show that the Simulated Annealing heuristic can be very effective also when the cost function is unknown and has to be learned by an artificial agent.
BibTeX
@misc{baldassi2020ergodic,
  author = {Carlo Baldassi and Fabio Maccheroni and Massimo Marinacci and Marco Pirazzini},
  title = {{Ergodic Annealing}},
  year = {2020},
  eprint = {2008.00234},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2008.00234},
}
Figure