Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: +First rigorous approach to defining gameability

+Interesting and novel theory

+Good motivating example in Fig 1

+I like the idea of looking at optimization and not relying on agents finding optimal policy for proxy

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

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

-Some of the writing and results are unclear/opaque.

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.

Lines 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?

Line 138: is this a kleeny star? good to define since often star is used for optimal in MDP literature

Figure 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?

301 "there" is no reward

Figure 5: Very confusing. what are the different colors. what are the axis for J_1 and J_2? What is C'?

Line 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?

Line 376: "functions remain"

Line 390: If you don't optimize a reward how do you even define gameability?
limitations: The authors mention limitations several times throughout the paper.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:
1. It is the first paper formally studying the concept of reward gaming. This concept is rather interesting in my view.
2. The notions are basically introduced clearly.
3. Theorem 1 and Theorem 2 are crucial to this paper.


Weaknesses:
1. The property of asymmetry in proxy optimization is not well exploited.
2. I think for Definition 2 and the rotating contour lines proof for Theorem 2, the authors should provide more intuitive explanations. 
questions: What is the definition for $\mathcal{F} (\Pi)$ in Lemma 1 and Theorem 3?
I 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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

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.

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

Do 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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 . 
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. 

I 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. 
The 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).  


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

In 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). 
questions: **Definition of Ungameable Reward Functions:**
If 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?   

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



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


limitations: I very much appreciate the authors acknowledging the limitations of their work in their discussion.
review_title: null

Meta-review: metareview: The paper introduces the question of whether a pair of reward function and a proxy reward function is "gameable", i.e., whether maximizing the proxy may actually decrease the return in the original reward function. The authors develop a fairly complete analysis of this problem revealing a set of non-trivial results on, e.g., the possibility of creating ungameable pairs.

There is a general consensus among the reviewers that the contribution is novel and interesting and thus I'm proposing acceptance. For the final version of the paper, I strongly suggest the authors to
- Integrate some of the discussion from the rebuttal
- Clarify that the scope of the paper is more on the introduction of the concept and it's analysis rather in proposing new algorithms or practical approaches
- Expand as much as possible its connections with existing literature on inverse reinforcement learning
confidence: Certain
Decision: Accept