Intelligent Agent Foundations Forumsign up / log in
Universal Inductors
post by Scott Garrabrant 621 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.)





Note: I currently think that
by Jessica Taylor on Predicting HCH using expert advice | 0 likes

Counterfactual mugging
by Jessica Taylor on Doubts about Updatelessness | 0 likes

What do you mean by "in full
by David Krueger on Doubts about Updatelessness | 0 likes

It seems relatively plausible
by Paul Christiano on Maximally efficient agents will probably have an a... | 1 like

I think that in that case,
by Alex Appel on Smoking Lesion Steelman | 1 like

Two minor comments. First,
by Sam Eisenstat on No Constant Distribution Can be a Logical Inductor | 1 like

A: While that is a really
by Alex Appel on Musings on Exploration | 0 likes

> The true reason to do
by Jessica Taylor on Musings on Exploration | 0 likes

A few comments. Traps are
by Vadim Kosoy on Musings on Exploration | 1 like

I'm not convinced exploration
by Abram Demski on Musings on Exploration | 0 likes

Update: This isn't really an
by Alex Appel on A Difficulty With Density-Zero Exploration | 0 likes

If you drop the
by Alex Appel on Distributed Cooperation | 1 like

Cool! I'm happy to see this
by Abram Demski on Distributed Cooperation | 0 likes

Caveat: The version of EDT
by 258 on In memoryless Cartesian environments, every UDT po... | 2 likes

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


Privacy & Terms