Source-linked AI summary
Safe Multi-Objective Reinforcement Learning: Zero Constraint Violation and Primal-Averaging Convergence
Chenxi Li, Yao Shu, Siyang Gao, Shuang Qiu, Guangxin Jiang
TL;DR
Safe MORL must balance conflicting objectives while meeting safety constraints, yet safe exploration with unknown costs and dynamics is difficult. The paper develops preference-based and preference-free algorithms using optimistic reward estimates and pessimistic cost bounds; they guarantee zero violations for executed policies under stated assumptions and provide extensions when those assumptions are relaxed.
Problem
Safe MORL lacks a unified sample-efficient framework guaranteeing zero constraint violation throughout learning under cumulative or stepwise constraints, despite the need to explore with unknown costs and dynamics.
Source: §1 · p. 2Method
CSTRL uses optimistic reward estimates and pessimistic cost bounds for a specified preference, while PF-CSTRL safely explores first and plans for a later preference.
Source: §1 · p. 3, §8 · p. 20Results
The algorithms guarantee zero constraint violation for every executed policy when a strictly safe policy and its costs are known, and return a safe policy from averaged occupancy measures.
Source: §1 · p. 3, §8 · p. 20Takeaways & Limitations
Preference-free exploration supports computing a policy for any later-specified preference without further environment interaction; when the safe policy is unknown, cumulative violation remains bounded by a constant.
Source: §8 · p. 20
Abstract
from arXiv · showhide
Many applications of multi-objective reinforcement learning (MORL) require policies that balance conflicting objectives while satisfying safety constraints. We study safe MORL with zero constraint violation throughout learning, covering both cumulative and stepwise constraints. A key challenge is to explore sufficiently under unknown dynamics and constraint costs without violating the constraints. For a given preference over objectives, we develop an algorithm to learn a safe Pareto optimal policy by combining optimistic reward estimates with pessimistic cost bounds. With high probability, every policy executed over $T$ episodes incurs zero constraint violation. The algorithm returns a safe Markov policy induced by the averaged occupancy measure and achieves an $\widetilde{O}(1/\sqrt{T})$ suboptimality gap under smooth Tchebycheff scalarization. We further develop a preference-free algorithm that first explores safely without a prespecified preference and then computes a safe policy for any given preference without further interaction. Over $T$ exploration episodes and $K$ planning iterations, it retains the same safety guarantee and achieves an $\widetilde{O}(1/\sqrt{T}+1/\sqrt{K})$ suboptimality gap. Both algorithms require knowledge of a policy that strictly satisfies the constraints and its costs. We then relax these requirements, incurring at most constant cumulative violation. To our knowledge, we provide the first sample-efficient MORL algorithms that guarantee safety for every executed policy.
1 Introduction
Safe MORL seeks policies that balance conflicting objectives while meeting explicit constraints, but existing work lacks a unified sample-efficient approach guaranteeing zero violations during learning. The paper proposes preference-based and preference-free algorithms, with guarantees for executed policies and extensions for weaker prior knowledge.
1 Introduction
- The paper targets a gap in constrained MORL: sample-efficient methods that guarantee zero constraint violation throughout learning under cumulative or stepwise constraints are lacking.Prior safe MORL methods may violate constraints during learning, while much constrained RL work is single-objective.Source: §1 · pp. 2, 4
- Unknown costs and dynamics make safe exploration difficult, while safe Pareto policies may be dominated by unsafe policies and must cover preferences not known during exploration.Estimating safe objective optima requires auxiliary constrained RL problems; preference-free exploration must collect data sufficient for later preferences using only safe policies.Source: §1 · pp. 2–3
- CSTRL combines optimistic reward estimates with pessimistic cost bounds in mirror-ascent updates to learn a safe Pareto policy for a specified preference.PF-CSTRL guides safe exploration using reward and transition uncertainty, then plans for any subsequently specified preference.Source: §1 · p. 3
- With high probability, CSTRL guarantees zero constraint violation for every executed policy and returns a safe Markov policy induced by the primal average of occupancy measures.These guarantees apply to cumulative and stepwise safety constraints.Source: §1 · p. 3
- PF-CSTRL separates safe exploration from planning, allowing a policy for a later-specified preference to be computed without further environment interaction.The paper describes T exploration episodes followed by K planning iterations.Source: §1 · p. 3
- When the safe policy is known but its costs are unknown, the extensions preserve zero violation; when both are unknown, they incur only constant cumulative violation.The paper presents these as relaxations of the algorithms’ prior-knowledge requirements.Source: §1 · p. 3
2 Preliminaries
The preliminaries define a finite-horizon constrained multi-objective MDP with unknown rewards, costs, and dynamics. Safety is specified through cumulative or stepwise constraints, and Pareto optimality is defined relative to the safe policy class.
2 Preliminaries
- The setting is a finite-horizon constrained multi-objective MDP in which rewards, constraint costs, and transition dynamics are unknown.Policies are stochastic Markov policies over finite state and action spaces.Source: §2 · p. 4
- An occupancy measure is the joint distribution over states, actions, and next states used to formulate the optimization problem and recover policies and transitions.The induced policy and transition kernel can be reconstructed from the measure.Source: §2 · p. 5
- A policy is safe when its expected costs satisfy the thresholds; constraints applying at one step are stepwise, while those applying across the horizon are cumulative.The analysis adopts a Slater condition requiring a policy that satisfies every constraint strictly.Source: §2 · pp. 5–6
- The standard zero-violation setup assumes the learner knows both a strictly safe policy and its constraint costs, although existence alone does not ensure safety during learning when the policy is unknown.A conservative rule-based controller is given as a possible strictly safe policy in autonomous driving.Source: §2 · p. 6
- A safe Pareto optimal policy is undominated within the safe policy class, rather than among all policies.Policies that are Pareto optimal without constraints may violate safety requirements.Source: §2 · p. 6
3 Scalarization of Multiple Objectives
The section adapts smooth Tchebycheff scalarization to safe policies so a preference can select a safe Pareto-optimal policy. It establishes properties of the safe value set and scalarization, while noting a boundary in the convexity argument.
3 Scalarization of Multiple Objectives
- The safe smooth Tchebycheff scalarization adapts preference-based optimization to the safe policy class to cover its Pareto front.The preference vector parameterizes the scalar optimization problem.Source: §3 · p. 6
- The safe value set is a nonempty convex polytope under Assumption 2.Source: §3 · p. 7
- The safe smooth Tchebycheff scalarization retains controllability and full coverage on the safe policy class.Source: §3 · p. 7
- The convexity argument relies on all stochastic Markov policies; the deterministic-policy extension is left for future work.Source: §3 · p. 7
- An equivalent min-max-max reformulation is suited to algorithms based on upper confidence bounds.Source: §3 · p. 7
4 Safe Multi-Objective RL
CSTRL combines optimistic reward estimates with pessimistic cost bounds to learn under a fixed preference. It provides high-probability safety for every executed policy and returns a safe Markov policy with a suboptimality guarantee.
4 Safe Multi-Objective RL
- CSTRL uses optimistic reward estimates to encourage exploration and pessimistic cost bounds to maintain safety.Source: §4 · p. 8
- Each episode collects a main trajectory and one auxiliary-policy trajectory per objective, with auxiliary trajectories updating their corresponding estimates.Source: §4 · p. 8
- Its mirror-ascent occupancy updates are projected onto an optimistic feasible set before the resulting policy is selected for execution.Source: §4 · p. 9
- CSTRL achieves an eO(T^-1/2) suboptimality gap and returns a Markov policy induced by the primal-averaged occupancy measure.The guarantee is for the smooth Tchebycheff scalarization objective.Source: §4 · p. 11
- With probability at least 1−δ, CSTRL keeps every executed and output policy safe under stepwise (d=1) or cumulative (d=H) constraints.Source: §4 · p. 11
5 Preference-Free Safe Multi-Objective RL
PF-CSTRL separates safe, preference-free exploration from preference-dependent planning, allowing a policy for any later preference to be computed without further environment interaction. It guarantees zero constraint violation with high probability, while its suboptimality bound combines exploration and planning errors.
5 Preference-Free Safe Multi-Objective RL
- PF-CSTRL explores safely without a prespecified preference, then plans for any λ from the collected dataset without further environment interaction.Unlike preference-based CSTRL, it does not require a new exploration process when λ changes.Source: §5 · p. 12
- Its exploration reward combines reward and transition bonuses to encourage broad state-action coverage for subsequent planning.The exploration stage collects one trajectory per episode and uses safe policies.Source: §5 · p. 12
- The suboptimality bound separates statistical error from preference-free exploration and optimization error from planning on the fixed dataset.The T-dependent term comes from reward and transition bonuses and selection probabilities for π†; K-dependent terms arise from occupancy updates, optimistic values, and smooth Tchebycheff dual updates. The bound hides logarithmic factors in m, n, |S|, |A|, H, T, K, and 1/δ.Source: §5 · p. 12
- With probability at least 1−δ, every exploration and planning policy, as well as the returned policy induced by the averaged occupancy measure, has zero constraint violation.The guarantee applies to both cumulative and stepwise safety constraints.Source: §5 · pp. 12–13
6 Extensions
The extensions relax prior-knowledge requirements for safe MORL, first allowing unknown safe-policy costs and then allowing both the policy and its costs to be unknown. The latter extensions permit bounded cumulative violation during estimation while keeping later policies and the output safe.
6.1 Known π† and Unknown γ
- When π† is known but its costs are unknown, the learner estimates those costs by repeatedly executing π†, then runs CSTRL-UC or PF-CSTRL-UC using a conservative cost bound.The estimation phase lasts at most 1 + 8d^2 ln(4nT/δ)/(ϱ†)^2 episodes with high probability.Source: §6.1 · pp. 13–14
6 Extensions
- The extensions relax the requirement that the learner know a strictly safe policy and its constraint costs, while retaining the assumption that such a policy exists.The unknown-policy variants estimate a strictly safe policy and its costs before running CSTRL or PF-CSTRL.Source: §6 · p. 13, §6.2 · p. 15
6.2 Unknown π† and Unknown γ
- With unknown π† and unknown costs, CSTRL-US and PF-CSTRL-US first estimate a strictly safe policy and its costs, requiring T = Õ((H^4|S|^2|A| + nd^2)/ϱ^2) for the stated estimation guarantee.The procedure uses primal and dual regret minimizers during estimation.Source: §6.2 · p. 15
- For CSTRL-US and PF-CSTRL-US, cumulative violation is at most d t_s with probability at least 1−δ; policies after estimation and the returned policy are safe.PF-CSTRL-US also guarantees safety for every main policy generated during planning.Source: §6.2 · p. 16
7 Theoretical Analysis
The theoretical analysis bounds the learning and planning errors while establishing safety for preference-based and preference-free algorithms, including extensions with unknown constraint costs or an unknown safe policy.
7.1 Proof Sketch of Theorem 9
- Theorem 9's proof separates occupancy-learning, dual and estimation, and safe-policy-selection errors, bounding updates after SafeProj rather than relying on optimistic Bellman recursions.The final high-probability bound combines these terms with the initial policy's H/T contribution.Source: §7.1 · pp. 17–18
7.2 Proof Sketch of Theorem 10
- SafeProj ensures each executed CSTRL policy satisfies the constraints, and convex averaging yields a safe Markov policy.The proof applies the feasibility argument to initial and auxiliary policies as well as later policies.Source: §7.2 · p. 18
7.3 Proof Sketch of Theorem 11
- PF-CSTRL's planning bound combines optimistic-value, dual, and primal errors after comparing optimistic main values with true policy values.The proof combines the bounds for the three terms into a final bound.Source: §7.3 · p. 19
7.4 Proof Sketch of Theorem 12
- Fixed cost and transition confidence bounds let SafeProj keep every PF-CSTRL exploration and planning policy feasible.The same safety argument applies in both stages.Source: §7.4 · p. 20
7.5 Proof Sketch for the Unknown Constraint Cost Extensions
- With unknown constraint costs, the estimation phase executes the known safe policy, then conservative cost bounds support the algorithms on the remaining episodes.The estimated bounds are used for the remaining preference-based or preference-free learning and planning.Source: §7.5 · p. 20
7.6 Proof Sketch for the Unknown Safe Policy Extensions
- When the safe policy is unknown, estimation incurs at most d violation per episode; afterward the guarantees bound total violation by d times the estimation length.The policies executed after estimation, including returned policies, are shown safe.Source: §7.6 · p. 20
8 Conclusion
The paper presents a unified safe MORL framework for cumulative and stepwise constraints, with preference-based and preference-free learning. Its guarantees depend on knowing a strictly safe policy and its costs for zero violation; when the policy is unknown, cumulative violation remains bounded by a constant.
8 Conclusion
- The framework covers cumulative and stepwise constraints, supports computing a policy for any preference from exploration data without further interaction, and bounds cumulative violation when the strictly safe policy is unknown.With a known strictly safe policy and unknown costs, it guarantees zero violation.Source: §8 · p. 20
Appendix A. Proof of Proposition 6
The appendix characterizes occupancy measures induced by stochastic Markov policies and shows that imposing safety constraints preserves a convex-polytope representation.
Appendix A. Proof of Proposition 6
- The state marginal sums a state's action occupancies, providing the denominator for reconstructing a policy's action probabilities from its occupancy measure.When a state marginal is zero, the construction uses the uniform action distribution.Source: Appendix A · p. 22
- Every feasible occupancy-measure vector corresponds to a stochastic Markov policy, and the set of such measures is a convex polytope.The proof establishes both the policy correspondence and the finite linear characterization.Source: Appendix A · p. 22
- Adding the safety inequalities characterizes the safe occupancy-measure set, which is also a convex polytope.The characterization holds in both directions between feasible measures and safe policies.Source: Appendix A · pp. 22–23
- The attainable safe objective-value set is a nonempty convex polytope because it is a linear image of the safe occupancy-measure polytope.Linear maps preserve convex combinations.Source: Appendix A · p. 23
Appendix B. Proof of Proposition 7
The appendix develops proof results for Proposition 7, establishing properties of smooth Tchebycheff minimizers over safe policies and deriving safe-occupancy, confidence, and supporting bounds for Algorithm 1’s auxiliary policies, SafeProj step, and mirror-ascent update.
Appendix B. Proof of Proposition 7
- Every minimizer of the smooth Tchebycheff scalarization over safe policies is safe Pareto optimal, and each safe Pareto-optimal value minimizes the scalarization for some positive preference vector.The converse constructs a normalized positive preference so the value minimizes the scalarization over a supporting hyperplane and hence over the safe value set.Source: Appendix B · pp. 23–24
Appendix C. Proof of Proposition 8
- All policies minimizing the smooth Tchebycheff scalarization over the safe set attain the same value on every objective.The proof uses strict convexity of log-sum-exp except along translations, then uses positive preference weights to conclude equality of objective values.Source: Appendix C · p. 24
Appendix D. Proof of Theorem 9
- The joint transition, cost, and reward confidence event, together with the required martingale events, holds with probability at least 1−δ by a union bound.The failure-probability allocation across O(m) events affects only ln(m/δ) factors, absorbed in the eO(·) notation.Source: Appendix D · p. 25
D.1 Lemmas
- With probability at least 1−δ, transition, cost, and reward estimates satisfy their confidence bounds; the transition-consistent occupancy set Θ(P_t) is a convex polytope.The three confidence guarantees are stated for all episodes and relevant states, actions, steps, and objectives.Source: §D.1 · pp. 25–27
- On the joint confidence event, SafeProj’s occupancy update is analyzed against any safe occupancy measure using step size η=T^-1/2.The lemma states this comparison for every safe occupancy measure and the occupancy measure generated by SafeProj.Source: §D.1 · p. 29
- For each objective, the proof analyzes Algorithm 1’s projected occupancy measure against a single-objective safe optimum on event E_R,C,T(δ), with η = T^-1/2.The stated result is for every objective i ∈ [m].Source: §D.1 · p. 31
- Lemma 31 states a probability-at-least-1−δ bound, simultaneously for every objective, for auxiliary policies generated by Algorithm 1.The displayed passages do not include the bound’s expression.Source: §D.1 · p. 33
- Lemma 32 analyzes SafeProj’s mixing probability ψ when its candidate occupancy measure satisfies the pessimistic cost constraint (bC − Ξ)^⊤eθ ≤ τ.The mixing probability is given by equation (12).Source: §D.1 · p. 33
- With α_t = 1/t^2 and β_t = 1/(μt), Lemma 33 gives an inequality for Algorithm 1’s mirror-ascent update.The stated inequality is expressed for an arbitrary comparator w.Source: §D.1 · p. 34
- A trajectory-sequence lemma bounds bonuses constructed from the sequence’s counts and bonuses.The supplied passage introduces the bound but omits its expression.Source: §D.1 · p. 35
D.2 Proof of Theorem 9
The proof establishes the theorem’s high-probability suboptimality guarantee by combining bounds on the learning and optimization errors. It also analyzes how the safe-policy mixture affects the reward estimates.
D.2 Proof of Theorem 9
- The error decomposition separates auxiliary single-objective learning error from smooth Tchebycheff dual optimization error.The proof bounds the difference between these terms and combines them with the decomposition.Source: §D.2 · p. 37
- The analyzed occupancy measure mixes the optimistic policy with the strictly safe policy, and the proof bounds the reward effect of this mixture.The mixture weight is ψ_t; the reward-confidence argument controls the optimistic-policy term.Source: §D.2 · pp. 38–39
- The proof combines its component bounds to establish the stated suboptimality guarantee with probability at least 1 − δ.The final step combines bounds from the decomposition and intermediate estimates.Source: §D.2 · pp. 37, 40
Appendix E. Proof of Theorem 10
These proofs show how safe-policy projection supports zero violation for executed and returned policies, and how the confidence analysis extends to preference-free planning from exploration data. The planning proof reuses the mirror-ascent analysis with K planning updates.
Appendix E. Proof of Theorem 10
- With probability at least 1 − δ, the initial policy and each subsequently executed policy satisfy the constraints, and the averaged-occupancy Markov policy has zero violation.The proof handles infeasible projections by selecting the strictly safe policy and uses convexity to show the averaged occupancy measure is safe.Source: Appendix E · pp. 40–41
Appendix F. Proof of Theorem 11
- Preference-free exploration collects one trajectory per episode; its confidence widths and transition bonus retain their forms, with final-count estimates used in planning.The proof applies the confidence lemmas to the exploration trajectories, with the resulting bounds changing only through logarithmic factors.Source: Appendix F · p. 41
F.1 Lemmas
- On the joint event, the planning-stage argument uses only fixed cost and transition confidence bounds; consequently, every policy πk+1 is safe, and Lemma 35 applies to each.Source: §F.1 · p. 42
F.2 Proof of Theorem 11
- The preference-free proof reuses the entropic mirror-ascent argument with K planning updates and normalization 1/K instead of T − 1 updates and 1/T.The proof then bounds the remaining objective difference for the averaged occupancy measure.Source: §F.2 · pp. 46–47
Appendix G. Proof of Theorem 12
The proof establishes safety for policies executed during both exploration and planning, then transfers safety to the returned Markov policy through its averaged occupancy measure. It covers both stepwise and cumulative constraint settings.
Appendix G. Proof of Theorem 12
- With probability at least 1 − δ, every exploration policy and every main planning policy satisfies the constraints.The proof applies the online confidence bounds during exploration and fixed confidence bounds during planning.Source: Appendix G · p. 48
- Convexity of the safe occupancy set makes the returned averaged occupancy measure safe, so its induced Markov policy has zero violation.The proof uses the correspondence between policies and occupancy measures.Source: Appendix G · p. 48
- When d = 1, the constraints apply at their specified time steps; when d = H, they apply cumulatively over the episode.Source: Appendix G · p. 48
Appendix H. Proofs for the Unknown Constraint Cost Extensions
The proofs extend the guarantees to estimated constraint costs and an unknown strictly safe policy. They bound the estimation phase and then apply the earlier safety and performance arguments using the estimated quantities.
Appendix H. Proofs for the Unknown Constraint Cost Extensions
- The estimated safe-policy costs satisfy γ_j ≤ γ̂_j ≤ (γ_j + τ_j)/2 < τ_j, and the estimated safety factor obeys ϕ̂_safe ≤ 4ϕ_safe with probability at least 1 − δ/2.The stopping time is bounded by 1 + 8d^2 ln(4nT/δ)/(ϱ†)^2 under the stated lower bound on T.Source: Appendix H · p. 48
H.1 Proof of Theorem 14
- Theorem 14’s proof substitutes the estimated safe-policy costs and safety factor after the estimation phase, preserving its bound with a union-bound guarantee.It applies the earlier theorem to the remaining T − t_s episodes.Source: Appendix H · p. 49, §H.1 · p. 49
H.2 Proof of Theorem 15
- During estimation for Theorem 15, the algorithm executes the strictly safe policy; afterward, the earlier argument gives zero violation for executed and returned policies.The proof conditions on estimates satisfying γ ≤ γ̂ < τ.Source: §H.2 · pp. 49–50
H.3 Proof of Theorem 16
- For Theorem 16, the proof applies the preference-free bound to the remaining exploration episodes and K planning iterations using estimated safe-policy costs.The estimated safety factor is also bounded by 4ϕ_safe.Source: §H.3 · p. 50
H.4 Proof of Theorem 17
- For Theorem 17, the proof establishes safety throughout preference-free exploration and planning, and zero violation for the returned policy.It applies the earlier proof using γ̂ in place of γ.Source: §H.4 · p. 50
Appendix I. Proofs for the Unknown Safe Policy Extensions
- The unknown-safe-policy extension estimates a positive safety margin, then defines a safe-policy estimate by mixing the policies executed during estimation.Algorithm 4 sets γ̂_j = τ_j − ϱ̂.Source: Appendix I · p. 50
I.1 Lemmas
- The auxiliary lemmas bound the stopping time by Õ((H^4|S|^2|A| + nd^2)/ϱ^2) and show the estimated mixture policy satisfies C⊤θ_P,π̂† ≤ γ̂ < τ.The margin estimate also satisfies ϱ̂ ≥ ϱ/2 > 0.Source: §I.1 · pp. 52–53
I.2 Proof of Theorem 18
- With probability at least 1 − δ, the estimation phase ends before T and the earlier CSTRL guarantee applies to the remaining episodes using the estimated safe policy.The proof uses the estimated safety factor in place of the known one.Source: §I.2 · pp. 53–54
I.3 Proof of Theorem 19
The proofs establish high-probability safety by bounding violations during estimation and showing that subsequent policies, including returned policies, are safe. They also give a preference-free guarantee and supporting KL-divergence bounds.
I.3 Proof of Theorem 19
- For Theorem 19, CSTRL policies after estimation and the returned policy are safe, while total violation is bounded by d t_s.The bound t_s = Õ((H^4|S|^2|A| + nd^2)/ϱ^2) is independent of T.Source: §I.3 · p. 54
I.4 Proof of Theorem 20
- Theorem 20's proof transfers Theorem 11's guarantee to T − t_s exploration episodes and K planning iterations, with overall probability at least 1 − δ.On the estimation event, the conservative cost bound implies bϕ_safe ≤ 4d^2/ϱ^2.Source: §I.4 · p. 54
I.5 Proof of Theorem 21
- After estimation, every policy executed by preference-free exploration and planning is safe, the returned policy has zero violation, and total violation is at most d t_s.The estimation phase lasts at most Õ((H^4|S|^2|A| + nd^2)/ϱ^2) episodes on the stated event.Source: §I.5 · p. 55
Appendix J. Other Supporting Lemmas
- The supporting lemmas give a KL-divergence three-point inequality and bound the divergence and L1 changes caused by simplex smoothing.For smoothing by α, the KL difference is at most α log m and the L1 change at most 2α.Source: Appendix J · p. 55