A Gradient-Aware Search Algorithm for Constrained Markov Decision Processes

Area of Science:

• Operations Research
• Artificial Intelligence
• Control Theory

Background:

• Constrained Markov Decision Processes (CMDPs) are typically solved using convex linear programming (LP).
• Existing methods may require hyperparameter tuning and can be sensitive to initial conditions.

Purpose of the Study:

• To develop a novel, efficient algorithm for solving finite CMDPs.
• To analyze the properties of the dual linear program in CMDPs.
• To compare the proposed algorithm against existing benchmark methods.

Main Methods:

• Proving the piecewise linear convex (PWLC) structure of the dual linear program's objective function in finite CMDPs.
• Developing a two-level gradient-aware search (GAS) algorithm leveraging the PWLC property.
• Applying the GAS algorithm to two constrained stochastic control problems.

Main Results:

• The dual objective function of a finite CMDP is proven to be PWLC with respect to Lagrange multipliers.
• The proposed GAS algorithm converges quickly to the optimal solution for CMDPs.
• GAS demonstrates robustness, being insensitive to the initialization of Lagrange multipliers and requiring no hyperparameter tuning.

Conclusions:

• The GAS algorithm provides a provably optimal and efficient method for solving finite CMDPs.
• The PWLC structure of the dual problem is key to the algorithm's performance.
• GAS offers a significant improvement over traditional methods like binary search and LP-based approaches.