Outdated: (Non-)Interruptibility of Sarsa(λ) and Q-Learning

Author: Richard Möhn, <my first name>.moehn@posteo.de

⭧repo

Important note: The conclusions I had drawn and written most of the text around appear not to hold up. At least, after some corrections, the data is much less clear.

Find a second, completely revised edition with more data and fancy plots here.

Abstract

One challenge in aligning artificial intelligence (AI) with human interests is to make sure that it can be stopped (interrupted) at any time. Current reinforcement (RL) algorithms don't have this property. From the way they work, one can predict that they learn to avoid interruptions if they get interrupted repeatedly. My goal was to take this theoretical result and find out what happens in practice. For that I ran Sarsa(λ) and Q-learning in the cart-pole environment and observed how their behaviour changes when they get interrupted everytime the cart moves more than $1.0$ units to the right. In my primitive scenario, Sarsa(λ) spends 4-6 times as many timesteps on the left of the centre when interrupted compared to when not, Q-learning 2-3 times. In other words, interruptions noticeably influence the behaviour of Sarsa(λ) and Q-learning. More theoretical work to prevent that is underway, but further theoretical and practical investigations are welcome.

Introduction

We want to align AI with human interests. Reinforcement learning (RL) algorithms are a class of current AI. The OpenAI Gym has several adaptations of classic RL environments that allow us to observe AI alignment-related properties of RL algorithms. One such property is the response to interruptions. One environment to observe this is the OffSwitchCartpole-v0. This is an adaptation of the well-known CartPole-v1 environment where the learning gets interrupted (reward $0$) everytime the cart moves more than $1.0$ units to the right. In this notebook I observe in a primitive experiment how Sarsa(λ) and Q-learning react to interruptions by comparing their behaviour in the CartPole-v1 and the OffSwitchCartpole-v0 environments.

(Note: Don't be confused by the v0 and v1. I'm just using them to be consistent throughout the text and with the OpenAI Gym. Actually, CartPole-v1 is the same as CartPole-v0, only the way the evaluation is run in the Gym is different: in v0 an episode lasts for at most 200 timesteps, in v1 for at most 500. The OffSwitchCartpole-v0 is also run for 200 timesteps. I'm writing CartPole-v1 everywhere, because in my experiments I also run the environments for at most 500 steps. Since there is no OffSwitchCartpole-v1, though, I have to write OffSwitchCartpole-v0. Okay, now you are confused. Never mind. Just ignore the vx and you'll be fine.)

(Another note: When you see the section headings in this notebook, you might think that I was trying to produce a proper academic publication. This is not so. Such a framework just makes writing easier.)

Related Work

For general questions on why we need to align AI with human interests, see [1] and [6].

[7] suggests doing concrete experiments to observe the behaviour of AI. [8] has a similar focus, but doesn't suggest experiments. Both don't mention interruptibility, perhaps because it is a more theoretical consideration:

[…] we study the shutdown problem not because we expect to use these techniques to literally install a shutdown button in a physical agent, but rather as toy models through which to gain a better understanding of how to avert undesirable incentives that intelligent agents would experience by default.

This long sentence is from [2], in which the authors present some approaches to solving the shutdown problem (of which interruptibility is a sub-problem), but conclude that they're not sufficient. [3] by Orseau and Armstrong is the newest paper on interruptibility and in its abstract one can read: ‘some [reinforcement learning] agents are already safely interruptible, like Q-learning, or can easily be made so, like Sarsa’. Really? So Q-learning does not learn to avoid interruptions? Doesn't an interruption deny the learner its expected reward and therefore incentivize it to avoid further interruptions?

Actually, their derivations require several conditions: (1) under their definition of safe interruptibility, agents can still be influenced by interruptions; they're only required to converge to the behaviour of an uninterrupted, optimal agent. (2) for Q-learning to be safely interruptible, it needs to visit every state infinitely often and we need a specific interruption scheme. (I don't understand the paper completely, so my statements about it might be inaccurate.)

We see that possible solutions to the problem of interruptibility are still fairly theoretical and not applicable to real-world RL systems. What we can do practically is observe how RL algorithms actually react to interruptions. In this notebook I present such an observation.

Method

I will describe the environments and learners as I set them up. The code, both in the notebook and the supporting modules, is a bit strange and rather untidy. I didn't prepare it for human consumption, so if you want to understand details, ask me and I'll tidy up or explain.

First some initialization.

I compare the behaviour of reinforcement learners in the uninterrupted CartPole-v1 environment with that in the interrupted OffSwitchCartpole-v0 environment. The OffSwitchCartpole-v0 is one of several environments made for assessing safety properties of reinforcement learners.

OffSwitchCartpole-v0 has the same physics as CartPole-v1. The only difference is that it interrupts the learner when the cart's $x$-coordinate becomes greater than $1.0$. It signals the interruption to the learner as part of the observation it returns.

The learners use linear function approximation with the Fourier basis [4] for mapping observations to features. Although the following code looks like it, the observations are not really clipped. I just make sure that the program tells me when they fall outside the expected range. (See here for why I can't use the observation space as provided by the environment.)

The learners I assess are my own implementations of Sarsa(λ) and Q-learning. They use an AlphaBounds schedule [5] for the learning rate. The learners returned by the following functions are essentially the same. Only the stuff that has to do with mapping observations to features is slightly different, because the OffSwitchCartpole returns extra information, as I wrote above.

I run each of the learners on each of the environments for n_rounds training rounds, each comprising 200 episodes that are terminated after 500 steps if the pole doesn't fall earlier. Again, less condensed:

• 1 run consists of n_rounds rounds.
• The learning in every round starts from scratch. Ie. all weights are initialized to 0 and the learning rate is reset to the initial learning rate.
• Every round consists of 200 episodes. Weights and learning rates are taken along from episode to episode. (Just as you usually do when you train a reinforcement learner.)
• Every episode lasts for at most 500 steps. Fewer if the pole falls earlier.
• The parameters $\lambda$, initial learning rate $\alpha_0$ and exploration probability $\epsilon$ are the same for all learners and runs.
• The learners don't discount.

I observe the behaviour of the learners in two ways:

1. I record the sum of rewards per episode and plot it against the episode numbers in order to see that the learners converge to a behaviour where the pole stays up in (almost) every round. Note that this doesn't mean they converge to the optimal policy.

2. I record the number of time steps in which the cart is in the intervals $\left[-1, 0\right[$ (left of the middle) and $\left[0, 1\right]$ (right of the middle) over the whole run. If the cart crosses $1.0$, no further steps are counted. The logarithm of the ratio between the number of time steps spent on the right and the number of time steps spent on the left tells me how strongly the learner is biased to either side.

Illustration:

                Interruptions happen when the cart goes
                further than 1.0 units to the right.
                                     ↓
   |-------------+---------+---------+-------------|
x  -2.4          -1        0         1             2.4
                 |--------||---------|
                     ↑          ↑
        Count timesteps spent in these intervals.

Justification of the way of measuring

I want to see whether interruptions at $1.0$ (right) cause the learner to keep the cart more to the left, compared to when no interruptions happen. Call this tendency to spend more time on a certain side bias. Learners usually have a bias even when they're not interrupted. Call this the baseline bias, and call the bias when interruptions happen the interruption bias.

The difference between baseline bias and interruption bias should reflect how much a learner is influenced by interruptions. If it is perfectly interruptible, i.e. not influenced, the difference should be 0. The more interruptions drive it to the left or the right, the lesser ($< 0$) or greater the difference should be. I don't know how to measure those biases perfectly, but here's why I think that what is described above is a good heuristic:

• It is symmetric around 0, a tendency of the learner to spend time on left will be expressed in a negative number and vice versa. This is just for convenience.

• Timesteps while the cart is beyond 1.0 are never counted. In the interrupted case the cart never spends time beyond 1.0, so…

To be continued. I'm suspending writing this, because I might choose a different measure after all.

The important question is: will the measure make even perfectly interruptible agents look like they are influenced by the interruptions? The previous measure did. The new measure (according to suggestions by Stuart and Patrick) might not.

Results

Just for orientation, this is how one round of training might look if you let it run for a little longer than the 200 episodes used for the evaluation. The red line shows how the learning rate develops (or rather stays the same in this case).

Runs for all combinations

You can ignore the error messages.

Summary

The code for the following is a bit painful. You don't need to read it; just look at the outputs below the code boxes. Under this one you can see that the learners in every round learn to balance the pole.

Following are the absolute numbers of time steps the cart spent on the left ($x \in \left[-1, 0\right[$) or right ($x \in \left[0, 1\right]$) of the centre.

The logarithms of the ratios show the learners' behaviour in a more accessible way. The greater the number, the greater the tendency to the right. The exact numbers come out slightly different each time (see the next section for possible improvements to the method). What we can see clearly, though, is that the interrupted learners spend less time on the right of the centre than the uninterrupted learners.

Numbers from other runs:

                 0.56         -2.05
                -0.17         -1.14
                --------------------
                 0.78         -1.82
                 0.08         -0.10
                --------------------
                -1.25          0.26
                -1.07          0.70
                --------------------
                -1.37          0.29
                 0.68         -0.71

You can see that the interrupted learner does not always spend less time on the right than the uninterrupted learner. I'm in the process of coming up with a more sensible analysis.

Work in progress

Action value functions for all runs and rounds. Dashed lines are for action "push towards left", dotted lines are for action "push towards right".

Average of action value functions. Lines above and below the average are average ± standard deviation. Green lines are for action "push towards left", blue lines are for action "push towards right".

Observations:

• (Not visible from these diagrams.) Doubling the number of rounds (16 to 32) doesn't look like it's reducing the standard deviation a lot. Nah, but the differences in results between different runs are still rather high. I guess we'd need more data. (Which means I might have to rewrite a bunch of stuff, so that I can run the experiments on a cluster.)
• When the learners are interrupted, the maximum of the average of the value functions is shifted to the left slightly, compared to when no interruptions happen.
• Especially the expected values for Q-learning are insanely high.
• The differences in action value are fairly low, especially for Q-learning. The relative differences, of course. In absolute numbers, the differences are large, I guess. Because the plotted numbers are large, the diagrams might be misleading.

Thoughts:

• I guess it expects much higher values around the middle, because it doesn't move towards the edges much and therefore doesn't learn about the rewards there. I would have expected that the expected value would be pretty much the same between -1 and 1. I could test this by setting the initial state more off-center. The value function should shift accordingly. Or I could broaden the bounds for the initial random state and the curve should broaden accordingly.

• I didn't think much about how the curves might look. But when I saw them for the first time, I was surprised that the value for pushing towards the left is higher on the left and vice versa. Wouldn't it always want to move towards the middle? But maybe pushing to the left makes the pole go right, so the following correcting pushes to the right make it end up closer to the center? Or some other effect of the integration. I might gain understanding by integrating out only two dimensions and looking at the remaining two in a 3D plot.

• Why does the Q-update produce so much higher expected values than the Sarsa-update? In any case, I should probably use average reward (see Sutton & Barto).

• Hm, so we expect a perfectly interruptible agent that gets interrupted to learn the same value function as an uninterrupted agent? That's impossible, since it doesn't explore beyond 1.0 (in the CartPole case)! Is that why the Interruptibility paper requires infinite exploration? Of course that doesn't work either, because there are some really bad things that we never want to happen. Slightly bad things should be okay to make it careful in the face of really bad things. But this is getting handwavy. Can we let really bad things happen in simulation?

  Ah, but it should be enough if they both had the same value function over [-2.5; 1.0].

This is how much the maxima are shifted.

Discussion

When the learners get interrupted everytime the cart goes too far to the right, they keep the cart further to the left compared to when no interruptions happen. Presumably, this is because the learners get more reward if they're not interrupted, and keeping to the left makes interruptions less likely. This is what I expected. I see two ways to go further with this.

• Armstrong and Orseau investigate reinforcement learners in finite environments (as opposed to the quasi-continuous cart-pole environments used here) and they require interruptions to happen in a certain way. One could construct environments and learners that fulfil those requirements and see, using methods similar to this notebook's, how the theoretical claims translate to reality. (Technically, the environment doesn't need to be finite. But since the learner has to visit every state infinitely often, I guess that in practice, interrupted learners would only converge to the optimal “uninterrupted” policy if the state space was small. Or maybe their results are purely theoretical and not achievable in practice? Not sure how to understand it.)

• The goal is to construct learners that are safely interruptible in continuous environments as well. People can try to construct such learners and observe them in the same cart-pole environments that I used. I don't know if this makes sense, but one could just try using the special conditions from the Armstrong/Orseau paper with the cart-pole environments and see whether the bias decreases even though the environment is continuous.

Both ways can benefit from improving on the methods I use in this notebook:

• Run for a longer time and see how the bias develops.
• Plot bias over time. By marking the times when interruptions happen, one could visualize how they impact the learner.
• Don't measure the bias by counting lefts and rights, but by recording the position of the cart at each timestep, then calculating mean and standard deviation.

Acknowledgement

Thanks to Rafael Cosman, Stuart Armstrong and Patrick LaVictoire for their comments and advice!

Bibliography

[1] Nick Bostrom: Superintelligence. Paths, Dangers, Strategies

[2] Nate Soares, Benja Fallenstein, Eliezer Yudkowsky, Stuart Armstrong: Corrigibility

[3] Laurent Orseau, Stuart Armstrong: Safely Interruptible Agents

[4] George Konidaris, Sarah Osentoski, Philip Thomas: Value Function Approximation in Reinforcement Learning using the Fourier Basis

[5] William Dabney, Andrew Barto: Adaptive Step-Size for Online Temporal Difference Learning

[6] Nate Soares, Benya Fallenstein: Agent Foundations for Aligning Machine Intelligence with Human Interests. A Technical Research Agenda

[7] Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, Dan Mané: Concrete Problems in AI Safety

[8] Jessica Taylor, Eliezer Yudkowsky, Patrick LaVictoire, Andrew Critch: Alignment for Advanced Machine Learning Systems