論文の概要: Does Feedback Help in Bandits with Arm Erasures?

• arxiv url: http://arxiv.org/abs/2504.20894v1
• Date: Tue, 29 Apr 2025 16:10:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:54.97732
• Title: Does Feedback Help in Bandits with Arm Erasures?
• Title（参考訳）: 腕の出血によるバンドのフィードバックは役立つか?
• Authors: Merve Karakas, Osama Hanna, Lin F. Yang, Christina Fragouli,
• Abstract要約: 本研究では,マルチアーム・バンディット (MAB) をアーム消去チャネル上に分散する問題について検討する。 本稿では,アームリクエストが受信されたかどうかについて,エージェントが学習者にフィードバックを送ることができる事例について考察する。 意外なことに, 消去フィードバックは, これまでに検討された無フィードバック設定よりも, 最悪の後悔の上位境界順序を改善できないことが証明された。
• 参考スコア（独自算出の注目度）: 20.235500642661812
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a distributed multi-armed bandit (MAB) problem over arm erasure channels, motivated by the increasing adoption of MAB algorithms over communication-constrained networks. In this setup, the learner communicates the chosen arm to play to an agent over an erasure channel with probability $\epsilon \in [0,1)$; if an erasure occurs, the agent continues pulling the last successfully received arm; the learner always observes the reward of the arm pulled. In past work, we considered the case where the agent cannot convey feedback to the learner, and thus the learner does not know whether the arm played is the requested or the last successfully received one. In this paper, we instead consider the case where the agent can send feedback to the learner on whether the arm request was received, and thus the learner exactly knows which arm was played. Surprisingly, we prove that erasure feedback does not improve the worst-case regret upper bound order over the previously studied no-feedback setting. In particular, we prove a regret lower bound of $\Omega(\sqrt{KT} + K / (1 - \epsilon))$, where $K$ is the number of arms and $T$ the time horizon, that matches no-feedback upper bounds up to logarithmic factors. We note however that the availability of feedback enables simpler algorithm designs that may achieve better constants (albeit not better order) regret bounds; we design one such algorithm and evaluate its performance numerically.
• Abstract（参考訳）: 我々は,通信制約付きネットワーク上でのMABアルゴリズムの採用の増加を動機として,アーム消去チャネル上の分散マルチアームバンディット(MAB)問題を考察した。 この設定では、学習者は選択した腕に通信して、消去チャンネル上のエージェントに、確率$\epsilon \in [0,1)$でプレーする。 過去の研究では,エージェントが学習者にフィードバックを伝達できない場合について検討した。 そこで,本稿では,エージェントが学習者にアーム要求を受信したかどうかのフィードバックを送信し,学習者がどのアームをプレイしているかを正確に把握する。 意外なことに, 消去フィードバックは, これまでに検討された無フィードバック設定よりも, 最悪の後悔の上位境界順序を改善できないことが証明された。 特に、後悔の少ない$\Omega(\sqrt{KT} + K / (1 - \epsilon))$を証明します。 しかし、フィードバックが利用できることで、より優れた定数(より良い順序ではない)の後悔境界を達成できるアルゴリズム設計が可能となり、そのようなアルゴリズムを1つ設計し、その性能を数値的に評価する。

関連論文リスト

• A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
  我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。 誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。 我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
  論文  参考訳（メタデータ） (2024-09-08T12:19:12Z)
• Learning for Bandits under Action Erasures [20.235500642661812]
  我々は,学習者が消去チャネル上で分散エージェントにアクションを伝える必要がある,新しいマルチアーム・バンディット(MAB)について考察する。 我々のモデルでは、分散エージェントはアクションが消去されるかどうかを知っているが、中心的な学習者は知らない。 本稿では,既存のMABアルゴリズム上で動作可能な手法を提案する。
  論文  参考訳（メタデータ） (2024-06-26T05:03:00Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Adversarial Bandits with Multi-User Delayed Feedback: Theory and Application [17.64363983613468]
  我々は,マルチユーザ遅延フィードバックを用いた逆MAB問題を定式化し,修正されたEXP3アルゴリズム MUD-EXP3 を設計する。 本稿では,複数のユーザからの遅延フィードバック結果について考察し,内部分布に制限を加えることなく検討する。
  論文  参考訳（メタデータ） (2023-10-17T12:08:15Z)
• Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback [9.771002043127728]
  本稿では,最大値報酬関数に対する最大値と指数フィードバックに基づくマルチアームバンディット問題を考察する。 有限なサポートを持つ任意の分布にしたがって、アーム結果を持つ問題インスタンスに対して、アルゴリズムを提案し、後悔の束縛を与える。 我々のアルゴリズムは、$O(((k/Delta)log(T))$ distribution-dependent と $tildeO(sqrtT)$ distribution-independent regret を達成する。
  論文  参考訳（メタデータ） (2023-05-25T14:02:12Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• Multi-armed Bandit Algorithm against Strategic Replication [5.235979896921492]
  我々は,各エージェントが一組のアームを登録する多腕バンディット問題を考慮し,各エージェントがそのアームを選択すると報酬を受け取る。 エージェントは、より多くの武器を複製で戦略的に送信し、バンディットアルゴリズムの探索と探索のバランスを悪用することで、より多くの報酬をもたらす可能性がある。 本稿では,複製の復号化と,最小限の累積後悔を実現するバンディットアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-23T07:38:44Z)
• 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)
• Online Model Selection: a Rested Bandit Formulation [49.69377391589057]
  静止したバンディット設定における最善のアーム識別問題を紹介し,解析する。 我々は、この問題の後悔の新しい概念を定義し、ゲームの終わりに最小の期待損失を持つ腕を常に再生するポリシーと比較します。 最近のバンディット文献における既知のモデル選択の試みとは異なり、アルゴリズムは問題の特定の構造を利用して、予想される損失関数の未知のパラメータを学習する。
  論文  参考訳（メタデータ） (2020-12-07T08:23:08Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Blocking Bandits [33.14975454724348]
  我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。 全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。 我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2019-07-27T20:42:01Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。