Budget Allocation using Weakly Coupled, Constrained Markov Decision Processes

Craig Boutilier, Tyler LuUAI 2016 · OpenReview

Abstract

Managing resource-constrained sequential decisions is a critical challenge in large-scale systems such as online advertising. This paper introduces Budgeted MDPs (BMDPs), a framework where optimal policies are computed as a function of available budget. By framing the allocation of a global budget across millions of users as a Multiple-Choice Knapsack Problem, the authors develop a greedy algorithm that optimizes total expected return while significantly outperforming traditional uniform allocation methods.

Introduction

In online advertising, every action—such as displaying an ad or sending an email—incurs a cost, while the objective is to maximize long-term rewards like conversions. Standard Markov Decision Processes (MDPs) are designed to maximize rewards but often fail to account for these costs. While Constrained MDPs (CMDPs) address this by enforcing budget limits, they typically require these limits to be fixed a priori for each individual user.

This approach is inefficient for advertisers managing millions of users. A "one-size-fits-all" budget per user ignores the reality that some users are significantly more likely to convert than others. The authors address this "Weakly Coupled" problem: how to optimally distribute a single, shared global budget across a massive population of independent users to maximize the total expected return.

Methodology

Budgeted MDPs (BMDPs)

The core innovation is the shift from solving for a single budget $b$ to solving for all possible budgets. The authors prove that the optimal value function $V(s, b)$ is Piecewise-Linear and Concave (PWLC). This concavity is crucial; it implies that the marginal return on investment (the slope of the function) decreases as more budget is allocated to a specific user state.

Piecewise-Linear and Concave (PWLC) Value Function

Greedy Budget Allocation (GBA)

Leveraging the concavity of the value functions, the global allocation problem is transformed into a variant of the Multiple-Choice Knapsack Problem (MCKP). The authors propose a Greedy Budget Allocation (GBA) algorithm. By calculating the "bang-per-buck" (BpB) ratio—the slope of the PWLC value function—the algorithm incrementally assigns budget to the users or states that provide the highest marginal return.

Dynamic Reallocation

To account for the stochastic nature of MDPs, the authors introduce Dynamic Budget Reallocation (DBRA). Since a user's actual spend may deviate from the expected spend, the global budget is re-allocated at every time step based on the current state of the entire population, ensuring the global constraint is respected while maintaining optimality.

Experimental Evaluation

The framework was evaluated using both synthetic and real-world datasets:

  1. Synthetic Ad MDP: A 15-state model simulating a typical purchase funnel, ranging from initial lack of interest to final conversion. This model allowed for exact computation and verification of the PWLC properties.
  2. Real-World Advertiser MDP: A large-scale dataset comprising 3.6 million trajectories and 10 million events. Using Variable-Order Markov Chain (VOMC) models, the researchers constructed a state space of over 450,000 states to test the scalability of the GBA algorithm.
Synthetic Ad MDP Purchase Funnel

Key Results and Insights

Computational Efficiency

Solving for every useful budget level can be computationally intensive. The authors implemented a pruning scheme to remove nearly collinear points on the PWLC function. In synthetic tests, this reduced the number of segments from over 3,000 to approximately 480, resulting in a 37x speedup with a negligible error of only 0.36%.

Performance Gains

The BMDP approach demonstrated superior performance across all tests:

  • Return on Investment: In a 1,000-user synthetic test, the BMDP policy yielded 2-3 times the return of static policies that strictly enforced per-user budgets.
  • Scalability: On the large-scale real-world model, GBA outperformed Uniform Budget Allocation (UBA) by up to 6.5%. For multi-million dollar advertising campaigns, such an improvement represents a significant increase in efficiency.
  • Risk Management: The DBRA scheme effectively mitigated the risk of overspending the global budget, a common issue in decentralized or static allocation systems.

Conclusion and Future Work

The BMDP framework provides a robust and scalable solution for global budget allocation in stochastic environments. By exploiting the concavity of the value function, the authors turn a potentially intractable problem into an efficient greedy optimization. Future research directions include addressing observability, as user intent is often a hidden state, and adapting the model for dynamic populations where users continuously enter and exit the system.

Summary updated

BibTeX
@inproceedings{boutilier2016budget,
  author = {Craig Boutilier and Tyler Lu},
  title = {{Budget Allocation using Weakly Coupled, Constrained Markov Decision Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=5dLQJ39smO_},
}
Figure