Expectation Alignment: Handling Reward Misspecification in the Presence of Expectation Mismatch
Authors: Malek Mechergui
Sarath Sreedharan
Venue: NeurIPS 2024 poster (2024)
Keywords: Reward Design
Primary area: human-AI_interaction

Abstract: Detecting and handling misspecified objectives, such as reward functions, has been widely recognized as one of the central challenges within the domain of Artificial Intelligence (AI) safety research. However, even with the recognition of the importance of this problem, we are unaware of any works that attempt to provide a clear definition for what constitutes (a) misspecified objectives and (b) successfully resolving such misspecifications. In this work, we use the theory of mind, i.e., the human user's beliefs about the AI agent, as a basis to develop a formal explanatory framework, called Expectation Alignment (EAL), to understand the objective misspecification and its causes.
Our EAL framework not only acts as an explanatory framework for existing works but also provides us with concrete insights into the limitations of existing methods to handle reward misspecification and novel solution strategies. We use these insights to propose a new interactive algorithm that uses the specified reward to infer potential user expectations about the system behavior. We show how one can efficiently implement this algorithm by mapping the inference problem into linear programs. We evaluate our method on a set of standard Markov Decision Process (MDP) benchmarks.

Expectation Alignment: Handling Reward Misspecification in the Presence of Expectation Mismatch
Malek Mechergui, Sarath Sreedharan Colorado State University Fort Collins, 80523 (Malek. Sarath. Sreedharan
Abstract
Detecting and handling misspecified objectives, such reward functions, has been widely recognized as one of the central challenges within the domain Artificial Intelligence (AI) safety research. However, even with the recognition the importance of this problem, we are unaware of any works that attempt to provide clear definition for what constitutes (a) misspecified objectives and (b) successfully resolving such misspecificaatios. In this work, we use the theory mind, i.c., the human user's beliefs about the Al agent, as basis to develop a formal explanatory framework, called Expectation Alignment (EAL), to understand the objective misspecification and its causes. Our EAL framework not only acts an explanatory framework for existing works but also provides us with concrete insights into the limitations of existing methods to handle reward misspecification and novel solution strategies. We use these insights to propose a new interactive algorithm that uses the specified reward infer potential user expectations about the system behavior. We show how one can efficiently implement this algorithm by mapping the inference problem into linear programs. We evaluate our method on a set of standard Markov Decision Process (MDP) benchmarks.
Introduction
Given the accelerating pace of advancement within AI, creating agents that can detect and handle incorrectly specified objectives has become evermore pressing problem [Dafoe et al. 2020). This has resulted in the development of several methods for addressing, among other forms objective functions, misspecified rewards (cf. Hadfield-Menne Menell al. [2017]). Unfortunately. these works operate under an implicit definition what constitutes an incorrectly specified reward function. The few works that have tried to formalize how agent could satisfy human objectives do by avoiding the objective specification step altogether [Hadfield- Menell et al. 2016).
Our primary objective with this paper is to start with explicit formalization of what constitutes misspecified reward function and the potential reasons why the user may have provided one in the first place. However, our motivation for providing such formalization goes beyond just the pedagogical. We see that such a formalization provides us with multiple insights of practical importance.
Our formulation will follow the intuition set by recent work (cf. [Abel et al.) (021 that looks at reward functions user starts with target outcome or behavior set of outcomes or behaviors that they want the agent to achieve. The reward function proposed by the user one whose maximization, they believe,
means of specifying a task as opposed to being an end to itself. As such, the
In this paper, we will focus cases where expected/desired outcomes correspond to agent achieving certain states. Section 3 provides a formal definition.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

will result in policy that will achieve the desired outcome. Figure 1 shows how users derive their reward specifications. As presented, their reward function will be informed by their beliefs about the agent and its capabilities (i.e., the user's theory of mind (Apperly and Butterfil] 2009] about the agent) and their ability to reason about how the agent will act given a specific reward function.
A given reward function is said to be misspecified when the policy identified by the agent for the re- ward function doesn't 't satisfy the user's is expectations. As discussed, the reasons for such misspecification could include users' incorrect beliefs about the agent and their limited inferential capabilities (Sreedha ran 2022 To see how such misspecification might occur, consider simple planning problem that can be captured by a Markov Decision Process (MDP) with only three states. Consider a problem where an agent can only perform two possible actions. These correspond to pressing two different switches. Each switch takes the agent to one of the two possible end states where the agent can no longer act. One corresponds to a safe end state, while the other cor- responds to unsafe one. Let's consider human supervisor who wants the agent to go the safe end state and, as such, identifies a reward function that they believe will result in such a state. If the supervisor is confused about which button leads to which state, they may end up coming up with reward function that will result in the exact opposite outcome. Please note that the problem here isn't 't that the agent can't achieve the desired outcome but rather that optimizing for the specified reward will not result in the desired outcome. In fact, given the human's 's confusion about the buttons, no reward function exists that could lead the agent to the desired outcome, which the human will agree is a correct reward function for the task.
Human's bellet about task and agent
expectation agent behavior
Agent Model
Possible reward fungtion
User
Agont
Reward spectfication
Expected pollcy
A diagrammatic overview of how specifying a reward function plays role in whether or not their expectations are met.
Figure I:
We will formalize this intuition about reward specification and, by extension, that of misspecification under the more general framework of Expectation Alignment (EAL). EAL framework will allow us capture scenarios, like the one discussed above, where the human cannot come up with a reward that satisfies the expectation in both their and the agent's models. This invalidates all approaches that try to identify 'true' human reward function, which is then passed onto the agent. Secondly, we will see how we can use EAL to develop novel algorithms for handling reward misspecification that explicitly leverages potential causes of misalignment to come up with more effective queries to identify the human's 's original intent. To summarize, the contributions of the paper are:
We introduce a framework for formalizing and understanding reward misspecification problems namely, Expectation Alignment.
We develop novel query-based algorithm to solve a specific instance of EAL problems.
We empirically demonstrate how the method compares against baseline methods for handling reward uncertainty in benchmark domains.
In the related work section (Section 5). we will also show how existing works on handling objective misspecification relate to our proposed framework. Since it will leverage the specifics of our proposed framework, we will look at the related work after defining our basic framework.
2 Background
We will primarily focus on problems that can be expressed as a Markov Decision Process or an MDP
[Puterman| 2014]. An MDP is usually represented by a tuple of the form M = (S, A, R, 7,80 8o Onder this notation scheme, S captures the set of states, A the set of actions, T S x x - [o, is the transition function such that T(s,, a, s') captures the probability of an action causing the state to transition from s to s', R S x A - IR is the reward function, 7 E [0, 1) the discount factor and finally so S is the initial state (the agent is expected to start from so). Since are focusing
We can additionally use control constraints to limit the actions possible from each state, as in the example in the introduction. However, we will leave it out of the formulation to support a more concise formulation.

---

problems related to reward specification, we will separate out all non-reward components of an MDP model, refer to it as the domain, and denote it as D = 7,,,
The objective of solving an MDP is to find a policy (a function of the form π. S - A) that maximizes the expected sum of discounted rewards (captured by a value function V S - IR). A policy is considered optimal (optimal policies will be denoted with the superscript "+", for example, x²) it results in the highest value (referred as the optimal value V*). is worth noting that an optimal policy is not unique, and for given task, there may be multiple optimal policies with the same value. We will denote the set of optimal policies associated with a model M as IT--
In this paper. we will be heavily utilizing the notion of discounted occupancy frequency or just occupancy frequency, n= S A + [0, 1] [Poupart 2005], associated with policy There are multiple ways to interpret occupancy frequency, but one of the most common ones is to think of them as the steady state probability associated with policy
In particular, the occupation frequency x² (s, a) captures the frequency with which an action a would be executed in a state 8 under the policy æ. Sometimes, we will also need identify the frequency with which a policy π would visit a state s. We can obtain this frequency by summing over the values of x" (s, a) for all actions, i.e., == (s) = En x (s, It is possible to reformulate the value obtained under a policy in terms of its occupancy frequency and rewards. One can also identify the optimal value and, thereby, the optimal policy by solving the following linear program (LP) expressed using occupancy frequency variables:
max
I(s, a) x r().
8,0
(1)
s.t. As S, x(s 8(s, 8b) +7x
als a (s', s'.a'
Σ
Here, is the set of variables that captures the occupancy frequency possible under policy, and 5(s, 80) is an indicator function that returns 1 when s = so and zero otherwise.
In this paper, we will be looking at settings where the human's 's (i.e. the user who is coming up with the reward function) understanding of the task may differ from that of the robot Fl As such, the information contained within the domain used by the robot might differ from the beliefs of the human. We will use the notation D& = (S, A , T 7 .88) to denote the domain used by the robot, while DH = (S, A# TH "H s0) is representation of the human beliefs, i.e., the theory of mind they ascribe to the robot. Note that under this notation scheme, we assume that the two models share the same state space and starting state. This was purely done to simplify the discussion. Our basic formulation and the specific instantiation hold as long as a surjective mapping exists from robot to human states. This would usually be the case where the human model is, in fact, some form of abstraction of the true robot model.
Expectation Alignment Framework
In this section, we will first develop framework to understand how humans go from expectations to reward specifications, which we will use define reward misspecification. With the basic model in place, we can effectively invert it to develop methods to address such misspecification.
To build such forward model, we need formal method to represent behavioral expectations in the context of MDPs. While several promising mathematical formalisms could be adopted to represent a human's behavioral expectations, we will focus on using the notion of occupancy frequency. There are multiple reasons for this choice. For one, this is a natural generalization of the notions of reachability, Psychological evidence supports that people use the notion of goals in decision-making [Simon] 1977]. While goals relate to the idea of reaching desirable end states, the notion of occupancy frequency allows us to extend it intermediate ones. It even allows us to express probabílistic notions of reachability, Secondly, occupancy frequencies present very general notion of problems that can be expressed as MDPs. As discussed in Section [ the value of any given policy can be represented in terms of their occupancy frequency [Poupart] 2005). Finally, the popular use cases in the space of reward misspecification can be captured using occupancy frequency (See Section (5).
So, we start by representing the set of human expectations as E which provides a set of states and any preferences placed on reachability for that state. More formally,
'We use the term robot to denote our Al agent as means of convenience. Nothing in this framework requires the agent to be physically embodied.
3

---

Definition 1. Given human's understanding of the task domain D = AS.A", "S."" human expectation set is denoted as E" where each element e in the set is given by the tuple of the form e = (Se; O O,k), where Se C S, O E -,,,,, is a relational operator and l E [0. 1]. O and places limit on the cumulative occupancy frequency over the set of states Se.
"u:?""), the
For cases where the human wants the robot completely avoid particular state 8, there would be a corresponding expectation element ({s): =, 0); on the other hand, if the human wants the robot to visit certain states, then there will be expectation elements that try enforce high occupancy frequencies for those states. In the simplest settings, humans might convert such expectations to rewards by setting low or even negative rewards to the states that need be avoided and high rewards to the states they want the robot to visit. One question that is worth considering is why humans don't just communicate this expectation set. Unfortunately, communicating the entire set may be relatively inefficient compared to coming up with a reward function (for example, one might be able to compactly represent the reward function as a piece of code, while this set may not). This could also be the case if the number of states is very high or even infinite, but even in these settings, the reward function could still be specified in terms of features. Secondly, even if they choose to specify desirable or undesirable states, the expectation set may contain states that the human incorrectly thinks are impossible (for example, the robot jumping onto the table) and may choose to ignore them. This is also related to the problem of unspecified side-effects (Zhang et al. 2018).
It is worth noting that Definition merely provides a mathematical formulation that is general enough to capture human expectations. We don't 't expect people to maintain an explicit set of numeric constraints on occupancy frequencies in their minds. Regardless of what form their actual expectation takes, as long as it can be expressed as some ordering on how the states should be visited, it can be captured using sets of the form provided in the above definition. One could, in theory, also capture non-Markovian expectations using such formalisms. For example, there may be cases where the user might want the robot to visit set of states specific sequence. We can capture such cases by creating augmented states that can track whether or not the robot visited the states in sequence. This method also allows Markovian reward functions to capture such considerations (cf. [Abel et al. 2),2T)), which is unsurprising since the expressivity of occupancy frequency parallels that of Markovian reward functions.
We will claim that policy satisfies an expectation element for a domain if the corresponding occupancy frequeney relation holds for the policy in that domain, or more formally:
Definition 2. A given policy iT is said to satisfy an expectation element
(Se, O,k) for a given domain D, or more concisely e FD n. if the occupancy frequency for state s (x(s) under policy π as evaluated for DD satisfies the specified relation, i.e., OEEes, (s), k) is true.
To relate these expectations to the reward specification process, we first need a way to represent the human decision-making process. For this discussion, we will start with a very abstract model of human decision-making which we will later ground in Section 4 In particular, we will represent human decision-making using a planning function pH that maps given model to a (possibly empty) set of policies.
Definition 3. For a given model M, the set of policies that the human thinks will be selected is given by the planning function P MI > 2 where WI is the space of possible models and II the space of possible policies.
It is worth noticing that, as with DH pp is a reflection of the human's 's belief about the robot's 's model and planning capabilities. In many cases, humans might ascribe lower level of cognitive capability to the robot. However, for this paper, we will ignore such considerations. With these definitions in place, we can describe how humans would choose an acceptable reward specification. Specifically, the human would think a reward function is sufficient if all policies they believe could be selected under this specification will satisfy their expectations, or more formally
Definition 4. For a given the human's 's belief about the task domain D and an expectation set H. a reward function R is considered tuman-sufficiett, if for every policy in π E ppl ((D" R)), you have e FD# n. for all e E "
In this definition, we can already see the outlines of the various sources of misspecification. For one, humans use their understanding of the task and the robot's 's capabilities (captured by Dz) to choose the reward specification. The true robot capabilities or task-level constraints could drastically differ from human beliefs. Next, the policies they anticipated being selected (PH ((D R))) could be

---

very different from what might be chosen by the robot. There is also the additional possibility that the human is not even able to correctly evaluate whether an expectation element holds for given policy, especially given the fact that people are known to be notoriously bad at handling probabilities (Tversky and Kahneman 1983, Kahneman and Tversky [ In many cases, the expectations might be limited to the occupancy frequencies being forced to be zero (avoid certain states) or taking a non-zero value (should try to visit certain states), Here, the human could ignore the probabilities and reason using determinized version of the model (Yoon et al. 2008). Even here, there is possibilityy that humans could overlook some paths that might cause the expectation element to be unsatisfied.
In general, we will deem reward function misspecified if at least one robot optimal policy has at least one unsatisfied expectation set element.
Definition 5. A human- suffaa-nfffiient reward function R is misspecified with respect to the robot task domain Dd and the human expectation set E", if there exists an E EH and a policy т that is optimal for MR = (DR, R), such that d' DD π.
In this setting, it no longer makes sense to talk about a true reward function anymore. As far as the human is concerned, R is the true reward function because it exactly results in the behavior they want in their domain model of the task (D"). ). One can even show that there may not exist a single reward function that allows the expectation set to be satisfied in both the human and robot models.
Theorem 1. There may be human and robot domains, DH and D and an expectation set E", such that one can never come up with a numan-sufficien reward function R that not misspecified with respect to DR, even if one allows the human planning function ' to correspond to some subset of optimal policies in the human model.
Proof Sketch. We can prove this by constructing an example where it holds. Consider the example discussed in the introduction. Here, there is state that the human wants the robot to visit (i.e., the occupancy frequency > 0), and there is a state that the human wants to avoid(i.e. the occupancy frequency- = 0). To achieve the expected behavior in the human model, they have to choose reward function that will result in an optimal policy where the button they believe will lead to the goal state has to be pressed. However, if the functionality of the switches is reversed in the robot model, none of those rewards will result in a robot policy that will lead to the state that the human wanted to visit. This shows that, for this example, there exists no reward function that will result in policy that satisfies the expectation set. Thus proving the theorem statement.
This theorem shows that one can't 't talk about single 'true' reward function that holds for both domains. In the example, as far as the human is concerned, the reward they came up with is the true reward since it results in the exact behavior they wanted. In fact, any reward function that results in the robot achieving its goal will be considered incorrect since it will never lead to the expected behavior in their model. This rules out the possibility of using methods like inverse reward design (Hadield- et al. 2017]. J. which aims to generate single reward function that applies to both the intended and actual environments. On the other hand, the underlying expectations are directly transferrable across the domains. This brings us what the robot's objective should be, namely, to come up with an expectation- aliinned policy, i.e., one that satisfies human expectations in the robot lask domain, when possible, or recognize when it cannot do so.
Definition 6. For human specified reward function R", human expectation set RH, and the robot task domain DR. a policy π E is said to be expectation-atigned, if for all E TH you have e FOR F, where M = (D",, R
The primary challenge to generating expectation-aligned policies is that the expectation set is not directly available. However, unlike previous works in this space, the fact that we have a model that maps the expectations to the reward function means that there is an opportunity to develop a more diverse set of possible solution approaches. For one, we could now look the possibility of starting by learning the human model (using methods similar to the ones described by Gong and Zhang (2020) and Reddy et al. (2018) and use that information to produce estimates of " from the reward specification. Along the same lines, we could leverage psychologically feasible models as stand-in for pH to further improve the accuracy of our estimates (possible candidates include noisy-rational model [Jeon et al. 2020). In the next section, we show how we can develop effective algorithms for generating expectation-aligned policies by looking at an instance where the expectation set limited to certain form.
5

---

4 Identifying Expectaiion-Algneed Policies
We will ground the proposed framework in use case with relatively simple planning function P that returns the set of optimal policies and where the expectation set takes a particular form. Specifically, we assume that there is an unknown set of states in the expectation set that cannot be visited, i.e., there exists some e E E"" takes the form ({+).=, =,00 0) and some states that they would like the robot to visit (i.e., of the form (1s), >, 0)). We will call the states that are part of the first set of expectations the forbidden state set S and the second one the goal set 89, The expectation set described here corresponds to the widely studied reward misspecification problem type. where the robot needs to avoid negative side effects while achieving the goal (cf. Saisubramanian et al. (2022)). )
Let R" be the reward function specified by the user. Since there are already works on learning human beliefs about the domain, we will assume access to DH The first observation we can make from the given setting is the fact that any state that can be visited by a policy that is optimal in R cannot be part of the forbidden state set (as evaluated in D
Proposition 1. There exists no state S and policy π E II MM. such that xx (s) 0 is true.
The proof sketch for the proposition is provided in Appendix 8.1 Next, we can also see that the states part of 89 must be reachable under every optimal policy.
Proposition 2. For every state s E S and policy π E &MMM. (s) > must always be true.
The proof sketch for the above proposition is again provided in Appendix 8.1 One might be tempted to generate the sets S and 5 by looking at all states with low and high reward values, respectively. However, there are multiple problems with such naive approach. Firstly, it is well-known that people encode solution strategies into the reward function in addition to eventual goals [Booth et al. 2023) This means there may be high-reward value states that are not part of S or relatively low-reward states that are not part of S These may have been added to get the robot to behave in certain ways. Secondly, humans may ignore states they think are guaranteed to be reached or will never be reached.
While we can't It exactly calculate S and SC, we will proceed to show how we can generate supersets of these sets. In particular, we will calculate the set of all states not reachable under any optimal policies (denoted S 2 ) and the set of all states that are reachable under every optimal policy (S9
S9) We can generate these sets by using modified forms of the LP formulation discussed in Equation To test whether a given state s; is part of S or not, we will look at an LP that will try to identify an optimal policy that will visit sy. Specifically, the LP would look like:
10, a) x ((8,a) + X [ Ex(s),a)
max
s.t. Vs S,
Σ x(s,0)= 8(s, +7x Σ x(s''a'') a') T (s' ,',
(2)
Σ a(ss,)) x r(s, a) = V
Where a is some positive valued coefficient and + is the value of the optimal policy in the starting state su. We can calculate V* by solving Equation Ton the human model with the specified reward. By adding the new term to the objective, we provide higher objective value to policies that visit the state s,. At the same time, the constraint Σ. x(so. a) = V* ensures we only consider optimal policies. We can now formally state the following property for the above IP formulation.
Proposition 3. For the LP described in Equation 2 if E S then the optimal value x" identified for the LP, the condition Σ. x² (st, a) = must hold.
This follows directly from the definitions of the expectation set and the planning function (a longer sketch is provided in Appendix J. We will again employ a variation of the LP formulation to identify S Specifically, to test if a given state s; is part of So or not, we test the solvability of an LP that tries to create policy optimal value that doesn't 't visit 8,.
max Σ x((s a) x a()
s.t. Vs E S, Σ
x x(s = 8(s, so) +7x X Σ aa x TH s',)
(3)
a
Σ a()s0aa) a) r(s, a) V Σ x x a)
This brings us to the proposition.

---

Algorithm The overall query process
Input:
D", DD, R
S Calculate from D and R
5
Calculate from D and R
S g
S +
while |8t U do
LP < CreateLP(D" (S S , ) Solve, De, Dr Solve(LP)
Dz. Dj +- FindPositiveV alues (DD, Dp)
if Solve not True then
return No Solution end if
2 UD = 0 then return Policy corresponding to X end if
gg S MapToStates S Di 8r, mp)
8 5 8 - S
S + 8 (QueryGoal$)) +
U UQueryForbidden
end while return solution
Proposition 4. For the LP described in Equation if E 89, then there must exist no solution for the given LP.
Now with both sets ST and 8o calculated, the objective of the robot is generate policy that covers all of the states in S9, while avoiding the states in ST. This may not always be possible, so we will need the system to query the user about whether a state E S is actually part of S (i.e., "do I need to avoid s?"), and if a state s' E S is actually part of 8 ("do I need to visit s'?"). Based on their response, we can update the sets and try to see we can now generate a policy that avoids remaining states in the updated set of forbidden states and visits all the states in the updated goal state set. We can identify whether such a policy exists and possible states to query by using the LP:
max -1 D.D
Σ d
dEDoUDP
s.t. Vs S. x((s 5(s, 50) +7x Σ x d') TT (s'.d'.s)
Σ
s'
Ad E De Dr, d20
ss; ST Σ x(; d. =0; Asy E $9 Σ a(5)) + 20
As seen in the equation, this formulation requires the introduction of two new sets of bookkeeping variables Dy and Dg. such that DD1 = | and [Dol = |89) To simplify notations, we will denote the bookkeeping variable corresponding all occupancy frequency is calculated using the robot model. The general idea here is that we turn the requirement of meeting reachability constraints that are part of 8 and S into soft constraints that can be ignored at a cost. This done through the manipulation of the bookkeeping variables. This brings to the first theorem
state s; E ST U S as d. The next thing note is that
Theorem 2. there exists policy that satisfies the requirement that no state in SF is visited and all states in 69 is visited (therefore satisfied the underlying expectation), then the optimal solution for Equation 4 must assign 0 to all variables in Dg and Dr.
Proof Sketch. The reasoning follows directly from how the last two constraints of Equation 4 and the fact setting more variables to zero will result in a higher objective value. Thus, the LP would want to minimize assigning positive values to d variables. It will only give d positive value if forbidden state has a non-zero occupancy frequency or some potential goal states are unreachable.
When such solutions are not found, the variables that take positive values tell us potential states can query. After the query if the user says state shouldn't be visited or should be visited the
7

---

corresponding states are removed from S or So and moved to the set S. (set of known forbidden states) and S (set of known goal states). Once these sets become non-empty, we use an updated form of Equation 4 which now has hard constraints of the form.
sss E S. > x((s = O; ass E S x(( 20
(5)
a
Theorem also holds for this new LP. If the user answers that a state is neither a forbidden nor goal state, then the state is simply removed from the corresponding superset. This process is repeated until a policy found, if there are no more elements in 8 U US9 or the I.P is unsolvable.
Algorithm I provides the pseudo-code for the query procedure. The procedure CreateLP creates an LP of the form described in Equation 4 for the current estimates for S and Šo (along with known ones). The estimates are refined through queries with the user (represented by the procedures QueryGoal and Query orbidden). The algorithm stops if solution is found that doesn't 't require any additional queries, the I.P is unsolvable, or it runs out of states to query.
Proposition 5. Algorithm 7 is guaranteed to exit in finite steps for all finite state space MDPs.
The above proposition holds since, in the worst case, the algorithm would query about every state in the MDP. Appendix 8.2 provides an extension of the method for a planning function based on a noisy rational model.
5 Related Works
Given the ever-increasing capabilities of Al agents, there has been lot of work that has looked at how to handle partially specified or misspecified objectives. Most work in this area tends to be motivated by the need to ensure safety. This fueled by the recognition that people tend to be bad at correctly specifying their objectives (Booth et al.) 2023 Milli et al., 2017]. and optimizing for incorrectly specified objectives could have disastrous results [Hadfield-Men could roughly categorize the work done to develop more general methods to address this problem into two broad categories.
et al., 2016). One
In the first, the reward function is mostly taken to be true, but they assume there is set of hard constraints, usually partially specified, on what state features could be changed [Weld and Etzioni 1994], which are usually referred to as side-effects. As such, these works are usually framed in terms of avoiding negative side effects. Many works in this direction focus on the problem of how to identify potential side-effect features (cf. [Zhang et al., [2018] (Saiubramannann et al.) [022] Mahmud ct a 2023b)), mostly by querying the users. Recent work has also looked at extending these methods to non-markovian side-effects [Srivastava et al.) 2023) and even to possible epistemic side effects [Klassen et al., 2023]. In addition to querying, there are also works that look at minimizing potential side effects when coming up with behavior [Klassen et al. [2022b] Previous work includes work in the context of factored planning problems (cf. [Klassen et al.) 2022a Mechergui and Sreedharan 2023 and reinforcement learning /Vamplew et al. 2021].
The second category treats the reward function provided by the user as merely constituting a partial specification or an observation of the true reward function held by the user. A canonical example is inverse reward design [Hadfeld-Menell) et al., 2017]. which uses the specified reward function as proxy to infer the true objective. For a good balance between conservatism and informativeness, Krasheninnikov et al. [2021] proposes an algorithm to infer the reward function from two conflicting reward function sources. Mahmud et al.
[2023a] use explanations within their framework to verify and improve reward alignment. Pan et al. [2022] proposes anomaly detection to tackle reward hacking due to misspecification. This is also related to the CIRL framework Haddield-Mennl et al. 2016). which eschews an agent from having its own reward function, but tries to maximize the human reward function. However, the agent estimate of this reward function may also be incorrect or incomplete.
Our expectation alignmeent framework allows us to capture the requirements of both of these sets of works. We can set negative side effects or safety constraints by setting the frequency of relevant states to zero. Our framework explicitly captures the fact that the specified reward should not be directly optimized in the true model. In scenarios where the reward function induces the same occupancy frequency in both human and robot models, recovering the human reward function suffices to generate pvecctttionaalinne policies. But, as discussed this is not general solution strategy.
8

---

Another stream of work that is relevant to the current problem is that of imitation learning [Torabi al. 2019] or learning from demonstration [Argall et al., 2009]. Under this regime, the teacher demonstrates a particular course of action to an agent, and it is expected to either imitate generate behaviors that match the intent behind the demonstration. Apprenticeship learning [Abheel and Ng. 2004), and other methods that use inverse reinforcement learning (cf. [Arora and Doshi 2021] treat the reward function as an unknown entity and use the demonstration and any knowledge about the demonstrator to identify the true reward function. The objective then becomes to identify policy that maximizes this learned reward function. In some sense, our work inverts this paradigm and starts from specified reward function and tries to recreate what expectations may have led to this reward function. In addition to all the work on partially specified rewards, our work is also connected to preference/model elicitation (cf. [Boutilier] 2002] and [Chen and Pu 2004]). Our proposed method can be thought of as a form of preference elicitation, except we focus on learning some specific kinds of preferences. It is also worth noting that there have been some efforts within the unverse-reinforcemenn learning community to formalize misspecification (cf. [Skalse and Abate 2023 However, we see such work being complementary our effort.
6 Evaluation
Our primary goal with the empirical evaluation was to compare our proposed method against two baseline methods selected from the two groups of works described in Section [S] Specifically, we wanted to test:
"How the method described in Section compared with existing methods in terms (a) computational efficiency (measured in terms of time-taken) (b) overhead placed on the user (number of queries) and (c) ability to satisfy user-expectations."
In particular, we selected Minimax- Regreet Querying (MMRQ-K) [hhng et al. 2018 (with query size k = 2 and all features set to unknown) and modified form of the Inverse Reward Design method [[Hadield-Menell et al., 2017]. To simplify the setting, we considered an MDP formulation where rewards were associated with just states as opposed to states and actions. For the modified IRD, we avoided the expensive step of calculating posterior distribution over the reward function set and instead directly used So and $². For the expected reward function, a high positive reward was assigned for SC and a negative one for S We then try to solve the MDP for this reward function using an LP planner. For the query-based methods, we simply check with the ground truth on whether a state belongs to the forbidden state set or to the goal state set.
Test Domains. We tested our method and baseline on five domains. Most of these are standard benchmark tasks taken from the SimpleRL library [Abell 2019). Since all examples were variations of a basic grid-world domain, we considered four different sizes and five random instantiations of each grid size (obtained by randomizing the initial state, goal state, forbidden states, and location of objects). For each of the tasks, the expectation set consists of reaching the goal state and avoiding some random states in the environment. The human models were generated by modifying the original task slightly. The walkway involves a simple grid world where the robot can use a movable walkway to reach certain states easily, but the human unaware of it. Obstacles involve the robot navigating to goal while avoiding obstacles (the human model includes incorrect information about the obstacles). Four rooms [Sutton et al. 1999 involves the robot navigating through connected rooms, but in the human model, the use of certain doors may not be allowed. In Puddle, the robot needs to travel to the goal while avoiding certain terrain types, while the human model may be wrong about the location of various terrain elements. Finally, in maze, the robot needs to navigate maze, while the human model may have incorrect information about what paths are available.
Evaluation. All the baselines were with a time-bound of 30 minutes per problem. All experiments were run on AlmaLine Linxx 8.9 with 32GB RAM and 16 Intel(R) (R) 2.60GHz CPUs. We used CPLEX [Blicklú al. [2144 as our LP solver (no-cost edition!] @ First, we found that the MMRQ-K method could not solve any of the instances. This was because the runtime was dominated by the time needed to calculate the exponential number of dominant policies. This shows how computationally
'The code for our experiments be found at atthtps:/ //te::///tttttt httpss////gghhuu...cm/aaa/eee htw.///awll.eeeheeeeee/eeeeeeeee Mechergus/codeMDD

---

Problem Instance
Our method
IRD
Domain
Grid size
Query Count
Time (secs)
No Violated Expectations
Time (msees)
Walkway
(4,4)
2.2 + 0.83
7.7 0.4
1.6 + 0.5
32.3 = 1.4
(5,5)
3.2 + 1.48
11.8 + 0.45
2.26 + 1.03
45 + 1.12
(9,9)
4.5 1 4.8
60 + 1
2.5 3
215.7 1
(11,11)
14.25 +: 2.91
138.57 1: 6.32
3.6 3.9
456.05 + 19
Obstacles
(4,4)
2.4 1.34
9.6
1.4 0.58
4
(5,5)
3+1
13 0.3
2 1.12
46.13 2.42
(9,9)
3.1
62.8 0,9
4 2.66
216.66 12.4
(11,11)
11.75 1: 2.87
134.51 1: 6.88
6.7
450 - 26.6
Four Rooms
(5,5)
1.4 4.55 0.55
3.1
1.42 + 0.75
49
(7.7)
1.8 + 0,45
12.9 + 0.7
1.07 + 0.73
111.5
(9.9)
2.75
71.2 + 0.8
1.35 + 0.74
251 3.5
(12,12)
4.44 1:44:.00
224.98 1 6.84
1 1 0.57
728 728::5222
Puddle
(5.5)
312
13.2
1.131 0.63
49.5
(7.7)
5.46
31.7 7
1.63
123.27 15
(9,9)
3.14
42.11 + 1.86
0.66
275.2 5.9
(11,11)
2.44 1.85
132.5 + 7.132
0.6
566.1 7.8
Maze
(3.3)
1.66 1 0.57
5.9 0.1
I 0.87
25.1 1..11... 1.51
(5,5)
1.66 0.57
13 1 30 = 0.5
1.36
0.67
47.3 1.3
(7.7)
2.33 - 0.57
1,46 + 0.66
106 1.6
(9,9)
7.5 + 6.27
35,34 + 14.18
1.42 + 0.51
244.29 + 14
Table I: For our method, the table reports the number of queries raised and the time taken by our method. For IRD, it shows the number of expectations violated by the generated policy and the time choose policy that results in violated expectations.
taken. Note that our method is guaranteed
expensive methods from the first group are. On the other hand, our method much faster, and even in the largest grids, it took less than five minutes (Table and only required very few queries. Note that the maximum number of queries that could be raised in each case corresponds to the total state space. In each case considered here the number of queries raised was substantially smaller than the state space size. Thus showing the effectiveness of our method compared to existing query methods.
In terms of comparing our method to IRD, the main point of comparison would be a number of violated expectations (after all IRD doesn't support querying). Table how, in almost all the cases, IRD generated policies that resulted in expectation violations. On the other hand, our method guarantees policies that will never result in violation user policies. While IRD fast, please keep in mind that avoided the expensive inference process of the original IRD with direct access to S and & (reported times don't 't include the calculation of these sets).
Conclusion
This paper introduces a novel paradigm for studying and developing approaches to handle reward misspecification problems. The eypectation-aaiiimmnt framework takes the explicit stand that any reward function a user provides is their attempt to drive the agent to generate behaviors that meet some underlying expectations. We formalize this intuition explicitly define reward misspecification, and we then use this framework to develop an algorithm to generate behavior in the presence of reward misspecification. We empirically demonstrate how our method provides significant advantage over similar methods to handle this reward misspecification in standard MDP planning benchmarks. Limitations. One aspect of reward misspecification we haven' 't discussed here is the one caused by human errors during transcription or communication of the reward function (say, bugs in the reward function code). As previous works have shown (Booth et 2023 reward misspecification is quite frequent in practice, even in the absence of such errors. This paper also focuses on settings where the models and planning functions are known upfront. We believe our method sets up solid formal framework that can be used as basis to develop future RL methods that could relax these assumptions. The paper also only instantiates a specific form of expectation set. More work needs to be done identify when different forms of expectation may be appropriate. Not only could different forms of expectation set be more intuitive or natural for different settings, but might also impact how effectively the user can be queried.
10

---

Acknowledgments and Disclosure of Funding
Sarath Sreedharan's research supported in part by grant NSF 2303019. This material is based part upon work supported by Other Transaction award HR001 12490377 from the U.S. Defense Advanced Research Projects Agency (DARPA) Friction for Accountability Conversational Transactions (FACT) program. Approved for public release, distribution unlimited.
References
P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning, In Proceedings of the Twenty-Firss International Conference on Machine Learning. ICML '04, page 1, New York, NY, USA, 2004. Association for Computing Machinery, ISBN 1581 138385. doi: 10.1145/1015330. 1015430. URL httpp:://ti...ooo 10, 1145/101113330 1015430
D. Abel. simple_rl: Reproducible reinforcement learning in python. RML@ ICLR, 2019.
D. Abel, W. Dabney, A. Harutyunyan, M. K. Ho, M. Littman, D. Precup, and S. Singh. On the expressivity of markov reward. Advances in Neural Information Processing Systems, 34:7799- 7812, 2021.
I. A. Apperly and S. A. Butterfill. Do humans have two systems to track beliefs and belief-like states? Psychological review, 116(4))953, 2009.
B. D. Argall, S. Chernova, M. Veloso, and B. Browning. A survey of robot learning from demonstra- tion. Robotics and autonomous systems, 57(5):469-44) 483. 2009.
Arora and P. Doshi. survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021.
C. Blicklú, ú, P. Bonami, and A. Lodi. Solving mixed-integer quadratic programming problems with ibm-cplex: a progress report. Proceedings of the twenty-sixth RAMP symposium, pages 16-17, 2014.
S. Booth, W. B. Knox, J. Shah, S. Nickum, P. Stone, and A. Allievi. The perils of trial-and-error reward design: misdesign through overfitting and invalid task specifications. In Proceedings of the AAAI Conference Artificial Intelligence, volume 37, pages 5920-59299 2023.
C. Boutilier. A pomdp formulation of preference elicitation problems. AAAI/AAAI, pages 239-246. Edmonton, AB, 2002.
I.. Chen and P. Pu. Survey of preference elicitation methods. Technical report, Ecole Politechnique Federale de Lausanne (EPFL.), 2004.
A. Dafoe, E. Hughes, Y. Bachrach, T. Collins, K. R. McKee, J. Z. Leibo, K. Larson, and T. Graepel. Open problems in cooperative ai, 2020.
Z. Gong and Y. Zhang. What you really want of me? generalized reward learning with biased beliefs about domain dynamics. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 2485-2492, 2020.
D. Medeilld-ennlll, learning. CoRR, Abs/1606.03137, 2016. URL httt://arxivv org/ http:/as//666.003/00
Dragan, Abbeel, and S. Russell, Cooperative inverse reinforcement
D. Hadficld-Menell, S. Milli, P. Abbeel, S. Russell, and A. D. Dragan. Inverse reward design. CoRR, abs/1711.02888 2017. URL http::/:://axiii wwgp/aaww.......aaaooooooa 122207100211
H. J. Jeon, S. Milli, and A. D. Dragan. Reward-rational (implicit) choice: A unifying formalism for reward learning. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, pages 4415-4426, Virtual, 2020. Curran Associates, Inc
D. Kahneman and A. Tversky. The simulation heuristic. National Technical Information Service, 1981.

---

T. Q. Klassen, S. A. Mcllraith, C. Muise, and J. Xu. Planning to avoid side effects. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9);9830-96)) 9839, Jun. 2022a. doi: 10.1609/aaai v3619.21219. URt.ttps::///
aaai. http://ww../////AAaarrraaaaa///a
T. Q. Klassen, S. A. Mcllraith, C. Muise, and J. Xu. Planning to avoid side effects. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 9830-9831 2022b.
T. Q. Klassen, A. Alamdari, and S. A. Mcllraith. Epistemic side effects: An ai safety problem. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, pages 1797-1801, 2023.
D. Krasheninnikov, R. Shah, and H. van Hoof. Combining reward information from multiple sources. CoRR, 1bb/22103.1214,, 2021. URL.httss httphtttt////i...ooo/. org. att/aabb.//111///1 12142
S. Mahmud, S. Saisubramanian, and S. Zilberstein. Explanation-guiiee reward alignment. In
E. Elkind, editor, Proceedings of the Thirty- International Joint Conference Artificial Intelligence, IJCAI-23, pages 473-482. International Joint Conferences on Artificial Intelligence Organization, 8 2023a. doi: 00224963/jcaai22223555 Main Track.
htt.tttts///oi..ooo www...////.....3/.1.. 24963/1jcai
2023/53
S. Mahmud, S. Saisubramanian, and S. Zilberstein. Explanation-guide reward alignment. In Proceedings of the Shirdy-Seood International Joint Conference Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China, pages 473-482. ijcai.org. 2023b.
M. Mechergui and S. Sreedharan. Goal alignment: A numan-aware account of value alignment problem, 2023.
S. Milli, D. Hadfield-Mennn A. D. Dragan, and S. Russell. Should robots be obedient? In C. Sierra, editor, Proceedings of the Twenty- Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pages 4754-4760, ijcai.org, 2017.
A. Pan, K. Bhatia, and J. Steinhardt. The effects of reward misspecification: Mapping and mitigat- ing misaligned models. CoRR, 0t///2011033444 2022. URL htt.tttss/aa.iv.orr/////o// 03544
P. Poupart. Exploiting structure to efficiently solve large scale partially observable Markov decision processes. Citeseer, 2005.
M. L. Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
S. Reddy, A. Dragan, and S. Levine. Where do you think you're going?: Inferring beliefs about dynamics from behavior. Advances in Neural Information Processing Systems, 31, 2018
S. Saisubramanian. Zilberstein, and E. Kamar. Avoiding negative side effects due to incomplete knowledge of ai systems. Al Magazine, 42(4):62-71, 2022.
H. A. Simon. The logic of heuristic decision making. In Models of discovery, pages 154-175. Springer, New York, 1977.
J. Skalse and A. Abate. Misspecification in inverse reinforcement learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 15136-15143, 2023.
Sreedharan. Foundations of Human-Aware Explanations for Sequential Decision-Making Problems. PhD thesis, Arizona State University, 2022.
A. Srivastava, S. Saisubramanian, P. Paruchuri, A. Kumar, and S. Zilberstein. Planning and learning for non-markovian negative side effects using finite state controllers. In Thirty-Sevnnth AAAI Con- ference Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pages 15144-15151, AAAI Press, 2023.
Innovative Applications
R. Sutton, Precup, and Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):11-211. 1999.
12

---

F. Torabi, G. Warnell, and P. Stone. Recent advances in imitation learning from observation, arXiv preprint arXiv:1905.13566 2019.
A. Tversky and D. Kahneman. Extensional versus intuitive reasoning: The conjunction fallacy in probability judgment, Psychological review, 90(4):293, 1983.
Vamplew, C. Foale, R. Dazeley, and A. Bignold. dntential-based multiobjective reinforcement learning approaches to low-impact agents for safety. Engineering Applications of Artificial Intel- ligence, 100:1041880 86, 2021. ISSN 0952-1976. doi: http:://ooooggg//...oooo./.gggap 1041186. URL httph:/t////// www. wttpaaaaaaaatttooooooooaaaaaaaaa htt.a//cccc...t.....a...oooo///a
D. Weld and O. Etzioni. The first law of robotics (a call to arms). In Proceedings of the Twelfth AAAI National Conference on Artificial Intelligence, AAAI'4, page 1042-1047. AAAI Press, 1994.
W. Yoon, A. Fern, R. Givan, and S. Kambhampati. Probabilistic planning via determinization in hindsight. In AAAI, pages 1010-1016, 2008
S. Zhang, E. H. Durfee, and S. Singh. Minimax-regge regret querying side effects for safe optimality in factored markov decision processes. In Proceedings of the Twenty-Seventh International Joint Conference Artificial Intelligence, IJCAI-18, pages 4867-4873. International Joint Conferences
on Artificial Intelligence Organization, 2018. doi: 00.24963/jeaii201180 URL https
o0o01.0 24963/126ee ijcai.cccaaiaiaa..i 2018/676
13

---

8 Appendix / supplemental material
8.1 Proof Sketch for Propositions
Proposition 1. There exists no state s e S and policy π E MM such that x= ==((s= >> 0 is true.
Proof Sketch. We will prove this through contradiction. Let's assume that there exists state 8 S where x" (s) > 0 for an optimal policy и E II for a human specified reward function R Per Definition reward function only specified, i.e., they are human-sufficient if, for every policy in π E pd ( (D4 R2), you have FDD 9, for all e E E If s E S then (18).= :). Per our assumptions, P returns the of optimal policies, hence π E pp ((D# R#)), This means that FD" 9, which is only true if x= (s) = 0. This contradicts our initial assertion, hence proving our statement by contradiction.
Proposition 2. For every state s 8 and policy MM x² (s) must always be true.
Proof Sketch. We can prove this through contradiction by following a rationale similar the earlier proposition. We will again leverage the intuition that for a reward function to be human-sufficien, all optimal policies must satisfy all specified expectations, which include visiting states in 59. As such, if a state is not visited by an optimal policy, it cannot be part of the set $
O
Proposition 3. For the LP described in Equation 2 if E S then for the optimal value x² identified for the LP,, the condition E. x² (8i, a) must hold.
Proof Sketch. In the equation the constraint Σs, x(s, a) x r((s = V ensures that the identified occupancy frequency corresponds to an optimal policy. The LP is trying to maximize the objective function. Since the first term of the objective function max, E.,a 2(s, a) x xr(s, a) corresponds to the value of the policy, it must be equal for all optimal policies. As such, the solver will try to identify occupancy frequencies that try to maximize the occupancy frequency for visiting &,. In other words, it will try to find optimal policies that visit the state. However, per Proposition no states in S are ever visited by an optimal policy. This means if the LP finds a solution with non-zero occupancy frequency for the state s; it cannot be part of S
Proposition 4. For the LP described in Equation if s, E S9, then there must exist no solution for the given LP.
Proof Sketch. The proof closely resembles the one provided for the earlier proposition. The constraint E.a 2(s, a) r(s,a) a) V*, forces the LP solver only consider occupancy frequencies for optimal policies. The new constraint Σ. ((5 a) 0, forces the LP to find optimal policies where the state not visited. in fact such a policy is found, per Proposition the state cannot be part of 8
8.2 Noisy Rational Model
It is well known that humans are better approximated as bounded rational agent, as opposed to rational agents. As such, except in the simplest scenarios, human users may not be able to identify the optimal decision. A popular model for approximating human aecisionnmakingg is to use the noisy rational model JJon et al. 2022). Under this approach, the likelihood of the human choosing a policy is given as
p(T) e (so)
Where V (sp) corresponds to the value associated with state Su under policy x. For any non-zero value, the user more likely to select policies with higher values. However, even non-optimal policies have a probability of getting picked. Additionally, as the value of B3 reduces, the likelihood of a non-optimal policy being selected increases, with 3 = 0 corresponding to a case where the user selects the policy completely randomly. As such, 33 is sometimes referred to as the rationality parameter.
For a non-zero 3 value, let VP. be the value for which the noisy rational model assigns a probability of at least p; of being picked. Now, let us consider case where want to extend our formulation to support planning function where the human could pick some policy with a probability greater than pi- In this case, we only need to update the LP to calculate the supersets. However, here S consists
14

---

of all states avoided by at least one policy and So consists of every state visited by at least one policy,
The corresponding LP formulation for S become
max
Σ
x(ss x r(s,a)
8,0
S.L. A& E S, Σ x(s,0) = 8(s, +7x Σ
a(''a' T (s', ,'',
(6)
s'
Σ x()0. x r(s,a)
V
Σ x((i,a) = 0
state belongs to S the above LP is solvable for given state.
x(s x (.a,))x(ssa))a E x(()),))
max
8,0
s.t. SA S. Σ x(s,0) = 6(s, 80)
x(s' x T (s,d's))
2(50 x r(s V
A state belongs to $9 if the above LP is solvable for given state.
As you can see, basically for this new planning function, we only need to swap the LP formulations, change the cost requirement to a looser one, and then check for solvability instead of unsolvability. Since we still get supersets, we can still use the pseudocode provided earlier.
9 Broader Impact
We see the problems and challenges being discussed here as being core to the aim of developing effective Al systems that can interact and work with people. We believe that as Al systems become more powerful, it is important that we have measures to detect possible misspecifications of rewards and objectives. The problems discussed here are also related to the problem of value alignment. However, goal is only to develop methods ensure AI system behavior aligns with expectations/intetiios.. We are not in any way assigning whether or not user behaviors align with larger societal values. We believe this is an orthogonal problem, which would still benefit from the methods we develop.
15

---

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:
We have a bulleted list in the introduction showing our contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have a limitations section under conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on 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 images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 set of assumptions and complete (and correct) proof?
Answer: [Yes]
16

---

All assumptions made are clearly mentioned, and all equations, definitions, theorems and propositions are numbered. All theorems have a proof sketch provided Guidelines:
Justification:
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 referenced in the statement of any theorems.
The proofs 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 short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix 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 the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide detailed discussion of the experiment setup, along with the solvers used, in the paper. We have also included the code with instructions on how to run it. All LP formulations are specified, and we also provide pseudocode for the overall algorithm the appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not 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 a dataset and/or model, the authors should describe the steps taken make their results reproducible 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 a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to 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 NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If 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- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
17

---

reproducible, they 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: [Yes]
Justification:
We have included a zip the code along with instructions. There was no
dataset.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/nips. wttpcc/pcccccccccccooooooop httee/ggguudes/oeeeuuubbiiiiiiii sereiisssooPoooi
for more details.
The authors should provide instructions on data access and preparation, including how 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. If only subset of experiments 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 supplemental material (appended to the paper) is recommended, but including URLs to data and code is 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: [Yes]
Justification: We have specified the solver used. Given these are just using LP formulations of MDPs didn't have any hyperparameters to select.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have included the average and standard deviation calculated for five randomly generated instances of each problem size.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
18

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is 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 of 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: [Yes]
Justification:
We have provided the information on the computational resources used.,
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU 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 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 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
We have reviewed the guidelines and ensured our submission meets
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We have include a broader impact section in the appendix.
Guidelines:
The answer NA means that there 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.
19

---

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 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 a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e-g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our method is merely way to avoid reward misspecification, and as such the safeguards are not relevant.
Guidelines:
The answer NA means that the paper poses 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
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?
Question:
Answer: [Yes]
Justification: All baselines used are properly cited. We wrote all the codes included, and they will be released with an open-source license. The only licensed component we use is CPLEX, which cited in the paper, and we use the no-cost edition.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
20

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
batasets.papersstt
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented, and is the documentation provided alongside the assets?
Answer: [NA]
Justification: There assets except the code ran for the experiments, which included along with the documentation.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/model as part of 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 is 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 the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No user studies performed
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No user studies were performed.
Guidelines:
The answer NA means that the paper does 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.
21

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere 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.
22


Reviews:
[{"review_id": "Bn5zTxYiYF", "reviewer": "Reviewer_RJbh", "summary": "The paper tackles the problem of reward misspecification in settings where humans have potentially incorrect beliefs about the environment. Instead of treating a true human reward function as the fundamental object, they introduce *expectation sets*, which specify the states that the human does or doesn't expect an optimal policy to visit. In a specialized setting where preferences consist purely of goal states and forbidden states, they then show how to find policies that meet those human expectations.", "questions": "Is there a clear reason to expect expectation sets to transfer better than reward functions between domains? In particular, why don't they face similar problems along the lines I mention above? i.e.:\n> the human might expect the optimal policy to spend time in some actually suboptimal state simply because they incorrectly believe this is necessary to reach the goal state\n\n\nAs a minor note, in definition 3, should the planning function map to the *powerset* of the space of policies? That seems to be how it's used in definition 4, where the planning function evaluated on a single model is a *set* of policies rather than a single policy.", "limitations": "The method assumes knowledge of a way to map between states in the human and robot model, as well as knowledge about the full human and robot models. These assumptions are made in other existing work as well, so are not a damning issue. But they still seem worth highlighting given how limiting they are for many applications.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Reward misspecification is an important topic, and this paper provides an interesting new perspective on it\n- The ideas are clearly described and mostly easy to follow\n- The expectation alignment framework/technique could be useful at least in certain settings", "weaknesses": "- I don't think the paper sufficiently demonstrates that the expectation alignment perspective is broadly better than thinking about an (unknown) true human reward function. Starting at line 203, the paper argues that expectation sets transfer better to different transition functions than reward functions do. This doesn't seem true in full generality: for both reward functions and expectation sets, we could assume that they express the true human preferences about states (in which case they'd transfer), or that they are entangled with the transition function. The latter could also be the case for expectation sets; for example, the human might expect the optimal policy to spend time in some actually suboptimal state simply because they incorrectly believe this is necessary to reach the goal state.\n- The setting for which the paper describes an algorithm is quite limited (with only \"goal states\" that should be reached with non-zero probability, and forbidden states that should be reached with zero probability).\n- It's hard to draw clear conclusions from the experiments:\n\t- The experiments measure the number of human expectations that inverse reward design violates, and compare that to the guarantee of expectation alignment not to violate any expectations. But of course, expectation alignment was directly designed for that purpose, whereas IRD was not—from the IRD perspective, the relevant thing to compare would be the reward achieved under the expected reward function that IRD's inputs are based on.\n\t- It would also be nice to have experiments in larger and more varied environments than just 11x11 gridworlds.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the feedback. We will make sure to incorporate them into the paper. Below, we have provided responses to some specific concerns and questions raised in the review.\n\nTransference: We want to thank the reviewer for all their constructive comments. In regards to the question of transferability, our main argument is built on the fact that the expectation set constitutes the behavior they want to see the robot perform. As such, instead of the question of transference, it becomes one of whether or not the AI agent/robot can achieve the desired/expected behavior. Which our method can determine. Our claim is further supported by the abundance of evidence from cognitive science and psychology (cf. [Simon,1977]), which shows that people inherently reason about tasks and plans in terms of goals of achievement. As discussed in the paper, the expectation set, as formulated in the paper, is a generalization of goals. On the other hand, we are unaware of any evidence that shows people have intrinsic reward functions associated with tasks. Some works show that even experts struggle to design reward functions (cf. [Booth et al., 2023]). As such, the use of reward functions becomes a means to the end of specifying the behavior they want to see. However, the reviewer is correct in asserting that users might not be fully aware of what is achievable in the environment (because of knowledge or inferential limitations). In such cases, we would argue that the system should use other mechanisms like explanation to inform the user what is possible rather than determining what they should want. We will make sure to update the text to make sure that this point is clearly articulated.\n\nSpecific Instance: As mentioned, our choice of specific instance was motivated by the importance of goals in human reasoning, per existing literature, and all the AI-safety works that have focused on avoiding side effects. Our current method captures both these considerations.\n\nExperiments: We chose to highlight IRD as one of the baselines because they center rewards and overlook the fact that the reward is an expression of some true underlying behavioral expectations. For the user, the reward itself is a means of achieving some behavior, and in the case we consider, where there are states to be avoided and achieved, violating them would render the policy useless. It is also worth noting that while, in the end, IRD settles for the use of an expected value, they do use behavior generated by a reward function as the means to identify potential hypotheses for true reward function. It is also worth noting that IRD was not the only baseline. We also used a query-based baseline. Unfortunately, it could not solve any of the problems we considered in the given time limit. As such, it was left out of the table, but we mentioned it in the text. This highlights the efficiency of our method and the advantages provided by considering the human model and planning set. Regarding scalability in non-grid environments, as mentioned in the main response, the primary method we can leverage is to use a feature-based representation. This representation scheme allows us to capture large state sets using a small set of features. This was briefly alluded to in the discussion about rewards. We also talk about how a large number of current work in avoiding negative side-effects already makes use of features. The occupancy frequency can easily be extended to capture the occupancy frequency of features, and the expectation set can be captured in terms of those. Here, the expectation set will consist of features to be achieved and avoided. In turn, we can update the LP formulations to use features, and constraints are represented using feature occupancy frequency. The queries will also be in terms of the features, which should keep the total number of queries fairly small. This should allow our methods to be scaled more easily. The availability of powerful and efficient LP solvers also makes our methods inherently more scalable.\n\nPowerset Defn3: Yes, this was a typo. We will fix it in the final draft.\n\nLimitation: We agree about the access to the mapping, but works exist that provide methods for learning such mappings.", "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": "3YJq28Bcmh", "reviewer": "Reviewer_pegd", "summary": "The paper addresses the problem of reward misspecification. It introduces a framework (EAL) to capture how humans go from setting expectations about a problem to specifying the reward for it. The problem is modeled as a single Human-Robot interaction. \nAfter introducing the formalism, the authors propose an algorithm to solve the EAL problem. It works by mapping the inference problem about the user expectations to LPs and by obtaining queries to the human, providing an efficient and effective way of inferring user expectations given a specified reward.", "questions": "- Do you have any formal proof ( to put in the Appendix) both for the Theorems and the Propositions? Even if most of the results and proof are pretty straightforward, I would still like to see the proofs formally written out\n- Could you please clarify how one should read the results from Table 1? I do not directly see how to relate query count and No of Violated Expectations. If the comparison is 1 to 1, it seems your algorithm is actually performing sub-optimally? \n- How do you think your algorithm can scale in non-grid environments? What about grid environments with a computationally untractable number of states? I imagine obtaining good results would require a too-high number of queries.", "limitations": "No ethical limitations", "rating": 7, "confidence": 3, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "- The paper is extremely well written. It introduces previous concepts clearly. The motivations for choices in the formalism introduced are also well-justified and adequately compared with the previous literature on the topic\n- The theoretical contributions are very solid and sound. \n- The formulation via occupancy measures and LP simplifies the problem significantly in my opinion, making it easy to understand why and how the algorithm is derived.", "weaknesses": "- The main weakness I find is the limited experimental evaluation. I understand that the contributions of this work are mainly theoretical, but I still think it would benefit from additional experiments", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the comments. We will make sure to incorporate them into the paper. Below, we have provided responses to some specific concerns and questions raised in the review.\n\nFormal Proof: We will be more than happy to include detailed formal proof for all the propositions and theorems. Since the allowed pdf isn’t supposed to include text, we are including a proof sketch here for proposition 1 as a sample proof.\n\nProposition 1 -   There exists no state $s \\in \\mathcal{S}^\\mathcal{F}$ and policy $\\pi  \\in \\Pi^*_{\\mathcal{M}^H}$, such that $x^\\pi(s) > 0$ is true.\n\nProof Sketch - \nWe will prove this through contradiction. Let's assume that there exists a state $s \\in \\mathcal{S}^\\mathcal{F}$, where $x^\\pi(s) > 0$ for an optimal policy $\\pi \\in \\Pi^*_{\\mathcal{M}^H}$ for a human specified reward function $\\mathcal{R}^H$. Per Definition 4, a reward function is only specified, i.e., they are human-sufficient, if for every policy $\\pi \\in \\mathcal{P}^H(\\langle \\mathcal{D}^H, \\mathcal{R}\\rangle)$, you have $e \\models_{\\mathcal{D}^H} \\pi$, for all $e \\in \\mathbb{E}^H$. If $s \\in \\mathcal{S}^\\mathcal{F}$, then $e = \\langle \\{s\\},=,0\\rangle$. Per our assumptions, $\\mathcal{P}$ returns the set of optimal policies, hence $\\pi \\in \\mathcal{P}^H(\\langle \\mathcal{D}^H, \\mathcal{R}^H\\rangle)$. This means that $e \\models_{\\mathcal{D}^H} \\pi$, which is only true if $x^\\pi(s) = 0$. This contradicts our initial assertion, hence proving our statement by contradiction.\n\nWe will include detailed proofs for all the theoretical assertions in the final draft.\n\nExperiments: \n\nAs mentioned in our response to other reviewers and the main rebuttal, our paper included two baselines. One of these was another query method, which unfortunately couldn’t solve any of the problems within the given time limit, showing the scalability of our method.\n\nTable1: Please note that the violations listed by the policy identified by IRD are not the whole set of constraints, even though the reward tried to penalize potential unsafe states and reward potential goal states. These constraints are upper bound by the actual number of constraints that were present in the instances, which is always much smaller than the total number of states. On the other hand, the query method could query about a number of states that are not actual constraint states. For the queries, the worst-case upper bound is the set of all states. This again points to some of the challenges faced by previous query methods. It is also worth noting that in safety-critical settings, even violating a single constraint could be bad. So, instead of the number of violations, the bigger problem is that it violates any constraints at all.\n\nNon gridworld domains: As discussed in the main rebuttal text, we can handle domains with large state space using feature-based representations, which are already popular in the safety literature and planning in general. Here, there would be a set of features that characterize the goal states and another set that captures the states to be avoided. A feature set can capture an exponential number of states. Here, the algorithm changes will be minimal, and instead of querying over the states, we will query over features, which will keep the query count small.", "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": "M9d4dTCcgi", "reviewer": "Reviewer_ahA3", "summary": "This paper studies the process of reward design and as a result reward misspecification when a human designer has potentially misspecified beliefs about the robot's operating domain or generally trouble with designing a reward leading to the robot generating desired behavior in its own domain. The paper formalizes the notion of \"expectation alignment\" over occupancy frequency under human and robot domains satisfying a set of desired or forbidden states. Since the human's expectation set is unknown, the authors propose a set of linear programs 1) to test whether a state belongs to the forbidden set, 2) to test whether a state belongs to the goal set, and 3) to find a minimal set of queryable states by minimizing the number of states in the forbidden and goal sets which can be used to query a human designer. The proposed method is mainly compared against inverse reward design.", "questions": "I have some minor questions on LP formulation and notation:\n* In eq 2 and 3, is the notation $V_{s_0}^*$ the optimal value function in $(D^{H}, R^{H})$ (since the authors only said calculate $V_{s_0}^*$ but did not say what is being calculated)? If so then I doubt that notation $\\sum_{a}x(s_{0}, a) = V_{s_0}^*$ is correct in general, since $x(s, a) \\in [0, 1]$ is the visitation frequency $\\frac{1}{H}\\mathbb{E}[\\sum_{H}Pr(s_t=s, a_t=a)]$ rather than a value function. \n* In all LP equations, there seem to be a typo on the transition matrix, i.e, it should probably be: $\\sum_{a}x(s, a) = \\delta(s, s_0) + \\gamma\\sum_{s', a'}x(s', a')T(s', a', s)$. See [Sikchi et al, 2024](https://arxiv.org/abs/2302.08560) eq 4.\n* For the LPs in eq 2 and 3, do you have to solve it for every $s_i$ being tested? This seems expensive?\n* In line 249, there seems to be a typo. I guess the authors are trying to say: \"calculate the set of all **forbidden** states reachable\" and \"calculate the set of all **goal** states reachable\".", "limitations": "Acknowledgement of limitations seem appropriate.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Originality & significance**: This work is original to my knowledge and the proposed method of tackling reward design and specification from the perspective of occupancy measure is novel and interesting. Given the increasing popularity and maturity of dual RL, the propose method has the potential to be extended to more practical settings. \n\n**Quality & clarity**: The paper is well written. Even though the problem studied is novel and somewhat \"niche\", the authors did a good job walking the readers through a lengthy problem formulation. I appreciate the thoughts that went into this problem formulation.", "weaknesses": "**Clarity**: I think the authors could provide more context (in main text or appendix) on inverse reward design (IRD) for readers to better understand and interpret the evaluation results. Currently, readers have to read the IRD paper to achieve that. \n\nThe authors claim that \"IRD generated policies that resulted in expectation violations. On the other hand, our method guarantees policies that will never result in violation of user policies\". As far as I understand, IRD proposes a model of how human specified reward relates to the true intended reward. In contrast to IRD which is a one-off process (one-shot learning if you will) where the human designer is queried only once and then the robot is deployed in the test environment, the proposed method is iterative where the human can potentially provide multiple feedback to the designed reward. In some sense, this is equivalent to assuming privileged access the test environment and the number of states in $\\mathbb{D}_{F}$ after the first human query is in some sense similar to the number of violated expectations. So stating that the proposed method never violates user policies doesn't seem appropriate, or at least comparing with IRD on this metric doesn't seem to be \"comparing apples to apples\".\n\n\nAnother minor suggestion is to put equation numbers in corresponding lines in the algorithm to make it easier for readers to understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the constructive feedback and for catching the typos. We will incorporate them into the final draft. Below, we have provided responses to specific questions and comments raised.\n\nIRD: We will make sure to provide a more clear description of IRD in the evaluation section. The reviewer is right in the fact that the method isn’t explicitly designed to avoid constraint violation. However, we believe that this also comes from the stance that the paper takes that there exists a single true reward function that is transferable across domains. We believe that if it had been accounted for, the authors would have included a querying strategy. We realize that this might not always be a fair comparison, and this is the reason why we also compared it with a method that explicitly performs queries. As we can see, that method cannot scale up to the problems we considered in this paper.\n\n$V^*_{s_0} $ and constraint: Thank you so much for catching it. This was an unfortunate typo that got copied around in the LP descriptions in the paper. The constraint should have read $\\sum_{s,a} x(s,a)r(s) = V^*_{s_0}$. Note that $\\sum_{s,a} x(s,a) r(s)$ returns the value of the state $s_0$ for the current policy (cf. [Poupart, 2005]). We will make sure to fix it in the final draft.\n\nTransition Function: We believe our formulation is correct in this case. Looking at the other paper, we believe the difference comes from how they represent the transition function. They seem to be using a conditional probability notational scheme, where they represent the probability of transition to a state s’ when action a is executed in state s as P(s’|s, a). We, on the other hand, use a simpler functional notation of the form $T: S \\times A \\times S \\rightarrow [0,1]$. In our case, the same probability will be returned by the arguments T(s, a, s’). We hope this clears the confusion, and we will make sure to emphasize this in the background section where we define our notations.\n\nQueries: The reviewer is correct in that we have to check it against every state. However, as discussed in the main rebuttal response, as we move to larger problem settings, we expect to use factored/feature-based representations. These allow for a relatively small set of features to represent large state spaces. Under these scenarios, the tests only need to be run once per each feature. This would dramatically cut down on the number of times it needs to be run. Standard planning benchmarks use relatively small feature counts[ext1], which number less than a hundred.\n\nLines 248-249: This was again a typo. $\\widehat{\\mathcal{S}}^\\mathcal{F}$ corresponds to states that are not reachable under any optimal policy. We will make sure to fix it in the final draft.\n\n[ext1] International Planning Competition, IPC Competition Domains. https://goo.gl/i35bxc, 2011.", "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:
We thank the reviewer for all the comments and feedback. We are extremely happy that the reviewers found our paper well-written, novel, interesting, and useful. We will make sure to incorporate all suggestions, recommendations, and corrections. We have tried to provide specific answers to each reviewer. However, we wanted to take this global response to address some common points brought about by multiple reviewers. Please note that all citations that don’t start with the ‘ext’ prefix refer to citations from the paper.

Experiments: We want to emphasize that we evaluated against two methods in the experiments. The IRD method tries to find a single reward function, and the MMRQ-k tries to query the user to identify potential constraints. It is worth noting that the baseline query method we used failed to solve a single problem in the fairly generous time limit of 30 minutes we set (the worst-case average time for our method was 224.98 secs). Our choice of IRD was motivated by the fact that it is a prototype of a work that tries to make the case for a single true reward function. Even when it tries to find potential alternate reward function hypotheses that account for the behavior, it will fail to generate violation-free behavior as it doesn’t directly query the user about their expectations. At the same time, MMRQ-k results show how poorly the current query methods scale and the utility of leveraging information about the user's mental model.

Moving Beyond Grid-based Domains: The most direct way to move beyond such problems would be to adopt factored or feature-based representations [ext1]. Such representation schemes are typical in reinforcement learning and inverse reinforcement learning works [ext2]. They are also quite popular in AI-safety works (cf. [Zhang et al. 2018],[Saisubramanian et al. 2022], [Mahmud et al. 2023b]). Feature-based representations allow us to provide compact representations of extremely large state spaces. For example, a set of $k$ binary features can encode $2^k$ states. Under this scheme, the goal states and forbidden states would be identified by a set of features, and any state where those features are true is, in fact, considered a goal or forbidden state. Our formulation can be easily extended to a feature-based representation because one could calculate a feature-based occupancy frequency can be calculated by marginalizing across other features. As such, all the constraints and penalties considered in the various LP formulations can still be applied in this case. More interestingly, many aspects of our methods will be simplified by the use of a feature-based representation. For most standard planning problems, the number of features considered is much smaller than the largest state space considered here. This reduces the number of possible queries (because queries are done once per feature) and the number of tests we need to perform to identify potential forbidden state and goal state candidates (again done only once per feature). 

[ext1] Brafman, Ronen I., and Carmel Domshlak. "Factored planning: How, when, and when not." AAAI. Vol. 6. 2006.

[ext2] Ng, Andrew Y., and Stuart Russell. "Algorithms for inverse reinforcement learning." Icml. Vol. 1. No. 2. 2000.

The attached PDF includes a table listing the number of constraints per problem instance. The IRD's violations should be compared against this number.

Meta-review: This paper proposes a new framework for inferring human rewards, based on reasoning about sets. The paper provides theoretical guarantees for the proposed approach, and limited evaluation on gridworlds. The reviewers assigned scores of 7/7/5. Reviewers found the paper novel and very well written. Reviewers raised some conceptual questions that were addressed during the rebuttal. The reviewers also raised concerns about limited experimental evaluation, which were not addressed in the rebuttal; during the reviewer discussion Reviewer ahA3 (the reviewer who assigned the paper the lowest score) said that the new “perspective” on preferences would be “valuable to the community,” believing that the “experiments can improve over time.”  Taking this all into account, I recommend that the paper be accepted.
Decision: Accept (poster)