  Given an input query, a recommendation model is trained using user feedback
data (e.g., click data) to output a ranked list of items. In real-world
systems, besides accuracy, an important consideration for a new model is
novelty of its top-k recommendations w.r.t. an existing deployed model.
However, novelty of top-k items is a difficult goal to optimize a model for,
since it involves a non-differentiable sorting operation on the model's
predictions. Moreover, novel items, by definition, do not have any user
feedback data. Given the semantic capabilities of large language models, we
address these problems using a reinforcement learning (RL) formulation where
large language models provide feedback for the novel items. However, given
millions of candidate items, the sample complexity of a standard RL algorithm
can be prohibitively high. To reduce sample complexity, we reduce the top-k
list reward to a set of item-wise rewards and reformulate the state space to
consist of <query, item> tuples such that the action space is reduced to a
binary decision; and show that this reformulation results in a significantly
lower complexity when the number of items is large. We evaluate the proposed
algorithm on improving novelty for a query-ad recommendation task on a
large-scale search engine. Compared to supervised finetuning on recent <query,
ad> pairs, the proposed RL-based algorithm leads to significant novelty gains
with minimal loss in recall. We obtain similar results on the ORCAS
query-webpage matching dataset and a product recommendation dataset based on
Amazon reviews.
