NeurIPS 2026 Papers

The public belief state (PBS), which is the posterior over game histories conditioned on public information, is a fundamental abstraction for designing game-theoretically sound search algorithms for imperfect-information games. Existing sound PBS search techniques for adversarial games fall into two categories: gadget-game-based algorithms (including Libratus, DeepStack, Pluribus, Supremus, and Student of Games) and ReBeL-based algorithms. Both these categories possess disadvantages, including a reliance on discontinuous functions, an inability to re-solve subgames, and an implicit representation of policies. In this work, we propose Gravel, a new approach for PBS search---different from these previous two categories---that achieves game-theoretic soundness via regularization. Unlike the aforementioned approaches, Gravel relies on smooth functions, can initiate search at any point in the game, and outputs explicit policies directly. We empirically demonstrate the advantages of Gravel for no-limit Texas hold'em, where we show that it outperforms ReBeL both in head-to-head competitions against Slumbot and in endgame solving. We include our codebase in the submission, making Gravel the first open-source high-performance no-limit Texas hold'em AI.

We propose a primal-dual policy optimization method for reinforcement learning in semi-infinitely constrained Markov decision processes (SICMDP), which extends standard constrained Markov decision processes by allowing a continuum of constraints. We call our proposed method \textbf{S}emi-\textbf{I}nfinitely \textbf{P}rimal-\textbf{D}ual \textbf{P}olicy \textbf{O}ptimization (SI-PDPO). By introducing an infinite-dimensional Lagrange multiplier, we derive the saddle-point formulation of the original SICMDP problem and prove strong duality under mild conditions. We then introduce a regularization term for the dual variable, and solve the resulting regularized saddle-point problem using first-order methods with a policy optimization subroutine (for example, NPG or PPO). Unlike existing primal-type policy optimization algorithms for semi-infinitely constrained reinforcement learning, our method does not require solving an inner-loop optimization problem, thereby mitigating computational intractability and reducing the over-conservative bias. We perform a series of numerical experiments, including a real-world power control task in wireless communications, to evaluate the performance of SI-PDPO. Empirical results show that SI-PDPO consistently outperforms existing primal-type algorithms.

We study the complexity of smoothed agnostic learning of halfspaces on $\{\pm 1\}^n$ under uniform marginals in the model of \citet{KM25} where each input coordinate is independently flipped with probability $\sigma \in (0, {1}/{2})$. We show that $L^1$ polynomial regression achieves runtime and sample complexity $\tilde{O}(n^{O(\log(1/\varepsilon)/\sigma)})$, and prove a nearly matching Statistical Query complexity lower bound of $n^{\Omega(\log(1+\sigma/\varepsilon^2)/\sigma)}$. This complements the recent work of \citet{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.

A common approach for contextual optimization first trains a model to predict the unknown state from the context, and then takes the action that is optimal for the predicted state. We show that this follow-the-prediction policy can be brittle: for several standard problems, even a minimum-variance predictor with arbitrarily small RMSE can incur constant excess loss. We propose a simple policy that robustifies any black-box predictor by optimizing against the worst case in an $\varepsilon$-neighborhood of the prediction. We identify a problem-specific quantity, the \emph{robust optimization gap}, that captures the price of this hedging, and prove a general bound on the loss. We instantiate the framework for contextual posted pricing, ski rental, and house flipping, deriving closed-form robust policies and $O(\eta^{2/3})$ loss bounds in all three settings, where $\eta$ is the RMSE of the predictor. For posted pricing, this improves upon a result of Medina and Vassilvitskii (2017), and with a substantially simpler argument.

Multivariate conformal prediction requires nonconformity scores that compress residual vectors into scalars while preserving certain implicit geometric structure of the residual distribution. We introduce a Multivariate Kernel Score (MKS) that produces prediction regions that explicitly adapt to this geometry. We show that the proposed score resembles the Gaussian process posterior variance, unifying Bayesian uncertainty quantification with the coverage guarantees of frequentist-type. Moreover, the MKS can be decomposed into an anisotropic Maximum Mean Discrepancy (MMD) that interpolates between kernel density estimation and covariance-weighted distance. We prove finite-sample coverage guarantees and establish convergence rates that depend on the effective rank of the kernel-based covariance operator rather than the ambient dimension, enabling dimension-free adaptation. On regression tasks, the MKS reduces the volume of prediction regions significantly, compared to ellipsoidal baselines while maintaining nominal coverage, with larger gains at higher dimensions and tighter coverage levels.

Modern probabilistic machine learning models increasingly produce multivariate outputs with complex dependence structure, from multi-step time-series forecasts to sample path predictions. Understanding which input features drive the predictive uncertainty is important for risk-aware decisions, model diagnostics, and deciding whether the uncertainty should be mitigated or hedged against. This attribution problem requires a choice of how dependencies between output components are treated. Existing approaches reduce the output to a scalar through aggregation or projection before attribution, thereby obscuring whether features affect marginal uncertainty, dependence structure, or both, while component-wise analyses can miss dependence effects entirely. We close this gap by introducing a hierarchy of three entropy-based Shapley games that make this output-side choice explicit for any ordered multivariate outcome, ranging from per-component marginal entropy to fully joint entropy. The hierarchy isolates a cross-component attribution term that captures how each feature shifts the dependence between output components, a quantity invisible to component-wise methods. We establish a chain-rule decomposition of the joint attribution and characterize the cross-component term through conditional total correlation, providing both closed-form and sample-based estimators. Finally, we demonstrate how the framework captures differences in learned joint structure across probabilistic models from distributional regression to a zero-shot time series foundation model.

Current world models operate at a single level of abstraction, with most prioritizing perceptual fidelity while lacking the spatial reasoning and semantic understanding required for real-world downstream tasks. We present a hierarchical driving world model that factorizes future prediction across two levels operating at distinct temporal and abstraction scales: a high-level predictor that forecasts coarse scene structure over extended temporal horizons, and a low-level generator that produces detailed predictions conditioned on the high-level output. This decomposition yields high perceptual fidelity while also capturing strong spatial and semantic representations. We further show that pretraining with a diffusion forcing objective yields substantially richer internal representations than the standard teacher forcing objective, while teacher forcing — predicting only the next frame from clean context — produces more stable autoregressive rollouts. We therefore introduce a generic two-stage training paradigm that pretrains the model with diffusion forcing and fine-tunes with teacher forcing, combining the representational benefits of the former with the rollout stability of the latter. Our approach achieves state-of-the-art results across the standard suite of driving world model evaluations on established benchmarks, including long-horizon generation fidelity, steering responsiveness evaluated on counterfactual scenarios, and internal representation quality.

We propose the Tikhonov layer, a graph neural network layer that is interpretable by design: once trained, its learned parameters directly reveal which node features and which aspects of the graph topology were leveraged for prediction. In practice, the layer's propagation matrix takes the closed-form $R = (p(L)+Q)^{-1}Q$, where $L$ is the normalized graph Laplacian, $Q = \mathrm{diag}(q_1,\ldots,q_n)$ a learnable diagonal matrix of positive node-importance scores, and $p(\cdot)$ a learnable polynomial. For any input feature $x$, the layer output $Rx$ is the exact minimizer of a generalized graph Tikhonov problem that trades off node-level data fidelity against a topology-driven regularization penalty. The learned pair $(\{q_i\},p)$ constitutes a built-in explanation: large $q_i$ indicates that node $i$'s own features drive the prediction, while small $q_i$ signals reliance on the local graph topology; the shape of $p$ reveals whether homophily, heterophily, or a band-pass response is exploited. Expressivity is preserved by routing complexity through a dedicated, arbitrarily deep $Q$-network that produces the importance scores, while the Tikhonov layer itself remains transparent. We prove that distinct explanations necessarily yield distinct propagation operators, preventing degenerate explanations by design. Additionally, the Tikhonov layer provides, in a single layer, a global receptive field under mild support-connectivity conditions, mitigating both oversmoothing and oversquashing. Experiments on standard graph classification benchmarks confirm that the model matches (and sometimes outperforms) opaque baselines while producing interpretable and faithful explanations.

The rapid scale-up of AI infrastructure has made datacenter reliability a cornerstone of the cloud business economy. Hardware failures in hyper-scale AI clusters do not merely disrupt individual machines; they stall multi-million dollar training workloads, and so the downtime of individual machines can cause outsized economic losses. Minimizing machine downtime, therefore, is more important than ever. To address this, we present DrWatson, an AI-driven hardware diagnosis system that pioneers a foundation-model approach to automated datacenter maintenance. Deployed at production scale within a major AI hyperscaler, DrWatson yields substantial efficiency gains across diverse compute architectures. Real-world evaluations demonstrate that it reduces production downtime by 18.3% on GPU platforms and 16.1% on custom AI accelerators. Furthermore, it significantly accelerates hardware deployment, cutting quality assurance (QA) time by 28.3% for GPUs and 25.1% for custom accelerators. These results establish DrWatson as a field-tested solution for maximizing the reliability and cost efficiency of next generation AI fleets.

The MOEA/D is one of the most successful multi-objective evolutionary algorithms. It operates by decomposing the optimization problem into single-objective subproblems, which are then solved in a co-evolutionary manner. The performance of the MOEA/D depends critically on this decomposition. In this work, we propose a novel way to adjust this decomposition on the fly, for the case of discrete bi-objective optimization. Different from all previous works in this direction, we support our new algorithm with a proven performance guarantee. This is the first work that rigorously proves the runtime of a dynamic multi-objective evolutionary algorithm. For monotonic distortions of the simple LOTZ benchmark, it is known that classic decompositions leave large holes in the Pareto front, making it very hard for the MOEA/D to cover the entire Pareto front. In contrast, we prove that our self-adjusting MOEA/D solves all these LOTZ problems in an expected number of $O(n^4)$ function evaluations. This relatively low runtime as well as the details of our mathematical proof show that the dynamic decomposition strategy indeed evolves a decomposition adjusted to each of these problem instances.

We propose a deep learning framework for scalar-on-function regression with possibly multiple functional predictors observed on irregular grids. The method represents each functional covariate by finitely many basis coefficients computed from the observed trajectories and fits a deep neural network using these coefficients as features. We establish a general nonasymptotic excess risk bound for the neural network estimator that decomposes the error into statistical, truncation, discretization, and network approximation terms. We then specialize the theory to two important settings. (i) For continuous functional models, an equal-width neural network estimator achieves a nearly minimax optimal rate up to a log-logarithm factor. (ii) For functional multiple-index models, we design a bottleneck-equal-width neural network estimator that exploits the low-dimensional index-link structure and attains a nearly minimax optimal rate up to a logarithm factor. The results provide theoretical support for neural network-based scalar-on-function regression and highlight the importance of architecture design.

Submodular functions have applications in several domains, \eg, text, vision, speech, \etc. Recent works have proposed neural architectures that are submodular functions by design. However, they do not explicitly capture pairwise interactions between set elements. In this work, we begin with the characterization of pairwise submodular functions, which capture the pairwise interaction across the elements of the input set. We observe that pairwise interactions yield monotone supermodular functions, since the number of terms grows quadratically in terms of the input set size, which poses a significant challenge in converting it into a submodular function. To address it, we provide a novel result that a derivative rate-controlled concave function can transform a monotone supermodular function into a monotone submodular function. We also extend our results to monotone $\alpha$-submodular functions. Leveraging this characterization, we design multi-layer neural cross-interaction architectures for monotone submodular functions and analyze their expressivity. Finally, we perform several experiments which show that our model performs better than existing baselines.

Posterior collapse is a common failure mode in variational autoencoders, but existing theory has mostly focused on Gaussian latent variables. Dirichlet VAEs are comparatively less understood, despite their use in settings where latent variables represent proportions, abundances, memberships, or convex mixture weights. We derive a closed-form local stability threshold $\beta_c$ for collapse in symmetric Dirichlet $\beta$-VAEs with linear Gaussian decoders. This threshold shows that collapse in those models depends not only on the data spectrum, but also on the simplex dimension and prior concentration through a trigamma curvature factor induced by the Dirichlet KL. Although $\beta_c$ is derived from a local analysis, we find that it accurately tracks the empirical onset of collapse beyond the local regime. We show its practical relevance in two real-world linear-mixture settings: hyperspectral unmixing and convex archetypal analysis. Across experiments, $\beta/\beta_c$ consistently organizes collapse-related behavior, providing an interpretable coordinate and a practical way to narrow the search over the $\beta$ hyperparameter before training. Taken together, these empirical findings suggest that $\beta_c$ can serve, beyond its local derivation, as a practical reference point for anticipating collapse and guiding $\beta$ selection in Dirichlet $\beta$-VAEs.

This paper studies the problem of jointly learning a reward function, a cost function, and a policy from an expert's preferences. We formulate the problem as a constrained bi-level optimization problem, where the upper level infers the reward and cost functions from preferences, while the lower level optimizes a policy to best align with those preferences. To solve this problem, we propose a double-loop algorithm, Constrained Bi-level Optimization for Preference-Based Reinforcement Learning (CB-PbRL), which solves the lower-level optimization problem in the inner loop and the upper-level optimization problem in the outer loop. We establish a theoretical guarantee that CB-PbRL converges at a rate of $\mathcal{O}(1/\sqrt{K})$, and we demonstrate its effectiveness across multiple simulation environments.

Activation functions play a central role in neural networks by shaping internal representations. Recently, learning binary activation representations has attracted significant attention due to their advantages in computational and memory efficiency, as well as interpretability. However, training neural networks with Heaviside activations remains challenging, as their non-differentiability obstructs standard gradient-based optimization. In this paper, we propose Heavy-Tailed Activation Function (HTAF), a smooth approximation to the Heaviside function that enables stable training with gradient-based optimization. We construct HTAF as a sigmoid–hyperbolic tangent composite function and theoretically show that it maintains a large gradient mass around zero inputs while exhibiting slower gradient decay in the tail regions. We show that Spiking Neural Networks, Binary Neural Networks and Deep Heaviside neural Networks can be trained stably using HTAF with gradient-based optimization. Finally, we introduce Implicit Concept Bottleneck Models (ICBM), an interpretable image model that leverages HTAF to induce discrete feature representations. Extensive experiments across various architectures and image datasets demonstrate that ICBM enables stable discretization while achieving prediction performance comparable to or better than standard models.

We investigate data filtering for large model pretraining via new scaling studies that target the high compute, data-scarce regime. In spite of an apparently common belief that filtering data to include only high-quality information is essential, our experiments suggest that with enough compute, the best data filter is no data filter. We find that sufficiently trained large parameter models not only tolerate low-quality and distractor data, but in fact, including nominally 'poor' data improves model performance.

Optimal transport (OT) provides a principled framework for mapping between probability distributions. Despite extensive progress, applying OT to large-scale data remains computationally demanding, and the resulting pointwise transport plans are often difficult to interpret. We introduce Optimal Mixture Transport (OMT), a scalable framework that shifts the transport paradigm from individual samples to mixtures of subpopulations, reformulating the transport problem as a strictly biconvex optimization with a unique global minimizer. We further establish theoretical guarantees on the stability of the OMT map, showing that bounded perturbations of the underlying distributions lead to bounded changes in the transport plan. By formulating subpopulations as exponential-family distributions, OMT decouples computational complexity from the sample size, scaling solely with the number of mixture components. We demonstrate the effectiveness and practicality of OMT on a wide range of synthetic benchmarks and real-world datasets, including image data and large-scale single-cell RNA sequencing measurements.

Long-form omni-modal video understanding requires models to integrate vision, speech, and ambient audio with coherent long-context reasoning. Existing video benchmarks often trade off temporal scale, modality coverage, open-ended interaction, and interpretable scoring. To address this gap, we introduce $\textbf{LongShOTBench}$, a long video evaluation benchmark designed around three coupled goals: holistic omni-modal integration, intent-driven open-ended interaction, and rubric-level diagnosis. It constructs single- and multi-turn questions from practical viewing scenarios, involving systematical tasks for probing visual, speech, ambient-audio, temporal, and cross-modal reasoning. Each item includes a reference answer and a weighted criterion-level rubric, enabling evaluation to identify which perceptual facts, temporal links, modality-grounding requirements, and reasoning steps are satisfied or missed. All samples are manually verified and corrected to improve grounding, clarity, and rubric reliability. We also introduce $\textbf{LongShOTAgent}$, a training-free omni-modal evidence-seeking agent that couples full-video preprocessing with targeted retrieval, query-adaptive segment refinement, and explicit claim verification over visual, speech, and non-speech audio evidence. Its iterative search-refine-verify loop exposes intermediate evidence and lets modality-specific specialists re-analyze relevant moments before answering. We perform comprehensive evaluation of 105 video-capable models spanning open-source omni-modal models, vision-language systems, audio LLMs, agentic pipelines and closed-source APIs. Across this broad evaluation, current MLLMs remain far from saturating LongShOTBench, while our LongShOTAgent emerges as the strongest training-free system, reaching 66.64\% overall. By releasing the benchmark, leaderboard, and agentic method, our work provides the community with a shared, interpretable testbed for evaluating and advancing long-form omni-modal video reasoning.

Vehicle trajectory generation is critical for autonomous driving simulation. However, current generative models face two coupled limitations: (i) imbalanced trajectory distributions bias them toward frequent motions, such as straight driving or stationary states, while weakening their ability to synthesize rare but safety critical motions, such as turning. (ii) Euclidean intermediate spaces provide limited geometric inductive bias for modeling vehicle pose evolution. Together, these limitations lead to mode biased generation and physically less coherent trajectories. To address this issue, we propose SEA, an \underline{\textbf{SE}}(2)-\underline{\textbf{A}}ware vehicle trajectory generation method that realizes the conditional transport path through planar rigid body poses. At the \textbf{data distribution} level, SEA learns vehicle trajectory distributions from traffic data to capture individual motion characteristics. At the \textbf{physical-space} level, motivated by the geometry dependence of {\bf optimal transport} interpolation, SEA realizes intermediate transport states through an $SE(2)$-consistent construction, thereby preserving geometric interpretability and physical coherence during generation. Extensive experiments on large scale real world datasets show that our method outperforms state of the art approaches by generating more realistic, diverse and dynamically consistent trajectories.