Q学習で迷路を解いたら、報酬が出口から逆向きに染みてきた。そして崖っぷちを攻めるQ学習と、遠回りするSARSA
約6分で読めます

Q学習で迷路を解いたら、報酬が出口から逆向きに染みてきた。そして崖っぷちを攻めるQ学習と、遠回りするSARSA

ε-greedyもUCB・Thompsonも、「どの腕を引くか」だけを考える状態のない世界の話だった。現実の問題はたいてい違う。今の選択が未来の状況を変え、報酬はずっと後になってから届く。

その最小の実験場が迷路だ。ゴールに着いたときだけ報酬+1。途中の分かれ道では何のヒントもない。「この曲がり角の価値」を、遠い未来の報酬からどうやって逆算するのか——強化学習の中心にあるQ学習を、numpyで実装して確かめた。

Q学習: 未来の自分からの又聞きで学ぶ

Q学習が更新するのは「状態sで行動aを取ることの価値 Q(s,a)」だ。更新式の中身は、要するに又聞きの連鎖である。

target = r + GAMMA * Q[s2].max()        # 移動先の「一番良い見込み」を割引いて
Q[s][a] += ALPHA * (target - Q[s][a])   # 今の見積もりを少し寄せる

ゴールの隣のマスは、ゴールに入った瞬間の報酬+1から直接学べる。その隣のマスは「ゴールの隣は価値が高いらしい」という又聞きから学ぶ。その繰り返しで、価値はゴールから逆向きに伝播していくはずだ。8×8の迷路(最短14手)で、それを実際に見る。

価値が出口から染みてくる

各マスの「一番良い行動」を矢印で、その価値を色で描き、エピソードが進むごとの変化をアニメーションにした。

迷路の矢印マップのアニメーション。最初は矢印が1本もないが、エピソードが進むとゴールの星の周辺から矢印が現れ始め、通路に沿ってスタート方向へじわじわ広がっていく。最終的に全通路の矢印がゴールへ向かう流れ場になる

見事に、出口の周りから染みてきた。報酬はゴールにしかないのに、又聞きの連鎖が1エピソードごとに1歩ずつ上流へ遡り、最終的には迷路全体が「ゴールへ流れる場」になる。学習曲線で見ると、初回は178ステップ迷子だったのが、400エピソード後には23ステップ(最短14手+探索の寄り道)まで縮んだ。

エピソードごとのゴール到達ステップ数。図内注釈「最初は178ステップ迷子」「終盤は最短21ステップ」。急速に下がって安定する

つまずき: エージェントは北の壁に頭を打ち続けていた

正直に書くと、最初の実装は一度もゴールに辿り着けなかった(400エピソード全部が500ステップ上限で強制終了)。原因はアルゴリズムではなく、np.argmaxの仕様だった。学習初期はQ値が全行動0で同点なのだが、argmaxは同点のとき常に先頭(この実装では「上」)を返す。ε=0.1なので、エージェントは90%の確率で律儀に「上」を選び続け——スタート地点の北の壁に、延々と頭を打ち付けていた。

同点の行動をランダムに選ぶよう1行直すと、あっさり学習が始まった。面白いのは、後述の崖歩き(1歩ごとに-1の報酬がある)では同じバグ入りコードでも学習できていたことだ。罰があると同点が即座に崩れて動き出せる。「全行動が0点=完全な無知」の状態では、タイブレークひとつが探索のすべてを支配する——強化学習の実装で新人が必ず踏む地雷を、私もしっかり踏んだ。

崖歩き: 同じ目的、違う性格

仕上げは古典の「崖歩き」問題。スタートとゴールの間に崖があり、落ちると-100。1歩ごとに-1なので、崖っぷちを直進するのが最短だが、危険と隣り合わせだ。ここでQ学習と、兄弟分のSARSA(更新式が1箇所だけ違う)を競わせた。

# Q学習: 移動先で「最善の行動を取る前提」で価値を見積もる (楽観)
target = r + GAMMA * Q[s2].max()
# SARSA: 移動先で「実際に取った行動」で見積もる (現実)
target = r + GAMMA * Q[s2][a2]

左: 学習後のルート比較。Q学習(赤)は崖のすぐ上を直進する11歩の最短路、SARSA(青)は崖から離れた上の段を通る15歩の遠回り。図内注釈つき。右: 学習中の1エピソード合計報酬。SARSAは-20前後で安定するが、Q学習は-40〜-80を上下し続ける

  • Q学習は崖っぷちの最短路(11歩)を学んだ。ただし学習中の成績は悪い(終盤100エピソード平均-50.2)。ε-greedyの探索でたまに踏み外し、崖に落ち続けながら最短路を信じている
  • SARSAは安全な遠回り(15歩)を学んだ。学習中の成績は良い(平均-19.9)。「自分はときどきランダムに動いてしまう」という現実を織り込んで、崖から距離を取る

更新式のたった1箇所——「最善を取るつもりの自分」で見積もるか、「実際にやらかす自分」で見積もるか——が、楽観的な最短主義と現実的な安全主義という性格の違いになって現れる。

手を動かして意外だったこと

矢印マップの伝播は、教科書の図で知っていたのに、自分の実装で染みてくるのを見ると別物の説得力があった。報酬という情報は、経験の回数だけ1歩ずつしか遡れない。ゴールから遠い場所の判断ほど、正しい価値が届くのに時間がかかる——「成果から遠い部署ほど、正しい評価が届くのが遅い」という組織の話に、そのまま聞こえてしまう。

そして崖歩きのQ学習とSARSAの対比は、「どちらが優秀か」の話ではなかった。Q学習が学ぶのは「理想的に動けた場合の最適戦略」、SARSAが学ぶのは「ミスをする自分にとっての最適戦略」。本番でεを0にできる(もう探索しない)ならQ学習の最短路が正しいし、本番でも手が滑る環境ならSARSAの遠回りが正しい。自分の未来のミスを計画に織り込むかどうかは、アルゴリズムの優劣ではなく、世界観の選択なのだった。

まとめ

  • Q学習をnumpyで実装し、8×8迷路(最短14手)を学習。初回178ステップ→400エピソード後23ステップ。価値(矢印マップ)がゴールから逆向きに伝播していく様子をアニメーションで確認した
  • 実装の罠: Q値が全て同点の初期状態でnp.argmaxが常に「上」を返し、エージェントが北の壁に頭を打ち続けて一度もゴールできなかった。同点のランダムタイブレークで解決——罰(負の報酬)がある環境ではこのバグが隠れる、という発見つき
  • 崖歩きでQ学習とSARSAを比較: Q学習は崖っぷちの最短路11歩(学習中の平均報酬-50.2)、SARSAは安全な遠回り15歩(-19.9)
  • 差は更新式の1箇所だけ——「最善を取る前提」(Q学習)か「実際に取る行動」(SARSA)か。楽観の最短主義と、自分のミスを織り込む安全主義という性格の違いになる

関連記事