Open-Endedness is Essential for Artificial Superhuman Intelligence — part 5/5
Cleaned-text code points [60513, 71259). Bibliography omitted here; source.md includes it.
We allow for the compression map C h t C_{h_{t}} to be lossy . Hence, O O also possesses a decompression map D h t : { 0 , 1 } ∗ → 𝒳 D_{h_{t}}:\{0,1\}^{*}\rightarrow\mathcal{X} , a symmetric loss function ℓ : 𝒳 × 𝒳 → ℝ + \ell:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}^{+} , and a threshold ϵ ∈ ℝ + \epsilon\in\mathbb{R}^{+} that upper-bounds the error made by by C h t C_{h_{t}} : ∀ T , ∀ t < T : ℓ ( D h t ( C h t ( X T ) ) , X T ) < ϵ . \forall T,\forall t<T:\ell(D_{h_{t}}(C_{h_{t}}(X_{T})),X_{T})<\epsilon. We can strengthen the definition to be independent of ϵ \epsilon by appealing to rate-distortion theory. A rate-distortion curve plots the the minimum information content | C h ( X ) | |C_{h}(X)| such that ℓ ( D h ( C h ( X ) ) , X ) < ϵ \ell(D_{h}(C_{h}(X)),X)<\epsilon against ϵ \epsilon , where the minimum is over the maps C h C_{h} and D h D_{h} . The information content is referred to as the rate and ϵ \epsilon is referred to as the distortion. Picture a grid of rate-distortion curves G t T G_{tT} indexed by (discretized) t t and T T , as in Figure 3 . Remember that T > t T>t , so G t T G_{tT} is strictly upper triangular, with other entries being undefined. Then broad novelty is the requirement that the curves get “fatter” as you move across the columns T T on the grid, for every row t t . Similarly, broad learnability is the requirement that the curves get “flatter” as you move down the rows t t on the grid, for every column T T . Broad open-endedness is the requirement that both broad novelty and broad learnability hold. This notion of broad open-endedness is vague in the same way the notion of “convergence” is vague in that it can be made precise in many subtly different but connected ways. For instance, one could say a system is “uniformly” open-ended if distortion increases across the rows and decreases down the columns for every rate ϵ \epsilon . Alternatively, one could define “average” open-endedness by requiring that the integral of the rate-distortion curve get larger as you move across the columns and smaller as you move down the rows. We hope that future work will elucidate these subtleties in defining broad open-endedness and determine which variants have theoretical or practical merit.
## Appendix C Further Related Work
Open-endedeness as a term emerged from the AI Life community when trying to quantify and replicate the increasing complexity and perpetual novelty of biological evolution. This is a rich field with a significant degree of disagreement [ Earle et al., 2021 ] . As such there are a wide range of metrics proposed within the context of evolutionary systems which aim to quantify it’s behavior. For instance persistence filtering, which measures how many generations an organism has persisted for [ Dolson et al., 2019 ] , and evolutionary activity statistics [ Bedau et al., 1997 , Bedau et al., 1998 ] . The closely related question around the necessary conditions to produce open-ended evolution has also been deeply studied [ Taylor, 2018 , Taylor, 2015 ] . As these definitions are largely specific to biological evolution, we focus the remainder of our discussion on the more recent definitions which aim to define open-ended systems in a way that applies to current ML systems and systems more broadly.
Our definition of open-endedness is closely related to the concept of potential surprise in economics [ Shackle, 1949 ] . To measure potential surprise , an individual should ask: “how surprised would I be if this outcome actually occurred, if, at the time it occurred, I were still looking at the world in the way I look at it right now?” [ Derbyshire, 2017 ] . Interpreting surprise as unpredictability under a statistical model, an open-ended system S S is precisely one which produces ever increasing “Shackle surprise” in an observer which is learning. The concept of potential surprise is itself based on the century-old idea of Knightian uncertainty [ Knight, 1921 ] . Knightian uncertainty is a lack of any quantifiable knowledge about some possible occurrence, as opposed to the presence of quantifiable risk. Thus, somewhat imprecisely, an open-ended system S S is one which induces Knightian uncertainty in an observer who is learning.
In Stanley and Lehman [2015] , the authors argue that local search for novel and interesting artifacts can be advantageous over optimization for a global objective. This is because stepping stones towards a solution that optimizes the global objective may well not resemble the solution itself. Hence it is hard to translate the global objective into a local improvement operator that reliably accumulates improvements without getting stuck in local optima. To address this deceptiveness, they suggest that novelty search [ Lehman and Stanley, 2011 ] , guided by a notion of interestingness, can uncover stepping stones that advance knowledge and capability. We take inspiration from this blueprint and turn it into a definition. In order to clarify the notions of novelty and interestingness, we formalize them with respect to an external observer. Novelty becomes unpredictability according to the observer’s history-conditional model, and interestingness becomes learnability of that model across the history of observations.
Our definition naturally relates to the notion of curiosity. Curiosity, implemented as prediction error of a world model, has long been mooted as an intrinsic motivation that can lead to open-ended discovery in RL agents given a sufficiently rich environment space [ Schmidhuber, 1991b , Pathak et al., 2017 , Raileanu and Rocktäschel, 2020 , Henaff et al., 2023 ] . Our definition of novelty is effectively a generalisation of curiosity, without requiring an overarching RL framework. Our requirement of learnability ensures that the observer attempts to capture all the epistemic uncertainty about the artifacts produced by a system. One challenge is that curiosity based on novelty alone leads to “stochastic traps”, whereby an agent will seek out sources of random noise with which to sate its curiosity [ Schmidhuber, 1991a , Burda et al., 2018 , Shyam et al., 2019 ] . In principle, our definition of novelty collapses such aleatoric uncertainty by taking the expectation. In practice, we can only estimate the expectation, so it may be useful to subtract from the loss an estimate of the aleatoric uncertainty as in Mavor-Parker et al. [2022] . We hope that future work will examine such subtleties required for an algorithmic implementation of our definition.
The synergies between foundation models and open-endedness have previously been discussed by Jiang et al. [2022] . The authors propose a general notion of exploration and detail how open-endedness can be used to solve exploration problems when training foundation models. Our work follows in this line of thinking, providing a formal definition of open-endedness to make the discussion precise, and further developing the connections between open-endedness and ASI. A construction of a particular open-ended learning system is provided in [ Jiang et al., 2022 ] , which may or may not fit our proposed definition of an open-ended system depending on how it is instantiated. The system generates Turing machine descriptions of MDPs, explicitly optimizing for an objective containing terms for learning potential, diversity, and grounding. These terms have some high-level relation to our notions of learnability and novelty, but they are quite distinct in the details. For instance, learning potential is divided into three sub-critia, improbability, learnability, and consistency, which are not made entirely formal. More crucially, the learnability discussed by [ Jiang et al., 2022 ] is a property of a single MDP, whereas the learnability we define is a property of a sequence of artifacts. Similarly, in [ Jiang et al., 2022 ] diversity is defined as a distance measure between MDPs, whereas novelty, as we define it, is a property of the learning of the observer with no necessary relationship to distances in the space of artifacts. It would be an interesting direction for future research to understand under what conditions the system described in [ Jiang et al., 2022 ] would be open-ended by our definition, and, more generally, whether one can directly optimize for open-endedness in some circumstances.
Open-endedness is related to, but separate from, the notion of an AI-generating algorithm [ Clune, 2020 , AIGA,] . An AIGA automatically learns how to build a general AI, based on meta-learning model architectures, meta-learning learning algorithms, and automatically generating data from which to learn. Adapting the logic of Clune [2020] , an AIGA need not be open-ended by our definition; if an AIGA had the objective of passing a Turing test, it need not produce any further novelty once this objective had been achieved. Likewise, an open-ended system need not be an AIGA; as we shall see in Section 2.4 , there exist open-ended systems with narrow scope that match or exceed human ability without full domain-generality. Our idea of an Open-Ended Foundation Model in Section 3 lives at the intersection between open-endedness and AIGAs.
Similarly open-endedness is related to, but distinct from, continual RL [ Abel et al., 2023 ] . A continual RL problem is one in which the best agents never stop learning. However, as observed by [ Sigaud et al., 2023 ] , this does not necessarily imply that the agent policies accumulate increasing novelty. Rather, a continual RL agent could cycle among some set of strategies. In the case where continual RL does produce policies which are open-ended according to some observer, this open-endedness will have a scope that is restricted by the environment.
## Instructions for reporting errors
We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:
Click the "Report Issue" ( ) button, located in the page header.
Tip: You can select the relevant text first, to include it in your report.
Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.
Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .