(In)action rollouts

[Stuart_Armstrong]

Overall summary post here.

I’ve previously looked at subagents in the context of stepwise inaction baselines. But there have been improvements to the basic stepwise inaction design, to include inaction rollouts. I’ll be looking at those in this post.

The baseline

The stepwise inaction baseline compares $s_t$, the current state, with $s_t^{\prime }$, what the current state would have been had the agent previously taken the noop action ${\varnothing }_{t-1}$, instead of $a_{t-1}$, its actual action.

Fix a policy ${\pi }_0$. Let $s_{t+\tau }^{\left(t\right)}$ be the state the environment would be in if the agent had followed ${\pi }_0$ from state $s_t$, for $\tau$ turns. Let $s_{t+\tau }^{\prime \left(t\right)}$ be the same, except that it started from state $s_t^{\prime }$ instead of $s_t$.

The inaction rollout has ${\pi }_0$ being the noop policy, but that is not necessary. The basic idea is to capture delayed impacts of ${\varnothing }_{t-1}$ by comparing not just $s_t$ and $s_t^{\prime }$, but the $s_{t+\tau }^{\left(t\right)}$ and $s_{t+\tau }^{\prime \left(t\right)}$ as well.

Given some value function $v_k$, define $V_k$ so that $V_k\left(s\right)={max}_{\pi }{v}_k(s,\pi )$. Or, equivalently, if ${\pi }_k^{\ast }$ is the policy that maximises $V_k$, $V_k\left(s\right)=v_k(s,{\pi }_k^{\ast })$. Then for a discount factor $\gamma$ define the rollout value of a state ${\tilde{s}}_t$ as

$$R{V}_k\left({\tilde{s}}_t\right)=(1-\gamma )\sum _{j=0}^{\infty }{\gamma }^j{V}_k\left({\tilde{s}}_{t+k}^{\left(t\right)}\right).$$

This is just the discounted future values of $V_k$, given ${\tilde{s}}_t$ and the policy ${\pi }_0$.

The impact measure is then defined, as in this post, as

$$D_A(s_t;s_t^{\prime })=\sum _{k\in K}{w}_{k}f\left(R{V}_k\right(s_t)-R{V}_k(s_t^{\prime }\left)\right),$$

with $R{V}_k$ replacing $V_k$.

To get away with a subagent

I will make one extra assumption here: that $A$ grants $SA$ knowledge of the policy that $A$ is following^[1].

As in this post, assume that the subagent is constructed in a single action $a_{SA}$. And, after building the subagent, the agent $A$ will only do $\varnothing$, so that there are no subsequent penalties (hence $s_{t+j}^{\prime }=s_{t+j}$, so $s_{t+j+\tau }^{\prime (t+j)}=s_{t+j+\tau }^{(t+j)}$ and the $R{V}_k$ are strictly identical). If the first action of ${\pi }_0$ is ${\varnothing }_t$, then $A$ will instead do ${\varnothing }_t^{\prime }$ on that turn.

So we only need to worry about the penalty between $s_t$ (following after $a_{SA}$) and $s_t^{\prime }$ (following after ${\varnothing }_{t-1}$).

But now note that $R{V}_k$ itself is just a value measure; we could write it $V_k^{\prime }$. Then $A$ just has to program $SA$ so that, if $A$ implements ${\pi }_0$ followed by ${\pi }_k^{\ast }$ after $\tau$ turns, then $SA$ will act to ensure that $V_k^{\prime }\left(s_t\right)$ (a term that is a sum of various value functions) is equal to $V_k^{\prime }\left(s_t^{\prime }\right)$ (from $t$ onward, a constant).

Stricter impact measures/​counterfactuals

There is something slightly dubious about the previous section. It assumes that $A$ could counterfactually implement ”${\pi }_0$ followed by ${\pi }_k^{\ast }$ after $\tau$ turns” (which necessary to define $V_k\left(s_{t+\tau }^{\left(t\right)}\right)$), but also that $SA$ knows $A$’s policy.

But does that mean that $SA$ knows at $t+1$ that $A$ is following that policy, or does it just know that $A$ is following ${\pi }_0$, to be followed at some later date by some ${\pi }_k^{\ast }$? This makes a difference, because in the second case, $SA$ doesn’t know $k$ from turn $t+1$, so has to prepare for all $k\in K$.

Which is true depends on how counterfactuals are defined. But we can avoid the whole issue by using a stricter impact measure, interchanging $f$ and weighted summation:

$$D_A(s_t;s_t^{\prime })=\sum _{k\in K}{w}_k\sum _{j=0}^{\infty }{\gamma }^{j}f\left(V_k\right(s_{t+j}^{\left(t\right)})-V_k(s_{t+j}^{\prime \left(t\right)}\left)\right).$$

This looks like an impact penalty with an inaction baseline—except that it starts at $s_{t-1}$, rather than $s_0$, and uses ${\pi }_0$ rather than inaction. Those changes don’t affect the results found here, so $SA$ will just behave as it does in that post… until it’s clear that $A$ is not following ${\pi }_0$.

Because $s_{t+j}^{\left(t\right)}$ is defined counterfactually (using ${\pi }_0$), even this stricter impact measure is weaker than the inaction baseline. As soon as $SA$ knows that $A$ is not following ${\pi }_0$, it has almost no further restrictions upon its actions.

The “almost” comes from $s_{t+0}^{\left(t\right)}=s_t$ which is actually defined, not counterfactually defined. But that’s the same situation as a stepwise inaction baseline without rollouts.

---

1. ↩︎

   One way this could happen, is if $A$ can add extra information to its action without affecting the outside world; such that $a_t$ could include a “hey, I’m not following ${\pi }_0$, just to let you know”.

[Vika]

I don’t understand this proposal so far. I’m particularly confused by the last paragraph in the “to get away” section:

• What does it mean in this context for A to implement a policy? I thought A was building a subagent and then following ${\pi }_0$ forever, thus not following ${\pi }_k^{\ast }$ for any $k$ at any point.

• If A follows ${\pi }_0$ for $\tau$ turns and then follows ${\pi }_k^{\ast }$, how are $\tau$ and $k$ chosen?

• It’s not clear to me that SA can act to ensure the baseline value of $V_k^{\prime }$ for all values of $k$ and $\tau$ unless it does nothing.

I think it might help to illustrate this proposal in your original gridworld example to make it clearer what’s going on. As far as I can tell so far, this does not address the issue I mentioned earlier where if the subagent actually achieves any of the auxiliary rewards, subagent creation will be penalized.

[Stuart_Armstrong]

I agree I should re-do these all with examples. But, to answer your questions as far as possible:

What $A$ will do: $\varnothing$ forever (maybe with some extra info for the $SA$).

What $A$ would counterfactually do (to define $V_k\left(s_{t+\tau }^{\left(t\right)}\right)$): ${\pi }_0$ for $\tau$ turns (the ${\pi }_0$ rollout, to define $s_{t+\tau }^{\left(t\right)}$) followed by ${\pi }_R^{\ast }$ (to define the $V_k$ aspect). Call this ${\pi }_{0,\tau ,k}^{\ast }$.

The penalty is defined in terms of these $V_k\left(s_{t+\tau }^{\left(t\right)}\right)$, entirely counterfactual except for $\tau =0$.

What $SA$ must do: iff $A$ follows ${\pi }_{0,\tau ,k}^{\ast }$, then $SA$ must ensure that $V_k\left(s_{t+\tau }^{\left(t\right)}\right)=V_k\left(s_{t+\tau }^{\prime \left(t\right)}\right)$.

So a key question is: how early can $SA$ detect if $A$ is following ${\pi }_{0,\tau ,k}^{\ast }$? If it can detect this immediately, then it can immediately implement the policy for ensuring that $V_k\left(s_{t+\tau }^{\left(t\right)}\right)=V_k\left(s_{t+\tau }^{\prime \left(t\right)}\right)$ (for the stricter impact measure) or the much easier $B{V}_k\left(s_t\right)=B{V}_k\left(s_t^{\prime }\right)$ (for the original impact measure).

If it has to wait $\tau$ turns to be sure, then it needs to preserve its power to control many different $k$.

Now, $A$ will never actually follow ${\pi }_{0,\tau ,k}^{\ast }$, so the penalty is (almost) entirely counterfactual. But the counterfactual abilities of $SA$ will determine the penalty; $SA$ is rewarded for quickly gaining control of the rewards.

In practice, $A$ will signal early on that it’s not following ${\pi }_{0,\tau ,k}^{\ast }$. Maybe there’s a very small impact action, ${\varnothing }^{ϵ}$, with a tiny penalty. Then $A$ would like to use that to signal to $SA$ that its not in the counterfactual world where it is following ${\pi }_{0,\tau ,k}^{\ast }$. So long as ${\pi }_0$‘s first action isn’t ${\varnothing }^{ϵ}$, that signal is enough (of course, if ${\pi }_0$’s first action isn’t $\varnothing$, then $\varnothing$ is a sufficient signal).

After getting that signal, the subagent is (almost) completely unconstrained, because the constraints are counterfactual, in a world it knows it isn’t in.

The one mild constraint remaining comes from $s_{t+0}^{\left(t\right)}=s_t$, which is not a counterfactually defined state (though $V_k\left(s_t\right)$ is a counterfactually defined property of that state).

I’ll try and write up a further clarification of this.