ICML 2026 论文列表

Online conformal prediction (OCP) seeks prediction intervals that achieve long-run $1-\alpha$ coverage for arbitrary (possibly adversarial) data streams, while remaining as informative as possible. Existing OCP methods often require manual learning-rate tuning to work well, and may also require algorithm-specific analyses. Here, we develop a general regret-to-coverage theory for interval-valued OCP based on the $(1-\alpha)$-pinball loss. Our first contribution is to identify *linearized regret* as a key notion, showing that controlling it implies coverage bounds for any online algorithm. This relies on a black-box reduction that depends only on the Fenchel conjugate of an upper bound on the linearized regret. Building on this theory, we propose UP-OCP, a parameter-free method for OCP, via a reduction to a two-asset portfolio selection problem, leveraging universal portfolio algorithms. We show strong finite-time bounds on the miscoverage of UP-OCP, even for polynomially growing predictions. Extensive experiments support that UP-OCP delivers consistently better size/coverage trade-offs than prior online conformal baselines.

We study generalized linear bandits with memory, an endogenous non-stationary setting in which rewards depend on past actions through a finite memory matrix. Building on prior work for linear models Clerici et al.,(2024), we show that the previously known $\tilde{\mathcal{O}}(T^{3/4})$ regret bound stems from a loose analysis, and we provide a sharpened analysis that recovers a $\tilde{\mathcal{O}}(\sqrt{T})$ regret rate in the linear case. We then extend this improvement to generalized linear models and propose a block-wise algorithm based on shrunken confidence bounds. Our algorithm achieves a regret bound of $\tilde{\mathcal{O}}\left(\sqrt{mT} + d\sqrt{T} + \sqrt{\kappa}d^{2} m^{1/4} T^{1/4} + \kappa d^{2} \right)$, where $d$ denotes the feature dimension, $m$ the memory length, and $\kappa$ a curvature parameter of the link function. This attains a $\sqrt{T}$-type rate despite nonlinear rewards and memory effects. To the best of our knowledge, this analysis provides a unified treatment of memory-induced non-stationarity and nonlinear link functions, while ensuring that the leading regret term is independent of the curvature of the link function. We conduct numerical experiments that are consistent with our theoretical findings.

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic $Q$-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.

We study an algorithm-independent, worst-case lower bound for the Gaussian process (GP) bandit problem in the frequentist setting, where the reward function is fixed and has a bounded norm in the known reproducing kernel Hilbert space (RKHS). Specifically, we focus on the squared exponential (SE) kernel, one of the most widely used kernel functions in GP bandits. One of the remaining open questions for this problem is the gap in the *dimension-dependent* logarithmic factors between upper and lower bounds. This paper partially resolves this open question under a hyperspherical input domain. We show that any algorithm suffers $\Omega(\sqrt{T (\ln T)^{d} (\ln \ln T)^{-d}})$ cumulative regret, where $T$ and $d$ represent the total number of steps and the dimension of the hyperspherical domain, respectively. Regarding the simple regret, we show that any algorithm requires $\Omega(\epsilon^{-2}(\ln \frac{1}{\epsilon})^d (\ln \ln \frac{1}{\epsilon})^{-d})$ time steps to find an $\epsilon$-optimal point. We also provide the improved $O((\ln T)^{d+1}(\ln \ln T)^{-d})$ upper bound on the maximum information gain for the SE kernel. Our results guarantee the optimality of the existing best algorithm up to *dimension-independent* logarithmic factors under a hyperspherical input domain.

Users increasingly face the challenge of selecting an appropriate LLM for a given task from a rapidly growing pool of LLMs, each with distinct but often opaque latent properties. Compounding this challenge, users may lack the vocabulary or awareness to explicitly articulate the characteristics they value in an LLM's responses or deployment. We propose an interaction-efficient active learning framework in which a dueling bandit algorithm iteratively selects pairs of LLMs, collects user feedback about their responses, and updates its belief about the user's latent preferences. We introduce a novel belief-aware upper confidence bound strategy that balances exploration of the model pool with exploitation of inferred preferences, enabling efficient alignment between user needs and LLM capabilities under user-specified cost and time budgets. Through diverse experiments on LLMs and human studies, we experimentally verify that our model can efficiently match users to LLMs at a lower cost.

We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{A}$ grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called "Level-Constrained-Littlestone-Littlestone (LCLL) tree", which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.

Rubrics provide a flexible way to train LLMs on open-ended long-form answers where verifiable rewards are not applicable and human preferences provide coarse signals. Prior work shows that reinforcement learning with rubric-based rewards leads to consistent gains in LLM post-training. Most existing approaches rely on rubrics that remain static over the course of training. Such static rubrics, however, are vulnerable to reward-hacking type behaviors and fail to capture emergent desiderata that arise during training. We introduce Online Rubrics Elicitation (OnlineRubrics), a method that dynamically curates evaluation criteria in an online manner through pairwise comparisons of responses from current and reference policies. This online process enables continuous identification and mitigation of errors as training proceeds. Empirically, this approach yields consistent improvements of up to 8% over training exclusively with static rubrics across AlpacaEval, GPQA, ArenaHard as well as the validation sets of expert questions and rubrics. We qualitatively analyze the elicited criteria and identify prominent themes such as transparency, practicality, organization, and reasoning.

We study a simple yet principled modification of classical Q-learning that clips the value estimate in the Bellman backup by a threshold $\lambda$. The resulting algorithm, clipped Q-learning, is motivated by a key theoretical insight: the clipped Bellman backup is an unbiased one-sample estimation of a robust Bellman operator arising naturally from a transition-regularized MDP framework. This formulation corresponds to optimizing performance against a specific class of adversarial dynamics perturbations at the test time that reallocate transition probability mass away from high-value states, thereby inducing conservative but stable decision making. Under this interpretation, clipped Q-learning can be viewed as tracking the fixed point of the robust Bellman equation and learning policies that hedge against adversarial dynamics shifts at test time. We analyze two clipped Q-learning variants with an optimistic exploration bonus and establish polynomial regret guarantees, demonstrating statistical efficiency. Beyond the tabular setting, our framework suggests that value clipping is a modular mechanism that can be incorporated into general value-based RL algorithms with function approximation. As a proof of concept, we evaluate a clipped Double DQN algorithm on a control task and observe robustness improvements consistent with our theoretical predictions.

Large-scale learning systems often face the challenge of balancing multiple, potentially competing objectives, such as fairness, accuracy, and latency. While recent work has formalized this as an optimization problem over binary states, many real-world control parameters---such as fairness thresholds, diversity mixing rates, or resource budgets---are continuous. In this work, we extend the framework to *continuous state spaces*. We model the problem as minimizing a sum of linear objectives subject to *movement costs* that penalize system instability. We capture the local structure of the objectives using a *dependency graph* (or factor graph), where each objective is determined by a subset of the state attributes. To address the tension between exploration and stability, we propose *Lazy Graph-LinUCB*, an algorithm that performs lazy updates to minimize switching costs while maintaining near-optimal regret. Beyond stability, we introduce three advanced mechanisms to exploit the underlying graph structure: (1) an *asynchronous* update schedule that eliminates synchronization overhead in sparse graphs; (2) an *adaptive* algorithm that learns the graph structure from data; and (3) a *joint estimator* that leverages data sharing among correlated objectives to significantly tighten regret bounds. Empirically, we demonstrate that these structural exploitations reduce movement costs by more than a factor of three in heterogeneous systems while maintaining similar cumulative losses.

Online evaluation of large language models increasingly relies on sequentially collected pairwise preferences, enabling human-aligned assessment and continuous data collection until closely performing models can be reliably distinguished. However, adaptive sampling and continuous monitoring invalidate classical fixed-sample inference, rendering existing ranking procedures largely heuristic. We propose SERPANT (Sequential E-value Ranking and Pruning via Adaptive Null Testing), a principled framework for online LLM ranking with anytime-valid guarantees. SERPANT formulates model comparison as a collection of pairwise hypothesis tests and constructs e-processes to ensure family-wise error rate control at any monitoring time. Anytime validity provides a theoretical justification for early stopping, enabling substantial cost savings from expensive human annotation. To improve efficiency, we introduce a novel tournament-based sampling strategy that adaptively selects comparisons based on past outcomes. The proposed framework is also extended to top-k model identification.

We consider a linear contextual bandit model where contexts and rewards are governed by a finite hidden Markov chain. We first revisit the simplified model by Nelson et al. (2022), in which rewards are linear functions of the posterior probabilities over the hidden states given the observed contexts (called beliefs), rather than functions of the hidden states themselves. This simplified model may be handled through a direct reduction to standard linear contextual bandits. We extend the theoretical analysis of this reduction to take into account the estimation of the parameters of the hidden Markov model [HMM] in the regret bound and to provide high-probability bounds not depending anymore on the reward functions and only depending on the model through the estimation of the HMM parameters. Second, and most importantly, we instead study the more natural and more complex model incorporating direct dependencies in the hidden states (on top of dependencies on the observed contexts, as is natural for contextual bandits). Under a classic HMM forgetting condition, the main algorithmic tool introduced to cope with the various statistical dependencies that the reward structure introduces is to only periodically update reward-model parameters.

We propose an anytime online algorithm for learning a sequence of convex cost functions while approximately satisfying a sequence of convex constraints, without prior knowledge of the time horizon. Both the cost and constraint functions may be chosen adversarially over time. While this problem has recently been resolved in the setting where the time horizon is known, extending these guarantees to the anytime setting, without resorting to inefficient doubling tricks, has remained technically challenging. Our main contribution is the introduction of a time-varying yet horizon-oblivious Lyapunov function to track constraint violations. The use of such a time-varying Lyapunov function introduces new technical difficulties, as a key monotonicity property underlying prior analyses no longer holds. By developing a novel analytical technique, we show that our algorithm achieves $O(\sqrt{t})$ regret and $\tilde{O}(\sqrt{t})$ cumulative constraint violation (CCV) for all $t \geq 1$. We further extend our framework to the dynamic regret setting, obtaining bounds that adapt to the unknown path length of the comparator sequence. Finally, we present an adaptive algorithm for the optimistic setting, whose performance scales gracefully with the cumulative prediction error. We validate the practical effectiveness of our approach through numerical experiments on the online shortest path problem.

Two-sided matching markets are pervasive in numerous real-world applications, ranging from labor markets to online advertising. A rich line of research has studied the matching bandit problem, where participants learn their preferences through iterative interactions. However, existing works assume a static environment with fixed participants and require synchronized learning, in which all participants start simultaneously and have access to a global clock. In reality, matching markets are inherently dynamic: participants may enter and leave at arbitrary time steps without any global signal, creating coordination challenges. To study the dynamic setting, we first investigate one-sided learning under uncoordinated player arrivals, where only the players need to learn their preferences. We propose the Way-SE algorithm, which achieves a regret of $O(\frac{K^2 \log T}{\Delta_{\min}^2})$, where $K$ is the number of arms, $T$ is the time horizon, and $\Delta_{min}$ is the minimum utility gap. This is done through a distributed exploration mechanism that coordinates exploration implicitly via just local clocks. More importantly, we extend our work to fully decentralized dynamic two-sided learning, where both sides need to learn their preferences, and players arrive or depart arbitrarily. We introduce Way-SE-2S, the first algorithm to achieve sublinear regret $O\left(\frac{K T^{1-1/K}(\log T)^{2/K}}{\Delta_{\min}^2}\right)$ in this challenging environment, without requiring global signals, restrictive preference structures, or observability of the results of competing agents. Our work provides the first theoretical guarantee for stable matching in fully decentralized and uncoordinated bandit markets.

In this paper, we study the rent-or-buy problem (also called the Bahncard problem) in the learning-augmented setting. In this problem, a traveler must complete a sequence of trips that are revealed online over time, each of which has an associated cost with it. The traveler has the option of buying a discount card at a fixed cost that gives a discount on trip costs for a fixed time after buying the card. The goal is to minimize the overall cost of all the trips, including the money spent on buying discount cards. For this problem, it is well-known that the best deterministic algorithm has a competitive ratio of 2. In this paper, we ask whether we can do better if the traveler has a *sample* of trips available offline, e.g., obtained from an ML model based on historical data. We show that even a sparse sample of the input can significantly improve the competitive ratio of the algorithm from 2 to 3/2, and further to close to 1 under some additional conditions. We also verify our theoretical bounds via numerical simulations, which reveal that our proposed algorithm obtains nearly optimal solutions for a variety of natural input classes.

We study the Awakening Crowd of Experts (ACE) problem, an online learning problem where the set of experts available to the learner grows at each round. ACE is a special case of the well-known sleeping experts problem (Kleinberg et al., 2010), where the number of experts is huge $(K=T)$. Existing results on sleeping experts preclude any learner from achieving a sublinear regret when the number of available experts is linear in $T$. Inspired by real-world applications, such as Q\&A platforms and social proof marketing, we thus focus on the awakening version of the sleeping experts problem, where a new expert arrives at every round and never leaves. We show that in the stochastic version of ACE, it is possible to obtain regret $\tilde{\mathcal{O}}(T^{2/3})$ using an unusual pessimism in the face of the uncertainty principle. Moreover, we characterize the dependence of the regret on the stability of an optimal strategy. For both results, we present matching lower bounds. Surprisingly, the adversarial version of ACE is sensibly harder. In particular, we provide a lower bound precluding sublinear $\alpha$-regret when the competitive ratio is constant. We provide an algorithm to face this crucial trade-off between competitive ratio and regret, and bound its $\alpha$-regret, almost matching the aforementioned lower bound. As a corollary, we get a $\tilde{\mathcal{O}}(\log(\log(T))$ competitive ratio when an optimal strategy enjoys a reward linear in $T$.

We investigate the contextual slate bandit problem with generalized linear rewards under limited adaptivity. At each round, the learner is presented with $N$ sets of items, where each item is represented by a $d$-dimensional feature vector. The learner then constructs a slate by selecting one item per set; the resulting slate yields a scalar reward sampled from a Generalized Linear Model (GLM). We propose algorithms under two limited-adaptivity settings: (a) Batched and (b) Rarely-Switching. For the batched setting, we introduce B-SlateGLinCB, which partitions the time horizon into $\mathcal{O}(\log\log T)$ batches such that each batch's policy relies only on data from previous batches. For the rarely-switching setting, we propose RS-SlateGLinCB, which adaptively performs only $\mathcal{O}(Nd\log T)$ parameter updates. Under a diversity assumption on the item sequences, we prove that B-SlateGLinCB and RS-SlateGLinCB achieve regret bounds of $\mathcal{O}(Nd^{3/2}\sqrt{T})$ and $\mathcal{O}(Nd\sqrt{T})$, respectively. Notably, both bounds are independent of the non-linearity parameter $\kappa$ that is typically found to scale the regret of GLM bandit algorithms. Our algorithms are computationally efficient, requiring only $\text{poly}(N)$ time per round despite $2^{\Omega(N)}$ possible slates. Simulations show our algorithms outperform existing baselines with limited adaptivity and remain competitive with Slate-GLM-OFU, a fully adaptive state-of-the-art algorithm. Notably, a slightly modified B-SlateGLinCB empirically matches this baseline. Finally, we demonstrate strong performance in a practical in-context example selection task for language models.

Online model editing for multimodal large language models (MLLMs) requires assimilating a stream of corrections under tight compute and memory budgets. Yet editors developed for text-only LLMs often degrade on MLLMs: visually dominant activations skew the statistics that shape updates, causing *cross-modal conflict*, while sequential writes become entangled in a shared edit space and amplify long-horizon interference, causing *inter-edit interference*. To address these, we propose **M-ORE**, a modality-decoupled online recursive editor for lifelong MLLM adaptation. M-ORE is derived from a unified proximal-projection formulation and admits a closed-form update with a Sherman-Morrison recursion, yielding constant per-edit overhead. It maintains module-wise locality statistics for the text stack and the visual projector to avoid visually dominated update shaping and performs continual updates in a fixed orthogonal low-rank edit subspace via a Sherman-Morrison recursion to mitigate long-horizon interference. Experiments on multiple MLLM backbones and online editing benchmarks show that our M-ORE method consistently improves reliability, generality, and locality over strong baselines, while achieving favorable quality-efficiency scaling. Our code is publicly available at https://github.com/lab-klc/M-ORE.

We study the online fair division problem, where indivisible goods arrive sequentially and must be allocated immediately and irrevocably. Prior work establishes strong impossibility results for approximating classic notions such as envy-freeness up to one good (EF1) and maximin share (MMS) in this setting, but the approximability of proportionality up to one good (PROP1) has remained unresolved. We resolve this gap in two steps. First, we show that three natural greedy allocation rules (standard baselines in fair division) fail to guarantee any multiplicative approximation to PROP1 against an adaptive adversary. These limitations motivate two relaxations: (i) restricting attention to a non-adaptive adversary, and (ii) incorporating coarse predictions in the spirit of learning-augmented algorithms. Under a non-adaptive adversary, we show that the uniform random allocation achieves a meaningful PROP1 approximation with high probability, and this guarantee is essentially tight for this approach; moreover, when item values are sufficiently small, the allocation is near-PROP1 with high probability. Finally, given maximum item value (MIV) predictions, we design an online algorithm that achieves robust approximation guarantees for PROP1, and degrades gracefully under one-sided prediction error. In contrast, we show that EF1, MMS, and PROPX remain inapproximable even with perfect MIV predictions.

The ski rental problem is a canonical model for online decision-making under uncertainty, capturing the fundamental trade-off between repeated rental costs and a one-time purchase. While classical algorithms focus on worst-case competitive ratios and recent ``learning-augmented'' methods leverage point-estimate predictions, neither approach fully exploits the richness of full distributional predictions while maintaining rigorous robustness guarantees. We address this gap by introducing algorithms that systematically integrate distributional predictions into both deterministic and randomized algorithms. For the deterministic setting, we formalize the problem under perfect distributional prediction and derive an efficient algorithm to compute the optimal threshold-buy day. We provide a rigorous performance analysis, identifying sufficient conditions on the predicted distribution under which the expected competitive ratio (ECR) matches the classic optimal randomized bound. To handle imperfect predictions, we propose the Clamp Policy, which restricts the buying threshold to a safe range controlled by a tunable parameter. We show that this policy is both robust, maintaining good performance even with large prediction errors, and consistent, approaching the optimal performance as predictions become accurate. For the randomized setting, we characterize the stopping distribution via a Water-Filling Algorithm, which optimizes expected cost while strictly satisfying robustness constraints. Experimental results across diverse distributions (Gaussian, geometric, and bi-modal) demonstrate that our framework improves consistency by significantly over existing point-prediction baselines while maintaining comparable robustness.