Bounding Goodhart's Law

post by eric_langlois · 2018-07-11T00:46:19.822Z · LW · GW · 2 comments

Contents

  Definitions
  Goodhart Regret
  Result: Uniformly Bounded Error
  Result: One-sided Error Bounds
  Non-Optimal π∗ 
    Example: Human Reward Learning
  Comments and Takeaways
None
2 comments

Goodhart's law seems to suggest that errors in utility or reward function specification are necessarily bad in sense that an optimal policy for the incorrect reward function would result in low return according to the true reward. But how strong is this effect?

Suppose the reward function were only slightly wrong. Can the resulting policy be arbitrarily bad according to the true reward or is it only slightly worse? It turns out the answer is "only slightly worse" (for the appropriate definition of "slightly wrong").

Definitions

Consider a Markov Decision Process (MDP) $M=(S,A,T,R^{\ast })$ where

• $S$ is the set of states,
• $A$ is the set of actions,
• $T:S\times A\times S\to R$ are the conditional transition probabilities, and
• $R^{\ast }:S\times A\to R$ is the reward function. (Note: "reward" is standard terminology for MDPs but it's fine to think of this as "utility")

A policy $\pi :S\times A\to R$ is a mapping from states to distributions over actions with$\pi (s,a)=\text{Pr}\left(a|s\right)$.

Any given policy $\pi$ induces a distribution $\sigma \left(\pi \right)$ over states in this MDP. If we are concerned about average reward we can take $\sigma \left(\pi \right)$ to be the stationary distribution or, if the environment is episodic, we can take $\sigma \left(\pi \right)$ to be the distribution of states visited during the episode. The exact definition is not particularly important for us.

Define the return of policy $\pi$ according to reward function $R$ to be

Goodhart Regret

Suppose we have an approximate reward signal $\hat{R}$ and we use it to specify a policy $\hat{\pi }$. How bad is $\hat{\pi }$ according to the true reward $R^{\ast }$?

More specifically, what is the regret of using $\hat{\pi }$ compared to the optimal policy ${\pi }^{\ast }$? Formally,

We can expand this as

Let $ϵ\ge 0,$ then $\text{Regret}\left(\hat{\pi }\right)\le 3ϵ$ if the following conditions are satisfied by $\hat{R}$ and $\hat{\pi }$:

1. $G({\pi }^{\ast },R^{\ast })-G({\pi }^{\ast },\hat{R})\le ϵ$

2. $G({\pi }^{\ast },\hat{R})-G(\hat{\pi },\hat{R})\le ϵ$

3. $G(\hat{\pi },\hat{R})-G(\hat{\pi },R^{\ast })\le ϵ$

Condition 2 says that $\hat{\pi }$ is not much worse than ${\pi }^{\ast }$ when measured against $\hat{R}$. That is what we expect if we designed $\hat{\pi }$ to be specifically good at $\hat{R}$, so condition 2 is just a formalization of the notion that $\hat{\pi }$ is tailored to $\hat{R}$.

Conditions 1 and 3 compare a fixed policy against two different reward functions. In general for policy $\pi$ and reward functions $R$ and $R^{\prime }$,

Result: Uniformly Bounded Error

Assume that we have a reward approximation $\hat{R}$ with uniformly bounded error. That is, $\forall s\in S,\forall a\in A,|R^{\ast }(s,a)-\hat{R}(s,a)|<ϵ$. Take $\hat{\pi }={\text{argmax}}_{\pi }G(\pi ,\hat{R})$.

Then $\text{Regret}\left(\hat{\pi }\right)<2ϵ$. (Condition 2 has bound 0 in this case).

Result: One-sided Error Bounds

A uniform bound on the error is a stronger condition than we really need. The conditions on $\hat{R}$ can be re-written:

1. $E_{{\pi }^{\ast }}\left[R^{\ast }(s,a)-\hat{R}(s,a)\right]\le ϵ$; $\hat{R}$ does not substantially underestimate the reward in the regions of state-space that are frequently visited by ${\pi }^{\ast }$.

3. $E_{\hat{\pi }}\left[R^{\ast }(s,a)-\hat{R}(s,a)\right]\ge -ϵ$; $\hat{R}$ does not substantially overestimate the reward in the regions of state-space that are frequently visited by $\hat{\pi }$.

In other words, it doesn't matter if the reward estimate is too low for states that ${\pi }^{\ast }$ doesn't want to visit anyways. This tells us that we should prefer biasing our reward approximation to be low in the absence of more information. We do need to be careful about not overestimating where $\hat{\pi }$ does visit, which is made difficult by the fact that condition 2 pushes $\hat{\pi }$ to visit states that $\hat{R}$ assigns high reward.

If we don't know what ${\pi }^{\ast }$ is then it might be difficult to ensure we don't underestimate the reward over $\sigma \left({\pi }^{\ast }\right)$. We probably have access to $\hat{\pi }$ so we might expect to have better reward approximations over $\sigma \left(\hat{\pi }\right)$ and therefore have an easier time satisfying condition 3 than 1.

Non-Optimal ${\pi }^{\ast }$

The bound on $G({\pi }^{\ast },R^{\ast })-G(\hat{\pi },R^{\ast })$ does not actually require ${\pi }^{\ast }$ to be an optimal policy for $R^{\ast }$. We can take ${\pi }^{\ast }$ to be any policy and if we can satisfy the 3 bounds then $\hat{\pi }$ will be not much worse than ${\pi }^{\ast }$ (and could be better). Using a known policy for ${\pi }^{\ast }$ likely makes it easier to satisfy condition 1, which is an expectation over the state-action distribution of ${\pi }^{\ast }$.

Example: Human Reward Learning

Since ${\pi }^{\ast }$ need not be optimal, we can take ${\pi }^{\ast }$ to be the policy of a human and try to learn our reward / utility function. Note: this is a very flawed proposal, its purpose is to demonstrate how one might think about using these bounds in reward learning, not to be a concrete example of safe reward learning.

Suppose that there is some ideal reward function $R^{\ast }$ that we'd like to approximate. We don't know $R^{\ast }$ in general but imagine we can evaluate it for state-action pairs that are performed by a human. Let $D_H=\left\{\right(s_i,a_i,r_i=R^{\ast }(s_i,a_i)){\}}_{i=1}^N$ be a collection of human demonstrations with labelled reward.

Consider the following algorithm:

1. Fit $\hat{R}$ to $D_H$ so that it does not underestimate.

2. Set $\hat{\pi }={\text{argmax}}_{\pi }G(\pi ,\hat{R})$.

3. Collect a batch $\hat{D}=\left\{\right(s_j,a_j){\}}_{j=1}^M$ of demonstrations from $\hat{\pi }$ (no reward labels).

4. Augment $D_H$ with some additional human demonstrations.

5. Modify $\hat{R}$ to assign lower reward to all of $\hat{D}$ while not underestimating on $D_H$

6. Repeat from 2.

Assuming $\hat{R}$ is sufficiently expressive, this algorithm pushes $\hat{R}$ and $\hat{\pi }$ towards satisfying all three conditions: $\hat{R}$ does not underestimate on the distribution of human-visited states, $\hat{R}$ is otherwise as low as possible on states $\hat{\pi }$ visits, and $\hat{\pi }$ is optimal for $\hat{R}$. If these are all met, the resulting policy would be no worse than the human at maximizing $R^{\ast }$ and possibly much better.

Comments and Takeaways

Goodhart's law is more impactful in the context of the sparse reward setting, in which approximation means deciding what to value, not how much to value. Consider a state space that is the real line and suppose that the true reward function is $R^{\ast }(s,a)=1[s=1]$ where $1[\cdot ]$ is the indicator function.

If we estimate

then Goodhart's law applies and we can expect that a policy optimized for ${\hat{R}}_1$ will have high regret on $R^{\ast }$.

On the other hand, if we estimate

then the regret bounds apply and a policy optimized for ${\hat{R}}_2$ will do very well on $R^{\ast }$.

• Assigning high value to the wrong things is bad.
• Assigning the wrong value to the right things is not too bad.
• Throwing a large amount of optimization power against an incorrect utility function is not always bad.

2 comments

Comments sorted by top scores.