RPAF: A Reinforcement Prediction-Allocation Framework for Cache Allocation in Large-Scale Recommender Systems

Recommender systems have been widely researched in recent years, but most studies focus on improving business revenue or user experience under sufficient computational resources (Zhu et al., 2018; Pi et al., 2020; Wang et al., 2020). Some studies focus on the computational resource allocation problem in recommender systems, such as DCAF (Jiang et al., 2020), CRAS (Yang et al., 2021), RL-MPCA (Zhou et al., 2023). DCAF and CRAS consider the computational resource allocation problem as a constrained optimization problem solved by linear programming. RL-MPCA discusses the computational resource allocation problem in multi-phase recommender systems. However, existing methods do not consider the value-strategy dependency in the cache allocation problem studied in this paper.

Reinforcement learning (RL) in recommender systems has gained significant attention due to its ability to optimize user long-term satisfaction (Cai et al., 2023; Afsar et al., 2022; Chen et al., 2024). Value-based approaches estimate the user’s satisfaction with recommended items from the available candidate set, and then select the one predicted to yield the highest satisfaction (Chen et al., 2018; Zhao et al., 2018). Policy-based methods directly learn the recommendation policy and optimize it to increase user satisfaction (Chen et al., 2019; Ma et al., 2020; Chen et al., 2024). RL-based models can consider the temporal dependency of the cache allocation problem, but it is challenging to consider the computational budget constraints in RL models. RL-MPCA (Zhou et al., 2023) uses deep Q-Network (DQN) with a dual variable to model the constraints, but we will show in this paper that DQN-like value-based methods face challenges when modeling the cache allocation problem with global and strict budget constraint. In contrast, we propose the RPAF with RLA to tackle the abovementioned challenges.

A common approach to solving constrained Markov Decision Processes (CMDP) is the Lagrangian relaxation method(Tessler et al., 2018; Chow et al., 2018; Dalal et al., 2018; Garcıa and Fernández, 2015; Liu et al., 2021). The constrained optimization problem is reduced to unconstrained by augmenting the objective with a sum of the constraint functions weighted by their corresponding Lagrangian multipliers. Then, the Lagrangian multipliers are updated in the dual problem to satisfy the constraints. However, existing methods only consider the local constraints under each request and, therefore, cannot be directly applied in the cache allocation problem where the budget constraints are global, based on all requests at that moment. Moreover, existing methods meet the constraint in the sense of expectation, while the budget constraint in our scenario is strict. In contrast, the RPAF considers globality and the strictness of budget constraints.

We first consider a simplified cache allocation problem, of which the values of different cache choices are pre-defined. Such a cache allocation problem is a constrained optimization problem shown in Figure 3. We denote $\mathcal{U}$ as the set of users. At each time period $t$, some users in $\mathcal{U}$ open the app and send requests to the recommender system. We use $c_{t}^{u}=1$ to denote that User $u$ sends a request at Time $t$, and $c_{t}^{u}=0$ to denote that User $u$ is inactive at Time $t$. When $c_{t}^{u}=1$, the system needs to recommend $K$ items to User $u$. There are two choices for the system to provide such a recommendation, represented by $a_{t}^{u}\in\{0,1\}$:

• •

  Real-Time recommendation. When $a_{t}^{u}=1$, the system will recommend by real-time computation. Specifically, there will be multiple stages, e.g., retrieval and ranking. In each stage, deep models will be used to predict the user’s possible feedback (watch time, follow, like, etc.), and return $L$ items, of which the top $K$ items are recommended to the user and the rest are put into a result cache for future use.

• •

  Recommendation by the cache. When $a_{t}^{u}=0$, the system will provide recommendations by the cache. In such cases, the recommender system obtains $K$ items directly from the user’s result cache, and then updates the result cache.

Real-time recommendations usually perform better than cached recommendations since they can utilize users’ most recent feedback by deep models (Liu et al., 2018). However, the computational burden of real-time recommendation is much larger, and the total requests to be processed by real-time recommendation must not exceed a given value $M$ in each time period. Under the above discussions, the cache allocation problem can be written as:

Suppose we have obtained the reward $R_{t}^{u}$ for each request, then the cache allocation problem in Eq. (1)$\sim$(3) can be easily solved:

Proposition 3.1 means that the optimal allocations of the real-time recommendations are the top $M$ requests regarding the value difference between real-time and cached recommendations. Such results are also discussed in (Jiang et al., 2020).

According to Corollary 3.2, we will replace Eq. (2) by the equality $\sum_{u}a_{t}^{u}=M$ in the rest of this paper.

Although the solution to CacheAlloc-Simplified is simple according to Proposition 3.1, it assumes that the value $R_{t}^{u}$ under each $a_{t}^{u}$ is pre-defined before we compute the cache allocation problem. Such an assumption is used in the existing computational resource allocation methods (Jiang et al., 2020; Lu et al., 2023; Zhou et al., 2023), but it does not hold in the cache allocation problem. Moreover, CacheAlloc-Simplified assumes the cache choices can be determined after the information of all requests is obtained at each time step, which contradicts the streaming manner of online requests. Now, we discuss the two challenges and provide the modeling of the real cache-allocation problem.

RPAF, as shown in Figure 5, contains two stages, i.e., a prediction stage to estimate the value under different cache choices considering the value-strategy dependency and an allocation stage to solve the stream cache allocation problem under the estimated value.

The prediction stage uses the actor-critic structure. Specifically, we let the cache choice $a_{t}^{u}$ be determined by an actor function $\mu\left(\boldsymbol{s}_{t};\theta\right)$ parameterized by $\theta$, and define the critic function $Q\left(\boldsymbol{s}_{t}^{u},a_{t}^{u};\phi\right)$, parameterized by $\phi$, to estimate the long-term reward $R_{t}^{u}$ in Eq. (7) under the action $a_{t}^{u}$. Then, the objective of critic learning is:

And the objective of actor learning is:

After the prediction stage, we obtain the estimated critic function $Q\left(\boldsymbol{s}_{t}^{u},a_{t}^{u};\phi\right)$. Then, in the allocation stage, we solve the following constrained optimization problem:

The key technique in RPAF is to separate the value estimation and the cache allocation while considering their dependency. The next problem is to solve RPAF. If the budget constraint in Eq. (10) did not exist, the problem would degenerate into a typical actor-critic structure, and there is an amount of research on more effective algorithms, e.g. DDPG (Lillicrap et al., 2015), TD3 (Fujimoto et al., 2018), SAC (Haarnoja et al., 2018), etc. However, the budget constraint brings significant challenges to solving the problem:

• •

  Globality. The budget constraint is over all the users in Time $t$, and the system needs to determine all actions according to all the user states, which is computationally unaffordable.

• •

  Strictness. The budget constraint should be satisfied strictly. However, typical RL algorithms are usually solved in the sense of expectation, which is unsatisfactory.

We use the relaxed local allocator (RLA) and the PoolRank technique to address these two issues, respectively.

The motivation of RLA is to transform the global and strict constraint in Eq. (10) into a local and relaxed constraint so that it can be solved by sample-wise gradient descent. We first relax the binary cache action $a_{t}^{u}$ to a continuous one $\tilde{a}_{t}^{u}\in[0,1]$. $\tilde{a}_{t}^{u}$ can be regarded as the probability of $a_{t}^{u}=1$. We define RLA as $\tilde{a}_{t}^{u}=\tilde{\mu}\left(\boldsymbol{s}_{t};\theta\right)$, i.e., the allocator to determine the relaxed cache action $\tilde{a}_{t}^{u}$. We reuse the critic $Q\left(\boldsymbol{s}_{t}^{u},\tilde{a}_{t}^{u};\phi\right)$ as the estimated long-term reward under the relaxed action $\tilde{a}_{t}^{u}$. By the probability explanation of $\tilde{a}_{t}^{u}$, we have

By replacing the true action with RLA, we can rewrite the actor learning in Eq. (9)(10) as:

Here, we rewrite the constraint by dividing by $\sum_{u}c_{t}^{u}$ on both sides of the equality, and so $m_{t}=M/\sum_{u}c_{t}^{u}$. $m_{t}\in(0,1)$ is the ratio of real-time recommendations at Time $t$.

With the proposed RLA, i.e. $\tilde{\mu}\left(\boldsymbol{s}_{t}^{u};\theta\right)$, we are ready to derive the training process. We consider a penalty function $T\left(\hat{x},x\right)$ satisfying:

• •

  $T\left(\hat{x},x\right)$ reaches the minimum at $\hat{x}=x$.

• •

  $T$ is convex with regard to $\hat{x}$.

Typically, $T(\cdot)$ can be chosen as:

• •

  mean square error (MSE) function: $T(\hat{x},x)=\left(\hat{x}-x\right)^{2}$.

• •

  Kullback–Leibler (KL) divergence:

  $T(\hat{x},x)=-\left[x\log\left(\hat{x}\right)+(1-x)\log\left(1-\hat{x}\right)\right]$

By using the penalty function to replace the constraint, we combine the constraint into the objective of the actor learning:

By minimizing $L_{a}(\theta)$, we obtain the policy $\tilde{\mu}$, which maximizes the critic function $Q$ under the budget constraints. However, the penalty function $T$ in Eq. (16) still contains a global sum over all users, which is computationally unaffordable. To tackle this challenge, we consider the upper bound of $L_{a}(\theta)$. According to the convexity of $T(\hat{x},x)$ regarding $\hat{x}$, we have

Then we obtain an upper bound $\bar{L}_{a}(\theta)$ satisfying $L_{a}(\theta)\leq\bar{L}_{a}(\theta)$:

By minimizing the upper bound $\bar{L}_{a}\left(\theta\right)$, the original loss $L_{a}\left(\theta\right)$ will also be bounded from above. Note that terms of different $u$ in Eq. (18) are independent. In the training process, for each sample containing a sample of a user $u$ at the time period $t$ satisfying $c_{t}^{u}=1$, the actor loss can be written in the local form:

and the critic loss of each sample is:

We provide the training algorithm with RLA in Algorithm 1.

After the prediction stage, we have obtained the critic $Q(\boldsymbol{s}_{t}^{u},\tilde{a}_{t}^{u};\phi)$. Because the strict action $a_{t}^{u}$ is a special case of the relaxed action $\tilde{a}_{t}^{u}$, $Q(\boldsymbol{s}_{t}^{u},\tilde{a}_{t}^{u};\phi)$ can also be used in the allocation stage in Eq. (11). Now we discuss the solution to the streaming allocation problem. Existing approaches (Jiang et al., 2020; Zhou et al., 2023) usually use the Lagrangian technique to make the computational resource allocation algorithm satisfy the streaming fashion, but the convergence of the Lagrangian multiplier is also a significant challenge. Luckily, the structure of the cache allocation problem makes it possible to find more effective approaches. Here, we propose the PoolRank algorithm to perform the streaming allocation in the allocation stage of RPAF.

We first show the relationship between the final allocation strategy $a_{t}^{u}$ and the RLA output $\tilde{\mu}\left(\boldsymbol{s}_{t}^{u};\theta\right)$:

Proposition 4.1 shows the relationship between the relaxed allocator $\tilde{\mu}$ and the final allocation result $a_{t}^{u}$. Actually, if a request is more desired for the real-time recommendation, RLA will also return a larger value. To illustrate the PoolRank algorithm, we rewrite Eq. (21) as

where $\Omega_{t}$ is the set of all LRA outputs $\tilde{\mu}\left(\boldsymbol{s}_{t}^{u}\right)$ at the time period $t$, and the Rank operator computes the rank of $\tilde{\mu}\left(\boldsymbol{s}_{t}^{u}\right)$ in $\Omega_{t}$ ordered from the largest to the smallest. Now, we modify Eq. (22) to a streaming fashion. Specifically, we introduce a detailed time $\tau$, where the time period $t$ is regarded as $\{\tau:t\leq\tau<t+1\}$. Assuming the requests come at $\tau$, the rank function in Eq. (22) should be modified to

where the time of each request is replaced by the detailed time $\tau\in[t,t+1)$, while the $\Omega_{t}$ is still the set of the RLA values of all the requests arriving from $t$ to $t+1$.

Here, the challenge of streaming allocation is evident: we cannot obtain $a_{\tau}^{u}$ because it needs to obtain $\Omega_{t}$, which contains the requests coming after $\tau$. To tackle this challenge, we can approximate $\Omega_{t}$ by $\Omega_{t-1}$, because the real-time request volume at the time period $t$ will not differ much from the time period $t-1$.

We call $\Omega_{t}$ the request pool, which contains a set of requests with the LRA values. Then, the PoolRank formulation is

The online PoolRank algorithm is shown in Algorithm 2. Besides the main formulation in Eq. (24), we also apply the following techniques to accelerate the computation:

• •

  Bucketization: the rank operator in Eq. (24) can be computed in a $O(1)$ time complexity by bucketization. We first bucketize $\tilde{\mu}\left(\boldsymbol{s}_{\tau}^{u}\right)$ to $I_{\tau}^{u}$. Then, a prefix array $A$ stores the number of requests in $\Omega_{t}$ with values larger than $I_{\tau}^{u}$. Then, the rank of the request can be obtained by a simple searching process, i.e., Line 6 in Algorithm 2.

• •

  Dual-Buffer Mechanism: note that the prefix array $A$ can be computed asynchronously. We use $A_{online}$ in the online process and update $A_{online}$ once a new $A$ is available. This mechanism avoids updating the prefix array $A$ online, which significantly accelerate the PoolRank process.

As a summary of this section, we provide RPAF to solve the cache allocation problem. The prediction stage utilizes RLA to learn the critic and policy function, as shown in Algorithm 1, while the allocation stage utilizes PoolRank to perform a streaming allocation, as shown in Algorithm 2. The next section will validate the effectiveness of RPAF by offline and online experiments.

We compare several methods as demonstrated in Table 1. To get the upper bound of the performance, an ideal strategy, All Real-Time, is included. This strategy chooses real-time recommendations regardless of the computational burden. As shown in Table 1, all dynamically allocated methods outperform the greedy approach. RPAF outperforms existing approaches, demonstrating the improvement achieved by considering the value-strategy dependency in cache allocation problems. Moreover, the comparison between RPAF with and without RLA demonstrates that RLA provides better performance by estimating the value of cache choice considering the constraint. A detailed discussion of RLA can be found in Section 5.3. Finally, RPAF with TD3 outperforms RPAF with DDPG, indicating that the RL backbone also impacts performance. Given that RPAF is independent of the RL backbone, any new studies on the actor-critic structure can be integrated into RPAF.

Additionally, Figure 6 illustrates the performance comparison across different time periods within a single day. During off-peak periods, for instance, from 0 AM to 6 AM, the total number of requests does not exceed the computational budget. Consequently, all the methods return real-time recommendations, resulting in the same reward. During peak periods, e.g., from 7 PM to 10 PM, cached recommendations become essential, and the performance of each method varies, of which RPAF achieves the best results.

This subsection validates the impacts of RLA. We regard the RPAF without RLA as RPAF with no penalty function $T(\hat{x},x)$. Figure 7 shows the convergence curve of the average output of the allocator $\tilde{\mu}\left(\boldsymbol{s}_{t}^{u};\theta\right)$ with and without the penalty function $T(\hat{x},x)$. The policy function $\tilde{\mu}$ is shown to collapse to $1$ without the penalty function $T$. This means that all requests will be processed through real-time recommendation, which violates the budget constraint. In contrast, RLA with localized penalty functions is observed to converge to a reasonable ratio of real-time recommendations. As shown in Table 1 and Figure 8, RPAF with RLA significantly outperforms RPAF without RLA, while the two penalty functions chosen(KL and MSE) yield similar performance, indicating that RPAF is not largely dependent of the choice of penalty functions in RLA.

Figure 9 shows the number of real-time recommendations per hour under different methods. It is assumed that requests come in a streaming manner, and the system needs to determine the cache choice immediately upon receipt of a request, while ensuring that the total real-time recommendation per hour does not exceed the budget. If the system chooses a real-time recommendation while the system has no buffer, the request will still be downgraded into the cached recommendation. We also consider the RPAF without PoolRank, which determines cache choices solely in accordance with the allocator $\tilde{\mu}$. It is shown that DCAF, RL-MPCA, and RPAF without PoolRank cannot fully utilize all available real-time traffic, while the introduction of PoolRank enables the full exploitation of computational resources. This phenomenon shows the difference between batch allocation and streaming allocation. In streaming allocation, it is impossible to determine the cache choice according to all the requests in a time period. Existing methods may underestimate the available real-time computation resources in the future. PoolRank, however, achieves better performance due to its utilization of the most recent information on computational resources.

We test the proposed RPAF method in Kwai, an online short video application with over 100 million users. The RPAF structure in the online system is shown in Figure 10. The model is trained continuously online. When a user’s session ends, the session’s data is immediately fed into the model for training, and the updated model is instantly deployed to the online service. We deploy the RPAF with the TD3 backbone and the MSE penalty function. There are 40% cached recommendations in the peak period. In this scenario, users’ experience is highly consistent with their daily usage time. Thus, we regard the watch time per request as the immediate reward $r_{t}^{u}$. We sequentially conduct a series of experiments related to DCAF, RPAF (without PoolRank), and RPAF (with PoolRank). Each method is tested for 7 consecutive days, with the confidence intervals shown in Table 2.

As shown in Table 2, RPAF obtains a 1.13% increase in daily watch time compared to the baseline and a 0.83% increase compared to DCAF. We emphasize that in our system, a 0.1% improvement holds statistical significance. Furthermore, a 150-day online experiment was conducted during which the experimental group employed DCAF, RPAF (without PoolRank) and RPAF (with PoolRank) in sequence, while the base group used the greedy strategy. Figure 11 plots the comparison results of RPAF with the baseline, where the x-axis represents the number of days since deployment, and the y-axis indicates the percentage difference in the number of daily active users between the experimental group and the baseline group. Figure 11 shows that the users in the experimental group are more likely to stay active on the platform, indicating an improvement in users’ long-term values.