論文の概要: The Hardness Analysis of Thompson Sampling for Combinatorial
Semi-bandits with Greedy Oracle
- arxiv url: http://arxiv.org/abs/2111.04295v1
- Date: Mon, 8 Nov 2021 06:40:03 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-09 15:34:47.372334
- Title: The Hardness Analysis of Thompson Sampling for Combinatorial
Semi-bandits with Greedy Oracle
- Title（参考訳）: 欲深いオラクルをもつ組合せ半バンドのためのトンプソンサンプリングの硬さ解析
- Authors: Fang Kong, Yueran Yang, Wei Chen, Shuai Li
- Abstract要約: トンプソンサンプリング(TS)は、バンディット地域に多くの関心を集めている。
1930年代に導入されたが、理論上は近年まで証明されていない。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: トンプソンサンプリング (ts) は、バンディット分野で多くの関心を集めている。
1930年代に導入されたが、理論上は近年まで証明されていない。
コンビネーショナル・マルチアームド・バンディット(cmab)の設定における解析はすべて、任意の入力に対して最適なソリューションを提供するための正確なオラクルが必要である。
しかし、多くの組合せ最適化問題はNPハードであり、近似オラクルのみが利用できるため、そのようなオラクルは通常実現不可能である。
例(Wang and Chen, 2018)では、近似オラクルでTSが学習できないことが示されている。
しかし、このオラクルは一般的ではなく、特定の問題インスタンスのためにのみ設計されている。
TS の収束解析が CMAB の正確なオラクルを超えて拡張できるかどうかはまだ明らかな問題である。
本稿では,多くの(オフライン)組合せ最適化問題の解法を理論的に保証する共通(近似)オラクルであるgreedy oracleの下で,この問題を考察する。
問題依存的後悔の少ない位数$\Omega(\log T/\Delta^2)$ を提供して TS の硬さを定量化し、greedy oracle を用いて CMAB 問題を解く。
私たちはまた、ほぼ一致する後悔の上限も提供します。
これらは TS が CMAB を共通の近似オラクルで解く最初の理論的結果であり、TS が近似オラクルでは働けないという誤解を破るものである。
関連論文リスト
- Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - When Combinatorial Thompson Sampling meets Approximation Regret [7.538482310185135]
マルチアームバンディット問題(CMAB)に対するコンビニアルトンプソンサンプリングポリシー(CTS)について検討する。
近似オラクルの特定の条件下で得られた CTS に対して,最初の $mathcalO(log(T)/Delta)$ approximation regret upperbound を提供する。
論文 参考訳（メタデータ） (2023-02-22T07:27:59Z) - A distribution testing oracle separation between QMA and QCMA [0.6144680854063939]
量子複雑性理論において、$textitnon-deterministic$ 量子計算の定義が量子証人を必要とするかどうかという長い議論である。
本稿では,各計算複雑性クラスを分離したランダム化された古典オラクルを構築することにより,この問題を進展させる。
論文 参考訳（メタデータ） (2022-10-27T12:43:56Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳（メタデータ） (2022-01-06T03:10:53Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。
目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。
この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
論文 参考訳（メタデータ） (2021-09-08T19:48:27Z) - Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with
a Faulty Oracle [7.449644976563424]
本稿では,クラスタリングを不良オラクルで研究するためのエレガントな理論的モデルを提案する。
一般の場合の$k$クラスタに対して、クエリ最適で時間効率のアルゴリズムを得られるかどうかというオープンな疑問として残された。
情報理論の回復が可能であれば,全ての定数$k$に対して,ほぼ最適なクエリ複雑性(最大$O(log2 n)$)を持つ時間効率アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-18T22:20:12Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳（メタデータ） (2021-06-18T15:01:01Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Zeroth-Order Algorithms for Smooth Saddle-Point Problems [117.44028458220427]
ゼロオーダーのオラクルを用いてサドルポイント問題を解くアルゴリズムをいくつか提案する。
解析により、この項の収束率は、一階法よりも$log n$因子の方が悪いことが示されている。
また、混合構成を考慮し、その部分に対してゼロ階のオラクルを使用する1/2階法を開発する。
論文 参考訳（メタデータ） (2020-09-21T14:26:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。