Semi-Infinitely Constrained Markov Decision Processes and Provably Efficient Reinforcement Learning.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Operations Research

Background:

• Constrained Markov Decision Processes (CMDPs) are widely used for sequential decision-making under constraints.
• Existing CMDP frameworks typically handle a finite number of constraints, limiting their applicability.
• There is a need for methods that can address decision-making problems with a continuum of constraints.

Purpose of the Study:

• To introduce a novel generalization of CMDPs called semi-infinitely constrained Markov decision processes (SICMDPs).
• To develop and analyze two new reinforcement learning algorithms, SI-CMBRL and SI-CPO, tailored for SICMDPs.
• To demonstrate the efficacy of these algorithms in solving complex control tasks.

Main Methods:

• Developed SI-CMBRL, a model-based reinforcement learning algorithm that transforms SICMDPs into linear semi-infinitely programming (LSIP) problems.
• Developed SI-CPO, a policy optimization algorithm employing cooperative stochastic approximation for policy updates.
• Applied techniques from semi-infinitely programming (SIP) to constrained reinforcement learning for the first time.

Main Results:

• Provided theoretical analysis for SI-CMBRL and SI-CPO, including iteration and sample complexity.
• Conducted extensive numerical experiments validating the SICMDP model.
• Demonstrated the capability of SI-CMBRL and SI-CPO to solve complex control tasks using deep reinforcement learning.

Conclusions:

• SICMDPs offer a powerful framework for decision-making with continuous constraints.
• The proposed algorithms SI-CMBRL and SI-CPO are effective and theoretically sound for solving SICMDPs.
• This work pioneers the application of semi-infinitely programming in constrained reinforcement learning.