论文检索

General Machine Learning · Online Learning, Active Learning and Bandits

Pascal Janetzky, Dr. Tobias Schlagenhauf, Stefan Feuerriegel

Continual learning (CL) aims to train models sequentially over multiple domains without forgetting previously learned knowledge. However, existing CL methods optimize for in-domain performance and are therefore prone to learning spurious, domain-specific cues (``shortcut learning''), which limits generalization to unseen domains after deployment. In this paper, we address this limitation through *continual learning of domain-invariant representation*. We introduce a broad class of CL methods that sequentially learn representations capturing invariant structures across domains. Our methods are motivated by the observation that such invariant structures often preserve the underlying causal mechanisms, which can reduce the risk of overfitting to domain-specific cues and thus offer better out-of-domain generalization. Our proposed CL methods combine replay-based training with a tailored sequential invariance alignment to learn---and preserve---invariant structures over time. We evaluate our methods under a deployment-oriented protocol that measures performance on unseen target domains. Across six benchmark and real-world datasets spanning vision, medicine, manufacturing, and ecology, our methods consistently outperform existing CL baselines in terms of generalization to unseen target domains. As an ablation, we further show that na\"ive extensions of sequential training with existing domain-invariant representation learning (DIRL) methods provide only limited benefits. To the best of our knowledge, this is the first work to develop domain-invariant representation methods for CL.

Theory · Learning Theory

Juno Kim, Jihun Yun, Jason Lee, Kwang-Sung Jun

On-policy preference learning algorithms for language model alignment such as online direct policy optimization (DPO) can significantly outperform their offline counterparts. We provide a theoretical explanation for this phenomenon by analyzing how the sampling policy's coverage evolves throughout on-policy training. We propose and rigorously justify the \emph{coverage improvement principle}: with sufficient batch size, each update moves into a region around the target where coverage is uniformly better, making subsequent data increasingly informative and enabling rapid convergence. In the contextual bandit setting with Bradley-Terry preferences and linear softmax policy class, we show that on-policy DPO converges exponentially in the number of iterations for batch size exceeding a generalized coverage threshold. In contrast, any learner restricted to offline samples from the initial policy suffers a slower minimax rate, leading to a sharp separation in total sample complexity. Motivated by this analysis, we further propose a simple hybrid sampler based on a novel \emph{preferential} G-optimal design, which removes dependence on coverage and guarantees convergence in just two rounds. Finally, we develop principled on-policy schemes for reward distillation in the general function class setting, and show faster noiseless rates under an alternative deviation-based notion of coverage.

General Machine Learning · Online Learning, Active Learning and Bandits

Yuxiao Wen, Zihao Hu, Yanjun Han, Yuan YAO, Zhengyuan Zhou

Existing auto-bidding algorithms in digital advertising often treat the value of an ad opportunity as the revenue obtained when an ad is shown and/or clicked, and bid accordingly. This can lead to wasteful spending because the true value is the marginal gain from paid exposure: even without winning a sponsored slot, an advertiser may still earn revenue via an organic search result (e.g., on Google or Amazon). Motivated by recent work, we model ad value as a treatment effect—the outcome difference between winning and losing the auction—and study online learning for bidding in second-price (Vickrey) auctions under this causal perspective. We develop algorithms that attain rate-optimal regret under several feedback models. A key ingredient exploits the information revealed by the second-price payment rule, which strictly improves regret relative to analogous learning problems in first-price auctions.

Deep Learning · Large Language Models

Kaiyu Huang, Xingyu Wang, Mingze Kong, Zhubo Shi, Yuqian Hou, Hong Xu, Zhongxiang Dai, Minchen Yu, Qingjiang Shi

In real-world deployments of large language models (LLMs), balancing inference quality and computational cost has become a central challenge. Existing approaches tackle this trade-off along two largely independent dimensions: model routing, which switches among models of different scales to match request complexity, and test-time scaling (TTS), which adjusts inference-time compute within a fixed model for fine-grained control. However, this decoupled design introduces inherent limitations. Model routing yields coarse-grained, discrete performance changes due to the sparse set of model scales, while single-model TTS often encounters capacity ceilings and exhibits diminishing returns as compute increases. Moreover, treating the two mechanisms separately restricts adaptability in dynamic inference environments. To overcome these limitations, we introduce *Unified Inference Scaling (UIS)*, which unifies model routing and TTS in a single optimization space. Building on this formulation, we propose UniScale, an online framework that models adaptive UIS as a contextual multi-armed bandit problem and learns inference policies via LinUCB. The framework incorporates efficiency-aware learning and cost modeling to ensure stable and scalable optimization over high-dimensional action spaces. Evaluation shows that UniScale effectively exploits the synergy in the UIS space to deliver a fine-grained and consistently better quality-cost trade-off across diverse, dynamic inference scenarios.

Deep Learning · Large Language Models

Xiang Li, Liping Yi, Mingze Kong, Min Zhang, Zhongxiang Dai, Qinghua Hu

Social simulation provides a compelling testbed for studying social intelligence, where agents interact through multi-turn dialogues under evolving contexts and strategically adapting opponents. Such environments are inherently non-stationary, requiring agents to dynamically adjust their strategies over time. However, most Large Language Model (LLM) based social agents rely on static personas, while existing approaches for enhancing social intelligence, such as offline reinforcement learning or external planners, are ill-suited to these settings, typically assuming stationarity and incurring substantial training overhead. To bridge this gap, we propose **ALSO** (**A**dversarial on**L**ine **S**trategy **O**ptimization), the first framework for online strategy optimization in multi-agent social simulation. ALSO advances social adaptation through two key contributions. (1) ALSO formulates multi-turn interaction as an adversarial bandit problem, where combinations of static personas and dynamic strategy instructions are treated as arms, providing a principled solution to non-stationarity without relying on environmental stability assumptions. (2) To predict rewards and generalize sparse feedback in multi-turn dialogues, ALSO introduces a lightweight neural surrogate to predict rewards from interaction histories, enabling sample-efficient exploration and continuous online adaptation. Experiments on the Sotopia benchmark demonstrate that ALSO consistently outperforms static baselines and existing optimization methods in dynamic environments, validating the effectiveness of adversarial online strategy optimization for building robust social agents. The codes of ALSO are available at https://anonymous.4open.science/r/ALSO-67D5/

Jiajun Chen, Jin Tian, Chris Quinn

Counterfactual reasoning is one of the fundamental facets of human cognition, involved in various tasks such as explanation, credit assignment, blame, and responsibility. It describes the queries what would have happened had some intervention been performed given that something else, corresponding to Layer 3 of the Pearl Causal Hierarchy. In this project, we examine a specific type of counterfactual quantities, called counterfactual direct (Str-DE), indirect (Str-IE), and spurious (Str-SE) effects for quantifying fairness in a sequential decision-making framework. Building on these measures, we formulate an online causally-fair learning problem with multiple long-term constraints and study it in both non-parametric contextual bandits and parametric logistic bandits settings. We achieve sublinear regret and violations bounds for both bandits settings with round-wise counterfactual fairness constraints (that are a priori unknown) without Slater’s condition. In particular, for logistic bandits, we obtain nearly optimal regret bound with leading term similar to that for unconstrained case (Zhang et al., 2025).

General Machine Learning · Online Learning, Active Learning and Bandits

Motti Goldberger, Nils Rudi

We study the active learning problem of fixed-confidence top-$k$ identification from noisy pairwise comparisons under latent-utility models. The objective is to identify the top-$k$ items with probability at least $1-\delta$ while using as few comparisons as possible by adaptively selecting which pairs to compare. While pure exploration with dueling bandits has been studied, an algorithm achieving asymptotic optimality has not yet been established. We characterize the structure of the information-theoretic lower bound on sample complexity, revealing a structured saddle-point problem. This structure enables a primal--dual algorithm that learns the optimal comparison allocation online while being computationally efficient. We then construct an adaptive comparison-allocation strategy that tracks the optimal solution and prove that the resulting procedure is asymptotically optimal.

General Machine Learning · Online Learning, Active Learning and Bandits

Yanchen Wu, Bo Li

Personalizing AI decision support for heterogeneous human decision-makers remains a key challenge. We study a collaboration workflow where AI provides a reduced prediction set via conformal prediction as an input for human, and human makes final decision. We use contextual bandits to learn the complex and intangible human decision function, where the optimal set size, governed by a significance parameter $\alpha$ (arms), varies across individuals and tasks (context). To address large arms spaces and high-dimensional contexts, we introduce the Adaptively Grouped Contextual Bandit (AGCB) framework, bypassing unreliable complex function online approximation in favor of directly exploiting Human-AI problem structure through two pillars: continuity-aware counterfactual reasoning that efficiently shares information across decisions, and a data-driven zooming mechanism that adaptively partitions the context space. The zooming mechanism performs a principled, native trade-off between intra-group estimation error and inter-group approximation bias, ensuring optimal granularity for both cumulative and simple regret objectives. Crucially, a single continuity assumption uniquely enables both the bias control for adaptive grouping and the robustness of our counterfactual updates. This leads to minimax-optimal regret rates. Empirical results confirm that AGCB significantly outperforms existing methods in heterogeneous, data-scarce environments.

Theory · Online Learning and Bandits

Xueping Gong, Jiheng Zhang

Contextual bandits serve as a foundational framework for sequential decision-making in domains like recommendation systems, IoT device management, and conversational AI, yet classical models overlook a critical practical constraint: acquiring extra observations incurs non-trivial costs, creating an unaddressed trade-off between information gain and expenditure. To fill this gap, we study contextual bandits with paid observations, where the learner actively chooses which actions to observe (at a specified cost) in each round, with the goal of minimizing total regret that combines learning losses and cumulative observation costs. We first design a near-optimal algorithm for adversarial environments, proving it achieves a regret rate significantly higher than that of cost-free contextual bandits—even for small observation costs—thus quantifying how paid observations reshape learning complexity. We then uncover a critical phase-transition phenomenon when incorporating free observation budgets: below a threshold budget, free observations only reduce total costs without changing the underlying regret rate, while above this threshold, they drastically improve learning efficiency, lowering the regret rate to match that of cost-free settings. To leverage this phenomenon, we develop a meta-controller that adaptively switches strategies based on the available budget, ensuring near-optimal performance across both low- and high-budget regimes. Furthermore, to address practical challenges like infinite policy spaces and computational inefficiency, we propose an oracle-efficient algorithm under a function approximation framework, which leverages an online regression oracle to maintain strong performance for stochastic losses. Our results also shed light on the scenarios about switching costs, budgeted constraints, model misspecification and the trade-offs involved in knapsack problems. Finally, we conduct numerical experiments to validate our theoretical findings and demonstrate practical efficiency. Key words: Contextual bandit, paid observation, function approximation, phase transition.

General Machine Learning · Online Learning, Active Learning and Bandits

Jiancheng Zhang, Meiqing Li, Qi Zhang, Yinglun Zhu

Real-world datasets across image and text domains are often characterized by skewed class distributions and noisy annotations, which jointly degrade model performance, particularly on minority classes. Among existing solutions, active learning offers an effective and efficient paradigm by selectively querying the most informative and balanced samples for annotation. We propose an innovative active learning framework that mitigates class imbalance and selects the most informative samples to annotate. Leveraging foundation model priors, our algorithm enables imbalance-aware co-decisions between foundation model and small model to tackle noisy and imbalanced labels across various domains. We introduce the first study to systematically explore active learning under the dual challenges of label noise and class imbalance across image and text domains. Extensive experiments on imbalanced datasets demonstrate that our method achieves substantial annotation savings—over 50\% compared to the best active learning baseline—while preserving performance and robustness to label noise.

Deep Learning · Large Language Models

Li, Yaming Guo, Shenghao Gao, Xinlong Chen, Zuhao Xu, Ying Sun, Chao Wang, Hui Xiong

While Large language models (LLMs) have strong abilities, they generally rely on fine-tuning to supplement downstream task-specific knowledge. Due to the prohibitive memory overhead of full fine-tuning (FT), existing parameter-efficient fine-tuning techniques, e.g., LoRA and Adapters, update parameters only in low-rank or restricted subspaces. However, they fail to approximate FT---the performative fine-tuner---and risk performance degradation in tough tasks. Therefore, we naturally raise a *Low-cost Full Fine-tuning* question: Can we approach standard full fine-tuning in theory, yet with much lower costs in practice? Our key insight is that performing selective updates at each step can, theoretically, recover FT asymptotically, while being cost-effective and ignoring no parameter direction. This motivates a new general fine-tuning paradigm (called *Think-Touch*): we first predict potentials of parameter groups (*think*) and then update only the selected (*touch*) in one step. Theoretically, we show that under a very weak sufficient condition---divergence of the cumulative coverage of the expected gradient norm---any selection strategy can converge in the full-parameter space to a stationary point at which the FT admits no further first-order improvement. Besides, we further derive the general convergence rate for our paradigm and identify a post-hoc greedy strategy that is rate-optimal. Unfortunately, this strategy cannot be directly applied in practice due to its reliance on full and accurate gradient information. Thus, we propose a bandit-based method to online approximate this ideal strategy in the long run with a rigorous regret guarantee. Extensive experimental results on various tasks demonstrate the potential of our paradigm, including much lower space overheads against FT and better performance than LoRAs.

Theory · Online Learning and Bandits

Yuming Shao, Zhixuan Fang

Linear bandits traditionally prioritize regret minimization, often overlooking statistical inference of the underlying parameter as a critical objective. In high-stakes settings such as healthcare, precise parameter estimation is indispensable, as it provides fundamental insights into system mechanisms and ensures robust decision-making under covariate shift. We investigate the tripartite balance between regret, inference, and safety, deriving a fundamental minimax lower bound that characterizes the Pareto-optimal frontier of these competing goals. We then propose SERMiSC, a novel algorithm that achieves the optimal trade-off by matching this lower bound while maintaining a near-constant $\tilde{O}(1)$ safety risk. Empirical results demonstrate that SERMiSC effectively navigates the Pareto frontier and outperforms various baselines, thereby validating our theoretical analysis.

Reinforcement Learning · Batch/Offline

Kai Fukazawa, Kunal Mundada, Iman Soltani

In safety-critical domains where online data collection is infeasible, offline reinforcement learning (RL) is attractive only if policies achieve high returns without catastrophic lower-tail risk. Prior work on risk-averse offline RL achieves safety at the cost of value- or model-based pessimism, and restricted policy classes that limit policy expressiveness, whereas diffusion/flow-based expressive generative policies have largely been used in risk-neutral settings. We introduce **Risk-Aware Multimodal Actor-Critic (RAMAC)**, a simple, modular, model-free framework that couples an expressive generative actor (e.g., diffusion/flow) with a distributional critic and optimizes a composite objective that combines Conditional Value-at-Risk (CVaR) with behavioral cloning (BC), enabling risk-sensitive learning in complex multimodal scenarios. Since out-of-distribution (OOD) actions are a major driver of catastrophic failures in offline RL, we further provide an objective-level analysis showing that controlling behavior divergence via BC suppresses OOD actions and stabilizes CVaR. Instantiating RAMAC with a diffusion actor, we illustrate these insights on a 2-D risky bandit and evaluate on Stochastic-D4RL, observing consistent gains in CVaR$_{0.1}$ while maintaining strong returns.

Theory · Online Learning and Bandits

Lixing Lyu, Jiashuo Jiang, Wang Chi Cheung

We study infinite-horizon discounted Markov decision processes (DMDPs) under a generative model. Motivated by the Algorithms with Advice framework (Mitzenmacher and Vassilvitskii, 2022), we propose a novel framework to investigate how black-box predictions of the transition matrix can enhance sample efficiency in solving DMDPs and improve sample complexity bounds. We focus on DMDPs with $N$ state–action pairs and discount factor $\gamma$. We first provide an impossibility result showing that, in the presence of predictions with unknown accuracy, no sampling policy can compute an $\epsilon$-optimal policy with a sample complexity better than $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, which matches the state-of-the-art minimax sample complexity bound without prediction. In complement, we design an algorithm based on minimax optimization techniques that leverages predictions of the transition matrix without requiring knowledge of the prediction error. Our algorithm achieves a sample complexity bound that depends on the prediction error and is uniformly better than $\tilde{O}((1-\gamma)^{-4} N \epsilon^{-2})$, the previous best result derived from convex optimization methods. In some cases, our bound even improves upon the state-of-the-art $\tilde{O}((1-\gamma)^{-3} N \epsilon^{-2})$, despite not having access to the prediction quality.

Applications · Language, Speech and Dialog

Geyang Guo, Hiromi Wakaki, Yuki Mitsufuji, Alan Ritter, Wei Xu

Large language models (LLMs) are trained on heterogeneous multilingual corpora, yet existing preference optimization methods often implicitly restrict each training question to a single response language or rely on a fixed dominant language for supervision. We propose language-routed preference optimization (LRPO), an online preference optimization framework that treats language as a selectable variable rather than a fixed input constraint. LRPO elicits multilingual rollouts for each training question and integrates their relative quality into preference-based policy updates, increasing the diversity and informativeness of training signals under the fixed rollout budget. To adaptively determine which languages to explore, we introduce a trainable language router formulated as a multi-armed bandit, balancing exploration of underutilized languages with exploitation of more informative ones. Extensive experiments show that LRPO consistently improves multilingual performance, demonstrating that adaptive language routing enables effective cross-lingual knowledge exploitation for training.

Deep Learning · Large Language Models

Zikun Qu, Min Zhang, Mingze Kong, Xiang Li, Zhiwei Shang, Zhiyong Wang, Yikun Ban, Shuang Qiu, Yao Shu, Zhongxiang Dai

Personalizing large language models (LLMs) to individual user preferences is a critical step beyond generating generically helpful responses. However, current personalization methods are ill-suited for new users, as they typically require either slow, resource-intensive fine-tuning or a substantial amount of pre-existing user data, creating a significant cold-start problem. To address this challenge, we introduce a new paradigm for real-time personalization by learning from online pairwise preference feedback collected during text generation. We propose T-POP (Test-Time Personalization with Online Preference Feedback), a novel algorithm that synergistically combines test-time alignment with dueling bandits. Without updating the LLM parameters, T-POP steers the decoding process of a frozen LLM by learning a reward function online that captures user preferences. By leveraging dueling bandits, T-POP intelligently queries the user to efficiently balance between exploring their preferences and exploiting the learned knowledge to generate personalized text. Extensive experiments demonstrate that T-POP achieves rapid and data-efficient personalization, significantly outperforming existing baselines and showing consistent improvement with more user interactions.

Theory · Online Learning and Bandits

Alhad Sethi, SOFIA SAGAR KAVALI, Shubhada Agrawal, Debabrota Basu, P. N. Karthik

We study one-sided and $\alpha$-correct sequential hypothesis testing for data generated by an ergodic Markov chain. The *null* hypothesis is that the unknown transition matrix belongs to a prescribed set $\cal P$ of stochastic matrices, and the *alternative* corresponds to a disjoint set $\cal Q$. We establish *a tight non-asymptotic instance-dependent lower bound* on the expected stopping time of any valid sequential test under the alternative. Our novel analysis improves the existing lower bounds, which are either asymptotic or provably sub-optimal in this setting. Our lower bound incorporates both the stationary distribution and the transition structure induced by the unknown Markov chain. We further propose an optimal test whose expected stopping time matches this lower bound asymptotically as $\alpha \to 0$. We illustrate the usefulness of our framework through applications to sequential detection of model misspecification in Markov Chain Monte Carlo and to testing structural properties, such as the linearity of transition dynamics, in Markov decision processes. Our findings yield a sharp and general characterization of optimal sequential testing procedures under Markovian dependence.

General Machine Learning · Online Learning, Active Learning and Bandits

Jiajun Chen, Jin Tian, Chris Quinn

Counterfactual reasoning is one of the fundamental facets of human cognition, involved in various tasks such as explanation, credit assignment, blame, and responsibility. It describes the queries what would have happened had some intervention been performed given that something else, corresponding to Layer 3 of the Pearl Causal Hierarchy. In this project, we examine a specific type of counterfactual quantities, called counterfactual direct (Str-DE), indirect (Str-IE), and spurious (Str-SE) effects for quantifying fairness in a sequential decision-making framework. Building on these measures, we formulate an online causally-fair learning problem with multiple long-term constraints and study it in both non-parametric contextual bandits and parametric logistic bandits settings. We achieve sublinear regret and violations bounds for both bandits settings with round-wise counterfactual fairness constraints (that are a priori unknown) without Slater’s condition. In particular, for logistic bandits, we obtain nearly optimal regret bound with leading term similar to that for unconstrained case (Zhang et al., 2025).

Theory · Online Learning and Bandits

Kapilan Balagopalan, Yinan Li, Tuan Nguyen, Yao Zhao, Anton Daitche, Houssam Nassif, Kwang-Sung Jun

The best-arm identification (BAI) problem is one of the most fundamental problems in interactive machine learning, which has two flavors: the fixed-budget setting (FB) and the fixed-confidence setting (FC). For $K$-armed bandits with the unique best arm, the optimal sample complexities for both settings have been settled down, and they match up to logarithmic factors. This prompts an interesting research question about the generic, potentially structured BAI problems: Is FB harder than FC or the other way around? In this paper, we show that FB is no harder than FC up to logarithmic factors. We do this constructively: we propose a novel algorithm called FC2FB (fixed confidence to fixed budget), which is a meta algorithm that takes in an FC algorithm $\mathcal{A}$ and turns it into an FB algorithm. We prove that this FC2FB enjoys a sample complexity that matches, up to logarithmic factors, that of the sample complexity of $\mathcal{A}$. This means that the optimal FC sample complexity is an upper bound of the optimal FB sample complexity up to logarithmic factors. Our result not only reveals a fundamental relationship between FB and FC, but also has a significant implication: FC2FB combined with existing state-of-the-art FC algorithms, leads to improved sample complexity for a number of FB problems.

General Machine Learning · Online Learning, Active Learning and Bandits

Hang Yu, Yu-Hu Yan, Peng Zhao

Gradient-variation online learning has drawn increasing attention due to its deep connections to game theory, optimization, etc. It has been studied extensively in the full-information setting, but is underexplored with bandit feedback. In this work, we focus on gradient variation in Bandit Convex Optimization (BCO) with two-point feedback. By proposing a refined analysis on the *non-consecutive* gradient variation, a fundamental quantity in gradient variation with bandits, we improve the dimension dependence for both convex and strongly convex functions compared with the best known results (Chiang et al., 2013). Our improved analysis for the non-consecutive gradient variation also implies other favorable problem-dependent guarantees, such as gradient-variance and small-loss regrets. Beyond the two-point setup, we demonstrate the versatility of our technique by achieving the *first* gradient-variation bound for one-point bandit linear optimization over hyper-rectangular domains. Finally, we validate the effectiveness of our results in more challenging tasks such as dynamic/universal regret minimization and bandit games, establishing the *first* gradient-variation dynamic and universal regret bounds for two-point BCO and fast convergence rates in bandit games.