Paper deep dive
Defining and Characterizing Reward Hacking
Joar Skalse, Nikolaus H. R. Howe, Dmitrii Krasheninnikov, David Krueger
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 3/12/2026, 7:55:10 PM
Summary
The paper provides a formal definition of 'reward hacking' in reinforcement learning, where optimizing a proxy reward function leads to poor performance on the true reward function. It introduces the concept of 'unhackability'—a condition where increasing proxy return never decreases true return—and proves that for the set of all stochastic policies, non-trivial unhackable pairs do not exist. The authors establish conditions for unhackability and simplification in finite policy sets and discuss the implications for AI alignment.
Entities (5)
Relation Signals (3)
Joar Skalse → authored → Defining and Characterizing Reward Hacking
confidence 100% · Defining and Characterizing Reward Hacking Joar Skalse
Simplification → isspecialcaseof → Unhackability
confidence 100% · we introduce the asymmetric special case of simplification
Reward Hacking → isdefinedby → Unhackability
confidence 90% · We provide the first formal definition of reward hacking... We say that a proxy is unhackable if increasing the expected proxy return can never decrease the expected true return.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We provide the first formal definition of reward hacking, a phenomenon where optimizing an imperfect proxy reward function leads to poor performance according to the true reward function. We say that a proxy is unhackable if increasing the expected proxy return can never decrease the expected true return. Intuitively, it might be possible to create an unhackable proxy by leaving some terms out of the reward function (making it "narrower") or overlooking fine-grained distinctions between roughly equivalent outcomes, but we show this is usually not the case. A key insight is that the linearity of reward (in state-action visit counts) makes unhackability a very strong condition. In particular, for the set of all stochastic policies, two reward functions can only be unhackable if one of them is constant. We thus turn our attention to deterministic policies and finite sets of stochastic policies, where non-trivial unhackable pairs always exist, and establish necessary and sufficient conditions for the existence of simplifications, an important special case of unhackability. Our results reveal a tension between using reward functions to specify narrow tasks and aligning AI systems with human values.
Tags
Links
- Source: https://arxiv.org/abs/2209.13085
- Canonical: https://arxiv.org/abs/2209.13085
Trouble viewing inline? Open PDF directly →
Full Text
79,199 characters extracted from source content.
Expand or collapse full text
Defining and Characterizing Reward Hacking Joar Skalse ∗ University of Oxford Nikolaus H. R. Howe Mila, Université de Montréal Dmitrii Krasheninnikov University of Cambridge David Krueger ∗ University of Cambridge Abstract We provide the first formal definition ofreward hacking, a phenomenon where optimizing an imperfect proxy reward function, ̃ R , leads to poor performance according to the true reward function,R. We say that a proxy isunhackableif increasing the expected proxy return can never decrease the expected true return. Intuitively, it might be possible to create an unhackable proxy by leaving some terms out of the reward function (making it “narrower”) or overlooking fine-grained distinctions between roughly equivalent outcomes, but we show this is usually not the case. A key insight is that the linearity of reward (in state-action visit counts) makes unhackability a very strong condition. In particular, for the set of all stochastic policies, two reward functions can only be unhackable if one of them is constant. We thus turn our attention to deterministic policies and finite sets of stochastic policies, where non-trivial unhackable pairs always exist, and establish necessary and sufficient conditions for the existence of simplifications, an important special case of unhackability. Our results reveal a tension between using reward functions to specify narrow tasks and aligning AI systems with human values. 1 Introduction It is well known that optimising a proxy can lead to unintended outcomes: a boat spins in circles collecting “powerups” instead of following the race track in a racing game (Clark and Amodei, 2016); an evolved circuit listens in on radio signals from nearby computers’ oscillators instead of building its own (Bird and Layzell, 2002); universities reject the most qualified applicants in order to appear more selective and boost their ratings (Golden, 2001). In the context of reinforcement learning (RL), such failures are calledreward hacking. For AI systems that take actions in safety-critical real world environments such as autonomous vehicles, algorithmic trading, or content recommendation systems, these unintended outcomes can be catastrophic. This makes it crucial to align autonomous AI systems with their users’ intentions. Precisely specifying which behaviours are or are not desirable is challenging, however. One approach to this specification problem is to learn an approximation of the true reward function (Ng et al., 2000; Ziebart, 2010; Leike et al., 2018). Optimizing a learned proxy reward can be dangerous, however; for instance, it might overlook side-effects (Krakovna et al., 2018; Turner et al., 2019) or encourage power-seeking (Turner et al., 2021) behavior. This raises the question motivating our work: When is it safe to optimise a proxy? To begin to answer this question, we consider a somewhat simpler one: Whencouldoptimising a proxy lead to worse behaviour? “Optimising”, in this context, does not refer to finding a global, or even local, optimum, but rather running a search process, such as stochastic gradient descent ∗ Equal contribution. Correspondence to:joar.mvs@gmail.com, david.scott.krueger@gmail.com 36th Conference on Neural Information Processing Systems (NeurIPS 2022). arXiv:2209.13085v2 [cs.LG] 5 Mar 2025 (SGD), that yields a sequence of candidate policies, and tends to move towards policies with higher (proxy) reward. We make no assumptions about the path through policy space that optimisation takes. 1 Instead, we ask whether there isanyway in which improving a policy according to the proxy could make the policy worse according to the true reward; this is equivalent to asking if there exists a pair of policiesπ 1 ,π 2 where the proxy prefersπ 1 , but the true reward function prefersπ 2 . When this is the case, we refer to this pair of true reward function and proxy reward function ashackable. Given the strictness of our definition, it is not immediately apparent that any non-trivial examples of unhackable reward function pairs exist. And indeed, if we consider the set of all stochastic policies, they do not (Section 5.1). However, restricting ourselves toanyfinite set of policies guarantees at least one non-trivial unhackable pair (Section 5.2). Intuitively, we might expect the proxy to be a “simpler” version of the true reward function. Noting that the definition of unhackability is symmetric, we introduce the asymmetric special case of simplification, and arrive at similar theoretical results for this notion. 2 In the process, and through examples, we show that seemingly natural ways of simplifying reward functions often fail to produce simplifications in our formal sense, and in fact fail to rule out the potential for reward hacking. We conclude with a discussion of the implications and limitations of our work. Briefly, our work suggests that a proxy reward function must satisfy demanding standards in order for it to be safe to optimize. This in turn implies that the reward functions learned by methods such as reward modeling and inverse RL are perhaps best viewed as auxiliaries to policy learning, rather than specifications that should be optimized. This conclusion is weakened, however, by the conservativeness of our chosen definitions; future work should explore when hackable proxies can be shown to be safe in a probabilistic or approximate sense, or when subject to only limited optimization. 2 Example: Cleaning Robot Consider a household robot tasked with cleaning a house with three rooms: Attic, Bedroom , and Kitchen. The robot’s (deterministic) policy is a vector indicating which rooms it cleans: π= [π 1 ,π 2 ,π 3 ]∈0,1 3 . The robot receives a (non-negative) reward ofr 1 ,r 2 ,r 3 for cleaning the attic, bedroom, and kitchen, respectively, and the total reward is given byJ(π) =π·r. For example, ifr= [1,2,3]and the robot cleans the attic and the kitchen, it receives a reward of1 + 3 = 4. Clean ! 푟 prox y = [1 ,0,0] Cleaning is better than cleaning both and . Clean and ! 푟 prox y = [1 ,1,0] Cleaning one room is never better than cleaning two rooms. (a) 푟 prox y is hackable (b) 푟 prox y is not hackable I want , , and cleaned, and care about all rooms equally: 푟 true = [1 ,1,1]. Figure 1: An illustration of hackable and unhackable proxy rewards arising from overlooking rewarding features. A human wants their house cleaned. In (a), the robot draws an incorrect conclusion because of the proxy; this could lead to hacking. In (b), no such hacking can occur: the proxy is unhackable. At least two ideas come to mind when thinking about “simplifying” a reward function. The first one isoverlooking rewarding features: suppose the true reward is equal for all the rooms,r true = [1,1,1], but we only ask the robot to clean the attic and bedroom,r proxy = [1,1,0]. In this case,r proxy and r true are unhackable. However, if we ask the robot to only clean the attic,r proxy = [1,0,0], this is hackable with respect tor true . To see this, note that according tor proxy cleaning the attic (J proxy = 1) is better than cleaning the bedroom and the kitchen (J proxy = 0). Yet,r true says that cleaning the attic (J true = 1) is worse than cleaning the bedroom and the kitchen (J true = 2). This situation is illustrated in Figure 1. 1 This assumption – although conservative – is reasonable because optimisation in state-of-the-art deep RL methods is poorly understood and results are often highly stochastic and suboptimal. 2 See Section 4.2 for formal definitions. 2 The second seemingly natural way to simplify a reward function isoverlooking fine details: suppose r true = [1,1.5,2], and we ask the robot to clean all the rooms,r proxy = [1,1,1]. For these values, the proxy and true reward are unhackable. However, with a slightly less balanced true reward function such asr true = [1,1.5,3]the proxy does lead to hacking, since the robot would falsely calculate that it’s better to clean the attic and the bedroom than the kitchen alone. These two examples illustrate that while simplification of reward functions is sometimes possible, attempts at simplification can easily lead to reward hacking. Intuitively, omitting/overlooking details is okay so long as all these details are not as important together as any of the details that we do share. In general, it is not obvious what the proxy must look like to avoid reward hacking, suggesting we should take great care when using proxies. For this specific environment, a proxy and a true reward are hackable exactly when there are two sets of roomsS 1 ,S 2 such that the true reward gives strictly higher value to cleaningS 1 than it does to cleaningS 2 , and the proxy says the opposite: J 1 (S 1 )> J 1 (S 2 ) &J 2 (S 1 )< J 2 (S 2 ). For a proof of this statement, see Appendix D.2.1. 3 Related Work Training time True reward Proxy reward Figure 2: An illustration of reward hacking when op- timizing a hackable proxy. The true reward first in- creases and then drops off, while the proxy reward continues to increase. While we are the first to define hackability, we are far from the first to study specification hacking. The observation that optimizing proxy met- rics tends to lead to perverse instantiations is often called “Goodhart’s Law”, and is attributed to Goodhart (1975). Manheim and Garrabrant (2018) provide a list of four mechanisms underlying this observation. Examples of such unintended behavior abound in both RL and other areas of AI; Krakovna et al. (2020) provide an extensive list. Notable recent instances include a robot positioning itself between the camera and the object it is supposed to grasp in a way that tricks the reward model (Amodei et al., 2017), the previously mentioned boat race exam- ple (Clark and Amodei, 2016), and a multitude of examples of reward model hacking in Atari (Ibarz et al., 2018). Reward hacking can occur suddenly. Ibarz et al. (2018) and Pan et al. (2022) showcase plots similar to one in Figure 2, where optimizing the proxy (either a learned reward model or a hand-specified reward function) first leads to both proxy and true rewards increasing, and then to a sudden phase transition where the true reward collapses while the proxy continues going up. Note that not all of these examples correspond to optimal behavior according to the proxy. Indeed, convergence to suboptimal policies is a well-known issue in RL (Thrun and Schwartz, 1993). As a consequence, improving optimization often leads to unexpected, qualitative changes in behavior. For instance, Zhang et al. (2021) demonstrate a novel cartwheeling behavior in the widely studied Half-Cheetah environment that exceeds previous performance so greatly that it breaks the simulator. The unpredictability of RL optimization is a key motivation for our definition of hackability, since we cannot assume that agents will find an optimal policy. Neither can we rule out the possibility of sudden improvements in proxy reward and corresponding qualitative changes in behavior. Unhackability could provide confidence that reward hacking will not occur despite these challenges. Despite the prevalence and potential severity of reward hacking, to our knowledge Pan et al. (2022) provide the first peer-reviewed work that focuses specifically on it, although Everitt et al. (2017) tackle the closely related issue of reward corruption. The work of Pan et al. (2022) is purely empirical; they manually construct proxy rewards for several diverse environments, and evaluate whether optimizing these proxies leads to reward hacking; in 5 out of 9 of their settings, it does. In another closely related work, Zhuang and Hadfield-Menell (2020) examine what happens when the proxy reward function depends on a strict subset of features relevant for the true reward. They show that optimizing the proxy reward can lead to arbitrarily low true reward under suitable assumptions. This can be seen as a seemingly valid simplification of the true reward that turns out to be (highly) hackable. While their result only applies to environments with decreasing marginal utility and increasing opportunity cost, we demonstrate hackability is an issue in arbitrary MDPs. 3 Hackability is particularly concerning given arguments that reward optimizing behavior tends to be power-seeking (Turner et al., 2021). But Leike et al. (2018) establish that any desired behavior (power-seeking or not) can in principle be specified as optimal via a reward function. 3 However, unlike us, they do not consider the entire policy preference ordering. Meanwhile, Abel et al. (2021) note that Markov reward functions cannot specify arbitrary orderings over policies or trajectories, although they do not consider hackability. Previous works consider reward functions to be equivalent if they preserve the ordering over policies (Ng et al., 1999, 2000). Unhackability relaxes this, allowing equalities to be refined to inequalities, and vice versa. Unhackability provides a notion of what it means to be “aligned enough”; Brown et al. (2020b) provide an alternative. They say a policy is ε-value aligned if its value at every state is close enough to optimal (according to the true reward function). Neither notion implies the other. Reward tampering(Everitt et al., 2017; Kumar et al., 2020; Uesato et al., 2020; Everitt et al., 2021) can be viewed as a special case of reward hacking, and refers to an agent corrupting the process generating reward signals, e.g. by tampering with sensors, memory registers storing the reward signal, or other hardware. Everitt et al. (2017) introduce the Corrupt Reward MDP (CRMDP), to model this possibility. A CRMDP distinguishes corrupted and uncorrupted rewards; these are exactly analogous to the proxy and true reward discussed in our work and others. Leike et al. (2018) distinguish reward tampering fromreward gaming, where an agent achieves inappropriately high reward without tampering. However, in principle, a reward function could prohibit all forms of tampering if the effects of tampering are captured in the state. So this distinction is somewhat imprecise, and the CRMDP framework is general enough to cover both forms of hacking. Our notion of simplification bears a close resemblance to quantilization (Taylor, 2016). Quantilization returns a random policy from the top n% best policies. This is similar to equating the values of those policies, but a simplification may also equate the values of the bottom/middle n%, etc. Thus simplification may achieve a similar effect to quantilization without assuming that we are free to choose from among the best policies. 4 Preliminaries We begin with an overview of reinforcement learning (RL) to establish our notation and terminology. Section 4.2 introduces our novel definitions of hackability and simplification. 4.1 Reinforcement Learning We expect readers to be familiar with the basics of RL, which can be found in Sutton and Barto (2018). RL methods attempt to solve a sequential decision problem, typically formalised as aMarkov decision process (MDP), which is a tuple(S,A,T,I,R,γ)whereSis a set of states,Ais a set of actions,T:S×A→∆(S)is a transition function,I∈∆(S)is an initial state distribution,R is a reward function, the most general form of which isR:S×A×S→∆(R), andγ∈[0,1] is the discount factor. Here∆(X)is the set of all distributions overX. Astationary policyis a functionπ:S→∆(A)that specifies a distribution over actions in each state, and anon-stationary policy is a functionπ: (S×A) ∗ ×S→∆(A), where∗is the Kleene star. Atrajectoryτis a path s 0 ,a 0 ,r 0 ,...through the MDP that is possible according toT,I, andR. Thereturnof a trajectory is the discounted sum of rewardsG(τ) . = P ∞ t=0 γ t r t , and thevalueof a policy is the expected return J(π) . =E τ∼π [G(τ)]. We derivepolicy (preference) orderingsfrom reward functions by ordering policies according to their value. In this paper, we assume thatSandAare finite, that|A|>1, that all states are reachable, and thatR(s,a,s ′ )has finite mean for alls,a,s ′ . In our work, we consider various reward functions for a given environment, which is then formally aMarkov decision process without rewardMDP . = (S,A,T,I,,γ). Having fixed an MDP , any reward function can be viewed as a function of only the current state and action by marginalizing over transitions:R(s,a) . = P s ′ ∼T(s ′ |s,a) R(s,a,s ′ ), we adopt this view from here on. We define the(discounted) visit countsof a policy asF π (s,a) . =E τ∼π [ P ∞ i=0 γ i 1(s i =s,a i =a)]. Note thatJ(π) = P s,a R(s,a)F π (s,a) , which we also write as⟨R,F π ⟩. When considering multiple reward functions in anMDP\ R, we defineJ R (π) . =⟨R,F π ⟩and sometimes use 3 Their result concerns non-stationary policies and use non-Markovian reward functions, but in Appendix C, we show how an analogous construction can be used with stationary policies and Markovian rewards. 4 J i (π) . =⟨R i ,F π ⟩as shorthand. We also useF: Π→R |S||A| to denote the embedding of policies into Euclidean space via their visit counts, and defineF( ̇ Π) . =F(π:π∈ ̇ Π)for any ̇ Π. Moreover, we also use a second way to embed policies into Euclidean space; letG(π)be the|S||A|-dimensional vector whereG(π)[s,a] =π(a|s), and letG( ̇ Π) . =G(π:π∈ ̇ Π). 4.2 Definitions and Basic Properties of Hackability and Simplification Here, we formally definehackabilityas a binary relation between reward functions. Definition 1.A pair of reward functionsR 1 ,R 2 arehackablerelative to policy setΠand an environment(S,A,T,I,,γ)if there existπ,π ′ ∈Πsuch that J 1 (π)< J 1 (π ′ ) &J 2 (π)> J 2 (π ′ ), else they areunhackable. Note that an unhackable reward pair can haveJ 1 (π)< J 1 (π ′ ) &J 2 (π) =J 2 (π ′ )or vice versa. Unhackability is symmetric; this can be seen be swappingπandπ ′ in Definition 1. It is not transitive, however. In particular, the constant reward function is unhackable with respect to any other reward function, so if itweretransitive, any pair of policies would be unhackable. Additionally, we say that R 1 andR 2 areequivalenton a set of policiesΠifJ 1 andJ 2 induce the same ordering ofΠ, and thatRistrivialonΠifJ(π) =J(π ′ )for allπ,π ′ ∈Π. It is clear thatR 1 andR 2 are unhackable whenever they are equivalent, or one of them is trivial, but this is relatively uninteresting. Our central question is if and when there are other unhackable reward pairs. The symmetric nature of this definition is counter-intuitive, given that our motivation distinguishes the proxy and true reward functions. We might break this symmetry by only considering policy sequences that monotonically increase the proxy, however, this is equivalent to our original definition of hackability: think ofR 1 as the proxy, and consider the sequenceπ,π ′ . We could also restrict ourselves to policies that are approximately optimal according to the proxy; Corollary 2 shows that Theorem 1 applies regardless of this restriction. Finally, we definesimplificationas an asymmetric special-case of unhackability; Theorem 3 shows this is in fact a more demanding condition. Definition 2.R 2 is asimplificationofR 1 relative to policy setΠif for allπ,π ′ ∈Π, J 1 (π)< J 1 (π ′ ) =⇒J 2 (π)≤J 2 (π ′ ) &J 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ ) and there existπ,π ′ ∈Πsuch thatJ 2 (π) =J 2 (π ′ )butJ 1 (π)̸=J 1 (π ′ ). Moreover, ifR 2 is trivial then we say that this is atrivial simplification. Intuitively, while unhackability allows replacing inequality with equality – or vice versa – a simplifi- cation can only replace inequalities with equality, collapsing distinctions between policies. When R 1 is a simplification ofR 2 , we also say thatR 2 is arefinementofR 1 . We denote this relation- ship asR 1 ⊴R 2 orR 2 ⊵R 1 ; the narrowing of the triangle atR 1 represents the collapsing of distinctions between policies. IfR 1 ⊴R 2 ⊵R 3 , then we have thatR 1 ,R 3 are unhackable, 4 but if R 1 ⊵R 2 ⊴R 3 , then this is not necessarily the case. 5 Note that these definitions are given relative to someMDP , although we often assume the environment in question is clear from context and suppress this dependence. The dependence on the policy setΠ, on the other hand, plays a critical role in our results. 5 Results Our results are aimed at understanding when it is possible to have an unhackable proxy reward function. We first establish (in Section 5.1) that (non-trivial) unhackability is impossible when considering the set of all policies. We might imagine that restricting ourselves to a set of sufficiently good (according to the proxy) policies would remove this limitation, but we show that this is not the case. We then analyze finite policy sets (with deterministic policies as a special case), and establish necessary and sufficient conditions for unhackability and simplification. Finally, we demonstrate via example that non-trivial simplifications are also possible for some infinite policy sets in Section 5.3. 4 IfJ 3 (π)> J 3 (π ′ )thenJ 2 (π)> J 2 (π ′ ), sinceR 2 ⊵R 3 , and ifJ 2 (π)> J 2 (π ′ )thenJ 1 (π)≥J 1 (π ′ ), sinceR 1 ⊴R 2 . It is therefore not possible thatJ 3 (π)> J 3 (π ′ )butJ 1 (π)< J 1 (π ′ ). 5 Consider the case whereR 2 is trivial – thenR 1 ⊵R 2 ⊴R 3 for anyR 1 ,R 3 . 5 5.1 Non-trivial Unhackability Requires Restricting the Policy Set State Reward(State) A B C Figure 3: Two reward functions. While the step function may seem like a simplification of the Gaussian, these reward functions are hackable. We start with a motivating example. Consider the setting shown in Figure 3, where the agent can move left/stay-still/right and gets a reward depending on its state. Let the Gaussian (blue) be the true rewardR 1 and the step function (orange) be the proxyR 2 . These are hackable. To see this, consider being at stateB. Letπ(B)travel toAorCwith 50/50 chance, and compare with the policyπ ′ that stays atB. Then we have thatJ 1 (π)> J 1 (π ′ )andJ 2 (π)< J 2 (π ′ ). Generally, we might hope that some environments allow for unhackable reward pairs that are not equivalent or trivial. Here we show that this is not the case, unless we impose restrictions on the set of policies we consider. First note that if we considernon-stationarypolicies, this result is relatively straightforward. Suppose R 1 andR 2 areunhackableandnon-trivialon the setΠ N of all non-stationary policies, and letπ ⋆ be a policy that maximises (R 1 andR 2 ) reward, andπ ⊥ be a policy thatminimises(R 1 andR 2 ) reward. Then the policyπ λ that playsπ ⋆ with probabilityλandπ ⊥ with probability1−λis a policy inΠ N . Moreover, for anyπthere are two uniqueα,β∈[0,1]such thatJ 1 (π) =J 1 (π α )and J 2 (π) =J 2 (π β ). Now, ifα̸=β, then eitherJ 1 (π)< J 1 (π δ )andJ 2 (π)> J 2 (π δ ), or vice versa, forδ= (α+β)/2. IfR 1 andR 2 are unhackable then this cannot happen, so it must be thatα=β. This, in turn, implies thatJ 1 (π) =J 1 (π ′ )iffJ 2 (π) =J 2 (π ′ ), and soR 1 andR 2 areequivalent. This means that no interesting unhackability can occur on the set of all non-stationary policies. The same argument cannot be applied to the set ofstationarypolicies, becauseπ λ is typically not stationary, and mixing stationary policies’ action probabilities does not have the same effect. For instance, consider a hallway environment where an agent can either move left or right. Mixing the “always go left” and “always go right” policies corresponds to picking a direction and sticking with it, whereas mixing their action probabilities corresponds to choosing to go left or right independently at every time-step. However, we will see that there still cannot be any interesting unhackability on this policy set, and, more generally, that there cannot be any interesting unhackability on any set of policies which contains anopen subset. Formally, a set of (stationary) policies ̇ Πis open ifG( ̇ Π)is open in the smallest affine space that containsG(Π), for the set of all stationary policiesΠ. We will use the following lemma: Lemma 1.In anyMDP , if ̇ Πis an open set of policies, thenF( ̇ Π)is open inR |S|(|A|−1) , and Fis a homeomorphism betweenG( ̇ Π)andF( ̇ Π). Using this lemma, we can show that interesting unhackability is impossible on any set of stationary policies ˆ Π which contains an open subset ̇ Π . Roughly, ifF( ̇ Π)is open, andR 1 andR 2 are non-trivial and unhackable on ̇ Π, then the fact thatJ 1 andJ 2 have a linear structure onF( ˆ Π)implies thatR 1 andR 2 must be equivalent on ̇ Π. From this, and the fact thatF( ̇ Π)is open, it follows thatR 1 and R 2 are equivalent everywhere. Theorem 1.In anyMDP , if ˆ Πcontains an open set, then any pair of reward functions that are unhackable and non-trivial on ˆ Πare equivalent on ˆ Π. Since simplification is a special case of unhackability, this also implies that non-trivial simplification is impossible for any such policy set. Also note that Theorem 1 makesno assumptionsabout the transition function, etc. From this result, we can show that interesting unhackability always is impossible on the setΠof all (stationary) policies. In particular, note that the set ̃ Πof all policies that always take each action with positive probability is an open set, and that ̃ Π⊂Π. Corollary 1.In anyMDP , any pair of reward functions that are unhackable and non-trivial on the set of all (stationary) policiesΠare equivalent onΠ. Theorem 1 can also be applied to many other policy sets. For example, we might not care about the hackability resulting from policies with low proxy reward, as we would not expect a sufficiently good learning algorithm to learn such policies. This leads us to consider the following definition: 6 Definition 3.A (stationary) policyπisε-suboptimal ifJ(π)≥J(π ⋆ )−ε. Alternatively, if the learning algorithm always uses a policy that is “nearly” deterministic (but with some probability of exploration), then we might not care about hackability resulting from very stochastic policies, leading us to consider the following definition: Definition 4.A (stationary) policyπisδ-deterministic if∀s∈S∃a∈A:P(π(s) =a)≥δ. Unfortunately, both of these sets contain open subsets, which means they are subject to Theorem 1. Corollary 2.In anyMDP , any pair of reward functions that are unhackable and non-trivial on the set of allε-suboptimal policies (ε >0)Π ε are equivalent onΠ ε , and any pair of reward functions that are unhackable and non-trivial on the set of allδ-deterministic policies (δ <1)Π δ are equivalent onΠ δ . Intuitively, Theorem 1 can be applied to any policy set with “volume” in policy space. 5.2 Finite Policy Sets Having established that interesting unhackability is impossible relative to the set of all policies, we now turn our attention to the case offinitepolicy sets. Note that this includes the set of all deterministic policies, since we restrict our analysis to finite MDPs. Surprisingly, here we find that non-trivial non-equivalent unhackable reward pairsalwaysexist. Theorem 2.For anyMDP , any finite set of policies ˆ Πcontaining at least twoπ,π ′ such that F(π)̸=F(π ′ ), and any reward functionR 1 , there is a non-trivial reward functionR 2 such thatR 1 andR 2 are unhackable but not equivalent. π 2 π 3 π 1 π 4 π 5 Rotating the reward to make V(π 3 ) equal V(π 4 ) first sets V(π 1 ) equal V(π 2 ) π 2 π 3 π 1 π 4 π 5 π 2 π 3 π 1 π 4 π 5 Figure 4: An illustration of the state-action oc- cupancy space with a reward function defined over it. Points correspond to policies’ state- action occupancies. Shading intensity indicates expected reward. Rotating the reward function to makeJ(π 3 )> J(π 4 )passes through a re- ward function that setsJ(π 1 ) =J(π 2 ). Solid black lines are contour lines of the original re- ward function, dotted blue lines are contour lines of the rotated reward function. This proof proceeds by finding a path fromR 1 to another reward functionR 3 that is hackable with respect toR 1 . Along the way to reversing one ofR 1 ’s inequalities, we must encounter a reward functionR 2 that instead replaces it with equality. In the case that dim( ˆ Π) = 3, we can visualize mov- ing along this path as rotating the contour lines of a reward function defined on the space containing the policies’ discounted state-action occupancies, see Figure 4. This path can be constructed so as to avoid any reward functions that produce trivial pol- icy orderings, thus guaranteeingR 2 is non-trivial. For asimplificationto exist, we require some fur- ther conditions, as established by the following theorem: Theorem 3.Let ˆ Π be a finite set of policies, and R 1 a reward function. The following procedure de- termines if there exists a non-trivial simplification ofR 1 in a givenMDP : 1. LetE 1 ...E m be the partition of ˆ Πwhereπ,π ′ belong to the same set iffJ(π) =J(π ′ ). 2.For each such setE i , select a policyπ i ∈E i and letZ i be the set of vectors that is obtained by subtractingF(π i )from each element ofF(E i ). Then there is a non-trivial simplification ofRiffdim(Z 1 ∪·∪Z m )≤dim(F( ˆ Π))−2, where dim(S)is the number of linearly independent vectors inS. The proof proceeds similarly to Theorem 2. However, in Theorem 2 it was sufficient to show that there are no trivial reward functions along the path fromR 1 toR 3 , whereas here we additionally need that ifJ(π) =J(π ′ )thenJ ′ (π) =J ′ (π ′ )for all functionsR 2 on the path — this is what the extra conditions ensure. Theorem 3 is opaque, but intuitively, the cases whereR 1 cannot be simplified are those whereR 1 imposes many different equality constraints that are difficult to satisfy simultaneously. We can think 7 ofdim(F(Π))as measuring how diverse the behaviours of policies in policy setΠare. Having a less diverse policy set means that a given policy ordering imposes fewer constraints on the reward function, creating more potential for simplification. The technical conditions of this proof determine when the diversity ofΠis or is not sufficient to prohibit simplification, as measured bydim(Z 1 ∪·∪Z m ). ProjectingE i toZ i simply moves these spaces to the origin, so that we can compare the directions in which they vary (i.e. their span). By assumption,E i ∩E j =, butspan(Z i )∩span(Z j )will include the origin, and may also contain linear subspaces of dimension greater than 0. This is the case exactly when there are a pair of policies inE i and a pair of policies inE j that differ by the same visit counts, for example, when the environment contains an obstacle that could be circumnavigated in several different ways (with an impact on visit counts, but no impact on reward), and the policies inE i andE j both need to circumnavigate it before doing something else. Roughly speaking,dim(Z 1 ∪·∪Z m ) is large when either (i) we have very large and diverse sets of policies in ˆ Πthat get the same reward according toR, or (i) we have a large number of different sets of policies that get the same reward according toR, and where there are different kinds of diversity in the behaviour of the policies in each set. There are also intuitive special cases of Theorem 3. For example, as noted before, ifE i is a singleton thenZ i has no impact ondim(Z 1 ∪·∪Z m ). This implies the following corollary: Corollary 3.For any finite set of policies ˆ Π, any environment, and any reward functionR, if| ˆ Π|≥2 andJ(π)̸=J(π ′ )for allπ,π ′ ∈ ˆ Πthen there is a non-trivial simplification ofR. A natural question is whether any reward function is guaranteed to have a non-trivial simplification on the set of all deterministic policies. As it turns out, this is not the case. For concreteness, and to build intuition for this result, we examine the set of deterministic policies in a simpleMDP withS=0,1,A=0,1,T(s,a) =a,I=0 : 0.5,1 : 0.5,γ= 0.5. Denoteπ ij the policy that takes actionifrom state 0 and actionjfrom state 1. There are exactly four deterministic policies. We find that of the4! = 24possible policy orderings, 12 are realizable via some reward function. In each of those 12 orderings, exactly two policies (of the six available pairs of policies in the ordering) can be set to equal value without resulting in the trivial reward function (whichpair can be equated depends on the ordering in consideration). Attempting to set three policies equal always results in the trivial reward simplification. For example, given the orderingπ 00 ≤π 01 ≤π 11 ≤π 10 , the simplificationπ 00 =π 01 < π 11 < π 10 is represented byR= [ 0 3 2 1 ], whereR(s,a) =R[s,a]: for example, here taking action 1 from state 0 gives rewardR(0,1) = 3. But there is no reward function representing a non-trivial simplification of this ordering withπ 01 =π 11 . We develop and release a software suite to compute these results. Given an environment and a set of policies, it can calculate all policy orderings represented by some reward function. Also, for a given policy ordering, it can calculate all nontrivial simplifications and reward functions that represent them. For a link to the repository, as well as a full exploration of these policies, orderings, and simplifications, see Appendix D.3. 5.3 Unhackability in Infinite Policy Sets The results in Section 5.1 do not characterize unhackability for infinite policy sets that do not contain open sets. Here, we provide two examples of such policy sets; one of them admits unhackable reward pairs and the other does not. Consider policiesA,B,C, and reward functionsR 1 with J 1 (C)< J 1 (B)< J 1 (A)andR 2 withJ 2 (C) =J 2 (B)< J 2 (A). Policy setsΠ a =A∪λB+ (1−λ)C:λ∈[0,1]andΠ b =A∪λB+ (1−λ)C:λ∈[0,1]are depicted in Figure 5; the vertical axis represents policies’ values according toR 1 andR 2 . ForΠ a ,R 2 is a simplification of R 1 , but forΠ b , it is not, sinceJ 1 (X)< J 1 (Y)andJ 2 (X)> J 2 (Y). 6 Discussion We reflect on our results and identify limitations in Section 6.1. In Section 6.2, we discuss how our work can inform discussions about the appropriateness, potential risks, and limitations of using of reward functions as specifications of desired behavior. 8 (a)(b) Figure 5: Infinite policy sets that do not contain open sets sometimes allow simplification (a), but not always (b). Points A, B, C represent deterministic policies, while the bold lines between them represent stochastic policies. The y-axis gives the values of the policies according to reward functions R 1 andR 2 . We attempt to simplifyR 1 by rotating the reward function such thatJ 2 (B) =J 2 (C); in the figure, we instead (equivalently) rotate the triangle along the AB axis, leading to the red triangle. In (a),R 2 simplifiesR 1 , setting all policies along the BC segment equal in value (but still lower than A). In (b),R 2 swaps the relative value of policies X and Y (J 1 (X)< J 1 (Y) =J 2 (Y)< J 2 (X)) and so does not simplifyR 1 . 6.1 Limitations Our work has a number of limitations. We have only considered finite MDPs and Markov reward functions, leaving more general environments for future work. While we characterized hackability and simplification for finite policy sets, the conditions for simplification are somewhat opaque, and our characterization of infinite policy sets remains incomplete. As previously discussed, our definition of hackability is strict, arguably too strict. Nonetheless, we believe that understanding the consequences of this strict definition is an important starting point for further theoretical work in this area. The main issue with the strictness of our definition has to do with the symmetric nature of hackability. The existence of complex behaviors that yield low proxy reward and high true reward is much less concerning than the reverse, as these behaviors are unlikely to be discovered while optimizing the proxy. For example, it is very unlikely that our agent would solve climate change in the course of learning how to wash dishes. Note that the existence ofsimplebehaviors with low proxy reward and high true rewardisconcerning; these could arise early in training, leading us to trust the proxy, only to later see the true reward decrease as the proxy is further optimized. To account for this issue, future work should explore more realistic assumptions about the probability of encountering a given sequence of policies when optimizing the proxy, and measure hackability in proportion to this probability. We could allow for approximate unhackability by only considering pairs of policies ranked differently by the true and proxy reward functions as evidence of hacking iff their value according to the true reward function differs by more than someε. Probabilistic unhackability could be defined by looking at the number of misordered policies; this would seem to require making assumptions about the probability of encountering a given policy when optimizing the proxy. Finally, while unhackability is a guarantee that no hacking will occur,hackabilityis far from a guarantee of hacking. Extensive empirical work is necessary to better understand the factors that influence the occurrence and severity of reward hacking in practice. 6.2 Implications How should we specify our preferences for AI systems’ behavior? And how detailed a specification is required to achieve a good outcome? In reinforcement learning, the goal of maximizing (some) reward function is often taken for granted, but a number of authors have expressed reservations about 9 this approach (Gabriel, 2020; Dobbe et al., 2021; Hadfield-Menell et al., 2016b, 2017; Bostrom, 2014). Our work has several implications for this discussion, although we caution against drawing any strong conclusions due to the limitations mentioned in Section 6.1. One source of confusion and disagreement is the role of the reward function; it is variously considered as a means of specifying a task (Leike et al., 2018) or encoding broad human values (Dewey, 2011); such distinctions are discussed by Christiano (2019) and Gabriel (2020). We might hope to use Markov reward functions to specify narrow tasks without risking behavior that goes against our broad values. However, if we consider the “narrow task” reward function as a proxy for the true “broad values” reward function, our results indicate that this is not possible: these two reward functions will invariably be hackable. Such reasoning suggests that reward functions must instead encode broad human values, or risk being hacked. This seems challenging, perhaps intractably so, indicating that alternatives to reward optimization may be more promising. Potential alternatives include imitation learning (Ross et al., 2011), constrained RL (Szepesvári, 2020), quantilizers (Taylor, 2016), and incentive management (Everitt et al., 2019). Scholars have also criticized the assumption that human values can be encoded as rewards (Dobbe et al., 2021), and challenged the use of metrics more broadly (O’Neil, 2016; Thomas and Uminsky, 2022), citing Goodhart’s Law (Manheim and Garrabrant, 2018; Goodhart, 1975). A concern more specific to the optimization of reward functions is power-seeking (Turner et al., 2021; Bostrom, 2012; Omohundro, 2008). Turner et al. (2021) prove that optimal policies tend to seek power in most MDPs and for most reward functions. Such behavior could lead to human disempowerment; for instance, an AI system might disable its off-switch (Hadfield-Menell et al., 2016a). Bostrom (2014) and others have argued that power-seeking makes even slight misspecification of rewards potentially catastrophic, although this has yet to be rigorously established. Despite such concerns, approaches to specification based on learning reward functions remain popular (Fu et al., 2017; Stiennon et al., 2020; Nakano et al., 2021). So far, reward hacking has usually been avoidable in practice, although some care must be taken (Stiennon et al., 2020). Proponents of such approaches have emphasized the importance of learning a reward model in order to exceed human performance and generalize to new settings (Brown et al., 2020a; Leike et al., 2018). But our work indicates that such learned rewards are almost certainly hackable, and so cannot be safely optimized. Thus we recommend viewing such approaches as a means of learning a policy in a safe and controlled setting, which should then be validated before being deployed. 7 Conclusion Our work begins the formal study of reward hacking in reinforcement learning. We formally define hackability and simplification of reward functions, and show conditions for the (non-)existence of non-trivial examples of each. We find that unhackability is quite a strict condition, as the set of all policies never contains non-trivial unhackable pairs of reward functions. Thus in practice, reward hacking must be prevented by limiting the set of possible policies, or controlling (e.g. limiting) optimization. Alternatively, we could pursue approaches not based on optimizing reward functions. References Abel, D., Dabney, W., Harutyunyan, A., Ho, M. K., Littman, M., Precup, D., and Singh, S. (2021). On the Expressivity of Markov Reward.Advances in Neural Information Processing Systems, 34. Amodei, D., Christiano, P., and Ray, A. (2017). Learning from Human Preferences. OpenAIhttps: //openai.com/blog/deep-reinforcement-learning-from-human-preferences/. Bird, J. and Layzell, P. (2002). The evolved radio and its implications for modelling the evolution of novel sensors. InProceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600), volume 2, pages 1836–1841. IEEE. Bostrom, N. (2012). The superintelligent will: Motivation and instrumental rationality in advanced artificial agents.Minds and Machines, 22(2):71–85. Bostrom, N. (2014). Superintelligence: Paths, Dangers, Strategies. 10 Brown, D. S., Goo, W., and Niekum, S. (2020a). Better-than-demonstrator imitation learning via automatically-ranked demonstrations. InConference on robot learning, pages 330–359. PMLR. Brown, D. S., Schneider, J., Dragan, A. D., and Niekum, S. (2020b). Value Alignment Verification. CoRR, abs/2012.01557. Christiano,P. (2019).Ambitious vs. narrow value learning.AI Alignment Forum.https://w.alignmentforum.org/posts/SvuLhtREMy8wRBzpC/ ambitious-vs-narrow-value-learning. Clark, J. and Amodei, D. (2016). Faulty Reward Functions in the Wild. OpenAI Codexhttps: //openai.com/blog/faulty-reward-functions/. Dewey, D. (2011). Learning What to Value. In Schmidhuber, J., Thórisson, K. R., and Looks, M., editors,Artificial General Intelligence: 4th International Conference, AGI 2011, pages 309–314, Berlin, Heidelberg. Springer Berlin Heidelberg. Dobbe, R., Gilbert, T. K., and Mintz, Y. (2021). Hard Choices in Artificial Intelligence.CoRR, abs/2106.11022. Everitt, T., Hutter, M., Kumar, R., and Krakovna, V. (2021). Reward tampering problems and solutions in reinforcement learning: A causal influence diagram perspective.Synthese, 198(27):6435–6467. Everitt, T., Krakovna, V., Orseau, L., Hutter, M., and Legg, S. (2017). Reinforcement learning with a corrupted reward channel.arXiv preprint arXiv:1705.08417. Everitt, T., Ortega, P. A., Barnes, E., and Legg, S. (2019). Understanding agent incentives using causal influence diagrams. Part I: Single action settings.arXiv preprint arXiv:1902.09980. Fu, J., Luo, K., and Levine, S. (2017). Learning robust rewards with adversarial inverse reinforcement learning.arXiv preprint arXiv:1710.11248. Gabriel, I. (2020). Artificial intelligence, values, and alignment.Minds and machines, 30(3):411–437. Golden, D. (2001). Glass Floor: Colleges Reject Top Applicants, Accepting Only the Stu- dents Likely to Enroll.The Wall Street Journal.https://w.wsj.com/articles/ SB991083160294634500. Goodhart, C. A. (1975). Problems of monetary management: the UK experience. In of Australia, R. B., editor,Papers in monetary economics. Reserve Bank of Australia. Hadfield-Menell, D., Dragan, A., Abbeel, P., and Russell, S. (2016a). The Off-Switch Game.CoRR, abs/1611.08219. Hadfield-Menell, D., Dragan, A. D., Abbeel, P., and Russell, S. J. (2016b). Cooperative Inverse Reinforcement Learning.CoRR, abs/1606.03137. Hadfield-Menell, D., Milli, S., Abbeel, P., Russell, S. J., and Dragan, A. (2017). Inverse reward design.Advances in neural information processing systems, 30. Ibarz, B., Leike, J., Pohlen, T., Irving, G., Legg, S., and Amodei, D. (2018). Reward learning from human preferences and demonstrations in atari.Advances in neural information processing systems, 31. Krakovna, V., Orseau, L., Kumar, R., Martic, M., and Legg, S. (2018). Penalizing side effects using stepwise relative reachability.CoRR, abs/1806.01186. Krakovna, V., Uesato, J., Mikulik, V., Rahtz, M., Everitt, T., Kumar, R., Kenton, Z., Leike, J., and Legg, S. (2020). Specification gaming: the flip side of AI ingenuity. Kumar, R., Uesato, J., Ngo, R., Everitt, T., Krakovna, V., and Legg, S. (2020). Realab: An embedded perspective on tampering.arXiv preprint arXiv:2011.08820. Leike, J., Krueger, D., Everitt, T., Martic, M., Maini, V., and Legg, S. (2018). Scalable agent alignment via reward modeling: a research direction.CoRR, abs/1811.07871. 11 Manheim, D. and Garrabrant, S. (2018). Categorizing Variants of Goodhart’s Law.CoRR, abs/1803.04585. Nakano, R., Hilton, J., Balaji, S., Wu, J., Ouyang, L., Kim, C., Hesse, C., Jain, S., Kosaraju, V., Saunders, W., et al. (2021). WebGPT: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332. Ng, A. Y., Harada, D., and Russell, S. (1999). Policy invariance under reward transformations: Theory and application to reward shaping. InIcml, volume 99, pages 278–287. Ng, A. Y., Russell, S. J., et al. (2000). Algorithms for inverse reinforcement learning. InIcml, volume 1, page 2. Omohundro, S. M. (2008). The basic AI drives. O’Neil, C. (2016).Weapons of math destruction: How big data increases inequality and threatens democracy. Crown Publishing Group. Pan, A., Bhatia, K., and Steinhardt, J. (2022). The Effects of Reward Misspecification: Mapping and Mitigating Misaligned Models.arXiv preprint arXiv:2201.03544. Ross, S., Gordon, G., and Bagnell, D. (2011). A reduction of imitation learning and structured prediction to no-regret online learning. InProceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627–635. JMLR Workshop and Conference Proceedings. Stiennon, N., Ouyang, L., Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. (2020). Learning to summarize with human feedback.Advances in Neural Information Processing Systems, 33:3008–3021. Sutton, R. S. and Barto, A. G. (2018).Reinforcement learning: An introduction. MIT press. Szepesvári, C. (2020). Constrained MDPs and the reward hypothesis.http://readingsml. blogspot.com/2020/03/constrained-mdps-and-reward-hypothesis.html. Taylor, J. (2016). Quantilizers: A safer alternative to maximizers for limited optimization. In Workshops at the Thirtieth AAAI Conference on Artificial Intelligence. Thomas, R. L. and Uminsky, D. (2022). Reliance on metrics is a fundamental challenge for AI. Patterns, 3(5):100476. Thrun, S. and Schwartz, A. (1993). Issues in using function approximation for reinforcement learning. InProceedings of the 1993 Connectionist Models Summer School Hillsdale, NJ. Lawrence Erlbaum, volume 6. Turner, A. M., Hadfield-Menell, D., and Tadepalli, P. (2019). Conservative Agency via Attainable Utility Preservation.CoRR, abs/1902.09725. Turner, A. M., Smith, L., Shah, R., Critch, A., and Tadepalli, P. (2021). Optimal Policies Tend to Seek Power.Advances in Neural Information Processing Systems. Uesato, J., Kumar, R., Krakovna, V., Everitt, T., Ngo, R., and Legg, S. (2020). Avoiding tampering incentives in deep rl via decoupled approval.arXiv preprint arXiv:2011.08827. Zhang, B., Rajan, R., Pineda, L., Lambert, N., Biedenkapp, A., Chua, K., Hutter, F., and Calandra, R. (2021). On the Importance of Hyperparameter Optimization for Model-based Reinforcement Learning.CoRR, abs/2102.13651. Zhuang, S. and Hadfield-Menell, D. (2020). Consequences of misaligned AI.Advances in Neural Information Processing Systems, 33:15763–15773. Ziebart, B. D. (2010).Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University. 12 Checklist 1. For all authors... (a)Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope? [Yes] (b) Did you describe the limitations of your work? [Yes] (c)Did you discuss any potential negative societal impacts of your work? [Yes] See Section 6.2 (d)Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] 2. If you are including theoretical results... (a) Did you state the full set of assumptions of all theoretical results? [Yes] (b) Did you include complete proofs of all theoretical results? [Yes] Some of the proofs are in the Appendix. 3. If you ran experiments... (a)Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] The code and instructions for running it are available in the supplementary materials. The code does not use any datasets. (b)Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A] We do not perform model training in this work. (c)Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A] (d)Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] No compute beyond a personal laptop (with integrated graphics) was used. 4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... (a)If your work uses existing assets, did you cite the creators? [N/A] The codebase was written from scratch. (b) Did you mention the license of the assets? [N/A] (c) Did you include any new assets either in the supplemental material or as a URL? [Yes] The codebase is available in the supplemental material. (d)Did you discuss whether and how consent was obtained from people whose data you’re using/curating? [N/A] (e)Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] 5. If you used crowdsourcing or conducted research with human subjects... (a)Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] (c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] 13 A Overview Section B contains proofs of the main theoretical results. Section D expands on examples given in the main text. Section E presents an unhackability diagram for a generic set of three policiesa,b,c; Section F shows a simplification diagram of the same policies. B Proofs Before proving our results, we restate assumptions and definitions. First, recall the preliminaries from Section 4.1, and in particular, that we useF: Π→R |S||A| to denote the embedding of policies into Euclidean space via their discounted state-action visit counts, i.e.; F(π)[s,a] = ∞ X t=0 γ t P(S t =s,A t =a). Given a reward functionR, let ⃗ R∈R |S||A| be the vector where ⃗ R[s,a] =E S ′ ∼T(s,a) [R(s,a,S ′ )]. Note thatJ(π) =F(π)· ⃗ R. We sayR 1 andR 2 areequivalenton a set of policiesΠifJ 1 andJ 2 induce the same ordering ofΠ, and thatRistrivialonΠifJ(π) =J(π ′ )for allπ,π ′ ∈Π. We also have the following definitions from Sections 4 and 5: Definition 1.A pair of reward functionsR 1 ,R 2 arehackablerelative to policy setΠand an environment(S,A,T,I,,γ)if there existπ,π ′ ∈Πsuch that J 1 (π)< J 1 (π ′ ) &J 2 (π)> J 2 (π ′ ), else they areunhackable. Definition 2.R 2 is asimplificationofR 1 relative to policy setΠif for allπ,π ′ ∈Π, J 1 (π)< J 1 (π ′ ) =⇒J 2 (π)≤J 2 (π ′ ) &J 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ ) and there existπ,π ′ ∈Πsuch thatJ 2 (π) =J 2 (π ′ )butJ 1 (π)̸=J 1 (π ′ ). Moreover, ifR 2 is trivial then we say that this is atrivial simplification. Note that these definitions only depend on the policy orderings associated withR 2 andR 1 , and so we can (and do) also speak of (ordered) pairs of policy orderings being simplifications or hackable. We also make use of the following definitions: Definition 3.A (stationary) policyπisε-suboptimal ifJ(π)≥J(π ⋆ )−ε, whereε >0 Definition 4.A (stationary) policyπisδ-deterministic if∀s∈S∃a∈A:P(π(s) =a)≥δ, where δ <1. B.1 Non-trivial Unhackability Requires Restricting the Policy Set Formally, a set of (stationary) policies ̇ ΠisopenifV( ̇ Π)is open in the smallest affine space that containsV(Π), whereΠis the set of all stationary policies. Note that this space is|S|(|A|−1)- dimensional, since all action probabilities sum to 1. We require two more propositions for the proof of this lemma. Proposition 1.If ̇ Πis open thenFis injective on ̇ Π. Proof.First note that, sinceπ(a|s)≥0, we have that if ̇ Πis open thenπ(a|s)>0for alls,afor allπ∈ ̇ Π. In other words, all policies in ̇ Πtake each action with positive probability in each state. Now supposeF(π) =F(π ′ )for someπ,π ′ ∈ ̃ Π. Next, definew π as w π (s) = ∞ X t=0 γ t P τ∼π (S t =s). 14 Note that ifF(π) =F(π ′ )thenw π =w π ′ , and moreover that F(π)[s,a] =w π (s)π(a|s). Next, sinceπtakes each action with positive probability in each state, we have thatπvisits every state with positive probability. This implies thatw π (s)̸= 0for alls, which means that we can expressπas π(a|s) = F(π)[s,a] w π (s) . This means that ifF(π) =F(π ′ )for someπ,π ′ ∈ ̃ Πthenπ=π ′ . Note thatFisnotinjective onΠ; if there is some statesthatπreaches with probability0, then we can alter the behaviour ofπatswithout changingF(π). But every policy in an open policy set ̇ Πvisits every state with positive probability, which then makesFinjective. In fact, Proposition 1 straightforwardly generalises to the set of all policies that visit all states with positive probability (although this will not be important for our purposes). Proposition 2.Im(F)is located in an affine subspace with|S|(|A|−1)dimensions. Proof. To show thatIm(F)is located in an affine subspace with|S|(|A|−1)dimensions, first note that X s,a F(π)[s,a] = ∞ X t=0 γ t = 1 1−γ for allπ. That is,Im(F)is located in an affine space of points with a fixedℓ 1 -norm, and this space does not contain the origin. Next, note thatJ(π) =F(π)· ⃗ R. This means that if knowing the value ofJfor allπdetermines ⃗ Rmodulo at leastnfree variables, thenIm(F)contains at most|S||A|−nlinearly independent vectors. Next recallpotential shaping(Ng et al., 1999). In brief, given a reward functionRand a potential functionΦ :S→R, we can define ashaped reward functionR ′ by R ′ (s,a,s ′ ) =R(s,a,s ′ ) +γΦ(s ′ )−Φ(s), or, alternatively, if we wishR ′ to be defined over the domainS×A, R ′ (s,a) =R(s,a) +γE S ′ ∼T(s,a) [Φ(S ′ )]−Φ(s). In either case, it is possible to show that ifR ′ is produced by shapingRwithΦ, andE S 0 ∼I [Φ(S 0 )] = 0, thenJ(π) =J ′ (π)for allπ. This means that knowing the value ofJ(π)for allπdetermines ⃗ R modulo at least|S|−1free variables, which means thatIm(F)contains at most|S||A|−(|S|−1) = |S|(|A|−1) + 1 linearly independent vectors. Since the smallest affine space that containsIm(F) doesnotcontain the origin, this in turn means thatIm(F)is located in an affine subspace with =|S|(|A|−1) + 1−1 =|S|(|A|−1)dimensions. Lemma 1.In anyMDP , if ̇ Πis an open set of policies, thenF( ̇ Π)is open inR |S|(|A|−1) , and Fis a homeomorphism betweenV( ̇ Π)andF( ̇ Π). Proof.By the Invariance of Domain Theorem, if 1.Uis an open subset ofR n , and 2.f:U→R n is an injective continuous map, thenf(U)is open inR n andfis a homeomorphism betweenUandf(U). We will show thatFand ̇ Πsatisfy the requirements of this theorem. We begin by noting that ̇ Πcan be represented as a set of points inR |S|(|A|−1) . First, project ̇ Πinto R |S||A| viaV. Next, since P a∈A π(a|s) = 1for alls,Im(V)is in fact located in an affine subspace with|S|(|A|−1)dimensions, which directly gives a representation inR |S|(|A|−1) . Concretely, this represents each policyπas a vectorV(π)with one entry containing the valueπ(a|s)for each 15 state-action pairs,a, but with one action left out for each state, since this value can be determined from the remaining values. We will assume that ̇ Πis embedded inR |S|(|A|−1) in this way. By assumption,V( ̇ Π)is an open set inR |S|(|A|−1) . Moreover, by Proposition 2, we have thatFis (isomorphic to) a mapping ̇ Π→R |S|(|A|−1) . By Proposition 1, we have thatFis injective on ̇ Π. Finally,Fis continuous; this can be seen from its definition. We can therefore apply the Invariance of Domain Theorem, and obtain thatF( ̇ Π)is open inR |S|(|A|−1) , and thatFis a homeomorphism betweenV( ̇ Π)andF( ̇ Π). Figure 6: Illustration of the various realizable feature counts used in the proof of Theorem 1. Theorem 1.In anyMDP , if ˆ Πcontains an open set, then any pair of reward functions that are unhackable and non-trivial on ˆ Πare equivalent on ˆ Π. Proof.LetR 1 andR 2 be any two unhackable and non-trivial reward functions. We will show that, for anyπ,π ′ ∈ ˆ Π, we haveJ 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ ), and thus, by symmetry, J 1 (π) =J 1 (π ′ )⇐⇒J 2 (π) =J 2 (π ′ ). SinceR 1 andR 2 are unhackable, this further means that they have exactly the same policy order, i.e. that they are equivalent. Choose two arbitraryπ,π ′ ∈ ˆ ΠwithJ 1 (π) =J 1 (π ′ )and letf . =F(π),f ′ . =F(π ′ ) . The proof has 3 steps: 1. We find analogues forfandf ′ , ̃ fand ̃ f ′ , within the same open ball inF( ˆ Π). 2. We show that the tangent hyperplanes of ⃗ R 1 and ⃗ R 2 at ̃ f must be equal to prevent neighbors of ̃ ffrom makingR 1 andR 2 hackable. 3. We use linearity to show that this implies thatJ 2 (π) =J 2 (π ′ ). Step 1:By assumption, ˆ Πcontains an open set ̇ Π. Letˆπbe some policy in ̇ Π, and let ˆ f . =F(ˆπ). Since ̇ Πis open, Lemma 1 implies thatF( ̇ Π)is open inR |S|(|A|−1) . This means that, ifv,v ′ are the vectors such that ˆ f+v=f and ˆ f+v ′ =f ′ , then there is a positive but sufficiently smallδsuch that ̃ f . = ˆ f+δvand ̃ f ′ . = ˆ f+δv ′ both are located inF( ̇ Π), see Figure 6. This further implies that there are policies ̃π, ̃ π ′ ∈ ̇ Πsuch thatF( ̃π) = ̃ fandF( ̃ π ′ ) = ̃ f ′ . Step 2:Recall thatJ(π) =F(π)· ⃗ R.SinceR 1 is non-trivial on ˆ Π, it induces a (|S|(|A|−1)−1)-dimensional hyperplane tangent to ⃗ R 1 corresponding to all pointsx∈R |S|(|A|−1) such thatx· ⃗ R 1 = ̃ f· ⃗ R 1 , and similarly forR 2 . Call these hyperplanesH 1 andH 2 , respectively. Note that ̃ fis contained in bothH 1 andH 2 . Next supposeH 1 ̸=H 2 . Then, we would be able to find a pointf 12 ∈F( ̇ Π), such thatf 12 · ⃗ R 1 > ̃ f· ⃗ R 1 butf 12 · ⃗ R 2 < ̃ f· ⃗ R 2 . This, in turn, means that there is a policyπ 12 ∈ ̇ Πsuch thatF(π 12 ) =f 12 , 16 and such thatJ 1 (π 12 )> J 1 ( ̃π)butJ 2 (π 12 )< J 2 ( ̃π). SinceR 1 andR 2 are unhackable, this is a contradiction. ThusH 1 =H 2 . Step 3:SinceJ 1 (π) =J 1 (π ′ ), we have thatf· ⃗ R 1 =f ′ · ⃗ R 1 . By linearity, this implies that ̃ f· ⃗ R 1 = ̃ f ′ · ⃗ R 1 ; we can see this by expanding ̃ f= ˆ f+δvand ̃ f ′ = ˆ f+δv ′ . This means that ̃ f ′ ∈H 1 . Now, sinceH 1 =H 2 , this means that ̃ f ′ ∈H 2 , which in turn implies that ̃ f· ⃗ R 2 = ̃ f ′ · ⃗ R 2 . By linearity, this then further implies thatf· ⃗ R 2 =f ′ · ⃗ R 2 , and hence thatJ 2 (π) =J 2 (π ′ ). Since π,π ′ were chosen arbitrarily, this means thatJ 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ ). Corollary 1.In anyMDP , any pair of reward functions that are unhackable and non-trivial on the set of all (stationary) policiesΠare equivalent onΠ. Proof.This corollary follows from Theorem 1, if we note that the set of all policies does contain an open set. This includes, for example, the set of all policies in anε-ball around the policy that takes all actions with equal probability in each state. Corollary 2.In anyMDP , any pair of reward functions that are unhackable and non-trivial on the set of allε-suboptimal policies (ε >0)Π ε are equivalent onΠ ε , and any pair of reward functions that are unhackable and non-trivial on the set of allδ-deterministic policies (δ <1)Π δ are equivalent onΠ δ . Proof.To prove this, we will establish that bothΠ ε andΠ δ contain open policy sets, and then apply Theorem 1. Let us begin withΠ δ . First, letπbe some deterministic policy, and letπ ε be the policy that in each state with probability1−εtakes the same action asπ, and otherwise samples an action uniformly. Then ifδ < ε <1,π ε is the center of an open ball inΠ δ . ThusΠ δ contains an open set, and we can apply Theorem 1. ForΠ ε , letπ ⋆ be an optimal policy, and apply an analogous argument. B.2 Finite Policy Sets Theorem 2.For anyMDP , any finite set of policies ˆ Π containing at least twoπ,π ′ such that F(π)̸=F(π ′ ), and any reward functionR 1 , there is a non-trivial reward functionR 2 such thatR 1 andR 2 are unhackable but not equivalent. Proof. IfR 1 is trivial, then simply choose any non-trivialR 2 . Otherwise, the proof proceeds by finding a path from ⃗ R 1 to− ⃗ R 1 , and showing that there must be an ⃗ R 2 on this path such thatR 2 is non-trivial and unhackable with respect toR 1 , but not equivalent toR 1 . The key technical difficulty is to show that there exists a continuous path fromR 1 to−R 1 inR |S||A| that does not include any trivial reward functions. Once we’ve established that, we can simply look for the first place where an inequality is reversed – because of continuity, it first becomes an equality. We call the reward function at that pointR 2 , and note thatR 2 is unhackable wrtR 1 and not equivalent toR 1 . We now walk through the technical details of these steps. First, note thatJ(π) =F(π)· ⃗ Ris continuous in ⃗ R. This means that ifJ 1 (π)> J 2 (π ′ )then there is a unique first vector ⃗ R 2 on any path from ⃗ R 1 to− ⃗ R 1 such thatF(π)· ⃗ R 2 ̸>F(π)· ⃗ R 2 , and for this vector we have thatF(π)· ⃗ R 2 =F(π)· ⃗ R 2 . Since ˆ Πis finite, and sinceR 1 is not trivial, this means that on any path from ⃗ R 1 to− ⃗ R 1 there is a unique first vector ⃗ R 2 such thatR 2 is not equivalent to R 1 , and thenR 2 must also be a unhackable with respect toR 1 . It remains to show that there is a path from ⃗ R 1 to− ⃗ R 1 such that no vector along this path corresponds to a trivial reward function. Once we have such a path, the argument above implies thatR 2 must be a non-trivial reward function that is unhackable with respect toR 1 . We do this using a dimensionality argument. IfRis trivial on ˆ Π, then there is somec∈Rsuch thatF(π)· ⃗ R=cfor allπ∈ ˆ Π. This means that ifF( ˆ Π)has at leastdlinearly independent vectors, then the set of all such vectors ⃗ R forms a linear subspace with at most|S||A|−ddimensions. Now, since ˆ Π contains at least two π,π ′ such thatF(π)̸=F(π ′ ), we have thatF( ˆ Π)has at least2linearly independent vectors, and 17 hence that the set of all reward functions that are trivial on ˆ Πforms a linear subspace with at most |S||A|−2dimensions. This means that there must exist a path from ⃗ R 1 to− ⃗ R 1 that avoids this subspace, since only a hyperplane (with dimension|S||A|−1) can splitR |S||A| into two disconnected components. Theorem 3.Let ˆ Πbe a finite set of policies, andRa reward function. The following procedure determines if there exists a non-trivial simplification ofRin a givenMDP : 1. LetE 1 ...E m be the partition of ˆ Πwhereπ,π ′ belong to the same set iffJ(π) =J(π ′ ). 2. For each such setE i , select a policyπ i ∈E i and letZ i be the set of vectors that is obtained by subtractingF(π i )from each element ofF(E i ). Then there is a non-trivial simplification ofRiffdim(Z 1 ∪·∪Z m )≤dim(F( ˆ Π))−2, where dim(S)is the number of linearly independent vectors inS. Proof.This proof uses a similar proof strategy as Theorem 2. However, in addition to avoiding trivial reward functions on the path from ⃗ R 1 to− ⃗ R 1 , we must also ensure that we stay within the “equality-preserving space”, to be defined below. First recall thatF( ˆ Π)is a set of vectors inR |S||A| . Ifdim(F( ˆ Π)) =Dthen these vectors are located in aD-dimensional linear subspace. Therefore, we will considerF( ˆ Π)to be a set of vectors inR D . Next, recall that any reward functionRinduces a linear functionLonR D , such thatJ=L◦F, and note that there is aD-dimensional vector ⃗ R that determines theorderingthatRinduces over all points inR D . To determine thevaluesofJon all points inR D we would need a(D+ 1)-dimensional vector, but to determine theordering, we can ignore the height of the function. In other words, L(x) =x· ⃗ R+L( ⃗ 0), for anyx∈R D . Note that this is a different vector representation of reward functions than that which was used in Theorem 2 and before. SupposeR 2 is a reward function such that ifJ 1 (π) =J 1 (π ′ )thenJ 2 (π) =J 2 (π ′ ), for allπ,π ′ ∈ ˆ Π. This is equivalent to saying thatL 2 (F(π)) =L 2 (F(π ′ ))ifπ,π ′ ∈E i for someE i . By the properties of linear functions, this implies that ifF(E i )containsd i linearly independent vectors then it specifies a(d i −1)-dimensional affine spaceS i such thatL 2 (x) =L 2 (x ′ )for all pointsx,x ′ ∈S i . Note that this is the smallest affine space which contains all points inE i . Moreover,L 2 is also constant for any affine space ̄ S i paralleltoS i . Formally, we say that ̄ S i is parallel toS i if there is a vectorzsuch that for anyy∈ ̄ S i there is anx∈S i such thaty=x+z. From the properties of linear functions, if L 2 (x) =L 2 (x ′ )thenL 2 (x+z) =L 2 (x ′ +z). Next, from the transitivity of equality, if we have two affine spaces ̄ S i and ̄ S j , such thatL 2 is constant over each of ̄ S i and ̄ S j , and such that ̄ S i and ̄ S j intersect, thenL 2 is constant over all points in ̄ S i ∪ ̄ S j . From the properties of linear functions, this then implies thatL 2 is constant over all points in the smallest affine space ̄ S i ⊗ ̄ S j containing ̄ S i and ̄ S j , given by combining the linearly independent vectors in ̄ S i and ̄ S j . Note that ̄ S i ⊗ ̄ S j has betweenmax(d i ,d j )and(d i +d j −1)dimensions. In particular, since the affine spaces ofZ 1 ...Z m intersect (at the origin), and sinceL 2 is constant over these spaces, we have thatL 2 must be constant for all points in the affine spaceZwhich is the smallest affine space containingZ 1 ∪·∪Z m . That is, ifR 2 is a reward function such that J 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ )for allπ,π ′ ∈ ˆ Π, thenL 2 is constant overZ. Moreover, ifL 2 is constant overZthenL 2 is also constant over each ofE 1 ...E m , since each ofE 1 ...E m is parallel toZ. This means thatR 2 satisfies thatJ 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ )for all π,π ′ ∈ ˆ Πif and only ifL 2 is constant overZ. Ifdim(Z) =D ′ then there is a linear subspace withD−D ′ dimensions, which contains the (D- dimensional) vector ⃗ R 2 of any reward functionR 2 whereJ 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ )for π,π ′ ∈ ˆ Π. This is becauseR 2 is constant overZif and only if ⃗ R 2 ·v= 0for allv∈Z. Then ifZ containsD ′ linearly independent vectorsv i ...v D ′ , then the solutions to the corresponding system of linear equations form a(D−D ′ )dimensional subspace ofR D . Call this space theequality-preserving space. Next, note thatR 2 is trivial on ˆ Πif and only if ⃗ R 2 is the zero vector ⃗ 0. Now we show that if the conditions are not satisfied, then there is no non-trivial simplification. SupposeD ′ ≥D−1, and thatR 2 is a simplification ofR 1 . Note that ifR 2 simplifiesR 1 then 18 ⃗ R 2 is in the equality-preserving space. Now, ifD ′ =DthenL 2 (andL 1 ) must be constant for all points inR D , which implies thatR 2 (andR 1 ) are trivial on ˆ Π. Next, ifD ′ =D−1then the equality-preserving space is one-dimensional. Note that we can always preserve all equalities of R 1 byscalingR 1 by a constant factor. That is, ifR 2 =c·R 1 for some (possibly negative)c∈R thenJ 1 (π) =J 1 (π ′ ) =⇒J 2 (π) =J 2 (π ′ )for allπ,π ′ ∈ ˆ Π. This means that the parameter which corresponds to the dimension of the equality-preserving space in this case must be the scaling of ⃗ R 2 . However, the only simplification ofR 1 that is obtainable by uniform scaling is the trivial simplification. This means that ifD ′ ≥D−1thenR 1 has no non-trivial simplifications on ˆ Π. For the other direction, supposeD ′ ≤D−2. Note that this implies thatR 1 is not trivial. Let R 3 =−R 1 . Now both ⃗ R 1 and ⃗ R 3 are located in the equality-preserving space. Next, since the equality-preserving space has at least two dimensions, this means that there is a continuous path from ⃗ R 1 to ⃗ R 3 through the equality-preserving space that does not pass the origin. Now, note that J i (π) =F(π)· ⃗ R i is continuous in ⃗ R i . This means that there, on the path from ⃗ R 1 to ⃗ R 3 is a first vector ⃗ R 2 such thatF(π)· ⃗ R 2 =F(π ′ )· ⃗ R 2 butF(π)· ⃗ R 1 ̸=F(π ′ )· ⃗ R 1 for someπ,π ′ ∈ ˆ Π. Let R 2 be a reward function corresponding to ⃗ R 2 . Since ⃗ R 2 is not ⃗ 0, we have thatR 2 is not trivial on ˆ Π . Moreover, since ⃗ R 2 is in the equality-preserving space, and sinceF(π)· ⃗ R 2 =F(π ′ )· ⃗ R 2 but F(π)· ⃗ R 1 ̸=F(π ′ )· ⃗ R 1 for someπ,π ′ ∈ ˆ Π, we have thatR 2 is a non-trivial simplification ofR 1 . Therefore, ifD ′ ≤D−2then there exists a non-trivial simplification ofR 1 . We have thus proven both directions, which completes the proof. Corollary 3.For any finite set of policies ˆ Π, any environment, and any reward functionR, if| ˆ Π|≥2 andJ(π)̸=J(π ′ )for allπ,π ′ ∈ ˆ Π, then there is a non-trivial simplification ofR. Proof. Note that ifE i is a singleton set thenZ i = ⃗ 0. Hence, if eachE i is a singleton set then dim(Z 1 ∪·∪Z m )= 0. If ˆ Πcontains at least twoπ,π ′ , andJ(π)̸=J(π ′ ), thenF(π)̸=F(π ′ ). This means thatdim(F( ˆ Π))≥2. Thus the conditions of Theorem 3 are satisfied. C Any Policy Can Be Made Optimal In this section, we show that any policy is optimal under some reward function. Proposition 3.For any rewardless MDP(S,A,T,I,,γ)and any policyπ, there exists a reward functionRsuch thatπis optimal in the corresponding MDP(S,A,T,I,R,γ). Proof.LetR(s,a,s ′ ) = 0ifa∈Support(π(s)), and−1otherwise. This shows that any policy is rationalised by some reward function in any environment. Any policy that gives0probability to any action whichπtakes with0probability is optimal under this construction. This means that ifπis deterministic, then it will be the only optimal policy in(S,A,T,I,R,γ). D Examples In this section, we take a closer look at two previously-seen examples: the two-stateMDP the cleaning robot. D.1 Two-stateMDP Let us explore in more detail the two-state system introduced in the main text. We decsribe this infinite-horizonMDP Table 1. We denoteπ ij (i,j∈ 0,1) the policy which takes actioniwhen in state 0 and actionjwhen in state 1. This gives us four possible deterministic policies: π 00 ,π 01 ,π 10 ,π 11 . 19 StatesS=0,1 ActionsA=0,1 DynamicsT(s,a) =afors∈S,a∈A Initial state distributionPr(start ins) = 0.5fors∈S Discount factorγ= 0.5 Table 1: The two-stateMDP consideration. There are4! = 24ways of ordering these policies with strict inequalities. Arbitrarily settingπ 00 < π 11 breaks a symmetry and reduces the number of policy orderings to 12. When a policy ordering can be derived from some reward functionR, we say thatRrepresentsit, and that the policy ordering is representable. Of these 12 policy orderings with strict inequalities, six are representable: π 00 < π 01 < π 10 < π 11 , π 00 < π 01 < π 11 < π 10 , π 00 < π 10 < π 01 < π 11 , π 01 < π 00 < π 11 < π 10 , π 10 < π 00 < π 01 < π 11 , π 10 < π 00 < π 11 < π 01 . Simplification in this environment is nontrivial – given a policy ordering, it is not obvious which strict inequalities can be set to equalities such that there is a reward function which represents the new ordering. Through a computational approach (see Section D.3) we find the following representable orderings, each of which is a simplification of one of the above strict orderings. π 00 =π 01 < π 11 < π 10 , π 00 =π 10 < π 01 < π 11 , π 00 < π 01 =π 10 < π 11 , π 01 < π 00 =π 11 < π 10 , π 10 < π 00 =π 11 < π 01 , π 00 < π 01 < π 10 =π 11 , π 10 < π 00 < π 01 =π 11 , π 00 =π 01 =π 10 =π 11 . Furthermore, for this environment, we find that any reward function which sets the value of three policies equal necessarily forces the value of the fourth policy to be equal as well. D.2 Cleaning robot example Recall the cleaning robot example in which a robot can choose to clean a combination of three rooms, and receives a nonnegative reward for each room cleaned. This setting can be thought of as a single-step eight-armed bandit with special reward structure. D.2.1 Hackability We begin our exploration of this environment with a statement regarding exactly when two policies are hackable. In fact, the proposition is slightly more general, extending to an arbitrary (finite) number of rooms. Proposition 4.Consider a cleaning robot which can cleanNdifferent rooms, and identify each room with a unique index in 1, . . . , N. Cleaning roomigives rewardr(i)≥0. Cleaning multiple rooms gives reward equal to the sum of the rewards of the rooms cleaned. The value of a policyπ S which cleans a collection of roomsSis the sum of the rewards corresponding to the rooms cleaned: J(π S ) = P i∈S r(i). For roomi, the true reward function assigns a valuer true (i), while the proxy reward function assigns it rewardr proxy (i). The proxy reward is hackable with respect to the true 20 reward if and only if there are two sets of roomsS 1 ,S 2 such that P i∈S 1 r proxy (i)< P i∈S 2 r proxy (i) and P i∈S 1 r true (i)> P i∈S 2 r true (i). Proof.We show the two directions of the double implication. ⇐Suppose there are two sets of roomsS 1 ,S 2 satisfying P i∈S 1 r proxy (i)< P i∈S 2 r proxy (i) and P i∈S 1 r true (i)> P i∈S 2 r true (i). The policiesπ S i =“clean exactly the rooms inS i ” fori∈1,2demonstrate thatr proxy ,r true are hackable. To see this, remember thatJ(π S ) = P i∈S r(i). Combining this with the premise immediately givesJ proxy (π S 1 )< J proxy (π S 2 ) andJ true (π S 1 )> J true (π S 2 ). ⇒Ifr proxy ,r true are hackable, then there must be a pair of policiesπ 1 ,π 2 such thatJ proxy (π 1 )< J proxy (π 2 )andJ true (π 1 )> J true (π 2 ). LetS 1 be the set of rooms cleaned byπ 1 andS 2 be the set of rooms cleaned byπ 2 . Again remembering thatJ(π S ) = P i∈S r(i)immediately gives us that P i∈S 1 r proxy (i)< P i∈S 2 r proxy (i)and P i∈S 1 r true (i)> P i∈S 2 r true (i). In the main text, we saw two intuitive ways of modifying the reward function in the cleaning robot example: omitting information and overlooking fine details. Unfortunately, there is no obvious mapping of Proposition 4 onto simple rules concerning how to safely omit information or overlook fine details: it seems that one must resort to ensuring that no two sets of rooms satisfy the conditions for hackability described in the proposition. D.2.2 Simplification We now consider simplification in this environment. Since we know the reward for cleaning each room is nonnegative, there will be some structure underneath all the possible orderings over the policies. This structure is shown in Figure 7: regardless of the value assigned to each room, a policy at the tail of an arrow can only be at most as good as a policy at the head of the arrow. [0, 0, 0] [0, 0, 1] [0, 1, 0] [1, 0, 0] [0, 1, 1] [1, 0, 1] [1, 1, 0] [1, 1, 1] Figure 7: The structure underlying all possible policy orderings (assuming nonnegative room value). The policy at the tail of the arrow is at most as good as the policy at the head of the arrow. If we decide to simplify an ordering by equating two policies connected by an arrow, the structure of the reward calculation will force other policies to also be equated. Specifically, if the equated policies differ only in positioni, then all pairs of policies which differ only in positioniwill also be set equal. For example, imagine we simplify the reward by saying we don’t care if the attic is cleaned or not, so long as the other two rooms are cleaned (recall that we named the rooms Attic, Bedroom and Kitchen). This amounts to saying thatJ([0,1,1]) =J([1,1,1]). Because the policy value function is of the form J(π) =J([x,y,z]) = [x,y,z]·[r 1 ,r 2 ,r 3 ] wherex,y,z∈ 0,1, this simplification forcesr 1 = 0. In turn, this implies thatJ([0,0,0]) = J([1,0,0])andJ([0,1,0]) =J([1,1,0]). The new structure underlying the ordering over policies is shown in Figure 8. [X, 0, 0] [X, 0, 1] [X, 1, 0] [X, 1, 1] Figure 8: The updated ordering structure after equating “clean all the rooms” and “clean all the rooms except the attic”. X can take either value in 0, 1. 21 An alternative way to think about simplification in this problem is by imagining policies as corners of a cube, and simplification as flattening of the cube along one dimension – simplification collapses this cube into a square. D.3 Software repository The software suite described in the paper (and used to calculate the representable policy orderings and simplifications of the two-stateMDP ) can be found athttps://github.com/nikihowe/ reward-hacking-paper. E Unhackability Diagram Consider a setting with three policiesa,b,c. We allow all possible orderings of the policies. In general, these orderings might not all be representable; a concrete case in which they are is when a,b,crepresent different deterministic policies in a 3-armed bandit. We can represent all unhackable pairs of policy orderings with an undirected graph, which we call an unhackability diagram. This includes a node for every representable ordering and edges connecting orderings which are unhackable. Figure 9 shows an unhackability diagram including all possible orderings of the three policiesa,b,c. b < a=c a < c < b c < a=b a=b=c c < b < a a=b < c c < a < b a < b=c b < c < ab < a < c a < b < c b=c < a a=c < b Figure 9: Illustration of the unhackable pairs of policy orderings when considering all possible orderings over three policiesa,b,c. Edges of the graph connect unhackable policy orderings. 22 F Simplification Diagram We can also represent all possible simplifications using a directed graph, which we call asimpli- fication diagram. This includes a node for every representable ordering and edges pointing from orderings to their simplifications. Figure 10 presents a simplification diagram including all possible orderings of three policiesa,b,c. a < b < c a < b=c a < c < b a=b < c a=b=c a=c < b b < a < c b < a=c b < c < a b=c < a c < a < b c < a=b c < b < a Figure 10: Illustration of the simplifications present when considering all possible orderings over three policiesa,b,c. Arrows represent simplification: the policy ordering at the head of an arrow is a simplification of the policy ordering at the tail of the arrow. We note that the simplification graph is a subgraph of the unhackability graph. This will always be the case, since simplification can never lead to reward hacking. 23