Best Arm Identification with Possibly Biased Offline Data

• URL: http://arxiv.org/abs/2505.23165v1
• Date: Thu, 29 May 2025 06:58:49 GMT
• Title: Best Arm Identification with Possibly Biased Offline Data
• Abstract summary: We study the best arm identification problem with potentially biased offline data in the fixed confidence setting.<n>We propose the LUCB-H algorithm, which introduces adaptive confidence bounds by incorporating an auxiliary bias correction.
• Score: 56.965938201853625
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the best arm identification (BAI) problem with potentially biased offline data in the fixed confidence setting, which commonly arises in real-world scenarios such as clinical trials. We prove an impossibility result for adaptive algorithms without prior knowledge of the bias bound between online and offline distributions. To address this, we propose the LUCB-H algorithm, which introduces adaptive confidence bounds by incorporating an auxiliary bias correction to balance offline and online data within the LUCB framework. Theoretical analysis shows that LUCB-H matches the sample complexity of standard LUCB when offline data is misleading and significantly outperforms it when offline data is helpful. We also derive an instance-dependent lower bound that matches the upper bound of LUCB-H in certain scenarios. Numerical experiments further demonstrate the robustness and adaptability of LUCB-H in effectively incorporating offline data.

Related papers

• Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift [24.048629084196904]
  A central challenge in offline-to-online learning is the distribution shift between offline and online data.<n>We propose a novel median-based anchoring rule that defines the arm index as the median of an online posterior sample, a hybrid posterior sample, and the online sample mean.<n>We establish theoretical guarantees showing that the proposed algorithm safely leverages offline data to accelerate online learning.
  arXiv  Detail & Related papers  (2026-05-11T09:50:58Z)
• Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms [10.146314852311638]
  We propose hybrid CMAB-T, a new framework that integrates offline data with online interaction in a principled manner.<n>Our proposed hybrid CUCB algorithm leverages offline data to guide exploration and accelerate convergence.<n>We provide theoretical guarantees on the algorithm's regret, demonstrating that hybrid CUCB significantly outperforms purely online approaches.
  arXiv  Detail & Related papers  (2025-12-26T08:42:12Z)
• Offline Clustering of Linear Bandits: The Power of Clusters under Limited Data [60.91600085523719]
  We study the offline clustering of bandits (Off-ClusBand) problem, which studies how to use the offline dataset to learn cluster properties and improve decision-making.<n>We propose two algorithms: Off-C2LUB, which we show analytically and experimentally outperforms existing methods under limited offline user data, and Off-CLUB, which may incur bias when data is sparse but performs well and nearly matches the lower bound when data is sufficient.
  arXiv  Detail & Related papers  (2025-05-25T08:43:40Z)
• Hybrid Reinforcement Learning from Offline Observation Alone [19.14864618744221]
  We consider the hybrid reinforcement learning setting where the agent has access to both offline data and online interactive access. We propose the first algorithm in the trace model setting that provably matches the performance of algorithms that leverage a reset model.
  arXiv  Detail & Related papers  (2024-06-11T13:34:05Z)
• Understanding the performance gap between online and offline alignment algorithms [63.137832242488926]
  We show that offline algorithms train policy to become good at pairwise classification, while online algorithms are good at generations. This hints at a unique interplay between discriminative and generative capabilities, which is greatly impacted by the sampling process. Our study sheds light on the pivotal role of on-policy sampling in AI alignment, and hints at certain fundamental challenges of offline alignment algorithms.
  arXiv  Detail & Related papers  (2024-05-14T09:12:30Z)
• Simple Ingredients for Offline Reinforcement Learning [86.1988266277766]
  offline reinforcement learning algorithms have proven effective on datasets highly connected to the target downstream task. We show that existing methods struggle with diverse data: their performance considerably deteriorates as data collected for related but different tasks is simply added to the offline buffer. We show that scale, more than algorithmic considerations, is the key factor influencing performance.
  arXiv  Detail & Related papers  (2024-03-19T18:57:53Z)
• The Role of Coverage in Online Reinforcement Learning [72.01066664756986]
  We show that the mere existence of a data distribution with good coverage can enable sample-efficient online RL. Existing complexity measures for online RL, including Bellman rank and Bellman-Eluder dimension, fail to optimally capture coverability. We propose a new complexity measure, the sequential extrapolation coefficient, to provide a unification.
  arXiv  Detail & Related papers  (2022-10-09T03:50:05Z)
• Distributed Semi-supervised Fuzzy Regression with Interpolation Consistency Regularization [38.16335448831723]
  We propose a distributed semi-supervised fuzzy regression (DSFR) model with fuzzy if-then rules and consistency regularization (ICR) Experiments results on both artificial and real-world datasets show that the proposed DSFR model can achieve much better performance than the state-of-the-art DSSL algorithm.
  arXiv  Detail & Related papers  (2022-09-18T04:46:51Z)
• Federated Offline Reinforcement Learning [55.326673977320574]
  We propose a multi-site Markov decision process model that allows for both homogeneous and heterogeneous effects across sites. We design the first federated policy optimization algorithm for offline RL with sample complexity. We give a theoretical guarantee for the proposed algorithm, where the suboptimality for the learned policies is comparable to the rate as if data is not distributed.
  arXiv  Detail & Related papers  (2022-06-11T18:03:26Z)
• Uncertainty-Based Offline Reinforcement Learning with Diversified Q-Ensemble [16.92791301062903]
  We propose an uncertainty-based offline RL method that takes into account the confidence of the Q-value prediction and does not require any estimation or sampling of the data distribution. Surprisingly, we find that it is possible to substantially outperform existing offline RL methods on various tasks by simply increasing the number of Q-networks along with the clipped Q-learning.
  arXiv  Detail & Related papers  (2021-10-04T16:40:13Z)
• Provably Efficient Causal Reinforcement Learning with Confounded Observational Data [135.64775986546505]
  We study how to incorporate the dataset (observational data) collected offline, which is often abundantly available in practice, to improve the sample efficiency in the online setting. We propose the deconfounded optimistic value iteration (DOVI) algorithm, which incorporates the confounded observational data in a provably efficient manner.
  arXiv  Detail & Related papers  (2020-06-22T14:49:33Z)

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.