UAI 2026 Papers

Causal discovery seeks to recover causal structure from data but the underlying graph is typically identifiable only up to its Markov equivalence class. Yet real-world systems often exhibit redundancy, where groups of variables share similar causal roles. We introduce a Bayesian causal discovery framework that leverages variable-level metadata to infer latent types and constrain causal interactions across variables. We model causal graphs as type-consistent DAGs and propose t-DiBS, a fully differentiable method that jointly learns variable types, graph structure, and metadata representations. Our approach enables principled uncertainty quantification and integrates expressive neural models for metadata. We provide theoretical results showing that, under structured assumptions, metadata combined with typing can improve identifiability beyond classical limits. Empirically, we demonstrate improved performance over standard causal discovery methods on synthetic and pseudo-real datasets, with detailed analysis demonstrating the benefit of joint type and structure learning. These results establish metadata-driven typing as a principled approach to identifiable causal discovery.

Open-world conditional modeling (OCM), requires a single model to answer arbitrary conditional queries across heterogeneous datasets, where observed variables and targets vary and arise from a vast open-ended task universe. Because any finite collection of real-world datasets covers only a small fraction of this space, we propose Task Expansion and Cross Refinement (TEXR), a semi-supervised framework that enlarges effective task coverage through structured synthesis and refinement of semantic data contexts. TEXR first generates diverse uninstantiated dataset schemas and weakly instantiates them via structured probabilistic generators guided by large language models. It then performs cross-model refinement by training on disjoint data partitions and revising synthetic values across splits to reduce confirmation bias and improve pseudo-value quality. The refined synthetic datasets are aggregated with real data to train a unified conditional model. Across heterogeneous tabular benchmarks, TEXR consistently improves zero-, few-, and many-shot performance for multiple OCM backbones, demonstrating that structured task expansion and cross refinement enhance open-world conditional modeling.

Symbolic regression is the problem of finding an algebraic expression describing a stochastic dependence of a target variable on a set of inputs. Unlike forms of regression that fit parameters assuming a fixed model structure, symbolic regression is a search problem over the space of expressions, represented, for example, as abstract syntax trees using a library of operators. Symbolic regression is typically used in settings with limited, noisy data in the natural sciences. However, searching for a single best-fitting expression fails to capture the epistemic uncertainty about the expression, which motivates a Bayesian perspective that enables uncertainty quantification and specification of natural priors to constrain the search space. In this work, we propose ERRLESS (Entropy-Regularized Reinforcement Learning for Expression Structure Sampling), a scalable approach for sampling from the posterior distribution over expressions given data using maximum-entropy reinforcement learning. ERRLESS learns a neural policy that constructs expressions sequentially by building up their abstract syntax trees. At convergence, the policy samples expressions from the posterior. At test time, expressions can be sampled by rollouts of this policy. We demonstrate that ERRLESS achieves competitive results on the Feynman benchmark while producing short and interpretable expressions. Additionally, we demonstrate that the mean of the posterior predictive approximated by ERRLESS achieves a high coefficient of determination (R^2) compared to an SMC baseline, highlighting the benefits of the Bayesian perspective in symbolic regression.

Bounding causal effects analytically, rather than numerically, is appealing for its interpretability and conceptual clarity. Existing sharp methods rely on optimization-based approaches such as the Balke–{Pearl} framework, whose computational complexity grows rapidly. An alternative line of work derives bounds heuristically using probability laws and generic inequalities, and some recent papers have claimed or conjectured that this approach can yield sharp analytical bounds with substantially lower complexity. In this paper, we show that this perceived advantage is illusory. In particular, in a discrete instrumental variable setting, we show that any sharp analytical bound for the average treatment effect must be expressible as a maximum (minimum) over a collection of linear terms whose cardinality grows exponentially in the number of values taken by the outcome. In parallel, we show that the number of instrumental variable inequalities itself also grows exponentially. Consequently, bounds and inequalities expressed using only polynomially many such terms cannot be sharp. As a constructive complement, the paper is accompanied by codes implemented in python and R to derive sharp analytical bounds and sharp inequalities with optimal computational complexity, matching the lower bounds proven in this paper. These codes are available \href{https://github.com/ArefeBoushehrian/Analytical-Causal-Bounds-in-Instrumental-Variable-Models}{online}.

Machine learning classifiers deployed in critical domains require comprehensible explanations. Abductive explanations identify minimal feature sets guaranteeing a decision but suffer from two limitations: exceeding human cognitive limits and ignoring user preferences (actionability, fairness, cost). Probabilistic explanations reduce size via controlled error, while preferred explanations integrate preferences; however, these approaches remain disjoint. We introduce the first framework unifying these paradigms: preferred probabilistic explanations balancing cognitive constraints, probabilistic accuracy, and user preferences. We formulate the problem via weighted scalarization **WPPE** and Pareto optimization PPPE, prove **NP**-hardness for decision trees, and exploit supermodularity to establish approximation guarantees. We propose three complementary algorithms: weighted greedy descent **WGD** with ratio (e^p_w-1)/p_w, Pareto frontier enumeration **PFE** for interactive exploration of non-dominated trade-offs, and lexicographic stratified algorithm **LSA** for strict ordinal preferences. Our framework enables rigorous navigation of the Pareto-optimal trade-off space between cognitive limits and user preferences.

Proximal Policy Optimization (PPO) has been applied to a wide range of applications, from robotics to large language models (LLMs). Yet, despite its success, it still suffers from unstable updates, performance collapse, and extreme sensitivity to hyperparameters. Many alternatives have been proposed to alleviate these issues, often demonstrating empirically stronger performance on standard reinforcement learning (RL) benchmarks. In this work, we observe that PPO’s training instability fundamentally stems from the brittle inter-coupling between its surrogate optimization hyperparameters which jointly dictate the effective size of policy updates. This complex coupling makes tuning quite difficult and, in practice, often leaves PPO under-performing. To mitigate this, we introduce a criterion on trajectories generated by behavior and target policies which can be used as an early stopping rule. This formulation effectively decouples the optimization dynamics, allowing the algorithm to adaptively scale its updates using a single threshold parameter. We additionally find a scaling law between this threshold parameter and the number of trajectory batches collected, further reducing the tuning burden. Using this simple criterion, we evaluate PPO on continuous control tasks from the DM Control Suite, outperforming prior policy gradient methods and revealing that many reported improvements were largely artifacts of under-performing PPO baselines.

Motivated by their connection to the limit behaviour of imprecise Markov chains, we study the asymptotic behaviour of upper transition operators. Our focus is on their convergence: the condition that for every real function, the sequence generated by repeated application of the operator admits a well-defined limit. This notion is strictly weaker than classical ergodicity, which enforces convergence to a constant, and therefore requires a different analytic treatment. We develop a full characterisation of convergence in terms of graph-theoretic relations induced by the operator: accessibility and lower reachability. The resulting criterion is both necessary and sufficient, and applies to arbitrary upper transition operators without structural restrictions, thus strengthening earlier work that provided only sufficient conditions for the unrestricted case.

The improving multi-armed bandits problem is a formal model for allocating effort under uncertainty, motivated by scenarios such as investing research effort into new technologies, performing clinical trials, and hyperparameter selection from learning curves. Each pull of an arm provides reward that increases monotonically with diminishing returns. A growing line of work has designed algorithms for improving bandits, albeit with somewhat pessimistic worst-case guarantees. Indeed, strong lower bounds of Ω(k) and Ω(√(k)) multiplicative approximation factors are known for both deterministic and randomized algorithms (respectively) relative to the optimal arm, where k is the number of bandit arms. In this work, we propose two new parameterized families of bandit algorithms and bound the sample complexity of learning the near-optimal algorithm from each family using offline data. We also perform empirical evaluations on standard hyperparameter tuning benchmarks. The first family we define includes the optimal randomized algorithm from prior work. We show that an appropriately chosen algorithm from this family can achieve stronger guarantees, with optimal dependence on k, when the arm reward curves satisfy additional properties related to the strength of concavity. Our second family contains algorithms that both guarantee best-arm identification on well-behaved instances and revert to worst-case guarantees on poorly-behaved instances.

A fundamental challenge in causal inference with observational data is correct specification of a causal model. When there is model uncertainty, analysts may seek to use estimates from multiple candidate models that rely on distinct, and possibly partially overlapping, sets of identifying assumptions to infer the causal effect, a process known as triangulation. Principled methods for triangulation, however, remain underdeveloped. Here, we develop a framework for causal effect triangulation that combines model testability methods from causal discovery with statistical inference methods from semiparametric theory, while avoiding explicit model selection and post-selection inference problems. We propose a triangulation functional that combines identified functionals from each model with data-driven measures of model validity. We provide a bound on the distance of the functional from the true causal effect along with conditions under which this distance can be taken to zero. Finally, we derive valid statistical inference for this functional. Our framework formalizes robustness under causal pluralism without requiring agreement across models or commitment to a single specification. We demonstrate its performance through simulations and an empirical application.

We consider hypothesis testing of binary causal queries using observational data. Since the mapping of causal models to the observational distribution that they induce is not one-to-one, in general, causal queries are often only partially identifiable. When binary statistical tests are used for testing partially-identifiable causal queries, their results do not translate in a straightforward manner to the causal hypothesis testing problem. We propose using ternary (three-outcome) statistical tests to test partially-identifiable causal queries. We establish testability requirements that ternary tests must satisfy in terms of uniform consistency and present equivalent topological conditions on the hypotheses. To leverage the existing toolbox of binary tests, we prove that obtaining ternary tests by combining binary tests is complete. Finally, we demonstrate how topological conditions serve as a guide to construct ternary tests for two concrete causal hypothesis testing problems, namely testing the instrumental variable (IV) inequalities and comparing treatment efficacy.

The Schrödinger bridge problem (SBP) provides a principled interpolation between two distributions by selecting, among all path measures matching given endpoint marginals, the one closest in relative entropy to a reference dynamics. In modern applications the marginals are observed only through samples, and standard computational pipelines solve a discretized SBP via Sinkhorn iterations and then heuristically extend the resulting dual potentials off-sample, entangling statistical, optimization, and smoothing errors. We study a learning-theoretic alternative based on a fixed-point characterization of a single transformed Schrödinger potential g^⋆, and we focus on quantitative approximation of g^⋆ by a sample-based estimator g that is continuous by construction. To address the intrinsic scaling ambiguity of Schrödinger potentials, we introduce a normalized, scale-invariant operator and analyze its local geometry around g^⋆. Our main theoretical contribution is a stability result linking the error of the fixed-point residual to a distance to the solution g^⋆ via analysis of spectral-gap property for the Fréchet derivative of the operator in a norm · being the sum of a localized Hilbert tangent seminorm and an L^2 distance. Combining this stability bound with the excess risk bounds and approximation error yields explicit non-asymptotic rates for g-g^⋆. We illustrate performance of the suggested approach with numerical experiments.

Generalization bounds for deep learning models are typically vacuous, not computable or restricted to specific model classes. In this paper, we tackle these issues by providing new disagreement-based certificates for the gap between the true risk of any two predictors. We then bound the true risk of the predictor of interest via a surrogate model that enjoys tight generalization guarantees, and by evaluating our disagreement bound on an unlabeled dataset. We empirically demonstrate the tightness of the obtained certificates and showcase the versatility of the approach by training surrogate models leveraging three different frameworks: sample compression, model compression and PAC-Bayes theory. Importantly, such guarantees are achieved without modifying the target model, nor adapting the training procedure to the generalization framework.

High-dimensional stochastic differential equations encode complex interaction structures within their drift component. We propose a novel approach to estimate this drift from independent high-frequency trajectory data observed over a short time horizon. Each trajectory is modelled as the solution of a Brownian-driven stochastic differential equation, while the number of time points within each path tends to infinity. We further assume that the drift function governing the dynamics can be expressed as a linear combination of a growing number of Lipschitz basis functions. To promote accurate recovery of the underlying dynamics under sparsity constraints, we propose a Lasso-regularised likelihood criterion. Under suitable regularity conditions, we establish convergence rates for the resulting estimator and emphasise how they depend on the dimensional parameters of the problem, in particular on the number of observed trajectories. We assess the performance of the estimator on synthetic datasets, both from an estimation and a generative perspective. Finally, we illustrate the practical relevance of the approach on a real-world climate dataset, highlighting its ability to perform variable selection.

Deep generative models for anomaly detection in multivariate time-series are typically trained by maximizing observed data likelihood. However, likelihood in observation space measures marginal density rather than conformity to structured temporal dynamics, and therefore can assign high probability to anomalous or out-of-distribution samples. We address this structural limitation by relocating the notion of anomaly to a prescribed latent space. We introduce explicit inductive biases in conditional normalizing flows, modeling time-series observations within a discrete-time state-space framework that constrains latent representations to evolve according to prescribed temporal dynamics. Under this formulation, expected behavior corresponds to compliance with a specified distribution over latent trajectories, while anomalies are defined as violations of these dynamics. Anomaly detection is consequently reformulated as a statistically grounded compliance test, such that observations are mapped to latent space and evaluated via goodness-of-fit tests against the prescribed latent evolution. This yields a principled decision rule that remains effective even in regions of high observation likelihood. Experiments on synthetic and real-world time-series demonstrate reliable detection of anomalies in frequency, amplitude, and observation noise, while providing interpretable diagnostics of model compliance.

Reliable uncertainty quantification remains a major obstacle to the deployment of deep learning models under distributional shift. Existing post-hoc approaches that retrofit pretrained models either inherit misplaced confidence or merely reshape predictions, without advising the model when to be uncertain. We introduce GUIDE, a lightweight evidential learning meta-model that attaches to a frozen deep learning model and is explicitly guided on when and how to be uncertain. GUIDE identifies salient internal features via a calibration stage and then uses these features to construct a noise-driven curriculum that teaches the model when and how to express uncertainty. GUIDE requires no retraining, no architectural modifications, and no manual intermediate-layer selection to the base deep learning model, thus ensuring broad applicability and minimal user intervention. The resulting model avoids distilling overconfidence from the base model, improves out-of-distribution detection (≈ 77

Foundational to interpreting pretrained representations of deep generative models, the linear representation hypothesis states that neural network activations encode high-level concepts as linear mixtures. However, linear representation does not imply linear accessibility of such concepts: under superposition, when the number of concepts exceeds the activation dimension, recovering the underlying latent factors requires sparse nonlinear inference, making methods such as linear probes insufficient. Sparse autoencoders (SAEs) perform nonlinear inference but amortize it into a fixed encoder, introducing a systematic amortization gap. We show this gap dominates all other error sources and persists as the number of training samples is increased, causing SAEs to fail under out-of-distribution (OOD) compositional shifts. In contrast, classical sparse coding with per-sample iterative inference leverages compressed sensing guarantees to recover latent factors robustly, maintaining near-zero gaps in the accuracy between in and out of distribution. Our results demonstrate that the recent OOD failures of SAEs can be attributed to amortization failures: per-sample inference at test time substantially improves OOD performance, even when using a dictionary learned by an SAE. This is observed along a spectrum of hybrid approaches that progressively undo amortization and recover OOD performance.

We study a robust online convex optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of rounds k, unknown to the learner. In contrast to prior works, we consider both bounded and unbounded domains and allow for large gradients for the losses without relying on a Lipschitz assumption or any prior knowledge of k. We introduce the Log Exponential Adjusted Robust and iNvex (LEARN) loss, a non-convex (invex) robust loss function to mitigate the effects of outliers and develop a robust variant of the online gradient descent algorithm by leveraging the LEARN loss. We establish dynamic regret guarantees with respect to the uncorrupted rounds and conduct experiments to validate our theory. Our upper bound matches the existing lower bound in the bounded domains and is tight (up to logarithmic factors) in the unbounded domains. Furthermore, we present a unified analysis framework for developing online optimization algorithms for non-convex (invex) losses, utilizing it to provide regret bounds with respect to the LEARN loss, which may be of independent interest.

Graph transformers are the state-of-the-art for learning from graph-structured data and are empirically known to avoid several pitfalls of message-passing architectures. However, there is limited theoretical analysis on why these models perform well in practice. In this work, we prove that attention-based architectures have structural benefits over graph convolutional networks in the context of node-level prediction tasks. Specifically, we study the neural network gaussian process limits of graph transformers (GAT, Graphormer, Specformer) with infinite width and infinite heads, and derive the node-level and edge-level kernels across the layers. Our results characterise how the node features and the graph structure propagate through the graph attention layers. As a specific example, we prove that graph transformers structurally preserve community information and maintain discriminative node representations even in deep layers, thereby preventing oversmoothing. We provide empirical evidence on synthetic and real-world graphs that validate our theoretical insights, such as integrating informative priors and positional encoding can improve performance of deep graph transformers.

Robust Markov Decision Processes (MDPs) address environmental shift through distributionally robust optimization (DRO) by finding an optimal worst-case policy within an uncertainty set of transition kernels. However, standard DRO approaches require enlarging the uncertainty set under large shifts, which leads to overly conservative and pessimistic policies. In this paper, we propose a framework for transfer under environment shift that derives a robust target-domain policy via estimate-centered uncertainty sets, constructed through constrained estimation that integrates limited target samples with side information about the source-target dynamics. The side information includes bounds on feature moments, distributional distances, and density ratios, yielding improved kernel estimates and tighter uncertainty sets. Error bounds and convergence results are established for both robust and non-robust value functions. Moreover, we provide a finite-sample guarantee on the learned robust policy and analyze the robust sub-optimality gap. Under mild low-dimensional structure on the transition model, the side information reduces this gap and improves sample efficiency. We assess the performance of our approach across OpenAI Gym environments and classic control problems, consistently demonstrating superior target-domain performance over state-of-the-art robust and non-robust baselines.