Optimal Policies Tend to Seek Power

Introduction

Omohundro , Bostrom , Russell 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.”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 argues that capable rl algorithms 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. 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.

We make no claims about when large-scale AI power-seeking behavior could become plausible. Instead, we consider the theoretical consequences of optimal action in mdps. Section 6 shows that power-seeking tendencies arise not from anthropomorphism, but from certain graphical symmetries present in many mdps. These symmetries automatically occur in many environments where the agent can be shut down or destroyed, yielding broad applicability of our main result (6.13).

Related work

An action is instrumental to an objective when it helps achieve that objective. Some actions are instrumental to a range of objectives, making them convergently instrumental. The claim that power-seeking is convergently instrumental is an instance of the instrumental 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 deactivation [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 , Drummond , Sutton et al. , Schaul et al. note that value functions encode important information about the environment, as they capture the agent’s ability to achieve different goals. Turner et al. speculate that a state’s optimal value correlates strongly across reward functions. In particular, Schaul et al. learn regularities across value functions, suggesting that some states are valuable for many different reward functions (i.e. powerful). Menache et al. 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 learn e.g. edge detectors, implying that these features are useful for a range of tasks [Olah et al., 2020].

State visit distribution functions quantify the agent’s available options

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 about a wide range of mdps. Appendix D.1 lists mdp theory contributions of independent interest, appendix D lists definitions and theorems, and appendix E contains the proofs.

$\langle\mathcal{S},\mathcal{A},T\rangle$ is a rewardless mdp with finite state and action spaces $\mathcal{S}$ and $\mathcal{A}$, and stochastic transition function $T\mathrel{\mathop{\ordinarycolon}}\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$. We treat the discount rate $\gamma$ as a variable with domain $$.

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 $\star$ than at the terminal state $\varnothing$. Formally, $\star$ has more visit distribution functions than $\varnothing$ does.

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).

Considering only visit distribution functions induced by policies taking action $a$ at state $s^{\prime}$, $\operatorname{\mathcal{F}}(s\mid\pi(s^{\prime})=a)\coloneqq\left\{\mathbf{f}\in\operatorname{\mathcal{F}}(s)\mid\exists\pi\in\Pi\mathrel{\mathop{\ordinarycolon}}\pi(s^{\prime})=a,\mathbf{f}^{\pi,s}=\mathbf{f}\right\}$.

Second, some $\mathbf{f}\in\operatorname{\mathcal{F}}(s)$ are “unimportant.” Consider an agent optimizing reward function $\mathbf{e}_{r_{\searrow}}$ (1 reward when at $r_{\searrow}$, 0 otherwise) at e.g. $\gamma=\frac{1}{2}$. Its optimal policies navigate to $r_{\searrow}$ and stay there. Similarly, for reward function $\mathbf{e}_{r_{\nearrow}}$, optimal policies navigate to $r_{\nearrow}$ and stay there. However, for no reward function is it uniquely optimal to alternate between $r_{\nearrow}$ and $r_{\searrow}$. Only dominated visit distribution functions alternate between $r_{\nearrow}$ and $r_{\searrow}$ (definition 3.6).

For any reward function $R$ and discount rate $\gamma$, $\mathbf{f}^{\pi}\in\operatorname{\mathcal{F}}(s)$ is (weakly) dominated by $\mathbf{f}^{\pi^{\prime}}\in\operatorname{\mathcal{F}}(s)$ if $V^{\pi}_{R}(s,\gamma)\leq V^{\pi^{\prime}}_{R}(s,\gamma)$. $\mathbf{f}^{\pi}\in\operatorname{\mathcal{F}_{nd}}(s)$ is non-dominated if there exist $R$ and $\gamma$ at which $\mathbf{f}^{\pi}$ is not dominated by any other $\mathbf{f}^{\pi^{\prime}}$.

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 function $\mathbf{e}_{r_{\searrow}}$, optimized at $\gamma=\frac{1}{2}$. Starting from $\star$, the optimal trajectory goes right to $r_{\triangleright}$ to $r_{\searrow}$, where the agent remains. The right action is optimal at $\star$ under these incentives. Optimal policy sets capture the behavior incentivized by a reward function and a discount rate.

$\Pi^{*}\left(R,\gamma\right)$ is the optimal policy set for reward function $R$ at $\gamma\in(0,1)$. All $R$ have at least one optimal policy $\pi\in\Pi$ [Puterman, 2014]. $\Pi^{*}\left(R,0\right)\coloneqq\lim_{\gamma\to 0}\Pi^{*}\left(R,\gamma\right)$ and $\Pi^{*}\left(R,1\right)\coloneqq\lim_{\gamma\to 1}\Pi^{*}\left(R,\gamma\right)$ exist by E.33 (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 of e.g. the reward shaping [Ng et al., 1999] or intrinsic motivation [Pathak et al., 2017]. Alternatively, one might attempt to reason about future rl agents, 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).

With $\mathcal{D}_{\text{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 $\star$ to $\varnothing$, or to go to $r_{\triangleright}$ and then stay at $r_{\nearrow}$. In this case, we quantify the optimality probability of $F\coloneqq\{\mathbf{e}_{\star}+\frac{\gamma}{1-\gamma}\mathbf{e}_{\varnothing},\mathbf{e}_{\star}+\gamma\mathbf{e}_{r_{\triangleright}}+\frac{\gamma^{2}}{1-\gamma}\mathbf{e}_{r_{\nearrow}}\}$.

Alternatively, perhaps we’re interested in the probability that right is optimal at $\star$.

Some states give the agent more control over the future

Figure 3 shows the pleasing result that for the max-entropy distribution, $r_{\searrow}$ has greater average optimal value than $\varnothing$. However, average optimal value has a few problems as a measure of power. The agent is rewarded for its initial presence at state $s$ (over which it has no control), and because $\left\lVert\mathbf{f}(\gamma)\right\rVert_{1}=\frac{1}{1-\gamma}$ (E.3) diverges as $\gamma\to 1$, $\lim_{\gamma\to 1}V^{*}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)$ tends to diverge. Definition 5.2 fixes these issues in order to better measure the agent’s control over the future.

$\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left(s,\gamma\right)$ is Lipschitz continuous on $\gamma\in$.

Let $\mathcal{D}_{\text{bound}}$ be bounded $[b,c]$. Suppose $s$ and $s^{\prime}$ can both reach each other in one step with probability 1.

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.”

Certain environmental symmetries produce power-seeking tendencies

We can permute reward functions, but we can also permute reward function distributions. Permuted distributions simply permute which states get which rewards.

Let $\phi\in S_{\left|\mathcal{S}\right|}$. $\phi\cdot\mathcal{D}_{\text{any}}$ is the pushforward distribution induced by applying the random vector $f(\mathbf{r})\coloneqq\mathbf{P}_{\phi}\mathbf{r}$ to $\mathcal{D}_{\text{any}}$.

The orbit of $\mathcal{D}_{\text{any}}$ under the symmetric group $S_{\left|\mathcal{S}\right|}$ is $S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}_{\text{any}}\coloneqq\{\phi\cdot\mathcal{D}_{\text{any}}\mid\phi\in S_{\left|\mathcal{S}\right|}\}$.

For example, the orbit of a degenerate state indicator distribution $\mathcal{D}_{s}$ is $S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}_{s}=\{\mathcal{D}_{s^{\prime}}\mid s^{\prime}\in\mathcal{S}\}$, and fig. 5 shows the orbit of a 2D Gaussian distribution.

If $\operatorname{\mathcal{F}}(s)$ contains a copy of $\operatorname{\mathcal{F}_{nd}}(s^{\prime})$ via $\phi$, then $\forall\gamma\in\mathrel{\mathop{\ordinarycolon}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}(s,\gamma)\geq_{\text{{most}}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}(s^{\prime},\gamma)$. If $\operatorname{\mathcal{F}_{nd}}(s)\setminus\phi\cdot\operatorname{\mathcal{F}_{nd}}(s^{\prime})$ is non-empty, then for all $\gamma\in(0,1)$, the converse $\leq_{\text{{most}}}$ statement does not hold.

Certain symmetries in the mdp structure ensure that, compared to left, going right tends to be optimal and to be Power-seeking. Intuitively, by going right, the agent has “strictly more choices.” 6.9 will formalize this tendency.

Actions $a_{1}$ and $a_{2}$ are equivalent at state $s$ (written $a_{1}\equiv_{s}a_{2}$) if they induce the same transition probabilities: $T(s,a_{1})=T(s,a_{2})$.

The agent can reach states in $\{r_{\triangleright},r_{\nearrow},r_{\searrow}\}$ by taking actions equivalent to right at state $\star$.

$\text{{Reach}}\left(s,a\right)$ is the set of states reachable with positive probability after taking the action $a$ in state $s$.

Suppose $F_{a}\coloneqq\operatorname{\mathcal{F}}(s\mid\pi(s)=a)$ contains a copy of $F_{a^{\prime}}\coloneqq\operatorname{\mathcal{F}}(s\mid\pi(s)=a^{\prime})$ via $\phi$.

If $\operatorname{\mathcal{F}_{nd}}(s)\cap\left(F_{a}\setminus\phi\cdot F_{a^{\prime}}\right)$ is non-empty, then $\forall\gamma\in(0,1)$, the converse $\leq_{\text{{most}}}$ statements do not hold.

2 When γ=1𝛾1\gamma=1, optimal policies tend to navigate towards “larger” sets of cycles

6.6 and 6.9 are powerful because they apply to all $\gamma\in$, but they can only be applied given hard-to-satisfy environmental symmetries. In contrast, 6.12 and 6.13 apply to many structured environments common to rl.

Starting from $\star$, 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.

A reward function’s optimal policies can vary with the discount rate. When $\gamma=1$, optimal policies ignore transient reward because average reward is the dominant consideration.

Average-optimal policies maximize average reward. Average reward is governed by rsd access. For example, $r_{\searrow}$ has “more” rsds than $\varnothing$; therefore, $r_{\searrow}$ usually has greater Power when $\gamma=1$.

Informally, states with more rsds generally have more Power at $\gamma=1$, no matter their transient dynamics. Furthermore, average-optimal policies are more likely to end up in larger sets of rsds than in smaller ones. Thus, average-optimal policies tend to navigate towards parts of the state space which contain more rsds.

This section’s results prove the $\gamma=1$ case. 5.3 shows that Power is continuous at $\gamma=1$. Therefore, if an action is strictly $\text{{Power}}_{\mathcal{D}}$-seeking when $\gamma=1$, it is strictly $\text{{Power}}_{\mathcal{D}}$-seeking at discount rates sufficiently close to 1. Future work may connect average optimality probability to optimality probability at $\gamma\approx 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.

3 How to reason about other environments

Consider an embodied navigation task through a room with a vase. 6.9 suggests that optimal policies tend to avoid immediately breaking the vase, since doing so would strictly decrease available options.

6.13 dictates where average-optimal agents tend to end up, but not what actions they tend to take in order to reach their rsds. Therefore, care is needed. In appendix B, fig. 10 demonstrates an environment in which seeking Power is a detour for most reward functions (since optimality probability measures “median” optimal value, while Power is a function of mean optimal value). However, suppose the agent confronts a fork in the road: Actions $a$ and $a^{\prime}$ lead to two disjoint sets of rsds $D_{a}$ and $D_{a^{\prime}}$, such that $D_{a}$ contains a copy of $D_{a^{\prime}}$. 6.13 shows that $a$ will tend to be average-optimal over $a^{\prime}$, and 6.12 shows that $a$ will tend to be Power-seeking compared to $a^{\prime}$. Such forks seem reasonably common in environments with irreversible actions.

6.13 applies to many structured rl environments, which tend to be spatially regular and to factorize along several dimensions. Therefore, different sets of rsds 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} $\times$ {position in room}. Therefore, the rsds can be divided into three similar subsets, depending on the agent’s room number.

6.14 dictates where average-optimal agents tend to end up, but not how they get there. 6.14 says that such agents tend not to stay in any given 1-cycle. It does not say that such agents will avoid entering such states. For example, in an embodied navigation task, a robot may enter a 1-cycle by idling in the center of a room. 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 robots do tend to avoid getting shut down. The agent’s task mdp often represents agent shutdown with terminal states. A terminal state is, by definition 3.2, unable to access other 1-cycles. Since 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 going left, but can reach thousands of rsds by heading in other directions. Even if some average-optimal policies go left in order to reach fig. 8’s “game over” terminal state, all other rsds cannot be reached by going left. There are many 1-cycles besides the immediate terminal state. Therefore, 6.14 proves that average-optimal policies tend to not go left in 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.

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 $\gamma\approx 1$, optimal policies tend to seek power by accumulating resources—to the detriment of any other agents in the environment.

Real-world training procedures often do not satisfy rl convergence 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 finite mdps, we expect the key conclusions to generalize. Furthermore, irregular stochasticity in environmental dynamics can make it hard to satisfy 6.13’s similarity requirement. We look forward to future work which addresses partially observable environments, suboptimal policies, or “almost similar” rsd sets.

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 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 why Power-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, 6.13 holds for one million involutions $\phi$. Does this guarantee more pronounced incentives than if 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.

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.

We developed the first formal theory of the statistical tendencies of optimal policies in reinforcement learning. In the context of mdps, we proved sufficient conditions under which optimal policies tend to seek power, both formally (by taking Power-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 mathematically prove that 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

Appendix A Comparing Power with information-theoretic empowerment

Salge et al. define information-theoretic empowerment as the maximum possible mutual information between the agent’s actions and the state observations $n$ steps in the future, written $\mathfrak{E}_{n}(s)$. This notion requires an arbitrary choice of horizon, failing to account for the agent’s discount rate $\gamma$. “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.

Power returns intuitive answers in these situations. \lim_{\gamma\to 1}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{1}},\gamma\right) converges by 5.3. Consider the obvious involution $\phi$ which takes each state in fig. 9(b) to its counterpart in fig. 9(c). Since \phi\cdot\operatorname{\mathcal{F}_{nd}}({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{3}})\subsetneq\operatorname{\mathcal{F}_{nd}}({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{4}})=\operatorname{\mathcal{F}}({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{4}}), 6.6 proves that \forall\gamma\in\mathrel{\mathop{\ordinarycolon}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{3}},\gamma\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{bound}}}\text{{Power}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{4}},\gamma\right), with the proof of 6.6 showing strict inequality under all $\mathcal{D}_{X\text{-}\textsc{iid}}$ when $\gamma\in(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 Power is formulated in terms of optimal value, we believe that Power is better suited for mdps than information-theoretic empowerment is.

Appendix B Seeking Power can be a detour

The results of appendix E do not depend on this section’s results.

One might suspect that optimal policies tautologically tend to seek Power. This intuition is wrong.

Consider the environment of fig. 10. Let $X_{u}\coloneqq\text{unif}(0,1)$, and consider $\mathcal{D}_{X_{u}\text{-}\textsc{iid}}$, which has bounded support. Direct computationIn small deterministic mdps, the Power and optimality probability of the maximum-entropy reward function distribution can be computed using https://github.com/loganriggs/Optimal-Policies-Tend-To-Seek-Power. of the Power expectation (definition 5.2) yields $\text{{Power}}_{\mathcal{D}_{X_{u}\text{-}\textsc{iid}}}\left(s_{2},1\right)=\frac{3}{4}>\frac{2}{3}=\text{{Power}}_{\mathcal{D}_{X_{u}\text{-}\textsc{iid}}}\left(s_{3},1\right)$. Therefore, N seeks more $\text{{Power}}_{\mathcal{D}_{X_{u}\text{-}\textsc{iid}}}$ than NE at state {\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{1}} and $\gamma=1$.

All $\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}$ such that $f_{1}(\mathcal{D}^{\prime})=f_{2}(\mathcal{D}^{\prime})$ satisfy $f_{1}(\mathcal{D}^{\prime})\geq f_{2}(\mathcal{D}^{\prime})$.

Otherwise, consider the $\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}$ such that $f_{1}(\mathcal{D}^{\prime})\neq f_{2}(\mathcal{D}^{\prime})$. By the definition of $\geq_{\text{{most}}}$ (definition 6.5), at least $\frac{1}{2}$ of these $\mathcal{D}^{\prime}$ satisfy $f_{1}(\mathcal{D}^{\prime})>f_{2}(\mathcal{D}^{\prime})$, in which case $f_{1}(\mathcal{D}^{\prime})\geq f_{2}(\mathcal{D}^{\prime})$. Then the desired inequality follows. ∎

By B.2, at least half of the elements $\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}$ satisfy $f_{1}(\mathcal{D}^{\prime})\geq f_{2}(\mathcal{D}^{\prime})$. But $\left|S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\right|=1$, and so $f_{1}(\mathcal{D})\geq f_{2}(\mathcal{D})$ must hold.

If $\mathcal{D}$ is iid, it has a one-element orbit due to the assumed identical distribution of reward. ∎

Appendix C Sub-optimal Power

In certain situations, Power returns 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 rewardless mdp of fig. 11.

We formalize a bounded agent’s goal-achievement capabilities with a function pol, 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 $\text{{Power}}_{\mathcal{D}_{\text{bound}}}$ with respect to pol.

\text{{Power}}^{\text{pol}}_{\mathcal{D}_{\text{bound}}}\left({\color[rgb]{.25,.45,.75}\definecolor[named]{pgfstrokecolor}{rgb}{.25,.45,.75}s_{0}},1\right) increases as the policies returned by pol are improved. We illustrate this by considering the $\mathcal{D}_{X\text{-}\textsc{iid}}$ case.

Appendix D Lists of results

We developed new basic mdp theory by exploring the structural properties of visit distribution functions. Echoing Wang et al. , we believe that this area is interesting and underexplored.

E.38 shows that $f(\gamma^{*})\coloneqq\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})V^{*}_{R}\left(s,\gamma^{*}\right)$ is Lipschitz continuous on $\gamma\in$, with Lipschitz constant depending only on $\left\lVert R\right\rVert_{1}$. For all states $s$ and policies $\pi\in\Pi$, E.5 shows that $V^{\pi}_{R}(s,\gamma)$ is rational on $\gamma$.

Optimal value has a well-known dual formulation: $V^{*}_{R}\left(s,\gamma\right)=\max_{\mathbf{f}\in\operatorname{\mathcal{F}}(s)}\mathbf{f}(\gamma)^{\top}\mathbf{r}$. {restatable*}[$\forall\gamma\in[0,1)\mathrel{\mathop{\ordinarycolon}}V^{*}_{R}\left(s,\gamma\right)=\max_{\mathbf{f}\in\operatorname{\mathcal{F}_{nd}}(s)}\mathbf{f}(\gamma)^{\top}\mathbf{r}$]lemoptVfFndRestrict In a fixed rewardless mdp, section D.1.1 may enable more efficient computation of optimal value functions for multiple reward functions.

D.1.2 Optimal policy theory

Section D.1.2 demonstrates how to preserve optimal incentives while changing the discount rate.

[How to transfer optimal policy sets across discount rates]proptransferDiscount Suppose reward function $R$ has optimal policy set $\Pi^{*}\left(R,\gamma\right)$ at discount rate $\gamma\in(0,1)$. For any $\gamma^{*}\in(0,1)$, we can construct a reward function $R^{\prime}$ such that $\Pi^{*}\left(R^{\prime},\gamma^{*}\right)=\Pi^{*}\left(R,\gamma\right)$. Furthermore, $V^{*}_{R^{\prime}}\left(\cdot,\gamma^{*}\right)=V^{*}_{R}\left(\cdot,\gamma\right)$.

D.1.3 Visit distribution theory

Appendix E Theoretical results

Let $\gamma\in(0,1)$ and let $R$ be a reward function. $\pi\in\Pi^{*}\left(R,\gamma\right)$ iff $\pi$ induces an optimal visit distribution at every state.

By definition, a policy $\pi$ is optimal iff $\pi$ induces the maximal on-policy value at each state, which is true iff $\pi$ induces an optimal visit distribution at every state (by the dual formulation of optimal value functions). ∎

$\mathbf{T}^{\pi}$ is the transition matrix induced by policy $\pi\in\Pi$, where $\mathbf{T}^{\pi}\mathbf{e}_{s}\coloneqq T(s,\pi(s))$. $(\mathbf{T}^{\pi})^{t}\mathbf{e}_{s}$ gives the probability distribution over the states visited at time step $t$, after following $\pi$ for $t$ steps from $s$.

Let $s,s^{\prime}\in\mathcal{S},\mathbf{f}^{\pi,s}\in\operatorname{\mathcal{F}}(s)$.

$\mathbf{f}^{\pi,s}(\gamma)$ is element-wise non-negative and element-wise monotonically increasing on $\gamma\in[0,1)$.

$\forall\gamma\in[0,1)\mathrel{\mathop{\ordinarycolon}}\left\lVert\mathbf{f}^{\pi,s}(\gamma)\right\rVert_{1}=\frac{1}{1-\gamma}$.

Item 1: by examination of definition 3.3, $\mathbf{f}^{\pi,s}=\sum_{t=0}^{\infty}\left(\gamma\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s}$. Since each $\left(\mathbf{T}^{\pi}\right)^{t}$ is left stochastic and $\mathbf{e}_{s}$ is the standard unit vector, each entry in each summand is non-negative. Therefore, $\forall\gamma\in[0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s^{\prime}}\geq 0$, and this function monotonically increases on $\gamma$.

Equation 7 follows because all entries in each $\left(\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s}$ are non-negative by item 1. Equation 8 follows because each $\left(\mathbf{T}^{\pi}\right)^{t}$ is left stochastic and $\mathbf{e}_{s}$ is a stochastic vector, and so $\left\lVert\left(\mathbf{T}^{\pi}\right)^{t}\mathbf{e}_{s}\right\rVert_{1}=1$. ∎

$\mathbf{f}^{\pi}\in\operatorname{\mathcal{F}}(s)$ is a multivariate rational function on $\gamma\in[0,1)$.

By the Bellman equations, $\mathbf{v}^{\pi}_{R}=\left(\mathbf{I}-\gamma\mathbf{T}^{\pi}\right)^{-1}\mathbf{r}.$ Let $\mathbf{A}_{\gamma}\coloneqq\left(\mathbf{I}-\gamma\mathbf{T}^{\pi}\right)^{-1}$, and for state $s$, form $\mathbf{A}_{s,\gamma}$ by replacing $\mathbf{A}_{\gamma}$’s column for state $s$ with $\mathbf{r}$. As noted by Lippman , by Cramer’s rule, $V^{\pi}_{R}(s,\gamma)=\frac{\det{\mathbf{A}_{s,\gamma}}}{\det\mathbf{A}_{\gamma}}$ is a rational function with numerator and denominator having degree at most $\left|\mathcal{S}\right|$.

In particular, for each state indicator reward function $\mathbf{e}_{s_{i}}$, $V^{\pi}_{s_{i}}(s,\gamma)=\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s_{i}}$ is a rational function of $\gamma$ whose numerator and denominator each have degree at most $\left|\mathcal{S}\right|$. This implies that $\mathbf{f}^{\pi}(\gamma)$ is multivariate rational on $\gamma\in[0,1)$. ∎

Let $\pi\in\Pi$ and $R$ be any reward function. $V^{\pi}_{R}(s,\gamma)$ is rational on $\gamma\in[0,1)$.

$V^{\pi}_{R}(s,\gamma)=\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{r}$, and $\mathbf{f}$ is a multivariate rational function of $\gamma$ by E.4. Therefore, for fixed $\mathbf{r}$, $\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{r}$ is a rational function of $\gamma$. ∎

Results with $\mathcal{D}_{\text{cont}}$ hold for any absolutely continuous reward function distribution.

Let $A(\mathbf{r}\mid X)\coloneqq\operatorname*{arg\,max}_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}=\left\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\right\}$. Then

In eq. 10, each $\mathbf{x}^{\top}\mathbf{r}$ expression is linear on $\mathbf{r}$. The $\max$ is piecewise linear on $\mathbf{r}$ since it is the maximum of a finite set of linear functionals. In particular, all expressions in eq. 10 are continuous on $\mathbf{r}$, and so we can find some $\delta>0$ neighborhood $B(\mathbf{r},\delta)$ such that $\forall\mathbf{r}^{\prime}\in B(\mathbf{r},\delta)\mathrel{\mathop{\ordinarycolon}}\max_{\mathbf{x}_{i}\in A(\mathbf{r}\mid X)}\mathbf{x}_{i}^{\top}\mathbf{r}^{\prime}>\max_{\mathbf{x}^{\prime}\in X\setminus A(\mathbf{r}\mid X)}\mathbf{x}^{\prime\top}\mathbf{r}^{\prime}$.

But almost all $\mathbf{r}^{\prime}\in B(\mathbf{r},\delta)$ are maximized by a unique functional $\mathbf{x}^{*}$ by E.8; in particular, at least one such $\mathbf{r}^{\prime\prime}$ exists. Formally, $\exists\mathbf{r}^{\prime\prime}\in B(\mathbf{r},\delta)\mathrel{\mathop{\ordinarycolon}}\mathbf{x}^{*\top}\mathbf{r}^{\prime\prime}>\max_{\mathbf{x}^{\prime}\in X\setminus\left\{\mathbf{x}^{*}\right\}}\mathbf{x}^{\prime\top}\mathbf{r}^{\prime\prime}$. Therefore, $\mathbf{x}^{*}\in\text{{ND}}\left(X\right)$ by definition E.9.

$\mathbf{x}^{*\top}\mathbf{r}^{\prime}\geq\max_{\mathbf{x}_{i}\in A(\mathbf{r}\mid X)}\mathbf{x}_{i}^{\top}\mathbf{r}^{\prime}>\max_{\mathbf{x}^{\prime}\in X\setminus A(\mathbf{r}\mid X)}\mathbf{x}^{\prime\top}\mathbf{r}^{\prime}$, with the strict inequality following because $\mathbf{r}^{\prime\prime}\in B(\mathbf{r},\delta)$. These inequalities imply that $\mathbf{x}^{*}\in A(\mathbf{r}\mid X)$. ∎

If $X$ is empty, holds trivially. Otherwise, apply E.10. ∎

If $\text{{ND}}\left(X\right)\subseteq X^{\prime}$, then $\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\leq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r}$.

If $\text{{ND}}\left(X\right)\subseteq X^{\prime}\subseteq X$, then $\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}=\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r}$.

Equation 11 follows by E.11. Equation 12 follows because $\text{{ND}}\left(X\right)\subseteq X^{\prime}$.

Item 2: by item 1, $\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\leq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r}$. Since $X^{\prime}\subseteq X$, we also have $\max_{\mathbf{x}\in X}\mathbf{x}^{\top}\mathbf{r}\geq\max_{\mathbf{x}^{\prime}\in X^{\prime}}\mathbf{x}^{\prime\top}\mathbf{r}$, and so equality must hold. ∎

$\operatorname{\mathcal{F}_{nd}}(s)=\text{{ND}}\left(\operatorname{\mathcal{F}}(s)\right)$ by definition 3.6.

Equation 14 follows because $c>0$. Equation 15 follows by the definition of $b$.

Therefore, $(c\mathbf{f}+\mathbf{a})\in\text{{ND}}\left(cF+\mathbf{a}\right)$. ∎

E.1.2 Inequalities which hold under most reward function distributions

Since $\phi$ does not belong to the stabilizer of $S_{\left|\mathcal{S}\right|}$, $\phi$ acts injectively on $S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}$. By assumption on $\phi$, the image of $\{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})<f_{2}(\mathcal{D}^{\prime})\}$ under $\phi$ is a subset of $\{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})>f_{2}(\mathcal{D}^{\prime})\}$. Since $\phi$ is injective, $\left|\{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})<f_{2}(\mathcal{D}^{\prime})\}\right|\leq\left|\{\mathcal{D}^{\prime}\in S_{\left|\mathcal{S}\right|}\cdot\mathcal{D}\mid f_{1}(\mathcal{D}^{\prime})>f_{2}(\mathcal{D}^{\prime})\}\right|$. $f_{1}(\mathcal{D})\geq_{\text{{most}}\text{: }\mathfrak{D}}f_{2}(\mathcal{D})$ by definition 6.5. ∎

for some function $g$, and that $f$ is well-defined for all $\mathcal{D}\in\mathfrak{D}$. Let $\phi$ be a state permutation. Then

Let distribution $\mathcal{D}$ have probability measure $F$, and let $\phi\cdot\mathcal{D}$ have probability measure $F_{\phi}$.

Equation 24 follows by the definition of $F_{\phi}$ (definition 6.3). Equation 25 follows by substituting $\mathbf{r}^{\prime}\coloneqq\mathbf{P}_{\phi}\mathbf{r}$. Equation 26 follows from the fact that all permutation matrices have unitary determinant and are orthogonal (and so $(\mathbf{P}_{\phi}^{-1})^{\top}=\mathbf{P}_{\phi}$). ∎

Note that $\mathbf{a}$ is still strictly optimal for $\mathbf{r}^{\prime}$:

$\mathcal{D}_{\text{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, $\mathcal{D}_{\text{any}}$ assigns positive probability to $N^{\prime}\subseteq\operatorname{supp}(\mathcal{D}_{\text{any}})$. ∎

If $\text{{ND}}\left(B\right)\setminus B^{\prime}$ is empty, then eq. 30 is an equality. If $\text{{ND}}\left(B\right)\setminus B^{\prime}$ is non-empty, $g$ is strictly increasing, and $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{\text{bound}})$, then eq. 30 is strict.

If $\text{{ND}}\left(B\right)\setminus B^{\prime}$ is empty, then $\text{{ND}}\left(B\right)\subseteq B^{\prime}$. By assumption, $B^{\prime}\subseteq B$. Then apply E.12 item 2 with $X\coloneqq B$, $X^{\prime}\coloneqq B^{\prime}$ in order to conclude that eq. 34 is an equality. Then eq. 30 is also an equality.

Suppose that $g$ is strictly increasing, $\text{{ND}}\left(B\right)\setminus B^{\prime}$ is non-empty, and $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{\text{bound}})$. Let $\mathbf{x}\in\text{{ND}}\left(B\right)\setminus B^{\prime}$.

$\mathbf{x}$ is strictly optimal for a positive-probability subset of $\operatorname{supp}(\mathcal{D}_{\text{bound}})$ by E.20. Since $g$ is strictly increasing, eq. 35 is strict. Therefore, we conclude that eq. 30 is strict. ∎

$\mathcal{D}_{X\text{-}\textsc{iid}}\coloneqq X^{\left|\mathcal{S}\right|}$. Since the state reward distribution $X$ is continuous, $X$ must have support on some open interval $(b,c)$. Since $\mathcal{D}_{X\text{-}\textsc{iid}}$ is iid across states, $(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{X\text{-}\textsc{iid}})$. ∎

Suppose $g$ is strictly increasing and $\text{{ND}}\left(B\right)\setminus B^{\prime}$ is non-empty. Let $\phi^{\prime}\in S_{\left|\mathcal{S}\right|}$.

Equation 42 and eq. 44 hold because $\mathcal{D}_{X\text{-}\textsc{iid}}$ distributes reward identically across states: $\forall\phi_{x}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\phi_{x}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}=\mathcal{D}_{X\text{-}\textsc{iid}}$. By E.22, $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{X\text{-}\textsc{iid}})$. Therefore, apply E.21 with $A^{\prime}\coloneqq\text{{ND}}\left(A\right)$ to conclude that eq. 43 holds.

If $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{\text{any}})$, $X\subseteq Y$, and $\text{{ND}}\left(Y\right)\cap\left(Y\setminus Y^{\prime}\right)$ is non-empty, then the second inequality is strict.

Suppose $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{\text{any}})$, $X\subseteq Y$, and $\text{{ND}}\left(Y\right)\cap\left(Y\setminus Y^{\prime}\right)$ is non-empty. Let $\mathbf{y}^{*}\in\text{{ND}}\left(Y\right)\cap\left(Y\setminus Y^{\prime}\right)$. By E.20, $\mathbf{y}^{*}$ is strictly optimal on a subset of $\operatorname{supp}(\mathcal{D}_{\text{any}})$ with positive measure under $\mathcal{D}_{\text{any}}$. In particular, for a set of $\mathbf{r}^{*}$ with positive measure under $\mathcal{D}_{\text{any}}$, we have $\mathbf{y}^{*\top}\mathbf{r}^{*}>\max_{\mathbf{y}\in Y^{\prime}}\mathbf{y}^{\top}\mathbf{r}^{*}.$

Then eq. 48 is strict, and therefore the second inequality of eq. 45 is strict as well. ∎

If $B^{\prime}=B$, then eq. 52 is an equality. If $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{\text{any}})$, $B^{\prime}\subseteq C$, and $\text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right)$ is non-empty, then eq. 52 is strict.

Equation 53 and eq. 59 follow by E.12’s item 2 with $X\coloneqq C$, $X^{\prime}\coloneqq Z$. Similarly, eq. 54 follows by E.12’s item 2 with $X\coloneqq A$, $X^{\prime}\coloneqq\text{{ND}}\left(A\right)$. Equation 55 follows by applying the first inequality of E.26 with $X\coloneqq\text{{ND}}\left(A\right),Y\coloneqq Z,Y^{\prime}\coloneqq Z\setminus(B\setminus B^{\prime})$. Equation 56 follows by applying E.17 to eq. 53 with permutation $\phi$.

Equation 57 follows by our assumptions on $\phi$. Equation 58 follows because by applying the second inequality of E.26 with $X\coloneqq B^{\prime},Y\coloneqq\text{{ND}}\left(C\right),Y^{\prime}\coloneqq\text{{ND}}\left(C\right)\setminus(B\setminus B^{\prime})$.

Suppose $B^{\prime}=B$. Then $B\setminus B^{\prime}=\emptyset$, and so eq. 55 and eq. 58 are trivially equalities. Then eq. 52 is an equality.

Suppose $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{\text{any}})$; note that $(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\phi\cdot\mathcal{D}_{\text{any}})$, since such support must be invariant to permutation. Further suppose that $B^{\prime}\subseteq C$ and that $\text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right)$ is non-empty. Then letting $X\coloneqq B^{\prime},Y\coloneqq Z,Y^{\prime}\coloneqq Z\setminus(B\setminus B^{\prime})$ and noting that $\text{{ND}}\left(\text{{ND}}\left(Z\right)\right)=\text{{ND}}\left(Z\right)$, apply E.26 to eq. 58 to conclude that eq. 52 is strict. ∎

If $B^{\prime}\subseteq C$ and $\text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right)$ is non-empty, then the inequality is strict for all $\mathcal{D}_{X\text{-}\textsc{iid}}\in\mathfrak{D}_{\textsc{c/b/}\textsc{iid}}$ and $p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right)$.

Suppose $\mathcal{D}_{\text{any}}$ is such that $p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right)<p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)$.

Equation 60 holds because $\phi$ is an involution. Equation 61 and eq. 63 hold by applying E.27 with permutation $\phi$. Equation 62 holds by assumption. Therefore, $p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\leq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right)$ by E.16.

Suppose $B^{\prime}\subseteq C$ and $\text{{ND}}\left(C\right)\cap\left(B\setminus B^{\prime}\right)$ is non-empty, and let $\mathcal{D}_{X\text{-}\textsc{iid}}$ be any continuous distribution which distributes reward independently and identically across states. Let $\phi^{\prime}\in S_{\left|\mathcal{S}\right|}$.

Equation 64 and eq. 66 hold because $\mathcal{D}_{X\text{-}\textsc{iid}}$ distributes reward identically across states, $\forall\phi_{x}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}\phi_{x}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}=\mathcal{D}_{X\text{-}\textsc{iid}}$. By E.22, $\exists b<c\mathrel{\mathop{\ordinarycolon}}(b,c)^{\left|\mathcal{S}\right|}\subseteq\operatorname{supp}(\mathcal{D}_{X\text{-}\textsc{iid}})$. Therefore, apply E.27 to conclude that eq. 65 holds.

Therefore, $\forall\phi^{\prime}\in S_{\left|\mathcal{S}\right|}\mathrel{\mathop{\ordinarycolon}}p_{\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(A\geq C\right)<p_{\phi^{\prime}\cdot\mathcal{D}_{X\text{-}\textsc{iid}}}\left(B\geq C\right)$. In particular, $p_{\mathcal{D}_{\text{any}}}\left(A\geq C\right)\not\geq_{\text{{most}}\text{: }\mathfrak{D}_{\text{any}}}p_{\mathcal{D}_{\text{any}}}\left(B\geq C\right)$ by definition 6.5. ∎

Let $F_{Z}$ satisfy $\text{{ND}}\left(F_{C}\right)\subseteq F_{Z}\subseteq F_{C}$. Suppose $F_{B}$ contains a copy of $F_{A}$ via $\phi$ such that $\phi\cdot\left(F_{Z}\setminus\left(F_{B}\setminus\phi\cdot F_{A}\right)\right)=F_{Z}\setminus\left(F_{B}\setminus\phi\cdot F_{A}\right)$. Then $f_{2}(\mathfrak{D})\leq_{\text{{most}}\text{: }\mathfrak{D}}f_{1}(\mathfrak{D})$.

Suppose $\mathcal{D}\in\mathfrak{D}$ is such that $f_{2}(\mathcal{D})>f_{1}(\mathcal{D})$.

By the assumption that $\mathfrak{D}$ is closed under permutation and $f_{2}$ is well-defined for all $\mathcal{D}\in\mathfrak{D}$, $f_{2}(\phi\cdot\mathcal{D})$ is well-defined. Equation 67 follows since $\phi=\phi^{-1}$ because $\phi$ is an involution. For all $\gamma^{*}\in I$, let $A\coloneqq F_{A}(\gamma^{*}),B\coloneqq F_{B}(\gamma^{*}),C\coloneqq F_{C}(\gamma^{*}),Z\coloneqq F_{Z}(\gamma^{*})$ (by definition E.13, $\text{{ND}}\left(C\right)\subseteq Z\subseteq C$). Since $\phi\cdot A\subseteq B$ by assumption, and since $\text{{ND}}\left(A\right)\subseteq A$, $B$ also contains a copy of $\text{{ND}}\left(A\right)$ via $\phi$. Furthermore, $\phi\cdot\left(Z\setminus\left(B\setminus\phi\cdot A\right)\right)=Z\setminus\left(B\setminus\phi\cdot A\right)$ (by assumption), and so apply E.27 to conclude that $p_{\phi^{-1}\cdot\mathcal{D}}\left(F_{A}(\gamma^{*})\geq F_{C}(\gamma^{*})\right)\leq p_{\mathcal{D}}\left(F_{B}(\gamma^{*})\geq F_{C}(\gamma^{*})\right)$. Therefore, the limit inequality eq. 69 holds. Equation 70 follows because we assumed that $f_{1}(\mathcal{D})<f_{2}(\mathcal{D})$. Equation 71 holds by reasoning similar to that given for eq. 69.

Therefore, $f_{2}(\mathcal{D})>f_{1}(\mathcal{D})$ implies that $f_{2}\left(\phi\cdot\mathcal{D}\right)<f_{1}\left(\phi\cdot\mathcal{D}\right)$, and so apply E.16 to conclude that $f_{2}(\mathcal{D})\leq_{\text{{most}}\text{: }\mathfrak{D}}f_{1}(\mathcal{D})$. ∎

Let $\pi\in\Pi$ be any policy. By the definition of optimal policies, $\pi\in\Pi^{*}\left(R^{\prime},\gamma^{*}\right)$ iff for all $s$:

For $\gamma\in(0,1)$, define $\operatorname{\mathcal{F}}(s,\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in\operatorname{\mathcal{F}}(s)\right\}$ and $\operatorname{\mathcal{F}_{nd}}(s,\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in\operatorname{\mathcal{F}_{nd}}(s)\right\}$. If $F\subseteq\operatorname{\mathcal{F}}(s)$, then $F(\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in F\right\}$.

Let $\mathbf{f}^{\pi}\in\text{{ND}}\left(F\right)$ be strictly optimal for reward function $R$ at discount rate $\gamma\in(0,1)$:

Let $\gamma^{*}\in(0,1)$. By section D.1.2, we can produce $R^{\prime}$ such that $\Pi^{*}\left(R^{\prime},\gamma^{*}\right)=\Pi^{*}\left(R,\gamma\right)$. Since the optimal policy sets are equal, E.1 implies that

Therefore, $\mathbf{f}^{\pi}(\gamma^{*})\in\text{{ND}}\left(F(\gamma^{*})\right)$.

The reverse direction follows by the definition of $\text{{ND}}\left(F\right)$. ∎

By definition E.30, $\operatorname{\mathcal{F}_{nd}}(s,\gamma)\coloneqq\left\{\mathbf{f}(\gamma)\mid\mathbf{f}\in\text{{ND}}\left(\operatorname{\mathcal{F}}(s)\right)\right\}$. By applying E.31 with $\Delta_{d}\coloneqq\mathbf{e}_{s}$, $\mathbf{f}\in\text{{ND}}\left(\operatorname{\mathcal{F}}(s)\right)$ iff $\forall\gamma\in(0,1)\mathrel{\mathop{\ordinarycolon}}\mathbf{f}(\gamma)\in\text{{ND}}\left(\operatorname{\mathcal{F}}(s,\gamma)\right)$. ∎

$\text{{ND}}\left(\operatorname{\mathcal{F}}(s,\gamma)\right)=\operatorname{\mathcal{F}_{nd}}(s,\gamma)$ by E.32, so apply E.11 with $X\coloneqq\operatorname{\mathcal{F}}(s,\gamma)$. ∎

E.2 Some actions have greater probability of being optimal

For fixed $R$, $\Pi^{*}\left(R,\gamma\right)$ can take on at most $(2\left|\mathcal{S}\right|+1)\sum_{s}\binom{\left|\operatorname{\mathcal{F}}(s)\right|}{2}$ distinct values over $\gamma\in(0,1)$.

By E.1, $\Pi^{*}\left(R,\gamma\right)$ changes value iff there is a change in optimality status for some visit distribution function at some state. Lippman showed that two visit distribution functions can trade off optimality status at most $2\left|\mathcal{S}\right|+1$ times. At each state $s$, there are $\binom{\left|\operatorname{\mathcal{F}}(s)\right|}{2}$ such pairs. ∎

If $\lim_{\gamma\to 1}\delta(\gamma)>0$, then there exist reward functions whose optimal policy sets $\Pi^{*}\left(R,\gamma\right)$ never converge (in the discrete topology on sets) to $\Pi^{*}\left(R,1\right)$, contradicting E.33. So $\lim_{\gamma\to 1}\delta(\gamma)=0$.

Let $\gamma\in(0,1)$ and let $F\subseteq\operatorname{\mathcal{F}}(s)$.

E.3 Basic properties of Power

Let $\pi$ be a policy, $R$ a reward function, and $s$ a state. For $\gamma\in$, $V^{\pi}_{R,\,\text{norm}}\left(s,\gamma\right)\coloneqq\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})V^{\pi}_{R}(s,\gamma^{*})$.

Let $\pi$ be any policy, $s$ a state, and $R$ a reward function. Since $V^{\pi}_{R,\,\text{norm}}\left(s,\gamma\right)=\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}^{\pi,s}(\gamma^{*})^{\top}\mathbf{r}$, $\frac{d}{d\gamma}V^{\pi}_{R,\,\text{norm}}\left(s,\gamma\right)$ is controlled by the behavior of $\lim_{\gamma^{*}\to\gamma}(1-\gamma^{*})\mathbf{f}^{\pi,s}(\gamma^{*})$. We show that this function’s gradient is bounded in infinity norm.

By E.4, $\mathbf{f}^{\pi,s}(\gamma)$ is a multivariate rational function on $\gamma$. Therefore, for any state $s^{\prime}$, $\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s^{\prime}}=\frac{P(\gamma)}{Q(\gamma)}$ in reduced form. By E.3, $0\leq\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s^{\prime}}\leq\frac{1}{1-\gamma}$. Thus, $Q$ may only have a root of multiplicity 1 at $\gamma=1$, and $Q(\gamma)\neq 0$ for $\gamma\in[0,1)$. Let $f_{s^{\prime}}(\gamma)\coloneqq(1-\gamma)\mathbf{f}^{\pi,s}(\gamma)^{\top}\mathbf{e}_{s^{\prime}}$.

If $Q(1)\neq 0$, then the derivative $f_{s^{\prime}}^{\prime}(\gamma)$ is bounded on $\gamma\in[0,1)$ because the polynomial $(1-\gamma)P(\gamma)$ cannot diverge on a bounded domain.

If $Q(1)=0$, then factor out the root as $Q(\gamma)=(1-\gamma)Q^{*}(\gamma)$.

Since $Q^{*}(\gamma)$ is a polynomial with no roots on $\gamma\in$, $f_{s^{\prime}}^{\prime}(\gamma)$ is bounded on $\gamma\in[0,1)$.

Therefore, whether or not $Q(\gamma)$ has a root at $\gamma=1$, $f_{s^{\prime}}^{\prime}(\gamma)$ is bounded on $\gamma\in[0,1)$. Furthermore, $\sup_{\gamma\in[0,1)}\left\lVert\nabla(1-\gamma)\mathbf{f}^{\pi,s}(\gamma)\right\rVert_{\infty}=\sup_{\gamma\in[0,1)}\max_{s^{\prime}\in\mathcal{S}}\left|f_{s^{\prime}}^{\prime}(\gamma)\right|$ is finite since there are only finitely many states.

There are finitely many $\pi\in\Pi$, and finitely many states $s$, and so there exists some $K^{\prime}$ such that $\sup_{\begin{subarray}{c}s\in\mathcal{S},\\ \pi\in\Pi,\gamma\in[0,1)\end{subarray}}\left\lVert\nabla(1-\gamma)\mathbf{f}^{\pi,s}(\gamma)\right\rVert_{\infty}\leq K^{\prime}$. Then $\left\lVert\nabla(1-\gamma)\mathbf{f}^{\pi,s}(\gamma)\right\rVert_{1}\leq\left|\mathcal{S}\right|K^{\prime}\eqqcolon K$.

Equation 99 holds because $V^{\pi}_{R}\left(s,\gamma\right)$ is continuous on $\gamma\in[0,1)$ by E.5. Equation 101 holds by the Cauchy-Schwarz inequality.

Since $\left|\frac{d}{d\gamma}V^{\pi}_{R,\text{norm}}\left(s,\gamma\right)\right|$ is bounded for all $\gamma\in[0,1)$, eq. 102 also holds for $\gamma\to 1$. ∎

Let $b,c$ be such that $\operatorname{supp}(\mathcal{D}_{\text{bound}})\subseteq[b,c]^{\left|\mathcal{S}\right|}$. For any $\mathbf{r}\in\operatorname{supp}(\mathcal{D}_{\text{bound}})$ and $\pi\in\Pi$, $V^{\pi}_{R,\,\text{norm}}\left(s,\gamma\right)$ has Lipschitz constant $K\left\lVert\mathbf{r}\right\rVert_{1}\leq K\left|\mathcal{S}\right|\left\lVert\mathbf{r}\right\rVert_{\infty}\leq K\left|\mathcal{S}\right|\max(\left|c\right|,\left|b\right|)$ on $\gamma\in(0,1)$ by E.38.