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

    【what is this】強化学習における「状態価値関数」をとりあげてきましたが、今回もその続編です。理論と手法の詳細は参考文献[1]を熟読戴くことにして、ここでは、「レンタカーショップ問題」と呼ばれる複雑な問題がこれに基づいて解けることを楽しみたいと思います。

■レンタカーショップ問題（Jack's Car Rental）
　この問題は著名なSuttonの著作[2]にありますが、簡潔に１ページに纏められており、そこから自分でプログラムを作るのは難しそうです。しかし、中井悦司著[2]では、実に丁寧にこの問題の設定と具体的な解法（Pythonプログラム付き）が解説されており、非常に有用です。このブログ記事は、それにしたがって学んだ結果を小生なりにまとめたものです。

　図１に、この問題の設定条件を示しました。２つの店Aと店Bを持つオーナーが、車貸出しによる利益を最大にするために取るべき行動（戦略）を求めます。その行動とは、営業終了後の夜間に、２つの店の間で適当な台数の車を移動させることです。両店の貸出し/返却の台数の発生確率が異なるため、翌日の営業に備えて、両店の車の台数を調整する必要があるのです。ただし、車を移動することで一定の損失（余分なガソリン代など）が発生します。

　両店の貸出し/返却の台数の発生確率は、ポアソン分布に従っており、その期待値は図１の説明文にあるように分かっているとします。図２に示すような確率分布となります。

■マルコフ決定過程における確率的な状態遷移
　この問題を解くためのベースとなる状態遷移を図３のように定めます。ある時点の状態は、店Aと店Bに現在残っている車の台数のペアとします。営業終了時（午前中は貸出しのみ、午後は返却のみ）の状態をSとします。それに対するアクションa（行動a）は、夜間に店Aから店Bへ|a|台の車を移動させることを意味します。逆向きの移動ではaの値は負値になります。その行動が終わり、さらに翌日の営業が終了した時点の状態をS'とします。つまり、状態Sにアクションaを適用した結果の状態がS'です。

　状態S'では、車の移動による損失と、貸出しによる利益が確率から計算されています。貸し出し／返却台数は乱数で決まるので、図３の遷移は、確率的な状態遷移を含むマルコフ決定過程といえます。この状態遷移をもとに、先の記事でも述べたベルマン方程式を作ることができます。ベルマン方程式を解くことは、各状態の価値（状態価値関数）を計算することになります。

　そして、状態価値関数はアクションaによって決まるわけであり、どの状態に対しても最も大きな状態価値観数値を与えるアクションを求める方法があります。その一つが、ここで使われている価値反復法と呼ばれるものです。

■価値反復法によるレンタカーショップ問題の最適解
　この方法は（詳細はここには書けませんが）、行動-状態価値関数計算とGreedyポリシーの更新と状態価値関数の更新をセットとして、全ての可能な状態（店Aと店Bに残っている台数のあらゆる組合せ）について行います。それを、すべての状態について変動がなくなるまで反復します。反復一回あたり計算量（可能なあらゆる台数についての確率計算を含む）は相当に大きくなりますが、種々の効率化手法がとられます。最終的には、比較的少ない反復回数（数十回程度）で収束解（最適解）が得られるようです。図４は、収束の途中の解（行動ポリシー）を示しています。

　そして、図５は、収束した最適解（最適行動ポリシー）の拡大図です。一つのマスは、一つの状態（店Aと店Bに残っている台数のペア）です。マスの中の数値は、店A→店Bへ|a|台の車を移動するという行動を意味します。この結果を眺めてみて、十分納得ができるように思います。

　全体としては、残っている台数が両店間で偏っている場合は、それを補正する方向になっています。ただし、両店の貸出し台数の期待値（ポアソン分布の）の違いを反映して、店Aから店Bへの移動が多くなっています。

　例えば、店Aに15台、店Bに２台残っている状態では、限度いっぱいの５台を店Bへ移動すべきとなっています。これは、店Bの方がポアソン分布の期待値が大きいことを反映しています。逆に、店Aに2台、店Bに15台残っている状態では、店Bの方が期待値は大きいものの、店Bから１台を店Aへ（少し損失は生ずるが）移動した方が全体の貸し出し数は増えるという判定となっています。

　図５の最適行動ポリシーによる状態価値関数の値を図６に示します。両店にともに車が多く残っている方が、翌日の営業での利益を大きく期待できることを示しており、これも納得できます。

■感想
　冒頭に述べた中井悦司著[1]は、全体で５章の構成、本文全276頁です。今回の話題は、そのうちに第３章（全体の約６割）までの集大成と言えます。つまり、状態遷移を表す条件付き確率が全て計算できる「環境が分かっている」場合の基本的な強化学習理論の結論であると言えましょう。

[参考文献]

[1] 中井悦司：ITエンジニアのための強化学習理論入門、技術評論社、2020年７月
[2] Richard S. Sutton and Andrew G. Barto, "Reinforcement Learning : An Introduction", second edition, The MIT Press, 2018.