Resource allocation problems in stochastic sequential decision making

In this thesis, we study resource allocation problems that arise in the context of stochastic sequential decision making problems. The practical utility of optimal algorithms for these problems is limited due to their high computational and storage requirements. Also, an increasing number of applications require a decentralized solution. We develop techniques for approximately solving certain class of resource allocation problems that arise in the context of stochastic sequential decision making problems that are computationally efficient with a focus on decentralized algorithms where appropriate. The first resource allocation problem that we study is a stochastic sequential decision making problem with multiple decision makers (agents) with two main features 1) Partial observability Each agent may not have complete information regarding the system 2) Limited Communication - Each agent may not be able to communicate with all other agents at all times. We formulate a Markov Decision Process (MDP) for this problem. The features of partial observability and limited communication impose additional computational constraints on the exact solution of the MDP. We propose a scheme for approximating the optimal Q function and the optimal value function associated with this MDP as a linear combination of preselected basis functions. We show that the proposed approximation scheme leads to decentralization of the agents' decisions thereby enabling their implementation under limited communication. We propose a linear program, ALP, for selecting the parameters for combining the basis functions. We establish bounds relating the approximation error due to the choice of the parameters selected by the ALP with the best possible error given the choice of basis functions.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Civil and Environmental Engineering.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2009

Author dc:creator

• Lakshmanan, Hariharan, 1980-

Advisor dc:contributor.advisor

• Daniela Pucci de Farias and David Simchi-Levi.

• Civil and Environmental Engineering.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/47736

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/47736