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 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. The algorithm derives a probability distribution over deterministic policies using this linear program, which it eventually returns as a solution.

Class: algorithms.mdp.colgen.ColGenFiniteHorizon

Supported constraints: budget, instantaneous

Parameters: tolerance which is used to determine whether the dual prices of the linear program have converged

CMDP linear program

The linear program for Constrained MDPs defines a stochastic policy which represents a conditional preallocation. The algorithm itself only initializes the linear program, and derives the stochastic policy from the solution after solving the linear program. More information about linear programs for Constrained MDPs can be found in a book by Altman (1999).

Class: algorithms.mdp.constrainedmdp.ConstrainedMDPFiniteHorizon

Supported constraints: budget, instantaneous

Parameters: none

Deterministic preallocation

The deterministic preallocation algorithm in the toolbox uses the same linear program as discussed above, except that it introduces additional binary variables to enforce that resource constraints are never violated. Similar variables have been used in algorithms by Wu and Durfee (2010) and De Nijs et al. (2018).

Class: algorithms.mdp.deterministicpreallocation.DPFiniteHorizon

Supported constraints: budget, instantaneous

Parameters: none

Dynamic relaxation

The dynamic constraint relaxation algorithm proposed by De Nijs et al. (2017) is a hybrid algorithm that bridges the gap between conditional preallocation methods and deterministic preallocation methods. Rather than enforcing that resource constraints are respected at all times, the algorithm computes a solution for which the (empirical) resource constraint violation probability is bounded by a given parameter alpha.

Class: algorithms.mdp.dynamicrelaxation.DynamicRelaxation

Supported constraints: budget, instantaneous

Parameters: tolerance on constraint violation probability (alpha), factor used for constraint relaxation (beta)

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.
• Altman, E. (1999). Constrained Markov Decision Processes. CRC Press.
• Wu, J., & Durfee, E. H. (2010). Resource-Driven Mission-Phasing Techniques for Constrained Agents in Stochastic Environments. Journal of Artificial Intelligence Research, 38, 415–473.
• De Nijs, F., Spaan, M. T. J., & De Weerdt, M. M. (2018). Preallocation and Planning under Stochastic Resource Constraints. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (pp. 4662–4669).
• De Nijs, F., Walraven, E., De Weerdt, M. M., & Spaan, M. T. J. (2017). Bounding the Probability of Resource Constraint Violations in Multi-Agent MDPs. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (pp. 3562–3568).