Proof Explained: Touchette-Lloyd Theorem

This is a sequel to our previous post on the Touchette-Lloyd theorem^[1]. The previous post contained some introductory material and motivation for the theorem. Here, we will walk through the proof of the theorem and explore its applications in a few worked examples. It isn’t strictly necessary to read that post before this one, but we recommend it if anything in this post seems unclear or if you would like some more background.

Recap and Setup

The theorem concerns three random variables. These are: the input ‘environment’ variable denoted by , the ‘action’ taken by a policy denoted by , and the output environment variable, denoted by . The environmental output is affected by the action and the initial environmental state. The way in which it is affected is given by expressed by a conditional probability distribution , which we will refer to as the ‘dynamics’ of the system. If is equal to either 0 or 1 for all values of then we will say that the dynamics is deterministic, but we will also allow for stochastic dynamics. As is standard, we will denote specific values that the random variables can take using lower case (eg. are values which can take, are values which can take). The variables and both represent the state of the ‘environment’ at different times (before and after the ‘action’ is taken). They will therefore both have the same domain (set of possible values) but we will nonetheless use (as opposed to ) to denote -values to avoid confusion over variables.

The way in which the action variable depends on the input environmental state is called the ‘policy’. The theorem concerns the comparison of two classes of polices: ‘Blind’ policies where the action cannot depend on (or ‘see’) the environmental state and ‘sighted’ policies where the action taken can depend on . ^[2] These policies can be represented by Bayes nets:

The theorem statement is the inequality

which relates the entropy change for a sighted policy with mutual information between the environment and action to the maximum possible entropy change achievable for a blind policy .

The Proof

We will use the subscript to indicate a blind policy (so is the environmental output for a blind policy, is the action variable for a blind policy). First, let us look at what the output distribution looks like for a blind policy. The dynamics is fixed and and are independent so the probability distribution over will be

Let us consider the performance of a policy like this in producing a distribution with a low final entropy. In particular, we can quantify this using the difference between the initial environmental entropy and the final environmental entropy :

Quantifying entropy reduction in this way is intuitive and captures the fact that (other things being equal) it is more impressive for a agent or controller to achieve a low output entropy from a high starting entropy than to start with a low entropy and maintain it.

For any given initial distribution, there is a maximum which can be achieved using a blind policy, but depends on the initial distribution. Consider the set of all possible initial probability distributions , that is, all distributions over the state space containing , … etc. For each there is a ‘best’ which can be achieved using a blind policy and cannot be surpassed by another blind policy acting on the same input distribution. Furthermore, there is some combination of initial distribution and policy which achieves a value of such that there is no other combination of blind policy and initial distribution which achieves a greater . Let this optimal value of achievable by a blind policy be labelled :

where is the set of all distributions over actions which correspond to blind policies.

We can ask: is there a combination of initial distribution and sighted policy which can outperform this value of ? And if so, by how much does it outperform this value? We will answer this question by investigating some general properties of sighted policies.

For a general ‘sighted’ policy, the action will depend on the environmental state , so the output distribution will include this dependency

Notice that we can use Bayes rule to re-write the conditional probabilities relating and . In particular, we can write

where

Note that this doesn’t imply that the causal relationship between and has changed. We are still considering the case where the policy changes its action depending on what environmental state it ‘sees’. We are just re-writing the probabilities.

Substituting this back in and rewriting the order of things, we can write the output distribution for a general policy as

Notice that this is a weighted average over probability distributions for each -value. If we consider only the cases where the action taken is one particular -value, say , we can obtain a conditional probability distribution over :

Interestingly, (and this is the key insight of the proof) we can think of this conditional output distribution for a sighted policy as the output distribution of a blind policy which always selects acting on an input distribution ^[3]. This means that the difference between the entropy of and is upper bounded by the blind policy entropy reduction . We can therefore write

Furthermore, since was arbitrary, this inequality holds for every possible -value, meaning that we can sum over the -values used by the sighted policy, weighted by :

Recall the definition of conditional entropy which allows us to write:

This allows us to simplify this equation and obtain

To turn this bound on conditional entropies into a bound on for a general policy, we can add the entropy of the initial distribution to both sides and re-arrange to obtain:

Now, note two things. First, since , we can write

Second, note that , the difference between the entropy of and the entropy of , conditional on , is the definition of the mutual information between and so . Combining these two observations, we arrive at the following inequality relating the entropy reduction achievable through sighted policies to the blind entropy reduction:

which is the result!

What does this result tell us?

From the point of view of the agent structure problem, we can view this result as a selection theorem which tells us that, if we select for (or observe) a policy which achieves an entropy reduction which is greater than then, at minimum, its actions must share an amount of mutual information with the environment.

Examples of different dynamics

To gain some intuition for this result, we will explore its implications through a few examples. These can have very different feels, but in all cases, the dynamics are fully specified by defining the conditional distribution for all and .

1. Entropy decreasing dynamics

First, we will consider an entropy decreasing dynamics. In this example the entropy of the environment will naturally tend to decrease, without help from the policy. A simple example of such a dynamics is one where all input states are mapped to the same output, regardless of the action taken by the policy. If we consider each state to be labelled by a 5-bit string the following probability distribution has this property:

If we only observed environmental states, we would see that regardless of the entropy of the initial distribution over input strings, the output distribution would have zero entropy. Naively, one might attribute this entropy reduction to an effective policy using information about its environment. But in fact, the entropy reduction is a property of the environmental dynamics, not the policy. This can be seen by the fact that no policy, blind or sighted, can achieve a greater entropy change than that achieved by a blind policy. For this dynamics, , and no policy can achieve a greater entropy reduction. In this sense, tells us the the degree to which the environment itself contains entropy-reducing dynamics. We can see a slightly more subtle example of this by considering the following environmental dynamics

In words: the output state is equal to the input state, unless the action taken is , in which case the output state is . This dynamics contains two subdynamics: one (where ) which is entropy preserving and one (where ) which is entropy decreasing. A blind policy can guide the dynamics to become entropy decreasing (by picking ) and thus achieve maximal entropy reduction without requiring knowledge of the input state. In this sense, again captures the entropy-reducing qualities present in the environment itself, as opposed to the entropy-reducing qualities of a policy.

2. Entropy non-increasing dynamics

Let’s return to the example given in the previous post, where the policy has to guess the correct 5-bit string. The dynamics of this example is deterministic and characterised by the following conditional probabilities

In words: the output state is if the action picked has the same string as the input state. Otherwise the output state is the same as the input state.

First, we will find . We do this by finding a blind policy and input distribution which maximizes the change in entropy between the input distribution and the output distribution. Note that the only way that a policy can reduce the entropy is to guess the correct string and that randomizing which string is guessed can do no better than picking the same (highest probability) string each time. Furthermore, the dynamics are symmetric with respect to all strings except 00000 so without loss of generality, we can assume that the best blind policy involves picking the string with probability one. Now, we need to find which input distribution maximizes for this policy.

First note that if is restricted to only having nonzero probabilities over and , then the final distribution will always have zero entropy. Therefore, in this restricted case, the maximum entropy reduction is achieved when the input distribution has maximum entropy (ie. which has 1 bit of entropy). This leads to an entropy reduction of 1 bit. We will now show that this distribution is in fact optimal and .

Note also that the above argument can be extended to show that, for any initial distribution, the blind policy will always achieve a greater entropy reduction when the probabilities of 00000 and 11111 are equal compared to when they are not.

Now, notice that any input distribution can be viewed as a mixture between a distribution over the domain which we will call and some other distribution over a domain not including 00000 and 11111 which we will call . Thus we can write the optimal input distribution as:

where is the optimal distribution over and is a ‘mixing probability’. Since this distribution is a mixture of two distributions over non-overlapping domains, its entropy is given by:

where is the binary entropy of the mixing constant (a nice proof of this fact can be found here).

Now let us consider the output entropy for this distribution, under a blind policy. With probability , the output will be 00000, since any result in the domain will be mapped to 00000. We will call this outcome which has zero entropy so . With probability , the output will be a random variable from the distribution . The entropy of the total output can similarly be thought of as a mixture of non-overlapping distributions meaning that we can write it as

By subtracting from we can find the change in entropy between input and output:

The terms involving distributions over the domain excluding cancel out. Therefore, the blind entropy reduction is maximized by setting and as a maximum entropy distribution over the domain. We have therefore proved that . This means that if we observe a policy achieving an entropy reduction of greater than 1 bit on some input policy, we know that policy must be sighted-its actions must have some mutual information with the environmental state. In practice, this means that the policy must be taking in information about the environmental state.

Suppose we now observed a policy which achieved an output entropy of 2.83 bits when fed a maximum entropy input distribution with bits. Armed with the Touchette-Lloyd theorem, what can we deduce about this policy?

The entropy reduction achieved by this policy is bits. Since the inequality tells us

this means that our policy must have at least bits of mutual information with the environment. In fact, the policy which achieves this entropy change is the policy described in the first post, in the section titled ‘A Formal Example’. This policy takes the first four bits of the environmental state (and then selects the action where are the first four bits of ) and thus has four bits of mutual information. This example raises an important point about the Touchette-Lloyd inequality which is that while it is true (4 bits is indeed greater than 1.17 bits) it doesn’t always saturate. It would be nice if we could get a higher lower bound on the mutual information. There are two related ways to use the inequality to tighten the bound.

First, note that in the derivation of the inequality, we used the fact that , so unless we have a situation where , we cannot expect the bound to be tight. In a step near the end of our derivation, we obtained the inequality

Since , we can use this to obtain a tighter bound:

In our case, while , we have . This is because we can tell the first four bits of by looking at . For a uniform input distribution, given , the probability and . Using and yields the improved bound

So in fact, we can improve on the bound provided by the original Touchette-Lloyd inequality, provided that we are willing to replace with the slightly less intuitive quantity . However, the advantage of using the inequality in terms of is that knowing involves only observing changes in the environment and does not presume knowing all the actions which the policy takes. After all, if you already know what actions a policy is taking, you can probably calculate the mutual information already. From a selection theorem point of view we are more interested in inferring that a policy is using information from its environment by observing the changes in the environment.

Another way to increase the lower bound on is to observe the policy for different initial distributions. For example, if the policy was run on a distribution which was uniform over all 5-bit strings which end in ‘1’ then the initial entropy would be bits but the policy would reduce the final entropy to , achieving . When plugged into the Touchette-Lloyd inequality (along with ) this would give a lower bound of 3 bits on the mutual information which is much tighter than the ‘unoptimized’ value of 1.17 bits (recall, the true mutual information between the action and environment for this policy is 4 bits).

3. Entropy increasing dynamics

We described the dynamics above as ‘entropy non-increasing’, since it is impossible for any policy to lead to an output distribution with a higher entropy than the input. We can also consider dynamics where entropy can increase and a policy has to be more proactive in fighting this entropy increase.

Consider the following dynamics, again in a situation where both environmental state and the action are described by 5-bit strings. If the action matches the environmental state (ie. if ), then the output environmental state is . On the other hand, if the action does not match the state (ie. if ) then is drawn from a uniform distribution over all 5-bit strings excluding 00000. This has dynamics corresponding to the following distribution

Using a similar argument to the one in the previous section, we can find that the maximum blind policy entropy change is 0 bits, achieved when the initial distribution (and the corresponding action string) is completely concentrated on one environmental state. This is because any initial distribution which allows the policy to guess wrong will be punished by a high-entropy final state leading to a negative .

Consider the sighted policy from the previous section which can ‘see’ the first four bits and chooses the action in this new environment. For a uniform initial distribution, this leads to a final distribution with and for strings . This output distribution has an entropy of so , leading to the lower bound on the entropy of .

Similarly to the previous section, we can improve on this bound by changing the initial distribution. If we consider the case where the initial distribution is over all strings which end in the bit ‘1’ then this sighted policy chooses the correct action every time and reduces the final entropy to zero. This corresponds to . Since , this gives us the bound . Recall that this policy does indeed have 4 bits of mutual information with the environment, so this bound cannot be improved upon.

Moving to an environment which was more hostile to entropy reduction leads to a greater discrepancy between blind and sighted policies, this in turn allows the bound on mutual information provided by the Touchette-Lloyd inequality to be made tighter than in the ‘entropy non-increasing’ environment of the previous example.

Incidentally, this environment also highlights why, when calculating , the maximum must be taken over all initial distributions. It would be convenient if the inequality was true but was instead defined as the maximum change in entropy achievable for a blind policy with the same initial distribution as the term in the inequality. But this is not the case, instead is defined as the maximum entropy change achievable for a blind policy over any initial distribution. We can see why this must be the case by considering this environment.

If the initial distribution has intermediate entropy (ie. nonzero but not maximal) , then a sighted policy can achieve a zero entropy final distribution if it has full knowledge of the environmental state, meaning . A blind policy acting on this initial distribution will, most of the time guess the incorrect action to take, leading to the final state being drawn from an almost maximum entropy distribution. This can lead to the maximum blind policy entropy change being negative, (ie. the final distribution has a larger entropy than the initial distribution) for intermediate entropy distributions. If we define to be the maximum entropy change for a blind policy acting on an initial distribution and consider the for a sighted policy acting on the same initial distribution we might conjecture the following inequality

(NOTE: THIS INEQUALITY IS NOT TRUE!)

But we have just argued that a sighted policy can achieve using mutual information and that can be negative for the same initial distribution. Therefore the above inequality cannot hold.

On the other hand, if we define in the way that Touchette and Lloyd do, as the maximum blind entropy change achievable over all input distributions, then we can note that for a zero entropy initial distribution (ie. one where only takes a single value), a blind policy can achieve a zero entropy output distribution by choosing the correct action 100% of the time. This means that while was negative will equal zero, making the inequality valid. Understanding the slightly unintuitive way that is defined is important for using the Touchette-Lloyd theorem. We highlight this here as it was something that we took a long time to properly appreciate.

Conclusions & Further Work

We hope that the Touchette-Lloyd theorem is clear to you after reading this. We think that it is pretty interesting result from an Agent Foundations point of view and are interested in seeing if we can extend it. We have some ideas for a few avenues for further research.

• Re-frame the result using expected utility. Reducing entropy and maximizing expected utility are (in some regards) similar in that they are both forms of optimization. If one policy achieves a particular expected utility (for some utility function over ) can we ascribe some lower bound on the mutual information between its actions and the environmental state?

• Extend the result to a non-Markovian environment. We assumed here that the environment was Markovian so that X could be treated as a random variable independent of its previous value. But most interesting environments do not have this property. Does a similar result hold when a policy must ‘remember’ previous environmental states to choose optimally at a given timestep?

• Policies which ‘model’ the dynamics, not just the state. The Touchette-Lloyd theorem broadly tells us when a policy has ‘knowledge’ of the environmental state. But having mutual information between the state and does not necessarily imply successful entropy reduction. In order to successfully reduce entropy, one must also choose actions which are appropriate for the dynamics of the environment. Can we prove a similar which captures whether a policy is modelling the dynamics of the system?

• Prove an equivalent result using K-complexity. Entropy reduction is one hallmark of an optimizer. But if a system reduces in complexity or description length, it could also reasonably be said to be ‘being optimized’. Can we prove a similar theorem involving the reduction of K-complexity, instead of entropy?

1. ^

   That is, theorem 10 from the paper Information-theoretic approach to the study of control systems.

2. ^

   In control theory terminology, these families of policies are known as ‘open loop’ and ‘closed loop’ respectively. But as a personal preference we find the names ‘blind’ and ‘sighted’ more evocative so we will use them instead.

3. ^

   Touchette and Lloyd describe this as “the fact that a closed-loop controller is formally equivalent to an ensemble of open-loop controllers acting on the conditional supports instead of ” (where they are using to represent a specific controller action, equivalent to our )

[XelaP]

In the utility maximization as description length minimization setting, we get something kinda weird:

Say that X, Y are random variables “of the same type” (that is, outcomes are in the same space), and say we fix a distribution M (corresponding to the utility function) over that space. Let be the cross entropy , and likewise . Let and let

Then you get the analogous version of Touchette-Lloyd… except, notice how is actually just equal to ? So you actually just get

that is, you can’t get more improvement than the best blind policy & input distribution gets‽

I sorta suspect it’s just because allowing the input distribution to vary in your maximum is allowing a lot of “cheating”.

As an example, take something like the password example from John’s “How many bits of optimization does one bit unlock” post. Here, the best blind policy is going to “cheat” by imagining that the password was some specific value, and then taking the action that gives that value to the “lock”. So it just says that you can’t do better than if you knew the password.

[Alfred Harwood]

This sounds right. Since expected utility is linear, the expected utility of any policy will be a weighted sum of the expected utilities of all possible (action, initial state) pairs. One of these pairs (call it (a_0, x_0)) will have the highest expected change in utility after going through the dynamics so you can pick the initial input x_0 and have a deterministic blind policy of picking a_0. This will be a blind policy and by definition will have the highest possible change in utility. This isn’t true with entropy since entropy is convex, not linear.

I encountered this issue when trying to prove an equivalent version of the TL theorem for utility maximization, but didn’t get beyond it. Of course, if you can’t choose the input distribution, then having mutual information with the input should still help you maximize your expected utility, but I couldn’t find an elegant/​general way to express this fact!

[XelaP]

My naive attempt to make the algorithmic-information-theory variant of the theorem is (I’m pretty sure) false.

That is: I’m pretty sure there’s some f, A, X such that

Sketch: Given some special A’, X’, define f(X,A) = s if X,A=X’,A’ else X, for some easily compressible s; and require that K(A’) - K(A’|X’) > ϵ. Then if the inputs have less than epsilon of algorithmic mutual information, you’d know you didn’t have the special inputs, and so f would spit out X and thus not reduce the complexity.

If we chose our s so that K(s) < K(X’|A’), then we’ll get a counterexample.

I’m pretty sure you should be able to construct X’, A’ that satisfy those two inequalities, but I was struggling with some of the details.

[XelaP]

Entropy reduction is always bounded by a deterministic policy’s entropy reduction.

In particular, entropy reduction for a blind policy is a convex function on the convex set ΔA of blind policies; so an extreme point will always be a maximum.

Likewise, we can get a weaker form of the bound: ΔH ≤ ΔH_f ≤ Δ H^{max}{blind} + H_f (A)

where f is an optimal (or at least better than the actual policy) sighted deterministic policy, and H_f means we take the entropy under the distribution using f as the policy.

This doesn’t seem to make the proofs easier, but it’s an interesting fact anyways