Algorithms

The toolbox provides a collection of algorithms for Markov Decision Processes and Partially Observable Markov Decision Processes with resource constraints. On this page we provide an overview of the high-level architecture of the algorithms, and we provide information about the specific algorithms that have been implemented.

Markov Decision Processes

explain input and output

Column generation

The column generation algorithm in the class algorithms.mdp.colgen.ColGenFiniteHorizon is a conditional preallocation method which has been introduced by Yost and Washburn (2000). The algorithm iteratively generates policies and adds the corresponding columns to a linear program. This linear program is used to derive a probability distribution over policies, and therefore the solution returned by the algorithm is a probability distribution over deterministic policies. The algorithm supports budget constraints and instantaneous constraints.

CMDP linear program

Deterministic preallocation

Dynamic relaxation

Partially Observable Markov Decision Processes

explain input and output

CGCP

CALP

References

• Yost, K. A., & Washburn, A. R. (2000). The LP/POMDP Marriage: Optimization with Imperfect Information. Naval Research Logistics, 47(8), 607–619.