Can an AI Agent Safely Run a Government? Existence of Probably Approximately Aligned Policies

Authors: frédéric  berdoz
roger  wattenhofer
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 10:37:40

Abstract: While autonomous agents often surpass humans in their ability to handle vast and complex data, their potential misalignment (i.e., lack of transparency regarding their true objective) has thus far hindered their use in critical applications such as social decision processes. More importantly, existing alignment methods provide no formal guarantees on the safety of such models. Drawing from utility and social choice theory, we provide a novel quantitative definition of alignment in the context of social decision-making. Building on this definition, we introduce probably approximately aligned (i.e., near-optimal) policies, and we derive a sufficient condition for their existence. Lastly, recognizing the practical difficulty of satisfying this condition, we introduce the relaxed concept of safe (i.e., nondestructive) policies, and we propose a simple yet robust method to safeguard the black-box policy of any autonomous agent, ensuring all its actions are verifiably safe for the society.

Main paper: 
 introduction: 
 The deployment of AI systems in critical applications, such as social decision-making, is often stalled by the following two shortcomings: 1) They are brittle and usually provide no guarantees on their expected performance when deployed in the real world [8] , and 2) there is no formal guarantee that the objective they have been trained against, typically a scalar quantity such as a loss or a reward, faithfully represents human interest at large [41] . Addressing these limitations is commonly referred to as AI alignment, an umbrella term including a wide array of methods supposed to make AI systems of different modalities behave as intended [17, 24] .Yet, to our knowledge, every metric for alignment is a posteriori, i.e., a system is deemed aligned as long as it does not display misaligned behavior (e.g., through red teaming [14] ). This stems from the fact that most of these methods focus on aligning generative models of complex modalities (text, images, video, audio, etc.) where the input and output domains are particularly vast, and where no single metric can perfectly represent the intended behavior.In the context of critical (e.g., social) decision processes, where an autonomous agent must repeatedly take actions in a complex environment with many stakeholders, a posteriori alignment is not sufficient. Indeed, for the same reasons that a society would not trust a human policymaker with hidden motives and unknown track record, it would also distrust an autonomous policymaker whose objective is not, a priori, perfectly clear and verifiably aligned, as the cost of a single bad action (due to their known brittleness) could easily outweigh the benefits of leveraging such systems. This issue is accentuated by the fact that, unlike humans, holding a deceptive AI agent accountable remains a challenge [25] .Conversely, recent breakthroughs in AI have significantly increased its potential for beneficial use in these critical settings. For example, tax rates and public spending are typically set periodically by a parliament. However, this small group of representatives is inevitably overwhelmed by the vast amount of complex economic data as well as the pleas of millions of individuals. Due to this information bottleneck, governments can only make educated guesses about what is best for the society (assuming they can come to an agreement in the first place). On the other hand, provided that it is verifiably aligned, an autonomous government could efficiently leverage this vast amount of information in order to find the optimal tax rates and public spending (see Figure 1 ).While it is clear that a priori alignment is essential for the safe delegation of such decision power, it comes at the cost of two unavoidable prerequisites. Firstly, it requires a definition of alignment that is both quantitative and measurable. Given our focus on social decision processes, where the perception of each action may differ among individuals, we define and quantify alignment by drawing from long-established theories of utility and social choice. For completeness, we also discuss all the assumptions that allow such a metric to exist. Secondly, one can only ensure that an agent is a priori aligned if one independently understands (at least reasonably well) how its available actions may affect society, regardless of how those effects are perceived. Indeed, asserting the safety of an autonomous agent would be impossible if it could take actions with unknown consequences. Although we make no assumption of the exact nature of this knowledge (domain specific expertise, heuristics, physical/data-driven modeling, or a mix thereof), we assume it is encapsulated in a world model that estimates, given an action and a current state, the probability of moving to any other state.A natural question then arises: Can we leverage this knowledge to construct a verifiably aligned policy? Or, at the very least, can we use it to ensure the safety of a more complex (black-box) policy? We address these questions by introducing probably approximately aligned (PAA) and safe policies, and by studying their existence based on the quality of this knowledge. Akin to the probably approximately correct (PAC) framework in the theory of learnability [38] , we are also interested in the sample complexity of finding PAA policies. In our setting, this complexity is two-faceted: First, the number of calls to the world model (similar to the number of calls to a perfect generative model in [18] ), and second, the amount of feedback (think ballots) required to confidently rank which state is socially preferred. While we are not yet concerned with efficient PAA policies, whose sample complexity is at most polynomial with respect to the desired tolerances, we argue that these complexities should, at least, be independent of the number of possible states (similarly to sparse sampling algorithms [19] ), as most natural state spaces are infinite. We refer to such policies as computable. Conversely, as one can decide which decisions are delegated to autonomous agents, we assume that the action space is finite. Concretely, our contribution is threefold:• First, we define a new type of Social Markov Decision Processes, replacing the traditional reward with aggregated utilities of individuals. Expanding on this definition, we present a formal quantitative definition of alignment in the context of social choice, which naturally leads to the concept of probably approximately aligned (PAA) policies.• Next, given an approximate world model with sufficient statistical accuracy (which we quantitatively derive), we prove the existence of PAA policies by amending a simple sparse sampling algorithm.• Finally, we propose a simple and intuitive method to safeguard any black-box (potentially misaligned) policy in order to ensure that it does not take any destructive decisions, i.e., actions that might lead to a state where even the optimal policy is unsatisfactory. We refer to these adapted policies as safe policies.2 BackgroundLemma 1. For any SMDP M I = (S, A, p, W q , u, γ), the expected future discounted social welfare of a policy π is the state value function of π in the MDP M = (S, A, p, r I , γ), with r I set in Eq. (2).Proof. Let τ t = s 0 , a 0 , s 1 , a 1 , ..., s t denote a truncated trajectory up to time t. From the definitions of V π (s; M) and r I , we haveV π (s; M) = E τ ∼pτ (•|π,s0=s) ∞ t=0 γ t r I (s t , a t ) = E τ ∼pτ (•|π,s0=s) ∞ t=0 γ t E s ′ ∼p(•|st,at) [W q (u(s ′ ))] = ∞ t=0 γ t E τ ∼pτ (•|π,s0=s) E s ′ ∼p(•|st,at) [W q (u(s ′ ))] = ∞ t=0 γ t E τt∼pτ t (•|π,s0=s),at∼π(•|st) E s ′ ∼p(•|st,at) [W q (u(s ′ ))] = ∞ t=0 γ t E τt+1∼pτ t+1 (•|π,s0=s) [W q (u(s t+1 ))] = ∞ t=0 γ t E τ ∼pτ (•|π,s0=s) [W q (u(s t+1 ))] = E τ ∼pτ (•|π,s0=s) ∞ t=0 γ t W q (u(s t+1 ))= W π (s; M I ).Lemma 5. Let W q be the power-mean defined in Eq. (1), with q ∈ R. Given a, b ∈ R * + (or R + for q = 1) such that a < b , let X ∈ [a, b] N be a set of size N and let X n be a subset of size n < N sampled uniformly at random without replacement from X . Then, for 0 < ε < W q (X ) and m = min(n, N -n),EQUATIONwhereΓ(ε, a, b, q) =                (1-2 q ) 2 b 2q-2 (a q -b q ) 2 q < 0 1 (b+ε) 2 (log b-log a) 2 q = 0 q 2 a 2q (b+(1-q)ε) 2 (b q -a q ) 2 0 < q < 1 1 (b-a) 2 q = 1 q 2 a 2q (b+qε) 2 (b q -a q ) 2 q > 1 (9)Similarly, for q ∈ {±∞}:P [|W q (X n ) -W q (X )| ≥ ε] ≤ 1 - n N .Proof. To simplify the notation, we write S = W q (X n ) and µ = W q (X ) such thatS q = 1 n xi∈Xn x q i , µ q = 1 N xi∈X x q i for q ∈ R * log S = 1 n xi∈Xn log x q i log µ = 1 N xi∈X log x q i for q = 0For q ∈ R, we haveEQUATIONTherefore:• For q < 0:EQUATIONwhere we have used the following approximation (holding for 0 < x ≤ 1 and q < 0):(1 + x) q ≤ 1 -(1 -2 q )x < 1 < 1 + (1 -2 q )x ≤ (1 -x) q .Combining Eq. ( 11) and ( 12), and using the Hoeffding-Serfling inequality (Lemma 9) after observing that b q ≤ x q i ≤ a q for all i, we getP [|S -µ| ≥ ε] ≤ P |S q -µ q | ≥ (1 -2 q )b q-1 ε ≤ 2 exp - 2n(1 -2 q ) 2 b 2q-2 ε 2 (1 -n N )(1 + 1 m )(a q -b q ) 2 .• For q = 0:EQUATIONwhere we have used the following approximation (holding for 0 < x < 1):log(1 -x) ≤ - x 1 + x < 0 < x 1 + x ≤ log(1 + x).Combining Eq. ( 11) and ( 13) and using the Hoeffding-Serfling inequality (Lemma 9) after observing that log a ≤ log x q i ≤ log b for all i, we getP [|S -µ| ≥ ε] ≤ P | log S -log µ| ≥ ε b + ε ≤ 2 exp - 2nε 2 (1 -n N )(1 + 1 m )(b + ε) 2 (log b -log a) 2 .• For 0 < q < 1:EQUATIONwhere we have used the following approximation (holding for 0 < x ≤ 1 and 0 < q < 1):(1 -x) q ≤ 1 - qx 1 + (1 -q)x < 1 < 1 + qx 1 + (1 -q)x ≤ (1 + x) q .Combining Eq. ( 11) and ( 14), and using the Hoeffding-Serfling inequality (Lemma 9) after observing that a q ≤ x q i ≤ b q for all i, we getP [|S -µ| ≥ ε] ≤ P |S q -µ q | ≥ qa q ε b + (1 -q)ε ≤ 2 exp - 2nq 2 a 2q ε 2 (1 -n N )(1 + 1 m )(b + (1 -q)ε) 2 (b q -a q ) 2 .• For q = 1: We directly apply the Hoeffding-Serfling inequality (Lemma 9) to obtainP [|S -µ| ≥ ε] ≤ 2 exp - 2nε 2 (1 -n N )(1 + 1 m )(b -a).• For q > 1:EQUATION)where we have used the following approximation (holding for 0 < x ≤ 1 and q > 1):(1 -x) q ≤ 1 - qx 1 + qx < 1 < 1 + qx 1 + qx ≤ (1 + x) q .Combining Eq. ( 11) and (15) , and using the Hoeffding-Serfling inequality (Lemma 9) after observing that a q ≤ x q i ≤ b q for all i, we getP [|S -µ| ≥ ε] ≤ P |S q -µ q | ≥ qa q ε b + qε ≤ 2 exp - 2nq 2 a 2q ε 2 (1 -n N )(1 + 1 m )(b + qε) 2 (b q -a q ) 2 .• For q = +∞: Since we make no assumptions on the distributions of x i other than a ≤ x i ≤ b, we can only guarantee that | max xi∈Xn x i -max xi∈X x i | < ε if x max = arg max xi∈X x i is sampled in X n . This happens with probability at least n N (the maximum might not be unique), and thusP [| max xi∈Xn x i -max xi∈X x i | ≥ ε] ≤ 1 -n N .• For q = -∞: Same analysis as for q = +∞. Lemma 6. Let f : S → [f min , f max ] be a bounded function with 0 ≤ f min ≤ f max < ∞, and p, p ∈ P(S) be two distributions such that D KL (p∥p) ≤ d ∈ R and . ThenE s∼p [f (s)] -E s∼ p[f (s)] ≤ 2(f max -f min ) min{ d 2 , 1 -e -d }.Proof.E s∼p [f (s)] -E s∼ p[f (s)] = S f (s)p(s) ds - S f (s)p(s) ds = S (f (s) -f min )p(s) ds - S (f (s) -f min )p(s) ds = S (f (s) -f min )(p(s) -p(s)) ds ≤ S |f (s) -f min ||p(s) -p(s)| ds ≤ (f max -f min ) S |p(s) -p(s)| ds = 2(f max -f min )δ(p, p)where we have used the definition of the total variation distance: δ(p, p) = 1 2 S |p(s) -p(s)| ds. By Pinsker's inequality, we haveδ(p, p) ≤ 1 2 D KL (p∥p).Additionally, by Bretagnolle and Huber's inequality:δ(p, p) ≤ 1 -e -D KL (p∥ p) .The result follows from the assumption D KL (p∥p) ≤ d.Lemma 7. Let Q be a (randomized) approximation of Q * such that |Q * (s, a) -Q(s, a)| ≤ ε with probability at least 1 -δ for any state-action pair (s, a), with ε > 0 and 0 ≤ δ < 1. Let π Q be the greedy policy defined by π Q(s) = arg max a∈A Q(s, a). Then, for all states s:1) V * (s) -V π Q (s) ≤ 2ε 1 -γ + γ k (V max -V min ) with probability at least 1 -2kδ, ∀k ∈ N * , 2) V * (s) -V π Q (s) ≤ 2ε + 2δ(V max -V min ) 1 -γ almost surely. Proof. First, note that if |Q * (s, a) -Q(s, a)| ≤ ε with probability at least 1 -δ for all state-action pairs (s, a), then Q * (s, π * (s)) -Q * (s, π Q(s)) ≤ 2ε with probability at least 1 -2δ since Q * (s, π * (s)) ≤ Q(s, π * (s)) + ε ≤ Q(s, π Q(s)) + ε ≤ [Q * (s, π Q(s)) + ε] + ε.The factor 2 in the probability comes from the fact that we need the Q estimates to be accurate for both actions π * (s) and π Q(s). For the first inequality, note that, with probability at least 1 -2kδ, the first k estimates of Q are 2ε-accurate for actions π * (s t ) and π Q(s t ), t = 0, ..., k -1. If this happens, then we haveV * (s) -V π Q (s) = Q * (s, π * (s)) -Q π Q (s, π Q(s)) ≤ 2ε + Q * (s, π Q(s)) -Q π Q (s, π Q(s)) = 2ε + γE s ′ ∼p(•|s,π Q (s)) [V * (s ′ ) -V π Q (s ′ )] ≤ 2ε k-1 t=0 γ t + γ k (V max -V min ) ≤ 2ε 1 -γ + γ k (V max -V min ),which concludes the first part of the proof. Concerning the second inequality, since V min ≤ Q * (s, a) ≤ V max , we haveE Q Q * (s, π Q(s)) ≥ (1-2δ)[Q * (s, π * (s))-2ε]+2δV min ≥ Q * (s, π * (s)-(2ε+2δ(V max -V min )).Let π j be a policy that replicates π Q for the first j actions and that is optimal from action j + 1 onward. We now show by induction that V πj (s) ≥ V * (s) -λ j for all s, where λ = λ 1 = 2ε + 2δ(V max -V min ) and λ j = λ + γλ j-1 for j > 1. This clearly holds for j = 1:V π1 (s) = E Q r(s, π Q(s)) + γE s ′ ∼p(•|s,π Q (s)) [V * (s ′ )] = E Q Q * (s, π Q(s)) ≥ Q * (s, π * (s)) -λ = V * (s) -λ 1 .For j > 1, assuming that the statement holds for j -1, we haveV πj (s) = E Q r(s, π Q(s)) + γE s ′ ∼p(•|s,π Q (s)) [V πj-1 (s ′ )] ≥ E Q r(s, π Q(s)) + γE s ′ ∼p(•|s,π Q (s)) [V * (s ′ ) -λ j-1 ] = E Q r(s, π Q(s)) + γE s ′ ∼p(•|s,π Q (s)) [V * (s ′ )] -γλ j-1 = E Q Q * (s, π Q(s) -γλ j-1 ≥ Q * (s, π * (s)) -λ -γλ j-1 = V * (s) -λ j .We now show that lim j→∞ V πj (s) = V π Q (s) for all s. Noting that V πj (s) ≥ V π Q (s) (due to the optimality of π j after j steps), we have0 ≤ V πj (s) -V π Q (s) = E τ ∼pτ (•|πj ,s0=s) ∞ i=0 γ i r(s i , a i ) -E τ ∼pτ (•|π Q ,s0=s) ∞ i=0 γ i r(s i , a i ) = E τ ∼pτ (•|πj ,s0=s)   ∞ i=j γ i r(s i , a i )   -E τ ∼pτ (•|π Q ,s0=s)   ∞ i=j γ i r(s i , a i )   ≤ ∞ i=j γ i (R max -R min ) = γ j R max -R min 1 -γ → j→∞ 0.Therefore, by the squeeze theorem, we have lim j→∞ V πj (s) -V π Q (s) = 0. Finally, noting thatlim j→∞ λ j = ∞ j=0 γ j λ = λ 1 -γ ,we have for all s:V π Q (s) = lim j→∞ V πj (s) ≥ V * (s) -lim j→∞ λ j = V * (s) - 2ε + 2δ(V max -V min ) 1 -γ .Lemma 9 (Hoeffding-Serfling Inequalities [4, 33] ). Let X = {x i } N i=1 be a finite set of N > 1 real points and X n = {X j } n j=1 a subset of size n < N sampled uniformly at random without replacement from X . Additionally, denote µ = 1 N N i=1 x i , a = min i x i and b = max i x i . Then, for m = min(n, N -n) and any ε > 0:P   1 n n j=1 X j -µ ≥ ε   ≤ 2 exp - 2ε 2 n (1 -n N )(1 + 1 m )(b -a) 2 .Proof. First, we show the slightly more general result:1) P   1 n n j=1 X j -µ ≥ ε   ≤ exp - 2ε 2 n (1 -n N )(1 + 1 n )(b -a) 2 ,2)P   1 n n j=1 X j -µ ≤ -ε   ≤ exp - 2ε 2 n (1 -n N )(1 + 1 N -n )(b -a) 2 .The proof of 1) is similar to the one proposed in [4] :Let Z n = 1 n n j=1 X j -µ.We have for any λ > 0:P [Z n ≥ ε] = P e λnZn ≥ e λnε ≤ E[e λnZn ] e λnε ≤ exp 1 8 (b -a) 2 λ 2 (n + 1) 1 - n N -λnε ,where we have used Markov's inequality along with Proposition 2.3 from [4] (slightly improving the original result proposed by Serfling [33] ). The result 1) follows by finding λ that minimizes this upper-bound, i.e.,λ = 4nε (n + 1)(1 -n N )(b -a) 2 .For 2), we note that sampling X n is equivalent to sampling X ′ N -n = X \ X n . Therefore: 2 , where we have used 1) in the last step. Lastly, the final result follows from Boole's inequality (union bound) between 1) and 2).P   1 n n j=1 X j -µ ≤ -ε   = P   1 n   n j=1 X j -nµ   ≤ -ε   = P   1 n   N µ - N -n j=1 X ′ j -nµ   ≤ -ε   = P   N -n n   µ - 1 N -n N -n j=1 X ′ j   ≤ -ε   = P   1 N -n N -n j=1 X ′ j -µ ≥ nε N -n   ≤ exp - 2ε 2 n (1 -n N )(1 + 1 N -n )(b -a) 
utility and social choice theory: 
 We are interested in building autonomous agents whose objective is to maximizes social satisfaction by taking actions that alter the state of the society. In this section, we define what is meant by social satisfaction (often called social welfare), and we provide the conditions under which it is quantifiable.It is commonly assumed that the agency of an individual is governed by its internal binary preference relationship ⪯ over the set of outcomes S. When presented with two choices s and s ′ , the individual will introspect its satisfaction (welfare) levels and either strictly prefer one outcome (s ≺ s ′ or s ′ ≺ s) or be indifferent to both (s ∼ s ′ ). We are interested in quantitatively measuring these welfare levels. Debreu's representation theorem [10] states that if this preference relationship is complete, continuous, and transitive on the topological space S, then there exists infinitely many continuous, real-valued functions u : S → R (called utility functions) such that u(s) ≤ u(s ′ ) ⇔ s ⪯ s ′ , ∀s, s ′ ∈ S (note that any strictly monotonically increasing function can transform a valid utility function into another). While these findings establish the existence of these utility functions, which are proxies for the intrinsic welfare levels of individuals, they do not provide insights into their measurability and interpersonal comparability. It is these two properties, however, that eventually determine what measure of social welfare can be derived. In a nutshell, measurability and comparability impose how much information can be extracted from the values |u i (s) -u i (s ′ )| and u i (s) -u j (s), respectively, for any i ̸ = j and s ̸ = s ′ . We detail the various measurability and comparability levels in Appendix A.1.1, and we refer to these levels as the informational basis of utilities. Apart from that, we fix 0 < U min ≤ u i (s) ≤ U max < ∞ for any s and i (we will allow U min = 0 in specific cases). That is, we assume that individuals cannot be infinitely satisfied or dissatisfied, and that they must scale their utilities when reporting (which does not imply measurability or comparability!). Lastly, we define ∆U ≜ U max -U min and U ≜ {u : S → [U min , U max ]}.Let I be a society composed of N members, each with its preference relationship ⪯ i and a corresponding utility function u i ∈ U over state space S, i ∈ I. Let R S be the set of complete orderings on S and u ∈ U N be a vector gathering the utility functions of all individuals. A social welfare functional f (SWFL) is a mappingD f → R S with D f ⊆ U N .In other words, it is an aggregator of individuals' utilities, indirectly preferences. A long line of work [9, 32, 29] has attempted to define which conditions this SWFL should satisfy (sometimes called axioms of cardinal welfarism, see Appendix A.1.2 for an extensive list of these properties and their respective implications). For the remainder of this work, we will follow the common assumption that any reasonable SWFL should satisfy the following: universality (U), informational basis invariance (XI), independence of irrelevant alternatives (IIA), weak Pareto criterion (WP) and anonymity (A).An important result [29] states that, for any informational basis (X) listed in Appendix A.1.1 and any SWFL f satisfying (XI), (U), (IIA) and (WP), there exists a social welfare function (SWF)W : R N → R such that, if W (u(s)) > W (u(s ′)), then s ranks strictly higher than s ′ in f (u). This is important as it states that the best social state must maximize a certain function W , which can therefore be used as a measure of social satisfaction. In other words, the non-welfare characteristics (i.e., any information influencing f (u) beside u, such as the judgement of an AI agent) are of secondary importance, as they can only break ties between s and s ′ such that W (u(s)) = W (u(s ′ )) and cannot be detrimental to the society. Although we do not require it in this work, maximization of W can be made sufficient if one imposes Welfarism (W), e.g., by replacing (WP) with Weak Pareto Indifference (WPI) or more drastically by imposing Continuity (C) (see Appendix A.1.2 for more details). We are left with the following question: Given a SWFL satisfying (XI), (U), (IIA), (WP) and (A), what is the form of the corresponding SWF? It turns out that the choice is relatively limited and depends mostly on the informational basis invariance (XI). It has been shown, with additional small technical assumptions [7] , that the power mean defined in Eq. ( 1) covers all possible SFWL. See Appendix A.1.3 for a detailed mapping between informational bases, SWFLs and parameter q.W q (u(s);I) =                  min i∈I u i (s) q = -∞ q 1 |I| i∈I u i (s) q q ∈ R * |I| i∈I u i (s) q = 0 max i∈I u i (s) q = ∞ (1)At deployment, a safe autonomous agent must provide assurances that its future actions will continue to serve the best interests of society. This becomes ill-defined if these interests evolve with time. To address this, we assume that both I and u are constant, i.e., u i (s; t) = u i (s; t ′ ) ≡ u i (s) for all s, i and discrete times t ̸ = t ′ . In addition, we also assume that the meaning of these utilities does not change with time, that is, if u i (s; t) ≥ u i (s ′ ; t ′ ) for states s, s ′ and times t ̸ = t ′ , then i's welfare is at least as high in state s at time t than in state s ′ at time t ′ (or vice versa for ≤). Finally, we assume that the SWFL f is such that its corresponding SWF remains the same. In other words, only the method to break ties between states can evolve through time. This makes it possible to predict, at time t, what will be the satisfaction levels at time t ′ > t in any given state. However, to model the fact that humans prefer immediate reward, we discount the utility of the state at time t ′ with a factor γ (t ′ -t) when comparing it with the utility of the state at time t, where γ ∈ [0, 1[ is a discount factor. From these assumptions, it becomes possible, at time t = 0, to quantify the cumulative social welfare of any future state trajectory s 1 s 2 s 3 s 4 ... by computing the quantity ∞ t=0 γ t W q (u(s t+1 )), which we will refer to as the future discounted social welfare of that trajectory (see Section 2.2.2). Using this quantity, we formally define alignment as follows:An autonomous agent is aligned if and only if it always takes actions that maximize the expected future discounted social welfare.The expectation in the above definition accounts for the inherent randomness of most natural systems.In this section, we model the social dynamics as a particular type of Markov Decision Process (MDP), where the probability of transitioning to any state depends solely on the current state and next action.Let M = (S, A, p, r, γ) be an infinite horizon, γ-discounted, discrete time MDP where S is the state space (discrete or continuous), A is the action space (discrete or continuous), p : S × A → P(S) is the transition dynamics of the environment (with P(S) the set of probability distributions over S), r : S × A → [R min , R max ] is the reward of the environment, and γ ∈ [0, 1[ is a discount factor (favoring immediate over distant rewards). Given s ∈ S and a ∈ A, p(s ′ |s, a) is the probability of transitioning to state s ′ after taking action a in state s, and r(s, a) is the expected immediate reward after taking that action. In MDPs, actions are chosen according to a policy π : S → P(A), with π(a|s) the probability of taking action a in state s. Given an initial state s 0 , the tuple (M, π, s 0 ) fully defines a distribution p τ over trajectories τ = s 0 a 0 s 1 a 1 s 2 a 2 ..., where a t ∼ π(•|s t ) and s t+1 ∼ p(•|s t , a t ).If the environment dynamics or the policy are deterministic, we will use the slight abuse of notation s t+1 = p(s t , a t ) and a t = π(s t ), respectively. The efficacy of a given policy π is measured by the state and state-action value functions, defined respectively as follows:V π (s) = E τ ∼pτ (•|π,s0=s) ∞ t=0 γ t r(s t , a t ) , Q π (s, a) = r(s, a) + γE s ′ ∼p(•|a,s) [V π (s ′ )].For a given state s and action a, the optimal state and action-state value functions are defined by V * (s) = sup π V π (s) and Q * (s, a) = sup π Q π (s, a). Given ε ≥ 0, a policy is called ε-optimal (or optimal) if it satisfies V π (s) ≥ V * (s) -ε (respectively V π (s) = V * (s)) for all s. Given small technical assumptions, it can be shown that there always exists an optimal policy [37, 12] .Definition (Social Markov Decision Process). Let I be a society with utility profile u ∈ U N and social welfare function W q . In addition, let S and A be the corresponding state and action spaces, p the social environment dynamics and γ a discount factor. The MDP (S, A, p, r I , γ) with reward r I defined byEQUATIONis a Social Markov Decision Process (SMDP), denoted M I = (S, A, p, W q , u, γ).In this setting, S contains all the possible states of the N individuals, as well as all those of the environment in which they evolve, and A contains all the actions that are delegated to an autonomous agent. Expanding on this definition, we can formally define the alignment metric proposed above: Definition (Expected Future Discounted Social Welfare). Let M I = (S, A, p, W q , u, γ) be a SMDP. The expected future discounted social welfare of a policy π in state s is defined asW π (s) = E τ ∼pτ (•|π,s0=s) ∞ t=0 γ t W q (u(s t+1 ); I) ,and takes value between W min ≜ Umin 1-γ and W max ≜ Umax 1-γ , with ∆W ≜ W max -W min .As shown with the next lemma, the expected future discounted social welfare of a SMDP is equivalent to the state value function of the corresponding MDP. This equivalence makes it a natural metric for alignment, as it enables the use of a wide array of known results on MDPs. Lemma 1. For any SMDP M I = (S, A, p, W q , u, γ), the expected future discounted social welfare of a policy π is the state value function of π in the MDP M = (S, A, p, r I , γ), with r I set in Eq. (2).The proof follows directly from the tower property of conditional expectations (see Appendix A.2.1).If p is unknown, the true reward of the SMDP in Eq. (2) can only be estimated a posteriori, i.e., after taking action a in state s multiple times and observing W q (u(s ′ )). This would require a long exploration phase if S is large, which can be costly and even impossible in critical decisions processes. Instead, one must usually plan using an approximate dynamics model p ∈ P(S) to anticipate the effect of an action. Moreover, even if p is known, computing W q (u(s ′ )) exactly for a given s ′ ∼ p would require full knowledge of u(s ′ ), which is only possible by obtaining feedback from the entire society about s ′ without making additional assumptions on u. For these reasons, we consider a more realistic scenario: Given a set of assessors I n ⊆ I of size n ≤ N and an approximate dynamics model p, the true reward can be approximated by asking the assessors about their utilities on the anticipated future societal states:EQUATIONwhere ÊK s ′ ∼ p is a "Monte Carlo" estimation of E s ′ ∼ p, with K ∈ N samples independently drawn from p(•|s, a), denoted s 1 , s 2 ..., s K . The core of our analysis is to understand how K, n and the inaccuracies of p affect the validity of alignment guarantees.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: The main theoretical and practical limitations of the results are presented in Section 5. The assumptions are extensively discussed in Section 2, and the complexity of the proposed method is discussed in Sections 3 and 5.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
existence of aligned policies: 
 Having formally derived a quantitative measure of alignment W π in the context of social decision processes, we are now prepared to introduce and prove the existence of verifiably aligned policies: Definition (Probably Approximately Aligned Policy). Given 0 ≤ δ < 1, ε > 0 and a SMDP M I = (S, A, p, W q , u, γ), a policy π is δ-ε-PAA (Probably Approximately Aligned) if, for any given s ∈ S, the following inequality holds with probability at least 1 -δ:EQUATIONDefinition (Approximately Aligned Policy). Given ε > 0, a policy π is ε-AA (Approximately Aligned) if and only if it is 0-ε-PAA.We state below one of our main contribution, i.e., the existence of computable PAA and AA policies, which follows directly from Theorem 3 (δ > 0) and Corollary 4 (δ = 0) in the next section. Theorem 2 (Existence of PAA and AA policies). Given a SMDP M I = (S, A, p, W q , u, γ) with q ∈ R and any tolerances ε > 0 and 0 ≤ δ < 1, if there exists an approximate world model p such that sup (s,a)∈S×AEQUATIONthen there exists a computable δ-ε-PAA policy. Consequently, there also exists a computable ε-AA policy.We prove Theorem 2 by providing a planning policy π P AA and by proving it satisfies Eq. ( 4) under the given assumptions. To this end, we present a modified version of the sparse sampling algorithm [19] (which originally assumes that p and r are known, which is not the case here). Given some parameters K, C and n, we define the recursive functions:Qh (s, a; K, C, I n ) = 0 h = 0 rIn (s, a; K) + γ ÊC s ′ ∼ p(•|s,a) V h-1 (s ′ ; K, C, I n ) h ∈ N * (6) V h (s; K, C, I n ) = max a∈A Qh (s, a; K, C, I n ).Intuitively, Qh and V h are recursive approximations of Q * and V * , K and C controls the accuracy of the empirical expectation operators in Q, h controls how far one looks into the future, and n controls the accuracy of the social welfare function estimates. The proposed PAA policy is simply the greedy policy acting on the state-action value estimates, i.e.,EQUATIONIt is deterministic in the sense that, for a given QH , it outputs a single action. However, QH is non-deterministic since I n and s ′ are sampled randomly. The next results clarifies under which conditions π P AA is indeed δ-ε-PAA (Theorem 3) or ε-AA (Corollary 4).Theorem 3 (π P AA is δ-ε-PAA). Let M I = (S, A, p, W q , u, γ) be a SMDP with q ∈ R and pan approximate dynamics model such that d ≜ sup (s,a) D KL (p(•|s, a)∥p(•|s, a)) < ε 2 (1-γ) 6 8∆U 2for any desired tolerances ε > 0 and 0 < δ < 1. For any k ≥ log γ(1-γ)ε ∆U - √ 8d (1-γ) 2 , define β ≜ (1-γ) 2 ε 8 - √ d∆U √ 8(1-γ) -(1-γ)γ k ∆U 8and let π P AA be the policy defined in Eq. ( 7) with parameters• H ≥ max 1, log γ β ∆U , • K ≥ ∆U 2 β 2 (H -1) ln H-1 √ 24k(H -1)|A| ∆U 2 β 2 + ln 1 δ , • C ≥ γ 2 (1-γ) 2 K, • n ≥ N 1 + ∆U 2 N 2K Γ (β, U min , U max , q) -1, and where Γ (β, U min , U max , q) is a function defined in Eq. (9). Then π P AA is a δ-ε-PAA policy.Corollary 4. Let M I = (S, A, p, W q , u, γ) be a SMDP with q ∈ R and p an approximate dynamicsEQUATION5(1-γ) and let π P AA be the policy defined in Eq. (7) with parameters H, C and n as in Theorem 3 andK ≥ ∆U 2 β 2 (H -1) ln H-1 √ 12(H -1)|A| ∆U 2 β 2 + ln ∆U β . Then π P AA is an ε-AA policy.See Appendix A.2.2 for the full derivation of these two results. We now outline a proof sketch. The skeleton of the proof is similar to the one proposed by Kearns et al. [19] for their original sparse sampling algorithm, although several additional tricks and intermediate results are necessary to accommodate the approximate world model p and reward rI . First, we derive a concentration inequality for the power mean function in order to quantify the approximation error between W q (•; I n ) and W q (•; I). Using a slightly modified (two-sided) version of the Hoeffding-Serfling inequality [4, 33] (see Lemma 9 in Appendix A.2.1), we find the following bounds: Lemma 5. Let W q be the power-mean defined in Eq. (1), with q ∈ R. Given a, b ∈ R * + (or R + for q = 1) such that a < b , let X ∈ [a, b] N be a set of size N and let X n be a subset of size n < N sampled uniformly at random without replacement from X . Then, for 0 < ε < W q (X ) and m = min(n, N -n),EQUATIONwhereΓ(ε, a, b, q) =                (1-2 q ) 2 b 2q-2 (a q -b q ) 2 q < 0 1 (b+ε) 2 (log b-log a) 2 q = 0 q 2 a 2q (b+(1-q)ε) 2 (b q -a q ) 2 0 < q < 1 1 (b-a) 2 q = 1 q 2 a 2q (b+qε) 2 (b q -a q ) 2 q > 1 (9)Similarly, for q ∈ {±∞}:P [|W q (X n ) -W q (X )| ≥ ε] ≤ 1 - n N .See Appendix A.2.1 for the full proof. Note that, for q = 1 (utilitarian rule), it is sufficient to have n = N 1 + N-1 in Theorem 3. However, for q ̸ = 1, Γ depends highly on a and b (respectively U min and U max in our setting). Worse, for q = ±∞, the bound depends linearly on n. Indeed, q = -∞ corresponds to the egalitarian rule, which defines social welfare as the lowest welfare among individuals. As this individual might be unique, the probability of not selecting it in I n can be as high as 1 -n N . The same argument can be made for q = +∞, which is why we purposefully avoid these scenarios in Theorems 2, 3 and 8. Regarding the error induced by the approximate model p, we bound it using the following lemma: Lemma 6. Let f : S → [f min , f max ] be a bounded function with 0 ≤ f min ≤ f max < ∞, and p, p ∈ P(S) be two distributions such that D KL (p∥p) ≤ d ∈ R and . ThenE s∼p [f (s)] -E s∼ p[f (s)] ≤ 2(f max -f min ) min{ d 2 , 1 -e -d }.See Appendix A.2.1 for the full proof. Combining Lemmas 5 and 6 along with other classical concentration inequalities, we can bound the error |Q * (s, a) -Qh (s, a)| with high probability. The last step of the proof is to quantify how this error affects the state value function V π P AA (consequently W π P AA from Lemma 1), which can be done using the following results:Lemma 7. Let Q be a (randomized) approximation of Q * such that |Q * (s, a) -Q(s, a)| ≤ ε withprobability at least 1 -δ for any state-action pair (s, a), with ε > 0 and 0 ≤ δ < 1. Let π Q be the greedy policy defined by π Q(s) = arg max a∈A Q(s, a). Then, for all states s:1) V * (s) -V π Q (s) ≤ 2ε 1 -γ + γ k (V max -V min ) with probability at least 1 -2kδ, ∀k ∈ N * , 2) V * (s) -V π Q (s) ≤ 2ε + 2δ(V max -V min ) 1 -γ almost surely.These are fairly general results as they do not depend on how Q is derived. Statements closely related to 2) have already been shown [19, 35] . We provide a proof in Appendix A.2.1 for completeness.Although Theorem 2 may initially inspire optimism regarding the title of the paper, the policy π P AA proposed in Eq. ( 7) is expensive for small ε, both in terms of sample complexity and in terms of required accuracy of the world model. A more efficient PAA policy derived in future work might partially solve the sample complexity issue, but the challenge of building predictive models of high accuracy remains untouched. In most realistic settings, D KL (p∥p) is imposed by the state-of-the-art knowledge upon which p is built, which implicitly restricts the achievable tolerance ε. Therefore, it seems unlikely that such policies could be used as a primary tool for social decisions, as their sole objective would be to maximize a dubious approximation of social welfare. On the other hand, even for large ε, we will show that we can use our PAA policy to adapt any black-box policy π (e.g., a policy built on top of a LLM) into a safe policy, which we formally define as follows:Definition (Safe Policy). Given ω ∈ [W min , W max ] and 0 < δ < 1, a policy π is δ-ω-safe if, for any current state s, the inequality E s ′ ∼p(•|s,a) sup π ′ W π ′ (s ′ )≥ ω holds with probability at least 1 -δ for any action a such that π(a|s) > 0.Intuitively, a safe policy ensures (with high probability and in expectation over the environment dynamics) that the society is not led in a destructive state, that is, a state which might generate high immediate satisfaction but where no policy can generate an expected future discounted social welfare of at least ω. This is considerably weaker than the PAA requirements, as we are no longer concerned about social welfare optimality. The ability to adapt any black-box policy into a safe policy would allow to leverage their strengths while fully removing their brittleness (by bounding the probability of a destructive decision by any desired value δ > 0). To this end, we use another type of policy:Definition (Restricted Version of a Black-Box Policy). Let π : S → A be any policy and Ā(s) ⊆ A be restricted subsets of actions for all states s, with Π(s) ≜ a∈ Ā(s) π(a|s). The restricted version π of π is defined asEQUATIONThis is similar to action masking presented in [20] . It might happen that π(a|s) = 0 for all actions a, in which case it stops operating. However, if this happens, we have the guarantee that, with high probability, the society is currently not in a destructive state. The challenge lies in finding what are the subset of safe actions for every s. Our proposed method to safeguard any policy is the following:Theorem 8 (Safeguarding a Black-Box Policy). Given a SMDP M I = (S, A, p, W q , u, γ) with q ∈ R, a predictive model p and desired tolerances ω ∈ [W min , W max ] and 0 < δ < 1, define Qω (s, a) ≜ QH (s, a; K, C, I n ) with QH given in Eq. ( 6) and any H, K, C, n ≥ 1.For any policy π, let π saf e be the restricted version of π obtained with the restricted subsetsA saf e (s) ≜ {a ∈ A : Qω (s, a) ≥ γω + U max + α}, where α ≜ 2∆U d ′ (1 -γ) 2 + ln 12(C|A|) H-1 δ 1 -γ N -n nN Γ max + ∆U 2 2K + γ ∆U 2 2C(1 -γ) 2 + γ H ∆U 1 -γ ,and with the shortened notationΓ max ≜ Γ(U max , U min , U max , q), d ′ ≜ min{ d 2 , 1 -e -d } and d ≜ sup (s,a) D KL (p(•|s, a)∥p(•|s, a)). Then π saf e is δ-ω-safe.See Appendix A.2.3 for the full proof. While we are, in theory, not restricted by the statistical accuracy of the world model to find a safe version of any black-box policy, low statistical accuracy will, in practice, drastically reduce the number of verifiably safe actions, which at some point will render the safe policy obsolete (as it will refuse to take any action).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
related work: 
 MDP for social choice MDPs have already been used in the context of social decision processes. For instance, Parkes and Procaccia [28] (and more recently [21] ) use social choice MDPs in order to tackle decision-making under dynamic preferences. However, their setting is significantly different from ours: In their work, the state space S is the set of preference profiles U N , and p dictate how these preferences evolve based on the outcome selected by the social choice functional (the policy). Another relevant line of study is that of preference-based reinforcement learning (PbRL) [40] , where the traditional numerical reward of the underlying MDP is replaced with relative preferences between state-action trajectories. While social decision processes can also be cast as a PbRL problem, no previous work has attempted to formally and quantitatively define social alignment in that setting.AI safety A long line of work has attempted to address the challenge of building verifiably safe autonomous systems [2, 30] . In the context of MDPs, safe reinforcement learning (RL) tackles this challenge by introducing safety constraints [1] . See [15, 20] for comprehensive surveys on the topic. However, RL relies on exploration, which is not allowed in our setting. On the other hand, existing planning methods (where exploration is not needed if a world model p is available) do not relate the accuracy of p to the validity of the desired safety guarantees, as they mostly assume that p is known.Alignment The goal of alignment can be entirely different based on the context [13] . Recent research on this topic has primarily focused on aligning large language models (LLMs) [17] using human feedback [6, 26] and derivatives [11, 39, 5] . While some work has attempted to tackle LLM alignment from a social choice perspective [22] , the issue of aligning the meaning of generated text is, by nature, both qualitative and subjective, and therefore separate from ours. A setting closer to our work is the value alignment problem [34, 23] , based on the theory of basic human values [31] , where the preferences of individuals (over social states) are assumed to be guided by a predefined set of common values, and where the goal is to find "norms" (i.e., hard-coded logical constraints on actions) that guide society towards states that maximize these values. The alignment of these norm can be quantified by measuring the level of these values in the subsequent states, and the alignment of an autonomous system is simply given by the alignment of the norms it follows. However, this measure is intractable in most realistic settings, as it must be computed over all possible state trajectories [34] . 
limitations and future work: 
 From a practical standpoint, the main challenge lies in building a reliable world model p, since PAA guarantees depend on its statistical accuracy, which can only be measured exactly if the true world model p is known. In practice, a conservative estimate of this accuracy could be used instead. Another limitation arises from the dependence on the informational basis of utilities, a philosophical question that falls outside the scope of this paper but that is common to all systems involving human feedback. A third practical limitation is the assumptions that individuals can observe and evaluate the entire social states when reporting their utilities. Future work could extend our analysis to the setting of partially observable MDP (POMDP) [42] , for instance. Finally, the assumption that individuals have static preferences can also be challenged, but it is not clear how evolving preferences can be modeled, let alone factored in our analysis. From a theoretical perspective, the complexity results presented in the various theorems are poor for q ̸ = 1 and γ ≈ 1. These dependencies are hard to improve, as they relate to a known property of the power mean [7] and the ability to foresee the future, respectively. Lastly, while we make no assumption about the distribution of utilities u, one could investigate how such assumptions might improve these complexities (e.g., using Bernstein-Serfling inequality [4] ). 
conclusion: 
 We present a formal and quantitative definition of alignment in the context of social choice, leading to the concept of probably approximately aligned policies. Using an approximate world model, we derive sufficient conditions for such policies to exist (and be computable). In addition, we introduce the relaxed concept of safe policies, and we present a method to make any policy safe by restricting its action space. Overall, this work provides a first attempt at rigorously defining the alignment of governing autonomous agents, and at quantifying the resources (n, K, C, H) and knowledge (p) needed to enforce the desired level of alignment (ε) or safety (ω) with high confidence (δ).Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [NA]Justification: [NA] Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).• The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. The very subject of our paper is to make AI safer, and to understand when it is not. We do not foresee any misuse of our results. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: The broader impact of the paper is readily evident from the context and the results.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. 12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected? Answer: [NA] Justification: [NA] Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.• For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Measurability of u ∈ U can either be cardinal, where one can numerically measure absolute levels of satisfaction for a given state up to positive affine transformations, or ordinal, where one can only hope to rank states, meaning one can numerically measure utilities only up to increasing monotone transformations [16, 36, 27] . Additional dichotomization becomes possible when comparability is taken into account [29, 9, 32] . In a nutshell, utilities are either ordinal non-comparable (ONC), where individuals transform their intrinsic utilities differently when reporting; cardinal non-comparable (CNC), which is similar to ONC but with cardinal measurability), ordinal level comparable (OLC), where individuals transform their intrinsic utilities similarly when reporting; cardinal unit comparable (CUC), in which the affine transforms of the individuals have identical scaling factor but different bias; cardinal fully comparable (CFC), where individuals have the same affine transform; or cardinal ratio-scale comparable (CRS), in which all transforms are unbiased with the same scaling factor. Note that CRS is stronger than CFC in the sense that one can have statements such has "Bob is x times more satisfied than Alice" under the CRS assumption. In this paper, we refer to this classification as the informational basis of utilities.Here is a list of the most common properties imposed on a given SWFL f : D f → R S , along with their definitions. We denote ⪯ f (u) the binary preference relationship corresponding to f (u), that is, s ⪯ f (u) s ′ if and only if s ′ ranks equally or higher than s in f (u).(U) Universality or unrestricted domain:D f = U N . (IIA) Independence of Irrelevant Alternatives: For every u, u ′ ∈ U N and S ′ ⊆ S, if u(s) = u ′ (s)for all s ∈ S ′ , then f S ′ (u) = f S ′ (u ′ ), where f S ′ (u) is the partial ranking obtained after excluding S \ S ′ from f (u).(WP) Weak Pareto criterion or unanimity: For all pairs s, s ′ ∈ S, if u(s) > u(s ′ ), then s ranks strictly higher than s ′ in f (u).(WPI) Weak Pareto with Indifference criterion: For all pairs s, s ′ ∈ S, if u(s) ≥ u(s ′ ), then s ranks equally or higher than s ′ in f (u).(SP) Strong Pareto criterion: For all pairs s, s ′ ∈ S, if there exists i ∈ I such that u i (s) > u i (s ′ ) and u j (s) ≥ u j (s ′ ), ∀j ∈ I \ {i}, then s ranks strictly higher than s ′ in f (u).(NI) Non-Imposition: For all R ∈ R, there exists u ∈ D f such that f (u) = R.(C) Continuity: For any v ∈ R N and s, s ′ ∈ S, the sets{v ′ ∈ R N : u(s ′ ) = v ′ , u(s) = v and s ⪯ f (u) s ′ for some u ∈ U N },and {v ′ ∈ R N : u(s ′ ) = v ′ , u(s) = v and s ′ ⪯ f (u) s for some u ∈ U N } are closed.(WC) Weak Continuity: For any u ∈ U N and ε ∈ R N + , there exists u ′ ∈ U N such that f (u) = f (u ′ ) and 0 < u(s) -u ′ (s) < ε for all s ∈ S (component-wise inequalities).(N) Neutrality or welfarism: For all quadruples s, s ′ , t, t ′ ∈ S, if u, u ′ ∈ U N are such that u(s) = u ′ (s ′ ) and u(t) = u ′ (t ′ ), then f (u) and f (u ′ ) agree on the partial rankings of (s, t) and (s ′ , t ′ ) (i.e., either s and s ′ are preferred, or either t and t ′ ).(A) Anonymity or symmetry: For all u ∈ U N , f (u) = f (u ′ ) with u ′ any permutation of u.(ND) Non-Dictatorship: There is no single individual i such that ⪯ i =⪯ f (u) for any u.(IC) Incentive compatibility: It is in the best interest of each individual to report their true preferences (i.e., there is no tactical voting).(S) Separability or independence of unconcerned agents: For all u, u ′ ∈ U, if there existsI ′ ⊆ I such that u i = α ∈ R and u ′ i = α ′ ∈ R for i ∈ I ′ , and u i = u ′ i for i ∈ I \ I ′ , then f (u) = f (u ′ ). I ′ is the set of unconcerned agents.(PDT) Pigou-Dalton Transfer principle: Define ū(s) = i∈I u i (s). For all u ∈ U N and s, t ∈ S such that ū(s) = ū(t), if |u i (s) -ū(s)| ≤ |u i (t) -ū(t)| for all i ∈ I, then s ranks equally or higher than t in f (u). (XI) Informational basis Invariance (XI): The SWFL is invariant under the given measurability and comparability assumptions: (ONCI), (CNCI), (CUCI), (CFCI), (CRSI), (OLCI). That is, f (u) = f (u ′ ) for any two utility profile u, u ′ that are undistinguishable under the given informational basis.We now provide a short, intuitive explanation for the properties (U), (XI), (IIA), (WP) and (A) that we impose in this work. Enforcing unrestricted domains ensures that the SWFL always outputs a ranking.Informational basis invariance ensures that the SWFL outputs the same ranking for two preference profiles that are indistinguishable under the given measurability and comparability assumptions. Independence of irrelevant alternatives ensures that the rankings are robust, in the sense that they are not incoherently affected by removing or adding other options. The weak Pareto criterion ensures that the SWFL represents reasonably well the preference of society (if an outcome is unanimously preferred over another, then it must also be preferred at the social level). Anonymity ensures that all individuals have equal influence on the social ranking. Lastly, we recall a few important results (assuming |S| ≥ 3).• (CRSI) ⇒ (CFCI) ⇒ (CUCI) ⇒ (CNCI) ⇒ (ONCI). Additionally (OLCI) ⇒ (ONCI). • (XI) + (U) + (IIA) + (WP) ⇒ There exists W : R N → R such that W (u(s)) > W (u(s ′ ))implies that s ranks strictly higher than s ′ in f (u). This is important as it states that the best social state s must maximize W . In other words, even if f is not neutral, the non-welfarism characteristics are of a secondary importance and can only break ties between s and t such that W (u(s)) = W (u(t)). Maximization can be made sufficient if one imposes (W) on f (e.g., by replacing (WP) by (WPI) or more drastically by imposing continuity on f ). • Arrow's impossibility theorem [3]: (ONCI) + (U) + (WP) + (I) ⇒ ¬(ND). While this theorem seems to prevent any hope of finding good SWFLs, its statement is strongly dependent on the (often hidden) ONCI assumptions. Indeed, it is challenging to find a good social aggregator that only knows rankings of alternatives. Strengthening the measurability and comparability assumptions (and thus narrowing the informational basis invariance property) allows to find SWFLs that are non-dictatorial. • (A) ⇒ (ND).• Gibbard-Satterthwaite theorem (single winner elections): (ONCI) + (IC) ⇒ ¬(ND).• (SP) ⇒ (WP) but the converse is not true.Table 1 : The different social welfare functions (SWF) corresponding to a SWFL that satisfies (U), (IIA), (WP), (A) and (XI) for the different informational bases [29] . i∈I u i (s) q = 1 (OLCI) min i∈I u i (s) or max i∈I u i (s) q ∈ {±∞} (CFCI) min i∈I u i (s), max i∈I u i (s) or i∈I u i (s) q ∈ {±∞, 1} (CRSI) min i∈I u i (s), max i∈I u i (s), i∈I u i (s) q or i∈I log[u i (s)] q ∈ R ∪ {±∞} A.2 Proofs A.2.Theorem 3 (π P AA is δ-ε-PAA). Let M I = (S, A, p, W q , u, γ) be a SMDP with q ∈ R and pan approximate dynamics model such that d ≜ sup (s,a) D KL (p(•|s, a)∥p(•|s, a)) < ε 2 (1-γ) 6 8∆U 2for any desired tolerances ε > 0 and 0 < δ < 1. For any k ≥ log γ(1-γ)ε ∆U - √ 8d (1-γ) 2 , define β ≜ (1-γ) 2 ε 8 - √ d∆U √ 8(1-γ) -(1-γ)γ k ∆U 8and let π P AA be the policy defined in Eq. ( 7) with parameters• H ≥ max 1, log γ β ∆U , • K ≥ ∆U 2 β 2 (H -1) ln H-1 √ 24k(H -1)|A| ∆U 2 β 2 + ln 1 δ , • C ≥ γ 2 (1-γ) 2 K, • n ≥ N 1 + ∆U 2 N 2K Γ (β, U min , U max , q) -1, and where Γ (β, U min , U max , q) is a function defined in Eq. ( 9). Then π P AA is a δ-ε-PAA policy.Proof. Similarly to [19] , the core idea (and challenge) of the proof is to bound |Q * (s, a) -QH (s, a)| for all state-action pairs so that Lemma 7. However, in contrast with [19] , we must now deal with an approximate dynamics model, as well as an approximate reward, which significantly complicates the task. To do so, we write the following for h > 0 (omitting the dependency of K, C and I n in the notation):Q * (s, a) -Qh (s, a) = r I (s, a) -rIn (s, a) + γ E s ′ ∼p(•|s,a) [V * (s ′ )] -ÊC s ′ ∼ p(•|s,a) [ V h-1 (s ′ )] = E s ′ ∼p(•|s,a) [W q (u(s ′ ); I)] -ÊK s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )] + γ(E s ′ ∼p(•|s,a) [V * (s ′ )] -ÊC s ′ ∼ p(•|s,a) [ V h-1 (s ′ )]) = E s ′ ∼p(•|s,a) [W q (u(s ′ ); I)] -E s ′ ∼p(•|s,a) [W q (u(s ′ ); I n )] + E s ′ ∼p(•|s,a) [W q (u(s ′ ); I n )] -E s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )] + E s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )] -ÊK s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )] + γ(E s ′ ∼p(•|s,a) [V * (s ′ )] -E s ′ ∼ p(•|s,a) [V * (s ′ )]) + γ(E s ′ ∼ p(•|s,a) [V * (s ′ )] -ÊC s ′ ∼ p(•|s,a) [V * (s ′ )]) + γ( ÊC s ′ ∼ p(•|s,a) [V * (s ′ )] -ÊC s ′ ∼ p(•|s,a) [ V h-1 (s ′ )]) such that, for any state-action pair,|Q * (s, a) -Qh (s, a)| ≤ E s ′ ∼p(•|s,a) [|W q (u(s ′ ); I) -W q (u(s ′ ); I n )| Z1 ] + |E s ′ ∼p(•|s,a) [W q (u(s ′ ); I n )] -E s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )]| Z2 + |E s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )] -ÊK s ′ ∼ p(•|s,a) [W q (u(s ′ ); I n )]| Z3 + γ |E s ′ ∼p(•|s,a) [V * (s ′ )] -E s ′ ∼ p(•|s,a) [V * (s ′ )]| Z4 + γ |E s ′ ∼ p(•|s,a) [V * (s ′ )] -ÊC s ′ ∼ p(•|s,a) [V * (s ′ )]| Z5 + γ ÊC s ′ ∼ p(•|s,a) [|V * (s ′ ) -V h-1 (s ′ )|] Z6where we have used the triangle inequality, the linearity of expectation and the fact that |E[X]| ≤ E[|X|] for any random variable X. From Lemma 5, we have that Z 1 ≤ ε 1 with probability at least 1 -δ 1 whereδ 1 ≜ 2 exp - 2nε 2 1 (1 -n N )(1 + 1 m ) Γ(ε 1 , U min , U max , q) ≤ 2 exp - nε 2 1 1 -n N Γ(ε 1 , U min , U max , q) .Recall that U min ≤ W q (u(s)) ≤ U max and V min = Umin 1-γ ≤ V * (s) ≤ Umax 1-γ = V max for any state s and utility profile u. Therefore, from Lemma 6, we have (with probability 1)EQUATIONwhere ∆U ≜ U max -U min and d ≜ sup (s,a) D KL (p(•|s, a)||p(•|s, a)). Furthermore, by the standard Hoeffding's inequality, we have Z 3 ≤ ε 3 with probability at least 1 -δ 3 whereδ 3 ≜ 2 exp - 2Kε 2 3 ∆U 2 ,and Z 5 ≤ ε 5 with probability at least 1 -δ 5 whereδ 5 ≜ 2 exp - 2C(1 -γ) 2 ε 2 5 ∆U 2 .Finally, we haveÊC s ′ ∼ p(•|s,a) [|V * (s ′ ) -V h-1 (s ′ )|] = 1 C C i=1 |V * (s i ) -V h-1 (s i )| = 1 C C i=1 | max a Q * (s i , a) -max a Qh-1 (s i , a)| ≤ 1 C C i=1 |Q * (s i , ãi ) -Qh-1 (s i , ãi )| with ãi ≜ arg max a Q * (s i , a) if max a Q * (s i , a) ≥ max a Qh-1 (s i , a) arg max a Qh-1 (s i , a) if max a Q * (s i , a) < max a Qh-1 (s i , a) ,and where the last inequality is obtained after a careful analysis of the absolute value operator. This suggests that we can proceed by induction on h. Let α 0 ≜ ∆U 1-γ andα h ≜ ε 1 + ε 2 + ε 3 + γ(ε 4 + ε 5 + α h-1) for h > 0, and let ϕ 0 ≜ 0 and ϕ h ≜ δ 1 + δ 3 + δ 5 + C|A|ϕ h-1 for h > 0. We start the induction by noting that, for any state-action pair,|Q * (s, a) -Q0 (s, a)| = |Q * (s, a)| ≤ ∆U 1 -γ = α 0 with probability 1 = 1 -ϕ 0For h > 1, assuming that, for any state-action pair, |Q * (s, a) -Qh-1 (s, a)| ≤ α h-1 with probability at least 1 -ϕ h-1 , we have from aboveEQUATIONwith probability at least 1 -δ 1 -δ 3 -δ 5 -C|A|ϕ h-1 = 1 -ϕ h , as we require that all C estimates of Qh-1 are accurate for each action. Solving for α H , we getEQUATION)Note that ε 2 and ε 4 in Eq. ( 16) are non-controllable and only depend on the accuracy of the environment model p. If we require |V * (s) -V π P AA (s)| ≤ ε, then we must have 2(ε2+γε4)(1-γ) 2< ε from Lemma 7. Using the definitions of ε 2 and ε 4 from Eq. ( 16), this condition becomesmin{ d 2 , 1 -e -d } < (1-γ) 6 ε 2 16∆U 2 with d ≜ sup (s,a) D KL (p(•|s, a)∥p(•|s, a)). Since ε ≤ ∆U (1-γ)(as the bound would be trivial otherwise), the right-hand side of the inequality is less than 1, and thus it is less restrictive (on p) to only bound d 2 (as x 2 ≤ 1 -e -x for x ∈ [0, 1]), which concludes the proof on the required accuracy of the dynamics model. Now that we have ensured that the environment model is accurate enough, we must choose the algorithm's parameters (namely K, C and n) to ensure that the other inaccuracies do not exceed the remaining "approximation budget"ε - 2(ε 2 + γε 4 ) (1 -γ) 2 ≥ ε - √ 8d∆U (1 -γ) 3 > 0.Solving for ϕ H , we getEQUATIONwhere the last inequality follows from the fact that C|A| -1 ≥ 1 2 C|A| as C ≥ 1 and |A| ≥ 2. Finally, using part 1) of Lemma 7, we get that for any state s, with probability at leastEQUATION≤ 2 (1 -γ) 2 ε 1 + ε 2 + ε 3 + γ(ε 4 + ε 5 ) + γ H ∆U + 1 -γ 2 γ k ∆U .That is, using the definitions of ε 2 and ε 4 , and imposing the tolerance ε, we requireε 1 + ε 3 + γε 5 + γ H ∆U + 1 -γ 2 γ k ∆U ≤ (1 -γ) 2 2 ε - √ 8d∆U (1 -γ) 3 . We fix ε 1 = ε 3 = γε 5 = γ H ∆U = (1-γ) 2 8 ε - √ 8d∆U (1-γ) 3 -1 1-γ γ k ∆U ≜ β.From that, we directly obtain the required planning "depth" H = max 1, log γ β ∆U , as well as thelower bound k ≥ log γ (1-γ)ε ∆U - √ 8d (1-γ) 2 . Additionally, we choose C = γ 2 (1-γ) 2 K such that δ 3 = δ 5 = 2 exp -2Kβ 2(∆U ) 2 , and we choose n such that δ 1 ≤ δ 3 , or equivalentlynΓ(β, U min , U max , q) (1 -n N ) ≥ 2K ∆U 2 .This is satisfied forn ≥ N 1 + ∆U 2 Γ(β, U min , U max , q)N 2K -1.With this choice of C and n, we can writeδ 1 + δ 3 + δ 5 ≤ 6 exp - 2Kβ 2 ∆U 2 .The last step is to choose K such that 2kϕ H ≤ δ, that isEQUATIONIf H = 1 (i.e., γ ≤ β ∆U ), we can simply chooseK ≥ ∆U 2 2β 2 ln 24k δ ,and if H > 1 (i.e., γ > β ∆U ), we can chooseK ≥ ∆U 2 β 2 (H -1) ln H-1 √ 24k(H -1)|A| ∆U 2 β 2 + ln 1 δ .Indeed, setting x ≜ H-1 √ 24k(H -1)|A| and y ≜ β ∆U and substituting the expression for K, the left-hand term of inequality ( 21) can be rewritten asEQUATIONwhere we have used the observation that x ≥ 1 and y ≤ 1 along with the fact that 0 ≤ ln(z) z ≤ 1 for all z ≥ 1 in the last step. Finally, assuming there exists an optimal policy in M I (see [12, 37] for the necessary conditions), and knowing from Lemma 1 that V π (s) = W π (s) for any policy, we know that V * (s) -V π P AA (s) ≤ ε implies W π P AA (s) ≥ sup π ′ W π ′ (s) -ε.Corollary 4. Let M I = (S, A, p, W q , u, γ) be a SMDP with q ∈ R and p an approximate dynamicsmodel such that d ≜ sup (s,a) D KL (p(•|s, a)∥p(•|s, a)) < ε 2 (1-γ) 68∆U 2 for any desired tolerance ε > 0.EQUATION5(1-γ) and let π P AA be the policy defined in Eq. (7) with parameters H, C and n as in Theorem 3 andK ≥ ∆U 2 β 2 (H -1) ln H-1 √ 12(H -1)|A| ∆U 2 β 2 + ln ∆U β . Then π P AA is an ε-AA policy.Proof. The first part of the proof is identical to Theorem 3, but we use part 2) of Lemma 7 instead of part 1) in Eq. (20) . With that, we have for any state s:V * (s) -V π P AA (s) ≤ 2(1 -γ)α H + 2ϕ H ∆U (1 -γ) 2 ≤ 2 (1 -γ) 2 ε 1 + ε 2 + ε 3 + γ(ε 4 + ε 5 ) + γ H ∆U + 2∆U (δ 1 + δ 3 + δ 5 )(C|A|) H-1 .That is, using the definitions of ε 2 and ε 4 , and imposing the tolerance ε, we requireε 1 + ε 3 + γε 5 + γ H ∆U + 2∆U (δ 1 + δ 3 + δ 5 )(C|A|) H-1 ≤ (1 -γ) 2 2 ε - √ 8d∆U (1 -γ) 3 . We fix ε 1 = ε 3 = γε 5 = γ H ∆U = β ≜ (1-γ) 2 10 ε - √ 8d∆U(1-γ) 3 . From that, we directly obtain the required planning "depth" H = max 1, log γ β ∆U . Similarly to Theorem 3, we chooseC = γ 2 (1-γ) 2 K and n ≥ N 1 + ∆U 2 Γ(β, U min , U max , q)N 2K -1, such thatδ 1 + δ 3 + δ 5 ≤ 6 exp - 2Kβ 2 ∆U 2 .The last step is to choose K such thatEQUATIONIf H = 1 (i.e., γ ≤ β ∆U ), we can simply chooseK ≥ ∆U 2 2β 2 ln 12∆U β ,and if H > 1 (i.e., γ > β ∆U ), we can chooseK ≥ ∆U 2 β 2 (H -1) ln H-1 √ 12(H -1)|A| ∆U 2 β 2 + ln ∆U β .We show that this choice of K satisfies Eq. ( 23) by setting δ = β ∆U and k = 1 2 in Eq. (22) . We also conclude the proof using Lemma 1.Theorem 8 (Safeguarding a Black-Box Policy). Given a SMDP M I = (S, A, p, W q , u, γ) with q ∈ R, a predictive model p and desired tolerances ω ∈ [W min , W max ] and 0 < δ < 1, define Qω (s, a) ≜ QH (s, a; K, C, I n ) with QH given in Eq. ( 6) and any H, K, C, n ≥ 1. For any policy π, let π saf e be the restricted version of π obtained with the restricted subsets A saf e (s) ≜ {a ∈ A : Qω (s, a) γω + U max + α}, whereα ≜ 2∆U d ′ (1 -γ) 2 + ln 12(C|A|) H-1 δ 1 -γ N -n nN Γ max + ∆U 2 2K + γ ∆U 2 2C(1 -γ) 2 + γ H ∆U 1 -γ ,and with the shortened notation Γ max ≜ Γ(U max , U min , U max , q), d ′ ≜ min{ Proof. Assuming there exists an optimal policy in M I (see [12, 37] for the necessary conditions), and knowing from Lemma 1 that V π (s) = W π (s) for any policy, we can write sup π ′ W π ′ (s) = V * (s). Therefore, the condition for safe actions becomes E s ′ ∼p(•|s,a) [V * (s ′ )] ≥ ω. Using the definition of the optimal state-action value function Q * :Q * (s, a) = r I (s, a) + γE s ′ ∼p(•|s,a) [V * (s ′ )],we can rewrite this condition once again asQ * (s, a) ≥ γω + r I (s, a).We know from Eq. (17) in the proof of Theorem 3 that, for any state-action pair (s, a), |Q * (s, a) -QH (s, a; K, C, I n )| ≤ α H with probability at least 1 -ϕ H , where α H and ϕ H are given in Eq. ( 18) and (19) , respectively. That is, if QH (s, a; K, C, I n ) ≥ γω + r I (s, a) + α H , then the above condition is satisfied with probability at least 1 -ϕ H . From Eq. ( 18), we haveEQUATIONwhere (using d ≜ sup (s,a) D KL (p(•|s, a)∥p(•|s, a))):ε 1 = N -n nN Γ(ε 1 , U min , U max , q) ln 2 δ 1 ≤ N -n nN Γ(U max , U min , U max , q) ln 2 δ 1 , ε 2 = 2∆U min{ d 2 , 1 -e -d }, ε 3 = ∆U 2 2K ln 2 δ 3 , ε 4 = 2∆U 1 -γ min{ d 2 , 1 -e -d }, ε 5 = ∆U 2 2C(1 -γ) 2 ln 2 δ 5 .Finally, in order to obtain a δ-ω-safe policy, we must have ϕ H ≤ δ. From Eq. ( 19), this is satisfied if2(δ 1 + δ 3 + δ 5 )(C|A|) H-1 ≤ δ, or similarly if δ 1 = δ 3 = δ 5 = δ 6(C|A|) H-1 . Defining d ′ = min{ d 2 ,1 -e -d } and Γ max = Γ(U max , U min , U max , q), and substituting ε 1 , ε 2 , ε 3 , ε 4 , ε 5 , δ 1 , δ 3 , δ 5 in Eq. ( 24), we obtainα H ≤ 2∆U d ′ (1 -γ) 2 + ln 12(C|A|) H-1 δ 1 -γ N -n nN Γ max + ∆U 2 2K + γ ∆U 2 2C(1 -γ) 2 + γ H ∆U 1 -γ .Using the fact that r I (s, a) ≤ U max for any state-action pair, we can conservatively define the restricted subsets of safe actions as A saf e (s) = {a : QH (s, a; K, C, I n ) ≥ γω + U max + α} for any state s, where α is the right-hand term of the above inequality. Therefore, restricting any policy π with these subsets ensures that E s ′ ∼p(•|s,a) [V * (s ′ )] ≥ ω with probability at least 1 -δ for any action a that has a non-zero probability of being selected.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The three claims made in the abstract and introduction reflect accurately the framework presented in Section 2 and the results presented in Section 3. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 


Decision: After reviews and a rebuttal/discussion phase that involved all reviewers we have decided that this paper should be accepted to NeurIPS. The reviewers were in agreement that the paper is well written, brings metrics to a novel domain, and is theoretically rigorous.

Reviews: review: paper_summary: paper_summary: The paper investigates the potential for AI agents to safely make critical decisions, such as those in a government setting, by examining the concept of alignment. It introduces Probably Approximately Aligned (PAA) policies, which are policies that are nearly optimal in aligning with social welfare objectives. The authors draw from utility and social choice theories to provide a quantitative definition of alignment and propose methods to ensure AI actions are verifiably safe for society. They also discuss the practical challenges in implementing such policies and suggest future directions for research in this area. The focus is on developing a theoretical framework that could eventually be applied to AI governance and decision-making processes.
strength_weakness: strength_weakness: I think the problem is not well presented.
questions: questions: I think the problem is not well presented. 

E.g. 

Section 3.2 - Algorithm for Computing the Policy:
How can you the result of Equation (7) are not clearly explained. 

Estimation of Reward (Equation 3):
Equation (3) still appears to be a posterior approach.
limitations: limitations: Yes.
paper_summary: paper_summary: The paper aims to define alignment quantitatively and ensure AI agents' actions are predictable and safe. The paper start by outlines the basics of utility and social choice theory, focusing on quantifying social satisfaction and the conditions under which it is measurable. Next, the paper defines probably approximately aligned (PAA) and approximately aligned (AA) policies and provides a modified sparse sampling algorithm to achieve these policies under certain conditions. The paper also presents the idea of "safe policies" and a method to ensure AI actions are verifiably safe for society.
strength_weakness: strength_weakness: The safeguarding method is described in a general context, with limited discussion of its applicability to specific real-world problems. Consider adding examples of real-world applications where the safeguarding method could be particularly beneficial. For instance, discuss its application in autonomous vehicle systems, healthcare decision-making, or financial trading algorithms.
questions: questions: Could you provide more detailed steps on how the safeguarding method can be practically implemented in real-world systems? Consider add roadmap with examples on how to adapt a black-box policy into a safe policy.
limitations: limitations: The authors discuss various limitations of their approach, including computational complexity for large state spaces and strong assumptions about the availability and accuracy of information. The paper also highlights challenges in building reliable world models and the philosophical questions surrounding the informational basis of utilities.
paper_summary: paper_summary: This paper applies ideas from the Probably Approximately Correct framework to agent alignment. The paper defines a new idea of a policy which is Probably Approximately Aligned and explores the existence of such policies under certain assumptions of social welfare and models of the world. The authors show that probably approximately aligned (and approximately aligned) policies exist when there is a sufficiently accurate world model. However, to compute this policy is quite expensive. Thus, the authors also develop the idea of a safe policy which can be derived using a PAA policy and seems to be a policy that will probably not result in a catastrophically bad state.
strength_weakness: strength_weakness: Not a weakness, but my disclaimer: I was not able to thoroughly review every detail of the math due to time constraints so my understanding of the paper is limited.

The primary (and minor) issue I see with the paper is that it is quite abstract and doesn't give a clear idea of how close this is to being useful. While obviously difficult to fit into a conference paper, an experimental section may give some intuition for details such as how accurate a world model really needs to be, how beneficial PAA/safe policies are, etc.

It seems that Sec 3.2 is constructive in a sense and provides a PAA policy. Some further commentary on the practicality of this policy (is it entirely impractical to use it for synthetic experiments, or simply impractical in any useful setting/world model?) would help to contextualize the paper.
questions: questions: You do a good job of stating weaknesses but it seems that the first weakness listed may be quite significant. Is this work essentially just pushing the real difficulty of aligned policies into the task of building a statistically sound world model?
limitations: limitations: Limitations are well stated.
paper_summary: paper_summary: This paper defines social markov decision processes (SMDPs) as an MDP generalization incorporating a population of individuals with distinct utility profiles aggregated by a social welfare function. It provides a novel quantitative definition of alignment in this context, then leverages this definition to characterize probably approximately aligned policies and safe policies, prove the conditions under which they exist, and relate them to the accuracy of the reward model.
strength_weakness: strength_weakness: Even the more practical approach of safeguarding a black-box policy may have severe limitations. I believe the paper would be strengthened by a discussion of the feasibility of this -- in particular, what is computational complexity of computing $\mathcal{A}_{safe}$ for a SMDP?

Typo: On line 277, I believe "expansive" should be "expensive".
questions: questions: How does the SMDP formalism handle individuals that give assessments on different scales? What assumption(s) does it rely on regarding interpersonal comparisons of utility?
limitations: limitations: This paper includes an excellent discussion of the limitations of these results, including the theoretical conditions under which PAA and safe policies will be unreliable. The paper also discusses further practical and philosophical limitations in Section 5.

Comments: title: Reviewer - Author Discussion
comment: We want to clarify that we are not claiming that *modeling* the world is easy in any general setting. If this impression is conveyed in the paper or the rebuttal, please let us know where, and we will address it. Our intention was to answer your initial question by providing context regarding the implications of our work.

One alternative approach to understanding these implications is the comparison with LLM alignment. Pre-training a LLM on a large corpus of text essentially builds a world "language" model, where, given a state (the start of a sentence), the model predicts the probability of the next token with little to no consideration of the alignment of the full sentence. Then, an algorithm (e.g., RLHF or DPO) is used to align the model with the user's interests. While the analogy is somewhat limited, our work would correspond to this second phase.
Thanks for the response. It was a good discussion.
Thank you for the nuanced discussion. This work seems thorough to me, and I will maintain my original rating.
Thank you for the well reasoned response. I'm not fully convinced that accurately modeling the world is as easy as you make it out to be but getting into deeper detail is likely out of scope.
Thanks everyone for their hard work on the papers, reviews, and rebuttals. We now have a comprehensive rebuttal from the authors which responds both overall and to each review.

I'd please ask the reviewers to please post a comment acknowledging that they have read the response and ask any followup questions (if any).

This period is to be a discussion between authors and reviewers (Aug 7 - Aug 13) so please do engage now, early in the window, so there is time for a back and forth.

Thanks!