🤖 machine learning

An Information-Theoretic Definition for Open-Ended Learning

This paper introduces an information-theoretic definition of open-ended learning based on the concept of "bit-equivalent" to quantify the information required for reward attainment, demonstrating that linear growth in this metric distinguishes open-ended environments from classical bandits and presenting an algorithm that achieves such learning.

Original authors: Wanqiao Xu, Yifan Zhu, Benjamin Van Roy

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wanqiao Xu, Yifan Zhu, Benjamin Van Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game. In a normal game, there is a final boss, a high score, and a clear path to victory. Once you beat the boss, the game is "solved." You can't get much better at it because there's nothing new to learn.

Now, imagine a different kind of game. One where, the more you play, the more the game reveals new levels, new mechanics, and new challenges that you couldn't have imagined before. The game never ends, and you never stop getting smarter. This is what the authors call Open-Ended Learning.

The paper by Xu, Zhu, and Van Roy tries to answer a very tricky question: How do we know if an AI is truly in a game that never ends, versus just playing a really long, boring game?

Here is the breakdown of their ideas using simple analogies.

1. The Problem: "Novelty" isn't enough

Previously, people thought an environment was "open-ended" if it kept giving the AI new, weird, and interesting things to do. The authors say, "Not so fast."

Imagine a robot that keeps generating random, weird drawings. They are all "new" (novel) and you can "learn" to recognize them. But does the robot actually get better at drawing? No. It's just making noise.

The authors argue that true open-endedness isn't just about making new things; it's about continually needing to learn new information to get better. If you can get a high score without learning anything new, the game isn't open-ended.

2. The New Tool: The "Bit-Equivalent"

To measure this, the authors invented a new concept called the Bit-Equivalent.

Think of "bits" as the currency of information.

The Concept: The "Bit-Equivalent" of a reward is the minimum amount of information you need to understand the world to earn that specific reward.
The Analogy: Imagine you are trying to find a hidden treasure.
- If the treasure is a $1 bill sitting on the sidewalk, you need zero bits of information to find it. You just look down.
- If the treasure is a diamond hidden in a massive cave with a complex map, you need many bits of information (the map, the layout, the clues) to find it.

The authors define an environment as Open-Ended only if, to keep getting better rewards, the AI must keep collecting more and more information (bits) at a steady, linear pace. If the AI can keep getting rewards without learning new information, the environment is "closed."

3. The Test: Why Old Games Fail

The authors tested this definition on "classical" AI games (called Bandit environments). They found that almost all of them fail the open-ended test.

Finite Games (The Finite-Armed Bandit): Imagine a slot machine with 10 levers. Once you figure out which lever pays the most, you just pull that one forever. You stop learning. The "Bit-Equivalent" stops growing.
Infinite Games (The Infinite-Armed Bandit): Imagine a slot machine with infinite levers, but every lever is completely random and unrelated to the others. You can pull a new lever every time and get a new reward, but you aren't learning a pattern. You aren't building a deeper understanding of the machine. The information you gain doesn't help you get better rewards in the long run.

In both cases, the AI hits a wall where it can't get better without learning more, but the environment doesn't allow for that continuous learning.

4. The Solution: The "Insatiable" Game

The authors then built a new, custom game called the Insatiable Linear Bandit.

The Setup: Imagine a giant, infinite row of light switches. Each switch controls a tiny bit of your score. Some switches are broken (they lower your score), and some are good (they raise it).
The Catch: You don't know which switches are good. You have to flip them to find out.
Why it works: Because the row is infinite, there is always a new, unexplored section of switches that could be good. To get a higher score, you must keep flipping more switches and learning the pattern of which ones work. You can never "solve" the game because the game is infinitely deep.

5. The Strategy: "Truncated Thompson Sampling"

The authors also tried to teach an AI how to play this new game. They found that standard AI strategies failed:

Too greedy: If the AI tries to learn the entire infinite row at once, it gets overwhelmed and makes mistakes that hurt its score.
Too small: If the AI only looks at the first 10 switches and ignores the rest, it stops improving after a while.

The Winning Strategy: The authors created a method called Truncated Thompson Sampling (TTS).

The Analogy: Imagine you are reading a massive, infinite encyclopedia.
- Don't try to read the whole book in one day (you'll fail).
- Don't just read the first page forever (you'll learn nothing new).
- The TTS way: Read the first chapter. Master it. Then, move to the second chapter. Then the third. You keep expanding your "reading window" just enough to stay ahead of your learning curve.

By slowly expanding the scope of what it tries to learn, the AI can keep finding new "good switches" forever, and its score (and the information it holds) keeps growing linearly.

Summary

The paper claims that:

True Open-Endedness means an environment where getting better requires you to keep learning new information at a steady pace.
Most current AI games are not open-ended because you eventually stop needing to learn to get rewards.
They built a new game (the Insatiable Linear Bandit) where you must keep learning to improve.
They built a new AI strategy (Truncated Thompson Sampling) that successfully plays this game by slowly expanding its knowledge, proving that open-ended learning is possible under the right conditions.

Technical Summary: An Information-Theoretic Definition for Open-Ended Learning

Problem Statement

The paper addresses the lack of a coherent theoretical definition for open-endedness in AI systems. While existing literature characterizes open-ended environments as those presenting increasingly novel and complex tasks, or defines them via the novelty and learnability of agent-produced artifacts, these definitions fail to capture whether an agent can sustainably improve its capabilities through interaction. Specifically, generating novel policies does not necessarily imply the acquisition of information that enables improved performance.

The authors propose to formalize open-endedness by studying the relationship between expected reward and the information required to attain that reward. The central question is: Does an environment allow for sustained reward improvement that necessitates the continual acquisition of useful information at a non-vanishing rate?

Methodology and Definitions

The Bit-Equivalent

The core methodological contribution is the introduction of the bit-equivalent ( $B_\rho$ ). This concept quantifies the minimum amount of information (measured in nats) about the environment parameter $\theta$ required to select an action that yields an expected reward of at least $\rho$ .

Formally, for an expected reward level $\rho$ :
$B_\rho = \inf_{A: \mathbb{E}[r_\theta(A)] \geq \rho} I(\theta; A)$
where $I(\theta; A)$ is the mutual information between the environment parameter and the action.

Average Bit-Equivalent and Open-Endedness

The performance of an agent $\pi$ over time $T$ is characterized by the average bit-equivalent ( $B_T(\pi)$ ), defined as the time-average of the bit-equivalents of the rewards attained:
$B_T(\pi) = \frac{1}{T} \sum_{t=0}^{T-1} B_{\mathbb{E}_\pi[R_{t+1}]}$

Definition of Open-Endedness: An environment is defined as open-ended if there exists an agent $\pi$ such that the average bit-equivalent grows linearly with time:
$B_T(\pi) = \Omega(T)$
An agent achieves open-ended learning if it realizes this linear growth rate.

Analytical Framework

The authors analyze this definition within the context of bandit environments. They distinguish between:

Information Gain ( $\gamma_T$ ): The total mutual information $I(\theta; H_T)$ contained in the history.
Bit-Equivalent Growth: The specific information required to achieve reward improvements.

The paper establishes that while sublinear information gain implies non-open-endedness, linear information gain is not sufficient for open-endedness. An environment may allow linear information acquisition, but if that information does not translate to sustained reward-relevant bit-equivalent growth, the environment is not open-ended.

Key Contributions and Results

1. Negative Results: Classical Environments are Not Open-Ended

The paper proves that several standard bandit environments fail to meet the open-endedness criterion:

Finite-armed Bandits: Even with non-Gaussian noise allowing infinite information gain, the finite action set bounds the bit-equivalent by $\log |A|$ . Thus, $B_T(\pi) \leq \log |A|$ , which is not $\Omega(T)$ .
Finite-Dimensional Linear Bandits (Gaussian): Information gain grows as $O(d \log T)$ , which is sublinear ( $o(T)$ ).
Gaussian Process (GP) Bandits: Under standard kernel assumptions (e.g., Matérn, squared exponential), the spectral tail decay of the kernel eigenvalues ensures information gain is sublinear.
Infinite-Armed Bandits (i.i.d. means): Despite potentially unbounded information gain, the average bit-equivalent grows at most logarithmically ( $O(\log T)$ ) because the weak coupling between independent arms prevents linear growth of useful information.

2. Positive Result: The "Insatiable Linear Bandit"

The authors construct a specific environment, the insatiable linear bandit, which is open-ended.

Setup: The action set $A$ consists of infinite-dimensional binary vectors with finite support ( $a \in \{0,1\}^\mathbb{N}, \|a\|_1 < \infty$ ). The parameter $\theta \in \mathbb{R}^\mathbb{N}$ has independent components $\theta_i \sim \mathcal{N}(-1, 1)$ . The reward is $r_\theta(a) = \langle \theta, a \rangle + \text{noise}$ .
Key Property: Unlike GP bandits, the kernel eigenvalues in the coordinate basis are not summable, violating the spectral tail conditions that limit information gain.
Result: The authors prove that $B_T(\pi) = \Omega(T)$ for this environment, satisfying the definition of open-endedness.

3. Algorithmic Failure and Success

The paper analyzes why classical algorithms fail in the insatiable linear bandit and proposes a successful alternative:

Thompson Sampling (TS) Failure: Standard TS attempts to optimize over the full infinite-dimensional posterior. Since the posterior sample $\theta^{(t)}$ has infinitely many positive coordinates with probability 1, the supremum of the reward is unattainable within the valid action set $A$ . Even with finite truncation, the expected reward of the maximizer diverges to $-\infty$ as the truncation size increases.
Fixed Truncation (FT) Failure: Fixing a finite dimension $M$ limits the information acquisition to $O(M \log 2)$ , preventing linear growth.
Truncated Thompson Sampling (TTS) Success: The authors introduce TTS, which employs a sequence of learning targets. Instead of learning the full $\theta$ $θ$ or a fixed truncation, the agent dynamically increases the truncation level $m_t$ $m_{t}$ over time.
- Mechanism: The agent selects a truncation level $m_t$ based on the history, samples the posterior for the first $m_t$ coordinates, and acts optimally for that truncated parameter.
- Theoretical Guarantee: By carefully scheduling the growth of $m_t$ (balancing exploration of new coordinates with exploitation of learned ones), TTS achieves a cumulative reward of $\Omega(T^2)$ . Since reward growth implies bit-equivalent growth in this setting, TTS achieves $B_T(\pi) = \Omega(T)$ , proving open-ended learning.

Significance and Limitations

Significance

The paper provides the first quantitative, information-theoretic definition of open-endedness that directly links performance improvement to the acquisition of useful information. It demonstrates that:

Reward alone is insufficient: High or unbounded rewards do not guarantee open-endedness; the information cost of achieving those rewards is the critical metric.
Classical assumptions are insufficient: Unbounded rewards and infinite action sets (commonly assumed to enable open-endedness) are not sufficient conditions.
Learning Targets matter: Achieving open-endedness requires an agent to adapt its learning targets (e.g., via TTS) rather than attempting to learn the full environment state or fixing a static approximation.

Limitations

The authors explicitly note two main limitations:

Bandit Setting: The definition and analysis are currently restricted to bandit environments (stateless). Extending this framework to stateful, non-stationary, or full Reinforcement Learning (RL) environments is a necessary next step.
Hyperparameter Dependency: The proposed TTS algorithm requires a pre-specified sequence of learning targets (truncation levels). The authors acknowledge that designing agents that can autonomously determine these targets without deliberate hyperparameter choices remains an open challenge.

The paper concludes that while the TTS agent serves as a "sanity check" for the intuition that agents must continually expand their learning targets, the framework offers a rigorous foundation for future theoretical analyses and agent design principles in open-ended learning.