Non-evolutionary OE systems

From the OEE4 workshop chat, there was a bit of a discussion about whether there were examples of non-evolutionary systems exhibiting open-endedness, so I thought it might be useful to collect and discuss possible examples.

POET is the direct example from the workshop, since it doesn’t have to be driven in an evolutionary manner - you can use RL or even supervised learning to drive it if you make the agent and environment differentiable.

I’d also argue that Generative Adversarial Networks have a proto-open-ended characteristic in that if there’s something about their environment they have yet to learn to produce, the pressures between generator and discriminator will drive the generator to learn about it. They fail to be open-ended in that what they can learn is limited by what is in the data-set, but if you replace that dataset with a third agent (for example in an Artist-Forger-Curator system where one agent tries to make distinctive pictures, one tries to fake those pictures, and the curator tries to tell them apart) then that concern might be lifted, although this has other problems in that it produces variation rather than innovation.

The third category would be the various curiosity-based intrinsic motivation approaches, which basically have something along the lines of artificial boredom - you have some agent or network which tries to do things and if its successful the system as a whole moves away from those places of success. Some of these are density-based (so they try to spread out over some learned latent representation of the environment and find new things), others are skill-based.


Not sure I quite get the definition of the 3 categories, but certainly you indicate 3 interesting exemplars.

First category: maybe a good defitinion of this category is coevolution of problem set with problem solvers. POET does this explicitly; first time I remember seeing this explicitly was in an effort to evolve arithmetic computation: Evolving inductive generalization via genetic self-assembly .

Second category: what is the definition? Simply GAN and its generator discriminator instability as the mechanism for open-endedness? You are right about traditional GAN formulation being driven by data, but a population of GAN agents interacting with each other seems like a very natural context for open-endedness. Starting with a population of only 2 starts to look like a version of Takashi’s Can Mutual Imitation Generate Open-Ended Evolution? .

Third category: various => examples? Maybe simplest version of ‘artificial boredom’ (I like the term!) is wandering in a neutral landscape? Definition seems to need a space of possibilities (latent space is one example? skill-space??) and algorithm to explore the space.

I don’t think those are separate categories necessarily, just different examples.

In terms of the curiosity algorithms, here are a few examples of specific methods:

There is enough overlap in the various ways people implement curiosity that it’s probably time for a review article, but common themes are having a predictor/actor/etc and then trying to find your way to areas of the state space which cause it to have a high error. Another family of curiosity algorithms has some kind of (evolving) model of the state space, and tries to navigate to places it hasn’t been frequently (e.g. it tries to make the density of visits as close to uniform as possible).

This category is called ‘count-based exploration’, see e.g.

I don’t know if Go-Explore falls into that category or not, but it’s also a sort of curiosity algorithm: [1901.10995] Go-Explore: a New Approach for Hard-Exploration Problems

My instinct would be that Count-Based methods inherently have a problem going open-ended in environments with combinatorial structure. Wendelin Boehmer called this an ‘entropy trap’ at one point - count-based methods basically fill up the state space from ‘below’, in order of easiest to hardest to reach. So if you have a combinatorially large area of that space, the algorithm can slow down exponentially, even if eventually it would inevitably fill that space up given infinite time.

Adversarial methods seem like a reasonable way to escape that entropy trap to me, because they’re sort of aggressively trying to say that things are the same and so are trying to collapse those combinatorial sub-spaces down.

If we are just collecting examples, aren’t we missing some mentioned by Ken S in his talk? E.g. NEAT literature? He also touched on AI game design literature (Michael Cook “distinction between generative space and possibility space”, etc.).

That’s fair. How would you integrate NEAT and such into this picture? Or to put it another way, is it about pressure (the system is driven towards doing novel stuff) or capacity (enables an otherwise closed system to express an open-ended array of stuff)?

Have to think about / read about NEAT. re GAN: do you have a favorite implementation that would lend itself to a GAN imitation game?

Thank you Norman for highlighting this thread to me (and also of course for this whole site!). Of course I appreciate the discussion of this issue that I raised at the meeting!

It’s a nice coincidence that DeepMind just released its own take on non-evolutionary open-endedness a couple days ago: Generally capable agents emerge from open-ended play | DeepMind

So there’s another example.

In any case, it’s possible to argue whether any given approach (say GANs) is really open-ended because after all no approach today of any type is really open-ended in the strongest sense. That said, I think what’s interesting is to see a common theme and inspiration developing across areas. That is clearly happening even though some assumptions and criteria for progress might be different. But there are shared underlying themes, and it raises a question about whether we are really talking about different things or the same thing seen through different lenses. I think that’s pretty interesting to think about, and has implications for the cross-pollination of ideas that could be enriching to the overall hope for artificial open-endedness.

I’m not sure I have a reference implementation of an open-ended (not attached to data) GAN, though I’ve tried it a few times for different things so I could put that code somewhere…

For a basic GAN implementation, something like GitHub - arturml/pytorch-wgan-gp: A pytorch implementation of WGAN-GP seems to be a proper reference (slightly fancy tricks, but good ones to know). But maybe a tutorial code would be more useful? In which case something like this perhaps: DCGAN Tutorial — PyTorch Tutorials 1.9.0+cu102 documentation

I will try to get a simple artist-forger-discriminator reference into a state to work, but I’m on vacation for the next two weeks so it’ll have to wait till after then.

Interesting piece by DeepMind. But… they seem to hamstring themselves to prevent “strong open-endedness”, by defining a fixed universe of tasks:

We define a universe of tasks within an environment domain and demonstrate the ability to train agents that are generally capable across this vast space and beyond.

Of course, the space might be vast, but it can’t be as vast (or as interesting) as tasks that are dynamically generated by agent interaction. This is a nice aspect of POET, explicit co-development of problem with problem solvers.

A couple other thoughts:

  • Re. the idea of “really open-ended in the strongest sense”: would be nice to pin down what is meant by this, to the extent that we can know when we have achieved it.
  • Re. exemplars vs. categories: @NichG and I had a minor misunderstanding at the beginning of this thread, which might be useful to surface explicitly: Are we exploring a list of exemplars (of non-evolutionary open-endedness), or do we have enough knowledge about the exemplars to begin to categorize them?