References

Long-term Safe Reinforcement Learning with Binary Feedback
Akifumi Wachi1

Wataru Hashimoto2

Kazumune Hashimoto2

1 LINE Corporation
2 Osaka University

AAAI 2024

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Safe Reinforcement Learning

Safe reinforcement learning (RL) is a promising paradigm for applying RL
algorithms to real-world applications (Garcıa and Fernández, 2015).
Safe RL is beneficial in safety-critical decision-making problems, such as
autonomous driving, healthcare, and robotics, where safety requirements must beincorporated to prevent RL policies from posing risks to humans or objects(Dulac-Arnold et al., 2021).
Safe RL has received significant attention in recent years as a crucial issue of RL
during both the learning and execution phases (Amodei et al., 2016).

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Typical Safe RL Approaches

Safe RL is typically formulated as constrained policy optimization problems where
the expected cumulative reward is maximized while guaranteeing or encouraging
the satisfaction of safety constraint.
Satisfying safety constraints almost surely or with high probability received lessattention to date.

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Strongly Relevant Safe RL Appraoches
Several previous work on safe RL aimed to guarantee safety at every time stepwith high probability, even during the learning process.
However, existing work has room for improvement regarding strong assumptions.
State transition

Wachi and Sui (2020)
Amani et al. (2021)
Wachi et al. (2021)
Bennett et al. (2023)
LoBiSaRL (Ours)

Known

D/SYesLinearYes
NoNoDSDSSSafety

Additional assumption(s)GPLinearGLM
GLM
GLM

Known safe policy
Known safe policy
Lipschitz continuity & conservative policy

Table: Comparison among existing work regarding their assumptions on a state transition, safety function, andothers (D means deterministic state transition, and S means stochastic state transition).

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Our Contributions

Propose an algorithm called Long-term Binary-feedback Safe RL, LoBiSaRL.
LoBiSaRL enables us to solve safe RL problems with binary feedback andunknown, stochastic state transition while guaranteeing the satisfaction oflong-term safety constraints.
Theoretically show that future safety can be pessimistically characterized by1) inevitable randomness due to the stochastic state transition and 2) divergence
between the current policy and a reference policy to stabilize the state.
Empirically demonstrate the effectiveness of the LoBiSaRL compared with severalbaselines.

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Constrained Markov Decision Processes (CMDPs)
Consider episodic finite-horizon CMDPs, which can be formally defined as a tupleM := (S, A, P, T, r, g, s1 ).

(1)

S is a state space {s} and A is an action space {a}P : S × A → ∆(S) is an unknown, stochastic state transition function to map astate-action pair to a probability distribution over the next states
T ∈ Z+ is a fixed length of each episoder : S × A → [0, 1] is a (bounded) reward function
g : S × A → {0, 1} is an unknown binary safety functions1 ∈ S is the initial stateLong-term Safe Reinforcement Learning with Binary FeedbackReferences

Problem StatementGoal. This paper aims to obtain the optimal policy π ⋆ : S → A to maximize the valuefunction Vtπ (st ) under the following safety constraint such thatnomax Vtπ (st ) s.t. Pr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ 1 − δ.
πRemark
It is quite hard to guarantee the satisfaction of the aforementioned constraint. It isbecause even if the agent executes an action at at time t and state st such that
noPr g(st , at ) = 1 ≥ 1 − δ,(2)there may not be any viable action at st+1 ∼ P (st , at ) and further future states.
Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Difficulties and Assumptions I
The problem we wish to solve has difficulties; hence, we make the following
assumptions.
Difficulty 1. If the binary safety function does not exhibit any regularity, it isimpossible to infer the safety of state-action pairs.
Assumption 1. There exists a known feature mapping function ϕ : S × A → Rm ,unknown coefficient vectors w⋆ ∈ Rm , and a fixed, strictly increasing (inverse) linkfunction µ : R → [0, 1] such thatE[ g(s, a) | s, a ] = µ f ⋆ (s, a) ,(3)for all (s, a) ∈ S × A, where f ⋆ : S × A → R is a linear predictor defined asf ⋆ (s, a) := ⟨ϕ(s, a), w⋆ ⟩,∀(s, a) ∈ S × A.

Long-term Safe Reinforcement Learning with Binary Feedback(4)

References

Difficulties and Assumptions II
Difficulty 2. The state transition is stochastic and unknown a priori→ To guarantee the satisfaction of the long-term safety constraint, we must explicitly
incorporate the stochasticity of the state transition and its influence on future safety.
Assumption 2. For all s, s̄ ∈ S and a, ā ∈ A, the feature mapping function ϕ(·, ·) isLipschitz continuous with a constant Lϕ ∈ R+ ; that is,∥ϕ(s, a) − ϕ(s̄, ā)∥2 ≤ Lϕ · dSA ((s, a), (s̄, ā)),(5)

where dSA (·, ·) is a distance metric on S × A. For ease of exposition, we assume thatdSA satisfies dSA ((s, a), (s̄, ā)) = dS (s, s̄) + dA (a, ā).

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Difficulties and Assumptions III
Assumption 3. Let L♯ ∈ R+ be a positive scalar. There exists a known L♯ -Lipschitz
continuous conservative policy π ♯ : S → A such that, for any states s, s̄ ∈ S,dA (π ♯ (s) − π ♯ (s̄)) ≤ L♯ · dS (s, s̄).

(6)

Also, with a positive scalar η ∈ R+ , for any policy π : S → A, the following inequality
holds for all s ∈ S:
maxs′ ∼P (·|s,π(s))

dS (s, s′ ) ≤ d¯ + η · dA (π(s), π ♯ (s)).

To guarantee long-term safety, it is important to properly tune the maximum
divergence from the conservative policy (MDCP).

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Characterizing Safety
We first obtain the lower bounds of the safety linear predictor f ⋆ :ℓ(st , at ) := max ℓGLM (st , at ), ℓLipschitz (st , at ) ,(7)where ℓGLM : S × A → R and ℓLipschitz : S × A → R are pessimistic safety linear
predictors inferred by GLM and Lipshitz continuity, which are respectively defined asℓGLM (st , at ) := ⟨ϕ(st , at ), ŵ⟩ − β · ∥ϕ(st , at )∥Wn−1 ,ℓLipschitz (st , at ) := f ♯ (s1 ) − L1 L2 t + L3 X1t−1 + xt ,Note: L1 , L2 and L3 are Lipschitz constants.

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Theoretical Results
Theorem (informal)
Suppose, at state st , the agent executes the action at while tuning the MDCPs
xt , xt+1 , . . . , xT so that the following inequality holds.
noT −1ℓ(st , at ) − L1 L2 (T − t) − (L3 − 1)xt + L3 Xt+1+ xT ≥ zSet δ := 1 − (1 − µ(z))T −t . Then, we havenoPr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ 1 − δ,∀t ∈ [T ],— i.e. the long-term safety constraint is satisfied — with a high probability.

Long-term Safe Reinforcement Learning with Binary Feedback(8)ReferencesExperiments
Grid-world environment with 20 × 20 square grids with random reward and safety.
Instantaneous agent is much safer than Random, Unsafe, Linearbaselines but sometimes violates the safety constraint.
As for safety, LoBiSaRL is the only algorithm to guarantee the satisfaction of thesafety constraint in the long run.
LoBiSaRL is often too conservative and the performance in terms of reward isworse than Instantaneous.

RandomUnsafeLinear
Instantaneous
LoBiSaRL (Ours)

RewardUnsafe actions

0.32 ± 0.24
1.00 ± 0.00
0.73 ± 0.13
0.86 ± 0.10
0.76 ± 0.12

23.2 ± 10.3
26.8 ± 13.6
18.3 ± 5.7
3.3 ± 2.2
0.0 ± 0.0

Table: Experimental results. Reward is normalized with respect to Unsafe agent.
Long-term Safe Reinforcement Learning with Binary FeedbackReferencesConclusion
Formulate a safe RL problem with stochastic state transition and binary safety
feedback and then propose an algorithm called LoBiSaRL.
Under the assumptions regarding the Lipschitz continuity of the feature mapping
function and the existence of a conservative policy, LoBiSaRL optimizes a policy
while ensuring that there is at least one viable action until the terminal time step.
Theoretically guarantee long-term safety and empirically evaluate the performanceof LoBiSaRL comparing with several baselines.

Contact: akifumi.wachi@lycorp.co.jp

Long-term Safe Reinforcement Learning with Binary FeedbackReferences

Reference I
Amani, S., Thrampoulidis, C., and Yang, L. (2021). Safe reinforcement learning with linear function
approximation. In International Conference on Machine Learning (ICML).
Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., and Mané, D. (2016). Concrete problems in
AI safety. arXiv preprint arXiv:1606.06565.
Bennett, A., Misra, D., and Kallus, N. (2023). Provable safe reinforcement learning with binary feedback. InInternational Conference on Artificial Intelligence and Statistics (AISTAT).
Dulac-Arnold, G., Levine, N., Mankowitz, D. J., Li, J., Paduraru, C., Gowal, S., and Hester, T. (2021).
Challenges of real-world reinforcement learning: definitions, benchmarks and analysis. Machine Learning,pages 1–50.
Garcıa, J. and Fernández, F. (2015). A comprehensive survey on safe reinforcement learning. Journal ofMachine Learning Research (JMLR), 16(1):1437–1480.
Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained markov decision processes. InInternational Conference on Machine Learning (ICML).
Wachi, A., Wei, Y., and Sui, Y. (2021). Safe policy optimization with local generalized linear function
approximations. Neural Information Processing Systems (NeurIPS).

Long-term Safe Reinforcement Learning with Binary Feedback