-
Notifications
You must be signed in to change notification settings - Fork 6
Efficient and Scalable Multi Stage Decision Making in R
Sequential decision-making problems arise naturally in a wide range of real-world tasks, such as robot control, game play, and healthcare. Consider the clinical trial design as an example. In designing the trials, we need to balance the statistical power and the total cost, which are conflicting. Such a conflict is even more complicated in personalized medicine and adaptive trial design, since multiple subpopulations and states are involved in the decision making. Recently, [1] provides a general approach to formulate sequential decision-making problems with Bayes risk constraints as sparse Linear Programming (LP) problems. As a special example, [1] formulates the two-stage and two-subpopulation adaptive trial design problem as a sparse LP problem, and solves it by commercial solvers, e.g., Gurobi. The resulting designs substantially outperform existing benchmarks. In various broader applications, it is often the case that the decision-making problem involves far more than two stages and two subpopulations. This can make the current approach computationally intensive or even infeasible, since the problem size grows exponentially as the number of subpopulations or stages increases. This project aims to develop new customized algorithms and R packages for sequential decision-making problems with three key features: 1). It provides a highly efficient solver to tackle an important class of large-scale LP problems; 2). It provides a solution for sequential decision-making problems with Bayes risk constraints; 3). It provides additional functions including visualization of the optimal decision maps.
Solving LP problems is of central importance in operations research, statistics, and computer science. There are mainly two classes of practical algorithms for solving LP problems, namely, the interior-point method [2] and the simplex method. Interior-point method enjoys a polynomial time convergence, and the iteration complexity cubically depends on the problem size. However, it does not scale with our problem size, where the dimension of the problem can be millions by millions. In contrast, the worst-case iteration complexity of the simplex method grows exponentially depending on the problem size. It is indeed highly efficient in practice, since the worst cases are hardly encountered. The two aforementioned methods are both designed for general LP problems, which cannot take our specific problem structures into consideration. In fact, our class of LP problems is highly sparse and well structured. We propose to solve the nonsmooth dual problem and exploit the dual sparsity. Our preliminary results show that this approach substantially improves the computational efficiency, and achieves the solvability for more sophisticated problems that were previously regarded as unsolvable.
We aim to develop an efficient R package for a class of large-scale LP-based sequential decision-making problems. The package has two key components: 1). A customized optimization engine for sequential decision-making problems. The optimization engine will be written in C++ that solves our class of LP problems efficiently. This engine will be optimized for our large-scale sparse LP problems. In particular, in solving the nonsmooth dual problem, we will develop a specialized algorithm framework with iterative subspace optimization and row generation phases that are particularly efficient for our problems. 2). A user-friendly interface, where the user could specify his/her requirement and objective. In addition, we will provide a visualization function for visualizing the optimal decision map.
The delivered R packages will provide an efficient tool that can solve a wide class of sequential decision-making problems with Bayes risk constraints. It will be the first R package that solves this broad class of problems. Furthermore, it will potentially help pharmaceutical companies significantly decrease the huge cost of clinical trials and thus accelerate new drug discoveries, which can be potentially beneficial to the control of the COVID-19 pandemic.
Evaluating Mentor: Ethan Fang (Assistant Professor, Penn State University, [email protected]), which is an expert of sequential decision making. He served as a GSOC mentor in 2020 and supervised the project "R Library for Multi-Stage Adaptive Enrichment Design". The package is now at the final stage of testing, and the GitHub repo can be found at https://github.com/cliang1453/maed.
The other mentor is Tuo Zhao (Assistant Professor, Georgia Tech, [email protected]), which is an expert of developing statistical software. He was the GSOC student developer in 2010-2012, and served as the mentor in 2013-2020. He has developed popular R packages for statistical machine learning such as huge (https://cran.r-project.org/web/packages/huge/index.html), Picasso (https://cran.r-project.org/web/packages/picasso/index.html) and flare (https://cran.r-project.org/web/packages/flare/index.html). The number of downloads of his packages in the past five years is over 500,000.
Students, please do one or more of the following tests before contacting the mentors above.
Easy: Based on [1], implement an optimal adaptive trial design using existing LP solvers in R. Test it on a small size problem.
Medium: Add some Bayes risk constraints and increase the problem size.
Hard: Since the core code should be implemented in C/C++. Write a simple package implementing Matrix multiplication. The main code should use C/C++.
[1] Rosenblum M, Fang E, Liu H. Optimal, two-stage, adaptive enrichment designs for randomized trials using sparse linear programming, 2017.
[2] Mehrotra S. On the implementation of a primal-dual interior point method. SIAM Journal on optimization, 1992, 2(4): 575-601.
Students, please post a link to your test results here.
- Student name: Minshuo Chen, test_results.