论文检索

Theory · Game Theory

Yuantong Li, Guang Cheng, Xiaowu Dai

Recommender systems play a crucial role in internet economies by connecting users with relevant products. However, designing effective recommender systems faces the key challenges: the \textit{exploration-exploitation} tradeoff in securing \textit{incentive} to explore new products against user's self-interested preferences. While prior work addresses Bayesian Incentive Compatibility (BIC) in fixed-design linear bandits \cite{sellke2023price}, we tackle the challenge of stochastic user covariates sampled online. Unlike standard black-box reductions \citep{mansour2020bayesian}, our two-stage framework exploits the linear reward structure to achieve sublinear regret while satisfying incentive constraints. To address it, we propose a two-stage algorithm that integrates incentivized exploration with \textit{any efficient plug-in offline learning algorithms}. In the first stage, it explores products while maintaining incentive compatibility to gather optimal samples. The second stage employs \textit{inverse proportional gap sampling strategy} integrated with any efficient learning methods to secure sublinear regret. Theoretically, we prove that algorithm \recon{} achieves $\tilde{O}(\sqrt{KdT})$ regret and simultaneously satisfies incentive constraints, and discovers the tradeoff between incentive budget and regret, validating in experiments. We demonstrate RCB's strong incentive gain, sublinear regret, and robustness through a real application on personalized warfarin dosing and simulations. To the best of our knowledge, this is the first analysis for BIC in online preference learning settings.

Theory · Online Learning and Bandits

Kiarash Banihashem, Natalie Collina, Alex Slivkins

We study a stylized social learning dynamics where self-interested agents collectively follow a simple multi-armed bandit protocol. Each agent controls an "episode": a short sequence of consecutive decisions. Motivating applications include users repeatedly interacting with an AI, or repeatedly shopping at a marketplace. While agents are incentivized to explore within their respective episodes, we show that the aggregate exploration fails: e.g., its Bayesian regret grows linearly over time. In fact, such failure is a (very) typical case, not just a worst-case scenario. This conclusion persists even if an agent's per-episode utility is some fixed function of the per-round outcomes: e.g., $\min$ or $\max$, not just the sum. Thus, externally driven exploration is needed even when some amount of exploration happens organically.

Theory · Online Learning and Bandits

Dhruv Sarkar, Nishant Pandey, Sayak Ray Chowdhury

Nash regret has recently emerged as a principled fairness-aware performance metric for stochastic multi-armed bandits, motivated by the Nash Social Welfare objective. Although this notion has been extended to linear bandits, existing results suffer from suboptimality in ambient dimension $d$, stemming from proof techniques that rely on restrictive concentration inequalities. In this work, we resolve this open problem by introducing new analytical tools that yield an order-optimal Nash regret bound in linear bandits. Beyond Nash regret, we initiate the study of $p$-means regret in linear bandits, a unifying framework that interpolates between fairness and utility objectives and strictly generalizes Nash regret. We propose a generic algorithmic framework, FairLinBandit, that works as a meta-algorithm on top of any linear bandit strategy. We instantiate this framework using two bandit algorithms: Phased Elimination and Upper Confidence Bound, and prove that both achieve sublinear $p$-means regret for the entire range of $p$. Extensive experiments on linear bandit instances generated from real-world datasets demonstrate that our methods consistently outperform the existing state-of-the-art baseline.

Theory · Online Learning and Bandits

VIKAS DEEP, Shubhada Agrawal

We revisit the problem of sequentially testing the mean of bounded distributions in a level-$\alpha$ power-one framework. We study a $\mathrm{KL_{inf}}$-based sequential test that is known to attain the information-theoretic lower bound on the expected stopping time with exact constants as $\alpha \to 0$. Going beyond first-order asymptotics, we establish a central limit theorem (CLT) for the stopping time of this test. Our analysis proceeds in two steps. First, we prove a novel CLT for the $\mathrm{KL_{inf}}$ statistic itself, characterizing its fluctuations around its deterministic linear growth. We then leverage this result to show that the stopping time, centered appropriately, and scaled by $\sqrt{\log(1/\alpha)}$, converges in distribution to a Gaussian limit with an explicit variance. This yields a second-order characterization of an asymptotically optimal sequential test for bounded distributions. Finally, we present numerical experiments that corroborate our theoretical findings.

General Machine Learning · Online Learning, Active Learning and Bandits

Simone Drago, Marco Mussi, Alberto Maria Metelli

In reinforcement learning, human preference feedback is emerging as a viable alternative to expert-designed reward functions, which can be difficult to engineer in real-world problems. However, despite the growing importance of preference feedback, how to effectively *elicit* preferences remains a fundamental open problem. This work focuses on the *compatible reward identification* task. The aim is to derive, starting from preference feedback, a reward function compatible with the observed preferences and accurate across the *entire* state-action space, ensuring higher transferability, safety, and interpretability. Indeed, the most common *reinforcement learning from human feedback* objective is to learn the *optimal policy*, requiring accuracy only in the portion of the state-action space that the agent visits. However, this goal cannot provide the same guarantees as compatible reward identification. First, we discuss commonalities and differences between the two goals. Then, we consider deterministic preferences, deriving the minimum number of interactions needed to identify the set of compatible rewards, and showing that using fewer queries may lead to arbitrarily large suboptimality. Finally, we focus on stochastic preferences generated via the Bradley-Terry (BT) model. We introduce the concepts of *query basis* and its *index*, relating them to the problem complexity. Upon this, we discuss the connection between the index of a basis and the BT model, as well as the limitations that the model induces in this setting. Additionally, we devise an algorithm to identify a nearly-optimal query basis with polynomial human query complexity.

Theory · Online Learning and Bandits

Kanad Pardeshi, Samsara Foubert, Aarti Singh

In many real-world settings, a centralized decision-maker must repeatedly allocate finite resources to a population over multiple time steps. Individuals who receive a resource derive some stochastic utility; to characterize the population-level effects of an allocation, the expected individual utilities are then aggregated using a social welfare function (SWF). We formalize this setting and present a general confidence sequence framework for SWF-based online learning and inference, valid for any monotonic, concave, and Lipschitz-continuous SWF. Our key insight is that monotonicity alone suffices to lift confidence sequences from individual utilities to anytime-valid bounds on optimal welfare. Building on this foundation, we propose SWF-UCB, a SWF-agnostic online learning algorithm that achieves near-optimal $\tilde{\mathcal{O}}(n+\sqrt{nkT})$ regret (for $k$ resources distributed among $n$ individuals at each of $T$ time steps). We instantiate our framework on three normatively distinct SWF families: Weighted Power Mean, Kolm, and Gini, providing bespoke oracle algorithms for each. Experiments confirm $\sqrt{T}$ scaling and reveal rich interactions between $k$ and SWF parameters. This framework naturally supports inference applications such as sequential hypothesis testing, optimal stopping, and policy evaluation.

Deep Learning · Large Language Models

Son Nguyen, Xinyuan Liu, Ransalu Senanayake

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.

General Machine Learning · Online Learning, Active Learning and Bandits

Ruizhe Deng, Bibhas Chakraborty, Ran Chen, Yan Shuo Tan

We propose Bayesian Forest Thompson Sampling (BFTS), which performs Thompson sampling using arm-wise Bayesian Additive Regression Trees (BART) to model each action's mean reward and generate MCMC-based posterior draws for decision-making. We derive an information-theoretic Bayesian regret bound of order $\widetilde{\mathcal O}(K\sigma\sqrt{T})$ for ideal posterior sampling under a correctly specified Bayesian design. Empirically, BFTS achieves competitive regret on nonlinear synthetic benchmarks with near-nominal uncertainty calibration, attains the best average rank across nine OpenML contextual bandit benchmarks, and yields higher estimated policy values than linear, neural, and tree-ensemble baselines in a Drink Less micro-randomized trial case study. Across OpenML benchmarks, BFTS is robust to hyperparameter choices.

Theory · Online Learning and Bandits

Zhen Li, Gilles Stoltz

We revisit the finite-armed linear bandit model by Nelson et al. [2022], where contexts and rewards are governed by a finite hidden Markov chain. Nelson et al. [2022] approach this model by a reduction to linear bandits, but relies on a simplification in which rewards are linear functions of the posterior probabilities over the hidden states given the observed contexts, rather than functions of the hidden states themselves, and assumes knowledge of the HMM parameters. We instead study the more natural model incorporating direct dependencies in the hidden states (on top of dependencies on the observed contexts, as is natural for contextual bandits) and also target stronger, high-probability, regret bounds for a fully adaptive strategy that estimates HMM parameters online.

Optimization · Discrete and Combinatorial Optimization

Esha Singh, Dongxia Wu, Chien-Yi Yang, Tajana Rosing, Rose Yu, Yian Ma

Multi-objective combinatorial optimization seeks Pareto-optimal solutions over exponentially large discrete spaces, yet existing methods sacrifice generality, scalability, or theoretical guarantees. We reformulate it as an online learning problem over a decomposed decision space, solving position-wise bandit subproblems via adaptive expert-guided sequential construction. This formulation admits regret bounds of $O(d\sqrt{T \log T})$ depending on subproblem dimensionality \(d\) rather than combinatorial space size. On standard benchmarks, our method achieves 80--98\% of specialized solvers performance while achieving two to three orders of magnitude improvement in sample and computational efficiency over Bayesian optimization methods. On real-world hardware-software co-design for AI accelerators with expensive simulations, we outperform competing methods under fixed evaluation budgets. The advantage grows with problem scale and objective count, establishing bandit optimization over decomposed decision spaces as a principled alternative to surrogate modeling or offline training for multi-objective optimization.

General Machine Learning · Online Learning, Active Learning and Bandits

Ziyi Wei, Huaiyang Zhong, Xiaocheng Li

We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means. Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $\Theta(T)$ times. This fundamental distinction makes exploration-free algorithms both natural and effective. Our work makes three contributions. First, we strengthen the existing results on subgaussian variance concentration using the Hanson-Wright inequality and identify a class of strictly subgaussian distributions that yield sharper guarantees. Second, we design exploration-free non-adaptive and adaptive algorithms, and we establish tighter regret bounds than the existing results. Third, we extend the framework to contextual bandit settings, an underexplored direction, and propose algorithms that leverage side information with provable guarantees. Overall, these results position exploration-free allocation as a principled and efficient approach to multi-group mean estimation, with potential applications in experimental design, personalization, and other domains requiring accurate multi-group inference.

General Machine Learning · Online Learning, Active Learning and Bandits

Kellian Cottart, Theo Ballet, Djohan Bonnet, Damien Querlioz

Always-on edge systems must keep learning as conditions change under tight compute budgets and must detect unreliable predictions. Bayesian binary neural networks are attractive in this setting, but mean-field Bernoulli posteriors can saturate on long non-stationary streams, wiping out epistemic uncertainty and freezing plasticity. We propose BiMU, derived from a bounded-memory variational objective that balances stability, plasticity, and forgetting. BiMU combines a data term with controlled relaxation toward the prior and an uncertainty-dependent step size that prevents saturation and sustains informative uncertainty. This non-degenerate posterior enables fully online, buffer-free active querying via Monte Carlo disagreement, reducing label queries and backpropagation updates under imbalance. BiMU sustains learning and strong OOD detection on 1000-task Permuted-MNIST, and on OpenLORIS-Object achieves up to 32× label/update savings at matched accuracy under class imbalance and feature compression.

Theory · Online Learning and Bandits

Mengtong Gao, Zhenhe Zhang, Jichen Li, Xia Xuanzhi, Wentao Zhou, Jing Chen

Two-sided matching markets are pervasive in numerous real-world applications, ranging from labor markets to online advertising. Recently, 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, leading to an uncoordinated scenario that render existing algorithms inapplicable. To address this challenge, we first investigate the one-sided learning setting under uncoordinated player arrivals, where only players need to learn their preferences. We propose the Way-SE algorithm, which achieves an $O(\frac{K^2 \log T}{\Delta_{\min}^2})$ regret through a distributed exploration mechanism that enables participants to implicitly coordinate exploration phases using only local clocks, without global synchronization. More importantly, we extend to the fully decentralized, dynamic two-sided learning setting where both sides need to learn their preferences and players may arrive or depart arbitrarily. We introduce Way-SE-2S, the first algorithm to achieve a sublinear regret $O(T^{\frac{K-1}{K}} \log T)$ in this challenging environment, without requiring global signals, restrictive preference structures, or observability of competing agents' outcomes. Our work provides the first theoretical guarantee for stable matching in fully decentralized and uncoordinated bandit markets.

Reinforcement Learning · Online

Kaixuan Ji, Jiafan He, Quanquan Gu

Aligning large language models (LLM) with human preference plays a key role in building modern generative models and can be achieved by reinforcement learning from human feedback (RLHF). Despite their superior performance, current RLHF approaches often require a large amount of human-labelled preference data, which is expensive to collect. In this paper, inspired by the success of active learning, we address this problem by proposing query-efficient RLHF methods. We first formalize the alignment problem as a contextual dueling bandit problem and design an active-query-based proximal policy optimization (APPO) algorithm with an $\tilde{O}(d^2/\Delta)$ instance-dependent regret bound and an $\tilde{O}(d^2/\Delta^2)$ query complexity, where $d$ is the dimension of feature space and $\Delta$ is the sub-optimality gap over all the contexts. We then propose ADPO, a practical version of our algorithm based on direct preference optimization (DPO) and apply it to fine-tuning LLMs. Our experiments show that ADPO, while only making about half of queries for human preference, matches the performance of DPO, establishing it as a data-efficient alternative to DPO. The codes are available at https://github.com/jkx19/ActiveQuery.

General Machine Learning · Online Learning, Active Learning and Bandits

Tuo Liu, Edgar Dobriban, Francesco Orabona

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.

Theory · Online Learning and Bandits

Yunfan Zhang, Yuxuan Han, Zhengyuan Zhou

We investigate the distributionally robust assortment optimization (DRAO) problem under the contextual multinomial logit (MNL) choice model, where the decision-maker seeks to maximize revenue against worst-case distributional deviations. To address potential distribution shifts relative to the observed data environment, we study DRAO under ambiguity sets defined by three divergences: total variation (TV), Kullback–Leibler (KL), and chi-square ($\chi^2$). Incorporating robust concerns poses challenges for both algorithm design and theoretical analysis. By leveraging strong duality results from the distributionally robust optimization literature and integrating them into the assortment optimization procedures, we develop tailored polynomial-time algorithms under each divergence. We further provide a theoretical analysis and establish sample complexity bounds for all three robust formulations.

General Machine Learning · Online Learning, Active Learning and Bandits

Ganghua Wang, Yuwei Cheng, Haifeng Xu

The probabilistic bisection algorithm (PBA) extends the classical binary search to settings with noisy responses, and is a foundational algorithm commonly used in basic problems such as root-finding. Despite its strong empirical success, its theoretical property, particularly the convergence rate, remains unclear. This paper establishes that PBA converges at a geometric rate, providing a rigorous justification for its empirical efficiency. Notably, this rate is optimal in the sense that it matches the performance of classical binary search under noiseless responses. The core of our analysis lies in directly characterizing the dynamics of PBA queries, which had not been examined in the prior literature. We show that the queries oscillate around the truth but steadily draw closer, thus leading to an estimator that rapidly concentrates on the truth. Beyond resolving the long-standing question of PBA’s convergence, our developed techniques offer new tools for analyzing PBA's dynamics, which may be of independent interest.

General Machine Learning · Online Learning, Active Learning and Bandits

Ruomeng Ding, Tianwei Gao, Tom Zollo, Eitan Bachmat, Richard Zemel, Xinyu Yang

Eliciting information to reduce uncertainty about latent group-level properties is a central problem in collective assessment, preference modeling, and opinion aggregation, and is especially important in survey-based studies. While natural language interactions provide a flexible interface, existing methods typically rely on fixed questionnaires and static respondent sets, and do not adapt to partial or missing responses across rounds. To address this gap, we study adaptive information elicitation through multi-turn interactions between a large language model and a group of individuals, where both queries and respondents are adaptively selected to infer latent group properties. We propose a theoretically grounded framework that, at each round, jointly selects a query and a subset of respondents based on previously observed responses to efficiently reduce uncertainty about a target latent quantity (e.g., group-level political inclination). Motivated by practical survey constraints, such as limited questions and costly participation, our strategy maximizes information gain under a fixed budget. To handle missing and incomplete responses, we combine graph neural networks for aggregating/imputing partial group information with an information-theoretic criterion that guides per-round selection. Across three real-world opinion datasets, we achieve consistent improvements in population-level response prediction under constrained budgets, including over a 12% relative gain on CES at a 10% respondent budget.

General Machine Learning · Online Learning, Active Learning and Bandits

Nitin Bisht, Linjiang Guo, Xiuwen Gong, Huan Huo, Guandong Xu

Recommender systems (RS) may suffer from feedback-driven exposure concentration, where repeated engagement optimization collapses exposure onto a narrow set of categories, reducing catalog coverage and degrading long-horizon learning. Existing methods are often post hoc and typically lack principled uncertainty-aware risk estimates for regulating exposure under endogenous feedback. We therefore propose **CORAL**, a model-agnostic, uncertainty-aware framework that formulates exposure regulation as a constrained sequential decision problem. Specifically, we model self-reinforcing interactions to construct an exposure-saturation state, then derive an upper confidence bound on category-conditioned violation risk from observed history and incorporate it through a state-dependent penalty for adaptive intervention near saturation. Moreover, we provide theoretical guarantees for risk bounds, finite-time recovery, and efficient long-term performance. Extensive experiments on real-world datasets and controlled simulations validate the effectiveness of the proposed framework, which aligns with our theoretical analysis. Our code is available at: https://anonymous.4open.science/r/Coral_Rec-8400.

Theory · Online Learning and Bandits

Arun Verma, Indrajit Saha, Makoto Yokoo, Bryan Kian Hsiang Low

This paper considers a novel variant of the online fair division problem involving multiple agents in which a learner sequentially observes an indivisible item that has to be irrevocably allocated to one of the agents while satisfying a desired balance between fairness and efficiency. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs from noisy observed utilities. However, this assumption may not hold in many real-life applications, for example, an online platform that has a large number of users (items) who use the platform's service providers (agents) only a few times (a few copies of items), which makes it difficult to accurately estimate utilities for all item-agent pairs. To address this limitation, we assume utility is an unknown function of item-agent features. We propose algorithms that model online fair division as a contextual bandit problem, with provable sub-linear regret upper bound guarantees. Our experimental results further validate the effectiveness of the proposed algorithms.