Agency under bounded compute and information

2.1 Resource-rational analysis

Lieder and Griffiths (2020) frames human cognition as the optimal use of finite computational resources. The procedure: define the agent’s task, the cognitive operations available, and their costs; derive the heuristic that maximises expected utility under the budget. The heuristic that comes out is the prediction; observed cognitive biases are the right answer to the constrained problem.

The phrase pops up in many papers (Bhui, Lai, and Gershman 2021; Collins et al. 2024; Hahn et al. 2022; Ho et al. 2022; Levine et al. 2024).

LLM summary follows:

The optimization has the same shape as the bounded-rationality entries above but at a different grain:

\[ \pi^* = \arg\max_{\pi \,\in\, \text{strategies}} \mathbb{E}\bigl[\,U(\pi) - \mathrm{cost}(\pi)\,\bigr], \]

where \(\pi\) is a cognitive strategy — an algorithm parameterized by how much compute it spends — and \(\mathrm{cost}(\pi)\) is a cost on cognitive operations (search expansions, posterior samples, working-memory loads). This lies between BO and RM in granularity: BO optimises whole programs offline, RM optimises individual computations online, and RRA optimises the heuristic itself — a strategy with a configurable compute budget — treating it as a unit.

RRA’s distinctive play is reading observed biases as \(\pi^*\) under some plausible cognitive cost model. Anchoring-style adjustment and availability-based estimation have been derived in this framework as resource-rational under specific costs on sample count and inference depth. The inferential arrow runs in the unusual direction: from observed heuristic, infer the brain’s implicit cost structure.

What it gives us: machinery for “best affordable model”. If the world is bigger than the agent, this is the framework that tells us which compression to keep.

2.2 Bounded optimality

Russell & Subramanian (S. J. Russell and Subramanian 1995) define a program as bounded-optimal for a given architecture if no other program for that architecture does better in the environment. The optimization moves from “best action” to “best algorithm-on-the-hardware”. Resource-rational analysis is its descendant in the cognitive-science direction; Gershman, Horvitz & Tenenbaum’s computational rationality (Gershman, Horvitz, and Tenenbaum 2015) is the umbrella name.

LLM summary follows:

Fix an architecture \(M\) — a machine model with bounded memory and per-step compute, plus a clock. Bounded optimality is the program \(\pi^*\) that maximises expected utility subject to running on \(M\):

\[ \pi^* = \arg\max_{\pi \,\in\, \mathrm{programs}(M)} \mathbb{E}\bigl[U \mid \pi,\,\text{environment}\bigr]. \]

So the agent is no longer choosing actions; it is choosing the algorithm that will, in turn, choose actions on its hardware (like resource-constained Functional Decision Theory?). This is a meta-level optimization over policies-as-programs, with the architecture’s resource constraints baked into the feasible set rather than tacked on as a soft penalty — which is what distinguishes BO from the KL-regularized, free-energy framing above.

Russell & Subramanian also propose asymptotic bounded optimality (ABO), a weakening that requires the program to approach optimality only as the architecture is scaled up, because strict per-architecture optimality is itself intractable to analyse. cf large sample theory — infinite asymptotics are more tractable to analyse. ABO is a softer cousin of AIXI’s compute-to-infinity move — when “best on \(M\)” is too hard to characterise, the analysis retreats to “best as \(M\) grows”. Sticking to bounded compute seems to be really hard, based on what smart people do when they try to stick to it.

What it gives us: an insistence that the budget is a property of the implementation.

Future me, if I am tempted to talk about “the agent’s budget” without specifying the architecture, see above.

2.3 Rational metareasoning

S. Russell and Wefald (1991) model each unit of computation as a decision: expected value of running the computation minus its cost.¹ The agent decides which inferences to run as a planning problem one level up.

LLM summary follows:

Two questions distinguish RM from the BO entry above (also a Russell programme): what is being optimized and when. BO optimises programs, offline — a designer picks the best program for a fixed architecture, once, and the program then just runs. RM optimises computation choices, online — at runtime the agent itself decides, step by step, which inference to run next. The two framings are complementary rather than competing: RM is the technique a bounded-optimal program might use internally to allocate its compute, and BO is the criterion under which the program-plus-RM-policy bundle as a whole should be assessed.

The decision-theoretic content is the value of computation (VOC). Let \(b\) be the agent’s current belief state and \(c\) a candidate computation — expanding a node in a search tree, sampling another rollout, refining a posterior. Then

\[ \mathrm{VOC}(c \mid b) = \mathbb{E}\bigl[\,U \,\big|\, \text{act after } c,\, b\,\bigr] - \mathbb{E}\bigl[\,U \,\big|\, \text{act now},\, b\,\bigr] - \mathrm{cost}(c). \]

Run \(c\) if its VOC is positive; act otherwise. The Hay-Russell-Tolpin-Shimony meta-MDP turns this into a proper Markov decision process whose states are beliefs over the underlying MDP and whose actions include both external actions and computation actions, with optimal policies given by Bellman equations on the meta level.

Notice the regress: estimating \(\mathrm{VOC}(c)\) before running \(c\) is itself a computation, and deciding whether that is worth running is another. Practical RM truncates the recursion — usually at one level (myopic VOC, “is this single next step worth it?”), occasionally deeper. The truncation is what lets the framework run; whether the truncated VOC is itself bounded-optimal in any tight sense is the question that makes RM and BO need each other.

What it gives us: a decision-theoretically explicit story about when to compute, which is the question posed by the good-regulator-meets-big-world tension. The agent cannot run the full simulation; the metareasoner picks the slice.

2.4 Information-theoretic bounded rationality

Ortega & Braun (Pedro Alejandro Ortega and Braun 2011; Pedro A. Ortega and Braun 2013) formalise a bounded-rational policy as the KL-divergence-constrained optimum of expected utility.

LLM summary follows:

Pick a reference or prior policy \(\pi_0\) — what the agent does cheaply, without deliberating — and constrain the deliberated policy \(\pi\) to stay close to it in KL. So the budget is on the KL divergence, not on FLOPs, and the optimization is

\[ \pi^* = \arg\max_\pi \;\mathbb{E}_\pi[U(a)] \quad\text{s.t.}\quad \mathrm{KL}(\pi \,\|\, \pi_0) \le B, \]

equivalently, with \(\beta\) the Lagrange multiplier on the constraint,

\[ \pi^* = \arg\max_\pi \;\mathbb{E}_\pi[U(a)] - \tfrac{1}{\beta}\,\mathrm{KL}(\pi \,\|\, \pi_0). \]

The thermodynamic flavour comes from reading \(\mathrm{KL}(\pi \,\|\, \pi_0)\) as the work done against the prior: every nat of divergence from \(\pi_0\) has to be extracted from somewhere, by the same Landauer-style accounting that prices erasure. That is the argument that this functional counts as a model of compute cost and not just a regularizer.

The functional that drops out is a free energy, \(F[\pi] = \mathbb{E}_\pi[U] - \tfrac{1}{\beta}\,\mathrm{KL}(\pi \,\|\, \pi_0)\), whose maximizer is the Boltzmann-tilted policy \(\pi^*(a) \propto \pi_0(a)\,\exp(\beta\,U(a))\). The convenient consequence is that we can sample from \(\pi^*\) by importance-weighting draws from \(\pi_0\) against \(\exp(\beta U)\) — no need to enumerate actions to find the argmax, because the optimum is an integral over \(\pi_0\) that a Monte Carlo planner approximates without bias.

What it gives us: a formal stand-in for “compute budget” inside decision theory. It is also the bridge to thermodynamics, since the same functional reappears in the substrate principle section. Hafner et al. (Hafner et al. 2022) cast action and perception as joint divergence minimization in this lineage.

2.5 Bounded inductive rationality

Oesterheld, Demski & Conitzer (Oesterheld, Demski, and Conitzer 2023) drop logical omniscience.

LLM summary follows:

Logical omniscience is the standard Bayesian assumption that an agent assigns probability 1 to every theorem and probability 0 to every contradiction the moment those are stated. Classical decision theory needs that assumption to make the consequences of beliefs cash out: if a finite reasoner believes Peano arithmetic and PA proves \(\varphi\), then classically the reasoner already believes \(\varphi\). In any practical sense it does not, because nobody has run the proof. Until the agent spends compute to derive \(\varphi\), the sentence’s truth-value is just a probability strictly between 0 and 1 — and the agent needs a coherent way to reason with that probability while the proof is still in flight.

The machinery is the logical-induction stuff: a market of traders who bet on whether sentences will be proved, refuted, or remain undecided by a given deductive horizon, with the agent’s beliefs as the market prices. Coherence is not a constraint at any single moment but a no-arbitrage criterion over time — no efficiently-computable trader should be able to extract unbounded money from the agent’s prices as the deductive horizon expands. The agent ends up with calibrated logical beliefs in the limit without ever having been classically coherent on any particular day. ODC’s contribution over the precursor logical-induction work is a clean axiomatization: the trader-market construction was the existence proof; ODC characterise the property class.

A consequence we will need later: the agent never has to commit to what it will prove. It has prices on its own future actions and inferences, which is the move that dissolves the Löbian / 5-and-10 / spurious-counterfactual traps in embedded agency. A coherent agent that is required to know now what it will do later runs into diagonal arguments; an inductively-rational agent answers “I will give you a probability, and update it as the proof comes in”.

This gives us a story close to the embedded agency problem, but still with bounded compute. This might be the most direct response to the Löbian-paradox stuff without leaving for AIXI’s infinity.

2.6 Computationally tractable choice

Camara (Camara 2021) adds an axiom of computational tractability to decision theory: rule out behaviours that are fundamentally hard.

LLM summary follows:

Camara messes with axioms. Take whatever set of decision-theory axioms you like — rationalizability, transitivity, independence — and add one more, that the agent’s choice function admits a polynomial-time implementation. Choice rules that fail this axiom are not admissible models of choosing agents.

So what does CTC rule out? Not agents — the framework takes for granted that agents exist and make choices. What it rules out are theories of choice. Camara identifies particular preference structures whose induced choice rules cannot be computed in polynomial time, and concludes that those structures cannot describe how any tractable computer chooses. If observed behaviour can only be rationalized by a super-polynomial decision rule, the verdict is that the rationalization is the wrong account — the right move is to find a tractable rule that also fits the data, not to credit the agent with running an intractable algorithm in its head.

So whereas bounded optimality picks the best program for a given architecture; CTC rules decision theories out for any architecture at all. We could do both— BO tells us how to optimize inside the admissible class of theories; CTC tells us what the admissible class is.

What it gives us: a decision-theoretic analogue of bounded optimality, more axiomatic in flavour, easier to plug into economics-of-cognition arguments.

2.7 POMDP-as-agent

Biehl and Virgo (2023) interpret a system as a POMDP solver: the internal state of the system maps to a belief state about the outside world, and the system’s actions are optimal given that belief.

LLM summary follows:

A system \(S\) is interpretable as a POMDP solver if its internal states map to belief states and its outputs map to policy actions under some POMDP — i.e. its dynamics factor as Bayesian belief-update composed with a value-optimising policy. The interpretation need not be unique: a single physical system can admit multiple POMDP readings, each with its own implied utility, observation model, and hidden-world structure. The criterion is structural — does the system’s behaviour factor in a POMDP shape — without committing to which POMDP it solves.

This is the formal version of the good-regulator claim that a well-performing agent contains a model. Biehl & Virgo make “contains a model” a checkable property, and they do it without first committing to a utility function — the system is generically agenty, not necessarily a particular agent. Bounded compute enters as a restriction on which POMDPs admit interpretations: a finite system can only realise belief-updates and policies whose state spaces fit its capacity.

What it gives us: a candidate formal substrate. The good regulator theorem and bounded rationality both translate into statements about which POMDP solutions a finite agent can realise.

2.8 Computationally-embedded big world

Lewandowski et al. (Lewandowski et al. 2025) is the spine of the tension stated above. An automaton inside a universal computer is implicitly constrained — there is no need to bolt the bound on. Their proposed objective, interactivity, measures the agent’s continuing ability to adapt and learn new predictions. Empirically, deep nonlinear networks struggle to maintain interactivity; deep linear networks do better as capacity grows. I expect this paper to be load-bearing for our agenda.

LLM summary follows:

The agent is a finite-state automaton with bounded memory and per-step compute. The world is the state of a universal computer evolving under some computable rule. They exchange symbols across an interface. The agent’s boundedness is a consequence of its automaton fitting inside the world’s automaton, not a separately-imposed budget — we are invited to consider this “agent inside a bigger computer” framing, maybe relevant to boundaries and multi-level agency and all that.

Interactivity, their proposed objective, measures the agent’s continuing capacity to acquire useful new predictions about the world’s dynamics as time goes on. This is the Big-World twist: there is no terminal “I have learned the environment” state, and the right objective is sustained learnability rather than convergence to a stationary optimum. RL’s usual maximise-and-stop framing is the wrong shape for an agent in this regime.

They even have an empirical finding! Expressive nonlinear networks, despite their nominal capacity advantage, lose interactivity as they scale — their representations collapse onto fixed features and they stop generating new predictions. Linear networks scale more gracefully on the same metric. Architectural choices that look like “more capability” under maximise-and-stop may be exactly the wrong choices for an agent that has to keep learning. Whatever bounded agency ends up requiring, “scale up the most expressive network you can afford” is not it.

2.9 NARS / Assumption of Insufficient Knowledge and Resources

Pei Wang’s NARS programme defines intelligence as adaptation under insufficient knowledge and resources. Already covered in the economics of cognition notebook; flagging here because it is philosophically closest to the “intelligence is boundedness” argument. It is also vague enough that I cannot work out exactly what they mean.

2.10 Infra-Bayesianism

Kosoy and Appel (Kosoy and Appel 2020) replace the Bayesian prior — a single measure over environments — with a convex set of sub-probability measures (an infradistribution, or in the imprecise-probability vocabulary, a credal set of sa-measures). The agent decides by minimax: evaluate each policy against the worst-case measure in the set.

Prima facie this gives us nothing particularly bounded, but I am told that I might find such things if I explore Infra-Bayesian physicalism (Kosoy 2021), so let us bookmark that.

2.11 God help us, predictive coding

The Friston-style free-energy / predictive-coding tradition is in this neighbourhood and I want to mark it as such without inheriting its commitments. Active inference is, viewed from outside, a particular package of internal-model + KL-constrained policy + thermodynamic substrate; the ingredients line up with what we are assembling here. From the outside it looks like a natural approach, but observationally, I think something must be wrong with the definitions or framing or something because no one can agree what this theory is “about”. I am hopeful that I will accidentally rediscover the “good bits” of the free-energy principle by proceeding without it.

2.12 Free energy and active inference in multi-agent models

Hyland et al. (2024) proposes modelling interactions between boundedly-rational agents as free-energy equilibria. Walters et al. (2025) applies free-energy risk metrics to multi-agent systems. The active-inference framing says each agent minimises its own free energy (surprise), and the question becomes: under what conditions does a collection of surprise-minimising agents produce an aggregate that is itself low-surprise in a useful sense? Crutchfield and Jurgens (2025) on “agentic information theory” — intrinsic semantics of information processes — bears on the same question. 🚧TODO🚧