論文の概要: 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と一致するサブ線形後悔上限を証明し,その結果を確定する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。