論文の概要: 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 Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Batch Bayesian Optimization for Replicable Experimental Design [56.64902148159355]
多くの実世界の設計問題は、大規模で異質な観測ノイズのため、複数の実験条件を並列に評価し、各条件を複数回再現する。
本稿では,3つのアルゴリズムを含むReplicable Experimental Designフレームワークのバッチトンプソンサンプリングを提案する。
我々は,アルゴリズムの有効性を,精密農業とAutoMLの2つの実世界の応用例で示す。
論文 参考訳(メタデータ) (2023-11-02T12:46:03Z) - 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 [84.04424523097168]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Multi-armed Bandit Algorithm against Strategic Replication [5.235979896921492]
我々は,各エージェントが一組のアームを登録する多腕バンディット問題を考慮し,各エージェントがそのアームを選択すると報酬を受け取る。
エージェントは、より多くの武器を複製で戦略的に送信し、バンディットアルゴリズムの探索と探索のバランスを悪用することで、より多くの報酬をもたらす可能性がある。
本稿では,複製の復号化と,最小限の累積後悔を実現するバンディットアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-23T07:38:44Z) - P-WAE: Generalized Patch-Wasserstein Autoencoder for Anomaly Screening [17.24628770042803]
Patch-wise Wasserstein AutoEncoder (P-WAE) アーキテクチャを提案する。
特に、ジグソーパズルの解法と結合したパッチワイド変分推論モデルを設計する。
MVTec ADデータセットを用いた総合的な実験は、我々のプロポの優れた性能を実証する。
論文 参考訳(メタデータ) (2021-08-09T05:31:45Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。