NeurIPS 2026 Papers

The task of constructing a predictor that is simultaneously accurate under multiple evaluation metrics has been popularized recently under the name omniprediction. Prior work in this area has largely focused on binary prediction tasks, and existing results for multiclass and continuous outcomes typically suffer from slow error rates. In this paper, we consider forecasts expressed as a set of quantiles over a discrete but otherwise arbitrary set of probability levels. We develop sample-efficient algorithms for constructing forecasts that are simultaneously accurate across all proper losses that satisfy mild regularity conditions, where proper losses are those minimized by predicting the true quantiles. Our algorithms are online and can operate in a dynamic environment while simultaneously taking multiple losses into account, and their forecasts offer the potential to provide diverse end-users with rich information for evaluating risk and informing a range of practical decision-making tasks. As an example, we demonstrate how our procedure can be used to ensemble quantile forecasts of COVID-19 hospitalizations made by experts during the pandemic.

We present an algorithm for margin-based online learning using lossless compressors (like zip) via the Minimum Description Length Principle. The technique, we call \emph{MDL-PA}, can be viewed as an analogue of Passive-Aggressive algorithms for probability distributions (equivalently viewed as lossless compression schemes) where we consider a \emph{code length margin}. Separate models are maintained per class, and the update rule is an information projection correcting the true-class model's prediction on a margin-violating sample. To bridge theory and practice, we demonstrate a practical approximation to this online learning setup via adaptive Lempel-Ziv-style compression dictionaries to classify sequences in the text and malware domains.

Conformal prediction is a framework that provides valid uncertainty quantification for general models with exchangeable data. However, in the online learning and time-series settings, exchangeability is not satisfied. Existing online conformal methods, such as adaptive conformal inference (ACI), can achieve long-run validity, yet they remain inefficient under covariate heterogeneity because they rely on global calibration. We propose *Online Localized Conformal Prediction (OLCP)*, which combines online adaptation with covariate-dependent localization to better reflect heterogeneity. To reduce sensitivity to the localization bandwidth, we further develop *OLCP-Hedge*, which performs bandwidth selection as an online expert aggregation problem using a constrained online convex optimization framework. Importantly, we provide coverage guarantees for both algorithms and demonstrate through simulations and real-data experiments that the proposed methods attain valid long-run coverage with narrower prediction intervals than existing baselines.

Online learning in non-stationary environments requires models to adapt rapidly from streaming data under strict computational constraints. A principled approach casts online learning as Bayesian state tracking, where model parameters are updated sequentially via Bayesian filtering. However, applying Bayesian filters directly to modern deep models is computationally prohibitive due to the high dimensionality of parameter space, forcing existing methods to rely on restrictive approximations or manually designed low-dimensional subspaces. In this work, we identify the absence of a suitable low-dimensional dynamical representation as the core bottleneck in Bayesian filtering-based online learning. Accordingly, we propose Adaptive Update through Representation Adaptation (AURA), a meta-learning framework that learns offline a low-dimensional latent state-space model governing the evolution of optimal model parameters under distribution shift. Online adaptation is then performed via extended Kalman filtering in this learned latent space followed by reconstruction of the full model parameters through a learned lifting map, enabling efficient single-step online adaptation while preserving model expressiveness. Evaluated on online adaptation of neural wireless receivers under time-varying channels and on non-stationary image classification, AURA shows substantial improvements in adaptation speed, accuracy, and computational efficiency over existing online learning and Bayesian filtering baselines, demonstrating that an adaptation-aware latent geometry is beneficial for effective Bayesian online learning in high-dimensional models.

We study online learning in linear dynamical games where multiple strategic agents act on a shared state evolving according to a linear dynamical system subject to adversarial disturbances. This setting lies beyond both single-agent nonstochastic online control and classical linear-quadratic games, which typically focus on quadratic objectives and noiseless or stochastic dynamics. Each agent seeks to minimize its own sequence of convex losses under full-state observability. Following the stabilizing-baseline paradigm in nonstochastic online control, we assume access to linear controllers that stabilize the noiseless system and focus on online adaptation by learning disturbance-action corrections. This extends adversarial online control to strategic multi-agent shared-state systems, where each agent's actions shape the state trajectory and hence the realized losses of all learners. Under state-only and aggregate-input feedback models, we analyze agents running online gradient descent with memory to update their own disturbance-action policies. We prove per-agent regret bounds that are sublinear and near-optimal in the time horizon, and show how their dependence on the number of agents varies with the feedback available to each learner. In the common-interest case, where all agents have identical cost functions, we show that the induced online problem forms a time-varying potential game and derive equilibrium-tracking guarantees. Together, these results provide a theoretical framework for adversarial online learning in stabilized linear dynamical games, connecting online control with learning in games.

We study the _online fair division_ of indivisible _mixed manna_ among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on _envy-freeness_ (EF) and one of its most prominent relaxations, _envy-freeness up to one item_ (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with _buffers_ that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized $k$-value instances, i.e., instances in which each agent assigns at most $k$ distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in $k$ and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.

Online A/B tests are the dominant tool for evaluating new LLM variants in deployment: each user query arrives sequentially, must be routed to one variant before its outcome is observed, and is then scored against the alternative. In practice, these tests almost always use complete randomization. Yet for many queries, simple signals such as predicted difficulty, expected reward, or embedding-based scores are already available, and these are predictive of the outcome. Using them to guide assignment can substantially reduce the variance of the estimated treatment effect. We propose a new dyadic design that uses such covariates to balance treatment and control online across the full covariate distribution, with no hyperparameters to tune. Under stochastic arrivals, our design attains a covariate matching discrepancy of $O(\log^{3} T)$ in one dimension, which is a significant improvement over the $O(T^{1/4})$ rate of existing online stratified designs, and matches the offline minimax rate up to logarithmic factors in higher dimensions, closing a gap left open by prior work. Experiments on a sequential A/B test simulator built from AlpacaEval, in which 805 prompts are scored under two real LLM variants, confirm the theory: our design achieves a covariate matching discrepancy roughly $6\times$ smaller than complete randomization and consistently outperforms the best-tuned online stratified baseline. The method extends to multi-dimensional covariates and to general sequential evaluation pipelines.

We develop an online directional regression for sufficient dimension reduction with streaming data. Unlike first-moment methods, directional regression exploits both inverse conditional means and inverse conditional variances, and can therefore recover central subspace directions generated by linear structures, symmetric dependencies, and interaction driven relationships. Extending directional regression to the online setting is nontrivial because its kernel depends on slice-wise inverse moments and on standardization by an unknown covariance matrix. We address these challenges by utilizing a stable slice probability free kernel, a ridge-stabilized recursive least-squares estimator of the standardization operator, metric-aware subspace tracking under a vanishing-ridge covariance metric, and a weighted-bootstrap ladle criterion for online structural dimension selection. Under standard regularity conditions, the online kernel estimator is root-$t$ consistent, the estimated generalized eigenspace consistently recovers the central subspace, and the proposed dimension selector consistently estimates the structural dimension. Simulation studies and real-data analyses demonstrate that the proposed method serves as a robust online alternative when the dominant data structure is unknown, adapting to both first-moment and second-moment-driven dependencies while yielding substantial computational savings relative to repeated batch directional regression.

Decision-focused learning (DFL) improves on the Predict-then-optimize (PtO) pipeline by training predictive models to minimize decision regret rather than prediction loss. Most DFL methods assume offline full-feedback data with complete action cost vectors. Many real-world decision systems instead operate in an online setting: in each round, the agent acts using past feedback and observes costs only for the selected components, yielding semi-bandit feedback. Bandit methods optimize regret in this regime, but train models with predictive updates rather than decision-focused updates. In this paper, we formalize online semi-bandit DFL: decision-focused learning for online optimization problems with semi-bandit feedback. The most straightforward extension would impute unobserved components with the model's own predictions and compute the decision-focused gradient. But this creates a self-confirming imputation degeneracy: imputation errors can flip counterfactual decisions that define the decision-focused gradient, biasing the representation update and reinforcing errors in later imputations. To address this degeneracy, we propose BayesianSPO, which combines an analytically updated Bayesian last-layer head with masked decision-focused learning. The Bayesian head supplies both (i) uncertainty to balance exploration and exploitation and (ii) stable imputations for unobserved components, while masking unobserved component gradients prevents those imputations from directly corrupting the representation update. Across knapsack, shortest-path, and portfolio benchmarks, BayesianSPO achieves the lowest mean cumulative regret on all five instances and the improvement is statistically significant on four of them.

With Large Language Model (LLM) pre-training and fine-tuning shifting its focus from data volume to data quality, quality data selection has emerged as a critical research topic. Existing online data selection methods for LLM training are typically ``batch-constrained'', limiting optimization to local utility within random batches. To overcome this, we propose GAIA (Global Adaptive Instruction tuning via GAussian processes), a framework that formulates data valuation as a global estimation process. GAIA employs Gaussian Process regression to model continuous utility manifolds across the semantic space, utilizing an adaptive strategy fusion mechanism to dynamically prioritize high-utility samples. By casting the strategy-posterior update as an instance of the classical fixed-share Hedge framework for tracking the best expert, we inherit a dynamic-regret guarantee that characterizes GAIA's robustness under non-stationary quality scores during training. Empirical evaluations on three datasets demonstrate that GAIA significantly outperforms state-of-the-art baselines like GREATS, establishing our method as a scalable and robust solution for efficient instruction tuning.

We consider a variant of the partially observed online control problem where there are _multiple sensors_ which provide noisy linear measurements of the system. In our setting, the system state evolves according to a discrete-time linear dynamical system. The objective is to design an algorithm which minimizes regret relative to the best _single-sensor_ policy (within a restricted class) in hindsight. When the system and process noise is stochastic and the costs are quadratic in the control and _unobserved state_, we design an algorithm that achieves $\mathcal{O}(\mathrm{poly}\log(S)\sqrt{n})$ regret over time horizon $n$ relative to our benchmark policy class if there are $S$ sensors. Notably, this regret guarantee is with respect to the _state costs_, which are never fully observed. When the system and process noise is chosen by an oblivious adversary, and the cost functions are convex-Lipschitz (or subquadratic) functions of the control and _observations_, then a similar $\mathcal{O}(\mathrm{poly}\log(S)\sqrt{n})$ regret is achievable. While our work is the first, to our knowledge, to study this generalization of the online control problem, we remark that a na\"ive application of known results in the partially observed online control literature have regret scaling $\mathcal{O}(\mathrm{poly}(S)\sqrt{n})$, exponentially worse than our regret scaling in terms of dependence on the number of sensors. Our algorithm is based on the Follow-The-Regularized-Leader framework, and our analysis carefully exploits the $\ell_1$ geometry of the policy class.

Brain–computer interfaces (BCIs) must continually adapt as neural signals drift, yet labeled calibration data is expensive to collect at time of use. Recent systems address this challenge by updating neural decoders using language-model–pseudo-labels, but they treat the pseudo-label as ground truth. We reinterpret recalibration as approximate Bayesian filtering: the decoder parameters are the latent states, and language models provide observations in the form of unnormalized potentials. Guided by this analysis, we introduce \textbf{B-CORP} (Bayesian Continual Online Recalibration with Pseudo-labels). B-CORP replaces hard pseudo-labels with a soft top-$K$ marginalization, increases the number of iterations in the coordinate ascent on the joint likelihood, and models parameter drift with a prior on latent dynamics. Across synthetic drifting regression tasks and real BCI benchmarks, including handwriting and speech BCI datasets, B-CORP attains word error rates consistently under 3\% on a difficult handwriting BCI dataset. B-CORP improves almost 30\% versus the state-of-the-art, while retaining performance even with poor pseudo-labels where naive methods fail. More broadly, our approach connects pseudo-label recalibration with online Bayesian inference, providing a principled foundation for problems requiring long-term recalibration with access to black box predictive models, such as LLMs, for use as strong priors over the labels.

While modern applications of large language models (LLMs) rarely rely on a single model, evaluation still collapses each model into a single benchmark score. This simplification obscures each model's specific weaknesses and how those weaknesses are shared or unique across models. To address this, this paper presents Online Weakness-Conditioned Evaluation (OWCE), an evaluation framework that diagnoses each model's recurring weaknesses, generates weakness-conditioned follow-up items at increasing difficulty, and cross-evaluates the resulting items on all models. Beyond a scalar score, OWCE produces per-model weakness profiles, enabling direct comparison of where models fail and which others recover those weaknesses. These profiles expose pairwise structure that scalar scores leave invisible. This paper finds that each model has a best-matched counterpart that reduces its failure rate by up to $25$ percentage points. This counterpart is determined by weakness profiles rather than overall benchmark ranking, indicating that the highest-scoring model is not always the most effective partner for a given target. This paper evaluates OWCE empirically across seven benchmarks and seven models, and conducts a mathematical analysis showing that the generated items can provide more discriminative information under benchmark saturation. Code is available at https://anonymous.4open.science/r/OWCE-57E7

In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning. This is an active sequential hypothesis testing problem in which the learner's objective is to identify an optimal policy in a Markov Decision Process (MDP) with high confidence, while minimizing the expected sample complexity to do so. We consider an online setting with deterministic rewards, where the agent must strategically navigate through the MDP in order to effectively explore. Previous works in the literature have provided asymptotically optimal methods for BPI, such as the Navigate and Stop (NaS) algorithm and its variants, however existing analysis remains asymptotic. In this work, we fill that gap by providing the first non-asymptotic sample complexity guarantees for NaS, showing that its sample complexity depends not only on the characteristic time, but also on the connectivity of the underlying MDP, the curvature of the optimal characteristic time, and other instance-dependent quantities. We identify these additional attributes and make explicit their contributions to the overall sample complexity.

Monocular online 3D instance segmentation enables embodied agents to build object-level 3D understanding while continuously exploring their environments. Unlike RGB-D settings, monocular RGB streams lack direct depth and camera pose information, making geometry reconstruction necessary for 3D segmentation. Recent reconstruction foundation models (RFMs) have made this task more feasible by recovering 3D geometry and cross-view cues from monocular images. However, reconstructed geometry remains noisy and incomplete, and streaming observations provide only partial views of object instances, making local observations insufficient for stable instance representations and temporally consistent segmentation. We propose MonoChunk3D, an online 3D instance segmentation framework that incrementally reconstructs, aligns, and segments incoming monocular RGB chunks. Rather than treating reconstructed geometry merely as input, the framework adaptively integrates complementary RFM-derived cross-view priors with 3D geometric features to initialize current-chunk instance queries. To overcome the limitations of local observations, we maintain compact persistent instance states composed of explicit prototypes, implicit query embeddings, and spatial bounds to preserve long-term instance context. These states are propagated as history-aware queries and jointly decoded with current-chunk queries, allowing the preserved instance context to directly guide current-chunk segmentation. The resulting predictions are associated with historical instances to update the persistent states, enabling temporally consistent segmentation over streaming observations. Experiments on ScanNet200, ScanNetV2, and SceneNN show that MonoChunk3D achieves consistent improvements over existing methods in the monocular online setting.

Many partially observed data streams are globally high-rank yet locally low-rank: user–item interactions in recommender systems span multiple preference groups, distinct operating regimes in sensor and network monitoring induce different low-dimensional structures, and the active latent subspace in adaptive systems shifts over time. We formalize this as online matrix completion on a drifting union of subspaces: each sample lies in one of K low-dimensional subspaces, only a random subset of its coordinates is observed, and the subspaces drift across epochs. We propose MoSAIC (MoE Subspace Adaptation via Incremental Completion), a method based on a routed mixture of low-rank experts trained in two phases. A base model is first pre-trained on samples from a fixed source distribution. It is then adapted on the non-stationary stream by routing each incoming sample to a single expert and updating only that expert. Our analysis identifies sufficient conditions under which the router remains correct with high probability throughout learning, while within each epoch the routed experts contract toward the current subspaces at a sublinear rate. The technical core is a uniform routing concentration argument that converts the random time steps on which each expert is updated into a deterministic time scale, reducing the per-expert analysis to a tractable stochastic recursion. Experiments on streams with repeated non-stationary changes corroborate the theory and show clear improvements over competitive baselines.

Model-based reinforcement learning (MBRL) promises high sample efficiency but is often crippled by compounding model errors: small prediction inaccuracies accumulate rapidly over multi-step rollouts, leading to biased policy optimization. We propose FTA, a trajectory-level generative framework using conditional flow matching (CFM) instead of step-wise dynamics. To avoid curved, energy-inefficient paths, we introduce an optimal transport regularizer grounded in the Benamou–Brenier formula. This regularizer minimizes kinetic energy while enforcing exact state displacement, yielding straight, low-energy trajectories with provable linear error propagation. Since a static generator fails in online RL due to (i) shifting data distributions and (ii) mismatch between training (historical) and desired (high-return) conditionals, we add periodic retraining from the replay buffer and a value-guided ODE sampler that biases generation toward high returns via the current Q-function. Theoretically, the regularizer drives the flow toward the Wasserstein-2 optimal transport map, and value-guided sampling reduces asymptotic Q-estimate bias. On MuJoCo benchmarks, FTA consistently outperforms strong MBRL and model-free baselines in sample efficiency and final performance, and generalizes across tasks. By mitigating compounding errors at the trajectory level and adapting to online shifts, FTA offers a robust, data-efficient alternative to traditional dynamics models.

Streaming decision trees are natural candidates for open-world continual learning, as they perform local updates, enjoy bounded memory, and static decision boundaries. Despite these, they still fail in online class-incremental learning due to two coupled miscalibrations: (i) their split criterion grows unreliable as the class count $K$ expands, and (ii) the absence of knowledge transfer at split time. Both failures share a common root: the range of Information Gain intrinsically scales with $\log_2 K$. Consequently, any Hoeffding-style confidence radius derived from it must inevitably grow with the class count, making a $K$-independent split criterion structurally impossible, taking away the potential benefits of applying streaming decision trees to continual learning. To fix this issue, we present \mist{} (McDiarmid Incremental Streaming Tree), which resolves both failures through three integrated components: (i) a tight, $K$-independent McDiarmid confidence radius for Gini splitting that acts as a structural regulariser; (ii) a Bayesian inheritance protocol that projects parent statistics to child nodes via truncated-Gaussian moments, with variance reduction guarantees strongest precisely when splitting is most conservative; and (iii) per-leaf KLL quantile sketches that support both continuous threshold evaluation and geometry-adaptive leaf prediction from a single data structure. On standard and stress-test tabular streams, \mist{} is competitive with global parametric methods on near-Gaussian benchmarks and uniquely robust on non-Gaussian geometry where SOTA benchmarks collapse.

We study online scheduling in a shared-resource system where tasks of different types arrive sequentially and compete for limited resources. Each task is modeled as an $H$-stage episodic Markov decision process, which captures the sequential resource-allocation decisions made within the task. At the system level, the learner must coordinate resource sharing across tasks to maximize the long-term ratio of cumulative reward to cumulative cost over $K$ tasks, without knowledge of the task distribution. The key challenges are coupled intra-task Markovian dynamics and inter-task ratio maximization, further complicated by unknown models and large or continuous state spaces. To address these challenges, we propose Contextual Optimistic Lyapunov Decomposition (COLD), a Lyapunov-driven optimistic learning algorithm. COLD converts the long-term ratio objective into a queue-adjusted per-task surrogate, thereby decoupling reward-cost optimization from statistical value estimation. It uses double-optimistic least-squares value iteration to estimate reward and cost values under linear function approximation, and a softmax policy to smooth the greedy update with only a controlled approximation error. We prove a regret bound of $\tilde{\mathcal{O}}(\sqrt{Md^3H^3T})$, where $M$ is the number of task types, $d$ is the feature dimension, $H$ is the episode horizon, and $T=KH$ is the number of interaction steps. The $\sqrt{T}$ dependence is order-optimal up to logarithmic factors, and the bound scales with the feature dimension rather than the size of the state space. Experiments on synthetic environments and an empirical KuaiRand-based MDP demonstrate the effectiveness of the proposed method.