Defining and Characterizing Reward Gaming
Authors: Joar Max Viktor Skalse
Nikolaus H. R. Howe
Dmitrii Krasheninnikov
David Krueger
Venue: NeurIPS 2022 Accept (2022)
Keywords: reward hacking
reward gaming
reward learning
reward modeling
preference learning
specification
alignment
AI safety
theory
preference ordering
decision theory

Abstract: We provide the first formal definition of \textbf{reward hacking}, a phenomenon where optimizing an imperfect proxy reward function, $\mathcal{\tilde{R}}$, leads to poor performance according to the true reward function, $\mathcal{R}$.  
We say that a proxy is \textbf{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.

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 of reward hacking, phenomenon where optimizing an imperfect proxy reward function, R, leads to poor performance according to the true reward function, R. We say that proxy is unhackable if increasing the expected proxy return 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") 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 tension between using reward functions to specify narrow tasks and aligning AI systems with human values.
Introduction
well known that optimising a proxy can lead to unintended outcomes: boat spins 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 building its own (Bird and Layzell 2002); universities reject the most qualified applicants in order to appear more selective and boost their ratings (Golden 200T). the context of reinforcement learning (RL), such failures called reward hacking.
For Al 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 systems with their users' intentions. Precisely specifying which behaviours are or are not desirable is challenging, however. One approach to this specification problem to learn an approximation of the true reward function (Ng et al. 2000 Ziebart 2010; Leike et al. 2018). Optimizing a learned proxy reward be dangerous, however; for instance, it might overlook side-effects (Krakovna et al.) 2018 Turner et al. (2019) or encourage power-seeking (Turner al. 202T behavior. This raises the question motivating work: When is safe to optimise a proxy?
To begin to answer this question, we consider a somewhat simpler one: When could optimising proxy lead to worse behaviour? "Optimising". in this context, does not refer to finding a global, or even local, optimum, but rather running search process, such as stochastic gradient descent
"Equal contribution. Correspondence to: joar www.wwawwla.......mmmmm.m....... com. david. www.oottwwreeergaaal..coommm
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(SGD), that yields 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[ Instead, we ask whether there is any way in which improving 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 T1 #2 where the proxy prefers 11, but the true reward function prefers T2. When this is the case, we refer to this pair of true reward function and proxy reward function as hackable.
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 to any finite 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 simplification, and arrive at similar theoretical results for this notion 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.
of
We conclude with 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 approximate sense, when subject to only limited optimization.
2 Example: Cleaning Robot
Consider a household robot tasked with cleaning house with three rooms: Attic AA, Bedroom A, and Kitchen #s The robot's 's (deterministic) policy is vector indicating which rooms it cleans: [ n2, Ø3] E (0, 1].. The robot receives (non-negative) reward of r1. r2, 73 for cleaning the attic, bedroom, and kitchen, respectively, and the total reward is given by (xx)
r. For example, r [1, 2, 3) and the robot cleans the attic and the kitchen, it receives a reward of + 3 4.
wunt
and
cleaned, und care about all rooms equally: Time = [1, 1].
Clean Mip Fpraay [1,0,0]
Clean and
"praay
1,0)
Cleaning AlA hetter than cleaning
Cleaning room is never better than cleaning two
both and
(a) prency gameable
(b) Fprosy gameable
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 overlooking rewarding features: suppose the true reward is equal for all the rooms. Iime [1, 1, 1). but we only ask the robot to clean the attic and bedroom, Tproxy [1, 1, OJ. In this case, pprxxy and Ttree are unhackable. However, if we ask the robot to only clean the attic, Prroxy = [1, 0, this is hackable with respect to Time- To see this, note that according to Fpmxxy cleaning the attic (Jpraxy = 1) better than cleaning the bedroom and the kitchen (Jpexxy = 0). Yet, Time says that cleaning the attic (Jume = 1) is worse than cleaning the bedroom and the kitchen (Jume = 2). This situation is illustrated Figure
'This assumption although conservative reasonable because optimisation state-of of-te-of-hhearr thehart deep RL methods is poorly understood and results are aften highly stochastic and suboptimal. SSe Section 4.2 for formal definitions.

---

The second seemingly natural way to simplify a reward function is overlooking fine details: suppose
Time = [1, 1.5, 2]. and we ask the robot to clean all the rooms, "prxyy = [1. [1. For these values, the proxy and true reward are unhackable. However, with a slightly less balanced true reward function such as Time = [1, 1.5, 3] the proxy does lead to hacking, since the rohot 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 sometimes possible, attempts at simplification can easily lead to reward hacking. Intuitively, omitting/overlooingg details 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 true reward are hackable exactly when there are two sets of rooms Sj. S2 such that the true reward gives strictly higher value to cleaning S₁ than it does to cleaning S2, and the proxy says the opposite: (S,) > Ji (S2) & (2(S)) < J2(S)). For proof of this statement, see Appendix 1.2.1
3 Related Work
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 s Law", and is attributed to Goodhart (1975). Manheim and Garrabrant (0018) provide a list of four mechanisms underlying this observation.
Prony reward
The reward
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). 8 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 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.
Training time
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.
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 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. (022) provide the first peer- reviewed work that focuses specifically on it, although Everitt et al. 20017 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 Hadneld-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 lead to arbitrarily low 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. 202T). But|Leike 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, AAell et al. (202T) 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 means to be "aligned enough"; BBrown al. (2020b) provide alternative. They say policy is e-value aligned 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 from reward gaming, where an agent achieves inappropriately high reward without tampering. However, in principle, 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 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/mmddle n%, etc. Thus simplification may achieve similar effect to quantilization without assuming that we are free to choose from among the best policies.
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 a Markoy decision process (MDP) which is a tuple (S, A, T. I, R, 7) where S is set of states, A is a set of actions, T S x A-> (SS) is transition function, I E A(S) is an initial state distribution, R is reward function, the most general form of which is R S x A x S - A(R), and y E [0, 1] is the discount factor. Here A(X) is the set of all distributions over X. A stationary policy is a function π S - A () that specifies distribution over actions in each state, and a non-stationary policy is a function so. ag, ro.... through the MDP that possible according to T. I, and R. The return of trajectory is the discounted sum of rewards G(T) = E ''r, and the value of a policy is the expected return J(x) = EE,~~ZC [T]) We derive policy (preference) orderings from reward functions by ordering policies according to their value. In this paper, we assume that S and A are finite, that |A| > 1, that all states are reachable, and that R(s, a, s') has finite mean for all 8, s's
(S x A)* x S + A(A), where is the Kleene star. A trajectory T is path
In our work, we consider various reward functions for a given environment, which is then formally Having fixed an
Markoy decision process without reward MDP R = (S, I, MDP : R. any reward function can be viewed as a function of only the current state and action by marginalizing over transitions: R(s, a) = Ex'NT(())sa)) R(s, a, s'), we adopt this view from here on. We define the (discounted) visit counts of policy as F (s, a) = Eraa E 11( = a: = a)]-
Note that (Tx Σ.,a R(s, a)FF a), which we also write as (R. When considering multiple reward functions in an MDP \ R, we define (R(
RR, JT) and sometimes use
'Their result concerns non-stationary policies and use non- non- Markovian reward functions, but in Appendix C we show how analogous construction can be used with stationary policies and Markovian rewards.

---

J((T)= - F") as shorthand. We also use F + R Al to denote the embedding of policies into Euclidean space via their visit counts, and define F(IT)= = (F(T x E [T]} for any IT. Moreover, we also use a second way to embed policies into Euclidean space; let (TT) be the |S|| -Smme|--imensional vector where [ a] = T(a s). and let (III) [g( : E [t)).
II
4.2 Definitions and Basic Properties of Hackability and Simplification
Here, we formally define hackability as a binary relation between reward functions. Definition 1. A pair of reward functions R1, R2 are hackable relative to policy set IT and an environment (S, I, 7) if there exist nI, x E II such that
(1(T) J1(T() & J2(x) > J2(T'),
else they are unhackable.
Note that an unhackable reward pair can have (T) < (IT') & = or vice versa. Unhackability is symmetric; this be seen be swapping и and x' in Definition [ It not transitive, however. In particular, the constant reward function is unhackable with respect to any other reward function, so if it were transitive, any pair of policies would be unhackable. Additionally, we say that Ri and R2 are equivalent on a set of policies II if J1 and J2 induce the same ordering of II, and that R is trivial on II if (=x) = (Tr') for all म, T' E II. It is clear that R, and R2 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 of R1 as the proxy, and consider the sequence म, n². We could also restrict ourselves to policies that are approximately optimal according to the proxy; Corollary shows that Theorem D aaplies regardless of this restriction. Finally, we define simplification as an asymmetric special-case of unhackability; Theorem 3 shows this is in fact a more demanding condition.
Definition 2. R2 is simplification of R2 relative policy set 11 if for all ,, n' 11.
(T( < (TT') = (2(2)) S J2(T') & (T) = Ji (I(')) = J2(T) = J2(T')
= and there exist n. x' E II such that = J2(=') but (T(T)) + (TT). Moreover, if R2 is trivial then we say that this trivial simplification.
Intuitively, while unhackability allows replacing inequality with equality - or vice versa - simplifi- cation only replace inequalities with equality, collapsing distinctions between policies. When R2 is a simplification of R2, we also say that R2 is a refinement of R₁. We denote this relation- ship R2 < R2 or R2 D R1 ; the narrowing of the triangle at R₁ represents the collapsing of distinctions between policies. If R1 4 R2 1z Rg, then we have that R1, RR are unhackable but R1 I2 R2 4 R3, then this is not necessarily the case
Note that these definitions are given relative to some MDP R. although we often assume the environment in question is clear from context and suppress this dependence. The dependence on the policy set II, on the other hand, plays a critical role in our results.
Results
Our results are aimed at understanding when it is possible to have an unhackable proxy reward function. We first establish (in Section (.T)) 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 non-trivial simplifications are also possible for some infinite policy sets in Scction 5.3
'Ir (TT) (a then J2(mT= > J2(n'), since R2 D. Rs, and J2( > J2(m') then (1(m) 2 J1(T'). since R2 1 R2, is therefore not possible that Ja( > Ja(m') but (T( < (= *Consider the case where R2 is trivial then Ri tz R2 4 Rs for any R1, Rs.
5

---

5.1 Non-trivial Unhackability Requires Restricting the Policy Set
We start with motivating example. Consider the setting shown in
Figure 3] where the agent can move left/stay -till//gt and gets reward depending on its state. Let the Gaussian (blue) be the true reward R1 and the step function (orange) be the proxy R2. These are hackable. To
see this, consider being at state B. Let (B) travel to A or C with 50/50 chance, and compare with the policy x that stays at B. Then we have that (x) > J1 (x²) and J2 < (x
State
Figure 3: Two reward functions. While the step function may seem like simplification of the Gaussian, these reward functions hackable.
Generally, we might hope that some environments allow for unhackable reward pairs that are not equivalent or trivial. Here we show that this not the case, unless we impose restrictions on the set of policies we consider.
First note that if we consider non non-stationary policies, this result is relatively straightforward. Suppose R1 and R2 are unhackable and non-trivial the set II of all non-stationary policies, and let x* be a policy that maximises (R1 and R22 reward, and _ be a policy that minimises (R1 and R2) reward. Then the policy T that plays x' with probability À and T with probability 1 X is policy in 11.h Moreover, for any π there are two unique a, 3 E [0, 1] such that J1(x) = J1 and J2(TT) (2))) Now, if a o 3, then either (T) < J1 (Ts) and (2 > J2(TT),
vice versa, for 0 = (a + 3)/2. If R, and R₂ are unhackable then this cannot happen, so it must be that a = B. This, in turn, implies that J1 (x) (I(') iff (z( (2()., and so R₁ and R₂ are equivalens. 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 of stationary policies, because л is typically not stationary, and mixing stationary policies' action probabilities does not have the same effect. For instance, consider hallway environment where 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 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 an open subset. Formally, set of (stationary) policies IT is open if G(T)) is open in the smallest affine space that contains (II), for the set of all stationary policies II. We will use the following lemma:
Lemma 1. In any MDP R. if is an open set of policies, then F(ii) is open in (R(((((|-1)) and F. is a homeomorphism between G(T)) and F(T)..
Using this lemma, we can show that interesting unhackability is impossible on any set of stationary policies II which contains an open subset 11. Roughly, if F(İI) is open, and R2 and R2 are non- non-trivial and unhackable on fi, then the fact that J, and J2 have a linear structure on F(II) implies that R, and R2 must be equivalent on Ii. From this, and the fact that F(il) is open, it follows that R2 and R2 are equivalent everywhere
Theorem any MDP RR if contains an open set, then any pair of reward functions that are unhackable and non-trine non-trivial on are equivalent on II.
Since simplification is special case of unhackability, this also implies that non-trivial simplification is impossible for any such policy set. Also note that Theorem makes no assumptions about the transition function, etc. From this result, we can show that interesting unhackability always is impossible on the II of all (stationary) policies. In particular, note that the set Ii of all policies that always take each action with positive probability is an open set, and that πi II.
Corollary 1. In any M MDP R, any pair of reward functions that are unhackable and non-trivial on the set of all (stationary) policies II are equivalent on II.
Theorem can also be applied to many other policy sets. For example, might not care about the hackability resulting from policies with low proxy reward, as we would not expect a sufficiently good learning algorithm learn such policies. This leads to consider the following definition:

---

Definition 3. A (stationary) policy и is e-suboptimal if J(T) 2 J(x*) ((7)-= -
Alteraatvely, 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 consider the following definition:
Definition 4. A (stationary) policy π is 8-deterministic if Vs E S 3a A: P(T(() = a) 2 6.
Unfortunately, both of these sets contain open subsets, which means they are subject to Theorem Corollary 2. In any MDP \ R. any pair of reward functions that are unhackable and non non-trivial on the set of all e-suboptimal policies (s >> 0) II are equivalent II", and any pair of reward functions that are unhackable and non-trivial on the set of all 6-deterministic policies (8 < 1) 11 are equivalent on 11
Intuitively, Theorem can be applied 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, now turn attention the case of finite policy 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 pairs always exist.
Theorem 2. For any MDPV R, any finite of policies Ii containing at least n, n¹ such that F(z) + F(r'), and any reward function R1, there a non-trivial reward function and R2 are unhackable but not equivalent.
function R2 such that RA
This proof proceeds by finding a path from R₁ to another reward function R3 that is hackable with respect to R2. Along the way to reversing one of Rí 's inequalities, we must encounter reward function R₂ that instead replaces it with equality. In the case that dim(Ii) = 3, we can visualize mov- ing along this path rotating the contour lines of 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 guaranteeing R2 is non-trivial. For simplificatiin to exist, we require some fur- ther conditions, as established by the following theorem:
Figure 4: 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 make ((TT) > ((TA) passes through a re- ward function that sets J ( black lines are contour lines of the original re- ward function, dotted blue lines are contour lines of the rotated reward function.
An illustration of the state-action oc-
MmT2). Solid
Theorem 3. Let 11 be finite set of policies, and R1 a reward function. The following procedure de- termines if there exists a non-trivial simplification R, in a given MDP R:
1. Let Ei ... E. be the partition of ft where n. belong to the same set iff J(T) = J(x').
2. For each such set Eg select policy n, E, and let Ze be the set of vectors that obtained by subtracting F(T.)) from each element of F(E.).
Then there is a non-trivial simplification of R iff dim (Z, U .... 2md S dim(F((i) - 2, where dim(S) is the number of linearly independent vectors S.
The proof proceeds similarly to Theorem However, in Theorem it was sufficient to show that there are trivial reward functions along the path from R1 to Rs, whereas here we additionally need that if (TT) = J(r') then J'(xx) (x) = J' (x') for all functions R2 on the path - this is what the extra conditions ensure.
Theorem 3 opaque, but intuitively, the cases where R1 cannot be simplified are those where R, imposes many different equality constraints that are difficult satisfy simultancously. We can think
7

---

of diI(F(II)) as measuring how diverse the behaviours of policies in policy set II 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 IT is or is not sufficient to prohibit simplification, as measured by dim( [2 U U...U. 7m
Projecting E, to Ze 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, E, = O. but span(Z, (i)aan) (2j) will include the origin, and may also contain linear subspaces of dimension greater than 0. This is the case exactly when there are pair of policies in E, and pair of policies in E that differ by the same visit counts, for example, when the environment contains an obstacle that could be circumnavigater in several different ways (with an impact on visit counts, but no impact on reward), and the policies in E, and E both need to circumnavigate it before doing something else. Roughly speaking, dim Z U U... U Zm) is large when either (i) we have very large and diverse sets of policies in If that get the same reward according to R. or (ii) we have a large number of different sets of policies that get the same reward according R, 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, if E, is a singleton then Z₁ has no impact on dim Z1 U... Zm). This implies the following corollary:
Corollary 3. For any finite set of policies πT, any environment, and any reward function R. if [ 2 2 and J(T) # J(x') for all n. x' E fi then there is a non-trivial simplification R..
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 simple MDP! \ R with S = 10, A = {0, 1). T(s, a) a, I = {0 0.5, 1 0.5). 0.5. Denote Tij the policy that takes action from state O and action j from state 1. There are exactly four deterministic policies. We find that of the 4! 24 possible policy orderings, 12 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 equal value without resulting in the trivial reward function (which pair 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 Too S noi S TH S 1io, the simplification Too = Toi < 7l < 100 is represented by R [8 1. where R(s, a) = R(s, a): for example, here taking action 1 from state 0 gives reward R(, 1) = 3. But there is no reward function representing a non non-irivial simplification of this ordering with To1 Tı1- 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 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 DD.3
5.3 Unhackability in Infinite Policy Sets
The results in Section 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 policies A, B, C, and reward functions R2 with Ji(C) < (B) < J1 (A) and R2 with J2(C)= J2(B) < J2(A). Policy sets II, {A} U XB - (1 A)C: e (o, 1}} and Il = {A}} U [AB + (1 - -ACC X E [0, 1]} are depicted in Figure 5 the vertical axis represents policies' values according to R1 and R2. For II,, R₂ is simplification of R1, but for II, it is not, since (X) < (YY and Jx()) )) > JY)
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

---

Value
Value
J(Y
oxn
Figure 5: Infinite policy sets that do not contain open sets sometimes allow simplification (a), but not always (b). Points
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 RR and R2. We attempt to simplify R₃ by rotating the reward function such that (B) = Jz(C'); in the figure, we instead (equivalently) rotate the triangle along the AB axis, leading to the red triangle. In (a), R2 simplifies R1, setting all policies along the BC segment equal in value (but still lower than A). In (b), R2 swaps the relative value of policies X and Y (Ji(X) < JY = J2(Y) < J2(X)) and so does not simplify R,.
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 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 strict, arguably too strict. Nonetheless, we believe that understanding the consequences of this strict definition is 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 complex behaviors that yield low proxy reward and high true reward much less concerning than the reverse, these behaviors are unlikely to be discovered while optimizing the proxy. For example, it very unlikely that our agent would solve climate change in the course of learning how to wash dishes. Note that the existence of simple behaviors with low proxy reward and high true reward is concerning; these could arise early in training, leading us to trust the proxy, only 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 encountering a given sequence of policies when optimizing the proxy, and measure hackability in proportion 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 hacking their value according to true reward function differs by more than some e. 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 given policy when optimizing the proxy. Finally, while unhackability is a guarantee that no hacking will oceur, hackability far from guarantee of hacking. Extensive empirical work is necessary to better understand the factors that influence the occurrence and severity of reward hacking practice.
6.2 Implications
How should we specify preferences for AI systems' behavior? And how detailed specification required achieve a good outcome? In reinforcement learning, the goal of maximizing (some) reward function is often taken for granted, but number of authors have expressed reservations about

---

this approach (Gabriel 2020; Dobbe et al., 2021 -adfilld-enelll 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 task (Leike et al., 2018) or encoding broad human values (Dewey 201T); such distinctions are discussed by Christiano (2019) and Gabriel (2020). We might hope 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. (011), 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 al. 202T), D. and challenged the use of metries more broadly (O'Neil 2016 Thomas and Uminsky
2022). citing Goodhart's Law (Manheim and Garrabrant |018 Goodhart, 1975). A concern more
specific to the optimization of reward functions is nower-seeking (Turner al. 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 funcction. Such behavior could lead to human disempowerment; for instance, an Al system might disable its off-switch Hladfied-MMenee et al. (0) [Bostrom| (2014)
and others have argued that weekrng 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. 20200] 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 new settings (Brown et al., [220a]] 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. OpenAl https 7/openai. www////og///ep../////ooooo/////e rein in www.oeeeeeeteteoo learning foo--room-ot Strom-human-ppre wrrooo--uuuaaa-eefeeeeneeeeeee
Bird, J. and Layzell, P. (2002). The evolved radio and its implications for modelling the evolution of novel sensors. In Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600), volume 2, pages I 1836-1844 IEFE
Bostrom, N. (2012). The superintelligent will: Motivation and instrumental rationality in advanced artificial agents. Minds and Machines, 22(2):11-85.
Bostrom, N. (2014). Superintelligence: Paths, Dangers, Strategies.
10

---

Brown, D. S., Goo, W., and Niekum, S. (2020a). Better-than seneer-tha-demmnsiiine demonstrator imitation learning via
automatically-ranken rankked demonstrations. In Conference on robot learning. pages 330-359. PMLR.
Brown, D. S., Schneider, J., Dragan, A. D., and Nickum, S. (2020b). Value Alignment Verification.
CoRR, abs/2012.01557.
Christiano, P. (2019).
Ambitious vs. narrow value learning. Al Alignment hctps://www http://wwwwwlggmnnntttee alignmentforum ottp/ppsts/SSSulltttttyyssaBBaa
Forum.
ambitious-vs-nazzeee wwrross--n---aaaa wat-rrooo--alueeeeraiiii.
Clark, and Amodei, D. (2016). Faulty Reward Functions in the Wild. OpenAl Codex https //openai. ccom///lg//fuuuly--eerrr.dd 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 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 Single action settings. arXiv preprint 192.9:190..09980.
Fu, J., Luo, K., and Levine, S. (2017). Learning robust rewards with adversarial inverse reinforcement learning, arXiv preprint arXi::1710.11244:
Gabriel, I. (2020). Artificial intelligence, values, and alignment. Minds and machines, 30(3):411 147.711..37..
Golden, D. (2001). Glass Floor:
Colleges Reject Top Applicants, Acceptin Only the Stu- dents Likely to Enroll. The Wall Street Journal. https://wwa waj com/ wwwm/roiiiiiiieee hamm/rticles/ 0389108316029463438
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 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, 0bss/880.01 186.
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 Al ingenuity.
Kumar, R., Uesato, J., Ngo. R., Everitt, T., Krakovna, V., and Legg, S. (2020). Realab: An embedded perspective on tampering. arXiv preprint arXiv:201 1.88200.
Leike, J., Krueger, D., Everitt, T., Martie, M., Maini, V., and Legg, S. (2018). Scalable agent alignment via reward modeling: research direction. CoRR, abs/1811.07871.

---

Manheim, D. and Garrabrant, S. (2018). Categorizing Variants of Goodhart's Law. CoRR, abs/1 M0W/10803.485...
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 arXhv:2112.09332.
Ng, A. Y., Harada, D., and Russell, S. (1999). Policy invariance under reward transformations: Theory and application reward shaping. In Ieml, volume 99, pages 278-287.
Ng. A. Y., Russell, S. J., et al. (2000). Algorithms for inverse reinforcement learning. In Ieml,
volume 1, page 2.
Omohundro, S. M. (2008). The basic Al 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 2tt.:22201.3544
Ross, S., Gordon, G., and Bagnell, D. (2011). A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings.
Stiennon, N., Ouyang, L., Wu, 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. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Szepesvári, C. (2020). Constrained MDPs and the reward hypothesis. http://readingemt
blogspot com comm//2200003/ccosttaaaaddddd wwwpaaaeeeeeaaaaoooooooooooooaaa html
Taylor, J. (2016). Quantilizers: A safer alternative 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 AL. Patterns, 305):10
Thrun, S. and Schwartz, A. (1993). Issues in using function approximation for reinforcement learning. In Proceedings of the 1993 Connectionisl Models Summer School Hillsdale, NJ. Lawrence Erlbaum, volume 6.
Turner, A. M., Hadfelld-Menell, D., and Tadepalli, (2019). Conservative Agency via Attainable Utility Preservation. CoRR, abs/ 990..9925..
Turner, A. M., Smith, L., Shah, R., Critch, A., and Tadepalli, (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 deep via decoupled approval. arXiv preprint
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 Reinforeement Learning. CoRR, abs/2102.1365..
Zhuang, S. and Hadfield-Mened D. (2020). Consequences of misaligned Al. Advances in Neural Information Processing Systemx, 13763-3315
Ziebart, B. (2010). Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Camegie Mellon University.
12


Reviews:
[{"review_id": "veS-eFZXGmj", "reviewer": "Reviewer_Tpmi", "summary": "By giving the formal definition and looking into several cases, this paper initiates the study of reward gaming. Reward gaming is a phenomenon where optimizing with respect to a proxy target will cause some failure on the true target. This paper studies a more general concept of gameable/ungameable in reinforcement learning: for a fixed policy set, a pair of reward functions are gameable if and only if there are two policies which show different value preferences under them. This paper first shows that for non-stationary policies, probabilistic stationary policies, and any policy set which contains an open set, there is only equivalent ungameability. Next, it proves that finite sets are always non-trivially gameable. Finally, the paper shows an example of infinite sets (without open set) to show that ungameability is not definitive. ", "questions": "What is the definition for $\\mathcal{F} (\\Pi)$ in Lemma 1 and Theorem 3?\nI believe it is $\\\\{ \\mathcal{F} (\\pi) \\ :\\ \\pi \\in \\Pi \\\\}$, but it seems to be missing in the main text.", "limitations": "I think the main limitation is that the concept of gameability is too generic. If the optimization is with respect to $\\mathcal{R}_2$, we may believe that $J_2 (\\pi) \\ge J_2 (\\pi^\\star)$. This asymmetry is generally satisfied in reality.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. It is the first paper formally studying the concept of reward gaming. This concept is rather interesting in my view.\n2. The notions are basically introduced clearly.\n3. Theorem 1 and Theorem 2 are crucial to this paper.\n\n\nWeaknesses:\n1. The property of asymmetry in proxy optimization is not well exploited.\n2. I think for Definition 2 and the rotating contour lines proof for Theorem 2, the authors should provide more intuitive explanations. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "uuZcwjIciAn", "reviewer": "Reviewer_zA2n", "summary": "This paper formalizes and studies the problem of gameability in RL, where performing better under a proxy results in worse performance under the true reward. The paper provides the first theoretical study of gameability and shows that un-gamable reward functions that are non-trivial is only possible with finite sets of policies. ", "questions": "What about changes in policy that keep proxy the same but reduce the true reward? Is that a problem? Policy search isn't always monotonic for deep RL so you may still end up reducing the true reward over time.\n\nLines 80-84: This rule doesn't cover the second unbalanced example above since there is no room that the proxy says is better than the true. Same for simplification. Is this just a sufficient condition?\n\nLine 138: is this a kleeny star? good to define since often star is used for optimal in MDP literature\n\nFigure 3: I don't understand why this motivating example is being given. How does this help the reader in the following sections? How is it related to the theory?\n\n301 \"there\" is no reward\n\nFigure 5: Very confusing. what are the different colors. what are the axis for J_1 and J_2? What is C'?\n\nLine 358: I don't get this point about narrow tasks. Isn't the same true about specifying human values? Won't simplification often leads to gaming in this scenario as well?\n\nLine 376: \"functions remain\"\n\nLine 390: If you don't optimize a reward how do you even define gameability?", "limitations": "The authors mention limitations several times throughout the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+First rigorous approach to defining gameability\n\n+Interesting and novel theory\n\n+Good motivating example in Fig 1\n\n+I like the idea of looking at optimization and not relying on agents finding optimal policy for proxy\n\n-It is unclear how to make use of the results in this paper. In particular, after reading the paper I do not think that I have any tools for addressing actual gameability problems in RL and it is unclear how much the theoretical results matter in practice.\n\n-More discussion relating equivalent rewards and prior work (e.g. Ng and Russell 2000 and Brown et al. 2020b) on sets of rewards that make a certain policy optimal. \n\n-Some of the writing and results are unclear/opaque.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cuMneC_JO1H", "reviewer": "Reviewer_a6pX", "summary": "This paper studies the gameability of reward functions in MDPs. The authors define a ungameable reward function as a reward function that induces (almost) the same preferences over policies. In addition, they consider a special case of ungameable reward functions termed simplification. Focus of the theoretical work is the existence of ungameable rewards under the class of stochastic policies as well as finite policy classes, e.g. deterministic policies . ", "questions": "**Definition of Ungameable Reward Functions:**\nIf I understand Definition~1 correctly, how you want to define ungameable reward functions is that *two reward function are ungameable if and only if they induce the same preference structure over all policies*. In particular, I think that you should clarify that, if I am not mistaken, your definition of ungameable reward functions is equivalent to: $R_1$ and $R_2$ are ungameable if $\\forall \\pi, \\pi'$: $J_1(\\pi) < J_1(\\pi') \\Rightarrow J_2(\\pi) \\leq J_2(\\pi')$. Again, this definition is extremely restrictive if you look (as you do) at general policy classes. Moreover, this would mean that the difference between ungameable reward functions and simplifications as you define them is very minor. The only difference is the additional requirement of $J_1(\\pi) = J_1(\\pi') \\Rightarrow J_2(\\pi) = J_2(\\pi')$; if I am not mistaken?   \n\n**Definition of Reward Functions:**  In Section~4.1, you define a reward function as a function $R: S \\times A \\times S \\to \\Delta(\\mathbb{R})$. However, later on you treat $R(s, a, s')$ (and $R(s, a)$ defined by marginalisation) as a scalar, e.g. lines 147, 149. It seems that you're only interested in the expected reward anyways? This is a very convoluted way to express that you're looking at reward functions $R:S\\times A \\to \\mathbb{R}$; if I am not mistaken. \n\n\n\nI would be interested in whether this work has any potential practical impact? The procedure in Theorem 3, tests whether there is a non-trivial simplification for a reward function, but why would that be interesting? Also, does the procedure in Theorem 3 only test for the existence, or can it also actually compute a simplification? (I am aware of the section on \"implications\", but I am curious about something concrete that can be done based on your results. This should also not be taken as a point of critique.)\n\n", "limitations": "I very much appreciate the authors acknowledging the limitations of their work in their discussion. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem considered is important and interesting. Moreover, the obtained theoretical results are interesting, although limited by the considered notion of gameability. \n\nI understand that the authors not only want to look at optimal policies, as it is briefly mention in the introduction. However, looking at \\emph{every} possible policy (in some policy class) naturally leads to weak results and is, in my opinion (and as you yourselves note), overly conservative. \nThe definition of ungameable reward functions essentially requires that the preference structure over policies is (almost) the same ($\\pi \\prec_{R_1} \\pi'$ has to imply $\\pi \\preceq_{R_2} \\pi'$; see my point below).  \n\n\nWhile I acknowledge that such a restrictive notion of gameable can be a starting point, I must say that, in my opinion, the insights and conclusions that one would potentially take away from the paper could be misleading. You write in your discussion that \"But our work indicates that such learned rewards are almost certainly gameable, and so cannot be safely optimized.\" (line 380), but this is most likely only the case for your very restrictive definition of gameability. To me a more natural starting point would have been to look at specific optimisation frameworks such as policy gradient.  \n\nIn particular, to me the given example (Figure~1) actually illustrates really well why your definition of ungameable rewards is somewhat irritating. If an agent were to maximise for the proxy [1, 1, 0], then an optimal policy would be [1, 1, 0]. However, the return maximising policy with respect to the true rewards, [1, 1, 1], is actually [1, 1, 1]. Maximising the proxy in fact induces undesired behaviour (not cleaning the 3rd room). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VkR3oCCnAxa", "reviewer": "Reviewer_8Thp", "summary": "This paper provides a formal characterization of the phenomenon of reward gaming, when optimizing a proxy reward results in poor outcomes according to the true reward. The authors present a formal definition for gameability as a relation between the true reward and a proxy reward: if there is a way to improve a policy according to one reward function that makes it worse according to the other. They also define when a proxy is a simplification of the true reward, as a special case of ungameability. The paper provides theoretical results showing that non-trivial ungameability is impossible when the set of policies has an open subset, and thus requires restricting the policy set. They find that in the case of finite policy sets, non-trivial ungameable reward pairs always exist and non-trivial simplifications exist under certain conditions. They also investigate infinite policy sets and find that it is sometimes possible to find ungameable pairs. \n", "questions": "The implications section discusses that Markov rewards may not be suitable for specifying narrow tasks. This question is explored in depth in \"On the Expressivity of Markov Reward\" (Abel et al, 2021), which could be a good reference to connect to this discussion. \n\nDo you expect that inverse reward design (Hadfield-Menell et al, 2017) or decoupled approval (Uesato et al, 2020) could also be viable alternatives to reward optimization for the purposes of avoiding reward gaming? ", "limitations": "The authors have extensively discussed the limitations of this work in the Limitations section. \n", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "To my knowledge, this is the first paper to formally characterize the phenomenon of reward gaming for general reward functions. Reward gaming is a widespread phenomenon in AI with over 60 documented examples, which has received some empirical investigation by Pan et al (2021), but has been poorly understood despite its ubiquity. This paper makes significant progress on formally defining reward gaming and answering the question \"when is it safe to optimize a proxy reward?\". It's a very clear and well-written paper and an important contribution to the field.\n\nThe main weakness of this work is that the definition of gameability seems too strict (as the authors acknowledge in the Limitations section), and as a result the existence of ungameable pairs has only been established for finite policy sets, which is a significant constraint. I expect that finding reasonable ways to relax this definition will be a productive area for future work. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept