Optimization Online


Aggregation in Stochastic Dynamic Programming

Theodore Lambert (tlambert***at***tmcc.edu)
Marina Epelman (mepelman***at***umich.edu)
Robert L. Smith (rlsmith***at***umich.edu)

Abstract: We present a general aggregation method applicable to all finite-horizon Markov decision problems. States of the MDP are aggregated into macro-states based on a pre-selected collection of “distinguished” states which serve as entry points into macro-states. The resulting macro-problem is also an MDP, whose solution approximates an optimal solution to the original problem. The aggregation scheme also provides a method to incorporate inter-period action space constraints without loss of the Markov property.

Keywords: Markov Decision Problems, Dynamic Programming, Aggregation

Category 1: Other Topics (Dynamic Programming )

Citation: Technical Report 04-07, University of Michigan, Industrial and Operations Engineering, 1205 Beal Ave., Ann Arbor, MI 48105, July 2004

Download: [PDF]

Entry Submitted: 08/01/2004
Entry Accepted: 08/05/2004
Entry Last Modified: 08/01/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society