Aadirupa Saha

Replicable Dueling Bandits

Rohan Deb, Aadirupa Saha, Udaya Ghai +2

Dueling bandits choose each comparison based on earlier noisy outcomes, so two runs on the same preferences can compare different pairs. We study replicable dueling bandits, where…

Bandit PCA with Minimax Optimal Regret

Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha

We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round $t = 1, \dots, T$ , the adversary selects a $d \times d$ symmetric gain matrix…

Learning to Allocate Resources with Censored Feedback

Giovanni Montanari, Côme Fiegel, Corentin Pla +2

We study an online resource allocation problem in which at each round, a budget $B$ must be allocated across $K$ arms under censored feedback. An arm yields a reward if and only if…

LLM-as-Judge on a Budget

Aadirupa Saha, Aniket Wagde, Branislav Kveton

LLM-as-a-judge has emerged as a cornerstone technique for evaluating large language models by leveraging LLM reasoning to score prompt-response pairs. Since LLM judgments are stoch…

One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise

Amith Bhat, Haipeng Luo, Aadirupa Saha

We study $K$ -armed Multiarmed Bandit (MAB) problem with $M$ heterogeneous data sources, each exhibiting unknown and distinct noise variances ${σ_{j}^{2}}_{j = 1}^{M}$ . The learner's obje…

cs.LG2025

Tracking the Best Expert Privately

Aadirupa Saha, Vinod Raman, Hilal Asi

We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three…

Hybrid Preference Optimization for Alignment: Provably Faster Convergence Rates by Combining Offline Preferences with Online Exploration

Avinandan Bose, Zhihan Xiong, Aadirupa Saha +2

Reinforcement Learning from Human Feedback (RLHF) is currently the leading approach for aligning large language models with human preferences. Typically, these models rely on exten…

Strategic Linear Contextual Bandits

Thomas Kleine Buening, Aadirupa Saha, Christos Dimitrakakis +1

Motivated by the phenomenon of strategic agents gaming a recommender system to maximize the number of times they are recommended to users, we study a strategic variant of the linea…

DP-Dueling: Learning from Preference Feedback without Compromising User Privacy

Aadirupa Saha, Hilal Asi

We consider the well-studied dueling bandit problem, where a learner aims to identify near-optimal actions using pairwise comparisons, under the constraint of differential privacy.…

Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimization

Aadirupa Saha, Pierre Gaillard

We address the problem of active online assortment optimization problem with preference feedback, which is a framework for modeling user choices and subsetwise utility maximization…

Think Before You Duel: Understanding Complexities of Preference Learning under Constrained Resources

Rohan Deb, Aadirupa Saha

We consider the problem of reward maximization in the dueling bandit setup along with constraints on resource consumption. As in the classic dueling bandits, at each round the lear…

Faster Convergence with Multiway Preferences

Aadirupa Saha, Vitaly Feldman, Tomer Koren +1

We address the problem of convex optimization with preference feedback, where the goal is to minimize a convex function given a weaker form of comparison queries. Each query consis…

Federated Online and Bandit Convex Optimization

Kumar Kshitij Patel, Lingxiao Wang, Aadirupa Saha +1

We study the problems of distributed online and bandit convex optimization against an adaptive adversary. We aim to minimize the average regret on $M$ machines working in parallel…

cs.LG2023★ 1 cited

Bandits Meet Mechanism Design to Combat Clickbait in Online Recommendation

Thomas Kleine Buening, Aadirupa Saha, Christos Dimitrakakis +1

We study a strategic variant of the multi-armed bandit problem, which we coin the strategic click-bandit. This model is motivated by applications in online recommendation where the…

cs.DS2023

Dueling Optimization with a Monotone Adversary

Avrim Blum, Meghal Gupta, Gene Li +3

We introduce and study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an…

On the Vulnerability of Fairness Constrained Learning to Malicious Noise

Avrim Blum, Princewill Okoroafor, Aadirupa Saha +1

We consider the vulnerability of fairness-constrained learning to small amounts of malicious noise in the training data. Konstantinov and Lampert (2021) initiated the study of this…

Only Pay for What Is Uncertain: Variance-Adaptive Thompson Sampling

Aadirupa Saha, Branislav Kveton

Most bandit algorithms assume that the reward variances or their upper bounds are known, and that they are the same for all arms. This naturally leads to suboptimal performance and…

Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback

Han Shao, Lee Cohen, Avrim Blum +3

In classic reinforcement learning (RL) and decision making problems, policies are evaluated with respect to a scalar reward function, and all optimal policies are the same with reg…

One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret Guarantees in Sleeping Bandits

Pierre Gaillard, Aadirupa Saha, Soham Dan

We address the problem of \emph{`Internal Regret'} in \emph{Sleeping Bandits} in the fully adversarial setup, as well as draw connections between different existing notions of slee…

ANACONDA: An Improved Dynamic Regret Algorithm for Adaptive Non-Stationary Dueling Bandits

Thomas Kleine Buening, Aadirupa Saha

We study the problem of non-stationary dueling bandits and provide the first adaptive dynamic regret algorithm for this problem. The only two existing attempts in this line of work…

math.OC2022

Dueling Convex Optimization with General Preferences

Aadirupa Saha, Tomer Koren, Yishay Mansour

We address the problem of \emph{convex optimization with dueling feedback}, where the goal is to minimize a convex function given a weaker form of \emph{dueling} feedback. Each que…

Exploiting Correlation to Achieve Faster Learning Rates in Low-Rank Preference Bandits

Suprovat Ghoshal, Aadirupa Saha

We introduce the \emph{Correlated Preference Bandits} problem with random utility-based choice models (RUMs), where the goal is to identify the best item from a given pool of $n$ i…

Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences

Aadirupa Saha, Pierre Gaillard

We study the problem of $K$ -armed dueling bandit for both stochastic and adversarial environments, where the goal of the learner is to aggregate information through relative prefer…