markov decision processes

A New Complexity Result on Solving the Markov Decision Problem

  • Yinyu Ye
    • Categories Linear Programming Tags , ,

    We present a new complexity result on solving the Markov decision problem (MDP) with $n$ states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that, when the discount factor $\theta$ is strictly less than $1$, the problem can be solved in … Read more

    Aggregation in Stochastic Dynamic Programming

  • Marina A. Epelman
  • Theodore Lambert
  • Robert L. Smith
    • Categories Dynamic Programming Tags , ,

    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 … Read more