# Leveraging the Power of Conversations: Optimal Key Term Selection in Conversational Contextual Bandits

arXiv: https://arxiv.org/abs/2505.21393 · HTML: https://mlsanity.com/paper/2505.21393/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 32 references that are in the map.
- First posted on arXiv 27 May 2025.

## Builds on (most cited first, 12 of 12)

- [Advances and Challenges in Conversational Recommender Systems: A Survey](https://mlsanity.com/paper/2101.09459/) (2021)
- [Conversational Recommender System](https://mlsanity.com/paper/1806.03277/) (2018)
- [Conversational Contextual Bandit: Algorithm and Application](https://mlsanity.com/paper/1906.01219/) (2019)
- [Seamlessly Unifying Attributes and Items: Conversational Recommendation for Cold-Start Users](https://mlsanity.com/paper/2005.12979/) (2020)
- [The Externalities of Exploration and How Data Diversity Helps Exploitation](https://mlsanity.com/paper/1806.00543/) (2018)
- [Comparison-based Conversational Recommender System with Relative Bandit Feedback](https://mlsanity.com/paper/2208.09837/) (2022)
- [Efficient Explorative Key-term Selection Strategies for Conversational Contextual Bandits](https://mlsanity.com/paper/2303.00315/) (2023)
- [Hierarchical Conversational Preference Elicitation with Bandit Feedback](https://mlsanity.com/paper/2209.06129/) (2022)
- [A Multi-Agent Conversational Bandit Approach to Online Evaluation and Selection of User-Aligned LLM Responses](https://mlsanity.com/paper/2501.01849/) (2025)
- [FedConPE: Efficient Federated Conversational Bandits with Heterogeneous Clients](https://mlsanity.com/paper/2405.02881/) (2024)
- [Conversational Dueling Bandits in Generalized Linear Models](https://mlsanity.com/paper/2407.18488/) (2024)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)

## Built on by (most cited first, 2 of 2)

- [Tailored Behavior-Change Messaging for Physical Activity: Integrating Contextual Bandits and Large Language Models](https://mlsanity.com/paper/2506.07275/) (2025)
- [Steering Frozen LLMs: Adaptive Social Alignment via Online Prompt Routing](https://mlsanity.com/paper/2603.15647/) (2026)

## Abstract (arXiv)

Conversational recommender systems proactively query users with relevant "key terms" and leverage the feedback to elicit users' preferences for personalized recommendations. Conversational contextual bandits, a prevalent approach in this domain, aim to optimize preference learning by balancing exploitation and exploration. However, several limitations hinder their effectiveness in real-world scenarios. First, existing algorithms employ key term selection strategies with insufficient exploration, often failing to thoroughly probe users' preferences and resulting in suboptimal preference estimation. Second, current algorithms typically rely on deterministic rules to initiate conversations, causing unnecessary interactions when preferences are well-understood and missed opportunities when preferences are uncertain. To address these limitations, we propose three novel algorithms: CLiSK, CLiME, and CLiSK-ME. CLiSK introduces smoothed key term contexts to enhance exploration in preference learning, CLiME adaptively initiates conversations based on preference uncertainty, and CLiSK-ME integrates both techniques. We theoretically prove that all three algorithms achieve a tighter regret upper bound of O(√dTlogT) with respect to the time horizon T, improving upon existing methods. Additionally, we provide a matching lower bound Omega(√dT) for conversational bandits, demonstrating that our algorithms are nearly minimax optimal. Extensive evaluations on both synthetic and real-world datasets show that our approaches achieve at least a 14.6% improvement in cumulative regret.