Toward the unlit corner: exploration without a reward
The problem
Put a child in an unfamiliar playground and they will work their way around it. Not systematically, and not because anybody is handing out points — they go to the thing they have not tried yet, and once they have tried it, it stops being the interesting thing. Come back an hour later and they have covered the place.
Software rarely gets this for free. An agent dropped into an unfamiliar space — a website it has to map, a building it has to survey, a set of configurations it has to characterise — typically either follows a script somebody wrote, or wanders at random. Wandering at random is worse than it sounds: a random walk spends most of its time revisiting, and the bigger the space the more of its time it wastes.
The usual fix is to invent a scoring scheme. Give the agent points for visiting new places, count how often each place has been seen, decay the counts, tune the weights. It works, and every one of those pieces is a knob you now own.
This walkthrough builds the same behaviour out of something the memory already computes for free. Every time you ask a memory a question, it tells you how strongly it recognised what you asked. Walk toward whatever it recognises least and you have directed exploration, with nothing added. At the end you will have measured it against a random walk, and fixed the one bug that makes the naive version go in circles.
You need a running HeatherDB and numpy.
The one number this runs on
When you ask this memory about something, it hands back the closest thing it holds along with how close that was, on a scale where 1.0 means an exact match and near zero means it has nothing like this at all. That number is what lets a memory refuse to answer when it is out of its depth. Read it the other way round — take the smallest one — and it points at whatever the memory knows least about. That is the entire policy.
For this to be more than a visited-or-not flag, nearby places must get similar patterns. If every square of a floor gets an unrelated pattern, then standing on one teaches the memory nothing about the square beside it, and recognition is either 1 or 0 with nothing in between. Instead each square's pattern is built from its coordinates, so that stepping one pace sideways changes it a little and walking across the room changes it a lot.
Step 1 — build patterns that know what "nearby" means
B, RX, RY = unitary("B"), unitary("RX"), unitary("RY")
PLACE = {(x, y): nrm(blend(RX, cpow(B, x)) + blend(RY, cpow(B, y)))
for x in range(M) for y in range(M)}
cpow(B, x) means "walk x steps along this direction", and it accepts
fractions, so the patterns vary smoothly rather than jumping. The two
directions are then labelled as the across-coordinate and the up-coordinate and
added together.
adjacent squares: 0.479 opposite corners: 0.064
Two squares one pace apart overlap about 48%; opposite corners of the floor overlap 6%. Visiting a square therefore makes its neighbours slightly familiar too, which is what turns "least recognised" into a direction to walk in rather than a coin flip between everything unvisited.
Step 2 — store what you see, without letting it blur
def store(coll, seen):
vs = [PLACE[p].tolist() for p in seen]
call(f"/collections/{coll}/bulk_load", {"addresses": vs, "counters": vs})
This is the step that quietly decides whether the agent works. The ordinary
write path folds together entries that resemble each other, which is the
right behaviour when you are accumulating noisy observations of the same thing
and exactly the wrong behaviour here — squares one pace apart resemble each
other by 48%, and they are still two different squares. Put four squares in
each way and ask about a fifth:
visited = [(2,2), (2,3), (2,4), (3,4)]
for how in ("write", "bulk_load"):
coll = f"check_{how}"
call(f"/collections/{coll}", method="DELETE")
if how == "write":
for p in visited: call(f"/collections/{coll}/write", {"vectors": [PLACE[p].tolist()]})
else:
store(coll, visited)
n = call(f"/collections/{coll}/stats", method="GET")["num_locations"]
print(f"{how:10s} 4 squares written -> {n} entries; "
f"a visited neighbour reads {familiarity(coll, [(2,3)])[0]:.2f}, "
f"an unvisited one {familiarity(coll, [(2,1)])[0]:.2f}")
write 4 squares written -> 2 entries; a visited neighbour reads 0.49, an unvisited one 0.48
bulk_load 4 squares written -> 4 entries; a visited neighbour reads 1.00, an unvisited one 0.50
Four squares written; the merging path keeps two entries, and a square the
agent has stood on becomes indistinguishable from one it has never seen — 0.49
against 0.48. The signal the whole agent depends on is gone. bulk_load stores
exactly what you hand it, and the same two squares read 1.00 and 0.50.
Since only a new square changes the memory, the reload happens at most 36 times over a 200-step walk.
Step 3 — walk toward whatever is least familiar
def familiarity(coll, cands):
# Ask about all reachable squares at once; keep the strongest match each got.
r = call(f"/collections/{coll}/batch_analyze",
{"queries": [PLACE[c].tolist() for c in cands], "strategy": "fast"})["results"]
return [a["activated_locations"][0]["similarity"] if a["activated_locations"] else 0.0
for a in r]
f = familiarity(coll, nb)
lo = min(f)
tied = [c for c, v in zip(nb, f) if v <= lo + 1e-9]
pos = tied[int(rng.integers(len(tied)))] # break ties at random
batch_analyze scores all four neighbours in one request. "fast" matters:
the patient read keeps refining its answer, which is useful when you want the
answer and destroys the thing you want here, which is the raw distance on first
contact.
Then the last line. Read on before deciding it is a detail.
Step 4 — measure it against a random walk
Three agents on a 6×6 floor, starting in the middle with an empty memory, eight runs each, and the same 200-step budget. One walks at random. One always takes the least familiar neighbour and, when several tie, takes the first in the list. One breaks those ties at random.
6x6 = 36 squares, mean of 8 runs
steps random curious/first-tie curious/random-tie
20 11.8 21.0 20.8
50 18.9 30.0 32.2
80 24.9 30.0 35.6
200 32.9 30.0 36.0
50% of the floor after random 45 first-tie 17 random-tie 17
90% of the floor after random 189 first-tie never random-tie 52
100% of the floor after random never first-tie never random-tie 161
Two things in that table.
The intended one: curiosity maps the floor far faster. Half the floor in 17 steps against 45, and 90% of it in 52 steps against 189 — nearly four times quicker to the same coverage, from a number the memory returns anyway. Both agents take the same steps and run the same read; one of them is being told which of its four options it knows least about.
The other one is the middle column. The tie-first agent starts out identical to its sibling — 21.0 against 20.8 at twenty steps — and then stops dead at 30 of 36 squares and never moves again. This is not curiosity running out. It happens because on an open floor several neighbours are very often equally unfamiliar, and an agent that always resolves that the same way becomes completely predictable, which for a walker on a grid means going round in a loop. The one line that fixes it is the one flagged in step 3.
Worth being precise, because the two failures look identical from outside: an agent stuck in a loop and an agent that has genuinely finished both show a flat coverage curve. The way to tell them apart is not the curve, it is the memory — ask how full the collection is.
The whole thing
import base64, hashlib, json, urllib.request
import numpy as np
BASE, D, M = "http://localhost:6398", 1024, 6
AUTH = base64.b64encode(b"admin:blog-demo").decode()
def call(path, body=None, method="POST"):
data = json.dumps(body).encode() if body is not None else None
req = urllib.request.Request(BASE + path, data=data, method=method,
headers={"Content-Type": "application/json", "Authorization": "Basic " + AUTH})
with urllib.request.urlopen(req, timeout=120) as r:
return json.loads(r.read() or b"null")
def nrm(v): return v / (np.linalg.norm(v) + 1e-12)
def unitary(name):
# A pattern with every ripple at equal strength, so blending by it shifts
# things around without making anything louder or quieter.
seed = int.from_bytes(hashlib.sha256(name.encode()).digest()[:8], "big") % (2**63)
ph = np.random.default_rng(seed).uniform(0, 1, D // 2 + 1)
f = np.exp(2j * np.pi * ph); f[0] = f[-1] = 1.0
return np.fft.irfft(f, n=D)
def cpow(v, p): # "walk p steps along this direction"
return np.fft.irfft(np.fft.rfft(v) ** p, n=D)
def blend(a, b):
return nrm(np.fft.irfft(np.fft.rfft(a) * np.fft.rfft(b), n=D))
B, RX, RY = unitary("B"), unitary("RX"), unitary("RY")
# One pattern per square. Squares that are close on the floor get similar
# patterns, so learning about one square teaches the agent a little about
# the squares beside it.
PLACE = {(x, y): nrm(blend(RX, cpow(B, x)) + blend(RY, cpow(B, y)))
for x in range(M) for y in range(M)}
print("adjacent squares:", round(float(PLACE[(2,2)] @ PLACE[(2,3)]), 3),
" opposite corners:", round(float(PLACE[(0,0)] @ PLACE[(5,5)]), 3))
def neighbors(x, y):
return [(x+dx, y+dy) for dx, dy in ((1,0),(-1,0),(0,1),(0,-1))
if 0 <= x+dx < M and 0 <= y+dy < M]
def store(coll, seen):
# bulk_load replaces the memory with exactly these patterns. The ordinary
# write path folds near-identical things together, which is the wrong
# behaviour here: two squares one pace apart must stay two entries.
vs = [PLACE[p].tolist() for p in seen]
call(f"/collections/{coll}/bulk_load", {"addresses": vs, "counters": vs})
def familiarity(coll, cands):
# Ask the memory about several squares at once. The strongest match it
# reports is how well it already knows that square: 1.0 = been there.
r = call(f"/collections/{coll}/batch_analyze",
{"queries": [PLACE[c].tolist() for c in cands], "strategy": "fast"})["results"]
return [a["activated_locations"][0]["similarity"] if a["activated_locations"] else 0.0
for a in r]
def walk(mode, steps, seed):
coll = f"visited_{mode}_{seed}"
call(f"/collections/{coll}", method="DELETE")
rng = np.random.default_rng(seed)
pos = (M // 2, M // 2)
seen = [pos]; store(coll, seen); cov = []
for _ in range(steps):
nb = neighbors(*pos)
if mode == "random":
pos = nb[int(rng.integers(len(nb)))]
else:
f = familiarity(coll, nb)
lo = min(f)
tied = [c for c, v in zip(nb, f) if v <= lo + 1e-9]
# The whole difference between the two curious runs is this line.
pos = tied[0] if mode == "first-tie" else tied[int(rng.integers(len(tied)))]
if pos not in seen:
seen.append(pos); store(coll, seen) # only a new square changes the memory
cov.append(len(seen))
call(f"/collections/{coll}", method="DELETE")
return np.array(cov)
STEPS, SEEDS = 200, 8
c = {m: np.mean([walk(m, STEPS, s) for s in range(SEEDS)], axis=0)
for m in ("random", "first-tie", "random-tie")}
print(f"\n{M}x{M} = {M*M} squares, mean of {SEEDS} runs")
print(" steps random curious/first-tie curious/random-tie")
for t in (20, 50, 80, 200):
print(f" {t:4d} {c['random'][t-1]:5.1f} {c['first-tie'][t-1]:5.1f}"
f" {c['random-tie'][t-1]:5.1f}")
def first(cv, frac):
i = int(np.argmax(cv >= frac * M * M))
return i + 1 if cv[i] >= frac * M * M else "never"
print()
for frac in (0.5, 0.9, 1.0):
print(f" {int(frac*100):3d}% of the floor after random {first(c['random'],frac)}"
f" first-tie {first(c['first-tie'],frac)}"
f" random-tie {first(c['random-tie'],frac)}")
What to change for your own space
Your squares are your states — pages of a site, configurations of a device,
positions of an arm. The only requirement is that you can turn each into a
pattern and that patterns for similar states come out similar. If the states
have coordinates, build the pattern from them the way PLACE does. If they do
not, use whatever description you have and check the sanity line from step 1:
two things you consider close should overlap substantially, two things you
consider unrelated should not.
Your neighbours are whatever one action can reach. The loop never assumes four of them, or a grid, or that moves are reversible.
Write only when something is new. If your world has genuinely repeated
observations worth accumulating, keep a second collection on the ordinary
write path for those, and keep this one literal. Mixing the two purposes in
one collection is what produced the 0.49-against-0.48 result above.
Watch the size of the collection. Roughly one entry per 32 numbers of pattern length is the comfortable load, so 1024-long patterns hold tens of entries cleanly. Past that, everything starts to look moderately familiar and the agent's compass goes vague — which reads exactly like a mapped world.
When this works
When something is genuinely unfamiliar. With a memory that is full, or a region already uniformly explored, the differences between candidates drop into the noise and "least familiar" stops pointing anywhere. The remaining unvisited squares in a run like this are typically the ones behind a band of mapped ground, and an agent that only looks one step ahead will not pay the cost of crossing the familiar to reach them. Getting there needs a plan, which is the other half of the pair.
When there is already something in memory. At the very first step everything is equally unknown, the number carries no preference, and the choice is arbitrary. Curiosity needs a little experience before it has a direction.
When you break ties at random. Not a caveat — a line of code. The middle column of step 4 is what the same agent does without it.
When you have a separate reason to stop. Least-familiar says where to go and never says when to be done. This loop runs until its step budget ends. Deciding that no remaining square is worth the walk is a different rule, and the curious agent guide gives one that prices a visit in bits rather than in a tuned threshold.
More depth: curiosity, fidelity and Build a curious agent.