Marketing Budget Allocation with Offline Constrained
Deep Reinforcement Learning

A well-established framework for studying constrained RL is the Constrained Markov decision process (CMDP) (Altman, 1999), which can be identified by a tuple $\{{\mathcal{S}},{\mathcal{A}},P,r,{\bm{c}}\}$. Over an infinite time horizon, each time at $t=1,2,...$, the agent observes a state $s_{t}\in{\mathcal{S}}$ among the state space and chooses an action $a_{t}\in{\mathcal{A}}$ among the action space. Given the current state and the action chosen, the state at the next observation evolves to state $s_{t+1}\in{\mathcal{S}}$ with probability $P(s_{t+1}|s_{t},a_{t})$, and the agent receives an immediate reward $r_{t}\in\mathbb{R}$. In particular, for the marketing budget allocation problem, the corresponding action $a_{t}$ consumes the limited budget that constrains the usage of resources. Therefore, we assume that action $a_{t}$ suffers an $m$-dimensional immediate cost ${\bm{c}}_{t}\in\mathbb{R}^{m}$, where $m$ is the number of constraints. The decisions are made according to a policy $\pi$. At each state, a policy is a distribution over action space.

In the following, we consider two types of policies. Deterministic policy chooses a single action deterministically for any state, and can be identified by the mapping $\pi:\mathcal{S}\mapsto\mathcal{A}$. The set of all deterministic policies is denoted by $\Pi$. To improve the convergence of value-based methods, it is helpful to consider mixed deterministic policy $\Delta(\Pi)$ (Le et al., 2019; Bohez et al., 2019; Miryoosefi et al., 2019; Zahavy et al., 2021), where $\mu\in\Delta(\Pi)$ is a distribution over $\Pi$. To execute a policy $\mu\in\Delta(\Pi)$, we first select a policy $\pi\in\Pi$ according to $\pi\sim\mu$ and then execute $\pi$ for the entire episode.

For any discount factor $\gamma\in[0,1)$ and any policy $\pi\in\Delta(\Pi)$, the expectations of the discounted reward $J_{r}(\pi)$ and the discounted cost $J_{\bm{c}}(\pi)$ are defined as

where the expectation is over the stochastic process. To simplify notions, we define a policy’s measurement vector as the $(m+1)$-dimensional vector containing the expectations of the discounted reward $J_{r}(\pi)$ and the discounted cost $J_{\bm{c}}(\pi)$ ,

In offline constrained RL, we have a pre-collected dataset $D:=\{(s_{i},a_{i},s_{i}^{\prime},r_{i},{\bm{c}}_{i})\}_{i=1}^{n}$ containing transitions generated from (possibly multiple) behavior policies, jointly denoted as $\pi_{B}$. The goal in offline constrained RL is to find an optimal policy, denoted as $\mu^{*}$, that maximizes the reward subject to the constraints

where $\tau\in\mathbb{R}^{m}$ is vector of known constants. For an optimal policy $\mu^{*}$, $J_{r}(\mu^{*})$ is called the optimal value of the problem. To simplify the discussion, for any $\mu$ not satisfying the constraints, let $J_{r}(\mu):=-\infty$.

Without the constraints, learning optimal policy from a pre-collected dataset is a well-studied problem. For such problems, many effective methods rely on Q-learning to learn in an off-policy style and find optimal deterministic policies efficiently (Sutton and Barto, 2018). However, different from the unconstrained case, for constrained RL, none of the optimal policies may be deterministic. We illustrate this with the following example.

Therefore to solve offline constrained RL, it is common to consider using mixed deterministic policy.

We now show that the offline constrained RL problem (1) can be reformulated to an equilibrium problem (2), which can then be solved using online learning techniques.

We first relax the constrained problem (1) into an equivalent unconstrained optimization problem, where the value function is penalized by the constraint violation. Using a Lagrangian multiplier ${\bm{\lambda}}\in\mathbb{R}^{m}_{+}$, we construct the Lagrangian

We show that solving the optimal value of the original constrained problem (1) is equivalent to solving the equilibrium or saddle point of this unconstrained problem

By a standard Lagrangian argument, $\forall\mu\in\Delta(\Pi)$ that violates certain constraints, by setting the corresponding dimensions of ${\bm{\lambda}}$ to $\infty$, and $0$ otherwise, then $L(\mu,{\bm{\lambda}})=-\infty$. On the other hand, for any feasible policy $\mu$, since all elements in $J_{\bm{c}}(\mu)-\tau$ are non-positive, the inner minimization is achieved when ${\bm{\lambda}}={\bm{0}}$. The outer maximization is then realized by certain feasible policies that maximize the discounted reward $J_{r}(\mu)$. Hence, we conclude the equivalence between the constrained task (1) and the unconstrained one (2).

We then take a game-theoretic perspective and solve the equilibrium finding problem (2) with online learning. From a game-theoretic perspective, the equilibrium finding problem (2) can be viewed as a two-player zero-sum game. The $\mu$ player plays against ${\bm{\lambda}}$ player, where $L(\mu,{\bm{\lambda}})$ is the utility gained by $\mu$ player and the loss suffered by the ${\bm{\lambda}}$ player. The equilibrium of this game can be solved by the general technique of (Freund and Schapire, 1999) by repetitively playing a no-regret online learning algorithm against a best response learner.

We take a brief review of the online learning framework, where the core idea is the existence of no-regret learners (Shalev-Shwartz et al., 2011). For a learner who makes a sequence of decisions, the no-regret property means the cumulative loss by the current learning algorithm converges to the best-fixed strategy in the hindsight sublinearly. That is, after making $T$ decisions,

where ${\bm{\lambda}}_{t}=\mathtt{Learner}(L(\mu_{1},\cdot),\dots,L(\mu_{t-1},\cdot))$ is generated by the online learning algorithm given the loss function of all previous plays. We also consider learners that are prescient, i.e. that can choose ${\bm{\lambda}}_{t}$ with the knowledge of $L(\mu_{t},\cdot)$ the loss function up to and including time $t$.

Perhaps the most trivial strategy in a prescient setting is simply to play the best choice for the current loss function. The best response strategy assumes the knowledge of the other player’s play, and simply maximizes utility for the current loss function. For the $\mu$ player, this can be defined as

Online Gradient Descent (OGD) (Zinkevich, 2003) is a typical online learning algorithm, defined as follows

By setting appropriate learning rate, it has no-regret. Usually, the learning rate can be set adaptively with $\eta_{t}:=1/\sqrt{t}$, then the regret bound is $O(1/\sqrt{T})$ (Zinkevich, 2003).

The method of Freund and Schapire (1999) to solve the equilibrium finding problem can be summarized as Algorithm 1, where the $\mathtt{Learner}$ can be, for example, the OGD defined in (3). As stated in the following proposition, the average of players’ decisions converges to the equilibrium point.

When running Algorithm 1 in practice, $\hat{{\bm{\lambda}}}$ can be easily maintained in place as a vector, and updated via $\hat{{\bm{\lambda}}}=\hat{{\bm{\lambda}}}\cdot(t-1)/t+{\bm{\lambda}}_{t}/t$ at each round. However, it is much more difficult to maintain the mixed policy $\mu$ in our scenario where deep neural networks are typically used as function approximators. Since neural networks are not linear, to recover the mixed policy, it requires to store the parameters of all individual policies $\{\pi_{1},\dots,\pi_{T}\}$. The memory cost is prohibitively expensive since the neural networks can be considerably large.

To overcome this problem, in the following section, we introduce a novel notion of Affinely Independent Mixed (AIM) policy, which reformulates any mixed policy based on only constantly many individual policies, which successfully reduces the memory cost of mixed policy methods to a constant.

We first introduce some notations and definitions regarding mixed policy. For any mixed policy $\mu\in\Delta(\Pi)$, we define its active policy set $S_{p}(\mu)$ as the set of all deterministic policies with a non-zero probability in $\mu$. i.e.,¹¹1We here slightly abuse $\mu(\pi)\in[0,1]$ to denote the probability of any deterministic policy $\pi\in\Pi$ in the mixed policy $\mu$.

We also define its active measurement set $S_{x}(\mu)$ as the set of the measurement vectors of all these active policies, i.e.,

Recall that the measurement vector of $\mu$ is given as

Suppose the active policy set is finite, i.e., $S_{p}(\mu)=\{\pi_{1},...,\pi_{k}\}$, then we equivalently have

which is a convex combination of its active measurement vectors ${\bm{x}}(\pi_{1}),...,{\bm{x}}(\pi_{k})$ in $S_{\bm{x}}(\mu)$.

We call $\mu$ an AIM policy, if its active measurement vectors are affinely independent of each other. Intuitively, the AIM policy characterizes a family of mixed policies with a relatively small active policy set. Specifically, if some mixed policy $\mu^{\prime}\in\Delta(\Pi)$ is not an AIM policy, namely the elements in $S_{\bm{x}}(\mu^{\prime})$ are affinely dependent, we can pick several affinely independent elements such that ${\bm{x}}(\mu^{\prime})$ lies in the convex hull of these elements. In this case, by adjusting the mixing weights accordingly, the mixed policy $\mu^{\prime}$ can be recovered with a smaller active policy set.

To formalize the above reduction, notice that for an AIM policy $\mu$, its active measurement vectors are affinely independent and form a simplex in $\mathbb{R}^{m+1}$. For any policy $\mu^{\prime}$ whose measurement vector ${\bm{x}}(\mu^{\prime})$ lies in the affine hull ${\mathtt{aff}}(S_{\bm{x}}(\mu))$, its barycentric coordinate ${\bm{\alpha}}\in\mathbb{R}^{k}$ can be solved via

If $\alpha_{i}\geq 0$ for any $i$, then ${\bm{x}}(\mu^{\prime})$ lies inside the convex hull ${\mathtt{conv}}(S_{\bm{x}}(\mu))$. In this case, we can achieve the same measurement vector ${\bm{x}}(\mu^{\prime})$ of $\mu^{\prime}$ by randomly choosing the policy $\pi_{i}\in S_{p}(\mu)$ with probability $\alpha_{i}$. In this way, we only need to store the policies in $S_{p}(\mu)$, which might be smaller than $S_{p}(\mu^{\prime})$.

In summary, any mixed policy can be equivalently realized by randomly sampling with proper weights from several deterministic policies that are affinely independent in the measurement space $\mathbb{R}^{m+1}$. Since $\mathbb{R}^{m+1}$ is the affine span of any $m+2$ affinely independent vectors, intuitively we can reduce the number of the stored individual policies to at most $m+2$. In the following, we devise two algorithms that realize the AIM policy.

We first propose AIM-mean (Algorithm 2), which realizes the original mixed policy method (Algorithm 1) via AIM policies. At each round $t$, AIM-mean outputs an AIM policy whose measurement vector is equal to the average measurement of all historical policies, i.e.,

Therefore, AIM-mean evolves exactly the same as the original method, which ensures convergence to the optimal policy, while requiring to store no more than $m+2$ individual policies.

The core step of AIM-mean is the maintenance of the active policy set of the output mixed policy, which we now explicate in detail. At the beginning of each round $t$, the algorithm receives a new policy $\pi_{t}$ generated by the original algorithm, whose measurement vector takes ${\bm{x}}(\pi_{t})\in\mathbb{R}^{m+1}$. After receiving the policy, we first calculate the target vector ${\bm{x}}_{t}$ (i.e., the average measurement vector) at the current round, then decide whether we should alter the active set:

(i) If ${\bm{x}}_{t}\notin{\mathtt{aff}}(S_{\bm{x}}(\mu_{t-1}))$, this implies that the size of $S_{\bm{x}}(\mu_{t-1})$ is less than $m+2$ (otherwise we have ${\mathtt{aff}}(S_{\bm{x}}(\mu_{t-1}))=\mathbb{R}^{m+1}$). In this case, ${\bm{x}}(\pi_{t})$ is affinely independent of any vector in the current active set $S_{\bm{x}}(\mu_{t-1})$, and we add ${\bm{x}}(\pi_{t})$ to the active set.

(ii) If ${\bm{x}}_{t}\in{\mathtt{conv}}(S_{\bm{x}}(\mu_{t-1}))$, then we maintain the active set as $S_{\bm{x}}(\mu_{t-1})$. Now we just need to recalculate the mixing weights of the elements in $S_{\bm{x}}(\mu_{t-1})$ regarding ${\bm{x}}_{t}$ via (5).

(iii) If ${\bm{x}}_{t}\in{\mathtt{aff}}(S_{\bm{x}}(\mu_{t-1}))$ and $x_{t}\notin{\mathtt{conv}}(S_{\bm{x}}(\mu_{t-1}))$, then we need to alter the elements in active set and express ${\bm{x}}_{t}$ as a convex combination. Intuitively, we can replace one element in $S_{\bm{x}}(\mu_{t-1})$ by ${\bm{x}}(\pi_{t})$ so that the simplex formed by the new active set contains ${\bm{x}}_{t}$. Notice that since ${\bm{x}}(\mu_{t-1})$ and ${\bm{x}}_{t}$ lie inside and outside of the original simplex respectively, the segment joining the two points must cross the boundary of the original simplex. Therefore, we can find the specific facet where the intersection locates at, remove any vertex in $S_{\bm{x}}(\mu_{t-1})$ that is not on this facet, and add the new policy to the active set.

The above procedure of removing vertex is summarized as the $\mathtt{RemoveOneVertex}(S_{\bm{x}},{\bm{x}}_{t-1},{\bm{x}}_{t})$ subroutine, which takes three arguments, namely the vertices of the simplex $S_{\bm{x}}$, previous average measurement vector ${\bm{x}}_{t-1}$, and the target vector ${\bm{x}}_{t}$. $\mathtt{RemoveOneVertex}$ first finds the intersection of the above segment and the facet of the simplex, then replaces a random vertex that is not on the facet with the new policy $x(\pi_{t})$ at the current round. Specifically, assume ${\bm{\alpha}}_{t-1}$ and ${\bm{\alpha}}_{t}$ as the barycentric coordinates of ${\bm{x}}_{t-1}$ and ${\bm{x}}_{t}$ with respect to $S_{\bm{x}}$. Denote ${\bm{\alpha}}_{t}=(\alpha_{t,1},...,\alpha_{t,m+1})$. Since ${\bm{x}}_{t}\notin{\mathtt{conv}}(S_{\bm{x}})$, some entries of ${\bm{\alpha}}_{t}$ must be non-positive. Hence, we can set

Then ${\bm{\alpha}}_{t}\leftarrow\theta{\bm{\alpha}}_{t}+(1-\theta){\bm{\alpha}}_{t-1}$ is the point on the facet of the simplex. Now we just need to remove any vertex in $S_{\bm{x}}$ whose weight corresponding to $\alpha_{t}$ is non-positive, and update ${\bm{x}}_{t-1}\leftarrow\theta{\bm{x}}_{t}+(1-\theta){\bm{x}}_{t-1}$ accordingly.

After updating the active set $S_{\bm{x}}$ and the mixing weights ${\bm{\alpha}}_{t}$, we repeatedly call $\mathtt{RemoveOneVertex}$ to remove any vertex that does not contribute to ${\bm{x}}_{t}$. This further reduces the number of the stored individual policies without affecting the output mixed policy $\mu_{t}$.

It can be easily checked that at the end of each round, $S_{\bm{x}}$ is an affinely independent set and ${\bm{x}}_{t}\in{\mathtt{conv}}(S_{\bm{x}})$. This validates the correctness of AIM-mean, as summarized in the following.

Recall that classic mixed policy methods randomly select an individual policy from all historical policies via uniform sampling. There is another heuristic method (Le et al., 2019) that selects the single-best policy among all individual policies, which improves the empirical performance despite lack of convergence guarantee. To improve the practical performance, we propose a novel variant called AIM-greedy by removing ”bad” active policies in the mixed policy. Although it may not converge, AIM-greedy consistently outperforms the previous heuristic method in experiment, hence it is favorable for practical usage.

As described in Algorithm 3, AIM basically follows the procedure of AIM-mean to ensure the AIM property, except that it uses a more radical target vector ${\bm{x}}_{t}$ than AIM-mean.

To decide the target vector, AIM-greedy performs a greedy line search on the segment between the previous target vector ${\bm{x}}_{t-1}={\bm{x}}(\mu_{t-1})$ and the new policy ${\bm{x}}(\pi_{t})$, and selects a target vector ${\bm{x}}_{t}$ that maximizes the reward at the premise of least constraint violation. Specifically, (i) if both ${\bm{x}}_{t-1}$ and ${\bm{x}}(\pi_{t})$ satisfy the constraints, we set ${\bm{x}}_{t}$ to the policy with a higher reward; (ii) if neither satisfies the constraints, we choose the policy whose Euclidean distance to the target constraints is smaller; (iii) If one satisfies while the other does not, and the infeasible policy has the higher reward, we move ${\bm{x}}_{t}$ to the boundary of the constraints (i.e., line 6 in Algorithm 5.2).

In fact, AIM-greedy generalizes the idea of selecting the single best policy and is guaranteed to perform no worse than any single best policy.

We then discuss the optimal policy efficiency which shows that our AIM policy achieves optimal policy efficiency.

Since the affinely independent properties ensure the AIM-type policies store no more than $m+2$ policies throughout the learning process, and hence the storage complexity is optimal to ensure convergence when learning from off-policy samples.

During the marketing campaign, Alipay uses an online A/B testing system to perform user-level randomization; for a small percentage of users, a random budget allocation policy is used to assign coupon values. After running this randomized trial for a week in Dec 2020, 4.2 million samples are collected. Since the random strategy is likely to be non-optimal, given the average coupon amount of about 2.5 yuan, the collection of these samples is indeed expensive. Each sample has about one thousand raw features, which include timestamp, age, gender, city, and other behavior features. After one-hot encoding, all samples take around one hundred thousand different values. The label of each sample is the corresponding user’s DAU over the next 1/3/7 days.

The full dataset takes about 56 gigabytes on disk, and our deployed model is implemented with the company’s private distributed model training infrastructure that supports high-dimensional embedding lookup tables. To simplify the tuning process, we also create a simplified data set, which contains only 2 user features, 1) whether the user participated in the previous day, which is a boolean value, and 2) the activeness level of the user. The results on both datasets are qualitatively similar and are both reported.

We conduct a series of A/B experiments in a live system serving tens of millions of users and handing out more than one billion yuan worth cash coupons. Figure 3 illustrates the online request serving process and the offline training procedure. We train the model using BCQ, where the $\lambda$ is updated by an OGD method. The model is evaluated by an AIM-greedy method, and if the current policy shall be added into the mixed policy, the model parameters will be exported to disk, together with the weight for all exported models. These models are then loaded to our online serving machines, to provide online budget allocation services.

The online experiment is conducted by performing user-level randomization. We start an online experiment with a small percentage of traffic and gradually increase the traffic. The offline constrained deep RL model is compared with the baseline model that uses DIN with a linear programming solver to find the allocation plan. The online experiment run for a week, with 5.5 million cash coupons sent by each of the models. Though the offline constrained RL method has a lower coupon redemption rate (1d DAU) than the previous DIN model, after running the experiment for a week, it improves the weekly average DAU by 0.6% (7d DAU) for the app. Meanwhile, it reduces the coupon cost by 0.8%. Our retrospective analysis shows that the emphasis on long-term value drives this model to allocate more budgets to inactive users, and accelerate the process of user acquisition. The more frequent retention of these inactive users compensates for the short-term metrics deterioration of active users. The model is then successfully deployed to the full traffic during the marketing campaign after a week’s A/B testing.