Stochastic Resetting Accelerates Reinforcement Learning Beyond Random Search
Authors: Jello Zhou, David J. Schwab, Vudtiwat Ngampruetikorn
Organizations: Biophysics Program, Stanford University, Stanford, California 94301, USA · Initiative for the Theoretical Sciences and Princeton-CUNY Center for the Physics of Biological Function, The Graduate Center, CUNY, New York, NY 10016, USA · School of Physics, University of Sydney, Sydney, NSW 2006, Australia · National Institute for Theory and Mathematics in Biology, Northwestern University and The University of Chicago, Chicago, IL 60611, USA
Stochastic resetting -- intermittently returning a process to a fixed reference state -- has emerged as an effective mechanism for optimizing first-passage properties. Existing theory largely treats processes that search but do not learn: the searcher follows fixed dynamics, accumulating no knowledge between resets. Here we ask how stochastic resetting interacts with reinforcement learning, where the underlying dynamics adapt through experience. In tabular grid environments, we find that resetting can accelerate learning even when it does not reduce the search time of a diffusive agent. Our results reveal a distinct additional mechanism through which resetting speeds the propagation of reward information. We show that deterministic, sharp resetting accelerates learning more than the stochastic protocol but over a narrower range of reset rates. In a continuous-state task with neural-network-based value approximation, we demonstrate that resetting speeds up learning when exploration is hard and rewards are sparse. We argue further that, in the tabular tasks, resetting accelerates learning without altering the solution the agent ultimately reaches, unlike other techniques such as temporal discounting, which biases the optimal behavior. Our results establish stochastic resetting as a simple, tunable mechanism for accelerating learning by shaping how experience accumulates, extending a canonical phenomenon of statistical mechanics to adaptive systems.
Figures & tables
Figure 1: Competing effects of resetting across reinforcement-learning environments. (A) Two trajectories begin at the same start state (open circle). Resetting to the start (gray) shortens the remaining search for a trajectory that has wandered away from the goal, but lengthens it for one that has already moved closer; whether resetting accelerates search on average depends on the balance between these cases, set by the reset rate, the environment and the underlying process. (B) GridWorld: a tabular agent learns a shortest path on an open square lattice. (C) WindyCliff: stochastic wind and cliff penalties create a policy tradeoff from an externally imposed reset. (D) MountainCar: an underpowered car must build momentum to reach the goal. In all environments, resetting returns the agent to the start during training without producing a value-function update or erasing learned values.
Figure 2: Stochastic resetting accelerates Q-learning on an open GridWorld, and the learning speedup exceeds the diffusive first-passage-time speedup. (A) Median test steps of the greedy policy as a function of training step and stochastic reset rate; color encodes test steps on a logarithmic scale, and pale cells mark convergence toward the 40-step optimum. Moderate reset rates reach the optimum earlier than the no-reset baseline. (B) Median speedup relative to the no-reset baseline. The learning speedup—baseline convergence step divided by the convergence step at rate r —exceeds the diffusive first-passage-time (FPT) speedup, the analogous median ratio for an undirected random walker, across the useful range of reset rates. (C) Median number of completed episodes during the first 160,000 training steps. Moderate reset rates discover the goal fastest, whereas high rates suppress discovery by truncating trajectories before arrival. (D) Median value-front distance against completed episodes. Plotting against completed episodes isolates per-episode value propagation from the search clock; the residual separation across reset rates shows that resetting speeds value propagation independently of episode-completion rate. Unlike the episode-completion rate in (C), this effect strengthens monotonically with reset rate. GridWorld of size N=120 with γ=0.99 , α=0.0001 and exploration rate ε=1.0 ; learning statistics use 2048 matched seeds and the diffusive baseline 20,000 .
Figure 3: Sharp resetting yields a larger but narrower learning-speed optimum than stochastic resetting. (A) Median test steps of the greedy policy under sharp (deterministic) resetting, as a function of training step and equivalent reset rate r=1/T , on the same logarithmic scale as Fig 2 A. (B) Median learning speedup relative to no reset for stochastic and sharp resetting. Sharp resetting reaches a larger peak speedup but is less forgiving, falling off more steeply at high reset rates. Same GridWorld and hyperparameters as Fig 2 ( N=120 , γ=0.99 , α=0.0001 , ε=1.0 ; 2048 seeds); sharp resetting returns the agent to the start every T=round(1/r) steps.
Figure 4: Resetting accelerates WindyCliff learning without changing the converged policy, whereas the discount factor reshapes the optimal policy. (A) Median test steps of the greedy policy at γ=0.99 as a function of training step and stochastic reset rate; the orange region marks convergence toward the 28 -step learned path. (B) Reset learning speedup and diffusive FPT speedup relative to the no-reset baseline. The learning speedup exceeds the FPT speedup at every reset rate, and stays above one even where resetting slows the diffusive searcher. (C) Dynamic-programming (DP) optimal paths for γ=0.5 , 0.7 and 0.99 ; a lower discount selects a longer, safer route away from the cliff. (D) DP-optimal no-wind path length as a function of discount, shortening as γ increases. (E) Discount-only learning speedup, which stays essentially flat—tuning γ does not accelerate learning. WindyCliff of width 300 and height 150 with wind probability pw=0.005 and strength sw=3 ; reset panels use γ=0.99 , α=0.5 , ε=0.5 and 600,000 training steps over 2048 seeds, with 20,000 diffusive replicates. Panels D and E use a no-reset sweep over γ .
Figure 5: Stochastic resetting accelerates deep reinforcement learning in the extended MountainCar. (A) Fraction of replicates whose greedy-evaluation performance is at most 200 steps, as a function of cumulative training steps for each reset rate (legend). Intermediate reset rates rise earlier and stay higher than the no-reset baseline. Inset: median greedy-evaluation steps. (B) Median cumulative number of goals reached during training; intermediate reset rates raise the goal-encounter rate, while the highest rates interrupt the momentum-building trajectories needed to reach the goal. Extended MountainCar (left boundary xmin=−1.7 ) under the sparse-positive reward ( +1 at the goal, 0 otherwise), solved with a deep Q-network at γ=0.98 , learning rate 0.0001 and final exploration ε=0.1 ; 150,000 training steps and 2048 replicates per reset rate.
Figure 6: Sharp resetting changes the episode clock and the per-episode value-propagation clock in different ways. (A) Median completed episodes under sharp resetting as a function of training step and equivalent reset rate; the stepped overlay marks the training step at which the third episode is completed. (B) Training steps needed to reach the third completed episode, for stochastic and sharp resetting. Sharp resetting reaches the third episode sooner at low and intermediate rates, but later at high rates, where fixed-interval truncation more often interrupts a trajectory before it arrives. (C) Median value-front distance under sharp resetting as a function of completed episodes and reset rate; the stepped overlay marks the episode at which the value front reaches the start. (D) Completed episodes needed for the value front to reach the start, for stochastic and sharp resetting; sharp resetting propagates value to the start in fewer episodes at every rate. Same GridWorld and hyperparameters as Fig 2 .
Figure 7: The GridWorld learning-speed conclusion is robust to the near-optimality threshold used to define convergence. (A) Median convergence step against stochastic reset rate for N=60 , using convergence thresholds of 1.1 , 1.5 and 2.0 times the 40 -step optimal path. (B) The same threshold comparison for N=120 ; the intermediate-reset optimum persists across thresholds. Hyperparameters as in Fig 2 ( γ=0.99 , α=0.0001 , ε=1.0 ).
Figure 8: Resetting can speed learning beyond its effect on random search, and the separation is clearest in the larger GridWorld. (A) Median convergence step against stochastic reset rate for N=60 at exploration rates ε=0.6 , 0.8 and 1.0 . (B) The same exploration sweep for N=120 . (C) Speedup factors for N=60 ; the learning speedup is compared with the diffusive FPT speedup. (D) Speedup factors for N=120 , where the learning speedups exceed the FPT speedups by a wide margin at intermediate reset rates. Hyperparameters as in Fig 2 , with the diffusive baseline over 20,000 replicates.
Figure 9: Extended MountainCar with a step-penalty reward. As Fig 5 , but with a step-penalty reward ( −1 per step, 0 at the goal) on the extended environment ( xmin=−1.7 ). The penalty supplies a gradient signal on every transition, so exploration is no longer the bottleneck: learning curves for different reset rates largely overlap and the highest rates modestly impair performance. (A) Fraction of replicates with greedy-evaluation performance at most 200 steps; inset, median greedy-evaluation steps. (B) Median cumulative goals reached. Step-penalty hyperparameters: learning rate 0.004 , final exploration ε=0.07 ; 150,000 training steps and 2048 replicates per reset rate.
Figure 10: Standard MountainCar with a sparse-positive reward. As Fig 5 , but with the standard left boundary ( xmin=−1.2 ). The valley is shallow enough that the agent reliably discovers the goal unaided, so resetting offers no benefit. (A) Fraction of replicates with greedy-evaluation performance at most 200 steps; inset, median greedy-evaluation steps. (B) Median cumulative goals reached. Hyperparameters as in Fig 5 .
Figure 11: Standard MountainCar with a step-penalty reward. As Fig 9 , but with the standard left boundary ( xmin=−1.2 ). With both a dense penalty signal and easy goal discovery, resetting again offers no benefit. (A) Fraction of replicates with greedy-evaluation performance at most 200 steps; inset, median greedy-evaluation steps. (B) Median cumulative goals reached. Step-penalty hyperparameters as in Fig 9 .
Sparse-reward reinforcement learning often fails because rollouts from the unassisted evaluation start rarely reach later task stages. Reverse curricula address this by starting some training rollouts from easier intermediate states, called scaffolds. The main choices are which intermediate starts to use (scaffold access) and how to distribute training across them (scaffold allocation). Most prior curricula pace removal on one shared schedule, which can fail when task instances, or contexts, learn at different rates. We introduce an online, learner-agnostic reset controller that gives every context its own curriculum. We use binary rollout success to decide whether to move a context's start forward or back. A stalled frontier also gets an occasional harder-start trial. A counting construction shows that synchronized global pacing can be insufficient when contexts need conflicting amounts of assisted practice. Across six navigation and manipulation settings, scaffold access improves learning and enables success in three where unassisted training fails within the reported budget. None of the global schedules we tested solved both groups in the constructed conflict. The per-context controller did. Group-level pacing works if the labels capture how contexts learn. Without those labels, per-context pacing still handles differences within a group. These results suggest pacing assistance separately for contexts that learn at different rates.
Retry-based objectives such as pass@K and max@K optimize the best return obtained from multiple sampled trajectories, and recent work has shown that they can promote exploration without explicit exploration bonuses. In discrete action spaces, ReMax was shown to do so by adapting to return uncertainty. In this work, we introduce pathwise derivative estimators for retry objectives and use them to extend ReMax to continuous action spaces. We study the resulting learning dynamics and show that, even with deterministic rewards, ReMax can encourage stochastic exploration by reshaping the policy-gradient landscape. In particular, it alters gradients both in direction, biasing updates toward higher policy entropy, and in magnitude, damping gradients and slowing convergence. We further show that Adam's adaptive normalization can mitigate this damping, depending on its numerical stabilization parameter. Empirically, we instantiate this objective as ReMax Actor-Critic (ReMAC), an off-policy actor--critic algorithm that optimizes the ReMax objective using a pathwise derivative estimator. Our experiments show that ReMAC can promote higher policy entropy without entropy regularization and achieves performance comparable to SAC.
In reinforcement learning (RL), agents benefit from exploration only because they repeatedly encounter similar states: trying different actions can improve performance or reduce uncertainty; without such retries, a greedy policy is optimal. We formalize this intuition with ReMax, an objective that evaluates a policy by the expected maximum return over M samples, where M is a positive integer, while accounting for return uncertainty. Optimizing this objective induces stochastic exploration as an emergent property, without explicit bonus terms. For efficient policy optimization, we derive a new policy-gradient formulation for ReMax and introduce ReMax PPO (RePPO), a PPO variant that optimizes ReMax while generalizing the discrete retry count M to a continuous parameter m>0, enabling fine-grained control of exploration. Empirically, RePPO promotes exploration, without any explicit exploration bonuses, on the MinAtar and Craftax benchmarks.
Soichiro Nishimori, Paavo Parmas, Sotetsu Koyamada +4
The University of Tokyo, Tokyo, Japan · Kobe University, Kobe, Japan · Kyoto University, Kyoto, Japan +3