反事実的後悔最小化の導入（訳せてない）

http://modelai.gettysburg.edu/2013/cfr/cfr.pdf

元の論文

反事実的後悔最小化の導入

１．動機

　　2000年に、HartとMas-Colellは、重要なゲーム理論、リグレットマッチングアルゴリズム（後悔組合せ方式？）を導入した。プレイヤーは将来のプレイをポジティブリグレット（正の後悔？）に比例したものにするために、過去のプレイに対するリグレット（後悔）を追跡して均衡プレイに至る。

　　この手法は単純で直感的であるだけでなく、最も難しいブラフを使うゲームにおけるコンピュータゲームプレイの革命を起こした。これには年一回のコンピューターポーカー大会での明確な優勢も含まれる。このアルゴリズムは比較的最近のものであるため、この分野における次世代の研究者や実践者がリグレットベースのアルゴリズムを導入するために利用できるカリキュラム資料がほとんどない。これらの資料は最新のイノベーションを、上級コンピューターサイエンス学部の学生や院生、興味を持っている研究者や野心的な実践者が、より利用しやすくするための控えめな第一歩として意義がある。

　　第2節では、プレイヤーリグレットの概念を紹介し、じゃんけんの例を読み書きできるプログラミングスタイルで提示しすることで後悔マッチングアルゴリズムを説明するとともに、プレイヤーリグレットの概念と例題との関連を示す。

　　Counterfactual Regret Minimization（CFR）（反事実的後悔最小化）はクーンポーカーを解く実例を使って第3節で紹介している。また１対１のサイコロDudo（デュード）をプレイする実際的なCFRの試作を最適化するための支援コードが提供されている。

　　第4節では、多くの場合結果を改善することができる、おおよそ最適に計算されたポリシーである「クリーニング」の手段に簡単に触れる。

　　第5節は、繰り返し状態のゲームに適用する高度なCFRのアプリケーション（例えば、不完全なリコール抽象化）をカバーする、これはCFRトレーニング反復の計算上の複雑さを指数関数から線形に減少させる。ここでは、アルゴリズムのアプリケーションをデモンストレーションするために私たちが独自に考案したゲーム「Liar Die」を使う。私たちは読者がこのテクニックを3クレームのメモリーとして1対1サイコロDudoに適用することを想定している。

　　第6節では、公開研究の問題について簡単に議論する。可能な均衡戦略の中で、相手のエラーを最適に利用するものをどのように計算しますか？読者は、この興味深い問題の洞察を得るために、例とした「Liar Die」のコードを修正することを依頼されている。

　　最後に、第7節では、継続的な学習の問題と道筋にさらに挑戦します。

2.ゲームでの後悔

この節では、コンピュータが自己シミュレートしたプレイを通して、将来の選択に情報をあたえるために、過去のゲームの選択肢の後悔を使用する手段を説明する。 まず、慣れた親しんだゲームのじゃんけんを紹介する。 ゲーム理論の基礎的な用語を定義した後、後悔マッチングについて議論し、期待される後悔を最小限に抑えるアルゴリズム計算戦略を提示する。このアルゴリズムを使用して、じゃんけん戦略および関連する演習を学習するための実例を提示する。

2-1じゃんけん

 じゃんけんは岩、紙、ハサミの３つのジェスチャーののそれぞれを同時に行う2人プレイのゲームだ。

他のプレーヤーに勝つ、負けさせる、または引き分ける機会がある。同じジェスチャーを出したプレイヤー同士は引き分けだ。「岩はハサミを壊す」ので岩はハサミに勝つ。「ハサミは紙を切る」のでハサミは紙に勝つ。「紙は岩を包む」ので紙は岩に勝つ。プレイヤーは通常、4拍の詠唱をすることでプレイを同期させます。“Rock! Paper! Scissors! Shoot!”最初の３拍に指を伸ばした手のひらを細かく上下させ、4番目の拍に3つのジェスチャーのうちの1つを同時に表明する。

2-2ゲーム理論の定義

このようなゲームを最適に、または完全にプレイすることは、どういう意味だろう？この質問は、相手のプレイによって決まる勝ち負けの差し引きを最大化する、というようないくつかの意味をもつだろうか？この節では、ゲーム理論からのいくつかの基本的な用語と定義を紹介し、最適なプレイのための解法の概念を考察する。ここでは、［12］の表記と用語に従います。まず、ノーマルフォームのゲームをタプル（N、A、u）として定義する。ここで

•N = {1、...、n}はn人の選手の無限集合         

•Siは、プレイヤーiの行動や選択肢の無限の集合 

•A = S1×... Snは、すべてのプレイヤーの同時アクションのすべての可能な組み合わせの集合

(同時アクションの可能な組み合わせはそれぞれ、アクションプロファイルと呼ばれる。）

•uは、各アクションプロファイルを各プレイヤーのユーティリティのベクトルにマッピングする関数。私はプレーヤーiのペイオフをuiと呼んでいる。

ノーマルフォームのゲームは、各プレイヤーが1つの選択しかしないため、一般に「ワンショットゲーム」とも呼ばれる。 ノーマルフォームのゲームはｎ次元テーブルとして表される、各次元は一人のプレーヤのアクションに対応する行/列を有し、各テーブルエントリは、一つのアクションプロファイル（各プレイヤからの一つのアクションの交差点）に対応し、テーブルエントリは各プレーヤのユーティリティ（ペイオフまたは報酬）のベクトルが含まれている。じゃんけんのペイオフテーブルは次のとおりだ、