Reinforcement Learning in Newcomblike Environments
Authors: James Henry Bell
Linda Linsefors
Caspar Oesterheld
Joar Max Viktor Skalse
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: reinforcement learning
learning in games
decision theory

Abstract: Newcomblike decision problems have been studied extensively in the decision theory literature, but they have so far been largely absent in the reinforcement learning literature. In this paper we study value-based reinforcement learning algorithms in the Newcomblike setting, and answer some of the fundamental theoretical questions about the behaviour of such algorithms in these environments. We show that a value-based reinforcement learning agent cannot converge to a policy that is not \emph{ratifiable}, i.e., does not only choose actions that are optimal given that policy. This gives us a powerful tool for reasoning about the limit behaviour of agents -- for example, it lets us show that there are Newcomblike environments in which a reinforcement learning agent cannot converge to any optimal policy. We show that a ratifiable policy always exists in our setting, but that there are cases in which a reinforcement learning agent normally cannot converge to it (and hence cannot converge at all). We also prove several results about the possible limit behaviours of agents in cases where they do not converge to any policy.

Reinforcement Learning in Newcomblike Environments
James Bell
Linda Linsefors Independent Researcher
The Alan Turing Institute London, UK j bbel@postee.ccm
1 linda. winseeors@gmal..commm com
Caspar Oesterheld Department of Computer Science Duke University Durham, NC, USA
Joar Skalse
Department Computer Science
University of Oxford Oxford, UK joar skalseecss ac uk
caspar www.ereeeeeeeedddkeeee edu
Abstract
Newcomblike decision problems have been studied extensively in the decision theory literature, but they have so far been largely absent in the reinforcement learning literature. In this paper study value-based reinforcement learning algorithms the Newcomblike setting, and answer some of the fundamental theoretical questions about the behaviour of such algorithms in these enviromments. We show that a value-based reinforcement learning agent cannot converge to a policy that is not ratifiable, i.e., does not only choose actions that optimal given that policy. This gives us a powerful tool for reasoning about the limit behaviour of agents for example, it lets us show that there are Newcomblike environments in which a reinforcement learning agent cannot converge to any optimal policy. We show that ratifiable policy always exists in our setting, but that there are cases in which a reinforcement learning agent normally cannot converge to it (and hence cannot converge all). We also prove several results about the possible limit behaviours of agents in cases where they do not converge to any policy.
Introduction
In this paper, we study decision scenarios in which outcomes depend not only the choices made and physically implemented, but also depend directly on the agent's policy. As an example, consider autonomous vehicle (AV) whose goal it is to arrive target destinations quickly while minimising the probability of collisions. In practice, AVs are careful drivers. It is easy to imagine an experiment (or learning process) that might support careful driving: on each day, let the AV decide random between a careful and more aggressive style of driving; other drivers on the road are unaware of today's chosen driving style and therefore behave the same around the AV on both types of days. Presumably the decrease in accidents on careful days outweighs the increase in travel time.
However, imagine now that type of AV widely deployed. Then many of the drivers with whom the AVS interact on the road would know a lot about how these AVs behave (e.g., from reading about AVs, from having interacted with other AVs of the drivers know that the AVs rarely take risks, they might (whether rationally or irrationally) cut them off more, not give them right of way, etc. relative to the above experiment. Indeed, this phenomenon human drivers bullying timid AVs - has been reported in the real world (Condliffe) 2016 Liu et al. 2020: cf. Cooper et al. 2019 As result, the travel times of AV much longer if always
type in the past). In partieular, if the other
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

follows (and is known to follow) careful driving policy. Moreover, some of the safety benefits of careful choices disappear if the AV adopts a careful policy.
To comfortably model situations such as this one, we introduce Newcomblike decision processes (NDPs). The name derives from Newcomb's 's problem (Nozick) 1969), descrihed in the next subsec- tion, and similar problems that have been studied in the decision-thcoretic literature. NDPs are a generalisation of Markov decision processes wherein the transition probabilities and rewards depend not only on the agent's s action, but also directly on the agent's 's policy. Thus, for example, how aggressively other cars move depends on the timidness of the AV's policy. We describe NDPs in more detail in Sect. 1.1 Importantly, the NDP model does not assume other agents in the environment to respond rationally to the agent's policy. Thus, some NDPs cannot confortably be modelled as games. (See Sect. 5.1 for more detailed discussion of the relation between NDPs and -hee-the models.)
We believe that Newcomblike dynamics are commonplace when AI systems interact with other (human or artificial) agents (Cavalcanti 2010, Sect. 5: Desterheld 2019 Sect. Conitzer 22119) The deployment of AVs is rife with such dynamics. Besides aggressiveness, it might matter whether a policy is simple and thus predictable to humans, for instance. Another real-world scenario is that of recommendation systems: most readers of this paper have some idea of how these systems work and make choices based on it. ("I would like watch this cat video, but I do, my recommendations will soon be full of them.") Thus, the success of particular recommendation depends not only on the recommendation itself, but also on the recommendation system's 'ss policy.
We are interested in learning to play NDPs. More specifically, we study the behaviour of value-based, model-free RL agents, who maintain Q-function that assigns values to state- action pairs. We define these in more detail in Sect. 1.2] As we will see, such agents do not in general learn optimal policies in NDPs (as they do in MDPs), Nevertheless, we believe that studying them is an important first step in developing practical learning algorithms for NDPs due to the combination of the following points.
A) For illustrative purposes, the examples we discuss throughout this paper are simple and emphasise the dependence of the environment on the policy. However, we think that most real-world scenarios are only partially Newcomblike. For example, most of the AV's environment changes only in response to an AV's actions and does not directly depend on the AV's policy.
B) Value-based reinforcement learning algorithms are very well developed. In contrast, we would have to develop specialised learning algorithms for general NDPs from scratch.
C) As our results will show, in some situations and when set up correctly (e.g., in terms of learning rates) value-based learning converges to optimal policies, or at least to reasonable policies, even under Newcomblike dynamics. For example, game of rock-paper-scissors against an opponent who knows the agent's 's policy, some value-based learning agents learn the optimal policy of mixing uniformly.
In light of A-C, we think that the most realistic paths to developing learning algorithms for real-world scenarios with Newcomblike dynamics will involve value-based RL. Specifically, one avenue toward realistic algorithms is to develop extensions of value-based RL and can detect and correct failures that might arise in Newcomblike dynamics. For that, we need to understand how value-based RL behaves in NDPs.
Contributions In Sect. we demonstrate that value-based RL algorithms can only converge to a policy that is ratifiable that is, to policy π for which all actions taken by т have optimal expected reward when following æ. In Sect. 3 we discuss the convergence properties of agents in Newcomblike situations, and show that there are cases where baluedbased agents must fail to converge. The action frequencies might converge, even when the policies do not. Sect. f we establish some conditions on any action frequency that agent could converge to. We also show that there are decision problems and agents where even the action frequencies do not converge.
1.1 Newcomblike Decision Processes
Newcomblike decision process (NDP) a tuple (5, A, R,7) where S is a finite set of states; A is finite set of actions; T: S x A x (S ~ A) ~ S is a nondeterministic transition function; R: x A x S (S ma A) ~ TR is a nondeterministic reward function, which we assume to be bounded; and y [0, 1) is discount
2

---

A policy π: S ~- A is function that nondeterministicaly maps states to actions. We use a(a s) to denote the probability of taking action a state s while following the policy л. I and R are functions from states, actions, and policies. In other words, they allow the outcome of a decision to depend on the distributions from which the agent draws its actions, rather than just the state and the action that is in fact taken. Also note that T(s, a, x) and R(s, a, 8', TT) are defined even if (1aa s) = O. We say that an NDP is a bandit NDP if it has only one state. We will sometimes use R(s, O, T) as shorthand for R(s a, T T(s, a, T), T), and we will sometimes omit the state from T, R. and π for bandit NDPs. Moreover, we normally let 7 = for bandit NDPs.
Consider a distribution over initial states for an agent, and let ग be its policy, let be the sequence of states it visits and o, the sequence of actions it takes. We say π is optimal for that distribution if maximises E E ?2;(z; ag ai+1, d+) Note that unlike in the MDP case the optimal policy does depend on the initial distribution, however this isn't relevant in the bandit case.
As an example consider the eponymous Newcomb's 's Problem.
Newcomb's 's Problem (Nzzick 1969): transparent box. You can see that the transparent box contains $1,000. You can choose to either take only the opaque box, or to take both boxes. The boxes have been placed in this room by an agent who can predict your policy; if he believes that you will take only the opaque box then he has put $1 1,000,000 in the opaque box, but if he believes that you will take both boxes then he has left the opaque box empty. Do you take one box, or two?
There are two boxes in front of you; one opaque box, and one
version of Newcomb's Problem can be formalised as the following bandit NDP: S = ={}}.
A = {01. 02),
{ 0 w.p. T(2)) 10 w.p. T (a,)
5 w.p. T(02) and R(a2, T) = 15 w.p. ((a))
{
R(o1, T)
where "w.p." is short for "with probability". The key feature of this NDP is that, for any fixed policy, a2 ("two-boxing") yields higher reward than a1 ("one-boxing"). But the expected reward of a policy increases in i (a1) s.t. the optimal policy is to always play 01 [ We can view Newcomb's 's problem as simple version of the AV dynamic described in the introduction, where 02 is a driving action that allows other drivers to cut the AV off at no risk.
We say that an NDP is continuous if T and R are continuous in the policy. In this paper we work mainly with continuous NDPs. This is in part because it technically convenient, and in part because we believe that continuity is satisfied in many realistic cases
1.2 Reinforcement Learning Agents
We consider value-based reinforcement learning agents. Such agents have two main components; a Q-function S x A + E. that predicts the expected future discounted reward conditional on taking a particular action in a particular state, and bandit algorithm that is used to select actions in each state based on the Q-function. Given a policy π, we use (= 8) to denote the (true) expected future discounted reward conditional on taking action a in state while following the policy ι (and conditional on all subsequent actions being chosen by T). A model-free agent will update Q over time to make converge to 4x when following æ. If Q is represented as a lookup table, the agent is said to be tabular. If the state space is large, it is common to instead approximate dx (with e.g. neural network). For simplicity, we focus mostly on tabular agents. However, some of our results (Theorems 2 and 5) only assume that Q converges to In (for some yx:) and therefore apply immediately to non-tabular agents, as long as the function approximator for 9x converges to the same 4n-
II most versions of Newcomb's Problem, the predictor directly predicts the agent's action with some fixed accuracy, and the agent is unable to randomise in way that unpredictable to the environment. This version of the problem can be modelled as a regular MDP. However, we believe that our version is more realistic in the context of AL After all. AIs can at least act pseudo-randone randomly, while the distribution according to which they choose is predictable e.g. their source code is known.
Foor example, even if the environment has direct access to the source code of the agent, it may in general not be feasible to extract the exact action probabilities from the code. However, it is always possible to estimate the action probabilities by sampling. If this is done then I' and R will depend continuously on the policy.
3

---

The Q-values can be updated in different ways. One method is to use the update rule
Qc+1 sx) + (1 (5 ac)) Qc(ac sx) + ao(st, (r) + max Qe(a st+1)),
where de is the action taken at time t, st is the state visited at time t, Ft is the reward obtained at time t, and (s, a) is a learning rate. This update rule is known as Q-learning (Watkins 1986). Other widely used update rules include SARSA (Rummery and Niranjan 1994) and Expected SARSA (van Seijen et al. 2009). For the purposes of this paper it will not matter significantly how the Q-values computed, long as it is the case that if an agent converges to a policy in some NDP and explores infinitely often then Q converges to gx- We will later see that this is the case for Q-learning, SARSA, and Expected SARSA in continuous NDPs.
There are also several different bandit algorithms. Two types of agents that are widely used practice and that will refer to throughout the paper are sefimax agents and e- e-Greedy agents. The policy of a softmax agent with a sequence of temperatures 3e E IR+, is given by:
exp(Qr(a) s)/B,)
Ta 8) ".'es (xp(Q ss)B.))
Unless otherwise stated we assume that Be + 0. The policy of an e-Greedy agent with a sequence
of exploration probabilities e, E [0, 1] is (a 9) = - E, if a = arg max, Qx s) and aa s) = (/([| 1) otherwise. Unless otherwise stated
assume that 6 - 0. We assume that e-Greedy breaks ties for argmax, so that there is always some a E A such that Ta s) = 1 - q. We say that agent is greedy in the limit if the probability that the agent takes action that maximises Q converges to 1, and we say that it explores infinitely often if takes every action in every state infinitely many times.
1.3 Some Initial Observations
We here make three simple observations about NDPs that we will use to prove and understand the results throughout this paper. First, continuous NDP always has, for each possible distribution over initial states, a policy æ that maximises the expected discounted reward E[R x]. since R ^] exists and is continuous in π, and since the set of possible policies is compact set. Also note that an NDP in which T or R is discontinuous may not have any such policy.
Second, whereas all MDPs have a deterministic optimal policy, in some NDPs all optimal policies randomise. To see this we introduce another example we will look at in this paper.
Death in Damascus Gibbard and Harper, 1976): Death will come for you tomorrow. You can choose to stay in Damascus (where you are currently) you can flee Aleppo. If you are in the same city as Death tomorrow, you will die. Death has already decided which city he will go to however, he can predict your policy, and has decided go the city where he believes that you will be tomorrow. Do you stay in Damascus, or flee to Aleppo?
We formalise this as the bandit NDP S = {s}, A = Dammseuus Alleppo }. and
0 w.p. π (a
{
10 w.p. ((
R Damascus: π
and R(UAleppo= ④)
10 w.p. x (aAlepp))
w.p. (aAleepp))
where "w.p." is again short for "with probability". In this NDP, randomising uniformly between DDmascus and AAleppo is the unique optimal policy and in particular outperforms both deterministic policies.
Note also that the Bellman optimality equation does not hold for NDPs. Even in Newcomb's s Problem, as described above, Bellman's 's optimality equation is not satisfied by the optimal policy.
2 Ratifiability
If an agent the limit only takes the actions with the highest Q-values and converges to some policy Too then it is clear that, for given state, all actions in the support of 7 must have equal expected utility given 7.c. Otherwise, the Q-values would eventually reflect the differences in expected utility and the agent would move away from Too. Similarly, if the algorithm explores sufficiently often, the

---

actions that are taken with limit probability 0 cannot be better given Too than those taken by Toc. After all. they were better, the agent would have eventually figured this out and assigned them large probability.
This condition on Te resembles well-known doctrine in philosophical decision theory: ratifica- tionism (see [Wiirich| 2016, Sect. 3.6, for an overview). One form of ratificationism is based on a distinction between decision what the agent chooses and the act that is selected by that decision. Very roughly, ratificationism then states that a decision is rational only if the acts it selects have the highest expected utility given the decision. Concepts of causality are often invoked difference between the decision, the act, and their respective consequences. Our setup, however, has such a differentiation built in: we will view the policy as the "decision" and the action sampled from it as the "act".
formalise the
2.1 Strong Ratifiability
As hinted earlier, slightly different versions of the concept of ratifiability are relevant depending on how much exploration learning algorithm guarantees. We start with the stronger version, which more closely resembles what decision theorists mean when they speak about ratifiability.
Definition 1. Let M S S be set of states. A policy a is strongly ratifiable on M if supp(r(-) s)) arg m A 2x (a s) for all E M.
In Newcomb's 's Problem the only strongly ratifiable policy is to play d2 with probability 1. In Death in Damascus, only the optimal policy (mixing uniformly) is strongly ratifiable. There can also be several strongly ratifiable policies. For example, if you play the Coordination Game of Table against an opponent who samples his action from the same policy as you then there are three strongly ratifiable policies; to select action a with probability 1, select action with probability 1, and to select with probability 1/3 and with probability 2/3.
Theorem 2. Let A be a model-free reinforcement learning agent, and let n, and Q2 be A's policy and Q-function at time t. Let A satisfy the following in a given NDP:
is greedy in the limit, i.e. for all 6 > 0, P (Qr(TT(s)) max. Qi 5) 5) - 0 as t - xo. A'ss Q-values are accurate in the limit, i.e. if n. + The as 1 - xc, then Q: + an as t - oc.
Then if A's policy converges to Too then π. oo is strongly ratifiabe on the states that are visited infinitely many times.
In Appendix A we show that the Q-values of a tabular agent are accurate in the limit in any continuous NDP if the agent updates its Q-values with SARSA, Expected SARSA, or Q-learning, given that the agent explores in- finitely often and uses appropriate learning rates. Since would expect most well well-designed agents to have accu- rate Q-values in the limit, Theorem 2 should apply very broadly. Using Kakutani's fixed-poin point theorem, it can be shown that every continuous NDP has ratifiable policy.
a 2.2
0,0
b
0,0
1,1
Table 1: The Coordination Game
Theorem 3. Every continuous NDP has strongly ratifiable policy.
Of course, the fact that ratifiable policy always exists does not necessarily mean that reinforcement learning agent must converge to it - we will consider the question of whether or not this is the case in Sect. It is also worth noting that discontinuous NDP may not have any strongly ratifiable policy.
is a topic of ongoing discussion among philosophical decision thcorists whether (strong) ratifiability should be considered normative principle of rationality, see Weirich (2016) Sect. 3.6) for details. In general, the policy π that maximises R т may or may not be ratifiable, as shown by Death in Damascus and Newcomb's problem, respectively.
There correspondence between ratificationism and many game-theorede concepts. For example, if you are playing zero-sum game against an opponent who can see your policy and plays some distribution over best responses to it then и can only be ratifiable it is maximin strategy. To give another example, if you are playing symmetric game against an opponent who follows the same policy as you then π is ratifiable if and only if (TT, x) a Nash equilibrium. Joyce and Gibbard 1998 Sect. 5) discuss the relation in more detail.
5

---

2.2 Weak Ratifiability
We now show that even without infinite exploration, Too must still satisfy weaker notion of ratifiability.
Definition 4. Let M S be of states. A policy weakly ratifiable on M if (a 8) is constant across a E supp(r(s)) for all E M.
What makes this weak version of ratifiability is that it does not put any requirements on the expected utility of actions that π does not take, it merely says that all actions that takes with positive probability must have the same (actual) g-value. As a special case, this means that all deterministic policies are weakly ratifiable. This includes one-boxing in Newcomb's 's problem. Nonetheless, there are bandit NDPs which the optimal policy is not even weakly ratifiable. For example, consider an NDP with actions 41, Q2, where R(a1,5) π (00((T(01) 1/2)² + 1 and R(a2, π (()((((a)))))))))((( 1/2)². The optimal policy mixes close uniformly (I (TT 101/200), but this is not weakly ratifiable, because R(a1, x) R(a2,1)
Theorem 5. Same conditions as Theorem but where A's Q-values are only required to be accurate in the limit for state-action pairs that A visits infinitely many times. Then To is weakly ratifiable the set of states that are visited infinitely many times.
Non-Convergencee of Policies
We have shown that most reinforcement learning algorithms can only converge to (strongly) ratifiable policies. We now consider the question of whether they always converge to a policy at all. We find that this not the case.
3.1 Theoretical Results
From Theorem 2it follows that e.g. Death Damascus an e-Greedy agent who explores infinitely often cannot converge to any policy. After all, the only strongly ratifiable policy (and thus limit policy) to mix uniformly and an e-Greedy agent never mixes uniformly.
Perhaps more surprisingly, there are also NDPs in which a (slow-cooling) softmax agent cannot converge any policy, As example, consider bandit NDP with three actions a1 02, d3 and where the rewards R(a,, π) have expectations
((0+1)) + 44-133 (iTT II (T(a)))1/4).
(1)
For i 3, we here let a1+1 01. We also require that the rewards are stochastic with finite set of outcomes such that the empirical Q-values are never exactly equal between different actions. We call this the Repellor Problem. has only one strongly ratifiable policy (mixing uniformly), but as illustrated by Figure 1 when the current policy mixes close to uniformly, the softmax agent learns (in expectation) to play less uniformly.
Theorem 6. Let A be agent that plays the Repellor Problem, explores infinitely often, and updates its Q-values with a learning rate a that is constant across actions, and let ne and Q₂ be A's policy and Qufunction at time t.. Assume also that for j # i, if (T(a)), ne me(ag) both converge to positive values, then
T((a,) - Te (a,) Qe(ar) - Q((ag) a.s.
- 00
(2)
as f - xo. Then na almost surely does not converge.
Line is satisfied, for example, for softmax agents with 8r converging to 0. Recall also that e.g. Q-learnig and SARSA are equivalent for bandit NDPs (if 0).

---

3.2 Empirical Results
Empirically, softmax agents converge (to strongly ratifiable policies) in many NDPs, pro- vided that the temperature decreases sufficiently slowly. To illustrate this we will use Aymmet- ric Death in Damascus, version of Death in Damascus wherein the rewards of Allpppo are changed to be (instead of 0) with probabil- ity π. Aleppop and (as before) 10 with the re- maining probability. This NDP has only one (strongly) ratifiable policy, namely to to Aleppo with probability 3/3 and Damascus with probability 1/3. This is also the optimal policy. We use this asymmetric version to make easier to distinguish between convergence to the ratifi- able policy and default of uniform mixing at high temperatures. Figure 2 shows the probabil- ity of converging to this policy with a softmax agent and plot of the policy see that this agent reliably converges provided that the cooling is sufficiently slow.
x(2))
m(ag)
n (0g)
The triangle shows the space of possible policies in the Repellor Problem, parameterised by the probability they assign to each of the three actions. Plotted against this space is the expected direction in which softmax agent would change its policy if playing a particular policy.
Figure 1:
run. We can
Probability Convergence
1.0
Action Probabilities
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
2000
4000 6000 8000 10000
08.0
Step
Value of
Figure The left figure plots the probability of softmax converging in Asymmetric Death in Damascus given 8n assigned a Q-value of at least 5.5 to the action of going to Aleppo after 5000 iterations. These are empirical probabilities from 20,000 runs for every a that is multiple of 0.025, and 510,000 runs for each a that a multiple 0.005 between 0.5 and 0.55. Notice the "kink" at a 0.5. Based on our experiments, this kink is not an artefact and shows up reliably in this kind of graph. The right-hand figure shows how the action probabilities evolve over time for a single run (chosen to converge to the mixed strategy) for 0.3.
against a. More accurately is plot of the fraction of runs which
However, there are also fairly simple games in which it seems like softmax agents cannot converge. Consider Loss-Averse Rock-Pi Rock-Paper-See Paper-Scissors (LARPS), the problem of playing Rock-Paper-Seiin Scper-Scissoos against an opponent that selects each action with the same probability as you, and where you assign utility to win, to a draw, and -10 to a loss. conjecture that slow-cooling softmax agents do not converge in LARPS, We have unfortunately not been able to prove this formally, but Figure presents some empirical data which corroborates the hypothesis.
Convergence of Action Frequencies
We have seen that there are NDPs which some reinforcement learning algorithms cannot converge to any policy. But if they do not converge to any policy, what does their limit behaviour look like? We now examine whether these algorithms converge to taking each action with some limit frequency, and what sorts of frequencies they converge to.
7

---

4.1 Possible Frequencies in the Bandit Case
In this section we establish number of con- ditions that must be satisfied by any limit action frequency of a value-based agent. We consider agents that converge to determinis- tie policies (such as e-Greedy agents), and we limit our analysis to the bandit case (with
1.0
0.8
0.66
y =
0.2
Let PP; A + [0, 1] be the frequency with which each action in A is taken in the first t steps (for some agent and some bandit random variable. By the law of large numbers, (a)(a) 3/2 D 0 (a) converges to 0 almost surely as f + oc. Let T. be the policy that takes action a with probability 1, and let qa Ix.-
10'
Step
NDP). Note that P
Figure This figure shows five runs of a softmax agent in LARPS, and plots π (azocc) against the total number of episodes played. The agent's Q-values are the historical mean rewards for each action, and
B. = 1/11loogg
Theorem 7. Assume that there is some sequence of random variables (a 2 0)+ s.t. 4t t-+00
0 and
for all t E N it is
Σ
xa(a") 2 Ct.
(3)
Earg max, Qc(a)
Let PF p2 with positive probability oc. Then across all actions a E supp(p"), qa qa(a) is constant.
That is, the actions played with positive limit frequency must all be equally good when played deterministically. This condition is vaguely analogous to weak ratifiability, and is proven in roughly the same way as Theorem
Theorem 8. Same assumptions as Theorem 7 If [supp(>>)) exists a' E A s.f. qa(a') 2 (a).
> then for all E supp(p²) there
This condition an instability condition. Say that multiple actions are taken with nonzero limit frequency, and that action a has the highest Q-value at time t. Then for other actions to be played with positive limit frequency, other actions must some point be believed to be optimal again (since the probability of exploration goes to zero). Hence they cannot all be worse when explored while mainly playing a, since a could otherwise be played forever.
Theorem 9. Same assumptions as Theorem 7 Let U be the Q-value ga (a(a) which (by Theorem is constant across a E supp(p²). For any a' E A - supp(y²) that is played infinitely often, let frequency I of the exploratory plays of a' happen when playing policy near elements of (Ta a &uupp(p")} Then either there exists E supp(p²) such that qa(a') S U;; or qu (a') < U.
Theorem@describes what circumstances are needed for an actions a' be played with limit frequency zero. One possibility is that exploration is done only finitely many times (in which case bad luck could lead to low Q-values). second possibility is that the exploration mechanism "rigged" so that a' is mostly played when playing policies outside the proximity of {Ta, a E supp(p")) In this case the utility of a' under some zero-limii-frequency policy might lead to low Q-values. exploration of a' is spread out more naturally then all but frequency zero of that exploration will happen near elements of (n, a E supp(p")). In this case, the only reason for a' be played with zero frequeney is that exploring a' near some of the elements of a supp(p")) makes a' look poor.
4.2 When is Frequency Convergence Possible?
We believe there are NDPs in which an e-Greedy agent cannot converge to any limit action frequency. Specifically, we believe that LARPS such an example. Figure 4a] shows the directions in which the frequencies of different actions evolve. The graph seems to have no attractor and hence we believe an e-Greedy agent cannot converge to any limit action frequency in this NDP. We have not been able to rigorously prove this. However, experiments seem to confirm this hypothesis. Figure 4b depicts five
8

---

1.0
0.8
Frequency of
0.6
10
10 10
10
(a) This figure plots the dynamics of LARPS for
Step
e-Greedy agent. Each point represents triplet (IR, Is, [p). where IR denotes fraction past time steps at which aR was estimated to be the best action,
(b) This figure shows five of e-Greedy agent in LARPS, and plots the proportion of past episodes in which the agent played "rock" against the total number of episodes played. The agent's Q-values are the historical mean rewards for each action, and its e-value is 0.01.
and similarly for fs, fp. Plotted against this space is the expected direction in which the frequencies will change. For instance, if in the past ag, was mostly played, then ap will have the highest empirical Q- values and will therefore be played more in the future.
Figure 4
runs of e-Greedy in LARPS. We can see that the agents oscillate between different actions, and that the periods increase in length.
5
Related Work
5.1 Learning in games
Some of the Newcomblike dynamics we have described in this paper could also be modelled as games, especially as so-called Stackelberg games in which one player, the Stackelberg leader, chooses a strategy first and another player, the Stackelberg follower, then responds to that strategy. For example, in the case of autonomous vehicles (AVs), we might imagine that the AV company is the Stackelberg leader and the human drivers are the Stackelberg followers.
That said, there are differences between NDPs and games. NDPs can react arbitrarily to the agent's policy, whereas in games, the other players play best (i.e., expected-utility pnpectedluillitymmxiiiiinnng response. In many real-world situations, other agents the environment cannot be comfortably modelled as sectted-utiity-mmxmiie
agents. Interactions between AVs and humans can serve examples. Most people probably do not reason rationally about small-probability. big-impact events, such as crashes. Also, humans will generally operate on simplified models of an AV's policy (even when more detailed models are available). Of course, a game-theoretie analysis can also be fruitful and address issues that we ignore: By assuming all players be rational, game theory can provide recommendations and predictions for multiple agents simultancously. while our NDP model considers single agent for a given environment. We believe that the NDP perspective provides additional insight into learning in such situations.
Despite the differences between NDPs and games, there some interesting parallels between model-free learning in NDPs and in games, where similar learning methods are sometimes referred as fictitious play (Brown) 1951). Fudenberg and Levine [1998] Chapter 2) show that fictitious play can only converge to Nash equilibrium (for similar lar results about convergence to Nash equilibrium, e.g. Mazumdaa et al. 20200 Oesterheld et al. 202T). As noted in Sect. [2.1] the concept of Nash equilibrium resembles the concept of ratifiability. /Shapley (1964) shows that fictitious play can fail converge. However, there are many special cases which convergence is guaranteed. including two-player zero-sum games (Robinson, 195I) and generic 2 x 2 games (Miyasawa 1961).
5.2 Learning and Newcomblike problems
Other authors have discussed learning in Newcomblike problems. The most common setup one in which the learner assigns values directly to policies, more generally to that which the agent chooses.

---

It is then usually shown that (among the policies considered) the agent will converge to taking the one with the highest (so-called evidential) expected utility (Albert and Heiner 2001; Oesterheld 2018). This contrasts with our setup, in which the learner selects policies but assigns values to actions. Oesterheld 2019) also studies agents who maximise reward in Newcomblike environments. However, Oesterheld does not consider the learning process. Instead he assumes that the agent has already formed belief's and uses some form of expected utility maximisation. He also specifically considers the implications of having some overseer assign rewards based on beliefs about the state of the world (as opposed to having the reward come directly from the true world state).
Discussion and Further Work
We have seen that value-based reinforcement learning algorithms can fail to converge to any policy in some NDPs, and that when they do converge, they can only converge to ratifiable policies. Decision theorists have discussed whether ratifiability should be considered to be sound normative principle. Note that (as discussed in Sect. 2 the optimal policies т are not in general ratifiable. We have also examined the limit action frequencies that agents can converge to (even when the policies do not converge). Still, there are NDPs in which many agents cannot converge even to any such frequency. We gave some results on what actions can be taken with positive limit frequency. A loose connection to ratifiability can still be drawn.
Overall, established decision decision-theoretiinn theoretical ideas can be used to understand and formally describe the behaviour of "fout-of-the-hox" reinforcement learning agents in NDPs. However, their behaviour is not always desirable. Our work elucidates possible failures. We hope that our work will thus enable more accurate reasoning about the behaviour of RL agents in real-world situations, especially when interacting with humans other agents. We hold such improvements in understanding to be broadly beneficial to the safe design and deployment of AI systems.
Throughout the paper, we have noted specific open questions related to our results. For instance, can the results in Sect. be generalised beyond the bandit setting? There are also many topics and questions about our setting that we have not touched on at all. For instance, our experimental results indicate that convergence often slow (considering how simple the given problems are). It might be desirable to back up this impression with theoretical results. We have only studied simple aalue-based model-free algorithms- the analysis could be extended to other reinforcement learning algorithms (e.g.,
or model- -ased algorithms). Also, there are further ways in which we could generalise our setting. One example to introduce partial observability and imperfect memory into the NDPs. The latter has been studied in game and decision theory (Piccione and Rubinstein 1997 Elga 2000), but recently - under the name memoryless POMDP also in reinforcement learning (Azizzadenesheli et al.] 20166] Steckkelmacher et al., 2018: cf. Conitzer 2019). What makes this especially appealing in the NDP context is that problems related to imperfect memory relate closely to Newcomblike problems (Briggs) 2010 [Schwarz] 2013). One could also look for narrower classes of NDPs in which RL agents are guaranteed to perform well in some sense.
Ultimately, the goal of this line of research is to develop learners that are able to deal effectively and safely with Newcomblike dynamics. We hope that our results will be useful in developing extensions of value-based RL that can detect and correct for the failures that arise when existing methods are applied in Newcomblike settings. However, we should also consider alternative approaches that do not hinge on insights from the present work. For example, few recent papers (on learning in non-Newcomblike settings) have considered learning to predict the expected utility as a function of the policy (as opposed to traditional Q values, which are not paremeterised by the policy) (Harb et al., 2020). In principle, Iearning such a policy evaluation function avoids the problems of the learners considered in this paper. However, it remains to be seen how practical this approach is.
Acknowledgements
We thank our anonymous reviewers for their exceedingly helpful comments. We thank the Founda- tional Research Institute (now the Center on Long-Term Risk) and the funders and organisers of the AI Safety Camp 2018 on Gran Canaria for supporting this project. Caspar Oesterheld thankful for support by the National Science Foundation under Award HIS-1814056
10

---

References
Albert, M. and Heiner, R. A. (2001). An indirect-evolution approach to newcomb's problem. CSLE Discussion Paper, No. 2001-01.
Azizzadenesheli, K., Lazaric, A., and Anandkumar, (2016). Open problem: Approximate planning of pomdps in the class of memoryless policies. In JMLR: Workshop and Conference Proceedings, volume 49, pages 1-4.
Briggs, R. (2010). Putting value on beauty. In Oxford Studies Epistemology, volume 3, pages 3-24. Oxford University Press.
Brown, G. W. (1951). Iterative solutions of games by fictitious play. In Koopmans, T. C., editor, Activity Analysis of Production and Allocation, chapter XXIV, pages 371-376. John Wiley & Sons and Chapman Hall.
Cavalcanti, E. G. (2010). Causation, decision theory, and bell's theorem: A quantum analogue newcomb problem. The British Journal for the Philosophy of Science, 61(3):69-5977
Condliffe, J. (2016). Humans will bully mild-mannered autonomous cars. MIT Technology Review.
Conitzer, V. (2019). Designing preferences, beliefs, and identities for artificial intelligence. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19) Senior Member / Blue Sky Track.
Cooper, M., Lee, J. K., Beck, J.. Fishman, J. D., Gillett, M., Papakipos, Z., Zhang, A., Ramos, J., Shah, A., and Littman, M. L.. (2019). Stackelberg punishment and bully-proofing autonomous vehicles. In Proceedings of the 11th International Conference on Social Robotics, volume 11876 of Lecture Notes in Computer Science, pages 368-377. Springer, Madrid, Spain.
Elga, (2000). Self-locating belief and the sleeping beauty problem. Analysis, 60(2):143-147.
Fudenberg, D. and Levine, D. K. (1998). The Theory of Learning in Games. MIT Press.
Gibbard, A. and Harper, W. (1976). Counterfactuals and two kinds of expected utility. Foundations and Applications of Decision Theory, 1:125-162.
Hall, and Heyde, C. (1980). Martingale Limit Theory and its Applications. New York: Academic Press.
Harb, J., Schaul, T., Precup, D., and Bacon, P.-L.. (2020). Policy evaluation networks.
Joyce, J. M. and Gibbard, (1998). Causal decision theory. In Handbook of Utility Theory, Volume
1: Principles., chapter 13, pages 627-666. Kluwer.
Kakutani, S. (1941). A generalization of brouwer's fixed point theorem. Duke Math. J., 8(3):457-459,
Liu, P., Du, Y., Wang, L., and Ju, D. Y. (2020). Ready to bully automated vehicles on public roads? Accident Analysis & Prevention, 137.
Mazumdar, F., Ratliff, I.. J., and Sastry, S. S. (2020). On gradient-based learning in continuous games. SIAM Journal on Mathematics of Data Science, 101):103-131
Miyasawa, K. (1961). On the convergence the learning process in a 2x2 non-zero-sum two-person game.
Nozick, R. (1969). Newcomb's problem and two principles of choice. In al., N. R., editor, Essays in Honor of Carl G. Hempel, pages 1 114-146. Springer.
Oesterheld, C. (2018). Doing what has worked well in the past leads to evidential decision theory.
Oesterheld, C. (2019). Approval-directed agency and the decision theory of newcomb-like problems. Synthese.
Oesterheld, C., Demski, A., and Conitzer, V. (2021). A theory of bounded inductive rationality.

---

Piccione, M. and Rubinstein, A. (1997). On the interpretation of decision problems with imperfect recall. Games and Economic Behavior, 20:3-24.
Robinson, J. (1951). An iterative method of solving a game. Annals of Mathematics, 54(2):99-331.
Rummery, G. and Niranjan, M. (1994). On-line q-learning using connectionist systems. Technical report, Cambridge University Engineering Department.
Schwarz, W. (2015). Lost memories and useless coins: revisiting the absentminded driver. Synthese, 192(9):3011-300 1-3036.
Shapley, L. S. (1964). Some topics in two-person games. In Dresher, M., Shapley, L. S., and Tucker, A. W., editors, Advances Game Theory, chapter 1. Princeton University Press.
Singh, S., Jaakkola, T., Littmann M. L., and Szepesvári, C. (2000), Convergence results for single-step on-policy reinforeement-leerning algorithms. Machine Learning, 38:287-308.
Steckelmacher, D., Roijers, D. M., Harutyunyan, A., Vrancx, P., Plisnier, H., and Nowè, A. (2018). Reinforcement learning in pomdps with memoryless options and In The Thirty-Second AAAI Conference Artificial Intelligence (AAAI-18).
initiation sets.
van Seijen, H., Hasselt, H., Whiteson, S., and Wiering, M. (2009). A theoretical and empirical
analysis of expected sarsa. In 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, pages 177-184.
Watkins, C. (1986). Learning from delayed rewards. PhD thesis.
Weirich, P. (2016). Causal decision theory. In The Stanford Encyclopedia of Philosophy. Spring 2016 edition.
12


Reviews:
[{"review_id": "oJBO9Wl1bkx", "reviewer": "Reviewer_xfAj", "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:\n1. 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\n2. 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\n3. with the help of several bandit examples, show that standard RL such as QL and SARSA is not required to converge at all.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nMy 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "===== possible limitations and/or questions for authors: =====\n\nsignificance: 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?\n\nconnection 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.\n\nother 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?\n\n===== some other minor comments: =====\n\n- 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.\n- 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. \n\n===== references =====\n\nHarb, Jean, et al. \"Policy evaluation networks.\" arXiv preprint arXiv:2002.11833 (2020).\nBorsa, Diana, et al. \"Universal successor features approximators.\" arXiv preprint arXiv:1812.07626 (2018).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "lW6kpZFTV3u", "reviewer": "Reviewer_MhxB", "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). \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nThe main weakness of this paper that limits its impact is lack of clarity, which could be improved as follows:\n- 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\". \n- 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\".\n- Use more readable formatting for the second-last paragraph of the introduction (e.g. a numbered list).\n- Provide a statement of Newcomb's problem in the introduction, since not all readers will be familiar with the problem. \n- Provide a plain language description of the Death in Damascus problem in section 1.3.\n- 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. \n- Clarify how this paper differs from the previous work on Newcomblike problems referred to in \"Another more sophisticated setting was studied by Oesterheld (2019)\" \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}, {"review_id": "cyU7zxVtwX5", "reviewer": "Reviewer_4LMa", "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n**Quality.** The work seems sound, although I haven't gone through most of the math. The experiments are simple but illustrative. \n\n**Clarity.** I overall found the paper clear. The authors use intelligent examples and reasoning throughout the paper, and the graphics are good.\n\nThat said, I have several points of confusion:\n* Below page 89, what does \"w.p.\" mean? Given that you have extra room, can you remove the abbreviation?\n* I didn't understand 304-313 explaining theorem 9. Maybe a more concrete example would help.\n\n**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.\n\n**Post-rebuttal**: I thank the authors for their clarifications. My score remains unchanged: accept.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors clearly discuss the scope of their theoretical and empirical contributions. They note conjectures for future work. \n\nSocietally, 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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Ap_sgVBe1L", "reviewer": "Reviewer_L2sm", "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:\n\n1. 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.\n2. 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).\n3. Nonetheless, there exist continuous NDPs where typical RL algorithms almost surely do not converge to the strongly ratifiable policy.\n4. 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).\n5. 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).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall score\n-------------\n\n**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.\n\n**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.\n\nThe 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).\n\n**Quality:** The results are interesting and look correct to me (though I have not checked the proofs in detail).\n\n**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.\n\nRelation to game theory\n-----------------------\n\nNewcomblike 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).\n\nThe 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?\n\nMany 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):\n\nMazumdar, Eric, Lillian J. Ratliff, and S. Shankar Sastry. \"On gradient-based learning in continuous games.\"\nLetcher, Alistair, et al. \"Stable opponent shaping in differentiable games.\"\n\nQuestions\n---------\n\nHow do NDPs relate to game theory and multiagent RL? What novelty do NDPs introduce that could not already be modeled in these areas?\n\nI 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.)\n\nMinor nitpicks\n--------------\n\nSince 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]$).\n\n> The key feature of this NDP is that regardless of the policy a2 (“two-boxing”) yields a higher reward than a1 (“one-boxing”).\n\nI 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”).”\n\n> This is because the optimal policy in Newcomb’s Problem does not select optimal actions.\n\nI’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”.\n\n> it is clear that all actions in the support of π∞ must have equal expected utility given π∞.\n\nI would change this to “it is clear that, _for a given state_, all actions in…”", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See main review.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)