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.
Methodology: From Metropolis to Macau
The researchers propose a two-step evolution of the classic Simulated Annealing (SA) algorithm:
- 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.
- 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%.
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