# Optimizing Audio Recommendations for the Long-Term:
A Reinforcement Learning Perspective

Lucas Maystre  Spotify Daniel Russo  Spotify Columbia University  Yu Zhao
Spotify

###### Abstract

We study the problem of optimizing a recommender system for outcomes that
occur over several weeks or months. We begin by drawing on reinforcement
learning to formulate a comprehensive model of users’ recurring relationships
with a recommender system. Measurement, attribution, and coordination
challenges complicate algorithm design. We describe careful modeling—including
a new representation of user state and key conditional independence
assumptions—which overcomes these challenges and leads to simple, testable
recommender system prototypes. We apply our approach to a podcast recommender
system that makes personalized recommendations to hundreds of millions of
listeners. A/B tests demonstrate that purposefully optimizing for long-term
outcomes leads to large performance gains over conventional approaches that
optimize for short-term proxies.

##  1 Introduction

Recommendation systems are an essential component of modern online platforms.
They help individuals find candidates to interview for job postings, dating
partners, products to try, or media to engage with. Even though most users
have recurring relationships with recommendation systems, nearly all
recommendation systems rely on machine learning algorithms that are trained to
optimize short-term metrics, which may not accurately reflect the long-term
impact on user satisfaction.

This paper describes efforts at Spotify, a leading audio streaming service, to
optimize audio recommendations for their contribution to user’s long-term
listening habits. We draw inspiration from reinforcement learning (RL), which
gives a formal language for studying the problem of learning across users to
optimize recurring interactions with individual users. Figure 1 contrasts such
a model with popular contextual bandit models of recommender systems [see,
e.g., Li et al., 2010]. In both types of models, the goal is to learn from
interacting with users how to optimize interactions with future users.
Contextual bandit algorithms learn to optimize the immediate reward accrued
from a recommendation action. RL models aim to optimize a sequence of
interactions with an individual user, acknowledging that recommendation
decisions in one period can impact the efficacy of recommendations in future
periods. Unfortunately, it can be difficult to apply generic RL algorithms to
industrial scale recommender systems. The next subsection describes some of
the scientific and organizational challenges.

Figure 1: Contextual bandits vs RL Models

###  1.1 Challenges in optimizing recurring user interactions

While recommendations are often optimized for a myopic measure of success, the
real product and business goal is to power satisfying recurring user
interactions. A hypothetical Spotify user journey is depicted in Figure 2
below. Highlighted in green on the first day is an interaction when the user
searches for the term ‘podcast’ and receives personalized recommendations
through which they discover _Podcast X_ , a hypothetical podcast that releases
new episodes on a regular cadence. Sixty days later the user is still
listening to _Podcast X_ , and this deep connection to the content may have
been nurtured by a decision to recommend the show again on intermediate days.
In this instance, consequences of recommending the show took months to
realize. We would like to design a machine learning system that purposefully
fosters a satisfying recurring experience like this.

Figure 2: A depiction of a possible trajectory of user interactions over 60
days.

Despite these longer-term goals, it is plausible that a myopic recommendation
strategy is nearly optimal. Perhaps the best user experience is to be
presented with the items they are most likely to stream from in the moment.
Also plausible, however, is that a user’s streaming decisions in the short-
term reflect their listening impulses, and a different recommendation
criterion could help them maintain diverse and satisfying listening habits.
Testing the latter hypothesis requires a working, testable, methodology that
purposefully optimizes for longer-term goals. Unfortunately, efforts to
develop such a system run into crucial challenges. Figure 2 brings several of
these into focus.

Measurement.

A poor signal-to-noise ratio makes measurement challenging. Consider some very
holistic outcome of the 60 day user-journey, like whether the user remains a
subscriber after 60 days, or the total number of minutes they listen. One
approach to unbiased measurement is to inject randomness into recommendation
decisions and then assess whether users who received certain recommendations
by chance tend to have “better” outcomes. The signal-to-noise ratio is very
poor, however, both because user-behavior is inherently noisy and because a
single recommendation is a tiny part of their overall 60 day experience.

Attribution.

After observing a positive 60 day trajectory, it is difficult to assign credit
to individual actions in a coherent way. Should a user’s experience listening
to _Podcast X_ be credited to the recommendation that first led to the
discovery, to decisions to recommend that item again later, or, more
ambitiously, to the personalized playlist that preceded its discovery? A
subtlety is that whether a decision is effective at this point in time may
depend on how decisions will be made at other points in the future.
Recommending the user try _Podcast X_ for the first time might only be highly
valuable if future recommendations are likely to resurface that content later.

Coordination.

Notice that in Figure 2 the user seems to transition through many different
kinds of experiences. They see recommendations on the home page, but also see
personalized results on the search page. Some of their interactions may be
with a personalized playlist; podcasts like _Podcast X_ may be embedded within
certain mixed-audio playlists. Distinct, focused, teams optimize each such
experience for immediate outcomes, like whether a user streams after a search
result. Optimizing for the longer-term seems to require coordination among all
such teams.

###  1.2 Contributions of this paper

In this work, we seek to address these challenges and develop a principled but
pragmatic methodology that explicitly optimizes recommendations for the long-
term. The paper makes three main contributions to the literature.

####  1.2.1 Evidence of real-world impact

We provide evidence that successfully optimizing algorithmic recommendations
for longer-term outcomes can have substantial impact. One A/B test, conducted
at Spotify, compared two methods for recommending users podcast shows they
have never listened to previously. In the control group, the algorithm
optimizes the impression-to-stream rate while in the treatment group, the
algorithm also reasons about the downstream consequences of a first stream.
For 63% of users, the two methods disagree about which show to recommend. In
that case, being randomly placed in the treatment group was associated with a
81% increase in average listening minutes attributable to the recommendation.
This algorithm is now used to power recommendations to hundreds of millions of
users around the world.

####  1.2.2 Pragmatic methodology

We describe a methodology that adjusts the logic of an existing myopic
recommender system. At the core of most recommender systems is a vector
embedding of users and items. The dot product between a user and item vector
represents a user’s affinity for the item. For reasons that will become clear,
we refer to these item vectors as _clickiness_ vectors.

At the core of our methodology are new components of the item and user
representations. To the user representation, we add a _content-relationship
state_ that tracks a user’s relationship to items in the catalog. A user’s
content relationship state with a given item is a fixed-length encoding of
their past engagement pattern with it. We also augment an existing
representation of items by tracking _stickiness vectors_. These encode whether
users with given tastes and a given relationship state tend to return to the
item across many future days.

The methodology is easiest to understand when recommending an item the user
has never tried previously. That is, the user has a null relationship state
with that item, remains in that state if they choose not to try the
recommendation, and transitions to a state of having tried the item once if
they stream from the recommendation. The dot product between a user’s vector
and an item’s clickiness vector captures the user’s propensity to follow the
recommendation and try the item. It is similar to the likelihood of the
aforementioned state transition, given a recommendation is made. Stickiness
vectors are trained so that the dot product between a user’s vector and an
item’s stickiness vector encodes the user’s propensity to return to that item
across many future days, post discovery. By considering both clickiness and
stickiness, we hope to generate lasting discoveries that benefit both users
and creators.

Observe how these new representations power our approach to optimizing
recommendations for the long-term. Stickiness vectors offer an understanding
of items in the catalog that is focused on ‘habits’ rather than clicks.
Content-relationship states allow us to successfully reason about the long-
term impact of recommendation action as being mediated through its influence
on a certain state variable—precisely the kind of reasoning that is central to
dynamic programming and reinforcement learning. We think of traditional user
vectors as being poorly suited to this purpose: they are designed to encode a
user’s overall tastes, and, potentially their listening context, and hence may
be insensitive to a single recommendation decision. By contrast, recommending
an item can have a measurable and partly predictable impact on their
relationship state _with that item_.

####  1.2.3 Links to reinforcement learning

A third contribution of this paper is to develop a formal model of our
recommendation problem using the language of reinforcement learning. We
provide a generic formulation of an RL problem which requires grappling with
the measurement, attribution, and coordination challenges described above. We
then impose formal assumptions that underlie our algorithms. With these
assumptions in place, our relatively simple prototype algorithms can be
understood formally as a _policy iteration update_ to the recommendation
algorithm currently in use.

Given an RL style formulation, it is natural to consider applying algorithms
from the literature that impose fewer structural assumptions. As a bridge to
our methodology, we study one such approach in Section 5. The method there is
a so-called _actor-critic_ algorithm. We leverage theoretical understanding in
the literature to offer insight into how attribution and coordination
challenges are coherently addressed, but highlight through a simple example
that unstructured methods face crippling measurement challenges. Our
prototypes can be understood as a variant of this actor-critic algorithm that
relies on certain structural assumptions to alleviate measurement challenges.

In our view, the connection with a generic RL model provides several benefits.
First, it helps clarify the assumptions we make, so that they can be
critically inspected and, in the future, relaxed. Second, the theory of local
policy search offers insight into how our methodology addresses attribution
and coordination challenges in a coherent way. Finally, it could motivate
future RL research. Namely, our structural modeling appears to be critical to
addressing measurement challenges. Could generic RL approaches to
representation learning and value function estimation uncover the structures
we hand-code in our assumptions?

###  1.3 Outline

This paper is organized in an unusual manner. We begin in Section 3 by
describing the prototype solutions we implemented and evidence of real-world
impact from offline data analysis and online experiments. This section is
somewhat informal and meant to be accessible to a relatively broad audience.
With that section serving as motivation, the remainder of the paper provides a
more systematic and reproducible study. Section 4 formulates a generic problem
of optimizing recurring user interactions in RL lingo. Section 5 describes an
unstructured approach to policy improvement that is common in the RL
literature. We leverage ideas from RL theory to explain how attribution and
coordination challenges are coherently addressed, but highlight that
measurement challenges can be crippling. Section 6 imposes structural
assumptions that simplify the policy improvement problem and can greatly
alleviate measurement challenges. The solution derived in Section 6 exactly
matches our prototypes solutions from Section 3, providing a formal
justification for what was first presented as an intuitive heuristic.

##  2 Related literature

##### Recommender systems.

Recommender systems emerged alongside the World Wide Web in the 1990s, helping
to filter and personalize the massive volume of content available.
Recommendation strategies are often divided in to three categories: content-
based, collaborative filtering, and hybrid. A content-based approach relies on
observable properties of items (e.g., their text description) and recommends
items to users that are similar to ones they engaged with previously [Mooney
and Roy, 2000]. Collaborative filtering approaches instead use historical data
on interactions between users and items to make recommendations [Su and
Khoshgoftaar, 2009]. Matrix factorization techniques [Koren et al., 2009] are
a popular collaborative filtering approach. Hybrid approaches aim to mix both
sources of information; see also Ansari et al. [2000] for a Bayesian
preference model that allows many types of information to be leveraged.

Today, deep learning based systems are dominant in industrial recommender
systems [Hidasi et al., 2016, Wang et al., 2021]. In addition to their ability
to fit complex nonlinear patterns, a critical advantage of such methods is
their ability to incorporate and synthesize distinct sources of information.
See Steck et al. [2021] for a critical evaluation of the impact of deep
learning at Netflix.

A great deal of recent research aims to make recommender systems responsive to
users’ most recent interactions [Beutel et al., 2018, Wang et al., 2021]. Most
such work still optimizes individual recommendations myopically, and is
complementary to efforts to optimize sequences of recommendations for the long
term. Below, we describe several threads of research related to optimizing
user interactions for the long-term.

##### Surrogate outcomes and proxy-metrics.

Recognizing the drawbacks of optimizing recommendations only for immediate
engagement, many have tried to develop proxy metrics that are better aligned
with the long-term. This approach is common in many fields—not just
recommender systems. For instance, when the delay involved in measuring long-
term treatment effects is too severe, clinical trials often determine success
based on surrogate endpoints [Prentice, 1989]. A surrogate endpoint is
typically a health indicator (e.g. blood pressure) that is expected to mediate
a treatment’s effect on the true outcome of interest (e.g. whether the patient
suffers a heart attack.)

The use of surrogate or proxy metrics is common in recommender systems. For
instance, Zhou et al. [2010], Ziegler et al. [2005] and Anderson et al. [2020]
study the benefits of diversity in recommendations. Wang et al. [2022]
recently studied five surrogate outcomes at a large online video streaming
service. These are mathematical functions, computed based on user
interactions, which represent Diversity, Repeated Consumption, High-Quality
Consumption, Persistent Topics, and Page-Specific Revisits. They improve some
longer term outcomes by training the machine learning system to optimize for
these metrics, rather than just immediate engagement.

Several papers have proposed multi-armed bandit models where surrogate
outcomes encode actions’ long-term impacts. These include bandit models where
poor recommendations cause attrition [Ben-Porat et al., 2022, Bastani et al.,
2022] and bandit models where objectives incorporate diversity/boredom
considerations [Xie et al., 2022, Cao et al., 2020, Ma et al., 2016]. Wu et
al. [2017] studies a variation on typical bandit model where actions impact
whether a user will return to the system. Yang et al. [2020] combine bandit-
style exploration with long-term surrogate models to optimize promotional
discounts at the Boston Globe, a prominent newspaper.

Surrogacy assumptions are similar to Markov assumptions in RL. One of our main
assumptions in Section 6 can therefore be viewed as surrogacy assumption.
Approaches that combine several surrogate outcomes into a scalar surrogate
index [Athey et al., 2019] are intellectually similar to RL approaches that
fit an approximate value function and then choose actions to increase value-
to-go. There tends to be a distinction in terms of granularity, however. Most
RL implementations use high dimensional state variables and fit value function
approximations with neural networks, rather than handcraft a small number of
surrogate outcomes.

##### RL for optimizing a recommendation systems.

In recent years there have been many impressive demonstrations of algorithms
that synthesize reinforcement learning principles with deep learning.
Recommender systems would seem to be a natural application of these
techniques: they generate massive volumes of data, interact sequentially with
users, and deploy neural networks to optimize each interaction. Early
proposals to view recommendation as an RL problem [see, e.g., Shani et al.,
2005] have been revisited with renewed interested in the past few years. Afsar
et al. [2021] provide a sweeping survey of over a hundred conference and
workshop papers on this topic. Unfortunately, numerous challenges can inhibit
deployment reinforcement learning in the real world [Dulac-Arnold et al.,
2021].

We will focus our discussion in this section on a few high level themes in the
literature, aiming to highlight the primary distinguishing features of our
work. One segment of this literature uses RL to address single-period
decision-making problems with combinatorial decision-spaces. For instance,
consider the problem of selecting a full page or ‘slate’ of recommendations.
This can be broken down, via dynamic programming, into the problem of
selecting the first item, then the second, and so on. See Zhao et al. [2018],
Xie et al. [2021] or Elahi et al. [2022] for recent works along these lines.
This thread of work is not so closely related to ours. Another segment of work
tries to use model-based RL [Hu et al., 2017, Chen et al., 2019b, Shang et
al., 2019]. Since user behavior is notoriously complex and idiosyncratic, most
papers instead try to directly estimate a few relevant quantities of interest
from logged data, like value functions or policy gradients. We focus most of
our discussion on these works.

Several papers propose to optimize sequential user interactions by fitting—and
maximizing—approximate $Q$-functions. Zou et al. [2019] describe such an
approach for the problem of optimizing a sequence of product recommendations
appearing in a feed. Zheng et al. [2018] looks at optimizing a sequence of
news article recommendations. Xin et al. [2020] proposes a method that is
similar to an actor-critic algorithm, but with an augmented self-supervised
loss. Chen et al. [2022] describe a successful implementation at Youtube of an
actor critic algorithm for candidate generation111As is common, their system
relies on two separate pieces of logic: a candidate generation algorithm which
filters a corpus with millions of items down to hundreds and a ranking
algorithm which orders those on the page.. Actor-critic algorithms fit
approximate $Q$-functions and use them to estimate directions for local policy
improvements [Konda and Tsitsiklis, 1999, Sutton et al., 1999]. Chen et al.
[2019a] had previously applied the REINFORCE algorithm [Williams, 1992] to
this problem.

Another example is provided by Ie et al. [2019b]. Again, they test an RL based
recommendation algorithm in live experiments at Youtube. They focus on the
problem of optimizing the total engagement time before a recommendation
session ends. To our understanding, a session begins when a user clicks on a
video from the homescreen and ends when they exit the app or return to the
homescreen. In the interim, whenever a video is completed a full slate of
other videos is recommended. Ie et al. [2019b] fits an approximate
$Q$-function and then recommend slates that maximize it. To make the problem
tractable, they assume the $Q$-function decomposes additively across items and
modify RL iterations to fit this assumption. That work also contains many
helpful discussions of engineering efforts around serving, logging etc. and
develops a package for conducting simulation experiments [Ie et al., 2019a].

Our paper has much in common with these works. We are motivated by similar
pitfalls of myopic recommendation strategies, we grapple with the problem of
defining states and rewards, and we estimate $Q$-functions from offline data.
Like Chen et al. [2019a, 2022], our modeling decisions were heavily influenced
by the need to work within a complex industrial scale system.

Our paper is distinct in using bespoke modeling to enable optimizing for
sustainable listening habits that take months to unfold. Related papers appear
to consider much shorter planning horizons. Ie et al. [2019b] optimize
performance over a single viewing session. Zheng et al. [2018] and Zou et al.
[2019] use a discount factors of 0.4 and 0.9, respectively, in problems where
one recommendation is made per time period. Implicitly, they optimize
performance over a short sequence of recommendations. Optimizing instead over
a long horizon greatly exacerbates the coordination and measurement challenges
highlighted in Section 1.1. As a result, we cannot directly apply unstructured
actor-critic algorithms as in some of the aforementioned papers (see Section
5). To overcome this challenge, we make structural assumptions motivated by
product intuition and design new features of user/item representations that
are tailored to creating sustainable item-level habits. The modeling in
Sections 3 and 6 appears to be quite different from past work.

Besbes et al. [2016] study a non-myopic approach to news article
recommendation. They characterize content along two dimension: “clickability,
the likelihood to click to an article when it is recommended; and (2)
engageability, the likelihood to click from an article when it hosts a
recommendation.” They formulate the problem of maximizing clicks across an
entire visit to the system, and propose a one-step look-ahead policy that
balances immediate click-through rate and engageability. Their introduction of
a new engageability metric is reminiscent of our introduction of item
stickiness models.

##### Other MDP models of recurring customer interactions.

Markov decision process (MDP) models of recurring customer interactions are
almost as old as the formal study of MDPs themselves. Howard [2002] comments
that his invention of policy iteration in 1960 was inspired by the real-life
application of MDPs in optimizing catalog mailing policies at Sears, Roebuck
and Company. See Gönül and Shi [1998], Simester et al. [2006] or Gönül and
Hofstede [2006] for more recent published work along those lines. More
recently, but still over two decades ago, Pfeifer and Carraway [2000]
advocated for the use Markov chain models of customer lifetime value, and MDP
models of managing customer relationships. Rust and Chung [2006] calls
optimizing dynamic marketing interventions for the increase in customer
lifetime value the ‘Holy Grail’ of customer relationship management. The use
of hidden Markov models of latent customers relationship states is also well
established in the academic marketing literature [Netzer et al., 2008, Montoya
et al., 2010, Abhishek et al., 2012, Ascarza and Hardie, 2013, Liberali and
Ferecatu, 2022]. Recent work by Zhang et al. [2022] analyzes an MDP model of
pricing decisions that impact customer lifetime value.

One major dimension along which we differ from this work is the granularity of
personalization. Most aforementioned papers deal with simple structured
problems [e.g. Gönül and Shi, 1998] or problems where user states can take on
only a few possible values [e.g. Netzer et al., 2008] that make dynamic
programming or hidden Markov modeling tractable and interpretable. Successful
recommendation systems need a very refined understanding of user tastes and
item’s appeal, and modern ones do this by training neural networks on billions
of past user interactions. Our work tries to integrate the logic of MDPs into
such a system.

##  3 Prototypes with real-world impact

This section describes methods, developed at Spotify, that optimize podcast
recommendations for the long-term. These were designed to serve as testable
prototypes. With careful thought, but low engineering effort, we attempted to
prove that optimizing for the long-term could have large product impact. Part
of this methodology proved so effective that it is now used in production. We
share evidence from A/B tests involving tens of millions of users.

The presentation in this section is purposefully informal. It is meant to be
accessible to a fairly broad audience. It describes how these prototypes work,
but at this stage it may be unclear what the objective is or precisely what
assumptions we are making. With this section offering concrete motivation, in
Sections 4–6 we develop a formal model and offer precise connections between
these prototypes and general RL methodology.

We begin by describing, at a somewhat superficial level, how podcast
recommendations are optimized for short-term outcomes. We then describe, in
greater details, how this methodology was augmented to optimize for longer-
term goals. For product reasons, two cases are treated separately. Podcast
_discovery_ recommendations are restricted to podcast shows the user has never
tried previously (Section 3.1). Podcast _resurfacing_ recommendations are
restricted to shows the user has already listened to previously (Section 3.2.
In fact, we really provide a single methodology; The logic governing discovery
recommendations is a special case of the resurfacing logic.

###  3.1 Podcast discovery

Consider again the hypothetical 60-day user journey in Figure 2. On day one,
the user discovers the show _Podcast X_. The discovery seems to be directly
attributable to a personalized recommendation. It followed a search for the
generic term ‘podcast’, based on which a machine learning algorithm chose to
display _Podcast X_ to the user.

Was this interaction successful? Should this item be shown to similar users in
the future? One piece of implicit feedback is that the user clicked on the
item and listened to it. This signals that the user was, indeed, interested in
trying the item at that moment. However, the users’ downstream behavior offers
richer implicit feedback. Following the initial discovery, the user chose to
listen to the show again on subsequent days, seeming to signal deeper
enjoyment of the item.

In principle, the item a user is most likely to try in the current moment may
not be the item they are most likely to form a lasting attachment to. We
hypothesize that this offers an opportunity for substantially improving upon a
standard myopic recommendation logic.

####  3.1.1 User and item embeddings

Vector embeddings of users and items are central to many recommendation
systems. These representations are typically trained by solving a surrogate
classification problem. See Appendix A for an overview of influential work by
[Covington et al., 2016], which illustrates this problem.

We denote an item, like _Podcast X_ , by $a$ (chosen for ‘action’) and the
corresponding item vector by $\nu_{a}\in\mathbb{R}^{d}$. We use the variable
$u$ to index users and denote the corresponding user vector at time $t$ by
$u_{t}\in\mathbb{R}^{d}$. We think of $u_{t}$ as encoding the recommender
system’s understanding of the user’s tastes, and the dot product

$\displaystyle\mathrm{affinity}(u,a)=u_{t}^{\top}\nu_{a}$ (1)

as encoding the propensity of a user with given tastes to have a short
interaction with the item.

####  3.1.2 A fine-tuned short-term model

For concreteness, consider now the problem of recommending a podcast show on
the banner component of the home screen in the Spotify mobile app, displayed
in Figure 3(a). Given a trained representation of users and items, one simple
recommendation strategy is to pick an item with maximal affinity score (1)
among a pool of candidates. A more refined approach consists of training a
fine-tuned model that leverages the pre-trained embedding to predict the
short-term consequences of a recommendation. Consider a dataset
$\mathcal{D}=\\{(\nu_{A},u,X,\mathbbm{1}(Y>0))\\}$ describing the immediate
outcome of past recommendations on the banner. This contains the vector
representation $\nu_{A}$ of the recommended item, the vector representation
$u$ of the user at the time of the recommendation, a vector $X$ describing the
user’s context (e.g. the time of day), and an indicator $\mathbbm{1}(Y>0)$ of
whether the user clicked and listened to the item. We might learn the weights
$w$ of a neural network $P_{w}\left(\nu,u,x\right)$ by minimizing the
prediction error on $\mathcal{D}$. Specifically, they are chosen to
approximately solve:

$\min_{w}\sum_{(\nu,u,x,\mathbbm{1}(Y>0))\in\mathcal{D}}{\rm
CrossEntropyLoss}\big{[}P_{w}\left(\nu,u,x\right)\,,\,\mathbbm{1}(Y>0)\big{]},$
(2)

where ${\rm CrossEntropyLoss}(p,q)=-p\log q-(1-p)\log(1-q)$. Given trained
weights $\hat{w}$, a myopic recommender might select the item
$\operatorname*{arg\,max}_{a\in\mathbb{A}_{\star}}P_{\hat{w}}(\nu_{a},u_{t},X_{t})$
that the user is most likely to stream among a pool of eligible candidates
$\mathbb{A}_{\star}$.

(a) Home banner

(b) Podcast discovery shelf

Figure 3: Screenshots of Spotify mobile application. The banner component
displays a single content item, whereas the podcast discovery shelf contains
up to 20 cards that the user can scroll through.

####  3.1.3 Long-term stickiness model

We augment existing short-term models by training new long-term models. For
every item $a$, we gather a dataset on users who discovered item $a$, their
features at the time they first listened to the item, and their interactions
with the item post-discovery. Specifically, in our prototypes, we set
$\mathcal{D}_{a}=\\{(u,R)\\}$ to be a dataset of tuples ranging over users who
discovered the item more than 60 days ago. The tuple $(u,R)$ describes the
vector representation of the user’s tastes $u\in\mathbb{R}^{d}$ at the time of
the discovery and their return days $R\in\\{0,\cdots,59\\}$, indicating the
number of days in the subsequent 59 days that the user returned to and
listened to the item.222We choose a 60-day window for practical reasons. It is
long enough to capture recurring podcast listening habits, but short enough to
measure in practical experiments. Item “stickiness” vectors are trained by
solving the least-squares333In practice, we solve a regularized least-squared
problem. Regularizing toward an informed prior mean lets us handle long-tail
content, for which limited data is available. problem

$V_{a}=\operatorname*{arg\,min}_{V\in\mathbb{R}^{d}}\sum_{(u,R)\in\mathcal{D}_{a}}(V^{\top}u-R)^{2}.$

Recall from (1) that, through the dot product $\nu_{a}^{\top}u$, the original
item vector $\nu_{a}$ encodes a user’s propensity to have some interaction the
item, however brief it may be. At times, we call these “item clickiness
vectors.” In contrast, the item stickiness vector $V_{a}$ encodes the
propensity of users with certain tastes to return to item $a$ many times after
discovering it.

Stickiness vectors are trained not just on recent discoveries from banner
recommendations, but on discoveries from across the application and over a
fairly long time window. We gather enough data to do more than fine-tuning,
instead offering a new understanding of items in the catalog. This _data-
pooling_ is a key advantage to training the long-term model separately from
the short-term one.

####  3.1.4 Long-term recommendation logic

A myopic recommender values an impression of item $a$ by a given user $u$ by
$P_{w}(u_{t},x_{t},a)$, the estimated probability of a discovery given an
impression. Given the opportunity to make a recommendation, the most valuable
one is selected. Our proposed methods, instead, value impressions by their
expected long-term impact. For a user $u$, let
$S_{t}^{u}\supseteq\\{u_{t},X_{t}\\}$ represent all data the recommender has
about user $u$ at time $t$, i.e., the state of its knowledge. The quality
score of a recommendation action $a$ is set to

$\displaystyle
Q(S_{t}^{u},a)=\underbrace{P_{w}(u_{t},X_{t},a)}_{P(\text{discovery}\mid\text{impression})}\times\underbrace{\left(1+V_{a}^{\top}u_{t}\right)}_{1+\mathbb{E}[\text{returns}|\text{discovery}]}.$
(3)

This measures the expected number of show-active days that are attributable to
the impression. In Section 6 we show that, under appropriate assumptions, this
is indeed exactly equal to the $Q$-function in RL [Sutton and Barto, 2018].

####  3.1.5 A fine-tuned long-term model

To appreciate the methodology above, it may be helpful to offer a point of
comparison. Similar to the short-term fine-tuning presented in Section 3.1.2,
one could train a fine-tuned model that predicts a long-term and holistic
behavior, like the total number of active days on the app over the next sixty
days.444This metric is chosen solely for the purposes of illustration. We
overload notation and reuse the variable $R$, for total reward, to denote this
long-term outcome. Then, analogous to (2), a fine-tuned longer term model
could be trained by selecting the weights $w$ of a neural network $Q_{w}$ to
approximately solve

$\min_{w}\sum_{(\nu,u,x,R)\in\mathcal{D}}\big{(}Q_{w}\left([u,x],\nu\right)-R\big{)}^{2},$
(4)

where $\mathcal{D}$ is a dataset of past recommendations and corresponding
outcomes. This aims to directly approximate expected future reward when the
user is in a “state” represented by a concatenation of the user vector and the
current context, denoted $[u,x]$, and recommendation action is represented by
the item vector $\nu$. To avoid bias, it is essential that this method is
trained on recommendations $\mathcal{D}$ that are random conditioned on the
user vector and context.

Even with infinite data, direct-fine tuning is inherently limited by the
information reflected in current user and item vectors. Since these are
trained to encode a propensity for short-term interactions, they may not
capture the information that is needed to understand the differential long-
term benefit of particular recommendations. Our approach in (3) goes beyond
fine-tuning; It relies on stickiness vectors, a new understanding of items
reflecting users’ propensity to form long-term listening habits with them.

Putting aside issues of representation, the method in (4) may also struggle to
cope with measurement noise. Section 5 will demonstrate that the signal-to-
noise ratio may be too poor to detect the impact of individual recommendation
decisions on long-term holistic measures of user behavior. Our methodology,
which we formalize in Section 6, can be thought of as imposing conditional
independence assumptions that lead to the simpler formula for the $Q$-function
in (3). This simpler function depends on an existing short-term model and a
long-term model that predicts return days to a particular podcast. One helpful
feature is that the long-term model predicts return days to a particular
podcast, rather than to the app. Intuitively, which podcast a user discovers
may be strongly correlated with how often they return to _that podcast_ , but
only barely correlated with how often they return to _the app_ , since so many
other factors influence the latter quantity. Training the long-term model
separately from the short-term also helps alleviate measurement issues; See
the discussion of data pooling in Section 3.1.3.

####  3.1.6 Experimental results from a small A/B test

The first A/B test we describe involves results from show promotions on the
banner component displayed in Figure 3(a). Twelve markets were included in the
test. For each one, editors hand-picked between 3 and 74 shows that are
original and exclusive to Spotify. The test period lasts one week. During this
time, a single personalized recommendation of an eligible show is made to each
user in the test. For every user, we exclude from the candidate pool any show
that the user has already listened to in the past. Downstream activity is
observed for sixty days post-impression. Users are assigned to one of four
cells randomly.

Control.

In the control cell, a recommendation is made to maximize the predicted
probability of a stream as in Section 3.1.2.

Personalized.

In the long-term, personalized treatment cell, recommendation are determined
using the methodology described in Section 3.1.4.

Unpersonalized.

The long-term, unpersonalized treatment cell uses a personalized impression-
to-stream model, but predicts stickiness of item $a$ via an unpersonalized
estimate
$\bar{v}_{a}=\lvert\mathcal{D}_{a}\rvert^{-1}\sum_{(u,R)\in\mathcal{D}_{a}}R$,
instead of estimating vectors $V_{a}$ that enable personalized predictions.

Square-root.

The square-root, unpersonalized treatment cell maximizes the predicted
probability of a stream times the square-root of unpersonalized stickiness.
The square-root is a heuristic transformation that de-emphasizes stickiness
differences across items.

For approximately 37% of users, each of the four recommendation policies
select the same item at the time of the impression. (A contributing factor is
that the pool of candidates in a given market may be small.) We say that the
other 63% of users are _impacted_ by their randomized assignment to a
treatment cell. For each user that receives a recommendation, we measure three
quantities.

First stream.

Whether the user streamed from the recommendation or not. We use a 30-second
threshold to determine whether a stream has occurred or not.

60-day activity.

The number of days the user is active with the recommended show in the 60-day
window that starts from the day the user receives the recommendation.

60-day minutes.

The total number of minutes the user listened to the recommended show in the
same 60-day window.

Figure 4(a) shows average treatment effects among impacted users. There are
three main findings:

(a) User metrics

(b) 60-day minutes, normalized by Control

(c) Calibration of long-term value

Figure 4: Results from an online experiment on the Home banner.

  1. 1.

Optimizing for the long-term is different from optimizing for the short-term.
The long-term recommendation logic largely selected different items than
control. The number of first-streams of the recommended item, which is
purposefully optimized by control, was reduced by optimizing for the longer
term.

  2. 2.

Explicitly grappling with the long-term goal leads to large impact. Relative
to the control group, users in the long-term personalized treatment had an 81%
increase in 60-day show minutes and a 32% increase in 60-day show-active days.
Since these are average treatment effects, one might be concerned that it is
driven by a small cohort of users that listen for a disproportionately long
time. In fact, Figure 4(b) reveals that the treatment cell created many more
moderately engaged users. For instance, that figure shows that median 60-day
listening minutes were more than 80% larger in the long-term personalized cell
than in the control group.

  3. 3.

Causal assumptions were validated experimentally. The stickiness vectors
described in Section 3.1.3 were trained using data from users who discovered
the items anywhere on Spotify, including search. Our methodology assumed,
implicitly, that users who discovered the show through an advertisement on the
banner would have similar downstream behavior. Figure 4(c) confirms this. The
long-term predictions of our models are almost perfectly calibrated to the
results observed in the test.

####  3.1.7 A larger and longer experiment

A second experiment tested a larger and more persistent change in
recommendation logic. The horizontal row of recommendations labeled “Shows you
might like” in Figure 3(b) is called a _shelf_. Each item is called a _card_.
The first two cards of the shelf are immediately displayed on the screen, and
users can scroll to the right in order to reveal more cards. The experiment
ran for nine weeks, and during this time, the shelf was pinned near the top of
the screen, as illustrated in Figure 3(b). Two aspects distinguish this
experiment from the one described in Section 3.1.6. First, in this experiment
tens of thousands podcast shows are eligible to be recommended on the
shelf.555A candidate generation model returns a smaller, personalized pool of
approximately a hundred candidate shows for each user. In our experiment, this
model is fixed, and our intervention focuses on a second stage where the
candidates are ranked. As such, different recommendation policies almost
always result in a different ranking. Second, whereas the Home banner
experiment studied the impact of a single recommendation, in this experiment
we rank multiple recommendations at once. We display the shelf every time the
user opens the Home screen, over the entire duration of the test. As a
consequence, users have many opportunities to interact with the
recommendations, and we expect this experiment to exhibit a significantly
larger impact on users’ overall podcast habits. Users are assigned to one of
the following three cells, uniformly at random.

Control.

Users in the control cell received recommendations that were ranked in
decreasing order of predicted stream probability, similar to Section 3.1.2.

Personalized.

Users in the personalized long-term treatment cell received recommendations
that were ranked in decreasing order of the $Q$-values in Section 3.1.4.

Square-root.

Users in this cell received recommendations ranked in decreasing order
according a predicted impression-to-stream probability times the square-root
of a personalized stickiness estimate, similarly to the corresponding cell in
Section 3.1.6.

Given that the intervention we study encompasses a large number of
recommendation over a long period of time, we measure user metrics that
capture users’ overall engagement with podcasts on the platform. We focus on
the following three metrics.

Overall consumption in W8.

The total number of podcast minutes the user listened to during the week
leading to day 56 after first exposure.

Consumption from discoveries.

The total number of minutes the user listened to podcasts discovered anywhere
on the app during the first six weeks after first exposure.

At least one lasting discovery.

Whether the user discovered, anywhere on the app, at least one show that they
listened to  a) on at least three separate days, and  b) for at least 2 hours
in total,  during the first six weeks after first exposure.

Altering the ranking logic for that single shelf had a substantial impact, as
displayed in Figure 5(a). Week-8 overall podcast listening minutes on the app
were 1.7% greater among users in the long-term, personalized treatment cell.
Consumption from podcasts discoveries in the first six weeks increased by
6.2%. The number of users who had a “lasting” podcast discovery during that
time period increased by 5.4%. These results suggest that the insights
obtained using the clean but small intervention studied in Section 3.1.6 carry
over to practical, complex recommender systems: Explicitly driving podcast
recommendations towards long-term engagement leads to substantial impact.

In Figure 5(b) we plot the impact of the two treatment cells on the weekly
total number of podcast minutes consumed, as a function of the number of weeks
since users’ first exposure. The value at week 8 is identical to the metric
displayed in Figure 5(a) (left). This time series highlights the fact that the
rewards of successful recommendations early in the test take many weeks to
fully materialize. Measuring the effect of long-term policies at steady state
requires long-running experiments, and naive metrics measured early on might
severely underestimate the true long-term impact.

(a) User metrics

(b) Overall podcast consumption in $n$th week

Figure 5: Results from an online experiment on the Home podcast discovery
shelf.

###  3.2 Extension to item resurfacing

We have presented an approach to optimize recommendations of unfamiliar
items—those the user has never previously listened to. Inspired by the success
of these methods, we extend the approach to also optimize recommendations of
familiar items. There are two main challenges:

  1. 1.

Predictions of how often a user will return to an item need to be based on a
user’s past history with that item. We introduce content-relationship states,
which encode a user’s history with an item in a fixed-length vector. We then
extend stickiness vectors into stickiness models. These models forecast item
return days based not just on a user’s taste representation but also on their
relationship state with the item.

  2. 2.

It is subtle to properly attribute credit for downstream engagement. A user
might be expected to return to a familiar item many times regardless of
whether it is resurfaced on the banner today (we refer to this as _organic_
engagement). We address this through a counterfactual valuation logic in
Section 3.2.3.

####  3.2.1 Content-relationship states

We introduce a component of the user representation we call their _content-
relationship state_. A user $u$’s relationship state with item $a$ at time $t$
is a $k$-dimensional encoding $Z_{t,a}^{u}\in\mathbb{R}^{k}$ of their history
with the item. We set $Z_{t,a}^{u}=0\in\mathbb{R}^{k}$ if the user has never
listened to item $a$. When the catalog is large, $Z_{t}^{u}$ will be extremely
sparse. The state is updated recursively by applying some recurrent encoding
function $f$, as

$Z_{t+1,a}^{u}=f\left(Z_{t,a},C^{u}_{t,a}\right).$

The variable $C_{t,a}^{u}$ denotes the time the user spent listening to item
$a$ in period $t$. (The letter $C$ stands for “consumption.”) While $f(\cdot)$
could be learned, prototype implementations use a simple handcrafted encoding.
We update relationship sates as

$Z_{t+1,a}^{u}=\alpha\circ
Z^{u}_{t,a}+(1-\alpha)\circ\mathbbm{1}\left(C_{t,a}^{u}>0\right)$ (5)

where $\alpha\in[0,1]^{k}$ is a vector of forgetting factors and $\circ$
denotes componentwise multiplication. Each element of $Z_{t,a}^{u}$ is an
exponential moving average of listening indicators. When a varied range of
forgetting factors are used, the whole vector encodes the user’s level of
engagement with the item and how this has changed across time.

A few aspects of this state variable prove helpful. Unlike the user vector
$u_{t}$, which might be thought of as capturing the system’s understanding of
the user’s overall taste, the next content-relationship state $Z_{t+1,a}^{u}$
is highly sensitive to whether the user engages with that item. This lets us
think of recommendation actions as having long-term impact through their
impact on the user’s “state”. Next, reasoning about the next state in (5)
reduces to predicting an engagement indicator. This helps align with the
methodology in Section 3.1, which predicts whether the user streams an item
and not for how long.

In our prototype implementations, a time period represents a 24-hour period.
This is natural since we are emphasizing listening habits that form across
months.

####  3.2.2 Stickiness models

Section 3.1.3 defined the linear stickiness model
$V^{(a)}(u_{t})=V_{a}^{\top}u_{t}$. This models a user’s expected return days
to item $a$, forecasting from the time point at which they first try it. Put
differently, it applies when $Z_{t+1,a}^{u}=1-\alpha$. We extend this to a
stickiness model

$V^{(a)}(u_{t},Z_{t+1,a}^{u})=\mathbb{E}\left[\text{show-returns}\mid
u_{t},Z_{t+1,a}^{u}\right],$

which predicts the user’s return days to the item based on their engagement
state with it and the taste representation $u_{t}$.

####  3.2.3 Counterfactual valuation logic

Again, let $S_{t}^{u}\supseteq\\{u_{t},Z_{t}^{u},X_{t}\\}$ denote all data the
system has about user $u$ at time $t$, i.e., the state of its knowledge. We
assess the value of an impression of item $a$ through the score

$\displaystyle Q(S_{t}^{u},a)=$
$\displaystyle\underbrace{\Big{[}P(C_{t,a}>0|S_{t}^{u},\text{rec})-P(C_{t,a}>0|S_{t}^{u},\text{no
rec})\Big{]}}_{\text{impact of recommendation on stream probability}}$ (6)
$\displaystyle\qquad\qquad\times\underbrace{\left[\left(1+V^{(a)}(u_{t},Z_{t+1,a}^{u,+})\right)-\left(0+V^{(a)}(u_{t},Z_{t+1,a}^{u,-})\right)\right]}_{\text{impact
of stream on long-term engagement}}.$

The term $P(C_{t,a}>0|S_{t}^{u},\text{rec})$ denotes the probability that the
user streams item $a$ today if it is recommended on the banner. The
probability conditioned on _no rec_ , corresponding to organic streams, is
defined analogously. The variables

$\displaystyle Z_{t+1,a}^{u,+}$ $\displaystyle=\alpha\circ
Z_{t,a}^{u}+(1-\alpha)\circ 1,$ $\displaystyle Z_{t+1,a}^{u,-}$
$\displaystyle=\alpha\circ Z_{t,a}^{u}+(1-\alpha)\circ 0$

denote successor states that follow a stream and no-stream, respectively. The
formula values a recommendation based on based on two factors:  a) its
influence on whether a stream occurs today, and  b) whether stream and no-
stream events result in substantially different expected return days.

####  3.2.4 Intuitive understanding

To gain understanding, let us first compare the $Q$-value (6) to the discovery
logic (3) in Section 3.1.4. That logic applies in the special case where
$Z_{t,a}^{u}=0$. It keeps the term $\left(1+V^{(a)}(u_{t},1-\alpha)\right)$,
corresponding to the stickiness prediction when the user has just discovered
the item and $Z^{u,+}_{t,a}=1-\alpha$. The counterfactual value corresponding
to the user choosing not to try item $a$, leading to
$Z_{t,a}^{u,-}=0\in\mathbb{R}^{k}$, is ignored. Effectively, we assume that
$V^{(a)}(u,0)\approx 0$. The user is unlikely to have substantial future
activity with a particular item which they have never listened to previously.
The discovery logic also assumes that the impact of an individual
recommendation on the probability that item is listened to today is equal to
the chance that the user streams from the recommendation. Again, we are
assuming that the user is unlikely to try that particular item for the first
time, on that day, without the recommendation on the banner. Under these
approximations, the simplified expression (6) is identical to (3). These
approximations are no longer reasonable if the item is one the user already
listens to on a regular basis.

The goal is to build a service that helps users discover and, later, recall,
items they enjoy—signaled by their choice to return to it later. Among
unfamiliar items, high $Q$-values are associated with those the user is likely
to try, if recommended, and expected to return to, if they tried. High
$Q$-value might also be associated with resurfacing an item the user recently
tried or resurfacing an item the user once listened to frequently, but has not
listened to recently—if resurfacing is expected to re-activate their habit.
But lower $Q$-values might be associated with recommending an item the user
already engages with frequently. If expected active days are similar whether
or not the item is recommended on the banner today, then the _counterfactual
value_ is small.

####  3.2.5 Offline analysis

In order to build a qualitative understanding of different approaches to
recommending familiar content, and to illustrate the opportunities that our
counterfactual, long-term approach opens up, we analyze recurring interaction
data of Spotify users with three podcast shows. Similarly to the discovery
setting, we collect two datasets.

  1. 1.

The first dataset $\mathcal{D}=\\{A,u,Z_{a},\mathbbm{1}(Y>0)\\}$ contains
immediate outcomes to recommendations.

  2. 2.

For every item $a$, we gather a second dataset
$\mathcal{D}_{a}=\\{u,Z_{a},\mathbbm{1}(C_{a}>0),R\\}$ that contains user
state information, and immediate and long-term organic consumption.
$\mathbbm{1}(C_{a}>0)$ indicates a stream of item $a$ occurred on a given day,
and $R\in\\{0,59\\}$ is the number of return days, similarly to Section 3.1.3.

For purposes of illustration, we ignore $u_{t}$ and train non-parametric
models on an aggregated representation of the content-relationship state $Z$.
Letting $\mathcal{R}(z)$ be the set of all states in the same aggregation
region as $z$, we estimate the probability that a user in state $z$ streams
from a recommendation of content $a$ as

$\displaystyle P(a,z)$
$\displaystyle=\mathbb{E}_{\mathcal{D}}[\mathbbm{1}(Y>0)\mid
A=a,Z\in\mathcal{R}(z)],$

the probability that a user in state $z$ streams content $a$ organically as

$\displaystyle P(C_{a}>0\mid z,\text{no rec})$
$\displaystyle=\mathbb{E}_{\mathcal{D}_{a}}[\mathbbm{1}(C>0)\mid
A=a,Z\in\mathcal{R}(z)],$

and the expected return days of a user in engagement state $z$ as

$\displaystyle V^{(a)}(z)$ $\displaystyle=\mathbb{E}_{\mathcal{D}_{a}}[R\mid
A=a,Z\in\mathcal{R}(z)],$

where $\mathbb{E}_{\mathcal{D}}[\cdot]$ denotes the empirical average over
$\mathcal{D}$. Given these, we estimate the probability that a user in state
$z$ streams content $a$ given a recommendation as

$\displaystyle P(C_{a}>0\mid z,\text{rec})$
$\displaystyle=P(a,z)+[1-P(a,z)]\times P(C_{a}>0\mid z,\text{no rec}).$ (7)

Observe that, while learning $P(C_{a}>0\mid z,\text{rec})$ requires data from
a specific recommender system of interest, we are able to take advantage of
data from across the entire application to learn a model for $V$. This extends
the data-pooling benefit discussed in Section 3.1.3 to the resurfacing
setting. We discuss the causal assumptions implied by our modeling choices in
Section 3.2.6.

We visualize the patterns learned by these models in Figure 6. Each plot
represents values for a hypothetical user that has been using the Spotify
service for 4 weeks. The $xy$-axes corresponds to a two-dimensional projection
of the content-relationship state; For example, the cell at index $(2,3)$
corresponds to a user that was active 20% of the days in weeks 1 & 2, and 10%
of the days in weeks 3 & 4\. The value at a given cell is computed by
averaging model estimates corresponding to all engagement states with the
prescribed activity ratio during the two periods. Note that the bottom-left
corner, i.e., position $(1,1)$, corresponds to the engagement state associated
to the discovery setting (the user has never engaged with this item before).
The plots visualize the following quantities as a function of $z$, for all
three podcasts under consideration.

  * •

Figure 6(a) represents the factual and counterfactual probability of
streaming, $P(C_{a}>0\mid z,\text{rec})$ and $P(C_{a}>0\mid
z,\text{rec})-P(C_{a}>0\mid z,\text{no rec})$, respectively.

  * •

Figure 6(b) represents the factual and counterfactual long-term value,
$1+V^{(a)}(z^{+})$ and $[1+V^{(a)}(z^{+})]-[0+V^{(a)}(z^{-})]$, respectively,
where $z^{+}=\alpha\circ z+(1-\alpha)\circ 1$ and $z^{-}=\alpha\circ
z+(1-\alpha)\circ 0$.

  * •

Figure 6(c) represents the $Q$-value (6). This corresponds to the product of
the probability of streaming and long-term value counterfactuals.

(a) Probability of streaming

(b) Long-term value

(c) $Q$-value

Figure 6: Resurfacing quantities.

Collectively, these reveal several important insights. First, _counterfactual
reasoning is important_. Content that the user listened to recently is
systematically more likely to be streamed today, but a lot of these streams
would occur organically anyway, even without a recommendation. A similar
observation holds for the long-term value: High recent engagement is likely to
lead to high engagement in the future, irrespective of whether or not a stream
occurs today. In contrast, the counterfactuals (second row in Figures 6(a) and
6(b)) highlight that the highest _impact_ on short-term and long-term outcomes
is often obtained in lower engagement states.

Second, there is _significant heterogeneity across items and states_. Focusing
on Figure 6(c), we observe that, for a given state, there is a large
difference in the predicted impact of a recommendation across items. This is
most easily observed for the no-engagement state (bottom-left cell), for
example: A recommendation of Podcast 1 appears to be more valuable than the
two other items. Likewise, for any given item, there are substantial
variations in predicted impact across states, and the patterns are not
identical across shows. As a consequence, the relative ranking of items
depends on past engagement. While a recommendation for Podcast 1 has higher
value in the no-engagement state (bottom-left cell), a recommendation for
Podcast 3 has higher value for users who are in a high past-engagement, low
recent-engagement state (top-left cell). Similar observations hold for Figures
6(a) and 6(b).

Third, the _short-term counterfactual and full $Q$-value are misaligned_.
Reasoning about the downstream impact of short-term outcomes often leads to
distinctly different decisions. For example, Figure 6(a) seems to suggest that
recommending Podcast 3 to users with high recent engagement is always the best
course of action, by a large margin. In fact, Figure 6(c) reveals that, once
long-term impact is accounted for, there are item-state pairs that might lead
to recommendations with a larger impact.

####  3.2.6 Open questions around experimental evaluation

For the insights of the previous section to be verified experimentally, two
assumptions need to hold, at least approximately. First, similarly to the
discovery setting, the long-term value counterfactual,
$[1+V^{(a)}(z^{+})]-[0-V^{(a)}(z^{-})]$, learned using data from across the
app, should be an unbiased estimate of the causal impact of a recommendation-
induced stream. Second, for (7) to hold, whether the user streams from a
recommendation should be independent of whether the user streams organically,
for all engagement states. The second assumption is plausible if the
probability of streaming from a recommendation primarily reflects whether or
not the user pays attention to the recommendation.

The offline analysis in Section 3.2.5 helps justify the most important aspects
of our methodology. In particular, the analysis highlights the importance of
optimizing for the long-term, of counterfactual evaluation, and of capturing
heterogeneity across both items and user relationship states. For discovery
recommendations—a special case of the general methodology—A/B tests described
in Sections 3.1.6 and 3.1.7 validate causal assumptions and show large product
impact. For recommendations of familiar items, we do not yet have such
evidence. At the moment, it is not clear whether this is the best place to
invest engineering resources.666Resurfacing recommendation decisions are
highly sensitive to users’ recent engagement, such as whether users have
streamed an item today or yesterday. Computing the $Q$-value requires near-
real-time systems that maintain engagement states and compute recommendations
on-the-fly, at a significant engineering and infrastructure cost. In contrast,
discovery recommendations are less likely to be affected by recent engagement
and might be computed offline and in batch, e.g., at the start of every day.
One factor is that smarter resurfacing may have low potential to impact users
who have listened to very few shows. Nevertheless, we feel that it is quite
important, intellectually, to understand the methodology in a general way that
accommodates both discovery and resurfacing of familiar items. The general
methodology has a rigorous justification (Section 6), and it may have large
impact in the future or in other recommendation scenarios.

###  3.3 Key aspects of these prototypes

Let us reflect on a few key aspects of these prototypes. First, we focus on
_item-level habits_. Our machine learning algorithms model how recommendations
influence whether a user will return to a podcast show many times in the
future, instead of directly measuring overall engagement with the application.
This choice alleviates measurement challenges (see Sections 5.4 and 6.3 for
more discussion). This modeling decision is especially well suited to podcast
recommendation, where shows often release many episodes which overlap in terms
of topic, style, host, humor, etc. At a high level, the idea seems to extend
to recommender systems in other domains: users may attach to specific
creators, to journalists who write recurring newsletters, to freelancers who
they hire repeatedly, or, more abstractly, to genres of content.

Second, our prototypes use _a new item representation_ tailored to modeling
item-level habits. A more conventional approach would be to keep the
representation fixed but train a fine-tuned model to predict long-term
outcomes, as in Section 3.1.2. Similarly, papers on RL in recommendation
systems also often use existing representations to optimize for a different,
longer-term goal [see, e.g., Zheng et al., 2018, Ie et al., 2019b]. Our
stickiness models go further, and learn latent properties of items in the
catalog that are not captured by existing item vectors. It is worth commenting
that the training process in Section 3.1.3 is atypical. Training new embedding
is usually a substantial engineering endeavor which involves training a large
neural network on data from across the application. We sidestep some of this
effort in our prototypes by observing that, if the user vectors are fixed, the
training of item vectors decomposes into separate linear regression problems.

Finally, our prototypes introduce a _new component of the user representation_
that is, again, tailored to modeling item-level habits. The idea behind
content-relationship states is that the system should maintain a concise
encoding of users’ engagement pattern with specific items. These states
capture the system’s knowledge of the user’s relationship to the item. We
design them in such a way that a user’s engagement with the item today has a
predictable impact on the next relationship state, making it easy to integrate
existing short-term models with long-term value models. This short-term /
long-term decomposition is also key to unlocking the data pooling benefit.

##  4 Formal model

The testable prototypes and experimental results described above motivate
deeper study. How do the ‘states‘ and ‘$Q$-functions’ there connect to a full
reinforcement learning problem? What assumptions were implicit there? Is there
a sense in which the approach outperforms generic black-box RL algorithms? The
remainder of the paper provides a formal academic study of these questions.

In this section, we formulate the problem of optimizing recurring user
interactions using the language of reinforcement learning. Section 5 describes
a standard, unstructured, approach to policy improvement in such problems. We
leverage RL theory to offer insights into how coordination and attribution
challenges are addressed, but highlight that measurement challenges can be
crippling. Section 6 imposes structural assumptions that simplify the policy
improvement problem and alleviate measurement challenges. The solutions in
that section match the prototypes described already in Section 3, explaining
their underpinnings.

###  4.1 Motivation for modeling abstractions

To understand our modeling choices, it is helpful to recall one recommendation
task which served the basis an A/B test described in Section 3. Figure 3(a)
shows a screenshot of the Spotify mobile app. At the very top are shortcut
icons, making it easy for the user to return to key albums, playlists, or
podcasts. Just below that is a banner, which prominently recommends a
particular podcast to the user. The user may choose to scroll past the banner,
encountering further personalized recommendations. Through search results or
playlists — including mixed-audio playlists which incorporate talk audio —
they may encounter personalized recommendations of various items. Often, when
a user opens the app there will be no banner present.

We develop a stylized model that lets us explore the challenges described in
Section 1.1. Doing so requires abstracting away many of the complexities of a
real-world recommender system while maintaining the intellectually essential
elements. In our model, the user interacts with the app across discrete time
periods—thought of as separate days. Within a single day, they receive $L$
recommendations. Think of $L$ being a large number and of the user as skipping
over most recommendations without much thought given. We call
$\ell\in[L]=\\{1,\cdots,L\\}$ a _position_ , in rough analogy to the page
displayed in Figure 3(a), and focus on the logic that governs recommendations
at special position $\star\in[L]$, which might be thought of as the banner.
The same item may be recommended in several positions, reflecting that a user
may see the same recommendation multiple times within a day. Specialized and
loosely coordinated logic may govern the choice of the other $L-1$
recommendations. This model reflects that users may encounter recommendations
in varied ways throughout the day, and the logic that recommends a podcast on
the banner component may be distinct from the logic that places a short
podcast episode within a mixed-audio playlist.

In reality, components of a recommendation system may adapt recommendations in
response to a user’s activity earlier in the same day [Hidasi et al., 2016,
Beutel et al., 2018]. We abstract away from this, assuming all $L$ items are
picked based on information available at the start of the period. This choice
reflects that we are primarily interested in modeling impact over quite a long
time horizon—like multiple months—rather than the problem of creating a
rapidly responsive system.

Historical data is available from the recommender. This data reflects the
performance of an _incumbent policy_ , which is denoted by $\pi^{0}$. Our goal
is to use the historical data to improve upon the incumbent policy by
modifying a specific component: the rule that determines personalized
recommendations at position $\star$.

###  4.2 Optimizing repeated interactions with a single user

Table 1:  Symbols and notation introduced in Section 4.  Symbol | Domain | Description
---|---|---
$T_{0}$ | $\mathbb{Z}$ | Period at which user creates an account
$T_{1}$ | $\mathbb{Z}$ | Period at which user deactivates
$\gamma$ | $(0,1)$ | Independent retention rate
$X_{t}$ | $\mathbb{X}$ |  Context of user at time $t$
$L$ | $\mathbb{N}$ | Number of recommendations per period
$A_{t}$ | $\mathbb{A}^{L}$ |  Recommendations exposed to user at period $t$
$Y_{t}$ | $\mathbb{R}_{+}^{L}$ |  Consumption of user at period $t$
$H_{t}$ | $\mathbb{H}$ |  History of user prior to period $t$
$\omega$ | $\Omega$ | Unobservable type of user
$S_{t}$ | $\mathbb{S}\subseteq\mathbb{X}\times\mathbb{H}$ |  State of user at period $t$
$\pi(\cdot)$ | $\mathbb{S}\to\mathbb{A}^{L}$ | Recommendation policy
$R(\cdot,\cdot)$ | $\mathbb{R}_{+}^{L}\times\mathbb{A}^{L}\to\mathbb{R}$ |  Reward function, applied to $(Y_{t},A_{t})$
$\pi^{0}(\cdot)$ | $\mathbb{S}\to\mathbb{A}^{L}$ | Incumbent recommendation policy
$\star$ | $[L]$ | Recommendation position under consideration
$\pi_{\star}(\cdot)$ | $\mathbb{S}\to\mathbb{A}_{\star}$ | Policy component for position under consideration
Figure 7:  Graphical representation of user behavior model.

$X_{0}$$H_{0}$$A_{0}$$Y_{0}$$X_{1}$$H_{1}$$A_{1}$$Y_{1}$$X_{2}$$H_{2}$$A_{2}$$Y_{2}$

Consider a particular user of a recommendation system, viewed as being drawn
at random from a population of users. The user creates an account at period
$T_{0}$, de-activates at some period $T_{1}$, and in between they interact
with the recommender on each period. We assume that a user’s lifetime is
geometrically distributed, with $T_{1}-T_{0}\mid T_{0}\sim{\rm
Geometric}(1-\gamma)$ for $\gamma\in(0,1)$. This choice lets us mimic
discounted objectives; see Remark 1. We further assume that a user’s lifetime
is independent of all else, including the recommender’s decisions. A choice to
disengage due to poor recommendations can still by modeled through a user’s
decision to consume no content in the future due to past decisions.

In each period $t\in\\{T_{0},\cdots,T_{1}\\}$, the user is in some context
$X_{t}\in\mathbb{X}$ and observes a collection of recommendations
$A_{t}=(A_{t,1},\cdots,A_{t,L})\in\mathbb{A}^{L}$ where $\mathbb{A}$ is finite
list of items. The user engages with item $\ell$ for
$Y_{t,\ell}\in\mathbb{R}_{+}$ seconds, with $Y_{t,\ell}=0$ indicating the item
is immediately skipped. Let $Y_{t}=(Y_{t,1},\cdots,Y_{t,L})$. We assume the
user does not listen to items that are not recommended777This assumption is
more innocuous than it may appear at first. In our model a large number of
recommendations per day (i.e. $L-1$) are governed by some logic that we cannot
influence. Search results can be thought of an extension where a user provides
a query which seeds some components of these recommendations. Adding user
queries to the model seems to complicate the presentation without yielding new
insights..

The sequence of contexts $(X_{t}:t\in\\{T_{0},\cdots,T_{1}\\})$ follows an
exogenous Markov chain, representing factors like a user’s age, device, or the
day of the week. Formally, conditioned on $X_{t}$, $X_{t+1}$ is independent of
$A_{t}$ and $Y_{t}$ as well as all prior contexts, recommendations, and
streaming decisions.

##### User behavior.

The user’s response to recommendations $A_{t}$ is influenced by their history
prior to day $t$,
$H_{t}=\\{(X_{\tau},A_{\tau},Y_{\tau}):\tau\in\\{T_{0},\cdots,t-1\\}\\}\in\mathbb{H}$,
the context $X_{t}$, a latent and unobservable type of the user
$\omega\in\Omega$, and an unobservable shock $\xi_{t}\in\Xi$ drawn
independently and identically across time and independently from all else.
Formally, there is some fixed function $\psi$ that determines the user
response as

$Y_{t}=\psi(H_{t},A_{t},X_{t},\omega,\xi_{t}).$

The variable $\xi_{t}$ is meant to capture idiosyncratic randomness in user
behavior. The latent type $\omega$ is meant to model persistent user
preferences that are unknown to the recommender but might be partially
inferred from their behavior. Since the user is randomly drawn from a
population, $\omega$ is a random variable. The dependence of future behavior
on a user’s history means that recommendations in one period can influence the
efficacy of recommendations in the future. Our algorithms do not explicitly
model $\psi$, but it may help the reader to understand structural assumptions
of Section 6 as, at least implicitly, restricting the form of $\psi$.

##### Exhaustive state representation.

The exhaustive encoding of the state of a user includes all information
available to the recommender at time $t$ as $S_{t}=(X_{t},H_{t})$. If
$t\notin\\{T_{0},\cdots,T_{1}\\}$, indicating the user is inactive, we write
$S_{t}=\varnothing$. Take $\mathbb{S}$ to be the set of possible states
excluding the null state. The recommender’s action $A_{t}$ is necessarily a
function of the state variable, and perhaps some exogenous randomness, since
it has no other information on which to base its decisions. This state
variable trivially obeys the Markov property
$\operatorname*{\mathbb{P}}(S_{t+1}\in\cdot\mid
S_{t},A_{t})=\operatorname*{\mathbb{P}}(S_{t+1}\in\cdot\mid
S_{1},A_{1},\cdots,S_{t},A_{t})$, since $S_{t}$ encodes all information in
$(A_{1},S_{1},\cdots A_{t-1},S_{t-1})$. Practical algorithms need a more
parsimonious state description: for instance our prototypes can be understood
as tracking a state variable is the concatenation of a user’s taste vectors
and their content-relationship states.

Viewing the state variable as reflecting the state of the decision-maker’s
knowledge is classical in treatments of partially observable Markov Decisions
Processes [Bertsekas, 2012, Chapter 4]; See Sutton and Barto [2018, Chapter
17.3] or Lu et al. [2021] for a discussion of encoding the history as a state
variable.

##### Recommendation policies.

A randomized policy is a function
$\pi:\mathbb{S}\times\Xi^{L}\to\mathbb{A}^{L}$ which associates a state in
$\mathbb{S}$ and an exogenous noise vector in $\Xi^{L}$ with a sequence of
items. We take $\pi_{\ell}:\mathbb{S}\times\Xi\to\mathbb{A}$ to be the $i^{\rm
th}$ component of a policy. Our goal will be to optimize $\pi_{\star}$, where
$\star\in[L]$ denotes the position under consideration, while treating
components $\pi_{\smallsetminus\star}=(\pi_{\ell}:\ell\neq\star)$ as fixed. We
focus on rules $\pi_{\star}$ with restricted range
$\mathbb{A}_{\star}\subset\mathbb{A}$. Here $\mathbb{A}_{\star}$ is a filtered
subset of a catalogue that is eligible888For loose motivation, consider the
screenshots in Figure 3. The user interface arranges items in a two-
dimensional grid. Each row lists a restricted recommendation hypothesis, like
_Recently played_. Another row might restrict to podcast shows (_Shows you
might like_) or personalized music playlists (_Made for you_). We imagine that
some preliminary logic selects a subset of items that align with the title of
the row and are eligible to be recommended there. for placement at position
$\star$. Without loss of generality, take $\star=1$ so
$\pi=(\pi_{\star},\pi_{\smallsetminus\star})$.

We define the exogenous randomness formally as follows. There is an i.i.d.
collection of random variables
$\epsilon=(\epsilon_{t,\ell}:t\in\\{\cdots,-1,0,1,\cdots\\},\ell\in[L])$
taking values in $\Xi$, such that
$A_{t,\ell}=\pi_{t,\ell}(S_{t},\epsilon_{t,\ell})$. Assume that the
algorithm’s internal randomness $\epsilon$ is independent from the random
shocks $(\xi_{t}:t\in\\{\cdots,-1,0,1,\cdots\\})$ that influence user
behavior. We assume that the incumbent recommendation policy has a nonzero
chance of selecting each action in each state. One can interpret this as a
source of exploration and unbiased training data. Much of our motivation for
making Assumption  ‣ 4.2 is expository. See Remark 2 below.

######  Assumption 0 (Randomness in action selection).

For each $s\in\mathbb{S}$,
$\operatorname*{\mathbb{P}}(\pi_{\star}^{0}(s,\epsilon_{t,\star})=a_{\star})>0$
for each $a_{\star}\in\mathbb{A}_{\star}$.

##### Reward and value functions.

The holistic reward function
$R:\mathbb{R}_{+}^{L}\times\mathbb{A}^{L}\to\mathbb{R}$ associates a user’s
daily interactions with a measure of success. A policy $\pi$ has value
function $V_{\pi}:\mathbb{S}\cup\\{\varnothing\\}\to\mathbb{R}$ defined as

$V_{\pi}(s)=\mathbb{E}_{\pi}\left[\sum_{\tau=t}^{T_{1}}R(Y_{\tau},A_{\tau})\mid
S_{t}=s\right]\qquad\text{for all }s\in\mathbb{S},$ (8)

with $V_{\pi}(\varnothing)=0$. The subscript $\pi$ indicates that actions are
selected according to $\pi$. That $s\in\mathbb{S}$ implies it is not the null
(inactive) state. If
$R(Y_{t},A_{t})=\mathbbm{1}(\sum_{\ell=1}^{L}Y_{t,\ell}>0)$ is an indicator of
activity in the period, then the sum of rewards assesses habitual use of the
service. In that case, the value-to-go $V_{\pi}(s)$ measures whether habitual
use is expected given a user’s state. A value function defines a partial order
policies, with one policy outperforming another if it offers higher value-to-
go for every possible state. It is sometimes helpful to also consider a scalar
objective function,

$J(\pi)=\operatorname*{\mathbb{E}}\left[V_{\pi}(S_{T_{0}})\right],$ (9)

which considers the average lifetime reward for a new user.

######  Remark 1 (Implicit discounting).

The formulation defines an interaction protocol that could be used to generate
an infinite trajectory
$(S_{t},A_{t},Y_{t}:t\in\\{T_{0},T_{0}+1,T_{0}+2,\cdots\\})$. By integrating
over the random, geometric lifetime $T_{1}-T_{0}$, which is independent of
this trajectory, one can show that

$V_{\pi}(s)=\mathbb{E}_{\pi}\left[\sum_{\tau=t}^{\infty}\gamma^{\tau-t}R(Y_{\tau},A_{\tau})\mid
S_{t}=s\right]\qquad\text{for all }s\in\mathbb{S}.$

By creating a model in which users deactivate with probability $1-\gamma$
independently in each period, we effectively formulate a problem with a
discounted infinite horizon objective.

######  Remark 2 (Causal interpretation of conditional expectations).

Consider the difference in a user’s chance of engaging with the recommendation
at position $\star$ under two possible recommendations:

$\mathbb{P}_{\pi^{0}}(Y_{t,\star}>0\mid
A_{t,\star}=a_{\star},S_{t})-\mathbb{P}_{\pi^{0}}(Y_{t,\star}>0\mid
A_{t,\star}=a^{\prime}_{\star},S_{t}).$

These conditional probabilities are well defined due to Assumption  ‣ 4.2.
Because, conditioned on the state, the recommendation at position $\star$ is a
function of exogenous randomness specific to that decision, the difference
above can be thought of as the causal impact of choosing to recommend item
$a_{\star}$ rather than $a^{\prime}_{\star}$. In particular, in the notation
of Pearl [2009],

$\mathbb{P}_{\pi^{0}}(Y_{t,\star}>0\mid
A_{t,\star}=a_{\star},S_{t})=\mathbb{P}_{\pi^{0}}(Y_{t,\star}>0\mid
do\left(A_{t,\star}=a_{\star}\right),S_{t}).$

For this reason, we are able to avoid specialized causal inference notation
like that of Pearl [2009] or Rubin [1974] throughout the paper. The focus on
the event $\\{Y_{t,\star}>0\\}$ was for concreteness only. An analogous
statement holds for any event depending only on the user’s future
recommendations and behavior.

###  4.3 Learning an improved policy from logged user trajectories

Our work fits more naturally into an _offline_ reinforcement learning
formulation. We are given access to a batch of trajectories of user
interactions

$\mathcal{D}=\\{(S_{t}^{u},A_{t}^{u},Y_{t}^{u}):t\in\\{T_{0}^{u},\cdots,T_{1}^{u}\\}\\}_{u\in
U},$ (10)

ranging over users in a finite set $U$ whose interactions were with an
_incumbent policy_ $\pi^{0}$. Our ultimate system will need to involve
quantities that can be estimated using such data. For this reason, we do not
frame our objective as one of identifying the optimal recommendation
policy999This might require inferring how users would respond if their
interactions with the app were radically different..

Our goal, roughly speaking, is to increase the lifetime average reward in (9)
by adjusting the recommendation policy at position $\star$. To describe this
concretely, we introduce the partial state-action value function
$Q_{\pi^{0}}:\mathbb{S}\times\mathbb{A}_{\star}\to\mathbb{R}$ defined by

$Q_{\pi^{0}}(s,a_{*})=\mathbb{E}_{\pi^{0}}\left[\sum_{t=0}^{T_{1}}R(Y_{t},A_{t})\mid
S_{0}=s,A_{0,\star}=a_{\star}\right].$ (11)

This measures the expected remaining lifetime reward when item $a_{\star}$ is
recommended at position $\star$ to a user whose current state is $s$ and the
incumbent policy $\pi^{0}$ is used to determine recommendations at other
positions and in future time-periods. Since the $Q$–function in (11) is
defined by an expectation under the incumbent policy, there is hope of
approximating it using the logged data $\mathcal{D}$.

While (11) appears to consider a single period decision-problem, it can be
used to derive policies with superior performance in long-horizon problems. In
particular, the policy iteration update $\pi^{+}$, defined by
$\pi_{\star}^{+}(s)\in\operatorname*{arg\,max}_{a_{\star}\in
A_{\star}}Q_{\pi^{0}}(s,a_{\star})$ and $\pi_{\ell}^{+}(s)=\pi^{0}_{\ell}(s)$
for $\ell\neq\star$, satisfies $V_{\pi^{+}}(s)\geq V_{\pi^{0}}(s)$ for every
$s\in\mathbb{S}$ [Bertsekas, 2012]. This implies
$J([\pi^{+}_{\star},\pi_{\smallsetminus\star}^{0}])\geq
J([\pi^{0}_{\star},\pi_{\smallsetminus\star}^{0}])$. We aim to approximate
$\pi^{+}$ using logged data.

######  Remark 3 (On terminology).

Much of the offline RL literature calls $\pi^{0}$ either a “behavioral
policy”, or a “logging policy”. We use the term incumbent policy to emphasize
that it represents not just the data collection rule but also the natural
benchmark against which the performance of other policies is judged.

##  5 A direct, unstructured, policy improvement approach

This section describes a simple and direct approach to improving a component
of the recommendation policy: fit a parametric approximation to the
$Q$-function in (11) and then adjust the recommendation policy toward actions
with higher $Q$-values. In the reinforcement learning literature, this is
referred to as an _actor-critic_ method [Sutton et al., 1999, Konda and
Tsitsiklis, 1999]. Unstructured approaches are popular. Using some fixed-
length representation of user’s states101010For instance, the concatenation of
the user vectors mentioned in Section 3 and some handcrafted features provides
a natural starting point., one might train a fully connected neural network to
minimize empirical error in the definition (11) and then maximize this
$Q$-function. The literature review describes several papers which apply such
an approach to recommender systems. Does this adequately address the
measurement, attribution, and coordination challenges highlighted in Section
1.1?

We derive rigorous insights in the case where $Q$-functions are approximated
using state-aggregation, a special kind of parametric approximation. Several
appealing features of the direct estimation approach come into focus: it is
naturally implemented using the logged data in $\mathcal{D}$ (Section 5.1), it
works gracefully in a decentralized setting (Section 5.2), and it seems to
address attribution challenges in a coherent way (Section 5.3). Unfortunately,
a key remaining challenge also comes into focus: a poor signal-to-noise ratio
leads to impractical data requirements and limits personalization. This
insight then motivates Section 6, which imposes structural assumptions that
simplify $Q$-function estimation and yield the prototypes described in Section
3.

We believe the main insights in this section apply to many kinds of parametric
approximations used in practice, not just to state-aggregation. The theory of
actor-critic methods that we rely on in Sections 5.1-5.3 was originally
developed (in a slightly different form) for more complex function
approximation [Sutton et al., 1999, Konda and Tsitsiklis, 1999]. The poor
signal-to-noise ratio highlighted in Section 5.4 is a fundamental feature of
the training label; it seems just as relevant to neural network based
approximation as to state-aggregation.

###  5.1 An approximate policy improvement update via logged data

Because a user’s state is represented by the exhaustive history of their
interactions, it is possible that no two users share an identical state. A
successful recommender system needs to recommend items to users that were
liked by users with _similar_ states. How does this fit with the goal of
policy improvement described in the previous section? Here we introduce the
reader to ideas of approximation and generalization in policy improvement by
considering state-aggregated policies, a simple form of approximation that has
been studied for decades [Whitt, 1978, Bean et al., 1987, Singh et al., 1995,
Gordon, 1995, Tsitsiklis and Van Roy, 1996, Rust, 1997, Li et al., 2006, Jiang
et al., 2015].

Under a state-aggregated policy, the state space is partitioned into segments,
and users whose states fall into a common segment receive the same
recommendation. Fix a rule $\phi:\mathbb{S}\to\\{1,\cdots,m\\}$ which assigns
each state to one of $m$ segments. We stay agnostic to the choice of $\phi$,
determining how the state-space is partitioned, but one could imagine applying
a standard procedure to cluster user-vectors, like those described in Appendix
A. We say $\phi$ is _non-degenerate_ if there are no empty user clusters, i.e.
$\mathbb{E}_{\pi^{0}}\left[\sum_{t=T_{0}}^{T_{1}}\mathbbm{1}\\{\phi(S_{t})=i\\}\right]>0$
for each $i\in[m]$.

For a given non-degenerate aggregation rule $\phi:\mathbb{S}\to[m]$, define
the state-aggregated value function
$\bar{Q}_{\pi^{0}}:[m]\times\mathbb{A}_{\star}$ by

$\bar{Q}_{\pi^{0}}(i,a)=\frac{\mathbb{E}_{\pi^{0}}\left[\sum_{t=T_{0}}^{T_{1}}Q_{\pi^{0}}(S_{t},a)\mathbbm{1}\\{\phi(S_{t})=i\\}\right]}{\mathbb{E}_{\pi^{0}}\left[\sum_{t=T_{0}}^{T_{1}}\mathbbm{1}\\{\phi(S_{t})=i\\}\right]}\quad\forall
i\in[m],a\in\mathbb{A}_{\star}.$ (12)

This can be thought of as a regression-based approximation to the
$Q$-function. Among all state-aggregated functions,
$\bar{Q}(\cdot,a):\mathbb{S}\to\mathbb{R}$ minimizes the mean-squared error
metric $\mathbb{E}_{s\sim
w}(\bar{Q}_{\pi^{0}}(\phi(s),a)-Q_{\pi^{0}}(s,a))^{2}$ where
$w(s)\propto\mathbb{E}_{\pi^{0}}\left[\sum_{t=T_{0}}^{T_{1}}\mathbbm{1}\\{S_{t}=s\\}\right]$.
See Appendix C.2 for details.

Whereas the exact policy iteration update requires representing the value of
each action at each possible state, forming the approximation in (12) requires
computing $|\mathbb{A}_{\star}|\cdot m$ averages. Crucially, the averages are
computed under the distribution of states visited by the incumbent policy,
which is exactly the data we have access to in $\mathcal{D}$. Algorithm 1
shows how to build a sample based approximation to this policy improvement
problem, based on the definition of the $Q$-functions in (11).

Algorithm 1 Direct, locally optimal, state-aggregated policy improvement

Aggregation rule $\phi:\mathbb{S}\to[m]$, dataset of user trajectories
$\\{(S_{t}^{u},A_{t}^{u},Y_{t}^{u}):t\in\\{T_{0}^{u},\cdots,T_{1}^{u}\\}\\}_{u\in
U}$, reward function $R$. $i\in[m]$$a\in\mathbb{A}_{\star}$

$\mathcal{D}_{i,a}=\\{(u,t):\phi(S_{t}^{u})=i\,,\,A_{t,\star}^{u}=a\\}$.

$\hat{Q}^{\rm
direct}\left(i,a\right)=\frac{1}{|\mathcal{D}_{i,a}|}\sum_{(u,t)\in\mathcal{D}_{i,a}}\left(\sum_{\tau=t}^{T_{1}^{u}}R(A_{\tau}^{u},Y_{\tau}^{u})\right)$.

Pick
$\hat{a}_{i}\in\operatorname*{arg\,max}_{a\in\mathbb{A}_{\star}}\hat{Q}^{\rm
direct}(i,a)$ Return $\hat{Q}^{\rm direct}$ and
$(\hat{a}_{1},\cdots,\hat{a}_{m})$ defining a policy.

###  5.2 How coordination challenges are addressed

Classical theory of dynamic programming covers policy iteration methods that
optimize the true $Q$-function at every state. This subsection interprets
methods that optimize the simplified approximate $Q$-function in (12) as
performing _coordinate ascent_ : they produce a steepest ascent update to a
component of the recommendation policy, within a restricted class of policies.
This is accomplished naturally by fitting $Q$-functions on data generated by
the incumbent policy.

Coordinate ascent is a _decentralized_ method if not a _coordinated_ one. It
optimizes a component of the recommendation system in the context of how the
rest of the system behaves. A coordinated solution might instead change many
parts of the system to attain a goal. To appreciate this distinction, consider
our podcast discovery prototypes from Section 3. Those methods predict whether
a user is likely to form a listening habit with a podcast show if the try it
once. Implicitly, this depends not just on the user’s tastes, but on the
incumbent policy of the recommender system, which influences whether
subsequent recommendations resurface that show to the user.

The rest of this subsection makes the coordinate ascent interpretation formal.
First, the definition below formally defines a set of deterministic state-
aggregated policies which may deviate from the incumbent policy at position
$\star$ but not at other positions.

######  Definition 1.

A state aggregation rule is a map $\phi:\mathbb{S}\to[m]$. For a given
aggregation rule $\phi$, take $\Pi_{\star}^{\phi}$ to be the set of all
policies of the form $\pi=(\pi_{\star},\pi_{\smallsetminus\star})$ such that
$\pi_{\star}(s,\epsilon_{t,\star})$ does not depend on the idiosyncratic
randomness $\epsilon_{t,\star}$ and depends on $s$ only through $\phi(s)$.
Each such policy can be represented by $m$ actions
$a_{1},\cdots,a_{m}\in\mathbb{A}_{\star}$ with
$\pi_{\star}(s,\epsilon_{t,\star})=a_{\phi(s)}$ almost surely for each
$s\in\mathbb{S}$.

Recall the performance measure
$J(\pi)=\operatorname*{\mathbb{E}}[V_{\pi}(S_{T_{0}})]$ represents the average
cumulative reward across a user’s lifetime interactions. For a policy
$\pi^{\prime}\in\Pi_{\star}^{\phi}$, take ${\rm
Mix}(\pi^{\prime},\pi_{0},\beta)$ to be a policy that, independently in each
period, selects the action $\pi^{\prime}_{\star}(S_{t},\epsilon_{t,\star})$
with probability $\beta$ and otherwise selects
$\pi^{0}_{\star}(S_{t},\epsilon_{t,\star})$. Consider the local policy
improvement problem,

$\pi^{+}\in\operatorname*{arg\,max}_{\pi\in\Pi_{\star}^{\phi}}\,\frac{d}{d\beta}\,J\left(\,{\rm
Mix}(\pi,\pi_{0},\beta)\,\right)\bigg{|}_{\beta=0},$ (13)

which aims to attain the steepest rate of improvement in lifetime reward among
all state-aggregated policies. The randomization in ${\rm
Mix}(\pi^{\prime},\pi_{0},\beta)$ is not an essential part of the current
paper. One should think of this a formal device for studying _small_
alterations of the user experience.111111The theory of policy gradient methods
clarifies when the derivative with respect to $\beta$ accurately captures also
the change for moderate values of $\beta$. The major concern is distribution
shift, where altering component $\pi_{\star}$ substantially alters the
fraction of users whose states fall within various clusters. See the
discussion in Schulman et al. [2015], or, for precise expressions, see the
proof in Appendix C.4. The next lemma shows that $\pi^{+}$ is the maximizer of
an approximate $Q$-function. This result is a modified version of the “actor-
critic” form of the policy gradient theorem, first discovered by Sutton et al.
[1999] and Konda and Tsitsiklis [1999]. Theorem 8 in Russo [2020] provides a
result that is almost analogous to this one. For completeness, we provide a
proof in Appendix C.5.

######  Lemma 1.

For a given non-degenerate aggregation rule $\phi:\mathbb{S}\to[m]$, consider
the state-aggregated value function
$\bar{Q}_{\pi^{0}}:[m]\times\mathbb{A}_{\star}$ defined in (12). A policy
$\pi^{+}\in\Pi_{\star}^{\phi}$ represented by actions
$(a^{(1)},\cdots,a^{(m)})$ solves (13) if and only if

$a^{(i)}\in\operatorname*{arg\,max}_{a\in\mathbb{A}_{\star}}\bar{Q}_{\pi^{0}}(i,a)\quad\text{for
each }i\in[m].$ (14)

###  5.3 How attribution challenges are addressed

Attribution challenges are also addressed coherently. Credit for selecting
action $\pi^{\prime}_{\star}(S_{t},\epsilon_{t})$ rather than the prescribed
action $\pi^{0}_{\star}(S_{t},\epsilon_{t})$ is assigned based on the
difference in fitted $Q$-values under those actions. This difference is often
called an _advantage_ in RL. The next lemma shows that, in expectation, the
cumulative sum of credited values equals the true difference in long-term
value, up to a second order term. This property is similar to what Singal et
al. [2022] call _counterfactual efficiency_ in their axiomatic approach to
coherent attribution. The term that is $O(\beta^{2})$ depends on the degree of
distribution shift and is described explicitly in Appendix C.4.

######  Lemma 2 (Specialization of the policy gradient theorem).

For a policy $\pi^{\prime}\in\Pi^{\phi}_{\star}$,

$\underbrace{J({\rm
Mix}(\pi^{\prime},\pi^{0},\beta))-J(\pi^{0})}_{\text{Change in long-term
value}}=\beta\mathbb{E}_{\pi^{0}}\left[\sum_{t=T_{0}}^{T_{1}}\underbrace{\left(\bar{Q}_{\pi^{0}}\left(\phi\left(S_{t}\right),\pi^{\prime}_{\star}(S_{t},\epsilon_{t,\star})\right)-\bar{Q}_{\pi^{0}}\left(\phi\left(S_{t}\right),\pi^{0}_{\star}(S_{t},\epsilon_{t,\star})\right)\right)}_{\text{Estimated
advantage of }\pi^{\prime}\text{ over }\pi^{0}\text{ at
}S_{t}}\right]+O(\beta^{2}).$

###  5.4 Crippling measurement challenges

We introduced an actor-critic algorithm which implements a coordinate-ascent
step by selecting recommendations according to an approximate $Q$-function.
The last two subsections gave insights into how this approach deals with
attribution and decentralization challenges. But the approach has a crippling
limitation: an enormous amount of data per user cluster is required to
adequately estimate the $Q$-function. Conventional myopic recommendation
strategies ignore long-term impact, but require far less data. The reduced
data requirements allow one to reliably use a finer clustering and hence offer
greater personalization. We construct an example that lets us demonstrate this
phenomenon rigorously. The conclusion is stated informally below:
Under a simple model of user and recommendation behavior (which will be
described in Example 1), both the policy returned by the long-term actor-
critic algorithm (Algorithm 1) and the policy returned by a myopic
optimization (descibed in Algorithm 2) would, with enough data, converge on
applying the same action in the $i^{\rm th}$ user segment. However, the long-
term estimation in Algorithm 1 requires data from
$L\times\operatorname*{\mathbb{E}}[T_{1}-T_{0}]$ times as many users. Data
requirements expand by a factor of the number of recommendations a user
receives throughout their lifetime—a potentially enormous factor.

##### A naive myopic algorithm.

We compare the data requirements of the long-term recommendation logic in
Algorithm 1 to a more naive alternative defined below in Algorithm 2. The
baseline approach measures the engagement with the recommendation in the
current period. It attributes all credit for that immediate engagement back to
the recommendation and attributes no credit for downstream engagement to the
recommendation.

Algorithm 2 Naive state-aggregated policy evaluation

Aggregation rule $\phi:\mathbb{S}\to[m]$, dataset of user trajectories
$\\{(S_{t}^{u},A_{t}^{u},Y_{t}^{u}):t\in\\{T_{0}^{u},\cdots,T_{1}^{u}\\}\\}_{u\in
U}$. $i\in[m]$$a\in\mathbb{A}_{\star}$

$\mathcal{D}_{i,a}=\\{(u,t):\phi(S_{t}^{u})=i\,,\,A_{t,\star}^{u}=a\\}$.

$\hat{Q}^{\rm
naive}\left(i,a\right)=\frac{1}{|\mathcal{D}_{i,a}|}\sum_{(u,t)\in\mathcal{D}_{i,a}}Y_{t,\star}^{u}$.

Pick
$\hat{a}_{i}\in\operatorname*{arg\,max}_{a\in\mathbb{A}_{\star}}\hat{Q}^{\rm
naive}(i,a)$

Return $\hat{Q}^{\rm naive}$ and $(\hat{a}_{1},\cdots,\hat{a}_{m})$.

##### An example with repeated interactions.

Even with infinite data, Algorithm 2 does not properly capture the long-term
impact of recommendations. To sidestep this issue and focus solely on issues
of measurement, we consider a simple example in which Algorithms 1 and 2
eventually converge to the same estimates, but exhibit different variances
with finite datasets.

In this example, recommendation decisions have no delayed impact. Moreover,
there is no interaction between user responses to recommendations made at
different positions. To optimize cumulative long-term reward, it is enough to
always maximize immediate engagement with the recommended item. In this
example, there is a special item which users in cluster $i$ engage with for
$\Delta$ seconds longer, on average, than with all other items.

######  Example 1 (Repeated independent interactions).

Consider a very simple process under which $\phi(S_{t})=\phi(S_{t+1})$ almost
surely for $t+1\leq T_{1}$. This occurs if the cluster to which a user is
assigned is based on variables like their device, rather than their
interaction history. Suppose that $\pi^{0}_{\star}$ has the following form:
when $\phi(S_{t})=i$, i.e. state $S_{t}$ falls in the $i^{\rm th}$ partition,
it flips a coin with bias $1-\epsilon$. If the coin lands heads (which occurs
with probability $1-\epsilon)$ it picks the action $\tilde{a}^{i}$. If the
coin lands tails, it picks an action uniformly at random from
$\mathbb{A}_{\star}$. There is special action $a^{i}_{\rm
opt}\neq\tilde{a}^{i}$, which is the optimal choice in cluster $i$.

Assume that $R(Y_{t},A_{t})=\sum_{\ell=1}^{L}Y_{t,\ell}$ is the total
engagement time. Assume that there is an i.i.d. sequence of latent random
variables $\tilde{Y}_{t,\ell}$ with variance $\sigma^{2}$, drawn independently
of all else, and a special action $a^{i}_{\rm opt}\in\mathbb{A}_{\star}$ such
that $Y_{t,\ell}=\tilde{Y}_{t,\ell}+\Delta\mathbbm{1}\\{A_{t,\ell}=a^{i}_{\rm
opt}\wedge\ell=\star\\}$. That is, all items are equal, except a single one
which offers an increase in immediate reward of $\Delta$ if recommended in
position $\star$.

##### Formal statement.

The next lemma shows formally that Algorithms 1 and 2 would eventually
converge on the same recommendation strategy, but the standard errors of the
local and myopic estimates are much smaller. The proof of this result is given
in Appendix D.1. The symbol $\overset{d.}{\longrightarrow}$ is used for
convergence in distribution.

######  Lemma 3.

Consider Example 1 and the estimates $\hat{Q}^{\rm direct}$ and $\hat{Q}^{\rm
naive}$ returned, respectively, by Algorithms 1 and 2 applied to a common
dataset of user-interactions collected under policy $\pi^{0}$. Take
$U_{i}=\\{u\in U:\phi(S_{T_{0}^{u}}^{u})=i\\}$ to be the set of users in
cluster $i$, and let $a\notin\\{\tilde{a}^{i},a^{i}_{\rm opt}\\}$.

As the number of independent user trajectories for users in cluster $i$,
$|U_{i}|$, tends to infinity,

$\sqrt{|U_{i}|}\left(\hat{Q}^{\rm direct}(i,a^{i}_{\rm opt})-\hat{Q}^{\rm
direct}(i,a)-\Delta\right)\overset{d.}{\longrightarrow}N\left(0,\sigma^{2}_{\rm
direct}\right)$

and

$\sqrt{|U_{i}|}\left(\hat{Q}^{\rm naive}(i,a^{i}_{\rm opt})-\hat{Q}^{\rm
naive}(i,a)-\Delta\right)\overset{d.}{\longrightarrow}N\left(0,\sigma^{2}_{\rm
naive}\right)$

where $\sigma_{\rm
naive}^{2}=\frac{2\sigma^{2}}{\epsilon\cdot\operatorname*{\mathbb{E}}[T_{1}-T_{0}]}$
and $\sigma_{\rm direct}^{2}\geq\frac{2L\sigma^{2}}{\epsilon}+O_{\epsilon\to
0}(1)$ and hence

$\frac{\sigma^{2}_{\rm direct}}{\sigma^{2}_{\rm naive}}\geq
L\cdot\operatorname*{\mathbb{E}}[T_{1}-T_{0}]+O_{\epsilon\to 0}(\epsilon).$
(15)

The $O(\epsilon)$ term is small if exploration is infrequent. We use a small
$\epsilon$ approximation to avoid statistical dependencies that complicate
variance calculations. Our goal is to provide clean insight in a limited
special case, rather than provide a generic analysis of the sample complexity
of reinforcement learning.

Recall that $L\cdot\operatorname*{\mathbb{E}}[T_{1}-T_{0}]$ is the average
number of recommendations a user receives throughout their lifetime on the
service. When this number is large, a single recommendation is a tiny part of
a user’s overall experience. As formalized by Lemma 3, even if recommendations
overall have a large impact, it is difficult to correlate lifetime rewards
with a single recommendation decision. The estimates produced by Algorithm 2,
which tries only to associate a recommendation decision with a user’s
immediate engagement with that recommendation, have much lower variance.

Figure 8 plots approximations to the probability of correctly identifying that
$a^{i}_{\rm opt}$ outperforms $a$ under the two estimation strategies in a
setting with $\sigma^{2}=1$, $\Delta=0.1$, $\epsilon=.02$,
$|\mathbb{A}_{\star}|=5$, $L=30$ and
$\operatorname*{\mathbb{E}}[T_{1}-T_{0}]=60$. Algorithm 2 succeeds with high
probability when there are about 30,000 users in the $i^{\rm th}$ cluster. For
a platform with hundreds of millions of users, this represents a fairly small
segment who might have somewhat unique tastes. For Algorithm 1 to succeed with
a given probability, segment $i$ must be
$L\cdot\operatorname*{\mathbb{E}}[T_{1}-T_{0}]=1,800$ times larger. The
segment needs contain over 50 million users, exceeding the size of many
countries.

(a) Small cluster sizes

(b) Large cluster sizes

Figure 8: Visualization of the sample-size implications of Lemma 3. Plots
$\Phi^{-1}\left(\Delta\frac{\sqrt{|U_{i}|}}{\sigma_{\rm naive}}\right)$ which
is an asymptotic approximation based on Lemma 3 to the number of users
required under Algorithm 2 to differentiate $a^{i}_{\rm opt}$ and $a^{\prime}$
in the setting of Example 1. This is compared to,
$\Phi^{-1}\left(\frac{\Delta\sqrt{|U_{i}|}}{\sigma_{\rm
naive}}\cdot\frac{1}{\sqrt{L\cdot\operatorname*{\mathbb{E}}[T_{1}-T_{0}]}}\right)$,
an asymptotic _upper bound_ on the corresponding quantity under Algorithm 1.
The figure uses $\sigma^{2}=1$, $\Delta=0.1$, $\epsilon=.02$,
$|\mathbb{A}_{\star}|=5$, $L=30$ and
$\operatorname*{\mathbb{E}}[T_{1}-T_{0}]=60$.

###  5.5 Conclusions

Focusing on the case of state-aggregation allowed us to derive several clean
insights. The process of forming regression-style approximation of the
$Q$-function, based on logged data from the incumbent policy, and then
optimizing that approximate $Q$-function, can be understood as implementing a
coordinate ascent step on the space of policies. Local optimization of a
component of a policy in this manner is especially attractive in a
decentralized system. We also showed that the differences in estimated
$Q$-values provide a coherent way of attributing value to individual
recommendations add beyond the incumbent policy. Unfortunately, direct
estimates of long-term rewards are very noisy. A single recommendation makes
up only a small fraction of the overall user experience, and so it is
difficult to correlate holistic long-term outcomes with a single (randomized)
recommendation decision.

Our prototypes are motivated by this understanding. We estimate approximate
$Q$-functions from logged data and then follow the recommendation decisions
prescribed by them. But we impose modeling assumptions that greatly simplify
the estimation problem and help overcome the measurement challenges.

##  6 Deriving our prototypes via structural assumptions

We aim to estimate the $Q$-function from logged data in a manner that
overcomes measurement challenges. Guided by intuition on the nature of audio
streaming habits, we impose structural assumptions under which the
$Q$-function simplifies greatly; see Theorem 1. In particular, we arrive at a
formula that matches the $Q$-value in Section 3, providing a rigorous
justification these prototypes and clarifying the assumptions that underlie
them.

###  6.1 Structural assumptions

##### Additively separable reward functions.

We consider reward functions that are based on a user’s engagement or
_consumption_ in period $t$, defined as a vector
$C_{t}\in\mathbb{R}^{\lvert\mathbb{A}\rvert}$ with components

$C_{t,a}=\sum_{\ell=1}^{L}Y_{t,\ell}\mathbbm{1}(A_{t,\ell}=a).$ (16)

Our methodology requires immediate rewards are _additively separable_
functions of consumption.

######  Assumption 1.

There exists a function $r:\mathbb{R}_{+}\to\mathbb{R}$ and weights
$(\lambda_{a}:a\in\mathbb{A})\in\mathbb{R}_{+}^{|\mathbb{A}|}$ such that
$R(A_{t},Y_{t})=\sum_{a\in\mathbb{A}}\lambda_{a}r(C_{t,a})$ almost surely.

With the choice $r(c)=c$ and $\lambda_{a}=1$ for each $a$, single-period
rewards track total minutes of engagement. A strictly concave content-level
reward $r(\cdot)$ prioritizes engagement with many pieces of content over
extreme engagement with a single item.

The scalar weights do not play an important role in our work, but provide
added flexibility that could be useful in certain applications. In general,
one might view a separable reward function as a convenient proxy, or
surrogate, for a more complex objective and the weights may aid in ensuring
this approximation is faithful.

##### Restricting to direct effects of a recommendation.

It is natural to expect that recommending an item increases the chance the
user listens to _that_ item. We refer to this as the _direct_ impact of a
recommendation. As a simplifying assumption, we assume that recommendations
have no indirect effects. In words, the next assumption states that, given
what is known about a user (i.e., $S_{t}$), and given that item $a_{\star}$ is
not recommended, discounted future reward associated with consumption of item
$a_{\star}$ does not depend on which item is recommended. See Figure 9 for a
graphical representation.

######  Assumption 2 (No indirect impact of recommendation).

Under $\pi^{0}$, for every $a_{\star}\in\mathbb{A}_{\star}$,

$\sum_{\tau=t}^{T_{1}}r\left(C_{\tau,a_{\star}}\right)\perp A_{t,\star}\mid
S_{t}\,,\,\mathbbm{1}\\{A_{t,\star}=a_{\star}\\}.$

Recommendations likely do have indirect effects. There could be substitution
effects, where a successful recommendation supplants other consumption, or
spillover benefits, where a successful recommendation makes a user more likely
to engage with others, or possible annoyance, where a poor recommendation
causes a user to close the app. To build a simple, pragmatic, system, we do
not model complex indirect effects of recommendations.

Figure 9:  Graphical model encoding Assumption 2.

##### Surrogacy.

Key to our approach is the use of a state representation that is sensitive to
a decision of whether to recommend a given item while, plausibly, capturing
the full impact of that recommendation on future habits. We call this a user’s
content-relationship state and introduced it already in Section 3. To review,
a user’s content state $Z_{t}\in\mathbb{R}^{|\mathbb{A}|\times k}$ consists of
a $k$ dimensional embedded representation of a user’s consumption history of
each piece of content. For this to have an interpretation a _state_ variable,
we assume it can be updated incrementally as

$Z_{t+1,a}=f(Z_{t,a},C_{t,a})$ (17)

from an initial value $Z_{T_{0},a}=0\in\mathbb{R}^{k}$. Recall that
$C_{t,a}=\sum_{\ell=1}^{L}Y_{t,\ell}\mathbbm{1}(A_{t,\ell}=a)$ denotes
consumption from item $a$. The map $f$ could be learned by training a
recurrent neural network on some surrogate prediction task. Our prototypes
have used a simple handcrafted encoding described in Section 3. We assume that
$f$ maps inputs $Z_{t,a}=0\in\mathbb{R}^{k}$ and $C_{t,a}=0\in\mathbb{R}$ to
the vector $Z_{t+1,a}=0\in\mathbb{R}^{k}$, representing the state of having no
prior engagement with that piece of content. In most large-scale
recommendation systems, where the content library is enormous, we expect a
user’s content state to be extremely sparse.

Our final assumption is that the impact of deciding to recommend an item on
rewards associated with future engagement with that item is mediated through
the recommendation’s impact on the user’s next engagement-state with the item.
Figure 10 displays the conditional independence structures stated in
Assumptions 2 and 3. Conditioned on the user’s state, the (randomized)
decision to recommend item $a_{\star}$ influences immediate consumption of
item $a_{\star}$, which then influences the next relationship state with item
$a_{\star}$, which may alter projected future engagement with that item.
Notice that this assumption conditions on the full state in the current period
(i.e. period $t$) but the content-state in the _next_ period ($t+1$).

######  Assumption 3 (Surrogacy).

Under $\pi^{0}$, for any item $a_{*}\in\mathbb{A}_{\star}$ and period $t$,

$\sum_{\tau=t+1}^{T_{1}}r(C_{\tau,a_{\star}})\perp\mathbbm{1}\\{A_{t,\star}=a_{\star}\\}\mid
S_{t},Z_{t+1,a_{\star}}.$

It is worth emphasizing that future rewards still depend on the item
$a_{\star}$ itself. A critical part of our prototypes is in understanding
which items users are likely to form recurring habits with.

##### Extra simplification: binary consumption outcomes.

Under the next assumption, it is enough to track a binary indicator of whether
a user engages with an item in a given period, discarding the continuous
outcome of their engagement time. It should be emphasized that _our main
theorem does not impose this assumption_. It is used only in a special case of
the result which mirrors the prototypes in Section 3.

######  Assumption 4 (Binary outcomes).

The reward function is a binary indicator of positive consumption, written
$r(c)=\mathbbm{1}\\{c>0\\}$. The function $f(z,c)$ defined in (17) maps all
positive consumption levels to the same value, meaning
$f(z,c)=f(z,\mathbbm{1}(c>0))$.

When this assumption holds, the rule (17) for updating the content-engagement
state can be rewritten as

$Z_{t+1,a}=f(Z_{t,a},\mathbbm{1}\\{C_{t,a}>0\\}).$ (18)

The exponential moving averages in Section 3 provide a concrete illustration.

Figure 10:  Graphical model encoding Assumptions 2 and 3.

###  6.2 Decomposition of the value function : deriving our prototypes

Define the item-level value function

$\displaystyle
V^{(a)}_{\pi}(z_{a};s)=\mathbb{E}_{\pi}\left[\sum_{\tau=t+1}^{T_{1}}r\left(C_{\tau,a}\right)\mid
Z_{t+1,a}=z_{a}\,,\,S_{t}=s,S_{t+1}\neq\varnothing\right].$

This specifies an expected long-term reward associated with a user’s
engagement with item $a$. It depends on the item, the user’s current content-
relationship-state with that item, and the user’s state up to the last period
(encoding, for instance, the user’s overall tastes).

For a particular item $a$, we call the item-level value function
$V^{a}_{\pi^{0}}$ the item’s _stickiness model_. For a cohort of users with
similar features and similar relationship-states with the item, it represents
the expected strength their habitual attachment to the item going forward.
Under the binary reward in Assumption 4, this is exactly the stickiness model
presented in Section 3.

The next corollary decomposes the impact of a recommendation into two main
terms. The first captures the impact of a recommendation of item $a$ at
position $\star$ on the user’s likelihood of engaging with the item this
period. The second measures the impact of a choice to listen this period, both
through the immediate reward it generates and through the change in future
rewards as measured by the item’s stickiness model.

######  Corollary 1.

Under Assumptions 1, 2, and 3, and Assumption 4, if $S_{t}\neq\varnothing$
then for each $a\in\mathbb{A}_{\star}$,

$\displaystyle Q_{\pi^{0}}(S_{t},a)=b_{\pi^{0}}(S_{t})+$
$\displaystyle\lambda_{a}\left[\mathbb{P}_{\pi^{0}}\left(C_{t,a}>0\mid
S_{t},A_{t,\star}=a\right)-\mathbb{P}_{\pi^{0}}\left(C_{t,a}>0\mid
S_{t},A_{t,\star}\neq a\right)\right]$
$\displaystyle\times\left[\left(1+\gamma
V_{\pi^{0}}^{(a)}\left(Z_{t+1}^{+};S_{t}\right)\right)-\left(0+\gamma
V_{\pi^{0}}^{(a)}\left(Z_{t+1}^{-};S_{t}\right)\right)\right]$

where $Z_{t+1}^{+}=f(Z_{t,a},1)$ and $Z_{t+1}^{-}=f(Z_{t,a},0)$ are the
possible content-relationship states in the next period, and
$b_{\pi^{0}}(S_{t})$ does not depend on the recommendation decision $a$; it is
defined in Theorem 1.

That corollary is a special case of the theorem below, which does not rely on
the binary outcomes condition in Assumption 4. Note that the conditional
expectation in the formula for $Q_{\pi^{0}}$ integrates only over the
consumption of item $a$, $C_{t,a}$, since the content-relationship state
$Z_{t,a}$ is a known given the full state $S_{t}$.

######  Theorem 1.

Under Assumptions 1, 2, and 3, if $S_{t}\neq\varnothing$ then for each
$a\in\mathbb{A}_{\star}$,

$\displaystyle Q_{\pi^{0}}(S_{t},a)=b_{\pi^{0}}(S_{t})$
$\displaystyle+\mathbb{E}_{\pi^{0}}\left[r(C_{t,a})+\gamma
V^{(a)}_{\pi^{0}}\left(f\left(Z_{t,a},C_{t,a}\right)\,,\,S_{t}\right)\mid
A_{t,\star}=a\,,\,S_{t}\right]$
$\displaystyle-\mathbb{E}_{\pi^{0}}\left[r(C_{t,a})+\gamma
V^{(a)}_{\pi^{0}}\left(f\left(Z_{t,a},C_{t,a}\right)\,,\,S_{t}\right)\mid
A_{t,\star}\neq a\,,\,S_{t}\right].$

where the baseline value

$b_{\pi^{0}}(S_{t})=\sum_{a\in\mathbb{A}}\lambda_{a}\mathbb{E}_{\pi^{0}}\left[\sum_{\tau=t}^{T_{1}}r\left(C_{\tau,a}\right)\mid
S_{t},A_{t,\star}\neq a\right]$

does not depend on the recommendation decision $a$.

For completeness, Section E provides pseudocode for estimating the
$Q$-function from logged data in a manner that leverages the structure in
Theorem 1. It relies on state aggregation and is meant to be comparable to
Algorithm 1.

###  6.3 How the structural modeling alleviates measurement issues

Section 5.4 highlighted the severe measurement challenges faced by an
unstructured $Q$-estimation strategy. Namely, Lemma 3 highlighted that its
asymptotic variance could be $L\times\mathbb{E}[T_{1}-T_{0}]$ times larger
than a standard myopic approach. Two factors drive the increase in variance:

Global focus.

Algorithm 1 tries to correlate individual recommendation actions during a day
(e.g. the choice of $A_{t,\star}$) with overall rewards, like total engagement
with the app on a given day. This global focus leads to a poor signal-to-noise
ratio and is roughly the source of the factor of $L$ in Lemma 3.

Long-term measurement.

Algorithm 1 tries to correlate individual recommendation actions with a long-
term outcomes, namely the lifetime reward. This can also lead to low signal-
to-noise ratio and is roughly the reason $\mathbb{E}[T_{1}-T_{0}]$ appears in
Lemma 3.

How might our structural assumptions, and Theorem 1 in particular, alleviate
these two sources of variance?

Item-level focus.

Our approach measures the effects of a recommendation on item-level habits
whereas the unstructured approach aims to correlate recommendation decisions
with app-level habits. If assumption 2 is valid, and users often engage with
recommendations of many different items in a single day, then this can
substantially improve the signal-to-noise ratio.

Data pooling.

Sections 3.1.3 and 3.3 emphasized that our prototypes pool data across the app
when estimating the stickiness model. This helps to combat the high variance
of cumulative long-term rewards. Assumption 3 is what unlocks the data pooling
benefit. When appropriate, the assumption allows us, for instance, to use all
data on users who just discovered a podcast (and are in the corresponding
content-relationship state), regardless of whether this happened from a
recommendation on a particular surface and in a particular context.

Theorem 1 suggests an _indirect_ approach to $Q$-function estimation. For
instance Algorithm 4 in Appendix E trains a value function and then performs
an empirical Bellman backup. Indirect value function estimation is common in
the RL literature, exemplified by temporal difference learning [Sutton and
Barto, 2018]. Algorithm 1 instead used _direct_ value function estimation,
often called “Monte-Carlo” value function estimation in the RL literature.
Cheikhi and Russo [2023] provide formal theory showing that the statistical
benefits of indirect value estimation scale with the degree of data pooling.

##  7 Conclusion

We optimize a component of an industrial-scale recommender system for outcomes
that occur over months. This generates substantial impact, even from a small
alteration to the overall system. Are such large improvements possible for
many other recommender systems? We believe so. Unfortunately, optimizing for
the long-term successfully requires overcoming many challenges. We overcome
these by creating a tailored approach that leverages product intuition about
the nature of podcast listening habits. Our methods can be interpreted as RL
algorithms that apply when structural assumptions simplify value functions.
The ‘holy grail’ for the field of RL is to also efficiently learn the
structures we have handcrafted.

### Acknowledgments

For their contributions to this work, we wish to thank Sainath Adapa, Shubham
Bansal, Sonia Bhaskar, Dave Bredesen, Lauren Campbell, Kamil Ciosek, Zhenwen
Dai, Tonia Danylenko, David Gustafsson, Tony Jebara, Jon King, Mounia Lalmas-
Roelleke, Crystal Lin, Shawn Lin, Dylan Linthorne, Alan Lu, Andrew Martin,
Roberto Sanchis Ojeda, Vladan Radosavljevic, Oguz Semerci, Oskar Stal, Tiffany
Wu, and Cindy Zhang. We thank anonymous reviewers of the Reinforcement
Learning for Real Life Workshop at NeurIPS 2022 for their feedback. Daniel
Russo would also like to thank Joseph Cauteruccio, Ian Anderson, David
Murgatroyd, and Clay Gibson, whose thoughts on reinforcement learning strategy
influenced his thinking.

## References

  * Abhishek et al. [2012] Vibhanshu Abhishek, Peter Fader, and Kartik Hosanagar.  Media exposure through the funnel: A model of multi-stage attribution.  _Available at SSRN 2158421_ , 2012.
  * Afsar et al. [2021] M Mehdi Afsar, Trafford Crump, and Behrouz Far.  Reinforcement learning based recommender systems: A survey.  _ACM Computing Surveys (CSUR)_ , 2021.
  * Anderson et al. [2020] Ashton Anderson, Lucas Maystre, Ian Anderson, Rishabh Mehrotra, and Mounia Lalmas.  Algorithmic effects on the diversity of consumption on Spotify.  In _Proceedings of The Web Conference 2020_ , pages 2155–2165, 2020\.
  * Ansari et al. [2000] A Ansari, S Essegaier, and R Kohli.  Internet recommendation systems.  _Journal of Marketing Research_ , 37(3):363–375, 2000.
  * Ascarza and Hardie [2013] Eva Ascarza and Bruce GS Hardie.  A joint model of usage and churn in contractual settings.  _Marketing Science_ , 32(4):570–590, 2013.
  * Athey et al. [2019] Susan Athey, Raj Chetty, Guido W Imbens, and Hyunseung Kang.  The surrogate index: Combining short-term proxies to estimate long-term treatment effects more rapidly and precisely.  Technical report, National Bureau of Economic Research, 2019.
  * Bastani et al. [2022] Hamsa Bastani, Pavithra Harsha, Georgia Perakis, and Divya Singhvi.  Learning personalized product recommendations with customer disengagement.  _Manufacturing & Service Operations Management_, 24(4):2010–2028, 2022.
  * Bean et al. [1987] James C Bean, John R Birge, and Robert L Smith.  Aggregation in dynamic programming.  _Operations Research_ , 35(2):215–220, 1987.
  * Ben-Porat et al. [2022] Omer Ben-Porat, Lee Cohen, Liu Leqi, Zachary C Lipton, and Yishay Mansour.  Modeling attrition in recommender systems with departing bandits.  In _Proceedings of AAAI 2022_ , Washington, D.C., USA, February 2022\.
  * Bertsekas [2012] Dimitri Bertsekas.  _Dynamic programming and optimal control: Volume I_ , volume 1.  Athena scientific, 4 edition, 2012.
  * Besbes et al. [2016] Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Optimization in online content recommendation services: Beyond click-through rates.  _Manufacturing & Service Operations Management_, 18(1):15–33, 2016.
  * Beutel et al. [2018] Alex Beutel, Paul Covington, Sagar Jain, Can Xu, Jia Li, Vince Gatto, and Ed H Chi.  Latent cross: Making use of context in recurrent recommender systems.  In _Proceedings of WSDM 2018_ , Los Angeles, CA, USA, February 2018\.
  * Cao et al. [2020] Junyu Cao, Wei Sun, Zuo-Jun Max Shen, and Markus Ettl.  Fatigue-aware bandits for dependent click models.  In _Proceedings of AAAI 2020_ , New York, NY, USA, February 2020.
  * Cheikhi and Russo [2023] David Cheikhi and Daniel Russo.  On the statistical benefits of temporal difference learning.  _arXiv preprint arXiv:2301.13289_ , 2023.
  * Chen et al. [2019a] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi.  Top-k off-policy correction for a reinforce recommender system.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_ , pages 456–464, 2019a.
  * Chen et al. [2022] Minmin Chen, Can Xu, Vince Gatto, Devanshu Jain, Aviral Kumar, and Ed Chi.  Off-policy actor-critic for recommender systems.  In _Proceedings of the 16th ACM Conference on Recommender Systems_ , pages 338–349, 2022.
  * Chen et al. [2019b] Xinshi Chen, Shuang Li, Hui Li, Shaohua Jiang, Yuan Qi, and Le Song.  Generative adversarial user model for reinforcement learning based recommendation system.  In _International Conference on Machine Learning_ , pages 1052–1061. PMLR, 2019b.
  * Covington et al. [2016] Paul Covington, Jay Adams, and Emre Sargin.  Deep neural networks for youtube recommendations.  In _Proceedings of the 10th ACM conference on recommender systems_ , pages 191–198, 2016.
  * Dulac-Arnold et al. [2021] Gabriel Dulac-Arnold, Nir Levine, Daniel J Mankowitz, Jerry Li, Cosmin Paduraru, Sven Gowal, and Todd Hester.  Challenges of real-world reinforcement learning: definitions, benchmarks and analysis.  _Machine Learning_ , 110(9):2419–2468, 2021.
  * Elahi et al. [2022] Ehtsham Elahi, James McInerney, Nathan Kallus, Dario Garcia Garcia, and Justin Basilico.  Reinforcement learning for budget constrained recommendations.  https://netflixtechblog.com/reinforcement-learning-for-budget-constrained-recommendations-6cbc5263a32a, 2022\.  Accessed: 2022-01-09.
  * Gönül and Shi [1998] Füsun Gönül and Meng Ze Shi.  Optimal mailing of catalogs: a new methodology using estimable structural dynamic programming models.  _Management Science_ , 44(9):1249–1262, 1998\.
  * Gönül and Hofstede [2006] Füsun F Gönül and Frenkel Ter Hofstede.  How to compute optimal catalog mailing decisions.  _Marketing Science_ , 25(1):65–74, 2006.
  * Gordon [1995] Geoffrey J Gordon.  Stable function approximation in dynamic programming.  In _Machine Learning Proceedings 1995_ , pages 261–268. Elsevier, 1995.
  * Hidasi et al. [2016] Balázs Hidasi, Alexandros Karatzoglou, Linas Baltrunas, and Domonkos Tikk.  Session-based recommendations with recurrent neural networks.  In _Proceedings of ICLR 2016_ , San Juan, Puerto Rico, May 2016.
  * Howard [2002] Ronald A Howard.  Comments on the origin and application of markov decision processes.  _Operations Research_ , 50(1):100–102, 2002.
  * Hu et al. [2017] Binbin Hu, Chuan Shi, and Jian Liu.  Playlist recommendation based on reinforcement learning.  In _International Conference on Intelligence Science_ , pages 172–182. Springer, 2017.
  * Ie et al. [2019a] Eugene Ie, Chih-wei Hsu, Martin Mladenov, Vihan Jain, Sanmit Narvekar, Jing Wang, Rui Wu, and Craig Boutilier.  Recsim: A configurable simulation platform for recommender systems.  _arXiv preprint arXiv:1909.04847_ , 2019a.
  * Ie et al. [2019b] Eugene Ie, Vihan Jain, Jing Wang, Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Morgane Lustman, Vince Gatto, Paul Covington, et al.  Reinforcement learning for slate-based recommender systems: A tractable decomposition and practical methodology.  _arXiv preprint arXiv:1905.12767_ , 2019b.
  * Jiang et al. [2015] Nan Jiang, Alex Kulesza, and Satinder Singh.  Abstraction selection in model-based reinforcement learning.  In _International Conference on Machine Learning_ , pages 179–188, 2015.
  * Kakade and Langford [2002] Sham Kakade and John Langford.  Approximately optimal approximate reinforcement learning.  In _In Proc. 19th International Conference on Machine Learning_. Citeseer, 2002.
  * Konda and Tsitsiklis [1999] Vijay Konda and John Tsitsiklis.  Actor-critic algorithms.  _Advances in neural information processing systems_ , 12, 1999.
  * Koren et al. [2009] Yehuda Koren, Robert Bell, and Chris Volinsky.  Matrix factorization techniques for recommender systems.  _Computer_ , 42(8):30–37, 2009.
  * Li et al. [2006] Lihong Li, Thomas J Walsh, and Michael L Littman.  Towards a unified theory of state abstraction for MDPs.  In _ISAIM_ , 2006.
  * Li et al. [2010] Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Liberali and Ferecatu [2022] Gui Liberali and Alina Ferecatu.  Morphing for consumer dynamics: Bandits meet hidden markov models.  _Marketing Science_ , 2022.
  * Lu et al. [2021] Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen.  Reinforcement learning, bit by bit.  _arXiv preprint arXiv:2103.04047_ , 2021.
  * Ma et al. [2016] Hao Ma, Xueqing Liu, and Zhihong Shen.  User fatigue in online news recommendation.  In _Proceedings of the 25th International Conference on World Wide Web_ , pages 1363–1372, 2016.
  * Montoya et al. [2010] Ricardo Montoya, Oded Netzer, and Kamel Jedidi.  Dynamic allocation of pharmaceutical detailing and sampling for long-term profitability.  _Marketing Science_ , 29(5):909–924, 2010.
  * Mooney and Roy [2000] Raymond J Mooney and Loriene Roy.  Content-based book recommending using learning for text categorization.  In _Proceedings of the fifth ACM conference on Digital libraries_ , pages 195–204, 2000.
  * Netzer et al. [2008] Oded Netzer, James M Lattin, and Vikram Srinivasan.  A hidden markov model of customer relationship dynamics.  _Marketing science_ , 27(2):185–204, 2008.
  * Pearl [2009] Judea Pearl.  Causal inference in statistics: An overview.  _Statistics surveys_ , 3:96–146, 2009.
  * Pfeifer and Carraway [2000] Phillip E Pfeifer and Robert L Carraway.  Modeling customer relationships as markov chains.  _Journal of interactive marketing_ , 14(2):43–55, 2000.
  * Prentice [1989] Ross L Prentice.  Surrogate endpoints in clinical trials: definition and operational criteria.  _Statistics in Medicine_ , 8(4):431–440, 1989\.
  * Rubin [1974] Donald B Rubin.  Estimating causal effects of treatments in randomized and nonrandomized studies.  _Journal of educational Psychology_ , 66(5):688, 1974.
  * Russo [2020] Daniel Russo.  Approximation benefits of policy gradient methods with aggregated states.  _arXiv preprint arXiv:2007.11684_ , 2020.
  * Rust [1997] John Rust.  Using randomization to break the curse of dimensionality.  _Econometrica: Journal of the Econometric Society_ , pages 487–516, 1997.
  * Rust and Chung [2006] Roland T Rust and Tuck Siong Chung.  Marketing models of service and relationships.  _Marketing science_ , 25(6):560–580, 2006.
  * Schulman et al. [2015] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz.  Trust region policy optimization.  In _International conference on machine learning_ , pages 1889–1897. PMLR, 2015.
  * Shang et al. [2019] Wenjie Shang, Yang Yu, Qingyang Li, Zhiwei Qin, Yiping Meng, and Jieping Ye.  Environment reconstruction with hidden confounders for reinforcement learning based recommendation.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 566–576, 2019.
  * Shani et al. [2005] Guy Shani, David Heckerman, Ronen I Brafman, and Craig Boutilier.  An mdp-based recommender system.  _Journal of Machine Learning Research_ , 6(9), 2005.
  * Simester et al. [2006] Duncan I Simester, Peng Sun, and John N Tsitsiklis.  Dynamic catalog mailing policies.  _Management science_ , 52(5):683–696, 2006.
  * Singal et al. [2022] Raghav Singal, Omar Besbes, Antoine Desir, Vineet Goyal, and Garud Iyengar.  Shapley meets uniform: An axiomatic framework for attribution in online advertising.  _Management Science_ , 68(10):7457–7479, 2022\.
  * Singh et al. [1995] Satinder P Singh, Tommi Jaakkola, and Michael I Jordan.  Reinforcement learning with soft state aggregation.  In _Advances in neural information processing systems_ , pages 361–368, 1995.
  * Steck et al. [2021] Harald Steck, Linas Baltrunas, Ehtsham Elahi, Dawen Liang, Yves Raimond, and Justin Basilico.  Deep learning for recommender systems: A netflix case study.  _AI Magazine_ , 42(3):7–18, 2021.
  * Su and Khoshgoftaar [2009] Xiaoyuan Su and Taghi M Khoshgoftaar.  A survey of collaborative filtering techniques.  _Advances in artificial intelligence_ , 2009, 2009.