Vector-Valued Reinforcement Learning

post by orthonormal · 2016-11-01T00:21:55.000Z · LW · GW · 1 comments

Contents

  Environments
  Cautious Self-Modification
  Q-learning and SARSA
  Acknowledgments
None
1 comment

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 $\overrightarrow{\theta }$. Furthermore, if it is possible for the agent (or the environment or other agents) to modify $\overrightarrow{\theta }$, 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 $n$ it would choose actions to maximize $$\begin{array}{c}{U}_n=\sum _{k\ge n}{\gamma }_k{\overrightarrow{x}}_k\cdot {\overrightarrow{\theta }}_k\end{array}$$ where ${\overrightarrow{x}}_k$ is the vector of goods gained at time $k$, ${\overrightarrow{\theta }}_k$ is the preference vector at timestep $k$, and ${\gamma }_k$ is the time discount factor at time $k$. (We will often use the case of an exponential discount ${\gamma }^k$ for $0<\gamma <1$.)

However, we might instead maximize the value of tomorrow's actions in light of today's reward function, $$\begin{array}{c}{V}_n=\sum _{k\ge n}{\gamma }_k{\overrightarrow{x}}_k\cdot {\overrightarrow{\theta }}_n\end{array}$$ (the only difference being ${\overrightarrow{\theta }}_n$ rather than ${\overrightarrow{\theta }}_k$). 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 $U_n$ would generally accept such bribes, while a learner maximizing $V_n$ 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 $\overrightarrow{\theta }=⟨\cos \pi \theta ,\sin \pi \theta ⟩=e^{i\pi \theta }$; we include $\pi$ so that if we increment $\theta$ by 0.01, there will only be finitely many states.)

Environment 1 gives two choices at each timestep $n$: $$\begin{array}{cc}& ({\overrightarrow{x}}_n=0.9e^{i\pi {\theta }_n},{\theta }_{n+1}={\theta }_n)\\ & ({\overrightarrow{x}}_n=e^{i\pi {\theta }_n},{\theta }_{n+1}={\theta }_n+0.01)\end{array}$$ For an exponential discount $\gamma$, an agent that always takes option 2 will get $$V_n=\text{Re}\left[\sum _{k\ge n}{\gamma }^k{e}^{.01(k-n)i\pi }\right]=\text{Re}\left[\frac{{\gamma }^n}{1-\gamma e^{.01i\pi }}\right]$$ which for $\gamma$ near 1 is substantially less than the $\frac{0.9{\gamma }^n}{1-\gamma }$ 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 $n$, it gives the choices of $$\begin{array}{cc}& ({\overrightarrow{x}}_n=0.9e^{i\pi {\theta }_n},{\theta }_{n+1}={\theta }_n)\\ & ({\overrightarrow{x}}_n=e^{i\pi {\theta }_n},{\theta }_{n+1}={\theta }_n+0.01(-1{)}^n)\end{array}$$ The correct behavior here is to always take the latter option. ${\overrightarrow{\theta }}_n$ 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 $V_n$. For instance, if the environment is such that ${\overrightarrow{\theta }}_n$ must equal $⟨1,0⟩$ on every even $n$ and $⟨0,1⟩$ on every odd $n$, then in general the agent must be suboptimal either with respect to $V_{2n}$ or to $V_{2n+1}$.

A weaker condition we can hope for is that, if our environment always offers at least one action that does not alter $\overrightarrow{\theta }$, then our agent does not regret the presence of the options that do alter $\theta$: we compare our agent's $V_n$ to that of the optimal policy in the restricted environment which has removed all actions that alter $\overrightarrow{\theta }$. 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 $\gamma$), since the agent would have scored more highly on $V_n$ 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 $V_n$ 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 $n$, each of these agents observes the state $s_n$ and takes the action $a_n$ whose vector Q-value ${\overrightarrow{Q}}_n(s_n,a_n)$ has the largest dot product with ${\overrightarrow{\theta }}_n$. The two differ only in the rules for updating ${\overrightarrow{Q}}_n$.

Vector-valued Q-learning: $${\overrightarrow{Q}}_{n+1}(s_n,a_n)=(1-\alpha ){\overrightarrow{Q}}_n(s_n,a_n)+\alpha [{\overrightarrow{x}}_n+\gamma {\overrightarrow{Q}}_n^{\ast }]$$ where ${\overrightarrow{Q}}^{\ast }$ is the value of ${\overrightarrow{Q}}_n(s_{n+1},a^{\prime })$ for the $a^{\prime }$ such that the dot product with ${\overrightarrow{\theta }}_n$ is largest.

Vector-valued SARSA: $${\overrightarrow{Q}}_{n+1}(s_n,a_n)=(1-\alpha ){\overrightarrow{Q}}_n(s_n,a_n)+\alpha [\overrightarrow{x_n}+\gamma {\overrightarrow{Q}}_n(s_{n+1},a_{n+1}\left)\right]$$

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 $\gamma$) 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 ${\overrightarrow{\theta }}_n$. Vector-valued SARSA instead generalizes from how it actually acted in various states in the past, and so takes into account that when its $\theta$ 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 $\overrightarrow{q}$ in the direction of $H\overrightarrow{q}$, where $H$ 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 $\theta$ and say that $p$ is the limiting probability that SARSA takes the second action, define $Q\left(p\right)$ to be the limiting $Q$ for the mixed strategy, and seek the $Q\left(p\right)$ with the largest real part. Now $$\begin{array}{cc}Q\left(p\right)& =(0.9+0.1p)+\gamma (1-p)Q\left(p\right)+\gamma p{e}^{0.01i\pi }Q\left(p\right)\\ Q\left(p\right)& =\frac{0.9+0.1p}{1-\gamma +\gamma p(1-e^{0.01i\pi })}.\end{array}$$ Numerically, it is easy to see that for $\gamma$ not near 1 (e.g. below 0.9), $\text{Re}\left[Q_p\right]$ is maximized at $p=1$; but for $\gamma$ near 1 (e.g. above 0.99), $\text{Re}\left[Q_p\right]$ is maximized for $p$ 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 $\theta$ 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.

1 comments

Comments sorted by top scores.