Expectation Alignment: Handling Reward Misspecification in the Presence of Expectation Mismatch

Authors: malek  mechergui
sarath  sreedharan
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-02 15:56:24

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.

Main paper: 
 introduction: 
 Given the accelerating pace of advancement within AI, creating agents that can detect and handle incorrectly specified objectives has become an evermore pressing problem [Dafoe et al., 2020] . This has resulted in the development of several methods for addressing, among other forms of objective functions, misspecified rewards (cf. Hadfield-Menell et al. [2017] ). Unfortunately, these works operate under an implicit definition of what constitutes an incorrectly specified reward function. The few works that have tried to formalize how an agent could satisfy human objectives do so by avoiding the objective specification step altogether [Hadfield-Menell et al., 2016] .Our primary objective with this paper is to start with an explicit formalization of what constitutes a misspecified reward function and the potential reasons why the user may have provided one in the first place. However, our motivation for providing such a 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., 2021] ) that looks at reward functions as a means of specifying a task as opposed to being an end to itself. As such, the user starts with a target outcome or behavior or a set of outcomes or behaviors 1 that they want the agent to achieve. The reward function proposed by the user is one whose maximization, they believe, will result in a 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 Butterfill, 2009] about the agent) and their ability to reason about how the agent will act given a specific reward function.Figure 1 : A diagrammatic overview of how specifying a reward function plays a role in whether or not their expectations are met.A given reward function is said to be misspecified when the policy identified by the agent for the reward function doesn't satisfy the user's expectations. As discussed, the reasons for such misspecification could include users' incorrect beliefs about the agent and their limited inferential capabilities [Sreedharan, 2022] . To see how such misspecification might occur, consider a 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 corresponds to an unsafe one. Let's consider a human supervisor who wants the agent to go to 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 a reward function that will result in the exact opposite outcome. Please note that the problem here isn'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 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.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 to 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 a '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 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 a 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. 
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, T, R, γ, s 0 ⟩2 . Under this notation scheme, S captures the set of states, A the set of actions, T :S × A × S → [0, 1]is the transition function such that T (s, a, s ′ ) captures the probability of an action a causing the state to transition from s to s ′ , R : S × A → R is the reward function, γ ∈ [0, 1) the discount factor and finally s 0 ∈ S is the initial state (the agent is expected to start from s 0 ). Since we are focusing on 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 = ⟨S, A, T, γ, s 0 ⟩.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 → R). A policy is considered optimal (optimal policies will be denoted with the superscript ' * ', for example, π * ) if it results in the highest value (referred to as the optimal value V * ). It is worth noting that an optimal policy is not unique, and for a 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 Π * M . In this paper, we will be heavily utilizing the notion of discounted occupancy frequency or just occupancy frequency, x π : S × A → [0, 1] [Poupart, 2005] , associated with a 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 a policy π. In particular, the occupation frequency x π (s, a) captures the frequency with which an action a would be executed in a state s under the policy π. Sometimes, we will also need to 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., x π (s) = a x π (s, a). 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 x s,ax(s, a) × r(s, a)EQUATIONHere, x is the set of variables that captures the occupancy frequency possible under a policy, and δ(s, s 0 ) is an indicator function that returns 1 when s = s 0 and zero otherwise.In this paper, we will be looking at settings where the human's (i.e. the user who is coming up with the reward function) understanding of the task may differ from that of the robot3 . 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 R = ⟨S, A R , T R , γ R , s 0 ⟩ to denote the domain used by the robot, while D H = ⟨S, A H , T H , γ H , s 0 ⟩ is a 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 a framework to understand how humans go from expectations to reward specifications, which we will use to define reward misspecification. With the basic model in place, we can effectively invert it to develop methods to address such misspecification.To build such a forward model, we need a 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 to intermediate ones. It even allows us to express probabilistic notions of reachability. Secondly, occupancy frequencies present a very general notion of problems that can be expressed as MDPs. As discussed in Section 2, 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 H , which provides a set of states and any preferences placed on reachability for that state. More formally, Definition 1. Given human's understanding of the task domain D H = ⟨S, A H , T H , s 0 , γ H ⟩, the human expectation set is denoted as E H , where each element e in the set is given by the tuple of the form e = ⟨S e , O, k⟩, where S e ⊆ S, O ∈ {<, >, ≤, ≥, =} is a relational operator and k ∈ [0, 1].O and k places limit on the cumulative occupancy frequency over the set of states S e .For cases where the human wants the robot to completely avoid a particular state s, 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 to 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 to 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 1 merely provides a mathematical formulation that is general enough to capture human expectations. We don'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 a set of states in a 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., 2021] ), which is unsurprising since the expressivity of occupancy frequency parallels that of Markovian reward functions.We will claim that a policy satisfies an expectation element for a domain if the corresponding occupancy frequency relation holds for the policy in that domain, or more formally:Definition 2. A given policy π is said to satisfy an expectation element e = ⟨S e , O, k⟩ for a given domain D, or more concisely e |= D π, if the occupancy frequency for state s (x(s)) under policy π as evaluated for D satisfies the specified relation, i.e., O( s∈Se x π (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 P H , that maps a 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 H : M → 2 Π , where M is the space of possible models and Π the space of possible policies.It is worth noticing that, as with D H , P H is a reflection of the human's belief about the robot's model and planning capabilities. In many cases, humans might ascribe a 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 belief about the task domain D H and an expectation set E H , a reward function R is considered human-sufficient, if for every policy in π ∈ P H (⟨D H , R⟩), you have e |= D H π, for all e ∈ E H .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 capabilities (captured by D H ) 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 (P H (⟨D H , 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 a given policy, especially given the fact that people are known to be notoriously bad at handling probabilities [Tversky and Kahneman, 1983, Kahneman and Tversky, 1981] . 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 a determinized version of the model [Yoon et al., 2008] . Even here, there is a possibility that humans could overlook some paths that might cause the expectation element to be unsatisfied.In general, we will deem a reward function misspecified if at least one robot optimal policy has at least one unsatisfied expectation set element.Definition 5. A human-sufficient reward function R is misspecified with respect to the robot task domain D R and the human expectation set E H , if there exists an e ′ ∈ E H and a policy π that is optimal forM R = ⟨D R , R⟩, such that e ′ ̸ |= D R π.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 H ). 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, D H and D R , and an expectation set E H , such that one can never come up with a human-sufficient reward function R that is not misspecified with respect to D R , even if one allows the human planning function P H 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 a 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 a 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 a policy that satisfies the expectation set. Thus proving the theorem statement.This theorem shows that one can't talk about a 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 [Hadfield-Menell et al., 2017] , which aims to generate a 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 to what the robot's objective should be, namely, to come up with an expectation-aligned policy, i.e., one that satisfies human expectations in the robot task domain, when possible, or recognize when it cannot do so.Definition 6. For a human specified reward function R H , human expectation set E H , and the robot task domain D R , a policy π E is said to be expectation-aligned, if for all e ∈ E H , you havee |= D R π E , where M R = ⟨D R , R H ⟩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 at 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 E H from the reward specification. Along the same lines, we could leverage psychologically feasible models as a stand-in for P H 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 is limited to a certain form. 
identifying expectation-aligned policies: 
 We will ground the proposed framework in a use case with a 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 H , takes the form ⟨{s}, =, 0⟩ and some states that they would like the robot to visit (i.e., e of the form ⟨{s}, >, 0⟩). We will call the states that are part of the first set of expectations the forbidden state set S F and the second one the goal set S G . 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 H 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 D H . 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 H cannot be part of the forbidden state set (as evaluated in D H ). Proposition 1. There exists no state s ∈ S F and policy π ∈ Π * M H , such that x π (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 S G must be reachable under every optimal policy. Proposition 2. For every state s ∈ S G and policy π ∈ Π * M H , x π (s) > 0 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 F and S G by looking at all states with low and high reward values, respectively. However, there are multiple problems with such a 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 G or relatively low-reward states that are not part of S F . 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 exactly calculate S F and S G , 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 as S F ⊇ S F ) and the set of all states that are reachable under every optimal policy ( S G ⊇ S G ). We can generate these sets by using modified forms of the LP formulation discussed in Equation 1. To test whether a given state s i is part of S F or not, we will look at an LP that will try to identify an optimal policy that will visit s i . Specifically, the LP would look like:max x s,a x(s, a) × r(s, a) + α × ( a x(s i , a)) s.t. ∀s ∈ S, a x(s, a) = δ(s, s 0 ) + γ × s ′ ,a ′ x(s ′ , a ′ ) × T H (s ′ , a ′ , s) s,a x(s, a) × r(s, a) = V * s0 (2)Where α is some positive valued coefficient and V * s0 is the value of the optimal policy in the starting state s 0 . We can calculate V * s0 by solving Equation 1 on 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 i . At the same time, the constraint a x(s 0 , a) = V * s0 ensures we only consider optimal policies. We can now formally state the following property for the above LP formulation. Proposition 3. For the LP described in Equation 2, if s i ∈ S F then for the optimal value x * identified for the LP, the condition a x * (s i , a) = 0 must hold. This follows directly from the definitions of the expectation set and the planning function (a longer sketch is provided in Appendix 8.1). We will again employ a variation of the LP formulation to identify S G . Specifically, to test if a given state s i is part of S G or not, we test the solvability of an LP that tries to create a policy optimal value that doesn't visit s i . max x s,ax(s, a) × r(s, a)EQUATIONThis brings us to the proposition.Algorithm 1 The overall query processInput: D H , D R , R H S F ← Calculate from D H and R H S G ← Calculate from D H and R H S F * ← ∅ S G * ← ∅ while | S G ∪ S F | ̸ = 0 do LP ← CreateLP (D R , S G , S F , S G * , S F * ) Solve, X, DG, DF ← Solve(LP ) D + G , D + F ← F indP ositiveV alues(DG, DF ) if Solve not True then return No Solution end if if |D + G ∪ D + F | = 0 then return Policy corresponding to X end if S ′ G , S ′ F ← M apT oStates( S G , D + G , S F , D + F ) S G = S G \ S ′ G , S F = S F \ S ′ F S G * ← S G * ∪ QueryGoal(S ′ G ), S F * ← S F * ∪ QueryF orbidden(S ′ F ) end while return No solutionProposition 4. For the LP described in Equation 3, if s i ∈ S G , then there must exist no solution for the given LP. Now with both sets S F and S G calculated, the objective of the robot is to generate a policy that covers all of the states in S G , while avoiding the states in S F . This may not always be possible, so we will need the system to query the user about whether a state s ∈ S F is actually part of S F (i.e., "do I need to avoid s?"), and if a state s ′ ∈ S G is actually part of S G ("do I need to visit s ′ ?"). Based on their response, we can update the sets and try to see if 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 x,D F ,D G -1 × d∈D G ∪D F d s.t. ∀s ∈ S, a x(s, a) = δ(s, s 0 ) + γ × s ′ ,a ′ x(s ′ , a ′ ) × T R (s ′ , a ′ , s) ∀d ∈ D G ∪ D F , d ≥ 0 ∀s i ∈ S F a x(s i , a) -d i = 0; ∀s j ∈ S G a x(s j , a) + d j ≥ 0 (4)As seen in the equation, this formulation requires the introduction of two new sets of bookkeeping variables D F and D G , such that|D F | = | S F | and |D G | = | S G |.To simplify notations, we will denote the bookkeeping variable corresponding to a state s i ∈ S F ∪ S G as d i . The next thing to note is that 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 S F and S G into soft constraints that can be ignored at a cost. This is done through the manipulation of the bookkeeping variables. This brings us to the first theorem Theorem 2. If there exists a policy that satisfies the requirement that no state in S F is visited and all states in S G is visited (therefore satisfied the underlying expectation), then the optimal solution for Equation 4, must assign 0 to all variables in D G and D F . Proof Sketch. The reasoning follows directly from how the last two constraints of Equation 4 and the fact setting more d 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 a positive value if a forbidden state has a non-zero occupancy frequency or if some potential goal states are unreachable.When such solutions are not found, the d variables that take positive values tell us potential states we can query. After the query if the user says a state shouldn't be visited or should be visited the corresponding states are removed from S F or S G and moved to the set S F * (set of known forbidden states) and S G * (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.∀s i ∈ S F * , a x(s i , a) = 0; ∀s i ∈ S G * , a x(s i , a) ≥ 0 (5)Theorem 2 also holds for this new LP. If the user answers that a state is neither a forbidden nor a goal state, then the state is simply removed from the corresponding superset. This process is repeated until a policy is found, if there are no more elements in S F ∪ S G , or if the LP is unsolvable.Algorithm 1 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 F and S G (along with known ones). The estimates are refined through queries with the user (represented by the procedures QueryGoal and QueryF orbidden). The algorithm stops if a solution is found that doesn't require any additional queries, if the LP is unsolvable, or if it runs out of states to query. Proposition 5. Algorithm 1, 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. 
related works: 
 Given the ever-increasing capabilities of AI agents, there has been a 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 is 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-Menell et al., 2016] . One could roughly categorize the work done to develop more general methods to address this problem into two broad categories.In the first, the reward function is mostly taken to be true, but they assume there is a 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 , Saisubramanian et al., 2022 , Mahmud et al., 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 [Hadfield-Menell et al., 2017] , which uses the specified reward function as a 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 [Hadfield-Menell 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-alignment 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 expectation-aligned policies. But, as discussed this is not a general solution strategy.Another stream of work that is relevant to the current problem is that of imitation learning [Torabi et 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 or generate behaviors that match the intent behind the demonstration. Apprenticeship learning [Abbeel 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 a policy that maximizes this learned reward function. In some sense, our work inverts this paradigm and starts from a 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 inverse-reinforcement learning community to formalize misspecification (cf. [Skalse and Abate, 2023] ). However, we see such work being complementary to our effort. 
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 5. Specifically, we wanted to test:"How the method described in Section 4 compared with existing methods in terms of (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-Regret Querying (MMRQ-k) [Zhang et al., 2018] (with query size k = 2 and all features set to unknown) and a modified form of the Inverse Reward Design method [Hadfield-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 S G and S F . For the expected reward function, a high positive reward was assigned for S G and a negative one for S F . 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 [Abel, 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 is unaware of it. Obstacles involve the robot navigating to a 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 a maze, while the human model may have incorrect information about what paths are available.Evaluation. All the baselines were run with a time-bound of 30 minutes per problem. All experiments were run on AlmaLinux 8.9 with 32GB RAM and 16 Intel(R) Xeon(R) 2.60GHz CPUs. We used CPLEX [Bliek1ú et al., 2014] as our LP solver (no-cost edition)4 . 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 1 : 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 taken. Note that our method is guaranteed not to choose a policy that results in violated expectations.expensive methods from the first group are. On the other hand, our method is much faster, and even in the largest grids, it took less than five minutes (Table 1 ) 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 1 shows 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 of user policies. While IRD is fast, please keep in mind that we avoided the expensive inference process of the original IRD with direct access to S F and S G (reported times don'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 expectation-alignment 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 to 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 a 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 al., 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 a solid formal framework that can be used as a 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 to 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 it might also impact how effectively the user can be queried.8 Appendix / supplemental material 8.1 Proof Sketch for Propositions Proposition 1. There exists no state s ∈ S F and policy π ∈ Π * M H , such that x π (s) > 0 is true.Proof Sketch. We will prove this through contradiction. Let's assume that there exists a state s ∈ S F , where x π (s) > 0 for an optimal policy π ∈ Π * M H for a human specified reward function R H . Per Definition 4, a reward function is only specified, i.e., they are human-sufficient if, for every policy in π ∈ P H (⟨D H , R⟩), you have e |= D H π, for all e ∈ E H . If s ∈ S F , then e = ⟨{s}, =, 0⟩. Per our assumptions, P returns the set of optimal policies, hence π ∈ P H (⟨D H , R H ⟩). This means that e |= D H π, 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 ∈ S G and policy π ∈ Π * M H , x π (s) > 0 must always be true. Proof Sketch. We can prove this through contradiction by following a rationale similar to the earlier proposition. We will again leverage the intuition that for a reward function to be human-sufficient, all optimal policies must satisfy all specified expectations, which include visiting states in S G . As such, if a state is not visited by an optimal policy, it cannot be part of the set S G . Proposition 3. For the LP described in Equation 2, if s i ∈ S F then for the optimal value x * identified for the LP, the condition a x * (s i , a) = 0 must hold.Proof Sketch. In the equation the constraint s,a x(s, a) × r(s, a) = V * s0 , 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 x s,a x(s, a) × r(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 s i . In other words, it will try to find optimal policies that visit the state. However, per Proposition 1, no states in S F are ever visited by an optimal policy. This means if the LP finds a solution with non-zero occupancy frequency for the state s i it cannot be part of S F . Proposition 4. For the LP described in Equation 3, if s i ∈ S G , 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 s,a x(s, a) × r(s, a) = V * s0 forces the LP solver to only consider occupancy frequencies for optimal policies. The new constraint a x(s i , a) = 0, forces the LP to find optimal policies where the state is not visited. If in fact such a policy is found, per Proposition 4, the state cannot be part of S G . 
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 decision-making is to use the noisy rational model Jeon et al. [2020] . Under this approach, the likelihood of the human choosing a policy π is given as p(π) ∝ e β×V π (s0)Where V π (s 0 ) corresponds to the value associated with state s 0 under a policy π. For any non-zero β value, the user is more likely to select policies with higher values. However, even non-optimal policies have a probability of getting picked. Additionally, as the value of β reduces, the likelihood of a non-optimal policy being selected increases, with β = 0 corresponding to a case where the user selects the policy completely randomly. As such, β is sometimes referred to as the rationality parameter.For a non-zero β value, let V pi S0 , be the value for which the noisy rational model assigns a probability of at least p i of being picked. Now, let us consider a case where we want to extend our formulation to support a planning function where the human could pick some policy with a probability greater than p i . In this case, we only need to update the LP to calculate the supersets. However, here S F consists of all states avoided by at least one policy and S G consists of every state visited by at least one policy. The corresponding LP formulation for S F become max x s,ax(s, a) × r(s, a)EQUATIONA state belongs to S F if the above LP is solvable for a given state. 
broader impact: 
 We see the problems and challenges being discussed here as being core to the aim of developing effective AI systems that can interact and work with people. We believe that as AI 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, our goal is only to develop methods to ensure AI system behavior aligns with user expectations/intentions. 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.• 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. Justification: We have include a broader impact section in the appendix. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our method is merely a way to avoid reward misspecification, and as such the safeguards are not relevant.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [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 is cited in the paper, and we use the no-cost edition.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented, and is the documentation provided alongside the assets? Answer: [NA] Justification: There are no assets except the code we ran for the experiments, which are included along with the documentation. Guidelines:• The answer NA means that the paper does not release new 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: x s,ax(s, a) × r(s, a) + α × ( a x(s i , a))EQUATIONA state belongs to S G if the above LP is solvable for a 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.In this paper, we will focus on cases where expected/desired outcomes correspond to the agent achieving certain states. Section 3 provides a formal definition.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.We use the term robot to denote our AI agent as means of convenience. Nothing in this framework requires the agent to be physically embodied.The code for our experiments can be found at https://github.com/Malek-Mechergui/codeMDP 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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).
- It's hard to draw clear conclusions from the experiments:
	- 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.
	- It would also be nice to have experiments in larger and more varied environments than just 11x11 gridworlds.
questions: 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.:
> 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


As 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: 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.
paper_summary: paper_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. 
After 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.
strength_weakness: strength_weakness: - 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
questions: 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
- 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? 
- 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: limitations: No ethical limitations
paper_summary: paper_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.
strength_weakness: strength_weakness: **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. 

The 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".


Another minor suggestion is to put equation numbers in corresponding lines in the algorithm to make it easier for readers to understand.
questions: questions: I have some minor questions on LP formulation and notation:
* 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. 
* 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.
* For the LPs in eq 2 and 3, do you have to solve it for every $s_i$ being tested? This seems expensive?
* 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: limitations: Acknowledgement of limitations seem appropriate.

Comments: title: Re: Comment
Response
Follow up on the comment
Re: Response to the reviewer
Re: Reviewer Response
Thanks for your answer
Re: Comments
Re: Transition Function
comment: We really appreciate the reviewer's taking the time to engage with us. It really gave us a chance to understand the points of potential confusion and where clarification is needed. 

True representations of the preferences: We will definitely leave a note that the expectation set doesn't necessarily have to always be the true representation of human preference. Our primary motivating principle was that there could be a separation between what the user would want to see and how the actual instructions/objectives are specified, and that could have implications on how the user should be queried. It is better to query in terms of their true intent as opposed to in terms of the queries themselves. While our choices of expectation set were inspired by results from cognitive science, we agree that those results don't constitute a proof. We will make sure to note that, and it is possible that there could be scenarios where people inherently think in terms of rewards. We will make sure to highlight this distinction and make it part of the narrative.

Running Example that ties to the Proof: Thank you for that suggestion. We agree that it would help with the flow of the paper a lot. We will make sure to include a motivating/running example that directly ties to Theorem 1.

Thank you again for your extremely thoughtful and thorough review and feedback. We really appreciate it.
Thanks. I agree that being able to flag when an expectation is unsatisfiable is very useful. I mostly still stand by the high-level concerns I expressed in my original review, but I've become convinced on enough specific points that I'm increasing my score.

A few remaining points (which I don't expect us to converge on in the remaining time, I'm listing these just in case they're useful when updating the paper):

> Yes, we are assuming that the expectation set captures the true human preferences.

This seems like a reasonable assumption for research purposes but I certainly don't think it holds universally. And I think there are likely some cases where humans have an easier time expressing a correct reward functions than having correct expectations about specific behavior (many games with simple goals come to mind as an artificial example). So my current view on this paper is that it's introducing an alternative to reward function as a basis for preferences, and that this alternative is likely sometimes more and sometimes less appropriate. (It may well be that expectation sets are *usually* a better choice, I don't have particularly strong views on that.) If you agree with this interpretation, I would suggest making it more prominent in the presentation.

On the theorem 1 proof: if I understand this construction correctly, it relies crucially on the fact that there are no actions in the final states and so we can't assign a reward of form R(s, a) to them (and thus have to give the reward in an earlier state). This feels pretty artificial, and hopefully, there's an example that doesn't rely on anything like that (e.g. would also work with no-op actions added everywhere). I think if you can find an example that shows theorem 1 while also being a realistic demonstration of the usefulness of expectation sets, that could be very useful for exposition.
Again, thank you so much for responding to our comments

Example:
So, in the example you provided, there is a question about whether the expectation was to reach the goal or to follow the exact path. Let's go with the second case and assume the human's expectation was, in fact, to pass through that exact path. In this case, the robot can never achieve it, as with the reward function. Our method can detect the fact that this cannot be achieved and let humans know that the expectation set cannot be achieved. A purely reward-based system would try to optimize for the best reward estimate (or worse yet, the original reward function); this is what an approach like IRD might do. Even though IRD paper uses the cell with lava as an example, depending on the example, it is possible the average reward need not penalize the lava cells enough to cause the agent to avoid it (for example, there might be other cells of unknown features that weren't there in the human model either). The other advantage of expectations again goes back to the point about transferability and when the expectation set can be satisfied in the robot model. The same reward function might not lead to policies that will satisfy the expectations set in both models. However, different reward functions might exist that would satisfy them in each model. However, the reverse is not true. If the expectation set cannot be achieved in the robot model, no reward function can change that.

Yes, we are assuming that the expectation set captures the true human preferences.


Theorem1 proof:
Again, please note that we are fine with cases where no solutions exist. It is important to identify the problem and inform the user.

So, there are multiple ways to construct a counter-example that shows the absence of a reward function that translates across domains, but policy exists. The simplest one is when you have a case where you take the form of rewards to be $R: S \times A \rightarrow \mathbb{R}$ (note the reward form has nothing to do with the generality of MDP formulation or any of our methods). Now, let us assume the states to be achieved and avoided are ones where no actions are available (again consistent with the most general MDP construction, referred to as control constraint in optimal control [1]). Now, from the starting state, it has access to two actions. One that takes you to the goal state and the other one that takes you to the state to be avoided deterministically. Now, in the human model, you have to reward one over the other. Let's assume in the robot model, their dynamics are reversed. Now, the previous reward function is no longer able to achieve the expectation set in the robot model. 

[1] Bertsekas, Dimitri. Dynamic programming and optimal control: Volume I. Vol. 4. Athena scientific, 2012. (http://www.athenasc.com/DP_Slides_2015.pdf page nine for reference)
Thanks for the additional explanation; this has helped clarify some things for me. I have two key uncertainties left, first about the intended scope and second about Theorem 1 (or more broadly about examples of expectation sets being a better perspective than rewards, but Theorem 1 seems a good candidate for that).

**Scope:** To make this concrete, let me describe a toy example I've been thinking about. Say we have a gridworld with a fixed start and goal state (for simplicity), and the human wants the robot to move to the goal as quickly as possible. The human (incorrectly) believes that the geometrically shortest path from start to goal is free of undesirable states. So the policy they expect is to walk directly from the start to the goal. As an expectation set, this might be expressed by saying that the occupancy frequency on all other states (not on this path) must be zero (or at least close). An example of a human-sufficient reward function would be a reward of +1 for reaching the goal and some negative reward for each time step.

Now assume that, in fact, there is lava in one of the states on the direct path (i.e. this is the correct robot model). If the human knew this, they'd like the robot to avoid the lava. Intuitively, it seems clear that the reward function above is misspecified (since it doesn't include the negative reward for lava). Similarly, the expectation set feels "misspecified" to me, since the only policy that satisfies the expectation set (under the true robot model) walks through lava. So my sense is that both reward functions and expectation sets suffer from exactly the same type of problem here. This is an example of what I had in mind when expressing concerns about whether expectation sets really improve the situation.

My current understanding is that this is *not* a type of misspecification/limited human knowledge you are addressing. Instead, you are *assuming* that the expectation set correctly expresses human preferences, and the only issue arises from incorrect beliefs about the transition function. Is that a good summary?

**Theorem 1/Examples:** I've looked in more detail at Theorem 1, since it seems like it could provide good examples motivating expectation sets from my perspective. (Apologies for not noticing this earlier.) Right now though, I don't follow the proof sketch.

If we only had two expectation elements, <S, >, 0> and <S', =, 0>, I think we could just set the reward on S' to something very negative and on S to something much larger. Then, if there is any policy that satisfies the expectation set, all optimal policies should satisfy the expectation set. (Let me know if that doesn't seem right.) So I think there are two ways to prove Theorem 1:
1. Construct a case where *no* policy satisfies the expectation set (under the robot domain). This would make the claim technically true but I'd interpret the meaning quite differently: this wouldn't be about reward misspecification, it would just be about humans having unrealistic expectations that can't be met by any policy.
2. Construct a more complex expectation set that doesn't have any representation as a reward function for a more "interesting" reason than just being fundamentally unsatisfiable.

If the proof sketch is meant to do 2., then it's not currently clear to me what this expectation set actually looks like (the part about needing to reward some states differently isn't yet obvious to me).

**Questions I still have:**
* Did I understand correctly that the example I describe is out of scope for the problems you're trying to solve? If not, could you say more about how expectation sets help in this specific example?
* The example I describe seems like a simplified version of how I think misspecification in the "Puddle" environment works in your experiments. Is that correct? This makes me think it would *not* be out of scope. Are you modeling things differently than I did above?
* Could you say more about the proof sketch for Theorem 1? (e.g. describe the actual example similar to my gridworld description above, or at least describe the expectation set more if a full construction is too lengthy)

I realize these are a lot of new questions/notes---your responses have helped me clarify my initial concerns into these hopefully more concrete uncertainties.
We hope our response helped answer your question. If not, please let us know; we would be happy to elaborate.
Thank you for the quick response.

The main difference is that the expectation set is a direct encoding of agent behavior. The occupancy frequency can be though of as being determined by the traces the policy would generate over the current transition function. As such, it is already accounting for the transition function and what will happen. However, one needs to use the transition function to figure out what policy would be generated in response to that reward function. Thus, the question of transferability never arises in our case because the users want to see the robot perform the behavior they expected (another way to think about it is that the expectation set is directly transferred over without any modifications). They want to see the robot follow a policy that meets the expectations defined over the occupancy frequency in the robot model. The question that arises is whether the robot can achieve this behavior or not, which our method directly tries to address.


It is also worth repeating that the two main central assertions in this paper are as follows:

1. People don't necessarily start with a reward function. Rather, it is more plausible that they have some target behavior in mind that they want the robot/AI agent to perform.

2. The human and robot models could be different. This is, in fact, a very common case. Limited situational awareness, i.e., cases where the user's understanding of the task may be wrong, is a popular issue studied within human factors/psychology literature. The unfortunate fact is that as the complexity of the task increases, it might not be possible to completely resolve this discrepancy. This is a fact that is accepted by most explainable AI methods. This is one of the reasons why abstractions are a very popular tool within XAI.

Please let us know if this answers your questions. We would be more than happy to expand on any of the points discussed above.
Thank you for the detailed response! I still think it would be good to have more concrete arguments that expectation sets transfer better (or have other advantages). Everything you mention (connections to cognitive science, the difficulty of specifying reward functions) is great *motivation* for studying alternative frameworks. But I think it falls short of being sufficiently convincing evidence, given that these feel like very high-level conceptual arguments. For example:

> the expectation set, as formulated in the paper, is a generalization of goals

Yes, but we could also think of reward functions as a generalization of goals (where goals would be encoded as reward functions that only give rewards 0 or 1). Clearly, expectation sets generalize goals in an interestingly different way, and maybe a better way. But whether (or in which cases) expectation sets are the "right" generalization of goals seems like the crucial question.

> 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.

I don't think I follow this argument. If we assume that the system can explain everything the user needs to know about the environment, this just seems to solve the problem I understood the paper to be tackling. (Humans having incorrect beliefs about the environment and thus providing misspecified rewards.) In this setting, where humans now have correct beliefs about the environment, it seems reward functions should work just as well as expectation sets. (At least in the framework presented in the paper: if the human model and robot models match, then every human-sufficient reward function should be correctly specified, I think?)

So it seems to me that either we don't assume the robot can explain everything to the human, in which case both reward functions and expectation sets can fail to transfer in at least some cases, or we let the robot explain everything, in which case both approaches work fine. It might still be the case that expectation sets transfer more often or have some other advantage, but I currently don't see the concrete argument in favor of that claim.

Please let me know in case I've misunderstood anything!

To be clear, I think it would be unreasonable to expect this paper to fully demonstrate that expectation sets are always the right approach. But I do think it would be good if there was at least one clear demonstrable advantage of expectation sets, rather than only high-level arguments (that in my view are only moderately compelling, but naturally views on that will diverge more than they would for more specific claims).
Thank you for the quick response and all the helpful feedback. We will make sure to incorporate them into the paper.
Thanks for your response.

**Experiments**: Thanks for clarifying your results. I suggest using this answer to increase the clarity of the presentation in the Experiments section

**Non gridworld domains**: I've read the main rebuttal text as well, and this clarifies my main doubts. 

**Proofs**: Thanks for the sketch of the proof.

The authors addressed most of my concerns. Including a formal proof for all the statements (even in the appendix) will much increase the quality and strength of the submission. Since the authors mentioned that this will be done, and a sample proof is provided, I'll increase my score accordingly.
Thank you again for your extremely helpful comments. We really appreciate it.
I thank the authors for confirming. All my questions are resolved.
You are actually correct. We apologize for missing that. During the rebuttal, we were mainly focused on the form of the transition function, and we didn't notice the summand was switched. In fact, to avoid further confusion, we will stick with the convention of s' being the next state and rewrite the constraint to

$\sum_{a'} x(s',a') = \delta(s',s_0) + \gamma\times \sum_{s,a} x(s,a) \times T^R(s, a, s')$

This is the more popular way of denoting occupancy frequency equation (also used by the paper, the reviewer pointed to). We thank the reviewer for catching that, and we apologize for the confusion.
I thank the authors for their responses. Most of my questions are resolved. 

I have one follow up question on the transition function. My original question is on the summands of the transition function, i.e., the current states and actions should be summed out as opposed to the future states and actions. I think this makes sense because the basic idea of the Bellman flow equation, similar to the Bellman equation, is that the long term occupancy is the sum of the immediate occupancy and the expected next occupancy. Another point of reference is eq 3 in [this paper](https://arxiv.org/abs/1906.04733) which illustrates the same point. Please feel free to correct me if I'm wrong about this.