NeurIPS 2026 Papers

Online robust zero-sum Markov games pose a coupled operator-learning and game-solving problem: from nominal interaction data, the learner must recover a worst-case minimax Bellman operator while maintaining strategic coverage and controlling stage-game approximation error. Existing robust reinforcement-learning theory does not yet provide such an operator-learning perspective beyond specialized multi-agent settings. We develop an optimistic dual robust Bellman framework that combines dual robust Bellman fitting, optimistic minimax planning, backward-validated confidence sets, and exploiter-mix data collection. Our analysis is organized around the robust Bellman residuals induced by the candidate value class and yields a regret reduction that separates exploration complexity, robust operator-estimation error, stage-game solution error, and misspecification. Under explicit interpretable assumptions, we obtain conditional theorem interfaces for general and projected function approximation, together with closed results in several structured regimes, including tabular, epochwise/cross-fit linear, self-normalized pure-online linear / finite-rank kernel, and projected RKHS truncation. We also provide numerical experiments that validate the theoretical predictions.

Pruning has emerged as a promising direction for accelerating large language model (LLM) inference. However, many existing methods rely on offline calibration data, making them sensitive to distribution shifts between calibration data and inference inputs. In this paper, we introduce Token Filtering, a lightweight online pruning method that selectively skips attention computation for redundant tokens during inference, without requiring any calibration data or fine-tuning. Token Filtering identifies redundant tokens based on joint key–value (KV) similarity and bypasses their attention computation. This approach reduces both compute and KV cache size while preserving essential contextual information. To preserve accuracy while meeting the target pruning ratio, we restrict pruning to later layers, which are typically less sensitive to pruning, with a layer-wise threshold that adaptively tracks the target pruning ratio. Extensive experiments on LLaMA3.1-8B, LLaMA3.1-8B-Instruct, and Qwen3-8B demonstrate that Token Filtering consistently achieves better accuracy–efficiency trade-offs than prior methods. In long-context generation, Token Filtering achieves up to 1.5X higher accuracy than the best-performing pruning baseline while reducing latency by up to 44% compared to the dense baseline.

In this paper, we introduce a semi-random model in online optimization, which interpolates naturally between the standard (adversarial) and random-order arrival model, which we call the online with a random sample (ORS) model: the full input may be chosen adversarially, but a random $p$-fraction of the input is selected and presented to the algorithm in random-order, before the remaining non-sampled elements are presented (in adversarial order). While similar in spirit to the AOS (adversarial order with a sample) model introduced by Kaplan, Naori and Raz, in our ORS model, the sampled $p$-fraction is revealed online instead of offline, and hence, competitiveness is measured with respect to the full input. Our central focus in the paper is applying the ORS model to the secretary problem and its natural $(k,1)$ variant. For the secretary problem, we present an optimal $pe^{-p}$-competitive algorithm, while for the $(k,1)$-secretary problem, we obtain a competitive algorithm whose performance converges to optimal competitiveness as $p\rightarrow 1$. We also include a $O(\log (1/p))$-competitive algorithm for facility location.

Kotłowski et al. (NeurIPS 2017) posed as a central open problem the design of efficient online isotonic regression algorithms beyond totally ordered domains. We resolve this for the product order $[m]\times[m]$, the canonical two-dimensional case, by determining the minimax regret up to constant factors: $$ R_T^* = \Theta\left(\min\left\\{T,\ \inf_{K \in \mathbb{N}_+}\left[\log\Omega([m]^2, K+1) + \frac{T}{K^2}\right]\right\\}\right), $$ where $\Omega(\mathcal{P}, K+1)$ is the order polynomial counting monotone maps from $\mathcal{P}$ to $[K+1]$. This unified formula reveals a three-phase scaling law: $\Theta(T)$ for $T \lesssim m$, $\Theta(m^{2/3} T^{1/3})$ for $m \lesssim T \lesssim m^4$, and $\Theta(m^2 \log(T/m^4))$ for $T \gg m^4$. We further construct polynomial-time algorithms achieving this rate in every regime, including a horizon-free variant requiring no advance knowledge of $T$.

Data-parallel (DP) load balancing has emerged as a first-order bottleneck in large-scale LLM serving. When a model is sharded across devices via tensor parallelism (TP) or expert parallelism (EP) and replicated across many DP workers, every decode step ends in a synchronization barrier whose latency is set by the most heavily loaded worker; even modest persistent imbalance across DP workers compounds, step after step, into a substantial fraction of wasted compute. The problem is hard for reasons specific to LLM decoding: assignments are sticky (KV caches cannot be migrated), per-request loads grow over time, arrivals are non-stationary, and the router must decide within a sub-100ms decode budget over hundreds of waiting requests and tens of workers. We present BalanceRoute, a family of practical online routing algorithms that target this bottleneck. The first, BR-0, requires no prediction infrastructure and uses a piecewise-linear F-score that captures the sharp asymmetry between admissions that fill safe margin and those that overflow into the envelope; a two-stage decomposition keeps per-step cost compatible with millisecond-scale scheduling. The second, BR-H, generalizes BR-0 with a short, constant lookahead $H$ and a lightweight termination-classifier interface, extending the F-score to a horizon-discounted form. We deploy BalanceRoute on a 144-NPU cluster and evaluate against vLLM baselines on both a proprietary production trace and the public Azure-2024 trace. Across both workloads, BalanceRoute substantially reduces average DP imbalance and improves end-to-end serving throughput. An anonymized open-source release is available at https://anonymous.4open.science/r/BR-Family-on-vllm-acend-0F95/.

We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner's performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, for any interval $[a,b] \subseteq [T]$, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\\|g_t\\|^2+\lambda_t\\|g_t\\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $\lambda_t$ is the movement-cost coefficient at round $t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.

We consider the scheduling problem of online speed scaling where the goal is to minimize the energy consumption of a machine that controls the speed at which jobs are processed. Recent work has leveraged the learning-augmented framework, where the algorithm is provided with predictions about jobs that will arrive in the future, to manage power usage more efficiently. This paper proposes a novel prediction model for speed scaling where the predictions are about the machine speed (the output), instead of the jobs (the input). Machine speed predictions have multiple advantages: they are succinct, admit strong PAC-learnability guarantees, can be provided dynamically, and lead to a natural definition of smoothness. We give an algorithm for dynamic machine speed predictions that is $(1+\epsilon)$-consistent and $O(1)$-robust. For offline machine speed predictions and job speed predictions, we provide an algorithm that achieves the stronger guarantee of $(1+\epsilon)$-smoothness, while maintaining $O(1)$-robustness. These guarantees are comparable to previous work, but do not require predicting the entire input.

Online safe reinforcement learning (RL) seeks policies that maximize reward while satisfying safety constraints. A popular line of research in safe RL relaxes safety to a soft expected-cost constraint and solves the resulting Constrained Markov Decision Process (CMDP) via primal-dual Lagrangian updates that only enforce safety on average. To address this limitation, hard, state-wise constraints are introduced and often imposed through Hamilton-Jacobi (HJ) reachability. Yet such constraints require solving different objectives in the feasible and infeasible regions of the state space: reward maximization in the former, recovery toward the feasible regions in the latter. The resulting target action distributions are inherently multimodal, and this structure poses a fundamental challenge for the Gaussian or deterministic actors used in existing HJ-based safe RL, which often collapse onto suboptimal modes. Diffusion policies provide the expressiveness needed to represent such distributions, and recent work on Q-score matching offers a route to training them for online RL by score regression---but has been applied only to reward maximization. Building on this framework, we propose Safe Score Matching (SSM), an off-policy actor-critic method that adapts Q-score matching to hard-constrained safe RL by gating a two-branch score target with HJ reachability: inside the feasible set, the denoising process degenerates to Q-score matching on actions classified as viable by the HJ critic, encouraging reward maximization; outside, a recovery branch biases denoising toward regions with lower worst-case violation, guided by the negative action gradient of the HJ safety value. Across high-dimensional quadrotor and fixed-wing trajectory-tracking and stabilize-and-avoid benchmarks, SSM achieves competitive performance without sacrificing safety, in contrast to primal-dual and reachability-based baselines, which tend to trade off performance for safety and are thus overly conservative.

Online POMDP planners optimize the expected cumulative cost, which can mask dangerous states when the belief places significant mass on high-cost states. Existing risk-averse methods apply static or dynamic Conditional Value at Risk (CVaR) to the value function, capturing trajectory-level risk, but share two gaps: (i) by retaining the immediate cost as an expectation of a state-dependent cost over the belief, the risk \emph{within} the belief is left unaddressed; and (ii) by modifying the value function, they require new tailored algorithms rather than reusing existing expectation-based planners. We instead apply CVaR to the immediate cost over the belief at each step, directly targeting per-step uncertainty about the current state. The standard expected cumulative return is retained as the objective, so the resulting problem has a standard MDP structure: any expectation-based POMDP planner can be made risk-sensitive by changing only the cost computation. We inherit finite-time guarantees for policy evaluation and sparse sampling---with estimation error independent of the risk level---and, as our central theoretical result, prove a finite-time bound on the gap between the particle belief MDP surrogate and the original POMDP, which together yield an end-to-end guarantee from the true POMDP value to the algorithmic estimate. In the risk-neutral limit, the formulation recovers standard expectation-based planning.

Algorithmic *replicability* has recently been introduced to address the need for reproducible experiments in machine learning. A *replicable online learning* algorithm is one that takes the same sequence of decisions across different executions in the same environment, with high probability. We initiate the study of algorithmic replicability in *constrained* MAB problems, where a learner interacts with an unknown stochastic environment for $T$ rounds, seeking to maximize reward while satisfying multiple constraints. Our main result is that replicability can be achieved in constrained MABs. Specifically, we design replicable algorithms whose regret and constraint violation match those of non-replicable ones in terms of $T$. As a key step, we develop the first replicable UCB-like algorithm for *unconstrained* MABs, showing that algorithms that employ the optimism in-the-face-of-uncertainty principle can be replicable, a result that we believe is of independent interest.

Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle. While such agnostic learners achieve near-optimal expected regret, they suffer from a doubly-exponential oracle complexity of $\mathcal{O}\big(T^{2^{\mathcal{O}(d_\mathrm{LD})}}\big)$, where $d_\mathrm{LD}$ is the Littlestone dimension and $T$ is the number of rounds. In this work, we significantly improve this oracle complexity while relying on an even weaker primitive: a weak-consistency oracle, which merely decides whether a given labeled dataset is realizable. At the core of our approach is an adaptive and dynamic agnostic-to-realizable reduction that actively prunes non-realizable label sequences on the fly. By using the VC dimension ($d_\mathrm{VC}$) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to $\mathcal{O}(T^{d_\mathrm{VC}+1})$ while perfectly preserving near-optimal expected regret. Crucially, this dynamic pruning also yields a memory reduction over the standard reduction. Furthermore, we formally quantify the regret--oracle complexity tradeoff, providing upper bounds that smoothly interpolate between restricted query budgets and attainable expected regret. We complement these with lower bounds proving that any learner restricted to $Q = o(\sqrt{T})$ queries must suffer an expected regret of $\Omega(T/Q)$.

Online reinforcement learning (RL) has achieved significant success in decision-making tasks, but modern online RL remains highly sensitive to the quality of training experience. Understanding the role of training data in online RL is challenging because the training distribution evolves together with the policy, causing the influence of the training data to propagate across future optimization and future data collection. Existing data-attribution methods for online RL primarily focus on local influence within a single training round, overlooking the non-local data influence across multiple training rounds. In this work, we formalize data attribution in online RL through a trajectory-level leave-one-out quantity, RL-LOO, which measures how one training sample influences a downstream target after subsequent online updates have taken place. We then derive RL-Inf, a first-order estimator that propagates data influence through both optimization effects and policy-induced sampling effects, and provide theoretical guarantees on its approximation accuracy under smoothness assumptions. Our analysis further disentangles these two effects and shows both theoretically and empirically that the full RL-Inf estimator can often be well approximated using the optimization effect alone. Building on this observation, we develop RINSE, a practical data filtering method for online RL. Experiments on standard control benchmarks and an RLHF-style toxicity-mitigation setting show that RINSE improves training efficiency and final performance over standard PPO and local attribution baselines. These results suggest that RL-Inf provides a practical and principled framework for understanding and improving online RL.

We consider the problem of *regularized* best-response max-regret minimization in online RLHF under general preferences and bandit feedback. While various regularizers are utilized to robustify alignment, known polylogarithmic regret guarantees remain heavily specific to KL. To investigate whether such fast rates extend beyond KL, we adopt the *Generalized Bilinear Preference Model (GBPM)*—capturing intransitive preferences over $d$-dimensional item-wise features via a rank-$2r$ skew-symmetric matrix—to isolate the impact of generic regularization. Crucially, under GBPM, we prove that the dual gap of any greedy policy is bounded by the *squared* estimation error, derived using *only* strong convexity and skew-symmetry. Under a feature coverage assumption, we establish polylogarithmic $\tilde{\mathcal{O}}(\eta d^4 (\log T)^2 \wedge d^2 \sqrt{T})$ regret with Greedy Sampling and $\mathrm{poly}(d)$-free $\tilde{\mathcal{O}}(\sqrt{\eta r T} \wedge r^{1/3} T^{2/3})$ regret with Explore-Then-Commit, where $\eta^{-1}$ is the regularization coefficient and $T$ is the time horizon. This demonstrates that ``fast'' regrets are *not* KL-specific, but rather a fundamental consequence of generic strongly convex geometry.

We develop a quantitative statistical theory of transformers in the large-context regime by adopting the abstraction of contextual flow maps: dynamical systems that evolve a distinguished token in the presence of a contextual measure across a stack of attention blocks. Within this framework, the finite-context model approximates an idealized infinite-context system in which the contextual measure is replaced by its underlying population, so that the context length $n$ becomes a statistical resource. Exploiting the McKean--Vlasov structure of the dynamics and the classical machinery of propagation of chaos, we establish a forward bound controlling the deviation between the finite- and infinite-context flow maps uniformly along depth, and a backward bound controlling the deviation between the corresponding training trajectories uniformly across iterations of online gradient descent. Both bounds achieve the optimal Wasserstein rate $n^{-1/d}$. The analysis rests on a new Eulerian adjoint formulation of the loss gradient and stability estimates for the resulting forward--adjoint system, both of which may be of independent interest. We further verify that the standard transformer architecture satisfies these estimates with Lipschitz constants independent of embedding and parameter dimensions, suggesting a structural reason why transformers train stably across model scales.

Learning in POMDPs is known to be significantly harder than in MDPs. In this paper, we consider the online learning problem for episodic POMDPs with unknown transition and observation models. We propose a Posterior Sampling-based reinforcement learning algorithm for POMDPs (PS4POMDP), which is much simpler and more implementable compared to state-of-the-art optimism-based online learning algorithms for POMDPs. We show that the Bayesian regret of the proposed algorithm scales as the square root of the number of episodes and is polynomial in the other parameters. In a general setting, the regret scales exponentially in the horizon length $H$, and we show that this is inevitable by providing a lower bound. However, when the POMDP is undercomplete and weakly revealing (a common assumption in the recent literature), we establish a polynomial Bayesian regret bound. We finally propose a posterior sampling algorithm for multi-agent POMDPs, and show it too has sublinear regret.

Reinforcement learning (RL) is well known to be data-intensive, and recent works have proposed leveraging data from similar systems to improve sample efficiency. In this work, we focus on the collaborative Linear Quadratic Regulator (LQR) setting and study the problem of learning under heterogeneous system dynamics. Due to the presence of a heterogeneity-induced additive bias, most existing collaborative methods are suitable only for low heterogeneity regimes and exhibit suboptimal performance under large heterogeneity. Based on the principle of Thompson sampling (TS), we propose an algorithm that, by leveraging data from other agents, yields a \emph{personalized} controller for every agent without incurring any additive heterogeneity-induced bias, i.e., with sublinear Bayes regret even under large heterogeneity. Under high heterogeneity regimes, we establish that our algorithm incurs $\tilde{\mathcal{O}}( T^{1-0.5\epsilon}\sqrt{\Delta})$ cumulative regret, where $T$ denotes the time horizon, $\epsilon\in[0,1]$ is a user-defined personalization parameter, and $\Delta$ denotes an upper bound on the maximum dissimilarity among the agents' dynamics. Our algorithm and analysis also generalize the special case of no heterogeneity. In particular, under no heterogeneity, we establish that our algorithm incurs $\mathcal{O}(\sqrt{T/M})$ cumulative regret. From a distributed implementation perspective, our method incurs only logarithmic communication overhead. Additionally, our algorithm outperforms methods that do not personalize data from other agents and, in certain regimes, also outperforms methods that do not utilize any data from other agents.

We study online alignment of large language models under misspecified preference feedback, where the observed preference oracle deviates from an ideal but unknown ground-truth oracle. The online LLM alignment problem is a bi-level reinforcement problem due to the coupling between data collection and policy updates. Recently, the problem has been reduced to a tractable single-level objective in the SAIL (Self-Improving Efficient Online Alignment) framework. In this paper, we introduce a pointwise oracle uncertainty set in this problem and formulate an oracle-robust online alignment objective as a worst-case optimization problem. For log-linear policies, we show that this robust objective admits an exact closed-form decomposition into the original loss function plus an explicit sensitivity penalty. We develop projected stochastic composite updates for the resulting weakly convex objective and prove $\widetilde{O}(\varepsilon^{-2})$ oracle complexity for reaching approximate stationarity.

We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary ``hint'' sequence of forecasts, the learner must output new predictions that are calibrated while incurring small excess error relative to the original forecasts, under a proper loss. We give an online algorithm that achieves $(\varepsilon, \varepsilon^2)$-recalibration for Lipschitz proper losses in $T \approx \varepsilon^{-3}$ rounds, using an imbalanced extension of the recent simultaneous Blackwell approachability reduction framework of [HTY26]. We also show this tradeoff is optimal by proving a matching lower bound for recalibrating against the squared loss. As an application, we show how our recalibration algorithm can be combined with the online refinement method of [FH23] to obtain simultaneous $\varepsilon$-calibration and $\varepsilon^2$-calibeating for smooth proper losses at the same asymptotic rate, improving upon prior works that achieved these properties separately or with a worse $\varepsilon$ dependence. We also discuss extensions to settings with multiple hint sequences.

We consider the problem of learning an unknown subset $N^{target}$ of a domain in an online setting. % In each round $t$, the learner predicts a set of items ${N}_t$ and receives one of two types of feedback, each with equal probability: {\it precision feedback}, in which a randomly chosen item from the predicted set $N_t$ is revealed and the learner is told whether it belongs to $N^{target}$ (incurring a reward if it does), or {\it recall feedback}, in which a randomly chosen item from the target set $N^{target}$ is revealed and the learner is told whether it belongs to $N_t$ (incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision and recall--type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning---where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM)---our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.