Oracle-Efficient Combinatorial Semi-Bandits

• URL: http://arxiv.org/abs/2510.21431v1
• Date: Fri, 24 Oct 2025 13:07:08 GMT
• Title: Oracle-Efficient Combinatorial Semi-Bandits
• Abstract summary: We study the semi-bandit problem where an agent selects a subset of base arms and receives individual feedback.<n>We propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees.
• Score: 38.838934613131535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the combinatorial semi-bandit problem where an agent selects a subset of base arms and receives individual feedback. While this generalizes the classical multi-armed bandit and has broad applicability, its scalability is limited by the high cost of combinatorial optimization, requiring oracle queries at every round. To tackle this, we propose oracle-efficient frameworks that significantly reduce oracle calls while maintaining tight regret guarantees. For the worst-case linear reward setting, our algorithms achieve $\tilde{O}(\sqrt{T})$ regret using only $O(\log\log T)$ oracle queries. We also propose covariance-adaptive algorithms that leverage noise structure for improved regret, and extend our approach to general (non-linear) rewards. Overall, our methods reduce oracle usage from linear to (doubly) logarithmic in time, with strong theoretical guarantees.

Related papers

• Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning [37.15283418677639]
  Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner.<n>We replace the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization oracle.<n>We show that our algorithm reduces the total query complexity down to $O(Td_mathrmVC+1)$ while perfectly preserving near-optimal expected regret.
  arXiv  Detail & Related papers  (2026-05-08T02:41:23Z)
• Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation [21.36054923028733]
  Reinforcement learning (RL) in large environments often suffers from severe computational bottlenecks.<n>We propose a novel algorithm that achieves the optimal $tildeO(sqrtT)$ regret bound while requiring only $O(Hloglog T)$ calls.<n>This oracle complexity is entirely independent of the size of the state and action spaces.
  arXiv  Detail & Related papers  (2026-05-01T04:32:23Z)
• A Perturbation Approach to Unconstrained Linear Bandits [48.45987210959519]
  We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO)<n>We show the surprising result that in the unconstrained setting, this approach effectively reduces Bandit Linear Optimization (BLO) to a standard Online Linear Optimization (OLO) problem.
  arXiv  Detail & Related papers  (2026-03-30T09:17:46Z)
• Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity [80.65200796386168]
  We present and analyze a novel derivative-free method for solving such problems.<n>We show that when mixing time $$ of the underlying noise sequence is less than the dimension of the problem $d$, the convergence estimates of our method do not depend on $$.
  arXiv  Detail & Related papers  (2026-01-03T11:27:07Z)
• Adaptive Sparsification for Linear Programming [3.735586259382096]
  We introduce a generic framework for solving linear programs with many constraints $(n gg d)$ via adaptive sparsification.<n>We present a quantum version of Clarkson's algorithm that finds an exact solution to an LP using $tildeO(sqrtn d3)$ row-queries to the constraint matrix.<n>Second, our framework yields new state-of-the-art algorithms for mixed packing and covering problems when the packing constraints are simple''
  arXiv  Detail & Related papers  (2025-10-09T15:36:00Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Projection-Free Online Convex Optimization with Time-Varying Constraints [19.993839085310643]
  We consider the setting of online convex optimization with adversarial time-varying constraints. Motivated by scenarios in which the fixed feasible set is difficult to project on, we consider projection-free algorithms that access this set only through a linear optimization oracle (LOO) We present an algorithm that, on a sequence of length $T$ and using overall $T$ calls to the LOO, guarantees $tildeO(T3/4)$ regret w.r.t. the losses and $O(T 7/8)$ constraints violation.
  arXiv  Detail & Related papers  (2024-02-13T21:13:29Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• Distributionally Robust Optimization via Ball Oracle Acceleration [8.417186276756336]
  We develop and analyze algorithms for distributionally robust optimization (DRO) of convex losses. Compared to existing algorithms for this problem, we improve complexity by a factor of up to $epsilon-4/3$.
  arXiv  Detail & Related papers  (2022-03-24T17:31:43Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  We study the $K$ contextual dueling bandit problem, a sequential decision making setting in which the learner uses contextual information to make two decisions, but only observes emphpreference-based feedback suggesting that one decision was better than the other. We provide a new algorithm that achieves the optimal regret rate for a new notion of best response regret, which is a strictly stronger performance measure than those considered in prior works.
  arXiv  Detail & Related papers  (2021-11-24T07:14:57Z)
• The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle [16.50998008977657]
  Thompson sampling (TS) has attracted a lot of interest in the bandit area. It was introduced in the 1930s but has not been theoretically proven until recent years.
  arXiv  Detail & Related papers  (2021-11-08T06:40:03Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  We introduce a new family of oracle-efficient algorithms for $varepsilon$-misspecified contextual bandits. We obtain the first algorithm that achieves the optimal $O(dsqrtT + varepsilonsqrtdT)$ regret bound for unknown misspecification level.
  arXiv  Detail & Related papers  (2021-07-12T21:30:41Z)
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability [18.45278329799526]
  We design a fast and simple algorithm that achieves the statistically optimal regret with only $O(log T)$ calls to an offline regression oracle. Our results provide the first universal and optimal reduction from contextual bandits to offline regression.
  arXiv  Detail & Related papers  (2020-03-28T04:16:52Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  We provide the first universal and optimal reduction from contextual bandits to online regression. Our algorithm requires no distributional assumptions beyond realizability, and works even when contexts are chosen adversarially.
  arXiv  Detail & Related papers  (2020-02-12T11:33:46Z)

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.