Online Matching: A Real-time Bandit System for Large-scale Recommendations

Neural modeling has emerged as the dominant approach for constructing large-scale recommender systems in a range of industry applications, including video discovery (Covington et al., 2016), news recommendations (Okura et al., 2017), and social networks (Liu et al., 2017; Zhai et al., 2017). These models cover a broad range of tasks, from retrieval (Yi et al., 2019) to ranking (Cheng et al., 2016; Zhao et al., 2019). The main focus of this paper is on the retrieval problem, where the goal is to find a few related items from a large item corpus. This problem is also known as deep retrieval and has been extensively studied in the past. For example, a line of work (Yi et al., 2019; Yang et al., 2020; Chang et al., 2020; Yao et al., 2021) studied two-tower models for learning user and item representations in the same embedding space, allowing converting the problem of retrieval to maximum-inner-product-search (MIPS) (Guo et al., 2020) with sub-linear complexity. Compared to matrix factorization and extreme classification models (Covington et al., 2016), two-tower architecture can leverage content features of items, making it more suitable for generating reasonable representations of fresh items with little user engagement. Although a large amount of training data is often available in real-world applications, neural models (including aforementioned two-tower models) are typically trained offline on logged user feedback in a supervised fashion, making them biased toward existing recommendation policies and hard to promptly adapt to system changes. In this paper, we propose an efficient exploration space pruning strategy, using two-tower models as a key part of our offline learning framework. Benefiting from the generalization capabilities of two-tower models, our strategy makes online learning feasible under strict latency and traffic constraint.

To alleviate the aforementioned bias problem, there has been a body of work bringing offline reinforcement learning (RL) techniques to neural recommender systems. The idea of off-policy learning is to estimate the value of a target policy or to train it using data collected by a different behavior policy. A series of work (see e.g. (Gilotte et al., 2018; Swaminathan and Joachims, 2015; Thomas and Brunskill, 2016)) focused on developing off-policy estimators through inverse-propensity weighting. For target policy learning, Chen et al. (Chen et al., 2022) applied off-policy correction to training a neural sequence model for video retrieval. There are also various papers (see e.g. (Joachims et al., 2017; Zhao et al., 2019)) studying learning unbiased ranking models from biased logged feedback. More recently, Ma et al. (Ma et al., 2020) proposed using off-policy learning for two-stage recommender systems. One challenge in off-policy learning is that data collected from the existing behavior policy might not accurately represent the target policy. This is especially true for fresh items with minimal or no engagement data, where the inverse propensity weighting can have a high variance. Offline RL, like traditional batch trained neural recommenders, is also subject to significant delays in data logging, model training, and deployment, as it is still based on the batch training paradigm.

Online learning provides a useful framework for building recommenders that are adaptable to user feedback. One commonly used type of online learning algorithm is bandit algorithms, such as UCB (Auer et al., 2002), Thompson Sampling (Chapelle and Li, 2011), and LinUCB (Chu et al., 2011). These algorithms are designed to balance the exploration of new options with the exploitation of known good options, allowing the system to learn and adapt to user behavior over time. The application of bandits to recommenders dates back to the seminal work by Li et al. (Li et al., 2010) on using contextual bandits for news recommendation. The work in (Chapelle and Li, 2011) provided an evaluation of Thompson Sampling on real-world datasets. Jeremie et al. (Mary et al., 2015) studied bridging matrix factorization and bandits to solve the cold-start problem in recommenders. Besides the use of bandits for exploring new items, more recently, Song et al. (Song et al., 2022) proposed creating a hierarchical representation of item space to help explore new user interests. To the best of our knowledge, most of the works on bandits for recommendations conduct experiments on offline synthetic or real-world datasets with simulated environment, and how to scale online learning system to billions of users and millions of items with real-time updates is not well studied. In contrast, a key contribution of this paper is on scaling in real-world environment, and we provide the engineering details on how we build the Online Matching system.

Building real-time systems that can quickly process user feedback is critical for recommenders, especially in applications where new items are quickly added. StreamRec (Chandramouli et al., 2011) is a demo for event-driven fast data processing for training recommender models. Recently, Monolith was introduced in (Liu et al., 2022) as a system for fast model training with collisionless embedding table. In addition to the real-time update capability, our Online Matching system is further built with explicit exploration strategies to address the feedback loop problem (Chaney et al., 2018) that is not addressed in this stream of work.

We aim to build Online Matching by learning users’ feedback to items in a closed loop, see Fig. 1 for an illustration. One naive approach is to apply multi-armed bandits for each user. That is for each user, we maintain a set of bandit parameters for all the explored items. This approach is not scalable because when there is a large number of explored items, many trials are needed for each user, making it hard for bandit parameters to converge, especially in the case new items are continuously added. Therefore, we need to consider contextual bandits where user context is modeled to allow using context features and across-user learning. Formally, let $t$ denote the current time step, $a_{t}\in\mathcal{A}$ denote the action selected at time $t$ from the entire action space $\mathcal{A}$, and $r_{t}(a_{t})$ denote the reward obtained by selecting action $a_{t}$ at time $t$. The goal is to learn a policy $\pi_{t}({\mathbf{x}}_{t})$ that maps the observed user feature ${\mathbf{x}}_{t}\in\mathbb{R}^{d}$ to an action $a_{t}$, such that the expected cumulative reward is maximized over a sequence of $T$ time steps:

In contextual linear bandits, the reward function is assumed to be linear in the feature vector ${\mathbf{x}}_{t}$, i.e.,

for all $t$, where ${\bm{\theta}}_{a}^{*}$ is an unknown weight vector associated with action $a$. The goal is to estimate the weight vectors ${\bm{\theta}}_{a}^{*}$ ($a\in\mathcal{A}$) and use them to select actions that maximize the expected reward. A more generic formulation (Chu et al., 2011) is assuming there is a single unknown weight vector ${\bm{\theta}}^{*}$, and the expectation reward is ${\mathbf{x}}_{t,a}^{\top}{\bm{\theta}}^{*}$, where ${\mathbf{x}}_{t,a}$ represents both user and item features. We choose not to model item features in this work because we find item id is a very important feature to reflect the finest difference among various items, and adding this feature to ${\mathbf{x}}_{t,a}$ can make this vector to be very high-dimensional. The setup in (2) is also called disjoint linear models as studied in a few papers (Li et al., 2010; Deshpande and Montanari, 2012; Wang et al., 2017).

The LinUCB algorithm (Li et al., 2010) maintains an estimate of the unknown parameter vector ${\bm{\theta}}_{a,t}$ for each action $a$ at each time step $t$. Let ${\mathbf{A}}_{a,t}$ and ${\mathbf{b}}_{a,t}$ be the $d$-by-$d$ positive definite matrix and $d$-dimensional vector that represent the covariance matrix and mean vector of the context features up to time $t$, respectively. Then the estimate of ${\bm{\theta}}_{a,t}$ is given by:

LinUCB selects the arm with the highest upper confidence bound, namely:

where $\alpha$ is a hyperparameter that controls the exploration-exploitation tradeoff. If action $a$ is chosen, ${\mathbf{A}}_{a,t}$ and ${\mathbf{b}}_{a,t}$ are then updated using the observed reward $r_{a,t}$ and context vector ${\mathbf{x}}_{t}$ through:

For any action $a$ not chosen, we have ${\mathbf{A}}_{a,t}\leftarrow{\mathbf{A}}_{a,t-1},{\mathbf{b}}_{a,t}\leftarrow{\mathbf{b}}_{a,t-1}$. See Algorithm 1 for a detailed description.

Scaling problems of LinUCB. There are several practical issues that prevent us from directly using LinUCB for serving online traffic and getting real-time updates:

• •

  Large Action Space. The computation of $UCB_{j}(t)$ is over all actions or items. In our application, even after narrowing the corpus down to fresh items, there are still millions of items worth exploring.

• •

  Covariance Inversion. Computing $UCB_{j}(t)$ and updating $\theta_{a,t}$ depend on calculating the inverse of the covariance matrix ${\mathbf{A}}_{a,t}$ that has a size of $d$-by-$d$. Note that the covariance matrix cannot be precomputed or cached due to the streaming updates. The online computational cost could be prohibitively high when facing a large user traffic.

• •

  Synchronous Updates. When one item is exposed to users, there could be many feedback received from various users. The streaming updates of ${\mathbf{A}}_{a,t}$ and ${\mathbf{b}}_{a,t}$ require an item-level synchronization, which poses a challenge on maintaining a high throughput to handle large traffic. As LinUCB converges to exploiting fewer top items, synchronization cost could be a real bottleneck.

To overcome the aforementioned challenges, we propose a novel variant of LinUCB. Before diving into that, we take a step back to build some intuitions for our solution. Let’s look at the problem of user-item matching from a graph perspective. As shown in Fig. (2(a)), suppose there is a dense bipartite graph between users and items, the main goal of recommendation is to find good edges in the graph to make the connections between users and items. Naively, we could explore all items for each user disjointly, but apparently this would not be efficient. Our idea is to group users by clusters, and then reduce the exploration space in each cluster. As illustrated in Fig. (2(b)), we build user clusters where each cluster can be considered as a user cohort. For each cluster representing users with certain type of interest, we only consider a small subset of items to explore since it is not worth exploring many unrelated items in the corpus. For each user, we assign them to multiple top clusters and use the cluster weights when deciding how to connect user to the items in their corresponding clusters. The edges in the sparsified graph can be further converted to bandit parameters learnt online. Besides the intuitions, we provide a principled bandit framing in Section 3.3.

Embedding-based graph construction. With the graph view, now we describe how the graph is constructed offline. The idea is to leverage neural modeling. We first train a two-tower model to co-embed users and items, similar to the way many batch retrieval models (Yi et al., 2019) are built nowadays. Specifically, we train two neural networks, denoted by $f$ and $g$, to encode user and item features ${\mathbf{x}},{\mathbf{y}}$ to embeddings $f({\mathbf{x}})$ and $g({\mathbf{y}})$ respectively. Given a batch of positive user-item pairs $\{{\mathbf{x}}_{i},{\mathbf{y}}_{i}\}_{i=1}^{B}$, we use the batch softmax loss to train the two-tower model:

where $\tau$ is a hyperparameter representing softmax temperature. In practice, using normalized embeddings, i.e., $\|f({\mathbf{x}}_{i})\|_{2}=\|g({\mathbf{y}}_{i})\|_{2}=1$, can greatly improve trainability. As a result, we need to scale the logits to obtain meaningful softmax probabilities using $\tau$, as the logits are limited to the range of -1 to 1. We omit further details here and refer interested readers to (Yi et al., 2019), as the offline modeling is not the main focus of this paper.

Next, we apply off-the-shelf clustering algorithms to discretize the embedding space into a set of user clusters, based on a large sample of user embeddings. For each user cluster, we choose the set of items with the highest embedding similarity measured by dot product between cluster centroid embeddings and item embeddings. This step largely narrows down the exploration space, allowing the online learning algorithm to focus on the items that have a higher probability of success. More details can be found in Algorithm 2. Note that it is possible to apply various clustering algorithms in our proposed framework, though we adopt kMeans in our system for simplicity.

Now that we have explained the graph sparsification, we can proceed to introduce our bandit learning algorithm. We should note that if we assign each user to only one cluster during online learning, we can view the items ($\mathcal{I}_{c}$) in each cluster as distinct arms in a multi-armed bandit problem and utilize the UCB algorithm. Nonetheless, limiting each user to a single cluster could lead to a considerable loss of information from user embeddings. To tackle this issue, we instead assign each user to the closest $K$ (e.g., 10) clusters and also incorporate the cluster weights as part of the context representation. The question now becomes how to design an effective exploration-exploitation strategy to handle the many-to-many mapping from both users to clusters and items to clusters. We propose a principled framing called sparse linear bandits, where the cluster weights can be effectively treated as a sparse context representation of a user in the high-dimensional space $\mathbb{R}^{C}$.

Sparse linear bandits. Given $C$ clusters, let ${\mathbf{w}}_{u}\in\mathbb{R}^{C}$ represent the weights of the top-$K$ clusters for the query from user $u$. Note that ${\mathbf{w}}_{u}$ is very sparse because $C$ is large and $\|{\mathbf{w}}_{u}\|_{0}=K<<C$. On the other hand, suppose for each item $j$, we have the “ground-truth” parameter ${\bm{\theta}}_{j}^{*}\in\mathbb{R}^{C}$, where the $c$-th coordinate $\theta_{j,c}^{*}$ represents the quality or value of item $j$ for the cluster $c$. Based on the sparse graph in Fig. (2(b)), we can assume that $\theta_{j,c}^{*}=0$ if there is no edge between item $j$ and cluster $c$. Accordingly, ${\bm{\theta}}_{j}^{*}$ is also sparse, and we have $\|{\bm{\theta}}_{j}^{*}\|_{0}<<C$ for most items. It is possible that some items (e.g., the popular ones with large audience) can belong to many clusters, but we could always control the sparsity of ${\bm{\theta}}_{j}^{*}$ by setting a maximum degree per item. Similar to linear bandits, the reward $r_{u,j}$ is assumed to satisfy $\mathbb{E}(r_{u,j}|{\mathbf{w}}_{u})=<{\mathbf{w}}_{u},{\bm{\theta}}_{j}^{*}>$. Based on our sparsity assumption, we can see that $\mathbb{E}(r_{u,j})$ is 0 for most $(u,j)$ pairs, and such pairs won’t be explored in our algorithm. In other words, the Large Action Space problem of LinUCB is largely mitigated by our graph sparsification. Now we introduce a novel approximation, Diagonal LinUCB, to avoid computing the expensive Covariance Inversions and to address the Synchronous Updates problem in the meantime.

Diagonal LinUCB. The key idea is to only maintain and utilize the diagonal terms of covariance matrix ${\mathbf{A}}_{j,t}$ for item $j$ at step $t$. This is inspired by the momentum-based gradient descent methods (e.g., Adagrad and Adam) where only diagonal terms of Hessian matrix are used. Actually, covariance matrix ${\mathbf{A}}_{j,t}$ is essentially the Hessian matrix for solving linear regression. From this point forward, we will omit the subscript $t$ to simplify the notation. Let vector ${\mathbf{d}}_{j}$ denote the diagonal terms of ${\mathbf{A}}_{j}$ at some step. Let $d_{j,c}$ be the $c$-th coordinate of ${\mathbf{d}}_{j}$, and let $w_{u,c}$ be the $c$-th coordinate of ${\mathbf{w}}_{u}$. For a vector ${\mathbf{x}}$, let $\|{\mathbf{x}}\|_{supp}$ denote its support, i.e., the set of indices with non-zero entries. Then the update rules of ${\mathbf{d}}_{j}$ and ${\mathbf{b}}_{j}$ become:

where $\mathcal{I}_{c}$ is from Algorithm 2. Furthermore, $UCB_{j}$ becomes

In exploitation mode, we drop the confidence bound term, and the estimated reward becomes

In the experiment section below, we will discuss how the exploitation mode is used in the use case of fresh content discovery. Putting things together, our detailed algorithm is shown in Algorithm 3.

Discussion on Eq. (3.3). Now we take a closer look at the parameter updates in Eq. (3.3). Given a reward $r_{u,j}$, the update of $b_{j,c}$ gives higher weights to clusters closer to the user embedding. In other words, for user that is more familiar with an explored item, their feedback on the item will be trusted more. It is worth noting that when $w_{u,c}=1$, Eq. $(\ref{eq:diag_linucb_update})$ is reduced to multiple $UCB$ that run separately for each cluster. As shown in experiments, we find that incorporating cluster weights can outperform treating all clusters equally. Compared to LinUCB, the updates in Diag-LinUCB are much more light-weighted, and more importantly, do not require the item-level synchronization since the updates are fully distributed over the edges in the sparse graph. This property eases the design of online learning infrastructure and significantly improves the system throughput.

Context vector. There could be a few options for computing the context vector ${\mathbf{w}}_{u}$ from user embedding ${\mathbf{u}}$. The naive way is to let $w_{u,c}=\langle{\mathbf{u}},{\mathbf{c}}_{c}\rangle$ where ${\mathbf{c}}_{c}$ is the embedding of each centroid. As mentioned in Section 3.2, we apply embedding normalization and softmax temperature when learning the two-tower model, which usually leads to top clusters having similar weights, with small numerical differences. This is expected because small difference in logits is amplified by the temperature $\tau<<1$ and the softmax function during training. Directly using the logits as context vector does not reflect the true user preferences over various clusters. To address this issue, one option is to use a softmax transform similar to the one used in the training stage, namely

where $\tau^{\prime}$ is another hyperparameter. One limitation of this approach is that we need to empirically tune $\tau^{\prime}$. Another option is to train a multi-class classification model to directly predict the distribution over user clusters. However, this requires a much more intricate pipeline that involves training both the two-tower model and the user clusters. In this paper, we choose the simple approach in Eq. (10) and leave the second option to future work.

The entire Online Matching workflow consists of an offline pipeline and an online agent responsible for the closed-loop learning, as shown in Fig. 3. The offline pipeline produces a sparse bipartite graph, as introduced in Section 3.2, which is adopted by the online agent. It has the following components:

• •

  Two-tower model trainer. We train an offline two-tower model by sequentially consuming a large amount of logged user feedback over time. The sequential training ensures that the model can adapt to the distribution change in the latest batch of data. As mentioned earlier, this model encodes item features, allowing it to generate meaningful embeddings even for newly added items. The two-tower model is exported on a daily basis, with both towers used by the downstream components to create the sparse bipartite graph. The user tower is also used by the online system to generate user embedding ${\mathbf{u}}$ and context vector ${\mathbf{w}}_{u}$.

• •

  Candidate selection. This component creates a corpus of items eligible for exploration. Multiple filters are applied to ensure the selected candidates satisfy our strict trust-and-safety criteria. In this paper, our system is mainly focused on exploring fresh videos, therefore a rolling time window that covers a few days is used for item selection. We also apply various quality thresholds to balance the quality and size of the corpus.

• •

  Clustering and graph building. Once clustering is finished based on the two-tower model exported most recently, graph builder is triggered to build the sparse graph according to Algorithm  2. The graph building process is executed in both batch and real-time modes concurrently. In batch mode, graph builder takes the output of the candidate selection step, and exports a new graph every few hours. Real-time mode complements batch mode by incrementally updating the sparse graph with newly eligible items to ensure a small latency for items to enter the exploration pool.

Online agent represents the system that conducts the bandit algorithm and aggregates user feedback in real-time. It takes the sparse graph produced from the above pipeline as input. Whenever the sparse graph is updated, bandit parameters are synchronized in online agent with low latency: new edges are added with infinite confidence bound (so that they will be prioritized for future exploration), and old edges that are only in the previous graph version are removed. In the next section, we will delve into the specifics of online agent.

As shown in Fig. 4, the key components of online agent are chained as a closed loop. Explored items from Online Matching are allowed to be shown at a fixed position in the UI, so that users’ direct feedback on them can be measured without being affected by existing ranking policies. The log processor is used to incrementally generate various kinds of engagement signals on the explored items in the format compatible with the downstream jobs. The feedback aggregation processor is built on top of Bigtable  (Chang et al., 2006) and is responsible for aggregating pair-wise (cluster and video) bandit parameters according to Eq. (3.3). As illustrated in Table  1, each row in the Bigtable represents one cluster, and each column represents the corresponding items of that cluster in the sparse graph. Conceptually, Bigtable is a sparsely populated table that can scale to the billions of rows and columns, and is compatible with the proposed Diag-LinUCB algorithm.

Bandit parameters in Bigtable are frequently pushed to the cluster-to-candidates lookup service. The recommender service is used for obtaining user clusters, and look up the candidates and their bandit parameters from the lookup service. The recommender service is further used to rank all the candidates according to the UCB in Eq. (8) or Eq. (9) if the goal is to exploit high quality candidates.

It is worth noting that, compared to the classic bandits setup with a fixed set of arms, we always have fresh items added as new arms in Online Matching. In particular, fresh items are continuously injected into the bipartite graph through the graph building pipeline. New items that have never been explored would have an infinite confidence bound in Eq.  (8) and are therefore prioritized for exploration in the recommender service. Due to the batch addition of new items, we can observe spikes of infinite UCB scores as shown in Fig. 5. The spikes usually disappear quickly, demonstrating that users’ feedback to new items are quickly incorporated in bandit parameters.

To demonstrate the real-time performance of Online Matching, we measure the following two types of update latency:

• •

  Policy update latency: This is the period of time from the point user sees the explored item, to the point when user’s feedback on the item is incorporated in bandit parameters contained in the lookup service in Fig. 4. Since our primary application is video recommendation, this latency also includes user’s watch time on video capped at a certain value, as a major part of the latency in the log processor. Actually sessionizing user feedback in the log processor contributes to most of the policy update latency.

• •

  Corpus update latency: This is the period of time from the point a fresh item is eligible for exploration to the point when the item is added to the sparse graph.

The median and the 95-th percentile of both latency are summarized in Table 2. Besides latency, our system achieves high throughput, e.g., it can handle millions of bandit updates per second, allowing it to scale to billions of users.

Particularly, the low latency of policy update is critical for recommendation quality since the expected regret grows as the feedback delay increases (Joulani et al., 2013). To empirically verify the expected regrets, we add artificial latency into the aggregation processor in Fig. 4. As shown in Table  3, as latency was introduced, the agent became less capable of identifying low-performing bandits, resulting in a decrease in CTR and total rewards on explored items.

We primarily consider two use cases of Online Matching:

• •

  Fresh Content Discovery (Type-I). Content creators upload millions of videos to Youtube on a daily basis. These videos vary a lot in quality and traditional batch-learning based recommender systems are limited in their capability to identify high-quality fresh videos and recommend them to the appropriate audience in a timely manner. Intuitively, an efficient exploration system on fresh content can supplement traditional recommender systems by identifying and leveraging quality fresh content to improve user experience with satisfied engagement, particularly with fresh content. To compensate the quality loss from exploration, the idea is to use a very small traffic for exploration, and conduct exploitation (i.e., amplifying high-quality candidates) for the rest of traffic.

• •

  Corpus Exploration (Type-II). Real-world recommender systems typically have a long-tail distribution over the recommendation corpus. Traditional recommender systems are primarily exploitation-based due to a feedback loop that reinforces the existing “winners” in the corpus. Exploring and leveraging the long-tail portion of the corpus is both challenging given its vast size and rewarding. In this case, the goal is to grow the discoverable corpus. Having a larger discoverable corpus is argued to bring long-term value to recommenders, e.g., through reducing system uncertainty on sparse data region (Chen, 2021). It can also provide torso or long-tailed content creators more opportunities to showcase their content to a wider audience. However, similar to Type-I, explicitly exploring long-tail and fresh items can lead to short-term loss of user engagement and satisfaction. Therefore, the goal of this use case is to enlarge discoverable corpus while having minimal regret on short-term engagement.

Online Matching is a fitting solution for the above use cases thanks to its efficiency in both the exploration algorithm and system. On one hand, Online Matching trims the exploration space through offline learning, making it possible to only use small traffic for exploration in the first use case. On the other hand, the real-time property of Online Matching system helps to minimize exploration errors, so that it can effectively enlarge the discoverable corpus while maintaining a small regret on short-term engagement in the second use case.