Fictitious Self-Play in Extensive-Form Games, ICML2015
fictitious play問題は、プレイヤー同士がゲームをプレイし、敵対者の期待戦略に対する最適な対応行動を選択する問題である。
特定のクラスのゲームでは、上記設定におけるプレイヤーの期待行動はナッシュ均衡に収束する。
この問題に対する手法はlarge-scaleに対応したものが少ない。
ゲームには2種類あり、extensive formは逐次各状態毎に行動戦略関数を用い行動を決定する。
normal formはプレイヤーが到達可能な状態を全て考慮し行動を決定する。
extensive formはnormal formに変換可能だが、可能な行動が指数的に増大する。
extensive formは行動戦略関数の利用により表現力が高い。
この行動戦略関数にfictitious playの考え方を適用した2つの定義が提案されているが、それらの収束性は不完全情報ゲームで示されていない。
本論で提案するfictitious playの派生手法の1つ目は、normal formと等価なextensive formの手法で、収束保証がなされている。
しかし状態数に対して線形オーダーの複雑性を持った戦略関数しか用いる事が出来ない。
こうした手法は厳密に各状態から可能な行動を全て考慮する。
一方で戦略関数を機械学習モデルなどで近似して推論を行うweakened fictitious play手法がある。
本論でこの手法に基づき、かつサンプリングベースの強化学習手法としてfictitious self playを提案する。
これは今までの経験をexperience playの考え方で再学習する事も取り入れている。
Subsampling Methods for Persistent Homology, ICML2015
topological data analysisでは、ある確率測度の元サンプルされたデータを元にそれが持つ構造的特徴を解析する分野である。
TDAの1つとしてスケールを変化させられる距離関数で、そのスケール変化に対するデータ特徴変化を要約し、landscapeと呼ばれる要約関数で表現するpersistent homologyがある。
こうした要約統計量を計算する際には、データの時空間方向に対するスケーラビリティが、高次元データへTDAを適用する場合に問題になる。
本論では、Wasserstein計量の元で摂動が起こる測度空間上でサブサンプルする場合に、そこから確率的に得られるlandscape関数の期待値は不偏推定値として用いれる事を示した。
この期待値は外れ値に対してロバストである。
また同様の考え方で、測度に関するsupport集合に近づけるようなサブサンプルを行う事で推定を行う手法を提案する。