Early Stopping in Contextual Bandits and Inferences

• URL: http://arxiv.org/abs/2502.02793v1
• Date: Wed, 05 Feb 2025 00:40:10 GMT
• Title: Early Stopping in Contextual Bandits and Inferences
• Abstract summary: Excessive sampling can be costly, motivating the devolopment of early stopping methods and reliable post-experiment inferences.<n>This paper studies early stopping methods in linear contextual bandits, including both pre-determined and online stopping rules, to minimize in-experiment regrets while accounting for sampling costs.
• Score: 0.5439020425819
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bandit algorithms sequentially accumulate data using adaptive sampling policies, offering flexibility for real-world applications. However, excessive sampling can be costly, motivating the devolopment of early stopping methods and reliable post-experiment conditional inferences. This paper studies early stopping methods in linear contextual bandits, including both pre-determined and online stopping rules, to minimize in-experiment regrets while accounting for sampling costs. We propose stopping rules based on the Opportunity Cost and Threshold Method, utilizing the variances of unbiased or consistent online estimators to quantify the upper regret bounds of learned optimal policy. The study focuses on batched settings for stability, selecting a weighed combination of batched estimators as the online estimator and deriving its asymptotic distribution. Online statistical inferences are performed based on the selected estimator, conditional on the realized stopping time. Our proposed method provides a systematic approach to minimize in-experiment regret and conduct robust post-experiment inferences, facilitating decision-making in future applications.

Related papers

• BayesFP: Posterior Estimation for Flow-Based Policies via Feynman-Kac Sampling [7.25385467896207]
  We develop a unified, inference-time, retraining-free sampler for flow-matching policies.<n>We show improvements on the base $_0.5 on zero-shot optimal tasks.
  arXiv  Detail & Related papers  (2026-06-19T00:55:24Z)
• Cost-optimal Sequential Testing via Doubly Robust Q-learning [17.865867651025717]
  We study the problem of learning cost-optimal sequential decision policies from retrospective data.<n>We develop a doubly robust Q-learning framework for estimating optimal policies.
  arXiv  Detail & Related papers  (2026-04-13T08:26:27Z)
• Contextual Preference Distribution Learning [5.872632454395936]
  We propose a sequential learning-and-optimization pipeline to learn preference distributions and leverage them to solve downstream problems.<n>We focus on human choice settings that can be formulated as (integer) linear programs.
  arXiv  Detail & Related papers  (2026-03-17T21:11:21Z)
• On the System Theoretic Offline Learning of Continuous-Time LQR with Exogenous Disturbances [3.701656361145375]
  We analyze offline designs of linear quadratic regulator (LQR) strategies with uncertain disturbances.<n>Our approach builds on the fundamental learning-based framework of adaptive dynamic programming.
  arXiv  Detail & Related papers  (2025-09-20T17:14:27Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [68.43987626137512]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Dependent Randomized Rounding for Budget Constrained Experimental Design [18.677808169753032]
  We propose a framework that applies a dependent randomized rounding procedure to convert assignment probabilities into binary treatment decisions.<n>Our proposed solution preserves the marginal treatment probabilities while inducing negative correlations among assignments, leading to improved estimator precision through variance reduction.
  arXiv  Detail & Related papers  (2025-06-15T01:10:06Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [56.92178753201331]
  We tackle average-reward infinite-horizon POMDPs with an unknown transition model.<n>We present a novel and simple estimator that overcomes this barrier.
  arXiv  Detail & Related papers  (2025-01-30T22:29:41Z)
• Regret Minimization and Statistical Inference in Online Decision Making with High-dimensional Covariates [7.21848268647674]
  We integrate the $varepsilon$-greedy bandit algorithm for decision-making with a hard thresholding algorithm for estimating sparse bandit parameters. Under a margin condition, our method achieves either $O(T1/2)$ regret or classical $O(T1/2)$-consistent inference.
  arXiv  Detail & Related papers  (2024-11-10T01:47:11Z)
• Adaptive Experimentation When You Can't Experiment [55.86593195947978]
  This paper introduces the emphconfounded pure exploration transductive linear bandit (textttCPET-LB) problem. Online services can employ a properly randomized encouragement that incentivizes users toward a specific treatment.
  arXiv  Detail & Related papers  (2024-06-15T20:54:48Z)
• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Bayesian Nonparametrics Meets Data-Driven Distributionally Robust Optimization [29.24821214671497]
  Training machine learning and statistical models often involve optimizing a data-driven risk criterion. We propose a novel robust criterion by combining insights from Bayesian nonparametric (i.e., Dirichlet process) theory and a recent decision-theoretic model of smooth ambiguity-averse preferences. For practical implementation, we propose and study tractable approximations of the criterion based on well-known Dirichlet process representations.
  arXiv  Detail & Related papers  (2024-01-28T21:19:15Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• Improved Policy Evaluation for Randomized Trials of Algorithmic Resource Allocation [54.72195809248172]
  We present a new estimator leveraging our proposed novel concept, that involves retrospective reshuffling of participants across experimental arms at the end of an RCT. We prove theoretically that such an estimator is more accurate than common estimators based on sample means.
  arXiv  Detail & Related papers  (2023-02-06T05:17:22Z)
• Reinforcement Learning for Adaptive Optimal Stationary Control of Linear Stochastic Systems [15.410124023805249]
  This paper studies the adaptive optimal stationary control of continuous-time linear systems with both additive and multiplicative noises. A novel off-policy reinforcement learning algorithm, named optimistic least-squares-based iteration policy, is proposed.
  arXiv  Detail & Related papers  (2021-07-16T09:27:02Z)
• Post-Contextual-Bandit Inference [57.88785630755165]
  Contextual bandit algorithms are increasingly replacing non-adaptive A/B tests in e-commerce, healthcare, and policymaking. They can both improve outcomes for study participants and increase the chance of identifying good or even best policies. To support credible inference on novel interventions at the end of the study, we still want to construct valid confidence intervals on average treatment effects, subgroup effects, or value of new policies.
  arXiv  Detail & Related papers  (2021-06-01T12:01:51Z)

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.