Abstract of Learning in Combinatorial Optimization: What and How to Explore

We study a family of sequential decision problems under model uncertainty where, at each period, the decision maker faces an instance of a combinatorial optimization problem. Objective coefficient vectors, unobserved prior to implementation, are random draws from an initially unknown distribution function. By implementing different solutions, the decision maker extracts information about the objective function, but at the same time experiences the value associated with said solutions. In balancing the implied exploration vs. exploitation trade-off the decision maker must resolve the issue of what to explore and how to do so. Our work provides answers to both questions. In particular, we show that efficient data collection involves solving a new class of combinatorial problems, which we refer to as Optimality Cover Problem (OCP). Our main result establishes a fundamental limit on the performance of any admissible policy, which is expressed in terms of the solution to OCP.

Return to Seminars List