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