The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle

• URL: http://arxiv.org/abs/2111.04295v1
• Date: Mon, 8 Nov 2021 06:40:03 GMT
• Title: The Hardness Analysis of Thompson Sampling for Combinatorial Semi-bandits with Greedy Oracle
• Abstract summary: 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.
• Score: 16.50998008977657
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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. All of its analysis in the combinatorial multi-armed bandit (CMAB) setting requires an exact oracle to provide optimal solutions with any input. However, such an oracle is usually not feasible since many combinatorial optimization problems are NP-hard and only approximation oracles are available. An example (Wang and Chen, 2018) has shown the failure of TS to learn with an approximation oracle. However, this oracle is uncommon and is designed only for a specific problem instance. It is still an open question whether the convergence analysis of TS can be extended beyond the exact oracle in CMAB. In this paper, we study this question under the greedy oracle, which is a common (approximation) oracle with theoretical guarantees to solve many (offline) combinatorial optimization problems. We provide a problem-dependent regret lower bound of order $\Omega(\log T/\Delta^2)$ to quantify the hardness of TS to solve CMAB problems with greedy oracle, where $T$ is the time horizon and $\Delta$ is some reward gap. We also provide an almost matching regret upper bound. These are the first theoretical results for TS to solve CMAB with a common approximation oracle and break the misconception that TS cannot work with approximation oracles.

Related papers

• Oracle Separations in the Fourier Hierarchy [0.0]
  We prove that for every constant $kge2$ there is an oracle relative to which $mathrmFH_ksubsetneqmathrmFH_k+1$.<n>This holds for both of the usual ways of giving a circuit access to an oracle, the phase oracle and the standard oracle.<n>We also separate the union of all the levels from $mathrmBQP$ relative to an oracle.
  arXiv  Detail & Related papers  (2026-09-10T17:23:35Z)
• En Route to a Standard QMA1 vs. QCMA Oracle Separation [0.25489046505746704]
  We study the power of quantum witnesses under perfect completeness.<n>We construct a classical oracle relative to which a language lies in $mathsfQMA$ but not in $mathsfQCMA$.
  arXiv  Detail & Related papers  (2026-04-29T17:38:20Z)
• 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)
• Oracle-Efficient Combinatorial Semi-Bandits [38.838934613131535]
  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.
  arXiv  Detail & Related papers  (2025-10-24T13:07:08Z)
• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  We provide evidence that existing learning algorithms, such as multiplicative weights update, are close to optimal. Our results are obtained in the algorithmic framework put forward by Kothari and Mehta.
  arXiv  Detail & Related papers  (2024-11-04T00:39:52Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• When Combinatorial Thompson Sampling meets Approximation Regret [7.538482310185135]
  We study the Combinatorial Thompson Sampling policy (CTS) for multi-armed bandit problems (CMAB) We provide the first $mathcalO(log(T)/Delta)$ approximation regret upper bound for CTS, obtained under a specific condition on the approximation oracle.
  arXiv  Detail & Related papers  (2023-02-22T07:27:59Z)
• A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
  It is a long-standing open question in quantum complexity theory whether the definition of $textitnon-deterministic$ quantum computation requires quantum witnesses. We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes.
  arXiv  Detail & Related papers  (2022-10-27T12:43:56Z)
• An optimal oracle separation of classical and quantum hybrid schemes [0.0]
  We show that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$, when computation-time classical is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes.
  arXiv  Detail & Related papers  (2022-05-10T02:31:19Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
  oracle access to bits of an unknown string $x$ of length $n$, with the promise that it belongs to a known set $Csubseteq0,1n$. The goal is to identify $x$ using as few queries to the oracle as possible. We develop a quantum query algorithm for this problem with query complexity $Oleft(sqrtfracnlog M log(n/log M)+1right)$, where $M$ is the size of $C$.
  arXiv  Detail & Related papers  (2021-09-08T19:48:27Z)
• Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle [7.449644976563424]
  We propose an elegant theoretical model for studying clustering with a faulty oracle. It was left as an open question whether one can obtain a query-optimal, time-efficient algorithm for the general case of $k$ clusters. We provide a time-efficient algorithm with nearly-optimal query complexity (up to a factor of $O(log2 n)$) for all constant $k$ and any $delta$ in the regime when information-theoretic recovery is possible.
  arXiv  Detail & Related papers  (2021-06-18T22:20:12Z)
• Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
  We investigate the problem dependent regime in the Thresholding Bandit problem (TBP) The objective of the learner is to output, at the end of a sequential game, the set of arms whose means are above a given threshold. We provide upper and lower bounds for the probability of error in both the concave and monotone settings.
  arXiv  Detail & Related papers  (2021-06-18T15:01:01Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
  We propose several algorithms to solve saddle-point problems using zeroth-order oracles. Our analysis shows that our convergence rate for the term is only by a $log n$ factor worse than for the first-order methods. We also consider a mixed setup and develop 1/2th-order methods that use zeroth-order oracle for the part.
  arXiv  Detail & Related papers  (2020-09-21T14:26:48Z)

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.