論文の概要: Replication-proof Bandit Mechanism Design

• arxiv url: http://arxiv.org/abs/2312.16896v1
• Date: Thu, 28 Dec 2023 08:36:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-29 16:46:39.505111
• Title: Replication-proof Bandit Mechanism Design
• Title（参考訳）: 複製防止バンド機構の設計
• Authors: Seyed Esmaeili, MohammadTaghi Hajiaghayi, Suho Shin
• Abstract要約: エージェントが自分の腕を戦略的に登録したり、複製したりする際に、複製防止バンディット機構を設計する問題について検討する。 この拡張は平衡解析において大きな課題をもたらす。 あらゆる問題に対して複製耐性のアルゴリズムを提供する。
• 参考スコア（独自算出の注目度）: 9.101603681930085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a problem of designing replication-proof bandit mechanisms when agents strategically register or replicate their own arms to maximize their payoff. We consider Bayesian agents who are unaware of ex-post realization of their own arms' mean rewards, which is the first to study Bayesian extension of Shin et al. (2022). This extension presents significant challenges in analyzing equilibrium, in contrast to the fully-informed setting by Shin et al. (2022) under which the problem simply reduces to a case where each agent only has a single arm. With Bayesian agents, even in a single-agent setting, analyzing the replication-proofness of an algorithm becomes complicated. Remarkably, we first show that the algorithm proposed by Shin et al. (2022), defined H-UCB, is no longer replication-proof for any exploration parameters. Then, we provide sufficient and necessary conditions for an algorithm to be replication-proof in the single-agent setting. These results centers around several analytical results in comparing the expected regret of multiple bandit instances, which might be of independent interest. We further prove that exploration-then-commit (ETC) algorithm satisfies these properties, whereas UCB does not, which in fact leads to the failure of being replication-proof. We expand this result to multi-agent setting, and provide a replication-proof algorithm for any problem instance. The proof mainly relies on the single-agent result, as well as some structural properties of ETC and the novel introduction of a restarting round, which largely simplifies the analysis while maintaining the regret unchanged (up to polylogarithmic factor). We finalize our result by proving its sublinear regret upper bound, which matches that of H-UCB.
• Abstract（参考訳）: エージェントが自分の腕を戦略的に登録したり複製したりする際に、複製防止バンディット機構を設計する際の課題について検討する。 我々は,自分たちの腕の平均報酬の実現を意識していないベイジアンエージェントを考察し,shin et al. (2022) のベイジアン拡張を初めて研究した。 この拡張は、S Shin et al. (2022) による完全インフォームド・セッティングとは対照的に、平衡解析において重要な課題を示しており、各エージェントが単一のアームしか持たないケースに還元される。 ベイズエージェントでは、単一エージェントの設定であっても、アルゴリズムの複製耐性を解析することが複雑になる。 H-UCB の定義した Shin et al. (2022) が提案したアルゴリズムは、探索パラメータに対してもはや複製耐性がないことを示す。 そして,単一エージェント設定において,アルゴリズムが複製耐性を持つための十分かつ必要な条件を提供する。 これらの結果は、いくつかの分析結果を中心に、独立した関心を持つ複数のbanditインスタンスの期待された後悔を比較する。 さらに、ETCアルゴリズムがこれらの特性を満たすことを証明しているが、UCBはそうではない。 この結果をマルチエージェント設定に拡張し、任意の問題に対してレプリケーション耐性アルゴリズムを提供する。 この証明は、主に単一エージェントの結果と、etのいくつかの構造的性質と、リスタートリングラウンドの新規導入に依存している。 我々は,H-UCBと一致するサブ線形後悔上限を証明し,その結果を確定する。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Regression with Multi-Expert Deferral [30.389055604165222]
  複数の専門家で予測を遅延させる学習は、学習者が複数の専門家に予測を遅延させることを選択できるフレームワークである。 本稿では、複数の専門家に予測を延期することを含む、遅延を伴う新しい回帰の枠組みを提案する。 両シナリオに新たなサロゲート損失関数を導入し,これらが$H$一貫性境界でサポートされていることを証明した。
  論文  参考訳（メタデータ） (2024-03-28T15:26:38Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  マルチエージェント強化学習(MARL)理論における中心的な問題は、構造条件やアルゴリズムの原理がサンプル効率の学習保証につながるかを理解することである。 本稿では,複数のエージェントを用いた対話型意思決定のための一般的な枠組みとして,この問題について考察する。 マルチエージェント意思決定における統計的複雑性を特徴付けることは、単一エージェント決定の統計的複雑性を特徴付けることと等価であることを示す。
  論文  参考訳（メタデータ） (2023-05-01T06:46:22Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Multi-armed Bandit Algorithm against Strategic Replication [5.235979896921492]
  我々は,各エージェントが一組のアームを登録する多腕バンディット問題を考慮し,各エージェントがそのアームを選択すると報酬を受け取る。 エージェントは、より多くの武器を複製で戦略的に送信し、バンディットアルゴリズムの探索と探索のバランスを悪用することで、より多くの報酬をもたらす可能性がある。 本稿では,複製の復号化と,最小限の累積後悔を実現するバンディットアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-23T07:38:44Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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