New Direction Speaker: Retsef Levi
Retsef Levi, Professor of Operations Management, CoDirector of Leaders for Global Operations (LGO) Program, MIT Sloan School of Management
Date: Thursday, Feb 4, 2015, 12:15 to 1:15 pm
Location: Stanford University, Skilling 193
Exploration vs. Exploitation: Reducing Uncertainty in Operational Problems
Abstract: Motivated by several core operational applications, we introduce a new class of multistage stochastic optimization models that capture a fundamental tradeoff between performing work and making decisions under uncertainty (exploitation) and investing capacity (and time) to reduce the uncertainty in the decision making (exploration). Unlike existing models, in which the exploration-exploitation tradeoffs typically relate to learning the underlying distributions, the models we introduce assume a known probabilistic characterization of the uncertainty, and focus on the tradeoff of learning (or partially learning) the exact realizations.
For several interesting scheduling models we derive insightful structural results on the optimal policies that lead not only to quantification of the value of learning, but also obtain surprising optimal local decision rules for when it is optimal to explore (learn). We then generalize the results to a broad class of fundamental stochastic combinatorial optimization problems captured by polymatroids.
The talk is based on two papers that are joint work with Chen Atias, Tom Magnanti, Robi Krauthgamer and Yaron Shaposhnik.
Provably Near Optimal Algorithms for Dynamic Assortment Problems
