Research map / Reinforcement learning / Policy gradient and actor-critic
Maximizing the Success Probability of Policy Allocations in Online Systems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SuccessProbaMax, which allocates user-level bidding policies per bucket by gradient ascent on a Gaussian approximation of the probability that the total (value, cost) outcome lands in a success region relative to a reference policy.
Problem
Policy allocation for online advertising budgets: standard expected-value knapsack formulations maximize expected value under expected cost constraints, which ignores outcome variance and the business notion of success (higher value without higher cost than a reference).
Approach
Reformulate policy allocation to maximize the probability that the aggregate outcome falls in a convex success region, approximate the outcome distribution as Gaussian with allocation-dependent mean and variance, and optimize soft allocations via gradient ascent with an analytic or autodiff gradient.
Key results
- On the private dataset, SuccessProbaMax reaches a 0.01 value gain over reference with probability 0.7 on train and 0.4 on test, versus 0.35 and 0.1 for MixedInt.
- On the one-dimensional private dataset, the method reaches a 2.9% gain with probability almost 1 while Greedy1D reaches about 0.7.
- On CRITEO-UPLIFT v2 it finds higher success probability than Bruteforce in some regions (e.g. r_c in [0.03,0.04], r_v in [0.04,0.08]), with value rising roughly 2x as fast as cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize success probability with SuccessProbaMax instead of mean value with MixedInt | policy allocation · Private dataset, two-dimensional outcome, train | success probability: 0.35 -> 0.7 | Helped |
| Optimize success probability with SuccessProbaMax instead of mean value with MixedInt | policy allocation · Private dataset, two-dimensional outcome, test | success probability: 0.1 -> 0.4 | Helped |
| Optimize success probability with SuccessProbaMax instead of mean outcome with Greedy1D | policy allocation · Private dataset, one-dimensional outcome, Gain 0.029 | success probability: around 0.7 -> almost 1 | Helped |
| Use small rather than large variance | SuccessProbaMax versus Greedy1D · Synthetic one-dimensional outcome | success probability | Mixed |
| Start from uniform allocation rather than a warm-start or explored allocation | SuccessProbaMax · Synthetic one-dimensional outcome, small variance, r > 6 | success probability | Hurt |
| Optimize success probability instead of mean value | policy allocation · CRITEO-UPLIFT v2, two-dimensional outcome | success probability | Mixed |
Surprising findings
- On the toy Gaussian example, the success-probability optimum (allocating all to the lower-mean, lower-variance policy) differs from the greedy mean-maximizing allocation.
- Hard (Bruteforce/MixedInt) allocations can be outperformed by soft allocations for some success regions.
Limitations
- Gaussian approximation of aggregate outcomes via the Lyapunov CLT, with the variance assumed linear in allocation.
- Gradient vanishes when the reference criterion is 0 (flat regions), requiring warm starts or random initialization.
- Bucket partitioning is assumed given and not optimized jointly; parameter estimation noise is largely excluded from the main analysis.
Experimental setup
Datasets: CRITEO-UPLIFT v2 Private RTB RCT dataset Synthetic Gaussian data
Benchmarks: CRITEO-UPLIFT v2 Private RTB dataset Synthetic Gaussian setups
Metrics: success probability success rate
Baselines: Bruteforce Greedy1D LinProg MixedInt
Builds on: multiple choice knapsack problem Lagrangian relaxation causal trees
Closest papers by meaning
- Utility Maximizer or Value Maximizer: Mechanism Design for Mixed Bidders in Online Advertising (AAAI 2023 · similarity 0.88)
- Real-Time Bidding with Side Information (NeurIPS 2017 · similarity 0.88)
- Leveraging the Hints: Adaptive Bidding in Repeated First-Price Auctions (NeurIPS 2022 · similarity 0.88)
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.86)
- LLM-Auction: Generative Auction towards LLM-Native Advertising (NeurIPS 2026 · similarity 0.86)
- AuctionNet: A Novel Benchmark for Decision-Making in Large-Scale Games (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.