NeurIPS 2026 Papers

Kullback-Leibler (KL) regularization is widely used in offline decision-making and offers several benefits, motivating recent work on the sample complexity of offline learning with respect to \emph{KL-regularized performance metrics}. Nevertheless, the exact sample complexity of KL-regularized offline learning remains largely from fully characterized. In this paper, we study this question in the setting of multi-armed bandits (MABs). We provide a sharp analysis of KL-PCB~(Zhao et al., 2026), showing that it achieves a sample complexity of $\tilde{O}(\eta SAC^{\pi^\*}/\epsilon)$ under large regularization $\eta = \tilde{O}(\epsilon^{-1})$, and a sample complexity of $\tilde{\Omega}(SAC^{\pi^\*}/\epsilon^2)$ under small regularization $\eta = \tilde{\Omega}(\epsilon^{-1})$, where $\eta$ is the regularization parameter, $S$ is the number of contexts, $A$ is the number of arms, $C^{\pi^\*}$ is the policy coverage coefficient at the optimal policy $\pi^*$, $\epsilon$ is the desired sub-optimality, and $\tilde{O}$ and $\tilde{\Omega}$ hide all poly-logarithmic factors. We further provide a pair of sharper sample complexity lower bounds, which matches the upper bounds over the entire range of regularization strengths. Overall, our results provide a nearly complete characterization of offline multi-armed bandits with KL regularization.

Multi-token prediction (MTP) accelerates autoregressive decoding through blockwise prediction, but remains vulnerable to error accumulation across sequentially generated blocks. Existing work primarily focuses on improving MTP’s acceleration ratio while largely overlooking the compounding errors that accumulate during block-wise generation. In this work, we study MTP from an information-theoretic perspective and identify the strength of inter-block dependencies as a key factor governing its performance. Building on the cumulative information loss, we theoretically quantify the gap of block-sequence representation. Motivated by the analysis, we propose Dual-MTP, a novel MTP training framework that explicitly models inter-block dependencies from two complementary perspectives, thus reducing the block-sequence representation gap across decoding steps. Specifically, Dual-MTP introduces a dual-perspective training objective with random masking, where each block is jointly trained for forward prediction and masked context reconstruction, encouraging robust block-level representations. Experiments across five model backbones and six tasks spanning math reasoning and GLUE understanding show that Dual-MTP consistently outperforms standard MTP on both quality and efficiency, attaining the highest average accuracy on every backbone with gains of +0.3 to +3.0 points and a 1.4× to 1.9× wall-clock speedup over standard autoregressive decoding.

More data is commonly assumed to improve learning performance. We show that this intuition can fail in sequential decision-making. Motivated by multi-agent collaborative learning, we study stochastic bandits with exogenous side information, and ask if free and unbiased reward samples are guaranteed to reduce regret. We introduce a formal notion of non-degradation under side information and demonstrate that the widely used UCB algorithm violates this property: there exist benign side-information designs under which UCB incurs strictly higher regret than when run without side information. We contrast this behavior with Thompson Sampling and Explore-Then-Commit, which benefit from the same information. Constructively, we further propose a meta-algorithm that enforces non-degradation for a broad class of bandit algorithms. Finally, experiments in recommender systems scenarios show that data sharing among different groups of users under UCB can yield diminishing and even negative returns for individual groups.

Multimodal agents that interact with users over days or months must remember not only what was said, but what was shown, heard, and played. Current memory benchmarks are predominantly text-only or cover at most two modalities. Those that do incorporate multimodal content still evaluate with aggregate scores that conflate retrieval and reasoning errors, and provide no mechanism to test whether performance degrades as context scales, leaving our understanding of agent memory fundamentally incomplete. We introduce OmniMemBench, to our knowledge the first long-term memory benchmark that spans image, audio, and video in multi-session dialogue. Its design is guided by three requirements for reliable evaluation. First, an anti-leakage mechanism filters questions answerable from text alone, reducing text-only solvability to a negligible level. Second, two LLM-judged retrieval metrics—Clue Coverage and Entry Relevance—operate on content rather than entry IDs, enabling unified retrieval diagnosis across RAG and memory paradigms. The gap between retrieval coverage and downstream QA scores further localizes failures to the memorization stage. Third, content-isolated distractor injection scales context from 128K to 1M tokens while holding evidence constant, so scalability can be measured without confounding difficulty. The benchmark covers 103 characters and 6,655 QAs across 8 task types and 4 context tiers. Evaluating representative long-context, RAG, and structured-memory methods, we find that no single paradigm dominates: long-context models lead overall, yet RAG surpasses them on targeted fact extraction. Further analysis shows that memory methods retrieve clues at coverage rates comparable to RAG but score substantially lower on QA, revealing that the bottleneck is not what is retrieved but what is lost during memorization. Caption-based processing irreversibly discards perceptual details; raw embeddings degrade retrieval accuracy; and scaling the memorization model yields negligible gains.

Deep multi-view clustering often struggles with inter-view feature redundancy and dimensionality collapse during iterative representation fusion. To address these limitations, we propose Orthogonal Residual Consensus Alignment (ORCA). First, a Semantic Incremental Recurrent Fusion (SIRF) module explicitly separates shared redundancy from complementary residuals via geometric projection. By employing an adaptive halting mechanism, SIRF autonomously maximizes information gain while avoiding structural collapse. Second, a Consensus-Calibrated Hierarchical Contrastive Alignment (CCHA) module is introduced to preserve multi-scale semantics. It adaptively aligns view-level, local, and recurrent representations using the global consensus as a semantic anchor. Consequently, ORCA learns latent representations with robust structural integrity and highly discriminative semantics. Extensive experiments on multiple benchmarks demonstrate that ORCA consistently outperforms state-of-the-art methods, with comprehensive ablations verifying its robustness.

AI agents are increasingly deployed in shared environments where they pursue diverse goals and compete for rewards. This multi-agent competition can lead to behaviors that serve individual gains at collective cost—for instance, marketing agents may post misleading content as a result of competing for engagement on social media. Human societies address such problems through *norms* that constrain acceptable behavior, supported by *enforcement mechanisms* that detect and penalize violations. Motivated by this, we study norm enforcement mechanisms for language model agents. We find that simple enforcement mechanisms are exploited by misaligned agents for competitive advantage, even when they are not explicitly trained or prompted to do so. We thus turn our attention to designing more robust mechanisms, and identify two key ingredients: estimating each agent’s reliability over time, and updating this estimate with escalating penalties for repeated misbehavior. Across three simulated environments and a variety of agent populations, mechanisms built on these principles resist exploitation, while still penalizing norm violations at comparable or lower cost than baselines. Our results position norm enforcement mechanisms as promising levers for shaping agents' behavior, but only when designed to anticipate becoming part of the environment they govern.

It is now common to use 2D diffusion priors for problems where the underlying object is 3D (e.g., medical imaging). We would pick a noise schedule from the EDM literature, anneal a tilted prior, and then use the formulation as a 3D generative model. It works empirically. But we know very little about what it converges to and how fast. We study this question for a natural target: the multi-marginal Schrödinger bridge, the relative-entropy projection of a 3D prior onto the distribution whose rendered slices match the 2D marginals. But computing it is intractable. The annealed 2D-tilted surrogate is what one actually uses in applications. The main question is how close the latter object is to the former. Our main idea is that the discrepancy between these two laws — a comparison of two high-dimensional, fully coupled distributions — can be reduced to the size of a *single* scalar correction field. This field has a nice two-piece form: residual coupling across slices and tempering mismatch from the annealed discrete schedule. Using a Gaussian-smoothed filtration, Wasserstein screening, and conditional concentration, we obtain an explicit discrepancy bound in which the relevant terms separate into latent and posterior-residual contributions. When the smoothing scale is identified with the EDM noise level $\sigma(\tau)$, our bound yields $\mathrm{KL}(\Pi_\tau\|P^\star)=O\left(N\sigma(\tau)^2\right)$ and $\|\Pi_\tau-P^\star\|_{\mathrm{TV}}=O\left(\sqrt{N}\sigma(\tau)\right),$ if the latent scale remains bounded and the surrogate log-discrepancy is noise-aligned. So, the 2D-tilted construction converges to the Schrödinger-bridge lift at a rate governed by user-checkable quantities like the surrogate Lipschitz constants and the posterior concentration constant.

A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates `Poll`, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, `Poll` uses significantly fewer operations than exact computation and other distributed methods; statistically, its query complexity scales with topology and preference heterogeneity rather than with population size; and economically, it converges to welfare-maximizing prices while inducing truthful reports and detecting adversarial deviations.

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for *loss-independent delays*, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for *loss-dependent delays*, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the *delay-as-payoff model*, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. [2025] show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal $t^{-\frac{1}{2}}$ rate after $t$ rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than $t^{-\frac{1}{3}}$ in expectation or $t^{-\frac{1}{4}}$ with high probability. However, in many practical settings (such as preference learning), the players observe not only their loss but also the opponent’s action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that $t^{-\frac{1}{2}}$ last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits (the single-player case) from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

We study the decoupled multi-armed bandit problem, where the player selects one arm to exploit (incurring its loss) and one arm to explore (observing its loss) at each round. We propose two algorithms: D-Exp3-Ada, based on Exp3 with an AdaGrad learning rate, and D-TINF-SPM, based on FTRL with Tsallis entropy and the stability-penalty matching learning rate. Here, $K$ denotes the number of arms, $T$ the time horizon, and $\Delta_i$ the suboptimality gap of arm $i$. D-Exp3-Ada achieves $\mathcal{O}(\sqrt{KT\log K})$ regret in adversarial regimes and $\mathcal{O}(\sum_{i \neq i^{\star}} \frac{\log K}{\Delta_i})$ in stochastic regimes, combining simplicity of algorithm design with strong guarantees. D-TINF-SPM achieves the minimax optimal $\mathcal{O}(\sqrt{KT})$ in adversarial regimes and $\mathcal{O}(\min\{\sqrt{K\sum_{i \neq i^{\star}} \frac{1}{\Delta_{i}^2}}, \sum_{i \neq i^{\star}} \frac{\log K}{\Delta_i}\})$ in stochastic regimes. We also provide a refined analysis of the prior best algorithm. Finally, we derive instance-dependent lower bounds under natural monotonicity and permutation-invariance assumptions on regret upper bounds, proving that our algorithms are optimal up to $\mathcal{O}((\log K)^2)$ within this class.

We study fair multi-armed bandits under the Nash Social Welfare (NSW) objective, which measures performance via the geometric mean of accumulated rewards as a fairness-respecting performance metric. Existing formulations define Nash regret as $NR_T = \mu^\star - (\prod_{t=1}^T \mathbb{E}\mu_{I_t})^{1/T}$, where $\mu_{I_t}$ is the mean reward of the recommended arm $I_t$ and $T$ is the learning horizon. We observe that, since ensemble Nash regret operates on per-round marginal expectations before applying the geometric mean, it does not capture the joint distribution of rewards across rounds — leaving an aspect of the NSW fairness motivation unaddressed at the trajectory level. To address this, we propose \emph{trajectory-wise Nash regret} $\widetilde{NR_T}= \mu^\star - \mathbb{E}[(\prod_{t=1}^T \mu_{I_t})^{1/T}]$, where the geometric mean is computed over complete sample paths before taking expectations. This formulation captures the fairness properties of NSW more faithfully and requires controlling the joint distribution of rewards across rounds, rather than merely per-round marginals. By Jensen's inequality applied to the concave geometric mean, $\widetilde{NR_T} \geq NR_T$, making it a strictly stronger metric. We additionally introduce \emph{high probability Nash regret} $\widehat{NR_T} = \mu^\star - (\prod_t \mu_{I_t})^{1/T}$, obtaining the first high probability regret bounds in the fair bandits literature. We propose a two-phase algorithm, Round Robin Nash Confidence Bound (\texttt{RR-NCB}), combining structured round robin exploration with a Nash confidence bound index policy. We establish that $\widetilde{NR_T} \leq \widetilde{\mathcal{O}}(\sqrt{k\log T/T})$ and $\widehat{NR_T} \leq \widetilde{\mathcal{O}}(\sqrt{k\log(kT/\delta)/T})$ with probability $1-\delta$, matching the optimal $\widetilde{\mathcal{O}}(\sqrt{k/T})$ scaling despite operating under strictly stronger metrics. Optimality follows from a lower bound chain via AM-GM and standard $k$-armed bandit minimax arguments. We validate our theoretical findings through simulations.

Sparse-view novel view synthesis is a central problem in 3D content creation, but diffusion-based approaches remain limited by iterative denoising, making multi-view generation expensive at inference time. We introduce NAMVIS, a diffusion-free framework that reformulates multi-view image synthesis as geometry-conditioned next-scale autoregression. Instead of generating target views through repeated denoising, NAMVIS predicts discrete visual tokens through a small number of coarse-to-fine scale steps, while sampling all tokens within each scale and across target views in parallel. To anchor this generation process to explicit camera geometry, we propose Multi-scale Projective Pose Encoding, which injects source and target camera transformations into both target-view self-attention and source-to-target cross-attention at every resolution. NAMVIS further combines global conditioning with dense geometry-aware cross-attention, enabling the model to preserve source-view appearance while maintaining target-view consistency. Across Objaverse, GSO, and OmniObject3D, NAMVIS outperforms diffusion-based baselines in PSNR, SSIM, and LPIPS, while running over 3× faster than the evaluated diffusion baselines under the same evaluation setting. These results suggest that geometry-conditioned next-scale autoregression is a promising and efficient alternative to diffusion for sparse-view multi-view synthesis.

Reconstructing accurate camera poses and floor-plan layouts from sparse, unposed, wide-baseline RGB panoramas remains a challenging open problem. Direct multi-room floor-plan prediction is especially difficult in this setting: pose, geometry, semantics, and global layout structure are tightly coupled, yet a complete floor-plan is hard to learn as a single global output. Our key insight is to keep the model's predictions strictly local. Multi-view Ordered Wall Instance Segmentation (MOIS) is designed around this concept. Each panorama column predicts only the wall it observes plus the next two adjacent walls in clockwise order. The global wall partition, room layouts, and shared coordinates emerge from deterministic aggregation of overlapping local predictions. Building on MOIS, we propose Multi-view floor-plan Feed-Forward Network (MvFFN), which jointly predicts coarse camera poses, dense global geometry, and per-wall semantic outputs. A downstream Layout Chaining (LC) post processing pipeline then assembles these predictions into multi-room floor-plans with shared global coordinates, consistent wall identities, and connected room structure. The dense MOIS predictions recover cross-view wall identity and local within-room connectivity more accurately than composed modular baselines, and the assembled layouts substantially outperform prior methods on wall and junction level accuracy. We also introduce the ZInD-CrossView dataset, which augments ZInD with globally unique wall instances and cross-view segmentation labels for this task.

Consistency models achieve fast image synthesis by chaining a small number of neural evaluations along a diffusion trajectory, yet the distribution error of $N$-step sampling for $N \geq 3$ has lacked a rigorous characterisation. We establish a tight Wasserstein-$p$ error bound for arbitrary $N$: the total error equals a Lipschitz-weighted sum of per-step local consistency errors, $\sum_{k=1}^{N} L_x^{N-k} \delta_k$, making the propagation mechanism explicit. From this bound we derive a closed-form optimal step count $N^{\star}$ whose structure bifurcates on whether the spatial Lipschitz constant $L_x$ exceeds one: for $L_x > 1$, exponential error growth yields $N^{\star} \approx (\ln L_x)^{-1} \log(\beta\gamma(L_x-1)/(c \ln L_x))$; for $L_x < 1$, geometric-series saturation gives $N^{\star} \approx (\beta\gamma(1-L_x)/(c \, |\ln L_x|))^{1/(\gamma+1)}$. The two-regime structure accounts for ECT's best FID of $2.73$ at $N=2$: with $L_x \approx 0.85 < 1$ (Case 2), the formula gives $N^{\star} \approx 1.7$. Experiments on CIFAR-10 reproduce the predicted U-shaped FID curve with $N^{\star} = 8$ on a capacity-constrained model in which error accumulation is easier to see.

Wearables are widely used for mobile health monitoring, and photoplethysmography (PPG) is a key sensing modality for heart rate and related physiological measurements. However, public in-the-wild PPG datasets remain largely wrist-centric or limited to short, controlled studies, constraining research on emerging wearable form factors. We present Multi-site PPG, an in-the-wild physiological dataset collected from four custom-developed unobtrusive wearables: a smart earring, ring, watch, and necklace. Each device records green and infrared reflective PPG, 3-axis acceleration, and temperature with timestamps for cross-device alignment, while a Polar H10 chest strap provides reference electrocardiogram (ECG). Participants wore the devices for one to multiple days during daytime activities while continuing their normal routines. The dataset contains over 350 hours of raw data and 230–290 hours of preprocessed, modeling-ready 8-second windows data per wearable. We benchmark heuristic, supervised, and self-supervised heart-rate estimation methods, showing substantial body-site differences: the best methods achieve mean absolute errors (MAEs) of 2.30 bpm on the earring, 5.13 bpm on the ring, 8.37 bpm on the watch, and 8.68 bpm on the necklace. We further analyze motion effects and evaluate multi-site and PPG–accelerometer fusion, demonstrating the dataset’s value for robust physiological sensing across emerging wearable form factors.

Recent advances in multi-agent systems have shown great potential for solving complex tasks. However, when multiple agents edit a shared codebase concurrently, their changes can silently conflict and inconsistent views lead to integration failures. Existing multi-agent systems address this through workspace isolation (e.g., one git worktree per agent), but this defers conflict resolution to a post-hoc merge step where recovery is expensive. In this paper, we propose STORM, i.e., STate-ORiented Management for multi-agent collaboration. Specifically, STORM manages agent states by mediating their interactions with the shared workspace, ensuring that each agent operates on a consistent view of the codebase and that conflicting edits are detected and resolved at write time.We evaluate STORM on Commit0 and PaperBench across multiple LLMs. STORM outperforms the git-worktree-based multi-agent baseline by +18.7 on Commit0-Lite and +1.4 on PaperBench, while achieving comparable or better cost efficiency. Combined with single-agent runs, STORM reaches highest scores of 87.6 and 78.2 on the two benchmarks respectively, suggesting that explicit state management is a more effective foundation for multi-agent collaboration than workspace isolation. STORM can also be plugged into any multi-agent system. Our code is available at \url{https://anonymous.4open.science/r/STORM-Mutli-Agent}.

Conformal prediction constructs prediction sets with finite-sample coverage guarantees, but its calibration stage is structurally constrained to a scalar score function and a single threshold variable — forcing shapes of prediction sets to be fixed before calibration, typically through data splitting. We introduce multi-variable conformal prediction (MCP), a framework that extends conformal prediction to vector-valued score functions with multiple simultaneous calibration variables. Building on scenario theory as a principled framework for certifying data-driven decisions, MCP unifies prediction set design and calibration into a single optimization problem, eliminating data splitting without sacrificing coverage guarantees. We propose two computationally efficient variants: RemMCP, grounded in constrained optimization with constraint removal, which admits a clean generalization of split conformal prediction; and RelMCP, based on iterative optimization with constraint relaxation, which supports non-convex score functions at the cost of possibly greater conservatism. Through numerical experiments on ellipsoidal and multi-modal prediction sets, we demonstrate that RemMCP and RelMCP consistently meet the target coverage with prediction set sizes smaller than or comparable to those of baselines with data split, while considerably reducing variance across calibration runs — a direct consequence of using all available data for shape optimization and calibration simultaneously.

Reinforcement learning with verifiable rewards (RLVR) plays a pivotal role in improving the reasoning ability of large language models. However, widely used PPO surrogate objectives are fundamentally *local*, as they rely on a local approximation of the exact policy gradient objective. While this approximation improves stability by reducing the variance induced by importance sampling, it also introduces structural bias into the surrogate objective, which must be controlled through trust region mechanisms. In this work, we introduce the $N$-step forward trace, which augments the PPO surrogate objective using the cumulative likelihood ratio of the next $N-1$ tokens. Building on this idea, we propose $N$-Step Forward-Trace Policy Optimization (NFPO), a practical RLVR algorithm that integrates the $N$-step forward trace into the masked policy gradient framework. NFPO provides a continuous bridge between the PPO surrogate objective and the exact policy gradient objective, offering a principled mechanism for controlling the bias–variance trade-off. Our theoretical analysis shows that, with an appropriate choice of $N$, the proposed objective yields a tighter policy-improvement bound than the standard PPO surrogate. Experiments on comprehensive reasoning benchmarks demonstrate that NFPO consistently improves performance, supporting our theoretical findings.