論文の概要: Replication-proof Bandit Mechanism Design with Bayesian Agents
- arxiv url: http://arxiv.org/abs/2312.16896v2
- Date: Fri, 31 Jan 2025 22:11:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-04 16:03:41.609913
- Title: Replication-proof Bandit Mechanism Design with Bayesian Agents
- Title(参考訳): ベイズ剤を用いた複製防止バンド機構の設計
- Authors: Suho Shin, Seyed A. Esmaeili, MohammadTaghi Hajiaghayi,
- Abstract要約: エージェントが自分の腕を戦略的に登録したり複製したりする際に、複製防止バンディット機構を設計する際の課題について検討する。
我々は,各自の腕の平均報酬の分布のみを把握しているベイズエージェントについて検討する。
- 参考スコア(独自算出の注目度): 11.758708370032469
- License:
- Abstract: We study the problem of designing replication-proof bandit mechanisms when agents strategically register or replicate their own arms to maximize their payoff. Specifically, we consider Bayesian agents who only know the distribution from which their own arms' mean rewards are sampled, unlike the original setting of by Shin et al. 2022. Interestingly, with Bayesian agents in stark contrast to the previous work, analyzing the replication-proofness of an algorithm becomes significantly complicated even in a single-agent setting. We provide sufficient and necessary conditions for an algorithm to be replication-proof in the single-agent setting, and present an algorithm that satisfies these properties. These results center around several analytical theorems that focus on \emph{comparing the expected regret of multiple bandit instances}, and therefore might be of independent interest since they have not been studied before to the best of our knowledge. We expand this result to the multi-agent setting, and provide a replication-proof algorithm for any problem instance. We finalize our result by proving its sublinear regret upper bound which matches that of Shin et al. 2022.
- Abstract(参考訳): エージェントが自分の腕を戦略的に登録したり複製したりする際に、複製防止バンディット機構を設計する際の問題点について検討する。
具体的には,各自の腕の平均報酬の分布のみを把握しているベイズエージェントについて検討する。
興味深いことに、ベイズエージェントは以前の研究とは対照的に、単一エージェントの設定でもアルゴリズムの複製耐性を分析することは著しく複雑になる。
単一エージェント環境では,アルゴリズムが複製耐性を持つための十分かつ必要な条件を提供し,これらの特性を満たすアルゴリズムを提案する。
これらの結果は、複数のバンドイットインスタンスの期待された後悔を伴って \emph{comparing the expected regret of multiple bandit instance} に焦点をあてるいくつかの解析的定理を中心にしている。
この結果をマルチエージェント設定に拡張し、任意の問題に対してレプリケーション耐性アルゴリズムを提供する。
我々は,Shin et al 2022と一致するサブリニア後悔の上界を証明し,その結果を確定する。
関連論文リスト
- Replicability is Asymptotically Free in Multi-armed Bandits [41.86005698892541]
我々は,アルゴリズムの動作シーケンスがデータセットに固有のランダム性の影響を受けないことを高い確率で保証する,レプリカブルなマルチアームバンディットアルゴリズムを考察する。
非複製の確率を制限するための原則的アプローチを提案する。
論文 参考訳(メタデータ) (2024-02-12T03:31:34Z) - Pure Exploration under Mediators' Feedback [63.56002444692792]
マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。
本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。
本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
論文 参考訳(メタデータ) (2023-08-29T18:18:21Z) - 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) - Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。
エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。
我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
論文 参考訳(メタデータ) (2022-06-01T00:44:53Z) - 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) - Adaptive Algorithms for Multi-armed Bandit with Composite and Anonymous
Feedback [32.62857394584907]
複合および匿名フィードバックによるマルチアームバンディット(MAB)問題を研究する。
本稿では,逆の場合と非逆の場合の適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-13T12:25:41Z) - Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a
Differentially Private Scheme [16.1694012177079]
我々は,多腕バンディットにおける最高の武器識別問題,潜在的に私的な報酬について検討する。
ゴールは、固定された所定のレベルで、最も高い定量値を持つ腕を特定することである。
このアルゴリズムは$delta$-PACであり,サンプルの複雑さを特徴付ける。
論文 参考訳(メタデータ) (2020-06-11T20:23:43Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳(メタデータ) (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。