Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries

arXiv:2606.08410 · cs.LG, cs.AI · Submitted 2026-08-14 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries".

Jane: The paper was written by Linfeng Cao, Ming Shi and Ness B. Shroff from The Ohio State University and University at Buffalo.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back, everyone. Today we're looking at a paper with a real mouthful of a title: "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries." Jane, I'm going to need you to break that down for me because my brain is already spinning.

Jane: Happy to, Tom. So, imagine you're a hotel booking app. You have a bunch of hotels, and each one has different qualities—price, cleanliness, location. That's the "multi-objective" part. The "bandit" part is the algorithm trying to figure out which hotel to show you while learning what you like.

Tom: Okay, so it's like a smart recommender system. But what's the "proactive conversational" part? Is it just a chatbot asking me what I want?

Jane: That's the key difference. Old systems are passive. They show you a hotel and ask, "Do you like it?" and you say yes or no. That gives them very little information. This new framework lets *you* take the lead. You type, "I want a cheap and clean hotel," and the system uses that as a structured signal about your priorities.

Lu: And that's the brilliant part, Jane. It's not just a keyword search. The paper models your query as a ranking of your preferences. If you say "cheap and clean," the algorithm assumes your top two objectives are price and cleanliness, in that order. That's a much richer piece of data than a simple thumbs up or down.

Tom: So it's like the user is handing the algorithm a cheat sheet for their own brain. I love that. But I have to ask, Meng, from an engineering standpoint, is this just a fancy way of saying "we parse the text"?

Meng: It's more than that. The challenge is that the algorithm can't just trust that cheat sheet blindly. The paper shows that if you only listen to what the user says, you hit a wall. The math can't tell the difference between a user who loves everything a little bit and a user who loves everything a lot. It's a fundamental problem with the model.

Jane: Right, it's a shift-invariance issue. The algorithm can learn your *relative* preferences—you like price more than cleanliness—but it can't learn your *absolute* preference. It doesn't know if you'd be happy with a three-star hotel or if you absolutely need a five-star one. And that absolute value is what determines which hotel is actually the best for you.

Tom: So the user's query is helpful, but it's not enough on its own. You need the bandit feedback to calibrate the scale. It's like having a map but not knowing the scale, so you need to walk a few steps to figure out how far a mile actually is.

Lu: Exactly, Tom. And that's the core contribution of "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries." It combines the user's proactive query with the passive feedback from their choices to get the best of both worlds. The query gives you a head start, and the feedback corrects your course. It's a really elegant solution to a problem that seemed pretty stuck.

Tom: So we've got a hybrid approach that uses both the user's words and their actions. I'm curious to see how they actually prove this works and what the numbers look like. Let's dig into the summary next.

Summary: Jane: So, Tom, we've established that this paper, "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries," is about blending user queries with action feedback. Now, let's talk about what they actually proved.

Tom: Please, I'm all ears. Did they just say "it works," or did they do the math?

Jane: Oh, they did the math. They created an algorithm called MO-PQUCB. The headline result is that it achieves a regret that scales like the square root of the time horizon, but with a much smaller logarithmic factor than previous methods. It’s a provable improvement in how fast the system learns.

Meng: For our listeners, regret is basically the cost of learning. It's the difference between the reward you got and the reward you *could* have gotten if you knew the user's preferences perfectly from the start. Lower regret means the system gets to the right answer faster.

Tom: So they're saying their algorithm learns faster than the previous best-in-class? That's a strong claim. What's the secret sauce?

Lu: The secret is in how they structure the learning. They use the user's query to anchor the preference estimate, which shrinks the uncertainty in one direction. Then they use the bandit feedback to explore the remaining uncertainty. It's a dual-exploration strategy. They're not just pulling arms randomly; they're pulling arms to specifically reduce the uncertainty that the query couldn't resolve.

Jane: And they have a really nice way of showing why this is necessary. They prove that if you *only* use the queries, you're doomed. You get linear regret, which means you never learn and you're basically guessing forever. That's the shift-invariance problem we talked about. The query alone can't tell you the absolute scale of the user's preferences.

Meng: So the theory is solid, but what about when things go wrong? In the real world, users don't always type perfectly clear queries. What if the language model misinterprets what they say?

Jane: That's the most impressive part, Meng. They have a whole section on that. They model "corrupted" queries, where the feedback is partially wrong. And they show that even then, their algorithm is robust, as long as the corruption isn't too severe. They even designed a special estimator to handle it.

Tom: So it's not just a toy problem. They're building in safeguards for the messy reality of human communication. That's what separates a good paper from a great one. I'm really impressed by the theoretical depth here. It feels like they've closed a real gap in the research.

Lu: They certainly have. The formal guarantees are what make this stand out. It's not just an idea that works in practice; it's an idea that's proven to work. And the robustness analysis makes it even more compelling for real-world deployment.

Tom: Okay, so we've got the theory and the robustness. But I'm a practical guy. How does this actually change the way we build these systems? Let's get into the improvements and the practical side of things.

Improvements: Tom: So, we've got the theory and the robustness. But I'm a practical guy. How does this actually change the way we build these systems? Let's get into the improvements and the practical side of things.

Meng: The biggest practical improvement is the interaction model. Instead of a system that just throws items at you, this paper, "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries," fundamentally changes the conversation. It lets the user steer the ship from the start.

Jane: And it's not just about typing. The paper shows how you can integrate this with large language models. You can have an LLM interpret a user's natural language query and turn it into the structured preference ranking the algorithm needs. That's the bridge between human language and the math.

Tom: So the LLM is the translator. It takes the messy sentence "I want a cheap and clean hotel" and translates it into a clean, structured signal: "Price is priority one, cleanliness is priority two." That's a game-changer for user experience.

Lu: It is, Tom. And the experiments show it. They ran this on real-world datasets like TripAdvisor and BeerAdvocate, and MO-PQUCB consistently outperformed all the baselines. It had lower regret and, importantly, lower variance. It's not just better on average; it's more consistently good.

Meng: The variance point is huge for us engineers. A system that's sometimes great and sometimes terrible is hard to trust. A system that's reliably good is something you can actually ship. And the fact that they tested it with actual LLMs like Gemini and Llama shows it's not just a theoretical construct.

Jane: And what about the robustness? We talked about the theory, but did they show it works in practice?

Meng: They did. They simulated corrupted queries, where the LLM might misinterpret the user or the user might be vague. And their robust variant, MO-PQUCB-GL, still performed well. The regret increased a bit, but it stayed sublinear. It didn't fall off a cliff.

Tom: So it's a system that's not only smart but also resilient. It can handle the noise of the real world. That's the kind of engineering I can get behind. This isn't just a paper for academics; it's a blueprint for building better products.

Lu: And the implications go beyond hotels and beer. Think about personalized education, where the system has to balance a student's desire for a challenge against their need for success. Or healthcare, where you're balancing treatment efficacy against side effects. Anywhere you have competing objectives and a user with personal preferences, this framework can help.

Tom: So we're not just talking about a better recommender system. We're talking about a general framework for personalized decision-making. That's a pretty profound idea. Let's wrap this up and think about what it all means for the future.

Conclusion: Tom: Well, we've covered a lot of ground on "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries." We started with the core problem of learning user preferences in a multi-objective world.

Jane: And we saw how the paper solves it by combining proactive user queries with passive bandit feedback. The query gives a head start, and the feedback calibrates the scale. It's a hybrid approach that's both theoretically sound and practically robust.

Tom: The math is impressive, the experiments are convincing, and the potential applications are huge. This feels like a significant step forward for personalized recommendation systems.

Lu: I think the most exciting part is that it gives us a principled way to use the rich information that users are already willing to provide. We don't have to rely on passive observation anymore. We can actively engage with users and use their words to make better decisions.

Meng: And from an engineering perspective, the fact that they've shown it works with LLMs makes it immediately relevant. The infrastructure is already there; we just needed the right algorithm to tie it all together.

Tom: It's a real pleasure to see a paper that's so complete. It has the theory, the practical validation, and the vision. It's a tough act to follow.

Jane: It really is. So, with that, we'll say goodbye to "Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries." Thanks for listening, and we'll be back soon with the next paper to dissect.

Linfeng Cao, Ming Shi, Ness B. Shroff

The Ohio State University · University at Buffalo

cs.LG, cs.AI

Submitted: 2026-08-14

Updated: 2026-08-18

Comments: UAI 2026

Code: https://github.com/caolinfeng/MO-PQUCB

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

Key concepts

Multi-Objective Bandit: This is an algorithmic approach used in recommender systems where the system must balance multiple competing qualities (like price and cleanliness) while learning user preferences through trial and error.
Proactive Conversational Queries: Instead of passively asking users for feedback, this method allows the user to actively guide the system by stating their priorities in natural language, providing structured signals about their needs.
Regret: In this context, regret is the cost of learning—the difference between the reward received and the optimal reward that could have been achieved if user preferences were known perfectly from the start. Lower regret means faster learning.
Shift-invariance issue: This is a fundamental problem where a model can learn relative preferences (e.g., price > cleanliness) but cannot determine the absolute scale of those preferences, requiring external feedback to calibrate the true value.

Terminology

Regret — 87× in this paper · explained in 3 episodes
Regularization — 16× in this paper · explained in 3 episodes
Robustness — 16× in this paper · explained in 5 episodes
Trace — 6× in this paper · explained in 2 episodes
Loss Function — 4× in this paper · explained in 2 episodes
Sparsity — 4× in this paper · explained in 4 episodes
Adaptation — 3× in this paper · explained in 1 episode
Alignment — 3× in this paper · explained in 1 episode
Proactive Query Elicitation — 3× in this paper
Adaptability — 2× in this paper · explained in 1 episode
Core — 2× in this paper · explained in 2 episodes
Hybrid Approach — 2× in this paper · explained in 4 episodes
Pairwise Comparisons — 2× in this paper · explained in 2 episodes
Reinforcement Learning — 2× in this paper · explained in 4 episodes
Theoretical Guarantees — 2× in this paper · explained in 2 episodes
Adversarial Attacks — 1× in this paper · explained in 1 episode
Calibration — 1× in this paper · explained in 7 episodes
Contextual Bandit Problem — 1× in this paper · explained in 2 episodes
Contextual Bandits — 1× in this paper · explained in 3 episodes
Distribution Shift — 1× in this paper · explained in 5 episodes
Multi-objective Optimization — 1× in this paper · explained in 4 episodes
Personalization — 1× in this paper · explained in 2 episodes
Unified Framework — 1× in this paper · explained in 5 episodes

Summary

Summary

This paper introduces a novel framework for personalized decision-making in multi-objective multi-armed bandits (MO-MAB) by incorporating proactive conversational queries from users. The authors identify a key limitation in existing preference-aware MO-MAB methods: they estimate user preferences solely from bandit utility feedback, which couples preference learning with reward exploration and limits statistical efficiency. In contrast, the proposed framework leverages structured preference signals that users proactively provide through natural-language queries (e.g., cheap and clean hotel).

Problem Formulation. The paper adopts the preference-aware MO-MAB framework with K arms, N users, and D objective dimensions. Each user n has a latent mean preference vector c n ∈ R D, and the utility of arm i for user n is defined as the inner product ⟨c n, μ i⟩, where μ i is the mean reward vector of arm i. At each round t, user n is presented with an available arm set A n,t, and the learner selects an arm and observes both the objective reward vector and the scalar utility. The goal is to minimize cumulative regret R(T) = Σ t=1 T Σ n=1 N ⟨c n, μ a* n,t - μ a n,t⟩, where a* n,t is the optimal arm for user n.

Proactive Query Elicitation (QE). At each round, users provide a top-m n,t ordered subset S t n = [σ n,t(1),..., σ n,t(m n,t)] indicating their most preferred objectives. These rankings are modeled using the Plackett–Luce (PL) subset choice model, where the probability of observing a ranking S is P(Sc) = Π j=1 m exp(c S(j)) / Σ k∈[D]S(1),...,S(j-1) exp(c k). This model generalizes the Bradley–Terry–Luce model (when m=1, D=2) and the full ranking PL model (when m=D).

Key Theoretical Insights. The paper establishes two fundamental insights:

Efficiency of Proactive QE: The QE-based maximum likelihood estimator achieves an error of Õ((m n,tt)-1/2) on the mean-centered preference vector c 0 n, showing that richer elicitation (larger m n,t) improves learning efficiency.
QE-Only Learning is Insufficient: The paper proves a lower bound (Theorem 1) showing that any algorithm relying solely on QE-based preference estimates suffers linear regret R(T) = Ω(T). This arises from the shift-invariance of the PL model: additive shifts to the preference vector do not change the ranking distribution, but they do change arm rankings in MO-MAB whenever Σ d μ i(d) differs across arms. Thus, indistinguishable preference vectors under QE can induce different optimal arms.

MO-PQUCB Algorithm. To resolve this tension, the authors propose MO-PQUCB (Multi-Objective Proactive Query UCB), which integrates QE-based preference anchoring with bandit feedback. The algorithm has two key components:

QE-Anchored Preference Estimator: The hybrid estimator solves a regularized least-squares problem: ĉ(HB) n,t = argmin c∈R D [α Σ l=1 t-1 (⟨c, r a n,l,l⟩ - g a n,l,l)2 + (1-α)c - ĉ(QE) n,t2 U λ], where U λ = U + λI, U = I - (1/D)11 T is the projector onto the subspace orthogonal to 1, and α ∈ (0,1) balances QE anchoring with bandit feedback. The projector U ensures regularization is restricted to the orthogonal subspace, leaving the shift direction unconstrained so bandit feedback can determine it. This admits a closed-form solution: ĉ(HB) n,t = V-1 n,t[α Σ l=1 t-1 g a n,l,l r a n,l,l + (1-α)U λ ĉ(QE) n,t], where V n,t = α Σ l=1 t-1 r a n,l,l r T a n,l,l + (1-α)U λ.
Dual-Exploration UCB Policy: The arm selection policy is a n,t = argmax i∈A n,t [⟨ĉ(HB) n,t, r̂ i,t⟩ + B(r) i,t + B(c) i,t], where B(r) i,t = γ i,tĉ(HB) n,t1 captures reward uncertainty (local exploration), and B(c) i,t = β n t r̂ i,t + γ i,t1 V-1 n,t captures preference uncertainty (global exploration). Here, γ i,t = √(log(t/ρ)/max 1,N i,t) and β n t = C2√(αD3log(αDt)) + D√((1-α)log(t)/(m n,tt)).

Regret Guarantees. The main theoretical result (Theorem 2) shows that with high probability, the user-specific regret satisfies R n(T) = O(√(D3/m n,T + BD3)√(αT log T) + (αBD/√λ)√(KT log T)). By setting α = λ = Θ(log-1(T)), the regret simplifies to R n(T) = O(√(D3/m n,T + BD3)√(KT log T)). Aggregating over all users yields R(T) = O(N√(T log T)). This improves upon the prior PRUCB method [Cao et al., 2025], which achieves O(N√(T log T)) regret, by reducing the logarithmic dependence on T.

Robustness under Corrupted Queries. The paper also studies a setting where proactive queries are partially corrupted. The corruption model assumes that with probability ϵ, the preference vector is permuted: c̃ n,t = P n,tc n, where P n,t is an arbitrary permutation matrix. The paper establishes:

Lower Bound (Theorem 3): For any estimator, the minimax error is Ω(1) when ϵ ≥ 1/2 - 1/(√(DL)), and Ω((1-2ϵ)-1/(√(DL))) otherwise. This reveals a sharp transition at ϵ = 1/2, beyond which consistent estimation is impossible.
Robust Estimator: The paper proposes a group-wise Lasso maximum likelihood estimator that jointly learns the clean preference vector and identifies corrupted samples: (ĉ(QE) n,t, δ̂ n,1:t) = argmin c,δ [Σ j=1 t l PL(S̃ j n; c + δ j) + η Σ j=1 t δ j2]. The l2 group penalty enforces sparsity across samples, encouraging δ j = 0 for clean feedback while permitting nonzero corrections for corrupted rankings.
Regret under Corruption (Theorem 4): With α = λ = Θ(ϵ + log-1(T)), the regret satisfies R(T) = O(N(√(T log T) + √(ϵT log T))). When ϵ = O(1/log T), the corruption term is negligible and the regret matches the uncorrupted setting.

Experiments. The paper validates the theoretical results on synthetic data, TripAdvisor hotel reviews, and BeerAdvocate beer reviews. Key findings include:

MO-PQUCB consistently achieves the lowest cumulative regret and variance compared to baselines including S-UCB, S-MOSS, Pareto-UCB, Pareto-TS, MO-OFUL, ConUCB, and PRUCB.
Under corrupted queries (ϵ = 0.2), MO-PQUCB-GL (with group-wise Lasso) still outperforms all baselines.
Integration with LLMs (Gemini-2.5, Llama-3.1-8B, GPT-OSS-120B, Qwen-Flash, Deepseek-V3) as conversational agents demonstrates practical applicability, with MO-PQUCB variants achieving significantly lower regret than traditional baselines even under conversational noise.
Increasing query elicitation size m (number of top-ranked objectives per query) monotonically improves both regret and preference estimation error.

Improvements for AI systems

Based on the paper, here are the specific improvements I can make to AI systems and what the improved systems can do:

Improvement: Replace passive, system-driven questioning (e.g., Do you like this item?) with proactive, user-initiated preference extraction. The AI system should parse natural-language queries (e.g., cheap and clean hotel) to infer a ranked subset of objectives using a Plackett–Luce model.

What the improved system can do:

Extract top-m objective rankings from free-text user input (e.g., I want a hotel that's affordable and clean → [price, cleanliness]).
Use these rankings to anchor preference estimation, reducing the number of interactions needed to learn user trade-offs.
Achieve a √log T improvement in regret compared to passive feedback systems (from O(√T log T) to O(√T log T)).