Markov Decision Problem and Linear Programming

Stanford University, Stanford CA

Investigators

Abstract

The aim of this proposal is to further develop the complexity theory of Linear Programming (LP), which continually plays a central role in complexity analysis. In particular, we analyze the Markov Decision Problem (MDP) with n states and m actions for each state, a special class of real-number linear programs with the Leontief matrix structure. The research objectives and activities include the following: 1) Develop a new class of algorithms, "combinatorial interior-point algorithms", for solving the MDP, with the best achievable complexity result and practical efficiency; and establish certain complexity lower bounds for the MDP, which may provide a "negative result" on the quest for whether or not there is a strongly polynomial time algorithm for LP. 2) Both undergraduate and graduate students will participate in the project, new course materials on the MDP will be produced, and the PI will also give presentations to the Stanford Summer Program for grades K-12 and community college students in the Bay Area. 3) Apply the new fast MDP algorithm to research activities in function areas such as Call Admission and Routing, Strategic Asset Allocation, Supply- Chain Management, Emissions Reductions, and Semiconductor Wafer Fabrication. Due to the relentless research effort in LP algorithms, a linear program can be solved today one million times faster than it was done twenty years ago. Businesses, large and small, use linear programming models to optimize communication systems, to schedule transportation networks, to control inventories, to plan investments, and to maximize productivity. Furthermore, LP has become a popular subject now taught in undergraduate, graduate, and MBA curriculums, advancing human knowledge and promoting scientific understanding. Recently, there has been a renewed and strong interest in the MDP (a special large-scale LP) due to its wide applications. With the rising demand in telecommunication network resources, effective management is as important as ever. Call Admission (deciding which calls to accept/reject) and routing (allocating links in the network to particular calls) are examples of decisions that must be made at any point in time. The objective is to make the "best" use of limited network resources. Such sequential decision problems can be addressed by a dynamic programming model and the MDP. Another application: the threat of global warming that may result from the accumulation of carbon dioxide and other "greenhouse gases" poses a serious dilemma. In particular, cuts in emission levels bear a detrimental short-term impact on economic growth. At the same time, a depleting environment can severely hurt the economy - especially the agricultural sector - in the longer term. To complicate the matter further, scientific evidence on the relationship between emission levels and global warming is inconclusive, leading to uncertainty about the benefits of various cuts. One systematic approach to considering these conflicting goals involves the formulation of a dynamic system and MDP model that describes our understanding of economic growth and environmental science, as is done by Nordhaus. However, these MDP problems are too complex to be solved by the current MDP solvers. A major objective of the project is to develop new Markov Decision Algorithms such that these models would be effectively analyzed to satisfaction. Progress in the area of developing efficient algorithms for solving large-scale stochastic decision problems will be of great significance in improving industrial competitiveness, scientific understanding, and technology learning.