Let’s split out two different types of optimization. The first type includes things like Google Maps’ pathfinder, a human making a plan, or Amazon’s logistical algorithms. The second type includes things like a thermostat, a heat-seeking missile, or water flowing downhill.
The distinction I want to point to here is where the things-we’re-optimizing-over live. For the first type, optimization is over things-in-a-model; a search algorithm runs on a map. For the second type, optimization is over things-in-the-world; a search algorithm runs on the territory directly. Search-in-map vs search-in-territory.
Same Algorithm, Different Inputs
A toy example: suppose we have a big pile of rocks, and we want to find the rock whose mass is closest to the mass of a reference weight (without going over).
A search-in-territory algorithm might use one of those old-school balance-scales to compare masses pairwise. We could pull each rock out of the pile one-by-one, and:
- First, compare the rock to the reference weight. If it’s heavier, throw it away and move on to the next rock.
- Second, compare it to the best rock found thus far, and replace the best rock with this one if it’s heavier.
At the end, we’ll have chosen the best rock.
A search-in-map algorithm might instead start by weighing the reference weight and each rock on a scale, and entering all the masses into a spreadsheet. But then, it could proceed exactly like the search-in-territory algorithm. It would run through the list of rock-masses one-by-one, and:
- First, compare the rock-mass to the reference mass. If the rock-mass is larger, move on to the next one.
- Second, compare the rock-mass to the best rock-mass found thus far, and replace the best rock-mass with this one if it’s larger.
At the end, there is one extra step: we have to go back out into the world and find the actual rock with the best mass. Note that this could be nontrivial, if we didn’t label or organize our rocks in the process of weighing them.
Key point of this example: these two types of optimization need not involve different algorithms. In practice they often do - things we typically think of as “search algorithms” tend to be used more for search-in-map, and things we typically think of as “controllers” tend to be used more for search-in-territory. But in principle, one can often apply the algorithms opposite their usual context.
When Should Search-In-Map Be Favored?
I see two main features of search-in-map which aren’t (typically) shared by search-in-territory:
- The map-making process can use information before the search process “knows what to do with it”. For instance, in the rock-pile example, we could weigh all the rocks before we gain access to the reference rock, or even before we know what the task is at all.
- The map itself can use a convenient representation or data structure - e.g. indexes, caching, sorted lists, etc.
These features can sometimes be replicated to some extent in the territory - e.g. we could weigh all the physical rocks and store them in sorted order before gaining access to the reference weight. But this only works when we have lots of control over the physical system, and can arrange it how we please. A map can pretty much always be arranged how we please.
Key point: if we can use information to build a map before we have full information about the optimization/search task, that means we can build one map and use it for many different tasks. We can weigh all the rocks, put that info in a spreadsheet, then use the spreadsheet for many different problems: finding the rock closest in weight to a reference, finding the heaviest/lightest rock, picking out rocks which together weigh some specified amount, etc. The map is a capital investment.
A more typical example: creating a streetmap is expensive. If we just want to figure out one shortest path, then directly measuring physical distances along a bunch of paths might be faster. But once the streetmap is created, it can be used repeatedly by lots of different people for lots of different pathfinding problems.
When Should Search-In-Territory Be Favored?
The key feature of search-in-territory is that it does not require making a map - and therefore requires no extra information or assumptions beyond what the algorithm itself uses.
In the rock-pile example, the search-in-territory uses only pairwise comparisons between weights - i.e. a balance scale. We never actually know the mass of any particular rock. The search-in-map, on the other hand, relies on direct measurements of mass. To perform the search-in-map with only a balance scale, we’d either need to compare all pairs of weights ahead of time (which would mean effort), or we’d need to run out and compare physical weights in the middle of the search (at which point we’re effectively back to search-in-territory).
Key point: if we don’t rely on extra information, then we don’t rely on extra assumptions; there are no extra sources of error. In the rock-pile search-in-map example, error could come from the scale becoming uncalibrated as we proceed through the rocks, or from insufficient precision in the measured masses, or from data corruption in the spreadsheet, or from failing to connect the search result to the right physical rock at the end. We have to assume that we correctly understand each of those pieces. For the search-in-territory version, we only need to assume that the balance scale works correctly.
A more typical example: many feedback controllers work well even when our model of the system’s dynamics isn’t quite correct.
How Does This Compare To Selection Vs Control?
Abram’s Selection vs Control offers a similar distinction between two kinds of optimizers. “Selectors”, in his breakdown, directly instantiate and compare objects in the search space. There’s an explicit space of “options” or “possibilities” over which the search operates. This includes all of the search-in-map examples from earlier, but also biological evolution.
“Controllers” don’t necessarily have that explicit search-space - they tend to operate directly on the external world. “Other possibilities” for a controller would mean other counterfactual worlds, which aren’t necessarily unambiguously defined. This includes all of the search-in-territory examples from earlier.
I claim that search-in-territory vs search-in-map is usually the right distinction to think about when considering the intuitive selection vs control clusters. The main reason is that counterfactuals always live in a model. An objectively defined “search space” exists only in a model.
There are cases where certain search spaces/counterfactuals seem particularly natural. For instance, in the case of biological evolution, it seems natural to consider the space of DNA sequences. But remember that evolution does not “actually search” this space - it only samples a relatively-small chunk of the exponentially large space of sequences.
Conversely, there are cases where we think of a search-in-territory as having some search space. For instance, an optimal controller might minimize some expected “cost” under some model of the system under control, but without explicitly representing that map or optimizing over it.
Why Does This Matter?
As with the selection-vs-control distinction, it intuitively feels like search-in-map is “more powerful” than search-in-territory; it looks less like a thermostat and more like an agent. But if they both do optimization (i.e. they both steer certain parts of the universe into a smaller set of states, which is equivalent to expected utility maximization in a God's-eye model), then what’s the difference?
The discussion above suggests one possible answer: maps generalize. This connects to the (Improved) Good Regulator Theorem: a system “should” use an efficient internal map when it “doesn’t know what game it’s playing” until later. In that case, we need to keep around useful information, but we still want to compress and precompute where possible.
Then the interesting question is: how do we recognize a map embedded in the territory, or a search algorithm running on such a map?