🤖 AI

Calculating Mutual Information between a Reward Maximizer and its Environment

This paper proves that for a Controlled Markov Process with $n$ states and $m$ actions, observing an optimal deterministic policy conveys exactly $n \log m$ bits of information about the underlying environment, thereby establishing a precise information-theoretic lower bound on the implicit world model required for optimality across various reward maximization objectives.

Original authors: Alfred Harwood, Jose Faustino, Alex Altair

Published 2026-07-15

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Alfred Harwood, Jose Faustino, Alex Altair

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

The Secret Language of Perfect Players

Imagine you are watching a master chess player. You don't know the rules of the board, you don't know where the pieces started, and you don't know if the opponent is playing randomly or with a grand plan. Yet, as the master makes move after move, you start to realize something profound: their perfect strategy must contain a hidden map of the game. If they know exactly which move wins, they must know something about how the pieces move and how the board is set up. This is the heart of a big question in the world of artificial intelligence (AI): Does a smart agent need to "understand" the world it lives in to do a good job, or can it just guess its way to success?

To answer this, scientists use a concept called Mutual Information. Think of this as a measure of how much two things "tell" you about each other. If you know the weather, you know a lot about whether people are carrying umbrellas; the two have high mutual information. If you know someone's shoe size, you know almost nothing about what they had for breakfast; the mutual information is low. In AI, researchers want to know: If we see an AI acting perfectly, how much does that behavior reveal about the hidden rules of its world? Does the AI have to carry a massive, detailed "world model" in its brain, or is a tiny, vague hint enough? This paper dives into that question, treating the AI's perfect strategy like a locked box that, once opened, reveals a precise amount of secret data about the world inside.

The Paper's Big Discovery: The Perfect Map

In this new study, a team of researchers from Dovetail Research and the University of Sao Paulo decided to play a game of "reverse engineering." They asked a simple but tricky question: If we see an AI agent acting as the perfect reward maximizer (meaning it always gets the best possible score), how much information about its environment is hidden inside that perfect behavior?

To figure this out, they imagined a world that is a bit like a giant, multi-room maze. This maze has $n$ different rooms (states) and $m$ different doors (actions) the agent can choose to open in each room. The twist? The researchers started with "maximum ignorance." They didn't know which door led where. Every possible way the doors could connect to the rooms was equally likely, like a deck of cards where every shuffle is a different possible world.

Then, they watched the AI. They saw that the AI had found a specific, deterministic plan: "If I'm in Room 1, open Door A. If I'm in Room 2, open Door B," and so on. Crucially, this plan was the only way to get the highest score for a specific goal (like collecting the most gold coins).

The team proved a surprising mathematical fact: The moment you learn that this specific plan is the perfect one, you instantly learn exactly $n \log m$ bits of information about the maze.

Let's break down what that means with a playful analogy. Imagine the maze is a giant library with $n$ shelves. On each shelf, there are $m$ different books you could pull out. The "perfect plan" is like a librarian who knows exactly which book to pull from every single shelf to find the best story. The researchers showed that the librarian's perfect list of choices acts like a key. It doesn't just tell you one thing; it tells you enough about the library's connections to narrow down the possibilities to a specific volume of information.

The number $n \log m$ is the "size" of that secret.

$n$ is the number of places you can be.
$m$ is the number of choices you have in each place.
$\log m$ is the amount of information needed to pick one choice out of $m$ options.

So, if you have 3 rooms and 2 doors in each, the perfect strategy contains $3 \times \log(2)$ bits of info. If you have 100 rooms and 10 doors, the strategy contains $100 \times \log(10)$ bits. The paper proves this number is exact for the vast majority of cases, representing a precise lower bound on the information contained in the policy.

Why This Matters (And What It Rules Out)

This finding is a big deal because it puts a strict lower limit on how much "world knowledge" a perfect agent must have. It suggests that you cannot be a perfect reward-maximizer without implicitly knowing a specific amount of information about how your world works.

The paper is very careful about what it doesn't say, too. It doesn't claim that the AI has a giant, human-like 3D model of the world in its head. It doesn't say the AI "thinks" in pictures. Instead, it says the AI's behavior contains the same amount of information as a world model would. The information is there, whether it's stored in a complex neural network, a simple lookup table, or even a magical black box. The paper proves that the content of the information is fixed at $n \log m$ bits, regardless of how the AI is built.

The researchers also tested this idea across different types of "games." They looked at:

Short games: Where the agent tries to get the best score in a fixed number of steps.
Long games: Where the agent plays forever but cares more about immediate rewards (discounted rewards).
Endless games: Where the agent plays forever and cares about the average score over time.

In all these cases, the math held up. As long as the goal is to get the best score based on where the agent is (and not based on some weird, random rule), the perfect strategy always reveals exactly $n \log m$ bits of the environment's secrets, with the exception of a tiny, mathematically negligible set of edge cases.

The "Equal Volume" Secret

How did they prove this? They used a clever geometric trick. Imagine the space of all possible mazes as a giant, multi-dimensional blob. The researchers showed that if you slice this blob up based on which strategy is the best, every single strategy gets an exactly equal-sized slice of the blob.

Think of it like a giant pizza cut into $m^n$ slices (since there are $m$ choices for each of the $n$ rooms). If you pick a random pizza, any specific slice is just as likely to be the "best" one as any other. Because every slice is the same size, finding out which slice you are in (by observing the perfect strategy) reduces your uncertainty by a precise amount: the logarithm of the number of slices. That calculation leads directly to the $n \log m$ result.

The paper is rigorous about this. They proved that for almost every possible maze (ignoring a tiny, mathematically negligible set of weird edge cases where multiple strategies tie perfectly), there is exactly one perfect strategy. And because the "best" strategy is equally likely to be any of the possible strategies, the information gain is constant and calculable.

What's Next?

The authors are honest about the limits of their work. They only looked at agents that make one decision based on where they are right now (deterministic, memoryless policies). They didn't look at agents that flip a coin to decide (randomized policies) or agents that remember their entire history. They also didn't look at agents that can't see the whole room (partially observable environments).

However, for the specific type of perfect, clear-sighted agent they studied, the answer is clear: To be perfect, you must carry exactly $n \log m$ bits of the world's secrets. It's a precise, mathematical proof that a good performance isn't just luck; it's a reflection of a hidden map, and we can now measure exactly how big that map is.

Technical Summary: Calculating Mutual Information between a Reward Maximizer and its Environment

Problem Statement
The paper addresses a fundamental question in artificial intelligence: to what extent does successful, goal-directed behavior necessitate an internal representation (a "world model") of the environment? While it is established that agents with perfect world models can achieve optimality, the inverse relationship—whether high performance implies the possession of specific environmental information—remains less formally quantified. The authors operationalize this by asking: if an observer knows that a specific policy is optimal for a given goal, how much information about the underlying environment can be extracted from that policy? The study focuses on the information-theoretic content of the policy itself, independent of the agent's internal architecture or implementation.

Methodology
The authors model the environment as a Controlled Markov Process (CMP) with $n$ states and $m$ actions. The space of possible environments, denoted as $\mathcal{X}$ , is defined by the set of all valid transition probability matrices, forming a product of simplexes.

The core methodology relies on Information Theory, specifically the calculation of Mutual Information $I(X; \Pi)$ between the random variable representing the environment ( $X$ ) and the random variable representing the optimal policy ( $\Pi$ ).

Prior Assumption: The analysis begins with a state of "maximal ignorance," assuming a uniform prior probability density function (PDF) over the space of all possible environments $\mathcal{X}$ .
Policy Space: The agent is assumed to use a deterministic, Markovian policy ( $\pi: S \to A$ ). There are $m^n$ such possible policies.
Optimality Conditions: The study investigates the conditions under which a policy is optimal for maximizing a value function $V_\pi(x)$ $V_{π} (x)$ . The authors consider three standard reward aggregation methods:
- Finite-horizon total reward.
- Infinite-horizon discounted reward.
- Time-averaged reward.
- The reward function $r: S \to (0,1)$ is required to be non-constant.
Geometric Partitioning: The proof strategy involves analyzing the geometry of the environment space $\mathcal{X}$ . The authors define subsets $X_i \subset \mathcal{X}$ where a specific policy $\pi_i$ is the unique optimal policy. They aim to prove that these subsets form a partition of $\mathcal{X}$ (up to a set of measure zero) and that each subset has an equal volume.

Key Contributions and Results

The paper establishes a precise lower bound on the information contained in an optimal policy. The main result is derived through a series of lemmas and theorems:

Equal Volume Partition (Theorem 3.2): The authors prove that for any value function dependent on the policy only through the induced transition matrix $M_\pi(x)$ , the volume of environments for which any specific deterministic policy $\pi_i$ is uniquely optimal is identical for all $i$ . This is demonstrated by constructing a measure-preserving, invertible mapping $g_{ij}$ that swaps the transition probabilities associated with the differing actions of two policies, effectively mapping the set of environments where $\pi_i$ is optimal to the set where $\pi_j$ is optimal.
Uniqueness of Optimal Policy (Lemmas 3.3–3.13): Using the property that the value functions for the considered reward types are real analytic functions of the environment parameters, the authors show that the set of environments where two distinct policies yield identical performance (i.e., $V_{\pi_i}(x) = V_{\pi_j}(x)$ ) has a Lebesgue measure of zero. Consequently, for almost all environments, there is exactly one unique optimal policy.
Mutual Information Bound (Lemma 3.1 & Main Theorems):
- If the environment space is partitioned into $m^n$ subsets of equal volume, and one learns which subset contains the true environment (by observing the optimal policy), the reduction in differential entropy is exactly $\log(m^n)$ .
- The paper proves that for any non-constant reward function and across finite-horizon, infinite-discounted, and time-averaged regimes, the mutual information between the environment and the optimal deterministic policy is exactly:
  $I(X; \Pi) = n \log m \text{ bits}$
- This result holds regardless of the specific reward function values, provided the reward is non-constant, and holds for any prior invariant under action re-labelling.

Significance and Claims
The paper claims to provide a precise, information-theoretic lower bound on the "implicit world model" necessary for optimality. The significance of the findings includes:

Quantification of Implicit Knowledge: It demonstrates that an optimal policy is not merely a behavior but a carrier of specific information about the environment's transition dynamics. Specifically, knowing the optimal policy reveals $n \log m$ bits of information, effectively narrowing the possible environment space from the entire manifold to a specific partition cell of volume $V/m^n$ .
Generality: The result is robust across a broad class of objectives (finite, discounted, and time-averaged) and does not rely on the agent having a "general" goal-conditioned policy (unlike prior work which required agents to handle a wide range of goals). It applies even when the agent is optimized for a single, specific reward function.
Safety and Interpretability: The authors suggest that these formal results could aid in understanding the fragility of machine learning systems. If performance is observed, one can deduce the minimum amount of world information the system must possess, potentially helping to assess trustworthiness or detect "out-of-distribution" failures where the implicit model might be insufficient.

Limitations and Future Directions
The authors explicitly note the following limitations and potential extensions:

Determinism: The current result applies strictly to deterministic policies. Extending this to stochastic policies ( $\pi: S \to \Delta A$ ) is a noted future direction.
Memory: The analysis assumes Markovian policies (memoryless). Agents with memory (policies based on history) are not covered.
Partial Observability: The study assumes fully observable environments. The results for partially observable environments (POMDPs) are not derived.
Sub-optimality: The paper focuses on optimal policies. It poses the question of whether a bound can be established for policies that are $\delta$ -optimal (near-optimal).
Algorithmic Information Theory: The authors suggest future work could explore these bounds using Algorithmic Information Theory rather than Shannon information.

In summary, the paper provides a rigorous geometric and information-theoretic proof that optimal reward maximization in a CMP inherently encodes a specific, quantifiable amount of information about the environment's transition structure, independent of the specific reward values or the accumulation method used.