Intelligent Agent Foundations Forumsign up / log in
Universal Inductors
post by Scott Garrabrant 522 days ago | Sam Eisenstat, Jack Gallagher, Benja Fallenstein, Jessica Taylor, Patrick LaVictoire and Tsvi Benson-Tilsen like this | discuss

Now that the Logical Induction paper is out, I am directing my attention towards decision theory. The approach I currently think will be most fruitful is attempting to make a logically updateless version of Wei Dai’s Updateless Decision Theory. Abram Demski has posted on here about this, but I think Logical Induction provides a new angle with which we can attack the problem. This post will present an alternate way of viewing Logical Induction which I think will be especially helpful for building a logical UDT. (The Logical Induction paper is a prerequisite for this post.)

This post will make several informal claims without proof. Many of the claims are analogous to things proven in the Logical Induction paper, and the math is not substantially difficult. I might extend the paper to have a section talking about the following concepts more formally.

A Universal Inductor is an infinite sequence \(\{\mathbb{P}_n\}\) of probability distributions on infinite bit strings. Satisfying the following two properties:

  1. The function \((n,\sigma)\mapsto \mathbb{P}_n(\sigma)\) is computable, where \(\sigma\) is a finite prefix, and \(\mathbb{P}_n(\sigma)\) is the probability that an infinite bit string begins with the prefix \(\sigma\).

  2. Consider the propositional theory whose \(n\)th atom is identified with the event “the \(n\)th bit in the infinite bit string is a 1.” Then the probability distribution \(\mathbb{P}_n\) induces an function from sentences in the language of this theory to probabilities. The sequence of probability assignments must form a Logical Inductor over the empty deductive process.

Note that a Universal Inductor corresponds to a Logical Inductor, but the associated Logical Inductor will not have finite support, and so will be different from the one constructed in the paper. Never the less, Universal Inductors can be shown to exist using a similar construction. Note that the second condition technically implies the first, but I separate them for emphasis.

Here are some facts about Universal Inductors:

  1. The probability distributions converge to a limiting distribution on infinite bit strings, \(\mathbb{P}_\infty\).

  2. This limiting distribution dominates the universal semi measure. In particular, every finite prefix is given nonzero probability.

  3. Given any consistent deductive process, we can construct a logical inductor over that deductive process simply by associating atoms of the theory with bits in the bit string (in an efficient computable manner), conditioning \(\mathbb{P}_n\) on the event corresponding to the \(n\)th list in the deductive process, and taking the function from logical sentences to probabilities induced by that probability distribution. (Thus, a Universal inductor can be used to construct a Logical Inductor over PA by looking at some of the conditional probabilities, and can be used to construct a Logical Inductor over ZFC by looking at other conditional probabilities (Hence the name Universal Inductor))

The 2 major differences between the Universal Inductor and Logical Inductor formalisms are:

  1. Universal Inductors are probability distributions at every finite stage, not just in the limit, so we can more naturally talk about conditional probabilities at every stage.

  2. Universal Inductors are only over empty deductive processes, and we simulate nontrivial deductive processes only through conditioning.

I feel that this will especially make for a better framework for thinking about logical updatelessness.

Here is an open question about Universal Inductors:

If \(\mathbb{P}_\infty\) and \(\mathbb{P}^\prime_\infty\) are the limits of two different universal inductors, do they necessarily dominate each other? i.e. does there exist a constant \(\varepsilon>0\) such that \(\mathbb{P}^\prime_\infty(\sigma)>\varepsilon\mathbb{P}_\infty(\sigma)\) for all prefixes \(\sigma\)?

(This is equivalent to the analogous question about logical inductors over the same theory, but it feels more natural to state in this framework.)





[Delegative Reinforcement
by Vadim Kosoy on Stable Pointers to Value II: Environmental Goals | 1 like

Intermediate update: The
by Alex Appel on Further Progress on a Bayesian Version of Logical ... | 0 likes

Since Briggs [1] shows that
by 258 on In memoryless Cartesian environments, every UDT po... | 2 likes

This doesn't quite work. The
by Nisan Stiennon on Logical counterfactuals and differential privacy | 0 likes

I at first didn't understand
by Sam Eisenstat on An Untrollable Mathematician | 1 like

This is somewhat related to
by Vadim Kosoy on The set of Logical Inductors is not Convex | 0 likes

This uses logical inductors
by Abram Demski on The set of Logical Inductors is not Convex | 0 likes

Nice writeup. Is one-boxing
by Tom Everitt on Smoking Lesion Steelman II | 0 likes

Hi Alex! The definition of
by Vadim Kosoy on Delegative Inverse Reinforcement Learning | 0 likes

A summary that might be
by Alex Appel on Delegative Inverse Reinforcement Learning | 1 like

I don't believe that
by Alex Appel on Delegative Inverse Reinforcement Learning | 0 likes

This is exactly the sort of
by Stuart Armstrong on Being legible to other agents by committing to usi... | 0 likes

When considering an embedder
by Jack Gallagher on Where does ADT Go Wrong? | 0 likes

The differences between this
by Abram Demski on Policy Selection Solves Most Problems | 1 like

Looking "at the very
by Abram Demski on Policy Selection Solves Most Problems | 0 likes


Privacy & Terms