The paper presents an exponential lower bound on the number of iterations required by Howard's policy iteration algorithm for deterministic discounted Markov decision processes with at most two actions per state, when the discount factor is part of the input. This result shows that Howard's method cannot be strongly polynomial in this setting and establishes an exponential gap compared to the simplex method with Dantzig's pivoting rule, which remains strongly polynomial. Even with rewards limited to logarithmic bit length, a stretched‑exponential lower bound is achieved, highlighting a fundamental difference between decentralized, simultaneous improvements and Dantzig's coordinated single‑action selection.
By Han Zhong, Yinyu Ye
The paper introduces OMAF, an Online MARL framework that uses a one-step Transformer-based flow policy to generate coordinated actions efficiently. By replacing costly iterative sampling with a single-step action generation and a joint optimization scheme that couples softmax Q-value estimation with flow policy objectives, OMAF maintains expressive multimodal behavior while improving training speed. Experiments on 10 tasks from MPE and MAMuJoCo demonstrate up to 3.4× higher returns and 10.5× better sample efficiency compared to baseline methods.
By Zhuoran Li, Yunzhan Li, Xun Wang, Yihan Du, Longbo Huang
The paper introduces a computationally efficient algorithm for infinite-horizon average-reward constrained Markov decision processes (CMDPs) under weak communication. It achieves a high-probability regret and cumulative constraint violation of ×O(√T) in the tabular setting, matching optimal dependence up to logarithmic factors. The method augments the state with cumulative constraint violation, reshapes rewards using a Huber potential, and applies finite-horizon approximation with optimistic value iteration to maintain bounded per-step rewards.
By Kihyun Yu, Seoungbin Bae, Dabeen Lee
The paper presents a hierarchical reinforcement learning framework for jointly optimizing routing and switch placement in chip design. It builds solutions from a minimal routing graph using three operations—switch expansion, switch placement, and route refinement—that maintain routing validity by construction. Neural‑guided Gumbel Monte Carlo Tree Search and pretraining across floorplans are shown to improve solution quality over non‑learning methods.
By Dorian Gailhard, Ugo Lecerf, Enzo Tartaglione, Donatello Conte, Jhony H. Giraldo
The paper introduces a reinforcement learning-guided framework for graph transformations aimed at optimizing sparse triangular solve (SpTRSV) kernels. By treating graph transformation as a sequential decision-making task, the RL agent learns matrix-dependent policies that reduce the number of levels by 23% and the coefficient of variation of level costs by 29%, while modifying less than 1% of matrix rows. Experimental results on real-world sparse matrices show significant performance improvements and demonstrate that the learned policies can transfer to unseen matrices via curriculum learning and fine-tuning.
By Buse Y{\i}lmaz
The paper introduces GAP-DPO, a method for personalizing large language models by selecting preference pairs based on gradient alignment with user utility. It formalizes personalized preference learning as a geometry‑aligned optimization problem, showing that off‑policy sampling can shift DPO updates from error correction to reinforcement when preference margins align with utility gradients. Experiments demonstrate that GAP‑DPO improves stylistic fidelity, preference alignment, and overall generation quality over standard DPO variants.
By Ruoming Jin, Xinyu Li, Hao Zhou, Jianfeng Zhu, Ruixin Guo, Feodor Dragan, Lei Xu, Haixun Wang, Yang Zhou
The paper introduces Decision Titan, a variant of the Decision Transformer that incorporates Test‑Time Training (TTT) layers to store episodic memories in network parameters. It evaluates this architecture on the X‑Maze environment, showing that Decision Titan can learn long‑term dependencies up to 20 times longer than its context window and generalise to sequences 1.7 times longer than the training data. The study also finds that temporal generalisation depends on the choice of time embeddings and that the ability to learn long‑term dependencies hinges on how relevant information is encoded.
By Jude Waide, Robert Lieck
The paper introduces Quasar, a model‑free Q‑learning algorithm that guarantees asymptotic convergence for reachability objectives in Markov Decision Processes that are free of non‑terminal maximal end components (MECs). Unlike prior model‑based methods, Quasar does not estimate transition probabilities, reducing memory usage from O(|S|²|A|) to O(|S||A|). Experiments on the Quantitative Verification Benchmark Set show that Quasar converges to optimal policies with far fewer samples than existing state‑of‑the‑art model‑based approaches.
By Lu-Chin Chang, Suguman Bansal
The paper introduces the Homomorphic Advantage Operator (HAO), a stabilization framework for reinforcement learning under fully homomorphic encryption (FHE). HAO applies a zero‑mean centering projection to temporal‑difference targets, eliminating the uniform state‑value baseline that causes the Bellman drift and keeping network pre‑activations within safe polynomial approximation bounds. Experiments on tabular MDPs, an encrypted CartPole environment, and a logistics routing benchmark show that HAO prevents boundary breaches entirely, improves optimal policy accuracy by 18 percentage points, and remains stable even with added Gaussian noise.
By Abid Mohamed Nadhir, Ahmad Al Hanbali, Beggas Mounir
The paper reports that applying reinforcement learning (RL) to the Kimi K2.7 Code model on 1,700 agentic coding tasks improves its performance on six external benchmarks. After a single epoch of GSPO training on a rank‑32 LoRA adapter, pass‑@1 scores increased across all benchmarks, with significant gains even on data released after training. The trained model also reduces agent steps and avoids common failure modes such as dropping requirements or breaking existing behavior.
By Sushant Mehta, Logan Ritchie, Edwin Chen
Architectural Sampling is a training‑free technique that improves test‑time scaling for frozen vision‑language models by generating diverse candidates through distinct forward computations. It achieves this by reusing selected blocks of decoder layers, varying block location and repetition count, thereby creating computational diversity without updating weights or adding parameters. Experiments on five Qwen checkpoints across twelve multimodal benchmarks show that this method raises pass@9 by an average of 6.58 percentage points over standard temperature sampling, with early‑layer reuse delivering the strongest gains and lower lexical overlap in the generated candidates.
By Akshit Singh, Shyam Marjit, Wei Lin, Leonid Karlinsky, M. Jehanzeb Mirza
The paper presents an analysis of asynchronous reinforcement learning for large language model post‑training, focusing on the impact of stale rollouts. It derives a convergence bound for GRPO‑style algorithms that balances the gradient estimator’s second moment and bias, and introduces a new group‑mass capping GRPO (GMC‑GRPO) method that reduces delay‑dependent bias. Experiments on Qwen3 models and reasoning benchmarks show that GMC‑GRPO outperforms existing baselines in robustness to large rollout delays.
By Qijia He, Ruinan Jin, Jun Luo, Shaofeng Zou, Yingbin Liang
The paper introduces a closed‑loop framework that refines structured policies for imitation learning by using large language models (LLMs) to analyze policy rollouts logged as semantically meaningful tabular data. By prompting the LLM to generate diagnostic code, the method identifies and corrects suboptimalities in the policy structure without human instruction. Experiments on car racing and door opening tasks show up to 15% performance improvement over zero‑shot LLM‑generated structures and a 75% reduction in compute needed to reach the same reinforcement learning performance.
By Feiyu Gavin Zhu, Qi Xu, Zhifei Deng, Zhigang Hua, Luke Simon, Jean Oh, Reid Simmons
The paper introduces a Markov chain Monte Carlo (MCMC) sampling algorithm that transforms off‑policy traces into more on‑policy data for supervised finetuning (SFT). By tailoring the data distribution rather than changing the learning objective, the method allows SFT to match or surpass traditional post‑training techniques such as reinforcement learning across tasks like scientific skill acquisition, mathematical reasoning, and open‑ended expertise. The resulting models generalize better, forget less, and exhibit strong distributional performance, demonstrating that sampling can serve as a model‑native operator for broader post‑training applications.
By Aayush Karan, Sitan Chen, Yilun Du
KaliBench is a fine‑grained benchmark that evaluates large language models’ ability to translate natural‑language queries into executable command‑line instructions for Kali Linux. It contains 8,504 query–command pairs covering 1,642 tools across 23 capability dimensions and 5 security phases, and uses a deterministic, alias‑aware evaluation pipeline with multi‑stage verification (LLM validation, sandboxed execution, and human refinement). The benchmark also supports runtime‑free verifiable rewards, enabling training improvements that bring smaller models close to the performance of a 685B MoE model.
By Pengfei Li, Naufal Suryanto, Sicheng Zhang, Muzammal Naseer
The paper introduces MSARL, a Multi‑Small‑Agent Reinforcement Learning framework that separates reasoning from tool use. A single Reasoning Agent plans and decomposes tasks, while multiple specialized Tool Agents handle specific external tools, each trained with imitation learning and reinforcement learning using role‑specific rewards. Experiments on mathematical problem solving with code execution show that MSARL improves reasoning stability and final‑answer accuracy compared to single‑agent baselines, and the architecture generalizes to other tool‑use tasks.
By Dayu Wang, Yutong Liu, Jiaye Yang, Weikang Li, Jiahui Liang, Yang Li
The paper presents a reinforcement learning framework for training autonomous large language model agents to act as sellers in multi-product bargaining markets. It models the problem as a Partially Observable Markov Decision Process and introduces a structured message protocol to map natural language into a regulated decision space. Using Reinforcement Learning from Verifiable Rewards, the trained agents match limited inventory to buyers more effectively, achieving seller surplus extraction and allocation quality comparable to or better than trillion‑parameter models, and generalize to unseen market conditions.
By Shuze Daniel Liu, Claire Chen, Jiuqi Wang, David Simchi-Levi, Thorsten Joachims
The paper introduces Uncertainty‑Normalized Margin DPO (UNM‑DPO), a method that augments direct preference optimization with strength‑dependent margins and a learned prompt scale derived from a heteroskedastic Bradley‑Terry model. Two training objectives—advantage‑only (AO) and whole‑residual (WR)—compare implicit rewards from response log‑probability ratios, with WR enabling identification of the prompt scale and a practical learning procedure. Building on WR, ULNM‑DPO‑WR further normalizes rewards by response length, and experiments on HelpSteer2/3 and AlpacaEval show higher win rates, mean rewards, and shorter responses compared to baseline DPO and SimPO.
By Sadegh Khorasani, Petrus Mikkola, Matthias Grossglauser
The paper introduces WSP-CVaR-RLHF, a risk‑sensitive reinforcement learning algorithm that learns from human feedback while handling corrupted or adversarial preference labels. It uses uncertainty‑weighted reward estimation and optimistic CVaR planning to achieve a regret bound that separates clean statistical cost from corruption penalties. Experiments with four adversarial attacks show that the method consistently reduces cumulative regret compared to an unweighted robust baseline while maintaining confidence‑set coverage.
By Xinyi Ni, Lifeng Lai
The paper introduces CG-OMatG, an equivariant Riemannian flow-based generative model that predicts molecular crystal structures using a coarse-grained, hierarchical representation. It treats molecules as rigid bodies, performs inter- and intra-molecular message passing, and learns to reconstruct molecule centroids, orientations, and lattice parameters conditioned on chemical species and conformer geometry. The model is trained on OMC25 and CSD datasets, fine-tuned with policy gradient reinforcement learning to favor low-energy structures, and validated against a CSP blind test benchmark using COMPACK packing-similarity analysis.
By Thomas Egg, Harry Winston Sullivan, Maya M. Martirossyan, Philipp H\"ollmer, Cheng Zeng, Adrian Roitberg, Mingjie Liu, Richard Hennig, Sapna Sarupria, Ellad B. Tadmor, Stefano Martiniani