论文检索

Minh-Tung Luu, Hwanhee Kim, Younghwan Lee, Chang D. Yoo

Conveying complex objectives to reinforcement learning (RL) agents often requires meticulous reward engineering. Preference-based RL (PbRL) offers a promising alternative by learning reward functions from human feedback, but its scalability is hindered by high labeling costs. Inspired by advances in Video Foundation Models (ViFMs), we present Video-based Optimal Transport Preference (VOTP), a semi-supervised framework that learns effective reward functions from only a handful of labels. By leveraging optimal transport to align visual trajectories within the rich representation space of ViFMs, VOTP effectively generates high-fidelity pseudo-labels for large amounts of unlabeled data, substantially reducing human supervision. Extensive experiments across locomotion and manipulation benchmarks demonstrate the superiority of VOTP, which outperforms state-of-the-art offline PbRL methods under limited feedback budgets. We also showcase the robustness of VOTP in the presence of visual distractors and validate its utility on real robotic tasks, where it learns meaningful rewards with minimal human input.

General Machine Learning · Representation Learning

Huaihai Lyu, Chaofan Chen, Yuheng Ji, Xiansheng Chen, Pengwei Wang, Shanghang Zhang, Changsheng Xu

We formulate the learning of generalist Vision-Language-Action (VLA) models as a Gromov-Wasserstein alignment problem, aiming to map semantically similar VL embeddings to physically similar motion primitives. However, solving this is challenging due to the mathematical heterogeneity between the domains: the semantic space of vision-language is topologically linear and isotropic, while the physical manifold of robotic action is non-Euclidean and anisotropic. As a result, direct regression approaches fail due to the disjoint metric structures of these domains, making standard distance minimization ill-posed. To resolve this incompatibility, we introduce LAST (Lie-algebraic Action Space Tokenizer). LAST reconstructs the action space to establish a more consistent metric alignment between the VL and Action modalities. Specifically, LAST bridges the heterogeneity via two stages: (1) *Global Topological Linearization*, which linearizes the action manifold through Lie-algebraic mapping, converting trajectories into a fixed-length, physically additive representation; and (2) *Local Metric Discretization*, where the representation is discretized hierarchically into schemas and whitened residuals, establishing a mathematical isomorphism with the isotropic Euclidean metric. By addressing the structural mismatch globally and locally, LAST enables VLA models with enhanced convergence and generalizability.

Deep Learning · Theory

Adel Javanmard, Baharan Mirzasoleiman, Vahab Mirrokni

Large Language Models (LLMs) are pretrained on massive datasets and later instruction-tuned via supervised fine-tuning (SFT) or reinforcement learning (RL). Best practices emphasize large, diverse pretraining data, whereas post-training operates differently: SFT relies on smaller, high-quality datasets, while RL benefits more from scale, with larger amounts of feedback often outweighing label quality. Yet it remains unclear why pretraining and RL require large datasets, why SFT excels on smaller ones, and what defines high-quality SFT data. In this work, we theoretically analyze transformers trained on an in-context weight prediction task for linear regression. Our analysis reveals several key findings: $(i)$ balanced pretraining data can induce latent capabilities later activated during post-training, and $(ii)$ SFT learns best from a small set of examples challenging for the pretrained model, while excessively large SFT datasets may dilute informative pretraining signals. In contrast, RL is most effective on large-scale data that is not overly difficult for the pretrained model. We validate these theoretical insights with experiments on large nonlinear transformer architectures.

Reinforcement Learning · Batch/Offline

Minh-Tung Luu, Hwanhee Kim, Younghwan Lee, Chang D. Yoo

Conveying complex objectives to reinforcement learning (RL) agents often requires meticulous reward engineering. Preference-based RL (PbRL) offers a promising alternative by learning reward functions from human feedback, but its scalability is hindered by high labeling costs. Inspired by advances in Video Foundation Models (ViFMs), we present Video-based Optimal Transport Preference (VOTP), a semi-supervised framework that learns effective reward functions from only a handful of labels. By leveraging optimal transport to align visual trajectories within the rich representation space of ViFMs, VOTP effectively generates high-fidelity pseudo-labels for large amounts of unlabeled data, substantially reducing human supervision. Extensive experiments across locomotion and manipulation benchmarks demonstrate the superiority of VOTP, which outperforms state-of-the-art offline PbRL methods under limited feedback budgets. We also showcase the robustness of VOTP in the presence of visual distractors and validate its utility on real robotic tasks, where it learns meaningful rewards with minimal human input.

Applications · Computer Vision

Minghang Zheng, Zihao Yin, YI YANG, Yuxin Peng, Yang Liu

Multi-modal Large Language Models (MLLMs) have achieved remarkable progress in video temporal grounding (VTG) with the introduction of reinforcement learning (RL) for generating reasoning paths. However, existing models often produce superficial reasoning, such as providing generic video descriptions, which offer limited guidance for precise temporal localization. This limitation stems from (1) inefficient random exploration in RL, and (2) reward functions that focus solely on the answer correctness while ignoring reasoning quality. To address these issues, we propose TaRO (Temporal-Aware Reasoning Optimization), a framework that explicitly enhances the model’s ability of thinking with time. First, we introduce a Constructive Reasoning Exploration that leverages pre-generated dense captions to construct reasoning paths grounded in explicit visual cues and timestamps, enabling efficient exploration of high-quality time-aware reasoning. Second, to evaluate reasoning quality, we design a Temporal-Sensitivity Reward. We postulate that high-quality reasoning should be anchored to specific events and timestamps. If the event boundary under thinking is disrupted (e.g., via frame shuffling), such reasoning should become invalid, leading to a drop in the logit of the reasoning path. We utilize this drop as a critique of reasoning quality. Finally, TaRO follows a progressive curriculum, which starts by utilizing this reward to select better constructed reasoning paths, and evolves to a free exploration phase where the model autonomously generates effective reasoning. Extensive experiments demonstrate that TaRO improves temporal reasoning and achieves state-of-the-art performance on VTG benchmarks.

Theory · Game Theory

Ioannis Anagnostides, Ioannis Panageas, Nikolas Patris, Tuomas Sandholm

Follow the regularized leader (FTRL) is the premier algorithm for online optimization. However, despite decades of research on its convergence in constrained optimization---and potential games in particular---its behavior remained hitherto poorly understood. In this paper, we establish that FTRL can take exponential time to converge to a Nash equilibrium in two-player potential games for any (permutation-invariant) regularizer and potentially vanishing learning rate. By known equivalences, this translates to an exponential lower bound for certain mirror descent counterparts, most notably multiplicative weights update. On the positive side, we establish the potential property for FTRL and obtain an exponential upper bound $\exp(O_{\epsilon}(1/\epsilon^2))$ for any no-regret dynamics executed in a lazy, alternating fashion, matching our lower bound up to factors in the exponent. Finally, in multi-player potential games, we show that fictitious play---the extreme version of FTRL---can take doubly exponential time to reach a Nash equilibrium. This constitutes an exponentially stronger lower bound for the foundational learning algorithm in games.

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.

Deep Learning · Large Language Models

Dongyue Li, Zechun Liu, Kai Yi, Changsheng Zhao, Zhenshuo Zhang, Raghuraman Krishnamoorthi, Harshit Khaitan, Hongyang Zhang, Steven Li

Quantization-aware training is widely used for language model quantization in sub-4-bit precision, by training full-precision weights with gradients computed on the quantized model. The main bottleneck for this training approach is its slow convergence and plateauing of test performance, which gets worse in lower bit-widths. While observed in prior work, its precise cause has not been carefully studied. In this paper, we analyze the convergence by computing the Hessian spectrum of the model loss throughout quantization-aware training. We find the key reason is that the model weights converge to flat surfaces near saddle points, with a large fraction of Hessian eigenvalues concentrated around zero, and the magnitude of both positive and negative eigenvalues decreases over training. Additionally, the convergence speed is slower in lower bit-widths with significantly smaller Hessian eigenvalue magnitude. Motivated by these findings, we propose an approach to accelerate quantized training with minimal overhead named WinQ. This approach periodically performs linear weight interpolation between the full-precision and quantized weights and computes gradients on noise-injected weights. Both techniques effectively regularize the Hessian and accelerate training, resulting in an algorithm broadly applicable to quantization methods. Extensive experiments show that WinQ accelerates various quantized training methods by up to 4$\times$. Under the same training budget, WinQ improves state-of-the-art sub-4-bit quantization performance by up to 8.8% relatively. Additionally, WinQ remains consistently effective across 16 settings of different language models, quantization methods, and bit-widths.

Deep Learning · Foundation Models

Wenzhe Niu, Wei He, Zongxia Xie, Jinpeng Ou, Huichuan Fan, Yuchen Ge, Yanru Sun, Ziyin Wang, Yizhao Sun, Chengshun Shi 等

Reinforcement learning has become a cornerstone for enhancing the reasoning capabilities of Large Language Models, where group-based approaches such as GRPO have emerged as efficient paradigms that optimize policies by leveraging intra-group performance differences. However, these methods typically rely on absolute numerical rewards, introducing intrinsic limitations. In verifiable tasks, identical group evaluations often result in sparse supervision, while in open-ended scenarios, the score range instability of reward models undermines advantage estimation based on group means. To address these limitations, we propose **Reinforcement Learning with Relative Rewards (RLRR)**, a framework that shifts reward shaping from absolute scoring to relative ranking. Complementing this framework, we introduce the **Ranking Reward Model**, a listwise preference model tailored for group-based optimization to directly generate relative rankings. By transforming raw evaluations into robust relative signals, RLRR effectively mitigates signal sparsity and reward instability. Experimental results demonstrate that RLRR yields consistent performance improvements over standard group-based baselines across reasoning benchmarks and open-ended generation tasks. Our source code is available at https://anonymous.4open.science/r/RLRR-55AF.

Theory · Deep Learning

Sejun Park, Yeachan Park, Geonho Hwang

Research on the expressive power of neural networks has identified the minimum depth and width of neural networks that enable universal approximation and memorization. However, existing results are derived under exact arithmetic and cannot be directly applied to real implementations on computers, which can only use a finite set of numbers and inexact machine operations with round-off errors. In this work, we study floating-point ReLU networks that have floating-point parameters and use floating-point operations. Specifically, we investigate their minimum depth and width to represent all functions from the set of floating-point vectors $\mathbb F^d$ to the set of floating-point numbers $\mathbb F$. We first show that the minimum depth for representing all functions from $\mathbb F^d$ to $\mathbb F$ is exactly three, where two layers can be sufficient if we consider a smaller domain and/or codomain. We further show that the minimum width for representing all functions from $\mathbb F^d$ to $\mathbb F$ lies between $2d$ and $2d+4$. In addition, if we restrict the domain to non-negative floats, it lies between $d$ and $d+4$, where it can be smaller for a smaller domain, even beyond $d$. Our results show that the existing results analyzed under exact arithmetic do not extend to the floating-point setup.

Jiacheng Li, Jiahui Liu, Yuqing Wang, Gaochen Cui, Xiao Zhang, Qianchuan Zhao, Ziyou Zhang, Chenghao Li

Large language models (LLMs) are increasingly used as decision modules, yet existing benchmarks provide limited coverage of long-horizon, adversarial interaction while faithfully acting on human instructions. We introduce a long-horizon Red Alert RTS benchmark with a hierarchical interface in which LLMs output budgeted, low-frequency macro/tactical intents that are executed deterministically for standardized comparison. The benchmark evaluates (i) robustness to ``rules-as-variable'' perturbations via rule-style shifts , (ii) competitive strength via Elo-style ratings from head-to-head matches, and (iii) human steerability via standardized language interventions. Beyond win/loss, we log economy growth/spending, combat loss ratio, and visibility coverage to diagnose long-horizon failure modes. Overall, the benchmark provides a reproducible and diagnostic testbed for robustness and controllability in long-horizon adversarial decision making.

General Machine Learning · Evaluation

Hadi Khalaf, Flavio Calmon, Daniel Halpern, Ariel Procaccia, Itai Shapira, Serena Wang

The standard way to evaluate language models on subjective tasks is through pairwise comparisons: an annotator chooses the "better" of two model responses for a given prompt. These comparisons are then aggregated into a single ranking via the Bradley–Terry (BT) framework, forcing heterogeneous preferences into a total order and violating basic social-choice desiderata. In contrast, social choice theory provides an alternative approach called maximal lotteries, which aggregates pairwise preferences without imposing any assumptions on their structure. However, we show that maximal lotteries can be highly sensitive to heterogeneity among annotators and across prompts. We introduce *robust lotteries*, which optimize worst-case performance under plausible shifts in the preference data. On large-scale preference datasets, robust lotteries achieve more reliable win rate guarantees across the annotator distribution and recover a stable set of top performing models.

Yana Wei, Hongbo Peng, Yanlin Lai, Liang Zhao, Kangheng Lin, En Yu, Keyu Lv, Han Zhou, Yin Tang, Haodong Li 等

We introduce the Perception Rubric Benchmark (PRB), a rubric-based evaluation framework for Multimodal Large Language Models (MLLMs) that addresses the growing gap between benchmark scores and human-perceived quality. While standard perception metrics approach saturation, they produce compressed rankings that obscure meaningful performance differences, largely due to their linear and lenient reward designs. PRB reframes evaluation from holistic scoring to rubric-based verification. It is built through a scalable hybrid automation pipeline over a stratified collection of complex, multi-domain visual inputs. Using pair-wise contrastive generation, PRB distills over 15,000 diagnostic rubric criteria that function as explicit unit tests for perception and are evaluated via a ternary protocol distinguishing benign approximations from perceptually critical errors. Experiments show that PRB decouples compressed leaderboard rankings, reveals perceptual blind spots in top-performing models, and aligns more closely with human preference than conventional metrics. Beyond evaluation, generated rubrics can be reused as inference-time verifiers, yielding consistent gains on multiple perception benchmarks. PRB provides a principled foundation for reliable and discriminative multimodal evaluation.

Deep Learning · Generative Models and Autoencoders

Zhiyuan Ouyang, Simei Huang, Zuokai Wen, Xiangyun Zhang, Junchi Yan

A probability distribution $\mathbb{P}$ is a measure on a $\sigma$-algebra, assigning mass to sets rather than points. This poses a challenge for the training of neural networks, which often struggle to reconstruct the global topology of continuous manifolds from sparse samples. We mitigate this issue by innovatively transforming $\mathbb{P}$ into a continuous function via spectral methods, providing theoretical guarantees for the convergence of the learned distribution to the true distribution. Specifically, we introduce a network, PriSpecNet, with a single-function evaluation (1-NFE) Pseudoinverse Lévy Inversion (PiLI) solver that regards generation as a fast analytical problem, eliminating the need for iterative numerical integration. By reformulating the generation in the spectral domain, we bypass the computationally expensive sampling trajectory while maintaining full compatibility with the stochastic interpolants. We test our PriSpecNet in two applications. For time series, it unifies generation and forecasting, outperforming state-of-the-art (SOTA) baselines with Context-FID reductions of 50.0\%, 41.5\%, 80.6\%, and 63.1\% on Sines, Solar, ETTh, and Stock benchmarks, respectively, also decreasing forecasting MSE by 29.8\% on Solar and 23.8\% on Stock. For vision on ImageNet $256 \times 256$, 1-NFE PiLI achieves a competitive FID of **1.66** using only **26** Gflops, representing a **170** $\times$ reduction in total Gflops compared to the 4,436 Gflops required by the advanced 25-NFE DPM-Solver++.

Deep Learning · Foundation Models

Tianyu Yu, Kechen Fang, Zihao Wan, Kaidong Zhang, Yicheng Zhang, Jun Song, Bo Zheng, Yuan Yao

Most Vision Language Models (VLMs) directly map outputs from ViT encoders to the LLM via a lightweight projector. While effective, recent analysis suggests this architecture suffers from an alignment challenge: visual features remain distant from the text space in the initial layers of the LLM, forcing the model to waste critical depth on superficial modality alignment rather than deep understanding and complex reasoning. In this work, we propose Deep Pre-Alignment (DPA), a novel architecture that replaces the standard ViT encoder with a small VLM as perceiver, ensuring visual features are deeply aligned with the text space of the target large language model. Comprehensive experiments demonstrate the effectiveness of DPA. On the 4B parameter scale, DPA outperforms baselines by 1.9 points across 8 multimodal benchmarks, with gains widening to 3.0 points at the 32B scale. Moreover, by offloading alignment to the perceiver, DPA achieves a 32.9\% reduction in language capability forgetting over 3 text benchmarks. We further demonstrate that these gains are consistent across different LLM families including Qwen3 and LLaMA 3.2, highlighting the generality of our approach. Beyond performance, DPA also offers a seamless upgrade path for current VLM development, requiring only a modular replacement for the visual encoder with marginal computation overhead.

Deep Learning · Graph Neural Networks

Jaejun Lee, Seheon Kim, Joyce Whang

Hyper-relational knowledge graphs (HKGs) effectively represent complex facts. While inferring new knowledge in HKGs is a critical problem, current methods cast it as a simple link prediction, assuming that nearly all entities and relations within a fact are known, leaving only a single blank to be filled. However, this restricted assumption may not hold in real-world scenarios in which multiple, or even all, constituent components of a fact may be missing simultaneously. To bridge this gap, we introduce a task called fact generation: generating a valid hyper-relational fact from an arbitrarily masked query, i.e., completing a partially observed fact or generating a fact from scratch. We propose KREPE, the first generative representation learning method for HKGs that learns to model the probability distributions of missing components conditioned on the local fact components and global structure of HKGs via a masked discrete diffusion. KREPE models both the intra-fact dependencies by contextual message passing and inter-fact correlations by aggregating stochastically sampled contexts. KREPE seamlessly unifies link prediction and fact generation within a single training framework, achieving state-of-the-art performance on standard HKG link prediction benchmarks and outperforming LLM-based baselines in generating novel and correct facts.

Theory · Online Learning and Bandits

Vladimir Braverman, Chen Wang, Liudeng Wang, Samson Zhou

Motivated by the recency effect in online learning, we study algorithms for single-pass \emph{sliding-window streaming multi-armed bandits (MABs)} in this paper. In this setting, we are given $n$ arms with unknown sub-Gaussian reward distributions and a parameter $W$. The arms arrive in a single-pass stream, and only the most recent $W$ arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with \emph{limited memory}, \textcolor{red}{defined as the number of stored arms}. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an \emph{approximate} best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithms. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Applications · Chemistry, Physics, and Earth Sciences

Xinyu Pang, (Andrew) Zhanke Zhou, Xuan Li, Fangrui Lv, Shanshan Wei, Sen Cui, Bo Han, Changshui Zhang

Symbolic regression (SR) stands as a cornerstone of scientific discovery, deriving mathematical expressions from observing data. Recent advances incorporate large language models (LLMs) into evolutionary optimization, typically relying on iterative refinement driven by scalar feedback (e.g., mean squared error, MSE). However, such coarse feedback lacks directional guidance for strategic lookahead and diagnostic signals to localize structural errors, thereby confining the search to a myopic trial-and-error process. Additionally, treating optimization steps as isolated episodes precludes learning from historical trajectories. Consequently, optimization often degenerates into an inefficient search with substantial computational cost. Motivated by these limitations, we propose Deliberate Evolution, an agentic framework for SR tasks that equips LLM-based candidate proposal with explicit, structured guidance. Our approach steers optimization through adaptive evolutionary operators for directional control, analytical tools for diagnostic feedback, and reflective memory for historical insight. Extensive experiments on LLM-SRBench demonstrate that our approach consistently outperforms prior baselines while using merely 40\% of the sample budget.

Social Aspects · Security

Guangyu Shen, Siyuan Cheng, Xiangzhe Xu, Yuan Zhou, Hanxi Guo, Zhuo Zhang, Xiangyu Zhang

Backdoor attacks can introduce deceptive behaviors into large language models, causing them to execute prohibited actions only when specific secret triggers appear in the input. Existing safety training methods largely fail to address this vulnerability, due to the inherent difficulty of uncovering hidden triggers embedded within the model. Motivated by recent findings on LLMs’ situational awareness, we propose a novel post-training framework that cultivates backdoor self-awareness, enabling a poisoned LLM to precisely articulate its own implanted triggers. At its core, our approach introduces an inversion-inspired reinforcement learning framework that encourages models to introspectively reason about their behaviors and gradually reverse-engineer the triggers responsible for misaligned outputs. Building upon precise trigger articulation, we further present two complementary defense strategies for mitigating and detecting backdoor threats. Experiments on five backdoor attacks, compared against six baseline methods, demonstrate that our approach has strong potential to improve the robustness of LLMs against backdoor risks.

Probabilistic Methods · Everything Else

Wenbin Zhou, Shixiang Zhu

Robust optimization safeguards decisions against uncertainty by optimizing against worst-case scenarios, yet their effectiveness hinges on a prespecified robustness level that is often chosen ad hoc, leading to either insufficient protection or overly conservative and costly solutions. Recent approaches using conformal prediction construct data-driven uncertainty sets with finite-sample coverage guarantees, but they still fix coverage targets a priori and offer little guidance for selecting robustness levels. We propose a new framework that provides distribution-free, finite-sample guarantees on both miscoverage and regret for any family of robust predict-then-optimize policies. Our method constructs valid estimators that trace out the miscoverage--regret Pareto frontier, enabling decision-makers to reliably evaluate and calibrate robustness levels according to their cost--risk preferences. The framework is simple to implement, broadly applicable across classical optimization formulations, and achieves sharper finite-sample performance. This paper offers a principled data-driven methodology for guiding robustness selection and empowers practitioners to balance robustness and conservativeness in high-stakes decision-making.