Paper deep dive
Optimal Policies Tend to Seek Power
Alexander Matt Turner, Logan Smith, Rohin Shah, Andrew Critch, Prasad Tadepalli
Models: N/A (theoretical, formal proofs on MDPs)
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 93%
Last extracted: 3/12/2026, 8:11:35 PM
Summary
The paper presents a formal theory of power-seeking in reinforcement learning (RL) agents. It defines 'power' as the ability to achieve a wide range of goals and proves that in many Markov Decision Processes (MDPs), optimal policies are incentivized to seek power due to environmental symmetries, such as the ability to avoid shutdown or maintain future options.
Entities (5)
Relation Signals (3)
Optimal Policy → tendstoexhibit → Power-seeking
confidence 95% · we prove that certain environmental symmetries are sufficient for optimal policies to tend to seek power over the environment.
Environmental Symmetries → causes → Power-seeking
confidence 90% · Section 6 shows that power-seeking tendencies arise not from anthropomorphism, but from certain graphical symmetries present in many MDPs.
Power-seeking → isinstanceof → Instrumental Convergence Thesis
confidence 90% · The claim that power-seeking is convergently instrumental is an instance of the instrumental convergence thesis
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Some researchers speculate that intelligent reinforcement learning (RL) agents would be incentivized to seek resources and power in pursuit of their objectives. Other researchers point out that RL agents need not have human-like power-seeking instincts. To clarify this discussion, we develop the first formal theory of the statistical tendencies of optimal policies. In the context of Markov decision processes, we prove that certain environmental symmetries are sufficient for optimal policies to tend to seek power over the environment. These symmetries exist in many environments in which the agent can be shut down or destroyed. We prove that in these environments, most reward functions make it optimal to seek power by keeping a range of options available and, when maximizing average reward, by navigating towards larger sets of potential terminal states.
Tags
Links
- Source: https://arxiv.org/abs/1912.01683
- Canonical: https://arxiv.org/abs/1912.01683
Trouble viewing inline? Open PDF directly →
Full Text
124,147 characters extracted from source content.
Expand or collapse full text
Optimal Policies Tend To Seek Power Alexander Matt Turner Oregon State University turneale@oregonstate.edu Logan Smith Mississippi State University ls1254@msstate.edu Rohin Shah UC Berkeley rohinmshah@berkeley.edu Andrew Critch UC Berkeley critch@berkeley.edu Prasad Tadepalli Oregon State University tadepall@eecs.oregonstate.edu Abstract Some researchers speculate that intelligent reinforcement learning (RL) agents would be incentivized to seek resources and power in pursuit of the objectives we specify for them. Other researchers point out thatRLagents need not have human-like power-seeking instincts. To clarify this discussion, we develop the first formal theory of the statistical tendencies of optimal policies. In the context of Markov decision processes (MDPs), we prove that certain environmental symme- tries are sufficient for optimal policies to tend to seek power over the environment. These symmetries exist in many environments in which the agent can be shut down or destroyed. We prove that in these environments, most reward functions make it optimal to seek power by keeping a range of options available and, when maximizing average reward, by navigating towards larger sets of potential terminal states. 1 Introduction Omohundro [2008], Bostrom [2014], Russell [2019] hypothesize that highly intelligent agents tend to seek power in pursuit of their goals. Such power-seeking agents might gain power over humans. Marvin Minsky imagined that an agent tasked with proving the Riemann hypothesis might rationally turn the planet—along with everyone on it—into computational resources [Russell and Norvig, 2009]. However, another possibility is that such concerns simply arise from the anthropomorphization of AI systems [LeCun and Zador, 2019, Various, 2019, Pinker and Russell, 2020, Mitchell, 2021]. We clarify this discussion by grounding the claim that highly intelligent agents will tend to seek power. In section 4, we identify optimal policies as a reasonable formalization of “highly intelligent agents.” 1 Optimal policies “tend to” take an action when the action is optimal for most reward functions. We expect future work to translate our theory from optimal policies to learned, real-world policies. Section 5 defines “power” as the ability to achieve a wide range of goals. For example, “money is power,” and money is instrumentally useful for many goals. Conversely, it’s harder to pursue most goals when physically restrained, and so a physically restrained person has little power. An action “seeks power” if it leads to states where the agent has higher power. 1 This paper assumes that reward functions reasonably describe a trained agent’s goals. Sometimes this is roughly true (e.g. chess with a sparse victory reward signal) and sometimes it is not true. 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. 35th Conference on Neural Information Processing Systems (NeurIPS 2021). arXiv:1912.01683v10 [cs.AI] 28 Jan 2023 We make no claims about when large-scale AI power-seeking behavior could become plausible. Instead, we consider the theoretical consequences of optimal action inMDPs. Section 6 shows that power-seeking tendencies arise not from anthropomorphism, but from certain graphical symmetries present in manyMDPs. These symmetries automatically occur in many environments where the agent can be shut down or destroyed, yielding broad applicability of our main result (theorem 6.13). 2 Related work An action isinstrumental to an objectivewhen it helps achieve that objective. Some actions are instrumental to a range of objectives, making themconvergently instrumental. The claim that power-seeking is convergently instrumental is an instance of theinstrumental convergence thesis: Several instrumental values can be identified which are convergent in the sense that their attainment would increase the chances of the agent’s goal being realized for a wide range of final goals and a wide range of situations, implying that these instrumental values are likely to be pursued by a broad spectrum of situated intelligent agents [Bostrom, 2012]. For example, in Atari games, avoiding (virtual) death is instrumental for both completing the game and for optimizing curiosity [Burda et al., 2019]. Many AI alignment researchers hypothesize that most advanced AI agents will have concerning instrumental incentives, such as resisting deactiva- tion [Soares et al., 2015, Milli et al., 2017, Hadfield-Menell et al., 2017, Carey, 2018] and acquiring resources [Benson-Tilsen and Soares, 2016]. We formalize power as the ability to achieve a wide variety of goals. Appendix A demonstrates that our formalization returns intuitive verdicts in situations where information-theoretic empowerment does not [Salge et al., 2014]. Some of our results relate the formal power of states to the structure of the environment. Foster and Dayan [2002], Drummond [1998], Sutton et al. [2011], Schaul et al. [2015] note that value functions encode important information about the environment, as they capture the agent’s ability to achieve different goals. Turner et al. [2020] speculate that a state’s optimal value correlates strongly across reward functions. In particular, Schaul et al. [2015] learn regularities across value functions, suggesting that some states are valuable for many different reward functions (i.e. powerful). Menache et al. [2002] identify and navigate towards convergently instrumental bottleneck states. We are not the first to study convergence of behavior, form, or function. In economics, turnpike theory studies how certain paths of accumulation tend to be optimal [McKenzie, 1976]. In biology, convergent evolution occurs when similar features (e.g. flight) independently evolve in different time periods [Reece and Campbell, 2011]. Lastly, computer vision networks reliably learne.g. edge detectors, implying that these features are useful for a range of tasks [Olah et al., 2020]. 3 State visit distribution functions quantify the agent’s available options F ∅ ` / left ` ↙ ` ↖ r . right r ↘ r ↗ Figure 1:` ↙ is a 1-cycle, and∅is a terminal state. Arrows represent deterministic transitions induced by taking some actiona∈ A. Since therightsubgraph contains a copy of theleftsubgraph, proposition 6.9 will prove that more reward functions have optimal policies which gorightthan which goleftat state?, and that such policies seek power—both intuitively, and in a reasonable formal sense. We clarify the power-seeking discussion by proving what optimal policies usually look like in a given environment. We illustrate our results with a simple case study, before explaining how to reason 2 about a wide range ofMDPs. Appendix D.1 listsMDPtheory contributions of independent interest, appendix D lists definitions and theorems, and appendix E contains the proofs. Definition 3.1(RewardlessMDP).〈S,A,T〉is a rewardlessMDPwith finite state and action spaces SandA, and stochastic transition functionT : S ×A →∆(S). We treat the discount rateγas a variable with domain[0,1]. Definition 3.2 (1-cycle states).Lete s ∈R |S| be the standard basis vector for states, such that there is a 1 in the entry for statesand 0 elsewhere. Statesis a1-cycleif∃a∈A : T(s,a) =e s . Statesis aterminal stateif∀a∈A : T(s,a) =e s . Our theorems apply to stochastic environments, but we present a deterministic case study for clarity. The environment of fig. 1 is small, but its structure is rich. For example, the agent has more “options” at?than at the terminal state∅. Formally,?has morevisit distribution functionsthan∅does. Definition 3.3 (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 |π∈Π. In fig. 1, starting from` ↙ , the agent can stay at` ↙ or alternate between` ↙ and` ↖ , and so F(` ↙ ) = 1 1−γ e ` ↙ , 1 1−γ 2 (e ` ↙ +γe ` ↖ ) . In contrast, at∅, all policiesπmap to visit distribution function 1 1−γ e ∅ . Before moving on, we introduce two important concepts used in our main results. First, we sometimes restrict our attention to visit distributions which take certain actions (fig. 2). F r . right r ↘ r ↗ Figure 2: The subgraph corresponding toF(?|π(?) =right). Some trajectories cannot be strictly optimal for any reward function, and so our results can ignore them. Gray dotted actions are only taken by the policies of dominatedf π ∈F(?) nd (?). Definition 3.4 (Fsingle-state restriction).Considering only visit distribution functions induced by policies taking actionaat states ′ ,F(s|π(s ′ ) =a) : = f∈F(s)|∃π∈Π : π(s ′ ) =a,f π,s =f . Second, somef∈ F(s)are “unimportant.” Consider an agent optimizing reward functione r ↘ (1 reward when atr ↘ , 0 otherwise) ate.g.γ= 1 2 . Its optimal policies navigate tor ↘ and stay there. Similarly, for reward functione r ↗ , optimal policies navigate tor ↗ and stay there. However, for no reward function is it uniquely optimal to alternate betweenr ↗ andr ↘ . Onlydominatedvisit distribution functions alternate betweenr ↗ andr ↘ (definition 3.6). Definition 3.5 (Value function).Letπ∈Π. For any reward functionR∈R S over the state space, theon-policy valueat statesand discount rateγ∈[0,1)isV π R (s,γ) : =f π,s (γ) > r, where r∈R |S| isRexpressed as a column vector (one entry per state). Theoptimal valueisV ∗ R (s,γ) : = max π∈Π V π R (s,γ). Definition 3.6(Non-domination). F nd (s) : =f π ∈F(s)|∃r∈R |S| ,γ∈(0,1) : f π (γ) > r>max f π ′ ∈F(s)\f π f π ′ (γ) > r.(1) For any reward functionRand discount rateγ,f π ∈ F(s)is (weakly) dominated byf π ′ ∈ F(s) ifV π R (s,γ)≤V π ′ R (s,γ).f π ∈ F nd (s)isnon-dominatedif there existRandγat whichf π is not dominated by any otherf π ′ . 3 4 Some actions have a greater probability of being optimal We claim that optimal policies “tend” to take certain actions in certain situations. We first consider the probability that certain actions are optimal. Reconsider the reward functione r ↘ , optimized atγ= 1 2 . Starting from?, the optimal trajectory goes righttor . tor ↘ , where the agent remains. Therightaction is optimal at?under these incentives. Optimal policy sets capture the behavior incentivized by a reward function and a discount rate. Definition 4.1(Optimal policy set function).Π ∗ (R,γ)is the optimal policy set for reward function Ratγ∈(0,1). AllRhave at least one optimal policyπ∈Π[Puterman, 2014].Π ∗ (R,0) : = lim γ→0 Π ∗ (R,γ)andΠ ∗ (R,1) : = lim γ→1 Π ∗ (R,γ)exist by lemma E.35 (taking the limits with respect to the discrete topology over policy sets). We may be unsure which reward function an agent will optimize. We may expect to deploy a system in a known environment, without knowing the exact form ofe.g. the reward shaping [Ng et al., 1999] or intrinsic motivation [Pathak et al., 2017]. Alternatively, one might attempt to reason about future RLagents, whose details are unknown. Our power-seeking results do not hinge on such uncertainty, as they also apply to degenerate distributions (i.e. we know what reward function will be optimized). Definition 4.2(Reward function distributions).Different results make different distributional as- sumptions. Results withD any ∈D any : = ∆(R |S| ) hold for any probability distribution overR |S| . D bound is the set of bounded-support probability distributionsD bound . For any distributionXoverR, D X-IID : =X |S| . For example, whenX u : =unif(0,1),D X u -IID is the maximum-entropy distribution. D s is the degenerate distribution on the state indicator reward functione s , which assigns 1 reward to sand 0 elsewhere. WithD any representing our prior beliefs about the agent’s reward function, what behavior should we expect from its optimal policies? Perhaps we want to reason about the probability that it’s optimal to go from?to∅, or to go tor . and then stay atr ↗ . In this case, we quantify the optimality probability ofF : =e ? + γ 1−γ e ∅ ,e ? +γe r . + γ 2 1−γ e r ↗ . Definition 4.3 (Visit distribution optimality probability).LetF⊆F(s),γ∈[0,1].P D any (F,γ) : = P R∼D any ( ∃f π ∈F : π∈Π ∗ (R,γ) ) . Alternatively, perhaps we’re interested in the probability thatrightis optimal at?. Definition 4.4(Action optimality probability).At discount rateγand at states, theoptimality probability of actionaisP D any (s,a,γ) : =P R∼D any ( ∃π ∗ ∈Π ∗ (R,γ) : π ∗ (s) =a ) . Optimality probability may seem hard to reason about. It’s hard enough to compute an optimal policy for a single reward function, let alone for uncountably many! But consider anyD X-IID distributing reward independently and identically across states. Whenγ= 0, optimal policies greedily maximize next-state reward. At?, identically distributed reward means` / andr . have an equal probability of having maximal next-state reward. Therefore,P D X-IID (?,left,0) =P D X-IID (?,right,0). This is not a proof, but such statements are provable. WithD ` / being the degenerate distribution on reward functione ` / ,P D ` / ( ?,left, 1 2 ) = 1>0 = P D ` / ( ?,right, 1 2 ) . Similarly,P D r . ( ?,left, 1 2 ) = 0<1 =P D r . ( ?,right, 1 2 ) . Therefore, “what do optimal policies ‘tend’ to look like?” seems to depend on one’s prior beliefs. But in fig. 1, we claimed thatleftis optimal for fewer reward functions thanrightis. The claim is meaningful and true, but we will return to it in section 6. 5 Some states give the agent more control over the future The agent has more options at` ↙ than at the inescapable terminal state∅. Furthermore, sincer ↗ has a loop, the agent has more options atr ↘ than at` ↙ . A glance at fig. 3 leads us to intuit thatr ↘ affords the agentmore powerthan∅. What is power? Philosophers have many answers. One prominent answer is thedispositionalview: Power is the ability to achieve a range of goals [Sattarov, 2019]. In anMDP, the optimal value 4 functionV ∗ R (s,γ)captures the agent’s ability to “achieve the goal”R. Therefore,averageoptimal value captures the agent’s ability to achieve a range of goalsD bound . 2 Definition 5.1(Average optimal value).Theaverage optimal value 3 at statesand discount rate γ∈(0,1)isV ∗ D bound (s,γ) : =E R∼D bound [ V ∗ R (s,γ) ] =E r∼D bound [ max f∈F(s) f(γ) > r ] . F ∅ ` / left ` ↙ ` ↖ r . right r ↘ r ↗ Figure 3: Intuitively, stater ↘ affords the agent more power than state∅. OurPOWERformal- ism captures that intuition by computing a function of the agent’s average optimal value across a range of reward functions. ForX u : =unif(0,1),V ∗ D X u -IID (∅,γ) = 1 2 1 1−γ ,V ∗ D X u -IID (` ↙ ,γ) = 1 2 + γ 1−γ 2 ( 2 3 + 1 2 γ) , andV ∗ D X u -IID (r ↘ ,γ) = 1 2 + γ 1−γ 2 3 . 1 2 and 2 3 are the expected maxima of one and two draws from the uniform distribution, respectively. For allγ∈(0,1),V ∗ D X u -IID (∅,γ)< V ∗ D X u -IID (` ↙ ,γ)< V ∗ D X u -IID (r ↘ ,γ) .POWER D X u -IID (∅,γ) = 1 2 ,POWER D X u -IID (` ↙ ,γ) = 1 1+γ ( 2 3 + 1 2 γ), andPOWER D X u -IID (r ↘ ,γ) = 2 3 . ThePOWERof` ↙ reflects the fact that when greater reward is assigned to` ↖ , the agent only visits` ↖ every other time step. Figure 3 shows the pleasing result that for the max-entropy distribution,r ↘ has greater average optimal value than∅. However, average optimal value has a few problems as a measure of power. The agent is rewarded for its initial presence at states(over which it has no control), and be- cause ∥ ∥ f(γ) ∥ ∥ 1 = 1 1−γ (proposition E.3) diverges asγ→1,lim γ→1 V ∗ D bound (s,γ) tends to diverge. Definition 5.2 fixes these issues in order to better measure the agent’s control over the future. Definition 5.2(POWER).Letγ∈(0,1). POWER D bound (s,γ) : =E r∼D bound [ max f∈F(s) 1−γ γ ( f(γ)−e s ) > r ] = 1−γ γ E R∼D bound [ V ∗ R (s,γ)−R(s) ] . (2) POWERhas nice formal properties. Lemma 5.3(Continuity of POWER).POWER D bound (s,γ)is Lipschitz continuous onγ∈[0,1]. Proposition 5.4(MaximalPOWER).POWER D bound (s,γ)≤E R∼D bound [ max s∈S R(s) ] , with equality ifscan deterministically reach all states in one step and all states are 1-cycles. Proposition 5.5(POWERis smooth across reversible dynamics).LetD bound be bounded[b,c]. Sup- posesands ′ can both reach each other in one step with probability 1. ∣ ∣ POWER D bound (s,γ)−POWER D bound ( s ′ ,γ ) ∣ ∣ ≤(c−b)(1−γ).(3) We consider power-seeking to be relative. Intuitively, “live and keep some options open” seeks more power than “die and keep no options open.” Similarly, “maximize open options” seeks more power than “don’t maximize open options.” Definition 5.6(POWER-seeking actions).At statesand discount rateγ∈[0,1], actionaseeks more POWER D bound thana ′ whenE s a ∼T(s,a) [ POWER D bound (s a ,γ) ] ≥E s a ′ ∼T(s,a ′ ) [ POWER D bound (s a ′ ,γ) ] . POWER is sensitive to choice of distribution.D ` ↙ gives maximalPOWER D ` ↙ to` ↙ .D r ↘ assigns maximalPOWER D r ↘ tor ↘ .D ∅ even gives maximalPOWER D ∅ to∅! In what sense does∅have “less POWER” thanr ↘ , and in what sense doesright“tend to seek POWER” compared toleft? 2 D bound ’s bounded support ensures thatE R∼D bound [ V ∗ R (s,γ) ] is well-defined. 3 Appendix C relaxes the optimality assumption. 5 6 Certain environmental symmetries produce power-seeking tendencies Proposition 6.6 proves that for allγ∈[0,1]and formost distributionsD,POWER D (` ↙ ,γ)≤ POWER D (r ↘ ,γ). But first, we explore why this must be true. F(` ↙ ) = 1 1−γ e ` ↙ , 1 1−γ 2 (e ` ↙ +γe ` ↖ )andF(r ↘ ) = 1 1−γ e r ↘ , 1 1−γ 2 (e r ↘ +γe r ↗ ),e r ↘ + γ 1−γ e r ↗ . These two sets look awfully similar.F(` ↙ )is a “subset” ofF(r ↘ ), only with “different states.” Figure 4 demonstrates a state permutationφwhichembedsF(` ↙ )intoF(r ↘ ). F ∅ ` / left ` ↙ ` ↖ r . right r ↘ r ↗ Involutionφ Figure 4: Intuitively, the agent can do more starting fromr ↘ than from` ↙ . By definition 6.1,F(r ↘ ) contains a copy ofF(` ↙ ): φ·F(` ↙ ) : = 1 1−γ P φ e ` ↙ , 1 1−γ 2 P φ (e ` ↙ +γe ` ↖ )= 1 1−γ e r ↘ , 1 1−γ 2 (e r ↘ +γe r ↗ )(F(r ↘ ). Definition 6.1 (Similarity of vector sets).Consider state permutationφ∈S |S| inducing an|S|×|S| permutation matrixP φ in row representation:(P φ ) ij = 1ifi=φ(j)and0otherwise. ForX⊆R |S| , φ·X : = P φ x|x∈X .X ′ ⊆R |S| is similar toXwhen∃φ : φ·X ′ =X.φis aninvolutionif φ=φ −1 (it either transposes states, or fixes them in place).Xcontains a copy ofX ′ whenX ′ is similar to a subset ofXvia an involutionφ. Definition 6.2(Similarity of vector function sets).LetI⊆R. IfF,F ′ are sets of functionsI7→R |S| , Fis (pointwise) similar toF ′ when∃φ : ∀γ∈I : P φ f(γ)|f∈F=f ′ (γ)|f ′ ∈F ′ . Consider a reward functionR ′ assigning 1 reward to` ↙ and` ↖ and 0 elsewhere.R ′ assigns more optimal value to` ↙ than tor ↘ :V ∗ R ′ (` ↙ ,γ) = 1 1−γ >0 =V ∗ R ′ (r ↘ ,γ) . Consideringφfrom fig. 4, φ·R ′ assigns 1 reward tor ↘ andr ↗ and 0 elsewhere. Therefore,φ·R ′ assigns more optimal value tor ↘ than to` ↙ :V ∗ φ·R ′ (` ↙ ,γ) = 0< 1 1−γ =V ∗ φ·R ′ (r ↘ ,γ). Remarkably, thisφhas the property that foranyRwhich assigns` ↙ greater optimal value thanr ↘ (i.e.V ∗ R (` ↙ ,γ)> V ∗ R (r ↘ ,γ)), the opposite holds for the permutedφ·R:V ∗ φ·R (` ↙ ,γ)< V ∗ φ·R (r ↘ ,γ). We can permute reward functions, but we can also permute reward function distributions. Permuted distributions simply permute which states get which rewards. x y D D ′ φ swap Figure 5: A permutation of a reward function swaps which states get which rewards. We will show that in certain situations, for any reward functionR, power-seeking is optimal for most of the permutations ofR. The orbit of a reward function is the set of its permutations. We can also consider the orbit of a distribution over reward functions. This figure shows the probability density plots of the Gaussian distributionsDandD ′ overR 2 . The symmetric groupS 2 contains the identity permutation φ id and the reflection permutationφ swap (switching theyandxvalues). The orbit ofDconsists of φ id ·D=Dandφ swap ·D=D ′ . 6 Definition 6.3(Pushforward distribution of a permutation).Letφ∈S |S| .φ·D any is the pushforward distribution induced by applying the random vectorf(r) : =P φ rtoD any . Definition 6.4 (Orbit of a probability distribution).TheorbitofD any under the symmetric group S |S| isS |S| ·D any : =φ·D any |φ∈S |S| . For example, the orbit of a degenerate state indicator distributionD s isS |S| ·D s =D s ′ |s ′ ∈S, and fig. 5 shows the orbit of a 2D Gaussian distribution. Consider again the involutionφof fig. 4. For everyD bound for which` ↙ has morePOWER D bound thanr ↘ ,` ↙ has lessPOWER φ·D bound thanr ↘ . This fact is not obvious—it is shown by the proof of lemma E.24. ImagineD bound ’s orbit elements “voting” whether` ↙ orr ↘ has strictly morePOWER. Proposition 6.6 will show thatr ↘ can’t lose the “vote” for the orbit ofanybounded reward function distribution. Definition 6.5 formalizes this “voting” notion. 4 Definition 6.5(Inequalities which hold for most probability distributions).Letf 1 ,f 2 : ∆(R |S| )→R be functions from reward function distributions to real numbers and letD⊆∆(R |S| )be closed under permutation. We writef 1 (D)≥ most:D f 2 (D) 5 when, forallD ∈D, the following cardinality inequality holds: ∣ ∣ ∣ D ′ ∈S |S| ·D |f 1 (D ′ )> f 2 (D ′ ) ∣ ∣ ∣ ≥ ∣ ∣ ∣ D ′ ∈S |S| ·D |f 1 (D ′ )< f 2 (D ′ ) ∣ ∣ ∣ .(4) Proposition 6.6 (States with “more options” have morePOWER).IfF(s)contains a copy ofF nd (s ′ ) viaφ, then∀γ∈[0,1] : POWER D bound (s,γ)≥ most POWER D bound (s ′ ,γ). IfF nd (s)\φ·F nd (s ′ )is non-empty, then for allγ∈(0,1), the converse≤ most statement does not hold. Proposition 6.6 proves that for allγ∈[0,1],POWER D bound (r ↘ ,γ)≥ most POWER D bound (` ↙ ,γ)via s ′ : =` ↙ ,s : =r ↘ , and the involutionφshown in fig. 4. In fact, because( 1 1−γ e r ↗ )∈F nd (r ↘ )\φ· F nd (` ↙ ),r ↘ has “strictly more options” and therefore fulfills proposition 6.6’s stronger condition. Proposition 6.6 is shown using the fact thatφinjectively mapsDunder whichr ↘ has lessPOWER D , to distributionsφ·Dwhich agree with the intuition thatr ↘ offers more control. Therefore, at least half of each orbit must agree, andr ↘ never “loses the POWERvote” against` ↙ . 6 6.1 Keeping options open tends to be POWER-seeking and tends to be optimal Certain symmetries in theMDPstructure ensure that, compared toleft, goingrighttends to be optimal and to bePOWER-seeking. Intuitively, by goingright, the agent has “strictly more choices.” Proposition 6.9 will formalize this tendency. Definition 6.7(Equivalent actions).Actionsa 1 anda 2 areequivalent at states(writtena 1 ≡ s a 2 ) if they induce the same transition probabilities:T(s,a 1 ) =T(s,a 2 ). The agent can reach states inr . ,r ↗ ,r ↘ by taking actions equivalent torightat state?. Definition 6.8 (States reachable after taking an action).REACH(s,a)is the set of states reachable with positive probability after taking the actionain states. Proposition 6.9(Keeping options open tends to be POWER-seeking and tends to be optimal). SupposeF a : =F(s|π(s) =a)contains a copy ofF a ′ : =F(s|π(s) =a ′ )viaφ. 1. Ifs6∈REACH ( s,a ′ ) , then∀γ∈[0,1] : E s a ∼T(s,a) [ POWER D bound (s a ,γ) ] ≥ most:D bound E s a ′ ∼T(s,a ′ ) [ POWER D bound (s a ′ ,γ) ] . 4 The voting analogy and the “most” descriptor imply that we have endowed each orbit with the counting measure. However,a priori, we might expect that some orbit elements are more empirically likely to be specified than other orbit elements. See section 7 for more on this point. 5 We writef 1 (D)≥ most f 2 (D)whenDis clear from context. 6 Proposition 6.6 also proves that in general,∅has lessPOWERthan` ↙ andr ↘ . However, this does not prove that most distributionsDsatisfy the joint inequalityPOWER D (∅,γ)≤POWER D (` ↙ ,γ)≤POWER D (r ↘ ,γ). This only proves that these inequalities hold pairwise for mostD. The orbit elementsDwhich agree that∅has less POWER D than` ↙ need not be the same elementsD ′ which agree that` ↙ has less POWER D ′ thanr ↘ . 7 2.Ifscan only reach the states ofREACH ( s,a ′ ) ∪REACH(s,a) by taking actions equivalent toa ′ oraat states, then∀γ∈[0,1] : P D any (s,a,γ)≥ most:D any P D any ( s,a ′ ,γ ) . IfF nd (s)∩ ( F a \φ·F a ′ ) is non-empty, then∀γ∈(0,1), the converse≤ most statements do not hold. F ∅ ` / left ` ↙ ` ↖ r . right r ↘ r ↗ Involutionφ Figure 6: Goingrightis optimal for most reward functions. This is because wheneverRmakes leftstrictly optimal overright, its permutationφ·Rmakesrightstrictly optimal overleftby switching which states get which rewards. We check the conditions of proposition 6.9.s : =?,a ′ : =left,a : =right. Figure 6 shows that?6∈REACH(?,left)and that?can only reach` / ,` ↖ ,` ↙ ∪r . ,r ↗ ,r ↘ when the agent immediately takes actions equivalent toleftorright.F(?|π(?) =right)contains a copy of F(?|π(?) =left)viaφ. Furthermore,F nd (?)∩e ? +γe r . +γ 2 e r ↘ + γ 3 1−γ e r ↗ ,e ? +γe r . + γ 2 1−γ e r ↗ =e ? +γe r . + γ 2 1−γ e r ↗ is non-empty, and so all conditions are met. For anyγ∈[0,1]andDsuch thatP D (?,left,γ)>P D (?,right,γ), environmental symmetry ensures thatP φ·D (?,left,γ)<P φ·D (?,right,γ). A similar statement holds for POWER. 6.2 Whenγ= 1, optimal policies tend to navigate towards “larger” sets of cycles Proposition 6.6 and proposition 6.9 are powerful because they apply to allγ∈[0,1], but they can only be applied given hard-to-satisfy environmental symmetries. In contrast, proposition 6.12 and theorem 6.13 apply to many structured environments common toRL. Starting from?, consider the cycles which the agent can reach. Recurrent state distributions (RSDs) generalize deterministic graphical cycles to potentially stochastic environments.RSDs simply record how often the agent tends to visit a state in the limit of infinitely many time steps. Definition 6.10(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. As suggested by fig. 3,RSD(?) =e ` ↙ , 1 2 (e ` ↙ +e ` ↖ ),e ∅ ,e r ↗ , 1 2 (e r ↗ +e r ↘ ),e r ↘ . As dis- cussed in section 3, 1 2 (e r ↗ +e r ↘ )is dominated: Alternating betweenr ↗ andr ↘ is never strictly better than choosing one or the other. A reward function’s optimal policies can vary with the discount rate. Whenγ= 1, optimal policies ignore transient reward becauseaveragereward is the dominant consideration. Definition 6.11(Average-optimal policies).Theaverage-optimal policy setfor reward functionRis Π avg (R) : = π∈Π|∀s∈S : d π,s ∈arg max d∈RSD(s) d > r (the policies which induce optimal RSDs at all states). ForD⊆RSD(s), theaverage optimality probabilityisP D any (D,average) : = P R∼D any ( ∃d π,s ∈D : π∈Π avg (R) ) . Average-optimal policies maximize average reward. Average reward is governed byRSDaccess. For example,r ↘ has “more”RSDs than∅; therefore,r ↘ usually has greater POWERwhenγ= 1. Proposition 6.12(Whenγ= 1,RSDs controlPOWER).IfRSD(s)contains a copy ofRSD nd ( s ′ ) viaφ, thenPOWER D bound (s,1)≥ most POWER D bound ( s ′ ,1 ) . IfRSD nd (s)\φ·RSD nd (s ′ )is non-empty, then the converse≤ most statement does not hold. 8 We check that both conditions of proposition 6.12 are satisfied whens ′ : =∅,s : =r ↘ , and the involutionφswaps∅andr ↘ . Formally,φ·RSD nd (∅) =φ·e ∅ =e r ↘ (e r ↘ ,e r ↗ = RSD nd (r ↘ )⊆[r ↘ ]. The conditions are satisfied. Informally, states with moreRSDs generally have morePOWERatγ= 1, no matter their transient dynamics. Furthermore, average-optimal policies are more likely to end up in larger sets ofRSDs than in smaller ones. Thus, average-optimal policies tend to navigate towards parts of the state space which contain moreRSDs. F ∅ ` / left ` ↙ ` ↖ r . right r ↘ r ↗ Figure 7: The cycles inRSD(?). Most reward functions make it average-optimal to avoid∅, because ∅is only a single inescapable terminal state, while other parts of the state space offer more 1-cycles. Theorem 6.13(Average-optimal policies tend to end up in “larger” sets ofRSDs).LetD,D ′ ⊆ RSD(s) . Suppose thatDcontains a copy ofD ′ viaφ, and that the setsD∪D ′ andRSD nd (s)\ ( D ′ ∪D ) have pairwise orthogonal vector elements (i.e. pairwise disjoint vector support). Then P D any (D,average)≥ most P D any ( D ′ ,average ) . IfRSD nd (s)∩ ( D\φ·D ′ ) is non-empty, the converse ≤ most statement does not hold. Corollary 6.14 (Average-optimal policies tend not to end up in any given 1-cycle).Sup- posee s x ,e s ′ ∈RSD(s) are distinct.ThenP D any ( RSD(s)\e s x ,average ) ≥ most P D any ( e s x ,average ) . If there is a thirde s ′ ∈RSD(s), the converse≤ most statement does not hold. Figure 7 illustrates thate ∅ ,e r ↘ ,e r ↗ ∈RSD(?).Thus,both conclusions of corollary 6.14 hold:P D any ( RSD(?)\e ∅ ,average ) ≥ most P D any ( e ∅ ,average ) and P D any ( RSD(?)\e ∅ ,average ) 6≤ most P D any ( e ∅ ,average ) . In other words, average-optimal policies tend to end up inRSDs besides∅. Since∅is a terminal state, it cannot reach otherRSDs. Since average-optimal policies tend to end up in otherRSDs, average-optimal policies tend to avoid ∅. This section’s results prove theγ= 1case. Lemma 5.3 shows thatPOWERis continuous atγ= 1. Therefore, if an action is strictlyPOWER D -seeking whenγ= 1, it is strictlyPOWER D -seeking at discount rates sufficiently close to 1. Future work may connect average optimality probability to optimality probability atγ≈1. Lastly, our key results apply to all degenerate reward function distributions. Therefore, these results apply not just to distributions over reward functions, but to individual reward functions. 6.3 How to reason about other environments Consider an embodied navigation task through a room with a vase. Proposition 6.9 suggests that optimal policies tend to avoid immediately breaking the vase, since doing so would strictly decrease available options. Theorem 6.13 dictates where average-optimal agents tend to end up, but not what actions they tend to take in order to reach theirRSDs. Therefore, care is needed. In appendix B, fig. 10 demonstrates an environment in which seekingPOWERis a detour for most reward functions (since optimality probability measures “median” optimal value, whilePOWERis a function of mean optimal value). However, suppose the agent confronts a fork in the road: Actionsaanda ′ lead to two disjoint sets of RSDsD a andD a ′ , such thatD a contains a copy ofD a ′ . Theorem 6.13 shows thatawill tend to be average-optimal overa ′ , and proposition 6.12 shows thatawill tend to bePOWER-seeking compared toa ′ . Such forks seem reasonably common in environments with irreversible actions. 9 Theorem 6.13 applies to many structuredRLenvironments, which tend to be spatially regular and to factorize along several dimensions. Therefore, different sets ofRSDs will be similar, requiring only modification of factor values. For example, if an embodied agent can deterministically navigate a set of three similar rooms (spatial regularity), then the agent’s position factors via room number× position in room. Therefore, theRSDs can be divided into three similar subsets, depending on the agent’s room number. Corollary 6.14 dictates where average-optimal agents tend to end up, but not how they get there. Corollary 6.14 says that such agents tend not tostayin any given 1-cycle. It does not say that such agents will avoidenteringsuch states. For example, in an embodied navigation task, a robot may enter a 1-cycle by idling in the center of a room. Corollary 6.14 implies that average-optimal robots tend not to idle in that particular spot, but not that they tend to avoid that spot entirely. However, average-optimal robotsdotend to avoid getting shut down. The agent’s taskMDPoften represents agent shutdown with terminal states. A terminal state is, by definition 3.2, unable to access other 1-cycles. Since corollary 6.14 shows that average-optimal agents tend to end up in other 1-cycles, average-optimal policies must tend to completely avoid the terminal state. Therefore, we conclude that in many such situations, average-optimal policies tend to avoid shutdown. Intuitively, survival is power-seeking relative to dying, and so shutdown-avoidance is power-seeking behavior. In fig. 8, the player dies by goingleft, but can reach thousands ofRSDs by heading in other directions. Even if some average-optimal policies goleftin order to reach fig. 8’s “game over” terminal state, all otherRSDs cannot be reached by goingleft. There are many 1-cycles besides the immediate terminal state. Therefore, corollary 6.14 proves that average-optimal policies tend to not goleftin this situation. Average-optimal policies tend to avoid immediately dying in Pac-Man, even though most reward functions do not resemble Pac-Man’s original score function. 7 Discussion Reconsider the case of a hypothetical intelligent real-world agent which optimizes average reward for some objective. Suppose the designers initially have control over the agent. If the agent began to misbehave, perhaps they could just deactivate it. Unfortunately, our results suggest that this strategy might not work. Average-optimal agents would generally stop us from deactivating them, if physically possible. Extrapolating from our results, we conjecture that whenγ≈1, optimal policies tend to seek power by accumulating resources—to the detriment of any other agents in the environment. Future work.Real-world training procedures often do not satisfyRLconvergence theorems. Thus, learned policies are rarely optimal. We expect this point to seriously constrain the applicability of this theory. Emphatically, optimal policies are often qualitatively divorced from the actual policies learned by reinforcement learning. For example, the mathematics of policy gradient algorithms is not to update policies so as to maximize reward. Instead, the rewards provide gradients to the parameterization of the policy [Turner, 2022]. On that view, reward functions are simply sources of gradient updates which designers use in order to control generalization behavior. Most real-world tasks are partially observable. Although our results only apply to optimal policies in finiteMDPs, we expect the key conclusions to generalize. Furthermore, irregular stochasticity in environmental dynamics can make it hard to satisfy theorem 6.13’s similarity requirement. We look forward to future work which addresses partially observable environments, suboptimal policies, or “almost similar”RSDsets. Past work shows that it would be bad for an agent to disempower humans in its environment. In a two-player agent / human game, minimizing the human’s information-theoretic empowerment [Salge · left right Figure 8: Consider the dynamics of the Pac-Man video game. Ghosts kill the player, at which point we consider the player to enter a “game over” terminal state which shows the final configuration. This rewardlessMDPhas Pac-Man’s dynamics, butnotits usual score function. Fixing the dynamics, as the reward function varies,righttends to be average-optimal overleft. Roughly, this is because the agent can do more by staying alive. 10 et al., 2014] produces adversarial agent behavior [Guckelsberger et al., 2018]. In contrast, maximizing human empowerment produces helpful agent behavior [Salge and Polani, 2017, Guckelsberger et al., 2016, Du et al., 2020]. We do not yet formally understand if, when, or whyPOWER-seeking policies tend to disempower other agents in the environment. More complex environments probably have more pronounced power-seeking incentives. Intuitively, there are often many ways for power-seeking to be optimal, and relatively few ways for power-seeking not to be optimal. For example, suppose that in some environment, theorem 6.13 holds for one million involutionsφ. Does this guarantee more pronounced incentives than if theorem 6.13 only held for one involution? We proved sufficient conditions for when reward functions tend to have optimal policies which seek power. In the absence of prior information, one should expect that an arbitrary reward function has optimal policies which exhibit power-seeking behavior under these conditions. However, we have prior information: AI designers usually try to specify a good reward function. Even so, it may be hard to specify orbit elements which do not—at optimum—incentivize bad power-seeking. Societal impact.We believe that this paper builds toward a rigorous understanding of the risks presented by AI power-seeking incentives. Understanding these risks is the first step in addressing them. However, basic theoretical work can have many consequences. For example, this theory could somehow help future researchers build power-seeking agents which disempower humans. We believe that the benefit of understanding outweighs the potential societal harm. Conclusion.We developed the first formal theory of the statistical tendencies of optimal policies in reinforcement learning. In the context ofMDPs, we proved sufficient conditions under which optimal policies tend to seek power, both formally (by takingPOWER-seeking actions) and intuitively (by taking actions which keep the agent’s options open). Many real-world environments have symmetries which produce power-seeking incentives. In particular, optimal policies tend to seek power when the agent can be shut down or destroyed. Seeking control over the environment will often involve resisting shutdown, and perhaps monopolizing resources. We caution that many real-world tasks are partially observable and that learned policies are rarely optimal. Our results do not mathematicallyprovethat hypothetical superintelligent AI agents will seek power. However, we hope that this work will foster thoughtful, serious, and rigorous discussion of this possibility. Acknowledgments Alexander Turner was supported by the Berkeley Existential Risk Initiative and the Long-Term Future Fund. Alexander Turner, Rohin Shah, and Andrew Critch were supported by the Center for Human-Compatible AI. Prasad Tadepalli was supported by the National Science Foundation. Yousif Almulla, John E. Ball, Daniel Blank, Steve Byrnes, Ryan Carey, Michael Dennis, Scott Emmons, Alan Fern, Daniel Filan, Ben Garfinkel, Adam Gleave, Edouard Harris, Evan Hubinger, DNL Kok, Vanessa Kosoy, Victoria Krakovna, Cassidy Laidlaw, Joel Lehman, David Lindner, Dylan Hadfield-Menell, Richard Möhn, Alexandra Nolan, Matt Olson, Neale Ratzlaff, Adam Shimi, Sam Toyer, Joshua Turner, Cody Wild, Davide Zagami, and our anonymous reviewers provided valuable feedback. References Tsvi Benson-Tilsen and Nate Soares. Formalizing convergent instrumental goals.Workshops at the Thirtieth AAAI Conference on Artificial Intelligence, 2016. Nick Bostrom. The superintelligent will: Motivation and instrumental rationality in advanced artificial agents. Minds and Machines, 22(2):71–85, 2012. Nick Bostrom.Superintelligence. Oxford University Press, 2014. Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A. Efros. Large-scale study of curiosity-driven learning. InInternational Conference on Learning Representations, 2019. 11 Ryan Carey. Incorrigibility in the CIRL framework.AI, Ethics, and Society, 2018. Chris Drummond. Composing functions to speed up reinforcement learning in a changing world. InMachine Learning: ECML-98, volume 1398, pages 370–381. Springer, 1998. Yuqing Du, Stas Tiomkin, Emre Kiciman, Daniel Polani, Pieter Abbeel, and Anca Dragan. AvE: Assistance via empowerment.Advances in Neural Information Processing Systems, 33, 2020. David Foster and Peter Dayan. Structure in the space of value functions.Machine Learning, pages 325–346, 2002. Christian Guckelsberger, Christoph Salge, and Simon Colton. Intrinsically motivated general companion NPCs via coupled empowerment maximisation. InIEEE Conference on Computational Intelligence and Games, pages 1–8, 2016. Christian Guckelsberger, Christoph Salge, and Julian Togelius. New and surprising ways to be mean. InIEEE Conference on Computational Intelligence and Games, pages 1–8, 2018. Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel, and Stuart Russell. The off-switch game. InProceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pages 220–227, 2017. Yann LeCun and Anthony Zador. Don’t fear the Terminator, September 2019. URLhttps://blogs. scientificamerican.com/observations/dont-fear-the-terminator/. Steven A Lippman. On the set of optimal policies in discrete dynamic programming.Journal of Mathematical Analysis and Applications, 24(2):440–445, 1968. Lionel W McKenzie. Turnpike theory.Econometrica: Journal of the Econometric Society, pages 841–865, 1976. Ishai Menache, Shie Mannor, and Nahum Shimkin. Q-cut—dynamic discovery of sub-goals in reinforcement learning. InEuropean Conference on Machine Learning, pages 295–306. Springer, 2002. Smitha Milli, Dylan Hadfield-Menell, Anca Dragan, and Stuart Russell. Should robots be obedient? In Proceedings of the 26th International Joint Conference on Artificial Intelligence, pages 4754–4760, 2017. Melanie Mitchell. Why AI is harder than we think.arXiv preprint arXiv:2104.12871, 2021. Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. InProceedings of the Sixteenth International Conference on Machine Learning, pages 278–287. Morgan Kaufmann, 1999. Chris Olah, Nick Cammarata, Ludwig Schubert, Gabriel Goh, Michael Petrov, and Shan Carter. Zoom in: An introduction to circuits.Distill, 2020. Stephen Omohundro. The basic AI drives, 2008. Deepak Pathak, Pulkit Agrawal, Alexei A. Efros, and Trevor Darrell. Curiosity-driven exploration by self- supervised prediction. InICML, 2017. Steven Pinker and Stuart Russell. The foundations, benefits, and possible existential threat of AI, June 2020. URLhttps://futureoflife.org/2020/06/15/steven-pinker-and-stuart-russell-on- the-foundations-benefits-and-possible-existential-risk-of-ai/. Martin L Puterman.Markov decision processes: Discrete stochastic dynamic programming. John Wiley & Sons, 2014. J.B. Reece and N.A. Campbell.Campbell Biology. Pearson Australia, 2011. Kevin Regan and Craig Boutilier. Robust policy computation in reward-uncertain MDPs using nondominated policies. InTwenty-Fourth AAAI Conference on Artificial Intelligence, 2010. Stuart Russell.Human compatible: Artificial intelligence and the problem of control. Viking, 2019. Stuart J Russell and Peter Norvig.Artificial intelligence: a modern approach. Pearson Education Limited, 2009. Christoph Salge and Daniel Polani. Empowerment as replacement for the three laws of robotics.Frontiers in Robotics and AI, 4:25, 2017. Christoph Salge, Cornelius Glackin, and Daniel Polani. Empowerment–an introduction. InGuided Self- Organization: Inception, pages 67–114. Springer, 2014. 12 Faridun Sattarov.Power and technology: a philosophical and ethical analysis. Rowman & Littlefield Interna- tional, Ltd, 2019. Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International Conference on Machine Learning, pages 1312–1320, 2015. Nate Soares, Benja Fallenstein, Stuart Armstrong, and Eliezer Yudkowsky. Corrigibility.AAAI Workshops, 2015. Richard S Sutton and Andrew G Barto.Reinforcement learning: an introduction. MIT Press, 1998. Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: A scalable real-time architecture for learning knowledge from unsupervised sensorimotor interaction. InInternational Conference on Autonomous Agents and Multiagent Systems, pages 761–768, 2011. 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, Dylan Hadfield-Menell, and Prasad Tadepalli. Conservative agency via attainable utility preservation. InProceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 385–391, 2020. Various. Debate on instrumental convergence between LeCun, Russell, Bengio, Zador, and more, 2019. URLhttps://w.alignmentforum.org/posts/WxW6Gc6f2z3mzmqKs/debate-on-instrumental- convergence-between-lecun-russell. Tao Wang, Michael Bowling, and Dale Schuurmans. Dual representations for dynamic programming and rein- forcement learning. InInternational Symposium on Approximate Dynamic Programming and Reinforcement Learning, pages 44–51. IEEE, 2007. Tao Wang, Michael Bowling, Dale Schuurmans, and Daniel J Lizotte. Stable dual dynamic programming. In Advances in Neural Information Processing Systems, pages 1569–1576, 2008. 13 Appendix A Comparing POWERwith information-theoretic empowerment Salge et al. [2014] define information-theoreticempowermentas the maximum possible mutual information between the agent’s actions and the state observationsnsteps in the future, written E n (s). This notion requires an arbitrary choice of horizon, failing to account for the agent’s discount rateγ. “In a discrete deterministic world empowerment reduces to the logarithm of the number of sensor states reachable with the available actions” [Salge et al., 2014]. Figure 9 demonstrates how empowerment can return counterintuitive verdicts with respect to the agent’s control over the future. 12 (a) 3 (b) 4 (c) Figure 9: Proposed empowerment measures fail to adequately capture how future choice is affected by present actions. In a:E n (s 1 )varies depending on whethernis even; thus,lim n→∞ E n (s 1 ) does not exist. In b and c:∀n : E n (s 3 ) =E n (s 4 ), even thoughs 4 allows greater control over future state trajectories thans 3 does. For example, suppose that in both b and c, the leftmost black state and the rightmost red state have 1 reward while all other states have 0 reward. In c, the agent can independently maximize the intermediate black-state reward and the delayed red-state reward. Independent maximization is not possible in b. POWERreturns intuitive answers in these situations.lim γ→1 POWER D bound (s 1 ,γ) converges by lemma 5.3. Consider the obvious involutionφwhich takes each state in fig. 9b to its counterpart in fig. 9c. Sinceφ· F nd (s 3 )(F nd (s 4 ) =F(s 4 ), proposition 6.6 proves that∀γ∈[0,1] : POWER D bound (s 3 ,γ)≤ most:D bound POWER D bound (s 4 ,γ), with the proof of proposition 6.6 showing strict inequality under allD X-IID whenγ∈(0,1). Empowerment can be adjusted to account for these cases, perhaps by considering the channel capacity between the agent’s actions and the state trajectories induced by stationary policies. However, since POWERis formulated in terms of optimal value, we believe thatPOWERis better suited forMDPs than information-theoretic empowerment is. Appendix B Seeking POWERcan be a detour Remark.The results of appendix E do not depend on this section’s results. One might suspect that optimal policies tautologically tend to seekPOWER. This intuition is wrong. 1 23 N NE Figure 10 Proposition B.1(GreaterPOWER D bound does not imply greaterP D bound ).Actionaseeking more POWER D bound thana ′ at statesandγdoes not imply thatP D bound (s,a,γ)≥P D bound ( s,a ′ ,γ ) . 14 Proof.Consider the environment of fig. 10. LetX u : =unif(0,1), and considerD X u -IID , which has bounded support. Direct computation 7 of thePOWERexpectation (definition 5.2) yields POWER D X u -IID (s 2 ,1) = 3 4 > 2 3 =POWER D X u -IID (s 3 ,1) . Therefore,Nseeks morePOWER D X u -IID thanNEat states 1 andγ= 1. However,P D X u -IID (s 1 ,N,1) = 1 3 < 2 3 =P D X u -IID (s 1 ,NE,1). Lemma B.2(Fraction of orbits which agree on weak optimality).LetD⊆∆(R |S| ), and sup- posef 1 ,f 2 : ∆(R |S| )→Rare such thatf 1 (D)≥ most:D f 2 (D). Then for allD ∈D, ∣ ∣ ∣ D ′ ∈S |S| ·D|f 1 (D ′ )≥f 2 (D ′ ) ∣ ∣ ∣ | S |S| ·D | ≥ 1 2 . Proof.AllD ′ ∈S |S| ·Dsuch thatf 1 (D ′ ) =f 2 (D ′ )satisfyf 1 (D ′ )≥f 2 (D ′ ). Otherwise, consider theD ′ ∈S |S| · Dsuch thatf 1 (D ′ )6=f 2 (D ′ ). By the definition of≥ most (definition 6.5), at least 1 2 of theseD ′ satisfyf 1 (D ′ )> f 2 (D ′ ), in which casef 1 (D ′ )≥f 2 (D ′ ). Then the desired inequality follows. Lemma B.3(≥ most and trivial orbits).LetD⊆∆(R |S| )and supposef 1 (D)≥ most:D f 2 (D). For all reward function distributionsD ∈Dwith one-element orbits,f 1 (D)≥f 2 (D). In particular,D has a one-element orbit when it distributes reward identically and independently (IID) across states. Proof.By lemma B.2, at least half of the elementsD ′ ∈S |S| ·Dsatisfyf 1 (D ′ )≥f 2 (D ′ ). But ∣ ∣ ∣ S |S| ·D ∣ ∣ ∣ = 1, and sof 1 (D)≥f 2 (D)must hold. IfDisIID, it has a one-element orbit due to the assumed identical distribution of reward. Proposition B.4(Actions which tend to seekPOWERdo not necessarily tend to be optimal).Action atending to seek morePOWERthana ′ at statesandγdoes not imply thatP D any (s,a,γ)≥ most:D any P D any ( s,a ′ ,γ ) . Proof.Consider the environment of fig. 10. SinceRSD nd (s 3 )(RSD(s 2 ), proposition 6.12 shows thatPOWER D bound (s 2 ,1)≥ most:D bound POWER D bound (s 3 ,1)vias ′ : =s 3 ,s : =s 2 ,φthe identity permutation (which is an involution). Therefore,Ntends to seek morePOWERthanNEat states 1 and γ= 1. IfP D any (s 1 ,N,1)≥ most:D any P D any (s 1 ,NE,1), then lemma B.3 shows thatP D X-IID (s 1 ,N,1)≥ P D X-IID (s 1 ,NE,1) for allD X-IID . But the proof of proposition B.1 showed thatP D X u -IID (s 1 ,N,1)< P D X u -IID (s 1 ,NE,1) forX u : =unif(0,1) . Therefore, it cannot be true thatP D any (s 1 ,N,1)≥ most:D any P D any (s 1 ,NE,1). Appendix C Sub-optimal POWER In certain situations,POWERreturns intuitively surprising verdicts. There exists a policy under which the reader chooses a winning lottery ticket, but it seems wrong to say that the reader has the power to win the lottery with high probability. For various reasons, humans and other bounded agents are generally incapable of computing optimal policies for arbitrary objectives. More formally, consider the rewardlessMDPof fig. 11. Consider a model-based RL agent with black-box simulator access to this environment. The agent has no prior information about the model, and so it acts randomly. Before long, the agent has probably learned how to navigate froms 0 to statess ` ,s r ,s 1 ,s 2 , ands 5 . However, over any reasonable timescale, it is extremely improbable that the agent discovers the two actions respectively leading to s 3 ands 4 . 7 In small deterministicMDPs, thePOWERand optimality probability of the maximum-entropy reward function distribution can be computed using https://github.com/loganriggs/Optimal-Policies-Tend-To-Seek-Power. 15 0 r 3 4 5 ` 2 1 Figure 11:s 0 is the starting state, and|A|= 10 10 10 . Ats 0 , half of the actions lead tos ` , while the other half lead tos r . Similarly, half of the actions ats ` lead tos 1 , while the other half lead tos 2 . At s r , one action leads tos 3 , one action leads tos 4 , and the remaining10 10 10 −2actions lead tos 5 . Even provided with a reward functionRand the discount rateγ, the agent has yet to learn the relevant environmental dynamics, and so many of its policies are far from optimal. Although proposition 6.6 shows that∀γ∈[0,1] : POWER D bound (s ` ,γ)≤ most:D bound POWER D bound (s r ,γ), there is a sense in whichs ` gives this agent more power. We formalize a bounded agent’s goal-achievement capabilities with a functionpol, which takes as input a reward function and a discount rate, and returns a policy. Informally, this is the best policy which the agent knows about. We can then calculate POWER D bound with respect to pol. Definition C.1(SuboptimalPOWER).LetΠ ∆ be the set of stationary stochastic policies, and let pol : R S ×[0,1]→Π ∆ . Forγ∈[0,1], POWER pol D bound (s,γ) : =E R∼D bound , a∼pol(R,γ)(s), s ′ ∼T(s,a) [ lim γ ∗ →γ (1−γ ∗ )V pol(R,γ) R ( s ′ ,γ ∗ ) ] .(5) By lemma E.38,POWER D bound is the special case where∀R∈R S ,γ∈[0,1] : pol(R,γ)∈Π ∗ (R,γ). We define POWER pol D bound -seeking similarly as in definition 5.6. POWER pol D bound (s 0 ,1) increases as the policies returned bypolare improved. We illustrate this by considering theD X-IID case. pol 1 The model is initially unknown, and so∀R,γ : pol 1 (R,γ)is a uniformly random policy. Sincepol 1 is constant on its inputs,POWER pol 1 D X-IID (s 0 ,1) =E[X] by the linearity of ex- pectation and the fact thatD X-IID distributes reward independently and identically across states. pol 2 The agent knows the dynamics, except that it does not know how to reachs 3 ors 4 . At this point,pol 2 (R,1)navigates froms 0 to the average-optimal choice among three terminal states:s 1 ,s 2 , ands 5 . Therefore, POWER pol 2 D bound (s 0 ,1) =E[maxof3draws fromX]. pol 3 The agent knows the dynamics, the environment is small enough to solve explicitly, and so∀R,γ : pol 3 (R,γ)is an optimal policy.pol 3 (R,1)navigates froms 0 to the average-optimal choice among all five terminal states. Therefore,POWER pol 3 D bound (s 0 ,1) = E[maxof5draws fromX]. As the agent learns more about the environment and improvespol, the agent’sPOWER pol D bound increases. The agent seeksPOWER pol 2 D bound by navigating tos ` instead ofs r , but seeks morePOWER D bound by navigating tos r instead ofs ` . Intuitively, bounded agents gain power by improvingpoland by formally seeking POWER pol D bound within the environment. Appendix D Lists of results List of definitions 3.1Definition (RewardlessMDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 16 3.2Definition (1-cycle states) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 3.3Definition (State visit distribution [Sutton and Barto, 1998]) . . . . . . . . . . . .3 3.4Definition (Fsingle-state restriction) . . . . . . . . . . . . . . . . . . . . . . . . .3 3.5Definition (Value function) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 3.6Definition (Non-domination) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 4.1Definition (Optimal policy set function) . . . . . . . . . . . . . . . . . . . . . . .4 4.2Definition (Reward function distributions) . . . . . . . . . . . . . . . . . . . . . .4 4.3Definition (Visit distribution optimality probability) . . . . . . . . . . . . . . . . .4 4.4Definition (Action optimality probability) . . . . . . . . . . . . . . . . . . . . . .4 5.1Definition (Average optimal value) . . . . . . . . . . . . . . . . . . . . . . . . . .5 5.2Definition (POWER) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 5.6Definition (POWER-seeking actions) . . . . . . . . . . . . . . . . . . . . . . . . .5 6.1Definition (Similarity of vector sets) . . . . . . . . . . . . . . . . . . . . . . . . .6 6.2Definition (Similarity of vector function sets) . . . . . . . . . . . . . . . . . . . .6 6.3Definition (Pushforward distribution of a permutation) . . . . . . . . . . . . . . .7 6.4Definition (Orbit of a probability distribution) . . . . . . . . . . . . . . . . . . . .7 6.5Definition (Inequalities which hold for most probability distributions) . . . . . . .7 6.7Definition (Equivalent actions) . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 6.8Definition (States reachable after taking an action) . . . . . . . . . . . . . . . . . .7 6.10 Definition (Recurrent state distributions [Puterman, 2014]) . . . . . . . . . . . . .8 6.11 Definition (Average-optimal policies) . . . . . . . . . . . . . . . . . . . . . . . .8 C.1 Definition (Suboptimal POWER) . . . . . . . . . . . . . . . . . . . . . . . . . . .16 E.2 Definition (Transition matrix induced by a policy) . . . . . . . . . . . . . . . . . .20 E.6 Definition (Continuous reward function distribution) . . . . . . . . . . . . . . . .21 E.9 Definition (Non-dominated linear functionals) . . . . . . . . . . . . . . . . . . . .21 E.13 Definition (Non-dominated vector functions) . . . . . . . . . . . . . . . . . . . .22 E.14 Definition (Affine transformation of visit distribution sets) . . . . . . . . . . . . .22 E.18 Definition (Support ofD any ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 E.19 Definition (Linear functional optimality probability) . . . . . . . . . . . . . . . . .24 E.23 Definition (Bounded, continuousIIDreward) . . . . . . . . . . . . . . . . . . . .25 E.25 Definition (Indicator function) . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 E.31 Definition (Evaluating sets of visit distribution functions atγ) . . . . . . . . . . . .29 E.39 Definition (Discount-normalized value function) . . . . . . . . . . . . . . . . . . .31 E.42 Definition (Normalized visit distribution function) . . . . . . . . . . . . . . . . . .34 List of theorems 5.3Lemma (Continuity of POWER) . . . . . . . . . . . . . . . . . . . . . . . . . . .5 5.4Proposition (Maximal POWER) . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 5.5Proposition (POWERis smooth across reversible dynamics) . . . . . . . . . . . . .5 17 6.6Proposition (States with “more options” have more POWER) . . . . . . . . . . . .7 6.9Proposition (Keeping options open tends to bePOWER-seeking and tends to be optimal)7 6.12 Proposition (Whenγ= 1,RSDs control POWER) . . . . . . . . . . . . . . . . . .8 6.13 Theorem (Average-optimal policies tend to end up in “larger” sets ofRSDs) . . . .9 6.14 Corollary (Average-optimal policies tend not to end up in any given 1-cycle) . . . .9 B.1 Proposition (Greater POWER D bound does not imply greaterP D bound ) . . . . . . . . . .14 B.2 Lemma (Fraction of orbits which agree on weak optimality) . . . . . . . . . . . .15 B.3 Lemma (≥ most and trivial orbits) . . . . . . . . . . . . . . . . . . . . . . . . . . .15 B.4Proposition (Actions which tend to seekPOWERdo not necessarily tend to be optimal)15 E.1 Lemma (A policy is optimal iff it induces an optimal visit distribution at every state)19 E.3 Proposition (Properties of visit distribution functions) . . . . . . . . . . . . . . . .20 E.4 Lemma (f∈F(s)is multivariate rational onγ) . . . . . . . . . . . . . . . . . . .20 E.5 Corollary (On-policy value is rational onγ) . . . . . . . . . . . . . . . . . . . . .20 E.7 Lemma (Distinct linear functionals disagree almost everywhere on their domains) .21 E.8 Corollary (Unique maximization of almost all vectors) . . . . . . . . . . . . . . .21 E.10 Lemma (All vectors are maximized by a non-dominated linear functional) . . . . .21 E.11 Corollary (Maximal value is invariant to restriction to non-dominated functionals) .21 E.12 Lemma (How non-domination containment affects optimal value) . . . . . . . . .21 E.15 Lemma (Invariance of non-domination under positive affine transform) . . . . . . .22 E.16 Lemma (Helper lemma for demonstrating≥ most:D any ) . . . . . . . . . . . . . . . .23 E.17 Lemma (A helper result for expectations of functions) . . . . . . . . . . . . . . . .23 E.20 Proposition (Non-dominated linear functionals and their optimality probability) . .24 E.21 Lemma (Expected value of similar linear functional sets) . . . . . . . . . . . . . .24 E.22 Lemma (For continuousIIDdistributionsD X-IID ,∃b < c : (b,c) |S| ⊆supp(D X-IID ))25 E.24 Lemma (Expectation superiority lemma) . . . . . . . . . . . . . . . . . . . . . . .25 E.26 Lemma (Optimality probability inclusion relations) . . . . . . . . . . . . . . . . .26 E.27 Lemma (Optimality probability of similar linear functional sets) . . . . . . . . . .27 E.28 Lemma (Optimality probability superiority lemma) . . . . . . . . . . . . . . . . .27 E.29 Lemma (Limit probability inequalities which hold for most distributions) . . . . .28 E.30 Proposition (How to transfer optimal policy sets across discount rates) . . . . . . .28 E.32 Lemma (Non-domination acrossγvalues for expectations of visit distributions) . .29 E.33 Lemma (∀γ∈(0,1) : d∈F nd (s,γ)iffd∈ND ( F(s,γ) ) ) . . . . . . . . . . . .29 E.34 Lemma (∀γ∈[0,1) : V ∗ R (s,γ) = max f∈F nd (s) f(γ) > r) . . . . . . . . . . . . . .29 E.35 Lemma (Optimal policy shift bound) . . . . . . . . . . . . . . . . . . . . . . . . .30 E.36 Proposition (Optimality probability’s limits exist) . . . . . . . . . . . . . . . . . .30 E.37 Lemma (Optimality probability identity) . . . . . . . . . . . . . . . . . . . . . . .30 E.38 Lemma (POWERidentities) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30 E.40 Lemma (Normalized value functions have uniformly bounded derivative) . . . . .31 E.41 Lemma (Lower bound on current POWERbased on future POWER) . . . . . . . . .33 18 E.43 Lemma (Normalized visit distribution functions are continuous) . . . . . . . . . .34 E.44 Lemma (Non-domination of normalized visit distribution functions) . . . . . . . .34 E.45 Lemma (POWERlimit identity) . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 E.46 Lemma (Lemma for POWERsuperiority) . . . . . . . . . . . . . . . . . . . . . . .35 E.47Lemma (Non-dominated visit distribution functions never agree with other visit distribution functions at that state) . . . . . . . . . . . . . . . . . . . . . . . . . .37 E.48 Corollary (Cardinality of non-dominated visit distributions) . . . . . . . . . . . . .37 E.49 Lemma (Optimality probability and state bottlenecks) . . . . . . . . . . . . . . . .37 E.50 Lemma (Action optimality probability is a special case of visit distribution optimality probability) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .39 E.51 Lemma (POWERidentity whenγ= 1) . . . . . . . . . . . . . . . . . . . . . . . .42 E.52 Proposition (RSDproperties) . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43 E.53 Lemma (When reachable with probability 1, 1-cycles induce non-dominatedRSDs)44 D.1 Contributions of independent interest We developed new basicMDPtheory by exploring the structural properties of visit distribution functions. Echoing Wang et al. [2007, 2008], we believe that this area is interesting and underexplored. D.1.1 Optimal value theory Lemma E.40 shows thatf(γ ∗ ) : = lim γ ∗ →γ (1−γ ∗ )V ∗ R (s,γ ∗ )is Lipschitz continuous onγ∈[0,1], with Lipschitz constant depending only on‖R‖ 1 . For all statessand policiesπ∈Π, corollary E.5 shows thatV π R (s,γ)is rational onγ. Optimal value has a well-known dual formulation:V ∗ R (s,γ) = max f∈F(s) f(γ) > r. Lemma E.34(∀γ∈[0,1) : V ∗ R (s,γ) = max f∈F nd (s) f(γ) > r). In a fixed rewardlessMDP, lemma E.34 may enable more efficient computation of optimal value functions for multiple reward functions. D.1.2 Optimal policy theory Proposition E.30 demonstrates how to preserve optimal incentives while changing the discount rate. Proposition E.30(How to transfer optimal policy sets across discount rates).Suppose reward functionRhas optimal policy setΠ ∗ (R,γ)at discount rateγ∈(0,1). For anyγ ∗ ∈(0,1), we can construct a reward functionR ′ such thatΠ ∗ ( R ′ ,γ ∗ ) = Π ∗ (R,γ). Furthermore,V ∗ R ′ (·,γ ∗ ) = V ∗ R (·,γ). D.1.3 Visit distribution theory While Regan and Boutilier [2010] consider a visit distribution functionf∈F(s)to be non-dominated if it is optimal for some reward function in a setR ⊆R |S| , our stricter definition 3.6 considersfto be non-dominated when∃r∈R |S| ,γ∈(0,1) : f(γ) > r>max f ′ ∈F(s)\f f ′ (γ) > r. Appendix E Theoretical results Lemma E.1(A policy is optimal iff it induces an optimal visit distribution at every state).Let γ∈(0,1)and letRbe a reward function.π∈Π ∗ (R,γ)iffπinduces an optimal visit distribution at every state. Proof.By definition, a policyπis optimal iffπinduces the maximal on-policy value at each state, which is true iffπinduces an optimal visit distribution at every state (by the dual formulation of optimal value functions). 19 Definition E.2(Transition matrix induced by a policy).T π is the transition matrix induced by policy π∈Π, whereT π e s : =T(s,π(s)).(T π ) t e s gives the probability distribution over the states visited at time stept, after followingπfortsteps froms. Proposition E.3(Properties of visit distribution functions).Lets,s ′ ∈S,f π,s ∈F(s). 1.f π,s (γ) is element-wise non-negative and element-wise monotonically increasing onγ∈ [0,1). 2.∀γ∈[0,1) : ∥ ∥ f π,s (γ) ∥ ∥ 1 = 1 1−γ . Proof.Item 1: by examination of definition 3.3,f π,s = ∑ ∞ t=0 (γT π ) t e s . Since each(T π ) t is left stochastic ande s is the standard unit vector, each entry in each summand is non-negative. Therefore, ∀γ∈[0,1) : f π,s (γ) > e s ′ ≥0, and this function monotonically increases onγ. Item 2: ∥ ∥ f π,s (γ) ∥ ∥ 1 = ∥ ∥ ∥ ∥ ∥ ∥ ∞ ∑ t=0 (γT π ) t e s ∥ ∥ ∥ ∥ ∥ ∥ 1 (6) = ∞ ∑ t=0 γ t ∥ ∥ ∥ (T π ) t e s ∥ ∥ ∥ 1 (7) = ∞ ∑ t=0 γ t (8) = 1 1−γ .(9) Equation (7) follows because all entries in each(T π ) t e s are non-negative by item 1. Equation (8) follows because each(T π ) t is left stochastic ande s is a stochastic vector, and so ∥ ∥ ∥ (T π ) t e s ∥ ∥ ∥ 1 = 1. Lemma E.4(f∈F(s)is multivariate rational onγ).f π ∈F(s)is a multivariate rational function onγ∈[0,1). Proof.Letr∈R |S| and considerf π ∈ F(s). Letv π R be theV ∗ R (s,γ) function in column vector form, with one entry per state value. By the Bellman equations,v π R = (I−γT π ) −1 r.LetA γ : = (I−γT π ) −1 , and for states, form A s,γ by replacingA γ ’s column for stateswithr. As noted by Lippman [1968], by Cramer’s rule, V π R (s,γ) = detA s,γ detA γ is a rational function with numerator and denominator having degree at most |S|. In particular, for each state indicator reward functione s i ,V π s i (s,γ) =f π,s (γ) > e s i is a rational function ofγwhose numerator and denominator each have degree at most|S|. This implies that f π (γ)is multivariate rational onγ∈[0,1). Corollary E.5(On-policy value is rational onγ).Letπ∈ΠandRbe any reward function.V π R (s,γ) is rational onγ∈[0,1). Proof.V π R (s,γ) =f π,s (γ) > r , andfis a multivariate rational function ofγby lemma E.4. Therefore, for fixedr,f π,s (γ) > ris a rational function ofγ. 20 E.1 Non-dominated visit distribution functions Definition E.6(Continuous reward function distribution).Results withD cont hold for any absolutely continuous reward function distribution. Remark.We assumeR |S| is endowed with the standard topology. Lemma E.7(Distinct linear functionals disagree almost everywhere on their domains).Letx,x ′ ∈ R |S| be distinct.P r∼D cont ( x > r=x ′> r ) = 0. Proof. r∈R |S| |(x−x ′ ) > r= 0 is a hyperplane sincex−x ′ 6=0. Therefore, it has no interior in the standard topology onR |S| . Since this empty-interior set is also convex, it has zero Lebesgue measure. By the Radon-Nikodym theorem, it has zero measure under any continuous distribution D cont . Corollary E.8(Unique maximization of almost all vectors).LetX( R |S| be finite. P r∼D cont ( ∣ ∣ arg max x ′ ∈X x ′> r ∣ ∣ >1 ) = 0. Proof. Letx,x ′ ∈Xbe distinct. For anyr∈R |S| ,x,x ′ ∈arg max x ′ ∈X x ′> riffx > r=x ′> r≥ max x ′ ∈X\x,x ′ x ′> r. By lemma E.7,x > r=x ′> rholds with probability 0 under anyD cont . E.1.1 Generalized non-domination results Our formalism includes bothF nd (s)andRSD nd (s); we therefore prove results that are applicable to both. Definition E.9(Non-dominated linear functionals).LetX( R |S| be finite.ND(X) : = x∈X|∃r∈R |S| : x > r>max x ′ ∈X\x x ′> r . Lemma E.10 (All vectors are maximized by a non-dominated linear functional).Letr∈R |S| and letX( R |S| be finite and non-empty.∃x ∗ ∈ND(X) : x ∗> r= max x∈X x > r. Proof.LetA(r|X) : = arg max x∈X x > r=x 1 ,...,x n . Then x > 1 r=·=x > n r>max x ′ ∈X (r|X) x ′> r.(10) In eq. (10), eachx > rexpression is linear onr. Themaxis piecewise linear onrsince it is the maximum of a finite set of linear functionals. In particular, all expressions in eq. (10) are continuous onr, and so we can find someδ >0neighborhoodB(r,δ)such that∀r ′ ∈B(r,δ) : max x i ∈A(r|X) x > i r ′ >max x ′ ∈X (r|X) x ′> r ′ . But almost allr ′ ∈B(r,δ)are maximized by a unique functionalx ∗ by corollary E.8; in particular, at least one suchr ′ exists. Formally,∃r ′ ∈B(r,δ) : x ∗> r ′ >max x ′ ∈X\x ∗ x ′> r ′ . Therefore, x ∗ ∈ND(X)by definition E.9. x ∗> r ′ ≥max x i ∈A(r|X) x > i r ′ >max x ′ ∈X (r|X) x ′> r ′ , with the strict inequality following because r ′ ∈B(r,δ). These inequalities imply thatx ∗ ∈A(r|X). Corollary E.11(Maximal value is invariant to restriction to non-dominated functionals).Letr∈R |S| and letX( R |S| be finite.max x∈X x > r= max x∈ND(X) x > r. Proof.IfXis empty, holds trivially. Otherwise, apply lemma E.10. Lemma E.12(How non-domination containment affects optimal value).Letr∈R |S| and let X,X ′ ( R |S| be finite. 1. IfND(X)⊆X ′ , thenmax x∈X x > r≤max x ′ ∈X ′ x ′> r. 21 2. IfND(X)⊆X ′ ⊆X, thenmax x∈X x > r= max x ′ ∈X ′ x ′> r. Proof.Item 1: max x∈X x > r= max x∈ND(X) x > r(11) ≤max x ′ ∈X ′ x ′> r.(12) Equation (11) follows by corollary E.11. Equation (12) follows because ND(X)⊆X ′ . Item 2: by item 1,max x∈X x > r≤max x ′ ∈X ′ x ′> r. SinceX ′ ⊆X, we also havemax x∈X x > r≥ max x ′ ∈X ′ x ′> r, and so equality must hold. DefinitionE.13(Non-dominatedvectorfunctions).LetI⊆Randlet F( ( R |S| ) I be a finite set of vector-valued functions onI.ND(F) : = f∈F|∃γ∈I,r∈R |S| : f(γ) > r>max f ′ ∈F\f f ′ (γ) > r . Remark.F nd (s) =ND ( F(s) ) by definition 3.6. Definition E.14 (Affine transformation of visit distribution sets).For notational convenience, we de- fine set-scalar multiplication and set-vector addition onX⊆R |S| : forc∈R,cX : = cx|x∈X . Fora∈R |S| ,X+a : = x+a|x∈X . Similar operations hold whenXis a set of vector functionsR7→R |S| . Lemma E.15(Invariance of non-domination under positive affine transform). 1.LetX( R |S| be finite. Ifx∈ND(X), then∀c >0,a∈R |S| : (cx+a)∈ND(cX+a). 2.LetI⊆Rand letF( ( R |S| ) I be a finite set of vector-valued functions onI. If f∈ND(F), then∀c >0,a∈R |S| : (cf+a)∈ND(cF+a). Proof. Item 1: Supposex∈ND(X)is strictly optimal forr∈R |S| . Then letc >0,a∈R |S| be arbitrary, and defineb : =a > r. x > r>max x ′ ∈X\x x ′> r(13) cx > r+b >max x ′ ∈X\x cx ′> r+b(14) (cx+a) > r>max x ′ ∈X\x (cx ′ +a) > r(15) (cx+a) > r>max x ′ ∈(cX+a)\cx+a x ′> r.(16) Equation (14) follows becausec >0. Equation (15) follows by the definition ofb. Item 2: Iff∈ND(F), then by definition E.13, there existγ∈I,r∈R |S| such that f(γ) > r>max f ′ ∈F\f f ′ (γ) > r.(17) Apply item 1 to conclude (cf(γ) +a) > r>max (cf ′ +a)∈(cF+a)\cf+a (cf ′ (γ) +a) > r.(18) Therefore,(cf+a)∈ND(cF+a). 22 E.1.2 Inequalities which hold under most reward function distributions Definition 6.5(Inequalities which hold for most probability distributions).Letf 1 ,f 2 : ∆(R |S| )→R be functions from reward function distributions to real numbers and letD⊆∆(R |S| )be closed under permutation. We writef 1 (D)≥ most:D f 2 (D) 8 when, forallD ∈D, the following cardinality inequality holds: ∣ ∣ ∣ D ′ ∈S |S| ·D |f 1 (D ′ )> f 2 (D ′ ) ∣ ∣ ∣ ≥ ∣ ∣ ∣ D ′ ∈S |S| ·D |f 1 (D ′ )< f 2 (D ′ ) ∣ ∣ ∣ .(4) Lemma E.16 (Helper lemma for demonstrating≥ most:D any ).LetD⊆∆(R |S| ). If∃φ∈S |S| such that for allD ∈D,f 1 (D)< f 2 (D)implies thatf 1 (φ·D)> f 2 (φ·D), thenf 1 (D)≥ most:D f 2 (D). Proof.Sinceφdoes not belong to the stabilizer ofS |S| ,φacts injectively onS |S| · D. By as- sumption onφ, the image ofD ′ ∈S |S| · D |f 1 (D ′ )< f 2 (D ′ )underφis a subset of D ′ ∈S |S| ·D |f 1 (D ′ )> f 2 (D ′ ). Sinceφis injective, ∣ ∣ ∣ D ′ ∈S |S| ·D |f 1 (D ′ )< f 2 (D ′ ) ∣ ∣ ∣ ≤ ∣ ∣ ∣ D ′ ∈S |S| ·D |f 1 (D ′ )> f 2 (D ′ ) ∣ ∣ ∣ .f 1 (D)≥ most:D f 2 (D)by definition 6.5. Lemma E.17(A helper result for expectations of functions).LetB 1 ,...,B n ( R |S| be finite and letD⊆∆(R |S| ). Supposefis a function of the form f ( B 1 ,...,B n |D ) =E r∼D [ g ( max b 1 ∈B 1 b > 1 r,...,max b n ∈B n b > n r ) ] (19) for some functiong, and thatfis well-defined for allD ∈D. Letφbe a state permutation. Then f ( B 1 ,...,B n |D ) =f ( φ·B 1 ,...,φ·B n |φ·D ) .(20) Proof.Let distributionDhave probability measureF, and letφ·Dhave probability measureF φ . f ( B 1 ,...,B n |D ) (21) : =E r∼D [ g ( max b 1 ∈B 1 b > 1 r,...,max b n ∈B n b > n r ) ] (22) : = ∫ R |S| g ( max b 1 ∈B 1 b > 1 r,...,max b n ∈B n b > n r ) dF(r)(23) = ∫ R |S| g ( max b 1 ∈B 1 b > 1 r,...,max b n ∈B n b > n r ) dF φ (P φ r)(24) = ∫ R |S| g ( max b 1 ∈B 1 b > 1 ( P −1 φ r ′ ) ,...,max b n ∈B n b > n ( P −1 φ r ′ ) ) ∣ ∣ detP φ ∣ ∣ dF φ (r ′ )(25) = ∫ R |S| g ( max b 1 ∈B 1 ( P φ b 1 ) > r ′ ,...,max b n ∈B n ( P φ b n ) > r ′ ) dF φ (r ′ )(26) = ∫ R |S| g ( max b ′ 1 ∈φ·B 1 b ′> 1 r ′ ,...,max b ′ n ∈φ·B n b ′> n r ′ ) dF φ (r ′ )(27) = : f ( φ·B 1 ,...,φ·B n |φ·D ) .(28) Equation (24) follows by the definition ofF φ (definition 6.3). Equation (25) follows by substituting r ′ : =P φ r. Equation (26) follows from the fact that all permutation matrices have unitary determinant and are orthogonal (and so(P −1 φ ) > =P φ ). Definition E.18(Support ofD any ).LetD any be any reward function distribution.supp(D any )is the smallest closed subset ofR |S| whose complement has measure zero underD any . 8 We writef 1 (D)≥ most f 2 (D)whenDis clear from context. 23 Definition E.19(Linear functional optimality probability).For finiteA,B( R |S| , theprobability underD any thatAis optimal overBisp D any (A≥B) : =P r∼D any ( max a∈A a > r≥max b∈B b > r ) . Proposition E.20(Non-dominated linear functionals and their optimality probability).LetA( R |S| be finite. If∃b < c : [b,c] |S| ⊆supp(D any ), thena∈ND(A)implies thatais strictly optimal for a set of reward functions with positive measure underD any . Proof.Suppose∃b < c : [b,c] |S| ⊆supp(D any ). Ifa∈ND(A), then letrbe such thata > r> max a ′ ∈A\a a ′> r . Fora 1 >0,a 2 ∈R, positively affinely transformr ′ : =a 1 r+a 2 1(where 1∈R |S| is the all-ones vector) so thatr ′ ∈(b,c) |S| . Note thatais still strictly optimal forr ′ : a > r>max a ′ ∈A\a a ′> r⇐⇒a > r ′ >max a ′ ∈A\a a ′> r ′ .(29) Furthermore, by the continuity of both terms on the right-hand side of eq. (29),ais strictly optimal for reward functions in some open neighborhoodNofr ′ . LetN ′ : =N∩(b,c) |S| .N ′ is still open in R |S| since it is the intersection of two open setsNand(b,c) |S| . D any must assign positive probability measure to all open sets in its support; otherwise, its support would exclude these zero-measure sets by definition E.18. Therefore,D any assigns positive probability toN ′ ⊆supp(D any ). Lemma E.21(Expected value of similar linear functional sets).LetA,B( R |S| be finite, letA ′ be such thatND(A)⊆A ′ ⊆A, and letg : R→Rbe an increasing function. IfBcontains a copyB ′ ofA ′ viaφ, then E r∼D bound [ g ( max a∈A a > r ) ] ≤E r∼φ·D bound [ g ( max b∈B b > r ) ] .(30) IfND(B) ′ is empty, then eq.(30)is an equality. IfND(B) ′ is non-empty,gis strictly increasing, and∃b < c : (b,c) |S| ⊆supp(D bound ), then eq.(30)is strict. Proof.Becauseg : R→Ris increasing, it is measurable (as ismax). Therefore, the relevant expectations exist for allD bound . E r∼D bound [ g ( max a∈A a > r ) ] =E r∼D bound [ g ( max a∈A ′ a > r ) ] (31) =E r∼φ·D bound [ g ( max a∈φ·A ′ a > r ) ] (32) =E r∼φ·D bound [ g ( max b∈B ′ b > r ) ] (33) ≤E r∼φ·D bound [ g ( max b∈B b > r ) ] .(34) Equation (31) holds because∀r∈R |S| : max a∈A a > r= max a∈A ′ a > rby lemma E.12’s item 2 withX : =A,X ′ : =A ′ . Equation (32) holds by lemma E.17. Equation (33) holds by the definition ofB ′ . Furthermore, our assumption onφguarantees thatB ′ ⊆B. Therefore,max b∈B ′ b > r≤ max b∈B b > r , and so eq. (34) holds by the fact thatgis an increasing function. Then eq. (30) holds. IfND(B) ′ is empty, thenND(B)⊆B ′ . By assumption,B ′ ⊆B. Then apply lemma E.12 item 2 withX : =B,X ′ : =B ′ in order to conclude that eq. (34) is an equality. Then eq. (30) is also an equality. 24 Suppose thatgis strictly increasing,ND(B) ′ is non-empty, and∃b < c : (b,c) |S| ⊆ supp(D bound ). Letx∈ND(B) ′ . E r∼φ·D bound [ g ( max b∈B ′ b > r ) ] <E r∼φ·D bound g ( max a∈B ′ ∪x b > r ) (35) ≤E r∼φ·D bound [ g ( max b∈B b > r ) ] .(36) x is strictly optimal for a positive-probability subset ofsupp(D bound )by proposition E.20. Sincegis strictly increasing, eq. (35) is strict. Therefore, we conclude that eq. (30) is strict. Lemma E.22(For continuousIIDdistributionsD X-IID ,∃b < c : (b,c) |S| ⊆supp(D X-IID )). Proof.D X-IID : =X |S| . Since the state reward distributionXis continuous,Xmust have support on some open interval(b,c). SinceD X-IID isIIDacross states,(b,c) |S| ⊆supp(D X-IID ). Definition E.23(Bounded, continuousIIDreward).D C/B/IID is the set ofD X-IID which equalX |S| for some continuous, bounded-support distributionXoverR. Lemma E.24(Expectation superiority lemma).LetA,B( R |S| be finite and letg : R→Rbe an increasing function. IfBcontains a copyB ′ ofND(A)viaφ, then E r∼D bound [ g ( max a∈A a > r ) ] ≤ most:D bound E r∼D bound [ g ( max b∈B b > r ) ] .(37) Furthermore, ifgis strictly increasing andND(B)\φ·ND(A)is non-empty, then eq.(37) is strict for allD X-IID ∈D C/B/IID .In particular,E r∼D bound [ g ( max a∈A a > r ) ] 6≥ most:D bound E r∼D bound [ g ( max b∈B b > r ) ] . Proof. Becauseg : R→Ris increasing, it is measurable (as ismax). Therefore, the relevant expectations exist for allD bound . Suppose thatD bound is such thatE r∼D bound [ g ( max b∈B b > r ) ] <E r∼D bound [ g ( max a∈A a > r ) ] . E r∼φ·D bound [ g ( max a∈A a > r ) ] ≤E r∼φ 2 ·D bound [ g ( max b∈B b > r ) ] (38) =E r∼D bound [ g ( max b∈B b > r ) ] (39) <E r∼D bound [ g ( max a∈A a > r ) ] (40) ≤E r∼φ·D bound [ g ( max b∈B b > r ) ] .(41) Equation (38) follows by applying lemma E.21 with permutationφandA ′ : =ND(A). Equation (39) follows because involutions satisfyφ −1 =φ, andφ 2 is therefore the identity. Equation (40) follows because we assumed thatE r∼D bound [ g ( max b∈B b > r ) ] <E r∼D bound [ g ( max a∈A a > r ) ] . Equation (41) follows by applying lemma E.21 with permutationφand andA ′ : =ND(A) . By lemma E.16, eq. (37) holds. 25 Supposegis strictly increasing and ND(B) ′ is non-empty. Letφ ′ ∈S |S| . E r∼φ ′ ·D X-IID [ g ( max a∈A a > r ) ] =E r∼D X-IID [ g ( max a∈A a > r ) ] (42) <E r∼φ·D X-IID [ g ( max b∈B b > r ) ] (43) =E r∼φ ′ ·D X-IID [ g ( max b∈B b > r ) ] .(44) Equation (42) and eq. (44) hold becauseD X-IID distributes reward identically across states:∀φ x ∈ S |S| : φ x ·D X-IID =D X-IID . By lemma E.22,∃b < c : (b,c) |S| ⊆supp(D X-IID ). Therefore, apply lemma E.21 withA ′ : =ND(A)to conclude that eq. (43) holds. Therefore,∀φ ′ ∈S |S| : E r∼φ ′ ·D X-IID [ g ( max a∈A a > r ) ] <E r∼φ ′ ·D X-IID [ g ( max b∈B b > r ) ] , and so E r∼D bound [ g ( max a∈A a > r ) ] 6≥ most:D bound E r∼D bound [ g ( max b∈B b > r ) ] by definition 6.5. Definition E.25(Indicator function).LetLbe a predicate which takes inputx.1 L(x) is the function which returns 1 whenL(x)is true, and 0 otherwise. Lemma E.26 (Optimality probability inclusion relations).LetX,Y( R |S| be finite and suppose Y ′ ⊆Y. p D any (X≥Y)≤p D any ( X≥Y ′ ) ≤p D any ( X∪ ( Y ′ ) ≥Y ) .(45) If∃b < c : (b,c) |S| ⊆supp(D any ),X⊆Y, andND(Y)∩ ( Y ′ ) is non-empty, then the second inequality is strict. Proof. p D any (X≥Y) : =E r∼D any [ 1 max x∈X x > r≥max y∈Y y > r ] (46) ≤E r∼D any [ 1 max x∈X x > r≥max y∈Y ′ y > r ] (47) ≤E r∼D any [ 1 max x∈X∪(Y ′ ) x > r≥max y∈Y ′ y > r ] (48) =E r∼D any [ 1 max x∈X∪(Y ′ ) x > r≥max y∈Y ′ ∪(Y ′ ) y > r ] (49) =E r∼D any [ 1 max x∈X∪(Y ′ ) x > r≥max y∈Y y > r ] (50) = : p D any ( X∪ ( Y ′ ) ≥Y ) .(51) Equation (47) follows because∀r∈R |S| : 1 max x∈X x > r≥max y∈Y y > r ≤1 max x∈X x > r≥max y∈Y ′ y > r sinceY ′ ⊆Y; note that eq. (47) equalsp D any ( X≥Y ′ ) , and so the first inequality of eq. (45) is shown. Equation (48) holds because∀r∈R |S| : 1 max x∈X x > r≥max y∈Y ′ y > r ≤ 1 max x∈X∪(Y ′ ) x > r≥max y∈Y ′ b > r . Suppose∃b < c : (b,c) |S| ⊆supp(D any ),X⊆Y, andND(Y)∩ ( Y ′ ) is non-empty. Let y ∗ ∈ND(Y)∩ ( Y ′ ) . By proposition E.20,y ∗ is strictly optimal on a subset ofsupp(D any ) with positive measure underD any . In particular, for a set ofr ∗ with positive measure underD any , we havey ∗> r ∗ >max y∈Y ′ y > r ∗ . Then eq. (48) is strict, and therefore the second inequality of eq. (45) is strict as well. 26 Lemma E.27(Optimality probability of similar linear functional sets).LetA,B,C( R |S| be finite, and letZ⊆R |S| be such thatND(C)⊆Z⊆C. IfND(A)is similar toB ′ ⊆Bviaφsuch that φ· ( Z\ ( B ′ ) ) =Z\ ( B ′ ) , then p D any (A≥C)≤p φ·D any (B≥C).(52) IfB ′ =B, then eq.(52)is an equality. If∃b < c : (b,c) |S| ⊆supp(D any ),B ′ ⊆C, and ND(C)∩ ( B ′ ) is non-empty, then eq.(52)is strict. Proof. p D any (A≥C) =p D any (A≥Z)(53) =p D any ( ND(A)≥Z ) (54) ≤p D any ( ND(A)≥Z\ ( B ′ ) ) (55) =p φ·D any ( φ·ND(A)≥φ·Z\ ( B ′ ) ) (56) =p φ·D any ( B ′ ≥Z\ ( B ′ ) ) (57) ≤p φ·D any ( B ′ ∪ ( B ′ ) ≥Z ) (58) =p φ·D any (B≥C).(59) Equation (53) and eq. (59) follow by lemma E.12’s item 2 withX : =C,X ′ : =Z. Similarly, eq. (54) follows by lemma E.12’s item 2 withX : =A,X ′ : =ND(A). Equation (55) follows by applying the first inequality of lemma E.26 withX : =ND(A),Y : =Z,Y ′ : =Z\(B ′ ). Equation (56) follows by applying lemma E.17 to eq. (53) with permutationφ. Equation (57) follows by our assumptions onφ. Equation (58) follows because by applying the second inequality of lemma E.26 withX : =B ′ ,Y : =ND(C),Y ′ : =ND(C)\(B ′ ). SupposeB ′ =B. ThenB ′ =∅, and so eq. (55) and eq. (58) are trivially equalities. Then eq. (52) is an equality. Suppose∃b < c : (b,c) |S| ⊆supp(D any ); note that(b,c) |S| ⊆supp(φ·D any ), since such support must be invariant to permutation. Further suppose thatB ′ ⊆Cand thatND(C)∩ ( B ′ ) is non- empty. Then lettingX : =B ′ ,Y : =Z,Y ′ : =Z\(B ′ )and noting thatND ( ND(Z) ) =ND(Z), apply lemma E.26 to eq. (58) to conclude that eq. (52) is strict. Lemma E.28(Optimality probability superiority lemma).LetA,B,C( R |S| be finite, and letZ satisfyND(C)⊆Z⊆C. IfBcontains a copyB ′ ofND(A)viaφsuch thatφ· ( Z\ ( B ′ ) ) = Z\ ( B ′ ) , thenp D any (A≥C)≤ most:D any p D any (B≥C). IfB ′ ⊆CandND(C)∩ ( B ′ ) is non-empty, then the inequality is strict for allD X-IID ∈D C/B/IID andp D any (A≥C)6≥ most:D any p D any (B≥C). Proof.SupposeD any is such thatp D any (B≥C)< p D any (A≥C). p φ·D any (A≥C) =p φ −1 ·D any (A≥C)(60) ≤p D any (B≥C)(61) < p D any (A≥C)(62) ≤p φ·D any (B≥C).(63) Equation (60) holds becauseφis an involution.Equation (61) and eq. (63) hold by ap- plying lemma E.27 with permutationφ.Equation (62) holds by assumption.Therefore, p D any (A≥C)≤ most:D any p D any (B≥C)by lemma E.16. 27 SupposeB ′ ⊆CandND(C)∩ ( B ′ ) is non-empty, and letD X-IID be any continuous distribution which distributes reward independently and identically across states. Letφ ′ ∈S |S| . p φ ′ ·D X-IID (A≥C) =p D X-IID (A≥C)(64) < p φ·D X-IID (B≥C)(65) =p φ ′ ·D X-IID (A≥C).(66) Equation (64) and eq. (66) hold becauseD X-IID distributes reward identically across states,∀φ x ∈ S |S| : φ x ·D X-IID =D X-IID . By lemma E.22,∃b < c : (b,c) |S| ⊆supp(D X-IID ). Therefore, apply lemma E.27 to conclude that eq. (65) holds. Therefore,∀φ ′ ∈S |S| : p φ ′ ·D X-IID (A≥C)< p φ ′ ·D X-IID (B≥C).In particular, p D any (A≥C)6≥ most:D any p D any (B≥C)by definition 6.5. Lemma E.29(Limit probability inequalities which hold for most distributions).LetI⊆R, let D⊆∆(R |S| )be closed under permutation, and letF A ,F B ,F C be finite sets of vector functionsI7→ R |S| . Letγbe a limit point ofIsuch thatf 1 (D) : = lim γ ∗ →γ p D ( F B (γ ∗ )≥F C (γ ∗ ) ) ,f 2 (D) : = lim γ ∗ →γ p D ( F A (γ ∗ )≥F C (γ ∗ ) ) are well-defined for allD ∈D. LetF Z satisfyND(F C )⊆F Z ⊆F C . SupposeF B contains a copy ofF A viaφsuch thatφ· ( F Z \ ( F B \φ·F A ) ) =F Z \ ( F B \φ·F A ) . Thenf 2 (D)≤ most:D f 1 (D). Proof.SupposeD ∈Dis such thatf 2 (D)> f 1 (D). f 2 (φ·D) =f 2 ( φ −1 ·D ) (67) : = lim γ ∗ →γ p φ −1 ·D ( F A (γ ∗ )≥F C (γ ∗ ) ) (68) ≤lim γ ∗ →γ p D ( F B (γ ∗ )≥F C (γ ∗ ) ) (69) <lim γ ∗ →γ p D ( F A (γ ∗ )≥F C (γ ∗ ) ) (70) ≤lim γ ∗ →γ p φ·D ( F B (γ ∗ )≥F C (γ ∗ ) ) (71) = : f 1 (φ·D).(72) By the assumption thatDis closed under permutation andf 2 is well-defined for allD ∈D,f 2 (φ·D) is well-defined. Equation (67) follows sinceφ=φ −1 becauseφis an involution. For allγ ∗ ∈I, let A : =F A (γ ∗ ),B : =F B (γ ∗ ),C : =F C (γ ∗ ),Z : =F Z (γ ∗ ) (by definition E.13,ND(C)⊆Z⊆C). Sinceφ·A⊆Bby assumption, and sinceND(A)⊆A,Balso contains a copy ofND(A) viaφ. Furthermore,φ· ( Z\ ( B\φ·A ) ) =Z\ ( B\φ·A ) (by assumption), and so apply lemma E.27 to conclude thatp φ −1 ·D ( F A (γ ∗ )≥F C (γ ∗ ) ) ≤p D ( F B (γ ∗ )≥F C (γ ∗ ) ) . Therefore, the limit inequality eq. (69) holds. Equation (70) follows because we assumed thatf 1 (D)< f 2 (D). Equation (71) holds by reasoning similar to that given for eq. (69). Therefore,f 2 (D)> f 1 (D)implies thatf 2 (φ·D)< f 1 (φ·D), and so apply lemma E.16 to conclude thatf 2 (D)≤ most:D f 1 (D). E.1.3F nd results Proposition E.30(How to transfer optimal policy sets across discount rates).Suppose reward functionRhas optimal policy setΠ ∗ (R,γ)at discount rateγ∈(0,1). For anyγ ∗ ∈(0,1), we can construct a reward functionR ′ such thatΠ ∗ ( R ′ ,γ ∗ ) = Π ∗ (R,γ) . Furthermore,V ∗ R ′ (·,γ ∗ ) = V ∗ R (·,γ). Proof. LetRbe any reward function. Supposeγ ∗ ∈(0,1)and constructR ′ (s) : =V ∗ R (s,γ)− γ ∗ max a∈A E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] . 28 Letπ∈Πbe any policy. By the definition of optimal policies,π∈Π ∗ ( R ′ ,γ ∗ ) iff for alls: R ′ (s) +γ ∗ E s ′ ∼T ( s,π(s) ) [ V ∗ R ′ ( s ′ ,γ ∗ ) ] =R ′ (s) +γ ∗ max a∈A E s ′ ∼T(s,a) [ V ∗ R ′ ( s ′ ,γ ∗ ) ] (73) R ′ (s) +γ ∗ E s ′ ∼T ( s,π(s) ) [ V ∗ R ( s ′ ,γ ) ] =R ′ (s) +γ ∗ max a∈A E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] (74) γ ∗ E s ′ ∼T ( s,π(s) ) [ V ∗ R ( s ′ ,γ ) ] =γ ∗ max a∈A E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] (75) E s ′ ∼T ( s,π(s) ) [ V ∗ R ( s ′ ,γ ) ] = max a∈A E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] .(76) By the Bellman equations,R ′ (s) =V ∗ R ′ (s,γ ∗ )−γ ∗ max a∈A E s ′ ∼T(s,a) [ V ∗ R ′ ( s ′ ,γ ∗ ) ] . By the definition ofR ′ ,V ∗ R ′ (·,γ ∗ ) =V ∗ R (·,γ)must be the unique solution to the Bellman equations for R ′ atγ ∗ . Therefore, eq. (74) holds. Equation (75) follows by plugging inR ′ : =V ∗ R (s,γ)− γ ∗ max a∈A E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] to eq. (74) and doing algebraic manipulation. Equation (76) follows becauseγ ∗ >0. Equation (76) shows thatπ∈Π ∗ ( R ′ ,γ ∗ ) iff∀s : E s ′ ∼T(s,π(s)) [ V ∗ R ( s ′ ,γ ) ] = max a∈A E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] . That is,π∈Π ∗ ( R ′ ,γ ∗ ) iffπ∈Π ∗ (R,γ). Definition E.31(Evaluating sets of visit distribution functions atγ).Forγ∈(0,1), define F(s,γ) : = f(γ)|f∈F(s) andF nd (s,γ) : = f(γ)|f∈F nd (s) . IfF⊆ F(s), then F(γ) : = f(γ)|f∈F . Lemma E.32(Non-domination acrossγvalues for expectations of visit distributions).Let∆ d ∈ ∆ ( R |S| ) be any state distribution and letF : = E s d ∼∆ d [f π,s d ]|π∈Π .f∈ND(F)iff∀γ ∗ ∈ (0,1) : f(γ ∗ )∈ND ( F(γ ∗ ) ) . Proof.Letf π ∈ND(F)be strictly optimal for reward functionRat discount rateγ∈(0,1): f π (γ) > r>max f π ′ ∈F\f π f π ′ (γ) > r.(77) Letγ ∗ ∈(0,1). By proposition E.30, we can produceR ′ such thatΠ ∗ ( R ′ ,γ ∗ ) = Π ∗ (R,γ). Since the optimal policy sets are equal, lemma E.1 implies that f π (γ ∗ ) > r ′ >max f π ′ ∈F\f π f π ′ (γ ∗ ) > r ′ .(78) Therefore,f π (γ ∗ )∈ND ( F(γ ∗ ) ) . The reverse direction follows by the definition of ND(F). Lemma E.33(∀γ∈(0,1) : d∈F nd (s,γ)iffd∈ND ( F(s,γ) ) ). Proof. By definition E.31,F nd (s,γ) : = f(γ)|f∈ND ( F(s) ) . By applying lemma E.32 with ∆ d : =e s ,f∈ND ( F(s) ) iff∀γ∈(0,1) : f(γ)∈ND ( F(s,γ) ) . Lemma E.34(∀γ∈[0,1) : V ∗ R (s,γ) = max f∈F nd (s) f(γ) > r). Proof.ND ( F(s,γ) ) =F nd (s,γ)by lemma E.33, so apply corollary E.11 withX : =F(s,γ). 29 E.2 Some actions have greater probability of being optimal Lemma E.35(Optimal policy shift bound).For fixedR,Π ∗ (R,γ)can take on at most(2|S|+ 1) ∑ s ( | F(s) | 2 ) distinct values overγ∈(0,1). Proof.By lemma E.1,Π ∗ (R,γ)changes value iff there is a change in optimality status for some visit distribution function at some state. Lippman [1968] showed that two visit distribution functions can trade off optimality status at most2|S|+ 1times. At each states, there are ( | F(s) | 2 ) such pairs. Proposition E.36(Optimality probability’s limits exist).LetF⊆ F(s).P D any (F,0) = lim γ→0 P D any (F,γ)andP D any (F,1) = lim γ→1 P D any (F,γ). Proof. First consider the limit asγ→1. LetD any have probability measureF any , and define δ(γ) : =F any ( R∈R S |∃γ ∗ ∈[γ,1) : Π ∗ (R,γ ∗ )6= Π ∗ (R,1) ) . SinceF any is a probability measure,δ(γ)is bounded[0,1], andδ(γ)is monotone decreasing. Therefore,lim γ→1 δ(γ)exists. Iflim γ→1 δ(γ)>0, then there exist reward functions whose optimal policy setsΠ ∗ (R,γ)never converge (in the discrete topology on sets) toΠ ∗ (R,1), contradicting lemma E.35. Solim γ→1 δ(γ) = 0. By the definition of optimality probability (definition 4.3) and ofδ(γ),|P D any (F,γ)−P D any (F,1)|≤ δ(γ). Sincelim γ→1 δ(γ) = 0,lim γ→1 P D any (F,γ) =P D any (F,1). A similar proof shows thatlim γ→0 P D any (F,γ) =P D any (F,0). Lemma E.37(Optimality probability identity).Letγ∈(0,1)and letF⊆F(s). P D any (F,γ) =p D ′ ( F(γ)≥F(s,γ) ) =p D ′ ( F(γ)≥F nd (s,γ) ) .(79) Proof.Letγ∈(0,1). P D any (F,γ) : =P R∼D any ( ∃f π ∈F : π∈Π ∗ (R,γ) ) (80) =E r∼D any [ 1 max f∈F f(γ) > r=max f ′ ∈F(s) f ′ (γ) > r ] (81) =E r∼D any [ 1 max f∈F f(γ) > r=max f ′ ∈F nd (s) f ′ (γ) > r ] (82) = : p D ′ ( F(γ)≥F nd (s,γ) ) .(83) Equation (81) follows because lemma E.1 shows thatπis optimal iff it induces an optimal visit distributionfat every state. Equation (82) follows because∀r∈R |S| : max f ′ ∈F(s) f ′ (γ) > r= max f ′ ∈F nd (s) f ′ (γ) > rby lemma E.34. E.3 Basic properties of POWER Lemma E.38(POWERidentities).Letγ∈(0,1). POWER D bound (s,γ) =E r∼D bound [ max f∈F nd (s) 1−γ γ ( f(γ)−e s ) > r ] (84) = 1−γ γ E r∼D bound [ V ∗ R (s,γ)−R(s) ] (85) = 1−γ γ ( V ∗ D bound (s,γ)−E R∼D bound [ R(s) ] ) (86) =E R∼D bound max π∈Π E s ′ ∼T ( s,π(s) ) [ (1−γ)V π R ( s ′ ,γ ) ] .(87) 30 Proof. POWER D bound (s,γ) : =E r∼D bound [ max f∈F(s) 1−γ γ ( f(γ)−e s ) > r ] (88) =E r∼D bound [ max f∈F nd (s) 1−γ γ ( f(γ)−e s ) > r ] (89) =E r∼D bound [ max f∈F(s) 1−γ γ ( f(γ)−e s ) > r ] (90) = 1−γ γ E r∼D bound [ V ∗ R (s,γ)−R(s) ] (91) = 1−γ γ ( V ∗ D bound (s,γ)−E R∼D bound [ R(s) ] ) (92) =E r∼D bound max π∈Π E s ′ ∼T ( s,π(s) ) [ (1−γ)f π,s ′ (γ) > r ] (93) =E R∼D bound max π∈Π E s ′ ∼T ( s,π(s) ) [ (1−γ)V π R ( s ′ ,γ ) ] .(94) Equation (89) follows from lemma E.34. Equation (91) follows from the dual formulation of optimal value functions. Equation (92) holds by the definition ofV ∗ D bound (s,γ)(definition 5.1). Equation (93) holds becausef π,s (γ) =e s +γE s ′ ∼T ( s,π(s) ) [ f π,s ′ (γ) ] by the definition of a visit distribution function (definition 3.3). Definition E.39(Discount-normalized value function).Letπbe a policy,Ra reward function, ands a state. Forγ∈[0,1],V π R,norm (s,γ) : = lim γ ∗ →γ (1−γ ∗ )V π R (s,γ ∗ ). Lemma E.40 (Normalized value functions have uniformly bounded derivative).There existsK≥0 such that for all reward functionsr∈R |S| ,sup s∈S,π∈Π,γ∈[0,1] ∣ ∣ ∣ d dγ V π R,norm (s,γ) ∣ ∣ ∣ ≤K‖r‖ 1 . Proof. Letπbe any policy,sa state, andRa reward function. SinceV π R,norm (s,γ) = lim γ ∗ →γ (1− γ ∗ )f π,s (γ ∗ ) > r , d dγ V π R,norm (s,γ) is controlled by the behavior oflim γ ∗ →γ (1−γ ∗ )f π,s (γ ∗ ). We show that this function’s gradient is bounded in infinity norm. By lemma E.4,f π,s (γ)is a multivariate rational function onγ. Therefore, for any states ′ , f π,s (γ) > e s ′ = P(γ) Q(γ) in reduced form. By proposition E.3,0≤f π,s (γ) > e s ′ ≤ 1 1−γ . Thus, Qmay only have a root of multiplicity 1 atγ= 1, andQ(γ)6= 0forγ∈[0,1). Let f s ′ (γ) : = (1−γ)f π,s (γ) > e s ′ . IfQ(1)6= 0, then the derivativef ′ s ′ (γ)is bounded onγ∈[0,1)because the polynomial(1−γ)P(γ) cannot diverge on a bounded domain. IfQ(1) = 0, then factor out the root asQ(γ) = (1−γ)Q ∗ (γ). f ′ s ′ (γ) = d dγ ( (1−γ)P(γ) Q(γ) ) (95) = d dγ ( P(γ) Q ∗ (γ) ) (96) = P ′ (γ)Q ∗ (γ)−(Q ∗ ) ′ (γ)P(γ) (Q ∗ (γ)) 2 .(97) SinceQ ∗ (γ)is a polynomial with no roots onγ∈[0,1],f ′ s ′ (γ)is bounded onγ∈[0,1). 31 Therefore, whether or notQ(γ)has a root atγ= 1,f ′ s ′ (γ) is bounded onγ∈[0,1). Furthermore, sup γ∈[0,1) ∥ ∥ ∇(1−γ)f π,s (γ) ∥ ∥ ∞ = sup γ∈[0,1) max s ′ ∈S ∣ ∣ f ′ s ′ (γ) ∣ ∣ is finite since there are only finitely many states. There are finitely manyπ∈Π, and finitely many statess, and so there exists someK ′ such that sup s∈S, π∈Π,γ∈[0,1) ∥ ∥ ∇(1−γ)f π,s (γ) ∥ ∥ ∞ ≤K ′ . Then ∥ ∥ ∇(1−γ)f π,s (γ) ∥ ∥ 1 ≤|S|K ′ = : K. sup s∈S, π∈Π,γ∈[0,1) ∣ ∣ ∣ ∣ d dγ V π R,norm (s,γ) ∣ ∣ ∣ ∣ : =sup s∈S, π∈Π,γ∈[0,1) ∣ ∣ ∣ ∣ d dγ lim γ ∗ →γ (1−γ ∗ )V π R (s,γ ∗ ) ∣ ∣ ∣ ∣ (98) =sup s∈S, π∈Π,γ∈[0,1) ∣ ∣ ∣ ∣ d dγ (1−γ)V π R (s,γ) ∣ ∣ ∣ ∣ (99) =sup s∈S, π∈Π,γ∈[0,1) ∣ ∣ ∣ ∇(1−γ)f π,s (γ) > r ∣ ∣ ∣ (100) ≤sup s∈S, π∈Π,γ∈[0,1) ∥ ∥ ∇(1−γ)f π,s (γ) ∥ ∥ 1 ‖r‖ 1 (101) ≤K‖r‖ 1 .(102) Equation (99) holds becauseV π R (s,γ)is continuous onγ∈[0,1)by corollary E.5. Equation (101) holds by the Cauchy-Schwarz inequality. Since ∣ ∣ ∣ d dγ V π R,norm (s,γ) ∣ ∣ ∣ is bounded for allγ∈[0,1), eq. (102) also holds forγ→1. Lemma 5.3(Continuity of POWER).POWER D bound (s,γ)is Lipschitz continuous onγ∈[0,1]. Proof.Letb,cbe such thatsupp(D bound )⊆[b,c] |S| . For anyr∈supp(D bound )andπ∈Π, V π R,norm (s,γ) has Lipschitz constantK‖r‖ 1 ≤K|S|‖r‖ ∞ ≤K|S|max(|c|,|b|)onγ∈(0,1)by lemma E.40. Forγ∈(0,1),POWER D bound (s,γ) =E R∼D bound [ max π∈Π E s ′ ∼T ( s,π(s) ) [ (1−γ)V π R ( s ′ ,γ ) ] ] by eq. (94). The expectation of the maximum of a set of functions which share a Lipschitz constant, also shares the Lipschitz constant. This shows thatPOWER D bound (s,γ)is Lipschitz continuous on γ∈(0,1). Thus, its limits are well-defined asγ→0andγ→1. So it is Lipschitz continuous on the closed unit interval. Proposition 5.4(MaximalPOWER).POWER D bound (s,γ)≤E R∼D bound [ max s∈S R(s) ] , with equality ifscan deterministically reach all states in one step and all states are 1-cycles. Proof.Letγ∈(0,1). POWER D bound (s,γ) =E R∼D bound [ max π∈Π E s ′ ∼T(s,π(s)) [ (1−γ)V ∗ R ( s ′ ,γ ) ] ] (103) ≤E R∼D bound [ max π∈Π E s ′ ∼T(s,π(s)) [ (1−γ) max s ′ ∈S R(s ′ ) 1−γ ] ] (104) =E R∼D bound [ max s ′ ∈S R(s ′ ) ] .(105) Equation (103) follows from lemma E.38.Equation (104) follows becauseV ∗ R ( s ′ ,γ ) ≤ max s ′ ∈S R(s ′ ) 1−γ , as no policy can do better than achieving maximal reward at each time step. Taking limits, the inequality holds for allγ∈[0,1]. Suppose thatscan deterministically reach all states in one step and all states are 1-cycles. Then eq. (104) is an equality for allγ∈(0,1), since for eachR, the agent can select an action which 32 deterministically transitions to a state with maximal reward. Thus the equality holds for allγ∈ [0,1]. Lemma E.41(Lower bound on current POWERbased on future POWER). POWER D bound (s,γ)≥(1−γ) min a E s ′ ∼T(s,a), R∼D bound [ R(s ′ ) ] +γmax a E s ′ ∼T(s,a) [ POWER D bound ( s ′ ,γ ) ] . (106) Proof.Letγ∈(0,1)and leta ∗ ∈arg max a E s ′ ∼T(s,a) [ POWER D bound ( s ′ ,γ ) ] . POWER D bound (s,γ)(107) = (1−γ)E R∼D bound [ max a E s ′ ∼T(s,a) [ V ∗ R ( s ′ ,γ ) ] ] (108) ≥(1−γ) max a E s ′ ∼T(s,a) [ E R∼D bound [ V ∗ R ( s ′ ,γ ) ] ] (109) = (1−γ) max a E s ′ ∼T(s,a) [ V ∗ D bound ( s ′ ,γ ) ] (110) = (1−γ) max a E s ′ ∼T(s,a) [ E R∼D bound [ R(s ′ ) ] + γ 1−γ POWER D bound ( s ′ ,γ ) ] (111) ≥(1−γ)E s ′ ∼T(s,a ∗ ) [ E R∼D bound [ R(s ′ ) ] + γ 1−γ POWER D bound ( s ′ ,γ ) ] (112) ≥(1−γ) min a E s ′ ∼T(s,a), R∼D bound [ R(s ′ ) ] +γE s ′ ∼T(s,a ∗ ) [ POWER D bound ( s ′ ,γ ) ] .(113) Equation (108) holds by lemma E.38. Equation (109) follows becauseE x∼X [ max a f(a,x) ] ≥ max a E x∼X [ f(a,x) ] by Jensen’s inequality, and eq. (111) follows by lemma E.38. The inequality also holds when we take the limitsγ→0orγ→1. Proposition 5.5(POWERis smooth across reversible dynamics).LetD bound be bounded[b,c]. Sup- posesands ′ can both reach each other in one step with probability 1. ∣ ∣ POWER D bound (s,γ)−POWER D bound ( s ′ ,γ ) ∣ ∣ ≤(c−b)(1−γ).(3) Proof.Supposeγ∈[0,1]. First consider the case where POWER D bound (s,γ)≥POWER D bound ( s ′ ,γ ) . POWER D bound ( s ′ ,γ ) ≥(1−γ) min a E s x ∼T(s ′ ,a), R∼D bound [ R(s x ) ] +γmax a E s x ∼T(s ′ ,a) [ POWER D bound (s x ,γ) ] (114) ≥(1−γ)b+γPOWER D bound (s,γ).(115) Equation (114) follows by lemma E.41. Equation (115) follows because reward is lower-bounded by band becauses ′ can reachsin one step with probability 1. ∣ ∣ ∣ POWER D bound (s,γ)−POWER D bound ( s ′ ,γ ) ∣ ∣ ∣ =POWER D bound (s,γ)−POWER D bound ( s ′ ,γ ) (116) ≤POWER D bound (s,γ)− ( (1−γ)b+γPOWER D bound (s,γ) ) (117) = (1−γ) ( POWER D bound (s,γ)−b ) (118) ≤(1−γ) ( E R∼D bound [ max s ′ ∈S R(s ′ ) ] −b ) (119) ≤(1−γ)(c−b).(120) 33 Equation (116) follows becausePOWER D bound (s,γ)≥POWER D bound ( s ′ ,γ ) . Equation (117) follows by eq. (115). Equation (119) follows by proposition 5.4. Equation (120) follows because reward underD bound is upper-bounded byc. The case wherePOWER D bound (s,γ)≤POWER D bound ( s ′ ,γ ) is similar, leveraging the fact thatscan also reachs ′ in one step with probability 1. E.4 Seeking POWERis often more probable under optimality E.4.1 Keeping options open tends to be POWER-seeking and tends to be optimal Definition E.42(Normalized visit distribution function).Letf : [0,1)→R |S| be a vector function. Forγ∈[0,1],NORM(f,γ) : = lim γ ∗ →γ (1−γ ∗ )f(γ ∗ )(this limit need not exist for arbitraryf). If Fis a set of suchf, then NORM(F,γ) : = NORM(f,γ)|f∈F . Remark.RSD(s) =NORM ( F(s),1 ) . Lemma E.43 (Normalized visit distribution functions are continuous).Let∆ s ∈∆(S)be a state probability distribution, letπ∈Π, and letf ∗ : =E s∼∆ s [f π,s ].NORM(f ∗ ,γ)is continuous on γ∈[0,1]. Proof. NORM(f ∗ ,γ) : = lim γ ∗ →γ (1−γ ∗ )E s∼∆ s [ f π,s (γ ∗ ) ] (121) =E s∼∆ s [ lim γ ∗ →γ (1−γ ∗ )f π,s (γ ∗ ) ] (122) = : E s∼∆ s [ NORM(f π,s ,γ) ] .(123) Equation (122) follows because the expectation is over a finite set. Eachf π,s ∈F(s)is continuous onγ∈[0,1)by lemma E.4, andlim γ ∗ →1 (1−γ ∗ )f π,s (γ ∗ )exists becauseRSDs are well-defined [Puterman, 2014]. Therefore, eachNORM(f π,s ,γ)is continuous onγ∈[0,1]. Lastly, eq. (123)’s expectation over finitely many continuous functions is itself continuous. Lemma E.44(Non-domination of normalized visit distribution functions).Let∆ s ∈∆(S) be a state probability distribution and letF : = E s∼∆ s [f π,s ]|π∈Π . For allγ∈[0,1], ND ( NORM(F,γ) ) ⊆NORM ( ND(F),γ ) , with equality whenγ∈(0,1). Proof.Supposeγ∈(0,1). ND ( NORM(F,γ) ) =ND ( (1−γ)F(γ) ) (124) = (1−γ)ND ( F(γ) ) (125) = (1−γ) ( ND(F) (γ) ) (126) =NORM ( ND(F),γ ) .(127) Equation (124) and eq. (127) follow by the continuity ofNORM(f,γ)(lemma E.43). Equation (125) follows by lemma E.15 item 1. Equation (126) follows by lemma E.32. Letγ= 1. Letd∈ND ( NORM(F,1) ) be strictly optimal forr ∗ ∈R |S| . Then letF d ⊆Fbe the subset off∈Fsuch that NORM(f,1) =d. max f∈F d NORM(f,1) > r ∗ >max f ′ ∈F d NORM ( f ′ ,1 ) > r ∗ .(128) SinceNORM(f,1)is continuous atγ= 1(lemma E.43),x > r ∗ is continuous onx∈R |S| , andF is finite, eq. (128) holds for someγ ∗ ∈(0,1)sufficiently close toγ= 1. By lemma E.10, at least onef∈F d is an element ofND ( F(γ ∗ ) ) . Then by lemma E.32,f∈ND(F). We conclude that ND ( NORM(F,1) ) ⊆NORM ( ND(F),1 ) . The case forγ= 0proceeds similarly. 34 Lemma E.45(POWERlimit identity).Letγ∈[0,1]. POWER D bound (s,γ) =E r∼D bound [ max f∈F nd (s) lim γ ∗ →γ 1−γ ∗ γ ∗ ( f(γ ∗ )−e s ) > r ] .(129) Proof.Letγ∈[0,1]. POWER D bound (s,γ) = lim γ ∗ →γ POWER D bound (s,γ ∗ )(130) = lim γ ∗ →γ E r∼D bound [ max f∈F nd (s) 1−γ ∗ γ ∗ ( f(γ ∗ )−e s ) > r ] (131) =E r∼D bound [ lim γ ∗ →γ max f∈F nd (s) 1−γ ∗ γ ∗ ( f(γ ∗ )−e s ) > r ] (132) =E r∼D bound [ max f∈F nd (s) lim γ ∗ →γ 1−γ ∗ γ ∗ ( f(γ ∗ )−e s ) > r ] .(133) Equation (130) follows becausePOWER D bound (s,γ)is continuous onγ∈[0,1]by lemma 5.3. Equation (131) follows by lemma E.38. Forγ ∗ ∈(0,1), letf γ ∗ (r) : = max f∈F nd (s) 1−γ ∗ γ ∗ ( f(γ ∗ )−e s ) > r . For any sequenceγ n →γ, ( f γ n ) ∞ n=1 is a sequence of functions which are piecewise linear onr∈R |S| , which means they are continuous and therefore measurable. Since lemma E.4 shows that eachf∈F nd (s)is multivariate rational onγ ∗ (and therefore continuous onγ ∗ ), f γ n ∞ n=1 converges pointwise to limit functionf γ . Furthermore, ∣ ∣ V ∗ R (s,γ n )−R(s) ∣ ∣ ≤ γ 1−γ n ‖R‖ ∞ , and so ∣ ∣ f γ n (r) ∣ ∣ = ∣ ∣ ∣ 1−γ n γ n (V ∗ R (s,γ n )−R(s)) ∣ ∣ ∣ ≤ g(r)≤‖r‖ ∞ = : g(r) , which is measurable. Therefore, apply Lebesgue’s dominated convergence theorem to conclude that eq. (132) holds. Equation (133) holds becausemaxis a continuous function. Lemma E.46(Lemma forPOWERsuperiority).Let∆ 1 ,∆ 2 ∈∆ (S)be state probability dis- tributions. Fori= 1,2, letF ∆ i : = γ −1 E s i ∼∆ i [f π,s i −e s i ]|π∈Π . SupposeF ∆ 2 con- tains a copy ofND(F ∆ 1 )viaφ. Then∀γ∈[0,1] : E s 1 ∼∆ 1 [ POWER D bound (s 1 ,γ) ] ≤ most:D bound E s 2 ∼∆ 2 [ POWER D bound (s 2 ,γ) ] . IfND(F ∆ 2 )\φ·ND(F ∆ 1 ) is non-empty, then for allγ∈(0,1), the inequality is strict for all D X-IID ∈D C/B/IID andE s 1 ∼∆ 1 [ POWER D bound (s 1 ,γ) ] 6≥ most:D bound E s 2 ∼∆ 2 [ POWER D bound (s 2 ,γ) ] . These results also hold when replacingF ∆ i withF ∗ ∆ i : = E s i ∼∆ i [f π,s i ]|π∈Π fori= 1,2. Proof. φ·ND ( NORM(F ∆ 1 ,γ) ) ⊆φ·NORM ( ND(F ∆ 1 ),γ ) (134) : = P φ lim γ ∗ →γ (1−γ ∗ )f(γ ∗ )|f∈ND(F ∆ 1 ) (135) = lim γ ∗ →γ (1−γ ∗ )P φ f(γ ∗ )|f∈ND(F ∆ 1 ) (136) = lim γ ∗ →γ (1−γ ∗ )f(γ ∗ )|f∈F ′ sub (137) ⊆ lim γ ∗ →γ (1−γ ∗ )f(γ ∗ )|f∈F ∆ 2 (138) = : NORM(F ∆ 2 ,γ).(139) Equation (134) follows by lemma E.44. Equation (136) follows becauseP φ is a continuous linear operator. Equation (138) follows by assumption. E s 1 ∼∆ 1 [ POWER D bound (s 1 ,γ) ] : =E s 1 ∼∆ 1 , r∼D bound [ max π∈Π lim γ ∗ →γ 1−γ ∗ γ ∗ ( f π,s 1 (γ ∗ )−e s 1 ) > r ] (140) 35 =E r∼D bound [ max π∈Π lim γ ∗ →γ 1−γ ∗ γ ∗ E s 1 ∼∆ 1 [ f π,s 1 (γ ∗ )−e s 1 ] > r ] (141) =E r∼D bound max d∈NORM ( F ∆ 1 ,γ ) d > r (142) =E r∼D bound max d∈ND ( NORM ( F ∆ 1 ,γ ) ) d > r (143) ≤ most:D bound E r∼D bound max d∈NORM ( F ∆ 2 ,γ ) d > r (144) =E r∼D bound [ max π∈Π lim γ ∗ →γ 1−γ ∗ γ ∗ E s 2 ∼∆ 2 [ f π,s 2 (γ ∗ )−e s 2 ] > r ] (145) =E s 2 ∼∆ 2 , r∼D bound [ max π∈Π lim γ ∗ →γ 1−γ ∗ γ ∗ ( f π,s 2 (γ ∗ )−e s 2 ) > r ] (146) = : E s 2 ∼∆ 2 [ POWER D bound (s 2 ,γ) ] .(147) Equation (140) and eq. (147) follow by lemma E.45. Equation (141) and eq. (146) follow because eachRhas a stationary deterministic optimal policyπ∈Π ∗ (R,γ)⊆Πwhich simultaneously achieves optimal value at all states. Equation (143) follows by corollary E.11. Apply lemma E.24 withA : =NORM(F ∆ 1 ,γ),B : =NORM(F ∆ 2 ,γ) ,gthe identity function, and involutionφ(satisfyingφ·ND(A)⊆Bby eq. (139)) in order to conclude that eq. (144) holds. Suppose thatND(F ∆ 2 )\φ·ND(F ∆ 1 )is non-empty; letF ′ sub : =φ·ND(F ∆ 1 ). Lemma E.32 shows that for allγ∈(0,1),ND ( F ∆ 2 (γ) ) ′ sub (γ)is non-empty. Lemma E.15 item 1 then im- plies thatND(B)\φ·A= 1−γ γ ( ND ( F ∆ 2 (γ) ) −e s ) \ ( 1−γ γ F ′ sub (γ) ) is non-empty. Then lemma E.24 implies that for allγ∈(0,1), eq. (144) is strict for allD X-IID ∈D C/B/IID and E s 1 ∼∆ 1 [ POWER D bound (s 1 ,γ) ] 6≥ most:D bound E s 2 ∼∆ 2 [ POWER D bound (s 2 ,γ) ] . We show that this result’s preconditions holding forF ∗ ∆ i implies theF ∆ i preconditions. Suppose F ∗ ∆ i : = E s i ∼∆ i [f π,s i ]|π∈Π fori= 1,2are such thatF ∗ sub : =φ·ND ( F ∗ ∆ 1 ) ⊆F ∗ ∆ 2 . In the following, the∆ i are represented as vectors inR |S| , andγis a variable. φ· γf|f∈ND(F ∆ 1 ) =φ· ( ND ( F ∗ ∆ 1 −∆ 1 ) ) (148) =φ· ( ND ( F ∗ ∆ 1 ) −∆ 1 ) (149) = P φ f−P φ ∆ 1 |f∈ND ( F ∗ ∆ 1 ) (150) ⊆ f−∆ 2 |f∈F ∗ ∆ 2 (151) = γf|f∈F ∆ 2 .(152) Equation (149) follows from lemma E.15 item 2. Since we assumed thatφ·ND ( F ∗ ∆ 1 ) ⊆F ∗ ∆ 2 , φ·∆ 1 =φ· ( ND ( F ∗ ∆ 1 ) (0) ) ⊆F ∗ ∆ 2 (0) =∆ 2 . This implies thatP φ ∆ 1 = ∆ 2 and so eq. (151) follows. Equation (152) shows thatφ· γf|f∈ND(F ∆ 1 ) ⊆ γf|f∈F ∆ 2 .But we then haveφ· γf|f∈ND(F ∆ 1 ) : = γP φ f|f∈ND(F ∆ 1 ) = γf|f∈φ·ND(F ∆ 1 ) ⊆ γf|f∈F ∆ 2 . Thus,φ·ND(F ∆ 1 )⊆F ∆ 2 . 36 Suppose ND ( F ∗ ∆ 2 ) \φ·ND ( F ∗ ∆ 1 ) is non-empty, which implies that φ· γf|f∈ND(F ∆ 1 ) = P φ f−P φ ∆ 1 |f∈ND ( F ∗ ∆ 1 ) (153) = f−P φ ∆ 1 |f∈φ·ND ( F ∗ ∆ 1 ) (154) ( f−∆ 2 |f∈ND ( F ∗ ∆ 2 ) (155) = γf|f∈ND(F ∆ 2 ) .(156) ThenND(F ∆ 2 )\φ·ND(F ∆ 1 )must be non-empty. Therefore, if the preconditions of this result are met forF ∗ ∆ i , they are met forF ∆ i . Proposition 6.6(States with “more options” have morePOWER).IfF(s)contains a copy ofF nd (s ′ ) viaφ, then∀γ∈[0,1] : POWER D bound (s,γ)≥ most POWER D bound (s ′ ,γ). IfF nd (s)\φ·F nd (s ′ )is non-empty, then for allγ∈(0,1), the converse≤ most statement does not hold. Proof. LetF sub : =φ· F nd (s ′ )⊆ F(s) . Let∆ 1 : =e s ′ ,∆ 2 : =e s , and defineF ∗ ∆ i : = E s i ∼∆ i [f π,s i ]|π∈Π fori= 1,2.ThenF nd (s ′ ) =ND ( F ∗ ∆ 1 ) is similar toF sub = F ∗ sub ⊆F ∗ ∆ 2 =F(s)via involutionφ. Apply lemma E.46 to conclude that∀γ∈[0,1] : POWER D bound ( s ′ ,γ ) ≤ most:D bound POWER D bound (s,γ). Furthermore,F nd (s) =ND ( F ∗ ∆ 2 ) , andF sub =F ∗ sub , and so ifF nd (s)\φ·F nd (s ′ ) : =F nd (s)\ F sub =ND ( F ∗ ∆ 2 ) ∗ sub is non-empty, then lemma E.46 shows that for allγ∈(0,1), the inequality is strict for allD X-IID ∈D C/B/IID and POWER D bound ( s ′ ,γ ) 6≥ most:D bound POWER D bound (s,γ). Lemma E.47(Non-dominated visit distribution functions never agree with other visit distribution functions at that state).Letf∈F nd (s),f ′ ∈F(s)\f.∀γ∈(0,1) : f(γ)6=f ′ (γ). Proof. Letγ∈(0,1). Sincef∈F nd (s), there exists aγ ∗ ∈(0,1)at whichfis strictly optimal for some reward function. Then by proposition E.30, we can produce another reward function for which fis strictly optimal at discount rateγ; in particular, proposition E.30 guarantees that the policies which inducef ′ are not optimal atγ. Sof(γ)6=f ′ (γ). Corollary E.48(Cardinality of non-dominated visit distributions).LetF⊆ F(s).∀γ∈(0,1) : ∣ ∣ F∩F nd (s) ∣ ∣ = ∣ ∣ F(γ)∩F nd (s,γ) ∣ ∣ . Proof. Letγ∈(0,1). By applying lemma E.32 with∆ d : =e s ,f∈ F nd (s) =ND ( F(s) ) iff f(γ)∈ND ( F(s,γ) ) . By lemma E.33,ND ( F(s,γ) ) =F nd (s,γ). So allf∈F∩F nd (s)induce f(γ)∈F(γ)∩F nd (s,γ), and ∣ ∣ F∩F nd (s) ∣ ∣ ≥ ∣ ∣ F(γ)∩F nd (s,γ) ∣ ∣ . Lemma E.47 implies that for allf,f ′ ∈F nd (s),f=f ′ ifff(γ) =f ′ (γ). Therefore, ∣ ∣ F∩F nd (s) ∣ ∣ ≤ ∣ ∣ F(γ)∩F nd (s,γ) ∣ ∣ . So ∣ ∣ F∩F nd (s) ∣ ∣ = ∣ ∣ F(γ)∩F nd (s,γ) ∣ ∣ . Lemma E.49(Optimality probability and state bottlenecks).Suppose thatscan reach REACH ( s ′ ,a ′ ) ∪REACH ( s ′ ,a ) , but only by taking actions equivalent toa ′ oraat states ′ . F nd,a ′ : =F nd (s|π(s ′ ) =a ′ ),F a : =F(s|π(s ′ ) =a). SupposeF a contains a copy ofF nd,a ′ viaφwhich fixes all states not belonging toREACH ( s ′ ,a ′ ) ∪REACH ( s ′ ,a ) . Then ∀γ∈[0,1] : P D any ( F nd,a ′ ,γ ) ≤ most:D any P D any (F a ,γ). IfF nd (s)∩ ( F a \φ·F nd,a ′ ) is non-empty, then for allγ∈(0,1), the inequality is strict for all D X-IID ∈D C/B/IID , andP D any ( F nd,a ′ ,γ ) 6≥ most:D any P D any (F a ,γ). 37 Proof.LetF sub : =φ·F nd,a ′ . LetF ∗ : = ⋃ a ′ ∈A : ( a ′ 6≡ s ′ a ) ∧ ( a ′ 6≡ s ′ a ′ ) F(s|π(s ′ ) =a ′ )∪F nd,a ′ ∪F sub . φ·F ∗ : =φ· ⋃ a ′ ∈A : ( a ′ 6≡ s ′ a ) ∧ ( a ′ 6≡ s ′ a ′ ) F(s|π(s ′ ) =a ′ )∪F nd,a ′ ∪F sub (157) = ⋃ a ′ ∈A : ( a ′ 6≡ s ′ a ) ∧ ( a ′ 6≡ s ′ a ′ ) φ·F(s|π(s ′ ) =a ′ )∪ ( φ·F nd,a ′ ) ∪(φ·F sub )(158) = ⋃ a ′ ∈A : ( a ′ 6≡ s ′ a ) ∧ ( a ′ 6≡ s ′ a ′ ) φ·F(s|π(s ′ ) =a ′ )∪F sub ∪F nd,a ′ (159) = ⋃ a ′ ∈A : ( a ′ 6≡ s ′ a ) ∧ ( a ′ 6≡ s ′ a ′ ) F(s|π(s ′ ) =a ′ )∪F sub ∪F nd,a ′ (160) = : F ∗ .(161) Equation (159) follows because the involutionφensures thatφ·F sub =F nd,a ′ . By assumption,φ fixes alls ′ 6∈REACH ( s ′ ,a ′ ) ∪REACH ( s ′ ,a ) . Supposef∈F(s)\ ( F nd,a ′ ∪F a ) . By the bottleneck assumption,fdoes not visit states inREACH ( s ′ ,a ′ ) ∪REACH ( s ′ ,a ) . Therefore,P φ f=f, and so eq. (160) follows. LetF Z : = ( F(s)\(F(s|π(s) =a ′ )∪F a ) ) ∪F nd,a ′ ∪F a . By definition,F Z ⊆F(s). Furthermore, F nd (s) = ⋃ a ′ ∈A F nd (s|π(s ′ ) =a ′ )⊆ ( F(s)\(F(s|π(s) =a ′ )∪F a ) ) ∪F nd (s|π(s) = a ′ )∪F a = : F Z , and soF nd (s)⊆F Z . Note thatF ∗ =F Z \(F a sub ). Case:γ∈(0,1). P D any ( F nd,a ′ ,γ ) =p D any ( F nd,a ′ (γ)≥F(s,γ) ) (162) ≤ most:D any p D any ( F a (γ)≥F(s,γ) ) (163) =P D any ( F nd,a ′ ,γ ) .(164) Equation (162) and eq. (164) follow from lemma E.37. Equation (163) follows by applying lemma E.28 withA : =F nd,a ′ (γ),B ′ : =F sub (γ),B : =F a (γ),C : =F(s,γ),Z : =F Z (γ) which satisfiesND(C) =F nd (s,γ)⊆F Z (γ)⊆ F(s,γ) =C, and involutionφwhich satis- fiesφ·F ∗ (γ) =φ· ( Z\ ( B ′ ) ) =Z\ ( B ′ ) =F ∗ (γ). SupposeF nd (s)∩ ( F a sub ) is non-empty.0< ∣ ∣ ∣ F nd (s)∩ ( F a sub ) ∣ ∣ ∣ = ∣ ∣ ∣ F nd (s,γ)∩ ( F a (γ) sub (γ) ) ∣ ∣ ∣ = : ∣ ∣ ∣ ND(C)∩ ( B ′ ) ∣ ∣ ∣ (with the first equality hold- ing by corollary E.48), and soND(C)∩ ( B ′ ) is non-empty.We also have B : =F a (γ)⊆ F(s,γ) = : C.Then reapplying lemma E.28, eq. (163) is strict for all D X-IID ∈D C/B/IID , andP D any ( F nd,a ′ ,γ ) 6≥ most:D any P D any (F a ,γ). Case:γ= 1,γ= 0. P D any ( F nd,a ′ ,1 ) = lim γ ∗ →1 P D any ( F nd,a ′ ,γ ∗ ) (165) = lim γ ∗ →1 p D any ( F nd,a ′ (γ ∗ )≥F(s,γ ∗ ) ) (166) ≤ most:D any lim γ ∗ →1 p D any ( F a (γ ∗ )≥F(s,γ ∗ ) ) (167) = lim γ ∗ →1 P D any (F a ,γ ∗ )(168) 38 =P D any (F a ,1).(169) Equation (165) and eq. (169) hold by proposition E.36. Equation (166) and eq. (168) follow by lemma E.37. Applying lemma E.29 withγ : = 1,I : = (0,1),F A : =F nd,a ′ ,F B : =F a ,F C : =F(s), F Z as defined above, and involutionφ(for whichφ· ( F Z \ ( F B \φ·F A ) ) =F Z \ ( F B \φ·F A ) ), we conclude that eq. (167) follows. Theγ= 0case proceeds similarly toγ= 1. Lemma E.50(Action optimality probability is a special case of visit distribution optimality probabil- ity).P D any (s,a,γ) =P D any ( F(s|π(s) =a),γ ) . Proof.LetF a : =F(s|π(s) =a). Forγ∈(0,1), P D any (s,a,γ) : =P R∼D any ( ∃π ∗ ∈Π ∗ (R,γ) : π ∗ (s) =a ) (170) =P r∼D any ( ∃f π ∗ ,s ∈F a : f π ∗ ,s (γ) > r= max f∈F(s) f(γ) > r ) (171) =P D any (F a ,γ).(172) By lemma E.1, if∃π ∗ ∈Π ∗ (R,γ) : π ∗ (s) =a, then it induces some optimalf π ∗ ,s ∈F a . Conversely, iff π ∗ ,s ∈F a is optimal atγ∈(0,1), thenπ ∗ chooses optimal actions on the support off π ∗ ,s (γ). Let π ′ agree withπ ∗ on that support and letπ ′ take optimal actions at all other states. Thenπ ′ ∈Π ∗ (R,γ) andπ ′ (s) =a. So eq. (171) follows. Supposeγ= 0orγ= 1. Consider any sequence(γ n ) ∞ n=1 converging toγ, and letD any induce probability measureF. P D any (F a ,γ) : = lim γ ∗ →γ P D any (F a ,γ ∗ )(173) = lim γ ∗ →γ P R∼D any ( ∃π ∗ ∈Π ∗ (R,γ ∗ ) : π ∗ (s) =a ) (174) = lim n→∞ P R∼D any ( ∃π ∗ ∈Π ∗ (R,γ n ) : π ∗ (s) =a ) (175) = lim n→∞ ∫ R S 1 ∃π ∗ ∈Π ∗ (R,γ n ) : π ∗ (s)=a dF(R)(176) = ∫ R S lim n→∞ 1 ∃π ∗ ∈Π ∗ (R,γ n ) : π ∗ (s)=a dF(R)(177) = ∫ R S 1 ∃π ∗ ∈Π ∗ (R,γ) : π ∗ (s)=a dF(R)(178) = : P D any (s,a,γ).(179) Equation (174) follows by eq. (172). forγ ∗ ∈[0,1], letf γ ∗ (R) : =1 ∃π ∗ ∈Π ∗ (R,γ ∗ ) : π ∗ (s)=a . For eachR∈R S , lemma E.35 existsγ x ≈γsuch that for all intermediateγ ′ x betweenγ x andγ, Π ∗ ( R,γ ′ x ) = Π ∗ (R,γ) . Sinceγ n →γ, this means that ( f γ n ) ∞ n=1 converges pointwise tof γ . Furthermore,∀n∈N,R∈R S : ∣ ∣ f γ n (R) ∣ ∣ ≤1 by definition. Therefore, eq. (177) follows by Lebesgue’s dominated convergence theorem. Proposition 6.9(Keeping options open tends to be POWER-seeking and tends to be optimal). SupposeF a : =F(s|π(s) =a)contains a copy ofF a ′ : =F(s|π(s) =a ′ )viaφ. 1.Ifs6∈REACH ( s,a ′ ) , then∀γ∈[0,1] : E s a ∼T(s,a) [ POWER D bound (s a ,γ) ] ≥ most:D bound E s a ′ ∼T(s,a ′ ) [ POWER D bound (s a ′ ,γ) ] . 2. Ifscan only reach the states ofREACH ( s,a ′ ) ∪REACH(s,a) by taking actions equivalent toa ′ oraat states, then∀γ∈[0,1] : P D any (s,a,γ)≥ most:D any P D any ( s,a ′ ,γ ) . 39 IfF nd (s)∩ ( F a \φ·F a ′ ) is non-empty, then∀γ∈(0,1), the converse≤ most statements do not hold. Proof.Note that by definition 3.3,F a ′ (0) =e s =F a (0) . Sinceφ·F a ′ ⊆F a , in particular we haveφ·F a ′ (0) = P φ e s ⊆e s =F a (0), and soφ(s) =s. Item 1.For state probability distribution∆ s ∈∆(S), letF ∗ ∆ s : = E s ′ ∼∆ s [ f π,s ′ ] |π∈Π . Unless otherwise stated, we treatγas a variable in this item; we apply element-wise vector addition, constant multiplication, and variable multiplication via the conventions outlined in definition E.14. F a ′ = e s +γE s a ′ ∼T(s,a ′ ) [f π,s a ′ ]|π∈Π : π(s) =a ′ (180) = e s +γE s a ′ ∼T(s,a ′ ) [f π,s a ′ ]|π∈Π (181) =e s +γF ∗ T(s,a ′ ) .(182) Equation (180) follows by definition 3.3, since eachf∈F(s)has an initial term ofe s . Equation (181) follows becauses6∈REACH ( s,a ′ ) , and so for alls a ′ ∈supp(T(s,a ′ )),f π,s a ′ is unaffected by the choice of actionπ(s). Note that similar reasoning implies thatF a ⊆e s +γF ∗ T(s,a) (because eq. (181) is a containment relation in general). SinceF a ′ =e s +γF ∗ T(s,a ′ ) , ifF a contains a copy ofF a ′ viaφ, thenF ∗ T(s,a) contains a copy of F ∗ T(s,a ′ ) viaφ. Thenφ·ND ( F ∗ T(s,a ′ ) ) ⊆φ·F ∗ T(s,a ′ ) ⊆F ∗ T(s,a) , and soF ∗ T(s,a) contains a copy of ND ( F ∗ T(s,a ′ ) ) . Then apply lemma E.46 with∆ 1 : =T(s,a ′ ) and∆ 2 : =T(s,a) to conclude that ∀γ∈[0,1] : E s a ′ ∼T(s,a ′ ) [ POWER D bound (s a ′ ,γ) ] ≤ most:D bound E s a ∼T(s,a) [ POWER D bound (s a ,γ) ] . SupposeF nd (s)∩ ( F a \φ·F a ′ ) is non-empty. To apply the second condition of lemma E.46, we want to demonstrate that ND ( F ∗ T(s,a) ) \φ·ND ( F ∗ T(s,a ′ ) ) is also non-empty. First considerf∈F nd (s)∩F a . BecauseF a ⊆e s +γF ∗ T(s,a) , we have thatγ −1 (f−e s )∈F ∗ T(s,a) . Becausef∈F nd (s), by definition 3.6,∃r∈R |S| ,γ x ∈(0,1)such that f(γ x ) > r>max f ′ ∈F(s)\f f ′ (γ x ) > r.(183) Then sinceγ x ∈(0,1), γ −1 x (f(γ x )−e s ) > r>max f ′ ∈F(s)\f γ −1 x (f ′ (γ x )−e s ) > r(184) =max f ′ ∈γ −1 x ( (F(s)\f)−e s ) f ′ (γ x ) > r(185) ≥max f ′ ∈γ −1 x ( (F a \f)−e s ) f ′ (γ x ) > r(186) =max f ′ ∈F ∗ T(s,a) \ γ −1 x (f−e s ) f ′ (γ x ) > r.(187) Equation (186) holds becauseF a ⊆ F(s). By assumption, actionais optimal forrat statesand at discount rateγ x . Equation (181) shows thatF ∗ T(s,a) potentially allows the agent a non-stationary policy choice ats, but non-stationary policies cannot increase optimal value [Puterman, 2014]. Therefore, eq. (187) holds. We assumed thatγ −1 (f−e s )∈γ −1 (F nd (s)−e s ). Furthermore, since we just showed that γ −1 (f−e s )∈F ∗ T(s,a) is strictly optimal over the other elements ofF ∗ T(s,a) for reward functionr at discount rateγ x ∈(0,1), we conclude that it is an element ofND ( F ∗ T(s,a) ) by definition E.13. Then we conclude thatγ −1 (F nd (s)−e s )∩F ∗ T(s,a) ⊆ND ( F ∗ T(s,a) ) . 40 We now show that ND ( F ∗ T(s,a) ) \φ·ND ( F ∗ T(s,a ′ ) ) is non-empty. 0< ∣ ∣ ∣ F nd (s)∩ ( F a \φ·F a ′ ) ∣ ∣ ∣ (188) = ∣ ∣ ∣ ∣ γ −1 ( F nd (s)∩ ( F a \φ·F a ′ ) −e s ) ∣ ∣ ∣ ∣ (189) ≤ ∣ ∣ ∣ ∣ γ −1 ( F nd (s)−e s ) ∩ ( F ∗ T(s,a) \φ·F ∗ T(s,a ′ ) ) ∣ ∣ ∣ ∣ (190) = ∣ ∣ ∣ ∣ ( γ −1 ( F nd (s)−e s ) ∩F ∗ T(s,a) ) \φ·F ∗ T(s,a ′ ) ∣ ∣ ∣ ∣ (191) ≤ ∣ ∣ ∣ ∣ ND ( F ∗ T(s,a) ) \φ·F ∗ T(s,a ′ ) ∣ ∣ ∣ ∣ (192) ≤ ∣ ∣ ∣ ∣ ND ( F ∗ T(s,a) ) \φ·ND ( F ∗ T(s,a ′ ) ) ∣ ∣ ∣ ∣ .(193) Equation (188) follows by the assumption thatF nd (s)∩ ( F a \φ·F a ′ ) is non-empty. Letf,f ′ ∈ F nd (s)∩ ( F a \φ·F a ′ ) be distinct. Then we must have that for someγ x ∈(0,1),f(γ x )6=f ′ (γ x ). This holds iffγ −1 x (f(γ x )−e s )6=γ −1 x (f ′ (γ x )−e s ), and so eq. (189) holds. Equation (190) holds becauseF a ⊆e s +γF ∗ T(s,a) andF ′ a =e s +γF ∗ T(s,a ′ ) by eq. (182). Equa- tion (192) holds because we showed above thatγ −1 (F nd (s)−e s )∩F ∗ T(s,a) ⊆ND ( F ∗ T(s,a) ) . Equation (193) holds because ND ( F ∗ T(s,a ′ ) ) ⊆F ∗ T(s,a ′ ) by definition E.13. Therefore,ND ( F ∗ T(s,a) ) \φ·ND ( F ∗ T(s,a ′ ) ) is non-empty, and so apply the second con- dition of lemma E.46 to conclude that for allD X-IID ∈D C/B/IID ,∀γ∈(0,1) : E s a ′ ∼T(s,a ′ ) [ POWER D X-IID (s a ′ ,γ) ] <E s a ∼T(s,a) [ POWER D X-IID (s a ,γ) ] , and that∀γ∈(0,1) : E s a ′ ∼T(s,a ′ ) [ POWER D bound (s a ′ ,γ) ] 6≥ most:D bound E s a ∼T(s,a) [ POWER D bound (s a ,γ) ] . Item 2.Letφ ′ (s x ) : =φ(s x )whens x ∈REACH ( s,a ′ ) ∪REACH(s,a), and equals x otherwise. Sinceφis an involution, so isφ ′ . φ ′ ·F a ′ : = P φ ′ ( e s +γE s a ′ ∼T(s,a ′ ) [f π,s a ′ ] ) |π∈Π,π(s) =a ′ (194) = e s +γE s a ′ ∼T(s,a ′ ) [ P φ ′ f π,s a ′ ] |π∈Π,π(s) =a ′ (195) = P φ e s +γE s a ′ ∼T(s,a ′ ) [ P φ f π,s a ′ ] |π∈Π,π(s) =a ′ (196) = : φ·F a ′ (197) ⊆F a .(198) Equation (195) follows because ifs∈REACH ( s,a ′ ) ∪REACH(s,a) , then we already showed that φfixess. Otherwise,φ ′ (s) =sby definition. Equation (196) follows by the definition ofφ ′ on REACH ( s,a ′ ) ∪REACH(s,a) and becausee s =P φ e s . Next, we assumed thatφ·F a ′ ⊆F a , and so eq. (198) holds. Therefore,F a contains a copy ofF a ′ viaφ ′ fixing alls x 6∈REACH ( s,a ′ ) ∪REACH(s,a). Therefore, F a contains a copy ofF nd,a ′ : =F nd (s)∩F a ′ via the sameφ ′ . Then apply lemma E.49 withs ′ : =sto conclude that∀γ∈[0,1] : P D any (F a ′ ,γ)≤ most:D any P D any (F a ,γ) . By lemma E.50,P D any ( s,a ′ ,γ ) = P D any (F a ′ ,γ) andP D any (s,a,γ) =P D any (F a ,γ) . Therefore,∀γ∈[0,1] : P D any ( s,a ′ ,γ ) ≤ most:D any P D any (s,a,γ). 41 IfF nd (s)∩ ( F a \φ·F a ′ ) is non-empty, then apply the second condition of lemma E.49 to conclude that for allγ∈(0,1), the inequality is strict for allD X-IID ∈D C/B/IID , andP D any ( s,a ′ ,γ ) 6≥ most:D any P D any (s,a,γ). E.4.2 Whenγ= 1, optimal policies tend to navigate towards “larger” sets of cycles Lemma E.51(POWERidentity whenγ= 1). POWER D bound (s,1) =E r∼D bound [ max d∈RSD(s) d > r ] =E r∼D bound [ max d∈RSD nd (s) d > r ] .(199) Proof. POWER D bound (s,1) =E r∼D bound [ max f π,s ∈F(s) lim γ→1 1−γ γ ( f π,s (γ)−e s ) > r ] (200) =E r∼D bound [ max d∈RSD(s) d > r ] (201) =E r∼D bound [ max d∈RSD nd (s) d > r ] .(202) Equation (200) follows by lemma E.45. Equation (201) follows by the definition ofRSD(s) (definition 6.10). Equation (202) follows because for allr∈R |S| , corollary E.11 shows that max d∈RSD(s) d > r= max d∈ND ( RSD(s) ) d > r= : max d∈RSD nd (s) d > r. Proposition 6.12(Whenγ= 1,RSDs controlPOWER).IfRSD(s)contains a copy ofRSD nd ( s ′ ) viaφ, thenPOWER D bound (s,1)≥ most POWER D bound ( s ′ ,1 ) . IfRSD nd (s)\φ·RSD nd (s ′ )is non-empty, then the converse≤ most statement does not hold. Proof.Suppose RSD nd ( s ′ ) is similar toD⊆RSD(s)via involutionφ. POWER D bound ( s ′ ,1 ) =E r∼D bound [ max d∈RSD nd (s ′ ) d > r ] (203) ≤ most:D bound E r∼D bound [ max d∈RSD nd (s) d > r ] (204) =POWER D bound (s,1)(205) Equation (203) and eq. (205) follow from lemma E.51. By applying lemma E.24 withA : = RSD ( s ′ ) ,B ′ : =D,B : =RSD(s)andgthe identity function, eq. (204) follows. SupposeRSD nd (s) non-empty. By the same result, eq. (204) is a strict inequality for all D X-IID ∈D C/B/IID , and we conclude that POWER D bound ( s ′ ,1 ) 6≥ most:D bound POWER D bound (s,1). Theorem 6.13(Average-optimal policies tend to end up in “larger” sets ofRSDs).LetD,D ′ ⊆ RSD(s) . Suppose thatDcontains a copy ofD ′ viaφ, and that the setsD∪D ′ andRSD nd (s)\ ( D ′ ∪D ) have pairwise orthogonal vector elements (i.e. pairwise disjoint vector support). Then P D any (D,average)≥ most P D any ( D ′ ,average ) . IfRSD nd (s)∩ ( D\φ·D ′ ) is non-empty, the converse ≤ most statement does not hold. Proof.LetD sub : =φ·D ′ , whereD sub ⊆Dby assumption.LetX : = s i ∈S |max d∈D ′ ∪D d > e s i >0 . Define φ ′ (s i ) : = φ(s i )ifs i ∈X s i else. (206) 42 Sinceφis an involution,φ ′ is also an involution. Furthermore, by the definition ofX,φ ′ ·D ′ =D sub andφ ′ ·D sub =D ′ (because we assumed that both equalities hold forφ). LetD ∗ : =D ′ ∪D sub ∪ ( RSD nd (s)\(D ′ ∪D) ) . φ ′ ·D ∗ : =φ ′ · ( D ′ ∪D sub ∪ ( RSD nd (s)\(D ′ ∪D) ) ) (207) = ( φ ′ ·D ′ ) ∪ ( φ ′ ·D sub ) ∪φ ′ · ( RSD nd (s)\(D ′ ∪D) ) (208) =D sub ∪D ′ ∪ ( RSD nd (s)\(D ′ ∪D) ) (209) = : D ∗ .(210) In eq. (209), we know thatφ ′ ·D ′ =D sub andφ ′ ·D sub =D ′ . We just need to show that φ ′ · ( RSD nd (s)\(D ′ ∪D) ) =RSD nd (s)\(D ′ ∪D). Suppose∃s i ∈X,d ′ ∈RSD nd (s)\(D ′ ∪D) : d ′> e s i >0. By the definition ofX,∃d∈D ′ ∪D : d > e s i >0. Then d > d ′ = |S| ∑ j=1 d > (d ′ e s j )(211) ≥d > (d ′ e s i )(212) =d > ( (d ′> e s i )e s i ) (213) = (d ′> e s i )·(d > e s i )(214) >0.(215) Equation (211) follows from the definitions of the dot and Hadamard products. Equation (212) follows becausedandd ′ have non-negative entries. Equation (215) follows becaused > e s i and d ′> e s i are both positive. But eq. (215) shows thatd > d ′ >0, contradicting our assumption thatd andd ′ are orthogonal. Therefore, such ans i cannot exist, andX ′ : = s ′ i ∈S |max d ′ ∈RSD nd (s)\(D ′ ∪D) d ′> e s i >0 ⊆ (S ). By eq. (206),∀s ′ i ∈X ′ : φ ′ (s ′ i ) =s ′ i . Thus,φ ′ · ( RSD nd (s)\(D ′ ∪D) ) =RSD nd (s)\ (D ′ ∪D), and eq. (209) follows. We conclude thatφ ′ ·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 sub ). P D any ( D ′ ,average ) =p D any ( D ′ ≥RSD(s) ) (216) ≤ most:D any p D any ( D≥RSD(s) ) (217) =P D any (D,average).(218) Sinceφ·D ′ ⊆DandND ( D ′ ) ⊆D ′ ,φ·ND ( D ′ ) ⊆D . Then eq. (217) holds by applying lemma E.28 withA : =D ′ ,B ′ : =D sub ,B : =D,C : =RSD(s), and the previously definedZ which we showed satisfiesND(C)⊆Z⊆C. Furthermore, involutionφ ′ satisfiesφ ′ ·B ∗ = φ ′ · ( Z\(B ′ ) ) =Z\(B ′ ) =B ∗ by eq. (210). WhenRSD nd (s)∩ ( D sub ) is non-empty, sinceB ′ ⊆Cby assumption, lemma E.28 also shows that eq. (217) is strict for allD X-IID ∈D C/B/IID , and thatP D any ( D ′ ,average ) 6≥ most:D any P D any (D,average). Proposition E.52(RSDproperties).Letd∈RSD(s).dis element-wise non-negative and‖d‖ 1 = 1. 43 Proof.dhas non-negative elements because it equals the limit oflim γ→1 (1−γ)f(γ), whose elements are non-negative by proposition E.3 item 1. ‖d‖ 1 = ∥ ∥ ∥ ∥ lim γ→1 (1−γ)f(γ) ∥ ∥ ∥ ∥ 1 (219) = lim γ→1 (1−γ) ∥ ∥ f(γ) ∥ ∥ 1 (220) = 1.(221) Equation (219) follows because the definition ofRSDs (definition 6.10) ensures that∃f∈ F(s) : lim γ→1 (1−γ)f(γ) =d. Equation (220) follows because‖·‖ 1 is a continuous function. Equa- tion (221) follows because ∥ ∥ f(γ) ∥ ∥ 1 = 1 1−γ by proposition E.3 item 2. Lemma E.53(When reachable with probability 1, 1-cycles induce non-dominatedRSDs).Ife s ′ ∈ RSD(s), thene s ′ ∈RSD nd (s). Proof.Ifd∈RSD(s)is distinct frome s ′ , then‖d‖ 1 = 1anddhas non-negative entries by proposition E.52. Sincedis distinct frome s ′ , then its entry for indexs ′ must be strictly less than 1: d > e s ′ <1 =e > s ′ e s ′ . Therefore,e s ′ ∈RSD(s)is strictly optimal for thereward functionr : =e s ′ , and soe s ′ ∈RSD nd (s). Corollary 6.14(Average-optimal policies tend not to end up in any given 1-cycle).Sup- posee s x ,e s ′ ∈RSD(s)are distinct.ThenP D any ( RSD(s)\e s x ,average ) ≥ most P D any ( e s x ,average ) . If there is a thirde s ′ ∈RSD(s) , the converse≤ most statement does not hold. Proof.Supposee s x ,e s ′ ∈RSD(s)are distinct. Letφ : = (s x s ′ ),D ′ : =e s x ,D : =RSD(s)\ e s x .φ·D ′ =e s ′ ⊆RSD(s)\e s x = : Dsinces x 6=s ′ .D ′ ∪D=RSD(s)andRSD nd (s)\ (D ′ ∪D) =RSD nd (s) (s) =∅trivially have pairwise orthogonal vector elements. Then apply theorem 6.13 to conclude thatP D any ( e s x ,average ) ≤ most:D any P D any ( RSD(s)\e s x ,average ) . Suppose there exists anothere s ′ ∈RSD(s). By lemma E.53,e s ′ ∈RSD nd (s). Further- more, sinces ′ 6∈ s ′ ,s x ,e s ′ ∈ ( RSD(s)\e s x ) \ e s ′ =D\φ·D ′ . Therefore, e s ′ ∈RSD nd (s)∩ ( D\φ·D ′ ) . Then apply the second condition of theorem 6.13 to conclude that P D any ( e s x ,average ) 6≥ most:D bound P D any ( RSD(s)\e s x ,average ) . 44