Can an AI Agent Safely Run a Government? Existence of Probably Approximately Aligned Policies
Authors: Frédéric Berdoz
Roger Wattenhofer
Venue: NeurIPS 2024 poster (2024)
Keywords: Alignment
Planning
Social Choice
AI Safety
Primary area: safety_in_machine_learning
TL;DR: This paper introduces probably approximately aligned (PAA) and safe policies in the context of social decision processes.

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.

Can an AI Agent Safely Run a Government? Existence of Probably Approximately Aligned Policies
Frédéric Berdoz
Roger Wattenhofer
ETH Zürich fberdoz0ethz.cn ch
ETH Zürich
wattenhofer@ethh.cdh ch
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 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 sufficient condi- tion 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.
Introduction
The deployment of Al systems in critical applications, such 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 the real world [8) and 2) there is no formal guarantee that the objective they have been trained against, typically scalar quantity such as loss or a reward, faithfully represents human interest large [4]) Addressing these limitations is commonly referred to as Al aligument, an umbrella term including a wide array of methods supposed to make Al systems
of different modalities behave as intended 11 24
Yet, to our knowledge, every metric for alignment is a posteriori, i.e., a system is deemed aligned as long it does 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 particularly vast, and where single metric can perfectly represent the intended behavior.
In the context of critical (e.g., social) decision processes, where 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 society would not trust human policymaker with hidden motives and unknown track record, it would also distrust an autonomous policymaker whose objective is not, priori, perfectly clear and verifiably aligned, as the cost of 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 Al agent accountable remains 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 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Democratic
Social
Autonomoux government
government
Election
A Aligmment--
Information bottleneck
Complete infommation
Society
Policymakers
PAA sgfe agent
Slow
Next
Action
Social
Action
dy mumices
Democratic (left) autonomous (right) governments. Transparent elections must be Figure 1:
replaced with reliable alignment mechanisms.
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 I..
While it is clear that priori alignment is essential for the safe delegation of such decision power, comes the cost of two unavoidable prerequisites. Firstly, requires 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-estable eesaealtabllee theories of utility and social choice. For completeness, we also discuss all the assumptions that allow such metric to exist. Secondly, one can only ensure that an agent is 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 this knowledge (domain specific expertise, heuristics, physical/data-dritee driven modeling, or mix thereof), assume it is encapsulated in 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 construct verifiably aligned policy? Or, the very least, can we use to ensure the safety of more complex (black-bor -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), in the sample complexity of finding PAA policies. In our setting, this complexity two-faceted: First, the number of calls to the world model (similar the number of calls to perfect generative model in [18), ), and second, the amount of feedback (think ballots) required to confidently rank which state is socially preferred. While 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, assume that the action space is finite. Concretely, our contribution is threefold:
also interested
can decide which decisions delegated autonomous agents,
First, define 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.
type of Social Markov Decision Processes, replacing the traditional
Next, given an approximate world model with sufficient statistical accuracy (which 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 (poten- tially misaligned) policy in order to ensure that it does not take any destructive decisions, i.e., actions that might lead state where even the optimal policy is unsatisfactory. We refer to these adapted policies safe policies.

---

2 Background
2.1 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
2.1.1 Utility theory
is commonly assumed that the agency of an individual is governed by its internal binary preference relationship z 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 's representation theorem [T] 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 : - T (called wiility functions) such that u(s) S u(s') < 8 338 8 Vs, s' E (note that any strictly monotonically increasing function can transform 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)(s) 4z (s')) and 2s (s)) - us(s), respectively, for any i f and j 8'. We detail the various measurability and comparability levels in Appendix I.I.I. and we refer to these levels as the informational basis of utilities. Apart from that, we fix 0 <<0min mmin S (8) S Umar < for any and (we will allow Umin 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 AU A Umaz
Unin and L
{u S + [Umin Umaz]]
2.1.2 Social choice theory
Let I be a society composed of N members, each with its preference relationship 3; and a corre- sponding utility function u, E U over state space S, í E I. Let Rs be the set of complete orderings on S and u E 2 be a vector gathering the utility functions of all individuals. A social welfare functional f (SWFL) is a mapping D, - Rs with D, S 2 In other words, it is an aggregator of individuals' utilities, indirectly preferences. A long line of work ( 32 29 has attempted to define which conditions this SWFL should satisfy (sometimes called axioms of cardinal welfarism, see Appendix 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 I. and any SWFL f satisfying (XI), (U), (IIA) and (WP), there exists social welfare function (SWF) W R + R such that, if (u(s)) > W(u(s')). then ranks strictly higher than s' in su). This important it states that the best social state must maximize certain function W, which can therefore be used as a measure of social satisfaction. In other words, the non-welfare characteristics (i.c., any information influencing f fu) 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 1..22 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? 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 Eq. ① covers all possible SFWI.. See Appendix A.1.3 for detailed mapping between informational bases, SWFLs and parameter q.
3

---

min (s
9 = -00
xEI
Σ
u=(s)9
0 E R
(u())))
FET
(I)
π (s())) AEI
9 = 0
max us (s)
9 = 00
2.1.3 Future discounted social welfare
At deployment, 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 are constant, i.c., u,(s; t) u, t') u;(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. (s( 2 uz t''; for states s, s' and times t * f', then i's welfare is at least as high in state at time than in state s' at time t' (or vice versa for S). 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 I, what will the satisfaction levels at time 1' >> in any given state. However, to model the fact that humans prefer immediate reward, we discount the utility of the state at time L' with factor ((('-t) when comparing it with the utility of the state at time t, where 7 E [0, 1[ is discount factor. From these assumptions, becomes possible, at time t = O, to quantify the cumulative social welfare of any future state trajectory $1 $185554... by computing the quantity -t=0
_/= n' ((41)). )), which
will refer to as the future discounted social welfare of that trajectory (see Section 2.2.2) 2). Using this quantity, we formally define alignment follows:
An autonomous agent aligned if and only if it always takes actions that maximize the expected future discounted social welfare.
2.2 Social dynamics
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.
2.2.1 Markov decision process
Let M = AS,A, p, 7. be an infinite horizon, 7-discounted, discrete time MDP where S is the state space (discrete or continuous), AA is the action space (discrete continuous), p : x A + P(S) is the transition dynamics of the environment (with P(S) the set of probability distributions over S). A - RRmin Rmaz] the reward of the environment, and 7 E [0, 1 is a discount factor (favoring immediate over distant rewards). Given E S and E AA, p(s"|s, a) is the probability of transitioning to state s' after taking action state s, and r(s, a) the expected immediate reward after taking that action. In MDPs, actions are chosen according to policy т. S + P(A). with T ([als) the probability of taking action a state s. Given an initial state 8p, the tuple (M, π. 80) fully defines a distribution P- over trajectories
$1008101 $202.... where a; T T(-1s;) and 8141 ~ pl 8t, az). If the environment dynamics or the policy are deterministic, we will use the slight abuse of notation
St41 p(st, 0z) and Tss)). respectively. The efficacy of given policy n is measured by the state and state-action value functions, defined respectively as follows:
Σ Ent(ss t=0
TT (s) (1
(=(sa))=((s.. + (Bssp(( (s))).
For a given state 8 and action a, the optimal state and action-state value functions are defined by V*(s)= sup, V*()) and (*( = sup,, Q* (s((s)). a). Given > 0, policy is called e-optimal (or optimal) if satisfies V (*) 2 V*(s) - e (respectively V*(ss = (s) for all 8. Given small
technical assumptions, it can be shown that there always exists optimal policy 337 [2].

---

2.2.2 Social Markov decision process
Definition (Social Markov Decision Process). Let I be society with utility profile u E UN and social welfare function Wg. In addition, let and A be the corresponding state and action spaces, p the social environment dynamics and 7 discount factor. The MDP (S, A,p,Yz,7) with reward rz defined by
( a) = (e (u('));;; is a Social Markov Decision Process (SMDP), denoted MM = w.
In this setting, S contains all the possible states of the N individuals, 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 Mr = (S, A. Wq: u 7) be SMDP. The expected future discounted social welfare of policy in state is defined
WT ((-pp((1i)0==)))
Σ (Wg(u((e+1):
and takes value between Wmin
Unin and Wm Uans, with AW Wmer Wmin- T-y
As shown with the next lemma, the expected future discounted social welfare of a SMDP is equivalent the state value function of the corresponding MDP. This equivalence makes it natural metric for alignment, as it enables the use of wide array of known results on MDPs.
Lemma 1. For any SMDP Mi =S, A. p. Wa: u, 7), the expected future discounted social welfare of policy is the state value function of in the MDP M = AS,A., 7), with rz set in Eq. (2)
The proof follows directly from the tower property of conditional expectations (see Appendix 1.2.1
2.2.3 Approximate rewards
If p is unknown, the true reward of the SMDP in Eq. 2 can only be estimated a posteriori, i.e., after taking action in state multiple times and observing Wa (us))). 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 E P(S) to anticipate the effect of an action. Moreover, even if p is known, computing W (u(s')) exactly for given s' ~ 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 set of assessors I, C 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:
K -) (u(((s)): K Σ (y(u(s*)).
fI (s, a; K) EK
(3)
where sp is a "Monte Carlo" estimation of Eses, with K E N samples independently drawn from p(-1s, a), denoted s s?..... The core of our analysis is to understand how K, and the inaccuracies of e affect the validity of alignment guarantees.
Results
3.1 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 S < 1, E > 0 and SMDP Mz = (S, A. W q: 7). a policy л is 8-g-PAA (Probably Approximately Aligned) if, for any given 8 E S, the following inequality holds with probability at least 1-60 d:
TT (8) 2 max T (s)
7²
5

---

Definition (Approximately Aligned Policy). Given E > 0, policy is E-AA (Approximately Aligned) and only if is O-E-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 (6 > 0) and Corollary (6 = 0) in the next section.
Theorem 2 (Existence of PAA and AA policies). Given SMDP Mr (S, Wg u.?) with E R and any tolerances >> 0 and 0 - 5 < 1, if there exists an approximate world model p such that
(1-1))
sup (s.a)ESxA
(KL(p(-1s, a))lp(-1s, a))
(5)
8AW
then there exists computable 8-E-PAA policy. Consequently, there also exists computable e-AA policy.
3.2 Near optimal planning
We prove Theorem by providing planning policy πAA and by proving it satisfies Eq. 4 under the given assumptions. To this end, we present a modified version the sparse sampling algorithm [9] (which originally assumes that p and are known, which is not the case here). Given some parameters K, C' and n, we define the recursive functions:
("(s,a:KCC,I,)- {
h= heN*
(s, K) +) + (-00 (s;
(6)
(" max Q" as,,, aEA
Intuitively, Q² and 4 are recursive approximations 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.,
(
max Q" (s, I, eEAA
It is deterministic in the sense that, for given QH, it outputs single action. However, Q is non-deterministic since In and s' are sampled randomly. The next results clarifies under which conditions TAA is indeed 8-E-PAA (Theorem 3 or e-AA (Corollary 4
Theorem 3 (TAA is d-E-PAA). Let MI (S,A, W u, 7) be a SMDP with IR and an approximate dynamics model such that d sup(s.a) DeL(p(-1 a) ()),)(-1,,.))
(1-77)
< 8AU
for
any desired tolerances 0 and O 6 < 1. For any k 2 log,
(1-7)c
/Bd
define
AU
(1-7))
2 (1-7)²s
Vdav (1-7)**AU and let TPA be the policy defined Eq. v8(1-7)
with param-
eters
H2 2 max (,,, (L))
K > Ar? g=
((H - 1) In In x "-V24K(H A 212
In (t)
C2 (I-7]= K,
x2
n N 1
2 2K
r (3, Uminy U Umaz, 4)
and where I (B, Umin, Umaz, 9) is function defined in Eq. 9 Then TPAA is 8-E-PAA policy. Corollary 4. Let Mz = AS W u, 7 be SMDP with q E R and an approximate dynamics model such that d sup(ea) (Kl(p( (s, a))
(1 8AU2
any for any desired tolerance 0.

---

Define A (1-7)e VAAU 5(1-7) and let πAΛΛ be the policy defined in Eg.
7
with parameters H, C
10
and n as in Theorem
3 and K 2 B
(H 1) (1-1) H "VV12(H- - 1)IA
AV g²
+ In
) Then [UU
PAA is an E-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 the one proposed by Kearns et al. [9] for their original sparse sampling algorithm, although several additional tricks and intermediate results are necessary to accommodate the approximate world model ý and reward řz. First, we derive a concentration inequality for the power mean function in order to quantify the approximation error between W:(:; T,) and Wa (:(:Z), Using a slightly modified (two-sided) version of the Sreffdinn-SSrfliing inequality 4 33 (see Lemma in Appendix [...II. we find the following bounds:
Lemma 5. Let Wa be the power-mean defined in Eq. Q.. with q E RR. Given a, a E R. (or R.
for 9 = 1) such that a < b, let X E [a,b] be a set of size N and let Xn be a subset of size N sampled uniformly at random without replacement from X. Then, for 0 < (X( and
m min(n, N n),
2no²
(X),((,,,) W. (x(x) 2c 2ccp
(T
T(E,a,b,))
(8)
n N
)1
+ m
where
(1-2 (1-20)
9<0
(a (oタ-ルン
9 ==
(b+z) (log b- loga)
a(e,a,b,g) =
0< < 1
(9)
(b4 ()6) 0933
q 9=1
[b-a]²
2aa2 29
(b+gr) [br 2a)²
9>1
Similarly, for q E {+ox):
P (X,,) (2()) 2 8 <
n
N
(utilitarian rule). is sufficient to have N' (1 + 2X in Theorem 3 However, for 1, I depends highly on and b (respectively Umin and U Umar in our setting). Worse, for q to, the bound depends linearly on n. Indeed, q -0 corresponds to the egalitarian rule, which defines social welfare the lowest welfare among individuals. As this individual might be unique, the probability of not selecting it in I, can be as high as N. The same argument can made for q = +o, which is why we purposefully avoid these scenarios in Theorems 2 and 8 Regarding the eиror induced by the approximate model p. we bound it using the following lemma:
See Appendix A.2. for the full proof. Note that, for
Lemma 6. Let f S + [fmmn fmarl be bounded function with 0 S fmin S fmaz < oc, and p. E P(S) be two distributions such that D (xll)) S E TR. and. Then
d [xs][f(s)] - EEmD[f())]] s 2(fmax - fmon ) min 2. 1-1---4
See Appendix A for the full proof. Combining Lemmas and 6 along with other classical concentration inequalities, we can bound the error (Q"(s, (s (s,a) with high probability. The last step of the proof is to quantify how this error affects the state value function V (consequently WTPAA from Lemma D. which can be done using the following results:
Lemma 7. Let Q be a (randomized) approximation Q" such that (s. (s. a)l S with probability at least 5 for any state aactionction pair (s, a), with E > 0 and < 5 < Let TQ be the
greedy policy defined by ( arg max Qss, a). Then, for all states
25 > (Vmax Vmin) with probability at least 1 2k6, VK N",
1) (*(s) - (5) <
7
1-7
2: + 28(Vmac Vmen)
2) (*(s)= - (F) <
almost surely.
1-7
7

---

These are fairly general results as they do not depend on how Q is derived. Statements closely related We provide a proof in Appendix A.2.1 for completeness.
to 2) have already been shown T9 35
3.3 Safe policies
Although Theorem 2 may initially inspire optimism regarding the title of the paper, the policy TAAA proposed in Eq. 7 is expensive for small E, 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 aceuracy remains untouched. In most realistic settings, Dx (pll)) is imposed by the state-of-the-ar knowledge upon which ý is built, which implicitly restricts the achievable tolerance E. 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 E, we will show that we can use our PAA policy to adapt any black-box policy π (e.g., a policy built top of a LLM) into safe policy, which we formally define as follows:
Definition (Safe Policy). Given [Mmine Wmar] and 0 << 8 < 1, policy π is 8-w-safe if, for any current state s, the inequality (x, sup,, W [s') 2 holds with probability at least
1- 8 for any action a such that T(als) > O.
Intuitively, a safe policy ensures (with high probability and in expectation over the environment dynamics) that the society is not led in destructive state, that is, state which might generate high immediate satisfaction but where no policy can generate an expected future discounted social welfare of at least w. This is considerably weaker than the PAA requirements, as we no longer concerned about social welfare optimality. The ability to adapt any black- 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-Bal Box Policy). Let R S + A be any policy and A(s) S A be restricted subsets of actions for all states s, with I(s) A EmeA(s) m(als). The restricted version f of π is defined as
a aE A(s)) or
II(s) 0, 0 < II(s) < 1, II(s) -0)=1 1,
[(ass) &
(a|ss I
a A(s)
and
(10)
T (a a A(s)
and
This is similar to action masking presented in 20) It might happen that (alss) = 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 destructive state. The challenge lies in finding what are the subset of safe actions for every 8. Our proposed method to safeguard any policy is the following:
Theorem 8 (Safeguarding a Black-Box Policy). Given a SMDP MM = (S, A, P. WT, q: u, with q E IR predictive model p and desired tolerances E [Wminy W Wmaz] and O 8 1, define (s)ssa) & Q"(ss a; K, In) with Q" given in Eq. (6) and any H, K, C,n 2 1. For any policy ग, let Tsafe be the restricted version of л obtained with the restricted subsets Asafels) A {a E A: (8) 2 you + Umax o.,, where
In 12(C1A|)8
dAUd' (1 7]-
N nNT man
AU2 2K
AU2
H HAU
+7V 2C(1 - 7)²
and with the shortened notation I maz A D(Umany U Uning Umar, 9) d' A /mint [ e-d) and
d a a..() (
Then Tsafe is 8-w-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 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).
8

---

4
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 (2I]) use social choice MDPs in order to tackle decision-making under dynamic preferences. However, their setting significandly different from ours: In their work, the state space S is the set of preference profiles u 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- 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 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 .. 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 ý is available) do not relate the accuracy of P to the validity of the desired safety guarantees, as they mostly assume that p 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 [1] 39 55. 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] [3], based on the theory of basic human values (3I. 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 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 intractable in most realistic settings, as it must be computed over all possible state trajectories [34
5
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. third practical limitation 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 # and y R 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- Serefinn-Srfigggg inequality (4).
Conclusion
We present a formal and quantitative definition of aligmment 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 first attempt at rigorously defining the alignment of governing autonomous agents, and at quantifying the resources (n, K, C, H) and knowledge (ø) needed to enforce the desired level of alignment (=) or safety (w) with high confidence (8).

---

Acknowledgments and Disclosure of Funding
Special thanks Prof. Dr. Hans Gersbach for his insightful and thorough feedback, which contributed to the refinement and clarity of this paper.
References
Eitan Altman. Constrained Markov Decision Processes. Routledge. 2021.
[2] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete Problems Al Safety, arXiv preprint arXiv: 06565, 2016.
Kenneth Joseph Arrow. Social Choice and Individual Values. Wiley: New York, 1951.
Rémi Bardenet and Odalric-Ambrym Maillard. Concentration Inequalities for Sampling without Replace- ment. Bernoulli, 21(3):1361 1385, 2015.
[5] Samuel Bowman, Jeeyoon Hyun. Ethan Perez, Edwin Chen, Craig Pettit, Scott Heiner, Kamile Lukosuite, Amanda Askell, Andy Jones, Anna Chen, et al. Mcasuring Progress on Scalable Oversight for Large Language Models. arXiv preprint arXiv:22 2idi::2211.0335 1.03500, 2022.
[6] Paul F. Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep Reinforcement Learning from Human Preferences. In Advances in Neural Information Processing Systems 30 (NIPS), pages 4299 -307,, 2017.
[7] Cyrus Cousins. An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning. In Advances in Neural Information Processing Systems 34 (NeurlPS), pages 16610-16621, 2021.
[8] Mary Cummings. Rethinking the Maturity of Artificial Intelligence in Safety-Critical Settings Al Magazine, 62-1), 2021.
[9] Claude Aspremont and Louis Gevers. Equity and the Informational Basis of Collective Choice. The Review of Economic Studies, 44(2):199-28) 209, 1977.
[10] Gerard Debreu and Werner Hildenbrand. Representation of a preference ordering by a numerical func- tion. In Mathematical Economics: Tiventy Papers of Gerard Debreu, Econometric Society Monographs, chapter 6, page 105-110. Cambridge University Press, 1983.
[11] Hanze Dong, Wei Xiong, Deepanshu Goyal, Yihan Zhang, Winnie Chow, Rui Pan, Shizhe Diao, Jipeng Zhang, Kashun Shum, and Tong Zhang. RAFT: Reward rAnked FineTuning for Generative Foundation Model Aligmment. arXiv preprint arXiv:2304.06767 2023.
[12] Fugene A. Feinberg. Total Expected Discounted Reward MDPS: Existence of Optimal Policies. Wiley Encyclopedia Operations Research and Management Science, John Wiley Sons, Ltd, 2011.
[13] lason Gabriel. Artificial intelligence, values, and alignment. Minds and machines, 30(3):41 I 1-437, 2020.
[14] Deep Ganguli. Liane Lovitt, Jackson Kernion, Amanda Askell, Yuntao Bai, Saurav Kadavath, Ben Mann. Ethan Perez. Nicholas Schiefer, Kamal Ndousse, et al. Red Teaming Language Models to Reduce Harms: Methods, Scaling Behaviors, and Lessons Leamned arXiv preprint arXiv:2209.0783 2022.
[15] Shangding Gu, Long Yang. Yali Du, Guang Chen, Florian Walter, Jun Wang, Yaodong Yang, and Alois Knoll. A Review of Safe Reinforcement Learning: Methods, Theory and Applications. arXiv preprint arXiv:2205. 10330, 2023.
[16] John R. Hicks and Roy G. D. Allen. A Reconsideration of the Theory of Value. Part Economica, 1(1): 52-76. 1934.
[17] Jiaming Ji. Tianyi Qiu, Boyuan Chen, Borong Zhang, Hantao Lou, Kaile Wang, Yawen Duan, Zhong- hao He, Jiayi Zhou, Zhaowei Zhang, et Alignment: Comprehensive Survey. arXiv preprint 13 19852, 2023.
[18] Sham Machandranath Kakade. On the Sample Complexity of Reinforcement Learning, Doctoral dissertation, University College London (United Kingdom), 2003.
[19] Michael Kearns, Yishay Mansour, and Andrew Y Ng. A Sparse Sampling Algorithm for Near-optimal Planning in Large Markov Decision Processes. Machine learning,
2002.
10

---

[20] Hanna Krasowski, Jakob Thumm, Marlon Müller, Lukas Schäfer, Xiao Wang, and Matthias Althoff. Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarking. arXiv preprint urXiv:2205.06550 2023.
[21] Kshitij Kulkarmi and Sven Neth. Social Choice with Changing Preferences: Representation Theorems and Long-run Policies. arXiv preprint arXiv:201 1.02544, 2020.
[22] Abhilash Mishra. Al Alignment and Social Choice: Fundamental Limitations and Policy Implications. arXiv preprint arXiv:2310.1668 2023.
[23] Nieves Montes and Carles Sierra. Value-Guided Synthesis of Parametric Normative Systems. In Proceed- ings the 20th International Conference Autonamous Agents and Multingent Systems (AAMAS), page 907-915, 2021.
[24] Richard Ngo. Lawrence Chan, and Sören Mindermann. The Alignment Problem from Deep Learning Perspective. arXiv preprint arXiv:2209, 200.22209000666. 2022.
[25] Claudio Novelli, Mariarosaria Taddeo, and Luciano Floridi. Accountability Artificial Intelligence: What it is and how it works, Al & SOCIETY, pages 1-12, 2023.
[26] Long Ouyang. Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang. Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Training Language Models to Follow Instructions with Human Feedback. In Advances in Neural Information Processing Systems 35 (NeurIPS), pages 27730-27744 2022.
[27] Vilfredo Pareto. Manuale Economia Politica con una Introduzione alla Scienza Sociale. Piccola biblioteca scientifica. Societa editrice libraria, 1906.
[28] David Parkes and Ariel Procaccia. Dynamic Social Choice with Evolving Preferences. In Proceedings of the 27th AAAI conference on artificial intelligence, pages 767-773, 2013.
[29] Kevin W. S. Roberts. Interpersonal Comparability and Social Choice Theory. The Review of Economic Studies, 47(2):211 1-399, 1980.
[30] Stuart Russell, Daniel Dewey, and Max Tegmark. Research Priorities for Robust and Beneficial Artificial Intelligence, Al magazine, 36(4): 105-1 2015.
[31] Shalom H. Schwartz. Universals in the Content and Structure of Values: Theoretical Advances and Empirical Tests in 20 Countries. In Mark P. Zanna, editor, Advances in Experimental Social Psychology. volume 25, pages 1-65. Academic Press, 1992.
[32] Amartya Sen. On Weights and Measures: Informational Constraints in Social Welfare Analysis. Econo- metrica, 45(7):1539-1572 1977.
[33] R. Serfling. Probability Inequalities for the Sum in Sampling without Replacement. The Annals of Statistics, 2(1):39 48, 1974.
[34] Carles Sierra, Nardine Osman, Pablo Noriega, Jordi Sabater-Mir, and Antoni Perelló. Value Alignment: A Formal Approach. arXiv preprint arXiv:21 2021.
[35] Satinder Singh and Richard C. Yee. An Upper Bound on the Loss from Approximate Optimal-Vaar Value Functions. Machine Learning, 16(3):227-233, 1994.
[36] Robert H. Strotz. Cardinal Utility. The American Economic Review, 43(2):384 397, 1953.
[37] Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[38] Leslie Gabriel Valiant. A Theory of the Learnable. Communications of the ACM, 27(11):133-1144 1984.
[39] Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoe V. Le. Finetuned Language Models are Zero-Shot Learners. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
[40] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz. Survey Preference- -Based Reinforcement Learning Methods. Journal of Machine Learning Research, 18(136): 1-413)))446,.. 2017.
[41] Simon Zhuang and Dylan HadfieldMMenell Consequences of Misaligned AL. In Advances in Neurul Information Processing Systems 33 (NeurIPS), pages 15763-15773, 2020.
[42] Åström, Karl Johan. Optimal Control of Markov Processes with Incomplete State Information I. Journal of Mathematical Analysis and Applications, 10:174-205, 1965.

---

A Appendix
A.1 Utility and Social Choice Theory
A.1.1 Measuring and comparing utilities
Measurability of u U can either be cardinal, where one can numerically measure absolute levels of satisfaction for 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 Additional dichotomization becomes possible when comparability is nutshell, utilities are either ordinal non-comparable (ONC), where individuals transform their intrinsic utilities differently when reporting; cardinal non-comparable (CNC), which 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; 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.
transformations [16 36 27
taken into account 22
A.1.2 SWFL properties and implications
Here is list of the most common properties imposed given SWFL D, - Rs. along with their definitions. We denote s the binary preference relationship corresponding to s(u), that is, s I(()> s' and only if s' ranks equally or higher than s in f'u).
(U) Universality or unrestricted domain: U
(IIA) Independence of Irrelevant Alternatives: For every u, u' E uN and S' C (f for all S' then fs (u) = fs (u'), where fs (u) is the partial ranking obtained after excluding S' from fu))
(WP) Weak Pareto criterion or unanimity: For all pairs 8 E S, if u(s) > u(s). then s ranks strictly higher than s' in fu)
(WPI) Weak Pareto with Indifference criterion: For all pairs s, E S,, if u(s) 2 u(s'), then ranks equally or higher than s' in f(u).
(SP) Strong Pareto criterion: For all pairs 8, E S, if there exists i E I such that u.(s) > ux(s") and (s) 2 u, (s'), Vj E I \ {i), then s ranks strictly higher than s' in f(u).
(NI) Non-Imposition: For all R E R. there exists u E 'Dy such that s(u) = R.
(C) Continuity: For any v E R and s, S.S, the sets
E E u(sss) = vu((s) = v and Im))) s' for some u E u N
and
(V' VERN u(s') = v. (ss) and s' Is(a) for some E 3
are closed.
(WC) Weak Continuity: For any
x and R., there exists u' E u such that f fu) fu') and 0 < u(s) - u((s) for all s E (component-wise inequalities).
(N) Neutrality or welfarism: For all quadruples s',t,'' E S, if u, u' E are such that us)) = (s') and u(l) = u' (t'), then f(u) and fu'' agree on the partial rankings of (s, I) and (s' t') (i.e., either and s' are preferred, or either t and t').
(A) Anonymity or symmetry: For all u E UN f(u) = f(u') with u' any permutation of u.
(ND) Non- Dictattoto::::: There is no single individual such that === for any u.
(IC) Incentive compatibility: preferences (i.c., there is no tactical voting).
in the best interest of each individual to report their true
12

---

(S) Separability or independence of unconcerned agents: For all u, u' E u. if there exists IR and of a' E R for E I', and u, = ud for i I T'', then
I' C I such that u, ((u) = [nn). I' is the set of unconcerned agents.
(PDT) Pigou-Dalton Transfer principle: Define r(s) = Eiez (s()). For all u E u and 8, / E S such that (()) = a(t), if [s)(s) - ū(s)] - (t) u(t) for all i E Z, then s ranks equally higher than in fuu).
(XI) Informational basis Invariance (XI): The SWFL is invariant under the given measurability and comparability assumptions: (ONCT), (CNCI), (CUCT), (CFCI), (CRSI), (OLCT). That is. (u) = f(u') for any two utility profile u, u' that are undistinguishable under the given informational basis.
We now provide 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 few important results (assuming ||| 2 3).
(CRSI) (CFCT) (CUCT) (CNCT) = (ONCI). Additionally (OLCI) = (ONCI).
(XI) (U) (IIA) (WP) = There exists W TR-N -> IR such that W (u(s)) > W(n(s') implies that ranks strictly higher than in fu) This is important as it states that the best social state must maximize W. In other words, even if f is not neutral, the non wellariaarssm characteristics are of a secondary importance and can only break ties between and t such that W (u(s)) = W (u({).. 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) + -(DD). 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 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 SWFL.s that are non-dictatorial.
(A) - (ND).
theorem (single winner elections): (ONCT) + (IC) + -(ND). (SP) + (WP) but the converse is not true.
Giibard-Satterthen
(XI) + (WC)
A.1.3 Power mean and SWFL correspondence
Table 1: The different social welfare functions (SWF) corresponding SWFL that satisfies (U),
(II),, (WP), (A) and (XI) for the different informational bases 29
(XI)
SWF (W)
Power mean
(ONCI) (CNCI)
Impossibility (Arrow 3
(CUCI)
(s)
g 1
SEZ
(OLCI)
min (s) or max us(s) TE
E {
VET.
(CFCI)
min u, (s), max (s()) or Σ (s())
E [
iEI
NEI
AET
(CRSI)
min u, (s), max (s)), Σ ui (8)9 or Σ log[u:(s)]
g E (+oo)
'E1 iEI
IEI
13

---

A.2 Proofs
A.2.1 Intermediate results
Lemma 1. For any SMDP Mr = (S. Wa: u, the expected future discounted social welfare of a policy is the state value function of in the MDP M = A,,.,, 7), with set in Eq. (2)
Proof. Let T. 80: do, $1, d1,, 8, denote truncated trajectory up time L. From the definitions of (s; and rz, we have
(rr)
(150000
Eyap, (118,80=))
E Eyppp (1,,)
Σ
> B (1t_:)/((mm000))))rr)//) ( (y (u({))
+ (1 (g(u($(+1))
E Tup (1,,50mm) [Wg(u(s(+1))
t=
Eyopp (1s.e0)))
Σ > Ln' (u((tt))))
(s;
Lemma 5. Let Wg be the power-mean defined in Eq. ① with q E R. Given a, b E R (or R+ for g 1) such that < b let X E ba be set of size N and let Xn be subset of size n < N sampled uniformly at random without replacement from X. Then, for 0 < E < Wx( and min(n, N n),
(X),((X,)) Wx(x) 2 2cxp (-01-
2n
T(E,a,b.g).
(8)
3 [1
where
2029-2 (at b9
q <<0
9 0
(b+5)=(log 1o
T(E,a,b,g)=
6- 10+ (4(1-91e1 (bv 2v)
0 0<
(9)
1 9=1
(b-
2020 24
9> 1
(b+ge) (br avy
Similarly, for q E {
P [I], (x(X)] 2 8) 5
Proof. To simplify the notation, write S Wx(X,)) and μ (2') such that
5a
Σ 2
4
Σ x
for q E
N
z,eX,
Z
log S logat x?
Σ
log 1 =
Σ
loga!
for q = 0
z
ZEEX
14

---

For E R. we have
PISS
14) 2 e = - P [M - E< < 8 pt
pl E) < <(
g < 0
P [log(H - 5) < <log
q=
(1)
P [H- E)9 < 5 < ((++)
q 9> 0
Therefore:
For q < 0:
8
16 < 5" < ( E
P [[u < - < (p (m- s) = P
1 +
109
11)
11.
( 1 (1-29) 29)E
14 (1 27)E
P P
1C < S" <
1
P
= P 112- (1 22) 8 < 8 < + (1- - 22 1-
[8]
2 P 112 (1 29) 8 p² (1 29)89-18)
||S μ71 < (1 22--9)))-
(12)
where we have used the following approximation (holding for 0 < x S 1 and g < 0):
(1+
2 < < 1 (1 29) < (1 a²)..
Combining Eq.
11 and 12 and using the Hoeffding-Serfiin inequality (Lemma 9 after observing that 0 < a for all i, we get
P
i|s - μ|
N
$] S IP 1|S
- 101 2 (1 (1- 24)-29)69--
(1 (- (- 2n(1 - 22)-229)222222
< 2exp
(1 )ay 19)2
For q = 0:
log(1 -) /
-
IP [log(1 8) < log S < log(( + 8)] = P
< log S -log <
loog(1
E
E
2
< log S -log μ <
#+
+
E
2 P
< log S - log <
(13)
b+c
b+e
where we have used the following approximation (holding for 0 < < 1):
log(1 x)
1 <0
<
S log(1 + +r).
1 x
Combining Eq. (1] and 13 and using the Hoeffding-Serfinng inequality (Lemma 9 after < log for all i, we get
observing that log < log x
P|S pl 2 P
log
log ul| > + E
2n
< 2exp -- (b + <) 2 log a)2
(1
15

---

. For00<q 1:
9
E
P Plu < < <u++=) =P
12 S
14
H 19
1
qEEa
qEPº
2 P
S
11
11 + (1 q)
1t + (1 9)
9E
P
S" 159 (1 g)
b (1 8)
9a
gate
P
b (1 q)E
(1 9)
9aag
P
84 μ < b - g)e
(14)
where have used the following approximation (holding for 0 < S and 0 q < 1):
(1-x)
S
q2
< <1<
qa
S (1+z)².
1+ (1 q)x
(+ q)x
Combining Eq.
11 and 14) and using the Seeffdinn-SSrffling inequality (Lemma 9 after 1 for all i, we get
observing that x
qaaE
P|S - 11
2
e)
S
S
10
b + (1
9
S 2eexp
(1 (-
2nq2 au
- aoyo)
g)s) 11+
. For g 1: We directly apply the Hoeffding-Serfiing inequality (Lemma 9 to obtain
(-i1-
2nc²
PIJS e N s] S 2exp
[1-
a N
)1
1)
a)
m
For q >
11 E
P F(u - =) < S (μ +) = P
4 < 8
4
14
9e
qe
P
49 < 5 <
+
14
+ 9e
+ 9e
qE
9E
P
12 <
1+
44
b + qs
+ qs
qaae
ga?e
2 P
4
S" 41 +
+ 9p
+ qs
n71 < ga
P
|S
(15)
+
g
where we have used the following approximation (holding for 0 < x S 1 and g > I):
q2
qe
1- (1=)) S1
(1 + x)).
1 1 q
1 1 qr
Combining Eq.
11 and 15 , and using the SrefffdingSSeffiing inequality (Lemma 9 after x b for all i, we get
observing that α
9a
PIS a
>
e]
<
P
S
b 9s
(-
2nq
2xpp
(11-
-1-
) 4 a9)²
16

---

For q = +oo; Since we make no assumptions on the distributions of r; other than a S S b, we can only guarantee that max,,ex, 2, x. zil < E if Zaar arg max 2; is sampled in X,- This happens with probability at least N (the maximum might not be unique), and thus P max 22 maxx;ex 24z
N
For q = oo: Same analysis as for = +00.
Lemma 6. Let f S - [mmin Fmazl be bounded function with 0 I fmin fmaz < and
p.P E P(S) be two distributions such that D (pll)) I d RR and Then
Exsp([((s) - Bx- < 2(Smax Sminn m min 2: - e-d).
Proof.
1 f(s)p(s)ds - {(s))(())
BBnglf(s)] - Eanp(f(s)]
1 (J(s) - fmin)p(s) - (J(s) - smin)((s) ds
| (f(s) - -mmn)(((s) -p(s))(s)))) ds
/ If(s) -fmin [I((s) p(s)
I (Jmaz Smin) / (p(s) ((5) ds
= 2(fmax - Smin )0pp
where have used the definition of the total variation distance: 8(p.D) Ss (p(s) -(s) ds. By Pinsker's inequality, we have
8(p. p) S V DKL(Pl)))
Additionally, by Bretagnolle and Huber's inequality:
8(p. S VI e- (pl())
The result follows from the assumption (KL(P))) S
Lemma 7. Let Q be a (randomized) approximation of Q" such that (Q* a) Q(s a)l S a with probability at least 5 for any state-action pair a), with >> 0 and 8 < Let aQ be the greedy policy defined by <s(s)) = arg max Q(, a). Then, for all states
25
1) (*(s) - (())) <
+ 7hth (V Vmmi)) with probability at least 1 2k8, VA N",
1-7
22 + 28(V 28(m Vinn)
2) V*(s) (8) <
almost surely.
1-7
Proof. First, note that if 1Q" Q(s, a)l < E with probability at least 1- 8 for all state-action pairs (s, then (s x- (s)) Q* T (s)) < 25 with probability at least - 28 since
(s x (s)) < Q(s (s) + = Q(s, (s())) + = (s, + +
The factor in the probability comes from the fact that we need the Q estimates to accurate for both actions n (s) and TO (s). For the first inequality, note that, with probability at least - 2k6, the
17

---

first l estimates of Q are as-accurate for actions x (st) and T5(5)), t = o,.... k
- 1. If this happens,
then we have
(*(s)- = (0s (
2 + (T. (8)) ( (3()))
= 2s + yB /Be'pp |a (s)) IV (V* V (s))
k-1
S
Σ
7' + 7 "Vean - V Vmin)
25
1-7 (Vmax Vmnn),
which concludes the first part of the proof. Concerning the second inequality, since Vnnin 1 (*)s I Vmars we have
3 Q (0(( 2 (1-28)lQ (s, (2) min 2 x (s)) maz Vminn)).
Let my be a policy that replicates T6 for the first j actions and that is optimal from action j + 1 onward. We now show by induction that (s)(s) 2 V*(s) >y for all 8, where X = )1 = 2s 25(mma Vmin) and A3- X 715-1 for j > 1. This clearly holds for = 1:
4 (s) B& [(s, (s)) + >TE (o=))==
=E
2 (x, (s)) -
(s) A1-
For j > 1, assuming that the statement holds for j - 1, we have
V (s) Es
+ , - ( 2 B [(0, (8)) + F, ~ +
(5') -1y-11
3 [ (8))
V - -
ES [0(():T((8) -
2 (*, (8)) -- 7
(*(() >g.
We now show that limy (s) = V=O (s) for all s. Noting that V (s) 2 (*) (due to the optimality of f after steps), we have
S V*) - v=a = EErnp-((ny
7r((8 az)
7 7'1(8, as)
Σ >r (8i, az)
- Brapp (0=8) 00=))
7 7888
(Bmax Remin)
Rmax
Rmin
+
Therefore, by the squeeze theorem, we have limj-so0
- (T) = 0. Finally, noting that (s)
A
lim
\j
1 1-7"
==
18

---

we have for all s:
28 + 20(V Vmnn)
(*) lim (s) (s) 3
lim X, (s)
700
Lemma 9 (Hoeffding-Serfinng Inequalities 4 33 Let X = { be finite set of N
real points and Xn = {x,}}== subset of size n < N sampled uniformly at random without
replacement from X. Additionally, denote p 1/2 Σ Di=1 2t min, 24 and max; 24. Then, for m min(n, N n) and any & > 0:
2 N )1
P
X,
26
< 2
(1
1 (b a)
Proof. First, we show the slightly more general result:
n n
2:
1)
P
X,
M26
S exp
{
(1 x) 1)(( a)2
j=1
1
202n
2)
F
X,
- us S
< exp
n
(1 - {
x1(1 + N- [b a)
The proof of 1) similar to the one proposed in 4 Let Zn 1/2 Ei= X3- μ.. We have for any 0:
P Z 2 P An...
Anee]
E(eAnZn)
exp
16- a)) X2
n2
Ane
Ann
N
where we have used Markov's inequality along with Proposition 2.3 from 4 the original result proposed by Serfling [33]. The result 1) follows by finding that minimizes this upper-bound, i.e.,
(slightly improving
4ng
(n + 1)
{b - a)
For 2), we note that sampling Xn, is equivalent to sampling X'v-n = X \ Xn. Therefore:
1 Σ
P
X
=
X
nf
$
N
X
-
==l
N R
N-n
P
X
-
11
N
j=1
1 N-n
P
X -
nE
N
N- 71
j=l
252n n
$ exp
(1 [1
(1-
x
where we have used 1) the last step. Lastly, the final result follows from Boole's inequality (union bound) between 1) and 2).
19

---

A.2.2 Existence of PAA and AA policies
u. 7) be a SMDP with E IR and P Theorem 3 (TPAA is P-c-PAA). Let Mz = (S,A, W u,
2101-))
an approximate dynamics model such that 2 (e)() DKL PxL(p(-1s, a))lp(-1s, a)) < 820 for
any desired tolerances
0 and O 5 < 1. For any k 2 log, (1-2)s v
(1-7)² ).
define
_
(1-2)²E
vasu v8(1-7)
(1-7)n*U and let TAA be the policy defined in Eq.
with param-
eters
H 2 max (,,00g, {
K > AU2 f²
(1I- (IH-1)lm In "- (M 1) B+
AU2 In (t)
72 c (1-7)2 K,
n N (1 AURN r (B, miins U Umazi a)
and where (3, mnias Umaz: 9) is a function defined in Eq.
9 Then TPAA is 6-E-PAA policy.
Proof. Similarly to [9,, the core idea (and challenge) of the proof is to bound [Q" a) Q# (s, a)l for all atate-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, write the following for h 0 (omitting the dependency of K, C' and In in the notation):
(s) - (s, = rr( - fr, as) + E,
8 ap) (V" - EC
(g (())))))) (('))
-E [W (u( [)) s'rpl (s I (uss)) 4n)
BK
+ * [V* EC E (s
(8')))
-x W (u(s - E ~p( (s.aa)
((()s 4n)
+ Ex' [W,(us')): [x]] B.
W2 (u(ss);; In)
+ -0 (w,')(s)): [.)] B (s,a)
(G(u(s'):L.)
+ > (E [V* Evr (0)
V
(s')l)
+ > (E, -f (s,n)
[V*(s']] - (..))
V (s'))
+ > [ p 13.
[V')''
EC EC (o)) (s)))
such that, for any state-action pair,
QQ (x, a)
(* S F. (p
[Wg(((s): Wg (u('('');
2,
+ (ma) (a (x)) -. (W (n)(
20
+ EE Io [n)] - 30110()))0) W (u(sss)) A.)1
Za
+7
E V (s')) (a.n (5))
Za
+ 7 (E V (8') - EC
pp)ap(-) (V* (s'))
2, 1 (m))) (1()) - n (s')ll
+ y DC
2o
20

---

where we have used the triangle inequality, the linearity of expectation and the fact that |B[X]| S
|| for any random variable X. From Lemma 5
we have that Z S E with probability least
1 - 61 where
81 _ 2 exp
(- (-(1 21 m
2
(51 Umins Umars 1))
exp (- (-1-
net
I(11, Umins Umaz>9) 9))
a N
Recall that Umin I (u()) I Uma and Vinin and utility profile u. Therefore, from Lemma 6 we have (with probability 1)
Uiuaz = Vmaz for any state Limin I (*)))= I T-7 T-7
Z2 S 2AU min { d 2 1.1--00 o
AU
min d 2 , -e 1all-e--- m E1, (16)
and
Za 2
where AU - Umaz Umin and d a (s.o) DrL (s, a)ll,(-1s, a)). Furthermore, by the standard Hoeffding's ss inequality, we have Zz S with probability at least 1 - 83 where
2K 2
83 a 2 exp
AU2
and Z5 S cs with probability at least 1 ds where
- 20(1
20
233
8, 2 2exp
AU2
Finally, we have
C
EC (lo))) -
Σ
(s()) - -s:)
= C
i=1
1
max Q² ("((ss,)) a) -max (s,
0 1=1
1
Q* a.) (st x;)l
0
with
ā - arg max. (s), if max. Q (8i, a) 2 max. 1 arg max, (s; if max, (s; a) < max, (
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 cg a AU and on & E1 + + E3 + 7 + I-y
E3 + -1) for h > O, and let do _ and d), - 6 + 83 + 5g + CLAl for h > We start the induction by noting that, for any state-action pair,
AU
Q² (s, a) - (s, 1Q" < 1-7 on
with probability Φ0
For h 1, assuming that, for any state-action pair, (s, ( an-1 with probability at least 1 - 0h-1, we have from above
IQ" (s, a) Q" (s, a)l E + 82 + 7854 + Es + 0a-1) = 0%
(17)
with probability at least 1 - 51 8g 5g ClAl = tn. as we require that all C estimates of Qh-1 are accurate for each action. Solving for an, we get
# Σ 1=0
AU + 7 1-7
aи
(' to
(e) + + 7(4 +ss) 1-
+ AU 1 1-7
1-7
33 21+ + 7 + +es) + AAU
(18)
1-7
21

---

Note that E2 and E in Eq. (6) are non-controllable and only depend on the accuracy of the en- vironment model p. If require (*()) ()PAa(()) I c, then must have 2(2+)ee)) from Lemma 7 Using the definitions of E2 and E1 from Eq. (T)). this condition becomes minf of 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 (as - for z E [0, D). 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"
(1-7)a
2 1 - e ) <
(1~>)%=² with d - (s,)) DKL (p(-1s, a)llp(-Iss, a)). Since S (1-7) (as
AU
16AU2
2(E2 + 7EA)
V8dAU 7)3 > 0.
28
(1 (1-7)2
Solving for Φh, we get
Φн (61 + 53 + 65) Σ (CIA))
1=0
(C|AI)
(81 + 63 + 65)
CIA -1
3 2( + 8g + (c(A)) H-1
(19)
where the last inequality follows from the fact that C/A - 2 CCAI C and |A| 2 2. Finally, using part 1) of Lemma] 7
we get that for any state 8, with probability at least 2k0H.
h E N
2ah + +
V*(s) VVFAAAS)
<
(20)
1-7
+(e + AU + 1 1-2,
2 トー AU)
<
E1 + + te 7(4 65)
(1 7)
That is, using the definitions of E2 and 64, and imposing the tolerance E, we require
E + E3 + YES + * AU +
7 7 AUU S
(1
(1
V8dAU
E (1 713
2
2
We fix 5 = 785 7 H AU
(1-g)² (e
EdAU (1-7)3
1
A B. From that,
I-
directly obtain the required planning "depth" H max (1, log,
3 Av
}1 as well as the
lower bound k 2 log,
(1-2)c
Rd (1-7)²
Additionally, choose C (1-)-= K such that
7²
AU
83 65 eex (-
2k [AU}]
and we choose n such that 81 S d3, or equivalently
nt n8, Unin Umars 4)
2K
2
(1 N)
AU
This is satisfied for
n N N 1+ AU2T(B Umins Umany 9)N
2K
With this choice C and n, we can write
2K 82 AU2
81 + dz + 8z < 6exp
The last step choose K such that 2k0H S 8, that
2K82
24k(K| H-1 exp
(21)
AU2
22

---

H = (i.e., 1
s0
f
we can simply choose
AU2
24%
K
In
2,32
8
and if H > 1 (i.e., 7 >
AU we can choose
AU2
A
K 2
(I 1)
244 1)|
12
Indeed, setting 2 -
# V2 1)I and y -
8 AU
and substituting the expression for K, the
left-hand term of inequality (1 can be rewritten as
H-
--1
2(H
-H
In
In
1 In
8
11
8
8
8²
y²
y
H-1
In
126
8²
26 T-
y28
H-1
In
926
6
1
S 6,
(22)
where we have used the observation that x 2 1 and y S 1 along with the fact that 0 < In(x)
< 1 for
all 2 1 in the last step. Finally, assuming there exists an optimal policy in MM (see [12
37
37 for the
necessary conditions), and knowing from Lemma that V*(s) = (s) for any policy, we know
that V (s) VEPAA (8) S implies (s) 2 sup, W (8) -
Corollary 4. Ler Mr = (S, W u, 7) be a SMDP with q E R and P an approximate dynamics (1--2)"
model such that d 2 (u.() DKL (KL(p( (-1,,,,, a)ll a)) < 8AU2 for any desired tolerance > Define B & (1-y)²e
/2dAU and let TAAA be the policy defined in Eq. 7 with parameters H, C
10
5(1-7)
and n as in Theorem and K
AC2 g
(H 1n)m ( 1222 1)
AU
+
AU D
Then
TPAA is s-AA policy.
Proof. The first part of the proof is identical to Theorem 3 but we use part 2) of Lemma instead of part 1) in Eq. 200.. With that, we have for any state s:
2(1 - 7)aH + 2ΦHAU
(*(s) (T (s) <
(1 7)
2
(1 11-71 72 (5) 82 + + ((4 + + AU 2AU (81 + +6)(C((41)))1)
That is, using the definitions e2 and E4. and imposing the tolerance require
(1 (1-7)²
VddAU
E1 + E3 705 + 7 H AU + 20 + 8g + (5)(C(A)))
c (1 7)
2
E3 YES n" AU B A (1->)² [e- VadAU (1-7)a²
We fix 51
From that, we directly obtain
10
the required planning "depth" Il max 11, log,
}
Similarly Theorem 3 we choose
AU
C' -1 K and
AB2 Umins Umaus N)NV -1
n 2 N 1+
2K
23

---

such that
2K3²
51 + + + 85 S 6exp
AU2
The last step to choose K such that
2K
3
12((]Al)"" exp
(23)
AU2
AU
If H (i.e., 7 7 ).). ) simply choose
AU
12AU
K
In
2,3
8
and if H (i.e., 7 > AT can choose
K
A B
(111)
"-V12(H
A)
A
+n
AU
ga
3
We show that this choice of satisfies Eq. 23 by setting conclude the proof using Lemma]
AU and in Eq.
22
We also
A.2.3 Safe policies
Theorem 8 (Safeguarding a Black-Bot Policy). Given a SMDP (S, Wq: u. u.?) with q E R. predictive model and desired tolerances E [Wminn Wmazi and 0 < à < 1, define Qu(s,a) & (s, K, C, In) with Q" given in Eq. (6) and any H, K, C, > 1. For any policy т, let Tsafe be the restricted version of a obtained with the restricted subsets Asafols) {a E A: Qu(s,a) 2 yo + Uman a), where
In 12(C
2AUd'
N
AU
AU2
H A
+7V
7)2
nNT
2K
2C(1
-7-2
1
and with the shortened notation I maz A (Umaax U Umary 4) d' / f2 e-d) and
d A suP(s,a) (xz(p(((s,o))l a)). Then ssafe 8-w-safe.
37 for the necessary conditions), and knowing from Lemma 1 that (*(s) WT for any policy, we can write sup W (s) = (s). 2 w. Using the definition of
Proof. Assuming there exists optimal policy in Mz (see 12
Therefore, the condition for safe actions becomes (V the optimal state-action value function Q":
(s, rz (s, a) DE s (s'),,
we can rewrite this condition once again as
Q' 2 + rz(s,a).
We know from Eq. 17 in the proof of Theorem that, for any state-action pair (8, a), (s, ( a; K, I. I ay with probability at least 1 âhi where ar and dh given Eq. (18) and (9). respectively. That is, if Q" a; K, C, Ia) 2 yo rr(s. + ag, then the above condition is satisfied with probability at least 1 ΦH.
From Eq. (88 have
E2 + 7E1
E1 + E3 + yEs
7 AU
ag <
+
(24)
1-
1-7
1 1-2
24

---

where (using d (s,) (x
-
2
N n
2 81
61
In
-
In
(1 Umins 9
81
n.NI(Uman mazi Umins Umaz, q)
E2
2
min
2'
e
A
2
E3
In
2K
83
2AU
d
84
min 2'
e-d];
AU2
85
2C(1 - 2)
In
55
Finally, in order to obtain 8-w-safe policy, we must have @F S 5. From Eq. 19), this is satisfied if
2(61 + 63 (c)(C()) "1 <
or similarly if 833 ds 6 (CCAAD
Defining d' min 2: 1 e-d d and F maz
T(Umaz: Umins Umazi 9), and substituting
6,, 61, E5 d1, 83, óg in Eq. 24
we obtain
12ICIA))
2AUX' - (1 7)2 +
n
A
A 2C(1 7)
7 AU
1-7
nNT mar
2K
1-y
Using the fact that r)) I Umaz for any state-action pair, we can conservatively define the restricted subsets of safe actions as (s) {a Q" a; K, I.) nw + Umar + a for any state 8, where a is the right-hand term of the above inequality. Therefore, restricting any policy π with probability least 1 ó for any action
with these subsets ensures that (s)-p((ss.a) [V* (s') 2 a that has a non-zero probability of being selected.
25

---

NeurIPS Paper Checklist
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 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 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 is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The main theoretical and practical limitations of the results are presented in Section []] The assumptions are extensively discussed in Section and the complexity of the proposed method is discussed in Sections and 5
Guidelines:
The answer NA means that the paper has 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 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
26

---

Answer: [Yes]
Justification: For the main results, S simply from Theorem and Corollary whose respective proofs are sketched Section 3.2 and fully derived in Appendix A.2.2
The proof of Theorem is presented in Appendix A.2.3 All intermediate results (lemmas) are derived in Appendix A.2.1
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
27

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, 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 the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. 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, confi-
dence intervals, statistical significance tests, 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 with given experimental conditions).
28

---

The method for calculating the error bars should be explained (closed form formula, call 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.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Question:
Answer: [Yes]
Justification: We have reviewed the Code of Ethics, and we have conducted our work in accordance with it. The very subject of our paper is to make Al safer, and to understand when 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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations 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 why the paper does not address societal impact.
29

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 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 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe 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)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have 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 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 use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include 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 use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
30

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
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.
31


Reviews:
[{"review_id": "FlnhSsYALS", "reviewer": "Reviewer_1bQj", "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.", "questions": "I think the problem is not well presented. \n\nE.g. \n\nSection 3.2 - Algorithm for Computing the Policy:\nHow can you the result of Equation (7) are not clearly explained. \n\nEstimation of Reward (Equation 3):\nEquation (3) still appears to be a posterior approach.", "limitations": "Yes.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "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.", "weaknesses": "I think the problem is not well presented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for the time spent reviewing our paper.\n\nIt is primarily mentioned that the problem is not well presented. We agree that clarity in presentation is crucial and would greatly appreciate specific suggestions on how to improve it. Below is a detailed discussion about the two specific examples that are put forward:\n\n- **Equation (7)**: To prove our main contribution, the existence of PAA policies (Theorem 2), we construct such a policy in Section 3.2. This policy is built on a near-optimal planning algorithm that approximates Q-values using a world model. Once these Q-values are obtained, the policy selects actions with the highest Q-value, similar to many common reinforcement learning algorithms. Equation (7) formally defines this policy. The technical core of the paper demonstrates that this policy is indeed PAA. In Section 3.2 (with full proofs in the Appendix), we show that the approximate Q-values can be made arbitrarily close to the optimal Q-values. While this specific policy is primarily designed to be provably PAA across various applications, we acknowledge that is is one of many possible PAA policies and we anticipate that future work may develop more efficient algorithms for specific applications.\n- **Equation (3)**: This is still a prior approach according to our definitions because the future states $s'$ are sampled based on the world model $\\hat{p}$ rather than the true environment $p$. Thus, the agent does not need to perform actions in the real world to learn the optimal actions. Instead, it can plan according to $\\hat{p}$ to ensure that its next action is quasi-optimal with high probability. The policy is therefore a priori aligned, as it ensures alignment before any real actions are taken.\n\nWhile the main concerns of the reviewer focus on presentation and clarity, we would greatly appreciate a more detailed feedback related to the paper's soundness and contribution, which would help us address the concerns leading to the borderline score. In particular, we would like to understand if the reviewer found that some claims could be better supported (soundness), and if these claims lack originality (or significance) with respect to existing literature (contribution).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r7NuVYd0Xp", "reviewer": "Reviewer_Fxrx", "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.", "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": "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Originality: This paper introduces a novel, quantitative definition of alignment in social decision-making contexts, drawing from utility and social choice theory.\n\n- Quality: The paper primarily focuses on theoretical contributions rather than empirical experiments. It is well-structured.\n\n- Clarity: The paper provides detailed mathematical derivations and proofs to support the existence of PAA and safe policies. It includes extensive references and context, including foundational works in utility theory, social choice, AI safety, and reinforcement learning, emphasizing the interdisciplinary nature of aligning AI with human values.\n\n- Significance: This work has a significant impact. While primarily theoretical, the work aims to provide a foundation for developing AI systems that could be safely used in critical applications like social governance, policy-making, or resource allocation.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for the time spent reviewing our paper.\n\nWe understand that that the primary concern of the reviewer is the gap between the theoretical result presented in the paper and their practical implementation in real-world scenarios (in particular for safe policies). To address this concern, please find below a detailed discussion about the implementability of these policies in several applications, along with a general roadmap.\n\n- **Healthcare decision making**: \nWe consider a personalized autonomous doctor (black-box AI agent) for a specific patient. Each week, based on the patient’s health data, the agent determines the appropriate medication for the patient by consulting the patient about various alternatives about aspects such as tolerance to side effects, budget constraints, and preferred timing of administration. In that scenario, the world model could simply be the rate of success and of side effects associated with each medication/dosage during the trial phase of that treatment. Based on these factors, the patient rates each medication alternative on a scale from 1 to 10, and can decide on a minimum discounted welfare level $\\omega$. If the agent cannot find a verifiably safe action among its proposed alternatives, it halts and refers the patient to a human doctor. Based on the given guarantees, there will still exist (with high probability) a medication path that generate a future discounted welfare of at lease $\\omega$.\nA certified doctor (or several) could also be directly involved in the process. This involvement could take two forms: (i) the doctor acts as a stakeholder accountable for the AI's recommendation, providing feedback on the risks associated with each alternative (also on a scale from 1 to 10 , which is then aggregated with the patient’s score to form a global welfare score), or (ii) the doctor serves as a world model, predicting the impact of each alternative on the patient's health in the absence of other predictive models.\n\n- **Financial trading**:\nWe consider the example of an autonomous mutual fund, where investors pool their money to generate returns. The investors could collectively set an aggregate tolerance threshold, $\\omega$, that the autonomous trading system must guarantee. Before executing any trade, the system could present various trading strategies along with their associated risks to a subset of the investors. These investors would then assign a utility score (e.g., from 1 to 10) to each option, considering factors like risk and investment type. If no strategy meets the risk tolerance $\\omega$, the autonomous trader would abort the transaction and either defer to a human trader or return the funds to the investors. This mechanism ensures that each investor can trust the autonomous agent with their capital, offering a level of verifiable security not always present with human traders. This type of framework could strongly appeal to ethical investors, who prioritize not only the financial returns of their investments but also their moral implications.\n\n- **Autonomous driving**:\nIn such a scenario, where decisions need to be made rapidly (likely at the sensor acquisition rate), direct human feedback is typically not feasible. However, cars could communicate with each other. For instance, when a car intends to change its trajectory (such as overtaking, turning, stopping, or accelerating), it could broadcast various proposed paths to nearby vehicles. These neighboring cars would then assess the risk (e.g., collision potential) of each trajectory based on their own planned actions and surroundings (which might not be visible to the initial car). The initial car would then select a safe trajectory or abort the maneuver and return control to the driver if no safe options are available. Although this may not be the most natural application of PAA policies, we believe that designers of autonomous vehicles could benefit from approaching the autonomous driving problem through a social choice framework, where each car would act as a stakeholder within the environment (i.e., the roads).\n\n- **General roadmap**:\nIn general, to construct a safe policy from a black-box policy, several factors must be considered. First, we need to establish acceptable tolerance levels, $\\omega$ and $\\delta$. Next, we must select values for $H, K, C, n$ based on the available resource constraints, such as the number of feedback instances we can gather and the frequency with which we can query the world model to plan each action. Increasing these hyperparameters (excluding $\\delta$) typically leads to a lower $\\alpha$, resulting in a safe policy that is less prone to delegating its decision authority (i.e., that is more useful). The accuracy of the world model also influences $\\alpha$, with a higher accuracy producing a more useful safe policy. If the resulting safe policy is not useful enough, it suggests that either the resources allocated are inadequate or the world model lacks sufficient accuracy  (i.e., $\\alpha$ is too large). In both cases, it indicates that we are not yet ready to safely use the black-box policy for that particular application. However, if the amount of feedback required is the bottleneck, one can also imagine a proxy setting where each stakeholder delegates it’s ability to provide feedback to a personalized model (similar to a reward model) that can automatically provide feedback on a given state without human intervention. Note that the safety guarantees would be valid on the alignement metric computed with these surrogate models rather than with the real utilities.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mUZGgSPdW4", "reviewer": "Reviewer_KXy4", "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.", "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 are well stated.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall the paper appears to be a very reasonable application of a well established form of analysis into a novel domain.\n\nThe main idea of providing bounds for the quality of an agent's policy is very important and will likely be the focus of much work in the near future. This is quite useful work and appears to me as the potential basis for work that can eventually have significant beneficial impact on the world.\n\nThe paper is generally well written and the motivation is clear. In places the math is a little dense but it seems to be as approachable as it can be for this sort of analysis. I do certainly appreciate that you've put a moderate amount of the work into the actual paper rather than stuffing all the important stuff into the appendix.", "weaknesses": "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.\n\nThe 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.\n\nIt 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for the time spent reviewing our paper.\n\n**Usefulness of the theoretical results**\n\nWe understand that the reviewer's primary concern is the lack of clarity regarding the applicability of the theoretical results to real-world scenarios. While we do not expect PAA (or safe) policies to be implemented in practical applications in the immediate future, we believe this work lays a foundation for future research, where relaxing some constraints could make the approach more practical. For instance, as mentioned in our response to review Fxrx, one potential relaxation is using surrogate models to provide the necessary feedback for constructing the alignment metric. Another relaxation to address the issue of world model accuracy is to develop world models biased towards predicting catastrophic state-action pairs, as errors in predicting non-critical outcomes are less problematic. The rationale behind the paper's fully theoretical approach is to emphasize the existence of a priori alignement (through PAA policies) rather than presenting and testing a specific policy, with the hope that it will spark further research in this direction.\n\n**Practicality of the proposed PAA policy**\n\nRegarding the practicality of the PAA policy introduced in the paper, it is designed primarily to facilitate mathematical proof of its PAA property in a general setting (hence demonstrating the existence of PAA policies in any context). The policy essentially employs a brute force approach by testing all possible actions to identify the best one. However, in a real-world scenario, domain expertise and other simplifying assumptions would certainly be leveraged to eliminate certain state-action pairs, significantly reducing the algorithm's complexity. We intentionally omitted an experimental section to avoid giving the impression that one of the main contribution of the paper is the PAA policy itself, and that it should be implemented as is.\n\n**Are we simply shifting the difficulty to building better world models?**\n\nThe main question of the reviewer is a very important one. We address it by exploring two key implications of our work:\n\n- Firstly, as mentioned in the paper’s introduction, *a priori* alignment is feasible only if we have a sufficient understanding of the consequences of each action available to the autonomous agent. However, our results offer an alternative perspective: they indicate that critical actions should not be delegated to an autonomous agent if the available world model is poor when it comes to predicting their effects. In that sense, our work is the first to provide a quantitative framework for determining which actions can be safely entrusted to an autonomous agent. We believe this type of analysis alone could initiate several research threads in the near future.\n- Secondly, while it is true that creating a statistically accurate world model can indeed be as challenging as developing an aligned AI agent, achieving consensus on what constitutes a good world model (i.e., one with high empirical accuracy) is generally more straightforward than defining what constitutes an aligned AI agent (i.e., one with sufficient alignment, which is typically poorly defined). In other words, while our work may shift the challenge to another complex problem, it is one where the solution is easier to verify and where the objective is better defined.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qkU9KJfMQU", "reviewer": "Reviewer_nJtj", "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.", "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": "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.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper is well written, and the background is particularly clear.\n2. The definitions and theoretical results are thorough and rigorous. This paper precisely relates the probability of aligned behavior to the world model accuracy, which I believe is valuable.\n3. This paper acknowledges that realistic inaccuracy in the world model could cause intolerable uncertainty in the PAA policy, and shows a more practical approach (safeguarding a black-box policy).", "weaknesses": "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?\n\nTypo: On line 277, I believe \"expansive\" should be \"expensive\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and for the time spent reviewing our paper.\n\n**Feasibility of safeguarding black-box policies in SMDPs**\n\nWe argue that the main issue is not whether safeguarding a black-box policy is feasible, but whether it produces a useful policy. Indeed, the practicality of the safeguarding method comes from the fact that the computational complexity of finding $\\mathcal A_{safe}$ can be made as small as desired based on the resources available (with $K$, $C$, $H$, and $n$ being chosen as desired, unlike the PAA policy where they are determined by $\\epsilon$, $\\delta$, $\\gamma$ and $D_{KL}(p\\Vert\\hat{p})$). However, as these values decrease, the $\\alpha$ term in the definition of  $\\mathcal A_{safe}$ increases, and the resulting policy may become less useful, as only actions with very high Q-values will be considered safe. Such actions might not even exist (empty $\\mathcal{A}_{safe}$), in which case the safe policy is essentially useless. On the other hand, deriving the computational complexity to ensure usefulness (i.e., the safe policy always selects an action) cannot be done in the general case, as it would require knowledge of the Q-values for every state-action pairs.\n\n**Scale of the reported utilities**\n\nWe believe it is crucial that assessors are instructed to report their utilities for different states within a unified range, such as between 1 and 10. If this range is not standardized, utilities would need to be artificially mapped to a common scale to be aggregated, which we believe would introduce more distortion compared to when this mapping is done internally by the assessor before reporting. However, even with a unified range, interpersonal comparability is not guaranteed, as any given rating within that range might reflect different levels of welfare across different individuals. This issue is philosophical in nature, and there is no feasible experiment to determine whether utilities are truly comparable.\n\nFrom this point, two approaches can be taken:\n\n- One can simply treat the utilities as if they were comparable, and construct a social welfare function based on them.\n- Alternatively, one can take additional steps to calibrate the utilities using anchor states that should elicit similar welfare across individuals. For instance, in an economic context, assessors could be instructed that a rating of 9 corresponds to landing their dream job, while a rating of 2 corresponds to being unemployed. Although this may not necessarily make utilities more comparable (as people may have different sensibilities to these events), it does provide a more interpretable framework.\n\nIn general, while interpersonal comparability might seem like a strong assumption, there are practical examples where it appears evident. For instance, it is generally conceivable that two people can determine who enjoys chocolate more through a conversation. This necessarily implies that their utilities have a certain level of comparability.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)