Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces

• URL: http://arxiv.org/abs/2502.18655v1
• Date: Tue, 25 Feb 2025 21:32:55 GMT
• Title: Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spaces
• Authors: Amirhossein Roknilamouki, Arnob Ghosh, Ming Shi, Fatemeh Nourzad, Eylem Ekici, Ness B. Shroff,
• Abstract summary: In Reinforcement tasks with constraints, it is important to avoid errors.<n>In this paper, we develop a novel technique to properly resolve the constraints.
• Score: 27.07625013423198
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In Reinforcement Learning (RL), tasks with instantaneous hard constraints present significant challenges, particularly when the decision space is non-convex or non-star-convex. This issue is especially relevant in domains like autonomous vehicles and robotics, where constraints such as collision avoidance often take a non-convex form. In this paper, we establish a regret bound of $\tilde{\mathcal{O}}\bigl(\bigl(1 + \tfrac{1}{\tau}\bigr) \sqrt{\log(\tfrac{1}{\tau}) d^3 H^4 K} \bigr)$, applicable to both star-convex and non-star-convex cases, where $d$ is the feature dimension, $H$ the episode length, $K$ the number of episodes, and $\tau$ the safety threshold. Moreover, the violation of safety constraints is zero with high probability throughout the learning process. A key technical challenge in these settings is bounding the covering number of the value-function class, which is essential for achieving value-aware uniform concentration in model-free function approximation. For the star-convex setting, we develop a novel technique called Objective Constraint-Decomposition (OCD) to properly bound the covering number. This result also resolves an error in a previous work on constrained RL. In non-star-convex scenarios, where the covering number can become infinitely large, we propose a two-phase algorithm, Non-Convex Safe Least Squares Value Iteration (NCS-LSVI), which first reduces uncertainty about the safe set by playing a known safe policy. After that, it carefully balances exploration and exploitation to achieve the regret bound. Finally, numerical simulations on an autonomous driving scenario demonstrate the effectiveness of NCS-LSVI.

Related papers

• Achieving Constant Regret in Linear Markov Decision Processes [57.34287648914407]
  We introduce an algorithm, Cert-LSVI-UCB, for misspecified linear Markov decision processes (MDPs)<n>We show that Cert-LSVI-UCB has a cumulative regret of $tildemathcalO(d3H5/Delta)$ with high probability, provided that the misspecification level $zeta$ is below $tildemathcalO(Delta / (sqrtdH2))$.
  arXiv  Detail & Related papers  (2024-04-16T17:23:19Z)
• Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration [20.630973009400574]
  We study safe Reinforcement Learning (safe RL) with linear function approximation and under hard instantaneous constraints. Our proposed algorithm, LSVI-AE, achieves $tildecO(sqrtd3H4K)$ hard constraint violation when the cost function is linear and $cO(Hgamma_K sqrtK)$ hard constraint violation when the cost function belongs to RKHS.
  arXiv  Detail & Related papers  (2023-12-22T06:45:45Z)
• A Multiplicative Value Function for Safe and Efficient Reinforcement Learning [131.96501469927733]
  We propose a safe model-free RL algorithm with a novel multiplicative value function consisting of a safety critic and a reward critic. The safety critic predicts the probability of constraint violation and discounts the reward critic that only estimates constraint-free returns. We evaluate our method in four safety-focused environments, including classical RL benchmarks augmented with safety constraints and robot navigation tasks with images and raw Lidar scans as observations.
  arXiv  Detail & Related papers  (2023-03-07T18:29:15Z)
• A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraints [43.895798638743784]
  We develop the first near-optimal safe RL algorithm for episodic Markov Decision Processes with unsafe states and actions. It achieves a regret $tildeO(fracd H3 sqrtdKDelta_c)$ that tightly matches the state-of-the-art regret in the setting. We also provide a lower bound $tildeOmega(maxdH sqrtK, fracHDelta_c2)$, which indicates that the dependency on $
  arXiv  Detail & Related papers  (2023-02-08T23:42:04Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  We show that it is possible to obtain regret scaling as $mathcalO(sqrtV_1star K)$ in reinforcement learning with large state spaces. We demonstrate that existing techniques based on at least squares estimation are insufficient to obtain this result.
  arXiv  Detail & Related papers  (2021-12-07T00:29:57Z)
• Safe Exploration for Constrained Reinforcement Learning with Provable Guarantees [2.379828460137829]
  We propose a model-based safe RL algorithm that we call the Optimistic-Pessimistic Safe Reinforcement Learning (OPSRL) algorithm. We show that it achieves an $tildemathcalO(S2sqrtA H7K/ (barC - barC_b)$ cumulative regret without violating the safety constraints during learning.
  arXiv  Detail & Related papers  (2021-12-01T23:21:48Z)
• Safe Reinforcement Learning with Linear Function Approximation [48.75026009895308]
  We introduce safety as an unknown linear cost function of states and actions, which must always fall below a certain threshold. We then present algorithms, termed SLUCB-QVI and RSLUCB-QVI, for episodic Markov decision processes (MDPs) with linear function approximation. We show that SLUCB-QVI and RSLUCB-QVI, while with emphno safety violation, achieve a $tildemathcalOleft(kappasqrtd3H3Tright)$ regret, nearly matching
  arXiv  Detail & Related papers  (2021-06-11T08:46:57Z)
• Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
  We consider non-textitunknown yet safety-critical optimization problems under textitunknown yet safety-critical constraints. Such problems naturally arise in a variety of domains including robotics, manufacturing, and medical procedures. A crucial component of our analysis is to introduce and apply a technique called shrinkage in the context of safe optimization.
  arXiv  Detail & Related papers  (2020-06-23T20:51:00Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation. We present an provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.
  arXiv  Detail & Related papers  (2020-03-01T17:47:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.