Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a formal definition for a measure of power in reinforcement learning. It is expressed as a scaled expectation of the difference of the optimal value function in a state and the immediate reward in that state, where the expectation is taken over possible reward functions and it is scaled by (1-\gamma)/\gamma. Using this measure, the authors show that any state or action that leaves more options open has more power. 
main_review: The paper is generally very well-written and propose an intriguing framework to discuss about whether intelligent agent may seek more power. I also appreciate the small example of Markov decision process, which is provided to illustrate all the results.

However, I am not completely convinced that the proposed measure of power helps answer the initially-raised question of whether an intelligent agent would seek power, a question that I understand as focusing on one given agent, which would in the course of solving a given task seek power. It seems to me that the authors rather provide an answer to the question of whether given many intelligent agents with potentially different reward functions would they on average favor some states or actions for their optimal policies. For this latter question, the obtained results can be understood quite intuitively since a state or an action that leaves option open can potentially satisfy more various reward functions.
Although the authors mention that their results apply to the case with a degenerate distribution, it is not clear to me how the proposed measure is useful to answer the former question about one given agent. I think more discussion on that point would be warranted.

Besides, could the introduced notion of power be extended when the reward function depends on the action and/or future state?

POST-REBUTTAL
The authors' responses clarify the first point I raised and address my concern. 
limitations_and_societal_impact: The authors discuss the societal impact of their work in a satisfying way.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper presents a new way to think about the power of an MDP state with a view to understanding when and why autonomous agents seek power in a given environment. Similar to other treatments "power" captures something about the freedom to act towards diverse objectives, and the authors relate this appropriately to that literature, e.g. empowerment.

The authors begin with motivation to develop a notion of power that is free from anthropomorphic a priori assumption. However, this is a mostly theoretical/mathematical contribution with a series of definitions, e.g. the power-function of a state, and theoretical results, e.g. smoothness properties of their power-function and gives a general perspective of why autonomous agents might act to seek power (i.e. to navigate towards states of high power). The later results exploit ways to think about symmetries in MDPs based on permutations of states, and allows for quite general results pertaining to agents navigating to states of high power under weak assumptions.

The paper ends with a discussion of how the concrete mathematical arguments can be applied to more general domains including those of a general agent acting in an open environment. One conclusion is a warning about how weak assumptions about how a an autonomous learner is motivates can lead to impulsions to "seek power" and explain that this may have relevance for the safe development of autonomous agents operating in society.
main_review: The authors develop their mathematical ideas for an MDP with infinite horizon (i.e. with absorbing/terminal states represented as those with only reflexive outgoing edges of the graph) and then define states in terms of their set of available "visit distribution functions" and various restrictions of this notion. This is a very neat way to abstract away from many of the complexities arising from such things as multiple actions having the same outcome, and lays the foundations for simliar neat abstractions on top of this, such as the non-dominated set of visit functions.

Section 5 gives a result that states something along the lines of "this state has a higher expected optimal value" (as an expectation over reward functions drawn from a known distribution) and consequently defines the power of a state as a related function with various goodness properties. I had some concerns reading the opening sections that there were going to be (strong) implicit assumptions about the distribution of tasks/reward functions, and these concerned were alleviated here, as the assumptions are explicitly stated and in many cases only weak constraining (e.g. that the functions/distributions over functions are bounded). 

Section 6 defines the orbit of a distribution as a set of distributions resulting from permutations of the original distribution's dimensions, and another novel (to me) idea that similarity up to permutation between a one states visit distribution (functions) and a subset of another's visit distribution (functions). This gives them a way to explore how fairly general symmetries in the environment can be used to score states and actions within states with very weak assumptions over reward functions. Finally, the authors give results relating to Blackwell optimal policies (essentially average reward optimisers) again reasoning in a general way about the states that "tend" to be navigated towards by "most" policies. The descriptive language here lets them down a little, as I think they could be clearer in explaining what they mean by such things as "tend", "usually" and "most" but the mathematical definitions are clear.


I find the arguments here compelling and novel and expect them to have relevance to the RL community as well as more widely (especially the final few comments relating to autonomous agents acting in society). The arguments are clearly made with formal mathematical definitions. I spotted a few minor things that were either unclear or ambiguious, but on the whole it was exceptionally clear mathematically and well described in natural language.

I have a few specific points, e.g. typos etc, these are:

* [line 39 onwards] The definition of robustly instrumental is making some assumption about distribution of tasks. That could be clearer.
* [line 64] The comment about computer vision systems reliably learning is less obviously tied to the line of reasoning than it could be.
* [line 111] The set of "non-dominated" visit distribution functions seems to comprise of visit functions that strictly dominate for at least one reward function. Would a better name be "dominating" visit distribution functions? It's a minor point but one that confused me for a while.
* [lines 129] For $D_{bound}$ are you assuming a distribution whose support is bounded, or a distribution with bounded variance. I assume the former, but this could be clearer, and the former would exclude a gaussian distribution.
* [lines 144-148] This was a bit difficult for me to parse.
* [line 166] By "count the agent's initial presence" I think you mean "reward" the agent for its presence in state s at the beginning of any trajectory from s. 
* [Figure 3 caption] The last sentence should end with something like "...when greater reward is assigned to $l_{\nwarrow}$.
* [line 194] drop the word "instead"
* [lines 201-206] I get a bit lost here in the example.
* Definition 6.7 uses a very similar notation for a subset of possible states as it does for the full set of states (only the font style changes).
* [lines 333-334] It isn't really clear what you mean by randomly generated MDPs nor why they would be "unlikely" to have any particular property. Nor is it entirely clear what sufficient conditions you are referring to.

limitations_and_societal_impact: There is a clear route to societal impact outlined by the authors, and while it isn't conclusive, the authors are asking for a debate and I think that is valid.

My concerns are relatively minor and tend to relate to the justifications for a implications of the theoretical work rather than the work itself. These are:

* A comment that different results make different distributional assumptions over rewards appears on line 129 in section 4, but it would be good to have this stated very early on e.g. abstract/introduction.
* That at times (towards the end of the paper), I am not sure whether the descriptive language appropriately captures the mathematical concepts being developed. For instance, the use of the words "tends", "usually" and "most". While there are distributions applied to reward functions, the orbits are sets of distributions and there is no measure defined over this set. The use of adverbs of degree to describe the high frequency outcomes in a subset of distributions should be made a little clearer I think.
* In fact, it could be clearer what the motivation is for defining distributions of plausible reward functions in the way that is done. It may be the case that certain topological properties of sub-parts of a naturally arising decision problem correlate with reward function over that sub-part. In fact, it is extremely uncommon in games/human activities for task success to be associated with hard to reach states. That isn't to say these states aren't of high power, just that the assumptions about IID rewards and orbits based on permutations of rewards, may not always be applicable.
* On lines 320-323, you state that your result applies to all degenerate distributions. However, we should remember that the orbit of a degnenerate distributions is any permutation of a degenerate distribution. Your earlier use of "tends" and "most" etc , seems to suggest that you are treating this orbit in some kind of measurable way, e.g. as a distribution of its own, and so the message here isn't as clear as it could be.

These issues could be addressed with a couple of comments relating to the validity/scope of assumptions and how to interpret particular choices of words.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper formalizes a notion of power-seeking in MDPs and shows that many reward functions lead to optimal policies that achieve powerful states.
main_review: This is a significant step towards settling a long-standing debate that most AI researchers will have considered or even participated in but only in an informal context. It is also an important debate as it affects the field’s priorities. The result is perhaps not surprising to everyone but nonetheless important because it contributes to this ongoing debate. Not only the results but also the formalizations will be useful for future research and discussion. Taken together, the paper is likely to be among the most high-impact ones at Neurips. 

Although the community has expected that results like the ones in this paper can be proven, my impression is that, it has been difficult to do so with any generality and therefore nothing is published yet. It is good to see results with some generality now.

Perhaps as a side effect of trying to achieve more general results, the derivations with substantial amounts of notation are a bit tedious to follow at times. Although the prose is well-written, mathematical presentation could be further improved.

-------


Minor comments:

- Can we use these insights to engineer a system that avoids power seeking?

- First paragraph of discussion: not clear what is the point of this paragraph

- Can you discuss more clearly why and to what extent your results apply to many MDPs?

- It’s obvious but maybe mention why an analysis of optimal policies is useful. I.e. because our community is constantly improving agents to produce closer to optimal policies

-------

Comments on presentation/writing:

- The paper could benefit from an illustrative example. The MDP graphs help but they are not self-explanatory. One way to address this would be to cast the MDP in terms of concrete objects and explain the intuitions in the caption. Additionally, section 6 could also benefit from an intuitive characterization both in section 6 itself and in other parts of the paper that refer to it. Otherwise I fear you’ve lost many readers by this point. This should also explain why many MDPs should have the proposed symmetries.

- The paper could state more clearly throughout if the goal is to show that agents seek influence (e.g. by earning money), or seek survival, or both. The last sentence of the discussion highlights this issue - can you discuss the evidence that your results can be extrapolated to accumulating resources? The concept of ‘keeping options open’ sounds more like postponing commitment than e.g. accumulating resources or influence. A more appropriate term might be ‘maximizing open options’?

- The notation is overall a cluttered which can make the derivations tedious to follow. 

- “into computational resources” - while this is related to power seeking it seems more of a central example for side effects

- “Section 5 defines “power” as the ability to achieve a wide range of goals: after all, “money is power”, and money is instrumentally useful for many goals.”: the first part of the sentence (“power” as the ability to achieve a wide range of goals) does not follow from the second.

- I’d recommend using less scare quotes 

- “Optimal policies for e.g. Pac-Man do not seek power in the real world”: I don’t follow, why would someone deploy a pacman policy in the real world?


limitations_and_societal_impact: Limitations and societal impact are adequately addressed in the discussion.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper formalises the notion of an agent's power in a state $s$ as the average optimal value of that state, which the authors claim can be measured using a related power function. The paper posits that most optimal policies tend to seek states that achieve a higher value of power according to the power function under the set of bounded reward distributions. This is explained by optimal policies keeping options open, which naturally leads to a greater probability of optimal value for at least one option under the set of bounded reward distributions, and hence greater power. The paper then gives conditions in terms of symmetries in the MDP where such behaviour can be proved. 
main_review: Taking a dispositional view of power 'as the ability to achieve a wide variety of goals' is certainly valid, however I have concerns about the limitations of its formalisation here. 

1. PATHOLOGIES IN THE FORMALISATION OF POWER

The paper posits that 'in an MDP, optimal value functions capture the agent’s ability to “achieve the goal” R. So average optimal value captures the agent’s ability to achieve a range of goals'. In the current definition of the MDP, I'm not sure that this is true as this does not account for preference over goals in terms of their optimal value. It would seem that using the average optimal reward would be vunerable to certain pathologies. As a counter example, consider the following MDP:

Consider a starting state $s_0$ and two actions that lead the agent deterministically to $s_l$ and $s_r$. In $s_l$, the agent recieves a reward of $R_l$ and then transitions to a terminal state $s_t$ with reward of 0. In $s_r$, the agent has a choice of 9 actions, each deterministically transitioning to a state $s_{r_i}$, $i\in\{1:9\}$. The reward for each state is $R_{r_i}$. The agent then transitions to the terminal state $s_t$.

If $R_l >> \max\_{i\in\{1:9\}} R_{r_i}$, then the average optimal value for being in $s_l$ is much higher than $s_r$. However being in state $s_l$ only allows the achievement of one goal, not a wide variety of goals. One could avoid such situations by introducing a restriction on rewards to normalise optimal value functions, however I believe this would severely limit the scope of the work as it seems natural that some goals should always have more value to agents than other: As an example of where this sort of MDP could be encountered, consider the option of somebody training for a very specific but very powerful job represented by entering in state $s_l$ vs obtaining a more general qualification that would allow that person to do a wide variety of jobs, but none of which would have as much power (or earn as much money) as the job in $s_l$. It seems natural that we would want to account for these situations if we were to formalise power. Perhaps a better solution would be to re-define or at least clarify what is meant by power to include a notion that powerful states can also lead agents to goals that a achieve a greater affect on the world in terms of optimal value at the expense of being able to achieve fewer goals overall.

2. DIFFERENCE BETWEEN $\textrm{Power}$ FUNCTION AND AVERAGE OPTIMAL VALUE

Ignoring this pathology, there is also a disconnect between the measure of power in terms of average optimal value and the $\textrm{Power}$ function that isn't explained. This is revealed by manipulating its definition:
$$
\begin{aligned}\textrm{Power}_\mathcal{D}(s,\gamma):=&\frac{1-\gamma}{\gamma} \mathbb{E}_\mathcal{D}\left[V_R^*(s)-R(s)\right],\\\\
=&\frac{1-\gamma}{\gamma} \mathbb{E}_\mathcal{D}\left[ \mathbb{E}\_{P\^\star(\tau\vert s)}\left[R(s) +\sum\_{i=1}^\infty\gamma^i R(s_i)\right]- R(s)\right],\\\ 
=&(1-\gamma)\mathbb{E}_\mathcal{D}\left[ \mathbb{E}\_{P\^\star(\tau\vert s)}\left[ \sum\_{i=1}^\infty\gamma\^{i-1} R(s_i)\right]\right],\\\\
=&(1-\gamma) \mathbb{E}_\mathcal{D}\left[\mathbb{E}\_{P\^\star(s_1\vert s)}\left[V^*_R(s_1)\right]\right],
\end{aligned}
$$
which is the average optimal value of the next state given state $s$. This leads to a different definition of power that ignores the reward of the current state (notice how it cancels between lines 2 and 3 above). It is easy to construct counterexample MDPs that would lead to opposing notions of which state is more powerful under the average optimal value definition and the $\textrm{Power}$ function in the same vein as the pathological example above. In addition, the $\textrm{Power}$ function is not motivated as a replacement for average optimal value beyond it not diverging in the limit $\gamma\rightarrow 1$. If this is a critical property, why not just use the optimal average value scaled by $(1-\gamma)$? As we see in the above derivation, this is essentially what you are using but averaged over the transition dynamics for the next state, and so by using optimal average value scaled by $(1-\gamma)$ you will obtain the same desired properties without changing its meaning. 

3. UNCLEAR SIGNIFICANCE OF CONTRIBUTION

To me, it seems like the paper proves an obvious observation that can be elucidated by considering the MDP in 1 again. It seems somewhat trivial that for most bounded reward distributions over the reward function, being in state $s_r$ would lead to greater average optimal value as $9$ out of $10$ times the reward function would give the highest reward to one of $s_{r_i}$. Hence having more options would clearly lead to greater power under your definition. Although the paper seems to formalise and generalise this observation, which I think may be a valuable contribution as an abstract peice of theory, I'm not sure that it makes sense in the context of trying to formalise power. As discussed in 1, characterising power in this way is very limited, precisely because in many situations it doesn't make sense to consider all bounded distributions of rewards: we want to preserve some notion that highly specific states can lead to more power because they tend to give greater reward, even if we are uncertain about precisely what that reward is. 

4. VALID CONTRIBUTION IN TERMS OF AI SAFETLY

I do, however, believe there is a valid contribution in the context of analysing the behaviour of a agent trying to be shut down in an MDP. If this was the sole focus of the work, rather than attempting to formalise a notion of power, I think it would improve its clarity and contribution significantly. 

EDIT:

Following discussion with authors, most of my concerns have been addressed.
limitations_and_societal_impact: On a philosophical level, I think that the authors' formalisation that power is being in a state that can lead to many rewarding goals being achieved in terms of average optimal value is limited and doesn't fully account for power under the working definition given in the paper, i.e. that 'power is the ability to achieve a range of goals [Sattarov, 2019]'. For example, the agent might not be able to learn the optimal value to act optimally, they might be uncertain about the MDP or even have incorrect knowledge of the state they are in - in the context of an AI agent avoiding being shut down, the agent is clearly in a lesser state of power if we can withold information about it ever being able to be shut down. Even the MDP the agent is in must be an essential part of understanding power. All of these other aspects are necessary for an agent to have power in terms of being able to actually achieve a goal. However these apsects are ignored in this work. As a real-life example, imagine that somebody has inherited a car. Unfortunately, they have no idea how to drive it. Having a car clearly increases the agent's power under the authors' definition of average optimal value as they are in a state where their actions have the potential to acheive a wider ranger of goals. Indeed, it would be easy to show that their average optimal value in this state is higher than a state without a car.  Crucially though, they don't have access to the optimal value function to be able to actually drive it. This means that they may actually be in state of less power (now being burdened with road tax , storage fees, nobody wanting to buy it etc.). One could posit a way of resolving this by making knowledge part of the agent's state, however this would mean extending state to include the agent's knowledge of the value function, which clearly creates issues in an MDP as any optimal value function would depend on knowledge of itself! 

I believe this issue can be resolved by acknowledging that there are many necessary and sufficient aspects of being in a position of power, with one sufficient aspect being that states where more options are available can be more powerful. I think taking this perspective, discussing (or better formalising) other necessary aspects of power as well as fixing the pathologies identified above would significantly improve this paper.
review_title: null

Meta-review: The discussion with the authors helped clear all the reviewer concerns.  The scores were all updated to clear accept.
Decision: Accept (Spotlight)