In contrast to popular decision-making frameworks such as reinforcement learning, which are built upon appealing to decision-theoretic notions such as Maximum Expected Utility, we instead construct an agent by trying to minimise the expected number of bits needed to losslessly describe general agent-environment interactions. The appeal with this approach is that if we can construct a good universal coding scheme for arbitrary agent interactions, one could simply sample from this coding distribution to generate a control policy. However when considering general agents, whose goal is to work well across multiple environments, this question turns out to be surprisingly subtle. Naive approaches which do not discriminate between actions and observations fail, and are subject to the self-delusion problem [Ortega et al., 2021]. In this work, we will adopt a universal source coding perspective to this question, and showcase its efficacy by applying it to the challenging non-stationary stochastic bandit problem. In the passive case, namely, sequential prediction of observations under the logarithmic loss, there is a well developed universal source coding literature for dealing with non-stationary sources under various types of non-stationarity. The most influential idea for modelling piecewise stationary sources is the transition diagram technique of Willems [1996]. This technique performs Bayesian model averaging over all possible partitions of a sequence of data, cleverly exploiting dynamic programming to yield an algorithm which has both quadratic time complexity and provable regret guarantees.

Large language models (LLMs) can be prompted to do many tasks, but finding good prompts is not always easy, nor is understanding some performant prompts. We explore these issues by viewing prompting as conditioning a near-optimal sequence predictor (LLM) pretrained on diverse data sources. Through numerous prompt search experiments, we show that the unintuitive patterns in optimal prompts can be better understood given the pretraining distribution, which is often unavailable in practice. Moreover, even using exhaustive search, reliably identifying optimal prompts from practical neural predictors can be difficult. Further, we demonstrate that common prompting methods, such as using intuitive prompts or samples from the targeted task, are in fact suboptimal. Thus, this work takes an initial step towards understanding the difficulties in finding and understanding optimal prompts from a statistical and empirical perspective.

We are interested in tree search algorithms for deterministic domains. Tree search algorithms such as all variants of best-first search -- including A* [Hart et al., 1968], Weighted-A* (WA*), and Greedy Best-First Search (GBFS) [Doran et al., 1966] -- and variants of MCTS -- such as UCT [Kocsis and Szepesvári, 2006], AlphaGo, AlphaZero and other variants [Silver et al., 2016, 2017b,a] -- explore the search tree starting at the root and can visit a node only if its parent has been visited first. These algorithms are often guided by some side information, such as with cost-to-go heuristic function for A*, WA* and GBFS, a reward/value function for UCT and AlphaZero, or a policy for AlphaZero, Levin Tree Search (LTS) [Orseau et al., 2018], and Policy-Guided Heuristic Search [Orseau and Lelis, 2021]. Such algorithms also sometimes come with different types of guarantees: A* and WA*, with an admissible heuristic function -- i.e., a function that never overestimates the optimal costto-go -- are guaranteed to return a solution that is cost-optimal (A*) or bounded-suboptimal (WA*), while UCT and AlphaZero are guaranteed to (eventually) have low regret in terms of cumulative reward during the search. LTS is guaranteed to return a solution within a number of search steps that depends on the quality of its policy. In this paper, we consider the latter type of guarantee, on the efficiency of the search process depending on the quality of the side information. To explain the main concepts of this paper, let us consider a kind of side information we call clues: some nodes are clue nodes, and a node can be known to be a clue node only when reaching it. A clue may be helpful if it is on the path toward a solution node, or misleading otherwise. The following example describes a minimalistic clue environment.

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 bad, in theory and in practice. When RL policies would devolve into undesired behavior, a common countermeasure is KL regularization to a trusted policy ("Don't do anything I wouldn't do"). All current cutting-edge language models are RL agents that are KL-regularized to a "base policy" that is purely predictive. Unfortunately, we demonstrate that when this base policy is a Bayesian predictive model of a trusted policy, the KL constraint is no longer reliable for controlling the behavior of an advanced RL agent. We demonstrate this theoretically using algorithmic information theory, and while systems today are too weak to exhibit this theorized failure precisely, we RL-finetune a language model and find evidence that our formal results are plausibly relevant in practice. We also propose a theoretical alternative that avoids this problem by replacing the "Don't do anything I wouldn't do" principle with "Don't do anything I mightn't do".

To understand the risks posed by a new AI system, we must understand what it can and cannot do. Building on prior work, we introduce a programme of new "dangerous capability" evaluations and pilot them on Gemini 1.0 models. Our evaluations cover four areas: (1) persuasion and deception; (2) cyber-security; (3) self-proliferation; and (4) self-reasoning. We do not find evidence of strong dangerous capabilities in the models we evaluated, but we flag early warning signs. Our goal is to help advance a rigorous science of dangerous capability evaluation, in preparation for future models.

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 improves the overall predictive performance, especially when considering distributional shift between training and evaluation data, we here emphasize the perspective that online adaptation turns parameters into temporally changing states and provides a form of context-length extension with memory in weights, more in line with the concept of memory in neuroscience. We pay particular attention to the speed of adaptation (in terms of sample efficiency),sensitivity to the overall distributional drift, and the computational overhead for performing gradient computations and parameter updates. Our empirical study provides insights on when online adaptation is particularly interesting. We highlight that with online adaptation the conceptual distinction between in-context learning and fine tuning blurs: both are methods to condition the model on previously observed tokens.

Meta-learning has emerged as a powerful approach to train neural networks to learn new tasks quickly from limited data. Broad exposure to different tasks leads to versatile representations enabling general problem solving. But, what are the limits of meta-learning? In this work, we explore the potential of amortizing the most powerful universal predictor, namely Solomonoff Induction (SI), into neural networks via leveraging meta-learning to its limits. We use Universal Turing Machines (UTMs) to generate training data used to expose networks to a broad range of patterns. We provide theoretical analysis of the UTM data generation processes and meta-training protocols. We conduct comprehensive experiments with neural architectures (e.g. LSTMs, Transformers) and algorithmic data generators of varying complexity and universality. Our results suggest that UTM data is a valuable resource for meta-learning, and that it can be used to train neural networks capable of learning universal prediction strategies.

Prior approximations of AIXI, a Bayesian optimality notion for general reinforcement learning, can only approximate AIXI's Bayesian environment model using an a-priori defined set of models. This is a fundamental source of epistemic uncertainty for the agent in settings where the existence of systematic bias in the predefined model class cannot be resolved by simply collecting more data from the environment. We address this issue in the context of Human-AI teaming by considering a setup where additional knowledge for the agent in the form of new candidate models arrives from a human operator in an online fashion. We introduce a new agent called DynamicHedgeAIXI that maintains an exact Bayesian mixture over dynamically changing sets of models via a time-adaptive prior constructed from a variant of the Hedge algorithm. The DynamicHedgeAIXI agent is the richest direct approximation of AIXI known to date and comes with good performance guarantees. Experimental results on epidemic control on contact networks validates the agent's practical utility.

We propose a novel algorithmic framework for distributional reinforcement learning, based on learning finite-dimensional mean embeddings of return distributions. We derive several new algorithms for dynamic programming and temporal-difference learning based on this framework, provide asymptotic convergence theory, and examine the empirical performance of the algorithms on a suite of tabular tasks. Further, we show that this approach can be straightforwardly combined with deep reinforcement learning, and obtain a new deep RL agent that improves over baseline distributional approaches on the Arcade Learning Environment.

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 prevalent in ML) by adopting an AIT perspective on the problem of learning kernels from data, in kernel ridge regression, through the method of Sparse Kernel Flows. In particular, by looking at the differences and commonalities between Minimal Description Length (MDL) and Regularization in Machine Learning (RML), we prove that the method of Sparse Kernel Flows is the natural approach to adopt to learn kernels from data. This paper shows that it is not necessary to use the statistical route to derive Sparse Kernel Flows and that one can directly work with code-lengths and complexities that are concepts that show up in AIT.