学マスで(私が)学ぶ、動的計画法(実装編その1)
前回記事の続き。玉手箱を開けてしまった浦島太郎よろしく、おじいちゃんが最近の技術を勉強する回です。そんなわけで、以下内容は誤りを含んでいる可能性があり、言わずもがなですが参考にされる際は自己責任でお願いします。
前回記事（基礎編）はこちら。
gymnasium
今回は、アマゾンで色々比較検討した結果、以下の書籍を参考に進めてみることにした。この本、めちゃくちゃわかりやすいぞ。今のところ当たり感がある。
gymnasiumというライブラリがある。chatGPTで有名なOpenAI が作っていたOpenAI gymがサ終して、フォークされたものとのこと。当初、上記底本を読む前に触ってみたのだが、ドキュメントがやや不親切でいじるのに難儀した。始めから底本を読んでおけばよかった。インストールはコマンドラインから
pip install gymnasiumでOK。なお、サイズの都合からか準備された環境は別インストールになっており、gymnasium[box2d]などとしてpip installすればいい。
強化学習は、エージェントが環境からフィードバックを得て方策(policy)をアップデートしていく型の機械学習だが、gymnasiumは、一言で言うと環境とエージェントを実装するための一貫したインターフェースだ。そしていくつかの環境については実装もある。備忘のため、gymnasiumのインターフェースをまとめておく。(底本で参照しているgymのバージョンが古いらしく動作が異なっており、https://gymnasium.farama.org/ のリファレンスを元にしている)
gymnasium.Env
環境を表したクラスで、学マスで言うとゲームシステムそのもの。大雑把には以下のインターフェース・メンバを把握して、サブクラスを実装していけばよい。(カッコ内は学マスとの対応）:
reset() -> observation, info:
メソッド。ゲーム状態を初期化する。初期状態の観測結果(体力が30で初期手札がこれで、といった情報）を返す。昔のバージョンだとinfoがなかったので、既存のコードを動かすときは注意。(だいたい、代入式の左辺に ,info を加える修正をすればOK)step(action) -> observation, reward, terminated, truncated, info:
メソッド。エージェントが行動をとることによる環境の更新およびその後の観測結果observationおよび報酬reward(そのターンで取った得点)を返す。なお、ゲーム終了判定としては予め設定された終了状態に到達したterminatedと途中で終了条件を満たしたtruncatedの二つのフラグで管理されている。どうやら昔はこの二つを合わせてdoneとして扱っていたようで、仕様が変わっていることに注意する。こちらも左辺の変数が足らなくなるので、いったんterminatedとtruncatedで受けて、is_done=truncated and terminated 等ととすればよい。action_space: Space
メンバ変数。取りうる行動の選択肢を網羅したリスト。(例えば手札に左から0, 1, 2と番号を付けることにすれば[0,1,2]というリストだが、詳細は後述する)なお抽象クラスSpaceはgymnasiumの独自クラスで、その中から一つをランダムに選ぶsample()と、行動aがaction_spaceに含まれているかを判定するcontains(a)というメソッドを持つ。observation_space: Space
メンバ変数。観測値の取りうる範囲を網羅したリスト。
学マスシステムのpythonへの移植
すぐに手が動く言語がC++ということもあり、学マスの試験・レッスンシステムをこれで実装していた。然るに、上記gymnasiumや最近のナウいディープなフレームワークは何かとpythonで書かれている。pythonとC++の連携をスムーズに書けるようなスキルは持ち合わせていないので、同等のシステムをpythonに移植することにした。過去、LLとしてpythonではなくrubyを使ってたため大分難儀した。(メソッドの第一引数selfはまだ許せるが、インデントでブロックを記述するとか正気の沙汰とは思えない、というのが当時の判断基準だったのだが、言語仕様に対する判断としてはそこまで間違っていない気がしてしまう。浅学故か。）
pythonは静的な言語と異なり、基本的には継承≒実装継承、mix-inと思っておけばよいので、まずはgymnasiumのインターフェースをゆるくふわっと理解したうえで、それっぽいクラスを単独で書いてしまうことにした。私はプログラムを書くのが好きで、一回作ったプログラムのリライトも好きなので、案外苦も無くできた。やはり一度作ったもののリライトだと、設計上の注意点が明確になるから綺麗に書き直せる。
Q学習法
いきなりgymnasiumをmix-inすると何やってるのかわからなくなるおそれがあったので、ひとまず移植した学マスシステムに対してQ学習法を実装してみた。
Q学習法(Q-learning)は、以下の再帰式を脳筋で解くことを意味する。(notationは前回記事参照)
$$
\begin{array}{c}
\bar Q^n(s,a) = (1-\alpha)\bar Q^{n-1}(s,a)+\alpha \hat q^n \\
\mathrm{where} \quad \hat q^n = r(s^n,a^n)+\max_{a'}\bar Q^{n-1}(s^{n+1},a')
\end{array}
$$
「脳筋」というのは、$${Q(s,a)}$$のクソデカ定義域を離散的に扱って、値をテーブル形式で保持することを意味している。これであれば、環境のコードさえできてしまえば特別なライブラリや複雑なコーディングをせずとも学習アルゴリズムが記述できるが、難点は再帰回数を増やさないとテーブルがなかなか埋まらないこと。しかも離散的なので、たくさんある状態のうち少しだけ違った$${Q}$$の値どうしに関係がなく、学習後の$${Q}$$を実践に使うとき安定しないという問題もある。
もう一つ、行動のモデリング方法にも工夫が必要になる。単純に行動をモデルするだけであれば、「手札のうち左から何枚目を使ったか」という整数一つでモデル化できそうである。しかしこれだと学習がうまくいかない。というのもこれだと、エージェントは「実際にどのカードを使ったのか」という情報を取得できないからである。学習は「こういう行動をとるといいことがありそうだから、重みをつけよう」という挙動の繰り返しだから、「手札の何枚目」方式だとそのありがたみがうまく設定できないのだ。そこで、行動空間としてはデッキ全体を採用し、手札にあるもののみから行動を決定する、という段取りにした。これは数学的には、$${Q}$$関数の定義域を一回広げてから制限していることに対応する。
学習結果
上記$${Q}$$学習法を、$${\epsilon}$$-greedyに実施した(学習の各ステップでは、確率$${\varepsilon}$$で行動をランダムサンプリングし、確率1-$${\varepsilon}$$で$${Q}$$関数を最大にする行動を選択して$${Q}$$を更新すること)。更新回数は10,000から30,000,000エピソード(ゲームを一回プレイする単位)、$${\epsilon}$$は線型にゼロに落としていくスケジュールで、学習率$${\alpha}$$は0.1とした。対象は前回同様、篠澤広SSR「光景」の初期デッキで、初回レッスンである。また、細かいが、各ターンの報酬はスコア増分とした。カードから出るスコアそのものとしなかったのは、「よりみち研究ノート」によるスコア（これは最後2ターンに現れる)上昇を初めの方のターンでの元気蓄積がもたらす点を表現するためである。
スコア期待値を上昇させるように学習しているので、$${10^6}$$程度まではエピソード数を増やしていくとスコア期待値とクリア確率はともに上昇していく。一方、パーフェクト確率は下がり、残りライフも減少しているため、各ターンで最大のスコアが出るような戦略(前々回の言葉遣いで言うところのgreedyな戦略*)に近づいて行っていると想像される。しかし、それ以降は少し状況が変わってきており、スコアだけでなくパーフェクト確率・残りライフともわずかに上昇してきているのが伺え、取っている行動が変わってきていることを示唆している。実際、エピソード数$${10^7}$$以上のシミュレーションで得られるスコア期待値は、前々回の実験において、各ターンで最大のスコアが出るような戦略で得られた期待値(43.6)を上回っている。
*強化学習の文脈でgreedyと言うと、価値関数やQ関数を含んだ形で最大化することを意味するようで、今後は使わないことにする。
そこで、各ターンでのカードごとの使用割合のエピソード数依存性を調べた。
エピソード数$${10^6}$$においては、使用割合のターン依存性はあまり大きくなく、とにかくスコアの出るカード(アピールの基本(9)、ポーズの基本(2)、気分転換(元気比例))を引いたら使うような戦略になっているように見える。
一方エピソード数を増やしていくと使用割合にターン数依存性が出てくる。具体的には、3ターン目までにアピールの基本を使用する頻度を抑え、代わりに本気の趣味(SSR効果)・表現の基本(元気+4)をできるだけ使って元気を溜めている。そして4ターン目以降にスコアの出るカードを突っ込むという、いかにも「やる気」特性らしいプレイングを学習できている。とにかく目先の点数を追い求めるプレイから将来のために元気を蓄積するプレイに移行していく、という何とも人間っぽい振舞いが観測された。
最後に、前々回の戦略決め打ちプレイよりスコア期待値が改善した理由について考える。これは、おそらく一ターン目の挙動だろう。上記結果を見るに、一ターン目における「アピールの基本」の使用割合は一定程度ある。これは、元気上昇系のカードを一枚も引けなかった場合、高確率でアピールの基本を引くことになるが、その場合は積極的に使っていくべし、という戦略に対応する。これは戦略決め打ちプレイでは漏れていた観点であり、実プレイへのインプリケーションとも言えよう。
まとめ
学マスシステムをpythonに移植して、Q学習法を使ったお手軽学習を実装・実験してみた。前々回の結論は「4ターン元気を溜めて2ターンスコアを出すのが最適」としていたが、Q学習法によって、「序盤、元気上昇系を引けなければアピールの基本を使っていけ」という、もう少しきめ細やかな戦略が見えてきた。
今回、何となく学習らしいことができたのは、状態数がさほど多くない初回レッスンを対象としたからだろう。より複雑な問題に対応するためには、やはり何らかの近似手法が必要になる。DQN(Q関数をNNで近似)や、cross-entropy法(policy関数をNNで近似)といったディープな手法の適用は次回の課題である。
また、そのようなモデルフリーな手法に限らず、モデルベースでこの問題を捉えることも考えてみたい。モデルベース手法だと、実装したアルゴリズムが汎用性を持たないという懸念はあるが、何の問題もない。私は強化学習の研究がしたいのではなく、アイドルをプロデュースしたいのだ。