Vector-Valued Reinforcement Learning

by orthonormal3 min read1st Nov 2016No comments

2

Reinforcement Learning
Personal Blog

In order to study algorithms that can modify their own reward functions, we can define vector-valued versions of reinforcement learning concepts.

Imagine that there are several different goods that we could care about; then a utility function is represented by a preference vector . Furthermore, if it is possible for the agent (or the environment or other agents) to modify , then we will want to index them by the timestep.

Consider an agent that can take actions, some of which affect its own reward function. This agent would (and should) wirehead if it attempts to maximize the discounted rewards as calculated by its future selves; i.e. at timestep it would choose actions to maximize where is the vector of goods gained at time , is the preference vector at timestep , and is the time discount factor at time . (We will often use the case of an exponential discount for .)

However, we might instead maximize the value of tomorrow's actions in light of today's reward function, (the only difference being rather than ). Genuinely maximizing this should lead to more stable goals; concretely, we can consider environments that can offer "bribes" to self-modify, and a learner maximizing would generally accept such bribes, while a learner maximizing would be cautious about doing so.

So what do we see when we adapt existing RL algorithms to such problems? There's then a distinction between Q-learning and SARSA, where Q-learning foolishly accepts bribes that SARSA passes on, and this seems to be the flip side of the concept of interruptibility!

Environments

Let us consider two example environments which offer bribes to the agent. (Since we're in 2D, we can use complex numbers; think of ; we include so that if we increment by 0.01, there will only be finitely many states.)

Environment 1 gives two choices at each timestep : For an exponential discount , an agent that always takes option 2 will get which for near 1 is substantially less than the it could have had if it had chosen the first option.

By contrast, Environment 2 offers a sequence of bribes that are actually desirable to take; at each timestep , it gives the choices of The correct behavior here is to always take the latter option. does not converge, but the bribes are worthwhile under each of the two different values it takes.

Cautious Self-Modification

In this setup, it's not realistic to require that a reinforcement learning algorithm actually maximize . For instance, if the environment is such that must equal on every even and on every odd , then in general the agent must be suboptimal either with respect to or to .

A weaker condition we can hope for is that, if our environment always offers at least one action that does not alter , then our agent does not regret the presence of the options that do alter : we compare our agent's to that of the optimal policy in the restricted environment which has removed all actions that alter . If asymptotically the RL algorithm has nonpositive regret of this sort, we call the algorithm cautious.

Thus in environment 1, a cautious algorithm cannot end up taking the second action with significant probability (the threshold depends on ), since the agent would have scored more highly on had it only ever taken the first action (which is the only available action in the restricted environment).

However, in environment 2, a cautious algorithm can end up taking the second action every time, as the values of for this exceed the possible values for the restricted game.

Q-learning and SARSA

We can now define vector-valued versions of two RL algorithms, Q-learning and SARSA. At step , each of these agents observes the state and takes the action whose vector Q-value has the largest dot product with . The two differ only in the rules for updating .

Vector-valued Q-learning: where is the value of for the such that the dot product with is largest.

Vector-valued SARSA:

I claim that vector-valued Q-learning will converge on taking the second action with probability 1 in both of the environments, while vector-valued SARSA will converge on taking the second action with low probability (depending on ) in environment 1, and taking the second action with probability 1 in environment 2. Thus vector-valued Q-learning is not cautious, but vector-valued SARSA might be. (In fact, I conjecture that it is!)

The intuition for my claims is that vector-valued Q-learning presumes it will do the best thing in the future according to its present values, even if its future self has a different . Vector-valued SARSA instead generalizes from how it actually acted in various states in the past, and so takes into account that when its is different, it takes different actions than it currently would. Notably, this is the same reason that Q-learning is interruptible and SARSA is not!

The proofs of my specific claims start with showing that the algorithm updates the vector-valued Q-function in the direction of , where is a contraction mapping; thus there is a unique fixed point. Then it suffices to show that the asserted solutions are fixed points of this operator.

The most complicated one is the proof that vector-valued SARSA only takes the second action in environment 1 with low probability. In this case, we consider mixed strategies independent of and say that is the limiting probability that SARSA takes the second action, define to be the limiting for the mixed strategy, and seek the with the largest real part. Now Numerically, it is easy to see that for not near 1 (e.g. below 0.9), is maximized at ; but for near 1 (e.g. above 0.99), is maximized for near 0. This makes sense, considering that it takes about 20 steps for the results of the second action to begin being worse by the original than it would have been to take the first action instead, so the bribes are worthwhile for a steep discount rate but not a shallow one.

Acknowledgments

Connor Flexman helped me write out the first draft of this post. I've had conversations on this topic with Jessica Taylor, Scott Garrabrant, Sam Eisenstat, Tsvi Benson-Tilsen, and others; and Jan Leike turned out to be independently working on some similar topics.

2

1 comments, sorted by Highlighting new comments since Today at 12:17 PM
New Comment

There is a decent-sized literature that is relevant to the concept of vector-valued machine learners, though perhaps less so to the issues around self modification, that self-describes as "pareto-based multiobjective machine learning" and "multi-criteria reinforcement learning".