The ability of natural systems to seemingly create an infinite succession of interesting things– interesting enough to capture our attention for a seemingly endless amount of time– remains elusive in digital, artificial worlds.
This particular post is one of two on the importance of “interestingness” in open-endedness. In particular, we explore the type of interestingness felt from a researcher’s perspective: the feeling that there is more to be learned by further study. How is it that, even when faced with something we have yet to study in detail, we can still judge whether it is worth studying further? Suppose we have a system whose expression to a human observer always passes this test. In this case, regardless of whether or not that system is innately open-ended in some formal way, interacting with the system over an extended period could feel like there are always new things to learn, similar to what we experience when we study nature.
So far, we’ve only been able to understand aspects of what seems “interesting enough” from the innate characteristics of artificial systems we build. We can code simulations of physical systems that never converge to a steady state. We can distinguish systems that “never stop” from systems that don’t repeat themselves. We can classify them into those that create independent samples from a combinatorial void and those that retain ongoing and increasingly complex interrelations between what is being newly-formed and what has come before. We can even formulate a decent theoretical grounding for these characteristics to explain why and how they emerge: self-similar solutions, traveling waves, heteroclinic orbits in chaotic dynamics, oscillatory or chaotic ecological dynamics, relative versus fixed fitnesses, minimal criteria, neutral spaces, and more.
Curiously, even as we develop more and more sophisticated simulations that display open-ended dynamics, these carefully constructed cases do not necessarily hold our attention nearly as well as things produced by the natural world. The variety of things generated by simple rules that break some of these considerations of theoretical open-endedness are, to a greater or lesser extent, provably “closed” (at least when it comes to their autonomous behavior).
Let’s set aside the question of whether or not we can build a system capable of generating open-endedness in some formal way, just for a bit. How might we understand our own ability to be endlessly fascinated by something? That ability may in fact be independent of whether a system is actually open-ended according to any particular metric.
For example, we can perceive cases in which there are yet things to learn, but of the same class as things we already know. Similarly, there is a difference between the perception that one has yet to finish studying a static system versus the perception that a system is actively creating an arbitrary number of new things to learn over time. It is similar to the saliency we experience when something seems “promising” or piques our curiosity.
The concept of “active inference,” situated in the general framework of statistical inference, provides a valuable handle for discussing the sense that “one could learn something” more concretely. While there are effects outside of “formally optimal inference” that shape the actual human experience of curiosity, even within a simple formal framework, we can find some examples of situations that would produce this sense of unending “interestingness.”
It may be easier to build systems that “trick” us into thinking we could learn more by studying them rather than to build systems that actually continuously create new things to study and learn. In this post, we’ll zoom in on that particular phenomenon. We’ll discuss different illusions and other ways that trick us, as observers, into thinking that a system is doing more than it does. Following that, we will (in an admittedly more hand-waving sort of way) broaden the idea by considering infinite-seeming perceptual illusions such as Sheppard tones and Risset rhythms, as well as the general existence of adversarial examples inmachine learning systems.
Statistical inference centers around determining the probability that some unseen variable takes on a particular value, given the values of observable variables and a model of the relationship between them. The model and observations are generally assumed to be fixed or given.
Active inference adds a twist. Suppose one could pick which experiments to perform, including how observations are made about a system of interacting variables. In that case, which experiment should you do to best pin down the unknown variable’s value? Because the state of one’s knowledge (and, in the most general case, the model of variable relationships) changes due to each observation, the value of subsequent observations also changes. Active inference is the process of finding a policy (of what actions to take, which experiments to perform) which answers this question of how to learn about the unknown variables as quickly as possible. One can also attach other goals, such as trying to maximize some reward via actions that have uncertain consequences. In this case, active inference is used to find the optimal trade-off between exploration and exploitation.
A simple example of this is the Bandit problem, named so because of the nickname of slot machines as being ’one-armed bandits’. Imagine multiple slot machines, each with a different unknown rate of payout. Given a specific number of pulls to make and a set of prior beliefs over the distribution of possible payout rates, the optimal strategy involves spending a portion of those pulls to learn which machine has the best payout, then using the rest of the pulls on that particular machine. Each play generates an observation specific to that machine, reducing the uncertainty about the machine’s actual payout rate.
In this case, a pull on a bad machine still causes you to gain value in the future, as your subsequent pulls will be more likely to be on a machine with a better payout. However unlike the actual payouts, there are diminishing returns: the more one knows about a machine already, the less valuable – with regards to information – subsequent plays of the same machine are. The optimal policy generated by this active inference process is to be curious. If it seems likely that old (known) information will be repeated more often than not, the policy will move on to trying something else, unless it is exploiting the machine and raking in sweet, sweet casino cash.
Finding optimal policies is useful in experiments regarding systems with lots of parameters. One can ask, “what is my expected information gain?” in each experiment and greedily optimize towards it. This happens by simulating the outcomes one might expect for some current beliefs, seeing how many times a new observation would shift those beliefs. The resulting policy is short-hand for the actual optimal policy, which might require a level of knowledge about details of the experimental system that can’t be comfortably parameterized or assigned good priors.
The connection we’d like to make is this: if we carefully construct some system to be open-ended in such a way that we can guarantee its open-endedness from a theoretical and engineering basis, we might already know too much about its future behavior for it to be interesting (in the sense that something new can be learned). The process of comprehensibly and intentionally constructing open-ended artificial systems can reduce the anticipated information we gain from observing them. By contrast, if we construct a system to ask a question where the outcome seems paradoxical or at odds with the forces within the system, we would guarantee to ourselves from the beginning that no matter what happens, we expect to be surprised.
Could we build systems like that, which indefinitely provide that level of paradoxical surprise? In stationary systems, statistical inference– including active inference–is convergent. While an individual observation can appear misleading, on average observations in a stationary system will cause the set of underlying beliefs about the system’s dynamics to converge to a more and more accurate set of predictions. However, suppose the system is constantly changing (specifically if an entropy source drives slowly-varying degrees of freedom controlling the system dynamics). In that case, those changes allow new information to seep in. This is transferred to an observer who continuously picks up on these system changes. It’s not that there is an infinite amount of meaningful and relevant things to learn about; rather, old things are becoming irrelevant to make way for new things to be picked up.
Another way this impression can emerge is if the hypothesis space is structured such that the information to distinguish different hypotheses would be distributed over an infinite amount of time. For infinitely-large hypothesis spaces, this can create the illusion that there is always more to learn, even if the actual underlying system is stationary, merely by including non-stationary hypotheses in the space of beliefs one is considering.
Let’s introduce a toy system that demonstrates this property. Imagine some unknown random process, like a person constantly flipping a coin with an unknown bias. The coin lands on the table as either “heads” or “tails” (0 or 1) and an observer takes note of these outcomes. For simplicity, let’s say the distribution ends up being 50% heads and 50% tails after many flips. If we only consider stationary hypotheses about the bias (that it’s 10% heads, 20% heads, etc), we will converge on the true 50/50 distribution of heads and tails in the limit of infinite observations.
But what if we consider the possibility that these flips are not actually independent, but that they represent some repeating sequence whose length we don’t know. So we consider (as well as the independent hypotheses) the possibility that after some N number of flip outcomes, we see the result of the first flip, the second flip, etc all over again. We have a hypothesis for each possible N up to some maximum M, with beliefs %%p(N)%%.
Because of the nature of these hypotheses, we can only disprove the hypothesis that the sequence loops after two flips on the third or higher flip, that the loop is three long on the fourth or higher flip, and so on. In general, for a hypothesis that the length of the loop is k, we can only disprove it with the %%k + 1th%% or higher flips. Now lets ask, if the true process is actually stationary and not periodic, how much information do we gain about our beliefs in the space of hypotheses on the kth flip, assuming we start with a uniform prior %%p(N) = 1/(M+1)%%?
The first flip does not provide any immediate evidence towards any of our hypotheses, but it does give us one bit of synergistic information we will use a lot going forward. The next flip, in combination with this synergistic information, gives us a 50% chance of disproving %%N = 1%% shifting the probability in that bin to all of the other bins, and a 50% chance of teaching us nothing. The subsequent flip might again disprove %%N = 1%% if it hasn’t been already, and has a 50% chance if disproving %%N = 2%%, and so on.
In general, if we have disproven all of the hypotheses up to k so far, our residual probability will look like %%pk(N > k) = 1 / (M+1−k)%% (and the probability that some hypothesis survives incorrectly decays exponentially, so this isn’t a bad approximation at least in the case where the true signal is not periodic). Under this approximation, the information gain we expect from the %%k +1 th%% flip is (1/2) the KL divergence between %%pk−1%% and %%pk%%. For %%k ≤ M%% This is:
%%I(k) = log (M + 2 − k) − log (M + 1 − k)%%
As %%k → M%% this function monotonically grows, reaching a maximum value of log(2). In this approximation, above M we gain no further information – we have disproven all of the periodic hypotheses. There is an additional interesting effect beyond just the increase in information gain: as we get closer to %%k = M%%, we are more likely to predict that the next flip corresponds to the first flip. This is because for the next flip, all hypotheses %%N > k%% and %%N = ∞%% predict a random result, but one hypothesis predicts whatever the first flip is. As we eliminate more and more hypotheses, while the probability given to %%N = ∞%% increases, it does so at the same rate as the %%N = k%% hypothesis. So as we reach %%k = M%%, we believe the next flip will be equal to the first flip with a probability of 75%.
In this toy example, the property of being endlessly and increasingly informative to continue to observe here is not in the end a property of the system itself, but a property of the mindset of the agent watching the system. Because of our choice of hypotheses to consider, we have created for ourselves a situation in which repeatedly observing the system actually makes us not only feel like the next observation is increasingly important (forever, if we take %%M → ∞%%). Somewhat disturbingly, our predictions additionally become more and more biased away from the true behavior as we keep observing it. This comes about not because our model is mis-specified or because we lack the true hypothesis, but just because we’ve agreed to consider these other possibilities. So it may be that an element to subjective open-endedness has to do with the angle of approach of the observer to the system – what are they conditioned to consider and what things are they already considering as possible things to be learned?
Above, we considered an example that turns out to be deceptive even to a certain formal inference process. But we could widen our net to include even more perceptual processes. Human perception is subject to a variety of illusions. One possible reason is that what we experience during perception is not reality as it is. Instead, it is likely the consequence of a subconscious process of inference. Some patterns may create the experience of motion even while remaining stationary, others may create the sensation of spatial objects via negative space or repetition, and others play with an ambiguous resolution of 2D or perspective-limited views with different potential 3D geometries. In the same way that we might perceive things in low-level sensory modalities as something different, the same might be true of our sense of meaningfulness of the potential to learn things. In some sense, this must be the case. Before we experiment or make any observations, we can, at best, guess what will happen. In that case, it may be possible to create systems that act as “curiosity illusions,” endlessly suggesting they have something new to show us while never actually
In particular, inference engines built upon learning are known to be vulnerable to adversarial examples: stimuli that look different than the prior distribution of inputs the model learned from and which can utilize the model’s untuned sensitivities in those unseen directions to influence its inferences strongly. There are hints that this is a fundamental and inescapable property– that there is a direct trade-off beyond a certain level between accuracy and robustness against these extraneous directions. So what might adversarial examples look like for processes used to determine saliency and novelty? How does one construct an illusion of the “infinitely interesting?”
In auditory perception, there are ways to construct illusions of sounds that constantly increase pitch (Sheppard tones) or rhythms that constantly go faster or slower (Risset rhythms). For pitch, these work by overlaying rising tones such that each tone becomes louder as it approaches the mean pitch, above which it decreases in volume and gradually fades out. So there are always elements of lower tones waiting to rise out of the inaudible limit while higher raising tones escape audibility. When one listens to such a pattern, the pitch is perceived to be constantly increasing. But this is only because higher tones sneakily fade into nothingness undetected by the listener, giving the impression that the overall average pitch is constantly increasing, even while the listener loses track of exactly what that pitch might be.
In a similar sense, a system that changes the level of understanding (instead of the pitch) can be detected by an observer. But the fact that the absolute level of understanding cannot be grounded might lead to a type of adversarial open-endedness.
The application of adversarial open-endedness might be the most obvious in video games. How long can a piece of software keep players engaged, interested, and wanting to keep coming back for more with minimal changes from game developers? At different stages of a game, a player may have the sense that there is yet stuff to uncover or do, regardless of how true that is. In open-world games, it is still common to discover new things on a second or third play-through, even when previous play-throughs felt satisfyingly complete. This suggests a contour of experience in which the actual potential of the space decreases more slowly than the player’s perception of that potential.
In visual novel games, one way to make the game seem less linear is to incorporate multiple characters who can be spoken to in different order in a section of the game. When side-events have triggers that are not communicated to the player in advance, the player can experience new events that suddenly appear even when the player does not feel like they triggered them. This can create the impression that more events can be unlocked given the right conditions or combinations of factors and that the player simply hasn’t discovered their triggers yet.
A handful of hidden events can make it feel as though there is a much larger space of possibilities. As a result, the player’s perception of the game’s possibility space ends up being larger than what it actually is, sustained by a few rare signals hinting that other rare signals may still exist. Combined with some necessary action on the player’s part to check for new events, the result inflates the apparent value of re-attempting even seemingly “failed” actions. As a result, this inflates the time that the player is willing to spend with the game.
With curiosity and open-endedness as learned perceptual heuristics, one could construct experiences that are front-loaded to communicate the suggestion that other (inert) options exist to expand the space of possibilities. For example, let’s imagine a game that takes place in a city, where building doors lead to small side areas. Early on, before the player gains the ability to open locked doors, they encounter a mix of doors they can and can’t open, as well as hand-crafted unique spaces. Of those spaces, say 25% have something interesting to discover and are placed behind those early doors. When the player gains the ability to pick locks, say 50% of the locked doors in previous areas and the current area have something interesting to discover. Then, for the rest of the game, say 90% of the doors lead to procedurally-generated spaces with generic but mildly valuable things. At this point in the game, only the remaining 10% of doors have hand-crafted spaces along with some external cue that maybe “this door” is interesting. That might lead the player to think, “Even though the actual fraction of interesting spaces has gone down, I just have to search more carefully for the good stuff.”
In a situation where the player’s journey through a game is less controlled, maybe a similar effect can happen by clustering interesting things. For example, a space exploration game may contain 400 billion star systems. Obviously, a very tiny fraction of them have any kind of hand-crafted content. But certain desirable discoveries (black holes, neutron stars) are arranged in clumps and streaks. So when a player discovers one of these areas, they get the feeling that there may be more cool stuff nearby. This motivates a change in play from longdistance directed travel to local exploration. This shift is not always rewarded but is rewarded frequently enough to make it seem as though paying attention to relationships between sequentially visited systems might be worth-while.
If we treat the scientific process as another one of these in-game experiences, we might find our interest drawn to systems that pay out with a few surprising transitions “early” in their investigation. They may also have a (very large) number of distinct opportunities that “look like” the sorts of things that paid out early on. For example, suppose we’re studying a system with a combinatorial space, and within the first few years of exploring it, we discover several distinct phases, behaviors, etc. In that case, we might be primed to believe that the rest of the combinatorial space is equally dense– whether or not there are actually
more things to find.
While we may not particularly want to build systems that have “fake openendedness,” it is still interesting to consider whether we might naturally (or at least accidentally) tend to create these kinds of illusions for ourselves in the process of doing science. The coin flip example shows that considering certain classes of hypotheses can lead us to believe that each subsequent confirmation of the same thing is telling us more and more. Areas of science which involve extrapolation (for example, drawing conclusions about scaling behaviors) might be vulnerable to this. It’s not difficult to generate hypotheses that would agree in the viewed range but vary wildly from each other outside of it– even systematically by constructing effects controlled by small parameters that become large in some limit.
Beyond the adversarial picture, it could also be interesting to consider whether the priors we have about saliency could be a practical structural guide. For example, what underlies the mathematical intuition about which lines of thought might pay out or not? Perhaps we could build proxies for these forms of curious intuition using machine learning approaches, and then use those proxies to explore what sorts of things capture our interest.
(I’m not sure this actually belongs in this particular post, but I had the idea and wanted to note it down somewhere)
Using this framework, lets think about how games are perceived. At different stages of a game, a player may have the sense that there is yet stuff to uncover or do – that perception may in turn be accurate or inaccurate. In open-world games such as Skyrim or Fallout, its not uncommon to still discover new things on a second or third playthrough, even when previous playthroughs felt satisfyingly complete, suggesting a contour of experience in which the actual potential of the space decreases more slowly than the player’s perception of that potential.
In visual novels or visual novel hybrid games, one design pattern is to have sections of the game in which there might be for example multiple characters who can be spoken to in different order (or even at different points along the main plotline), to make the game seem less linear than it actually is. When those side-events have triggers that are not communicated in advance to the player, the player can experience new events just appearing even when they do not feel they did anything in particular to make those events appear. That can create the impression that there could be more such events to be unlocked given the right conditions or combinations of factors, that the player simply hasn’t discovered yet. A handful of such hidden events can make it feel as though there is a much larger space of possibilities – the player’s perception of the potential of the game’s space ends up being larger than the actual potential, sustained by a few rare signals hinting that it is likely other rare signals may exist. When this is combined with some sort of necessary action on the player’s part to check for new events, the result is to inflate the apparent value of re-attempting even seemingly ’failed’ actions and as a result inflating the time that the player is willing to spend with the game.
From the perspective of curiosity and open-endedness being learned perceptual heuristics, one could think to construct experiences which are front-loaded to communicate the suggestion that other (inert) options existing for expanding the space. For example, let’s imagine a game taking place in a city, where doors of buildings lead to small side-areas. Early on, before the character gains the ability to open locked doors, they encounter a mix of doors they can explore and doors they can’t, and hand-crafted unique spaces of which say 25% have something interesting to discover are placed behind those early doors. When the player then gets the ability to pick locks, 50% of the locked doors in previous areas and the current area have something interesting to discover. Then, for the rest of the game, 90% of doors lead to procedurally generated spaces with maybe some generic but mildly useful things, and only the remaining 10% have hand-crafted spaces along with some kind of external cue that maybe ’this door’ is interesting. That might lead the player to feel as though even though the actual fraction of interesting spaces they encounter has gone down, they just have to search more carefully.
In something where the player’s course through the game is less controlled, maybe a similar effect can arise from the clustering of interesting things. For example, Elite Dangerous contains 400 billion star systems, obviously a very tiny of fraction of which have any kind of hand-crafted content. But certain desirable discoveries (black holes, neutron stars) are arranged in clumps and streaks. So when a player discovers once such site, there is the feeling that there may (or may not) be others nearby, motivating a change in play focus from directed travel to local exploration. That change in focus is not always rewarded, but is rewarded frequently enough to make it seem as though paying attention to relationships between sequentially visited systems might be worth-while.
Treating scientific process as just another one of these experiences, we might find our interest drawn to systems which pay out with a few surprising transitions ’early’ in their investigation, and which also have a (very large) number of distinct opportunities that ’look like’ the sorts of things that paid out early on. If for example we’re studying a system with a combinatorial space and within the first few years of exploring it we discover several distinct phases, behaviors, etc, then we might be primed to believe that the rest of the combinatorial space is equally dense – whether or not there are things to find.
While we may not particularly want to make ’fake open-endedness’ in these ways, it’s interesting to consider whether we might naturally (or at least accidentally) tend to create this kind of illusion for ourselves in the process of doing science. The coin flip example shows that even considering certain classes of hypothesis can lead us to the belief that each subsequent confirmation of the same thing is actually telling us more and more. Areas of science which involve extrapolation (for example in drawing conclusions about scaling behaviors) might be vulnerable to this, as it’s not difficult to generate hypotheses which would agree in the viewed range but vary wildly from each-other outside of it - even systematically by for example constructing effects controlled by small parameters that become large in some limit.
Beyond the adversarial picture, it would also be interesting to consider whether the priors we have about saliency could be a useful structural guide. What underlies mathematical intuition, for example, about which lines of thought might pay out or not? Perhaps we could build proxies for these forms of curious intuition using machine learning approaches, and then use those proxies to explore what sorts of things capture our interest.