Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms

• URL: http://arxiv.org/abs/2512.21925v1
• Date: Fri, 26 Dec 2025 08:42:12 GMT
• Title: Hybrid Combinatorial Multi-armed Bandits with Probabilistically Triggered Arms
• Abstract summary: 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.
• Score: 10.146314852311638
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of combinatorial multi-armed bandits with probabilistically triggered arms (CMAB-T) has been extensively studied. Prior work primarily focuses on either the online setting where an agent learns about the unknown environment through iterative interactions, or the offline setting where a policy is learned solely from logged data. However, each of these paradigms has inherent limitations: online algorithms suffer from high interaction costs and slow adaptation, while offline methods are constrained by dataset quality and lack of exploration capabilities. To address these complementary weaknesses, we propose hybrid CMAB-T, a new framework that integrates offline data with online interaction in a principled manner. Our proposed hybrid CUCB algorithm leverages offline data to guide exploration and accelerate convergence, while strategically incorporating online interactions to mitigate the insufficient coverage or distributional bias of the offline dataset. We provide theoretical guarantees on the algorithm's regret, demonstrating that hybrid CUCB significantly outperforms purely online approaches when high-quality offline data is available, and effectively corrects the bias inherent in offline-only methods when the data is limited or misaligned. Empirical results further demonstrate the consistent advantage of our algorithm.

Related papers

• A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics [36.92549343895364]
  We propose a unified algorithmic framework featuring two algorithms: MIN-UCB-VI for regret minimization and MAX-LCB-VI for best policy identification.<n>We provide theoretical guarantees for our framework, including both instance-dependent and independent upper bounds on regret and sub-optimality gap.
  arXiv  Detail & Related papers  (2026-07-28T02:27:27Z)
• Best Arm Identification with Possibly Biased Offline Data [56.965938201853625]
  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.
  arXiv  Detail & Related papers  (2025-05-29T06:58:49Z)
• 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)
• Evaluation-Time Policy Switching for Offline Reinforcement Learning [5.052293146674794]
  offline reinforcement learning (RL) looks at learning how to optimally solve tasks using a fixed dataset of interactions from the environment.<n>Many off-policy algorithms developed for online learning struggle in the offline setting as they tend to over-estimate the behaviour of out of distributions of actions.<n>Existing offline RL algorithms adapt off-policy algorithms, employing techniques such as constraining the policy or modifying the value function to achieve good performance on individual datasets.<n>We introduce a policy switching technique that dynamically combines the behaviour of a pure off-policy RL agent, for improving behaviour, and a behavioural cloning (BC) agent, for staying close to the
  arXiv  Detail & Related papers  (2025-03-15T18:12:16Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB.<n>Off-CMAB combines pessimistic reward estimations with solvers.<n>Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• 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)
• A Natural Extension To Online Algorithms For Hybrid RL With Limited Coverage [7.438754486636558]
  We show that a well-designed online algorithm should "fill in the gaps" in the offline dataset. We show that it achieves similar provable gains from hybrid data even when the offline dataset does not have single-policy concentrability.
  arXiv  Detail & Related papers  (2024-03-07T19:39:47Z)
• Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning [66.43003402281659]
  A central question boils down to how to efficiently utilize online data collection to strengthen and complement the offline dataset. We design a three-stage hybrid RL algorithm that beats the best of both worlds -- pure offline RL and pure online RL. The proposed algorithm does not require any reward information during data collection.
  arXiv  Detail & Related papers  (2023-05-17T15:17:23Z)
• Adaptive Policy Learning for Offline-to-Online Reinforcement Learning [27.80266207283246]
  We consider an offline-to-online setting where the agent is first learned from the offline dataset and then trained online. We propose a framework called Adaptive Policy Learning for effectively taking advantage of offline and online data.
  arXiv  Detail & Related papers  (2023-03-14T08:13:21Z)
• 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)

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.