Learning to reset in target search problems

• URL: http://arxiv.org/abs/2503.11330v1
• Date: Fri, 14 Mar 2025 11:57:51 GMT
• Title: Learning to reset in target search problems
• Abstract summary: We propose a reinforcement learning framework to train agents capable of optimizing their search efficiency in environments by learning how to reset.<n>First, we validate the approach in a well-established benchmark: the Brownian search with resetting.<n>We then extend the framework by allowing agents to control not only when to reset, but also their spatial dynamics through turning actions.
• Score: 0.6554326244334868
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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.

Related papers

• Search Strategies for Optimal Classification and Regression Trees [6.627152091494143]
  Optimal decision trees (ODTs) are machine learning models that globally optimize a given objective.<n>Recent work has proposed a variety of search strategies to improve scalability, but the precise contribution of each strategy remains unclear.<n>We introduce a general algorithmic framework for ODTs that instantiates previously used search strategies and enables the definition of new ones.
  arXiv  Detail & Related papers  (2026-07-30T13:08:21Z)
• Step-by-Step Optimization-like Reasoning in LLMs over Expanding Search Spaces [63.82675722580452]
  OPT* is a family of optimization-style tasks for training and evaluating LLM step-by-step optimization-like reasoning.<n>Each task provides a feasibility checker and evaluator, while a complexity parameter expands the search space without requiring new human labels.<n>We show that training on OPT* improves step-by-step optimization-like reasoning.
  arXiv  Detail & Related papers  (2026-06-03T21:43:38Z)
• FML-bench: A Controlled Study of AI Research Agent Strategies from the Perspective of Search Dynamics [24.125726163497742]
  FML-Bench is a benchmark of 18 fundamental ML research tasks across 10 domains.<n>It separates agent strategy from execution infrastructure and defines 12 process-level behavioral metrics.<n>We find greedy search tends to be more effective when opportunities are dense, while tree-search and evolutionary strategies tend to be more effective when opportunities are sparse.
  arXiv  Detail & Related papers  (2026-05-17T10:30:38Z)
• CoSearch: Joint Training of Reasoning and Document Ranking via Reinforcement Learning for Agentic Search [51.911048955965136]
  CoSearch is a framework that jointly trains a multi-step reasoning agent and a generative document ranking model.<n>Our results show that joint training of the reasoning agent and retrieval system is both feasible and strongly performant.
  arXiv  Detail & Related papers  (2026-04-19T17:48:17Z)
• Cycle-Consistent Search: Question Reconstructability as a Proxy Reward for Search Agent Training [80.20022221643414]
  Cycle-Consistent Search is a gold-supervision-free framework for training search agents.<n>We show that CCS achieves performance comparable to supervised baselines.<n>These results suggest that CCS provides a scalable training paradigm for training search agents in settings where gold supervision is unavailable.
  arXiv  Detail & Related papers  (2026-04-14T17:00:18Z)
• When should I search more: Adaptive Complex Query Optimization with Reinforcement Learning [26.489185170468062]
  We propose a novel RL framework called Adaptive Complex Query Optimization (ACQO)<n>Our framework is designed to adaptively determine when and how to expand the search process.<n>ACQO achieves state-of-the-art performance on three complex query benchmarks, significantly outperforming established baselines.
  arXiv  Detail & Related papers  (2026-01-29T03:16:53Z)
• PRISMA: Reinforcement Learning Guided Two-Stage Policy Optimization in Multi-Agent Architecture for Open-Domain Multi-Hop Question Answering [26.994531058178982]
  Answering real-world open-domain questions over massive corpora is a critical challenge in Retrieval-Augmented Generation (RAG) systems.<n>Recent research employs reinforcement learning (RL) to end-to-end optimize the retrieval-augmented reasoning process.<n>We propose PRISMA, a decoupled-guided framework featuring a Plan-Retrieve-Inspect-Memoize architecture.
  arXiv  Detail & Related papers  (2026-01-09T01:38:38Z)
• RE-Searcher: Robust Agentic Search with Goal-oriented Planning and Self-reflection [55.125987985864896]
  We present a systematic analysis that quantifies how environmental complexity induces fragile search behaviors.<n>We propose a simple yet effective approach to instantiate a search agent, RE-Searcher.<n>This combination of goal-oriented planning and self-reflection enables RE-Searcher to resist spurious cues in complex search environments.
  arXiv  Detail & Related papers  (2025-09-30T10:25:27Z)
• Zobrist Hash-based Duplicate Detection in Symbolic Regression [0.5439020425819]
  Genetic Programming (GP) is an evolutionary search method that evolves a population of mathematical expressions through the mechanism of natural selection.<n>We show that many points in the search space are re-visited and re-evaluated multiple times by the algorithm, leading to wasted computational effort.<n>We introduce a caching mechanism based on the Zobrist hash, a type of hashing frequently used in abstract board games.
  arXiv  Detail & Related papers  (2025-08-19T14:18:16Z)
• Process vs. Outcome Reward: Which is Better for Agentic RAG Reinforcement Learning [45.10424242207931]
  Retrieval-augmented generation (RAG) enhances the text generation capabilities of large language models (LLMs)<n>We introduce a novel method ReasonRAG that automatically constructs RAG-ProGuide, a high-quality dataset providing process-level rewards for query generation, evidence extraction, and answer generation.<n>With the process-level policy optimization, the proposed framework empowers LLMs to autonomously invoke search, generate queries, extract relevant evidence, and produce final answers.
  arXiv  Detail & Related papers  (2025-05-20T08:21:00Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• Self-Routing RAG: Binding Selective Retrieval with Knowledge Verbalization [97.72503890388866]
  We propose Self-Routing RAG (SR-RAG), a novel framework that binds selective retrieval with knowledge verbalization. SR-RAG enables an LLM to dynamically decide between external retrieval and verbalizing its own parametric knowledge. We introduce dynamic knowledge source inference via nearest neighbor search to improve the accuracy of knowledge source decision.
  arXiv  Detail & Related papers  (2025-04-01T17:59:30Z)
• Fast or Better? Balancing Accuracy and Cost in Retrieval-Augmented Generation with Flexible User Control [52.405085773954596]
  Retrieval-Augmented Generation (RAG) has emerged as a powerful approach to mitigate large language model hallucinations.<n>Existing RAG frameworks often apply retrieval indiscriminately,leading to inefficiencies-over-retrieving.<n>We introduce a novel user-controllable RAG framework that enables dynamic adjustment of the accuracy-cost trade-off.
  arXiv  Detail & Related papers  (2025-02-17T18:56:20Z)
• Chain-of-Retrieval Augmented Generation [72.06205327186069]
  This paper introduces an approach for training o1-like RAG models that retrieve and reason over relevant information step by step before generating the final answer.<n>Our proposed method, CoRAG, allows the model to dynamically reformulate the query based on the evolving state.
  arXiv  Detail & Related papers  (2025-01-24T09:12:52Z)
• Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation [0.40964539027092917]
  We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based optimization improvements. We show that LRBS significantly enhances both in-distribution performance and generalization to larger problem instances. We also employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance.
  arXiv  Detail & Related papers  (2024-12-13T14:25:27Z)
• MBA-RAG: a Bandit Approach for Adaptive Retrieval-Augmented Generation through Question Complexity [30.346398341996476]
  We propose a reinforcement learning-based framework that dynamically selects the most suitable retrieval strategy based on query complexity.<n>Our method achieves new state of the art results on multiple single-hop and multi-hop datasets while reducing retrieval costs.
  arXiv  Detail & Related papers  (2024-12-02T14:55:02Z)
• Learning to Rank for Multiple Retrieval-Augmented Models through Iterative Utility Maximization [21.115495457454365]
  This paper investigates the design of a unified search engine to serve multiple retrieval-augmented generation (RAG) agents. We introduce an iterative approach where the search engine generates retrieval results for these RAG agents and gathers feedback on the quality of the retrieved documents during an offline phase. We adapt this approach to an online setting, allowing the search engine to refine its behavior based on real-time individual agents feedback.
  arXiv  Detail & Related papers  (2024-10-13T17:53:50Z)
• Discovering Preference Optimization Algorithms with and for Large Language Models [50.843710797024805]
  offline preference optimization is a key method for enhancing and controlling the quality of Large Language Model (LLM) outputs. We perform objective discovery to automatically discover new state-of-the-art preference optimization algorithms without (expert) human intervention. Experiments demonstrate the state-of-the-art performance of DiscoPOP, a novel algorithm that adaptively blends logistic and exponential losses.
  arXiv  Detail & Related papers  (2024-06-12T16:58:41Z)
• Surpassing legacy approaches to PWR core reload optimization with single-objective Reinforcement learning [0.0]
  We have developed methods based on Deep Reinforcement Learning (DRL) for both single- and multi-objective optimization. In this paper, we demonstrate the advantage of our RL-based approach, specifically using Proximal Policy Optimization (PPO) PPO adapts its search capability via a policy with learnable weights, allowing it to function as both a global and local search method.
  arXiv  Detail & Related papers  (2024-02-16T19:35:58Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• Online Control of Adaptive Large Neighborhood Search using Deep Reinforcement Learning [4.374837991804085]
  We introduce a Deep Reinforcement Learning based approach called DR-ALNS that selects operators, adjusts parameters, and controls the acceptance criterion throughout the search. We evaluate the proposed method on a problem with orienteering weights and time windows, as presented in an IJCAI competition. The results show that our approach outperforms vanilla ALNS, ALNS tuned with Bayesian optimization, and two state-of-the-art DRL approaches.
  arXiv  Detail & Related papers  (2022-11-01T21:33:46Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.