Microsoftの最強麻雀AI Suphx の論文ざっくり日本語訳（各種アルゴリズムからpMCPAまで）

## こちらの記事の続きになります

この論文を読んだことが無い方はこちらの記事から読むことをおすすめします。
（それと麻雀と情報工学基礎レベル（エントロピッピがわかるレベル）で噛み砕いているので、分かりづらかったらごめんなさい）

https://qiita.com/Intel0tw5727/items/e122197b5a2958a22b34

## 3. 学習アルゴリズム

Suphxの学習には大きく3つのステップがあり、天鳳の上位ユーザーの牌譜を用いて5つのモデル（捨て牌・ポン・カン・チー・リーチモデル）を教師あり学習で学習する。次に強化学習によって作成したモデルを改良する。強化学習では3.1節で解説する一般的な勾配アルゴリズムを採用し、3.2節で解説するGlobal reward Predictionと3.3節で解説するOracle guideを導入することで、麻雀特有の課題を解決している。そして最後にオンライン対戦時には3.4節で解説するRuntime Policy adaptation を使用して、現在の局からの予測結果を活用することでよりよい成果を発揮します。

### 3.1 エントロピー正則化による分散強化学習

Suphxの学習は分散強化学習に基づいており、特に方策勾配法[^1]を採用して、重点サンプリング[^2]を活用することで、非同期分散学習において欲しい範囲のサンプルを重点的にサンプリングすることができる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/f4ec59d3-abc9-9c28-8781-56f3523a0cad.png)

$\theta'$ は学習用の軌跡を生成するポリシー[^3]のパラメータである。$\theta$は更新するべき新しいポリシーだが、強化学習ではポリシーのエントロピーに敏感であるため、エントロピーが小さい場合に収束が早まってしまってあまり改善がされない。そのため強化学習中のポリシーのエントロピーを以下のように正則化する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/de2015a4-24b5-4275-132e-4db2962ac71d.png)

$H(\pi_{\theta})$ はポリシー $\pi_{\theta}$のエントロピーで、 $\alpha$ はトレードオフ係数にあたる。安定した探索を実施するために、直近でポリシーのエントロピーが $H_{target}$よりも小さいもしくは大きい場合に、エントロピー項を増加もしくは減少するように $\alpha$ を動的に調整する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/5e61fb33-e2e6-2874-7237-2bbc9b51daa4.png)

$\bar{H}(\pi_{\theta})$ は直近の学習におけるエントロピーであり、$\beta > 0$は小さなステップサイズにあたる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/86914907-98e0-08dc-1aeb-8403fb3ef520.png)

Suphxが使用している分散型強化学習システムを図6に示す。このシステムでは複数のSelf-play workersで構成されていて、それぞれにはCPUベースの麻雀シミュレーターのセットと、軌道を生成するためのGPUベースの推論エンジンのセットが含まれている。ポリシーの更新自体は推論エンジンとは別になっており、Parameter server上にてポリシーを更新する。シミュレーターでは強化学習エージェントをプレイヤーとしてゲームをランダムに実行し、もしアクションを起こす必要があった場合には現在の状況を推論エンジンに送り、行動をエージェントに返す。推論エンジンはParameter serverから最新のポリシーを定期的に更新し最新のポリシーに近いものになるようにしている。

### 3.2 Global Reward Prediction

麻雀は1半荘で約8局から12局ほど対局するが、プレイヤーは各局終了時に点棒移動が行われオーラス終了時の点数によって最終順位が得られる。しかしこのルールは点棒を軸にしても、現在順位を軸にしても、強化学習という観点では良い報酬になりえない。

- 点棒が報酬になりえない理由として、各局ごとの結果を元にしてうまく打てた局とそうでない局を区別することができない。そのため各局ごとにパフォーマンスを測定する必要がある。
- 現在順位が報酬になりえない理由として、打ち筋が局ごとに異なる（例としてオーラス1着の場合、打ち筋は保守的になるなど）ため、必ずしもアガリを重ね続けることが方針としていいわけではなく、局ごとに打ち方の評価が一定ではないことがあげられる。

したがって、強化学習に効果的な報酬を設計するには、局ごとの理想的な持ち点を各局ごとに適切に与える必要がある。そのために、現在の局と過去の局の情報から、最終的な持ち点を予測するGrobal Reward Prediction $\phi$ を導入する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/a77a95b7-c3e5-9071-12aa-f16f9f8af836.png)

図7に示すように、予測機はRNNで構成され具体的には2層のGRU[^4]とそれに続く2つの全結合層で構成される。予測器の学習データは天鳳の上位プレイヤーの牌譜から来ており、 $\phi$ は平均二乗誤差を最小化することで学習される。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/dc349037-eb63-992c-5d1f-e334ca589354.png)

$N$は学習データのゲーム数を差していて、$R_i$はi局時点の持ち点。$K_i$はi局時点の局数、$x^{k}_{i}$はi局時点の特徴ベクトルを示す。 $\phi$ が十分に学習されている場合には、K局のゲームでは強化学習のためにk番目の対局の報酬として $\phi(x^k) - \phi(x^{k-1})$ を使用する。（前の対局より優れた対局ができていたか）

### 3.3 Oracle Guiding

麻雀には山や王牌や他プレイヤーの手牌など、隠れた情報が多く存在する。これらの情報が見えていない状況で最適な行動を学習するのは難しく、たとえ強化学習で方針を学べるとしても効率はよくなく学習が遅くなることが考えられる。そこで見えていない情報をすべて見える状態のエージェントを導入して学習を高速化する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/dc049d34-a58e-8bdc-dd55-fa4f2dcdcb00.png)

隠れ情報を含むすべての情報を得たオラクルエージェントがどのようにして、通常のエージェントの学習を高速化させるのかというと隠れ情報が見える状態を1としたときに、そこから徐々に0に近づけていくようにトレーニングさせることで最終的には通常のエージェントの学習と遜色ない学習にする。0になったときにそこから通常の学習を複数回実施する。この継続的な学習の際に学習率を10分の1にして、重みが予め設定された閾値より大きい場合に、いくつか状態と行動のペアを拒否することで、本稿では安定した学習をみることができた。逆にこれを試さない場合は改善がなかった。

### 3.4 Prametric Monte-Carlo Policy Adaptation

麻雀の場合、各局ごとに与えられる配牌によって戦略が大きく異なる。例えば手牌が良い場合は点数が大きくなるように積極的に動いたり、悪ければ点数を振り込まないように考えたり点数度外視で早くアガるなどといった風に打っていくだろう。これを事前に戦略として取り入れモデルの予測時に適用させられればより強いエージェントが作成できると考えられる。

モンテカルロ木探索(MCTS)は囲碁や将棋などで使われているものの、初期状態が配牌で異なるためゲームツリーを作るのは難しい。そこで新しくParametric Monte-Carlo Policy Adaptationを提案する。

局が始まる際に事前に学習されたポリシーを初期手牌に対して以下のように適用させる

1. シミュレーションの実施
    - 具体的には配られた手牌を除いた残りの牌で相手の手牌をランダムにサンプリングして、ポリシーに基づきどのような対局になるかをKパターンほど生成する。
1. 適応
    - 生成した対局パターンを用いて勾配更新を行って、オフラインポリシーを微調整する
1. 推論
    - この局で対局するためのポリシーを2で適用させたオフラインポリシーに更新する

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/186010/28815f73-0846-58b1-38c1-10930c468e06.png)

$h$ はある局でのエージェントの手牌、 $\theta_o$はオフラインで学習したポリシーのパラメータ、 $\theta_a$ は新しく更新したパラメータになる。 $\tau(h)$ は軌道の集合で、 $p(\tau;\theta)$ はポリシーが軌道を生成する確率になる。

本研究では、シミュレーションの数Kはあまり大きくする必要は鳴くpMCPAは局すべての次の状態を集める必要はない。pMCPAがパラメトリックな手法のため、更新されたポリシーはシミュレーションでは見られなかった状態の推定も更新することができる。つまり、少ないシミュレーションであってもある程度一般化することに役立つ。

ただしポリシーの更新は各局ごとに実施されることに注意する必要がある。その局で更新されたポリシーを次の局で使うことはなく、またオフラインのポリシーをベースに更新していくことになる。

## 次の目標

アルゴリズムを理解しながらまとめていくの大変だったので4章は次で。 

https://qiita.com/Intel0tw5727/items/e7625fb005982d225ea2

[^1]: すごく丁寧にまとめてくださっている方がいらっしゃったので雰囲気から理解しておきたい方は[こちら](https://dajiro.com/entry/2020/05/19/170402)より
[^2]: 超絶わかりやすくまとめてくださってる方がいらっしゃったので雰囲気から理解しておきたい方は[こちら](https://aidiary.hatenablog.com/entry/20140920/1411207305)
[^3]: 強化学習には On-policy な学習と Off-policy な学習がある。短くまとめると「戦略に乗っ取って行動する」か「戦略に関係なく行動する」からしいです。ウルトラわかりやすくまとめてくださっている方がいらっしゃったので雰囲気から理解しておきたい方は[こちら](https://qiita.com/ABmushi/items/83a639506fcbc4050ce8#sarsaon-policy%E3%82%A8%E3%83%BC%E3%82%B8%E3%82%A7%E3%83%B3%E3%83%88)
[^4]: GRUの理解にはRNN→LSTMと再帰型ニューラルネットワークの基礎を抑えてある必要があるので、ざっくり理解したいんだよという方はこちらにアルティメットわかりやすくまとめてくださっている方がいらっしゃったので雰囲気から理解しておきたい方は[こちら](https://agirobots.com/lstmgruentrance-noformula/#keni-toc19)