Source-linked AI summary
Safe Reinforcement Learning in Constrained Markov Decision Processes
Akifumi Wachi, Yanan Sui
TL;DR
Safe reinforcement learning must balance exploration safety with cumulative reward when safety and reward functions are unknown. This paper proposes SNO-MDP, which first expands and certifies a safe region, then optimizes reward there, with theoretical guarantees and evaluations on synthetic and Mars terrain data.
Problem
Unknown safety functions make it difficult to explore a constrained MDP while guaranteeing safety, although safety alone may produce overly conservative policies.
Method
SNO-MDP first explores the safety function by expanding a safe region, then optimizes cumulative reward in the certified safe region.
Results
SNO-MDP is theoretically shown to guarantee safety and near-optimal cumulative reward, and is evaluated in GP-SAFETY-GYM and with real Mars terrain data.
Takeaways & Limitations
The stepwise approach supports safe exploration and reward optimization in safety-constrained MDPs with unknown functions.
Takeaways & Limitations
The theoretical guarantees rely on assumptions including a known safe initial state set and regularity of the safety function.
Abstract
from arXiv · showhide
Safe reinforcement learning has been a promising approach for optimizing the policy of an agent that operates in safety-critical applications. In this paper, we propose an algorithm, SNO-MDP, that explores and optimizes Markov decision processes under unknown safety constraints. Specifically, we take a stepwise approach for optimizing safety and cumulative reward. In our method, the agent first learns safety constraints by expanding the safe region, and then optimizes the cumulative reward in the certified safe region. We provide theoretical guarantees on both the satisfaction of the safety constraint and the near-optimality of the cumulative reward under proper regularity assumptions. In our experiments, we demonstrate the effectiveness of SNO-MDP through two experiments: one uses a synthetic data in a new, openly-available environment named GP-SAFETY-GYM, and the other simulates Mars surface exploration by using real observation data.
1. Introduction
Safe reinforcement learning addresses settings where an agent must explore unknown environments without unsafe actions while still pursuing cumulative reward. SNO-MDP separates safety exploration from reward optimization and provides theoretical and experimental support for this objective.
- Motivation: Safety-critical agents must autonomously explore environments and guarantee safety when hazards are discovered only through in situ observations.Mars rovers exemplify this setting because close-up terrain data become available only after landing.
- Motivation: Safety is essential, but maximizing reward remains the primary objective because policies focused only on survival can be extremely conservative.The paper gives staying at the current position as an example of conservative safety behavior.
- Research gap: Prior safe RL work can guarantee safety under unknown reward and safety functions without guaranteeing near-optimal cumulative reward.SNO-MDP is introduced to address both requirements simultaneously.
- Related work: Safety-agnostic exploration may execute unsafe actions, motivating algorithms that guarantee safety during training with high probability.This concern distinguishes conventional PAC-MDP methods, which target near-optimal behavior with polynomial samples, from safety-focused approaches.
- Contributions: SNO-MDP first explores the safety function and then optimizes cumulative reward in the certified safe region, with PAC-MDP guarantees and evaluations in GP-SAFETY-GYM and Mars terrain data.The paper also proposes ES2 for faster convergence while maintaining probabilistic safety and reward guarantees.
2. Problem Statement
The paper formulates a finite constrained MDP with unknown reward and safety functions, requiring every visited state to satisfy a safety threshold. The central challenge is learning the unknown safety function while maintaining safety, addressed through safe initial states and regularity assumptions.
- MDP formulation: The constrained MDP uses finite state and action sets, deterministic transitions, bounded rewards, an unknown safety function, and discount factor γ.The reward maps states to (0, Rmax], while the safety function maps states to real values.
- MDP formulation: A policy maps states to actions, and its value is the discounted cumulative reward subject to g(st+τ) ≥h for all future time steps.The objective is to obtain a policy close to the optimal value while satisfying the safety constraint.
- Difficulties: The key difficulty is exploring a safety function that is unknown a priori while guaranteeing constraint satisfaction.This differs from conventional safety-constrained RL, which assumes the safety function is known.
- Difficulties: Without known safe state-action pairs or regularity in the safety function, the agent may lack a viable initial action and cannot infer decision safety.These conditions make the problem intractable without further assumptions.
- Assumptions: The method assumes a known safe initial state set and a safety function with bounded RKHS norm and L-Lipschitz continuity.A positive definite kernel captures safety-function regularity.
- Function modeling: Gaussian processes model the reward and safety functions from observations, providing posterior means and variances for optimistic and pessimistic estimates.The GP representation uses separate kernels and noisy observations for reward and safety.
3. Background
The background develops GP-based safe-space estimates and the reachability, returnability, and confidence concepts used to expand safety conservatively. It then connects these estimates to the constrained optimal-policy objective and probabilistic guarantees.
- Predicted safe spaces: GP inference yields pessimistic safe spaces containing states likely to satisfy the safety constraint and optimistic spaces containing states that may be safe.The pessimistic space supports safety guarantees, while the optimistic space provides information for inferring the safety function.
- Reachability and returnability: Safe expansion additionally requires reachability from the current set and returnability to the previously identified safe set.These constraints prevent entering states from which safe continuation or return may be impossible.
- Confidence intervals: The algorithm guarantees safety probabilistically by allowing visits only to states in the predicted pessimistic safe space.Safety intervals are inferred by the GP and updated through intersections of confidence intervals over time.
- Confidence intervals: The safety confidence interval holds for all t ≥1 with probability at least 1 −∆g, and the analogous reward interval holds with probability at least 1 −∆r.The confidence parameter β controls conservativeness, while Γg measures effective kernel degrees of freedom.
- Optimal solution: The unknown-function problem is evaluated against an optimal policy whose value satisfies a Bellman equation under the safety constraint.The target is a policy close to V∗M while safely learning within the largest appropriately learnable region.
4. Algorithm
SNO-MDP separates safe-region expansion from reward optimization, using ES2 to stop safety exploration once the certified region is sufficient for near-optimal reward. P-ES2 replaces a conservative safety assumption with state-wise safety probabilities for better empirical performance, while sacrificing the theoretical reward guarantee.
- SNO-MDP: SNO-MDP first expands the pessimistic safe region and then explores and exploits reward within the certified region.The stepwise design avoids further safety-function uncertainty after the safe region is fixed.
- 4.3. Early Stopping of Exploration of Safety (ES2): ES2 stops expanding the safe region when an auxiliary optimistic-safe-space MDP indicates that further exploration is unnecessary for near-optimal reward.The auxiliary MDP modifies the state space and reward so the stopping test accounts for reward optimization.
- 4.1. Exploration of Safety (Step 1): Safety exploration selects the expander with maximum confidence-interval width and plans a path to reach it safely.The width measures uncertainty in the safety function, while the path cost can be based on distance or uncertainty.
- 4.2. Exploration and Exploitation of Reward (Step 2): After safety expansion, SNO-MDP optimizes reward with a probabilistic upper confidence bound and solves a Bellman equation using fixed reward and safety beliefs.The upper-confidence formulation includes an exploration bonus to balance reward exploration and exploitation.
- 4.4. More Practical ES2 Algorithm (P-ES2): P-ES2 models uncertain safety through a virtual state z reached with probability 1 − p, producing smoother transitions for practical optimization.The virtual state has zero reward and is absorbing; P-ES2 improves empirical performance but lacks ES2’s theoretical near-optimality guarantee.
5. Theoretical Results
Theoretical results establish that SNO-MDP safely expands a certified region before reward optimization, achieving near-optimal cumulative reward with high probability. ES2 preserves this near-optimality while enabling earlier termination of safety exploration.
- Theoretical Results: The theorems separately cover safe-region convergence, near-optimal cumulative reward, and preservation of near-optimality under ES2.The paper identifies these as Theorems 1, 2, and 3, respectively.
- Safety Guarantee and Completeness: Theorem 1 guarantees safety during both safety exploration and reward optimization, while the certified region eventually contains the approximately safe reachable region.These guarantees hold with high probability after sufficiently many time steps.
- Near-Optimality: After safe-space exploration, the certified region lies between an approximately safe region and the exactly safe reachable-returnable region.This containment supports the subsequent near-optimality argument.
- Near-Optimality: Optimistic reward estimates that decay with sampling enable SNO-MDP to obtain an ϵ*_V-close policy to the optimal policy in the safety-constrained MDP.The proof adapts PAC-MDP arguments while optimizing reward within the certified safe region.
- ES2 Guarantee: With high probability, the ES2 version is ˜ϵ_V-close to the optimal policy for all but ˜t time steps while maintaining safety probability at least 1 −∆g.ES2 therefore preserves the near-optimality guarantee of SNO-MDP.
6. Experiment
Experiments evaluate SNO-MDP in a synthetic GP-SAFETY-GYM environment and a Mars terrain simulation. Across both settings, SNO-MDP improves reward relative to the safety-focused baselines without executing unsafe actions, while P-ES2 accelerates convergence in the synthetic experiment.
- Experiment: Two experiments evaluate SNO-MDP: a synthetic environment and a Mars surface exploration simulation using real terrain observation data.The synthetic environment is GP-SAFETY-GYM, while the Mars experiment uses a public digital elevation model.
- Synthetic GP-SAFETY-GYM Environment: SNO-MDP achieved the optimal reward after switching to reward optimization and outperformed SAFEMDP and SAFEEXPOPT-MDP after sufficiently many time steps.SAFEEXPOPT-MDP could become stuck in a local optimum when safe-region expansion was insufficient.
- Synthetic GP-SAFETY-GYM Environment: P-ES2 converged faster in reward than the original ES2, and all methods, including the baselines, avoided unsafe actions.Synthetic rewards were normalized relative to the SAFE/REWARD KNOWN case.
- Simulated Mars Surface Exploration: In the Mars experiment, SNO-MDP with either P-ES2 or ES2 outperformed SAFEMDP and SAFEEXPOPT-MDP in normalized accumulated reward.The rover treated states with slope angles greater than 25° as unsafe.
- Simulated Mars Surface Exploration: No unsafe action was executed by any tested algorithm in the Mars experiment.The experiments compared cumulative reward and the number of unsafe actions.
7. Conclusion
The paper proposes SNO-MDP for safe exploration and reward optimization in unknown safety-constrained MDPs, with theoretical safety and near-optimality guarantees. ES2 and P-ES2 improve reward acquisition efficiency, and experiments support the approach in synthetic and Mars terrain settings.
- Conclusion: SNO-MDP is a stepwise approach that explores and optimizes safety-constrained MDPs while targeting near-optimal cumulative reward with safety guarantees.The paper proves a sample-complexity bound for ϵ_V-closeness to the optimal policy with high-probability safety.
- Conclusion: ES2 and P-ES2 are proposed to improve the efficiency of obtaining rewards.The paper also develops GP-SAFETY-GYM as an open-source evaluation environment.
- Conclusion: Experiments demonstrate the advantages of SNO-MDP in GP-SAFETY-GYM and with real Mars terrain data.These settings cover synthetic simulation and Mars surface exploration.
A. Definitions
The definitions formalize safe states, confidence-based safe spaces, reachability, returnability, and the exploration–exploitation procedures used by the algorithms. These constructions specify how candidate states are expanded and retained within the safe region.
- Definitions: The pessimistic safe space contains states identified as safe above a confidence level, while the optimistic safe space includes states that may be safe with small probability.These two predicted safe spaces distinguish conservative certification from exploratory inclusion.
- Definitions: The reachability operator adds states reachable from a set through an available action and the transition function.It formalizes one-step expansion from the current set.
- Definitions: The returnability operator retains states that can transition back into a designated safe subset.Safe-space construction uses reachability and returnability together.
- Algorithm Procedures: The algorithm definitions separately specify reward exploration–exploitation balancing and termination checks.These procedures are given for the baseline approach and its reward-focused variants.
- Supporting Lemma: The appendix includes an inequality lemma for arbitrary functions and derives it by setting one function equal to the sum of two others.This lemma supports the surrounding theoretical development.
C. Near-optimality
SNO-MDP's near-optimality analysis bounds the value of its policy relative to the optimal policy using belief and escape-probability arguments. The proof develops generalized inequalities for regions where reward and safety models agree, then applies them to the certified safe region.
- The analysis compares SNO-MDP's value function with the optimal constrained-MDP value function.The proof introduces value-function inequalities and repeatedly applies them to establish the desired bound.
- The concentration arguments rely on information-gain terms, sub-Gaussian noise, and confidence parameters for reward estimation.These conditions appear in the supporting lemmas and their probability statements.
- The generalized induced inequality bounds value differences using the probability of leaving a region where beliefs and rewards agree.It assumes the value is bounded in [0, Vmax].
D. ES2 algorithm
The ES2 variant is analyzed through a parallel value-function argument that tracks the learned safety region and the policy's probability of leaving it. Its proof reuses the same induced-inequality strategy while accounting for ES2's exploration schedule.
- The proof applies the same lemma-based chain of inequalities used for the non-ES2 analysis.The derivation again invokes definitions of the safety indicator, value functions, and supporting lemmas.
- The next-state argument establishes that following the relevant optimal policy from Yt keeps the next state within Yt.This invariance statement is used to complete the corresponding lemma.
- With ES2, the analysis defines a value function for the policy computed from current beliefs and the exploration-bonus reward.The proof then compares this policy with an optimal policy over a modified reward model.
E. Main Theoretical Results
The main theorems show that SNO-MDP expands a safe region under regularity assumptions and obtains near-optimal value while maintaining probabilistic safety guarantees. The ES2 analysis establishes an analogous result with its own exploration-time bound.
- Safety exploration: Under the stated assumptions, exploration of safety continues until the maximum safety uncertainty over Gt is below ϵg.The stopping time t∗ is defined from this condition.
- Safety exploration: With probability at least 1 −∆g, an εg-reachable safe region is contained in the learned region, which is contained in the zero-tolerance safe region.The theorem states this inclusion for some t0 ≤ t∗.
- Theoretical scope: The safety-region theorem extends prior work by treating t as the number of actions rather than the number of samples.This identifies the distinction between the earlier result and the present setting.
- Near-optimality: After the safe region is fully explored, the policy is V-close to optimal for all but t∗ time steps while guaranteeing safety with probability at least 1 −∆g.The result applies after the exploration stage under the theorem's regularity assumptions.
- ES2 guarantee: The ES2 variant is likewise ˜ϵV-close to optimal for all but ˜t time steps while guaranteeing safety with high probability.The corresponding theorem states this result jointly with the ES2 exploration analysis.