Explore vs Exploit: New Results vs Known Results

The Dilemma in Retrieval

When a user queries a memory system, the system has a set of candidate memories ranked by its current scoring function. Exploitation serves the top-ranked memories according to the current scores. This is safe: the system delivers its best guess at relevant results. But if the scoring function is wrong, or if better results exist that have never been tried, exploitation locks the system into a suboptimal strategy permanently.

Exploration means serving some results that are not top-ranked, perhaps memories with uncertain scores, newly added memories that have not been evaluated yet, or memories ranked by a different scoring strategy. This is risky: the user might receive worse results for this particular query. But it is also how the system discovers that a memory it never served before is actually more useful than the ones it has been serving.

In production, the cost of exploration is real and asymmetric. A user who receives irrelevant results because the system was "exploring" does not care about long-term system improvement. They care about their current experience. Exploitation benefits the current user immediately. Exploration benefits future users eventually. This asymmetry is why naive exploration strategies (randomly shuffling results 10% of the time) fail in production: the cost to current users is concrete and immediate, while the benefit to future users is uncertain and diffuse.

The Regret Framework

Regret theory provides a formal way to think about the explore-exploit tradeoff. Regret is the difference between the reward you would have received by always choosing the best option and the reward you actually received. Every time you explore (choosing a suboptimal option to learn), you incur regret. Every time you exploit without exploring, you might be missing a better option, incurring regret of a different kind.

The goal is not to eliminate regret (that is impossible without omniscience) but to minimize cumulative regret over time. Optimal algorithms like Thompson sampling achieve sublinear regret: the total regret grows slower than the number of interactions, meaning the average regret per interaction decreases over time. Early on, the system explores frequently and incurs higher per-interaction regret. Later, the system has learned enough to exploit effectively, and per-interaction regret drops toward zero.

For retrieval systems, this means accepting some quality degradation in early interactions (the system is still learning which ranking works best) in exchange for significantly better quality in later interactions (the system has converged to an effective strategy). The total quality delivered over the system's lifetime is higher with this tradeoff than with pure exploitation from day one, because pure exploitation locks in whatever initial ranking was configured, even if a better ranking exists.

Balancing Strategies

Decaying exploration. Start with high exploration (10-20% of queries serve alternative rankings) and decrease over time as confidence in the current best strategy grows. This front-loads learning when the system needs it most and delivers increasingly reliable results as the system matures. The decay schedule can be fixed (reduce by 1% per week) or adaptive (reduce when quality metrics stabilize).

Low-risk exploration. Explore only in positions 3-5 of the result list, never in positions 1-2. Users pay the most attention to top results, so keeping those stable while experimenting with lower positions minimizes the impact of exploration on user experience. The system learns from whether users engage with the exploratory results in lower positions, and successful exploratory results can be promoted to top positions in future queries.

Uncertainty-driven exploration. Only explore when the system is uncertain about the ranking. If one memory has a score of 0.95 and the next has 0.60, exploit the clear winner. If two memories have scores of 0.78 and 0.76, the system is uncertain about which is better, so explore by occasionally swapping their positions. This focuses exploration where it is most likely to produce useful information and avoids unnecessary exploration when the current ranking is clearly correct.

Thompson sampling. Sample from probability distributions over memory quality rather than using point estimates. High-uncertainty memories occasionally produce high samples and get explored, while well-understood memories produce predictable samples and get exploited. Thompson sampling provides natural, principled exploration without manual tuning of exploration rates, decay schedules, or uncertainty thresholds. It is the most widely recommended algorithm for the explore-exploit problem because it adapts automatically to the uncertainty structure of the data.

Exploration for New Memories

Memory systems have a natural exploration challenge that most retrieval systems lack: new memories. Every time a new memory is stored, it enters the system with uncertain quality. The system must decide how aggressively to serve this new memory versus sticking with established ones. Too conservative, and valuable new information takes too long to surface. Too aggressive, and every new memory disrupts established rankings with unproven content.

This is the cold-start problem at the item level. A newly stored memory has no access history, no confidence score from corroboration, and no entity connections established through use. Its only signals are its vector embedding (for similarity matching) and its recency (it was just created). The system needs a policy for introducing new items that balances the potential value of fresh information against the proven value of established memories.

Adaptive Recall handles this through ACT-R's activation model. New memories start with moderate activation because their novelty gives them a recency boost (the base-level activation equation weights recent access events heavily). This recency boost makes new memories likely to be served in the first few queries where they are relevant, providing the initial exploration that tests their value. As the recency fades, activation depends increasingly on whether the memory was actually used when served. Memories that were served and used gain cumulative activation from their access history. Memories that were served but ignored lose their recency boost and sink in the rankings. This creates a natural probationary period for new memories: they get a fair trial through the recency boost, and their long-term ranking depends entirely on whether they proved useful.

When to Favor Exploitation

Favor exploitation when the cost of a bad result is high. Medical information, financial decisions, customer-facing support, and any context where an incorrect memory could cause real harm should prioritize serving the most reliable, well-established memories. In these contexts, exploration should be limited to low-risk positions or off-peak periods where fewer users are affected.

Favor exploitation when you have high confidence in your current rankings. If the system has processed thousands of interactions and the ranking quality metrics have stabilized, the benefit of additional exploration is small. The system has already discovered the good strategies and the bad ones. Further exploration incurs cost without proportional benefit.

Favor exploitation when the user is in the middle of a critical task. If the user has been working on a complex debugging session for an hour, disrupting their flow with exploratory (and potentially irrelevant) memories is counterproductive. Reserve exploration for session beginnings, low-stakes queries, and contexts where an imperfect result has minimal downstream impact.

When to Favor Exploration

Favor exploration when quality metrics are declining. If retrieval quality has degraded over the past week (users reformulating more, engagement dropping), the current ranking strategy may no longer be optimal. Increasing exploration allows the system to discover new strategies that better match the changed landscape.

Favor exploration when significant new content has been added. If 500 new memories were just imported from a CRM backfill or a batch extraction, those memories have no usage history and will never surface through pure exploitation. Temporarily increasing exploration gives new content a chance to prove its value.

Favor exploration when you are in the early stages of system deployment. With limited feedback data, the system's confidence in its current rankings is low. Exploration is cheap (there is little established quality to sacrifice) and valuable (every interaction provides high-information feedback about what works).