概要
ポーカーとかのAIで有名なcounterfactual regret minimization(CFR)。ひとことで言うと、近似ナッシュ均衡を求めるための手法。
Regret Minimization
まず、CFRの元となったRegret Minimizationの説明から。Regret Minimizationとは、その名の通り、過去の学習データから、regret(後悔)が最も小さくなる(minimization)手を選択する手法。
じゃんけんの例
例として、二人でじゃんけんを繰り返し行う場合を考える。この時、勝つと1点、負けると-1点、引き分けると0点もらえるとし、これを繰り返し試行する仮定する。
まず1回目としてプレイヤーAがグー、プレイヤーBがパーを出したとする。
そしてプレイヤーAは負けたので-1点となる。
ここでプレイヤーAはパーを出してれば引き分けで0点、チョキを出していれば勝利で1点もらえる。
つまりプレイヤーAは1回目の戦略に対して、下記のように後悔の値を定量化することが出来る。この定量化した値をregretと呼ぶ。
- 戦略パー 0 - (-1) = 1
- 戦略チョキ 1- (-1) = 2
CFRでは、2回目の戦略を決めるにあたって、regretに比例した確率で戦略を決定する。
つまり、2回目にチョキを選ぶ確率は2/3、パーを選ぶ確率は1/3、グーを選ぶ確率は0である。
ここで2回目の試行としてプレイヤーAがチョキ、プレイヤーBがグーを出したとする。
2回目の試行もプレイヤーAの負けなので、-1点となる。regretはそれぞれ次のようになる。
- 戦略パー 1 - (-1) = 2
- 戦略グー 0 - (-1) = 1
3回目の試行では、1,2回目を通したregretの値を利用する。
- 戦略パー 1 + 2 = 3
- 戦略チョキ 2 + 0 = 2
- 戦略グー 0 + 1 = 1
よって、3回目の試行でそれぞれの戦略が選ばれる確率は、パーが3/6=1/2、チョキが2/6=1/3、グーが1/6である。
これがRegret Minimization。
ここで非常に重要なのが、Regret Minimizationにおいて、プレイヤーの平均的なregretがe未満であるとき、その時の戦略は近似ナッシュ均衡戦略であるといえる、という定理があること。
つまり、言い換えるとRegret Minimizationは近似ナッシュ均衡戦略を求める手法であるということが出来る。
Counterfactual Regret Minimization
そしてようやく出てきてCFR。これのコンセプト自体を直感的に説明するのは少々難しいので別の機会に譲る。
ただ、これがなぜ重要なのかだけをメモしておく。
まず、CFRで提案されている概念のRegret(Immediate counterfactual regret) は必ず、Regret Minimizationのregret以上の値になる。つまり、Immediate counterfactual regretを最小化することは、Regretを最小化することにつながる。仮にImmediate counterfactual regretがaと求められたのならば、少なくともその時の戦略はa以下の近似ナッシュ均衡戦略であると言えるわけだ。
なぜ、こんなめんどくさいことが重要かといえば、解を解くときの計算量の関係。
ナッシュ均衡はとてもじゃないけど求められないし、近似ナッシュ均衡戦略を求めるregret minimizationもまだ十分に計算量が多い。そこで計算量が小さいCFRが重宝されている。
0 件のコメント:
コメントを投稿