論文の概要: Problem Dependent View on Structured Thresholding Bandit Problems
- arxiv url: http://arxiv.org/abs/2106.10166v1
- Date: Fri, 18 Jun 2021 15:01:01 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-21 19:22:12.412954
- Title: Problem Dependent View on Structured Thresholding Bandit Problems
- Title（参考訳）: 構造化しきい値バンディット問題に対する問題依存的視点
- Authors: James Cheshire, Pierre M\'enard, Alexandra Carpentier
- Abstract要約: 我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
- 参考スコア（独自算出の注目度）: 73.70176003598449
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We investigate the problem dependent regime in the stochastic Thresholding
Bandit problem (TBP) under several shape constraints. In the 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. The vanilla, unstructured, case is
already well studied in the literature. Taking $K$ as the number of arms, we
consider the case where (i) the sequence of arm's means $(\mu_k)_{k=1}^K$ is
monotonically increasing (MTBP) and (ii) the case where $(\mu_k)_{k=1}^K$ is
concave (CTBP). We consider both cases in the problem dependent regime and
study the probability of error - i.e. the probability to mis-classify at least
one arm. In the fixed budget setting, we provide upper and lower bounds for the
probability of error in both the concave and monotone settings, as well as
associated algorithms. In both settings the bounds match in the problem
dependent regime up to universal constants in the exponential.
- Abstract（参考訳）: 確率的しきい値バンディット問題 (tbp) における問題依存構造について, 形状制約下で検討した。
TBPでは、学習者の目的は、シーケンシャルゲームの終了時に、所定のしきい値を超える手段を持つアームセットを出力することである。
バニラは非構造で、既に文献でよく研究されている。
腕の数として$K$とすると、(i)アームの列が$(\mu_k)_{k=1}^K$が単調に増加(MTBP)している場合、(ii)$(\mu_k)_{k=1}^K$が凹(CTBP)である場合を考える。
問題依存体制におけるどちらのケースも考慮し、エラーの確率、すなわち、調査する。
少なくとも一つの腕を誤分類する確率。
固定予算設定では、コンケーブとモノトーンの両方の設定における誤差の確率の上限と下限、および関連するアルゴリズムを提供する。
どちらの設定でも、境界は指数関数の普遍定数まで問題に依存する状態に一致する。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。
目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。
我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
論文 参考訳（メタデータ） (2024-05-23T22:35:11Z) - Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Multi-Fidelity Multi-Armed Bandits Revisited [46.19926456682379]
我々は,MF-MAB(Multi-fidelity multi-armed bandit)問題の拡張であるMF-MAB(Multi-fidelity multi-armed bandit)について検討した。
MF-MABは、各アームを異なるコスト(忠実さ)と観察精度で引っ張ることができる。
論文 参考訳（メタデータ） (2023-06-13T13:19:20Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [45.305256056479045]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with
Probabilistically Triggered Arms or Independent Arms [53.89752069984382]
半帯域 (CMAB) について検討し, 半帯域 (CMAB) におけるバッチサイズ (K$) の依存性の低減に着目した。
まず,確率的に引き起こされるアーム(CMAB-T)を用いたCMABの設定に対して,分散を考慮した信頼区間を持つBCUCB-Tアルゴリズムを提案する。
次に,独立アームを用いた非トリガ型CMABの設定に対して,TPVM条件の非トリガ型を利用したSESCBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-31T13:09:39Z) - The Influence of Shape Constraints on the Thresholding Bandit Problem [74.73898216415049]
本稿では,いくつかの形状制約の下でThresholding Bandit問題(TBP)について検討する。
TBP問題において、目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
後悔の最小値は (i) $sqrtlog(K)K/T$ for TBP, (ii) $sqrtlog(K)/T$ for UTBP, (iii) $sqrtK/T$ for CTBP, (iv) であることが証明されている。
論文 参考訳（メタデータ） (2020-06-17T17:12:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。