サンプリング平衡:構造化ゲームにおける高速非リグレット学習【JST・京大機械翻訳】

Beaglehole Daniel; Hopkins Max; Kane Daniel; Liu Sihan; Lovett Shachar

プレプリント

J-GLOBAL ID：202202205108524168 整理番号：22P0279918

サンプリング平衡:構造化ゲームにおける高速非リグレット学習【JST・京大機械翻訳】

Sampling Equilibria: Fast No-Regret Learning in Structured Games

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

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

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

ゲームにおける学習と平衡計算は,コンピュータ科学と経済学における基本的問題であり,政治から機械学習までの応用がある。この領域における多くの作業は,ランダム加重大多数(RWM)と呼ばれる単純なアルゴリズム,すなわち,「Hedge」または「Multiplicitive weight update」として知られており,これは,敵対的設定(LitlestoneおよびWarmuth’94,FreundおよびSchapire’99)において,統計的に最適な速度を達成することが良く知られている。残念ながら,RWMは固有の計算障壁を持つ:それは全ての可能な行動にわたって分布からの維持とサンプリングを必要とする。関心の典型的設定において,行動空間は指数的に大きく,実際にはRWMを実際に利用しない。本研究では,多様な構造化ゲームに対するこの概念を精緻化し,RWMの多対数時間における行動空間を効率的に(約)サンプルに見出すことが可能であることを示した。これは,(離散)コロニーBlottoゲーム,マトロイド輻輳,マトロイドセキュリティ,および基本的推論ゲームのような問題のための最初の効率的非レグレットアルゴリズムを与える。即座として,著者らは,いくつかの重要な設定において以前の方法より指数的に速いこれらのゲームのために,近似Nash Equilibriaを計算するための多対数時間メタアルゴリズムを与えた。さらに,このアルゴリズムは,一般的和,2つ以上のプレーヤー,およびコロニーBlotto,複数の資源タイプで,これらのゲームのより関係する変異体に対する平衡を効率的に計算するために初めてである。【JST・京大機械翻訳】

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

人工知能 , ゲーム理論

, , , ,

前のページに戻る