Optimal Decision Making via Stochastic Modeling and Machine Learning: Applications to Resource Allocation Problems and Sequential Decision Problems

Abstract

This thesis is about optimal decision making for resource allocation problems and sequential decision problems. There are two parts to this thesis: the first part focuses on developing an optimization framework for the inventory allocation problem in an on-demand rental network. Specifically, we consider a bike-share inventory management problem where the operator of the system must determine a cost-effective inventory allocation to meet the quality of service requirements at each location. The second part focuses on developing a general learning framework for sequential decision problems. Specifically, we consider learning tasks that can be formulated as sequential decision problems, where the decision-maker takes action in every period and hopes to maximize the total expected long-term reward.

For the first part, we propose a bi-level optimization framework for the inventory allocation problems. At the upper level of the framework, we solve the initial inventory allocation problem by determining the optimal inventory allocation that minimizes the total user-dissatisfaction for all stations. At the lower level of the framework, we solve the vehicle routing problem, by determining the cost-effective truck route for repositioning inventories in the system. To demonstrate the practicality of our approach, extensive computational results on the proposed framework and theoretical results on the transient distribution of the bike-share inventory queueing model are also included.

For the second part, we propose a tree-based method for solving sequential decision problems using Monte Carlo Tree Search (MCTS). Our method works by iteratively applying MCTS on small, finite-horizon versions of the original infinite horizon Markov decision process. To demonstrate the efficiency of our approach, we provide the first sample complexity analysis of the batch MCTS-based Reinforcement Learning method and show that with large enough sample sizes and sufficiently large tree search effort, the performance of the estimated policies can be made close to optimal, up to some unavoidable approximation error. Lastly, we tested the neural network implementation of our methods in a challenging video game environment to demonstrate the power of our approach.