论文检索

Reinforcement Learning · Policy Search

James Heald, Vittorio Caggiano, Vikash Kumar, Maneesh Sahani

Searching for effective policies in high-dimensional action spaces is notoriously challenging. This difficulty is compounded in overactuated musculoskeletal systems, where multiple muscles span each joint, and individual muscles actuate multiple joints. Although this redundancy complicates naive policy search, it also implies that effective control can be captured by a low-dimensional action manifold. To identify such a manifold, we introduce *joint-space empowerment (JSE)*, a novel information-theoretic principle that quantifies how much control an agent has over its body. We use JSE to discover high-empowerment action manifolds, and demonstrate that manipulation policies learned on these manifolds show significantly enhanced dexterity, sample efficiency and improved generalization. These results suggest a general principle for motor coordination in high-dimensional, overactuated systems, with implications for both biological motor control and embodied artificial agents.

Social Aspects · Safety

Huilin Zhou, Jian Zhao, Yilu Zhong, Zhen Liang, Xiuyuan Chen, Yuchen Yuan, Tianle Zhang, Chi Zhang, Lan Zhang, Xuelong Li

Red teaming is critical for uncovering vulnerabilities in Large Language Models (LLMs). While automated methods have improved scalability, existing approaches often rely on static heuristics or stochastic search, rendering them brittle against advanced safety alignment. To address this, we introduce \textbf{Metis}, a framework that reformulates jailbreaking as inference-time policy optimization within an adversarial Partially Observable Markov Decision Process (POMDP). Metis employs a self-evolving metacognitive loop to perform causal diagnosis of a target's defense logic and leverages structured feedback as a semantic gradient to refine its policy, offering enhanced interpretability through transparent reasoning traces. Extensive evaluations across 10 diverse models demonstrate that Metis establishes a new state-of-the-art with an average Attack Success Rate (ASR) of 89.2\%, maintaining high efficacy on resilient frontier models (e.g., 76.0\% on O1 and 78.0\% on GPT-5-chat) where traditional baselines exhibit substantial performance degradation. By replacing redundant exploration with directed optimization, Metis reduces token costs by an average of 8.2$\times$ (and up to 11.4$\times$). Our analysis reveals that current defenses remain systematically vulnerable to internally-steered, closed-loop reasoning trajectories, highlighting a critical need for next-generation defenses capable of reasoning about safety dynamically during inference.

Applications · Health / Medicine

Jiwoong Sohn, Tomasz Sternal, Kenneth Styppa, Torsten Hoefler, Michael Moor

Reasoning in knowledge-intensive domains remains challenging because intermediate steps are often not locally verifiable: unlike math or code, evaluating step correctness may require synthesizing clues across large external knowledge sources. As a result, subtle errors can propagate through reasoning traces, potentially never to be detected. Prior work has proposed process reward models (PRMs), including retrieval-augmented variants. However, due to retrieval they operate post hoc by scoring completed trajectories which prevents their integration into dynamic inference procedures. Here, we introduce Process Reward Agents~(PRA), a test-time method for providing domain-grounded, online, step-wise rewards to a frozen reasoner. In contrast to prior retrieval-augmented PRMs, PRA enables search-based decoding to rank and prune candidate trajectories at every generation step. Experiments on multiple medical reasoning benchmarks demonstrate that PRA consistently outperforms strong baselines, achieving 80.9\% accuracy on MedQA with Qwen3-4B, a new state of the art at the 4B scale. Crucially, PRA generalizes to unseen frozen policy models ranging from 0.5B to 8B parameters, improving their accuracy by up to +25.7\% without any policy model updates. Ultimately, PRA suggests a paradigm in which frozen reasoners are decoupled from domain-specific tool-augmented reward modules, which enables the deployment of new backbones in complex domains without retraining. To support reproducibility, we release all code and data in an anonymous repository.

Reinforcement Learning · Batch/Offline

Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

Offline goal-conditioned reinforcement learning (GCRL) often struggles with long-horizon tasks, where errors in value estimation accumulate and produce unreliable policies. It is typically assumed that effective long-term planning is infeasible without specialized training. In contrast, our work demonstrates that existing GCRL policies can complete long-horizon tasks when combined with a lightweight, training-free planning wrapper. We find that standard goal-conditioned value functions encode locally consistent geometric structure sufficient for planning. Our approach, Test-Time Graph Search (TTGS), constructs a graph over the offline dataset and employs an adaptive subgoal selection strategy. To address unreliable value estimates during shortest-path search, we propose a novel mechanism that softly penalizes long-distance transitions. Our method incurs negligible computational overhead and requires no additional supervision or parameter updates. On the OGBench benchmark, TTGS unlocks latent capabilities in diverse base learners, boosting success rates on challenging locomotion tasks from near-zero to over 90\%, often matching or outperforming methods that require complex auxiliary training.

Optimization · Discrete and Combinatorial Optimization

Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

Large Language Models (LLMs) have enabled automated heuristic design (AHD) for combinatorial optimization problems (COPs), but existing frameworks' reliance on fixed evolutionary rules and static prompt templates often leads to myopic heuristic generation, redundant evaluations, and limited reasoning about how new heuristics should be derived. We propose a novel multi-agent reasoning framework, referred to as Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (PathWise), which formulates heuristic generation as a sequential decision process over an entailment graph serving as a compact, stateful memory of the search trajectory. This approach allows the system to carry forward past decisions and reuse or avoid derivation information across generations. A policy agent plans evolutionary actions, a world model agent generates heuristic rollouts conditioned on those actions, and critic agents provide routed reflections summarizing lessons from prior steps, shifting LLM-based AHD from trial-and-error evolution toward state-aware planning through reasoning. Experiments across diverse COPs show that PathWise converges faster to better heuristics, generalizes across different LLM backbones, and scales to larger problem sizes.

Reinforcement Learning · Online

Haruka Kiyohara, Mihaela Curmei, Ariel Evnine, Shankar Kalyanaraman, Israel Nir, Ana-Roxana Pop, Nitzan Razin, Sarah Dean, Thorsten Joachims, Udi Weinsberg

Large-scale search, recommendation, and retrieval-augmented generation (RAG) systems typically employ a two-stage architecture: an early-stage ranker (ESR) generates a candidate set, which is subsequently re-ranked by a late-stage ranker (LSR). While there are many reinforcement learning (RL) methods for training the LSR, end-to-end training of the ESR has proven challenging. In particular, naive application of "vanilla" policy gradient (V-PG) is not scalable for candidate-set sizes relevant for practical use due to exploding variance. This issue arises because V-PG propagates the gradient to the joint probability of the candidate sets, ignoring the contribution of each specific item in the candidate set to the reward. To mitigate this issue, we propose a novel *"credit-assigned" PG (CA-PG)*, which computes gradients with respect to the probability that the target item is chosen in any candidate set, i.e. marginalizing over all candidate sets that contain it. Our theoretical analysis reveals that CA-PG significantly reduces the variance of V-PG by marginalizing over the specific composition of the candidate set, while preserving the ability to learn the correct ranking of actions under a reasonably aligned LSR policy. Experiments on both synthetic and real-world data demonstrate that CA-PG improves the convergence speed and training stability for ESRs utilizing the canonical Plackett-Luce model, especially when the candidate-set size is large.

Reinforcement Learning · Deep RL

Wei-Di Chang, Mikael Henaff, Brandon Amos, Gregory Dudek, Scott Fujimoto

This paper investigates search in model-based reinforcement learning (RL). Conventional wisdom holds that long-term predictions and compounding errors are the primary obstacles for model-based RL. We challenge this view, showing that search is not a plug-and-play replacement for a learned policy. Surprisingly, we find that search can harm performance even when the model is highly accurate. Instead, we show that mitigating distribution shift matters more than improving model or value function accuracy. Building on this insight, we identify key techniques for enabling effective search, achieving state-of-the-art performance across multiple popular benchmark domains.

Optimization · Zero-order and Black-box Optimization

Sichen Wang, Zhipeng Lu

Noisy evolution strategies commonly mitigate ranking uncertainty by improving per-generation fidelity—for example, by allocating budget to resampling candidates or using robust aggregation to stabilize the within-generation ordering. Under strict fixed evaluation budgets, however, any additional intra-generation querying directly reduces the number of generations the algorithm can execute, shortening the optimization trajectory. This dynamic can be characterized as prioritizing fidelity over depth. We propose a paradigm shift in fixed-budget regimes toward depth over fidelity, arguing that the cumulative progress from a long sequence of noise-smoothed updates often outweighs that of a short sequence of rigorously denoised ones. We operationalize this principle via probabilistic elite membership, replacing hard truncation with conditional expected rank weights that integrate over ranking uncertainty. This shifts noise handling from the evaluation stage to the selection stage: rather than repeatedly reevaluating candidates to denoise their objective values, we directly smooth the selection signal driving the update. We instantiate this approach using residual bootstrapping: we perform sparse reevaluations near the selection boundary, store standardized noise residuals in a reusable pool, and generate bootstrap rankings to estimate expected weights. Recognizing that residual pool mismatch constitutes a potential statistical risk, we derive a falsifiable error decomposition and provide runtime diagnostics to ensure estimator validity. To prevent oversmoothing in low-noise regimes, we introduce an adaptive probe-and-switch mechanism that leverages a low-cost rank disagreement metric to dynamically select between standard CMA-ES and our bootstrap-based updates. Extensive evaluations across the COCO bbob-noisy suite and diverse external tasks—including RL policy search and noisy HPO—demonstrate consistent gains. Specifically, in high-misranking regimes constrained by strict budgets, our residual-bootstrap approach achieves substantially steeper progress curves than both uncertainty-handling CMA-ES and fixed-k resampling baselines. These results substantiate a testable thesis: when budgets are limited and ranking uncertainty is high, integrating uncertainty at the selection stage is more sample-efficient than reducing it at the evaluation stage.

Applications · Health / Medicine

Xuanning Hu, Hao Tuo, Jinglong Ji, Anchen Li, Qianli Xing, Bo Yang

Structure-based drug design (SBDD) can be effectively realized through an iterative refinement via the Design-Make-Test-Analyze (DMTA) cycle, which is a common workflow used by human experts. However, most LLMs function as one-shot generators that lack feedback mechanisms, leaving the DMTA loop disconnected. In this work, we propose K-BTS, a Knowledge-Driven Bi-level Thompson Sampling framework that formalizes iterative SBDD as a Dynamic Hierarchical Multi-Armed Bandit problem. K-BTS closes the DMTA loop by decoupling decisions into two levels: an upper-level policy that prioritizes high-potential molecular lineages and a lower-level mechanism that retrieves explicit chemical rules to guide LLM generation. By integrating a dual-level Bayesian update, the framework transforms sparse docking scores into reusable experience. On the CrossDocked2020 benchmark, K-BTS achieves a state-of-the-art Top-1 average docking score. The results from diverse dimensions show that K-BTS ensures search determinism through a smooth, monotonic convergence that synchronizes structural drift with affinity improvement.

Reinforcement Learning · Everything Else

Siteng Liao, Yuzhu Liang, Hengzhong Rao, Xizhao Luo, Tian Wang

SLM-LLM routing accelerates generation by strategically invoking LLMs for critical tokens. However, existing methods typically train routers to mimic the LLM, capping performance at the reference trajectory's limit. In this work, we demonstrate that the SLM-LLM collaborative inference space offers a richer solution set, yielding correct answers even when the LLM fails. To exploit this, we propose **AlphaRouter**, a routing framework learning optimal collaborative inference paths via a *search and iterative update* paradigm. Formulating routing as a Markov Decision Process, we introduce Collaborative Inference Tree Search (CITS) to explore the solution space. To tackle the severe credit assignment challenge posed by sparse rewards, we propose Tree-Advantage Policy Optimization (TAPO) to optimize the routing policy. By leveraging counterfactual advantages within the tree structure, TAPO effectively attributes the final reward to specific routing decisions, stabilizing training without dense supervision. Extensive experiments show that AlphaRouter advances the Pareto frontier of accuracy-efficiency trade-offs by exploiting better inference trajectories in the collaborative space. Code is available at https://anonymous.4open.science/r/AlphaRouter.

Reinforcement Learning · Planning

Jake Tuero, Michael Buro, Levi Lelis, Laurent Orseau

Subgoal-based policy tree search, which uses a policy to guide search, is effective for complex single-agent deterministic problems but often relies on explicit subgoal generation that can incur substantial overhead and hinders scalability. In this paper, we overcome these limitations by using a learned ``rerooter'' through the recently-introduced $\sqrt{\text{LTS}}$ algorithm. A *rerooter* implicitly decomposes the problem into soft subtasks. While previous work focused on the formal guarantees for given or handcrafted rerooters, in this work we propose three rerooter designs: (i) a clustering-based rerooter that exploits global state-space structure, (ii) a heuristic-based rerooter that leverages learned cost-to-go estimates, and (iii) a hybrid that combines both signals. Our framework avoids having to explicitly reconstruct and reason over generated subgoals, thereby enabling scalable allocation of search effort with significantly lower computational overhead. Empirically, our rerooting-based methods scale to complex environments where subgoal-based policy tree search fails, and achieve state-of-the-art online training efficiency on the domains tested.

Probabilistic Methods · Gaussian Processes

Armin Lederer, Anuj Srivastava, Marco Bagatella, Andreas Krause

Bayesian optimization (BO) is a method commonly used for policy search in problems with low-dimensional policy parameterizations. While it is generally considered data-efficient, existing BO approaches are agnostic to the sequential structure of the optimization objective induced by policy roll-outs. Thereby, valuable information is discarded that could improve the convergence of BO. We address this inefficiency by developing and rigorously analyzing a novel approach for BO that relies on a temporal difference learning formulation for discounted infinite-horizon value functions based on Gaussian process (GP) regression. We derive learning error bounds for the proposed temporal difference GPs, such that we can exploit upper confidence bounds to analyze the cumulative regret of our BO approach. This analysis is further refined by bounding the maximal information gain for our temporal difference GP model. In a comparison with relevant baseline methods, we demonstrate the practical advantages of our method.

Reinforcement Learning · Policy Search

Joseph Cotnareanu, Chiara Roverato, Han Zhou, Didier Chételat, Yingxue Zhang, Mark Coates

Recent efforts to improve the reasoning abilities of Large Language Models (LLMs) have focused on integrating formal logic solvers within neurosymbolic frameworks. A key challenge is that formal solvers lack commonsense world knowledge, preventing them from making reasoning steps that humans find obvious. Prior methods address this by using LLMs to supply missing commonsense assumptions, but these approaches implicitly assume universal agreement on such commonsense facts. In reality, commonsense beliefs vary across individuals. We propose a probabilistic framework for abductive commonsense reasoning that explicitly models this variation, aiming to determine whether most people would judge a statement as true or false. We introduce Probabilistic Abductive CommonSense (PACS), a novel algorithm that uses an LLM and a formal solver to sample proofs as observations of individuals’ distinct commonsense beliefs, and aggregates conclusions across these samples. Empirically, PACS outperforms chain-of-thought reasoning, prior neurosymbolic methods, and search-based approaches across multiple benchmarks.

Optimization · Discrete and Combinatorial Optimization

Hongyu Cheng, Amitabh Basu

Machine learning is increasingly used to guide branch-and-cut (B&C) for mixed-integer linear programming by learning score-based policies for selecting branching variables and cutting planes. Many approaches train on local signals from lookahead heuristics such as strong branching, and linear programming (LP) bound improvement for cut selection. Training and evaluation of the learned models often focus on local score accuracy. We show that such local score-based methods can lead to search trees exponentially larger than optimal tree sizes, by identifying two sources of this gap. The first is that these widely used expert signals can be misaligned with overall tree size. LP bound improvement can select a root cut set that yields an exponentially larger strong branching tree than selecting cuts by a simple proxy score, and strong branching itself can be exponentially suboptimal (Dey et al., 2024). The second is that small discrepancies can be amplified by the branch-and-bound recursion. An arbitrarily small perturbation of the right-hand sides in a root cut set can change the minimum tree size from a single node to exponentially many. For branching, arbitrarily small score discrepancies, and differences only in tie-breaking, can produce trees of exponentially different sizes, and even a small number of decision differences along a trajectory can incur exponential growth. These results show that branch-and-cut policies trained and learned using local expert scores do not guarantee small trees, thus motivating the study of data-driven methods that produce policies better aligned with tree size rather than only accuracy on expert scores.

Deep Learning · Large Language Models

Yeqiu Chen, Ziyan Liu, Zhenxin Huang, Runquan Gui, Hong Wang, Lei Liu

Recent progress in LLM reasoning has increasingly shifted from single-pass generation to explicit search over intermediate reasoning states. Tree-of-Thoughts (ToT) organizes inference to tree-structured search with branching and backtracking, but it substantially amplifies the key--value (KV) cache: retaining KV states for a frontier of partial trajectories quickly becomes a memory bottleneck that limits throughput and constrains search depth and width under fixed hardware budgets. We address this challenge by observing that KV reuse in ToT-style inference is governed by search dynamics: near-term decoding depends primarily on the active branch and its ancestors, whereas inactive subtrees have low short-term reuse probability yet must remain recoverable for backtracking. Motivated by this, we propose **ArborKV**, a structure-aware eviction framework that couples a lightweight value estimator with a tree-aware allocation policy, and performs purely token-extractive eviction with lazy rehydration to support revisits. Experiments on ToT-style reasoning benchmarks show that ArborKV achieves up to $\sim4\times$ peak KV-memory reduction while preserving near-full-retention accuracy, enabling larger search configurations under fixed device budgets that would otherwise run out of memory.

General Machine Learning · Clustering

Xuqian Xue, Jun Zhang, Qi Cai, Zhizhong Huang, Hongming Shan, Junping Zhang

Existing contrastive multi-view clustering methods rely on a pre-defined cluster number, limiting their flexibility in real-world scenarios lacking prior knowledge. To address this, we propose GROK, a novel framework driven by a cluster decision agent for unknown-$K$ multi-view clustering. It pioneers the adaptation of group relative policy optimization (GRPO) —a reinforcement learning strategy for LLM reasoning— into the unsupervised domain to autonomously determine the optimal $K$. Specifically, the agent orchestrates the clustering process through three synergistic phases. First, in the state perception phase, we employ a structure-aware adaptive backbone to aggregate multi-view data, providing the agent with consistent and discriminative consensus observations. Second, in the group decision phase, we introduce an action space divide-and-conquer strategy and an adaptive reward function. Equipped with these mechanisms, the agent performs group sampling and relative advantage estimation within the discrete action space of candidate $K$ values, autonomously searching for the optimal $K$ via reward maximization. Finally, via geometric feedback, geometric clustering guidance mechanism transforms the agent's structural hypotheses into explicit differentiable constraints to reshape feature manifolds, thereby closing the perception-decision-feedback loop. Experimental results demonstrate that GROK achieves superior clustering performance in unknown-$K$ scenarios by autonomously exploring the underlying cluster structure.

Reinforcement Learning · Policy Search

Soichiro Nishimori, Paavo Parmas, Sotetsu Koyamada, Tadashi Kozuno, Toshinori Kitamura, Shin Ishii, Yutaka Matsuo

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 ($M \in \mathbb{N}$), 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 **Re**Max **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.

Deep Learning · Algorithms

Kaiqi Lin, Jianping Luo

While LLM-driven Neural Architecture Search (NAS) leverages exceptional code generation and reasoning, it suffers from a critical "Semantic-Physical Misalignment": LLMs prioritize high-level semantic plausibility but are agnostic to intrinsic physical dynamics such as gradient flow, whereas Zero-Cost Proxies (ZCPs) capture these local sensitivities but lack global semantic planning. To bridge this gap, we propose SAGE-NAS, a closed-loop evolutionary framework that synergizes an LLM-Based Semantic Agent with a Graph-Based Evaluator. Specifically, SAGE-NAS coordinates an LLM-driven Semantic Agent to construct candidate architectures by dynamically scheduling complementary sub-policies that balance exploitation with exploration. Furthermore, the framework integrates a Dual-Modality Graph Evaluator that serves as a rapid performance predictor by fusing ZCP statistics with topological features, and a State-Aware Behavioral Atlas that guides sparsity-driven exploration to escape local optima. Experiments demonstrate that SAGE-NAS achieves state-of-the-art performance across multiple mainstream search spaces and downstream tasks, exhibiting a superior balance between search efficiency, model accuracy, and cross-task generalization capability.

Reinforcement Learning · Deep RL

wenlong deng, Yushu Li, Boying Gong, YI REN, Christos Thrampoulidis, Xiaoxiao Li

Tool-integrated (TI) reinforcement learning (RL) enables large language models (LLMs) to perform multi-step reasoning by interacting with external tools such as search engines and retrievers. Group Relative Policy Optimization (GRPO), exemplified by the recent Search-R1, offers fast convergence and a value-free formulation that makes it appealing for this setting, yet consistently suffers from training collapse. We identify Lazy Likelihood Displacement (LLD), a systematic reduction or stagnation in the likelihood of both correct and incorrect responses, as the core mechanism driving this failure. LLD emerges early and triggers a self-reinforcing LLD Death Spiral, where declining likelihood leads to low-confidence responses, inflating gradients, and ultimately causing collapse. We empirically characterize this process across models on a Search-R1-style, search-integrated question answering task, revealing a consistent three-phase trajectory: early stagnation, steady decay, and accelerated collapse. To address this, we propose a likelihood-preserving regularization LLDS that activates only when a response action’s likelihood decreases, and regularizes only the tokens responsible. This fine-grained structure mitigates LLD with minimal interference. Our method stabilizes training, prevents gradient explosion, and yields substantial performance improvements across seven benchmarks, including relative improvements of +45.2% on Qwen2.5-3B and +37.1% on Qwen2.5-7B over vanilla GRPO training. Our results establish LLD as a previously overlooked bottleneck in GRPO- based TIRL and provide a practical path toward stable, scalable training of tool-integrated RL.

Reinforcement Learning · Everything Else

Yizhi Li, Qingshui Gu, Zhoufutu Wen, Ziniu Li, Ruibin Yuan, Tianshun Xing, Shuyue Guo, Tuney Zheng, 周欣, Xingwei Qu 等

Recent advancements in aligning large language models via reinforcement learning have achieved remarkable gains in solving complex reasoning problems, but at the cost of expensive on-policy rollouts and limited exploration of diverse reasoning paths. In this work, we introduce TreePO, involving a self-guided rollout algorithm that views sequence generation as a tree-structured searching process. Composed of dynamic tree sampling policy and fixed-length segment decoding, TreePO leverages local uncertainty to warrant additional branches. By amortizing computation across common prefixes and pruning low-value paths early, TreePO essentially reduces the per-update compute burden while preserving or enhancing exploration diversity. Key contributions include: (1) a segment-wise sampling algorithm that alleviates the KV cache burden through contiguous segments and spawns new branches along with an early-stop mechanism; (2) a tree-based segment-level advantage estimation that considers both global and local proximal policy optimization. and (3) analysis on the effectiveness of probability and quality-driven dynamic divergence and fallback strategy. We empirically validate the performance gain of \modelname on a set reasoning benchmarks and the efficiency saving of GPU hours from 22% up to 43% of the sampling design for the trained models, meanwhile showing up to 40% reduction at trajectory-level and 35% at token-level sampling compute for the existing models. While offering a free lunch of inference efficiency, TreePO reveals a practical path toward scaling RL-based post-training with fewer samples and less compute.