Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints
arXiv:2003.05555
Abstract
In the optimization of dynamic systems, the variables typically have constraints. Such problems can be modeled as a Constrained Markov Decision Process (CMDP). This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1. We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied. We define the concept of probably approximately correct (PAC) to the proposed PCMDP problem. The proposed algorithm is proved to achieve an -PAC policy when the episode , where and are the number of states and actions, respectively. is the number of epochs per episode. is the number of constraint functions, and . We note that this is the first result on PAC kind of analysis for PCMDP with peak constraints, where the transition dynamics are not known apriori. We demonstrate the proposed algorithm on an energy harvesting problem and a single machine scheduling problem, where it performs close to the theoretical upper bound of the studied optimization problem.
References in corpus (8)
- Trading Regret for Efficiency: Online Convex Optimization with Long Term Constraints
- Power Allocation for Energy Harvesting Transmitter with Causal Information
- Reinforcement Learning with Probabilistic Guarantees for Autonomous Driving
- Exploration-Exploitation in Constrained MDPs
- Constrained Upper Confidence Reinforcement Learning
- Variance Reduction Methods for Sublinear Reinforcement Learning
- A Low Complexity Algorithm with Regret and Constraint Violations for Online Convex Optimization with Long Term Constraints
- Reinforcement Learning of Markov Decision Processes with Peak Constraints