論文の概要: Adversarial Dueling Bandits
- arxiv url: http://arxiv.org/abs/2010.14563v1
- Date: Tue, 27 Oct 2020 19:09:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-02 11:31:26.110443
- Title: Adversarial Dueling Bandits
- Title(参考訳): 敵対的デュエル・バンディット
- Authors: Aadirupa Saha, Tomer Koren, Yishay Mansour
- Abstract要約: 本稿では,反逆デュエルバンドにおける後悔の問題を紹介する。
学習者は、繰り返し一対のアイテムを選択し、このペアに対する相対的な二項利得フィードバックのみを観察しなければならない。
我々の主な成果は、EmphBorda-winnerの1組の$K$アイテムと比較して、T$ラウンド後悔するアルゴリズムです。
- 参考スコア(独自算出の注目度): 85.14061196945599
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the problem of regret minimization in Adversarial Dueling
Bandits. As in classic Dueling Bandits, the learner has to repeatedly choose a
pair of items and observe only a relative binary `win-loss' feedback for this
pair, but here this feedback is generated from an arbitrary preference matrix,
possibly chosen adversarially. Our main result is an algorithm whose $T$-round
regret compared to the \emph{Borda-winner} from a set of $K$ items is
$\tilde{O}(K^{1/3}T^{2/3})$, as well as a matching $\Omega(K^{1/3}T^{2/3})$
lower bound. We also prove a similar high probability regret bound. We further
consider a simpler \emph{fixed-gap} adversarial setup, which bridges between
two extreme preference feedback models for dueling bandits: stationary
preferences and an arbitrary sequence of preferences. For the fixed-gap
adversarial setup we give an $\smash{ \tilde{O}((K/\Delta^2)\log{T}) }$ regret
algorithm, where $\Delta$ is the gap in Borda scores between the best item and
all other items, and show a lower bound of $\Omega(K/\Delta^2)$ indicating that
our dependence on the main problem parameters $K$ and $\Delta$ is tight (up to
logarithmic factors).
- Abstract(参考訳): 敵対的デュエル・バンディットにおける後悔の最小化の問題を紹介する。
古典的なDueling Banditsのように、学習者はアイテムのペアを何度も選択し、このペアに対して相対的なバイナリの ‘win-loss’ フィードバックのみを観察する必要があるが、このフィードバックは任意の選好行列から生成され、おそらく逆選択される。
我々の主な結果は、K$項目の集合から得られる 'emph{Borda-winner} に対して $T$-round regret が$\tilde{O}(K^{1/3}T^{2/3})$であり、一致する $\Omega(K^{1/3}T^{2/3})$ lower bound である。
私たちはまた、同様の高い確率の後悔境界を証明します。
さらに、より単純な \emph{fixed-gap} 逆向きの設定も検討し、これは2つの極端優先フィードバックモデル(定常選好と任意の選好列)をブリッジする。
ここでは、$\Delta$は、最良の項目と他のすべての項目の間のボルダのスコアのギャップであり、主な問題パラメータへの依存度が$K$と$\Delta$が(対数的要因まで)厳密であることを示す$\Omega(K/\Delta^2)の低い境界を示す。
関連論文リスト
- Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Better Best of Both Worlds Bounds for Bandits with Switching Costs [37.71741656687868]
本稿では,2021年にRouryer,Seldin,Cesa-Bianchiらにより,スイッチングコストを伴うバンディットのベスト・オブ・ザ・ワールドス・アルゴリズムについて検討した。
本稿では, 極小最小の最小残差を$mathcalO(T2/3)$で同時に達成する, 驚くほど単純かつ効果的に導入する。
論文 参考訳(メタデータ) (2022-06-07T08:22:56Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳(メタデータ) (2022-05-26T15:55:44Z) - Bounded Memory Adversarial Bandits with Composite Anonymous Delayed
Feedback [10.179145161000315]
複合匿名遅延フィードバックを用いた対向帯域幅問題について検討した。
この設定では、アクションの損失は$d$コンポーネントに分割され、アクションが選択された後に連続してラウンドが分散される。
損失シーケンスがメモリ境界である場合でも,$Omega(T)$疑似後悔が発生することを示す。
論文 参考訳(メタデータ) (2022-04-27T08:32:35Z) - Dueling Bandits with Adversarial Sleeping [26.308541799686505]
好みと敵意の相反するバンドレットを睡眠させるという問題を紹介した。
目標は、各ラウンドで最高のアイテムを識別できる最適なノンレグレットポリシーを見つけることです。
論文 参考訳(メタデータ) (2021-07-05T21:14:04Z) - Understanding Bandits with Graph Feedback [0.0]
一般的な後悔すべき上界$Oleft(left(delta*log |V|right)frac13Tfrac23right)$と下界$Omegaleft(left(delta*/alpharight)frac13Tfrac23right)$を証明します。
いくつかのグラフの特別な族に対して、$left(log |V|right)frac13$ factorを排除できることを示す。
論文 参考訳(メタデータ) (2021-05-29T09:35:28Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳(メタデータ) (2021-03-23T11:02:31Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳(メタデータ) (2021-03-03T23:08:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。