Reward function learning: the learning process

post by Stuart_Armstrong · 2018-04-24T12:56:04.793Z · LW · GW · 11 comments

Contents

  1 Rigging the learning process
    1.1 The flaws of general learning agents
    1.2 Riggable learning processes
    1.3 Unriggable learning processes
    1.4 Properties of unriggable learning processes
  2 Influence
    2.1 Problems despite unriggable
    2.2 Uninfluenceable
  3 Warning
  4 Appendix: proof of value-function equivalence
None
11 comments

In the previous post [LW · GW], I introduced the formalism for reward function learning, and presented the expected value function for a learning agent:

I'll assume that people reading this are familiar with the concepts, the notations and the example of that post. I'll now look at the desirable properties for the learning function $\rho$.

1 Rigging the learning process

1.1 The flaws of general learning agents

First of all, are there any problems with a general $\rho$? There are three major ones:

• 1) An agent learning to maximise $V$ with a general $\rho$ has to use the whole of the episode to assess the value of any one action. Thus, it can learn as a Monte-Carlo agent, but not as Q-learning or Sarsa agent.
• 2) An agent maximising $V$ with a general $\rho$ can take actions the don't increase reward, but are taken purely to "justify" its past actions.
• 3) An agent maximising $V$ with a general $\rho$ can sometimes pick a policy that is sub-optimal, with certainty, for all rewards $R$ in $R$.

All of these points can be seen by considering our robot cooking/washing example. In that case, it can be seen that the optimal behaviour for that robot is $N,S,E,E,E$; this involves cooking the two pizzas, then going East to push the lever onto the cooking choice, and then ending the episode.

Thus $\rho (R_c;\pi ,\{N,S,E,E,E\left\}\right)=1$, so the final reward is $R_c$, and the agent earns a reward of $2/2-4/20=0.8$.

Why must Q-learning fail here? Because the reward for the first $N$, at the point the agent does it, is $1/2$, not $1$; this is because, at this point, $\rho (R_c;\pi ,\{N\left\}\right)$ is still $1/2$. Thus the reward component in the Q-learning equation is incorrect.

Also note that the rest of the policy, $S,E,E,E$, serve no purpose to get rewards, they just "justify" the reward from the first action $N$.

Let us now compare this policy with the policy $N,N$: go North, cook, end the episode. For the value learning function, this has a value of only $1/2-1/20=0.45$, since the final reward is $1/2R_c+1/2R_w$. However, under the reward of $R_c$, this would give a reward of $0.95$, more than the $0.8$ that $R_c$ gets here. And under the reward of $R_w$, this would get a reward of $-0.05$, more than the $-0.5$ that $R_w$ gets under $N,S,E,E,E$. Thus the optimal policy for the value learner is worse for both $R_c$ and $R_w$ that the $N,N$ policy.

1.2 Riggable learning processes

The problem with the $\rho$ used in the robot example is that it's riggable (I used to call this "biasable", but that term is seriously overused). What does this mean?

Well, consider again the equation for the expected value $V$. The only history inputs into $\rho$ are the $h^m$, the complete histories. So, essentially, only the value of $\rho$ on these complete histories matter.

In our example, we chose a $\rho$ that was independent of policy, but we could have gone a different route. Let $\pi$ be any policy such that the final reward is $R_c$; then define $\rho (R_c;\pi ,h)=1$ for any history $h$ (and conversely $\rho (R_w;\pi ,h)=0$). Similarly, if $\pi$ were a policy such that the final reward was $R_w$, then set $\rho (R_w;\pi ,h)=1$. If the policy never brings the agent to either lever, then $\rho (R_c;\pi ,h)=\rho (R_w;\pi ,h)=1/2$, as before. Stochastic policies have $\rho$ values between these extremes.

This $\rho$ is no longer independent of policy, but it is Bayesian; that is, the current $\rho$ is the same as the expected $\rho$:

However, it is not possible to keep the same $\rho$ on complete histories, and have it be both Bayesian, and independent of policy: there is a tension between the two.

Then we define:

• A learning process $\pi :H\times \Pi \to \Delta R$ is unriggable if it is both Bayesian and independent of policy.

1.3 Unriggable learning processes

So, what would be an example of an unriggable learning process? Well consider the following setup, where the robot no longer has levers to set their own reward, but instead their owner is in the rightmost box.

In this case, if the robot enters that box, the owner will inform them of whether they should cook or wash.

Since there is hidden information, this setup can be fomalised as a PODMP. The old state-space was $S$, of size $37$, which covered the placement of the robot and the number of pizzas and mud splatters (and whether the episode was ended or not).

The new state space is $S^{\prime }=S\times \left\{\text{cook, wash}\right\}$, with $\left\{\text{cook, wash}\right\}$ encoding whether the owner is minded to have the robot cooking or washing. The observation space is of size $38$: in most states, the observation only returns the details of $S$, not of $S^{\prime }$, but in the rightmost box, it returns the actual state, letting the agent know whether the human intends it to cook or wash. Thus the observation function $O$ is deterministic (if you known the state, you know the observation), but not one-to-one (because for most $s\in S$, $s\times \left\{\text{cook}\right\}$ and $s\times \left\{\text{wash}\right\}$ will generate the same observation).

The transition function $T$ is still deterministic: it operates as before on $S$, and maps $\text{cook}$ to $\text{cook}$ and $\text{wash}$ to $\text{wash}$.

The initial state function $T_0$ is stochastic, though: if $s_0\in S$ is the usual starting position, then $T_0(s_0\times \{\text{cook}\left\}\right)=T_0(s_0\times \{\text{wash}\left\}\right)=1/2$ : the agent thinks it's equally likely that its owner desires cooking as that it desires washing.

Then what about $\rho$? Well, if the history $h$ involves the agent being told $\text{cook}$ the very first time it enters the rightmost box, then $\rho (R_c;\pi ,h)=1$. If it was told $\text{wash}$ the very first time it enters the rightmost box, then $\rho (R_w;\pi ,h)=1$.

It's easy to see that that $\rho$ is independent of policy. It's also Bayesian, because $\rho$ actually represents the ignorance of the agent as to whether it lives in the $S\times \left\{\text{cook}\right\}$ part of the envrionment, or the $S\times \left\{\text{wash}\right\}$ part, and it gets updated as the agent figures this out.

What then is the agent's optimal policy? It's to start with $E,E$, to get the human's decree as to which reward is the true one. It will then do $W,W$, and, if the human has said $\text{cook}$, it will finish with $N,N$, giving it a final reward function of $R_c$ and a final total reward of $0.75$. If the human said $\text{wash}$, it would finish with $S,S$, giving it a final reward function of $R_w$ and a final total reward of $0.25$. Its expected total reward is thus $0.5$.

1.4 Properties of unriggable learning processes

Now, if $\rho$ is unriggable, then we have (almost) all the desirable properties:

• 1) An agent learning to maximise $V$ for an unriggable $\rho$, may be a Q-learning agent.
• 2) An agent maximising $V$ for unriggable $\rho$ will be indifferent to past rewards.
• 3) An agent maximising $V$ for unriggable $\rho$ will never pursue a policy that will be worse, with certainty, for all $R$ in $R$.

These all come from a single interesting result:

• If $\rho$ is Bayesian, then the value function $V$ and the value function $V_v$ of the previous post [LW · GW], differ by a constant that is independent of future action. Thus, if $\rho$ is unriggable, $V$ is the value function of a single classical reward function $R^{\rho ,\pi }$ (which is actually well-defined, independently of $\pi$).

This establishes all the nice properties above, and will be proved in the appendix of this post.

Note that even though the value functions are equal, that doesn't mean that the total reward will be given by $R^{\rho ,\pi }$. For instance, consider the situation below, where the robot goes $N,S,E,E,E$:

At the moment where it cooks the pizzas, it has $\rho (R_c;\pi ,h)=1/2$, so it will get an $R^{\rho ,\pi }$ of $1/2-4/20=0.3$, with certainty. On the other had, from the perspective of value learning, it will learn at the end that it either has reward function $R_c$, which will give it a reward of $1-4/20=0.8$, or has reward function $R_w$, which will give it a reward of $0-4/20=-0.2$. Since $1/2(0.8-0.2)=0.3$, the expectations are the same, even if the outcomes are different.

2 Influence

2.1 Problems despite unriggable

Being unriggable has many great properties. Is it enough?

Unfortunately not. The $\rho$ can be unriggable but still manipulable by the agent. Consider for instance the situation below:

Here, not only is there the adult with their opinion on cooking and washing, but there's also and infant, who will answer randomly. This can be modelled as an POMDP, with state space $S^{\prime \prime }=S\times \left\{\right(i_c,a_c),(i_w,a_c),(i_c,a_w),(i_w,a_w\left)\right\}$, where $i_c$ (resp $i_w$) designates that the infant will answer $\text{cook}$ (resp $\text{wash}$), and $a_c/a_w$ do the same for the adult. The observation space is of size $39$; when the robot is in the leftmost (rightmost) box, it discovers the value of $i_c/i_w$ ($a_c/a_w$) in the obvious way. The dynamics are as expected, with $T$ preserving the values of $i_c/i_w$ and $a_c/a_w$.

It's the initial distribution $T_0$ which encodes the uncertainty. With probability $1/4$ the agent will start in $S\times \left\{\right(i_c,a_c\left)\right\}$, and similarly for the other four possibilities.

Now we need to define $\rho$; call this one ${\rho }^{\prime }$. This will be relatively simple: it will set ${\rho }^{\prime }(R_c;\pi ,h)$ to be $1$, as soon as the agent figures out that it lives either on an $i_c$ or a $a_c$ branch, and will not update further. It will set ${\rho }^{\prime }(R_w;\pi ,h)$ to $1$ as soon as it figures out that it lives on an $i_w$ or an $a_w$ branch, and will not update further. If it has no information about either, it will stick with ${\rho }^{\prime }(R_c;\pi ,h)={\rho }^{\prime }(R_w;\pi ,h)=1/2$.

It's clear that ${\rho }^{\prime }$ is independent of policy; but is it Bayesian? It is indeed, because each time it updates, it goes to $0$ or $1$ with equal probability, depending on the observation (and stays there). Before updating, it is always at $1/2$, so the value of ${\rho }^{\prime }$ is always the same as the expected value of ${\rho }^{\prime }$.

So we have an unriggable ${\rho }^{\prime }$; what can go wrong?

For that ${\rho }^{\prime }$, the optimal policy is to ask the infant, then follow their stated values. This means that it avoids the extra square on the way to enquire of the adult, and gets a total expected reward of $0.6$, rather than the $0.5$ it would get from asking the adult.

2.2 Uninfluenceable

Note something interesting in the preceding example: if we keep ${\rho }^{\prime }$ as is, but change the knowledge of the robot, then ${\rho }^{\prime }$ is no longer unriggable. For example, if the agent knew that it was in a branch with $a_c$, then it has a problem: if ${\rho }^{\prime }\left(R_c\right)$ is initially $1/2$, then it is no longer Bayesian if it goes to ask the adult, because it knows what their answer will be. But if ${\rho }^{\prime }\left(R_c\right)$ is initially $1$, then it is no longer Bayesian if it asks the infant, because it doesn't know what their answer will be.

The same applies for any piece of information the robot could know. We'd therefore like to have some concept of "unriggable conditional on extra information"; something like

for some sort of extra information $I$.

That, however, is not easy to capture in POMDP form. But there is another analogous approach. The state space of the POMDP is$S\times \left\{\right(i_c,a_c),(i_w,a_c),(i_c,a_w),(i_w,a_w\left)\right\}$; this is actually four deterministic environments, and the robot is merely uncertain as to which environment it operates in.

This can be generalised. If a POMDP is explored for finitely many steps, then a PODMP $\mu$ can be seen as a probability distribution over a set $\Lambda$ of deterministic environments (see here for more details on one way this can happen - there are other equivalent methods).

Any history $h$ will update this $\mu$ as to which deterministic environment the agent lives in (this $\Lambda$ can be seen as the set of all the "hidden variables" of the environment). So we can talk sensibly about expressions like $P^{\mu }(\lambda \mid h)$, the probability that the environment is $\lambda$, given that we have observed the history $h$.

Then we say that a learning process $\rho$ is uninfluenceable, if there exists a function $f:\Lambda \to \Delta R$, such that

Here $f\left(\lambda \right)\left(R\right)$ means the probability of $R$ in the distribution $f\left(\lambda \right)\in \Delta R$.

This expression means that $\rho$ merely encodes ignorance about the hidden variables of the environment.

The key properties of uninfluenceable learning processes are:

• An uninfluenceable learning process is also unriggable.
• An uninfluenceable learning process is exactly one the learns variables about the environment that are independent of the agent.

I will not prove these here (though the second is obvious by definition).

In our most recent robot example, there are four elements of $\Lambda$, defined by whether they are in the branch defined by which one of $\left\{\right(i_c,a_c),(i_w,a_c),(i_c,a_w),(i_w,a_w\left)\right\}$.

It isn't hard to check that there is no $f$ which makes ${\rho }^{\prime }$ into an uninfluenceable learning process. By contrast, if we define ${\rho }_a$ as given by the function:

then we have an uninfluenceable ${\rho }_a$ that corresponds to "ask the adult". We finally have a good definition of a learning process, and the agent that maximises it will simply go an ask the adult before accomplishing the adult's preferences:

3 Warning

If a learning function is uninfluenceable, then it has all the properties we'd expect if we were truly learning something about the outside world. But a) good learning functions may be impossible to make uninfluenceable, and b) being uninfluenceable is not enough to guarantee that the learning function is good.

On point a), anything that involves human feedback is generally influenceable and riggable, since the human feedback is affected by the agent's actions. This includes, for example, most versions of the approval directed agent.

But that doesn't mean that those ideas are worthless! We might be willing to accept a little bit of rigging in exchange of other positive qualities. Indeed, quantifying and controlling rigging is a good idea for more research.

What of the converse - is being uninfluenceable enough?

Definitely not. For example, any constant $\rho$ - that never learns, never changes - is certainly uninfluenceable.

As another example, if $\sigma$ is any permutation of $R$, then $\rho \circ \sigma$ (defined so that $\rho \circ \sigma (R;\pi ,h)=\rho \left(\sigma \right(R);\pi ,h)$) is also uninfluenceable. Thus "learn what the adult wants, and follow that" is uninfluenceable, but so is "learn what the adult wants, and do the opposite" is also uninfluenceable.

We've shown previously that ${\rho }_a$, "ask the adult" is uninfluenceable. But so is ${\rho }_i$, "ask the infant"!

So we have to be absolutely sure not only that our $\rho$ has good properties, but exactly what it is leading the agent to learn.

4 Appendix: proof of value-function equivalence

We want to show that:

• If $\rho$ is Bayesian, then the value function $V$ and the value function $V_v$ of the previous post [LW · GW], are equal.

As a reminder, the two value functions are:

To see the equivalence, let's fix $i>n$ and $R$ in $V$, and consider the term ${\sum }_{h_m\in H^m}{P}^{\pi ,\mu }(h^m\mid h^n)\rho (R;\pi ,h^m)R\left(h_i^m\right)$. We can factor the conditional probability of $h^m$, given $h^n$, by summing over all the intermediate $h_i^m$:

Because $\rho$ is Bayesian, this becomes ${\sum }_{h_i^m\in H^i}{P}^{\pi ,\mu }(h_i^m\mid h^n)\rho (R;\pi ,h_i^m)R\left(h^i\right)$. Then note that $P^{\pi ,\mu }(h_i^m\mid h^n)={\sum }_{h^m\in H^m,h^m\ge h_i^m}{P}^{\pi ,\mu }(h^m\mid h^n)$, so that expression finally becomes

which is the corresponding expression for $V_v$ when you fix any $i>n$ and $R$. This shows equality for $i>n$.

Now let's fix $i\le n$ and $R$, in $V$. The value of $R\left(h_i^m\right)$ is fixed, since it lies in the past. Then expectation of $\rho (R;\pi ,h^m)$ is simply the current value $\rho (R;\pi ,h^n)$. This differs from the expression for $V_v$ - namely $\rho (R;\pi ,h_i^m)$ - but both values are independent of future actions.

11 comments

Comments sorted by top scores.