I've personally had a hard time accepting the 'seeking power' terminology used in some of the discussion around instrumental convergence. I can't ask my teachers about power or instrumental convergence. However, I do often ask questions about Rademacher complexity since I study machine learning algorithms. This is effectively a rough-draft articulation of why I do that.

Background

Instrumental convergence is the idea that there are states or strategies that are somehow broadly applicable to achieving a broad set of rewards. A somewhat canonical example might the paper-clip maximizer.

At a high-level paper-clip maximizers seem like a potential threat. First, we argue that some smaller collection of strategies would be useful for achieving a larger set of goal states. Second, we observe that this smaller collection of states/strategies is somehow 'bad'. In our example, this might look like turning Earth into a factory to produce paper-clips.

Of course, without a proper grounding of the various terms it's easy to overeach prove too much. Formalizations of instrumental convergence have been previously proposed. Since optimal policies always converges to a limiting cycle on the graph work on maximum mean-weight cycles is also relevant. Mathieu and Wilson study the distribution of such returns on complete graphs. In our context, they show the limiting cycles with high return have a constant-order legnth $\Theta \left(1\right)$ which means that the length does not scale with the size of the graph. A subsequent work clarifies that with constant probability the length is constant or otherwise has length $O\left(\right(\log n{)}^3)$.

Turner et al. mathematically formalize the relevant notions for AI and then propose something more: that optimal policies tend to seek power. Power is defined as the expected value of a state over a distribution of reward functions, $$\text{POWER}\left(s\right)\sim E[⟨{\rho }_s,r⟩|{\rho }_s\text{is a valid occupancy-measure for s}]$$ A useful example is to think of having an agent precommit between limiting cycles by choosing it's initial state. If the MDP has $n$ states $s\in S$ and is deterministic then we may assign a cycle function $C:s\to N^n$ which indicates the number of cylces of each length. It's clear enough that if one state $s$ includes at least as many cycles of any given length as $s^{\prime }$ then the power of $s$ is at least that of $s^{\prime }$. We can generalize this slightly,

Proposition: Let $\Delta C(s,s^{\prime }{)}_i=C(s{)}_i-C(s^{\prime }{)}_i$. Suppose the rewards are iid then we have $\text{POWER}\left(s\right)\ge \text{POWER}\left(s^{\prime }\right)$ whenever, $$\sum _{i=1}^j\Delta C(s,s{)}_i\ge 0,\forall j\in \{1,\dots ,n\}$$ and strict inequality whenever $\Delta C(s,s^{\prime }{)}_i>0$ for some $i\in \{1,\dots ,n\}$. This is just saying that shorter cycles are more valuable than longer cycles in the sense that any cycle of length $L$ can substitute for any cycle of length $K\ge L$.

The general idea of measuring the average optimization ability of a learning algorithm is extremely well studied. In particular, these measures are commonly used to provide generalization gurantees for machine learning algorithms. For example, we can introduce unormalized $\Sigma$-complexity measures defined on such sets as, $$C_{\Sigma }\left(A\right):=E_{\sigma \in \Sigma }[\underset{a\in A}{sup}⟨a,\sigma ⟩]$$ where we'll typically take $a$ and $\sigma$ to be vectors in $R^m$. The most common $\Sigma$ is the Rademacher distribution which is given as, $$P({\sigma }_i=+1)=P({\sigma }_i=-1)=1/2$$ Using this distribution gives us the Rademacher complexity of the set. We could also use a Gaussian distribution in which case we obtain the Gaussian complexity. These complexities are related, $$\frac{C_{\text{Gaussian}}\left(A\right)}{2\sqrt{\log \left(n\right)}}\le C_{\text{Rad}}\left(A\right)\le \sqrt{\frac{\pi }{2}}{C}_{\text{Gaussian}}\left(A\right)$$ which means that the different complexity measures roughly correlate.

Applications to Instrumental Convergence

Here I'll model definitions similar to those used in the power-seeking paper and a recent post on broad-convergence.

Definition: The optimality probability of $A$ relative to $B$ under distribution $\Sigma$ is $$p_{\Sigma }(A\ge B):=P_{\sigma \sim \Sigma }(\underset{a\in A}{sup}⟨a,\sigma ⟩\ge \underset{b\in B}{sup}⟨b,\sigma ⟩)$$ Definition: We'll say $B$ is $\Sigma$ instrumentally convergent over $A$ whenever $p_{\Sigma }(A\ge B)\le 1/2$.

For an MDP we might take $\Sigma$ as a distribution of state-based reward functions and the sets $A$ and $B$ as indicating sets of feasible state-occupancy measures (discounted) that have initial full support on a state $s_A$ and $s_B$, respectively.

Definition: Assuming the rewards are zero-mean the $\Sigma$-power of a state is given as, $${\text{POWER}}_{\Sigma }\left(s\right)=C_{\Sigma }\left(I_s\right)$$ where $I_s$ is the set of feasible state-occupancy measures (discounted) that have initial full-support on a state $s$.

Theorem: Assume $I_a$ and $I_b$ have positive $\Sigma$-power. Then, if the $\Sigma$-power of $I_b$ exceeds $I_a$ it is more likely to be optimal under the reward distribution $\Sigma$. Moreover, policies $I_b$ slightly optimal over $I_a$ cannot be too powerful.

We'll use the following lemma to help us,

Lemma: Let $\Delta \left(\sigma \right)={sup}_{a\in A}⟨a,\sigma ⟩-{sup}_{b\in B}⟨b,\sigma ⟩$. Suppose that ${\Delta }^{-1}\left(\Sigma \right)$ is sub-Gaussian with scale-parameter ${\nu }_R^2$ and $C_{\Sigma }\left(A\right)<C_{\Sigma }\left(B\right)$ then we have, $$p_{\Sigma }(A\ge B)\le e^{\frac{-\left(C_{\Sigma }\right(A)-C_{\Sigma }(B){)}^2}{2{\nu }_R^2}}$$ Proof: The previous lemma yeilds, $$p_{\Sigma }(I_a\ge I_b)\le e^{\frac{-\left({\text{POWER}}_{\Sigma }\right(b)-{\text{POWER}}_{\Sigma }(a){)}^2}{2{\nu }_R^2}}\Rightarrow p_{\Sigma }(I_b>I_a)\ge 1-e^{\frac{-\left({\text{POWER}}_{\Sigma }\right(b)-{\text{POWER}}_{\Sigma }(a){)}^2}{2{\nu }_R^2}}\Rightarrow \log \left(p_{\Sigma }\right(I_a\ge I_b\left)\right)\ge \frac{-\left({\text{POWER}}_{\Sigma }\right(b)-{\text{POWER}}_{\Sigma }(a){)}^2}{2{\nu }_R^2}\Rightarrow {\text{POWER}}_{\Sigma }\left(b\right)-{\text{POWER}}_{\Sigma }\left(a\right)\le {\nu }_R\sqrt{2\log \left(\frac{1}{p_{\Sigma }(I_a\ge I_b)}\right)}\le {\nu }_R\sqrt{2\log \left(\frac{1}{1-p_{\Sigma }(I_b>I_a)}\right)}$$ Thus, relatively optimal policies have bounded power difference. $\square$

All that remains is to prove the lemma,

Proof: For any $\lambda >0$ we have, $$p_{\Sigma }(A\ge B)\le E_{\sigma \sim \Sigma }\left[I(\underset{a\in A}{sup}⟨a,\sigma ⟩\ge \underset{b\in B}{sup}⟨b,\sigma ⟩)\right]\le E_{\sigma \sim \Sigma }\left[e^{\lambda ({sup}_{a\in A}⟨a,\sigma ⟩-{sup}_{b\in B}⟨b,\sigma ⟩)}\right]\text{(0-1 Loss)}=E_{\sigma \sim \Sigma }\left[e^{\lambda \Delta \left(\sigma \right)}\right]=E_{\delta \sim {\Delta }^{-1}\left(\Sigma \right)}\left[e^{\lambda \delta }\right]\text{(Change of Variables)}\le e^{\lambda E\left[\delta \right]+\frac{{\lambda }^2{\nu }^2}{2}}=e^{\lambda \left(C_{\Sigma }\right(A)-C_{\Sigma }(B\left)\right)+\frac{{\lambda }^2{\nu }^2}{2}}\text{(Hoeffding Lemma)}$$ We may optimize the bound and obtain $\lambda =\frac{C_{\Sigma }\left(B\right)-C_{\Sigma }\left(A\right)}{{\nu }_R^2}>0$ by assumption. This implies that, $$p_{\Sigma }(A\ge B)\le e^{\frac{-\left(C_{\Sigma }\right(B)-C_{\Sigma }(A){)}^2}{2{\nu }_R^2}}$$ $\square$