论文检索

Reinforcement Learning · Deep RL

Shiyi Wang, Yuyuan Chen, Peter Potaptchik, Jaeyeon Kim, Michael Albergo

Masked diffusion large language models (dLLMs) are a promising alternative to autoregressive generation. While reinforcement learning (RL) algorithms have been adapted to be compatible with dLLMs for fine-tuning them, their reliance on the computation of the marginal likelihood to evaluate policy objectives is intractable. To overcome this, we exploit a dynamical relation between the unmasking posterior of the base model and that which targets the reward-tilted distribution to derive Discrete Tilt Matching (DTM), an algorithm that avoids intractable likelihood evaluation entirely. DTM can be phrased as a cross-entropy loss that only requires forward evaluation of rewards and whose variance can be adaptively controlled, improving training stability. We motivate DTM on maze planning tasks, and show that fine-tuning LLaDA-8B-Instruct with DTM achieves higher accuracy at lower compute costs than prior RL-based fine-tuning methods across the Sudoku, Countdown, and MATH500 benchmarks.

Theory · Reinforcement Learning and Planning

Ryan Anderson, Guido Montufar

We study the geometry of feasible value functions in infinite-horizon partially observable Markov decision processes (POMDPs) under memoryless stochastic policies. Our main contribution is a characterization of the feasible set of value functions as a semi-algebraic set, defined by explicit polynomial inequalities determined by the transition dynamics, observation kernel, and reward structure of the POMDP. This result extends prior work for fully observable Markov decision processes, where the feasible set is known to be a polytope, to the substantially more intricate partially observable setting. In contrast to the polyhedral structure arising in MDPs, partial observability induces fundamentally nonlinear constraints, leading to a richer and more complex geometric structure. Our geometric characterization provides new insight into the landscape of policy optimization in both MDPs and POMDPs, and reveals qualitative phenomena unique to partial observability, including the emergence of isolated local maximizers of the long-term reward and their dependence on the initial state distribution.

Theory · Reinforcement Learning and Planning

Abdullah Akgül, Gulcin Baykal, Manuel Haussmann, Mustafa Mert Çelikok, Melih Kandemir

Optimal control of complex environments with robotic systems faces two complementary and intertwined challenges: efficient organization of sensory state information and far-sighted action planning. Because the reinforcement learning framework addresses only the latter, it tends to deliver sample-inefficient solutions. Active inference is the state-of-the-art process theory that explains how biological brains handle this dual problem. However, its applications to artificial intelligence have thus far been limited to extensions of existing model-based approaches. We present a formal abstraction of reinforcement learning algorithms that spans model-based, distributional, and model-free approaches. This abstraction seamlessly integrates active inference into the distributional reinforcement learning framework, making its performance advantages accessible without transition dynamics modeling.

Theory · Reinforcement Learning and Planning

Yifan Jiang, Jiasheng Pan, Mengtian Li, Li Jin

We study decentralized multi-agent reinforcement learning (MARL) for networked service systems with affinity in the presence of Byzantine nodes. The way that a server processes a job depends on an affinity state that captures the correlation between the job and the server. Each node learns a local control policy via an actor-critic algorithm with linear function approximation over inherently unbounded space of traffic states, while exchanging parameter information with neighbors through a communication graph. A set of Byzantine agents can exploit the unbounded state space and the resulting stochastic variance to compromise the consensus mechanism, destabilizing both learning and queuing processes. To address this vulnerability, we propose a resilient consensus-based MARL algorithm with momentum-based smoothing, which mitigates adversarial parameter manipulation and guarantees traffic stability under mild assumptions. We prove that the cooperative agents’ policies converge almost surely to a bounded neighborhood of a stationary solution of the global objective. We demonstrate the effectiveness and generality of the proposed framework in several representative service systems, including semantic routing for large language model serving, distributed polling in cloud computing, and smart manufacturing logistics.

Theory · Reinforcement Learning and Planning

Vagul Mahadevan, Claire Chen, Shuze Liu, Shangtong Zhang

Stochastic approximations (SA)--algorithms which derive their power through the use of random, incremental updates--are at the heart of reinforcement learning (RL). Expanding the theory of SA has established rigorous results concerning the most important algorithms in RL, including stochastic gradient descent and temporal difference learning. In this work, we focus on two-timescale stochastic approximations, a class which notably includes temporal difference learning with gradient correction (TDC) and actor-critic methods. Prior work has developed stability (boundedness) and convergence criteria for two-timescale SA under i.i.d. noise, but analogous results for Markovian noise have remained elusive--a critical issue since RL data are generated by a Markov chain, making i.i.d. assumptions unrealistic. To address this gap, we present the first stability result and the first asymptotic convergence result for two-timescale schemes with Markovian noise under general, verifiable conditions--notably, without resorting to projected variants of the schemes or requiring the noise to be in a compact space. As a key application, we contribute the first asymptotic convergence proof of TDC, an off-policy prediction algorithm with linear approximation and eligibility traces. Together, our results extend SA theory, establishing the first theoretical foundation for analysis of two-timescale algorithms with the realistic noise models inherent to RL.

Theory · Reinforcement Learning and Planning

Muhammed Emrullah Ildiz, Halil Alperen Gozeten, Ege Onur Taga, Samet Oymak

State-of-the-art reasoning models can utilize long chain-of-thought to solve sophisticated coding and math problems. During this process, the model often attemps at a solution multiple times by utilizing verification and self-reflection capabilities. In this work, we view a long CoT as a process where the model makes K attempts at solving a problem in which each attempt is allowed to build on earlier solutions. This way, we formalize long CoT as a pass@K problem with dependent samples. Under this formalism, we derive the policy gradient and RL algorithms for optimizing long CoT reward and derive how each attempt should be weighed for unbiased gradient computation while maintaining small variance. Our theory reveals how the self-correction capability and dense feedback influence the training and eventual performance of long CoT-based reasoning. We provide both synthetic and real experiments corroborating our theory and the benefits of the associated algorithms. As a by product, our research also reveals when verification and long chain-of-thought is beneficial over parallel sampling strategies and the role of the model capability.

Reinforcement Learning · Deep RL

Haowen Sun, Liqi Huang, Mingyang Li, Sihua Ren, Xinzhe Chen, Chengzhong Ma, Zeyang Liu, Xingyu Chen, Xuguang Lan

Reinforcement learning from demonstrations (RLfD) offers a promising method for robotic manipulation with sparse rewards. However, limited demonstrations often cause agents to encounter out-of-distribution states where world models produce poor predictions. In multi-stage tasks, jointly optimizing a learned reward function and policy introduces a moving target problem, and the resulting non-stationarity intensifies the impact of uncertainty on policy learning. In this work, we propose QUEST, a model-based RL framework that adaptively switches between exploration and exploitation guided by uncertainty to achieve stable and efficient learning. Specifically, our approach employs intrinsic rewards to capture environmental stochasticity, leverages ensemble dynamics for uncertainty-guided planning, and introduces a hybrid sampling strategy to prioritize rare successful stage transitions. We evaluate QUEST on challenging sparse-reward manipulation tasks with limited expert demonstrations. Results show that QUEST outperforms state-of-the-art methods by 17\% on average, with gains increasing to 60\% on difficult tasks. We further demonstrate successful zero-shot sim-to-real transfer on three real-world tasks.

Reinforcement Learning · Deep RL

Tianyi Zhang, Likun Wang, Guojian Zhan, Feihong Zhang, Yang Guan, Yao Lyu, Shengbo Li

Planning-driven model-based (modelic) reinforcement learning has achieved impressive success in continuous control tasks but predominantly relies on zero-order optimizers like Model Predictive Path Integral (MPPI). While robust for global exploration, MPPI updates actions solely through sampling and neglects the smooth return gradients inherent in structured dynamics that guide fine-grained search. To complement MPPI’s robustness with gradient-guided precision, we first propose \textbf{La}ngevin \textbf{R}ollout \textbf{O}ptimization (LaRO), which leverages return gradients to refine actions via Langevin dynamics, achieving reliable local convergence without sacrificing multimodal exploration. This is supported by a score-augmented world model that jointly learns dynamics and a score function within a unified latent space, facilitating efficient and accurate gradient estimation for real-time planning. Second, we combine MPPI and LaRO through a simple yet effective choice mechanism, termed \textbf{M}aximum \textbf{L}ook-\textbf{A}head \textbf{P}lanning (MLAP). Finally, we instantiate MLAP within the latest BOOM algorithm, replacing its MPPI-only planner and yielding BOOM-L. Empirical results on the DeepMind Control Suite and Humanoid Bench demonstrate that BOOM-L consistently outperforms strong baselines in both sample efficiency and final performance.

Reinforcement Learning · Deep RL

Zhan Su, Peixi Peng, Xinyu Hu, Cong Li, Yisen Zhao, Zhuojian Li, Yonghong Tian, Fanqi Shen

Most reinforcement learning (RL) baselines maximize future cumulative rewards with a fixed single discount factor, which limits their performance in complex sequential decision-making tasks due to a failure to balance short-term objectives and long-term planning. To address this issue, this paper focuses on a multi-timescale critic framework, where each component corresponds to a Q-value with a distinct discount factor. Two key improvements are proposed: (1) A Neural Reward Decoder reconstructs the reward sequence from multi-scale Q-values, with value and reward reconstruction losses enhancing Q-value estimation consistency; (2) A cross-attention-based Q-weight predictor adaptively adjusts Q-value weights via current observations to generate the final Q-value for policy optimization. Extensive experiments on DMControl and CARLA benchmarks demonstrate that our method significantly outperforms state-of-the-art (SOTA) baselines. Furthermore, we validate the framework's generalizability by integrating it with both off-policy (SAC, DrQ-v2) and on-policy (PPO) algorithms, achieving consistent performance gains. The code is available in the supplementary material.

Reinforcement Learning · Planning

Yunxiang LI, Mark Schmidt, Reza Babanezhad, Sharan Vaswani

Temporal difference (TD) learning is a fundamental algorithm for estimating value functions in reinforcement learning. Recent finite-time analyses of TD with linear function approximation quantify its theoretical convergence rate. However, they often require setting the algorithm parameters using problem-dependent quantities that are difficult to estimate in practice --- such as the minimum eigenvalue of the feature covariance ($\omega$) or the mixing time of the underlying Markov chain ($\tau_\text{mix}$). In addition, some analyses rely on nonstandard and impractical modifications, exacerbating the gap between theory and practice. To address these limitations, we use an exponential step-size schedule with the standard TD(0) algorithm. We analyze the resulting method under two sampling regimes: independent and identically distributed (i.i.d.) sampling from the stationary distribution, and the more practical Markovian sampling along a single trajectory. In the i.i.d. setting, the proposed algorithm does not require the knowledge of problem-dependent quantities such as $\omega$, and attains the optimal bias-variance trade-off for the last iterate. In the Markovian setting, we propose a regularized TD(0) algorithm with an exponential step-size schedule. The resulting algorithm achieves a comparable convergence rate to prior works, without requiring projections, iterate averaging, or knowledge of $\tau_\text{mix}$ or $\omega$.

Theory · Reinforcement Learning and Planning

Yike Zhao, Onno Eberhard, Malek khammassi, Ali Sayed, Michael Muehlebach

The family of linear recurrent neural networks has shown strong performance as recurrent memory units in partially observable reinforcement learning. We provide a theoretical justification for their empirical effectiveness by constructing and studying two linear filters: (i) the first exactly reproduces the pre–softmax logits of the belief vector in a hidden Markov model (HMM) under a deterministic transition matrix, thereby serving as a sufficient statistic for optimal policy learning, (ii) the second achieves vanishing state-decoding error under a nearly deterministic transition matrix, thus reducing state ambiguity to near zero. The results extend to action-controlled HMMs, where the corresponding linear filters become time-varying with action-dependent dynamics. We illustrate our main results through numerical experiments and further show that the constructed linear filter serves as a strong feature extractor in a small reinforcement learning game.

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.

Theory · Reinforcement Learning and Planning

Viktor Stein, Adwait Datar, Nihat Ay

Kullback-Leibler divergence (KL) regularization is widely used in reinforcement learning, but it becomes infinite under support mismatch and can degenerate in low-noise limits. Utilizing a unified information-geometric framework we introduce (Kalman)-Wasserstein-based KL analogues by replacing the Fisher–Rao geometry in the dynamical formulation of the KL with transport-based geometries, and we derive closed-form values for common distribution families. These divergences remain finite under support mismatch and yield a geometric interpretation of regularization heuristics used in Kalman ensemble methods. We demonstrate the utility of these divergences in KL-regularized optimal control. In the fully tractable setting of linear time-invariant systems with Gaussian process noise, the classical KL reduces to a quadratic control penalty that becomes singular as process noise vanishes. Our variants remove this singularity and yield well-posed problems. On a double integrator and a cart-pole example, the resulting controls outperform KL-based regularization.

Reinforcement Learning · Planning

Axel Benyamine, Julien Grand-Clément, Marek Petrik, Michael Jordan, Alain Oliviero Durmus

In this paper, we propose a general theory of ambiguity-averse MDPs, which treats the uncertain transition probabilities as random variables and evaluates a policy via a risk measure applied to its random return. This ambiguity-averse MDP framework unifies several models of MDPs with epistemic uncertainty for specific choices of risk measures. We extend the concepts of value functions and Bellman operators to our setting. Based on these objects, we establish the consequences of dynamic programming principles in this framework (existence of stationary policies, value and policy iteration algorithms), and we completely characterize law-invariant risk measures compatible with dynamic programming. Our work draws connections among several variants of MDP models and fully delineates what is possible under the dynamic programming paradigm and which risk measures require leaving it.

Theory · Reinforcement Learning and Planning

Federico Corso, Marco Mussi, Alberto Maria Metelli

Stability is a property of fundamental importance in real-world systems. Although it has been widely studied and well understood in *control theory* (CT) for deterministic systems, it is largely overlooked in stochastic systems such as *Markov decision processes* (MDPs). In this paper, we aim to translate the steady-state control problem, well established in CT, where the goal is to synthesize a controller with prescribed asymptotic stability properties, into the MDP framework. To this end, we propose the novel *fast-mixing steady-state* (FMSS) problem. Given an ergodic MDP and a target steady-state distribution, the objective is to synthesize a Markovian policy that induces this distribution with the fastest possible convergence rate. Addressing this problem requires controlling the spectral properties of the induced *Markov chain* (MC) transition matrix, which generally leads to non-convex programs. Thus, we derive a tractable surrogate objective that leads to a convex program, whose properties we study in terms of approximation quality, feasibility, and computational complexity. We then move to the learning setting and propose an "offline" sample-based algorithm for FMSS (FMSS-SV), designed for tabular MDPs, in which the environment’s transition model is estimated from data. We quantify the impact of transition model estimation errors on both the objective value and the learned policy, and provide a finite-sample complexity analysis.

Reinforcement Learning · Planning

Robert Gieselmann, Mihai Samson, Federico Pecora, Jeremy Wyatt

Generative models have emerged as a powerful paradigm for AI planning, yet their performance remains constrained by training data distribution. One approach is to improve generated solutions during inference by scaling test-time compute. A more efficient alternative is to optimize the inferential process itself. In this paper, we show that a modified version of a classical Open-Closed List (OCL) search provides just such an efficient inferential procedure. Our algorithm synergizes two learned components: a generative model that performs fast rollouts from specific reasoning paths and a value model that manages which of many possible reasoning lines to follow. We present novel contributions in exploration control and how learned models are integrated within the OCL framework. Experimental evaluation across multiple combinatorial planning domains shows that our approach consistently outperforms baseline search algorithms in both computational efficiency and solution quality.

Applications · Chemistry, Physics, and Earth Sciences

Stefan Pranger, Bernhard Ramsauer, Oliver Hofmann, Bettina Könighofer

Scanning tunneling microscopy (STM) enables precise manipulation of individual atoms and molecules, offering a pathway to constructing nanoscale assemblies with rich quantum mechanical behavior. Despite its potential, STM-based fabrication remains limited by the inherent complexity of manipulation procedures and the extensive manual effort required. In this work, we take a substantial step toward autonomous manufacturing with STMs by introducing a novel AI-based planning framework for molecular assembly and a high-fidelity simulation environment. Our framework computes collision-free assembly plans that minimize the total distance traveled by molecules. Given an assignment of molecules to target positions, satisfiability solving is used to compute execution schedules in which each molecule has an empty corridor available when it is scheduled to move. Reinforcement learning (RL) agents then execute sequences of STM actions to manipulate molecules to their targets. We further introduce NanoAssemblyGym, a high-fidelity simulation environment for molecular manipulation built on the Gymnasium API, allowing seamless integration with existing RL libraries and workflows. Using NanoAssemblyGym, we demonstrate autonomous assembly of structures containing up to 420 molecules.

Jiajun Zhang, Yuheng Jing, Zeyu Cui, Hao Zheng, Wentao Chen, Kaixin LI, Jiaxi Yang, Tianbao Xie, Zeyao Ma, Tianyi Bai 等

The rapid evolution of Large Language Models (LLMs) has empowered even non-programmers to create visually appealing frontend mini-games with a single instruction. However, open-source models significantly lag behind proprietary counterparts in this domain. The core bottleneck is the lack of an evaluation mechanism that balances reliability with scalability, as existing methods either fail to verify dynamic interactivity or incur prohibitive computational costs. To bridge this gap, we introduce ALIVE (Aligning LLMs via Interactive Visual Execution), a high-throughput framework that leverages one-shot planning and DOM-based analysis to automatically evaluate generated games at scale. Extensive experiments demonstrate that ALIVE significantly outperforms static judge baselines in identifying functional flaws while remaining orders of magnitude more efficient than GUI agents. Functioning as a scalable `pre-flight' evaluation layer, it curates high-quality data for Supervised Fine-Tuning (SFT) and provides a consistent reward signal for Reinforcement Learning (RL). We leverage this pipeline to train ALIVE-Coder, a model achieving superior performance in interactive frontend generation. To the best of our knowledge, our work offers the first scalable path to evaluate and optimize interactive code, substantially advancing open-source capabilities.

Theory · Reinforcement Learning and Planning

Harin Lee, Kevin Jamieson

We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps. We propose an algorithm that combines the augmentation method and the upper confidence bound approach. For tabular Markov decision processes (MDPs), we derive a regret bound of $\tilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})$, where $S$ and $A$ are the cardinalities of the state and action spaces, $H$ is the time horizon, $K$ is the number of episodes, and $D_{\max}$ is the maximum length of the delay. We also provide a matching lower bound up to logarithmic factors, showing the optimality of our approach. Our analytical framework formulates this problem as a special case of a broader class of MDPs, where their transition dynamics decompose into a known component and an unknown but structured component. We establish general results for this abstract setting, which may be of independent interest.

Theory · Reinforcement Learning and Planning

Orin Levy, Aviv Rosenberg, Alon Peled-Cohen, Yishay Mansour

We introduce OPO-CMDP, the first policy optimization algorithm for stochastic Contextual Markov Decision Process (CMDPs) under general offline function approximation. Our approach achieves a high probability regret bound of $\widetilde{O}(H^4\sqrt{T|S||A|\log(|\mathcal{F}||\mathcal{P}|)}),$ where $S$ and $A$ denote the state and action spaces, $H$ the horizon length, $T$ the number of episodes, and $\mathcal{F}, \mathcal{P}$ the finite function classes used to approximate the losses and dynamics, respectively. This is the first regret bound with optimal dependence on $|S|$ and $|A|$, directly improving the current state-of-the-art (Qian, Hu, and Simchi-Levi, 2024). These results demonstrate that optimistic policy optimization provides a natural, computationally superior and theoretically near-optimal path for solving CMDPs.