論文の概要: One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret
Guarantees in Sleeping Bandits
- arxiv url: http://arxiv.org/abs/2210.14998v1
- Date: Wed, 26 Oct 2022 19:40:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-28 14:48:01.631521
- Title: One Arrow, Two Kills: An Unified Framework for Achieving Optimal Regret
Guarantees in Sleeping Bandits
- Title(参考訳): 1人死亡、2人死亡:睡眠バンドで最適な規則を守るための統一フレームワーク
- Authors: Pierre Gaillard, Aadirupa Saha, Soham Dan
- Abstract要約: 本稿では,emphSleeping Bandits における emphInternal Regret' の問題に対処する。
我々は, 完全に逆の損失と有効性の連続であっても, その尺度においてサブ線形後悔をもたらすアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 29.896865106960423
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the problem of \emph{`Internal Regret'} in \emph{Sleeping Bandits}
in the fully adversarial setup, as well as draw connections between different
existing notions of sleeping regrets in the multiarmed bandits (MAB) literature
and consequently analyze the implications: Our first contribution is to propose
the new notion of \emph{Internal Regret} for sleeping MAB. We then proposed an
algorithm that yields sublinear regret in that measure, even for a completely
adversarial sequence of losses and availabilities. We further show that a low
sleeping internal regret always implies a low external regret, and as well as a
low policy regret for iid sequence of losses. The main contribution of this
work precisely lies in unifying different notions of existing regret in
sleeping bandits and understand the implication of one to another. Finally, we
also extend our results to the setting of \emph{Dueling Bandits} (DB)--a
preference feedback variant of MAB, and proposed a reduction to MAB idea to
design a low regret algorithm for sleeping dueling bandits with stochastic
preferences and adversarial availabilities. The efficacy of our algorithms is
justified through empirical evaluations.
- Abstract(参考訳): 我々は、完全に敵対的な設定における「emph{`Internal Regret'」の問題に対処し、また、マルチアーム・バンディット(MAB)の文献において、睡眠中の後悔という既存の概念の相互関係を引き合いに出し、その結果、その意味を分析する。
そこで我々は,完全に逆の損失と有効性の連続であっても,その尺度においてサブ線形後悔をもたらすアルゴリズムを提案した。
さらに、睡眠中の内的後悔は、常に外的後悔の度合いが低く、また、損失の連続に対する政策上の後悔の度合いが低いことを示す。
この作品の主な貢献は、睡眠包帯における既存の後悔の異なる概念を統一し、互いの含意を理解することである。
また,MABの嗜好フィードバックの変種である「emph{Dueling Bandits} (DB) の設定にも拡張し,確率的嗜好と対角的利用性を備えた睡眠障害帯を睡眠する低遅延アルゴリズムを設計するための MAB アイデアの削減を提案した。
アルゴリズムの有効性は経験的評価によって正当化される。
関連論文リスト
- Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - Proportional Response: Contextual Bandits for Simple and Cumulative
Regret Minimization [29.579719765255927]
本稿では,文脈的帯域幅設定のための効率的な帯域幅アルゴリズムのファミリーを提案する。
我々のアルゴリズムは任意の関数クラスで動作し、不特定性をモデル化するのに堅牢で、連続したアーム設定で使用できます。
論文 参考訳(メタデータ) (2023-07-05T08:34:54Z) - Weighted Tallying Bandits: Overcoming Intractability via Repeated
Exposure Optimality [46.445321251991096]
推薦システムやクラウドソーシングアプリケーションでは、人間の好みや能力はアルゴリズムの最近の行動の関数であることが多い。
我々は、この設定を一般化するWeighted Tallying Bandit (WTB)を導入し、アクションの損失が、前回の$m$のタイムステップで腕が演奏された回数のエンフ和関数であることを要求して、この設定を一般化する。
我々は、$K$アクションと水平線$T$の問題に対して、逐次除去アルゴリズムの簡単な変更は、$O left( sqrtKT + m+)を持つことを示した。
論文 参考訳(メタデータ) (2023-05-04T15:59:43Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Contextual Bandits with Smooth Regret: Efficient Learning in Continuous
Action Spaces [14.366265951396587]
我々は、大規模または連続的なアクション空間に対する効率的な汎用的コンテキスト帯域幅アルゴリズムを設計する。
本稿では,従来提案されていた代替案に支配的な文脈的包帯に対して,スムーズな後悔の念を抱く概念を提案する。
我々のアルゴリズムは、標準的な後悔の下で以前のminimax/Paretoの最適保証を回復するために使用することができる。
論文 参考訳(メタデータ) (2022-07-12T21:27:09Z) - The Survival Bandit Problem [65.68378556428861]
我々は、サバイバル・バンディット問題(S-MAB)と呼ばれるマルチアーム・バンディット問題(MAB)の新たな変種を紹介し、研究する。
どちらの問題においても、いわゆる累積報酬を最大化することが目的であるが、この新しい変種では累積報酬が予め設定された閾値を下回った場合、手続きが中断される。
この単純なMABの拡張は、多くの実用的な応用から導かれる。
論文 参考訳(メタデータ) (2022-06-07T05:23:14Z) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳(メタデータ) (2022-04-24T03:10:27Z) - Versatile Dueling Bandits: Best-of-both-World Analyses for Online
Learning from Preferences [28.79598714109439]
両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。
まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。
提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
論文 参考訳(メタデータ) (2022-02-14T13:37:23Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳(メタデータ) (2020-06-22T16:06:25Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。