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

Solution returned: probability distribution over deterministic policies

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

Solution returned: stochastic policy

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

Solution returned: stochastic policy

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 resource constraint violation probability is (empirically) bounded by a given parameter alpha. The algorithm uses either Column Generation or the CMDP linear program as a subroutine, which have been discussed above.

Class: algorithms.mdp.dynamicrelaxation.DynamicRelaxation

Supported constraints: budget, instantaneous

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

Solution returned: probability distribution over deterministic policies (with column generation), stochastic policy (with CMDP linear program)

Partially Observable Markov Decision Processes

explain input and output

CGCP

The Column Generation algorithm for Constrained POMDPs (CGCP) proposed by Walraven and Spaan (2018) enhances the scalability of the original column generation algorithm by integrating tailored approximate POMDP algorithms. The algorithm uses point-based value iteration to generate the policies, and these policies are converted to a finite state controller before the corresponding column is added to the linear program. Similar to the MDP variant of the algorithm, which we discussed above, CGCP derives a probability distribution over policies from the linear program, which it returns as a solution.

Class: algorithms.pomdp.cgcp.CGCP

Supported constraints: budget

Parameters: tolerance which is used to determine whether the dual prices of the linear program have converged, time limit subproblem solver, amount of time by which time limit subproblem solver is increased upon convergence, minimum number of iterations required with an objective increase before increasing time limit subproblem solver

Solution returned: probability distribution over deterministic policies

CALP

The Constrained Approximate Linear Programming (CALP) algorithm by Poupart et al. (2015) formulates a Constrained POMDP as a Constrained MDP defined in terms of belief states rather than states. The algorithm searches iteratively for additional beliefs, which it uses to expand the Constrained MDP model. This model is solved using the standard linear program for Constrained MDPs, as discussed above.

Class: algorithms.pomdp.calp.FiniteCALP

Supported constraints: budget

Parameters: maximum number of new beliefs added in an iteration, maximum number of iterations, tolerance on reachability probability for the belief search

Solution returned: stochastic finite state controller

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).
• Walraven, E., & Spaan, M. T. J. (2018). Column Generation Algorithms for Constrained POMDPs. Journal of Artificial Intelligence Research, 62, 489–533.
• Poupart, P., Malhotra, A., Pei, P., Kim, K.E., Goh, B., & Bowling, M. (2015). Approximate Linear Programming for Constrained Partially Observable Markov Decision Processes. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (pp. 3342–3348).