Autoverse: an Evolvable Game Language for Learning Robust Embodied Agents

## Abstract

Abstract We introduce Autoverse , an evolvable, domain-specific language for single-player 2D grid-based games, and demonstrate its use as a scalable training ground for Open-Ended Learning (OEL) algorithms. Autoverse uses cellular-automaton-like rewrite rules to describe game mechanics, allowing it to express various game environments (e.g. mazes, dungeons, sokoban puzzles) that are popular testbeds for Reinforcement Learning (RL) agents. Each rewrite rule can be expressed as a series of simple convolutions, allowing for environments to be parallelized on the GPU, thereby drastically accelerating RL training. Using Autoverse , we propose jump-starting open-ended learning by imitation learning from search. In such an approach, we first evolve Autoverse environments (their rules and initial map topology) to maximize the number of iterations required by greedy tree search to discover a new best solution, producing a curriculum of increasingly complex environments and playtraces. We then distill these expert playtraces into a neural-network-based policy using imitation learning. Finally, we use the learned policy as a starting point for open-ended RL, where new training environments are continually evolved to maximize the RL player agent’s value function error (a proxy for its regret, or the learnability of generated environments), finding that this approach improves the performance and generality of resultant player agents.

## 1 Introduction

The idea of open-ended learning in virtual environments is to train agents that gradually get more capable and behaviorally complex. This idea comes in many shapes, but what unites them all is that there is no fixed objective or set of objectives; rather, the objectives depend in some way on the agent itself and its interaction with the environment and other agents. This is true for early work on competitive coevolution in evolutionary robotics, work on artificial life simulations, and also for more recent work on open-ended learning.

However, we have yet to see any literally open-ended learning take place in these environments. There have been interesting results, but learning generally stops at a rather low capability ceiling. We hypothesize that this is at least partly because the poverty of the environments, and the associated limitations in the variability of the environments. It has been observed that the complexity of the behavior of a living being, such an ant or a human, is at least partly a function of the complexity and variability of the environment it is situated in. And it stands to reason that even a very capable and motivated agent would not learn much in an empty white room with no toys, nor in a barren gridworld.

A secondary hypothesis of ours is that open-ended learning is hampered by the complexity of “cold-starting” learning policies from rewards in generated environments, as these may have rare rewards that can only be accessed through uncommon action sequences for which the agents have no priors. This hypothesis suggests that at least part of the reason for the success of reinforcement learning in more well-known domains is that designers, wittingly or unwittingly, build in priors and other domain-specific adaptations to their agents.

In this paper we present Autoverse, a new environment for open-ended learning. Autoverse stands out for allowing more complex environment dynamics and much more environmental diversity than other open-ended learning environments. Not only the layout, but almost every aspect of dynamics and interaction can be modified during the open-ended learning process. Environment dynamics are encoded as cellular automata, pairing conceptual simplicity with rich expressivity. The whole system is implemented using JAX, meaning that it run parallelized on GPUs, and at least an order of magnitude speedup.

We also conduct a set of experiments in open-ended learning with Autoverse. In particular, we investigate the value of “warm-starting" reinforcement learning by imitating trajectories taken by best-first tree search agents. This exploits the fact that Autoverse can be used as its own forward model, making rapid tree search practical.

Figure: (a) $t=1$
Refer to caption: x1.png

## 2 Methods

Figure: (a) A rule is defined as a sequence of local tile patterns, where the presence of an input pattern causes an output pattern to appear at the following timestep, and the application of a positive or negative reward. A rule set is implemented as a sequence of convolutions.

Figure: (a) Game environments are selected for maximum fitness—where fitness is defined as the steps-to-best-solution from greedy tree search—and mutated to produce offspring. At each generation, tree search is capped by a maximum number of steps, which is increased when fitness comes within a threshold of this maximum.

Figure: Figure 5: The trajectories and environments generated by autoverseare incorporated in an Open-Ended Reinforcement Learning loop.

### 2.1 Autoverse: a batched game engine with evolvable components

backgroundcolor=cyan]Sam: This section was condensed by Eugene, in whom I trust, but if we want to flesh it out a bit, there are more verbose versions in the other docs in this project.

In this section, we develop a framework for batched simulation of grid-world games, allowing game designers to rapidly generate robust agents and complex environments for a broad family of games. We propose a game engine—in the form of a domain specific language (DSL)—that is both general enough to encode a diversity of interesting and complex individual games, while also allowing for batched simulation so as to make rapid agent training accessible on a single GPU. Whereas prior studies have largely fixed the semantics of the generated environments—for example constraining them to always take place in a maze, on 2D navigable terrain (Brockman et al., ), or a 2.5D space with moveable objects and rigid-body physics (i.e. XLand Team et al. ())—we are interested in generating environments that may carry a broader diversity of possible agent-environment interactions to further push the generality of OEL-trained controllers. In this section we propose a method to easily batch a surprisingly large category of games.

We focus on games whose dynamics involve discrete elements interacting on a grid. At the core of the DSL are rewrite rules, which specify transformations applied to local patterns of tiles. Despite their seeming simplicity, rewrite rules have been leveraged in prior game description languages, and in particular, in the popular puzzle game engine PuzzleScript (Lavelle, ), to generate games ranging from rogue-likes (in which players navigate dungeons, collect treasure and fight enemies), Super Mario Bros-type side-scrolling platformers, and Sokoban-like box-pushing puzzle games and simulacra of circuit-building.

For example, in a roguelike game where a player is tasked with exploring a dungeon littered with obstacles, enemies, and treasure, a rewrite rule might describe the event of a player’s stepping into lava by indicating that, if a player tile and a lava tile are overlapping, at the next timestep, the player tile should disappear while the lava remains. A similar logic can be used to allow for basic player movement: we allow the player agent to place invisible ‘force’ tiles at any cell adjacent to the current player position; we then use a rewrite rule to ensure that whenever a player tile is adjacent to a force tile overlapping with a ‘floor’ tile (i.e. a grid cell unobstructed by obstacles preventing player movement), at the next timestep, the player should move onto this adjacent floor tile, consuming the force tile in the process.

We propose a novel approach to rewrite rules by taking advantage of the fact that they can be implemented with convolutions, allowing our environment to be both differentiable and easily hardware accelerated.
A rewrite rule says that when an $n\times m$ patch $\*I$ of tiles is present on the map at timestep $t$, it should be replaced by an $n\times m$ patch $\*O$ at timestep $t+1$.
We construct a convolutional kernel $\*K_{I}$, with dimensions $c\times c\times n\times m$ (where $c$ is the number of tile types) for recognizing the input pattern $\*I$. We set $\*K_{I}[:,\*o,:,:]:=\*I$, with 0 0s everywhere else.
We define $I$ to be the sum of the elements of the matrix $\*I$ (i.e. $I=\*1^{T}\cdot\*I\cdot\*1).$
Then, the transition of the entire board $\*D$ can be written as

$$ $\displaystyle\*D_{t+1}$ $\displaystyle=\text{ReLU}\left(\text{conv}_{\*K_{I}}\left(\*D_{t}\right)-I+1\right)$ $$

To generalize this implementation to rewrite rules with output patterns in which more than just the center cell is changed, we first apply a convolution (similar to that above) to generate binary activations indicating whether given input patterns are present, then apply a transposed convolution to generate the change to the board required by corresponding output patterns.
Focusing on a single rewrite rule with input and output patterns $\*I$ and $\*O$, and a patch of the board $\*B$, all with patch sizes $c\times n\times m$ (and one-hot encoded over the number of tile types), our network applies the following operation,

$$ $\displaystyle\*C_{t+1}$ $\displaystyle=\begin{cases}\*O&\text{if}\quad\lVert\*I\odot\*C_{t}\rVert_{L_{0 }}=I\\ \*C_{t}&\text{otherwise}\end{cases}$ $$

This operation can be implemented via a convolutional kernel $\*K_{I}$ of size $c\times 1\times n\times n$
We construct a transposed convolutional kernel $\*K_{O}$, which is binary with size $1\times c\times n\times m$, setting its elements equal to $O-I$ (adding to the result an input dimension at the front).

$$ $\displaystyle\*B_{t}$ $\displaystyle=\text{ReLU}\left(\text{conv}_{\*K_{I}}\left(\*D_{t}\right)-I+1\right)$ $\displaystyle\*D_{t+1}$ $\displaystyle=\text{conv}^{T}_{\*K_{O}}\left(\*B_{t}\right)+\*D_{t}$ $$

#### 2.1.1 Possible extensions to the Autoverse language

backgroundcolor=cyan]Sam: ZZ says: we could probably lose this as it feels rather out of the blue. Maybe just contextualize/future work it, as a way in which we could increase expressivity
In addition to binary patterns, we can generate networks for propagating scalar “flows”. To simulate a “source” of water using the binary rules above, we might specify that water cells can replicate downward when unobstructed, and otherwise sideways (when unobstructed to the side). When water flows to an adjacent tile, we update an additional channel, denoting the “level” of the water at that point, for example, decrementing once with each horizontal tile transition, such that water is “absorbed” by land tiles after a certain time.
Using similar auxiliary, integer-valued channels, we can effectively “count” the distance some substance has travelled from a source, and thereby can move beyond rewrite rules based on local patterns to instantiate more complex algorithms like breadth/depth-first search-based pathfinding (again as a batched, differentiable NCA, as demonstrated in our prior work (Earle et al., )).
Though in this work, we limit the games to only involve binary activations, we note that certain games can exhibit phenomena that appear “flow-like”, as an emergent property of interaction between evolved rules.
backgroundcolor=cyan]Sam: gen 25 elite 1 from evo run 1 is a nice example of this. Should perhaps include it to illustrate

Finally, we note that it is also possible to adapt the rewrite-rules, encoded as convolutions, to support applying each rule only once or a fixed number of times, and/or in a random order, by selecting tiles to rewrite by taking the maximum over an additional channel of ordered or randomly-generated index values.
For maximum parallelism, we opt to apply rules in parallel, but can use masking to guarantee that certain rules inhibit others.

### 2.2 Warm-starting open-ended learning from search

#### 2.2.1 Evolving game environments to maximize search-based complexity

The first component of our co-learning algorithm involves generating a large and diverse initial set of environment mechanics and layouts prior to agent training. We begin with a basic maze environment, in which the player moves as described above (by applying force tiles to adjacent cells), is blocked from traversing ‘wall’, and receives a reward when it consumes a ‘food’ tile by moving onto the cell it occupies. In addition to the 3 rules and 4 tile-types necessary for instantiating these dynamics, we add a handful of “no-op” tiles and rewrite rules, which start off empty and thereby leave the environment dynamics unchanged. During our evolutionary algorithm, these additional rules are randomly mutated by changing the value of tiles present in the rewrite rule. The tiles changed may be in the input and/or output pattern, and at various spatial positions relative to one another. For example, an empty rule might eventually be mutated such that it contains adjacent force and wall tiles in the input pattern, and a food tile in the output, resulting in a game mechanic wherein whenever the player approaches a wall (by placing force next to it), the wall tile is transformed into a food tile. Such a rule would incentivize a play strategy in which the player races to “consume” as many wall tiles as possible over the course of an episode. In practice, mutated rules may involve new tiles, such that these new tiles appear to exhibit certain behavior and relationships relative to the initial set of tiles, and rules may interact so as to form increasingly complex dynamics.

In addition the the modification of tiles in rewrite rules, the reward associated with the application of a given rewrite rule may also be modified. In the base, maze-like game, a separate rewrite rule describes the action of a player consuming a food tile (by applying force to the goal tile, moving onto it, and causing the food to disappear). Whenever this rule is applied, it results in a reward of 1 for the player agent. Similarly, mutable rules may be assigned positive negative rewards. From the standpoint of getting an early sense of the player’s awareness of and ability to adapt to new rules, this is a useful feature because it allows for two copies of an environment with identical dynamics to have inverted goals. For example, in one game, red tiles may provide reward, and in another, they may provide negative reward, ensuring that the player cannot ignore the specifics of mutated rules and apply the same strategy to both environments. It is also worth noting that when mutating rewrite rules, we allow for rules to emerge which “kill” the player and end the game (i.e. with one player tile in the input pattern and none in the output), which similarly raises the stakes and decreases the likelihood that a rule-agnostic strategy can be successfully applied to all environments.

Finally, we also mutate the initial level layout, a multi-hot array of tiles, by randomly flipping bits in the array. It is important to jointly evolve the initial level layouts as some initial levels, when paired with certain rulesets, may result in unsolvable environments or environments with uninteresting dynamics (e.g. where certain rewrite rules are never applied because some particular tile type necessary for the rule’s application is initially absent from the level). Conversely, the same rule-set can result in multiple diverse tasks when paired with different initial level layouts. As a sanity check, we can also disable ruleset-mutation and evolve the initial level layout of our base maze-like environment. This results in mazes requiring increasingly many steps to traverse the optimal path to a food tile.

A simple mu + lambda evolution strategy is used to evolve environments using the above-mentioned mutation operators. As a fitness metric, we compute a proxy for the complexity or difficulty of the environment using search. In particular, we use best-first search to explore possible sequences of actions that can be taken by a player agent, prioritizing those trajectories that lead to higher reward. The fitness of an environment is equal to the number of states visited by search prior to it finding the highest-reward solution. A “node” in the search tree corresponds to a game state, i.e. the current player reward, the position and orientation of the player agent, and the multihot array corresponding to the state of the level at a given timestep; an edge in the search tree is a player action (rotating left or right or moving forward). When a game state is encountered that is equivalent to some state seen earlier in search, the shallower node – closer to the root of the tree and thereby occurring after fewer player actions – is kept, and the deeper node is pruned from the search tree. If two states are equivalent except for their reward, then the state with higher reward is kept. The budget of breadth-first search is limited, and this limit is increased whenever there appears in the population an environment whose best solution required a number of search iterations approaching this limit to some degree.

#### 2.2.2 Imitation learning: distilling search-based solutions

Throughout this process of environment evolution, we store trajectories corresponding to the solutions of all environments encountered. If the same environment (i.e. a ruleset and initial level layout) appears twice, we keep the trajectory that led to higher reward. (This situation may arise when a clone of an environment is re-evaluated at a later stage in evolution, with a higher cap on the amount of search afforded to our fitness evaluation.)

We perform behavior cloning on this archive of trajectories, in effect distilling the set of solutions discovered by search into a neural network. Behavior cloning is a simplistic form of imitation learning, wherein the model is given (state, action) pairs and is trained to predict the corresponding action for each state. Observations consist of a local patch of the surrounding tiles, centered at the player’s current position, in addition to a binary representation of the evolved rules of the current environment (so that the agent may adapt its strategy to suit the given mechanics).

### 2.3 Open-ended reinforcement learning in evolving environments

Once the behavior cloning algorithm has converged, we continue training the agent with reinforcement learning, randomly sampling one of the unique evolved environments contained in the set of trajectories above, and using Proximal Policy Optimization (PPO) (Schulman et al., ) to update the agent’s parameters. Our PPO Jax implementation is based on PureJaxRL Lu et al. () which is in turn adapted from CleanRL Huang et al. (), which allows our entire training loop to be just-in-time compiled to run on the GPU. Following work in Unsupervised Environment Design (UED) (Jiang et al., ; Parker-Holder et al., ), we continue to evolve environments in order to generate an adaptive curriculum for our RL player agent.

Fixing some interval $k_{evo}$ as a hyperparameter, after every $k_{evo}$ updates in our RL loop, we evolve Autoverse environments—both the binary array corresponding to the initial map layout, and the convolutional kernels corresponding to the input-output patterns of the set of rewrite rules. To evaluate the mutated environments, we freeze the weights of the RL-trained player and have it play through 1 or more episodes in the environment. Following Jiang et al. (), we compute the mean absolute value function error of the agent over the course of an episode, and use this as the candidate environment’s fitness. The value function error is intended as a proxy measure of regret—that is, the difference in return (i.e. discounted reward) accumulated by the learned player over the course of an episode, and that of a hypothetical optimal player.
Dennis et al. () show that, when the adversarial loop between the environment-generator agent (in our case an evolutionary algorithm) and player agent is seen as a multi-agent game, wherein the generator’s objective to increase, and the player’s objective to decrease, such a measure of regret, then this game converges to a Nash equilibrium, implying that the generator has discovered maximally complex and challenging environments with respect to the agent, and the agent has discovered a maximally capable policy with respect to the environments produced by the generator (given some simplifying assumptions).
Intuitively, we can think of the value function error as indicating the extent to which the learned agent is “surprised” by the outcome of its episode (i.e. having either over- or under-estimated its performance during play).

## 3 Results

Table: Table 1: In agents trained with behavior cloning to imitate the solutions found from greedy search on evolved environments, training and testing performance is higher given larger observations of the surrounding board state. Agents that fully observe the board perform best.

Table: Table 2: In agents trained with imitation learning, observing an environments’ rules leads to higher performance at train and test time.

Tables 1 and 2 show the importance of observations on agent performance when imitation learning on trajectories generated from greedy tree search on evolved environments. Table 1 shows that generally, larger observations of the map allow for increased performance both during training, and on test environments (environments also generated by the evolutionary process, but held out for testing). The best performance comes from agents that are able to fully observe the map (where the observation is centered at the agent’s current position, and 0 0-padding is added to the map as necessary).

Table 2 shows that agents that are allowed to observe each environment’s rule-set perform better than agents for whom the rule-set is replaced by 0 0-padding. This shows that the mechanics of the generated environments are sufficiently distinct, such that agents cannot perform effectively without observing the rule-sets.

We show some preliminary qualitative results of the search-based evolutionary process in Figure 2.
We observe a variety of distinct environment dynamics in evolved environments.
The majority of environments exhibit highly unstable dynamics, in which the majority of cells on the map change state from one timestep to the next, as exhibited in 2(n). The prevalence of such environments may partially be explained by the fact that, in an environment where almost all states are different from one another, a search-based agent is less likely to encounter the same state twice, thus forcing it to search longer for optimal states. This is at least true toward the beginning of evolution: all else being equal, if we compare an environment in which the agent’s actions have no effect (i.e. there are no rules where the agent can construct the input pattern by placing force tiles) and which is also stable throughout the episode; with an environment in which the agent’s actions have no effect, but the map state is changing drastically from one timestep to another, the latter environment will force the agent to construct a larger search tree with more distinct nodes. Given that these chaotic environments remain prevalent later in evolution, however, requires further explanation. It must be the case that these environments are also highly reactive to the actions of the player agent, i.e. that by placing a force tile, the player can put into motion a chain of events (rule-applications) causing a sequence of novel states requiring further search to explore.

One difficulty with the kinds of chaotic dynamics that appear so frequently among evolved environments is the difficulty of interpreting a player-agent’s strategy. Further analysis will qualitatively assess the differences between high/medium/low reward trajectories in such environments (by recording some of the candidate action trajectories that were discovered early in the search process).

Another distinct type of environment which we observe in our experiments is exemplified by the evolved environment in 2(u). In this environment, there is some activity and stat-changes early on during the episode, after which point the map then becomes entirely stable, with the agent taking no further actions to affect outcomes. Presumably, all of the consequential decisions taken by the player agent occur early on during the episode in this environment. It is surprising, then, that such an environment persists later on in evolution, since one can easily imagine simply extending the complexity of the early-episode phase to later in the episode, thereby increasing potential search complexity. Indeed, it may be that as evolution continues, and the cap on search depth is gradually increased, such exclusively “early-game” environments will die out. On the other hand, it may be the case that the environment is not necessarily restricted to the early game, and that, instead, the vast majority of action trajectories would result in more chaotic behavior. This would be especially understandable if these more chaotic trajectories were deceptively rewarding, with the search agent exploring them in depth before finally arriving at an obscure but long-term rewarding early game move sequence (with this sequence perhaps being one of the rare sequences to result in a stable map state for the rest of the episode). Analysis of alternative action trajectories, along with human testing of the generated environment, can reveal the deeper nature of the evolved dynamics.

Finally, we also observe some environments with something of a balance between relatively fixed/stable states, and more chaotic patterns, as shown in 2(g). Here, the environment stabilizes after some initial activity, after which point the agent takes some actions which result in the emergence and propagation across the map of more dynamic structures. Arguably, such environments are the most interpretable: unlike the purely chaotic environments, the impact of the agent’s actions are more clearly distinguished against a non-chaotic backdrop; and unlike largely stable environments, the agent’s impact on the environment dynamics can be observed over time, instead of occurring in the flash of an instant in a handful of early steps. Another way of seeing this is that it seems less like the agent is learning a fine-grained, carefully-timed and exacting sequence of actions—a kind of rhythmic password—and more like it is planning on a larger scale. Further work would be needed, however, to formalize and quantify the difference between such types of strategies before we might begin to associate them with different environments; ultimately, such heuristics could be used to guide the evolutionary process itself toward environments begetting this type of behavior from player agents. Similarly, our notion of this class of environments being more “interpretable” than those previously described could be pursued further, with the aim of better aligning the open-ended learning process with notions of human interestingness.

## 4 Related work

Reinforcement learning research has long relied on benchmarks of various kinds. These are often taken from, or inspired by, games, including board games and video games, and sometimes from robotics and other disciplines. An issue with these benchmarks is the risk of overfitting. If the benchmark does not have appropriate degree of variability, the RL algorithm will tend to learn a policy that will work only for a particular configuration of a particular environment. For example, when training deep RL methods to play Atari games in the ALE framework, they will typically learn a policy that works for only one game, and only the particular levels of that game, and break if you give the trained policies a new level or even just introduce visual distortions Zhang et al. (); Justesen et al. (); Cobbe et al. ().

One approach to ensuring sufficient diversity is to rely on procedural content generation (PCG), where levels or other aspects of the benchmark are generated algorithmically Risi and Togelius (). While the simplest forms of PCG simply consists in randomly changing parameters or moving things around, there are numerous PCG methods building either on various forms of heuristics and optimization Shaker et al. () or machine learning, including deep learning Liu et al. (). Clearly, PCG can help to combat overfitting in RL; by training on an infinite stream of freshly generated levels, more general policies can be found Justesen et al. ().

However, diversity in the training set is even better if you have the right sort of diversity. One way of achieving this is through competitive coevolution, where agents seek to perform well in environments and environments seek to provide challenge to agents. This idea, originating in biology Dawkins and Krebs (), has a long history in evolutionary computation Rosin and Belew (); Hillis (), and was later re-discovered in the form of adversarial learning Goodfellow et al. (). Applied to generating environments for reinforcement learning, this basic idea has taken on different shapes, including generating environments that provide an appropriate level of challenge or that are learnable by the reinforcement learning algorithm Togelius and Schmidhuber (); Dennis et al. (); Bontrager and Togelius (); Mediratta et al. (). The animating spirit behind much of this work, beyond merely combating overfitting, is to enable open-ended learning.

While there are many benchmarks and testbeds for reinforcement learning methods, few existing benchmarks feature meaningful PCG; exceptions include Obstacle Tower Juliani et al. (), CoinRun Cobbe et al. (), and Neural MMO Suarez et al. (). In comparison to these, Autoverse is an RL benchmark explicitly relying on and aiming to enable open-ended learning, where environment generation is responsive to progress in agent capabilities.

## 5 Conclusion

We introduce autoverse, a scalable testbed for open-ended learning algorithms, and run some initial experiments exploring the use of an evolutionary strategy to search for autoverse environments comprising difficult game environments with respect to a search-based player agent. We formalize the underlying mechanics of autoverse by association with cellular automata and the rewrite-rule approach to game logic developed by other popular game languages. We walk through some examples of popular game and reinforcement learning environments, showing how mazes, dungeons, sokoban puzzles, can be implemented with relatively straightforward sets of rewrite rules. We also show how autoverse update rules in general can be implemented with a simple series of convolutions, allowing environment simulation to occur on the GPU, making for fast simulation and neural-network learning in particular within the framework.

Our evolutionary search for challenging environments relative to a search-based player discovers a large number of distinct environments, each constituting a potentially novel and interesting task for an RL-based player agent. This evolutionary search also returns a large number of expert trajectories, which can ultimately be used for imitation learning and to jump start RL. Because the cap on search depth is increased incrementally over the course of evolution, we also obtain a curriculum of increasingly expert trajectories and/or increasingly complex environments. Future work will study how this data can be used to jump-start a generalist reinforcement learning game playing agent by pre-training its weights using imitation learning.

Of particular interest in the evolved autoverse environments is the degree to which a given environment’s dynamics are stable or chaotic. We note that a large number of environments tend toward chaos, and argue that more human-relevant environments can be found in the middle ground of semi-stable environments, where stable or oscillating patterns tend to be reached, but the player agent can intervent to disrupt or alter them to some degree. Future work is needed to investigate quantitative metrics that may be used to guide the search process toward such environments. More broadly, using pre-trained foundation models or humans-in-the-loop could also allow us both to align the process with notions of human interestingness, as well as to introduce additional human-authored complexity into the learning process.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: 1. How can the diversity of the generated environments be evaluated more accurately and quantitatively? Besides the current qualitative analysis, are there other more objective and comprehensive indicators to measure the differences and complexity between different environments to better prove the effectiveness of environment generation?
2. How does the paper dynamically regulate the evolution speed of the environment to avoid being too fast for the agent to learn or too slow to cause resource waste?
soundness: 1
strengths: - The design of Autoverse combines a domain-specific language with cellular-automaton-like rewrite rules and achieves efficient computation through convolutions, providing new perspectives and methods for game environment generation and agent training.
- Through the evolution of the environment, the complexity of the environment can be gradually increased according to the search ability of the agent, effectively avoiding the agent from prematurely falling into local optimal solutions and also providing a curriculum learning from simple to complex for the agent.
summary: This paper proposes Autoverse, an evolvable domain-specific language for single-player 2D grid-based games, as a training ground for Open-Ended Learning (OEL) algorithms. It describes game mechanics through rewrite rules similar to cellular automata, combines evolutionary algorithms to generate complex environments, employs imitation learning and reinforcement learning to train agents, and experimentally studies the impact of the observation range on agent performance and the dynamic characteristics of the evolved environments.
weaknesses: 1. Overall, the paper has limitations in terms of innovation. The framework of combining imitation learning and reinforcement learning used is not novel and has been involved in many current related research fields.
2. Although the rewrite rules are highly expressive, they are difficult to understand and interpret, which may limit their promotion and further development in practical applications, especially when manual intervention of the rules is required.
3. In the process of environment evolution, only mutation operations are involved, and crossover operations are not included. This may limit the exploration range of the diversity of environment generation to some extent.
4. The main experiment is lacking. There is a lack of direct comparison experiments with other advanced methods, making it difficult to accurately evaluate the advantages and disadvantages of Autoverse and clearly define its competitiveness in this field.
5. The long-term training effect experiment is insufficient. The experimental results mainly present the immediate performance data under specific settings. The performance change trend after a significant increase in the training cycle, the stability of the agent's strategy after a large number of environmental changes, and the evolution law of the long-term adaptability to new environments are not provided, making it difficult to judge the long-term comprehensive ability development.
6. The coherence of the chapter structure is poor in some parts. For example, the transition from the method description to the experimental results is not natural, affecting the reader's understanding of the logical relationship of the paper.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: - Being able to generate a vast number of environments is very interesting from an open-endedness perspective. However, many of the features that enable such versatility and efficiency limit Autoverse to grid-like, 2D, and seemingly small environments. Can methods developed in Autoverse be applied to more realistic scenarios (that are ultimately of interest)? Examples of these alternative (also open-ended) scenarios are Craftax  (Matthews et al., 2024)  or MineDojo (Fan et al., 2022). If not applicable, then what is the relevance of Autoverse?

- Is the grid size constant in all of the generated environments? If not, would it be possible to modify the framework to hold grids of different sizes? 

- How does the search method (used for the "warm-start") scale with the size of the grid and number of actions?   

- What is (approximately) the ratio of unusable and usable environments generated by the evolutive algorithm? With unusable I refer to environments so unstable that are not beneficial for the optimization process of the RL agent. 

- Do the reward update rules always take into account the actions of the agent? or reward can be generated by multiple cells of the CA interacting with each other with no relation to the actions of the agent?
soundness: 1
strengths: - The idea of using CA-based environments is both original and interesting. The fact that practically limitless environments can be created by modifying the initial state and the update rules is very interesting from an open-ended learning perspective.

- I also find CA environments relevant for research on foundation models for RL. This type of environment could be very valuable for generating training data for these types of models.

- I think that the presentation of Autoverse (Section 2.1) is clear and can be easily understood, whereas Figure 1 also helps to visualize the types of environments that are generated by the evolution process.
summary: The paper introduces a novel 2D and grid-like environment framework, named Autoverse, based on Cellular Automata (CA).  They define environments using the initial state of the CA, and the update rules (including state transition rules and reward). This allows authors to evolve environments in an open-ended RL setting. Moreover, the authors also propose an open-ended RL method based on bootstrapping the open-ended learning by pre-training the agent using an initial set of evolved environments and expert trajectories from a search method. Experiments show that the evolution process generates many chaotic environments, stable environments, and others in between (the ones of most interest). Furthermore, the open-ended method seems to benefit from fully observing the environment and access to the update rules that update the cells of the CA.
weaknesses: Although I think that the main idea (evolvable CA environments) is very interesting and could be promising for areas as foundation models for RL, UED, and open-ended learning. I have important concerns on several aspects of the paper:

- Although most ideas are clearly explained, the overall presentation and soundness of the paper are poor. 
    + The introduction section makes many (non-trivial) statements with no references. The introduction has no references, which I found surprising. Some examples of such sentences missing references and evidence/support are:
        - L31: "The idea of open-ended learning in virtual environments is [...]"
        - L32: "This idea comes in many forms, but what unites them all is that [...]"
       - L38:  "There have been interesting results, but learning generally stops at a rather low capability ceiling."
       - L40: "It has been observed that the complexity of the behavior of a living being, [...]"

- The ability to endlessly evolve and generate new environments is compelling, but as mentioned multiple times in the paper (e.g.,   L71, L413) evolutive process generates very unstable environments in most cases. I have serious concerns about the ratio of unusable and usable environments generated by the evolutive process. Authors claim scalability, but how much computational resources are needed to generate a fair amount of actually usable scenarios? I think that an exhaustive analysis of this topic is crucial and missing in the current version of the paper.  

- I think that the paper misses many experimentation details. For instance, experiments shown in Table1 and 2 are missing information on the number of evaluations, the number of generated test/train environments, the number of repetitions, etc. Seems that this information is also missing in the appendix. Moreover, none of the appendix sections are referenced in the main paper. Please, consider providing as many details as possible on the experimentation to ensure transparency and reproducibility. Moreover, I strongly believe that all sections of the appendix should be referenced at least once in the main paper.

-   I strongly believe that experimentation should be improved. The authors propose a "warm-start" method for open-ended RL, but they do not provide any evidence for why this method is relevant for the research community. I won't ask for a comparison with tens of methods from previous literature, but proposing a new method at least requires an exhaustive analysis of it. Some examples of how I think this could be improved:
    - Reward values in Tables 1 and 2 are missing interpretability. I can see that the results of some settings are better than others, but how much? Having some sort of reference value could help (e.g., results of a random agent or some well-known baselines).
    - Why is this method interesting? Does it obtain better results? Does warm-staring help to improve the results? Many experiments could be presented to answer these questions.   

- The paper claims computational efficiency but no evidence is provided. Experiments/benchmarks on computational performance are missing if such claims are made. 

- I think that the presentation has room for improvement. Some examples:
     - Figure 1 is presented is located in page 2, but is referenced on page 8 for the first time. 
     - Figure 3 holds an entire page but some of its text (Fig 3.a) is **extremely** small. There is plenty of blank space on Page 3 to increase some parts of the figure or rearrange them to improve visibility.
    - The format of tables 1 and 2 is not aligned with the ICLR style. Please carefully read the style PDF before submitting the paper.
    - There are many incorrect usages of parenthesis in references. For example, parenthesis in Earle et al. 2023 L271 should be removed, and Section 4 is missing parentheses in most of its references: L470-471, L476, L482...

---

confidence: 3
contribution: 3
initial_rating: 3
presentation: 2
questions: 1. Please clarify any confusing parts in the figures and tables.

2. Please provide additional experiments to support each claim in the paper, such as scalability and comparisons with other environments.

3. Please ensure that the figures and results are presented neatly and clearly.
soundness: 2
strengths: Autoverse offers efficiency by leveraging GPU-based batch processing. Its rewrite rule framework enables the creation of a vast array of dynamic, grid-based game environments, enhancing agent adaptability and preventing overfitting to static setups. The method's progressive curriculum, which evolves increasingly complex environments, allows agents to improve incrementally, while the integration of imitation learning with RL provides agents with a solid starting foundation. These strengths make Autoverse an innovative and robust tool for advancing research in open-ended learning.
summary: The paper introduces Autoverse, a special programming language for creating different types of grid-based game environments that help with open-ended learning in RL. Autoverse lets people build complex, changing game settings, especially for 2D, single-player games like mazes, Sokoban puzzles, and dungeon exploring. It uses simple rules, based on cellular automata, to quickly create these environments, which run well on a GPU. The system first teaches RL agents by having them imitate expert examples, then moves to open-ended RL in constantly changing environments to make the agents more adaptable.
weaknesses: First, there are presentation issues, as figures (like 3 and 4) lack clarity—small text sizes, ambiguous elements, and layout issues reduce readability. Second, empirical evidence demonstrating scalability is lacking; additional experiments or metrics require to solidify this claims.  The paper fail to do performance comparisons of Autoverse’s combined imitation and RL approach against using either method alone. While it states that Autoverse’s environments are more complex and diverse than others, this claim lacks citations or direct comparisons with other open-ended learning benchmarks. Finally, the paper does not report the performance achieved after the behavior cloning stage, leaving its contribution to the final results ambiguous. Addressing these points could greatly enhance the paper’s clarity, rigor, and persuasive power.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 1
questions: In general, I would really appreciate it if the authors could provide more details and discussions of the proposed method performance and the reasons why they design the whole method and environment in this way. And also, the comparison with other baseline or ablation study will be welcomed.
soundness: 2
strengths: 1, Originality: The paper presents Autoverse, a new environment for open-ended learning, which allows more complex environment dynamics and much more environmental diversity than other open-ended learning environments.
2, Quality: The use of JAX for implementing cellular-automaton rules allows efficient parallelization on GPUs, and at least an order of magnitude speedup.
3, Significance: The use of imitation learning followed by reinforcement learning provides a structured way for agents to learn from expert play traces and then further refine their behavior, leading to better generalization.
summary: The paper introduces Autoverse, a domain-specific language (DSL) for creating 2D grid-based games, designed to enhance open-ended learning for Reinforcement Learning (RL) agents. Autoverse allows for evolving complex game environments using cellular-automaton-like rewrite rules, which can be parallelized on the GPU to speed up RL training. The authors propose a framework involving the evolution of environments, imitation learning from search-based solutions, and reinforcement learning in evolving environments to generate increasingly challenging tasks for RL agents. This approach aims to overcome the challenges of cold-starting RL in open-ended environments and produce more behaviorally complex and adaptable agents. They first evolve Autoverse environments (their rules and initial map topology) to maximize the number of iterations required by greedy tree search to discover a new best solution, producing a curriculum of increasingly complex environments and playtraces. The proposed method then distill these expert playtraces into a neuralnetwork-based policy using imitation learning. Finally, the learned policy becomes as a starting point for open-ended RL, where new training environments are continually evolved to maximize the RL player agent’s value function error (a proxy for its regret, or the learnability of generated environments), finding that this approach improves the performance and generality of resultant player agents.
weaknesses: 1, Presentation Improvement: Provide more detailed feedback, such as clarifying ambiguous elements like the meaning of the gray box in Figure 4 and addressing layout issues with full-page figures such as figure 3 and figure 4. And the texts in figure 3 are too small.
2, Scalability Evidence: Request empirical evidence or additional explanations to demonstrate scalability, including experiments or metrics.
3, Justification for Greedy Tree Search: Maybe adding references in related work and experimental validation to justify the choice of greedy tree search.
4, Comparison of Methods: Recommend including a comparison between the proposed approach and using only imitation learning or reinforcement learning.
5, Performance Results: The paper mentioned "Once the behavior cloning algorithm has converged, we continue training the agent with reinforcement learning", but there is no results show that what kind of performance can this method reach when behavior cloning algorithm has converged and what is the final performance compared to that stage.
6, Lack explanation of comparing with other environments: In the paper "Autoverse stands out for allowing more complex environment dynamics and much more environmental diversity than other open-ended learning environments." But I did not see any citation or detailed comparison with other open-ended learning environments. Further discussion will make the arguments more convincible.

Meta-review: Autoverse is a highly-original concept for a new open-ended learning environment. The ideas and engineering behind this work are creative. However, as all reviewers unanimously agreed, the presentation and experimental design have much room for improvement. Unfortunately, the current gap between the environment concept and the presentation of the empirical component of this work makes it unfit for publication at a top venue like ICLR. 

Specifically, the authors should seek to incorporate clearer quantitative comparisons that highlight the strengths of Autoverse as a benchmark environment for open-ended learning with respect to previous environments. For example, more in-depth analysis of the evolutionary dynamics during training and a clear quantitative comparison demonstrating a) how Autoverse environments are more diverse than previous environments, and b) how Autoverse environments provide a greater challenge to existing methods and therefore provides signal that previous benchmarks do not, which is at a high level, a central motivation for Autoverse.

Decision: Reject