Learning to reset in target search problems
Gorka Muñoz-Gil, Hans J. Briegel, Michele Caraglio · 2025
Read Learning to reset in target search problems by Gorka Muñoz-Gil, Hans J. Briegel, Michele Caraglio (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-11330.txt.
Introduction
Gorka Muñoz-Gil, Hans Briegel, and Michele Caraglio taught agents in twenty twenty-five to learn when to restart a search. Restarting — resetting to the origin — can dramatically speed the hunt for a randomly moving target, but the best reset policy depends on the problem and is hard to derive. Their framework uses reinforcement learning to discover it.
On the classic Brownian search benchmark, trained agents rediscovered the known optimal sharp resetting rule on their own. Given control of turning as well as resetting, agents in richer environments found strategies that adapt both to local conditions and beat hand-designed benchmarks. The authors present reinforcement learning as both an optimizer for search design and a lens for uncovering interpretable strategies in stochastic processes.
Catalog record
| CREATOR | Gorka Muñoz-Gil, Hans J. Briegel, Michele Caraglio |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 32 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-11330
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning to reset in target search problems Gorka Muñoz-Gil, Hans J. Briegel, Michele Caraglio Abstract Target search problems are central to a wide range of fields, from biological foraging to the optimization algorithms. Recently, the ability to reset the search has been shown to significantly improve the searcher’s efficiency. However, the optimal resetting strategy depends on the specific properties of the search problem and can often be challenging to determine. In this work, we propose a reinforcement learning (RL)-based framework to train agents capable of optimizing their search efficiency in environments by learning how to reset. First, we validate the approach in a well-established benchmark: the Brownian search with resetting. There, RL agents consistently recover strategies closely resembling the sharp resetting distribution, known to be optimal in this scenario. We then extend the framework by allowing agents to control not only when to reset, but also their spatial dynamics through turning actions. In this more complex setting, the agents discover strategies that adapt both resetting and turning to the properties of the environment, outperforming the proposed benchmarks. These results demonstrate how reinforcement learning can serve both as an optimization tool and a mechanism for uncovering new, interpretable strategies in stochastic search processes with resetting. I Introduction Target search is a crucial task recurring in various scientific contexts, ranging from ecological foraging [ 1 , 2 , 3 ] to optimizing search algorithms [ 4 , 5 ] . These problems often involve locating sparsely distributed targets in complex environments under various constraints. In this context, resetting to a fixed initial condition has emerged as a powerful mechanism that allows to improve search efficiency in specific circumstances [ 6 ] . For instance, when performing optimization in complex loss landscapes, where one may get stuck in local minima, it may be advantageous to just restart the algorithm [ 7 ] . Another paradigmatic example is that of a Brownian walker searching for a target in free space, for which periodically restarting its position to the origin ensures a finite mean hitting time [ 8 ] . In recent years, it has been shown that a particular resetting strategy, namely that in which a process is restarted at constant intervals, is typically optimal [ 9 , 10 ] . However, while such sharp resetting is optimal in simplified scenarios, this is rarely the case in real-world applications, where search dynamics often involve additional complexities [ 11 , 12 , 13 , 14 ] . The optimal strategy in such cases may depend not only on the properties of the environment, such as the target’s location and spatial constraints, but also on the capabilities of the agent performing the search [ 15 , 16 , 17 ] . Depending on the specific process under consideration, the agent may have access to a broader set of actions, defining its dynamics within the search process [ 18 ] . The interplay between these dynamics and resetting can lead to more efficient target acquisition strategies [ 19 ] . However, identifying optimal strategies is highly non-trivial and often extremely challenging, as targets are typically sparse, making the optimization of search strategies computationally demanding. In this work, we propose a machine-learning-assisted framework for identifying efficient target search strategies under restart. In recent years, machine learning (ML) has demonstrated remarkable success in tackling complex physics problems [ 20 , 21 , 22 ] . In particular, the optimization of particle navigation by means of ML has recently gained great attention [ 23 , 24 , 25 ] . The strength of these techniques lies not only in their capacity to solve such tasks but also to uncover interpretable solutions that provide better insights into the underlying phenomena. In this context, Ref. [ 26 ] , showed that reinforcement learning (RL) agents, provided with minimal prior information and trained solely to maximize the number of targets acquired, were able to develop efficient search strategies by uncovering the intrinsic scales of the environment. Building on this foundation, we extend the approach by introducing agents with the ability to reset, the time at which this occurs being learned during their training ( Section II.2 ). In a benchmark scenario where the RL agents diffuse freely and can only choose when to reset, we show that they converge to the known optimal sharp resetting strategy ( Section III.1 ). We then address a more complex scenario in which agents adapt both their resetting distribution and their spatial dynamics. By analyzing the learned behavior of the agent, we uncover new strategies that differ significantly from the optimal sharp strategy and, most importantly, outperform it ( Section III.2 ). II Methods Figure 1: RL formulation of the target search problem with resetting. a) In 1D environments, the agent has two actions: diffuse (squares), where steps are sampled from a normal distribution with diffusion coefficient D , and reset (circles), which relocates the agent to the origin ( x=0 ). A reward ( R=1 ) is given upon reaching x\geq L . b) In 2D environments, we consider two agents: a reset agent (as in 1D) and a turn-reset agent, equipped with three actions: continue in the same direction, performing a step of constant length d (triangles), turn by a random angle (blue circles) and reset (yellow circles). The target is positioned at distance L from the origin and has radius \rho . c) The RL agent, exemplified here by a turn-reset agent, selects its next action a —either continue (c), turn (t), or reset (r)— based on its policy \pi and current the environment state s , defined in this case by two counters: steps since the last turn ( c_{t} ) and reset ( c_{r} ). See the main text for details. In this section, we present the main components of our study: the properties of the environment in which agents operate and the conditions under which targets are acquired ( Section II.1 ); the various agent types, distinguished by the set of actions they can perform ( Section II.2 ); and, finally, the reinforcement learning (RL) framework used to train agents in these environments ( Section II.3 ). II.1 Environment We consider an infinite environment, with a single target positioned at distance L from the origin. Upon reaching the target, the agent resets and begins a new walk from the origin. We analyze two variants of this setup, one in one dimension (1D) ( Fig. 1 a) and the other in two dimensions (2D) ( Fig. 1 b). In 1D, the target is positioned at position x=L and is considered acquired when the agent reaches a coordinate x\geq L . In 2D, the target is still placed at a distance L from the origin but the azimuthal angle is randomly selected in the interval [0,2\pi) . In this second case, the target has a radius \rho and is acquired whenever the agent enters the target area. We consider that the target can be acquired even if the searcher trajectory crosses the target area in the middle of an integration step. As commonly considered, the target cannot be acquired while resetting to the origin. To ensure non-trivial strategies, we consider scenarios where the