Near-Optimal Experimental Design Under the Budget Constraint in Online Platforms

• URL: http://arxiv.org/abs/2302.05005v1
• Date: Fri, 10 Feb 2023 01:24:52 GMT
• Title: Near-Optimal Experimental Design Under the Budget Constraint in Online Platforms
• Authors: Yongkang Guo, Yuan Yuan, Jinshan Zhang, Yuqing Kong, Zhihua Zhu, Zheng Cai
• Abstract summary: A/B testing, or controlled experiments, is the gold standard approach to causally compare the performance of algorithms on online platforms. We develop a model to describe two-sided platforms where buyers have limited budgets. We provide an optimal experimental design that guarantees small bias and minimum variance.
• Score: 13.203565751596221
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A/B testing, or controlled experiments, is the gold standard approach to causally compare the performance of algorithms on online platforms. However, conventional Bernoulli randomization in A/B testing faces many challenges such as spillover and carryover effects. Our study focuses on another challenge, especially for A/B testing on two-sided platforms -- budget constraints. Buyers on two-sided platforms often have limited budgets, where the conventional A/B testing may be infeasible to be applied, partly because two variants of allocation algorithms may conflict and lead some buyers to exceed their budgets if they are implemented simultaneously. We develop a model to describe two-sided platforms where buyers have limited budgets. We then provide an optimal experimental design that guarantees small bias and minimum variance. Bias is lower when there is more budget and a higher supply-demand rate. We test our experimental design on both synthetic data and real-world data, which verifies the theoretical results and shows our advantage compared to Bernoulli randomization.

Related papers

• Towards Understanding Dual BN In Hybrid Adversarial Training [79.92394747290905]
  We show that disentangling statistics plays a less role than disentangling affine parameters in model training. We propose a two-task hypothesis which serves as the empirical foundation and a unified framework for Hybrid-AT improvement.
  arXiv  Detail & Related papers  (2024-03-28T05:08:25Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• Towards Optimal Statistical Watermarking [95.46650092476372]
  We study statistical watermarking by formulating it as a hypothesis testing problem. Key to our formulation is a coupling of the output tokens and the rejection region. We characterize the Uniformly Most Powerful (UMP) watermark in the general hypothesis testing setting.
  arXiv  Detail & Related papers  (2023-12-13T06:57:00Z)
• Deep anytime-valid hypothesis testing [29.273915933729057]
  We propose a general framework for constructing powerful, sequential hypothesis tests for nonparametric testing problems. We develop a principled approach of leveraging the representation capability of machine learning models within the testing-by-betting framework. Empirical results on synthetic and real-world datasets demonstrate that tests instantiated using our general framework are competitive against specialized baselines.
  arXiv  Detail & Related papers  (2023-10-30T09:46:19Z)
• Task-specific experimental design for treatment effect estimation [59.879567967089145]
  Large randomised trials (RCTs) are the standard for causal inference. Recent work has proposed more sample-efficient alternatives to RCTs, but these are not adaptable to the downstream application for which the causal effect is sought. We develop a task-specific approach to experimental design and derive sampling strategies customised to particular downstream applications.
  arXiv  Detail & Related papers  (2023-06-08T18:10:37Z)
• A Common Misassumption in Online Experiments with Machine Learning Models [1.52292571922932]
  We argue that, because variants typically learn using pooled data, a lack of model interference cannot be guaranteed. We discuss the implications this has for practitioners, and for the research literature.
  arXiv  Detail & Related papers  (2023-04-21T11:36:44Z)
• Delving into Identify-Emphasize Paradigm for Combating Unknown Bias [52.76758938921129]
  We propose an effective bias-conflicting scoring method (ECS) to boost the identification accuracy. We also propose gradient alignment (GA) to balance the contributions of the mined bias-aligned and bias-conflicting samples. Experiments are conducted on multiple datasets in various settings, demonstrating that the proposed solution can mitigate the impact of unknown biases.
  arXiv  Detail & Related papers  (2023-02-22T14:50:24Z)
• Online Learning under Budget and ROI Constraints via Weak Adaptivity [57.097119428915796]
  Existing primal-dual algorithms for constrained online learning problems rely on two fundamental assumptions. We show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions.
  arXiv  Detail & Related papers  (2023-02-02T16:30:33Z)
• Hypothesis Testing for Equality of Latent Positions in Random Graphs [0.2741266294612775]
  We consider the hypothesis testing problem that two vertices $i$ and $j$th have the same latent positions, possibly up to scaling. We propose several test statistics based on the empirical Mahalanobis distances between the $i$th and $j$th rows of either the adjacency or the normalized Laplacian spectral embedding of the graph. Using these test statistics, we address the model selection problem of choosing between the standard block model and its degree-corrected variant.
  arXiv  Detail & Related papers  (2021-05-23T01:27:23Z)
• TSEC: a framework for online experimentation under experimental constraints [1.1470070927586016]
  Thompson sampling is a popular algorithm for solving multi-armed bandit problems. We propose a new Thompson Sampling under Experimental Constraints (TSEC) method, which addresses this so-called "arm budget constraint" We demonstrate the effectiveness of TSEC in two problems with arm budget constraints.
  arXiv  Detail & Related papers  (2021-01-17T05:04:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.