Naturalistic Logical Updates

Vadim pointed out in a comment to my post on logical counterfactuals that a very similar idea had been explained in a LessWrong post summarizing work by Vladimir Slepnev and Paul Christiano at a MIRI workshop in 2013. The algorithm which they suggested was called UDT 1.5. In fact, the essential idea is already argued by Vladimir Slepnev (cousin_it) in a post from 2012: Should logical probabilities be updateless too?.

Here, I continue to develop these ideas and those in my logical dutch-book post. I present an alternate prior to the one which was used for UDT 1.5. I show that this new prior has naturalistic logical updates, a kind of improvement-endorsing property which seems likely to work well with UDT. This property also gets around Paul Christiano’s paradox of ignorance.

Motivation

Slepnev motivates the problem with a variant of counterfactual mugging, inspired by a post by Wei Dai but simplified:

Suppose Omega (the near-omniscient near-omnipotent and almost perfectly trustworthy agent who prefers the pronouns ve/ver) appears before you. Omega tells you that ve has computed the millionth binary digit of $π$ , and that before knowing what the digit was, ve had committed to the following procedure: if the millionth digit is zero, ask you for $100. If the millionth digit is one, give you $10,000 only if you would have given Omega the $100 had the digit been zero; otherwise, give you nothing. Omega then tells you that the millionth digit was in fact zero, and asks you for $100.

Suppose you already use a variant of UDT, so you take the actions you would have approved of ahead of time. If you are a “smart” agent who already knew the millionth digit of $π$ and only calculated expected utility of universes consistent with this knowledge, you’d turn Omega down. If you’re a “dumb” agent who doesn’t, you’d give Omega the $100. (This is true even though UDT uses a kind of logical counterfactual; a UDT agent takes a counterfactual on its possible actions, not anything else, so it still doesn’t consider the worlds where digits of $π$ are different.)

This means that “dumb” agents don’t want to become “smart” agents. A UDT-like agent which improves its beliefs over time by proving more theorems will be temporally inconsistent. This calls into question approaches to logical uncertainty which rely on estimates which improve given more time, such as uniform coherence.

My intuition is that we want to bite the bullet and be updateless about logical uncertainty as well as empirical uncertainty, because this maximizes expected value from a logically uncertain perspective. This makes it seem like the only reflectively consistent possibility. Scott Garrabrant gave me a different argument for the same conclusion. My recollection of the argument is as follows:

Problems like this are a result of someone simulating you. You can’t be sure of whether you’re in the simulation, being fooled into thinking the millionth digit of $π$ is zero, or whether you’re in the real world. You can’t trust your own logic, since it could be spoofed. If you’re in the real world, you want to not give up the $100. If you’re in the simulation, then you’d like to give it up so that the real you gets $10,000. However, as in the absentminded driver problem, the sleeping beauty problem, and other such problems, you shouldn’t solve the problem by assigning probabilities to the two possibilities; instead, you want to act according to a policy you’d endorse ahead of time. Hence, an updateless solution.

(An interesting question: to what extent do the details of Omega’s counterfactual computation determine whether we buy the whole argument?)

Naturalistic Logical Updates

It seems we need a logically ignorant prior which is used to judge policies. This is a prior over impossible possible worlds, so it is bound to include some nonsense, but it can’t be as simple as assigning probability ¹⁄₂ to everything; there needs to be enough structure to get “reasonable” results. Slepnev and Christiano offered such a prior in the workshop results I mentioned, but I don’t see that it gets me the properties I want. I will construct one according to the properties I see as desirable, along the lines I started to develop in my logical dutch book post.

A logically updateless UDT should reduce to a logically updateful DT in circumstances which do not involve entanglements with impossible possible worlds. I won’t get that property here, but I will go for something suggestive: an approximation scheme for a logical prior which “endorses” improved approximations as being the appropriate update.

An AI which improves its logical consistency over time can be modeled by a sequence of approximate probability distributions $P_{1} (ϕ), P_{2} (ϕ), P_{3} (ϕ) . . .$ which are supposed to get better and better. For this post, the probability distribution will be over sentences of $P A$ . I make the assumption that the change between any $P_{n}$ and $P_{n + 1}$ in this sequence is due purely to information coming from a theorem-prover; at time $n + 1$ , we’ve proved more theorems, and taken them into account as logical constraints on beliefs. The type of constraints I will use will be partitions of truth: a set of sentences of which exactly one can be true. Coherence relative to a single constraint is defined by probabilities summing to one:

Relative Coherence: Where $σ$ is a finite set of sentences, $P (ϕ)$ is coherent relative to $σ$ if and only if $Σ_{ϕ \in σ} P (ϕ) = 1$ .

If a function is coherent relative to all provable partitions of truth, it is coherent in the standard sense. So, we can suppose that this is the only type of information which the theorem-prover gives us. (This is a version of coherence which I got from Scott.)

As I found when working on the logical Dutch book post, the behavior of conditional probabilities gets tricky when we only have relative coherence; we don’t necessarily have basic properties of conjunction, so we can have things like $P (ϕ | ϕ) \neq 1$ and probabilities which depend on the order in which we condition on evidence. This is a problem for getting nice properties out of such probability functions. To solve this, I will require propositional coherence: the distribution will be coherent relative to every constraint which is provable by propositional logic alone. (Although this introduces an infinite number of constraints, $P_{n} (ϕ)$ can still be computable, as I will show later.) This is probably overkill, but is convenient.

Let $┌ σ ┐$ be the sentence asserting that $σ$ is a partition of truth. (For example, if $σ = {ϕ}$ , then $┌ σ ┐ = ϕ$ ; on the other hand, if $σ = {ϕ, ψ, θ}$ , then $┌ σ ┐ = (ϕ \lor ψ \lor θ) \land \neg (ϕ \land ψ) \land \neg (ϕ \land θ) \land \neg (ψ \land θ)$ .) We define a naturalistic update as follows:

Naturalistic Logical Update: $P (ϕ)$ has a naturalistic logical update if and only if:

Where $σ$ is a partition of truth, $P (ϕ | □ ┌ σ ┐)$ is coherent relative to $σ$ .

This is the successor to my notion of “information-adding coherence” in the logical dutch book post. Note that this definition only requires coherence relative to real logical constraints. If $σ$ is not a genuine partition of truth, $P (ϕ | □_{n} ┌ σ ┐)$ may or may not be coherent relative to $σ$ . This is because coherence conditioning on arbitrary constraints would be impossible: we could condition on an unsatisfiable set of constraints.

We could then define $P_{n} (ϕ)$ by updating sequentially on theorems as we prove them. This won’t be quite what’s wanted, but it will give enough intuition for now. I’ll use $C_{n}$ to denote the set of constraints $P_{n} (ϕ)$ has updated on.

For an updateless decision theory which uses $P_{0} (ϕ)$ as a logically ignorant prior, this means the segment of expected utility of a policy coming from just those worlds in which constraints $C_{n}$ are provable should be exactly the expected utility under $P_{n} (ϕ)$ . If this possible world is sufficiently “isolated” from everything else (negligible probability of being simulated), then the preferred policy for this case should be very close to the policy for a logically updateful agent using $P_{n} (ϕ)$ . This suggests there’s some hope for a well-behaved UDT based on $P_{0} (ϕ)$ .

This is “naturalistic” in the sense that it doesn’t care where the proof comes from. The only difference between the internal theorem-prover and an external one is that the agent has perfect knowledge of it. If we instead update on observations which make it very probable that a external theorem-prover has proved something, the resulting distribution would be (almost) coherent with respect to those constraints. Note that this solves Paul Christiano’s paradox of ignorance: the counterintiutive effect was precisely that updating on information from an external theorem-prover was different from updating on an internal one. (Christiano 2014, section 6.1.5.)

This level of self-trust might appear concerning for Lobian reasons. We can apply the naturalistic update property to prove $P (ϕ | □ ϕ) = 1$ ; since $P (ϕ | □ ϕ) = P (ϕ \land □ ϕ) / P (□ ϕ)$ , we have $P (ϕ \land □ ϕ) = P (□ ϕ)$ ; then $P (□ ϕ \land \neg ϕ) = 0$ ; so we have $P (□ ϕ \to ϕ) = 1$ . However, recall that the naturalistic update property only applied to genuine partitions of truth; this line of argument only applies if $ϕ$ is a theorem in the first place. Furthermore, even if we construct a prior for which $P (□ ϕ \to ϕ) = 1$ for a much wider class of $ϕ$ than only theorems, this would still be a far cry from having $□ (□ ϕ \to ϕ)$ in the proof system itself.

It turns out such a distribution can be constructed by surprisingly simple means.

Theorem. There exists a computable probability distribution $P^{*} (ϕ)$ which is coherent with respect to propositional constraints, and which has a naturalistic logical update.

Proof. Sample a random infinite theory $T^{*}$ as follows. Let $μ (ϕ)$ be a positive probability distribution over sentences. Sampling from $μ (ϕ)$ repeatedly, accept those samples into $T^{*}$ which are consistent with everything accepted so far under the provability logic $G L S$ . (When I say a set of sentences is consistent under $G L S$ , I mean the following: Take the conjunction of all the sentences. Translate this sentence to modal logic, hiding all details which aren’t either propositional logic or the provability predicate. If the negation of the result is a theorem of $G L S$ , the set of sentences is said to be inconsistent; otherwise, it is consistent.)

Define $P^{*} (ψ)$ as the probability that $ψ$ will occur in such a $T^{*}$ . This is computable, as follows. Generate the tree of possible random theories, ending in a leaf whenever $ψ$ or $\neg ψ$ is sampled. The probability that one of the two will eventually be added to $T^{*}$ is 1, because $G L S$ extends propositional logic and so has the property that if both $α \land ψ$ and $α \land \neg ψ$ are inconsistent, $α$ is already inconsistent. Therefore, for any desired accuracy $ε > 0$ , we can extend the tree far enough to compute $P^{*} (ψ)$ to within $ε$ .

Suppose that $σ$ is a partition of truth which is provable by propositional means alone. Since $G L S$ extends propositional logic, any $T *$ sampled would contain at most one $ϕ \in σ$ to avoid inconsistency. Furthermore, since any $T^{*}$ eventually contains either $ϕ$ or $\neg ϕ$ for each $ϕ$ , it will also contain at least one: otherwise, it would contain the negation of all sentences in $σ$ , which would also be an inconsistency. Therefore, the probability of any propositional partition of truth sums to one, as required.

$P^{*} (ϕ)$ also has a naturalistic update. $G L S$ has $□ ϕ \to ϕ$ for all $ϕ$ . Therefore, $P^{*} (ϕ | □ ┌ σ ┐)$ is coherent relative to constraint $σ$ . $□$

It might seem strange that I’ve used $G L S$ rather than $G L$ . $G L S$ is the “truth provability logic”, which gives every true modal statement about provability in $P A$ , rather those provable in $P A$ . (Boolos, 1995.) $G L$ represents the knowledge about provability possessed by $P A$ , whereas $G L S$ represents knowledge beyond $P A$ . For example, $G L S$ proves $\neg □ ⊥$ . It might seem odd to impose this level of knowledge about provability on the probability distribution. However, coherence relative to $G L$ would be odd in other ways. $G L$ obeys “necessitation”: $ϕ \to □ ϕ$ . This means that anything true must be provable. This seems wrong for our logical prior: we’re sampling random sentences to create a probability distribution in part because we know not everything is provable or disprovable, but want to have beliefs about those things anyway. Consistency with respect to $G L$ would make us wrongly believe that $P (□ ϕ) + P (□ \neg ϕ) \geq 1$ . (Everything is provable or refutable or both.)

Of course, the main motivation here is that $G L$ wouldn’t get us a naturalistic logical update: we want to be consistent with constraint $σ$ by conditioning on the provability of $σ$ , $□ ┌ σ ┐$ . In $G L$ , $□ ψ$ is consistent with $\neg ψ$ , so conditioning on new provability facts coming from a theorem prover wouldn’t get us much at the object level. We would have to condition on $┌ σ ┐$ directly, making the role of the theorem prover non-naturalistic. This would (I suspect) be bad news if we then try to apply it to an updateless decision theory.

Updateless Decision Theory

Given that the motivation for naturalistic updates was an updateless one, it wouldn’t do to finish the post without at least sketching a UDT based on $P^{*}$ .

As in UDT 1.5, we have an agent $A ()$ search for a program with high expected value according to $P^{*} (ϕ)$ and according to a utility function $U ()$ . ( $U ()$ must be encoded in $P A$ , so I’ll make the assumption that it has natural-numbered values.) Define this as:

$a r g m a x_{p \in p r o g r a m s} Σ_{x} x \cdot P^{*} (U () = x | A () = p)$

The set of programs may be finite, for example when operating on a finite machine. In this case, the operation is computable (if infeasible).

Limitations

The above construction is not uniformly coherent. I haven’t even shown that it converges to something coherent as we update!

It’s not totally clear what happens as we update on constraints provable in $P A$ . One concern is that it sounds dangerous to mix $G L S$ with $P A$ -- one might get a system which obeys Lob’s theorem but also contains $□ ϕ \to ϕ$ . Things should be fine here, because we’re effectively just adding arithmetically true statements to $P A$ . Although this creates a stronger logic which endorses things like $\neg □ ⊥$ , the $□$ still refers to provability in $P A$ rather than provability in the new system.

One thing which I considered in the logical dutch book post which I didn’t manage to achieve here is updating on failed proof attempts. Trying to prove something for a long time without success should make us find it less likely. For this purpose, I introduce the notation $□_{n} ϕ$ , which says that there is a proof of $ϕ$ of length at most $n$ . We want updating on this to obey conservation of expected evidence:

Conservation of Expected Proof:

$P (ϕ) = P (ϕ | □_{n} ψ) P (□_{n} ψ) + P (ϕ | \neg □_{n} ψ) P (\neg □_{n} ψ)$

Note, however, that this already follows from propositional coherence alone. To make this meaningful, we also want:

Bounded Naturalistic Update

Where $σ$ is a partition of truth, $P (ϕ | □_{n} ┌ σ ┐)$ is coherent relative to $σ$ .

This could likely be achieved by enforcing $□_{n} ϕ \to □ ϕ$ for all $ϕ$ , in addition to everything already being enforced in $P^{*} (ϕ)$ . Showing that the result is still well-defined and computable requires more than just the decidability of $G L S$ , which is why I didn’t do this here.

We could then define $P_{n} (ϕ)$ by updating sequentially on all our proof attempts, successful or unsuccessful. (Differentiating proof attempts by a length-bound only is very course-grained, but we could make this finer-grained as desired.)

Works Cited:

Paul Christiano. 2014. Non-Omniscience, Probabilistic Inference, and Metamathematics. Technical report 2014–3. MIRI.

Boolos, George. The logic of provability. Cambridge university press, 1995.