UAI 2026 Papers

Implicit graph neural networks (GNNs) cast inference as optimization, computing node embeddings as the solution to a graph-structured optimization problem. By coupling node embeddings through a shared global objective, implicit GNNs naturally capture long-range dependencies, addressing a key limitation of standard message-passing GNNs. Another appealing property of these models is that inference can be performed in a decentralized and asynchronous manner, making them well suited for deployment in multi-agent systems. However, training is costly, as it requires solving optimization problems in both the forward and backward pass. In this work, we focus on graph-level prediction and introduce an approach for directly computing graph-level representations in implicit GNNs that bypasses the need for node embeddings. We do this by reformulating the internal optimization problem to operate over a shared graph embedding. This significantly reduces both computation and memory costs, while retaining compatibility with decentralized and asynchronous inference. Experiments across multiple benchmarks show that the shared-embedding approach consistently matches the predictive performance of using node embeddings, providing a simpler and more efficient alternative for graph-level tasks.

This paper studies a learning-based optimal admission control policy for an Erlang–B queuing system under partial observation. Only at each arrival, the dispatcher observes the current occupancy and decides whether to accept or reject the job. A completed job yields a fixed reward but incurs a cost proportional to the service duration. The objective is to design an admission control policy that maximizes the long-term average reward. The arrival and service rates are unknown, and unobserved departures complicate parameter estimation. The reward structure induces an asymmetry in the optimal decision across parameter regimes. We establish an instance-dependent asymptotic lower bound, explicitly dependent on the system parameters, demonstrating that the worst-case regret is logarithmic in the number of arrivals in one regime.

Causal knowledge can be used to support decision-making problems. This has been recognized in the causal bandits literature, where a causal (multi-armed) bandit is characterized by a causal graphical model and a target variable. The arms are then interventions on the causal model, and rewards are samples of the target variable. Causal bandits were originally studied with a focus on hard interventions. We focus instead on cases where the arms are conditional interventions, which more accurately model many real-world decision-making problems by allowing the value of the intervened variable to be chosen based on the observed values of other variables. This paper presents a graphical characterization of the minimal set of nodes guaranteed to contain the optimal conditional intervention, which maximizes the expected reward. We then propose an efficient algorithm with a time complexity of O(|V| + |E|) to identify this minimal set of nodes. We prove that the graphical characterization and the proposed algorithm are correct. Finally, we empirically demonstrate that our algorithm significantly prunes the search space and substantially accelerates convergence rates when integrated into standard multi-armed bandit algorithms.

Generative Marginalization Models (MaMs) have been recently introduced as efficient neural sampling models for any-order autoregressive modelling of discrete distributions. By learning both the marginal and conditional probabilities of a persistent-block Gibbs sampler, MaMs enable fast posterior evaluation with a single neural network forward pass. While prior work has considered MaMs to be distinct from Generative Flow Networks (GFlowNets), a well-established paradigm for inference in discrete stochastic models, we show that they are equivalent. Then, we also extend MaMs’ sampling strategy to non-autoregressive generative processes. In particular, we describe an automatic criterion for full-state rejuvenation of the Gibbs sampler, derived from the Gelman-Rubin statistic, which plays a key role in speeding up learning convergence. Our experiments show that our method, called Particle GFlowNets, markedly accelerates training in large combinatorial spaces.

Max-linear Bayesian networks (MLBNs) are a novel class of directed acyclic graphical models which are of interest to statistics and data science due to their relevance to causality and probabilistic inference, particularly of extreme events. Interestingly, MLBNs encode strictly more conditional independence than general structural causal models. Because of this, MLBNs are Markov to a strengthening of the d-separation criterion called ∗-separation. As many tools for causal inference (most notably, Judea Pearl’s do-calculus) are based on d-separation, we address the natural question of whether assuming Markovianity to ∗-separation can lead to additional causal effect identifiability under intervention. We answer this question in the affirmative and develop a stronger version of the do-calculus rules for models which are Markov to ∗-separation. However, we note that restrictions inherent to the max-linear setting (in particular, that they give rise to non strictly positive joint probability distributions) mean that our calculus is only applicable to specific kinds of policy intervention.

Bayesian inference for inverse problems involves computing expectations under posterior distributions–e.g., posterior means, variances, or predictive quantities–typically via Monte Carlo (MC) estimation. When the quantity of interest varies significantly under the posterior, accurate estimates demand many samples–a cost often prohibitive for partial differential equation-constrained problems. To address this challenge, we introduce conditional neural control variates, a modular method that learns amortized control variates from joint model-data samples to reduce the variance of MC estimators. To scale to high-dimensional problems, we leverage Stein’s identity to design an architecture based on an ensemble of hierarchical coupling layers with tractable Jacobian trace computation. Training requires: (i) samples from the joint distribution of unknown parameters and observed data; and (ii) the posterior score function, which can be computed from physics-based likelihood evaluations, neural operator surrogates, or learned generative models such as conditional normalizing flows. Once trained, the control variates generalize across observations without retraining. We validate our approach on stylized and partial differential equation-constrained Darcy flow inverse problems, outperforming classical Stein control variates and achieving substantial variance reduction, even when the analytical score is replaced by a learned surrogate.

As an effective post-processing approach to improving the quality of integrated labels, noise correction has received extensive attention in recent years. Recent studies have shown that utilizing information from both the original attribute view and the multiple noisy label view can significantly improve the performance of noise correction. However, most existing algorithms often learn information independently on each view, making them difficult to fully exploit the complementary information between these two views. To address this limitation, we propose a noise correction algorithm called collaborative multi-view learning from crowds (CMLFC). CMLFC first constructs instance correlation graphs on the original attribute view and the multiple noisy label view, respectively, and designs dedicated encoders to obtain view-specific representations. To capture the deep complementary information between these two views, it designs a contrastive fusion encoder to distill common representations from these two view-specific representations, and then forms a common view. Next, it trains three view-specific classifiers on these three views, and designs a joint loss function to collaboratively train these encoders and classifiers, enabling information to flow bidirectionally among views, thereby improving the quality of representations in each view. Finally, it employs the trained view-specific encoders and classifiers to obtain each instance’s representations and class probability distributions, respectively, which are then used to update its integrated label. Extensive experiments on real-world crowdsourced datasets validate the effectiveness, ablation, and sensitivity of CMLFC. Our codes and datasets are available at https://github.com/jiangliangxiao/CMLFC.

This paper studies the problem of identifying the treatment that maximizes the expected natural direct potential outcome (NDPO), which captures the potential outcome of an intervention while excluding the pathway transmitted through a mediator that researchers may wish to remove from evaluation. We first establish population-level identification of the expected NDPO in a causal bandit setting using observable interventional distributions. We then develop a fixed-confidence best-arm identification (BAI) algorithm based on the Track-and-Stop (TaS) framework, employing a cutting-set method to solve the resulting semi-infinite optimization problem. The proposed algorithm achieves sample-efficient identification with a high-probability correctness guarantee. We prove that it satisfies δ-correctness and asymptotic optimality. Finally, we validate the approach through empirical evaluations on a large-scale real-world advertising dataset (IPinYou).

"Probabilities of causation" play a crucial role in practical science. Pearl [2009] defined three types of probabilities of causation in the context of structural causal models: the probability of necessity (PN), the probability of sufficiency (PS), and the probability of necessity and sufficiency (PNS). Furthermore, Tian and Pearl [2000] and Kuroki and Cai [2011] provided the identification conditions for these probabilities under the assumption of monotonicity. However, these identification conditions are described based on "the joint probabilities of observed probabilities" and/or "causal risks". Therefore, they are not applicable to case–control studies, in which the available statistical data are given in the form of the conditional probabilities of observed variables given an outcome variable. To address this limitation, this paper provides novel identification conditions for the probabilities of causation using (i) two proxy covariates and (ii) a proxy covariate together with an instrumental variable. Remarkably, the use of a proxy covariate and an instrumental variable enables the identification not only of the probabilities of causation but also of the joint distribution of the potential outcome variables. When these probabilities can be evaluated using the proposed identification conditions, new plug-in estimators of these probabilities are presented.

Reliable uncertainty quantification (UQ) is critical for safety-sensitive federated learning (FL) applications, such as cross-hospital diagnosis and global sensor networks. In FL, privacy constraints prevent centralized data pooling, while client data exhibit joint distribution shifts across covariates, labels, and conditionals. These shifts violate the exchangeability assumption required by conformal prediction (CP), which otherwise guarantees distribution-free coverage under i.i.d. data. To address this gap, we propose Federated Conformal Prediction for Joint Shift (FCPJS), enabling valid CP under heterogeneous clients without sharing raw data. Specifically, the method operates in two stages: (i) the server constructs a privacy-preserving global sketch of nonconformity score distributions; (ii) each client performs importance-weighted calibration by contrasting its local scores with the global sketch. This distribution-ratio weighting corrects joint shifts in a unified manner. We prove that FCPJS attains valid marginal coverage across clients, up to an O(√(ε_m)+1/√(n)) error from the finite number of calibration samples n and sketch size m. Experiments on four heterogeneous benchmarks show that preserves coverage and improves predictive efficiency by 12.64

The problem of learning from pairwise comparisons has been widely studied across many domains such as recommendation systems, social choice, and more recently, fine-tuning large language models. In this problem, the goal is to learn item rewards based on pairwise comparisons between them. In many scenarios, these comparisons are elicited from crowdworkers using platforms such as Amazon Mechanical Turk, Scale AI, etc. However, crowdworkers are often unreliable due to limited domain knowledge or revenue-maximizing (spamming) behavior. In this work, our goal is to understand whether worker reliability (competency) can be learned jointly with item rewards. To this end, we adopt the Boltzmann-rational model for pairwise comparisons, which extends the Bradley–Terry–Luce model by incorporating worker competencies. We derive an EM-based algorithm for learning under this model by introducing Polya-Gamma latent variables to transform the logistic likelihood into a conditionally Gaussian form, enabling tractable optimization and leading to a simplified Q function in the E-step of the algorithm. This technique allows us to reduce our formulation to a matrix sensing problem, using which we establish theoretical convergence guarantees for our algorithm. We conduct extensive experiments on real-world and synthetic datasets. These experiments demonstrate the advantages of using our algorithm over several baselines and confirm its strong robustness to both spammers and adversarial workers, highlighting its practical effectiveness in realistic crowdsourcing and reward learning settings.

by [Pham and Pagh, 2013, Kar and Karnick, 2012] provides efficient sketching algorithms for high-dimensional polynomial kernels 𝐱^⊗ p∈ℝ^d^p. [Kar and Karnick, 2012] uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), whereas [Pham and Pagh, 2013] extends the sparse [Charikar et al., 2004] algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time O(p(nnz(𝐱) + D log D)). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3^p/D, where D denotes the sketch dimension. Recent work by [Wacker et al., 2023] showed that using complex-valued distribution reduces this dependence to 2^p/D for the approach of [Kar and Karnick, 2012]. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of [Pham and Pagh, 2013]. In this work, we introduce a simple variant of [Pham and Pagh, 2013] that achieves the same variance bound as [Wacker et al., 2023], while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.

Effective model-based reinforcement learning in stochastic environments requires planning that accounts for predictive uncertainty. Propagating full state distributions analytically offers a principled way to do this, but has traditionally required restrictive policy or reward structures to remain tractable. Consequently, modern deep reinforcement learning has largely retreated to either stochastic sampling, which introduces significant target variance, or deterministic point estimates that ignore predictive covariance entirely. We investigate whether distribution-aware planning is possible without these constraints. Using a quadratic action-value parameterization, we first reduce the Bellman backup to an expectation over the state-value function alone; the key idea is then a compatibility principle between the predictive transition distribution and the value function class, under which this expectation is analytic in the distribution’s moments. We instantiate this principle with a Gaussian transition model paired with a radial-basis value function, yielding a closed-form backup that propagates both predictive mean and covariance. Empirically, our approach reduces target variance and yields well-calibrated predictive uncertainty under stochastic observations in continuous control, providing a principled framework for planning with learned distribution models.

We study active elicitation of agent preferences for collectively choosing among m alternatives using prominent voting rules. We focus on the next-best query model, in which an agent responds to a query by revealing their next most favorite alternative, and measure the competitive ratio, which is the worst case ratio between the number of queries made by the active elicitation algorithm and the minimum number of queries needed to reveal the winning alternative(s) in hindsight. We show that the best competitive ratio is sublinear in m for many positional scoring rules but linear in m for all Condorcet-consistent rules. Our analysis centers on a simple elicitation algorithm we propose, which not only achieves optimal theoretical bounds, but also impressive empirical performance on real data.

This paper introduces Gestalt Reasoning Machines (GRMs), a novel neuro-symbolic framework that integrates Gestalt principles to enhance reasoning models with perception capabilities similar to human cognition. Traditional models, which rely on large datasets and complex computations, often overlook the crucial human cognitive function of grouping, resulting in inefficiencies when dealing with abstract concepts. GRMs address this challenge by incorporating a grouping mechanism grounded in Gestalt principles, enabling the system to recognize and reason over complex visual patterns that are otherwise difficult to capture through object-level features alone. This grouping capability allows GRMs to identify higher-order structures and relational configurations that are essential for human-like reasoning. We demonstrate that GRMs outperform purely neural baselines by leveraging logic-based reasoning infused with perceptual grouping cues, offering a more interpretable and cognitively aligned approach. Our contributions include the design of GRMs and the empirical validation of their effectiveness in visual reasoning tasks that demand structured perception.

We study identifiability in continuous-time linear stationary stochastic differential equations with a known causal structure. Unlike existing approaches, we relax the assumption of a known diffusion matrix, thereby respecting the model’s intrinsic scale invariance. Therefore, rather than recovering drift coefficients themselves, we introduce edge-sign identifiability: for a given causal structure, we ask whether the sign of a given drift entry is uniquely determined across all observational covariance matrices induced by parametrisations compatible with that structure. This leads to a trichotomy of edge-sign identifiability: identifiable, non-identifiable, and partially identifiable. This trichotomy introduces the new notion of partial identifiability to the literature, which we show is a genuine category in our setting. Under a notion of faithfulness, we derive criteria to identify membership of each category for general graphs. Applying our criteria to specific causal structures, both analogous to classical causal settings (e.g., instrumental variables) and novel cyclic settings, we determine their edge-sign identifiability and, in some cases, obtain explicit expressions for the sign of a target edge in terms of the observational covariance matrix.

We study stochastic bandits in which observing a reward is optional but incurs an action-dependent cost. This setting captures applications where feedback acquisition (e.g., human evaluation or randomized testing) is expensive, and the learner must trade off exploration, exploitation, and observation cost. We formulate regret to include both reward loss and the cumulative cost of requested observations. Our first result is structural: for minimizing regret, it is without loss of generality to consider two-phase policies that first request labels during an exploration phase and then commit to a single action without further observations. Building on this reduction, we introduce two cost-sensitive complexity measures that extend maximum information gain: a cost-adjusted information gain Γ_T(c) for minimax analysis, and a cost- and gap-adjusted information gain Γ_T^gap(Δ_c) for instance-dependent analysis. Using these quantities, we develop two Gaussian-process-based algorithms, C3-GP and GP-C-LUCB, and derive regret upper bounds for correlated-action settings with heterogeneous observation costs. In the finite independent-arm setting, we further prove matching lower and upper bounds (up to constants/logarithmic factors), yielding a tight characterization of both minimax and instance-dependent regret in terms of the proposed cost-aware complexity measures.

Tabular data is more challenging to generate than text and images, due to its heterogeneous features and much lower sample sizes. On this task, diffusion-based models are the current state-of-the-art (SotA) model class, achieving almost perfect performance on commonly used benchmarks. In this paper, we question the perception of progress for tabular data generation. First, we highlight the limitations of current protocols to evaluate the fidelity of generated data, and advocate for alternative ones. Next, we revisit a simple baseline—hierarchical mixture models in the form of deep probabilistic circuits (PCs)—which delivers competitive or superior performance to SotA models for a fraction of the cost. PCs are the generative counterpart of decision forests, and as such can natively handle heterogeneous data as well as deliver tractable probabilistic generation and inference. Finally, in a rigorous empirical analysis we show that the apparent saturation of progress for SotA models is largely due to the use of inadequate metrics. As such, we highlight that there is still much to be done to generate realistic tabular data.

We study infinite-horizon Constrained Markov Decision Processes (CMDPs) with general policy parameterizations and multi-layer neural network critics. Existing theoretical analyses for constrained reinforcement learning largely rely on tabular policies or linear critics, which limits their applicability to high-dimensional and continuous control problems. We propose a primal–dual natural actor–critic algorithm that integrates neural critic estimation with natural policy gradient updates and leverages Neural Tangent Kernel (NTK) theory to control function-approximation error under Markovian sampling, without requiring access to mixing-time oracles. We establish global convergence and cumulative constraint violation rates of 𝒪̃(T^-1/4) up to approximation errors induced by the policy and critic classes. Our results provide the first such guarantees for CMDPs with general policies and multi-layer neural critics, substantially extending the theoretical foundations of actor–critic methods beyond the linear-critic regime.