Ergodic Annealing
This addresses optimization problems for domains where cost functions are unknown, though it appears incremental as it modifies an existing heuristic.
The paper tackles optimization problems with unknown cost functions by replacing Simulated Annealing's Metropolis engine with a reinforcement learning variant called the Macau Algorithm, showing it can be effective in such scenarios.
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.