コミュニケーションのないマルチプレーヤマルチアームバンディットにおけるインスタンス依存保証のパレートフロンティア【JST・京大機械翻訳】

Liu Allen; Sellke Mark

プレプリント

J-GLOBAL ID：202202205829006966 整理番号：22P0292265

コミュニケーションのないマルチプレーヤマルチアームバンディットにおけるインスタンス依存保証のパレートフロンティア【JST・京大機械翻訳】

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年02月19日プレプリントサーバーでの情報更新日： 2022年06月06日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

確率的多重層マルチアームバンド問題を研究した。この問題において,mプレーヤは,K>mアームからそれらの総報酬を最大化するように協調する。しかし,同じアームを同じ時間に引き出すと,プレーヤーは通信できず,ペナルティ化(例えば報酬なし)される。Δがm-thとm+1-st最良アームの間のギャップである最適インスタンス依存regret O(1/Δ)を得ることが可能であるかどうかを検討した。このような保証は,最近,意図的衝突を通して暗黙的に通信するプレーヤーを可能にするモデルで達成された。驚くべきことに,著者らは,通信なしで,そのような保証は達成できないことを示した。事実,Δの幾つかの値に対する最適O(1/Δ)レレットを得ることは,他の領域における厳密な準最適レレットを意味する。主な結果は,通信なしに可能なパレート最適インスタンス依存トレードオフの完全な特性化である。著者らのアルゴリズムはBubeck,Budzinski,および第2著者のそれを一般化する。そこで,このアルゴリズムは,衝突時のフィードバックが,強い非衝突特性のおかげで,適応敵対によって崩壊できる場合でも成功する。著者らの下限は多重スケールでのトポロジー的障害物に基づいており,完全に新しい。【JST・京大機械翻訳】

, , , , , , , ,
, , , , 【Automatic Indexing@JST】

人工知能

, , ,

前のページに戻る