We focus on the dueling bandits problem, which has recently drawn significant attention due to its wide-ranging applications in online recommendation systems and the alignment of large language models (LLMs), considers an online preference learning scenario where the learner iteratively selects arms based on pairwise comparison feedback to infer user preferences. Two primary objectives are typically considered in dueling bandits: Regret Minimization (RM), which aims to improve the overall quality of selected arms over time, and Best Arm Identification (BAI), which seeks to efficiently identify the best item with minimal user feedback. For instance, RM is exemplified by the objective of consistently providing high-quality items, while BAI reduces the required human feedback by minimizing the number of necessary comparisons. Conventional research treats RM and BAI as two conflicting objectives, optimizing one at the expense of the other. In this paper, we propose a novel framework that demonstrates the near-consistency of RM and BAI in dueling bandits by reducing the BAI in dueling bandits into a sequential noisy identification problem. Based on our formulation, we propose a black-box reduction technique that transforms any RM algorithm into a BAI algorithm, and prove that such reduction with optimal RM algorithm achieves optimal sample complexity and nearly-optimal cumulative weak regret simultaneously. Our proposed algorithm acheives a nearly-optimal BAI sample complexity and attains a cumulative weak regret that is order-wise equivalent to the best-known result simultaneously. Experiments on both synthetic benchmarks and real-world online recommendation tasks validate the effectiveness of the proposed method, providing empirical evidences for our theoretical findings.

In open-environment machine learning (open ML), the learning objectives can vary according to specific real-world requirements. Models tailored for initial objectives may not be appropriate for the varied objectives. Retraining models from scratch for every single objective can be computationally intensive. Therefore, it is desirable to reuse models trained on the original objectives to help learn under the varied objectives. To this end, it is essential to characterize the objective correlations to better reuse the models. Previous works only consider the relative importance between pairs of previous and varied objectives, also known as previous-varied objectives correlations, ignoring correlations among the original objectives themselves. In this article, we demonstrate the importance of cross-original objective correlations. We propose a novel approach that employs the optimal transport technique to model correlations across all previous and varied objectives and then facilitates model reuse by utilizing learned transportation discrepancies to incorporate model reusabilities. Our empirical results show that our approach significantly outperforms existing benchmarks and well captures the underlying objective structure, validating the importance of accurate objective correlation modeling for learning with varied objectives.

Conventional machine learning typically assume a fixed learning objective throughout the learning process.However, for real-world tasks in open and dynamic environments, objectives can change frequently.For example, in autonomous driving, a car has several default modes, but a user's concern for speed and fuel consumption varies depending on road conditions and personal needs.We formulate this problem as learning with varied objectives (LVO), where the goal is to optimize a dynamic weighted combination of multiple sub-objectives by sequentially selecting actions that incur different losses on these sub-objectives.We propose the VaRons algorithm, which estimates the action-wise performance on each sub-objective and adaptively selects decisions according to the dynamic requirements on different sub-objectives.Further, we extend our approach to cases involving contextual representations and propose the Con-VaRons algorithm, assuming parameterized linear structure that links contextual features to the main objective.Both the VaRons and ConVaRons are provably minimax optimal with respect to the time horizon 𝑇 , with ConVaRons showing better dependency with the number of sub-objectives 𝐾.Experiments on dynamic classifier and real-world cluster service allocation tasks validate the effectiveness of our methods and support our theoretical findings.

This paper studies the problem of learning with augmented classes (LAC), where augmented classes unobserved in the training data might emerge in the testing phase. Previous studies generally attempt to discover augmented classes by exploiting geometric properties, achieving inspiring empirical performance yet lacking theoretical understandings particularly on the generalization ability. In this paper we show that, by using unlabeled training data to approximate the potential distribution of augmented classes, an unbiased risk estimator of the testing distribution can be established for the LAC problem under mild assumptions, which paves a way to develop a sound approach with theoretical guarantees. Moreover, the proposed approach can adapt to complex changing environments where augmented classes may appear and the prior of known classes may change simultaneously. Extensive experiments confirm the effectiveness of our proposed approach.