スマホアプリで「強化学習」を学ぶ魅力！

【what is this】最近の日経ソフトウェア誌に、「Pythonで強化学習を学ぶ」の解説記事がありました。丁寧に書かれていて分かりやすく、提供されているPythonプログラムも完全に動かすことができました。しかし、ここで留まらずに、理解をさらに深めるため、別のプラットフォーム（Androidスマホ）とプログラミング環境（MIT App Inventor）で、独自にそれを再構築してみました。

■ 解説記事：Pythonで「強化学習」を学ぶ
　まず、図１に示すのがこの記事です。全16ページに渡って、強化学習が非常に丁寧に解説されています。前半７ページでは、簡単な例題を使って強化学習の概念（Q-Learning）と具体的な動作が説明されています。後半９ページでは、Pythonでこれを実現する方法を説いています。コードの説明だけではなく、肝となるQ-Tableの学習則（学習率や割引率を含む）の解説が分かりやすく示されています。

　そして、何よりも嬉しいことに、提供されているPythonプログラム（４つのPythonファイルで合計約970行）が小生の環境でも問題なく、完全に動いたことです。図２はそれを示しています。

　素晴らしい！分かった気になる！でも本当にそうなのか。単にトレースしただけではないのか？という思いもあります。理解を本当に深めるのであれば、自分で、この解説の仕様に沿って、プログラムを独自に再構築するのがいいでしょう！ということで、それを実際にやってみました。

■ スマホアプリとして上記強化学習プログラムを独自に作る

　実は、小生は、上記のPythonコードの中味はほとんど読んでいません。にも拘わらず、図３に示すような、同等機能のスマホアプリを作成することができました。これは、この解説自体が素晴らしかったことに他なりません。MIT App Inventorを利用して開発しました。

■ スマホアプリの強化学習での「学習（訓練）」と「評価（実行）」

　詳細はここには書けませんが、このスマホアプリによる「学習」と「評価」を簡単に示します。まず、図４の(a)と(b)は、それぞれ、学習が不十分な場合と十分な場合に、タスクを実行した様子です。

　ここでは、ロボットの行動は、「右へ前進する」か「宝石を取る」のいずれかです。ロボットが緑色の宝石の位置と一致した時に「宝石を取る」ように学習（訓練）するわけです。図４(a)は、ロボットが宝石を得ることに失敗しています。なぜなら、学習が不十分であり、今の状況（赤枠）では、

Q-Tableの[宝石を取る行動価値, 右へ前進する行動価値] 

= [-0.71757, -1.01168]

となっており、ロボットがまだ宝石の位置にないのに、より行動価値が高い（すなわち、-0.71 > -1.01）と評価された「宝石を取る」行動を行ったためです。

　これに対して、図4(b)は、学習が十分に進んでいたため、Q-Tableの中味は正当なものになっており、ロボットは今ここで「宝石を取る」のではなく、宝石へ向かうことになります。

　そして、図５に示すように、ロボットはさらに宝石に近づき（途中の一歩の図示は省略）、位置が一致したところで、

Q-Tableの[宝石を取る行動価値, 右へ前進する行動価値] 

= [5.0, -1.9]

にしたがい、最終的に自信をもって（すなわち、5.0 > -1.9）、「宝石を取る」行動が成功しています。

　動作を確認するため、十分に学習済み（Q-Tableの内容が妥当になった）後の評価実行例を以下に示します。

■ スマホアプリで「強化学習」の意義
　Pythonプログラミング、もちろん良いでしょう。でも、スマホでアプリを開発するのならば、MIT App Inventorは非常に効率良く行えます。上記解説記事では、Q-Tableの実現に、Pythonの辞書型変数やnumpy配列を使っていますが、App Inventorでも同等のことが可能です。また、Pythonのmatplotlibほど高機能ではありませんが、図３に示したとおり、App Inventorでも折線グラフ（報酬の経緯）も描けています。

　スマホで、強化学習を実行し、その状況をグラフで可視化し、学習結果としてのQ-Tableの数値を確認し、評価のためのアニメーションも実行する。それらを、ボタン操作で、掌ですべてインタラクティブに行える。この魅力は大きなものと改めて感じます！

　例えば、図３で使用したハイパーパラメータを変えて学習させたい、という場合も、図６のように直ぐにその効果（収束速度や安定度など）をグラフで確認できます。

■ MIT App Inventorプログラムの複雑度
　上に述べたとおり、Pythonで約970行とほぼ同等のプログラムをMIT App Inventorで作成しました。それがどの程度の複雑度なのかを詳しく述べることは、ここではできませんが、プログラム全体（ブロック図）をご参考までに示します。小さくで中味は見えませんがご容赦下さい。

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

【what is this】前回の「Scratchで強化学習(2)」の続編です。伊藤真著[1]にある、レベル３の例題を検討します。前回のレベル２では、開始状態から最終状態までの「エピソード」を扱いましたが、今回の例題は最終状態の無いゲームでの得点（報酬）を競うものです。予測報酬（=行動価値Q）の計算において、「割引率」を導入するのがひとつのポイントです。

■ レベル３例題：お化けの飛行訓練ゲーム
　このレベル３例題は、図１に示すように、４つのボタンのいずれかを押す毎に、報酬表にある報酬（-3から3までの整数値）が得られます。負数の場合は左へ、正数の場合は右へその絶対値を歩数として進みます。100回のボタン押下において、できるだけ多くの総報酬（右方向の遠くの位置）を得ようとするものです。

　ボタンｎを押すという行動により現在の状態が状態ｎへ推移します。例えば、現在の状態（from）が状態１の時にボタン２を押すと、次の状態（to）としての状態２へ推移します。その際、報酬表（状態１, 状態２）の値（すなわち１）を報酬として得ます。報酬表の対角要素はすべて-1としてありますので、同じボタンを連続して押した場合は、いつも-1の報酬を得ます。

　報酬表の値は、ゲーム毎に変わりますが、もちろん、それらの値はプレイヤー（人間と「強化学習」）には知らされていません。

■ 「強化学習」プレイヤーの戦略
　今回の強化学習の戦略は、基本はレベル２の場合の学習則と同じです。しかし、冒頭に述べたとおり、今回は最終状態がなく、いつまでもボタン操作が続きます。状態の推移が巡回する場合もあります。（実際には、ここでは100回で打ち切りますが。）このため、得られる報酬がどんどん増大してしまい、行動価値Q(状態、行動）を従来の学習則のままで更新しようとしても収束しない恐れがあります。

　そこで、Q(状態、行動）を更新する際に、右辺のQの値に割引率γ（0.9とか0.8程度の値）を掛けて行き、遠くの報酬を少しづつ小さくします。それによって収束が期待できます。この割引率γを変更することで、遠くで得られる報酬の見積もりを（少なめに）調整することになります。あるQ(状態、行動）は、その絶対値よりも、他の（状態、行動）と比較して価値が高いかどうかが重要なので、この割引率の導入は妥当と思われます。（割引率導入の学習則の詳細は、参考文献[1]をご覧下さい。）

■行動価値Q(状態, 行動)の計算を観察する

　上記の割引率付きの学習則によるQ(状態、行動)の計算結果を観察してみます。上に述べたとおおり、Q(状態、行動) = Q(from-状態、to-状態)とみなすことができます。報酬は、図１に示した報酬表のとおりだとします。

　ボタン操作を100回で打ち切りますが、学習則にはランダム性が含まれているため、Q(from-状態、to-状態)の値は、一意には決まらず、無数に存在します。そのうちの２例を、図２aと図２bに示します。

　図2aと図2bの棒グラフの高さはまちまちのように見えますが、両者には共通の明確な特徴があります。すなわち、以下のような巡回があります。

• 状態１では、最大Qはボタン２の場合であり、状態２へ。
• 次に、状態２では、最大Qはボタン４の場合であり、状態４へ。
• さらに、状態４では、最大Qはボタン１の場合であり、状態１へ。

　結論が出ました！学習により、次のようなボタン押下が最適だ！

ボタン１→ボタン２→ボタン４→ボタン１→ . . . 

■ 感想
　これまで、書籍[1]にあるレベル１，レベル２，レベル３の例題を実際に動かしながら、自分なりの詳細観察を行ってきました。エピソード的な場合と非エピソード的な場合の両方で、Q(状態、行動)とはどんなものかを知る上で、非常に有用と感じました。

　本書は、初心者向けに分かりやすく、との方針に基づき、著者独自のやさしい用語も用いた丁寧な説明に徹しています。しかし、第７章「まとめ」では、今後、強化学習を専門書でさらに深く学ぶ場合に備えて、それらの用語と専門用語の対応についても説明があります。これだけ親切な著書はみたことがありません！ありがとうございました。

参考資料

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

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

 【what is this】前回の「Scratchで強化学習」の続編です。伊藤真著[1]にある、レベル２の例題を検討します。前回のレベル１では、「行動、報酬」だけでしたが、今回は「状態、行動、報酬」を扱う本格的な強化学習の仕組みが入っています。そこにおいて、各状態での行動に対する予測報酬（=行動価値Q）の計算を観察します。
[->続編はこちら]

■ レベル２例題：月面でダイヤ集めゲーム
　このレベル２例題は、図１に示すように、状態１〜状態３、および最終状態を持ちます。状態１から開始して、左右のどちらかを選択して次の状態へ達します。さらにその状態からふたたび左右のどちらかを選んで最終状態に達します。そこまでを１つのエピソードと呼びます。エピソードのなかで左右を選ぶ毎に、ある確率（報酬確率）でダイヤが出ます。ダイヤが出ると報酬１を、出ないと報酬０を得ます。例えば、50回のエピソードで、できるだけダイヤをたくさん集めて報酬の総計を大きくせよ、という問題です。

　場所によって報酬確率は異なります。図１の中の赤字の数値がそれです。もちろん、それらの確率は、プレイヤーには知らされていません。最も運が良ければ、１エピソードで得られる報酬は最大で２となります。

■ 「強化学習」プレイヤーの戦略
　今回の強化学習の戦略ですが、実は、状態２か、または状態３にいる場合は、前回のレベル１での戦略と同等です。しかし、状態１（開始状態）にいる場合には、左右どちらを選択した場合も、それによって直接得られる報酬に加えて、さらにその先の行動で得られる報酬も考慮する必要があります。例えば図１の場合、状態１においては、直接の報酬については、左が0.2で右が0.3なので右側の報酬確率が高いのですが、その先で得られる報酬の合計を考えると、逆に左側を選んだ方が得になります。

　このような判断を行うために、各状態において、各行動（右選択か左選択か）に対して、行動価値、すなわちQ(状態、行動)と呼ばれる値を学習によって求めることがキーポイントになります。この学習則についての詳細は、参考文献[1]を参照して下さい。このQ(状態、行動)は、その状態においてある行動を取った場合に、最終的にどれだけの総報酬が期待できるかという、期待値を計算するものです。したがって、このQの値が正確な値に近ければ、その状態で取るべき行動の指針となります。

■Q(状態, 行動)の計算を観察する

　以下では、このQ(状態、行動)の計算がどのように進行するのかを観察します。図１の底辺部分から始めます。まず、図2aは、状態２における行動価値Qの推移（エピソードの進行にともなう）を示しています。50エピソード時点でみると、Q(状態２, 左)=0.25、Q(状態２, 右)=0.86が得られています。状態２における実際の報酬確率は、左=0.20、右=0.90ですから、Qの計算結果はかなり正解に近いと言えます。素晴らしい、使える！という気になります。

　次の図2bは、状態３に対するものですが、上記と同様に、Qの計算結果はほぼ、実際の報酬確率に近いことが分かります。

　次の図2cは、状態１に対するものです。この図では、Qの値が、報酬確率とかなり離れているように見えますが、これで良いのです。というのは、冒頭で述べたとおり、状態１でのQの計算は、直後の報酬だけでなく、その先で得られる報酬の総和の期待値になっているからです。

　結論として言えることは、以下のように行動することが最善のようです。（もちろん、ゲーム毎に報酬確率の設定が異なりますので、図１のケースにおいてです。）

　状態１→左側選択→状態２→右側選択

　ただし、もしも、エピソード10が終わった時点で判断すると、図3cからも分かるように、状態１で右側を選んでしまうでしょう。そうすると、最終的に高い総報酬報酬は得られないはずです。どのくらい（エピソード数）学習させるべきかについては、十分な注意が必要でしょう。

■ 感想
　このレベル２の例題は、Q(状態、行動)とはどんなもの？という疑問に答えてくれと思います。そして、強化学習の入り口へ案内してくれるように感じます。

　なお、上のグラフですが、Scratchのリストはテキストファイルとして簡単に取り出せますので、それをExcelに与えて描画させました。

謝辞

著者の伊藤真氏からのご指摘で、記事の途中から「エピソード」が、誤って「エポック」になっていたことに気づき、訂正しました。

参考資料

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

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日第１版

「強化学習理論入門」の最終章は深層学習だった

 【what is this】強化学習理論入門を書籍[1]で学んできましたが、その最終章（第５章）は深層学習でQ-Learningを行うものでした。ここでその技術を述べることはできませんが、最後の例題「あるけあるけゲーム」でその魅力に浸りたいと思います。

■DQN（Deep Q Network）
　これまでに、行動ポリシーπについて、状態価値関数Vπ(s)や、行動-状態価値関数qπ(s, a)を計算して、最善の行動ポリシーを求めることをやってきました。しかし、状態(s)の数が非常に大きい場合などは、全ての状態についてこれらの関数値を保存しながら利用することは困難となります。（例えば、囲碁の場合、盤面の状態の数は10の172乗というとてつもない数になると言われています。）

　そういう状況で、状態価値関数や行動-状態価値関数の近似値を、ニューラルネットワークを利用して計算するというのが、この書籍[1]の最終章のテーマです。特に、先に述べたQ-Learningをニューラルネットワークで行うのが、DQN（Deep Q Network）です。また、この実行性能をさらに高めるために、「モンテカルロ･ツリーサーチ」の基本（実行時の一歩先読み）についても取り上げられています。

■DQNによる「あるけあるけゲーム」
　ここでとりあげる「あるけあるけゲーム」の規則は、図１の右側の説明にあります。キャラクターは障害物（および自分の辿った場所）を避けて、できるだけ長く歩く、というものです。何の方策もなく歩くと、図１の結果のように、長さ（Length）5程度で短く終わる場合が多いです。自分の軌跡に戻ってしまってゲーム終了となる場合も多いです。

　これに対して、DQNで一定程度学習した後に歩かせると、図２のとおり、長さ20程度まで伸びる場合が多いです。

　このDQNでの学習結果を使って、実行時にさらに一歩先読みする方法（モンテカルロ･ツリーサーチの考え方に基づく）によれば、図３のとおり、著しく長く歩くことができます。なかなか素晴らしい結果だと思います。

■上記DQNの構成と実行時間
　このゲームを、如何にしてベルマン方程式に結びつけるか（アクション、報酬、状態の設計）、そして、さらにどのようにニューラルネットワークで学習させるのか、それを学べるのが、この書籍の第５章なのです。図４はその最終的な結論としてのDQNのネットワーク構成です。詳細を掴むにはこの書籍を読んで戴く必要がありますが、画像認識で多用されている畳み込みフィルター（conv2d層）が使われている点がポイントの一つです。これは、別々のレイヤーに置かれたキャラクタと障害物の位置関係を把握するためです。

　畳み込みフィルタ(5x5を８種)、隠れ層２層(2,048ニューロンと1,024ニューロン)などが含まれているので、辺の重みやフィルタ値など合計で約500万個のパラメータを最適化することになります。そのため、Google Colab(GPU利用)で、図２に示した学習に約30分を要しました。しかし、パラメータ数は膨大のようにみえますが、上記のゲーム場面のすべての状態数よりははるかに少ないです。

■本書[1]で学んだ感想
　基礎から始めて高度な強化学習理論が実に丁寧に説明されており、最後まで挫折せずに読めました。書籍によっては、最初は緻密な説明がなされていても、途中から杜撰な叙述になったり、急に飛ばしはじめたりする場合もあるのですが、本書は全くぶれることなく、最後まで緻密な説明で貫かれています。Pythonのコードの説明も、同様に非常に詳しく、読者にとってとてもありがたい。完全に理解したとは言えないかも知れないが、この強化学習理論の専門書（５章構成、全283ページ）を丸々一冊読み上げたということで、力がついた気がします。

　なお、著者自身によって、この書籍全体を要約解説したスライド50枚も公開[2]されており、（本書を読み終わった後に）知識を整理するのに大いに役立つと感じました。

■本書に関する小生のブログ記事

　実は、この書を読みながら、自分のメモとして、これまでに、以下の記事をこのブログに書いて来ましたので、よろしけばご参考にされたい。

[第１章] 強化学習のゴールと課題

　･小学校で習う「平均」されど「平均」（基本編）

　･小学校で習う「平均」されど「平均」（揺れる平均値）

[第２章] 環境モデルを用いた強化学習の枠組み

　･状態価値関数（ベルマン方程式に基づく）に親しむ（その１）

　･状態価値関数（ベルマン方程式に基づく）に親しむ（その２）

[第３章] 行動ポリシーの改善アルゴリズム

　･レンタカーショップ問題（強化学習での行動ポリシー最適化）

[第４章] サンプリングを用いた学習法

　･強化学習：モンテカルロ法とQ-Learning

[第５章] ニューラルネットワークによる関数近似

　･「強化学習理論入門」の最終章は深層学習だった（↑今回の記事）

[参考文献]

[1] 中井悦司：ITエンジニアのための強化学習理論入門、技術評論社、2020年７月

[2] 中井悦司：60分で学ぶ「強化学習理論入門」、2020/09/04

https://speakerdeck.com/enakai00/60fen-dexue-bu-qiang-hua-xue-xi-li-lun-ru-men?slide=50

強化学習：モンテカルロ法とQ-Learning

【what is this】強化学習に関するさらなる続編です。前回のレンタカーショップ問題とは異なり、環境モデルが分からない場合の例としての迷路問題をとりあげます。そして、その解法としての、モンテカルロ法とQ-Learningの性能を観察します。

■迷路問題とレンタカーショップ問題
　先のレンタカーショップ問題では、ある状態Sにおいて行動aを取った場合に、得られる報酬rと次の状態S'が起こる条件付き確率が分かっている（計算できる）必要がありました。しかし、現実の問題ではそれを満たさない場合も多いです。以下に述べる迷路問題（開始点から終点までの最短経路を求める）もその一つです。

■モンテカルロ法とQ-Learning
　ここでは、迷路問題に対する解法として、モンテカルロ法とQ-Learningなどを検討しています。本記事は、実際のところ、これまでと同じく、中井悦司著[1]の第４章を学んだ成果を簡単に書いたものです。

　モンテカルロ法では、上に述べたような条件付き確率に頼るのではなく、シミュレーションによって、行動aに対して得られる結果の情報にもとづいて学習を行います。この方法では、シュミレーションのエピソード（episode：開始点から終了点に達する）が完了した情報が必要です。これに対して、Q-Learningと呼ばれる方法は、エピソードの完了を待たずに、１ステップ分の新しい情報を使って学習を進められる点が特徴です。

　手法の詳細は、参考文献[1]などをお読みいただきたいのですが、ここでは結果だけを示して、さらに知識を深める手掛かりとしたいと思います。図１は、両方法による迷路の最短経路の探索結果です。開始点(S)からゴール(G)を目指して、壁(#)を避けながら、上下左右のいずれかへ進みます。両方法で辿ったパスは違っていますが、ともに最適解になっているはずです。注目すべきは、学習に要した時間です。Q-Learningの方が圧倒的な高性能を示しました。

　これらの性能をさらに明確に示しているのが、図２です。学習中にどれだけの長さのepisodeを得たかを比較しています。モンテカルロ法では、初期の段階では、非常に長いepisodeを取得しながら学習しています。つまり、長いパスをさまよってなかなかゴールへ辿り着かない状況となっています。これに対して、Q-Learningでは、開始まもなく、急激に短いパスとなり、効率的に学習が行われていること示しています。

■感想

　冒頭に述べた中井悦司著[1]では、今回の第４章（Q-Learningあたり）がクライマックスと言えましょう。しかし、書籍全体の約６割を占める第３章「環境が分かっている場合」の状態価値関数による（ベルマン方程式に基づく）統計学的な厳密解の求め方までで、それに必要な基礎は出来上がっています。つまり、第３章まで熟読すれば、第４章はスムーズに理解できるはずです。この書では、非常に丁寧な叙述が特色であることを強く感じます。また、確認のためのPythonコードについても詳しい説明がついていますので、少なくとも、Pythonの初級を終えていれば、理解にはほとんど困らないと思います。

[参考文献]

[1] 中井悦司：ITエンジニアのための強化学習理論入門、技術評論社、2020年７月

状態価値関数（ベルマン方程式に基づく）に親しむ（その１）

  【what is this】現代AI技術において、強化学習（Reinforcement Learning）は重要です。これをご存じ無い方、または、（実は私もこれに該当しますが）少しは知っているがもっと明確にしたい方のために、ベルマン方程式に基づく「状態価値関数」とは何かをビジュアルに観察して、親しみを持ちましょう。さらに先をめざす手掛かりとして。

■ベルマン方程式にもとづく状態価値関数
　詳細を把握するには、例えば中井悦司著の強化学習に関する書籍[1]を読んでいただく必要がありますが、ここでは、状態価値関数の一面に親しむことにします。実際、以下の内容は、この書籍の第２章（pp.45-100）を学んで得られる成果（結論）なのです。

■例題：２次元Grid Worldに対する状態価値関数
　強化学習の定番例題のひとつに、２次元GridWorldがあります。そのバリエーションは多様ですが、ここでは図１のような設定にします。すなわち、２次元の特定のマスからひとマスづつ進めて、右下隅のゴールをめざします。ただし、進行方向は右か下かに限定され、それぞれ1/2の確率で選択されます。どのマスから開始すれば少ない移動回数でゴールできるでしょうか。（この例ではそれは自明かも知れませんが、一般的な解決手法を得たいのです。）

　ここで「状態価値関数」とは、各マスからゴールへ到達するという観点から、そのマスの価値（有利性）を示すものと言えます。統計の言葉で言えば「期待値」です。本例では、移動する毎に報酬（-1という負値）を与えることにします。従って、報酬の合計が大きいほど、少ない回数でゴールできます。この報酬と上記の移動確率などから「ベルマン方程式」というのが導出され、その解が「状態価値関数」に相当します。

　詳細理論はおいておき、本例に対する状態価値関数をみてみます。図１(a)では、予想どおり、左上隅から右下隅方向へ向かって、「価値」が高くなっています。マスの上の数値が状態価値関数の値であり、それが大きいほど価値が高いです。グラフでは、赤が濃いほど大きな数値で、青が濃いほど小さな数値を示しています。

　一方、図１(b)では、中央に「落とし穴」を設定しました。移動先がこの穴Pとなる場合は、直ちに、左上隅へ戻るか（確率=0.9で）、右下隅ゴールへ（確率=0.1で）移動してしまいます。したがって、これは確率的に不都合な落とし穴です。実際、この落とし穴の上、左、左上方向のマスの価値は低くなっています。図１(c)は、これとは逆に好都合の落とし穴です。落とし穴の上、左のマスの価値は高くなっており、この場合も納得できる結果が得られています。

　さらに、以下の図２は、グリッドを19x19に拡大した場合です。図１に比べて、より鮮明な結果をみることができます。

■まとめ
　ここでは、マスの右と下へある確率で移動する、という特定の行動ポリシーのもとで状態価値関数をみました。別の行動ポリシー（例えば、右と下へ移動する確率が均等でなかったり、斜め方向にも移動するなど）の場合は、当然、この状態価値関数は変わります。また、どのマスから開始しても、いつもこの関数値が一番大きくなる行動ポリシーを見つけることや、大規模なworldに対する状態価値関数の効率的な計算法も大きなテーマになります。

[参考文献]

[1] 中井悦司：ITエンジニアのための強化学習理論入門、技術評論社、2020年７月