Skip to content
conftrace_
2022 AAAI AAAI 2022

A Provably-Efficient Model-Free Algorithm for Infinite-Horizon Average-Reward Constrained Markov Decision Processes

Abstract

Abstract This paper presents a model-free reinforcement learning (RL) algorithm for infinite-horizon average-reward Constrained Markov Decision Processes (CMDPs). Considering a learning horizon K, which is sufficiently large, the proposed algorithm achieves sublinear regret and zero constraint violation. The bounds depend on the number of states S, the number of actions A, and two constants which are independent of the learning horizon K.

🌉 Interdisciplinary Bridge - Artificial Intelligence and Mathematics & Optimization and Reinforcement Learning
🐣 Hot Topic Early Bird - sublinear regret

Authors

Honghao Wei, Xin Liu, Lei Ying

Topics

Machine Learning > Optimization & Theory > Learning Theory Reinforcement Learning > Methods > Policy Learning Machine Learning > Learning Types > Reinforcement Learning Mathematics & Optimization > Optimization > Optimization

Keywords

constrained markov decision process sublinear regret average reward model-free reinforcement learning constraint violation constrained mdp model-free algorithm infinite horizon
Download PDF

More from AAAI 2022

All AAAI 2022 papers →
Real-Time Driver-Request Assignment in Ridesourcing
Encoding Multi-Valued Decision Diagram Constraints as Binary Constraint Trees
Sample Average Approximation for Stochastic Optimization with Dependent Data: Performance Guarantees and Tractability
TextHoaxer: Budgeted Hard-Label Adversarial Attacks on Text
Two Compacted Models for Efficient Model-Based Diagnosis
Parameterized Approximation Algorithms for K-center Clustering and Variants