Scratchプログラミングで強化学習の基礎(1)

【what is this】子供向けと言われるScratchですが、伊藤真著[1]にはゲームの形で、強化学習（３段階に分けたQ学習）が、実に丁寧に説明されています。大人にも有用と思われます。本記事では、このうちの最初の例題（レベル１）を対象として、（小生独自の改造も加えて）強化学習を詳しく観察します。
[->続編はこちら]

■ レベル１例題：砂漠でダイヤ集めゲーム
　レベル１例題は、図１(a)に示す左右の穴を掘って、ダイヤをたくさん集めよ、というものです。左右の穴はダイヤが出る確率が異なりますが、その確率はプレーヤーには知らされていません。ダイヤが出れば報酬１、出なければ報酬０が与えられます。プレーヤーは「人間」と「強化学習」です。限定された試行回数において、総報酬（=得点）をできるだけ多くするには、どのような戦略で左右の穴を選択すべきでしょうか？

　図１(a)はオリジナルのステージデザインですが、(b)は、後述する「予測報酬確率」の推移をグラフ化するための改造版です。

■ 「人間」プレイヤーの戦略
　人間がプレイヤーの場合、色々な戦略が考えられます。全くデタラメに左右を選ぶのではなく、ここでは、ひとつの方法として、以下の戦略をとります。例えば、試行回数100回の場合、

1. 最初の25回は左を選択し続けて、その穴のダイヤ出現確率を予測。
2. 次の25回は右を選択し続けて、その穴のダイヤ出現確率を予測。
3. 残りの50回は、上記の確率の高い方の穴を選択し続ける。

　この方法は、前半の50回を「探索」に、後半の50回を「活用」に費やすものであり、これでもある程度高い得点が得られるでしょう。

■ 「強化学習」プレイヤーの戦略
　この強化学習の戦略は、試行の度に、左右のダイヤの出る確率（予測報酬確率）を更新し、その時点で確率が高い方の穴を選択します。ただし、ある小さな確率（乱雑度ε）で、それには従わずにデタラメに右が左を選びます。図２がその概要です。この書籍では明記されていませんが、このような枠組みは、一般にε-greedyポリシーと呼ばれるものです。

　上記の左右の予測報酬確率は、図3に示す学習則で更新されます。左右どちらかの穴が選択される毎に、その穴に対する予測報酬確率が更新されます。小さな値の学習率を使って、予測報酬が実際の報酬に徐々に接近することが期待されます。なお、１回当たりの報酬は、図２に示すとおり、１か０です。

■ 報酬確率が途中で変更になった場合、どちらが有利？
　両方の戦略を実際に数回（いずれも試行回数100回で）試してみました。「強化学習」の方がやや優勢のようでしたが、それほどの差はないようです。「人間」の戦略でも、両方の穴の報酬確率は、25回の試行である程度正確に掴めるからでしょう。ただし、ここには、前提条件があります。つまり、両方の穴の報酬確率はもちろん知らされていないのですが、その報酬確率は途中で変わらないという前提です。

　もしも、報酬確率が途中で変わるとどうなるでしょうか。前半で左右の穴の報酬確率を予測、後半でそれを活用、という「人間」の戦略では、後半で報酬確率が大きく変動した場合、悲惨な結果となるでしょう。

■報酬確率が途中で変動しても対応できる「強化学習」
　このような、報酬確率が変動する場合でも、「強化学習」の方は対応できます。以下で、それを実際に確認します。図4(a)は、前半50回までの左右両穴の予測報酬確率の推移をグラフにしています。（実際の）報酬確率は左が0.7、右が0.4であり、予測報酬確率は、その付近を振動しています。そして、実際、左右の選択は、左が41回、右が9回であり、順当に進行しています。

　さて、ここで（51回目で）、左右の報酬確率が大きく変動しました。つまり、左右の報酬確率が入れ替わってしまいました。でもご心配なく。間もなく、予測報酬確率も、それに追随して減少（左の穴の場合）、増大（右の穴の場合）していることが分かります。右側の予測報酬確率の上昇により、右側の選択回数が上図の９回から３８回まで増大しています。

　結論として、100回の試行において、上記の報酬確率（0.4〜0.7）のもとで、６８点という良い得点が得られました。なるほど強化学習！という感じです。

（ただし、「途中で報酬確率が変わる」と言っても、変わった後の新しい報酬確率が一定期間持続するという前提においてです。全くデタラメに報酬確率が変化するのであれば、どんな戦略も有効とならないでしょう。）

■ 補足
　今回の例は、冒頭に述べたように、レベル１という初歩段階のものです。一般的な「強化学習」は、「状態、行動、報酬」を基に行われますが、今回は「状態」は扱わないものとなっています。レベル２，レベル３になると、「状態」も使った本格的な強化学習になって行きます。

■ 感想
　普段、PythonやJavaでプログラミングしている人にとっては、Scratchは別世界です。まどろっこしく感じる場面も多いです。しかし、本例のように、何かをもっと詳しく調査したい、その結果も素早くビジュアルにしたい、そういう場合はとても便利な開発環境だと感じました。そして、あまりプログラミングに馴れていない人に、説得力をもって説明する場合の助けになるとも思いました。

参考資料

[1] 伊藤　真：ScratchでAIを学ぼう- ゲームプログラミングで強化学習を体験、日経BP、2020年8月11日第１版

今いちど強化学習のCartPole（倒立振子）問題

【what is this】強化学習の定番例題のひとつに、CartPole（倒立振子）があります。多くの場合、ポールの初期状態をほぼ真上（北向き）にしていますが、完全に倒れた真下（南向き）にした場合でも、うまく学習できて、長時間ポールを立て続けることができます。

■ CartPole（倒立振子）問題 - 制御工学と強化学習
　この問題は、よく知られているように、台車にポールを立てた状態を長く維持するための制御です。図１にあるように、当初は制御工学の問題(1)だったと思います。それが、強化学習で著名なR. S. Suttonの書籍(2)で、Q-Learning（=強化学習の手法のひとつ）の例題としてとり上げられました。その後さらに、強化学習の実行とテスト（シュミレーションによる）のための例題として、MATLAB(3)や、OpenAI(4)で扱われています。

図１ CartPole（倒立振子）問題 - 制御工学と強化学習

■ Q-LearningでCartPoleを解く

　ここでは、OpenAIのGym（その中の"CartPole-V0"という環境）を使います。全体の状態は、台車の位置と速度、ポールの角度と角速度の４項で表現されます。これらは連続量なので、Q-Learningで扱うには、これらを離散化（連続量を６区分するなど）します。台車の制御は、単位時間毎に一定の力で右へ押すか、左へ押すかだけです。その動作に反応したポールの新しい状態は、Gymが運動方程式の計算結果として返してくれます。ただし、各時点でその状態がどの程度好ましいのかを示す点数付け（報酬付与）は、自分で設計します。

　ここでの問題は、どういう状態の時、台車をどちらに動かすのが良いかを学習させることです。それをQ-Learningという手法で実行します。OpenAIのGymを利用したのは、上記の力学計算をやってくれるとともに、台車とポールのアニメーションも提供されるからです。ビジュアライゼーションはいつも重要です！

■ Q-Learningによる学習結果をみる

　技術的詳細は置いておき、結果を楽しみましょう。以下の図は、まだ学習があまり進んでいない段階です。すぐに倒れてしまうことが多いです。アニメーションの途中で、ガクッとなっているのは、そこでポールが倒れることを意味しています。真北から左右に12度以上開いた角度になった時がそれに該当します。倒れるとその試行（エピソード）が終了し、直ちに、次の新しい試行に入っています。

学習初期の状態（開始時、ポールの向きはほぼ真上）

　一方、次の図は、学習がかなり進んだ段階です。上図に比べると、だいぶ長い間、ポールが倒れずに台車を制御できていることが分かります。

学習終盤の状態（開始時、ポールの向きはほぼ真上）

　さて、上記では、新しい試行はいつもポールをほぼ垂直に（僅かに左右に傾けて）立てた状態から開始しました。それでは、今度は、ポールが完全に倒れた状態、すなわち、真南を指している場合はどうでしょうか。その状態から、ポールを真北に向けてそれを維持するのはかなり大変そうに思います。

　これを、深層学習（DQN : Deep Q Network）を用いてQ-Learningでやった報告が参考資料[1]にありました。それを追試した結果が以下の図です。

学習終盤の状態（開始時、ポールの向きは真下）

　うまく行っています！ポールが、真下から持ち上がっています。このDQNでは、Chainer（Tensorflowでも良いのですが）を使っています。中間層のノード数は150で、この状態になるまでに約1,000エピソードを学習させました。実行時間は、通常のPCで10分程度でした。

　このようなアニメーションで興味を抱き、強化学習の詳細に入って行くきっかけになればよいですね。

参考資料

[1] 制御工学の基礎あれこれ
http://arduinopid.web.fc2.com/index.html