UAI 2026 Papers

Robust machine learning and optimization rely on the uncertainty model choice. We investigate which uncertainty directions a model must cover when defined by a finite dictionary and a budget constraint. Selecting a subset forms an atomic uncertainty set with a closed form support function, yielding tractable robust programs for affine objectives. We propose a data-driven selection rule based on a coverage objective over evaluation directions, including gradients, adversarial perturbations, or shifts observed on held out data. We prove this objective is monotone and submodular, supporting a greedy method with a (1-1/e) approximation guarantee and a matching hardness barrier. We also provide a certificate bounding the loss from the selected subset and a radius calibration rule with out-of-sample control.

Many counterfactual and causal queries are only partially identified from data, especially under unmeasured confounding. A common approach represents compatible nonparametric structural causal models (SCMs) on a finite canonical domain and computes sharp bounds via linear programming (LP) over the induced simplex. However, the canonical full counterfactual state space grows exponentially even for small graphs, making naive LP-based bounding computationally heavy. We propose a constraint-aware reduction that quotients out degrees of freedom irrelevant to the optimization problem. Because sharp bounds are determined jointly by the query functional and the data-implied information set, we aggregate full states into equivalence classes that are indistinguishable to every linear functional appearing in the LP objective and constraints. We show that optimizing over the induced push-forward distribution on the reduced domain preserves feasibility and yields the same sharp bounds as the full-domain.

Algorithmic decisions about individuals require predictions that are not only accurate but also fair with respect to sensitive attributes such as gender and race. Causal notions of fairness align with legal requirements, yet many methods assume access to detailed knowledge of the underlying causal graph, which is a demanding assumption in practice. We propose a learning framework that achieves interventional fairness by leveraging a causal graph over *clusters of variables*, which is substantially easier to estimate than a variable-level graph. With possible *adjustment cluster sets* identified from such a cluster causal graph, our framework trains a prediction model by reducing the worst-case discrepancy between interventional distributions across these sets. To this end, we develop a computationally efficient barycenter kernel maximum mean discrepancy (MMD) that scales favorably with the number of sensitive attribute values. Extensive experiments show that our framework strikes a better balance between fairness and accuracy than existing approaches, highlighting its effectiveness under limited causal graph knowledge.

We study episodic reinforcement learning with adversarial losses and bandit feedback in MDPs with unknown transitions under a linear-mixture model. In this setting, prior studies are typically built upon global optimization methods with the notion of occupancy measure, rather than the purely local policy optimization-based method, which avoids solving a constrained convex optimization problem and is thus more preferred in practice. In this work, we develop the first policy optimization-based algorithm that runs online mirror descent locally on each state. The main challenge is to interface local updates with transition learning: the dilated-bonus analysis requires predictable reachability surrogates and robust one-step maximizations over a confidence set, but the statistically natural VLS confidence region is a coupled ellipsoid over a shared parameter and is not (s,a)-rectangular. We address this by rectangularizing the VLS ellipsoid into local per-(s,a) kernel sets, which enables robust dynamic programming to compute occupancy envelopes and to drive the implicit-exploration estimator and dilated bonuses. Based on this technique, we prove a high-probability regret bound 𝒪(H^3/2√(S AK) + dH^3/2 S^3/2√(K)), which nearly matches the best-known bound achieved by occupancy-measure-based methods.

Belief Propagation (BP) has operated in Euclidean space for four decades, yet the polynomial volume growth of ℝ^d is fundamentally mismatched to hierarchical graphs: faithful embedding of exponentially branching structure demands d = Ω(log n) dimensions and prohibitive 𝒪(d^3) covariance costs, while truncating d corrupts marginal estimates. We introduce Continuous Hyperbolic Belief Propagation (CHBP), formulated natively on the Lorentz hyperboloid ℍ^n_K, whose exponential volume growth eliminates this bottleneck. CHBP parameterises beliefs as Jacobian-corrected Wrapped Normals, approximates message integrals via Gauss–Hermite quadrature, and transports covariance tensors between tangent spaces via closed-form Levi-Civita parallel transport, with a curvature annealing schedule ensuring stable convergence. On hierarchical graphs, CHBP at d=5 reduces marginal KL divergence by 25× versus Euclidean BP at d=50 and achieves up to 91.45

The K-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward is determined by the maximum outcome among K selected arms. When outcomes are continuous and only the maximum value together with the winner’s index is observed, this problem introduces unprecedented difficulties including discretization errors, non-deterministic tie-breaking, and severe estimation biases. To overcome these barriers, we introduce DCK-UCB, an efficient algorithm combining adaptive discretization with bias-corrected confidence bounds. We prove that DCK-UCB achieves a 𝒪(T^3/4) regret bound, the first sublinear guarantee in this setting. Numerical experiments show its superior performance over baseline methods. Furthermore, for the specific case of exponential distributions under full-bandit feedback, we propose MLE-Exp algorithm that attains a near-optimal 𝒪(√(T)) regret bound. This work establishes fundamental theoretical guarantees and provides a powerful algorithmic solution for continuous combinatorial bandits.

The classical notion of causal effect identifiability is defined in terms of treatment and outcome variables. In this paper, we consider the identifiability of state-based causal effects: how an intervention on a particular _state_ of treatment variables affects a particular _state_ of outcome variables. We demonstrate that state-based causal effects may be identifiable even when variable-based causal effects may not. Moreover, we show that this separation occurs only when additional knowledge — such as context-specific independencies — is available. We further examine knowledge that constrains the states of variables, and show that such knowledge can improve both variable-based and state-based identifiability when combined with other knowledge such as context-specific independencies. We finally propose an approach for identifying causal effects under these additional constraints, and conduct empirical studies to further illustrate the separations between the two levels of identifiability.

We study finite-sample equilibrium learning in episodic two-player zero-sum Markov games, where Nash equilibria coincide with minimax saddle points and Nash-Q style value iteration provides a natural algorithmic template. Existing analyses of Nash-Q style learning provide regret guarantees in tabular settings and under fixed linear realizability, but do not explicitly account for representation error arising from scalable nonlinear approximation. We propose an optimistic Nash Q-learning framework that replaces tabular/linear value representations with a hyperdimensional random-feature embedding—instantiated via random Fourier features to approximate a shift-invariant kernel—while retaining tractable ridge-style updates and per-state minimax stage-game computation. Our main results establish high-probability regret guarantees that decompose into a statistical uncertainty term governed by an effective-dimension complexity measure and an explicit additive approximation term induced by random-feature kernel approximation. The approximation term decreases with the embedding dimension, yielding a principled approximation–estimation tradeoff and recovering linear-style finite-sample behavior in the realizable regime. Empirically, we evaluate on a suite of episodic zero-sum benchmarks spanning tabular and continuous-state settings and observe stable learning behavior and performance trends consistent with the predicted dependence on representation dimension.

High-stakes decision-making involves navigating multiple competing objectives with expensive evaluations. For instance, in brachytherapy, clinicians must balance maximizing tumor coverage (e.g., an aspirational target or soft bound of >95

Safe reinforcement learning typically enforces safety by bounding expected cumulative costs, a criterion that often fails to detect rare but catastrophic tail events. To overcome these limitations, this paper introduces SteinGate, a boundary-aware distributional safety certificate that replaces fragile tail fitting with a robust consistency check using Kernelized Stein Discrepancy while accounting for boundary atoms induced by clipped costs. SteinGate evaluates whether observed policy rollout costs remain consistent with a safe reference distribution, providing a non-parametric safety certificate. This certificate is used to dynamically adapt the learning regime: favoring reward-improving policy updates when rollouts remain consistent with the safe reference and switching to recovery behavior when the cost tail deviates. Experiments on continuous-control benchmarks demonstrate that SteinGate significantly reduces both the frequency and severity of constraint violations during training while maintaining competitive returns relative to state-of-the-art baselines.

We study the classic linear regression problem under the challenging setting of heteroskedastic noise. We study a model in which we have n sources that each observe linear measurements of an unknown d-dimensional vector β. Each source has an unknown and distinct variance for the error, and the goal is to estimate the parameter vector β, under the assumption that there exist sufficiently many sources with small error (specifically, m sources have variance at most 1). Our results show that β can be estimated to sub-constant error, as long as the number of small-error sources, i.e., m, is large enough. We prove two main results. First, we show that even with just one observation per source, under minimal assumptions on the linear measurements, β can be estimated to sub-constant error when m ≥ n^1- 1/4d. Second, we show that if we have access to two observations per source, under similar assumptions on the linear measurements, β can be estimated to sub-constant error when m ≥ n^5/6. Our results are related to the recent line of work on mean estimation with heteroskedastic variances, and more specifically, the subset of signals model used in this literature. To the best of our knowledge, our results provide the first sub-constant recovery guarantees for regression in this model.

Quantile-based distribution families are an important subclass of parametric families, capable of exhibiting a wide range of behaviors using very few parameters. These parametric models present significant challenges for classical methods, since the CDF and density do not have a closed-form expression. Furthermore, approximate maximum likelihood estimation and related procedures may yield non-√(n) and non-normal asymptotics over regions of the parameter space, making bootstrap and resampling techniques unreliable. We develop a novel inference framework that constructs confidence sets by inverting distribution-free confidence bands for the empirical CDF through the known quantile function. Our proposed inference procedure provides a principled and assumption-lean alternative in this setting, requiring no distributional assumptions beyond the parametric model specification and avoiding the computational and theoretical difficulties associated with likelihood-based methods for these complex parametric families. We demonstrate our framework on Tukey Lambda and generalized Lambda distributions, evaluate performance through simulation studies, and illustrate practical utility with applications to a small-sample dataset (Twin Study) and a large-sample dataset (Spanish household incomes).

Multi-agent decision-making under both uncertainty and constraints is a central challenge in safety-critical domains such as autonomous driving, where agents must coordinate in uncertain environments while ensuring feasibility with respect to safety and resource limits. However, there is limited theoretical and practical work that addresses this challenge. Therefore, we introduce a Robust Constrained Markov Game (RCMG), the first multi-agent framework that simultaneously captures adversarial transition uncertainty and cost constraints. We further propose a solution concept, the Robust and Feasible Nash Equilibrium (RFNE), and a principled relaxation that yields a tractable surrogate upper bound to the intractable problem of computing an exact RFNE. This surrogate enables both a fixed-point existence proof via Kakutani’s theorem and a decentralized algorithm that alternates robust dynamic programming with Lagrangian dual updates. In settings where the relaxation is tight, the method provably recovers an exact RFNE. A grid-world experiment illustrates consistency with the theoretical results and highlights the viability of RCMGs as a foundation for reliable multi-agent decision-making under uncertainty and constraints.

We study the problem of allocating contiguous blocks of indivisible items positioned on a line to a set of agents where agents are partitioned into different groups. In the problem, agents must be located on a line, and items allocated to each agent must be contiguous and form a connected block. We study the settings, considered by Suksompong [2019] and Wang et al. [2021], without and with the requirement that items are assigned to their closest agents, respectively. For both settings, we focus on allocations that satisfy intra-group envy fairness (IEF) and inter-group fair share (GFS). In both settings, we show that determining the existence of IEF or GFS allocations is NP-complete. When the number of agents or items is constant, we provide polynomial algorithms to determine the existence of IEF or GFS allocations for both settings. For both settings, we provide upper and lower bounds on the existence of IEF or GFS allocations as well as allocations that satisfy both IEF and GFS simultaneously.

Boosting algorithms such as AdaBoost have achieved widespread success by iteratively focusing on hard-to-classify instances. However, this aggressive re-weighting mechanism makes them susceptible to label noise and overfitting. While robust variants like Conditional Boosting handle this by estimating conditional risk, they rely on global statistical approximations. We propose Neural Routed Boosting, a novel ensemble framework that addresses heteroscedastic noise through a structural approach. Neural Routed Boosting utilizes a lightweight neural network to partition the input space into geometrically coherent regions, training specialized weak learners for each. This isolates noisy subspaces, preventing them from corrupting the decision boundaries of clean regions. We prove that the composite model of a neural router and region-specific experts constitutes a valid weak learner under the boosting framework, guaranteeing training error convergence. Experimental results on synthetic and real-world datasets demonstrate that Neural Routed Boosting outperforms traditional and robust boosting baselines, including Conditional Boosting, in high-noise environments.

We propose a robust Bayesian formulation of random feature (RF) regression that accounts explicitly for prior and likelihood misspecification via Huber-style contamination sets. Starting from the classical equivalence between ridge-regularized RF training and Bayesian inference with Gaussian priors and likelihoods, we replace the single prior and likelihood with ϵ- and η-contaminated credal sets, respectively, and perform inference using pessimistic generalized Bayesian updating. We derive explicit and tractable bounds for the resulting lower and upper posterior predictive densities. These bounds show that, when contamination is moderate, prior and likelihood ambiguity effectively acts as a direct contamination of the posterior predictive distribution, yielding uncertainty envelopes around the classical Gaussian predictive. We introduce an Imprecise Highest Density Region (IHDR) for robust predictive uncertainty quantification and show that it admits an efficient outer approximation via an adjusted Gaussian credible interval. We further obtain predictive variance bounds (under a mild truncation approximation for the upper bound) and prove that they preserve the leading-order proportional-growth asymptotics known for RF models. Together, these results establish a robustness theory for Bayesian random features: predictive uncertainty remains computationally tractable, inherits the classical double-descent phase structure, and is improved by explicit worst-case guarantees under bounded prior and likelihood misspecification.

Personalized decision-making in multi-objective bandits requires learning user-specific trade-offs among competing objectives. Since arm utility depends on both unknown rewards and unknown preferences, existing methods infer preferences only from utility feedback, entangling preference learning with reward exploration. In practice, however, users often reveal their priorities through proactive conversational queries (e.g., “cheap and clean hotel”), yet this structured signal is not leveraged. We formalize a proactive query-based framework in which user queries provide structured preference signals. Modeling these signals via a Plackett–Luce subset choice model, we show that query-only learning is insufficient due to a fundamental shift-invariance barrier. To resolve this, we introduce MO-PQUCB, a hybrid algorithm that integrates query-based preference anchoring with bandit feedback through shift-invariant regularization and dual-exploration UCB. We prove that proactive queries accelerate preference estimation and yield improved regret scaling over prior preference-aware MO-MAB methods. Under corrupted queries, we further characterize statistical limits and design a robust estimator achieving near-optimal performance when corruption is sparse. Experiments validate both theoretical and practical gains.

Uncertainty quantification is crucial in machine learning, yet most (axiomatic) studies of uncertainty measures focus on classification, leaving a gap in regression settings with limited formal justification and evaluations. In this work, we provide a formal way of representing uncertainty in continuous space, using a general parametric formulation, allowing for tractable analysis and evaluation of uncertainty measures. Within this framework, we propose a set of axioms that enable rigorous assessment of total, aleatoric, and epistemic uncertainty measures. Together, this allows for a theoretical examination of uncertainty measures and their corresponding properties. As a specific example, we compare the widely used entropy- and variance-based measures with respect to established predictive models and analyze their limitations and challenges in uncertainty quantification. Our work provides a principled way to understand and develop uncertainty measures in supervised regression, offering theoretical insights and practical guidelines for reliable uncertainty assessment.

Regression tasks, notably in safety-critical domains, require reliable uncertainty quantification, yet the literature remains largely classification-focused. To address this, we introduce a family of measures for total, aleatoric, and epistemic uncertainty in multivariate regression based on strictly proper kernel scores. The framework provides a principled recipe for designing new uncertainty measures whose behavior, such as tail sensitivity or out-of-distribution responsiveness, is governed by the choice of the underlying kernel, while also encompassing existing measures under a joint analysis. We prove explicit correspondences between properties of the kernel and behavior of resulting uncertainty measures, yielding concrete design guidelines for practitioners. Extensive experiments across structured regression tasks, including spatial and functional domains, demonstrate effectiveness on downstream tasks such as out-of-distribution detection and active learning, and reveal that different kernel choices lead to distinct trade-offs, offering practitioners guidance for task-specific selection.