Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
We present a novel algorithm that efficiently computes near-optimal deterministic policies for constrained reinforcement learning (CRL) problems. Our approach combines three key ideas: (1) value-demand augmentation, (2) action-space approximate dynamic programming, and (3) time-space rounding. Our algorithm constitutes a fully polynomial-time approximation scheme (FPTAS) for any time-space recursive (TSR) cost criteria. A TSR criteria requires the cost of a policy to be computable recursively over both time and (state) space, which includes classical expectation, almost sure, and anytime constraints. Our work answers three open questions spanning two long-standing lines of research: polynomial-time approximability is possible for 1) anytime-constrained policies, 2) almost-sure-constrained policies, and 3) deterministic expectation-constrained policies.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision Makingreinforcement-learningReinforcement LearningSimilar Papers 제목 키워드 기반
Polynomial-Time Approximability of Constrained Reinforcement Learning
We study the computational complexity of approximating general constrained Markov decision processes. Our primary contribution is the design of a polynomial time $(0,\epsilon)$-additive bicriteria approximation algorithm…
reinforcement-learningReinforcement LearningAnytime-Constrained Reinforcement Learning
We introduce and study constrained Markov Decision Processes (cMDPs) with anytime constraints. An anytime constraint requires the agent to never violate its budget at any point in time, almost surely. Although Markovian …
reinforcement-learningReinforcement LearningA Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions
The fixed-horizon constrained Markov Decision Process (C-MDP) is a well-known model for planning in stochastic environments under operating constraints. Chance-Constrained MDP (CC-MDP) is a variant that allows bounding t…
Explicit Explore, Exploit, or Escape ($E^4$): near-optimal safety-constrained reinforcement learning in polynomial time
In reinforcement learning (RL), an agent must explore an initially unknown environment in order to learn a desired behaviour. When RL agents are deployed in real world environments, safety is of primary concern. Constrai…
Reinforcement Learning (RL)Near-Optimal Reinforcement Learning for Constrained Recurrence Objectives
Recurrence objectives, where a target region must be visited infinitely often, are a fundamental class of specifications for Markov decision processes (MDPs) and form the core of $ω$-regular and linear temporal logic (LT…
Reinforcement Learning