Cornell University

ORIE Colloquium: Mark E. Lewis (Cornell ORIE) - Uniform turnpike theorems for finite Markov decision processes

Tuesday, September 26, 2017 at 4:15pm

Frank H. T. Rhodes Hall, 253

A turnpike integer is the smallest finite horizon for which an optimal infinite horizon decision is the optimal initial decision. An important practical question considered in the literature is how to bound the turnpike integer using only the problem inputs. In this talk, we consider turnpike integers as a function of the discount factor. While a turnpike integer is finite for any fixed discount factor, we show that it approaches infinity in the neighborhood of a specific set of discount rates (for all but some exceptional finite Markov decision processes). We completely characterize this taboo set of discount factors and find necessary and sufficient conditions for a set of turnpike integers to be unbounded. This finding provides a cautionary tale for practitioners using point estimates of the discount factor to manage the length of rolling horizons by pointing to potential singularities in the procedure.



Professor Lewis received his Ph.D. in 1998 from the School of Industrial and Systems Engineering at Georgia Tech. After a postdoctoral fellowship at the University of British Columbia, he joined the faculty of Industrial and Operations Engineering at the University of Michigan. In 2005, he moved to the School of Operations Research and Information Engineering at Cornell. He is the recipient of multiple awards including an honorable mention for the Dantzig Dissertation Prize and the Presidential Early Career Award for Scientists and Engineers (PECASE).

Dr. Lewis’s research interests fall squarely in the area of dynamic decision-making, but with broad application areas. On the theory side, he has considered such topics as sensitive optimality criteria, convergence of discounted cost models to average cost models and turnpike theory. While most of the applications he considers are connected to queueing control (broadly speaking), he has also considered models in transportation, inventory, and medical services.

Event Type



College of Engineering, Operations Research and Information Engineering


engineering, operations research, orie, College of Engineering



Mark E. Lewis

Speaker Affiliation

School of Operations Research and Information Engineering, Cornell University

Google Calendar iCal Outlook

Recent Activity