Agency under bounded compute and information

2.1 Resource-rational analysis

Lieder & Griffiths (Lieder and Griffiths 2020) frame 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.

LLM summary follows:

The optimisation 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 parameterised by how much compute it spends — and \(\mathrm{cost}(\pi)\) is a cost on cognitive operations (search expansions, posterior samples, working-memory loads). This sits 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 an internal compute knob — treating it as a unit.

The interpretive move that makes RRA distinctive in the cognitive-science direction is reading observed biases as \(\pi^*\) for some plausible cost model, not as failures of rationality. 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: an explicit 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 optimisation 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. 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, not a vague hand-wave. 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 optimised 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 optimisation 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 minimisation in this lineage.

2.5 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.6 Bounded inductive rationality

Oesterheld, Demski & Conitzer (Oesterheld, Demski, and Conitzer 2023) explicitly 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 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, and the agent’s beliefs are 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 axiomatisation: 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.7 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 rationalised by a super-polynomial decision rule, the verdict is that the rationalisation 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.

This sits differently from BO. Bounded optimality picks the best program for a given architecture; CTC rules decision theories out for any architecture at all. The two are complementary — BO tells us how to optimise 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.8 POMDP-as-agent

Biehl & Virgo (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 explicit 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.9 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 the bounded agency cell ends up requiring, “scale up the most expressive network you can afford” is not it.