Sequential incentive marketing is an important approach for online businesses
to acquire customers, increase loyalty and boost sales. How to effectively
allocate the incentives so as to maximize the return (e.g., business
objectives) under the budget constraint, however, is less studied in the
literature. This problem is technically challenging due to the facts that 1)
the allocation strategy has to be learned using historically logged data, which
is counterfactual in nature, and 2) both the optimality and feasibility (i.e.,
that cost cannot exceed budget) needs to be assessed before being deployed to
online systems. In this paper, we formulate the problem as a constrained Markov
decision process (CMDP). To solve the CMDP problem with logged counterfactual
data, we propose an efficient learning algorithm which combines bisection
search and model-based planning. First, the CMDP is converted into its dual
using Lagrangian relaxation, which is proved to be monotonic with respect to
the dual variable. Furthermore, we show that the dual problem can be solved by
policy learning, with the optimal dual variable being found efficiently via
bisection search (i.e., by taking advantage of the monotonicity). Lastly, we
show that model-based planing can be used to effectively accelerate the joint
optimization process without retraining the policy for every dual variable.
Empirical results on synthetic and real marketing datasets confirm the
effectiveness of our methods.

本文提出采用 CMDP 框架和模型规划相结合的学习算法，解决了在线商业活动中如何高效地分配奖励从以往的历史订单数据中学习策略的问题。实验结果表明了本方法的有效性。