Sensitivity-based nested partitions for solving finite-horizon Markov decision processes

Research output: Contribution to journalArticlepeer-review


In this paper, we propose a heuristic for solving finite-horizon Markov decision processes. The heuristic uses the nested partitions (NP) framework to guide an iterative search for the optimal policy. NP focuses the search on certain promising subregions, flexibly determined by the sampling weight of each action branch. Within each subregion, an effective local policy optimization is developed using sensitivity-based approach, which optimizes the sampling weights based on estimated gradient information. Numerical results show the effectiveness of the proposed heuristic.

Original languageEnglish (US)
Pages (from-to)481-487
Number of pages7
JournalOperations Research Letters
Issue number5
StatePublished - Sep 2017

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics


  • Approximate dynamic programming
  • Markov decision processes
  • Nested partitions
  • Sensitivity-based approach


Dive into the research topics of 'Sensitivity-based nested partitions for solving finite-horizon Markov decision processes'. Together they form a unique fingerprint.

Cite this