Written as part of the MATS 9.1 extension program, mentored by Richard Ngo. Additional thanks to Maria Kostylew, Lorxus, and others for helpful feedback on this post.

Introduction

In this sequence, I will outline two prospective agendas that build on Logical Induction (LI) to contribute to a descriptive theory of embedded agency.

In part 0, I introduce LI and cover some progress the framework has made towards clarifying key properties of intelligence. This piece then concludes with a brief case for both the research directions. I am optimistic that these lines of inquiry could shed light on some fundamental concepts such as actions, inductive biases, and preferences.

1: Why Logical Induction?

1.0: A short introduction

Logical Induction is a 2016 paper that provides a theoretical proof-of-concept for logically uncertain bounded reasoning. Its key motivation is that bounded reasoners cannot fully propagate the consequences of their beliefs. They contrast (for example) Bayesian Networks (BNs), a standard mathematical framework for belief management. The idea of BNs is for dependencies between probability distributions to be represented by a Directed Acyclic Graph (DAG); updates to a set of distributions spread throughout the graph via a formal Bayesian update rule.

Bayesianism has some philosophical issues relating to unknown unknowns that we'll get to later, but their prosaic obstacle is that fully propagating updates (known as inference) is NP-hard. Therefore, understanding bounded cognition partially comes down to explaining how epistemic systems can perform computationally limited, incomplete belief updates while still achieving (weakened) rationality conditions. Logical Induction addresses these issues in a setting where a reasoner cannot always figure out the implications of their beliefs as described in mathematical logic.

The setup is a sequence of reasoners that, at each index n^[1], assigns credences between 0 and 1 to logical statements. The function mapping statements to credences is called a belief state. These belief states are simultaneously interpreted as markets that set prices in these statements. Traders are sequences of programs that, at each index n, issue buy and sell orders in logical statements according to the prices set by the market.

The arbiter of truth is a nested sequence of finite sets of sentences, called the deductive process, that represents statements that are revealed, observed, or proved^[2] to be true up to a fixed time-step. An issued share in a sentence cashes out at $1 at the end of time if the sentence is plausibly^[3] consistent with the deductive process. Traders are rewarded in the system's internal currency for behaviours such as:

buying shares in true statements before they are shown (or determined by consensus) to be true
selling shares in false statements before they are shown to be false
anticipating market price shifts to buy or sell shares in sentences pre-emptively.

A trader is said to exploit a sequence of belief states if its plausible wealth at the end of time is bounded from below, but not from above. Such traders are intuited as conducting arbitrage on the market prices, making risk-free unlimited profits. The rationality criterion for a sequence of reasoners (or, equivalently, for their belief states) is that no trader exploits it. This is a weakened anti-Dutch book or coherence condition. Indeed, the authors go on to prove that "inductors" that satisfy this criterion have various qualities (in the limit of infinite time-steps) one would expect of a consistent, accurate reasoner. For example, inductors learn to have stable beliefs. They also learn to assign provable statements^[4] a probability of 1, and are well-calibrated in their beliefs. I'll now zoom in on two aspects of Logical Inductors that are foundational for the directions covered in the sequence: introspection and inductive biases.

1.1: Introspection and game theory

One of the more remarkable properties of inductors is the ability to introspect. Classical reasoning systems struggle to coherently evaluate statements about themselves. These difficulties stem from paradoxes of self-reference where the truth of a statement depends on the reasoner's belief about that statement. A simple example is 'this statement is false'. You can imagine a reasoner that assigns boolean truth values to statements oscillating infinitely between concluding that is true, which makes false, which makes true, which makes...

Inductors solve this paradox by remaining uncertain about such statements. Specifically, they'll learn to assign a probability of . More generally, inductors are defined by a sequence of belief states, which are computable functions from sentences to values between 0 and 1. These functions can themselves be described in the same logical language, and so an inductor also assigns probabilities to statements such as . Not only are these probabilities well-defined, they are well-behaved in various ways. Notably, LIs learn to be sure about their own beliefs, up to an error that vanishes in the limit. They also learn to correctly anticipate what their beliefs will be in the future, and even to trust those future beliefs^[5].

Introspection, self-modelling, or metacognition^[6], is an unreasonably fruitful concept for thinking about intelligence. The 'outside view' justifying this is that metacognition sure seems to be a robust attractor state for intelligence. However, the concrete explanation I find most compelling comes from game theory:

Suppose you are an external, disembodied being that observes an AI acting on (parts of) the world. Then, modelling the AI's cognition as implementing something like a Markov Decision Process (MDP), or a control system works quite well. These paradigms don't carve out any space for the AI's cognition to explicitly distinguish itself from its environment, but this may never become an issue. Even elements like physical parts of a robot can be thought of as just 'part of the environment'.

Suppose instead that you are an embedded being that is interacting with that AI. Not only are you modelling the AI, it is modelling you back – and therefore it is modelling how you are modelling it, and therefore it is modelling how you are modelling how it is modelling how...

Game theory is about strategic encounters between multiple agents. Much of the field's insight comes from how it grapples with the ensuing infinite recursions. The importance of these 'belief hierarchies' to agents' behaviour motivates why self-models are so useful: there is immense selective pressure for stable self-models to develop in agents that have to interact with other agents. This makes introspection a desirable component of a theory of intelligence – one that gives an account (called a solution concept in the literature) of why agents would behave a particular way in a game-theoretic situation.

Another win you get from introspection is a notion of actions and goals as special types of beliefs of the agent, which I already outlined in a previous post. One rather inelegant feature of game theory is that both actions and goals (as determined by payoffs) are imposed as definitions. This doesn't address why beings in a deterministic or random world would cook up the concept of 'actions' or 'choice' in the first place. The ultimate success of the first research programme I'll describe would involve a new game theory where actions and payoffs are emergent properties of the agents' beliefs, as are solution concepts.

1.2: The LIA: hypotheses, inductive biases, and preferences

In the paper, the authors show that given a deductive process, which again stands in for an arbiter of ground truth (or at least of ground observations), there exists a computable sequence of belief states that satisfies the LI criterion (with respect to that process). The proof is constructive, giving a concrete algorithm that would – afforded enough computation – implement this sequence.

The "Logical Induction Algorithm" (LIA) itself hints at some fundamental insights. The idea of the LIA is to set up a subroutine, TradingFirm, that simulates an aggregation of a finite number of (efficiently computable) traders' strategies at each time-step. According to TradingFirm's simulation, the subroutine MarketMarker sets prices for the time-step so that simulated traders' plausible risk-free profits grow only as a function of a sequence with finite sum. More traders are covered by TradingFirm at each time-step, such that in the limit every single trader's^[7] activity is priced into the market.

The LIA gives some compelling theoretical suggestions for how we should think about intelligence as managing hypotheses or beliefs. Conventional Bayesian reasoning involves enumerating a set of hypotheses and then iteratively updating priors to revise credences in these hypotheses. As I alluded to earlier, this method doesn't deal well with unknown unknowns, or Knightian uncertainty. For example, no amount of Bayesian updating will converge to the correct hypothesis if that hypothesis was assigned probability 0 to start with. The LIA has a similar notion of privileged starting hypotheses (i.e. traders), namely those that are enumerated early by TradingFirm. However, it is flexible enough to eventually entertain hypotheses that weren't originally considered. This makes the algorithm a first attempt to describe reasoning under Knightian uncertainty. In addition, the set of traders has a nice algebraic structure that allows you to compose or aggregate them^[8].

LIAs are also an interesting toy model of inductive biases. Consider a reasoning system that implements a logically uncertain or computationally limited belief management system – such as a bounded version of a Bayesian network. I'll tentatively define inductive biases as a set of arbitrary rules about which beliefs get propagated or explored before others^[9]. Even though LIAs cover all traders in the limit, traders that are listed early in the process have an outsized impact on the prices set by MarketMaker. On the other hand, the algorithm works for an arbitrary enumeration of traders. One interpretation is that there are (countably infinitely many) degrees of freedom in the choice of inductive bias, and all of them still give a rational belief system. I find this promising because once we fix a level of intelligence with something like the LI criterion, there should be many different ways to achieve that level of intelligence. This feature works well with a descriptive agenda for agent foundations.

Moreover, inductive biases can be seen as giving agents their character, personality, or preferences. I also advocated this in the context of LLM (self)-prediction: a pure predictor, such as a pre-trained LLM, is a generic simulator from which we can't extract a concept of preferences. However, such predictors tend to become more agent-like when they are modified (for example via post-training) into biased predictors that are willing to simulate some things, but not others. The biases in the LIA could help describe the ways that intelligent beings can have an identity, or a robust set of preferences, without sacrificing too much of their predictive intelligence. The second path I will propose involves developing this idea.

1.3: Some caveats

For all of their lovely features and promises of philosophical insight, both logical inductors in general and the LIA specifically have a catch to them, both of which stem from the fact that they are total overkill.

The Logical Induction Criterion (LIC) dictates that the inductor not be exploitable by any trader; this forces any inductor to somehow cover every trader 'just in case', which leads to them having some ridiculously powerful properties. An example of this is the 'provability induction' theorem^[10]:

Let be a logical inductor and be an efficiently computable^[11] sequence of provable sentences. Then

The authors interpret this theorem as saying that the inductor must (in the limit) learn any pattern about as quickly as its sentences can be proven or verified by the deductive process^[12]. Such a result makes some sense for certain patterns. Consider the sequence of sentences "the n-th digit of 1/3 written in decimal is 3". We expect an intelligent being would eventually learn this statement is true for all n. More importantly, it should hopefully learn this fact through an abstract argument or from generalisation (such as having a base case and an induction argument). Even though this is technically an infinite sequence, there is a closed-form pattern that lets you express that sequence efficiently.

However, consider instead the sequence 'the n-th digit of in binary is 1'. The digits of are, as far as we can tell, pseudorandom. There is no known heuristic that lets you infer or even improve your guess of the hundredth digit of given the previous ninety-nine. This means that this sequence doesn't encode a compressible pattern, and indeed I would expect an intelligent probabilistic reasoner to learn this meta-pattern and assign a probability of 1/2 (until it gets around to computing that digit, anyway). Instead, Inductors are forced to learn the non-meta 'pattern' and assign the n-th digit of its correct value by time-step n (in the limit).

This is an absurdly high standard to hold a bounded intelligence to, but it follows inevitably from the rationality condition. On any given day, hypotheses can trade on (arbitrarily large) finite combinations of sentences. So, for any computable sequence, there exists a trader that could conduct arbitrage on the inductor's beliefs about that sequence alone. The issue with the LIA is directly related to this, and I've actually already mentioned it before:

The LIA computes every, single, trader in the limit. To be more precise, it computes every single trader a countably infinite number of times^[13]. Consequently, the LIA is hopelessly slow and cannot be implemented in practice, despite being computable in the technical sense^[14]. It's true that many incomputable objects are still numerically or practically useful; this is often because because they can be approximated with discrete algorithms with theoretical guarantees on the fidelity of the approximation. This is, for example, why regular (continuous, differentiable, smooth, etc...) functions are so useful despite being 'fake' in a physical sense. At least with our current state of knowledge, however, inductors resist these kinds of 'nice' approximations. After all, 'try everything' isn't a strategy that's easy to simulate with heuristics for finite computations.

To summarise: the core issue of logical induction is that the rationality criterion is extremely strong, and therefore that any prospective algorithm that satisfies it will be both functionally incomputable and hard to approximate. Two questions I'll return to occasionally in this sequence are: "to what extent does this limitation dampen my excitement for research that builds on logical induction? how do we relate to these limitations?"

2: Two paths

The first research direction I'll elaborate on here leverages introspection in Logical Induction to explore notions of actions, goals, and games. The second one uses the inductive biases natural to the framework to investigate the emergence of coherent preferences and identity. Both will get their own dedicated follow-up post.

2.1: A theory of actions and coordination

I mentioned earlier that a theory of actions emerges from a theory of introspection. Consider a metacognising predictor whose beliefs are connected via some actuator to the external world. If it is accurate or can learn, the predictor will figure out that its beliefs affect its subsequent observations; in other words, it should learn the pattern of which beliefs its actuator 'listens to' and instantiates in the world. This means that all the 'action-shaped' beliefs have the property that they happen when the predictor believes that they will. This inspires an informal definition:

Actions are sentences such that is high^[15].

Note that this doesn't make any claims about whether the agent is itself a free-energy-minimising-style agent. An inductor whose actions maximise a utility function would also learn such patterns.

If you are willing to see goals as 'an abstract concept well-suited to predict actions', a compelling definition also falls out of this theory. Goals are statements that are likely according to the predictor's model, and are dependent on the predictor's 'action' beliefs. In other words:

Goals are statements such that is high and is high.

The intuition behind this is that whenever there exists a 'goal' statement, an external observer can guess that the predictor will 'believe' action into existence (because that would be consistent with its accurate epistemic system).

There are at least two promising avenues for developing these ideas. Firstly, I have previously discussed how it's easy to find examples of 'actions' according to this definition that intuitively aren't actions, but also how this can be dealt with by Markov blankets. Circling back, the DAG structure on Bayesian Networks (BNs) is arguably reverse-engineered to express the concept of Markov Blankets^[16]; so we're back to asking what a good version of a BN would be. Fortunately, this question is partly what Richard Ngo's framework of belief webs is about, and some other people are tackling similar topics. Indeed, I am optimistic that combining belief webs with the introspective properties of Logical induction would get us close to a proof-of-concept for bounded, intelligent agency.

A second direction stems from the question: 'why do intelligent agents think of themselves as choosing their actions?' If one would implement a system like the one I describe above, then actions wouldn't be a set that an agent chooses from, but rather a label we put on part of a deterministic process. This is reasonable from an outside observer's perspective: 'agency' is a term we often give to things that seem intelligent, self-directed and hard to predict. Indeed, theories of agency tend to objectify agents by describing them as predictable and program-like. For example, game theory starts by giving players 'choices', but then attempts to find solution concepts that dictate what the choices must be.

Perhaps our concept of choice simply comes from us being uncertain about how our own belief webs will propagate information. In that case, 'deciding' how to act would in general be indistinguishable from inference. However, in the setting of logical induction, this gives us a rather unpleasant bullet to bite. Since inductors' beliefs stabilise in the limit of time-steps, the uncertainty over how beliefs propagate tapers off. So they lose their agency as they reach their limiting rationality.

Richard Ngo recently suggested that principled notion of choice could instead come from a related framework: probabilistic logic. This precursor to logical induction focused on proving existence of introspective probabilistic reasoners that have desiderate such as addressing paradoxes of self-reference and verifying reflective consistency^[17]. These reasoners have a couple of features that could be seen as representations of choice:

Such reasoners are infinitesimally uncertain about its own beliefs.
The proof of existence has a multiplicity of choices in its fixed point theorem.

Circling back, I complained earlier that 'actions' are contrived in game theory. So I am excited about whether this large space of (infinitesimally certain) fixed points could be the backbone of a theory of choice, and consequently of a new decision theory.

2.2: A theory of inductive biases

Scott Garrabrant has previously written about how the order in which traders are listed in the LIA can make an agent using an inductor fail the five-and-ten problem. He frames this as an issue for logical inductor decision theory. However, I think it means that inductors have built-in, latent notions of preferences that don't require an explicit utility function. Scott's example can thus be reinterpreted as saying that the agent has a strong preference for choosing five^[18], and therefore that the utility function that values the ten over the five simply doesn't fit its behaviour. If you actually wanted to construct an inductor that doesn't 'fail' the problem, all you'd have to do is change the traders' order.

I'll tentatively define inductive biases as rules an epistemic system follows about which hypotheses should be eliminated during reasoning. In a belief web, you can think of them as rules about which beliefs propagate, and how. Whereas goals (as defined in the previous sections) are an abstraction that help us predict actions, inductive biases are systematic patterns in how the agent's goals vary over time. An inductor with a strong-enough bias will not only select the five over the ten now, it will keep doing so consistently, forever. Building on Scott's example, I would be excited for research that explores the link between the order of traders and interpretations of which preference functions (e.g. utility) 'fit' an inductor's predictions.

Inductive biases can also be motivated as a computational heuristic: they are choices about what not to think about (or at least about what to not prioritise in your thinking). However, here comes one way in which the LIA's computational overkill is a bit unsatisfying. Sure, some traders are given negligible amounts of wealth as they are enumerated very late. We would like to think of this as de-prioritising the trader. However, the inductor still has to compute the trader, as not doing so could mean getting exploited: a trader whose unbounded gains grow at a small speed scaled down by still has unbounded gains.

So, even though inductors can highlight a profound connection between preferences (and therefore agency), inductive biases, and bounded computation, they don't seem very useful for exploring that connection. This is where I would love ideas for how to sensibly approximate inductors. An example idea for this includes weakening the LI criterion to inexploitability by traders that are simple according to some measure of complexity (e.g. K-complexity), then ordering traders by complexity in the LIA. Ideally, this would address the 'inductors learn arbitrary patterns' problem that I mentioned earlier. The ensuing objects could allow for research on how inductors learn 'real' patterns (e.g. those that can be expressed in closed form).

I haven't yet thought of an approach that feels particularly principled, but this link between biases, preferences, and computation seems promising enough to justify some exploration.

Conclusion

This piece introduces a sequence on two research directions that aim to build on Logical induction. In it, I first motivate the usefulness of the framework for clarifying foundational aspects of cognition and agency. The post then gives a short overview of the two prospective paths, which will be further elaborated in future posts.

^{^}
You can interpret the index of the sequence as time steps or 'logical time-steps' that pass after the inductor has completed a unit of reasoning.
^{^}
depending on your interpretation
^{^}
This is technically slightly inaccurate and is meant to convey the spirit of the thing while skipping some fiddly details. The work 'plausibly' is doing here relates to there being multiple consistent boolean valuations of the statements in a first-order logic.
^{^}
Technically these properties only apply to 'efficiently computable' statements, which has a specific technical meaning. Inductors actually learn to assign probabilities strictly between 0 and 1 to statements that are not efficiently computable.
^{^}
The mathematised versions of these claims are found in sections 4.8, 4.11, and 4.12 of the paper.
^{^}
I will use these terms roughly interchangeably.
^{^}
Technical detail: traders are programs and so there are no more than a countable number of them. This allows the inductor to simulate all of them in the limit.
^{^}
These nice algebraic properties are exactly what make the construction of TradingFirm viable, as it is itself a trader built from aggregating (a huge number of) traders. The structure of the space of traders seems semantically richer than algebras on probability spaces are, so that's another (related) win that LI gets over Bayesianism.
It's worth noting that TradingFirm doesn't contain itself because it is merely computable, not efficiently computable.
^{^}
The 'arbitrary-ness' of inductive biases is what makes them biases.
^{^}
Theorem 4.2.1 in the paper.
^{^}
This technical term is required because the traders (programs) that issue buy and sell orders are also efficiently computable. In general, inductors have nothing to say about sequences that aren't efficiently computable.
^{^}
The description 'about as quickly as its sentences can be proven...' is not sufficiently justified here. The paper has a running example of Logical Induction applied to Peano arithmetic that better explains the intuition behind this.
^{^}
The axiom of choice is doing some heavy lifting here...
^{^}
Never ask a man his age, a woman her salary, or a Logical Inductor its runtime. It won't answer during your life anyway...
^{^}
You could then define agents as logical inductors whose epistemics include these action-like beliefs.
^{^}
Ironically, Bayesian networks do not circle back.
^{^}
As opposed to Logical Induction, which focuses on how such a reasoner could be learned or approximated.
^{^}
A reviewer brought up that this conception of preferences risks only considering 'revealed' preferences.
Here's one way to address that concern: if you see preferences as an abstract concept for predicting actions, then revealed preferences are indeed the only preferences. If the revealed preference causes internal prediction error in the inductor, that means there is a wealthy trader putting upwards pressure on the probability of taking the ten instead. This inductive bias represented by the trader would have a real chance of 'winning out' eventually and having the 'ten' be chosen instead.