Long-term Safe Reinforcement Learningwith Binary Feedback
Akfumi Wachi , Wataru Hashimoto , Kazumune Hashimoto
121

LY Corporation

2

Osaka University

Our Contributions

Problem Formulation

Propose an algorithm called LoBiSaRL.
LoBiSaRL enables us to solve safe RL problems with binary feedback andunknown, stochastic state transition while guaranteeing the satisfactionof long-term safety constraints.
Theoretically show that future safety can be pessimistically characterizedby 1) 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 comparedwith several baselines.

Consider episodic finite-horizon CMDPs, which are defined as a tuple M :=(S, A, P, T, r, g, s1), where S is a state space {s},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 episode, r : S × A → [0, 1] is a reward function, g : S × A →{0, 1} is an unknown binary safety function, and s1 ∈ S is the initial state.

Safe Reinforcement Learning

Remark. It is quite hard to satisfy the aforementioned constraint. It is becauseeven if the agent executes an action at at time t and state st such thatno
Pr g(st, at) = 1 ≥ 1 − δ,(1)Safe reinforcement learning (RL) is a promising paradigm for applying RL
algorithms to real-world applications (Garcıa and Fernández, 2015).
Safe RL is beneficial in safety-critical decision-making problems, such as
autonomous driving, healthcare, and robotics, where safety issues must be
incorporated to prevent RL policies from posing risks to humans or objects.
Safe RL has received significant attention in recent years as a crucial issue ofRL during both the learning and execution phases (Amodei et al., 2016).

Existing Safe RL Approaches
Safe RL is typically formulated as constrained policy optimization problems
where the expected cumulative reward is maximized while guaranteeing orencouraging the satisfaction of safety constraint.
Satisfying safety constraints almost surely or with high probability received
less attention to date.
Several previous work on safe RL aimed to guarantee safety at every time
step with high probability, even during the learning process.
However, existing work has room for improvement regarding strong
assumptions.
State transition
Known

D/S

Wachi and Sui (2020) Yes
Amani et al. (2021)
LinearWachi et al. (2021)
Yes
Bennett et al. (2023)
No
LoBiSaRL (Ours)
NoDS
DSS

SafetyAdditional assumption(s)GP
LinearKnown safe policy
GLM
GLM
Known safe policyGLM Lipschitz continuity & conservative policy

Table 1. Comparison among existing work regarding their assumptions on a state transition,safety function, and others (D means deterministic state transition, and S means stochasticstate transition).

Characterizing Safety

Goal. This paper aims to obtain the optimal policy π ? : S → A to maximize thevalue function Vtπ (st) under the following safety constraint such thatnomax Vtπ (st) s.t. Pr g(sτ , aτ ) = 1 ∀τ ∈ [t, T ] ≥ 1 − δ.
πthere may not be any viable action at st+1 ∼ P (st, at) and further future states.

Difficulties and Assumptions

We first obtain the lower bounds of the safety linear predictor f ?:`(st, at) := max `GLM(st, at), `Lipschitz(st, at) ,(6)where `GLM : S × A → R and `Lipschitz : S × A → R are pessimistic safety linear
predictors inferred by GLM and Lipshitz continuity, defined as`GLM(st, at) := hφ(st, at), ŵi − β · kφ(st, at)kWn−1 ,]`Lipschitz(st, at) := f (s1) − L1 L2 t + L3X1t−1 + xt ,Note: L1, L2 and L3 are Lipschitz constants.

Theoretical ResultTheorem 1. Suppose, at state st, the agent executes the action at while tuning
the MDCPs xt, xt+1, . . . , xT so that the following inequality holds.
T −1`(st, at) − L1 L2(T − t) − (L3 − 1)xt + L3Xt+1+ xT ≥ z(7)Set δ := 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.
Difficulty 1. If the binary safety function does not exhibit any regularity, it is
impossible 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)
link function µ : R → [0, 1] such that?
E[ g(s, a) | s, a ] = µ f (s, a) ,(2)for all (s, a) ∈ S × A, where f ? : S × A → R is a linear predictor defined asf ?(s, a) := hφ(s, a), w?i,∀(s, a) ∈ S × A.

(3)

Difficulty 2. The state transition is stochastic and unknown a priori. Hence,to satisfy the long-term safety constraint, we must explicitly incorporate thestochasticity 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 φ(·, ·)is Lipschitz continuous with a constant Lφ ∈ R+; that is,kφ(s, a) − φ(s̄, ā)k2 ≤ Lφ · dSA((s, a), (s̄, ā)),(4)

where dSA(·, ·) is a distance metric on S × A. For ease of exposition, we assume
that dSA satisfies dSA((s, a), (s̄, ā)) = dS (s, s̄) + dA(a, ā).
Assumption 3. Let L] ∈ R+ be a positive scalar. There exists a known L]Lipschitz continuous policy π ] : S → A such that, for any states s, s̄ ∈ S,dA(π ](s) − π ](s̄)) ≤ L] · dS (s, s̄).

Also, with a positive scalar η ∈ R+, for any policy π : S → A, the following
inequality holds for all s ∈ S:max dS (s, s0) ≤ d¯ + η · dA(π(s), π ](s)).
s0∼P (·|s,π(s))

Poster Session

Experiments
Grid-world environment with random reward and safety.
Instantaneous agent is much safer than Random, Unsafe, Linear baselines
but sometimes violates the safety constraint.
As for safety, LoBiSaRL is the only algorithm to guarantee the satisfaction of
the safety constraint in the long run.
LoBiSaRL is often too conservative and the performance in terms of reward
is worse than Instantaneous.
Reward Unsafe actions
Random0.32 ± 0.24
Unsafe1.00 ± 0.00
Linear0.73 ± 0.13
Instantaneous
0.86 ± 0.10
LoBiSaRL (Ours) 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 2. Experimental results. Reward is normalized with respect to Unsafe agent.

References(5)

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

2Amani, S. et al. (2021). Safe reinforcement learning with linear function approximation. In ICML.
Amodei, D. et al. (2016). Concrete problems in AI safety. arXiv preprint arXiv:1606.06565.
Bennett, A. et al. (2023). Provable safe reinforcement learning with binary feedback. In AISTAT.
Garcıa, J. and Fernández, F. (2015).
16(1):1437–1480.

A comprehensive survey on safe reinforcement learning.

JMLR,

Wachi, A. et al. (2021). Safe policy optimization with local generalized linear function approximations. In NeurIPS.
Wachi, A. and Sui, Y. (2020). Safe reinforcement learning in constrained Markov decision processes. In ICML.

akifumi.wachi@lycorp.co.jp