I'm on my way to an important meeting. Am I worried? I'm not worried. The presentation is on my laptop. I distinctly remember putting it there (in the past), so I can safely predict that it's going to be there when I get to the office (in the future) - this is how well my laptop carries information through space and time.

My partner has no memory of me copying the file to the laptop. For her, the past and the future have mutual information: if Omega assured her that I'd copied the presentation, she would be able to predict the future much better than she can now.

For me, the past and the future are much less statistically dependent. Whatever entanglement remains between them is due to my memory not being perfect. If my partner suddenly remembers that she saw me copying the file, I will be a little bit more sure that I remember correctly, and that we'll have it at the meeting. Or if somehow, despite my very clear mental image of copying the file, it's not there at the meeting, my first suspicion will nevertheless be that I hadn't.

These unlikely possibilities aside, my memory does serve me. My partner is much less certain of the future than me, and more to the point, her uncertainty would decrease much more than mine if we both suddenly became perfectly aware of the past.

But now she turns on my laptop and checks. The file is there, yes, I could have told her that. And now that we know the state of my laptop, the past and the future are completely disentangled: maybe I put the file there, maybe the elves did - it makes no difference for the meeting. And maybe by the time we get to the office a hacker will remotely delete the file - its absence at the meeting will not be evidence that I'd neglected to copy the file: it was right there! We saw it!

(By "entanglement" I don't mean anything quantum theoretic; here it refers to statistical dependence, and its strength is measured by mutual information.)

The past and the future have mutual information. This is a necessary condition for life, for intelligence: we use the past to predict and plan for the future, and we couldn't do it if it were useless.

On the other hand, the future is independent of the past given the present. That's not profound metaphysics, that's simply how we define the state of a system: it's everything one needs to know of the past of the system to compute its future. The past is gone, and any information that it had on the future - information we could use to predict and make a better future - is inherited by the present.

But as limited agents inside the system, we don't get to know its entire state. Most of it is hidden from us, behind walls and hills and inside skulls and in nanostructures. So for us, the past and the future are entangled, which means that by learning one we could reduce our uncertainty about the other.

In control theory, memoryless agents have an unchanging internal structure, unable to entangle with the past and carry information useful for the future. Instead they react to whatever last input they received, like a function. These degenerate agents have an internal memory state M_t that depends only on the most recent observation O_t:

Figure 1: Dynamics of a memoryless reinforcement learning agents

W_t is the state of the world outside the agent at time t, O_t is the observation the agent makes of the world, M_t is the resulting internal state of the agent, and A_t is the action the agent chooses to take.

When a LED observes voltage, it emits light, regardless of whether it did so a second earlier. When the LED's internal attributes entangle with the voltage, they lose all information of what came before.

When the q key on a keyboard is pressed and released, the keyboard sends a signal to that effect to the computer, and that signal is mostly independent of which keys were pressed before and in what order (with a few exceptions; a keyboard is not entirely memoryless). A keyboard gets entangled with vast amounts of information over the years, but streams it through and loses almost any trace of it within seconds.

For a memoryless agent, all of the information between past and future flows through the environment outside the agent - through W_t. The world sans agent retains all the power to disentangle the past and the future: you can check in the graphical model in Figure 1 that W_t-1 and W_t+1 are independent given W_t.

The internal state M_t of the memoryless agent, on the other hand, of course reveals nothing about the link between past and future. Looking at my keyboard, you can't tell if I copied the presentation to my laptop, and if it's going to be there in half an hour.

Intelligent agents need to have memory:

Figure 2: General dynamics of a reinforcement learning agent

Now control over the flow of information has shifted, to some extent, in favor of the agent. The agent has a much wider channel over which to receive information from the past, and it can use this information to recover some truths about the present which aren't currently observable.

The past and the future are no longer independent given W_t alone, you need M_t and W_t together to completely separate the past and the future. An agent with memory of how W_t came to be can partly assume both roles, thus making itself a better separator than its memoryless counterpart could.

So here's how to become a good separator of past and future: remember things that are relevant for the future.

Memory is necessary for intelligence, you already knew that. What's new here is a way to measure just how useful memory is. Memory is useful exactly to the extent to which it shifts the power to control the flow of information.

For the agent, memory disentangles the past and the future. If you maintain in yourself some of the information that the past has about the future, you overcome the limitations of your ability to observe the present. I know I put the presentation on my laptop, so I don't need to check it's there.

For other agents, at the same time, the agent's memory is yet another limitation to their observability. Think of a secret handshake, for example. It's useful precisely because it predicts (and controls) the future for the confidants, while keeping it entangled with the hidden past for everyone else.

Continue reading: How to Be Oversurprised 

Followup to: The Bayesian Agent

This post explains one interesting and influential algorithm for achieving high utility of the actions of a Bayesian agent, called Point-Based Value Iteration (original paper). Its main premise resembles some concept of internal availability.

A reinforcement-learning agent chooses its actions based on its internal memory state. The memory doesn't have to include an exact account of all past observations - it's sufficient for the agent to keep track of a belief of the current state of the world.

This mitigates the problem of having the size of the memory state grow indefinitely. The memory-state space is now the set of all distributions over the world state. Importantly, this space doesn't grow exponentially with time like the space of observable histories. Unfortunately, it still has volume exponential in the number of world states.

So we moved away from specifying the action to take after each observable history, in favor of specifying the action to take in each belief state. This was justified by the belief being a sufficient statistic for the world state, and motivated by the belief space being much smaller (for long processes) than the history space. But for the purpose of understanding this algorithm, we should go back to describing the action policy in terms of the action to take after each observable history, π(A_t|O₁,...,O_t).

Now join us as we're watching the dynamics of the process unfold. We're at time t, and the agent has reached Bayesian belief B_t, the distribution of the world state to the best of the agent's knowledge. What prospects does the agent still have for future rewards? What is its value-to-go of being in this belief state?

If we know what action the agent will take after each observable history (if and when it comes to pass), it turns out that the expected total of future rewards is linear in B_t. To see why this is so, consider a specific future (and present):

w_t, o_t, a_t, w_t+1, o_t+1, a_t+1, ..., w_n, o_n, a_n

The reward of this future is:

R(w_t,a_t) + R(w_t+1,a_t+1) + ... + R(w_n,a_n)

The probability of this future, given that the agent already knows o₁,...,o_t, is:

B_t(w_t)·π(a_t|o₁,...,o_t)·p(w_t+1|w_t,a_t)·σ(o_t+1|w_t+1)·π(a_t+1|o₁,...,o_t+1)···

···p(w_n|w_n-1,a_n-1)·σ(o_n|w_n)·π(a_n|o₁,...,o_n)

We arrive at this by starting with the agent's belief B_t, which summarizes the distribution of w_t given the observable history; then going on to multiply the probability for each new variable, given those before it that have part in causing it.

Note how B_t linearly determines the probability for w_t, while the dynamics of the world and the agent determine the probability for the rest of the process. Now, to find the expected reward we sum, over all possible futures, the product of the future's reward and probability. This is all linear in the belief B_t at time t.

If the value of choosing a specific action policy is a linear function of B_t, the value of choosing the best action policy is the maximum of many linear functions of B_t. How many? If there are 2 possible observations, the observable history that will have unfolded in the next n-t steps can be any of 2^n-t possible "future histories". If there are 2 possible actions to choose for each one, there are 2^2n-t possible policies. A scary number if the end is still some time ahead of us.

Of course, we're not interested in the value of just any belief, only of those that can actually be reached at time t. Since the belief B_t is determined by the observable history o₁,...,o_t, there are at most 2^t such values. Less scary, but still not practical for long processes.

The secret of the algorithm is that it limits both of the figures above to a fixed, manageable number. Suppose that we have a list of 100 belief states which are the most interesting to us, perhaps because they are the most likely to be reached at time t. Suppose that we also have a list Π_t of 100 policies: for each belief on the first list, we have in the second list a policy that gets a good reward if indeed that belief is reached at time t. Now what is the value, at time t, of choosing the best action policy of these 100? It's the maximum of, not many, but |Π_t|=100 linear functions of B_t. Much more manageable.

Ok, we're done with time t. What about time t-1? We are going to consider 100 belief states which can be reached at time t-1. For each such belief B_t-1, we are going to consider each possible action A_t-1. Then we are going to consider each possible observation O_t that can come next - we can compute its probability from B_t-1 and the dynamics of the system. Given the observation, we will have a new belief B_t. And the previous paragraph tells us what to do in this case: choose one of the policies in Π_t which is best for B_t, to use for the rest of the process.

(Note that this new B_t doesn't have to be one of the 100 beliefs that were used to construct the 100 policies in Π_t.)

So this is how the recursive step goes:

• For each of 100 possible values for B_t-1
  • For each possible A_t-1
    • For each possible O_t
      • We compute B_t
      • We choose for B_t the best policy in Π_t, and find its value (it's a linear function of B_t)
    • We go back and ask: how good is it really to choose A_t-1? What is the expected value before knowing O_t?
  • We choose the best A_t-1
  • This gives us the best policy for B_t-1, under the restriction that we are only willing to use one of the policies in Π_t from time t onward
• After going over the 100 beliefs for time t-1, we now have a new stored list, Π_t-1, of 100 policies for time t-1.

We continue backward in time, until we reach the starting time t₀, where we choose the best policy in Π_t0 for the initial (prior) belief B_t0.

We still need to say how to choose those special 100 beliefs to optimize for. Actually, this is not a fixed set. Most point-based algorithms start with only one or a few beliefs, and gradually expand the set to find better and better solutions.

The original algorithm chooses beliefs in a similar way to an internal availability mechanism that may be responsible for conjuring up images of likely futures in human brains. It starts with only one belief (the prior B_t0) and finds a solution where only one policy is allowed in each Π_t. Then it adds some beliefs which seem likely to be reached in this solution, and finds a new and improved solution. It repeats this computation until a good-enough solution is reached, or until it runs out of time.

Point-based algorithms are today some of the best ones for finding good policies for Bayesian agents. They drive some real-world applications, and contribute to our understanding of how intelligent agents can act and react.

Edit: Following mixed reception, I decided to split this part out of the latest post in my sequence on reinforcement learning. It wasn't clear enough, and anyway didn't belong there.

I'm posting this hopefully better version to Discussion, and welcome further comments on content and style.

The availability heuristic seems to be a mechanism inside our brains which uses the ease with which images, events and concepts come to mind as evidence for their prevalence or probability of occurrence. For this heuristic to be worth the trouble it causes, there needs to be a counterpart, a second mechanism which actually makes things available to the first one in correlation with their likelihood. In this post I discuss why having such an internal availability mechanism can be a good idea, and outline some of the ways it can fail.

You're playing Texas Hold'em poker against another player, and she has just bet all her chips on the flop (the 2nd of 4 betting rounds, when there are 2 more shared cards to draw). You estimate that with high probability she has a low pair (say, under 9) with a high kicker (A or K, hoping to hit a second pair). You hold Q-J off-suit. Do you call?

One question this depends on is: what's the probability p that you will win this hand? An experienced player will know that your best hope is to hit a pair, without the other player hitting anything better than her low pair. This has probability of slightly less than 25%.

We could compute or remember a better estimate if we notice the probability of runner-runner outs, but is it worth it? It won't help us pin down p with amazing accuracy - we could be wrong about the opponent's hand to begin with. And anyway, the decision of whether to actually call depends on many other factors: the sizes of your stack, her stack, the blinds and so on. A 1% error in the estimate of the win probability is unlikely to change your decision.

So instead of pointlessly trying to predict the future to an impossible and useless degree of accuracy, what we did was tell ourselves a bunch of likely stories about what might happen, then combine these scenarios into a simple probabilistic prediction of the future, and plan as best we can given this prediction.

This may be the mechanism that makes the availability heuristic a smart choice. The main observed effect of this heuristic is that past (subjective) prevalence seems to be highly linked to future predictions. Patches of stories we've heard may even work their way into the stories we tell of the future. The missing link is an internal availability mechanism which chooses which patches to make available for retelling. We seem to use such a mechanism to identify likely outcomes; before we forward them to the more commonly discussed process which integrates these stories of the future into a usable prediction.

What events would be good candidates for becoming available? One thing to notice is that evaluation of the expected value of our actions depends both on the probability and on the impact of their results; but for each specific future we don't need both these numbers, only their product. If the main function of the internal availability mechanism is to predict value, rather than probability, it stands to reason that high-impact but improbable outcomes will become as available as mundane probable ones. Yes, concepts which were encountered most often in the past, in a context similar to the current one, come to mind easily. But one-in-a-hundred or -thousand outcomes should also become available if they are very important. One-in-a-million ones, on the other hand, are almost never worth the trouble.

If something similar is indeed going on in our brains, then it seems to be working pretty well, usually. When I walk down the street, I give no mind to the possibility that there are invisible obstacles in my way. It is so remote, that even if I took it into account with adequately small probability, my actions would probably be roughly the same. It is therefore wise not to occupy my precious processing power with such nonsense.

Even when the internal availability mechanism is working properly, it generates unavoidable errors in prediction. Strictly speaking, ignoring some unlikely and unimportant possibilities is wrong, however practical. And while it makes noticing things evidence for their higher probability, this heuristic could sometimes fail, particularly if the internal availability mechanism is built for utility but used for probability.

The mechanism itself can also fail. Availability doesn't seem to be binary, so one type of failure is to make certain scenarios over- or under-available, marking them as more or less likely and important than they are. There also appears to be some threshold, some minimal value for non-zero availability. Another type of failure is when an important outcome fails to meet this threshold, not becoming available.

Or perhaps an unlikely future becomes available even though it shouldn't. This may explain why people are unable to estimate low probabilities. In their mind, the prospect of winning the lottery and becoming millionaires creates a vivid image of an exciting future. It's so immersive, that it really appears to be a real possibility - it could actually happen!