  The recent advances of conversational recommendations provide a promising way
to efficiently elicit users' preferences via conversational interactions. To
achieve this, the recommender system conducts conversations with users, asking
their preferences for different items or item categories. Most existing
conversational recommender systems for cold-start users utilize a multi-armed
bandit framework to learn users' preference in an online manner. However, they
rely on a pre-defined conversation frequency for asking about item categories
instead of individual items, which may incur excessive conversational
interactions that hurt user experience. To enable more flexible questioning
about key-terms, we formulate a new conversational bandit problem that allows
the recommender system to choose either a key-term or an item to recommend at
each round and explicitly models the rewards of these actions. This motivates
us to handle a new exploration-exploitation (EE) trade-off between key-term
asking and item recommendation, which requires us to accurately model the
relationship between key-term and item rewards. We conduct a survey and analyze
a real-world dataset to find that, unlike assumptions made in prior works,
key-term rewards are mainly affected by rewards of representative items. We
propose two bandit algorithms, Hier-UCB and Hier-LinUCB, that leverage this
observed relationship and the hierarchical structure between key-terms and
items to efficiently learn which items to recommend. We theoretically prove
that our algorithm can reduce the regret bound's dependency on the total number
of items from previous work. We validate our proposed algorithms and regret
bound on both synthetic and real-world data.
