Bayesian Exploration for Approximate Dynamic Programming
Ilya O. Ryzhov, Martijn Mes, Warren B. Powell, Gerald van den Berg · Operations Research · 2019
Approximate dynamic programming has been applied to solve large-scale resource allocation problems in many domains, including transportation, energy, and healthcare. The main algorithmic challenge in these applications is to accurately estimate the value of a resource in a certain state (for example, a battery that is half full, or a truck en route to a certain destination). This “value function” must be learned as part of the decision-making process, giving rise to the “exploration/exploitation” challenge: we may, and often should, choose to experiment with seemingly suboptimal actions because they have high potential to be better than we believe. In “Bayesian Exploration for Approximate Dynamic Programming,” Ilya O. Ryzhov, Martijn R. K. Mes, Warren B. Powell and Gerald van den Berg present a principled framework for modeling uncertainty about the value function and measuring the potential of a state to improve a decision-making policy. This method is scalable and performs well in experiments.