Goal-directed optimisation requires information about the world

dubinsschwarz

This post was written as part of the 2026 Research Fellowship for Dovetail Research. I'm grateful to the organisers and research leads, Alex and Alfred, as well as the other research fellows for many helpful discussions on related topics. This work was funded by the Advanced Research + Invention Agency (ARIA) through project code MSAI-SE01-P005.

Declaration: I used GPT-5.5 and GPT-5.6 Sol significantly to assist me with the proofs. However, this post was entirely written by a human.

Prerequisites

This post assumes familiarity with the basic properties of KL divergences, elementary probability theory, and analysis at the undergraduate level.

Introduction

If an agent reduces the entropy of its environment significantly, then the Touchette-Lloyd theorem^[1] lets us deduce that it must have mutual information with the initial state of the environment. Briefly, if represents an initial environmental state, and a policy takes an action which interacts with to yield a resulting state , then it states that:

where is the Shannon entropy of , is the mutual information between and , and is the maximum entropy change achievable by a blind policy over all choices of initial distribution ; the latter acts as a baseline. The term can be interpreted as a simple proxy for world modelling.

In this post, we will ask a similar question: if an agent reduces the KL divergence of its environment to a goal , must it have mutual information with the environment?

We answer this in the affirmative. In Theorem 1, we prove that there is a direct parallel to Touchette-Lloyd in this setting, up to an irreducible correction term, and we illustrate this with examples after the proof. We also prove the sufficiency of an explicit algorithm for computing the optimal loss achieved by our analogous baseline policies, such that every unknown in the inequality can be computed.

The entropy of a random variable with finite support can be written as:

where is the uniform distribution on the same support. Thus, minimising entropy on a fixed set of letters is the same as maximising KL divergence to a uniform distribution — up to a constant which cancels when we take differences such as . This observation leads to the following generalisation of Touchette-Lloyd, which has exactly the same proof as the original:

Corollary

Let be any probability distribution on . Then:
where is the maximum change in KL divergence achievable by a blind policy over all choices of initial distribution .

But arguably minimising entropy, or maximising KL divergence away from a distribution, is less intuitive than optimising towards some goal distribution, which could be a high-entropy distribution in general. Moreover, for some utility functions, maximising utility maximisation is equivalent to simultaneous entropy and KL divergence minimisation. With this as motivation, we will prove the theorems below.

First, a full explanation of our notation, which deviates a little from the above.

Notation

We work with four random variables. All of them are finite.

is the action taken by a policy
is a measurement of some resulting state
are random variables representing information
- is all of the information available in the environment
- is a restricted subset of the information, which we use for our baseline

Hence, we will generally take to be coarser than . For example, we might let for some . For improved flexibility, we don't directly work with anymore, but when comparing to Touchette-Lloyd, it is natural to let .

We do not require to be fixed conditional on or to be fixed conditional on ; both the policy and the dynamics of the environment are allowed to behave stochastically. We write the equation:

captures the dynamics of how the environment evolves conditional on and is the natural incidence of in the environment. They do not depend on the policy. Finally, we will write expressions such as for the probability that takes action conditional on information , and for the distribution of conditional on when the policy is .

First Theorem

The following definition and lemma are needed for the first theorem.

Definition

Let be any policy. Then, the -blurring of is the policy defined by:
We say that a policy is -restricted if for all .
Thus, every -blurring is -restricted.

We derive an elementary identity relating to blurred policies as a lemma.

Lemma 0

Remark: The expression on the LHS, , will appear frequently throughout this article. Informally, it measures how much information and share which is not already present in .

The proof follows easily from the definitions.

Proof of Lemma 0

Fix a policy . Then, if is the distribution described by , by definition:

as required.

We will now state the main result of this article.

Theorem 1

Let be some goal distribution. Define the loss of a policy to be:
Then, if , we have the inequality:
where .

Let be the optimal loss across all -restricted policies. Then, by definition, so this has the immediate corollary below.

Theorem 1a

We comment that, up to the correction term of order , this looks remarkably similar to the Touchette-Lloyd theorem.

We can also state a variant of the theorem where the coefficient of the term is sharp. Define:

Then, we have the following result.

Theorem 1b

With the same definitions as above, we have:
where .

In the proof of Theorem 1, we use Pinsker's inequality to derive the term. The statement of Theorem 1b justifies that this correction term is not an artefact of Pinsker's inequality being sub-optimal in this context.

Theorem 1b is far from the tightest bound we can define in terms of the coefficient of , but its statement is given mostly for illustrative purposes, and we will not prove it here.

Theorem 1 also has the following pleasant corollary.

Corollary 1.1

If , then .

This is notable as a lower bound of in the special case , but also as an upper bound on the optimal loss for -restricted policies.

We will now begin the proof of Theorem 1. In the proof, we will often use the following shorthand when are fixed and known in context.

Proof of Theorem 1

Fix with . Then,

It follows easily that, for any , , and we can rearrange this to find that:

for any with .

For convenience, let . We will now prove the following claim:

The result then follows by averaging. First, we can write:

Now we will estimate the second expression. We work by cases.

Case 1:

In this case, making use of the inequality above, we write:

Let be the total variation distance between distributions . Then:

But we also have that . In particular, this implies that:

where abbreviates for with fixed.

Therefore, we deduce the inequality:

By Pinsker's inequality, we further bound this to:

This concludes this case.

Case 2:

If and , then the related summand is non-positive, so we are able to upper bound this sub-case by .

Therefore, we restrict to the sub-case . For this sub-case, define:

and let be the set of all in this sub-case. Then, the contribution from this sub-case is:

By the Cauchy-Schwarz inequality:

We bound the two factors independently. For the first factor, note that for ,

by integrating both sides. We temporarily write etc. for clarity on the page. Then:

where the second inequality follows since for all . But note that:

Thus, we simplify to:

But the sum on the RHS is the definition of the KL divergence from to so, in fact, we deduce that:

For the second factor, define:

Then:

since is a probability mass function. Hence:

But then, we also have that:

Hence:

Finally, for the equality case , we simply note that all such terms vanish in the sum.

If we now unify the bounds across all cases and substitute into the initial identity, we obtain that:

Recall we have kept fixed this entire time. We now average over , weighted by . Note that, by definition, we have:

and by data processing:

Thus, the only remaining term to evaluate is:

which we split into:

and:

For the first term, by the Cauchy-Schwarz inequality:

We recognise the expressions here to deduce:

Lastly, for , we may simply apply Jensen's inequality to find that:

Piecing together all of the information we have learnt, we find that:

as required.

We now illustrate the theorem with some examples.

Example 1

Let if it is raining and if it is not, with , and suppose a policy can take actions to go outside with an umbrella, to go outside leaving the umbrella at home, and to stay at home. In order to complete a task, the agent has to go outside at some point, so let if and only if it goes outside equipped suitably for the weather and otherwise, with a goal distribution of for every .
If is trivial, then to minimise KL-divergence, the optimal -restricted policy can do no better than flipping a coin, so is nats. On the other hand, if a policy is able to attain conditional on 99% of the time, then this implies that:
Lastly, we may calculate that . Hence, the theorem certifies that:
We compare this to Touchette-Lloyd. For this example, it actually gives a completely vacuous lower bound. The optimal blind policy for entropy reduction is the policy which stays at home with probability . But this means that , which is strictly greater than the entropy change achieved by . Thus, on its own, Touchette-Lloyd does not even justify that
This example identifies a general weak point of Touchette-Lloyd: maximising over all blind policies can include many policies which reduce entropy for trivial or extraneous reasons.

Example 2

Imagine that is at a poker table, in CO pre-flop. After 's 3x open raise, SB 3-bets with a 4x raise and everyone else folds round to . (Roughly speaking, has signalled that they might have a strong hand, but unfazed, the SB is betting very aggressively, either as a show of strength — or a bluff.)
In this context, we could take to be 's hand and let . Then, let and set the goal distribution to be the GTO action distribution for this spot. GTO stands for game-theory optimal; it is the Nash equilibrium strategy which cannot be beaten by any other.
In this scenario, if has a fairly strong hand, such as 99, then optimal play prescribes non-trivial probabilities for all of the possible actions. Raising can work as a counter-bluff, calling is often good value, and folding limits the downside risk. But any low-entropy strategy which always defaults to one of these is a flawed strategy which other players can easily exploit.
We won't directly compute any lower bounds on the mutual information for this example, but I hope it illustrates that there are real-world situations where might be a high-entropy distribution.

We will now discuss the second set of theorems.

Second Theorem

In the first section, we discussed how the bound with given in Theorem 1 will always be better than the bound with in Theorem 1a. But there's also a qualitative difference between the two results. Theorem 1 attests to the mutual information between and for a specific policy by comparing it to its own blurring . However, we can interpret Theorem 1a as proving a rate-distortion result: that whenever any policy achieves a certain loss, it must have a certain amount of mutual information with the environment.

We therefore find it worthwhile to investigate how to calculate . In this section, we claim that we can estimate its value through an explicit iterative process with effective error bounds, whenever the goal is fair. This differs notably to the term in the Touchette-Lloyd theorem, which is not trivial to determine in general as it involves considering all possible input distributions.

Definition

Let be a goal distribution. We say that is fair if, for every with and , there exists an action such that .

In other words, we rule out goals where there are outcomes which are not possible to achieve with any non-zero probability.

From here on, we will use for any generic policy which is -restricted.

Theorem 2

Let be any fair goal. Then,
a global minimiser for exists over the set of -restricted policies
we can define an iteration scheme which converges to one of the global minima as for suitable choices of
convergence occurs both in KL divergence and
if is the set of possible actions, then the initial policy is sufficient for the iteration to converge
for this choice of , we have the inequality:

The iteration scheme is defined for by:

This is a Richardson-Lucy^[2] type multiplicative update algorithm. Csiszár and Tusnády, among many others, did early work establishing connections between alternating KL-minimisation and the theory of EM-algorithms, and over the last few decades, this has become a well-known correspondence in information geometry.

In 2022, Aubin-Frankowski, Korba and Léger identified Richardson-Lucy as a type of mirror-descent iteration to prove quantitative error bounds for this algorithm equivalent to our result, though in much more generality. Kunstner, Kumar and Schmidt proved similar results for EM of exponential families in 2021.

Hence, while I've written up a full proof of this theorem in the appendix, I would like to emphasise that its technical content is not novel.

We discuss an example application of this theorem.

Example

Let be a policy which categorises pictures of cats and dogs, where is a picture of a cat (denoted by ) half of the time, and a picture of a dog (denoted by ) the rest of the time. Let represent no information. The policy has three possible actions: to label as cat, to label as dog, and to defer to an existing label which is accurate 100% of time (for some small ). Let be if gets it right, if it gets it wrong, and let the goal be defined by .
For this example, clearly the optimal -restricted policy for minimising the KL divergence to the goal is to always defer to the existing label. Below is a tersely-written proof that the iteration converges to this.
We begin with , which has . Note , so we can simplify the sum over to just one summand. Furthermore, , and:
for , while for :
Hence, if we write , then:
We deduce that for all , with:
Therefore, for , both and converge to exponentially in , and since each is a probability mass function, must converge to . By the fourth part, we also have that:

Theorem 2 has a few interesting generalisations and specialisations.

Theorem 2a

Let be any goal, and let be a non-empty set of admissible actions for each . If the policy defined by for all satisfies and for each , then the iteration defined by:
and for all and all converges to a global optimum over the set of all such policies. Furthermore:
where in this inequality, is the optimum over all -restricted policies with actions restricted to for each .

If we aren't interested in information restriction at all, then we can simply set .

Corollary 2b

Let be any goal, and let be a non-empty set of admissible actions for each . If for all satisfies for each , then the iteration defined by:
and for all and for all converges to a global optimum over the set of all such policies. Furthermore:

Here's an example which informally discusses why it might be worth thinking about action restriction.

Example 4

Imagine that is solving a Rubik's cube. Over multiple observations, we find that it can reliably solve the puzzle, never taking more than steps for some .
Now consider an experiment where we artificially restrict from rotating one of the faces clockwise. This shouldn't affect 's ability to solve the Rubik's cube because rotating a face clockwise is functionally equivalent to rotating it anti-clockwise three times. And indeed, if understands this, it should always be able to solve the Rubik's cube in at most steps despite the restriction (obviously this is a very weak upper bound).
We run the experiment, and surprisingly, it turns out that with the restriction, gets completely stuck. It is unable to solve the puzzle more than 10% of the time, and the number of steps it takes conditional on completion averages . So does not understand the dynamics of a Rubik's cube as well as we might have thought.

We will now give a final example to illustrate how the two sets of theorems dovetail together.

Example 5

Suppose is tasked with managing a service with six different fault modes, indicated by which, in order, occur with probabilities . There are five actions which can take to restore the service, with the resolution signature below:
Let be trivial and let the goal be .
Note that every fault mode has at least one action which resolves it. Let be a policy which picks the right action every time. Then, by Corollary 1.1, .
The direct approach to finding would involve solving a tangle of equations, but Theorem 2 makes finding an approximation simple. If we let be the uniform distribution, then we can calculate that:
Hence, . We emphasise that this lower bound can be calculated purely from knowing the dynamics and ; no information about is needed.
We now compare to the Touchette-Lloyd theorem. For our choice of , achieves an entropy reduction of bits. But for , picking achieves a zero-entropy distribution, and so we must have that is (at least) bits. In particular, Touchette-Lloyd at best grants that:
Thus, our method significantly outperforms Touchette-Lloyd for this example, even with a crude approximation.

Conclusion

We proved a generalisation of Touchette-Lloyd for policies which optimise towards a goal distribution in KL divergence. Our investigation yielded two qualitatively different theorems: one which determines a bound given a policy and another which is suitable for a universal lower bound with one unknown, . We noted that this lower bound outperforms the original Touchette-Lloyd theorem in many natural settings. In order to complete the universal bound, we determined a simple way to calculate which also generalises from information restriction to action restriction.

Appendix

In this appendix, we will focus on proving Theorem 2.

Many of the proofs are long, so I will isolate them all in collapsible sections. The proof of Theorem 2 essentially proves all of its claims at once rather than sequentially, so I have decomposed it into several lemmas.

Preliminary note

In the proofs, given a fixed with , we will use functions , which take a policy as input. We define these as:

These satisfy the relation:

so they are the same up to a constant (with respect to ), but it is convenient to use both of them to simplify the notation. The key point to note is that the critical points of and are the same. While trivial, we will use this in the proofs frequently without comment, which some readers may find confusing if they lose track of the notation. We also remark that we have the identity:

which is how we will extend from results about to a theorem about .

Throughout this proof, we fix with , and summands with factors of are ignored.

Lemma 2.1

Let be defined inductively by the following iteration scheme for :
assuming for every with .
Then, for all .

Translation: The iteration scheme above reduces the average conditional loss to the outcome distribution at every iteration.

Proof of Lemma 2.1

Let be any -restricted policy. Then,

We seek to minimise . For each , we have that:

With fixed, this is equivalent to minimising:

as discussed in the preliminary note. We differentiate to find a local minimum. From the expressions above, we find that:

This is a constrained optimisation problem since we wish to find the optimal solution within the simplex, so we use the KKT method. By convexity, every KKT point is globally optimal if it exists. Define the Lagrangian:

where , , and we have the complementary slackness condition . If we differentiate with respect to again, we find that at the minimum of :

By complementary slackness, the LHS is constant across every in the support of . If we sum both sides over weighted by , then we find that:

by complementary slackness again. We now evaluate the LHS.

Therefore, . Hence, at an optimum, for each , we can write:

which suggests the iterative system:

In order for the iteration to be well-defined, we must first justify that is always a probability distribution. But indeed all of the terms above are non-negative, so , and the proof that is similar to work above.

We must also justify that whenever for all . We assumed this for , so it suffices to prove an induction step.

Suppose and . We have that:

Therefore, there exists such that and . Then, given our assumption that ,

and , so this completes the proof by induction.

We may later write:

such that:

Any optimum is a fixed point of this system as implies that either (which in turn implies that ) or that the sum is ; in both cases, we have that .

We will now prove that the iteration scheme is monotonic. Fix . Then, define:

Recall that:

Hence, we have:

For any , by disregarding indices where , we can write:

whence by Jensen's inequality:

For any policy and fixed, consider:

Then, by the above inequality, we find that:

and it is easy to verify that we have equality at .

We bound below by where:

Both terms are dependent on , only the first is dependent on . We try maximising . Note that, from the definition of the iteration:

In particular:

Thus, is a global maximum for , and we are able to determine that:

But and only differ by a constant, so we deduce that:

as required.

Lemma 2.2

There exists a choice of such that has a convergent subsequence with and . In particular, is sufficient.

Translation: If we start with the policy which selects actions uniformly over , no matter the values of , then the iteration converges along a subsequence, and so do the KL divergences.

Proof of Lemma 2.2

Let be the probability simplex for . This is defined as

and it is a compact metric space with the inherited Euclidean topology ().

This is compact, so the sequence must have a convergent subsequence . We will call the limit of this subsequence . (This convergence is pointwise, which is equivalent to convergence in since is finite.)

We claim that for . Recall that:

so it suffices to prove that . But this follows immediately from the fairness of , with which these hypotheses imply that there exists an action such that , and thus that:

as required. By Lemma 2.1, we find that for every :

Hence, note that for any with ,

where . Thus, the KL divergences are uniformly bounded above across all and , which is sufficient to appeal to the continuity of KL divergence when passing to the limit, and so we find that as required.

Lemma 2.3

There exists a global minimiser for . Let any such minimiser be denoted by . If , then for every .

Proof of Lemma 2.3

Firstly, a global optimum exists because is lower semi-continuous, is compact, and is not identically on (as demonstrated by ). Hence, write for any global optimum.

Let be such that . Then, by the KKT conditions:

Therefore, there must exist a pair satisfying all of , and . By the same argument as in Lemma 2.1, implies that for every , which in turn implies for every . Finally, by induction on the relation:

we deduce that for every .

To summarise, we have shown that . This is sufficient to conclude that for every .

We now complete the proof of Theorem 2.

Proof of Theorem 2

For any , consider:

This is valid because and must imply that since . When or , we can simply ignore the summand.

Recall that for every with :

Therefore, for all such , we can treat the summands as weights for Jensen's inequality to deduce that:

Note that:

Therefore,

where we observe that the values of for which Jensen's inequality was not applicable vanish because they satisfy .

But we also have that:

(Note: the LHS is well-defined since both terms are finite by Lemma 2.3.)

Thus, we deduce the inequality:

This is known as a Bregman–Fejér inequality. By telescoping, we find that:

But we proved in Lemma 2.2 that . Therefore , and the subsequential limit is in fact a global optimiser.

Thus, we replace with in all of the results above. We have that:

In particular, is a decreasing sequence of real numbers. But along the subsequence , we have that . Therefore,

and we establish the convergence of in KL. Now, by Pinsker's inequality:

so we also deduce the convergence of to the global optimum in .

With the work above, we have proved (1), (2) and (3). Finally, we prove (4).

Since is a decreasing sequence, for any , we have that:

noting that is the uniform distribution on . Without an explicit lower bound on , we nonetheless deduce that:

We are almost done; we must now simply lift our results from to proper. But the extension follows immediately since and the choices of are independent across . Therefore, this completes the proof.

References

On Information and Sufficiency (Kullback, Leibler)
Information-theoretic approach to the study of control systems (Touchette, Lloyd)
Elements of Information Theory (Cover, Thomas)
Information Geometry and Alternating Minimization Procedures (Csiszár, Tusnády)
Bayesian-Based Iterative Method of Image Restoration (Richardson)
An iterative technique for the rectification of observed distributions (Lucy)
Homeomorphic-Invariance of EM: Non-Asymptotic Convergence in KL Divergence for Exponential Families via Mirror Descent (Kunstner, Kumar, Schmidt)
Mirror Descent with Relative Smoothness in Measure Spaces, with application to Sinkhorn and EM (Aubin-Frankowski, Korba, Léger)
Maximum Likelihood from Incomplete Data via the EM Algorithm (Dempster, Laird, Rubin)
Maximum likelihood reconstruction for emission tomography (Shepp, Vardi)
Convex Optimisation (Boyd, Vandenberghe)

^{^}
The result we refer to is Theorem 11 in the paper. It is also explained here.
^{^}
Richardson and Lucy both discovered the same algorithm independently.

7

Goal-directed optimisation requires information about the world

7

Prerequisites

Introduction

Notation

First Theorem

Second Theorem

Conclusion

Appendix

References

7

7