Publications (198)
An effective Procedure for Speeding up Algorithms
Marcus Hutter
The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed. The main idea is to enumerate all programs provably equivale…
A game theory for foundation models shows new paths to rational cooperation through similarity inference
Alexander Meulemans, Maciej Wołczyk, Maciej WoÅczyk +14
As autonomous agents powered by foundation models are increasingly integrated into social and economic systems, understanding the principles governing their collective behavior is…
RL, but don't do anything I wouldn't do
Michael K. Cohen, Marcus Hutter, Yoshua Bengio +1
In reinforcement learning, if the agent's reward differs from the designers' true utility, even only rarely, the state distribution resulting from the agent's policy can be very ba…
Consistency of Feature Markov Processes
Peter Sunehag, Marcus Hutter
We are studying long term sequence prediction (forecasting). We approach this by investigating criteria for choosing a compact useful state representation. The state is supposed to…
Bayesian Regression of Piecewise Constant Functions
Marcus Hutter
We derive an exact and efficient Bayesian regression algorithm for piecewise constant functions of unknown segment number, boundary location, and levels. It works for any noise and…
On the Computability of AIXI
Jan Leike, Marcus Hutter
How could we solve the machine learning and the artificial intelligence problem if we had infinite computation? Solomonoff induction and the reinforcement learning agent AIXI are p…
Neural Networks and the Chomsky Hierarchy
Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya +8
Reliable generalization lies at the heart of safe ML and AI. However, understanding when and how neural networks generalize remains one of the most important unsolved problems in t…
Sequential Learning Of Neural Networks for Prequential MDL
Jorg Bornschein, Yazhe Li, Marcus Hutter
Minimum Description Length (MDL) provides a framework and an objective for principled model evaluation. It formalizes Occam's Razor and can be applied to data from non-stationary s…
Robust Feature Selection by Mutual Information Distributions
Marco Zaffalon, Marcus Hutter
Mutual information is widely used in artificial intelligence, in a descriptive way, to measure the stochastic dependence of discrete random variables. In order to address questions…
The Loss Rank Principle for Model Selection
Marcus Hutter
We introduce a new principle for model selection in regression and classification. Many regression models are controlled by some smoothness or flexibility or complexity parameter c…
Offline to Online Conversion
Marcus Hutter
We consider the problem of converting offline estimators into an online predictor or estimator with small extra regret. Formally this is the problem of merging a collection of prob…
The Fastest and Shortest Algorithm for All Well-Defined Problems
Marcus Hutter
An algorithm is described that solves any well-defined problem as quickly as the fastest algorithm computing a solution to , save for a factor of 5 and low-order additiv…
Fitness Uniform Selection to Preserve Genetic Diversity
Marcus Hutter
In evolutionary algorithms, the fitness of a population increases with time by mutating and recombining individuals and by a biased selection of more fit individuals. The right sel…
A Novel Illumination-Invariant Loss for Monocular 3D Pose Estimation
Srimal Jayawardena, Marcus Hutter, Nathan Brewer
The problem of identifying the 3D pose of a known object from a given 2D image has important applications in Computer Vision. Our proposed method of registering a 3D model of a kno…
Compress and Control
Joel Veness, Marc G. Bellemare, Marcus Hutter +2
This paper describes a new information-theoretic policy evaluation technique for reinforcement learning. This technique converts any compression or density model into a correspondi…
Free Lunch for Optimisation under the Universal Distribution
Tom Everitt, Tor Lattimore, Marcus Hutter
Function optimisation is a major challenge in computer science. The No Free Lunch theorems state that if all functions with the same histogram are assumed to be equally probable th…
Robust Inference of Trees
Marco Zaffalon, Marcus Hutter
This paper is concerned with the reliable inference of optimal tree-approximations to the dependency structure of an unknown distribution generating data. The traditional approach…
Reinforcement Learning via AIXI Approximation
Joel Veness, Kee Siong Ng, Marcus Hutter +1
This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. This approach is based on a direct approximation of AIXI, a Bayesian…
Matching 2-D Ellipses to 3-D Circles with Application to Vehicle Pose Estimation
Marcus Hutter, Nathan Brewer
Finding the three-dimensional representation of all or a part of a scene from a single two dimensional image is a challenging task. In this paper we propose a method for identifyin…
On Universal Prediction and Bayesian Confirmation
Marcus Hutter
The Bayesian framework is a well-studied and successful framework for inductive reasoning, which includes hypothesis testing and confirmation, parameter estimation, sequence predic…
On the Foundations of Universal Sequence Prediction
Marcus Hutter
Solomonoff completed the Bayesian framework by providing a rigorous, unique, formal, and universal choice for the model class and the prior. We discuss in breadth how and in which…
On the Role of Neural Collapse in Transfer Learning
Tomer Galanti, András György, Marcus Hutter
We study the ability of foundation models to learn representations for classification that are transferable to new, unseen classes. Recent results in the literature show that repre…
A Combinatorial Perspective on Transfer Learning
Jianan Wang, Eren Sezener, David Budden +2
Human intelligence is characterized not only by the capacity to learn complex skills, but the ability to rapidly adapt and acquire new skills within an ever-changing environment. I…
Universal Algorithmic Intelligence: A mathematical top->down approach
Marcus Hutter
Sequential decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known. Solomonoff's theory…
Feature Dynamic Bayesian Networks
Marcus Hutter
Feature Markov Decision Processes (PhiMDPs) are well-suited for learning agents in general environments. Nevertheless, unstructured (Phi)MDPs are limited to relatively simple envir…
Universal Prediction of Selected Bits
Tor Lattimore, Marcus Hutter, Vaibhav Gavane
Many learning tasks can be viewed as sequence prediction problems. For example, online classification can be converted to sequence prediction with the sequence being pairs of input…
Asymptotics of Continuous Bayes for Non-i.i.d. Sources
Tor Lattimore, Marcus Hutter
Clarke and Barron analysed the relative entropy between an i.i.d. source and a Bayesian mixture over a continuous class containing that source. In this paper a comparable result is…
Distributional Bellman Operators over Mean Embeddings
Li Kevin Wenliang, Grégoire Delétang, Matthew Aitchison +4
We propose a novel algorithmic framework for distributional reinforcement learning, based on learning finite-dimensional mean embeddings of return distributions. We derive several…
Gluon Mass from Instantons
Marcus Hutter
The gluon propagator is calculated in the instanton background in a form appropriate for extracting the momentum dependent gluon mass. In background--gauge we get for the mass…
General Discounting versus Average Reward
Marcus Hutter
Consider an agent interacting with an environment in cycles. In every interaction cycle the agent is rewarded for its performance. We compare the average reward U from cycle 1 to m…
The Sample-Complexity of General Reinforcement Learning
Tor Lattimore, Marcus Hutter, Peter Sunehag
We present a new algorithm for general reinforcement learning where the true environment is known to belong to a finite class of N arbitrary models. The algorithm is shown to be ne…
Evaluating Representations with Readout Model Switching
Yazhe Li, Jorg Bornschein, Marcus Hutter
Although much of the success of Deep Learning builds on learning good representations, a rigorous method to evaluate their quality is lacking. In this paper, we treat the evaluatio…
A Monte Carlo AIXI Approximation
Joel Veness, Kee Siong Ng, Marcus Hutter +2
This paper introduces a principled approach for the design of a scalable general reinforcement learning agent. Our approach is based on a direct approximation of AIXI, a Bayesian o…
One Decade of Universal Artificial Intelligence
Marcus Hutter
The first decade of this century has seen the nascency of the first mathematical theory of general artificial intelligence. This theory of Universal Artificial Intelligence (UAI) h…
MDL Convergence Speed for Bernoulli Sequences
Jan Poland, Marcus Hutter
The Minimum Description Length principle for online sequence estimation/prediction in a proper learning setup is studied. If the underlying model class is discrete, then the total…
Exact Reduction of Huge Action Spaces in General Reinforcement Learning
Sultan Javed Majeed, Marcus Hutter
The reinforcement learning (RL) framework formalizes the notion of learning with interactions. Many real-world problems have large state-spaces and/or action-spaces such as in Go,…
Counterfactual Credit Assignment in Model-Free Reinforcement Learning
Thomas Mesnard, Théophane Weber, Fabio Viola +11
Credit assignment in reinforcement learning is the problem of measuring an action's influence on future rewards. In particular, this requires separating skill from luck, i.e. disen…
Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence
Daniil Ryabko, Marcus Hutter
We address the problem of reinforcement learning in which observations may exhibit an arbitrary form of stochastic dependence on past observations and actions. The task for an agen…
Adaptive Online Prediction by Following the Perturbed Leader
Marcus Hutter, Jan Poland
When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of sqrt(complexity/current loss) renders the a…
Bridging Algorithmic Information Theory and Machine Learning: A New Approach to Kernel Learning
Boumediene Hamzi, Marcus Hutter, Houman Owhadi
Machine Learning (ML) and Algorithmic Information Theory (AIT) look at Complexity from different points of view. We explore the interface between AIT and Kernel Methods (that are p…
Model Selection by Loss Rank for Classification and Unsupervised Learning
Minh-Ngoc Tran, Marcus Hutter
Hutter (2007) recently introduced the loss rank principle (LoRP) as a generalpurpose principle for model selection. The LoRP enjoys many attractive properties and deserves further…
A Theory of Universal Artificial Intelligence based on Algorithmic Complexity
Marcus Hutter
Decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental prior probability distribution is known. Solomonoff's theory of univers…
Reward Tampering Problems and Solutions in Reinforcement Learning: A Causal Influence Diagram Perspective
Tom Everitt, Marcus Hutter, Ramana Kumar +1
Can humans get arbitrarily capable reinforcement learning (RL) agents to do their bidding? Or will sufficiently capable RL agents always find ways to bypass their intended objectiv…
Sparse Sequential Dirichlet Coding
Joel Veness, Marcus Hutter
This short paper describes a simple coding technique, Sparse Sequential Dirichlet Coding, for multi-alphabet memoryless sources. It is appropriate in situations where only a small,…
Formalizing Embeddedness Failures in Universal Artificial Intelligence
Cole Wyeth, Marcus Hutter
We rigorously discuss the commonly asserted failures of the AIXI reinforcement learning agent as a model of embedded agency. We attempt to formalize these failure modes and prove t…
Sparse Adaptive Dirichlet-Multinomial-like Processes
Marcus Hutter
Online estimation and modelling of i.i.d. data for short sequences over large or complex "alphabets" is a ubiquitous (sub)problem in machine learning, information theory, data comp…
Prediction with Expert Advice by Following the Perturbed Leader for General Weights
Marcus Hutter, Jan Poland
When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of sqrt(complexity/current loss) renders the a…
Fully General Online Imitation Learning
Michael K. Cohen, Marcus Hutter, Neel Nanda
In imitation learning, imitators and demonstrators are policies for picking actions given past interactions with the environment. If we run an imitator, we probably want events to…
Combining a Meta-Policy and Monte-Carlo Planning for Scalable Type-Based Reasoning in Partially Observable Environments
Jonathon Schwartz, Hanna Kurniawati, Marcus Hutter
The design of autonomous agents that can interact effectively with other agents without prior coordination is a core problem in multi-agent systems. Type-based reasoning methods ac…
Towards a Universal Theory of Artificial Intelligence based on Algorithmic Probability and Sequential Decision Theory
Marcus Hutter
Decision theory formally solves the problem of rational agents in uncertain worlds if the true environmental probability distribution is known. Solomonoff's theory of universal ind…
Asymptotically Unambitious Artificial General Intelligence
Michael K Cohen, Badri Vellambi, Marcus Hutter
General intelligence, the ability to solve arbitrary solvable problems, is supposed by many to be artificially constructible. Narrow intelligence, the ability to solve a given part…
Reward-Punishment Symmetric Universal Intelligence
Samuel Allen Alexander, Marcus Hutter
Can an agent's intelligence level be negative? We extend the Legg-Hutter agent-environment framework to include punishments and argue for an affirmative answer to that question. We…
Gated Linear Networks
Joel Veness, Tor Lattimore, David Budden +8
This paper presents a new family of backpropagation-free neural architectures, Gated Linear Networks (GLNs). What distinguishes GLNs from contemporary neural networks is the distri…
U-Clip: On-Average Unbiased Stochastic Gradient Clipping
Bryn Elesedy, Marcus Hutter
U-Clip is a simple amendment to gradient clipping that can be applied to any iterative gradient optimization algorithm. Like regular clipping, U-Clip involves using gradients that…
Atari-5: Distilling the Arcade Learning Environment down to Five Games
Matthew Aitchison, Penny Sweetser, Marcus Hutter
The Arcade Learning Environment (ALE) has become an essential benchmark for assessing the performance of reinforcement learning algorithms. However, the computational cost of gener…
Properties of Algorithmic Information Distance
Marcus Hutter
The domain-independent universal Normalized Information Distance based on Kolmogorov complexity has been (in approximate form) successfully applied to a variety of difficult cluste…
Death and Suicide in Universal Artificial Intelligence
Jarryd Martin, Tom Everitt, Marcus Hutter
Reinforcement learning (RL) is a general paradigm for studying intelligent behaviour, with applications ranging from artificial intelligence to psychology and economics. AIXI is a…
Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games
Cole Wyeth, Marcus Hutter, Jan Leike +1
A Bayesian player acting in an infinite multi-player game learns to predict the other players' strategies if his prior assigns positive probability to their play (or contains a gra…
Convergence of Discrete MDL for Sequential Prediction
Jan Poland, Marcus Hutter
We study the properties of the Minimum Description Length principle for sequence prediction, considering a two-part MDL estimator which is chosen from a countable class of models.…
Gauge Invariant Quark Propagator in the Instanton Background
Marcus Hutter
After a general discussion on the choice of gauge, we compare the quark propagator in the background of one instanton in regular and singular gauge with a gauge invariant propagato…
Online Learning of k-CNF Boolean Functions
Joel Veness, Marcus Hutter
This paper revisits the problem of learning a k-CNF Boolean function from examples in the context of online learning under the logarithmic loss. In doing so, we give a Bayesian int…
Self-Modification of Policy and Utility Function in Rational Agents
Tom Everitt, Daniel Filan, Mayank Daswani +1
Any agent that is part of the environment it interacts with and has versatile actuators (such as arms and fingers), will in principle have the ability to self-modify -- for example…
Distribution of Mutual Information
Marcus Hutter
The mutual information of two random variables i and j with joint probabilities t_ij is commonly used in learning Bayesian nets as well as in many other fields. The chances t_ij ar…
On the Convergence Speed of MDL Predictions for Bernoulli Sequences
Jan Poland, Marcus Hutter
We consider the Minimum Description Length principle for online sequence prediction. If the underlying model class is discrete, then the total expected square loss is a particularl…
Convergence and Loss Bounds for Bayesian Sequence Prediction
Marcus Hutter
The probability of observing at time , given past observations can be computed with Bayes' rule if the true generating distribution of the sequences $…
Understanding Prompt Tuning and In-Context Learning via Meta-Learning
Tim Genewein, Li Kevin Wenliang, Jordi Grau-Moya +3
Prompting is one of the main ways to adapt a pretrained model to target tasks. Besides manually constructing prompts, many prompt optimization methods have been proposed in the lit…
Gradient-based Reinforcement Planning in Policy-Search Methods
Ivo Kwee, Marcus Hutter, Juergen Schmidhuber
We introduce a learning method called ``gradient-based reinforcement planning'' (GREP). Unlike traditional DP methods that improve their policy backwards in time, GREP is a gradien…
Hybrid Rounding Techniques for Knapsack Problems
Monaldo Mastrolilli, Marcus Hutter
We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rou…
Reinforcement Learning with a Corrupted Reward Channel
Tom Everitt, Victoria Krakovna, Laurent Orseau +2
No real-world reward function is perfect. Sensory errors and software bugs may result in RL agents observing higher (or lower) rewards than they should. For example, a reinforcemen…
Generalised Discount Functions applied to a Monte-Carlo AImu Implementation
Sean Lamont, John Aslanides, Jan Leike +1
In recent years, work has been done to develop the theory of General Reinforcement Learning (GRL). However, there are few examples demonstrating these results in a concrete way. In…
Exponential Speedups by Rerooting Levin Tree Search
Laurent Orseau, Marcus Hutter, Levi H. S. Lelis
Levin Tree Search (LTS) (Orseau et al., 2018) is a search algorithm for deterministic environments that uses a user-specified policy to guide the search. It comes with a formal gua…
Open Problems in Universal Induction & Intelligence
Marcus Hutter
Specialized intelligent systems can be found everywhere: finger print, handwriting, speech, and face recognition, spam filtering, chess and other game programs, robots, et al. This…
Shaking the foundations: delusions in sequence models for interaction and control
Pedro A. Ortega, Markus Kunesch, Grégoire Delétang +16
The recent phenomenal success of language models has reinvigorated machine learning research, and large sequence models such as transformers are being applied to a variety of domai…
Concentration and Confidence for Discrete Bayesian Sequence Predictors
Tor Lattimore, Marcus Hutter, Peter Sunehag
Bayesian sequence prediction is a simple technique for predicting future symbols sampled from an unknown measure on infinite sequences over a countable alphabet. While strong bound…
Master Algorithms for Active Experts Problems based on Increasing Loss Values
Jan Poland, Marcus Hutter
We specify an experts algorithm with the following characteristics: (a) it uses only feedback from the actions actually chosen (bandit setup), (b) it can be applied with countably…
Revisiting Dynamic Evaluation: Online Adaptation for Large Language Models
Amal Rannen-Triki, Jorg Bornschein, Razvan Pascanu +5
We consider the problem of online fine tuning the parameters of a language model at test time, also known as dynamic evaluation. While it is generally known that this approach impr…
Featureless 2D-3D Pose Estimation by Minimising an Illumination-Invariant Loss
Srimal Jayawardena, Marcus Hutter, Nathan Brewer
The problem of identifying the 3D pose of a known object from a given 2D image has important applications in Computer Vision ranging from robotic vision to image analysis. Our prop…
Defensive Universal Learning with Experts
Jan Poland, Marcus Hutter
This paper shows how universal learning can be achieved with expert advice. To this aim, we specify an experts algorithm with the following characteristics: (a) it uses only feedba…
A Bayesian View of the Poisson-Dirichlet Process
Wray Buntine, Marcus Hutter
The two parameter Poisson-Dirichlet Process (PDP), a generalisation of the Dirichlet Process, is increasingly being used for probabilistic modelling in discrete areas such as langu…
Count-Based Exploration in Feature Space for Reinforcement Learning
Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt +1
We introduce a new count-based optimistic exploration algorithm for Reinforcement Learning (RL) that is feasible in environments with high-dimensional state-action spaces. The succ…
Algorithmic Randomness as Foundation of Inductive Reasoning and Artificial Intelligence
Marcus Hutter
This article is a brief personal account of the past, present, and future of algorithmic randomness, emphasizing its role in inductive inference and artificial intelligence. It is…
Strong Asymptotic Assertions for Discrete MDL in Regression and Classification
Jan Poland, Marcus Hutter
We study the properties of the MDL (or maximum penalized complexity) estimator for Regression and Classification, where the underlying model class is countable. We show in particul…
Monotone Conditional Complexity Bounds on Future Prediction Errors
Alexey Chernov, Marcus Hutter
We bound the future loss when predicting any (computably) stochastic sequence online. Solomonoff finitely bounded the total deviation of his universal predictor M from the true dis…
A Strongly Asymptotically Optimal Agent in General Environments
Michael K. Cohen, Elliot Catt, Marcus Hutter
Reinforcement Learning agents are expected to eventually perform well. Typically, this takes the form of a guarantee about the asymptotic behavior of an algorithm given some assump…
A Complete Theory of Everything (will be subjective)
Marcus Hutter
Increasingly encompassing models have been suggested for our world. Theories range from generally accepted to increasingly speculative to apparently bogus. The progression of theor…
3D Model Assisted Image Segmentation
Srimal Jayawardena, Di Yang, Marcus Hutter
The problem of segmenting a given image into coherent regions is important in Computer Vision and many industrial applications require segmenting a known object into its components…
A Formal Measure of Machine Intelligence
Shane Legg, Marcus Hutter
A fundamental problem in artificial intelligence is that nobody really knows what intelligence is. The problem is especially acute when we need to consider artificial systems which…
Formal Algorithms for Transformers
Mary Phuong, Marcus Hutter
This document aims to be a self-contained, mathematically precise overview of transformer architectures and algorithms (*not* results). It covers what transformers are, how they ar…
Practical Robust Estimators for the Imprecise Dirichlet Model
Marcus Hutter
Walley's Imprecise Dirichlet Model (IDM) for categorical i.i.d. data extends the classical Dirichlet model to a set of priors. It overcomes several fundamental problems which other…
(Non-)Equivalence of Universal Priors
Ian Wood, Peter Sunehag, Marcus Hutter
Ray Solomonoff invented the notion of universal induction featuring an aptly termed "universal" prior probability function over all possible computable environments. The essential…
A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data
Ke Zhang, Marcus Hutter, Huidong Jin
Detecting outliers which are grossly different from or inconsistent with the remaining dataset is a major challenge in real-world KDD applications. Existing outlier detection metho…
Conditions on Features for Temporal Difference-Like Methods to Converge
Marcus Hutter, Samuel Yang-Zhao, Sultan J. Majeed
The convergence of many reinforcement learning (RL) algorithms with linear function approximation has been investigated extensively but most proofs assume that these methods conver…
Algorithmic Information Theory: a brief non-technical guide to the field
Marcus Hutter
This article is a brief guide to the field of algorithmic information theory (AIT), its underlying philosophy, and the most important concepts. AIT arises by mixing information the…
On Sequence Prediction for Arbitrary Measures
Daniil Ryabko, Marcus Hutter
Suppose we are given two probability measures on the set of one-way infinite finite-alphabet sequences and consider the question when one of the measures predicts the other, that i…
Discrete MDL Predicts in Total Variation
Marcus Hutter
The Minimum Description Length (MDL) principle selects the model that has the shortest code for data plus model. We show that for a countable class of models, MDL predictions are c…
Instantons in QCD: Theory and application of the instanton liquid model
Marcus Hutter
Numerical and anaytical studies of the instanton liquid model have allowed the determination of many hadronic parameters during the last 13 years. Most part of this thesis is devot…
Can Intelligence Explode?
Marcus Hutter
The technological singularity refers to a hypothetical scenario in which technological advances virtually explode. The most popular scenario is the creation of super-intelligent al…
PAC Bounds for Discounted MDPs
Tor Lattimore, Marcus Hutter
We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (MDPs). For the upper bound we make…
Principles of Solomonoff Induction and AIXI
Peter Sunehag, Marcus Hutter
We identify principles characterizing Solomonoff Induction by demands on an agent's external behaviour. Key concepts are rationality, computability, indifference and time consisten…
Self-Optimizing and Pareto-Optimal Policies in General Environments based on Bayes-Mixtures
Marcus Hutter
The problem of making sequential decisions in unknown probabilistic environments is studied. In cycle action results in perception and reward , where all quant…