Newcomb's paradox is an iconic paradox of decision theory. Introduced by Nozick [1969] , the problem involves a player, call her Alice, and a predictor that we will name Omega. Omega predicts Alice's behavior, and, essentially, determines her reward based on this prediction. This will then put Alice into some seemingly impossible dilemma.
On one hand, a seemingly causal argument suggests that Alice should ignore her predictability, especially once Omega's prediction has already been made. This argument suggests that Alice should then adopt a strategy called 2-box.
On the other hand, by modifying her behavior, and assuming that Omega's prediction is really reliable, Alice seems able to bias Omega's prediction so that it becomes aligned with Alice's interest. This suggests that Alice may be able to hack her predictability to gain more rewards -a strategy known as 1-box. More thorough details are provided in Section 3.1.
Remarkably, scholars are extremely divided on what strategy Alice should adopt. In fact, Newcomb's paradox seems to be unveiling a fundamental gap in our understanding of decision theory, and thus of related topics such as free will, game theory and algorithm design. Because of this, over the last half a century, Newcomb's paradox has received a lot of attention from philosophers (Schlesinger [1974] , Locke [1978] , Horwich [1985] , Nozick [1994 Nozick [ , 1997 , to name a few), mathematicians (Gardner [1974] , Wijayatunga [2019] , Giacopelli [2019] ), economists (Broome [1989] , Sugden [1991] , Weber [2016] ), political scientists (Brams [1975] , Frydman et al. [1982] ), computer scientists (Aaronson [2013] , Everitt [2018] ) and psychologists (Bar-Hillel and Margalit [1972] ).
In addition to connections to fundamental philosophical problems, Newcomb's paradox has been linked to practical problems, such as the voting dilemma (see Elster [1987] ). Assuming that Alice's vote has a negligible effect, but is time-costly for her, intuitively, the equivalent of 2-box would be to argue that Alice's optimal selfish strategy is to not take the time to vote. However, it has been argued that, by going voting, Alice changes what Alice would predict about the behaviour of individuals similar to her, thereby significantly increasing the probability that Alice's favorite candidate will get elected -which is in Alice's selfish interest. A 1-box argument suggests that Alice should vote.
In this paper, we present a novel analysis of Newcomb's paradox. The core idea of the analysis is a clear separation between an individual's epistemic system, and their decision system. The epistemic system will be assumed to be purely Bayesian, which means that all of its thoughts result from data and the laws of probability. In particular, thereby, the epistemic system can engage in counterfactual reasoning, to determine what decisions yield the largest counterfactual expected rewards.
As any good Bayesian, at any point in time, the epistemic system must also assign a probability to any future event. This evidently includes the individual's future decision. Now, in principle, such a probability could take the values 0 or 1. However, we stress the fact that an epistemic system with such a perfect knowledge of the individual's decision cannot engage in a counterfactual reasoning. Under perfect knowledge, and under the laws of probability, Bayesian counterfactual reasoning becomes nonsensical.
As a result, most of this paper discusses the arguably more realistic case of imperfect knowledge of the decision system. This means that the epistemic system fails to know with full certainty the algorithm executed by the decision system, and the decision system's inputs. In such a case, in Section 2, we prove Theorem 1, which says that no decision system can be expected to guarantee counterfactual optimization. We then discuss consequences of the theorem for decision theory.
In Section 3, we then tackle a generalization of Newcomb's paradox, under the assumption that a Bayesian Omega has collected a supset of Alice's data. We show that the counterfactual optimality of a decision strongly depends on the extent to which Alice believes the predictor Omega to know more than her about her decision system. Indeed, if Alice does not believe that Omega knows more than her, then 2-box is the only counterfactually optimal decision. But if Alice expects Omega to know a lot more to the point of being quasiomniscient, then 1-box becomes the only counterfactually optimal decision. These findings are formalized by Theorem 2, and by its diverse corollaries (see Section 3.3).
Section 4 will then discuss our results, and raise further questions. First, we analyze the impact of relaxing the assumptions of the previous section. Second, we discuss implications of our analysis to practical Newcomb-like problems. Third, we generalize the main idea of the paper, namely the separation of epistemic and decision systems, to a further separation of different systems of any information processing entity.
Finally, Section 5 concludes.
In this section, we show that no entity can guarantee counterfactual optimization. To understand this claim, we first insist on the distinction between an entity's epistemic system and their decision system. We then stress the fact that counterfactual optimization is not an algorithm, but a property, which results from the interaction between the epistemic system, the decision system and the problem at hand. We then state and prove the impossibility of counterfactual optimization, and discuss consequences.
In this paper, we study how an information processing entity, like a human, a machine or an organization, infers a world view and makes a decision. Confusingly, these two different tasks seem entangled. On one hand, it seems important to first infer a world view before making a decision. But as highlighted by Newcomb-like paradoxes, it seems that a decision can sometimes inform a world view.
To disentangle views and decisions, we propose to clarify the distinction between these two tasks. In fact, we will assume that each task is handled by a specific system of the entity. More specifically, in this paper, we focus on an entity that we call Alice, which possesses both an epistemic and a decision system. We call them respectively Emma and Dan. Emma will infer the state of the world based on her data. Dan will compute decisions based on his data.
Except in Section 4.2.2, we assume Emma to be a pure Bayesian. In other words, Emma will apply solely the laws of probabilities to compute credences and expectations 1 . In particular, Emma's credence in a theory T of the state of the world, given the data D E she collected, will be given by Bayes rule:
Note that we adopt here the purely Bayesian interpretation of probabilities. Namely, as discussed by Laplace [1840] , such probabilities describe an entity's knowledge and uncertainty, and apply even in a deterministic universe.
In this paper, we will discuss only Emma and Omega's credences, mostly under the assumption that they have common priors, and that Emma's data D E are common knowledge. As a result, without loss of generality, we omit the conditioning by D E in our notations.
In our paper, we analyze Dan's decision through the lenses of purely Bayesian counterfactuals.
Definition 1. Emma counterfactually prefers a decision X if, for any alternative decision Y, Emma estimates the counterfactual expected rewards to be larger assuming X than assuming Y, i.e.
(2)
Recall that the expectations are implicitly also conditioned by Emma's data D E .
Counterfactual optimality is often invoked to argue in favor of one decision over the other. In the case of the COVID-19 pandemic, for instance, some observers have argued that lockdown was not actually as bad for the economy as one might expect. Their argument was not that the economy did not suffer during the lockdown; rather, they argued that the counterfactual world without a lockdown decision would have seen a similar blow to the economy. By then also taking public health into consideration, such observers argued that lockdown was very probably counterfactually optimal. In other words, these observers have essentially argued that
where Welfare refers to some sort of public good, which involves both public health and financial safety. Interestingly, some opponents agreed with the general approach to determine if Lockdown was a good decision, but disagreed with the estimation of the counterfactual expectations 2 .
1 This contrasts with some versions of causal decision theory that invoke Pearl and Mackenzie [2018]'s "do-operator". This operator is thus added to Bayesianism, and also depends on some causal modeling of the problem. As a result, we do not consider it to be purely Bayesian.
2 Note that the counterfactual expectations should be also all conditioned on all the available data at the moment of the decision lockdown, including the dangerous spread of the COVID-19 disease.
Counterfactual optimization is also often invoked in the analysis of Newcomb's paradox, which is presented in Section 3.1. Again, the disagreements often lie in the estimation of the counterfactual expectations. The 1-boxer will typically argue that E [R | 1-box] = R, where R is the content of the opaque box if the predictor Omega predicts 1-box, while the counterfactual expected rewards are E [R | 2-box] = r < R, since Omega would then leave the opaque box empty. However, the 2-box will argue that E
Clearly, both cannot be right simultaneously. Section 3 will aim to clarify what is going on.
One feature of Bayesianism is that, if P [D] = 0, then P [T | D] is ill-defined. In a sense, a Bayesian cannot consider events that they have completely discarded. But this raises a serious technical issue, if we assume that Emma knows for sure Dan's decision X. Indeed, Emma would then be completely discarding the possibility that Dan makes an alternative decision Y. In other words, Emma may believe P [Y] = 0. But then, the counterfactual expectation E [R | Y] would be ill-defined, which makes counterfactual optimization nonsensical. To resolve this issue, in this paper, we will only consider Bayesians with imperfect knowledge.
Definition 2. A Bayesian has imperfect knowledge about X if, for any possible value x of the event, the Bayesian assigns a strictly positive probability to X = x.
In the case of Alice, it seems actually reasonable to assume that, especially in practice, Emma cannot guarantee that Dan will execute a given decision algorithm. After all, even if Emma carefully inspected Dan before Dan makes a decision, and even if Emma knows exactly the data given to Dan, Dan may still slightly change before the computation is executed. In other words, Emma may precisely know what Dan was like seconds ago, but she cannot know for sure what Dan will be doing in a few seconds, when Dan actually runs his computation to deliver a decision. It thus seems reasonable to assume that Emma has an imperfect knowledge of Dan's decision.
Finally, we can state the main result of this section. It asserts that no entity can guarantee counterfactual optimization.
Theorem 1. There exists a decision problem with n options, for which any entity with imperfect knowledge assigns a probability at least 1 − 1 /n to counterfactually bad decisions.
Proof. Consider n opaque boxes. Dan must choose one of the boxes. Denote Box-i the fact that Dan chooses the i-th box.
But, now assume that Emma gets convinced that a predictor Omega has the same data as her and knows her prior. As a result, Emma believes with probability 1 that Omega can compute Emma's credence P [Box-i] in Dan deciding Box-i. Suppose also that Emma also believes with probability 1 that Omega decides the content of box i as follows. Omega computes the smallest value * of i such that P [Box-i] ≤ 1/n. Omega then sets R * = 1, and R j = 0 for j = * .
Then, from Emma's perspective, given that she knows the rewards R i 's, any decision Box-j different from Box- * is counterfactually bad. However, we also know that Emma also assigns a probability at most 1/n to Box- * . Thus, according to Emma, there is a probability at least 1 − 1 /n that Dan's decision is counterfactually bad.
Note that our proof assumes that Emma knows for sure that Omega knows Emma's data and prior. Interestingly, it is however robust to relaxing this condition, and to assuming that Emma only strongly believes that Omega knows her data and prior. This then yields a probability of at least 1 − 1 /n − o(1) of a counterfactually bad decision, where o(1) denotes a term arbitrarily small by considering that Emma's credences are arbitrarily close to 1.
It is noteworthy that Theorem 1 does not apply to the framework of AIXI, a counterfactually optimal decision algorithm introduced by Hutter [2001 Hutter [ , 2004 . In this framework, an entity called AIXI interacts with its environment by making decisions based on its observed past data, and the environment responds to AIXI's decision by providing new data and a reward 3 .
Essentially, AIXI escapes our impossibility theorem because the AIXI framework prevents external entities from making AIXI's reward depend on AIXI's uncertainty about its decision. More precisely, AIXI's expected rewards given AIXI's decision X are assumed to be independent from AIXI's uncertainty about deciding X. Formally, this assumption enforces the equality 4
for any values of p and q. As a result, AIXI's credence P [X] in the fact that it will decide X cannot be exploited by the environment to bias AIXI's rewards. This contrasts with our proof of Theorem 1 in which, if P [X] is large, then the reward given X would be designed to be small.
Unfortunately, the restricted framework of AIXI has been argued to make AIXI unrealistic. In particular, the fact that the environment cannot exploit its understanding of AIXI seems incompatible with embedded agency, as discussed by Demski and Garrabrant [2019] . Embedded agency assumes that any entity must be part of its environment 5 . Given embedded agency, it then seems that any entity can be analyzed by some other entity Omega of the environment. Omega can then exploit its analysis to make counterfactual optimization impossible, as proved by Theorem 1.
Perhaps the most important take-away of Theorem 1 is that counterfactual optimization cannot be a decision algorithm. Rather, it should be regarded as a property that no decision algorithm always satisfy. At best, a decision algorithm should be designed to often satisfy counterfactual optimization. However, the more general question of what ought to be expected from a "good" decision algorithm seems still far from being resolved.
Theorem 1 may share similarities with the no-free-lunch theorems in learning theory (Wolpert [1996] , Joyce and Herrmann [2018] ). These theorems suggest that there is no canonical property that identifies the "good" learning algorithms, which are arguably what a "good" epistemic system should implement. Instead, the defense of Bayesianism, like in Hoang [2020], rests upon a myriad a desirable properties, some of which can be proved to be unique to Bayesianism, such as robustness to Dutch book arguments (Teller [1973] , Skyrms [1987] ), compatibility with logic (Cox [1946, 1963] , Jaynes [2003] ) and statistical admissibility (Wald [1947] , Robert [2007] ).
In fact, just as Bayesianism actually includes a large family of epistemologies, each derived from a given prior, the right path forward in decision theory might consist of proving that some desirable property can only be satisfied by decision algorithms taken from a certain family. Unfortunately, this research direction is out of the scope of the present paper.
In this section, we analyze Newcomb's paradox under the lens of Bayesian counterfactuals. But first, we need to consider a slight generalization of Newcomb's paradox, which more adequately fits the Bayesian framework.
In this paper, we consider a slight variation on Newcomb's problem to make it more realistic. In particular, we will care about the data that enables the predictor to make its prediction. Let us describe the problem we consider.
Alice enters a room with two boxes A and B.
• Box A is opaque.
Alice cannot see what is inside. But she knows how the content of Box A was decided, which is discussed below.
• Box B is transparent. Alice sees that Box B contains a reward r > 0.
Alice is then told that she must decide between two strategies.
• The 1-box strategy consists of only taking Box A.
• The 2-box strategy consists of taking both Box A and Box B.
What makes Newcomb's paradox interesting is the way the content of Box A is decided. In some classical versions of Newcomb's paradox, some omniscient entity Omega makes a prediction. If Omega predicts that Alice will 1-box, then Omega puts a large reward 6 R in Box A. Otherwise, if Omega predicts that Alice will 2-box, then Omega leaves Box A empty. However, the omniscience assumption is reasonably criticized for being too unrealistic. In this paper, we will instead assume that Omega is an information processing system which exploits huge amounts of data about Alice and about the world. Based on this large database D Ω , Omega infers a probability ω P [1-box | D Ω ] that Alice will 1-box. Now, given this probability guess ω, Omega will throw a biased coin, which has a probability ω to land on heads. If the coin lands on heads, Omega will put the reward R in Box A. Otherwise, Omega leaves Box A empty.
Note that the classical version of Newcomb's paradox is retrieved by assuming that Omega knows Alice's decision process and all the inputs to this process. Indeed, Omega can then simply simulate this decision process to determine Alice's decision. Our variant is thus a natural generalization of the classical paradox. Now, Alice knows how Omega operates. She knows that Omega applies Bayes rule and she knows that Omega has processed a huge amount of data that Alice cannot access. Alice wants to maximize her expected (counterfactual) rewards. Alice now has to choose between the 1-box and the 2-box strategy. What should she do?
3.1.1 Can Omega really know more?
The odd feature of Newcomb's paradox is the assumption that some external observer Omega can better know Alice than she knows herself. At first sight at least, it may seem that no one can better guess what Alice will decide than Alice herself, right before she makes her decision.
However, Libet [1993] 's famous experiment suggests that this may not be the case. An algorithm processing some magnetic resonance imaging of Alice's brain may then be better able to predict some of Alice's decision -at least a fraction of a second before the decision is made. More generally, it seems in fact clear that humans' decision systems are largely unknown to them. Similarly, and perhaps more strikingly, large institutions often hire external auditing companies to better understand how their decisions are made. Likewise, understanding in details what decisions were made by the YouTube recommender systems, and how they were made, is arguably largely out of reach of any data analytics systems within YouTube.
Perhaps a more realistic way for Omega to predict Alice's decision is to collect large amounts of data, not only about Alice, but also about entities similar to Alice. Typically, a philosopher who posed Newcomb's paradox to generations of students might have gained a remarkable capability to predict their current students' intuitions for the Newcomb's paradox. Similarly, by analyzing all sorts of data available on social medias, an algorithm could detect patterns that would allow it to reliably predict what a given social media user may decide. In fact, Wang and Kosinski [2018] designed one such algorithm, then replicated by Leuner [2019] , that achieved superhuman performances at predicting sexual orientations from human faces.
Let us focus on the case where Emma believes that Omega has the same prior as her, and has a supset of her data. We denote p P [1-box] Emma's prior on 1-box, and σ 2 V [ω] her prior variance on Omega's prediction. Assuming that Emma has imperfect knowledge of Dan then corresponds to 0 < p < 1.
Remarkably, under our assumptions, we can determine Emma's counterfactual preferences based solely on the variables p and σ 2 .
Theorem 2. Assume that Emma has imperfect knowledge of Dan. Suppose also that Emma believes that Omega is Bayesian, has the same prior as her and knows a supset of her data. Then, Emma counterfactually prefers to 1box, if and only if, we have r R ≤ σ 2 p(1 − p) .
Unsurprisingly, the larger R is relatively to r, the more 1-box will tend to be preferable. But perhaps what's more interesting is the right-hand side. Note that the quantity p(1 − p) is essentially the variance according to Emma's prior on what Dan will do. Thus, the right-hand side compares the variance of Omega's prediction to the variance of Dan's decision. Or, put differently, it is a measure of how much Emma expects Omega to know more than her about Dan. Intuitively, the more Emma knows about Dan, the more she will counterfactually prefer to 2-box. But the more she feels that Omega knows more than her, the more she will counterfactually prefer to 1-box.
Thus, at its core, Newcomb's paradox really seems to be about how much an entity believes that an observer can better know them than they know themselves. This may seem extremely confusing at first glance. But separating our epistemic system from our decision system arguably helps to clarify the origin of the paradox. Indeed, Newcomb's paradox is actually rather about how much the observer can better predict the output of the entity's decision system, than what the entity's epistemic system can predict. In particular, if this epistemic system is unreliable, then it may not be that hard to outperform it.
Before proving Theorem 2, let us first note the following lemma, which will be critical in the analysis of Newcomb's problem. The lemma states the validity of the argument of authority, if the authority is more a knowledgeable honest Bayesian.
Lemma 1 (Argument of authority). If Emma believes that Omega is an honest Bayesian, that Omega has the same prior as her, and that Omega has a supset of her data, then Emma should believe whatever Omega says. More formally, we have
Proof. To clarify, denote D p the set of data D Ω such that P [T | D Ω ] = p. Then D p excludes all data which do not satisfy this. By the law of total probability, we see that P [T | D p ] is then necessarily an average of terms P [T | D Ω ], for D Ω ∈ D p . But all such terms equal p, hence the theorem.
The proof of Theorem 2 yields some insights into the mechanisms at play. In fact, it rests on the following four interesting observations, on what Emma predicts based on her uncertainty about Omega's prediction. All the lemmas implicitly make the same assumptions as Theorem 2.
Lemma 2. Emma's prior p on Dan deciding to 1-box is equal to the expectation of her prior on Omega's prediction, i.e. p = E [ω].
Proof. According to the law of total probability, P
By Lemma 1, if Emma learned Omega's prediction ω = P [1-box | D Ω ], then she too would assign a probability ω to Dan deciding to 1-box. Therefore,
Lemma 3. Emma assigns a prior probability p to Box A containing the large reward R, P [A = R] = p.
Proof. According to the law of total probability, P
By the decision algorithm of Omega (see Section 3.1), we have P
Lemma 4. Emma's posterior belief that Box A contains the large reward R, given a 1-box decision by Dan, is given by P
Interestingly, this quantity is larger than the prior probability, especially if the variance σ 2 on Omega's prediction is large and if Omega is expected to essentially predict 2-box..
Proof. By the law of total probabilities, we have
In the second line, we used Bayes rule. In the third line, we use the conditionally independence of events A = R and 1-box, given ω, as well as Lemma 2. In the fourth line, we exploited the way the decision of A = R is decided by ω, as well as the Lemma 1 which implies P [1-box | ω] = ω. The last line also uses the definition of σ 2 .
Lemma 5. Emma's posterior belief that Box A contains the large reward R,
given a 2-box decision by Dan, is given by P
Perhaps not surprisingly given Lemma 4, this posterior is smaller than the prior, especially for large values of σ 2 and when Omega is expected to essentially predict 1-box.
Proof. Recall that, by Lemmas 2 and 3, we have P [A = R] = p = P [2-box]. Now, Bayes rule yields
where, in the fourth line, we used Lemma 4.
Theorem 2 then follows from our four previous lemmas.
Proof of Theorem 2. From Lemmas 4 and 5, we have
Now, Emma counterfactually prefers to 1-box if and only if the former conditional expectation is larger than the second, which is equivalent to saying
Rearranging the terms yields the theorem.
In this section, we discuss the corollaries of Theorem 2. These corollaries yield greater insight into the key variables of Newcomb's paradox.
Corollary 1. For any rewards R > r, if Emma has imperfect knowledge of Dan and if she expects Omega to have the same prior and data as her, then she will counterfactually prefer to 2-box.
Proof. This is the special case where σ 2 = 0.
In particular, if Emma is almost sure than Omega has the same prior and data as her, and if she is almost sure that Dan will 2-box, then she is almost sure that Dan's decision is counterfactually optimal.
In this section, we show that σ 2 is an increasing function of the size of the data D Ω that Emma suspects Omega to have. In other words, the more Emma thinks that Omega has a more data than her, the more she will lean towards counterfactually preferring to 1-box.
Lemma 6. Denote ω(D) = P [1-box | D] the prediction made based on data D about Dan. If we know with that the data D + Ω contain data D Ω , even though both are unknown, then
Proof. Note that
where, in the third line, we used the fact that, if D + Ω contains D Ω , then ω(D Ω ) = E ω(D + Ω ) D Ω .
]. This means that, for a Newcomb paradox with Omega + that has more data than Omega, the variance σ 2 of the predictor's prediction is larger. In particular, as Omega collects more and more data, Emma will tend more and more towards 1-box.
Unsurprisingly, if the reward r of Box B is necessarily larger than the reward of Box A, then 2-box is counterfactually preferable.
Corollary 2. If r ≥ R, if Emma has imperfect knowledge of Dan, and if she expects Omega to have the same prior and more data, then Emma counterfactually prefers to 2-box.
Proof of Corollary 2. Lemma 6 with D + Ω = D Ω ∧ 1-box implies that p(1 − p) ≥ σ 2 . If r ≥ R, then we have r R ≥ 1 ≥ σ 2 p(1 − p) .
One particularly interesting particular case is that of a quasi-omniscient Omega, which knows a lot more about Dan than Emma does. We formalize quasiomniscience as follows.
Definition 3. Emma believes Omega to be quasi-omniscient about Dan, if Emma rules out an uncertain prediction by Omega. Formally, Omega is
Note that δ-omniscience is a property that depends on Emma's prior on the data D Ω that Omega has access to. In fact, it is arguably not a fundamental property of Omega itself.
One thing that makes this case interesting is that, for a fixed prior p, especially in the limit δ → 0, the variance σ 2 gets maximized. In particular, throughout this section, we assume 0 < δ < min{p, 1 − p}, which allows to guarantee the fact that the conditional expectations that we will consider are well-defined.
Lemma 7. If Emma believes that Omega knows more and is δ-omniscient,
Proof. First, recall that, by Lemma 2, E [ω] = p. Now, denote q P [ω ≥ 1 − δ]. By the law of total probability,
and thus q ≥ p − δ. Therefore, σ 2 = E ω 2 − p 2 . Now, note that
Therefore, we have
We can then state the following insightful corollary of Theorem 2.
Corollary 3. If Emma has imperfect information about Dan, if she believes Omega knows more than her, and if she believes Omega to be δ-omniscient, then, in the limit δ ≪ min{p, 1 − p}, Emma counterfactually prefers to 1-box.
. We conclude by applying Theorem 2.
In other words, for any given values of R > r, and for any given prior uncertainty from Emma about Dan's decision, there is a sufficiently omniscient Omega such that Emma will counterfactually prefer to 1-box. Or, put differently, if Alice is pretty sure that she will 1-box, and if she is pretty sure that Omega is pretty-pretty-pretty sure of what Alice decide, then Alice will be pretty sure to make a counterfactually optimal decision. This conclusion may clarify some of the disagreements about Newcomb's paradox. If one believes that Alice fully knows what she decides, then it seems meaningless to consider that Omega could know a lot better than Alice what she will decide. Similarly, by considering that Omega is fully omniscient, one may be tempted to exclude some scenarios, such as Omega being wrong. But such scenarios are arguably not quite Bayesian, nor realistic. By more carefully considering imperfect knowledge, purely Bayesian counterfactuals in Newcomblike problems arguably seem less mysterious.
While our theorems closed a few problems, they arguably raised even more questions. In this section, we discuss take-aways and future research directions.
The results of Section 3 assumed that Emma believes that Omega has the same prior as her, as well as a supset of her data. In this section, we discuss the challenges to remove this assumption.
If Emma has a supset of Omega's data, then she would know Omega's prediction ω. It can be shown that, as a result, if Emma has imperfect knowledge of Dan, then so does Omega. But this also implies that Omega's actual decision to put R in Box A is not fully known to Omega. It may thus also be imperfectly known to Emma.
Unfortunately, this last bit of uncertainty may be where a Newcomb-like paradox kicks in. Typically, Omega's coin toss might be further biased by another entity Omega + that does have more data than Emma 7 .
Note though that if Emma believes that the coin toss is independent from Dan's decision given Emma's data, then Emma can be proved to counterfactually prefer to 2-box. Similarly, if Omega's uncertainty on the content of Box A disappears, for instance if Omega now decides to put R in Box A if and only if its credence in 1-box satisfies P [1-box | D Ω ] ≥ 1/2, then Emma will also counterfactually prefer to 2-box.
The most general and realistic case is evidently when Emma and Omega have access to very different data. In such a case, Lemma 1 does not apply. Unfortunately, as a result, Emma's counterfactual preferences are then much harder to analyze.
Nevertheless, it seems that the global take-away of our analysis still applies. Essentially, the more data Emma has compared to Omega, the more 2-box probably seems counterfactually preferable to her. Conversely, the more data Omega has, the more it seems that Emma will counterfactually prefer to 1box. However, we leave open the problem of proving this mathematically.
The other important assumption we have made throughout our analysis is that Emma believes that Omega has the same Bayesian prior as her. One way to weaken this assumption is to suppose instead that Emma has a prior on Omega's possible priors. By expliciting the prior on priors, it is then only a computation for Emma to determine what decision is counterfactually preferable.
Again, it seems intuitive that, as Omega gathers more and more data, Emma will tend to counterfactually prefer to 1-box. We conjecture that, even in this case, if Emma assigns a strictly positive probability to Omega's actual prior, and if she believes Omega to be sufficiently quasi-omniscient, then she will counterfactually prefer to 1-box. This has yet to be proved though.
Our generalization of Newcomb's paradox arguably made it more realistic. However, there still seems to be a gap between our analysis and practical Newcomblike problems.
At its heart, Newcomb's paradox is about the possibility for an external observer to better predict what we will decide than what we can predict ourselves. Crucially, we showed that such an external observer does not need to be some supernatural omniscient entity. Any observer with vastly more data than us could potentially predict our future decisions better than we can -and use this to trick us.
Arguably, billions of dollars are currently being invested to create such algorithmic observers. By leveraging the huge amounts of data provided by their users, social media algorithms are constantly trying to predict how likely we are to click on the contents that they decide to recommend to us. Meanwhile, the way we use these social medias, often without paying our utmost attention to our decision systems, means that we may make decisions without even realizing it. In such a case, it seems reasonable to argue that algorithms actually already know many of our future decisions better than we do ourselves.
It may be interesting for future work to investigate how Newcomb's paradox can inform us on what we ought to do in such contexts; or at least, on what decisions would be least counterfactually wrong.
We assumed that Emma and Omega are pure Bayesians. This hypothesis turned out to be extremely useful to gain insights into Newcomb's paradox. However, it is noteworthy that, in general, Bayesianism requires unreasonable computing resources, and thus cannot be applied exactly in practice, as explained by Solomonoff [2009] . This leaves us with the question of the robustness of our results, if we now consider non-Bayesian entities.
Note that the assumption that Omega is (believed to be) Bayesian is not critical. The critical feature of our analysis is rather that Omega is expected to have more data than Emma, which allows Omega to better predict what Dan will decide. In fact, it suffices that Omega's prediction ω remains strongly correlated with Dan's decision, even given Emma's data.
The case of Emma is slightly more problematic, as Emma needs to apply the law of probabilities to compute counterfactuals. However, again, by assuming that she can reasonably well approximate the computation of the counterfactuals, then it is sensible to consider that she is engaging in approximate Bayesian counterfactual reasoning. The general take-aways of our analysis would then apply.
Even if epistemic systems know exactly their decision algorithms and the inputs of these algorithms, they may be incapable to derive the decision unless they perform themselves the computations of the decision algorithms. This postulate was called computational irreducibility by Wolfram [2002] . A consequence of this postulate is that computational limits actually add another source of uncertainty, which cannot be taken into account by the Bayesian framework alone, as explained by Hoang [2020] .
More generally, as argued by Aaronson [2012] , computational complexity theory may be critical to understand diverse philosophical paradoxes. Its implications to Newcomb's paradox have yet to be analyzed.
The core idea of our analysis was a clear separation between an entity's epistemic system and their decision system. In particular, we exploited the fact that the epistemic system should have some epistemic uncertainty about their decision system, which we argued to be critical to understand Newcomb's paradox. However, the decomposition of any entity into different systems with different tasks can be taken further, as argued by Hoang [2019].
Interestingly, our analysis highlights the importance of data in Newcomb's paradox. Indeed, we saw that Emma will consider that 1-box is counterfactually preferable if and only if she expects Omega to have access to sufficiently more data D Ω so that Omega's uncertainty about Dan's decision is greatly reduced. Note that, however, we did not discuss how Omega would access such data.
More generally, data is arguably critical for any entity, both for the epistemic and the decision systems. Therefore, it seems critical for the entity, or for any analysis of the entity, to carefully design or understand their data collection system. Arguably, in the case of the COVID-19 crisis, in at least some parts of the world, this system was defective, typically because of a lack of tests or because of data misreporting. In practice, improving data collection systems is a key aspect of improving an entity.
In particular, especially for large-scale critical applications, designing a quality data collection systems seems to require features such as data authentication, data storage and data communication. Results in the fields of cryptography, differential privacy or distributed computing may add insights into Newcomb-like problems.
In this paper, we assumed that the rewards were given by Omega. In fact, Omega was essentially Emma's reward system.
In practice, most entities' rewards are much more complex to compute. Humans may care about happiness, glory or flourishing, or a certain combination of all three. Organizations may want to advance their cause, publish papers, protect their nations, save lives or make their business sustainable. Finally, many algorithms have been designed to maximize profits, clicks or user attention.
In most cases, rewards are arguably what determine these entities' decisions the most, and thus their impacts on the world. In particular, a watch-time maximizing algorithm may flood the Internet with clickbait, virulent and unreliable videos, which may then encourage climate denialism Allgaier [2019] , promote dangerous health recommandations Johnson et al. [2020] or normalize radicalizations Ribeiro et al. [2020] , while a profit-maximizing company may disregard its externalities, and a drug addict may neglect the long-term effects of their drug consumption. Note that, in these examples, the rewards to be maximized are not harmful in themselves; but they are oblivious of major negative side effects. Carefully understanding and designing entities' reward systems seems critical.
One important feature of reward systems is that they too need to rely on a data collection system and an epistemic system. To illustrate, the rewards to be given to a public health organization should arguably depend on the actual health of the population. However, if this population does not get tested, or if the mental health of the population is not properly inferred from the data, then the public health organization's rewards may be misleading. This defect of the computation of the rewards may then create flawed motivations for the entity, which can lead to poor decisions by the decision system, and to poor assessments by the epistemic system.
More generally, as argued by Hoang [2019], the careful understanding and design of entities' reward systems is arguably the most critical feature to understand these entities, and to make them more robustly beneficial for the future of our planet. Perhaps Newcomb-like paradoxes can shed more light into what can and cannot be achieved from the interaction between the reward system and the other systems of an entity.
One last component discussed in Hoang [2019] is the maintenance system. Given that any entity almost surely has imperfect data collection, reward, epistemic and decision systems, it seems critical that the entity is aware of this, and actively aims to combat the defects of these components.
One example of defect within humans, and arguably within organizations too, is the confirmation bias. A decision made by our decision systems can sometimes harm the capabilities of our epistemic systems, by irrationally favoring justifications of our decisions, even when they are poor (see the survey by Nickerson [1998] ).
Another example of defect is known as the law of Goodhart [1975] , which says that "when a measure becomes a target, it ceases to be a good measure". Recently, El-Mhamdi and Hoang [2020] even showed that a fat-tail discrepancy between a deployed imperfect reward system and its ideal version could make reward maximization infinitely bad, according to the ideal reward system.
It thus seems critical for any robustly beneficial entity evolving in complex environments with feedback loops to have a maintenance system that keeps track of the imperfections of their epistemic, decision, data collection and reward system, and that actively tries to fix and improve these systems if needed.
This paper proposed to more clearly distinguish an entity's epistemic system from its decision system. I argued that this allowed to better understand Newcomb-like problems. In particular, based on this insight, I proved the impossibility of counterfactual optimization. Moreover, I showed that Newcomb's problem can be reformulated in terms of the capability of some observer to better predict the decision of an entity than the epistemic system of the entity can. Finally, I discussed numerous further research challenges to better understand information processing entities, and to better design entities that make robustly beneficial decisions.