REVIEW 2 cited by
Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original abstract
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.
Forward citations
Cited by 2 Pith papers
-
Polynomial-Time Approximability of Constrained Reinforcement Learning
Constrained MDPs with recursively computable cost criteria admit polynomial-time (0, epsilon)-bicriteria approximations.
-
Unifying and Optimizing Data Values for Selection via Sequential Decision-Making
Data selection is reframed as dynamic programming over an MDP, existing data values are shown to be myopic linear approximations, and a bipartite coverage surrogate is proposed, but its exact optimality guarantee is unsound.
Discussion (0). Continue with ORCID to comment.