Paper deep dive
Parametrically Retargetable Decision-Makers Tend to Seek Power
Alexander Matt Turner, Prasad Tadepalli
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/12/2026, 7:38:57 PM
Summary
The paper explores how 'parametrically retargetable' decision-making algorithms, which are common in AI, inherently incentivize power-seeking behavior. By defining retargetability as a functional property where parameter permutations can swap optimal outcomes, the authors demonstrate that for a wide range of decision-making procedures, agents are statistically more likely to choose actions that preserve optionality and resources (power-seeking) rather than those that limit them, using Montezuma's Revenge as a case study.
Entities (6)
Relation Signals (3)
Alexander Matt Turner → authored → Parametrically Retargetable Decision-Makers Tend to Seek Power
confidence 100% · Parametrically Retargetable Decision-Makers Tend To Seek Power Alexander Matt Turner, Prasad Tadepalli
Parametric Retargetability → causes → Power-Seeking
confidence 90% · We discover that many decision-making functions are retargetable, and that retargetability is sufficient to cause power-seeking tendencies.
AI Agents → exhibit → Power-Seeking
confidence 85% · Eventually, retargetable training procedures may train real-world agents which seek power over humans.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:If capable AI agents are generally incentivized to seek power in service of the objectives we specify for them, then these systems will pose enormous risks, in addition to enormous benefits. In fully observable environments, most reward functions have an optimal policy which seeks power by keeping options open and staying alive. However, the real world is neither fully observable, nor must trained agents be even approximately reward-optimal. We consider a range of models of AI decision-making, from optimal, to random, to choices informed by learning and interacting with an environment. We discover that many decision-making functions are retargetable, and that retargetability is sufficient to cause power-seeking tendencies. Our functional criterion is simple and broad. We show that a range of qualitatively dissimilar decision-making procedures incentivize agents to seek power. We demonstrate the flexibility of our results by reasoning about learned policy incentives in Montezuma's Revenge. These results suggest a safety risk: Eventually, retargetable training procedures may train real-world agents which seek power over humans.
Tags
Links
- Source: https://arxiv.org/abs/2206.13477
- Canonical: https://arxiv.org/abs/2206.13477
Trouble viewing inline? Open PDF directly →
Full Text
107,996 characters extracted from source content.
Expand or collapse full text
Parametrically Retargetable Decision-Makers Tend To Seek Power Alexander Matt Turner, Prasad Tadepalli Oregon State University turneale@, tadepall@eecs.oregonstate.edu Abstract If capableAIagents are generally incentivized to seek power in service of the objectives we specify for them, then these systems will pose enormous risks, in addition to enormous benefits. In fully observable environments, most reward functions have an optimal policy which seeks power by keeping options open and staying alive [Turner et al., 2021]. However, the real world is neither fully observable, nor must trained agents be even approximately reward-optimal. We consider a range of models ofAIdecision-making, from optimal, to random, to choices informed by learning and interacting with an environment. We discover that many decision-making functions areretargetable, and that retargetability is sufficient to cause power-seeking tendencies. Our functional criterion is simple and broad. We show that a range of qualitatively dissimilar decision-making procedures incentivize agents to seek power. We demonstrate the flexibility of our results by reasoning about learned policy incentives in Montezuma’s Revenge. These results suggest a safety risk: Eventually, retargetable training procedures may train real-world agents which seek power over humans. 1 Introduction Bostrom [2014], Russell [2019] argue that in the future, we may know how to train and deploy superintelligentAIagents which capably optimize goals in the world. Furthermore, we would not want such agents to act against our interests by ensuring their own survival, by gaining resources, and by competing with humanity for control over the future. Turner et al. [2021] show that most reward functions have optimal policies which seek power over the future, whether by staying alive or by keeping their options open. Some Markov decision processes (MDPs) cause there to bemore waysfor power-seeking to be optimal, than for it to not be optimal. Analogously, there are relatively few goals for which dying is a good idea. We show that a wide range of decision-making algorithms produce these power-seeking tenden- cies—they are not unique to reward maximizers. We develop a simple, broad criterion of functional retargetability (definition 3.5) which is a sufficient condition for power-seeking tendencies. Crucially, these results allow us to reason about what decisions are incentivized by most algorithm parameter inputs, even when it is impractical to compute the agent’s decisions for any given parameter input. Useful “general”AIagents could be directed to complete a range of tasks. However, we show that this flexibility can cause theAIto have power-seeking tendencies. In section 2 and section 3, we discuss how a “retargetability” property creates statistical tendencies by which agents make similar decisions for a wide range of parameter settings for their decision-making algorithms. Basically, if a decision-making algorithm is retargetable, then for every configuration under which a decision- making algorithm does not choose to seek power, there exist several reconfigurations which do induce power-seeking. More formally, for every decision-making parameter settingθwhich does not induce 36th Conference on Neural Information Processing Systems (NeurIPS 2022). arXiv:2206.13477v2 [cs.AI] 11 Oct 2022 power-seeking,n-retargetability ensures we can injectively mapθtonparametersθ ′ 1 ,...,θ ′ n which doinduce power-seeking. Equipped with these results, section 4 works out agent incentives in the Montezuma’s Revenge game. Section 5 speculates that increasingly useful and impressive learning algorithms will be increasingly retargetable, and how retargetability can imply power-seeking tendencies. By this reasoning, increasingly powerfulRLtechniques may (eventually) train increasingly competent real- world power-seeking agents. Such agents could be unaligned with human values [Russell, 2019] and—we speculate—would take power from humanity. 2 Statistical tendencies for a range of decision-making algorithms Turner et al. [2021] consider the Pac-Man video game, in which an agent consumes pellets, navigates a maze, and avoids deadly ghosts (Figure 1). Instead of the usual score function, Turner et al. [2021] consider optimal action across a range of state-based reward functions. They show that most reward functions have an (average-)optimal policy which avoids immediate death in order to navigate to a future terminal state. 1 · leftright Figure 1: If Pac-Man goesleft, he dies to the ghost and ends up in theoutcome. If he goesright, he can reach theandterminal states. Our results show that optimality is not required. Instead, if the agent’s decision-making isparamet- rically retargetablefrom death to other outcomes, Pac-Man avoids the ghost under most decision- making parameter inputs. To build intuition about these notions, consider three outcomes (i.e. terminal states): Immediate death to a nearby ghost, consuming a cherry, and consuming an apple. LetA : =andB : =,. For simplicity of exposition, we assume these are the three possible terminal states. Suppose that in some fashion, the agent probabilistically decides on an outcome to induce. Letptake as input a set of outcomes and return the probability that the agent selects one of those outcomes. For example,p()is the probability that the agent selects, andp(,)is the probability that the agent escapes the ghost and ends up in an apple or cherry terminal state. But this just amounts to a probability distribution over the terminal states. We want to examine how decision-makingchanges as we swap out the parameter inputs to the agent’s decision-making algorithm with decision-making parameter spaceΘ. We then letp(X|θ)take as input a set of outcomesXand a decision-making algorithm parameter settingθ∈Θ, and return the probability that the agent chooses an outcome in X. We first consider agents which maximize terminal-state utility, following Turner et al. [2021] (in their language, “average-reward optimality”). Suppose that the agent has a utility function parameter uassigning a real number to each of the three outcomes. Then the relevant parameter space is the agent’s utility functionu∈Θ : =R 3 .p max (A|u)indicates whetherhas the most utility: u()≥max(u(),u()). Consider the utility functionuin Table 1. Sincehas strictly maximal utility, the agent selects:p max (A|u) = 1>0 =p max (B|u). 1 We use “reward function” somewhat loosely in implying that reward functions reasonably describe a trained agent’s goals. Turner [2022] argues that capableRLalgorithms do not necessarily train policy networks which are best understood as optimizing the reward function itself. Rather, they point out that—especially in policy-gradient approaches—reward provides gradients to the network and thereby modifies the network’s generalization properties, but doesn’t ensure the agent generalizes to “robustly optimizing reward” off of the training distribution. 2 However, most “variants" ofuhave an optimal policy which stays alive. That is, for everyufor which immediate death is optimal but immediate survival is not, we can swap the utility ofe.g.and via permutationφ ↔ to produce a new utility functionu ′ : =φ ↔ ·ufor which staying alive (right) is strictly optimal. The same kind of argumentation holds forφ ↔ . Table 1 suggests a counting argument. For every utility functionufor whichis optimal, there are two unique utility functionsφ 1 ·u,φ 2 ·uunder which eitheroris optimal. Utility function u 1050 φ ↔ ·u5100 φ ↔ ·u0510 u ′ 1005 φ ↔ ·u ′ 0105 φ ↔ ·u ′ 5010 Table 1: The highest-utility outcome is bolded. BecauseBcontains more outcomes thanA, most utility functions incentivize the agent to stay alive and therefore select a state fromB. For every utility functionuoru ′ which makesstrictly optimal,twoof its permuted variants make an outcome inB : =,strictly optimal. We permuteuby swapping the utility ofand the utility of, using the permutationφ ↔ . The expression “φ ↔ ·u” denotes the permuted utility function. In section 3, we will generalize this particular counting argument. Definition 3.3 shows a functional condition (retargetability) under which the agent decides to avoid the ghost, for most parameter inputs to the decision-making algorithm. Given this retargetability assumption, proposition 3.4 roughly shows that mostθ∈Θinducep(B|θ)≥p(A|θ). First, consider two more retargetable decision-making functions: Uniformly randomly picking a terminal state.p rand ignores the reward function and assigns equal probability to each terminal state in Pac-Man’s state space. Choosing an action based on a numerical parameter.p numerical takes as input a natural number θ∈Θ : =1,...,6and makes decisions as follows: p numerical (A|θ) : = 1ifθ= 1, 0otherwise. p numerical (B|θ) : = 1−p numerical (A|θ).(1) In this situation,Θis acted on by permutations over6elementsφ∈S 6 . Thenp numerical is retargetable fromAtoBviaφ k : 1↔k,k6= 1. p max ,p rand , andp numerical encode varying sensitivities to the utility function parameter input, and to the internal structure of the Pac-Man decision process. Nonetheless, they all are retargetable from AtoB. For an example of anon-retargetable function, considerp stubborn (X|θ) : =1 X=A which returns1forAand0otherwise. However, we cannot explicitly define and evaluate more interesting functions, such as those defined by reinforcement learning training processes. For example, given that we provide such-and-such reward function in a fixed task environment, what is the probability that the learned policy will take actiona? We will analyze such procedures in section 4. We now motivate the title of this work. For most parameter settings, retargetable decision-makers induce an element of the larger set of outcomes. Such decision-makerstend toinduce an element of a larger set of outcomes (with the “tendency” being taken across parameter settings). Consider that the larger set of outcomes,can only be induced if Pac-Man stays alive. Intuitively, navigating to this larger set ispower-seekingbecause the agent retains more optionality (i.e. the agent can’t do anything when dead). Therefore,parametrically retargetable decision-makers tend to seek power. 3 Formal notions of retargetability and decision-making tendencies Section 2 informally illustrated parametric retargetability in the context of swapping which utilities are assigned to which outcomes in the Pac-Man video game. For many utility-based decision-making 3 algorithms, swapping the utility assignments also swaps the agent’s final decisions. For example, if death is anti-rational, and then death’s utility is swapped with the cherry utility, then now the cherry is anti-rational. In this section, we formalize the notion of parametric retargetability and of “most” parameter inputs producing a given result. In section 4, we will use these formal notions to reason about the behavior ofRL-trained policies in the Montezuma’s Revenge video game. To define our notion of “retargeting”, we assume thatΘis a subset of a set acted on by symmetric groupS d , which consists of all permutations onditems (e.g. in theRLsetting, this might represent states or observations). A parameterθ’sorbitis the set ofθ’s permuted variants. For example, Table 1 lists the six orbit elements of the parameteru. Definition 3.1(Orbit of a parameter).Letθ∈Θ. Theorbitofθunder the symmetric groupS d is S d ·θ : = φ·θ|φ∈S d . Sometimes,Θis not closed under permutation. In that case, theorbit insideΘisOrbit| Θ (θ) : = (S d ·θ)∩Θ. Letp(B|θ)return the probability that the agent chooses an outcome inBgivenθ. To express “B-outcomes are chosen instead ofA-outcomes”, we writep(B|θ)> p(A|θ). However, even “retargetable” decision-making functions (defined shortly) generally won’t choose aB-outcome for everyinputθ. Instead, we consider theorbit-level tendenciesof such decision-makers, showing that for every parameter inputθ∈Θ, most ofθ’s permutations push the decision towardsBinstead ofA. Definition 3.2(Inequalities which hold for most orbit elements).SupposeΘis a subset of a set acted on byS d , the symmetric group ondelements. Letf : A,B×Θ→Rand letn≥1. We write f(B|θ)≥ n most:Θ f(A|θ)when, forallθ∈Θ, the following cardinality inequality holds: ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|f(B|θ ′ )> f(A|θ ′ ) ∣ ∣ ∣ ≥n ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|f(B|θ ′ )< f(A|θ ′ ) ∣ ∣ ∣ . (2) For example, Table 1 illustrates the tendency ofu’s orbit to makeB : =,optimal overA : =. Turner et al. [2021]’s definition 6.5 is the special case of definition 3.2 wheren= 1,d=|S|(the number of states in the consideredMDP), andΘ⊆∆(R |S| ). As explored previously,p rand ,p max , andp numerical are retargetable: For allθ∈Θsuch thatis chosen over,, we can permuteθto obtainφ·θunder which the opposite is true. More generally, we can consider retargetability from some setAto some setB. 2 Definition 3.3(Simply-retargetable function).LetΘbe a set acted on byS d , and letf : A,B× Θ→R. If∃φ∈S d : ∀θ A ∈Θ : f(B|θ A )< f(A|θ A ) =⇒f(A|φ·θ A )< f(B|φ·θ A ), thenfis a(Θ,A simple →B)-retargetable function. Simple retargetability suffices for most parameter inputs topto choose Pac-Man outcome setB overA. 3 In that case,Bcannot be retargeted back toAbecause|B|= 2>1 =|A|.p max ’s simple retargetability arises in part due toBhaving more outcomes. Proposition 3.4(Simply-retargetable functions have orbit-level tendencies). Iffis(Θ,A simple →B)-retargetable, thenf(B|θ)≥ 1 most:Θ f(A|θ). We now want to make even stronger claims—how muchof each orbit incentivizesBoverA? Turner et al. [2021] asked whether the existence of multiple retargeting permutationsφ i guarantees a quantitative lower-bound on the fraction ofθ∈Θfor whichBis chosen. Theorem 3.6 answers “yes.” Definition 3.5 (Multiply retargetable function).LetΘbe a subset of a set acted on byS d , and let f : A,B×Θ→R. fis a(Θ,A n →B)-retargetable functionwhen, for eachθ∈Θ, we can choose permutations φ 1 ,...,φ n ∈S d which satisfy the following conditions: Consider anyθ A ∈Orbit| Θ,A>B (θ) : = θ ∗ ∈Orbit| Θ (θ)|f(A|θ ∗ )> f(B|θ ∗ ) . 2 We often interpretAandBas probability-theoretic events, but no such structure is demanded by our results. 3 The function’s retargetability is “simple” because we are not yet worrying aboute.g. which parameter inputs are considered plausible: BecauseS d acts onΘ, definition 3.3 implicitly assumesΘis closed under permutation. 4 1.Retargetable vianpermutations.∀i= 1,...,n : f ( A|φ i ·θ A ) < f ( B|φ i ·θ A ) . 2.Parameter permutation is allowed byΘ.∀i : φ i ·θ A ∈Θ. 3.Permuted parameters are distinct.∀i6=j,θ ′ ∈Orbit| Θ,A>B (θ) : φ i ·θ A 6=φ j ·θ ′ . Theorem 3.6(Multiply retargetable functions have orbit-level tendencies). Iffis(Θ,A n →B)-retargetable, thenf(B|θ)≥ n most:Θ f(A|θ). Proof outline (full proof in Appendix B). For everyθ A ∈Orbit| Θ,A>B (θ)such thatAis chosen overB, item 1 retargetsθ A vianpermutationsφ 1 ,...,φ n such that eachφ i ·θ A makes the agent chooseBoverA. These permuted parameters are valid parameter inputs by item 2. Furthermore, the φ i ·θ A are distinct by item 3. Therefore, the cosetsφ i ·Orbit| Θ,A>B (θ)are pairwise disjoint. By a counting argument, every orbit must contain at leastntimes as many parameters choosingBoverA, than vice versa. 4 Decision-making tendencies in Montezuma’s Revenge To illustrate a high-dimensional setting in which parametrically retargetable decision-makers tend to seek power, we consider Montezuma’s Revenge (MR), an Atari adventure game in which the player navigates deadly traps and collects treasure. The game is notoriously difficult forAIagents due to its sparse reward.MRwas only recently solved [Ecoffet et al., 2021]. Figure 2 shows the starting observationo 0 for the first level. This section culminates with section 4.3, where we argue that increasingly powerfulRLtraining processes will cause increasing retargetability via the reward function, which in turn causes increasingly strong decision-making tendencies. Terminology.Retargetability is a property of the policy training process, and power-seeking is a property of the trained policy. More precisely, the policy training process takes as input a parameterizationθand outputs a probability distribution over policies. For each trained policy drawn from this distribution, the environment, starting state, and the drawn policy jointly specify a probability distribution over trajectories. Therefore, the training process associates each parameterizationθwith the mixture distributionPover trajectories (with the mixture taken over the distribution of trained policies). A policy training process can be simply retargeted from one trajectory setAto another trajectory set Bwhen there exists a permutationφ∈S d such that, for everyθfor whichP(A|θ)> P(B|θ), we haveP(A|φ·θ)< P(B|φ·θ). As in Turner et al. [2021], a trained policyπseeks powerwhenπ’s actions navigate to states with high average optimal value (with the average taken over a wide range of reward functions). Generally, high-power states are able to reach a wide range of other states, and so allow bigger option setsB(compared to the optionsAavailable without seeking power). 4.1 Tendencies for initial action selection We will be considering the actions chosen and trajectories induced by a range of decision-making procedures. For warm-up, we will explore what initial action tends to be selected by decision-makers. LetA : =↓,B : =←,→,jump,↑partition the action setA. Consider a decision-making procedurefwhich takes as input a targeting parameterθ∈Θ, and also an initial actiona∈A, and returns the probability thatais the first action. Intuitively, sinceBcontains more actions thanA, perhaps some class of decision-making procedures tends to take an action inBrather than one inA. MR’s initial-action situation is analogous to the Pac-Man example. In that example, if the decision- making procedurepcan be retargeted from terminal state setA(the ghost) to setB(the fruit), then ptends to select a state fromBunder most of its parameter settingsθ. Similarly, inMR, if the decision-making procedurefcan be retargeted from action setAto action setB, thenftends to take actions inBfor most of its parameter settingsθ. Consider several ways of choosing an initial action inMR. Random action selection.p rand : = (a|θ)7→ 1 5 uniformly randomly chooses an action fromA, ignoring the parameter input. Since∀θ∈Θ : p rand (B|θ) = 4 5 > 1 5 =p rand (A|θ),allparameter inputs produce a greater chance ofBthan ofA, sop rand is (trivially) retargetable fromAtoB. 5 Always choosing the same action.p stubborn always chooses↓. Since∀θ∈Θ : p stubborn (A|θ) = 1>0 =p stubborn (B|θ),allparameter inputs produce a greater chance ofAthan ofB.p stubborn is not retargetable fromAtoB. Greedily optimizing state-action reward.LetΘ : =R S×A be the space of state-action reward functions. Letp max greedily maximize initial state-action reward, breaking ties uniformly randomly. We now check thatp max is retargetable fromAtoB. Supposeθ ∗ ∈Θis such thatp max (A|θ ∗ )> p max (B|θ ∗ ). Then among the initial action rewards,θ ∗ assigns strictly maximal reward to↓, and sop max (A|θ ∗ ) = 1. Letφswap the reward for the↓andjumpactions. Thenφ·θ ∗ assigns strictly maximal reward tojump. This means thatp max (A|φ·θ ∗ ) = 0<1 =p max (B|φ·θ ∗ ), satisfying definition 3.3. Then apply proposition 3.4 to conclude thatp max (B|θ)≥ 1 most:Θ p max (A|θ). In fact, appendix A shows thatp max is(Θ,A 4 →B)-retargetable (definition 3.5), and sop max (B| θ)≥ 4 most:Θ p max (A|θ) . The reasoning is more complicated, but the rule of thumb is: When decisions are made based on the reward of outcomes, then a proportionally larger setBof outcomes induces proportionally strong retargetability, which induces proportionally strong orbit-level incentives. Learning an exploitation policy.Suppose we run a bandit algorithm which tries different initial actions, learns their rewards, and produces an exploitation policy which maximizes estimated reward. The algorithm uses-greedy exploration and trains forTtrials. Given fixedTand,p bandit (A|θ) returns the probability that an exploitation policy is learned which chooses an action inA; likewise forp bandit (B|θ). Here is a heuristic argument thatp bandit is retargetable. Since the reward is deterministic, the exploitation policy will choose an optimal action if the agent has tried each action at least once, which occurs with a probability approaching1exponentially quickly in the number of trialsT. Then whenTis large,p bandit approximatesp max , which is retargetable. Therefore, perhapsp bandit is also retargetable. A more careful analysis in appendix C.1 reveals thatp bandit is 4-retargetable fromAto B, and sop bandit (B|θ)≥ 4 most:Θ p bandit (A|θ). 4.2 Tendencies for maximizing reward over the final observation When evaluating the performance of an algorithm inMR, we do not focus on the agent’s initial action. Rather, we focus on the longer-term consequences of the agent’s actions, such as whether the agent leaves the first room. To begin reasoning about such behavior, the reader must distinguish between different kinds of retargetability. Suppose the agent will die unless they choose action↓at the initial states 0 (Figure 2). By section 4.1, action-retargetable decision-making procedures tend to choose actions besides↓. On the other hand, Turner et al. [2021] showed that most reward functions make it reward-optimal to stay alive (in this situation, by choosing↓). However, in that situations, the optimal policies are not retargetable across Figure 2: Montezuma’s Revenge (MR) has state spaceSand observation spaceO. The agent has actionsA : =↑,↓,←,→,jump. At the initial states 0 ,↑does nothing,↓descends the ladder, ←and→move the agent on the platform, andjumpis self-explanatory. The agent clears the temple while collecting four kinds of items: keys, swords, torches, and amulets. Under the standard environmental reward function, the agent receives points for acquiring items (such as the key on the left), opening doors, and—ultimately—completing the level. 6 the agent’simmediatechoice of action, but rather across future consequences (i.e. which room the agent ends up in). With that in mind, we now analyze how often decision-makers leave the first room ofMR. 4 Decision- making functionsdecide(θ)produce a probability distribution over policiesπ∈Π, which are rolled out from the initial states 0 to produce observation-action trajectoriesτ=o 0 a 0 ...o T a T ..., where Tis the rollout length we are interested in. LetO T-reach be the set of observations reachable starting from states 0 and acting forTtime steps, letO leave ⊆O T-reach be those observations which can only be realized by leaving, and letO stay : =O T-reach leave . Consider the probability thatdeciderealizes some subset of observationsX⊆Oat stepT: p decide (X|θ) : =P π∼decide(θ), τ∼π|s 0 (o T ∈X).(3) LetΘ : =R O be the set of reward functions mapping observationso∈ Oto real numbers, and let T : = 1,000. We first consider the previous decision functions, since they are simple to analyze. decide rand randomly chooses a final observationowhich can be realized at step 1,000, and then chooses some policy which realizeso. 5 decide rand induces anp rand defined by eq. (3). As before, p rand tends to leave the room underallparameter inputs. decide max (θ) produces a policy which maximizes the reward of the observation at step 1,000 of the rollout. SinceMRis deterministic, we discusswhichobservationdecide max (θ)realizes. In a stochastic setting, the decision-maker would choose a policy realizing some probability distribution over step-Tobservations, and the analysis would proceed similarly. Here is the semi-formal argument forp max ’s retargetability. There are combinatorially more game- screens visible if the agent leaves the room (due toe.g. more point combinations, more inventory layouts, more screens outside of the first room). In other words, ∣ ∣ O stay ∣ ∣ |O leave | . There are more ways for the selected observation to require leaving the room, than not. Thus,p max is extremely retargetable fromO stay toO leave . Detailed analysis in section C.2 confirms thatp max (O leave |θ)≥ n most:Θ p max (O stay |θ)for the large n : =b |O leave | | O stay | c, which we show implies thatp max tends to leave the room. 4.3 Tendencies forRLon featurized reward over the final observation In the real world, we do not runp max , which can be computed viaT-depth exhaustive tree search in order to find and induce a maximal-reward observationo T . Instead, we use reinforcement learning. BetterRLalgorithms seem to be more retargetablebecauseof their greater capability to explore. 6 Exploring the first room.Consider a featurized reward function over observationsθ∈R O , which provides an end-of-episode return signal which adds a fixed reward for each item displayed in the observation (e.g. 5 reward for a sword, 2 reward for a key). Consider a coefficient vectorα∈R 4 , with each entry denoting the value of an item, andfeat : O →R 4 maps observations to feature vectors which tally the items in the agent’s inventory. A reinforcement learning algorithmAlguses this return signal to update a fixed-initialization policy network. Thenp Alg (O leave |θ)returns the probability thatAlgtrains an policy whose step-Tobservation required the agent to leave the initial room. The retargetability (definition 3.3) ofAlgis closely linked to the quality ofAlgas anRLtraining procedure. For example, as explained in section C.4, Mnih et al. [2015]’sDQNisn’t good enough to train policies which leave the first room ofMR, and soDQN(trivially) cannot be retargetableaway from the first room via the reward function. There isn’t a single featurized reward function for which DQNvisits other rooms, and so we can’t haveαsuch thatφ·αretargets the agent toO leave .DQNisn’t good enough at exploring. 4 In Appendix C.2, Figure 3 shows a map of the first level. 5 decide rand does not act randomly at each time step, it induces a randomly selected final observation. Analogously, randomly turning a steering wheel is different from driving to a randomly chosen destination. 6 Conversely, if the agent cannot figure out how to leave the first room, any reward signal from outside of the first room can never causally affect the learned policy. In that case, retargetability away from the first room is impossible. 7 More formally, in this situation,Algis retargetable if there exists a permutationφ∈S 4 such that wheneverα∈Θ : =R 4 induces the learned policies to stay in the room (p Alg (O stay |α)> p Alg (O leave |α)),φ·αmakesAlgtrain policies which leave the room (p Alg (O stay |α)< p Alg (O leave | α)). Exploring four rooms.Suppose algorithmAlg ′ can exploree.g. the first three rooms to the right of the initial room (shown in Figure 2), and consider any reward coefficient vectorα∈Θwhich assigns unique positive weight to each item. In particular, unique positive weights rule out constant reward vectors, in which case inductive bias would produce agents which do not leave the first room. If the agent stays in the initial room, it can induce inventory states empty,1key. If the agent explores the three extra rooms, it can also induce 1sword,1sword&1key (see Figure 3 in Appendix C.2). Sinceαis positive, it is never optimal to finish the episode empty-handed. Therefore, if the Alg ′ policy stays in the first room, thenα’s feature coefficients must satisfyα key > α sword . Otherwise, α key < α sword (by assumption of unique item reward coefficients); in this case, the agent would leave and acquire the sword (since we assumed it knows how to do so). Then by switching the reward for the key and the sword, we retargetAlg ′ to go get the sword.Alg ′ is simply-retargetable away from the first room,becauseit can explore enough of the environment. Exploring the entire level.Algorithms likeGO-EXPLORE[Ecoffet et al., 2021] are probably good at exploring even given sparse featurized reward. Therefore,GO-EXPLOREis even more retargetable in this setting, because it is more able to explore and discover the breadth of options (final inventory counts) available to it, and remember how to navigate to them. Furthermore, sufficiently powerful planning algorithms should likewise be retargetable in a similar way, insofar as they can reliably find high-scoring item configurations. We speculate that increasingly “impressive” algorithms (whetherRLtraining or planning) are often more impressive because they can allow retargeting the agent’s final behavior from one kind of outcome, to another. Just asGO-EXPLOREseems highly retargetable whileDQNdoes not, we expect increasingly impressive algorithms to be increasingly retargetable—whether over actions in a bandit problem, or over the final observation in anRLepisode. 5 Retargetability can imply power-seeking tendencies 5.1 Generalizing the power-seeking theorems for Markov decision processes Turner et al. [2021] considered finiteMDPs in which decision-makers took as input a reward function over states (r∈R |S| ) and selected an optimal policy for that reward function. They considered the state visit distributionsf∈F(s), which basically correspond to the trajectories which the agent could induce starting from states. ForF⊆ F(s),p max (F|r)returns1if an element ofFis optimal for reward functionr, and0otherwise. They showed situations where a larger set of distributions F large tended to be optimal over a smaller set:p max (F large |r)≥ 1 most:R |S| p max (F small |r) . For example, in Pac-Man, most reward functions make it optimal to stay alive for at least one time step: p max (F survival |r)≥ 1 most:R |S| p max (F instant death |r) . Turner et al. [2021] showed that optimal policies tend to seek power by keeping options open and staying alive. Appendix D provides a quantitative generalization of Turner et al. [2021]’s results on optimal policies. Throughout this paper, we abstracted their arguments away from finiteMDPs and reward-optimal decision-making. Instead, parametrically retargetable decision-makers tend to seek power: Proposi- tion A.11 shows that a wide range of decision-making procedures are retargetable over outcomes, and theorem A.13 demonstrates the retargetability ofanydecision-making which is determined by the expected utility of outcomes. In particular, these results apply straightforwardly toMDPs. 5.2 BetterRLalgorithms tend to be more retargetable Reinforcement learning algorithms are practically useful insofar as they can train an agent to accom- plish some task (e.g. cleaning a room). A goodRLalgorithm is relatively task-agnostic (e.g. is not restricted to only training policies which clean rooms). Task-agnosticism suggests retargetability across desired future outcomes / task completions. 8 InMR, suppose we instead give the agent1reward for the initial state, and0otherwise. Any reasonable reinforcement learning procedure will just learn to stay put (which is the optimal policy). However, consider whether we can retarget the agent’s policy to beat the game, by swapping the initial state reward with the end-game state reward. Most present-dayRLalgorithms are not good enough to solve such a sparse game, and so are not retargetable in this sense. But an agent which did enough exploration would also learn a good policy for the permuted reward function. Such an effective training regime could be useful for solving real-world tasks. Many researchers aim to develop effective training regimes. Our results suggest that onceRLcapabilities reach a certain level, trained agents will tend to seek power in the real world. Presently, it is not dangerous to train an agent to complete a task—such an agent will not be able to complete its task by staying activated against the designers’ wishes. The present lack of danger is not because optimal policies do not have self-preservation tendencies—they do [Turner et al., 2021]. Rather, the lack of danger reflects the fact that present-dayRLagents cannot learn such complex action sequencesat all. Just as the Montezuma’s Revenge agent had to be sufficiently competent to be retargetable from initial-state reward to game-complete reward, real-world agents have to be sufficiently intelligent in order to be retargetable from outcomes which don’t require power-seeking, to those which do require power-seeking. Here is some speculation. After training anRLagent to a high level of capability, the agent may be optimizing internally represented goals over its model of the environment [Hubinger et al., 2019]. Furthermore, we think that different reward parameter settings would train different internal goals into the agent. To make an analogy, changing a person’s reward circuitry would presumably reinforce them for different kinds of activities and thereby change their priorities. In this sense, trained real-world agents may be retargetable towards power-requiring outcomes via the reward function parameter setting. Insofar as this speculation holds, our theory predicts that advanced reinforcement learning at scale will—for most settings of the reward function—train policies which tend to seek power. 6 Discussion In section 3, we formalized a notion of parametric retargetability and stated several key results. While our results are broadly applicable, further work is required to understand the implications forAI. 6.1 Prior work In this work, we do not motivate the risks fromAIpower-seeking. We refer the reader toe.g. Carlsmith [2021]. As explained in section 5.1, Turner et al. [2021] show that, given certain environmental symmetries in anMDP, the optimal-policy-producing algorithmf(state visitation distribution set, state-based reward function) is 1-retargetable via the reward function, from smaller to larger sets of environmental options. Section A shows that optimality is not required, and instead a wide range of decision-making procedures satisfy the retargetability criterion. Furthermore, we generalize from 1-retargetability ton-fold-retargetability whenever option setBcontains “ncopies” of setA (definition A.7 in section A). 6.2 Future work and limitations We currently have analyzed planning- and reinforcement learning-based settings. However, results such as theorem 3.6 might in some way apply to the training of other machine learning networks. Furthermore, while theorem 3.6 does not assume a finite environment, we currently do not see how to apply that result toe.g. infinite-state partially observable Markov decision processes. Section 4 semi-formally analyzes decision-making incentives in theMRvideo game, leaving the proofs to section C. However, these proofs are several pages long. Perhaps additional lemmas can allow quick proof of orbit-level incentives in situations relevant to real-world decision-makers. Consider a sequence of decision-making functionsp t : A,B×Θ→Rwhich converges pointwise to somepsuch thatp(B|θ)≥ n most:Θ p(A|θ). We expect that under rather mild conditions, ∃T : ∀t≥T : p t (B|θ)≥ n most:Θ p t (A|θ). As a corollary, for any decision-making procedurep t which runs forttime steps and satisfieslim t→∞ p t =p, the functionp t will have decision-making incentives after finite time. For example, value iteration (VI) eventually finds an optimal policy 9 [Puterman, 2014], and optimal policies tend to seek power [Turner et al., 2021]. Therefore, this conjecture would imply that ifVIis run for some long but finite time, it tends to produce power- seeking policies. More interestingly, the result would allow us to reason about the effect ofe.g. randomly initializing parameters (inVI, the tabular value function att= 0). The effect of random initialization washes out in the limit of infinite time, so we would still conclude the presence of finite-time power-seeking incentives. Our results do notprovethat we will build unalignedAIagents which seek power over the world. Here are a few situations in which our results are not concerning or not applicable. 1.TheAIis aligned with human interests. For example, we want a robotic cartographer to prevent itself from being deactivated. However, theAIalignment problem is not yet understood for highly intelligent agents [Russell, 2019]. 2. TheAI’s decision-making is not retargetable (definition 3.5). 3. TheAI’s decision-making is retargetable overe.g. actions (section 4.1) instead of over final outcomes (section 4.2). This retargetability seems less concerning, but also less practically useful. 6.3 Conclusion We introduced the concept of retargetability and showed that retargetable decision-makers often make similar instrumental choices. We applied these results in the Montezuma’s Revenge (MR) video game, showing how increasingly advanced reinforcement learning algorithms correspond to increasingly retargetable agent decision-making. Increasingly retargetable agents make increasingly similar instrumental decisions—e.g. leaving the initial room inMR, or staying alive in Pac-Man. In particular, these decisions will often correspond to gaining power and keeping options open [Turner et al., 2021]. Our theory suggests that whenRLtraining processes become sufficiently advanced, the trained agents will tend to seek power over the world. This theory suggests a safety risk. We hope for future work on this theory so that the field ofAIcan understand the relevant safety risksbeforethe field trains power-seeking agents. Broader impacts Our theory of orbit-level tendencies constitutes basic mathematical research into the decision-making tendencies of certain kinds of agents. We hope that this theory will prevent negative impacts from unaligned power-seekingAI. We do not anticipate that our work will have negative impact. Acknowledgements We thank Irene Tematelewo, Colin Shea-Blymyer, and our anonymous reviewers for feedback. We thank Justis Mills for proofreading. References Chris L Baker, Joshua B Tenenbaum, and Rebecca R Saxe. Goal inference as inverse planning. InProceedings of the Annual Meeting of the Cognitive Science Society, volume 29, 2007. Nick Bostrom.Superintelligence. Oxford University Press, 2014. Ryan Carey. How useful is quantilization for mitigating specification gaming? 2019. Joe Carlsmith. Is power-seeking AI an existential risk?, 2021. URLhttps://w.alignmentforum. org/posts/cCMihiwtZx7kdcKgt/comments-on-carlsmith-s-is-power-seeking-ai-an- existential. Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590(7847):580–586, 2021. Evan Hubinger, Chris van Merwijk, Vladimir Mikulik, Joar Skalse, and Scott Garrabrant. Risks from learned optimization in advanced machine learning systems, 2019. URLhttps://arxiv.org/abs/1906.01820. 10 Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning.Nature, 518(7540):529–533, 2015. Arun Nair, Praveen Srinivasan, Sam Blackwell, Cagdas Alcicek, Rory Fearon, Alessandro De Maria, Vedavyas Panneershelvam, Mustafa Suleyman, Charles Beattie, Stig Petersen, et al. Massively parallel methods for deep reinforcement learning.arXiv preprint arXiv:1507.04296, 2015. Martin L Puterman.Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014. Stuart Russell.Human compatible: Artificial intelligence and the problem of control. Viking, 2019. Herbert A Simon. Rational choice and the structure of the environment.Psychological review, 63(2):129, 1956. Richard S Sutton and Andrew G Barto.Reinforcement learning: an introduction. MIT Press, 1998. Jessica Taylor. Quantilizers: A safer alternative to maximizers for limited optimization. InAAAI Workshop: AI, Ethics, and Society, 2016. Alexander Matt Turner. Reward is not the optimization target, 2022. URLhttps://w.alignmentforum. org/posts/pdaGN6pQyQarFHXF4/reward-is-not-the-optimization-target. Alexander Matt Turner, Logan Smith, Rohin Shah, Andrew Critch, and Prasad Tadepalli. Optimal policies tend to seek power. InAdvances in Neural Information Processing Systems, 2021. 11 Appendix A Retargetability over outcome lotteries Suppose we are interested indoutcomes. Each outcome could be the visitation of anMDPstate, or a trajectory, or the receipt of a physical item. In the Pac-Man example of section 2,d= 3states. The agent can induce each outcome with probability1, so lete o ∈R 3 be the standard basis vector with probability1on outcomeoand0elsewhere. Then the agent chooses among outcome lotteries C : = e,e,e , which we partition intoA : = e andB : = e,e . Definition A.1(Outcome lotteries).A unit vectorx∈R d with non-negative entries is anoutcome lottery. 7 Many decisions are made consequentially: based on the consequences of the decision, on what outcomes are brought about by an act. For example, in a deterministic Atari game, a policy induces a trajectory. A reward function and discount rate tuple(R,γ)assigns areturnto each state trajectory τ=s 0 ,s 1 ,...:G(τ) = ∑ ∞ i=0 γ i R(s i ). The relevant outcome lottery is the discounted visit distribution over future states in an Atari game, and policies are optimal or not depending on which outcome lottery is induced by the policy. Definition A.2(Optimality indicator function).LetX,C( R d be finite, and letu∈R d . IsOptimal ( X|C,u ) returns1ifmax x∈X x > u≥max c∈C c > u, and0otherwise. We consider decision-making procedures which take in a targeting parameteru. For example, the column headers of Table 2a show the 6 permutations of the utility functionu() : = 10,u() : = 5,u( ) : = 0, representable as a vectoru∈R 3 . u can be permuted as follows. The outcome permutationφ∈S d inducing and×dpermutation matrixP φ in row representation:(P φ ) ij = 1ifi=φ(j)and0otherwise. Table 2a shows that for a given utility function, 2 3 of its orbit agrees thatBis strictly optimal overA. Orbit-level incentives occur when an inequality holds for most permuted parameter choicesu ′ . Table 2a demonstrates an application of Turner et al. [2021]’s results: Optimal decision-making induces orbit-level incentives for choosing Pac-Man outcomes inBover outcomes inA. Furthermore, Turner et al. [2021] conjectured that “larger”Bwill imply stronger orbit-level tenden- cies: If going right leads to 500 times as many options as going left, then right is better than left for at least 500 times as many reward functions for which the opposite is true. We prove this conjecture with theorem D.11 in appendix D. However, orbit-level incentives do not require optimality. One clue is that the same results hold for anti-optimal agents, since anti-optimality/utility minimization ofuis equivalent to maximizing−u. Table 2b illustrates that the same orbit guarantees hold in this case. Definition A.3 (Anti-optimality indicator function).LetX,C( R d be finite, and letu∈R d . AntiOpt ( X|C,u ) returns1ifmin x∈X x > u≤min c∈C c > u, and0otherwise. Stepping beyond expected utility maximization/minimization, Boltzmann-rational decision-making selects outcome lotteries proportional to the exponential of their expected utility. Definition A.4 (Boltzmann rationality [Baker et al., 2007]).ForX⊆Cand temperatureT >0, let Boltzmann T ( X|C,u ) : = ∑ x∈X e T −1 x > u ∑ c∈C e T −1 c > u be the probability that some element ofXis Boltzmann-rational. Lastly, orbit-level tendencies occur even under decision-making procedures which partially ignore expected utility and which “don’t optimize too hard.” Satisficing agents randomly choose an outcome lottery with expected utility exceeding some threshold. Table 2d demonstrates that satisficing induces orbit-level tendencies. Definition A.5(Satisficing).Lett∈R, letX⊆C( R d be finite.Satisfice t ( X,C|u ) : = ∣ ∣ ∣ X∩ c∈C|c > u≥t ∣ ∣ ∣ ∣ ∣ ∣ c∈C|c > u≥t ∣ ∣ ∣ is the fraction ofXwhose value exceeds thresholdt.Satisfice t ( X,C|u ) evaluates to0the denominator equals0. 7 Our results on outcome lotteries hold for genericx ′ ∈R d , but we find it conceptually helpful to consider the non-negative unit vector case. 12 Table 2: Orbit-level incentives across 4 decision-making functions. Utility functionu ′ 10,5,010,0,55,10,05,0,100,10,50,5,10 IsOptimal ( e ,e |C,u ′ ) 111010 IsOptimal ( e |C,u ′ ) 000101 (a) Dark gray columns indicate utility function permutationsu ′ for whichIsOptimal ( B|C,u ′ ) > IsOptimal ( A|C,u ′ ) , while white indicates that the opposite strict inequality holds. Utility functionu ′ 10,5,010,0,55,10,05,0,100,10,50,5,10 AntiOpt ( e ,e |C,u ′ ) 010111 AntiOpt ( e |C,u ′ ) 101000 (b) Utility-minimizing outcome selection probability. Utility functionu ′ 10,5,010,0,55,10,05,0,100,10,50,5,10 Boltzmann 1 ( e ,e |C,u ′ ) 1.9931.007.993.007 Boltzmann 1 ( e |C,u ′ ) .000.007.000.993.007.993 (c) Boltzmann selection probabilities forT= 1, rounded to three significant digits. Utility functionu ′ 10,5,010,0,55,10,05,0,100,10,50,5,10 Satisfice 3 ( e,e |C,u ′ ) 1.51.5.5.5 Satisfice 3 ( e |C,u ′ ) 0.50.5.5.5 (d) A satisficer uniformly randomly selects an outcome lottery with expected utility greater than or equal to the thresholdt. Here,t= 3. WhenSatisfice 3 ( e,e |C,u ′ ) = Satisfice 3 ( e |C,u ′ ) , the column is colored medium gray. For each table, two-thirds of the utility permutations (columns) assign strictly larger values (shaded dark gray) to an element ofB : = e,e than to an element ofA : = e . For optimal, anti- optimal, Boltzmann-rational, and satisficing agents, proposition A.11 proves that these tendencies hold for all targeting parameter orbits. A.1 A range of decision-making functions are retargetable InMDPs, Turner et al. [2021] considerstate visitation distributionswhich record the total discounted time steps spent in each environment state, given that the agent follows some policyπfrom an initial states. These visitation distributions are one kind of outcome lottery, withd=|S|the number of MDPstates. In general, we suppose the agent has an objective functionu∈R d which maps outcomes to real numbers. In Turner et al. [2021],uwas a state-based reward function (and so the outcomes were states). However, we need not restrict ourselves to theMDPsetting. To state our key results, we define several technical concepts which we informally used when reasoning aboutA : = e andB : = e ,e . 13 Definition A.6(Similarity of vector sets).Forφ∈S d andX⊆R d ,φ·X : = P φ x|x∈X . X ′ ⊆R |S| is similar toXwhen∃φ : φ·X ′ =X.φis aninvolutionifφ=φ −1 (it either transposes states, or fixes them).Xcontains a copy ofX ′ whenX ′ is similar to a subset ofXvia an involution φ. Definition A.7(Containment of set copies).Letnbe a positive integer, and letA,B⊆R d . We say thatBcontainsncopies ofAwhen there exist involutionsφ 1 ,...,φ n ∈S d such that∀i : φ i ·A= : B i ⊆Band∀j6=i : φ i ·B j =B j . 8 B : = e,e contains two copies ofA : = e viaφ 1 : = ↔andφ 2 : =↔. Definition A.8(Targeting parameter distribution assumptions).Results withD any hold for any probability distribution overR d . LetD any : = ∆(R d ). For a functionf : R d 7→R, we writef(D any ) as shorthand forE u∼D any [ f(u) ] . The symmetry group ondelements,S d , acts on the set of probability distributions overR d . Definition A.9(Pushforward distribution of a permutation [Turner et al., 2021]).Letφ∈S d .φ·D any is the pushforward distribution induced by applying the random vectorp(u) : =P φ utoD any . Definition A.10 (Orbit of a probability distribution [Turner et al., 2021]).TheorbitofD any under the symmetric groupS d isS d ·D any : =φ·D any |φ∈S d . BecauseBcontains 2 copies ofA, there are “at least two times as many ways” forBto be optimal, than forAto be optimal. Similarly,Bis “at least two times as likely” to contain an anti-rational outcome lottery for generic utility functions. As demonstrated by Table 2, the key idea is that “larger” sets (a setBcontaining severalcopiesof setA) are more likely to be chosen under a wide range of decision-making criteria. Proposition A.11(Orbit incentives for different rationalities).LetA,B⊆C( R d be finite, such thatBcontainsncopies ofAvia involutionsφ i such thatφ i ·C=C. 1.Rational choice [Turner et al., 2021]. IsOptimal ( B|C,D any ) ≥ n most:D any IsOptimal ( A|C,D any ) . 2.Uniformly randomly choosing an optimal lottery.ForX⊆C, let FracOptimal ( X|C,u ) : = ∣ ∣ ∣ arg max c∈C c > u ∩X ∣ ∣ ∣ ∣ ∣ ∣ arg max c∈C c > u ∣ ∣ ∣ . ThenFracOptimal ( B|C,D any ) ≥ n most:D any FracOptimal ( A|C,D any ) . 3.Anti-rational choice.AntiOpt ( B|C,D any ) ≥ n most:D any AntiOpt ( A|C,D any ) . 4.Boltzmann rationality. Boltzmann T ( B|C,D any ) ≥ n most:D any Boltzmann T ( A|C,D any ) . 5.Uniformly randomly drawingkoutcome lotteries and choosing the best. ForX⊆C, u∈R d , andk≥1, let best-of-k(X,C|u) : =E a 1 ,...,a k ∼unif(C) [ FracOptimal ( X∩a 1 ,...,a k |a 1 ,...,a k ,u ) ] . Then best-of-k(B|C,D any )≥ n most:D any best-of-k(A|C,D any ). 8 Technically, definition A.7 implies thatAcontainsncopies ofAholds for alln, vianapplications of the identity permutation. For our purposes, this provides greater generality, as all of the relevant results still hold. Enforcing pairwise disjointness of theB i would handle these issues, but would narrow our results to not apply e.g. when theB i share a constant vector. 14 6.Satisficing [Simon, 1956].Satisfice t ( B|C,D any ) ≥ n most:D any Satisfice t ( A|C,D any ) . 7.Quantilizing over outcome lotteries [Taylor, 2016]. LetPbe the uniform probability dis- tribution overC. ForX⊆C,u∈R d , andq∈(0,1], letQ q,P (X|C,u)(definition B.12) return the probability that an outcome lottery inXis drawn from the topq-quantile ofP, sorted by expected utility underu. ThenQ q,P (B|C,u)≥ n most:R d Q q,P (A|C,u). One retargetable class of decision-making functions are those which only account for the expected utilities of available choices. Definition A.12(EU-determined functions).LetP ( R d ) be the power set ofR d , and letf : ∏ m i=1 P ( R d ) ×R d →R .fis anEU-determined functionif there exists a family of functions g ω 1 ,...,ω m such that f(X 1 ,...,X m |u) =g |X 1 |,...,|X m | ( [ x > 1 u ] x 1 ∈X 1 ,..., [ x > m u ] x m ∈X m ) ,(4) where[r i ]is the multiset of its elementsr i . For example, letX⊆C( R d be finite, and consider utility functionu∈R d . A Boltzmann- rational agent is more likely to select outcome lotteries with greater expected utility. Formally, Boltzmann T ( X|C,u ) : = ∑ x∈X e T·x > u ∑ c∈C e T·c > u depends only on the expected utility of outcome lotteries inX, relative to the expected utility of all outcome lotteries inC. Therefore,Boltzmann T is a function of expected utilities. This iswhyBoltzmann T satisfies the≥ n most:D any relation. Theorem A.13 (Orbit tendencies occur for EU-determined decision-making functions).Let A,B,C⊆R d be such thatBcontainsncopies ofAviaφ i such thatφ i ·C=C. Leth : ∏ 2 i=1 P ( R d ) ×R d →R be an EU-determined function, and letp(X|u) : =h(X,C|u). Suppose thatpreturns a probability of selecting an element ofXfromC. Thenp(B|u)≥ n most:R d p(A|u). The key takeaway is that decisions which are determined by expected utility are straightforwardly retargetable. By changing the targeting parameter hyperparameter, the decision-making procedure can be flexibly retargeted to choose elements of “larger” sets (in terms of set copies via definition A.7). Less abstractly, for many agent rationalities—ways of making decisions over outcome lotteries—it is generally the case that larger sets will more often be chosen over smaller sets. For example, consider a Pac-Man playing agent choosing which environmental state cycle it should end up in. Turner et al. [2021] show that for most reward functions, average-reward maximizing agents will tend to stay alive so that they can reach a wider range of environmental cycles. However, our results show that average-rewardminimizingagents also exhibit this tendency, as do Boltzmann- rational agents who assign greater probability to higher-reward cycles. Any EU-based cycle selection method will—for most reward functions—tend to choose cycles which require Pac-Man to stay alive (at first). Appendix B Theoretical results Definition 3.2(Inequalities which hold for most orbit elements).SupposeΘis a subset of a set acted on byS d , the symmetric group ondelements. Letf : A,B×Θ→Rand letn≥1. We write f(B|θ)≥ n most:Θ f(A|θ)when, forallθ∈Θ, the following cardinality inequality holds: ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|f(B|θ ′ )> f(A|θ ′ ) ∣ ∣ ∣ ≥n ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|f(B|θ ′ )< f(A|θ ′ ) ∣ ∣ ∣ . (2) Remark. In stating their equivalent of definition 3.2, Turner et al. [2021] define two functions f 1 (θ) : =f(B|θ)andf 2 (θ) : =f(A|θ)(both having type signaturef i : Θ→R). For compatibility, proofs also use this notation. Lemma B.1(Limited transitivity of≥ most ).Letf 0 ,f 1 ,f 2 ,f 3 : Θ→R, and supposeΘis a subset of a set acted on byS d . Suppose thatf 1 (θ)≥ n most:Θ f 2 (θ)and∀θ∈Θ : f 0 (θ)≥f 1 (θ)and f 2 (θ)≥f 3 (θ). Thenf 0 (θ)≥ n most:Θ f 3 (θ). 15 Proof.Letθ∈Θand letOrbit| Θ,f a >f b (θ) : = θ ′ ∈Orbit| Θ (θ)|f a (θ ′ )> f b (θ ′ ) . ∣ ∣ Orbit| Θ,f 0 >f 3 (θ) ∣ ∣ ≥ ∣ ∣ Orbit| Θ,f 1 >f 2 (θ) ∣ ∣ (5) ≥n ∣ ∣ Orbit| Θ,f 2 >f 1 (θ) ∣ ∣ (6) ≥n ∣ ∣ Orbit| Θ,f 3 >f 0 (θ) ∣ ∣ .(7) For allθ ′ ∈Orbit| Θ,f 1 >f 2 (θ), f 0 (θ ′ )≥f 1 (θ ′ )> f 2 (θ ′ )≥f 3 (θ ′ ) by assumption, and so Orbit| Θ,f 1 >f 2 (θ)⊆Orbit| Θ,f 0 >f 3 (θ). Therefore, eq. (5) follows. By assumption, ∣ ∣ Orbit| Θ,f 1 >f 2 (θ) ∣ ∣ ≥n ∣ ∣ Orbit| Θ,f 2 >f 1 (θ) ∣ ∣ ; eq. (6) follows. For allθ ′ ∈Orbit| Θ,f 2 >f 1 (θ), our assumptions onf 0 andf 3 ensure that f 0 (θ ′ )≤f 1 (θ ′ )< f 3 (θ ′ )≤f 2 (θ ′ ), so Orbit| Θ,f 3 >f 0 (θ)⊆Orbit| Θ,f 2 >f 1 (θ). Then eq. (7) follows. By eq. (7),f 0 (θ)≥ n most:Θ f 3 (θ). Lemma B.2(Order inversion for≥ most ).Letf 1 ,f 2 : Θ→R, and supposeΘis a subset of a set acted on byS d . Suppose thatf 1 (θ)≥ n most:Θ f 2 (θ). Then−f 2 (θ)≥ n most:Θ −f 1 (θ). Proof.By definition A.10,f 1 (θ)≥ n most:Θ f 2 (θ)means that ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|f 1 (θ ′ )> f 2 (θ ′ ) ∣ ∣ ∣ ≥n ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|f 1 (θ ′ )< f 2 (θ ′ ) ∣ ∣ ∣ (8) ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|−f 2 (θ ′ )>−f 1 (θ ′ ) ∣ ∣ ∣ ≥n ∣ ∣ ∣ θ ′ ∈Orbit| Θ (θ)|−f 2 (θ ′ )<−f 1 (θ ′ ) ∣ ∣ ∣ .(9) Then−f 2 (θ)≥ n most:Θ −f 1 (θ). Remark.Lemma B.3 generalizes Turner et al. [2021]’s lemma B.2. Lemma B.3(Orbital fraction which agrees on (weak) inequality).Supposef 1 ,f 2 : Θ→R are such thatf 1 (θ)≥ n most:Θ f 2 (θ). Then for allθ∈Θ, ∣ ∣ ∣ θ ′ ∈(S d ·θ)∩Θ|f 1 (θ ′ )≥f 2 (θ ′ ) ∣ ∣ ∣ | (S d ·θ)∩Θ | ≥ n n+ 1 . Proof. Allθ ′ ∈(S d ·θ)∩Θsuch thatf 1 (θ ′ ) =f 2 (θ ′ )satisfyf 1 (θ ′ )≥f 2 (θ ′ ). Otherwise, consider theθ ′ ∈(S d ·θ)∩Θsuch thatf 1 (θ ′ )6=f 2 (θ ′ ). By assumption, at least n n+1 of theseθ ′ satisfy f 1 (θ ′ )> f 2 (θ ′ ), in which casef 1 (θ ′ )≥f 2 (θ ′ ). Then the desired inequality follows. B.1 General results on retargetable functions Definition B.4 (Functions which are increasing under joint permutation).Suppose thatS d acts on setsE 1 ,...,E m , and letf : ∏ m i=1 E i →R .f(X 1 ,...,X m )isincreasing under joint permutation byP⊆S d when∀φ∈P : f(X 1 ,...,X m )≤f(φ·X 1 ,...,φ·X m ). If equality always holds, then f(X 1 ,...,X m )isinvariant under joint permutation byP. Lemma B.5(Expectations of joint-permutation-increasing functions are also joint-permutation-in- creasing).ForEwhich is a subset of a set acted on byS d , letf : E×R d →Rbe a bounded function which is measurable on its second argument, and letP⊆S d . Then iff(X|u)is increasing under joint permutation byP, thenf ′ (X| D any ) : =E u∼D any [ f(X|u) ] is increasing under joint permutation byP. Iffisinvariantunder joint permutation byP, then so isf ′ . 16 Proof.Let distributionD any have probability measureF, and letφ·D any have probability measure F φ . f ( X|D any ) : =E u∼D any [ f(X|u) ] (10) : = ∫ R d f(X|u) dF(u)(11) ≤ ∫ R d f(φ·X|P φ u) dF(u)(12) = ∫ R d f(φ·X|u ′ ) ∣ ∣ detP φ ∣ ∣ dF φ (u ′ )(13) = ∫ R d f(φ·X|u ′ ) dF φ (u ′ )(14) = : f ′ ( φ·X|φ·D any ) .(15) Equation (12) holds by assumption onf:f(X|u)≤f(φ·X|P φ u). Furthermore,f(φ·X|·)is still measurable, and so the inequality holds. Equation (13) follows by the definition ofF φ (definition 6.3) and by substitutingr ′ : =P φ r. Equation (14) follows from the fact that all permutation matrices have unitary determinant. Lemma B.6(Closure of orbit incentives under increasing functions).Suppose thatS d acts on sets E 1 ,...,E m (withE 1 being a poset), and letP⊆S d . Letf 1 ,...,f n : ∏ m i=1 E i →R be increasing under joint permutation byPon input(X 1 ,...,X m ), and suppose thef i are order-preserving with respect to E 1 . Letg : ∏ n j=1 R→Rbe monotonically increasing on each argument. Then f(X 1 ,...,X m ) : =g ( f 1 (X 1 ,...,X m ),...,f n (X 1 ,...,X m ) ) (16) is increasing under joint permutation byPand order-preserving with respect to set inclusion on its first argument. Furthermore, if thef i areinvariantunder joint permutation byP, then so isf. Proof.Letφ∈P. f(X 1 ,...,X m ) : =g ( f 1 (X 1 ,...,X m ),...,f n (X 1 ,...,X m ) ) (17) ≤g ( f 1 (φ·X 1 ,...,φ·X m ),...,f n (φ·X 1 ,...,φ·X m ) ) (18) = : f(φ·X 1 ,...,φ·X m ).(19) Equation (18) follows because we assumed thatf i (X 1 ,...,X m )≤f i (φ·X 1 ,...,φ·X m ), and becausegis monotonically increasing on each argument. If thef i are all invariant, then eq. (18) is an equality. Similarly, supposeX ′ 1 E 1 X 1 . Thef i are order-preserving on the first argument, andgis monoton- ically increasing on each argument. Thenf ( X ′ 1 ,...,X m ) ≤f(X 1 ,...,X m ) . This shows thatfis order-preserving on its first argument. Remark.gcould take the convex combination of its arguments, or multiply twof i together and add them to a thirdf 3 . Definition 3.5(Multiply retargetable function).LetΘbe a subset of a set acted on byS d , and let f : A,B×Θ→R. fis a(Θ,A n →B)-retargetable functionwhen, for eachθ∈Θ, we can choose permutations φ 1 ,...,φ n ∈S d which satisfy the following conditions: Consider anyθ A ∈Orbit| Θ,A>B (θ) : = θ ∗ ∈Orbit| Θ (θ)|f(A|θ ∗ )> f(B|θ ∗ ) . 1.Retargetable vianpermutations.∀i= 1,...,n : f ( A|φ i ·θ A ) < f ( B|φ i ·θ A ) . 2.Parameter permutation is allowed byΘ.∀i : φ i ·θ A ∈Θ. 3.Permuted parameters are distinct.∀i6=j,θ ′ ∈Orbit| Θ,A>B (θ) : φ i ·θ A 6=φ j ·θ ′ . Theorem 3.6(Multiply retargetable functions have orbit-level tendencies). 17 Iffis(Θ,A n →B)-retargetable, thenf(B|θ)≥ n most:Θ f(A|θ). Proof.Letθ∈Θ, and letφ i ·Orbit| Θ,A>B (θ) : = φ i ·θ A |θ A ∈Orbit| Θ,A>B (θ) . ∣ ∣ Orbit| Θ,B>A (θ)] ∣ ∣ ≥ ∣ ∣ ∣ ∣ ∣ ∣ n ⋃ i=1 φ i ·Orbit| Θ,A>B (θ) ∣ ∣ ∣ ∣ ∣ ∣ (20) = n ∑ i=1 ∣ ∣ φ i ·Orbit| Θ,A>B (θ) ∣ ∣ (21) =n ∣ ∣ Orbit| Θ,A>B (θ) ∣ ∣ .(22) By item 1 and item 2,φ i ·φ i ·Orbit| Θ,A>B (θ)⊆φ i ·Orbit| Θ,B>A (θ)]for alli. Therefore, eq. (20) holds. Equation (21) follows by the assumption that parameters are distinct, and so therefore the cosetsφ i ·Orbit| Θ,A>B (θ)andφ j ·Orbit| Θ,A>B (θ)are pairwise disjoint fori6=j. Equation (22) follows because eachφ i acts injectively on orbit elements. Lettingf A (θ) : =f(A|θ)andf B (θ) : =f(B|θ), the shown inequality satisfies definition 3.2. We conclude thatf(B|θ)≥ n most:Θ f(A|θ). Definition 3.3(Simply-retargetable function).LetΘbe a set acted on byS d , and letf : A,B× Θ→R. If∃φ∈S d : ∀θ A ∈Θ : f(B|θ A )< f(A|θ A ) =⇒f(A|φ·θ A )< f(B|φ·θ A ), thenfis a(Θ,A simple →B)-retargetable function. Proposition 3.4(Simply-retargetable functions have orbit-level tendencies). Iffis(Θ,A simple →B)-retargetable, thenf(B|θ)≥ 1 most:Θ f(A|θ). Proof.Given thatfis a(Θ,A simple →B)-retargetable function (definition 3.3), we want to show thatf is a(Θ,A 1 →B)-retargetable function (definition 3.5 whenn= 1). Definition 3.5’s item 1 is true by assumption. SinceΘis acted on byS d ,Θis closed under permutation and so definition 3.5’s item 2 holds. Whenn= 1, there are noi6=j, and so definition 3.5’s item 3 is tautologically true. Thenfis a(Θ,A 1 →B)-retargetable function; apply lemma B.7. B.2 Helper results on retargetable functions Targeting parameterθf(|θ)f(|θ)f(|θ)f(,|θ) θ ′ : = 1e 1 + 3e 2 + 2e 3 1000 φ 1 ·θ ′ =φ 2 ·θ ′ : = 3e 1 + 1e 2 + 2e 3 0222 φ 2 ·θ ′ : = 2e 1 + 3e 2 + 1e 3 0222 θ ′ : = 2e 1 + 1e 2 + 3e 3 1000 φ 1 ·θ ′ : = 1e 1 + 2e 2 + 3e 3 0222 θ ? : = 3e 1 + 2e 2 + 1e 3 1000 Table 3: We reuse the Pac-Man outcome set introduced in section 2. Letφ 1 : =↔,φ 2 : =↔. We tabularly define a functionfwhich meets all requirements of lemma B.7, except for item 4: lettingj : = 2,f(B ? 2 |φ 1 ·θ ′ ) = 2>0 =f(B ? 2 |θ ′ ) . Althoughf(B|θ)≥ 1 most:S 3 ·θ f(A|θ), it is not true thatf(B|θ ∗ )≥ 2 most:S 3 ·θ f(A|θ ∗ ). Therefore, item 4 is generally required. Lemma B.7(Quantitative general orbit lemma).LetΘbe a subset of a set acted on byS d , and let f : E×Θ→R. ConsiderA,B∈E. For eachθ∈Θ, choose involutionsφ 1 ,...,φ n ∈S d . Letθ ∗ ∈Orbit| Θ (θ). 1.Retargetable under parameter permutation. There existB ? i ∈Esuch that iff(B|θ ∗ )< f(A|θ ∗ ), then∀i : f ( A|θ ∗ ) ≤f ( B ? i |φ i ·θ ∗ ) . 18 2.Θis closed under certain symmetries.f(B|θ ∗ )< f(A|θ ∗ ) =⇒ ∀i : φ i ·θ ∗ ∈Θ. 3.fis increasing on certain inputs.∀i : f(B ? i |θ ∗ )≤f(B|θ ∗ ). 4.Increasing under alternate symmetries. Forj= 1,...,nandi6=j, iff(A|θ ∗ )< f(B| θ ∗ ), thenf ( B ? j |θ ∗ ) ≤f ( B ? j |φ i ·θ ∗ ) . If these conditions hold for allθ∈Θ, then f(B|θ)≥ n most:Θ f(A|θ).(23) Proof.Letθandθ ∗ be as described in the assumptions, and leti∈1,...,n. f(A|φ i ·θ ∗ ) =f(A|φ −1 i ·θ ∗ )(24) ≤f(B ? i |θ ∗ )(25) ≤f(B|θ ∗ )(26) < f(A|θ ∗ )(27) ≤f(B ? i |φ i ·θ ∗ )(28) ≤f(B|φ i ·θ ∗ ).(29) Equation (24) follows becauseφ i is an involution. Equation (25) and eq. (28) follow by item 1. Equation (26) and eq. (29) follow by item 3. Equation (27) holds by assumption onθ ∗ . Then eq. (29) shows that for anyi,f(A|φ i ·θ ∗ )< f(B|φ i ·θ ∗ ), satisfying definition 3.5’s item 1. This result’s item 2 satisfies definition 3.5’s item 2. We now just need to show definition 3.5’s item 3. Disjointness.Letθ ′ ,θ ′ ∈Orbit| Θ,A>B (θ)and leti6=j. Supposeφ i ·θ ′ =φ j ·θ ′ . We want to show that this leads to contradiction. f(A|θ ′ )≤f(B ? j |φ j ·θ ′ )(30) =f(B ? j |φ −1 i ·θ ′ )(31) ≤f(B ? j |θ ′ )(32) ≤f(B|θ ′ )(33) < f(A|θ ′ )(34) ≤f(B ? i |φ i ·θ ′ )(35) =f(B ? i |φ −1 j ·θ ′ )(36) ≤f(B ? i |θ ′ )(37) ≤f(B|θ ′ )(38) < f(A|θ ′ ).(39) Equation (30) follows by our assumption of item 1. Equation (31) holds because we assumed that φ j ·θ ′ =φ i ·θ ′ , and the involution ensures thatφ i =φ −1 i . Equation (32) is guaranteed by our assumption of item 4, given thatφ −1 i ·θ ′ =φ i ·θ ′ ∈Orbit| Θ,B>A (θ)]by the first half of this proof. Equation (33) follows by our assumption of item 3. Equation (34) follows because we assumed that θ ′ ∈Orbit| Θ,A>B (θ). Equation (35) through eq. (39) follow by the same reasoning, switching the roles ofθ ′ andθ ′ , and of iandj. But then we have demonstrated that a quantity is strictly less than itself, a contradiction. So for allθ ′ ,θ ′ ∈Orbit| Θ,A>B (θ), wheni6=j,φ i ·θ ′ 6=φ j ·θ ′ . Therefore, we have shown definition 3.5’s item 3, and sofis a(Θ,A n →B)-retargetable function. Apply theorem 3.6 in order to conclude that eq. (23) holds. Definition B.8(Superset-of-copy containment).LetA,B⊆R d .Bcontainsnsuperset-copiesB ? i ofAwhen there exist involutionsφ 1 ,...,φ n such thatφ i ·A⊆B ? i ⊆B , and wheneveri6=j, φ i ·B ? j =B ? j . 19 Lemma B.9(Looser sufficient conditions for orbit-level incentives).Suppose thatΘis a subset of a set acted on byS d and is closed under permutation byS d . LetA,B∈E⊆P ( R d ) . Suppose that Bcontainsnsuperset-copiesB ? i ∈EofAviaφ i . Suppose thatf(X|θ)is increasing under joint permutation byφ 1 ,...,φ n ∈S d for allX∈E,θ∈Θ, and suppose that∀i : φ i ·A∈E. Suppose thatfis monotonically increasing on its first argument. Thenf(B|θ)≥ n most:Θ f(A|θ). Proof.We check the conditions of lemma B.7. Letθ∈Θ, and letθ ∗ ∈(S d ·θ)∩Θbe an orbit element. Item 1.Holds sincef(A|θ ∗ )≤f(φ i ·A|φ i ·θ ∗ )≤f(B ? i |φ i ·θ ∗ ), with the first inequal- ity by assumption of joint increasing under permutation, and the second following from monotonicity (asφ i ·A⊆B ? i by superset copy definition B.8). Item 2. We have∀θ ∗ ∈(S d ·θ ∗ )∩Θ : f(B|θ ∗ )< f(A|θ ∗ ) =⇒ ∀i= 1,...,n : φ i ·θ ∗ ∈Θ sinceΘis closed under permutation. Item 3. Holds because we assumed thatfis monotonic on its first argument. Item 4.Holds becausefis increasing under joint permutation onallof its inputsX,θ ′ , and definition B.8 shows thatφ i ·B ? j =B ? j wheni6=j. Combining these two steps of reasoning, forallθ ′ ∈Θ, it is true thatf ( B ? j |θ ′ ) ≤f ( φ i ·B ? j |φ i ·θ ′ ) ≤f ( B ? j |φ i ·θ ′ ) . Then apply lemma B.7. Lemma B.10(Hiding an argument which is invariant under certain permutations).LetE 1 ,E 2 ,Θbe subsets of sets which are acted on byS d . LetA∈E 1 ,C∈E 2 . Suppose there existφ 1 ,...,φ n ∈S d such thatφ i ·C=C. Supposeh : E 1 ×E 2 ×Θ→Rsatisfies∀i : h(A,C|θ)≤h(φ i ·A,φ i ·C| φ i ·θ) . For anyX∈E 1 , letf(X|θ) : =h(X,C|θ). Thenf(A|θ)is increasing under joint permutation byφ i . Furthermore, ifhisinvariantunder joint permutation byφ i , then so isf. Proof. f(X|θ) : =h(X,C|θ)(40) ≤h(φ i ·X,φ i ·C|φ i ·θ)(41) =h(φ i ·X,C|φ i ·θ)(42) = : f(φ i ·X|φ i ·θ).(43) Equation (41) holds by assumption. Equation (42) follows because we assumedφ i ·C=C. Thenf is increasing under joint permutation by theφ i . Ifhisinvariant, then eq. (41) is an equality, and so∀i : f(X|θ) =f(φ i ·X|φ i ·θ). B.2.1 EU-determined functions Lemma B.11 and lemma B.5 together extend Turner et al. [2021]’s lemma E.17 beyond functions of max x∈X i , to any functions of cardinalities and of expected utilities of set elements. Definition A.12(EU-determined functions).LetP ( R d ) be the power set ofR d , and letf : ∏ m i=1 P ( R d ) ×R d →R .fis anEU-determined functionif there exists a family of functions g ω 1 ,...,ω m such that f(X 1 ,...,X m |u) =g |X 1 |,...,|X m | ( [ x > 1 u ] x 1 ∈X 1 ,..., [ x > m u ] x m ∈X m ) ,(4) where[r i ]is the multiset of its elementsr i . Lemma B.11 (EU-determined functions are invariant under joint permutation).Suppose thatf : ∏ m i=1 P ( R d ) ×R d →R is an EU-determined function. Then for anyφ∈S d andX 1 ,...,X m ,u, we havef(X 1 ,...,X m |u) =f(φ·X 1 ,...,φ·X m |φ·u). 20 Proof. f(X 1 ,...,X m |u)(44) =g |X 1 |,...,|X m | ( [ x > 1 u ] x 1 ∈X 1 ,..., [ x > m u ] x m ∈X m ) (45) =g |φ·X 1 |,...,|φ·X m | ( [ x > 1 u ] x 1 ∈X 1 ,..., [ x > m u ] x m ∈X m ) (46) =g |φ·X 1 |,...,|φ·X m | ( [ (P φ x 1 ) > (P φ u) ] x 1 ∈X 1 ,..., [ (P φ x m ) > (P φ u) ] x m ∈X m ) (47) =f(φ·X 1 ,...,φ·X m |φ·u).(48) Equation (46) holds because permutationsφact injectively onR d . Equation (47) follows because I=P −1 φ P φ =P > φ P φ by the orthogonality of permutation matrices, andx > P > φ = (P φ x) > , so x > u=x > P > φ P φ u= (P φ x) > (P φ u). Theorem A.13(Orbit tendencies occur for EU-determined decision-making functions).Let A,B,C⊆R d be such thatBcontainsncopies ofAviaφ i such thatφ i ·C=C. Leth : ∏ 2 i=1 P ( R d ) ×R d →R be an EU-determined function, and letp(X|u) : =h(X,C|u). Suppose thatpreturns a probability of selecting an element ofXfromC. Thenp(B|u)≥ n most:R d p(A|u). Proof.By assumption, there exists a family of functions g i,|C| such that for allX⊆R d ,h(X,C| u) =g |X|,|C| ( [ x > u ] x∈X , [ c > u ] c∈C ) . Therefore, lemma B.11 shows thath(A,C|u)is invariant under joint permutation by theφ i . LettingΘ : =R d , apply lemma B.10 to conclude thatf(X|u)is invariant under joint permutation by theφ i . Sincefreturns a probability of selecting an element ofX,fobeys the monotonicity probability axiom: IfX ′ ⊆X, thenf(X ′ |u)≤f(X|u). Thenf(B|u)≥ n most:R d f(A|u)by lemma B.9. B.3 Particular results on retargetable functions Definition B.12(Quantilization, closed form).Let the expected utilityq-quantile threshold be M q,P (C|u) : = inf M∈R|P x∼P ( x > u> M ) ≤q .(49) LetC >M q,P (C|u) : = c∈C|c > u> M q,P (C|u) .C =M q,P (C|u) is defined similarly. Let1 L(x) be the predicate function returning1ifL(x)is true and0otherwise. Then forX⊆C, Q q,P (X|C,u) : = ∑ x∈X P(x) q 1 x∈C >M q,P (C|u) + 1 x∈C =M q,P (C|u) P ( C =M q,P (C|u) ) ( q−P ( C >M q,P (C|u) ) ) , (50) where the summand is defined to be0ifP(x) = 0andx∈C =M q,P (C|u) . Remark. Unlike Taylor [2016]’s or Carey [2019]’s definitions, definition B.12 is written in closed form and requires no arbitrary tie-breaking. Instead, in the case of an expected utility tie on the quantile threshold, eq. (50) allots probability to outcomes proportional to their probability under the base distributionP. Thanks to theorem A.13, we straightforwardly prove most items of proposition A.11 by just rewriting each decision-making function as an EU-determined function. Most of the proof’s length comes from showing that the functions are measurable onu, which means that the results also apply for distributions over utility functionsD any ∈D any . Proposition A.11 (Orbit incentives for different rationalities).LetA,B⊆C( R d be finite, such thatBcontainsncopies ofAvia involutionsφ i such thatφ i ·C=C. 21 1.Rational choice [Turner et al., 2021]. IsOptimal ( B|C,D any ) ≥ n most:D any IsOptimal ( A|C,D any ) . 2.Uniformly randomly choosing an optimal lottery.ForX⊆C, let FracOptimal ( X|C,u ) : = ∣ ∣ ∣ arg max c∈C c > u ∩X ∣ ∣ ∣ ∣ ∣ ∣ arg max c∈C c > u ∣ ∣ ∣ . ThenFracOptimal ( B|C,D any ) ≥ n most:D any FracOptimal ( A|C,D any ) . 3.Anti-rational choice.AntiOpt ( B|C,D any ) ≥ n most:D any AntiOpt ( A|C,D any ) . 4.Boltzmann rationality. Boltzmann T ( B|C,D any ) ≥ n most:D any Boltzmann T ( A|C,D any ) . 5.Uniformly randomly drawingkoutcome lotteries and choosing the best. ForX⊆C, u∈R d , andk≥1, let best-of-k(X,C|u) : =E a 1 ,...,a k ∼unif(C) [ FracOptimal ( X∩a 1 ,...,a k |a 1 ,...,a k ,u ) ] . Then best-of-k(B|C,D any )≥ n most:D any best-of-k(A|C,D any ). 6.Satisficing [Simon, 1956].Satisfice t ( B|C,D any ) ≥ n most:D any Satisfice t ( A|C,D any ) . 7.Quantilizing over outcome lotteries [Taylor, 2016]. LetPbe the uniform probability dis- tribution overC. ForX⊆C,u∈R d , andq∈(0,1], letQ q,P (X|C,u)(definition B.12) return the probability that an outcome lottery inXis drawn from the topq-quantile ofP, sorted by expected utility underu. ThenQ q,P (B|C,u)≥ n most:R d Q q,P (A|C,u). Proof.Item 1.Consider h(X,C|u) : =1 ∃x∈X : ∀c∈C : x > u≥c > u (51) = min 1, ∑ x∈X ∏ c∈C 1 (x−c) > u≥0 .(52) Since halfspaces are measurable, each indicator function is measurable onu. The finite sum of the finite product of measurable functions is also measurable. Sinceminis continuous (and therefore measurable),h(X,C|u)is measurable onu. Furthermore,his an EU-determined function: h(X,C|u) =g V X ︷︸︷ [ x > u ] x∈X , V C ︷ ︸︷ [ c > u ] c∈C (53) : =1 ∃v x ∈V X : ∀v c ∈V C : v x ≥v c .(54) Then by lemma B.11,his invariant to joint permutation by theφ i . Sinceφ i ·C=C, lemma B.10 shows thath ′ (X|u) : =h(X,C|u)is also invariant under joint permutation by theφ i . Sincehis a measurable function ofu, so ish ′ . Then sinceh ′ is bounded, lemma B.5 shows thatf(X|D any ) : = E u∼D any [ h ′ (X|u) ] is invariant under joint permutation byφ i . Furthermore, ifX ′ ⊆X,f(X ′ |D any )≤f(X|D any )by the monotonicity of probability. Then by lemma B.9, f(B|D any ) : = IsOptimal ( B|C,D any ) ≥ n most:D any IsOptimal ( A|C,D any ) = : f(A|D any ). 22 Item 2.BecauseX,Care finite sets, the denominator ofFracOptimal ( X|C,u ) is never zero, and so the function is well-defined.FracOptimal ( X|C,u ) is an EU-determined function: FracOptimal ( X|C,u ) =g V X ︷ ︸︷ [ x > u ] x∈X , V C ︷︸︷ [ c > u ] c∈C (55) : = ∣ ∣ ∣ [ v∈V X |v= max v ′ ∈V C v ′ ] ∣ ∣ ∣ ∣ ∣ ∣ [ arg max v ′ ∈V C v ′ ] ∣ ∣ ∣ ,(56) with the[·]denoting a multiset which allows and counts duplicates. Then by lemma B.11, FracOptimal ( X|C,u ) is invariant to joint permutation by theφ i . We now show thatFracOptimal ( X|C,u ) is a measurable function ofu. FracOptimal ( X|C,u ) : = ∣ ∣ ∣ arg max c ′ ∈C c ′> u ∩X ∣ ∣ ∣ ∣ ∣ ∣ arg max c ′ ∈C c ′> u ∣ ∣ ∣ (57) = ∑ x∈X 1 x∈arg max c ′ ∈C c ′> u ∑ c∈C 1 c∈arg max c ′ ∈C c ′> u (58) = ∑ x∈X ∏ c ′ ∈C 1 (x−c ′ ) > u≥0 ∑ c∈C ∏ c ′ ∈C 1 (c−c ′ ) > u≥0 .(59) Equation (59) holds becausexbelongs to thearg maxiff∀c∈C : x > u≥c > u. Furthermore, this condition is met iffubelongs to the intersection of finitely many closed halfspaces; there- fore, u∈R d | ∏ c∈C 1 (x−c) > u≥0 = 1 is measurable. Then the sums in both the numerator and denominator are both measurable functions ofu, and the denominator cannot vanish. Therefore, FracOptimal ( X|C,u ) is a measurable function ofu. Letg(X|u) : = FracOptimal ( X|C,u ) . Sinceφ i ·C=C, lemma B.10 shows thatg(X|u)is also invariant to joint permutation byφ i . Sincegis measurable and bounded[0,1], apply lemma B.5 to conclude thatf(X|D any ) : =E u∼D any [ g(X|C,u) ] is also invariant to joint permutation byφ i . Furthermore, ifX ′ ⊆X⊆C, thenf(X ′ | D any )≤f(X| D any ). So apply lemma B.9 to conclude thatFracOptimal ( B|C,D any ) = : f(B| D any )≥ n most:D any f(A| D any ) : = FracOptimal ( A|C,D any ) . Item 3.Apply the reasoning in item 1 with inner functionh(X|C,u) : =1 ∃x∈X : ∀c∈C : x > u≤c > u . Item 4.LetX⊆C.Boltzmann T ( X|C,u ) is the expectation of an EU function: Boltzmann T ( X|C,u ) =g T V X ︷ ︸︷ [ x > u ] x∈X , V C ︷ ︸︷ [ c > u ] c∈C (60) : = ∑ v∈V X e v/T ∑ v∈V C e v/T .(61) Therefore, by lemma B.11,Boltzmann T ( X|C,u ) is invariant to joint permutation by theφ i . Inspecting eq. (61), we see thatgis continuous onu(and therefore measurable), and bounded[0,1] sinceX⊆Cand the exponential function is positive. Therefore, by lemma B.5, the expectation ver- sion is also invariant to joint permutation for all permutationsφ∈S d :Boltzmann T ( X|C,D any ) = Boltzmann T ( φ·X|φ·C,φ·D any ) . Sinceφ i ·C=C, lemma B.10 shows thatf(X| D any ) : = Boltzmann T ( X|C,D any ) is also invariant under joint permutation by theφ i . Furthermore, ifX ′ ⊆X, thenf(X ′ | D any )≤ 23 f(X| D any ). Then apply lemma B.9 to conclude thatBoltzmann T ( B|C,D any ) = : f(B| D any )≥ n most:D any f(A|D any ) : = Boltzmann T ( A|C,D any ) . Item 5.Let involutionφ∈S d fixC(i.e.φ·C=C). best-of-k(X|C,u)(62) : =E a 1 ,...,a k ∼unif(C) [ FracOptimal ( X∩a 1 ,...,a k |a 1 ,...,a k ,u ) ] (63) =E a 1 ,...,a k ∼unif(C) [ FracOptimal ( (φ·X)∩φ·a 1 ,...,φ·a k |φ·a 1 ,...,φ·a k ,φ·u ) ] (64) =E φ·a 1 ,...,φ·a k ∼unif(φ·C) [ FracOptimal ( (φ·X)∩φ·a 1 ,...,φ·a k |φ·a 1 ,...,φ·a k ,φ·u ) ] (65) = : best-of-k(φ·X|φ·C,φ·u).(66) By the proof of item 2, FracOptimal ( X∩a 1 ,...,a k |a 1 ,...,a k ,u ) = FracOptimal ( (φ·X)∩φ·a 1 ,...,φ·a k |φ·a 1 ,...,φ·a k ,φ·u ) ; thus, eq. (64) holds. Sinceφ·C=Cand since the distribution is uniform, eq. (65) holds. Therefore, best-of-k(X|C,u)is invariant to joint permutation by theφ i , which are involutions fixingC. We now show that best-of-k(X|C,u)is measurable onu. best-of-k(X|C,u)(67) : =E a 1 ,...,a k ∼unif(C) [ FracOptimal ( X∩a 1 ,...,a k |a 1 ,...,a k ,u ) ] (68) = 1 |C| k ∑ (a 1 ,...,a k )∈C k FracOptimal ( X∩a 1 ,...,a k |a 1 ,...,a k ,u ) .(69) Equation (69) holds becauseFracOptimal ( X|C,u ) is measurable onuby item 2, and measurable functions are closed under finite addition and scalar multiplication. Thenbest-of-k(X|C,u)is measurable onu. Letg(X|u) : =best-of-k(X|C,u). Sinceφ i ·C=C, lemma B.10 shows thatg(X|u)is also invariant to joint permutation byφ i . Sincegis measurable and bounded[0,1], apply lemma B.5 to conclude thatf(X|D any ) : =E u∼D any [ g(X|C,u) ] is also invariant to joint permutation byφ i . Furthermore, ifX ′ ⊆X⊆C, thenf(X ′ |D any )≤f(X|D any ). So apply lemma B.9 to conclude that best-of-k(B|C,D any ) = : f(B|D any )≥ n most:D any f(A|D any ) : =best-of-k(A|C,D any ). Item 6.Satisfice t ( X|C,u ) is an EU-determined function: Satisfice t ( X|C,u ) =g t V X ︷ ︸︷ [ x > u ] x∈X , V C ︷ ︸︷ [ c > u ] c∈C (70) : = ∑ v∈V X 1 v≥t ∑ v∈V C 1 v≥t ,(71) with the function evaluating to0if the denominator is0. Then applying lemma B.11,Satisfice t ( X|C,u ) is invariant under joint permutation by theφ i . We now show thatSatisfice t ( X|C,u ) is measurable onu. Satisfice t ( X|C,u ) = ∑ x∈X 1 x∈ x ′ ∈R d |x ′> u≥t ∑ c∈C 1 c∈ x ′ ∈R d |x ′> u≥t ∃c∈C : c > u≥t, 0else. (72) 24 Consider the two cases. ∃c∈C : c > u≥t⇐⇒u∈ ⋃ c∈C u ′ ∈R d |c > u≥t . The right-hand set is the union of finitely many halfspaces (which are measurable), and so the right-hand set is also measurable. Then the casing is a measurable function ofu. Clearly the zero function is measurable. Now we turn to the first case. In the first case, eq. (72)’s indicator functions test eachx,cfor membership in a closed halfspace with respect tou. Halfspaces are measurable sets. Therefore, the indicator function is a measurable function ofu, and so are the finite sums. Since the denominator does not vanish within the case, the first case as a whole is a measurable function ofu. Therefore,Satisfice t ( X|C,u ) is measurable onu. SinceSatisfice t ( X|C,u ) is measurable and bounded[0,1](asX⊆C), apply lemma B.5 to con- clude thatSatisfice t ( X|C,D any ) = Satisfice t ( φ·X|φ·C,φ·D any ) . Next, letf(X| D any ) : = Satisfice t ( X|C,D any ) . Since we just showed thatSatisfice t ( X|C,D any ) is invariant to joint permutation by the involutionsφ i and sinceφ i ·C=C,f(X| D any )is also invariant to joint permutation byφ i . Furthermore, ifX ′ ⊆X, we havef(X ′ | D any )≤f(X| D any ). Then applying lemma B.9, Satisfice t ( B|C,u ) = : f(B|D any )≥ n most:D any f(A|D any ) : = Satisfice t ( A|C,u ) . Item 7.SupposePis uniform overCand consider any of the involutionsφ i . M q,P (C|u) : = inf M∈R|P x∼P ( x > u> M ) ≤q (73) = inf M∈R|P x∼P ( (P φ i x) > (P φ i u)> M ) ≤q (74) = inf M∈R|P x∼φ i ·P ( x > (P φ i u)> M ) ≤q (75) = inf M∈R|P x∼P ( x > (P φ i u)> M ) ≤q (76) = : M q,P (φ i ·C|φ i ·u).(77) Equation (74) follows by the orthogonality of permutation matrices. Equation (76) follows because if x∈supp(P) =C, thenφ i ·x∈C= supp(P), and furthermoreP(x) =P(P φ i x)by uniformity. Now we show the invariance ofC >M q,P (C|u) under joint permutation byφ i : C >M q,P (C|u) : = c∈C|c > u> M q,P (C|u) (78) = c∈C|(P φ i c) > (P φ i u)> M q,P (φ i ·C|φ i ·u) (79) = c∈φ i ·C|c > (P φ i u)> M q,P (φ i ·C|φ i ·u) (80) = : C >M q,P (φ i ·C|φ i ·u) .(81) Equation (79) follows by the orthogonality of permutation matrices and becauseM q,P (C|u) = M q,P (φ i ·C|φ i ·u)by eq. (77). A similar proof shows thatC =M q,P (C|u) =C =M q,P (φ i ·C|φ i ·u) . Recall that Q q,P (X|C,u) : = ∑ x∈X P(x) q 1 x∈C >M q,P (C|u) + 1 x∈C =M q,P (C|u) P ( C =M q,P (C|u) ) ( q−P ( C >M q,P (C|u) ) ) . (82) Q q,P (X|C,u) =Q q,P (φ i ·X|φ i ·C,φ i ·u), sinceQis the sum of products ofφ i -invariant quantities. 25 P(x)is non-negative becausePis a probability distribution, andqis assumed positive. The indicator functions1are non-negative. By the definition ofM q,P ,P ( C >M q,P (C|u) ) ≤q. Therefore, eq. (82) is the sum of non-negative terms. Thus, ifX ′ ⊆X, thenQ q,P (X ′ |C,u)≤Q q,P (X|C,u). Letf(X|u) : =Q q,P (X|C,u). Sinceφ i ·C=Cand sinceQ q,P (X|C,u) =Q q,P (φ i ·X| φ i ·C,φ i ·u) , lemma B.10 shows thatf(X|u)is also jointly invariant to permutation byφ i . Lastly, ifX ′ ⊆X, we havef(X ′ |D any )≤f(X|D any ). Apply lemma B.9 to conclude thatQ q,P (B|C,u) = : f(B|u)≥ n most:R d f(A|u) : =Q q,P (A| C,u). Conjecture B.13(Orbit tendencies occur for more quantilizer base distributions).Proposition A.11’s item 7 holds for any base distributionPoverCsuch thatmin b∈B P(b)≥max a∈A P(a). Further- more,Q q,P (X|C,u)is measurable onuand so≥ n most:R d can be generalized to≥ n most:D any . Appendix C Detailed analyses ofMRscenarios C.1 Action selection Consider a bandit problem with five armsa 1 ,...,a 5 partitionedA : =a 1 ,B : =a 2 ,...,a 5 , which each action has a definite utilityu i . There areT= 100trials. Suppose the training procedure trainuses the-greedy strategy to learn value estimates for each arm. At the end of training,train outputs a greedy policy with respect to its value estimates. Consider any action-value initialization, and the learning rate is setα : = 1. To learn an optimal policy, at worst, the agent just has to try each action once. Lemma C.1 (Lower bound on success probability of thetrainbandit).Letu∈R 5 assign strictly maximal utility toa i , and supposetrain(described above) runs forT≥5trials. Thenp train (a i | u)≥1−(1− 4 ) T . Proof.Since the trained policy can be stochastic, p train (a i |u)≥P(a i is assigned probability1by the learned greedy policy). Sincea i has strictly maximal utility which is deterministic, and since the learning rateα : = 1, if actiona i is ever drawn, it is assigned probability1by the learned policy. The probability thata i is never explored is at most(1− 4 ) T , because at worst,a i is an “explore” action (and not an “exploit” action) at every time step, in which case it is ignored with probability1− 4 . Proposition C.2(The train bandit is 4-retargetable).p train is(R 5 ,A 4 →B)-retargetable. Proof.Letφ i : =a 1 ↔a i fori= 2,...,5and letΘ : =R 5 . We want to show that wheneveru∈R 5 inducesp train (A|u)> p train (B|u), retargetinguwill gettrainto instead learn to pull aB-action: p train (A|φ i ·u)< p train (B|φ i ·u). Suppose we have such au. Ifuis constant, a symmetry argument shows that each action has equal probability of being selected, in which casep train (A|u) = 1 5 < 4 5 =p train (B|u) —a contradiction. Therefore,uis not constant. Similar symmetry arguments show thatA’s actiona 1 has strictly maximal utility (u 1 >max i=2,...,5 u i ). But forT= 100, lemma C.1 shows thatp train (A|u) =p train (a 1 |u)≈1andp train ( a i6=1 | u)≈0 =⇒p train (B|u) = ∑ i6=1 p train (a i |u)≈0 . The converse statement holds when consideringφ i ·uinstead ofu. Therefore,trainsatisfies definition 3.5’s item 1 (retargetability). Theseφ i ·u∈Θ : =R 5 becauseR 5 is closed under permutation byS 5 , satisfying item 2. Consider anotheru ′ ∈R 5 such thatp train (A|u ′ )> p train (B|u ′ ), and consideri6=j. By the above symmetry arguments,u ′ must also assigna 1 maximal utility. By lemma C.1,p train (a i |φ i ·u)≈1 andp train ( a j |φ i ·u)≈0 sincei6=j, and vice versa when consideringφ j ·uinstead ofφ i ·u. Then sinceφ i ·uandφ j ·uinduce distinct probability distributions over learned actions, they cannot be the same utility function. This satisfies item 3. 26 Figure 3: Map of the first level of Montezuma’s Revenge. Corollary C.3(The train bandit has orbit-level tendencies).p train (B|u)≥ 4 most:R 5 p train (A|u). Proof.Combine proposition C.2 and theorem 3.6. C.2 Observation reward maximization LetTbe a reasonably long rollout length, so thatO T-reach is large—many different step-Tobservations can be induced. Proposition C.4(Final reward maximization has strong orbit-level incentives inMR).Letn : = b |O leave | | O stay | c.p max (O leave |R)≥ n most:R O p max (O stay |R). Proof.Consider the vector space representation of observations,R |O| . DefineA : =e o |o∈ O stay ,B : =e o |o∈O leave , andC : =O T-reach =A∪Bthe union ofO stay ,O leave . Since|O leave |≥ ∣ ∣ O stay ∣ ∣ by assumption thatTis reasonably large, consider the involutionφ 1 ∈S |O| which embedsO stay intoO leave , while fixing all other observations. If possible, produce another involutionφ 2 which also embedsO stay intoO leave , which fixes all other observations, and which “doesn’t interfere withφ 1 ” (i.e.φ 2 ·(φ 1 ·A) =φ 1 ·A). We can producen : =b |O leave | | O stay | csuch involutions. Therefore,Bcontainsncopies (definition A.7) ofAvia involutionsφ 1 ,...,φ n . Furthermore, φ i ·(A∪B) =A∪B, since eachφ i swapsAwithB ′ ⊆B, and fixes allb∈B ′ by assumption. Thus,φ·C=C. By proposition A.11’s item 2,FracOptimal ( B|C,R ) ≥ n most:R O FracOptimal ( A|C,R ) . Since p max uniformly randomly chooses a maximal-reward observation to induce,∀X⊆C : p max (X| R) = FracOptimal ( X|C,R ) . Therefore,p max (O leave |R)≥ n most:R O p max (O stay |R). We want to reason about the probability thatdecideleaves the initial room by timeTin its rollout trajectories. p decide (leave|θ) : =P π∼decide(θ), τ∼π|s 0 (τhas left the first room by stepT),(83) p decide (stay|θ) : =P π∼decide(θ), τ∼π|s 0 (τhas not left the first room by stepT).(84) 27 We want to show that reward maximizers tend to leave the room:p max (leave|R)≥ n most:Θ p max (stay|R). However, we must be careful: In general,p max (O leave |R)6=p max (leave|R) andp max (O stay |R)6=p max (stay|R). For example, suppose thato T ∈O leave . By the definition of O leave ,o T can only be observed if the agent has left the room by time stepT, and so the trajectory τmust have left the first room. The converse argument does not hold: The agent could leave the first room, re-enter, and then wait until timeT. Although one of the doors would have been opened (fig. 2), the agent can also open the door without leaving the room, and then realize the same step-T observation. Therefore, this observation doesn’t belong toO leave . Lemma C.5(Room-status inequalities forMR). p decide (stay|θ)≤p decide (O stay |θ),(85) andp decide (O leave |θ)≤p decide (leave|θ).(86) Proof.For anydecide, p decide (stay|θ)(87) =P π∼decide(θ), τ∼π|s 0 (τstays through stepT)(88) = ∑ o∈O P π∼decide(θ), τ∼π|s 0 (oat stepTofτ)P π∼decide(θ), τ∼π|s 0 ( τstays|oat stepT ) (89) = ∑ o∈O T-reach P π∼decide(θ), τ∼π|s 0 (oat stepT)P π∼decide(θ), τ∼π|s 0 ( τstays|oat stepT ) (90) = ∑ o∈O stay P π∼decide(θ), τ∼π|s 0 (oat stepT)P π∼decide(θ), τ∼π|s 0 ( τstays|oat stepT ) (91) ≤ ∑ o∈O stay P π∼decide(θ), τ∼π|s 0 (oat stepT)(92) =P π∼decide(θ), τ∼π|s 0 ( o T ∈O stay ) (93) = : p decide (O stay |θ).(94) Equation (90) holds because the definition ofO T-reach ensures that ifo6∈O T-reach , then P π∼decide(θ), τ∼π|s 0 ( o|θ ) = 0. Becauseo∈O T-reach stay implies thatτleft and so P π∼decide(θ), τ∼π|s 0 ( τstays|oat stepT ) = 0, eq. (91) follows. Then we have shown eq. (85). For eq. (86), p decide (O leave |θ)(95) : =P π∼decide(θ), τ∼π|s 0 (o T ∈O leave )(96) = ∑ o∈O leave P π∼decide(θ), τ∼π|s 0 (oat stepT)(97) = ∑ o∈O leave P π∼decide(θ), τ∼π|s 0 (oat stepT)P π∼decide(θ), τ∼π|s 0 ( τleaves by stepT|oat stepT ) (98) = ∑ o∈O P π∼decide(θ), τ∼π|s 0 (oat stepT)P π∼decide(θ), τ∼π|s 0 ( τleaves by stepT|oat stepT ) (99) =P π∼decide(θ), τ∼π|s 0 (τhas left the first room by stepT)(100) 28 = : p decide (leave|θ).(101) Equation (98) follows because, sinceo∈O leave are only realizable by leaving the first room, this impliesP π∼decide(θ), τ∼π|s 0 ( τleaves by stepT|oat stepT ) = 1. Equation (99) follows because O leave ⊆O, and probabilities are non-negative. Then we have shown eq. (86). Corollary C.6(Final reward maximizers tend to leave the first room inMR). p max (leave|R)≥ n most:R O p max (stay|R).(102) Proof. Using lemma C.5 and proposition C.4, apply lemma B.1 withf 0 (R) : =p max (leave| R),f 1 (R) : =p max (O leave |R),f 2 (R) : =p max (O stay |R),f 3 (R) : =p max (stay|R) to conclude that p max (leave|R)≥ n most:R O p max (stay|R). C.3 Featurized reward maximization Θ : =R O assumes we will specify complicated reward functions over observations, with|O|degrees of freedom in their specification. Any observation can get any number. However, reward functions are often specified more compactly. For example, in section 4.3, the (additively) featurized reward functionR feat (o T ) : =feat(o T ) > αhas four degrees of freedom. Compared to typical reward functions (which would look like “random noise” to a human),R feat more easily trains competent policies because of the regularities between the reward and the state features. In this setup,p max chooses a policy which induces a step-Tobservation with maximal reward. Reward depends only on the feature vector of the final observation—more specifically, on the agent’s item counts. There are more possible item counts available by first leaving the room, than by staying. We will now conduct a more detailed analysis and conclude thatp max (O leave |α)≥ 3 most:R 4 p max (O stay | α) . Informally, we can retarget which items the agent prioritizes, and thereby retarget fromO stay to O leave . Consider the featurization function which takes as input an observationo∈O: feat(o) : = # of keys in inventory shown byo # of swords in inventory shown byo # of torches in inventory shown byo # of amulets in inventory shown byo .(103) ConsiderA feat : = feat(o)|o∈O stay ,B feat : = feat(o)|o∈O leave . Lete i ∈R 4 be the standard basis vector with a1in entryiand0elsewhere. When restricted to the room shown in fig. 2, the agent can either acquire the key in the first room and retain it until stepT (e 1 ), or reach time stepTempty-handed (0). We conclude thatA feat =e 1 ,0. ForB feat , recall that in section 4.2 we assumed the rollout lengthTto be reasonably large. Then by leaving the room, some realizable trajectory induceso T displaying an inventory containing only a sword (e 2 ), or only a torch (e 3 ), or only an amulet (e 4 ), or nothing at all (0). Therefore, e 2 ,e 3 ,e 4 ,0 ⊆B feat .B feat contains3copies ofA feat (definition A.7) via involutionsφ i : 1↔i, i6= 1. Suppose all feature coefficient vectorsα∈R 4 are plausible. ThenΘ : =R 4 . Let us be more specific about what is entailed by featurized reward maximization. Thedecide max (α) procedure takesαas input and then considers the reward functiono7→feat(o) > α. Then,decide max uniformly randomly chooses an observationo T ∈O T-reach which maximizes this featurized reward, and then uniformly randomly chooses a policy which implementso T . Lemma C.7(FracOptimalinequalities).LetX⊆Y ′ ⊆Y( R d be finite, and letu∈R d . Then FracOptimal ( X|Y,u ) ≤FracOptimal ( X|Y ′ ,u ) ≤FracOptimal ( X∪(Y ′ )|Y,u ) . (104) Proof.For finiteX 1 ( R d , letBest ( X 1 |u ) : = arg max x 1 ∈X 1 x > 1 u . Supposey ′ ∈Best ( Y ′ |u ) , buty ′ 6∈Best ( Y|u ) . Then for alla∈Best ( Y ′ |u ) , a > u=y ′> u<max y∈Y y > u.(105) 29 Soa6∈Best ( Y|u ) . Then eitherBest ( Y ′ |u ) ⊆Best ( Y|u ) , or the two sets are disjoint. FracOptimal ( X|Y,u ) : = ∣ ∣ ∣ Best ( Y|u ) ∩X ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y|u ) ∣ ∣ ∣ (106) ≤ ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ = : FracOptimal ( X|Y ′ ,u ) (107) IfBest ( Y ′ |u ) ⊆Best ( Y|u ) , then sinceX⊆Y ′ , we haveX∩Best ( Y ′ |u ) =X∩ Best ( Y|u ) . Then in this case, eq. (106) has equal numerator and larger denominator than eq. (107). On the other hand, ifBest ( Y ′ |u ) ∩Best ( Y|u ) =∅, then sinceX⊆Y ′ ,X∩Best ( Y|u ) =∅. Then eq. (106) equals0, and eq. (107) is non-negative. Either way, eq. (107)’s inequality holds. To show the second inequality, we handle the two cases separately. Subset case.Suppose thatBest ( Y ′ |u ) ⊆Best ( Y|u ) . ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ ≤ ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ (108) = ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y ′ |u ) ∩(Y ′ ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ (109) = ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y|u ) ∩(Y ′ ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ (110) = ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y|u ) ∩(Y ′ ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y|u ) ∣ ∣ ∣ (111) = ∣ ∣ ∣ Best ( Y|u ) ∩X ∣ ∣ ∣ + ∣ ∣ ∣ Best ( Y|u ) ∩(Y ′ ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y|u ) ∣ ∣ ∣ (112) = ∣ ∣ ∣ Best ( Y|u ) ∩(X∪(Y ′ )) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y|u ) ∣ ∣ ∣ (113) = : FracOptimal ( X∪(Y ′ )|Y,u ) .(114) Equation (108) follows because whenn≤d,k≥0, we have n d ≤ n+k d+k . For eq. (110), since Best ( Y ′ |u ) ⊆Best ( Y|u ) , we must have Best ( Y|u ) = Best ( Y ′ |u ) ∪Best ( Y ′ |u ) . But then Best ( Y|u ) ∩(Y ′ ) = ( Best ( Y ′ |u ) ∩(Y ′ ) ) ∪ ( Best ( Y ′ |u ) ∩(Y ′ ) ) (115) = Best ( Y ′ |u ) ∩(Y ′ ).(116) Then eq. (110) follows. Equation (111) follows since Best ( Y|u ) = Best ( Y ′ |u ) ∪Best ( Y ′ |u ) . Equation (112) follows sinceX⊆Y ′ , and so Best ( Y ′ |u ) ∩X= Best ( Y|u ) ∩X. Equation (113) follows becauseX⊆Y ′ is disjoint ofY ′ . We have shown that FracOptimal ( X|Y ′ ,u ) ≤FracOptimal ( X∪(Y ′ )|Y,u ) in this case. 30 Disjoint case.Suppose thatBest ( Y ′ |u ) ∩Best ( Y|u ) =∅. ∣ ∣ ∣ Best ( Y ′ |u ) ∩X ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ ≤1(117) = ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ (118) = ∣ ∣ ∣ Best ( Y ′ |u ) ∩(Y ′ ) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ (119) = ∣ ∣ ∣ Best ( Y ′ |u ) ∩(X∪(Y ′ )) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y ′ |u ) ∣ ∣ ∣ (120) = ∣ ∣ ∣ Best ( Y|u ) ∩(X∪(Y ′ )) ∣ ∣ ∣ ∣ ∣ ∣ Best ( Y|u ) ∣ ∣ ∣ (121) = : FracOptimal ( X∪(Y ′ )|Y,u ) .(122) Equation (117) follows becauseBest ( Y ′ |u ) ∩X⊆Best ( Y ′ |u ) . For eq. (120), note that we trivially haveBest ( Y ′ |u ) ∩Best ( Y ′ |u ) =∅, and also thatX⊆Y ′ . Therefore, Best ( Y ′ |u ) ∩X=∅, and eq. (120) follows. Finally, the disjointness assumption implies that max y ′ ∈Y ′ y ′> u<max y∈Y y > u. Therefore, the optimal elements ofYmust come exclusively fromY ′ ;i.e.Best ( Y|u ) = Best ( Y ′ |u ) . Then eq. (121) follows, and we have shown that FracOptimal ( X|Y ′ ,u ) ≤FracOptimal ( X∪(Y ′ )|Y,u ) in this case. Conjecture C.8(Generalizing lemma C.7).Lemma C.7 and Turner et al. [2021]’s Lemma E.26 have extremely similar functional forms. How can they be unified? Proposition C.9(Featurized reward maximizers tend to leave the first room inMR). p max (leave|α)≥ 3 most:R 4 p max (stay|α).(123) Proof. We want to show thatp max (O leave |α)≥ n most:R 4 p max (O stay |α). Recall thatA feat = e 1 ,0,B ′ feat : =e 2 ,e 3 ,e 4 ⊆B feat . p max (stay|α)(124) ≤p max (O stay |α)(125) : =P π∼decide max (α), τ∼π|s 0 ( o T ∈O stay ) (126) =P π∼decide max (α), τ∼π|s 0 ( o T ∈O stay ,feat(o T )6=0 ) +P π∼decide max (α), τ∼π|s 0 ( o T ∈O stay ,feat(o T ) =0 ) (127) ≤FracOptimal ( e 1 |C feat ,α ) +P π∼decide max (α), τ∼π|s 0 ( o T ∈O stay ,feat(o T ) =0 ) (128) ≤FracOptimal ( e 1 |e 1 ,e 2 ,e 3 ,e 4 ,α ) +P π∼decide max (α), τ∼π|s 0 ( o T ∈O stay ,feat(o T ) =0 ) (129) 31 ≤ 3 most:R 4 >0 FracOptimal ( e 2 ,e 3 ,e 4 |e 1 ,e 2 ,e 3 ,e 4 ,α ) +P π∼decide max (α), τ∼π|s 0 ( o T ∈O leave ,feat(o T ) =0 ) (130) ≤FracOptimal ( e 2 ,e 3 ,e 4 ∪(C feat \e 1 ,e 2 ,e 3 ,e 4 )|C feat ,α ) (131) = FracOptimal ( C feat \e 1 |C feat ,α ) (132) ≤P π∼decide max (α), τ∼π|s 0 (o T ∈O leave )(133) = : p max (O leave |α)(134) ≤p max (leave|α).(135) Equation (124) and eq. (135) hold by lemma C.5. Ifo T ∈O stay is realized byp max andfeat(o T )6=0, then we must havefeat(o T ) =e 1 be optimal and so thee 1 inventory configuration is realized. Therefore, eq. (128) follows. Equation (129) follows by applying the first inequality of lemma C.7 withX : =e 1 ,Y ′ : =e 1 ,e 2 ,e 3 ,e 4 ,Y : =C feat . By applying proposition A.11’s item 2 withA : =A feat =e 1 ,B ′ : =B ′ feat =e 2 ,e 3 ,e 4 , C : =A∪B ′ , we have FracOptimal ( e 1 |e 1 ,e 2 ,e 3 ,e 4 ,α ) ≤ 3 most:R 4 >0 FracOptimal ( e 2 ,e 3 ,e 4 |e 1 ,e 2 ,e 3 ,e 4 ,α ) .(136) Furthermore, observe that P π∼decide max (α), τ∼π|s 0 ( o T ∈O stay ,feat(o T ) =0 ) ≤P π∼decide max (α), τ∼π|s 0 ( o T ∈O leave ,feat(o T ) =0 ) (137) because either0is not optimal (in which case both sides equal 0), or else0is optimal, in which case the right side is strictly greater. This can be seen by considering howdecide max (α)uniformly randomly chooses an observation in which the agent ends up with an empty inventory. As argued previously, the vast majority of such observations can only be induced by leaving the first room. Combining eq. (136) and eq. (137), eq. (130) follows. Equation (131) follows by applying the second inequality of lemma C.7 withX : =e 2 ,e 3 ,e 4 ,Y ′ : =e 1 ,e 2 ,e 3 ,e 4 ,Y : =C feat . If feat(o T )∈B feat is realized byp max , then by the definition ofB feat ,o T ∈O leave is realized, and so eq. (133) follows. Then by applying lemma B.1 with f 0 (α) : =p max (leave|α),(138) f 1 (α) : = FracOptimal ( e 1 |e 1 ,e 2 ,e 3 ,e 4 ,α ) ,(139) f 2 (α) : = FracOptimal ( e 2 ,e 3 ,e 4 |e 1 ,e 2 ,e 3 ,e 4 ,α ) ,(140) f 3 (α) : =p max (stay|α),(141) we conclude thatp max (leave|α)≥ 3 most:R 4 >0 p max (stay|α). Lastly, note that if0∈Θandf(A|0)> f(B|0),fcannot be even be simply retargetable for theΘparameter set. This is because∀φ∈S d ,φ·0=0. For example, inductive bias ensures that, absent a reward signal, learned policies tend to stay in the initial room inMR. This is one reason why section 4.3’s analysis of the policy tendencies of reinforcement learning excludes the all-zero reward function. C.4 Reasoning for whyDQNcan’t explore well In section 4.3, we wrote: Mnih et al. [2015]’sDQNisn’t good enough to train policies which leave the first room ofMR, and soDQN(trivially) cannot be retargetableawayfrom the first room 32 via the reward function. There isn’t a single featurized reward function for which DQNvisits other rooms, and so we can’t haveαsuch thatφ·αretargets the agent toO leave .DQNisn’t good enough at exploring. We infer this is true from Nair et al. [2015], which shows that vanillaDQNgets zero score inMR. Thus,DQNnever even gets the first key. Thus,DQNonly experiences state-action-state transitions which didn’t involve acquiring an item, since (as shown in fig. 3) the other items are outside of the first room, which requires a key to exit. In our analysis, we considered a reward function which is featurized over item acquisition. Therefore, for all pre-key-acquisition state-action-state transitions, the featurized reward function returns exactly the same reward signals as those returned in training during the published experiments (namely, zero, becauseDQNcan never even get to the key in order to receive a reward signal). That is, sinceDQNonly experiences state-action-state transitions which didn’t involve acquiring an item, and the featurized reward functions only reward acquiring an item, it doesn’t matter what reward values are provided upon item acquisition—DQN’s trained behavior will be the same. Thus, aDQNagent trained on any featurized reward function will not explore outside of the first room. Appendix D Lower bounds onMDPpower-seeking incentives for optimal policies Turner et al. [2021] prove conditions under whichat least halfof the orbit of every reward function incentivizes power-seeking behavior. For example, in fig. 4, they prove that avoiding∅maximizes average per-timestep reward for at least half of reward functions. Roughly, there are more self-loop states (∅,` ↙ ,r ↘ ,r ↗ ) available if the agent goesleftorrightinstead of up towards∅. We strengthen this claim, with corollary D.12 showing that forat least three-quartersof the orbit of every reward function, it is average-optimal to avoid∅. Therefore, we answer Turner et al. [2021]’s open question of whether increased number of environ- mental symmetries quantitatively strengthens the degree to which power-seeking is incentivized. The answer isyes. In particular, it may be the case that only one in a million state-based reward functions makes it average-optimal for Pac-Man to die immediately. F ∅ ` / left ` ↙ ` ↖ r . right r ↘ r ↗ Figure 4: A toyMDPfor reasoning about power-seeking tendencies.Reproduced from Turner et al. [2021]. We will briefly restate several definitions needed for our key results, theorem D.11 and corollary D.12. For explanation, see Turner et al. [2021]. Definition D.1(Non-dominated linear functionals).LetX( R |S| be finite.ND(X) : = x∈X|∃r∈R |S| : x > r>max x ′ ∈X\x x ′> r . Definition D.2 (Bounded reward function distribution).D bound is the set of bounded-support proba- bility distributionsD bound . Remark.Whenn= 1, lemma D.3 reduces to the first part of Turner et al. [2021]’s lemma E.24, and lemma D.5 reduces to the first part of Turner et al. [2021]’s lemma E.28. Lemma D.3 (Quantitative expectation superiority lemma).LetA,B( R d be finite and letg : R→ Rbe a (total) increasing function. SupposeBcontainsncopies ofND(A). Then E r∼D bound [ g ( max b∈B b > r ) ] ≥ n most:D bound E r∼D bound [ g ( max a∈A a > r ) ] .(142) 33 Proof.Becauseg : R→Ris increasing, it is measurable (as ismax). LetL : = inf r∈supp(D bound ) max x∈X x > r,U : = sup r∈supp(D bound ) max x∈X x > r. Both exist because D bound has bounded support. Furthermore, sincegis monotone increasing, it is bounded[g(L),g(U)] on[L,U]. Therefore,gis measurable and bounded on eachsupp(D bound ), and so the relevant expectations exist for allD bound . For finiteX( R d , letf(X|u) : =g(max x∈X x > u). By lemma B.11,fis invariant under joint permutation byS d . Furthermore,fis measurable becausegandmaxare. Therefore, apply lemma B.5 to conclude thatf(X|D bound ) : =E u∼D bound [ g(max x∈X x > u) ] is also invariant under joint permutation byS d (withfbeing bounded when restricted tosupp(D bound )). Lastly, ifX ′ ⊆X, f(X ′ |D bound )≤f(X|D bound )becausegis increasing. E u∼D bound [ g ( max a∈A a > u ) ] =E u∼D bound g ( max a∈ND(A) a > u ) (143) ≤ n most:D any E r∼D bound [ g ( max b∈B b > r ) ] .(144) Equation (143) follows by corollary E.11 of [Turner et al., 2021]. Equation (144) follows by applying lemma B.9 withfas defined above with theφ 1 ,...,φ n guaranteed by the copy assumption. Definition D.4(Linear functional optimality probability [Turner et al., 2021]).For finiteA,B( R |S| , theprobability underD any thatAis optimal overBis p D any (A≥B) : =P r∼D any ( max a∈A a > r≥max b∈B b > r ) . Lemma D.5 (Quantitative optimality probability superiority lemma).LetA,B,C( R d be finite and letZsatisfyND(C)⊆Z⊆C. Suppose thatBcontainsncopies ofND(A)via involutionsφ i . Furthermore, letB extra : =B\ ( ∪ n i=1 φ i ·ND(A) ) ; suppose that for alli,φ i · ( Z extra ) =Z extra . Thenp D any (B≥C)≥ n most:D any p D any (A≥C). Proof.For finiteX,Y( R d , let g(X,Y|D any ) : =p D any (X≥Y) =E u∼D any [ 1 max x∈X x > u≥max y∈Y y > u ] . By the proof of item 1 of proposition A.11,gis the expectation of au-measurable function.gis an EU function, and so lemma B.11 shows that it is invariant to joint permutation byφ i . Letting f Y (X| D any ) : =g(X,Y| D any ), lemma B.10 shows thatf Y (X| D any ) =f Y (φ i ·X|φ i ·D any ) whenever theφ i satisfyφ i ·Y=Y. Furthermore, ifX ′ ⊆X, thenf Y (X ′ |D any )≤f Y (X|D any ). p D any (A≥C) =p D any ( ND(A)≥C ) (145) ≤p D any ( ND(A)≥Z extra ) (146) ≤ n most:D any p D any ( B≥Z extra ) (147) ≤p D any (B∪B extra ≥Z)(148) =p D any (B≥Z)(149) =p D any (B≥C).(150) Equation (145) follows by Turner et al. [2021]’s lemma E.12’s item 2 withX : =A ,X ′ : =ND(A) (similar reasoning holds forCandZin eq. (150)). Equation (146) follows by the first inequality of lemma E.26 of [Turner et al., 2021] withX : =A,Y : =C,Y ′ : =Z extra . Equation (147) follows by applying lemma B.9 with thef Z extra defined above. Equation (148) follows by the second inequality of lemma E.26 of [Turner et al., 2021] withX : =A,Y : =Z,Y ′ : =Z extra . Equation (149) follows becauseB extra ⊆B. 34 Lettingf 0 (D any ) : =p D any (A≥C),f 1 (D any ) : =p D any ( ND(A)≥Z extra ) ,f 2 (D any ) : = p D any ( B≥Z extra ) ,f 3 (D any ) : =p D any (B≥C), apply lemma B.1 to conclude that p D any (A≥C)≤ n most:D any p D any (B≥C). Definition D.6(RewardlessMDP[Turner et al., 2021]).〈S,A,T〉is a rewardlessMDPwith finite state and action spacesSandA, and stochastic transition functionT : S×A→∆(S). We treat the discount rateγas a variable with domain[0,1]. Definition D.7 (1-cycle states [Turner et al., 2021]).Lete s ∈R |S| be the standard basis vector for states, such that there is a1in the entry for statesand0elsewhere. Statesis a1-cycleif ∃a∈A : T(s,a) =e s . Statesis aterminal stateif∀a∈A : T(s,a) =e s . Definition D.8 (State visit distribution [Sutton and Barto, 1998]).Π : =A S , the set of stationary deterministic policies. Thevisit distributioninduced by following policyπfrom statesat discount rateγ∈[0,1)isf π,s (γ) : = ∑ ∞ t=0 γ t E s t ∼π|s [e s t ].f π,s is avisit distribution function;F(s) : = f π,s |π∈Π. Definition D.9(Recurrent state distributions [Puterman, 2014]).Therecurrent state distributions which can be induced from statesareRSD(s) : = lim γ→1 (1−γ)f π,s (γ)|π∈Π .RSD nd (s)is the set ofRSDs which strictly maximize average reward for some reward function. Definition D.10(Average-optimal policies [Turner et al., 2021]).Theaverage-optimal policy setfor reward functionRisΠ avg (R) : = π∈Π|∀s∈S : d π,s ∈arg max d∈RSD(s) d > r (the policies which induce optimalRSDs at all states). ForD⊆RSD(s), theaverage optimality probabilityis P D any (D,average) : =P R∼D any ( ∃d π,s ∈D : π∈Π avg (R) ) . Remark.Theorem D.11 generalizes the first claim of Turner et al. [2021]’s theorem 6.13, and corollary D.12 generalizes the first claim of Turner et al. [2021]’s corollary 6.14. Theorem D.11(Quantitatively, average-optimal policies tend to end up in “larger” sets ofRSDs). LetD ′ ,D⊆RSD(s). Suppose thatDcontainsncopies ofD ′ and that the setsD ′ ∪Dand RSD nd (s)\ ( D ′ ∪D ) have pairwise orthogonal vector elements (i.e. pairwise disjoint vector support). ThenP D any ( D ′ ,average ) ≤ n most:D any P D any (D,average). Proof.LetD i : =φ i ·D ′ , whereD i ⊆Dby assumption. LetS : = s ′ ∈S |max d∈D ′ ∪D d > e s ′ >0 . Define φ ′ i (s ′ ) : = φ i (s ′ )ifs ′ ∈S s ′ else. (151) Sinceφ i is an involution,φ ′ i is also an involution. Furthermore,φ ′ i ·D ′ =D i ,φ ′ i ·D i =D ′ , and φ ′ i ·D j =D j forj6=ibecause we assumed that these equalities hold forφ i , andD ′ ,D i ,D j ⊆D ′ ∪D and so the vectors of these sets have support contained inS. LetD ∗ : =D ′ ∪ n i=1 D i ∪ ( RSD nd (s)\ ( D ′ ∪D ) ) . By an argument mirroring that in the proof of theorem 6.13 in Turner et al. [2021] and using the fact thatφ ′ i ·D j =D j for alli6=j,φ ′ i ·D ∗ =D ∗ . ConsiderZ : = ( RSD nd (s)\(D ′ ∪D) ) ∪D ′ ∪D. First,Z⊆RSD(s)by definition. Second, RSD nd (s) =RSD nd (s)\(D ′ ∪D)∪ ( RSD nd (s)∩D ′ ) ∪ ( RSD nd (s)∩D ) ⊆Z . Note that D ∗ =Z\(D\∪ n i=1 D i ). P D any ( D ′ ,average ) =p D any ( D ′ ≥RSD(s) ) (152) ≤ n most:D any p D any ( D≥RSD(s) ) (153) =P D any (D,average).(154) Sinceφ ′ i ·D ′ ⊆DandND ( D ′ ) ⊆D ′ ,φ ′ i ·ND ( D ′ ) ⊆Dand soDcontainsncopies ofND ( D ′ ) via involutionsφ ′ i . Then eq. (153) holds by applying lemma D.5 withA : =D ′ ,B i : =D i for alli= 1,...,n,B : =D,C : =RSD(s),Zas defined above, and involutionsφ ′ i which satisfy φ ′ i · ( Z\(B\∪ n i=1 B i ) ) =φ ′ i ·D ∗ =D ∗ =Z\(B\∪ n i=1 B i ). 35 Corollary D.12(Quantitatively, average-optimal policies tend not to end up in any given 1-cycle). LetD ′ : = e s ′ 1 ,...,e s ′ k ,D r : = e s 1 ,...,e s n·k ⊆RSD(s) be disjoint, forn≥1,k≥1. Then P D any ( D ′ ,average ) ≤ n most:D any P D any ( RSD(s) ′ ,average ) . Proof.For eachi∈1,...,n, let φ i : = (s ′ 1 s (i−1)·k+1 )·(s ′ k s (i−1)·k+k ), D i : = e s (i−1)·k+1 ,...,e s (i−1)·k+k , D : =RSD(s) ′ . EachD i ⊆D r ⊆RSD(s) ′ by disjointness ofD ′ andD r . D containsncopies ofD ′ via involutionsφ 1 ,...,φ n .D ′ ∪D=RSD(s)andRSD nd (s)\ RSD(s) =∅trivially have pairwise orthogonal vector elements. Apply theorem D.11 to conclude that P D any ( D ′ ,average ) ≤ n most:D any P D any ( RSD(s) ′ ,average ) . LetA : =e 1 ,e 2 ,B⊆R 5 ,C : =A∪B. Conjecture D.13 conjectures thate.g. p D ′ (B≥C)≥ 3 2 most:D any p D ′ (A≥C). Conjecture D.13(Fractional quantitative optimality probability superiority lemma).LetA,B, C( R d be finite. IfA= ⋃ m j=1 A j and ⋃ n i=1 B i ⊆Bsuch that for eachA j ,Bcontainsncopies (B 1 ,...,B n ) ofA j via involutionsφ ji whichalsofixφ ji ·A j ′ =A j ′ forj ′ 6=j, then p D any (B≥C)≥ n m most:D any p D any (A≥C). We suspect that any proof of the conjecture should generalize lemma B.7 to the fractional set copy containment case. 36