Reinforcement Learning with Almost Sure Constraints

2021-12-09 · Agustin Castellano, Hancheng Min, Juan Bazerque, Enrique Mallada

In this work we address the problem of finding feasible policies for Constrained Markov Decision Processes under probability one constraints. We argue that stationary policies are not sufficient for solving this problem, and that a rich class of policies can be found by endowing the controller with a scalar quantity, so called budget, that tracks how close the agent is to violating the constraint. We show that the minimal budget required to act safely can be obtained as the smallest fixed point of a Bellman-like operator, for which we analyze its convergence properties. We also show how to learn this quantity when the true kernel of the Markov decision process is not known, while providing sample-complexity bounds. The utility of knowing this minimal budget relies in that it can aid in the search of optimal or near-optimal policies by shrinking down the region of the state space the agent must navigate. Simulations illustrate the different nature of probability one constraints against the typically used constraints in expectation.

📄 PDF Abstract BibTeX arXiv:2112.05198

Code (0)

등록된 구현이 없습니다.

Tasks

Navigatereinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Saute RL: Almost Surely Safe Reinforcement Learning Using State Augmentation

2022-02-14 · Aivar Sootla, Alexander I. Cowen-Rivers, Taher Jafferjee, Ziyan Wang 외

Satisfying safety constraints almost surely (or with probability one) can be critical for the deployment of Reinforcement Learning (RL) in real-life applications. For example, plane landing and take-off should ideally oc…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Safe Reinforcement Learning

Assured RL: Reinforcement Learning with Almost Sure Constraints

2020-12-24 · Agustin Castellano, Juan Bazerque, Enrique Mallada

We consider the problem of finding optimal policies for a Markov Decision Process with almost sure constraints on state transitions and action triplets. We define value and action-value functions that satisfy a barrier-b…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time

2024-05-23 · Jeremy McMahan

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) …

Decision Making reinforcement-learning Reinforcement Learning

Polynomial-Time Approximability of Constrained Reinforcement Learning

2025-02-11 · Jeremy McMahan

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-learning Reinforcement Learning

Stochastic Minimum-Cost Reach-Avoid Reinforcement Learning

2026-05-12 · Jingduo Pan, Taoran Wu, Yiling Xue, Bai Xue arxiv

We study stochastic minimum-cost reach-avoid reinforcement learning, where an agent must satisfy a reach-avoid specification with probability at least $p$ while minimizing expected cumulative costs in stochastic environm…

Reinforcement Learning