Response-Adaptive Resource Allocation With Many Treatments

Abstract

We study a sequential decision-making problem in which a decision maker allocates shared resources across multiple treatments over a finite horizon based on the decision maker’s beliefs about each treatment’s performance, with the goal of maximizing the expected total reward. The belief about each treatment’s performance is updated with the realized reward in each period, fitting the problem into a generalized multi-armed bandit model. Some applications of this problem include clinical trials, training of artificial intelligence models, online marketing, and production mix optimization, where efficient resource allocation is crucial for maximizing rewards while learning about treatment effectiveness. Such problems are naturally formulated as weakly coupled stochastic dynamic programs (DPs) that are difficult to solve as the state space grows exponentially in the number of treatments. In this dissertation, we use Lagrangian relaxation to characterize an optimal relaxed policy and its feasible version under assumptions on the time frame, prior beliefs, and available resources. We then bound the relative gap between the value of the feasible relaxed policy and the optimal value function, showing that the feasible policy proposed is asymptotically optimal.