Regret minimization in Linear Bandits with offline data via extended D-optimal exploration

• URL: http://arxiv.org/abs/2508.08420v2
• Date: Wed, 13 Aug 2025 06:00:10 GMT
• Title: Regret minimization in Linear Bandits with offline data via extended D-optimal exploration
• Authors: Sushant Vijayan, Arun Suggala, Karthikeyan Shanmugam, Soumyabrata Pal,
• Abstract summary: We consider the problem of online regret in linear bandits with access to prior observations (offline data) from the underlying bandit model.<n>Our algorithm, Offline-Online Phased Elimination (OOPE), effectively incorporates the offline data to substantially reduce the online regret compared to prior work.
• Score: 25.533340168328564
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We consider the problem of online regret minimization in linear bandits with access to prior observations (offline data) from the underlying bandit model. There are numerous applications where extensive offline data is often available, such as in recommendation systems, online advertising. Consequently, this problem has been studied intensively in recent literature. Our algorithm, Offline-Online Phased Elimination (OOPE), effectively incorporates the offline data to substantially reduce the online regret compared to prior work. To leverage offline information prudently, OOPE uses an extended D-optimal design within each exploration phase. OOPE achieves an online regret is $\tilde{O}(\sqrt{\deff T \log \left(|\mathcal{A}|T\right)}+d^2)$. $\deff \leq d)$ is the effective problem dimension which measures the number of poorly explored directions in offline data and depends on the eigen-spectrum $(\lambda_k)_{k \in [d]}$ of the Gram matrix of the offline data. The eigen-spectrum $(\lambda_k)_{k \in [d]}$ is a quantitative measure of the \emph{quality} of offline data. If the offline data is poorly explored ($\deff \approx d$), we recover the established regret bounds for purely online setting while, when offline data is abundant ($\Toff >> T$) and well-explored ($\deff = o(1) $), the online regret reduces substantially. Additionally, we provide the first known minimax regret lower bounds in this setting that depend explicitly on the quality of the offline data. These lower bounds establish the optimality of our algorithm in regimes where offline data is either well-explored or poorly explored. Finally, by using a Frank-Wolfe approximation to the extended optimal design we further improve the $O(d^{2})$ term to $O\left(\frac{d^{2}}{\deff} \min \{ \deff,1\} \right)$, which can be substantial in high dimensions with moderate quality of offline data $\deff = \Omega(1)$.

Related papers

• Contextual Online Pricing with (Biased) Offline Data [22.723289890639723]
  We study contextual online pricing with biased offline data.<n>An Optimism-in-the-Face-of-Uncertainty (OFU) policy achieves a minimax-optimal, instance-dependent regret bound $tildemathcalObig.
  arXiv  Detail & Related papers  (2025-07-03T16:21:49Z)
• Augmenting Online RL with Offline Data is All You Need: A Unified Hybrid RL Algorithm Design and Analysis [18.323002218335215]
  This paper investigates a hybrid learning framework for reinforcement learning (RL) in which the agent can leverage both an offline dataset and online interactions to learn the optimal policy.<n>We present a unified algorithm and analysis and show that augmenting confidence-based online RL algorithms with the offline dataset outperforms any pure online or offline algorithm alone.
  arXiv  Detail & Related papers  (2025-05-19T22:58:54Z)
• On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures [63.36095790552758]
  This article reviews the recent advances on the statistical foundation of reinforcement learning (RL) in the offline and low-adaptive settings.<n>We will start by arguing why offline RL is the appropriate model for almost any real-life ML problems, even if they have nothing to do with the recent AI breakthroughs that use RL.<n>We will zoom into two fundamental problems of offline RL: offline policy evaluation (OPE) and offline policy learning (OPL)
  arXiv  Detail & Related papers  (2025-01-03T20:27:53Z)
• Order-Optimal Instance-Dependent Bounds for Offline Reinforcement Learning with Preference Feedback [56.6950165117658]
  We consider offline reinforcement learning with preference feedback in which the implicit reward is a linear function of an unknown parameter. We propose an algorithm, underlineRL with underlineLocally underlineOptimal underlineWeights or sc RL-LOW, which yields a simple regret of $exp. We observe that the lower and upper bounds on the simple regret match order-wise in the exponent, demonstrating order-wise optimality of sc RL-LOW.
  arXiv  Detail & Related papers  (2024-06-18T02:03:12Z)
• Leveraging Offline Data in Linear Latent Contextual Bandits [27.272915631913175]
  We design end-to-end latent bandit algorithms capable of handing uncountably many latent states.<n>We present two online algorithms that utilize the output of this offline algorithm to accelerate online learning.
  arXiv  Detail & Related papers  (2024-05-27T16:23:34Z)
• Optimal Best-Arm Identification in Bandits with Access to Offline Data [27.365122983434887]
  We consider combining offline data with online learning, an area less studied but obvious practical importance. We develop algorithms that match the lower bound on sample complexity when $delta$ is small. Our algorithms are computationally efficient with an average per-sample acquisition cost of $tildeO(K)$, and rely on a careful characterization of the optimality conditions of the lower bound problem.
  arXiv  Detail & Related papers  (2023-06-15T11:12:35Z)
• On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation [80.86358123230757]
  We present an algorithm called Bootstrapped and Constrained Pessimistic Value Iteration (BCP-VI) Under a partial data coverage assumption, BCP-VI yields a fast rate of $tildemathcalO(frac1K)$ for offline RL when there is a positive gap in the optimal Q-value functions. These are the first $tildemathcalO(frac1K)$ bound and absolute zero sub-optimality bound respectively for offline RL with linear function approximation from adaptive data.
  arXiv  Detail & Related papers  (2022-11-23T18:50:44Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  We study offline reinforcement learning (RL) in partially observable Markov decision processes. We propose the underlineProxy variable underlinePessimistic underlinePolicy underlineOptimization (textttP3O) algorithm. textttP3O is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.
  arXiv  Detail & Related papers  (2022-05-26T19:13:55Z)
• Provably Efficient Generative Adversarial Imitation Learning for Online and Offline Setting with Linear Function Approximation [81.0955457177017]
  In generative adversarial imitation learning (GAIL), the agent aims to learn a policy from an expert demonstration so that its performance cannot be discriminated from the expert policy on a certain reward set. We study GAIL in both online and offline settings with linear function approximation, where both the transition and reward function are linear in the feature maps.
  arXiv  Detail & Related papers  (2021-08-19T16:16:00Z)
• Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning [59.02541753781001]
  This paper initiates the theoretical study of policy finetuning, that is, online RL where the learner has additional access to a "reference policy" We first design a sharp offline reduction algorithm that finds an $varepsilon$ near-optimal policy within $widetildeO(H3SCstar/varepsilon2)$ episodes. We then establish an $Omega(H3SminCstar, A/varepsilon2)$ sample complexity lower bound for any policy finetuning algorithm, including those that can adaptively explore the
  arXiv  Detail & Related papers  (2021-06-09T08:28:55Z)
• High-Dimensional Sparse Linear Bandits [67.9378546011416]
  We derive a novel $Omega(n2/3)$ dimension-free minimax regret lower bound for sparse linear bandits in the data-poor regime. We also prove a dimension-free $O(sqrtn)$ regret upper bound under an additional assumption on the magnitude of the signal for relevant features.
  arXiv  Detail & Related papers  (2020-11-08T16:48:11Z)

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.