Fugu-MT 論文翻訳(概要): Bridging Adversarial and Nonstationary Multi-armed Bandit

論文の概要: Bridging Adversarial and Nonstationary Multi-armed Bandit

arxiv url: http://arxiv.org/abs/2201.01628v3
Date: Sun, 26 Nov 2023 00:08:29 GMT
ステータス: 処理完了
システム内更新日: 2023-11-30 18:05:43.472889
Title: Bridging Adversarial and Nonstationary Multi-armed Bandit
Title（参考訳）: ブリッジと非定常マルチアームバンド
Authors: Ningyuan Chen, Shuoguang Yang, Hailun Zhang
Abstract要約: 2つの定式化は、典型的には時間変化の報酬分布を扱うために用いられる: 逆の帯域幅と非定常帯域幅である。この2つを特別なケースとしてスムーズにブリッジする統一的な定式化を提供する。一致した下界で最適な後悔を達成するアルゴリズムを提供する。
参考スコア（独自算出の注目度）: 10.3206415401832
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In the multi-armed bandit framework, there are two formulations that are commonly employed to handle time-varying reward distributions: adversarial bandit and nonstationary bandit. Although their oracles, algorithms, and regret analysis differ significantly, we provide a unified formulation in this paper that smoothly bridges the two as special cases. The formulation uses an oracle that takes the best-fixed arm within time windows. Depending on the window size, it turns into the oracle in hindsight in the adversarial bandit and dynamic oracle in the nonstationary bandit. We provide algorithms that attain the optimal regret with the matching lower bound.
Abstract（参考訳）: マルチアームのバンディットフレームワークでは、時変報酬分布を扱うために一般的に使われる2つの定式化がある: 逆バンディットと非定常バンディットである。本論文では, オーラクル, アルゴリズム, 後悔分析の相違について述べるが, この2つを特殊ケースとしてスムーズにブリッジする統一的な定式化について述べる。この定式化は、タイムウインドウ内で最高の固定アームを取るオラクルを使用します。ウィンドウサイズによっては、非定常バンディットの逆バンディットと動的オラクルにおいて後からオラクルになる。我々は、一致する下限で最適な後悔を得るアルゴリズムを提供する。

関連論文リスト

Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting [67.1631453378926]
Graph-Triggered Banditsは、安静と安静のバンディットを一般化するフレームワークである。本研究は,2種類の単調包帯に焦点をあてる: 立ち上がり, 腕の期待される報酬が増加する, 引き金の数が増える, 回転する, 反対の行動が起こる。
論文参考訳（メタデータ） (2024-09-09T18:23:07Z)
Multi-Player Approaches for Dueling Bandits [58.442742345319225]
Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
論文参考訳（メタデータ） (2024-05-25T10:25:48Z)
Dueling Bandits: From Two-dueling to Multi-dueling [40.4378338001229]
エージェントが複数の選択肢を同時に比較し、最適な腕を選択することで後悔を最小限に抑える、一般的なマルチダウリングバンディット問題について検討する。この設定は従来の二段バンディット問題を一般化し、複数の選択肢に対する主観的なフィードバックを含む現実世界の多くのアプリケーションを見つける。
論文参考訳（メタデータ） (2022-11-16T22:00:54Z)
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)
Bias-Robust Bayesian Optimization via Dueling Bandit [57.82422045437126]
ベイジアン最適化は、観測が逆偏りとなるような環境において考慮する。情報指向サンプリング(IDS)に基づくダリングバンディットの新しい手法を提案する。これにより、累積的後悔保証を伴う帯域幅の並列化のための、最初の効率的なカーネル化アルゴリズムが得られる。
論文参考訳（メタデータ） (2021-05-25T10:08:41Z)
Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文参考訳（メタデータ） (2021-05-22T02:46:04Z)
Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文参考訳（メタデータ） (2021-01-21T10:35:09Z)
Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
バンディットアルゴリズムを結合する簡単な手法を提案する。私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
論文参考訳（メタデータ） (2020-12-24T05:36:29Z)
A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-05-23T19:52:44Z)
Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文参考訳（メタデータ） (2020-03-06T20:34:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。