Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper begins by defining a Newcomblike decision process (NDP), a natural extension of MDP in which both the reward and/or dynamics are allowed to depend on the learner's policy. The main theoretical claims of the paper are largely three-fold:
1. define two notions of ratifiability (strong and weak). strong ratifiability can be seen as a policy that always selects actions among those that are optimal w.r.t. the q-values of the policy, while weak can be seen as q-values for a policy being constant among those actions sampled by the policy
2. show that q-values, when converge, must converge to a strong ratifiable policy; this can relaxed to weak ratifiability if q-values are accurate only for state-action pairs sampled infinitely often
3. with the help of several bandit examples, show that standard RL such as QL and SARSA is not required to converge at all.
main_review: Overall, I believe this paper is quite novel from a conceptual standpoint, presenting the idea of Newcomblike process for making decisions in long-term horizons. This formulation seems quite intuitively appealing, as do the paper's main contributions showing that either standard RL converges to a suitable notion of "optimality" or not at all (which can be viewed as an example of 0-1 law). I agree with the authors that a negative result here, namely the possible failure modes of standard RL algorithms, can be a good starting point for designing ones that do, though it is not fully clear how the analysis in the paper claims to be able to proceed from here. However, I believe the results could be important for shaping future work and have some impact in game-theoretic work in RL in the future. 

My main concerns, which I discuss in the limitations section, is that it becomes apparent fairly early that standard RL algorithms are not suitable here due to the policy dependence of the environment. I do not have any problem with providing negative results, but only if their outcome is fairly significant and insightful and can provide clear directions how to proceed from here and shape future algorithms, which I am not entirely sure here. As I read the paper I was wondering early on whether a game theoretic formulation of the agent could have made more sense as a starting point right away, rather than suggesting standard single agent QL (e.g. Nash-Q, fictitious play etc). I also have some slight issues with clarity of figures which I discuss later.
limitations_and_societal_impact: ===== possible limitations and/or questions for authors: =====

significance: The definition of "environment" in this paper is already quite different than what standard RL is able to solve, single they are tailored for "stationary" problems, whereas here the environment responds to the agent's policy in ad-hoc ways. Based on this, it is not clearly motivated why standard RL like Q-learning and SARSA would be natural starting points for solving the NDPs. Furthermore, is the NDP the best way to model the AV example in the intro? Wouldn't a standard game-theory formulation be able to deal with such problems, where the agent (AV) plays adversarially against nature (a single human driver or set of drivers)? Therefore, wouldn't an equilibrium-based strategy, such as Nash-Q, fictitious play, or other game-theoretic RL method do better for solving problems, given the vast literature already available for solving them? alternatively, could a restricted class of NDPs with certain structure (like a budget on how much the environment allowed to vary w.r.t policies) be suitable for standard RL with some sort of weak guarantees?

connection to multi-agent RL: In relation to above commentary, I do believe more discussion should be provided to shed light on how the NDP + RL formulation is more meaningful for solving the kind of problem motivated early on than typical game theory, or what kind of problems can be solved with the new formulation that cannot otherwise. It almost seems that the NDP formulation is a balance between single agent and multi agent RL, where we only learn from direct environment responses to our behaviors (which need not even be optimal from the nature's point of view), rather than not at all or trying to fully account for natures' best response to our behavior. the example provided shows that human drivers could directly formulate a best response to the AV policy. In light of this, i believe more needs to be discussed on this matter and make the connection with other game-theoretic notions more clear for readers.

other suitable formulations within ordinary RL: Since the environment here is policy conditioned, wouldn't it be possible to embed the policy conditioning within standard RL frameworks such as Q-learning? Such work has already been considered in the context of policy evaluation, see. e.g. Harb et al, 2020, or Borsa et al., 2018 for two examples in the RL context. If the Q(s, a; pi) is policy conditioned and standard RL with Bellman principle applied, then don't the problems with instability claimed here in sec. 4 disappear altogether, since now Q can assign credit appropriately in a way consistent with the true environment?

===== some other minor comments: =====

- would be nice to label axis in graphs, e.g. label x axis as \alpha in Fig 2a and "Probability of Convergence" as y, etc. I would make the axis numbering larger to make it easy to read as the font is too small.
- the idea of Newcomblike decision process does not appear in the cited papers apart from the single stage problem, as far as I can see. It would be nice to cite the appropriate reference to this modeling framework if it is previously considered in Sec 1.1. 

===== references =====

Harb, Jean, et al. "Policy evaluation networks." arXiv preprint arXiv:2002.11833 (2020).
Borsa, Diana, et al. "Universal successor features approximators." arXiv preprint arXiv:1812.07626 (2018).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces Newcomblike Decision Problems (NDPs), an analog of MDPs in which the environment (specifically the transitions and reward) may depend on the agent’s _policy_ in addition to the state and action. They theoretically study the performance of standard RL algorithms when applied as is to continuous NDPs. Key results include:

1. Any RL algorithm that eventually finds accurate Q-values for its policy, and is greedy with respect to those Q-values, will converge to a strongly ratifiable policy, or will not converge at all. A strongly ratifiable policy is one that never “wishes” it could switch its action while keeping its “identity” the same. (The informal description is mine; the paper presents a formal statement.) SARSA, Expected SARSA, and Q-learning all satisfy the conditions for this theorem.
2. In any continuous NDP there exists a “strongly ratifiable” policy, but it may not be the optimal policy (for example, in the classic Newcomb problem).
3. Nonetheless, there exist continuous NDPs where typical RL algorithms almost surely do not converge to the strongly ratifiable policy.
4. When there is not infinite exploration of states and actions, RL algorithms instead satisfy weak ratifiability, where the policy never “wishes” it could switch its action to some other action that is explored infinitely often (but may “wish” to switch actions to an action that isn’t explored infinitely often).
5. In the special case of bandit NDPs, similar results can be proven for algorithms with limiting _action frequencies_ (even if there is no limiting policy).
main_review: Overall score
-------------

**Originality:** While there has been some prior work on testing RL algorithms in Newcomblike problems (which the authors mention), to my knowledge there has not been any theoretical analysis of the kind done in this paper.

**Significance:** Newcomblike problems seem like an interesting problem to study: RL agents will be deployed in environments that then respond to the deployment of the RL agent (as in the autonomous driving example). While I tend to think of such situations from the lens of game theory, it can also be thought of as a Newcomblike situation. (An example of a paper studying a specific practical problem of this sort is Milli et al, “The Social Cost of Strategic Classification”, and various papers on recommender systems.) This paper provides some basic results for NDPs, establishing the basic theory on which future papers can build; this seems quite worthwhile.

The main argument against significance is that the paper studies RL algorithms applied to NDPs, even though RL algorithms are designed to work with MDPs and are not expected to work well on NDPs. Nonetheless, I agree with the authors that in practice it seems likely that we will apply RL algorithms to NDPs, and so it is worth studying this setting (for example, OpenAI Five was trained with PPO, but is effectively playing in an NDP since its human opponents know how it was trained and can adapt to its policy).

**Quality:** The results are interesting and look correct to me (though I have not checked the proofs in detail).

**Clarity:** I found the paper clear and surprisingly easy to read given the significant number of theorems. I have mentioned some nitpicks at the end of this review.

Relation to game theory
-----------------------

Newcomblike problems are often meant to capture cases in which the environment is “bigger” than the agent, i.e. the agent is unable to model the environment in perfect detail. This also happens in multiagent settings / game theory, since the agent cannot have a perfect model of other agents (e.g. if another agent is a copy of the agent, then the agent would have to have a perfect model of itself, which tends to lead to contradiction).

The authors briefly mention game theory in the related work, but it seems like there is much more to be said here. Can we reduce NDPs to game theory? In particular, it seems like we could take an arbitrary NDP and reduce it to a Stackelberg game (leader-follower game) in which the original agent is the leader and the environment is the follower. Does this reduction provide insight?

Many of the motivating examples for NDPs can also be modeled as games in which you are searching for Nash equilibria, e.g. in autonomous driving you want to find a policy that performs well _given how human drivers will respond_ -- this is very similar to what a Nash equilibrium would give you (to the extent that iterated best response in the “autonomous driving” game converges to a Nash equilibrium). As a result, the topic of this paper is very related to the large literature on multiagent RL, much of which is concerned about whether typical RL algorithms converge to Nash equilibria (just as this paper considers whether typical RL algorithms converge to optimal or strongly ratifiable policies). For example (the first is most relevant):

Mazumdar, Eric, Lillian J. Ratliff, and S. Shankar Sastry. "On gradient-based learning in continuous games."
Letcher, Alistair, et al. "Stable opponent shaping in differentiable games."

Questions
---------

How do NDPs relate to game theory and multiagent RL? What novelty do NDPs introduce that could not already be modeled in these areas?

I see the point of strong ratifiability: a strongly ratifiable policy never “wants to” switch to a different action (in this respect it is similar to a Nash equilibrium in game theory). What’s the point of weak ratifiability? My best guess is that in a weakly ratifiable policy, the policy never “wants to” switch between actions within its support -- but wouldn’t it “want to” switch to an action not in its support? Why do we care only about actions in the support of the policy? (Maybe the point is just “that’s what’s needed to make Theorem 5 work”, since it could be the case that the policy should “want to” switch to an action that hasn’t been infinitely explored.)

Minor nitpicks
--------------

Since you are introducing a new formalism, please define what an optimal policy is in this new formalism (I assume it is any policy in the set $\arg \max_{\pi} \mathbb{E} [ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t, s_{t+1}, \pi) ]$, which you also write as $\arg \max_{\pi} \mathbb{E}[R \mid \pi]$).

> The key feature of this NDP is that regardless of the policy a2 (“two-boxing”) yields a higher reward than a1 (“one-boxing”).

I wouldn’t say this is _regardless_ of the policy, as the policy very much does influence the reward. I might instead say something like “The key feature of this NDP is that for any fixed policy, a2 (“two-boxing”) would yield a higher reward than a1 (“one-boxing”).”

> This is because the optimal policy in Newcomb’s Problem does not select optimal actions.

I’m not sure what this means, and it doesn’t seem like an explanation. I would say something like “this is because the choice of which policy is optimal depends not only on actions, but also on the policy itself; the Bellman optimality condition does not include the effect of the policy on optimality”.

> it is clear that all actions in the support of π∞ must have equal expected utility given π∞.

I would change this to “it is clear that, _for a given state_, all actions in…”
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces Newcomblike decision processes (NDPs), a generalization of MDPs where the transition probabilities depend on the agent's policy, representing scenarios like Newcomb's problem. The authors use an autonomous driving example to illustrate how Newcomblike dynamics may arise in the real world. They define ratifiability for policies and show that a value-based RL agent cannot converge to a non-ratifiable policy.  They introduce some examples (Repellor Problem and LARPS) of settings where this implies that the algorithm cannot converge to any policy, and investigate the limit behavior of non-converging algorithms (convergence to a specific action frequency). 

main_review: This paper addresses an important setting where the outcomes for the agent depend not only on its actions but on its entire policy. It shows how this setting can arise not only in thought experiments but also in the real world using the example of autonomous driving, and introduces a generalization of MDPs for this setting. The non-convergence results are a novel and significant theoretical contribution. I have skimmed the main proofs and they appear to be correct. 

The main weakness of this paper that limits its impact is lack of clarity, which could be improved as follows:
- State the motivation more clearly in the introduction section, e.g. by moving the second paragraph of the discussion section to the introduction. Emphasize a take-home message for the readers, e.g. the implications of non-convergence and how you expect these results will contribute to "developing extensions of value-based RL that can detect and correct these failures". 
- Define ratifiability in the abstract (which should be self-contained), and provide a reference for the standard definition of ratifiability referred to in section 2 as "what decision theorists mean when they speak about ratifiability".
- Use more readable formatting for the second-last paragraph of the introduction (e.g. a numbered list).
- Provide a statement of Newcomb's problem in the introduction, since not all readers will be familiar with the problem. 
- Provide a plain language description of the Death in Damascus problem in section 1.3.
- Describe the theorems in section 4 (convergence of action frequencies) in plain language, since it is not obvious what they mean from the formal statements. 
- Clarify how this paper differs from the previous work on Newcomblike problems referred to in "Another more sophisticated setting was studied by Oesterheld (2019)" 

limitations_and_societal_impact: The paper adequately addresses limitations of this work but does not discuss possible societal impacts. It could be useful to discuss how better understanding of Newcomblike dynamics could potentially contribute to misuse of AI, e.g. in the example of autonomous vehicles discussed in the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper formalizes Newcomblike decision processes (NDPs), a generalization of Markov decision processes in which reward and transitions may depend on the agent's policy. This formalism better reflects how e.g. self-driving car policies (aggressive vs meek) affect how humans drive (back off vs take advantage of the docile AI). The authors prove a range of theoretical results about when model-free value-based RL algorithms converge to a policy, what that policy looks like, etc. The authors run simple experiments to validate their claims. 
main_review: **Originality.** This work formalizes several key concepts from the decision theory literature and situates them in the RL context. There is little past work in this setting, which makes this contribution especially valuable IMO.

**Quality.** The work seems sound, although I haven't gone through most of the math. The experiments are simple but illustrative. 

**Clarity.** I overall found the paper clear. The authors use intelligent examples and reasoning throughout the paper, and the graphics are good.

That said, I have several points of confusion:
* Below page 89, what does "w.p." mean? Given that you have extra room, can you remove the abbreviation?
* I didn't understand 304-313 explaining theorem 9. Maybe a more concrete example would help.

**Significance.** I think this paper is important, especially given the future work I hope it motivates. Newcomblike problems are understudied in the RL context, even though they are clearly relevant. The theoretical results are good, the experiments sensible, and the paper is well-written.

**Post-rebuttal**: I thank the authors for their clarifications. My score remains unchanged: accept.
limitations_and_societal_impact: The authors clearly discuss the scope of their theoretical and empirical contributions. They note conjectures for future work. 

Societally, this work seems beneficial, and I'd like to see the authors discuss the benefits of better understanding Newcomblike problems with respect to e.g. self-driving car policies.
review_title: null

Meta-review: The reviewers agree that the formalism introduced in the paper is both interesting and potentially useful. Newcomblike decision processes (NDPs) are a generalization of Markov decision processes (MDP). As such, they augment the space of environments we can model and can potentially lead to agents that are better equipped to tackle real-world problems. Since reinforcement learning algorithms used out-of-the-box do not always yield the most desirable behavior, the NDP formalism also invites future research on the design of new algorithms.
 
We encourage the authors to elaborate on the connections between NDPs and both game theory and multi-agent reinforcement learning, since this point has come up in multiple reviews and was one of the main themes of the discussion phase. A discussion on the societal impact of the proposed approach also seems particularly pertinent. Finally, we also ask the authors to carefully consider the reviewers’ suggestions to improve the presentation. 

Decision: Accept (Spotlight)