Optimistic initialization is the simplest directed exploration strategy in reinforcement learning (RL). The agent starts by believing every untried action is as good as the best possible outcome. It then acts greedily, and each disappointing experience pulls its estimate down, which steers it toward places it has not yet tried. The mechanism only works if the agent remembers what it has tried. In deep RL, the best working version, DOIE, keeps an explicit set of visited points and treats anything far from that set as unexplored. This proposal asks what happens when that memory has a fixed size. Our prediction is that the obvious way to stay within budget, deleting old points, is harmful. Each deletion makes a visited region look new again and brings back its optimism, so the agent pays to explore it a second time. Below some memory size these repeat visits should dominate regret, giving a sharp collapse that mirrors the memory cliffs proven for streaming bandits.
The proposed fix is to forget resolution rather than regions. When memory is full, the agent merges two neighboring remembered cells into one coarser cell instead of deleting one. The merged cell inherits the larger of the two optimistic ceilings, so a visited region never jumps back to "maximally promising." The agent's learned world model decides which merges are safe: it merges where the model already predicts the dynamics well, because there the model itself is a compact memory of the region. We will measure the predicted collapse under deletion and show that merging removes it, in tabular chains and in sparse-reward continuous control. We will also give a regret decomposition that explains both results.
Core Claim
Bounded-memory optimistic exploration has a phase transition. Its location is set by how many remembered cells the agent needs to avoid re-opening regions it has already visited. The memory-regret literature has proven such cliffs only for arm slots in bandits. Maiti et al. show regret jumps from $\widetilde{O}(\sqrt{T})$ to $\Omega(T^{2/3})$ once memory drops even one slot below the number of arms. He et al. show that the gap $(n-m)$ between arms and memory slots governs multi-pass regret. Chaudhuri and Kalyanakrishnan show that two slots, one for the current champion and one for a challenger, are the minimum for sublinear regret. None of these papers has state transitions, world models, or optimistic value functions.
Our claim is that in RL the mechanism behind the cliff is specific and measurable. We call it resurrection: a state-action pair is visited, its record is evicted, its optimism resets, and it is re-explored. We further claim that resolution-reducing merges, guided by a world model, turn the cliff into graceful degradation.
The tabular argument is the cleanest place to see this. The analysis of greedy model-based RL in Tight Regret Bounds for Model-Based RL with Greedy Policies bounds regret by the total downward revision of optimistic values. That paper calls this a "decreasing bounded process." It is the formal version of why optimistic initialization works, and it gives $\widetilde{O}(\sqrt{HSAT})$ regret for EULER-GP with only one-step greedy planning. Bounded memory breaks the monotonicity. If $\Delta_k \ge 0$ denotes the upward jump in the optimistic value of some state-action at memory event $k$, the same potential argument gives, roughly,
$$\text{Regret}(T) \;\lesssim\; R_{\text{GP}}(T) \;+\; H \sum_{k} \Delta_k ,$$
where $R_{\text{GP}}(T)$ is the full-memory greedy-planning regret and $H$ is the horizon. The second term comes from each upward jump re-entering the potential that later downward revisions must pay off.
Under deletion, every eviction of a visited pair on the near-optimal policy's path sets $\Delta_k$ to roughly the full gap between $V_{\max}$ and its revised value. If memory is smaller than the set of such pairs, these events recur in every episode, and regret becomes linear. Under merging, the jump is only the difference between the two merged ceilings. This is small exactly when the merged cells have similar dynamics and values, which is what the world model is used to certify.
Turning this sketch into a theorem is the first deliverable. The target is a bound in terms of $M$ and the size of the near-optimal support, with a matching lower-bound instance for deletion. This addresses Gap 4 of the research file directly.
Research Program
The continuous-control agent combines three published pieces. The first is MBPO's short model rollouts branched from real states (When to Trust Your Model). We reuse its ensemble model and soft actor-critic learner unchanged.
The second is DOIE's optimistic value (Lobel et al.):
$$Q^+(s,a) = \kappa(s,a)\,Q(s,a) + \big(1-\kappa(s,a)\big)\,Q_{\max}.$$
Here $Q$ is the learned value network, $Q_{\max}$ is an upper bound on achievable return, and $\kappa \in [0,1]$ is a "knownness" score. Knownness is computed from distance to a stored covering set of visited points. DOIE exists because "generalization is the enemy of optimism": a value network that is revised downward drags unvisited neighbors down with it. The explicit set protects those neighbors, but DOIE lets that set grow without limit. We cap it at $M$ cells.
The third piece is the new one. Each cell stores a centroid, a radius, a visit count, and an optimistic ceiling. When an incoming point would exceed the budget, we merge the pair of cells that minimizes a merge cost. The cost is the world model's prediction error on the cell's recent transitions, multiplied by the ceiling difference between the two cells. The merged cell's radius covers both originals, and its ceiling is the maximum of the two.
Low model error means the parametric model already "remembers" the region. Losing spatial resolution there costs little, and the planner can still evaluate the region through rollouts. The ensemble model is used only as a certifier for merges and as MBPO's rollout engine. It is never used as the exploration bonus itself. That keeps us clear of the generalization failure DOIE documents.
The tabular counterpart replaces covering cells with records of UCRL2-GP and EULER-GP statistics: counts and empirical transitions per state-action. Memory is limited to $M < SA$ records. Merging pools the records of two state-actions into one aggregate record, with the ceiling set to the maximum of the two. This setting is where the theory is checked exactly.
The program also measures a quantity no prior work reports. The resurrection count is the number of times a cell or record that was once marked known (knownness above 0.9) returns to near-zero knownness and is visited again. The theory predicts that this count, not memory size itself, accounts for most of the regret gap. That prediction can be tested directly.
Baselines
The naive reference is MBPO with Gaussian action noise and no optimism. This is the "do nothing about exploration" agent. Earlier results show undirected noise needing exponentially many samples in goal-directed tasks (Koenig et al.). On PointMaze, DOIE reports that standard exploration baselines failed within 2,000 episodes. We expect this agent to fail on the sparse tasks at every memory size, so it marks the floor.
The upper reference is unbounded-memory DOIE grafted onto the same MBPO backbone. This is the strongest existing optimistic-initialization method in continuous control. On PointMaze it reached near-perfect success faster than OMEGA and covered the state space roughly twice as fast as OMEGA, while RND and MPE failed within 2,000 episodes (Lobel et al.). The file gives no exact success percentage or return, so for numeric values: no reported result found on Lacuna for DOIE's PointMaze success rate. We will rerun it ourselves. Its covering-set size at convergence also defines the reference count $N_\epsilon$: the number of covering cells needed at DOIE's resolution $\epsilon$. Every memory budget is reported as $M/N_\epsilon$.
The strongest bounded-memory competitors are DOIE with first-in-first-out eviction and DOIE with reservoir eviction, each at the same $M$. These are what a practitioner would do by default. We will also evaluate them in the MBPO configuration where the replay buffer is capped by the same budget.
The second strong competitor is a SOMBRL-style agent (Sukhija et al.). It plans on the mean dynamics with an ensemble-disagreement reward bonus and keeps no explicit visited set. Because it has no covering set at all, it is the natural argument that explicit memory is unnecessary. It succeeded on Venture and MountainCar where greedy Dreamer failed, but the file reports no scores. For SOMBRL, no reported result was found on Lacuna for these tasks.
In the tabular setting, the strongest baselines are UCRL2-GP and EULER-GP. Their regret curves "perfectly overlap" full planning on the 25-state chain and the 5×5 grid. No numeric regret is given in the file, so we will reproduce them at full memory before capping.
The ablations isolate the two ingredients. Distance-only merging removes the world model's role by merging the nearest pair regardless of model error. Fixed coarse resolution removes adaptivity by choosing a single larger $\epsilon$ so that the unbounded covering set fits in $M$.
All methods share the same ensemble model, actor-critic learner, rollout length, and update ratio. Each method gets the same hyperparameter search budget of 20 configurations, tuned at one memory level and then frozen across all levels. All runs use 10 seeds. Memory is counted in stored state-action vectors, including any buffer the method keeps.
Beating the field means two things. At $M/N_\epsilon \le 0.25$, merging must retain at least 80% of unbounded DOIE's area under the success curve. The best eviction baseline and the SOMBRL-style agent must fall significantly below that, with non-overlapping 95% bootstrap intervals.
Why not just…?
Why not just evict with FIFO or reservoir sampling and accept some re-exploration? Bandit theory suggests the cost is not mild. Maiti et al. find a polynomial regret jump from losing a single slot. Braverman et al. show regret becomes linear when memory falls slightly below the window size. Our decomposition predicts the same in RL, specifically through resurrections. If the eviction baselines show no cliff and a low resurrection count, the core claim is wrong and we will report that.
Why not just use a coarser covering resolution that fits in memory? This is the most serious threat, because it is simple and it also never deletes regions. The case for adaptive merging is that a fixed coarse $\epsilon$ wastes resolution on irrelevant regions and lacks it near narrow passages, such as maze corridors or the swing-up region of a pendulum. The fixed-coarse ablation settles this. If it matches model-guided merging across the $M$ sweep, the finding becomes "uniform coarsening suffices," and we will recommend that simpler method.
Why not let the world model's ensemble disagreement serve as knownness, with no explicit memory? SOMBRL does essentially this and scales well. However, Lobel et al. found that prediction-error bonuses such as RND failed on PointMaze, consistent with network generalization erasing optimism. SOMBRL also depends on a tuned bonus weight. The SOMBRL-style baseline at matched compute is exactly this comparison. If it wins at small memory, explicit bounded memory is unnecessary for these tasks.
Why not delete points but replace $Q_{\max}$ with the model's predicted value for evicted regions? This would use the model as memory without any merging. The problem is that a model-predicted value is not an upper bound, so revisited regions could be under-explored. This is the Markov analogue of the re-sampling trap Maiti et al. identify, where stored statistics from lucky early streaks lock in mistakes. We include it as a further ablation to check whether merging's guaranteed ceiling actually matters.
Proposed Experiments
The tabular study runs UCRL2-GP and EULER-GP on the 25-state chain and the 5×5 grid from the greedy-planning paper, plus a scaled 15×15 grid so the memory sweep has room. Memory $M$ is swept over records as a fraction of $SA$ and of the measured near-optimal support. We plot cumulative regret against $M$ and test three predictions. First, deletion produces a slope change toward linear regret near the support size. Second, regret tracks $H\sum_k \Delta_k$ as computed from logged jumps. Third, merging keeps regret within a constant factor of full memory down to a much smaller $M$.
The continuous study uses PointMaze and the hardened DeepMind Control Pendulum and Acrobot with 1,000 initial no-op steps, both taken from DOIE, plus sparse MountainCar. We sweep $M/N_\epsilon \in \{1, 0.5, 0.25, 0.1, 0.05\}$. We report success rate and episodes to first goal, state-space coverage over time, and resurrection count. Dense-reward Ant serves as a sanity check that the memory cap does not hurt MBPO's sample efficiency where exploration is easy.
Three checks decide the outcome. First, deletion-based baselines must show a sharper drop in success across the sweep than merging, with resurrection count rising at the same budget where success falls. Second, model-guided merging must beat distance-only merging and fixed-coarse DOIE at the two smallest budgets on at least the maze and the hardened pendulum. Without this, the world model's role is not justified. Third, across all runs, resurrection count should explain more of the variance in final regret or success than memory budget alone. That is the empirical signature that the phase transition comes from the mechanism we propose and not from generic capacity loss.
References
- Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization
- Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
- Regret Minimisation in Multi-Armed Bandits Using Bounded Arm Memory
- Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policies
- When to Trust Your Model: Model-Based Policy Optimization
- Optimistic Initialization for Exploration in Continuous Control
- Complexity Analysis of Real-Time Reinforcement Learning
- SOMBRL: Scalable and Optimistic Model-Based RL
- Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits