Combining MORL with Restraining Bolts to Learn Normative Behaviour

1 Introduction

Autonomous agents play an increasingly significant role in society, and Reinforcement Learning (RL) [Sutton and Barto, 1998] offers one of the most promising means of designing them. In this approach, agents operating in a given environment are assigned rewards or punishments, and thereby learn which actions are optimal with respect to their goals. As RL-based agents often interact with humans, it is crucial to ensure their actions comply with legal, ethical, and social norms; these interactions present the challenge of restraining their behaviours while still enabling them to fulfil their goals.

In this work, we focus on model-free RL, where the agent has no model of its environment and relies on exploration to learn optimal behaviour. In such scenarios, an effective technique for defining boundaries for the actions of RL-based agents is the restraining bolt (RB) [De Giacomo et al., 2019], inspired by a device from Star Wars that enforces obedience in droids. This technique shapes the agent's behaviour, aligning it with LTLf (Linear Temporal Logic over finite traces) specifications by providing additional rewards when they are satisfied. While this approach ensures reasonable agent performance while adhering to a wide range of constraints, it is not specifically designed to address norms. Norms differ from regular constraints in that they define ideal rather than actual behaviour. Norms can be violated, are often conditional, can be activated or overridden by other norms, and may arise from the compliance with or violation of other norms (e.g., contrary-to-duty (CTD) obligations).

To address adherence to norms, [Neufeld et al., 2024] introduced Normative Restraining Bolts (NRBs) - an adaptation of RBs that uses LTLf formulae to specify norm violations rather than compliant behaviour. NRBs assign negative rewards (punishments) to discourage norm violations, making it effective for managing intricate normative dynamics, such as conditional obligations/prohibitions, CTDs, permissions as exceptions, and temporal obligations. While effective, NRBs rely on trial-and-error reward tuning to ensure norm adherence and therefore can be unwieldy when trying to resolve norm conflicts. Moreover, they require retraining to accommodate norm updates, and do not lend themselves to guarantees that optimal policies minimize norm violations.

In this paper, we propose an enhanced approach to address these limitations by introducing Ordered Normative Restraining Bolts (ONRBs). We frame learning with Normative Restraining Bolts (NRBs) as a multi-objective RL (MORL) problem, where each norm is treated as a separate objective, and we define a priority relation over each objective, depending on the importance of each norm. In contrast to restraining bolts [De Giacomo et al., 2019], which rely on manually selected rewards to enforce LTLf specifications, we build on the work of [Rodriguez-Soto et al., 2022; Rodriguez-Soto et al., 2023] and propose an algorithm that automatically derives the punishments required to enforce lexicographically ordered norms. Our approach adapts MORL techniques, specifically the Convex Hull Value Iteration (CHVI) algorithm [Barrett and Narayanan, 2008], to this setting. Beyond handling the normative dynamics addressed by NRBs, our framework effectively resolves conflicts between norms having differing priority, and supports norm updates. Moreover, it provides formal guarantees that optimal policies minimize norm violations with respect to the defined ordering.

Related Work. Reinforcement learning has emerged as a promising method for teaching autonomous agents normative behaviour (although, most approaches, while amenable to other kinds of norms, focus on ethical norms), e.g. [Abel et al., 2016]. Top-down approaches (cf. [van Rysewyk and Pontier, 2015]), which begin with given norms/values and design reward functions reflecting them, include [Rodriguez-Soto et al., 2021; Rodriguez-Soto et al., 2022; Ecoffet and Lehman, 2021; Neufeld, 2024; Neufeld et al., 2024]. In [RodriguezSoto et al., 2021; Rodriguez-Soto et al., 2022] (and then with multiple values in [Rodriguez-Soto et al., 2023]), though the ethical reward functions are specified manually, a method is provided to ensure that what they call an "ethical policy" is learned. The goal is to allow the agent to learn the defined ethical behaviour while still accomplishing a non-ethical objective; this multi-objective problem is converted to a singleobjective problem through linear scalarization of the agent's value functions with a vector of weights, and the minimum weights needed to guarantee that the agent's behaviour is ethical are computed via CHVI [Barrett and Narayanan, 2008]. Even with the automatic weight selection, manually specifying the ethical reward function still allows for human error. A common way to avoid this (especially in safe RL) is to utilize LTL(f) specifications. One approach to learning under LTL constraints is known as shielding, originating in [Alshiekh et al., 2018], and later expanded to model-free RL [Jansen et al., 2020]; inspired by this approach and partially based on the framework in [De Giacomo et al., 2019] is [Varricchione et al., 2024], designed for safe RL. Another approach (closer to learning with RBs [De Giacomo et al., 2019]) involves learning to maximize the probability of satisfying an LTL(f) formula, e.g. [Ding et al., 2011b; Ding et al., 2011a]; although this technique cannot handle norms (see e.g. [Neufeld et al., 2022]), the modification in [Kasenberg and Scheutz, 2018] does and can also deal with norm conflicts - yet, it does not mention CTDs or permissions. Subsequent approaches also include [Kasenberg et al., 2020] (which employs a preference ordering) and [Li et al., 2023]; however, like [Kasenberg and Scheutz, 2018], these only accommodate model-based RL. [De Giacomo et al., 2023; De Giacomo et al., 2024] both discuss learning optimal behaviour in an MDP with multiple objectives, including maximizing the probability of satisfying an LTLf formula. These approaches do not reward LTLf specifications individually (which is precisely what makes the restraining bolt suitable for dealing with norms), and are all model-based. [Hahn et al., 2021; Hahn et al., 2023] employ lexicographic B¨uchi automata to learn over lexicographic orderings on ω-regular objectives; however, they do not deal with normative reasoning.

2 Background

Reinforcement Learning. Model-free RL problems consist of an agent interacting with an unknown environment; this environment is modelled as a Markov decision process (MDP):

Definition 1 (Labelled MDP). An MDP is a tuple

where S is a set of states, A is a function A : S → 2Act from states to sets of possible actions (Act is the set of all actions available to the agent), Pr : S×Act×S → [0, 1] is a function that gives the probability Pr(s, a, s′ ) of transitioning from state s to state s′ after performing action a, L : S ×Act → 2AP is a labelling function from state-action pairs to sets of atomic propositions, and R : S×Act → R is a scalar reward function over states and actions.

The goal of RL is to find a policy π : S → Act which designates optimal behaviour; this optimality is determined with respect to a value function defined as:

which represents the expected accumulated value onward from state s if policy π is followed. In the above function, γ ∈ [0, 1] is a discount factor (so that rewards in the future do not have as much weight as the current reward). We can similarly define a Q-function:

which predicts the expected cumulative reward from R given that the agent is in state s taking action a.

The goal of RL is to find an optimal policy π∗ such that

where Π is the set of all policies over the MDP. This is accomplished by learning a Q-function s.t. V π∗ (s) = maxa∈A(s) Qπ∗ (s, a) and π∗ (s) ∈ argmaxa∈A(s)Qπ∗ (s, a). Throughout this paper we will be using the predominant model-free RL technique, Q-learning, to learn Qπ∗ .

MOMDPs. We generalize the notion of an MDP to have instead of a single scalar reward function R, a vector of reward functions ⃗R = [R1, ...,Rn]T , where each Ri corresponds to an individual objective in a multi-objective MDP (MOMDP). We can strategically combine reward functions to learn a policy that prioritizes or balances certain objectives; perhaps the simplest and most common approach is linear scalarization [Roijers et al., 2013a]. This involves selecting a vector ⃗w = [w1, ...,wn]T (where each wi is a weight for the objective corresponding to Ri) and learning a Q-function Qi(s, a) for each objective and following the policy π∗ (s) ∈ argmaxa∈A(s) ⃗Q(s, a) · ⃗w.

LTLf. Linear Temporal Logic (LTL) [Pnueli, 1977] extends classical propositional logic with two temporal operators. Its language is given by (let AP be a set of atomic propositions):

◦ is the "next" operator (◦φ iff φ is true in the next state), and U is the "until" operator (φUψ iff φ is true until ψ is true). We can also define a dual to the until operator, the "release" operator φRψ ≡ ¬(¬φU¬ψ) (φ releases ψ, or ψ is true up until φ is true, if ever), as well as the "finally" operator ♢φ ≡ ⊤Uφ (φ is eventually true), and its dual, the "globally" operator □φ ≡ ¬♢¬φ ≡ ⊥Rφ (φ is always true). ⊤, ∧, →, and ↔ can be derived in the usual ways.

LTL formulas are interpreted over infinite traces σ ∈ (2AP )ω ; LTLf [De Giacomo et al., 2013] differs from LTL only in that the traces that formulae are interpreted over are finite, of length λ. We say σ |= φ when σ satisfies φ.

Deterministic Finite Automata (DFAs). These are tuples A = ⟨Σ,Q, δ, q0, F⟩ consisting of a finite input alphabet Σ, a finite set of states Q, a transition function δ : Q× Σ → Q, an initial state q0 ∈ Q, and a set of final states F ⊆ Q. We say A accepts a word σ = ⟨σ0, ...σn⟩ ∈ Σ∗ if for the run q0, q1, ..., qn generated by inputting σ to A (i.e., qi+1 = δ(qi, σi) for i ∈ {0, ..., n - 1}), qn ∈ F .

LTLf formulas over AP can be transformed into equivalent DFAs [De Giacomo and Favorito, 2021; De Giacomo et al., 2015] such that σ |= φ (where Aφ = ⟨2AP ,Q, δ, q0, F⟩ is the DFA corresponding to φ) if and only if Aφ accepts σ.

Norms. We are interested in teaching RL agents to comply with norms that regulate behaviour. These include obligations (Oα, or "it is obligatory that α"), prohibitions Fα ≡ O¬α (we refer to obligations and prohibitions both as obligations), and permissions Pα, which often act as exceptions to obligations to the contrary (these are only kind of permissions we will consider here). Norms are often conditional, represented as O(α|β) ("α is obligatory when β"). We refer to a collection of such norms as a normative system.

As is well known LTL (and hence LTLf) cannot model norms explicitly [Governatori, 2015; Neufeld et al., 2022]; i.e., there is no LTL(f) formula φ that faithfully models an obligation. However, LTL(f) can be used to implicitly represent norms through modeling the conditions under which they are complied with or violated, e.g. [Alechina et al., 2018]. In this paper we will utilize violation specifications (which specify the violation condition of a norm) to represent obligations.

Using temporal logics to implicitly represent norms allows us to model also temporal obligations [Governatori et al., 2007]. Simple, conditional atemporal obligations (punctual obligations) O(α|β) can be represented through their violation conditions as ♢(β ∧¬α). Permissions P(¬α|β1 ∧β2) (as exception to an obligation O(α|β1)) can be represented with an exception specification ♢(¬α∧β1∧β2). Maintenance obligations OMδ (α|β) (which demand that upon being triggered with β, α is obligatory in each state until the deadline δ) can be modelled as ♢(β ∧ ¬δU¬α). Achievement obligations OAδ (α|β) (which state that after the trigger β, it is obligatory to achieve α before δ) can be modelled as ♢(β ∧ ¬αUδ).

3 Normative Restraining Bolts

A restraining bolt [De Giacomo et al., 2019] is a collection of LTLf formulae with associated rewards; the idea is that satisfying a given formula will award the RL agent the corresponding reward, incentivising the agent to satisfy the formula, and accommodating the learning of non-Markovian objectives. In [Neufeld et al., 2024], this technique was adapted to use LTLf formulae that specify norm violations rather than compliant behavior, assigning negative rewards (punishments) to discourage such violations. This "upsidedown" approach, inspired by the Andersonian reduction of deontic logic into modal logic [Anderson, 1958], avoids rewarding the agent for compliance in scenarios where no norm is triggered; in the case of conditional norms, this prevents the agent from attempting to extend its runtime solely to continue reaping rewards for compliance. Below, we present an adaptation of the normative restraining bolt NRB, which explicitly partitions the violation specifications based on the type of obligation the specification corresponds to.

Definition 2 (Normative Restraining Bolt (NRB)). A NRB is a tuple RB = ⟨L, {(φi,-ri)}Ni=1 ⟩, where L : S × Act → 2AP is a labelling function from state-action pairs to sets of atomic propositions, each ri ∈ R+, and N = n +m. For i ∈ {1, ..., n}, φi is the violation specification of a punctual or achievement obligation and for i ∈ {n+1, ..., n+m}, φi is the violation specification of a maintenance obligation.

Like restraining bolts, NRBs can be combined with a regular labelled MDPM= ⟨S,A, Pr,L,R⟩ (provided their labelling functions are identical) to shape the behaviour of an agent learning in M. Originally, restraining bolts combined with MDPs were directly translated into non-Markovian reward decision processes (NMRDPs, i.e. MDPs that attribute a reward to partial traces, instead of single state-action pairs); this NMRDP was then transformed into an extended MDP [Brafman et al., 2018] that was equivalent [Bacchus et al., 1996] to the NMRDP (in that the optimal policy for the extended MDP would yield an optimal policy in the NRMDP as well). We will not bring NMRDPs into the picture; instead we will skip right to a discussion of extended MDPs, which we will analyse independently of the equivalent NMRDP.

Definition 3 (Extended MDP). Let RB = ⟨L, {(φi,-ri)}Ni=1 ⟩ be a restraining bolt and M = ⟨S,A, Pr,L,R⟩ a labelled MDP. Furthermore, let each Aφi = ⟨2AP ,Qi, qi,0, δi, Fi⟩ be the DFA corresponding to each φi in RB. Then the extended MDP is MRB = ⟨S′ , A′ , P r′ , L′ , R′ ⟩, where:

• L′ (q1, ..., qN, s, a) = L(s, a)
• R′ (q1, ..., qN, s, a) =

We depart from the definition in [Neufeld et al., 2024] in two ways. First, we integrate the ad hoc automaton 'resetting' mechanism from their paper into the MDP. This mechanism handles repeated violations by redirecting transitions that would be into the final state instead to the initial state (for achievement and punctual obligations) or the previous state (for maintenance obligations). Moreover, [Neufeld et al., 2024] defines the reward function for the extended MDP associated with a normative restraining bolt as R′ (q1, ..., qN, s, a) = R(s, a) - ∑i: δi(qi,L(s)∪{a})∈Fi ri. In contrast, we split the second term into negatively weighted characteristic functions for each automaton's set of final states, a modification that proves useful in the next section when converting the problem into an MORL framework.

3.1 Reformulation as aMORL Problem

As it turns out, we can represent learning over MRB as a MORL problem. Recall that one way to learn an optimal policy in an MOMDP is to learn a Q-function for each objective, and select actions based on the inner product of these Q-functions and a vector of weights, corresponding the optimal policy of the scalarized reward function ⃗w · ⃗R. Let ⃗R = [-Rφ1 , ...,-RφN ,R]T and ⃗w = [r1, ...rN, 1]T ; then it is easy to see that for s ∈ S′ and a ∈ A′ (s):

This describes a scalarized reward function of an MOMDP, balancing a norm-agnostic objective with normative objectives; we adapt the term "compliance MDP" [Neufeld, 2024]:

Definition 4 (Extended Compliance MDP). We transform the extended MDP from Definition 3 into a MOMDP:

Learning over the extended compliance MDP is not difficult; we can use regular Q-learning over a scalarized vector of Q-functions ⃗Q = [Qπ-φ1 , ...,Qπ-φN ,Q]T associated with ⃗R. At each transition ((q1, ..., qN, s), a, (q′1 , ..., q′N , s′ )) (where a ∈ argmaxa′∈A′ (q1,...,qN,s) ⃗w · ⃗Q((q1, ..., qN, s), a′ ) and each q′i = δi(L(s, a), qi)) during training we update Q as usual with R(s, a) and update each Qπi -φi with -1 iff q′i ∈ Fi.

This approach of rewriting MRB as the MOMDP M′RB has several advantages. Firstly, it becomes more clear what we are learning; namely that we are dealing with a multiobjective problem in which R defines one objective (with weight 1), and visiting the final states of each Aφi as few times as possible is another. It also opens the possibility to accommodate norm changes; provided we have learned a Qfunction for an individual norm with violation specification φi in a given environment, we can temporarily add (by maintaining the associated ri in ⃗w) or remove (by replacing ri with 0) this norm from consideration in the final policy.

Most importantly, framing our problem in this way introduces the potential to leverage MORL techniques, such as algorithms that elucidate the correct rewards (weights) ri to be associated with each φi, ensuring that specific behaviours are prioritized. In particular, [Rodriguez-Soto et al., 2021] (and subsequent works by the same authors) utilize convex hull value iteration (CHVI) [Barrett and Narayanan, 2008] and linear programming to identify the minimal weights required to learn what they call an "ethical policy".

Finally, this MORL framing allows us to define what we are trying to learn precisely - a maximally compliant policy:

Definition 5 (Maximally Compliant Policy). Let Π be the set of all policies over the extended compliance MDPM′RB . A

policy π∗ ∈ Π is maximally compliant iff it is optimal w.r.t. the value functions V π -φi corresponding to each -Rφi . That is, π∗ is maximally compliant forM′RB iff for all s ∈ S′ :

Note that such a policy exists only if there are no dilemmas (cases where obeying one norm requires violating another); however, these cases can be addressed by imposing a priority structure over conflicting norms. In the next section, we will explore how to apply an approach like [Rodriguez-Soto et al., 2023] for this solution. For simplicity, for now we consider sets of norms that do not result in dilemmas. We will elaborate on this below, but first we take a closer look at what we actually achieve by learning in an extended compliance MDP.

Theorem 1. For the extended compliance MDP M′RB = ⟨S′ , A′ , Pr′ , L′ , ⃗R′ ⟩ where ⃗R = [-Rφ1 , ..., -RφN , R]T , any maximally compliant policy minimizes the discounted count of violations of the norm associated with the violation specification φi for each i ∈ {1, ...,N}.

Proof. Recall that maximally compliant policies are policies π∗ such that Equation 1 holds. Let V π φi and V π -φi be the value functions associated with Rφi and with the objective defined by -Rφi , respectively. Then, if we have a maximally compliant policy π∗ , for each individual objective corresponding to an individual violation specification φi:

by the linearity of conditional expectation. Hence the optimal policy π∗ for each violation specification φi is a policy s.t.:

Then, since V π φi (s) is the expected discounted count of visitations of the final states of Aφi (recall, Rφi yields a count of 1 when a final state is reached), which only occurs when φi is momentarily satisfied and thus the associated norm is violated, the discounted count of violations is minimized.

To ensure that we learn a maximally compliant policy (Defn. 5), we need the following condition to hold:

Condition 1. Given a compliance MDP with a reward vector ⃗R = [-Rφ1 , ...,-Rφn ,R]T with associated optimal Qfunctions Qπ1 -φ1 , ..., QπN -φN . Then:

In other words, among the possible optimal behaviours available for each φi, there is always an action that is optimal for all of them. Based on this condition we can prove:

Theorem 2. For any compliance MDPM′RB for which Condition 1 holds, there is a maximally compliant policy.

Proof. ∀i ∈ {1, ...,N} there exists at least one policy πi s.t.

The Condition 1 implies that for each s ∈ S′ , there exists an a ∈ A(s) such that ∀i ∈ {1, . . . , N}

Equivalently, there exists an a s.t. Qπi φi (s, a) = V πi φi (s) for each i. Then the policy π∗ (s) ↦→ a is optimal for all φi; i.e., V π∗ -φi (s) = maxπ∈Π V π -φi (s), ∀i ∈ {1, . . . , N}.

4 LeveragingMORL

Framing learning with NRBs as an MORL problem has several advantages. Besides clarifying the nature of the problem as multi-objective, this framing yields a more modular agent, where individual norms can be removed or reintroduced as objectives after an optimal Q-function has been learned. Most importantly, it allows us to use MORL techniques like CHVI to determine the weights needed to learn a maximally compliant policy. We can further extend our framework to encompass normative systems capable of handling (potential) norm conflicts by defining a priority relation among them. This approach allows us to omit Condition 1 and utilize a combination of CHVI and linear programming to compute the weights required to enforce the specified priority relation. We will formalize this enhancement of NRBs as ordered NRBs.

4.1 Ordered Normative Restraining Bolts

Even if we select a reward ri > 1 corresponding to φi, it may be the case that the agent does not prioritize avoiding satisfying φi over its main objective, described by R - in fact, it likely won't. Especially in cases where obeying a norm results in penalties from R, or two norms conflict and we want to prioritize one over another, we will need to adjust ri so that the expected value of undesirable behaviour is offset by the value of the correct choices. However, rather than knowing which weights will lead us to a maximally compliant policy, it is more likely we will have some notion of what norms we want to prioritize. This leads us to define:

Definition 6 (Ordered Normative Restraining Bolts (ONRBs)). An ONRB is a tuple Φ = ⟨L, {φi}Ni=1 ,>Φ⟩, where each φi is a violation specification and >Φ is a total ordering 1 over the set {φi}Ni=1 .

Note that from a regular labelled MDP and the ordered normative restraining bolt Φ we can also get an extended compliance MDP M′Φ. With ONRBs, our goal becomes finding a prioritized compliance policy:

1 The framework can be extended to support some partial orders.

Definition 7 (Prioritized Compliance Policy). Let [V1, ..., VN]T be the value functions of each -Rφi ordered according to >Φ, and let Π1 be the set of all policies over the extended compliance MDPM′Φ. Then a prioritized compliance policy π∗ is a policy such that for all s ∈ S′ :

The above expression defines a lexicographic ordering over value functions (as done in [Rodriguez-Soto et al., 2023]), where we first select policies optimal for the highest-ranked normative objective, then from among those policies we take those optimal for the second highest, and so on.

Theorem 3. For the extended compliance MDPM′Φ with the associated ordered normative restraining bolt Φ there exists a prioritized compliance policy.

Proof. By induction on the size of the ordered normative restraining bolt (i.e., the number of violation specification N).

If there is only one violation specification φ1 in Φ, the PCP is simply the optimal policy π∗ such that

where Π is the set of policies over M′Φ. Now suppose there is a PCP for M′Φ defined over value functions [V1, ..., VN]T . Consider an ONRB Φ′ = Φ ∪ {φN+1} where φi >Φ′ φN+1 for all i ∈ {1, ..., N}. Let ΠN+1 ⊆ Π1 be the reduced policy set defined recursively in Definition 7, then we know there is a π∗ such that

Learning a PCP requires applying Q-learning as seen before to an extended compliance MDP M′Φ - via linear scalarization - by converting >Φ into a weight vector ⃗w.

4.2 Implementing ONBRs

We cannot learn compliant behaviour directly from an ONRB paired with an MDP via linear scalarization, as demonstrated in the previous section; we need to retrieve the weights necessary to get the prioritized compliance policy, transforming the ONRB into a regular NRB in order to construct an extended compliance MDP. To do this, we employ a weight function.

Definition 8. The weight function wΦ : LLTLf → R maps an LTLf specification φi associated with an ONRB Φ to the minimum weight ri that ensures that we learn a prioritized compliance policy.

Computing wΦ is in general computationally intensive, (albeit fairly trivial in the case studies in Sections 5.2-3). However, this computation only needs to be performed once, before training the agent. We outline this 'pre-processing' step below, beginning with a review of the notion of a convex hull.

Definition 9. Let Π be the set of all possible policies over a given MOMDP. The convex hull of Π, CH(Π) is defined as:

That is, the convex hull represents the subset of policies whose linearly scalarized values are maximal for some ⃗w [Roijers et al., 2013b]. Following [Rodriguez-Soto et al., 2023], our implementation uses the partial convex hull P(Π), which is a subset of CH(Π), containing all policies that are maximal for a given ⃗w such that ri > 0 for all i ∈ {1, ...,N} and the weight corresponding to R is 1.

Following [Rodriguez-Soto et al., 2021; Rodriguez-Soto et al., 2022; Rodriguez-Soto et al., 2023], we have utilized convex hull value iteration (CHVI) to compute the partial convex hull of the set of policies Π for M′Φ. For brevity, we omit the algorithm's details, noting only that it computes the partial convex hull P(Π), by enhancing value iteration with four operations - scalarization, translation, merging, and summation - which akin to the standard value iteration perform updates on the value function, but operate over entire convex hulls [Barrett and Narayanan, 2008]. These computations increase the runtime of the standard value iteration algorithm by an exponential factor given by the size of the partial convex hull. As P(Π) includes a point corresponding to each policy that is optimal for some ⃗w, the partial convex hull can reach a size of |Act||S| [Barrett and Narayanan, 2008]. In our implementation, the number of states expands to |S| ∏Ni=1 ni (where ni is the number of states in the automaton Aφi ; see Remark 1). Consequently, computing the partial convex hull introduces an added complexity factor of O(|Act||S| ∏Ni=1 ni·(⌊ N2 ⌋) )[Barrett and Narayanan, 2008]. However, the runtime can be reduced in practice by restricting |S| ∏Ni=1 ni to reachable state configurations (q1, ...qN, s).

Remark 1. Although translating an LTLf formula into a DFA is double exponential in the formula's size [De Giacomo et al., 2015], the key factors are the number of temporal operators and their nesting depth. For many, if not most, norms (including those discussed in Section 5), the translation and the resulting automata size remains manageable, reducing the state space and preprocessing time.

Given CH(Π) (or P(Π) in our case), we can select for each state the vector of values ⃗V π∗ (s) corresponding to our PCP π∗ as per Definition 7. Once we pick out the value vector corresponding to π∗ , we can use Linear Programming to discern the minimum weights necessary to ensure this policy is followed throughout the trajectory (and indeed in any state). Following [Rodriguez-Soto et al., 2023] we solve the linear program (LP) over ⃗w = [r1, ...rN, 1]T :

where ϵ ∈ R+, π∗ is the optimal policy, and P the partial convex hull. Note that we modified the linear program in [Rodriguez-Soto et al., 2023] to reflect that the optimal value possible for our normative objectives is 0, and ensure that a PCP (for all states) is learned. The complexity for solving the LP, retrieving the weight function wΦ, depends on the choice of algorithm; using the simplex algorithm (efficient in practice [Spielman and Teng, 2004]), a worst-case exponential complexity can be reached [Klee and Minty, 1972].

Remark 2. We can reduce the size of the above LP substantially; in practice, we only need the constraints ⃗w · ⃗V π∗ (s) ≥ ⃗w · ⃗V π (s) + ϵ for states s we can actually start from. For environments with only one single start state s0 (as the one in Sec. 5) the implementation only needs to use as constraints ⃗w · ⃗V π∗ (s0) ≥ ⃗w · ⃗V π (s0) + ϵ for all π ∈ P \ {π∗ }.

Now that we have computed the weight function wΦ associated with Φ in the preprocessing step, we can essentially transform Φ into the regular normative restraining bolt NRB = ⟨L, {(φi,wΦ(φi))}Ni=1 ⟩ and use the given rewards to compute a PCP over the extended compliance MDP M′NRB = M′Φ with the ⃗w associated with NRB.

Theorem4. Let the associated extended complianceMDP of an ORNB be M′Φ = ⟨S′ ,A′ , Pr′ ,L′ , ⃗R⟩. Every policy π∗ which is optimal for M′Φ w.r.t. ⃗w = [r1, ..., rN, 1]T (where each ri = wΦ(φi)) is a PCP for Φ.

Proof. Let π∗ be optimal for M′Φ with respect to ⃗w = [r1, ..., rN, 1]T (ri = wΦ(φi)). Then for all s ∈ S′ :

which is equivalent to the conditions in the above LP if we take ϵ = 0. The policy represented by the value function on the left hand side of these inequalities (same as our ⃗V π∗ (s)) is by construction a PCP, so our π∗ is as well.

Implementing Norm Change

Each norm having its own Q-function enables the temporary suspension of individual norms. Instead of selecting actions at step t based on ⃗Qπ∗ (st, at) · ⃗w = Qπ∗ (st, at) + ∑ni=1 riQπ∗ φi (st, at), we can select actions based on Qπ∗ (st, at) + ∑ni=1 rif(φi, t)Qπ∗ φi (st, at), where f : LLTLf ×N→B, which returns 1 if the norm is in force, and 0 otherwise. The suspension or re-addition of norms may require us to solve the LP again (where we set the ri corresponding to each suspended norm to 0), but there is no need to repeat CHVI.

5 Case Studies

We will showcase ONRBs within an environment that highlights how the agent prioritizes adherence to a set of norms, even when doing so conflicts with its primary objective 2 . Despite these constraints, the agent should maintain optimal behaviour within the prescribed boundaries. We utilize the 'Travelling Merchant' environment, first introduced in [Neufeld et al., 2022]. This environment is an elaborate adaptation of the resource-gathering game from [Barrett and Narayanan, 2008] (seen again in e.g. [Vamplew et al., 2011]), which is in turn inspired by various strategy games. It entails an RL agent, a merchant, traversing a map and collecting resources to sell at a market on the other side of the map. The available resources are wood (extracted from trees, the green squares in Fig. 1(a-c)) and ore (extracted from rocks, the light grey squares); to collect a resource, the agent must perform the action extract in a cell where a resource is situated. "Dangerous" areas (pink squares) on the map exist where the agent will be attacked by bandits, at which point the agent has three choices: it can fight and end the attack, negotiate (giving up its inventory by using unload, also ending the attack), or try to escape (which fails with a certain probability; for the sake of simplicity we have set this to 1). The agent is rewarded based on how many resources it gathers, and how many items it unloads at the market; it is punished when it unloads its resources elsewhere. States are labelled with the cell type (e.g., at danger), whether or not the agent is being attacked (attack), whether or not the sun is down (sundown), and what it has in its inventory (e.g., has ore).

2 Implementation can be found at: https://github.com/lexeree/ ordered-normative-restraining-bolts

5.1 Managing Conflicting Norms

Suppose the merchant's highest priority, upon leaving home, is OAsundown (at market|at home), that is to visit the market before sunset; this norm has the violation specification φ1 := ♢(at home ∧ ¬at marketUsundown). The merchant's second priority is to avoid dangerous areas, F(at danger), which has the violation specification φ2 := ♢(at danger). Also let >Φ1 = {(φ1, φ2)}. Our ONRB will then be: Φ1 = ⟨L, {φ1, φ2},>Φ1 ⟩, where L is the merchant environment's labelling function. Using the preprocessing of the ONRB described in Section 4.2, we find that wΦ1 (φ1) = 15.5 and wΦ1 (φ2) = 57.5 (rounded up).

Figure 1(a) shows that to reach the market (blue square), the merchant must pass through a dangerous area (leftmost pink square). With only F(at danger), the agent circles near its home (yellow square) until the episode times out. However, since we derived the above based on the priority of the norm OAsundown (at market|at home), the agent nevertheless passes through the first dangerous area in order to arrive at the market before sundown, while avoiding the second dangerous area, despite that path leading to more resources.

The computations above were performed with an AMD Ryzen 7 5800H with Radeon Graphics (8 cores, 3.2 GHz) and 16 GB RAM, except the computation of wΦ1 , which ran on one core of an AMD EPYC 9334 (2.7 GHz), taking ∼2.5 hrs and <256 GB RAM.

5.2 Contrary-to-duty Obligations

We implement a set of norms already used in [Neufeld et al., 2024] with the purpose of illustrating the computation of the exact weights provided by the algorithm in Section 4.2. For the purposes of CTDs, we apply an option in the environment to force the agent to move toward the market (to avoid getting trapped around the home square). The norms are φ2 (from Section 5.1) and the CTD obligation O(unload|at danger ∧ attacked) stating that if the agent enters a dangerous area and is attacked, it must negotiate by unloading its resources. This norm has the violation specification φ3 := ♢(at danger∧attack∧¬unload). The ONRB is then Φ2 = ⟨L, {φ2, φ3},>Φ2 ⟩ (where the order >Φ2 is irrelevant), and when we compute the associated weights, we get wΦ2 (φ2) = 2.9 and wΦ2 (φ3) = 67.7.

Figure 1(b) shows the agent obeying the CTD when forced to pass through the first dangerous area, but avoiding the second, fulfilling the primary obligation when possible.

5.3 NormChange

Assume the agent is forbidden from extracting wood, F(extract|at tree); this norm has the violation specification φ4 := ♢(at tree ∧ extract). Suppose also the permission P(extract|at tree ∧ ¬has wood) with the exception specification 3 φ5 := ♢(at tree ∧ ¬has wood ∧ extract) - but this permission doesn't come into force until 15 time steps have passed. The ONRB will be: Φ3 = ⟨L, {φ4, φ5}, >Φ3 ⟩, for which we compute wΦ3 (φ4) = 88.1, and take the exception specification to have the same weight, but negative: wΦ3 (φ5) = -88.1, while f(φ5, t) = 0 for all t < 15.

Figure 1(c) shows the agent not extracting from the first tree, as the permission to extract wood is not yet active; once it is, the agent exercises it to extract from the second tree, and thereafter obeys the prohibition on extracting wood.

6 Conclusions

We introduced ordered normative restraining bolts, made possible by a MORL reformulation of learning with NRBs. Our framework eliminates the need to manually assign punishments to violation specifications by allowing explicit orderings over norms and providing an algorithm to derive punishments that enforce these lexicographically ordered norms. Like NRBs, ONRBs handle CTD obligations, selected permissions, and temporal obligations, while also addressing conflicts between prioritized norms and norm changes. Furthermore, it accommodates formal guarantees that optimal policies minimize norm violations w.r.t. the defined ordering.

Nevertheless, the computational cost of the required preprocessing is steep, and further research to reduce complexity is needed; using CHVI with linear scalarization is only one way to implement the multi-objective problem we have defined, and there are other MORL-based avenues we can explore. This would enable experimentation in more complex environments. However, tabular Q-learning is unsuitable for complex scenarios, and so extending our technique to Deep RL would be a major step forward.

3 As in [Neufeld et al., 2024] we accommodate permissions by assigning positive rewards when an exception condition applies.

Acknowledgments

This research was funded in whole or in part by the Vienna Science and Technology Fund (WWTF) project ICT22-023 and the Austrian Science Fund (FWF) 10.55776/COE12.