モチベーション
半年ほど前、「強化学習」に興味を持ち勉強しようとして検索していたが、やはり数学や数式がたくさん出てくる。機械学習の分野では当然必要なスキルであることは理解していても、苦手なものはやっぱり苦手なので読む気にならない。(というかまともに読めない)
逆に数学が無い説明を見つけたとしても、説明がふわっとしていて実装はおろか実際どういう処理が行われているかすらイメージできない状況だった。
そんな中で『強化学習(第2版)』を見つけて読んでみた。必要なところでは数学が出てくるが他の本と比較すると控えめだし、その数学があるページでさえ例を交えて丁寧に説明されていて置いてけぼりにならずに済んだ。
また、難しくて他の部分の理解に必要じゃない章には * マークが付けられており飛ばして読むことで、ある程度要領よく読むことができたと思う(ちゃんと理解できたかはさておき)。結構厚めの本ではあるが強化学習の理論を深めに勉強したいが数学は苦手!という人にはお勧めしたい。
また、先に読んでおいたことで数学アレルギーが軽減されたかもしれない『数学ビギナーズマニュアル』もついでに共有しておく(薄いのでサクッと読めた)。
自分の勉強を兼ねて、数学や数式をなるべく使わずに半年前の俺に話すならこんな感じかな~と強化学習をイメージできるように頑張って説明してみようと思う。
強化学習の何が嬉しいのか
機械学習で特に有名なのは深層学習(ディープラーニング)だと思うが、これは機械学習のジャンルとしては教師あり学習に分類される。
教師あり学習は「入力値」と「期待する出力値」のサンプルを大量に与え、現在の出力と期待する出力の誤差を減らすように内部パラメータを調整することを繰り返す。うまく学習ができると入力に対して期待した出力を返す関数を作ることができるし、学習に使っていない入力を与えた時にある程度期待した出力が出てくるようなものになる。
色々な手法はあるものの教師あり学習は、入力に対して期待する出力、すなわち答えを定義できなければいけない。
例えば犬か猫の写真を入力すると犬か猫を判定する判定機を作る場合では、犬の写真に対して「犬」という答えを、猫の写真には「猫」という答えを一意に決めることができる。当然だけど。
教師あり学習は人間でいえば英単語を覚えるために英単語(入力)を見て日本語訳(期待する出力)を言えるようになんども英単語帳を反復するようなイメージに近いかもしれない。
しかし問題によってはこのような明確な答えを与えることができない(もしくは非常に難しい)特性のものがある。
制御の問題はわかりやすいと思う。たとえばスーパーマリオブラザーズの画面を見ながら敵を避けたり落下しないようにマリオを適切に操作してゴールまで移動させることは制御だと考えることができる。
これを教師あり学習で行うのはかなり難しいと思う。前述した犬猫判定機の例と違って、入力と出力を考えようとしても何だか楽そうじゃない。「Aの状態のときはジャンプする」「Bの状態のときは右に走る」「Cの状態のときは左に向かってジャンプする」....という全パターンを網羅すればうまくいくかもしれない。
しかし、作業を進めているとマリオの位置だけじゃなく、クリボーやノコノコの位置、ブロックの状態、残り時間....など様々な状況を考慮しないといけないことに気づくはずだ。状態の数が多すぎて全てが嫌になってきた。
当然ながら英単語帳を反復する様にスーパーマリオブラザーズをプレイする人なんていない(もしいたらごめんなさい)。人間が初めてプレイする際は色々と操作して何度も死にながら、どう攻略すればいいか試行錯誤を繰り返すことで徐々にゴールへ近づけるようになっていく。
強化学習ではこれに近い「試行錯誤」のアプローチを取ることができる。この点で教師あり学習と違って制御問題では有利になる。
強化学習の説明でよく見るすごく抽象的な図を描いてみた。またこの意味わからない図が出たよ.....と読む気が失せて戻るボタンにカーソルを動かすのはもう少しだけ待ってほしい。
教科書的な説明だが、強化学習ではエージェントが以下のような処理を繰り返し行い、最終的に得られる報酬を最大化するように試行錯誤を繰り返す。このアプローチによって適切な報酬を与えてあげることにより徐々にゴールへ近づくことができるようになる。
- environment(ゲーム)から state(現在の状態、すなわちゲーム画面)を受け取る
- agent(マリオを操作するプログラム)は state を元に action(移動する方向やジャンプ・ダッシュするかどうかなど)を選択する
- action を実行する
- environment から次の state と reward(報酬、例えば前に進めば +1、死んだら -100 みたいな値)を受け取る
- reward を使い agent の判断を改善する
- 2に戻り繰り返す
それは分かったから、どうやって判断したり学習するの?
この図を見た時にそう思った。あの図だけでは強化学習を具体的にイメージすることができない。ここからは強化学習の仕組みについてもう少し具体的に(そして単純化のために詳細を省いたり、いろいろと誤魔化しながら)説明してみようと思う。
マルコフ決定過程(MDP)
強化学習では環境(environment)をマルコフ決定過程(MDP)という確率モデルとして扱う。
以下の図では S0, S1, S2 の状態(state)があり、a0, a1 の行動(action)を選択すると、予め決められた確率によって次の状態に推移する。またその際に報酬(reward、黄色い矢印)を受け取ることがある。
たとえば、最初は S0 の状態にあるとする。そこから a1 の行動を選択すると S2 に 100% の確率で遷移する。S2 の状態で a1 の行動を選択すると 40%の確率で元の S2 に戻り、30%の確率で S1 に遷移し、30% の確率で報酬 -1 を得て S0 に遷移する....という、そんな感じのモデル。
また、このモデルはマルコフ性を仮定している。マルコフ性とは、行動後の状態遷移確率や報酬は、元の状態と行動にのみ依存するような性質。つまり、過去にどのようなことが起きようが全く関係なく、現在の状態と選択した行動が同じであれば状態遷移の確率や報酬の期待値は同じだとする。1
この簡単な例では報酬の最大化は簡単だろう。以下のような組み合わせの行動をとり続けることで長期的に報酬を多く得ることができるようになる。これは言い換えると、「将来的に得られる報酬の期待値」が最大になる状態と行動の組み合わせである。
状態 | 最適な行動 |
---|---|
S0 | a1 |
S1 | a0 |
S2 | a1 |
このように、報酬の期待値が最大になる状態と行動の組み合わせを「最適方策」と呼ぶ。強化学習はこれを探すことが目的になる。
もちろんこんなに単純な例は珍しい。そもそも現在の状態から行動を選択した際にある状態に遷移する確率(ダイナミクスと呼ぶ)は事前に分からない場合が多いし2、状態数や取れる行動の数ももっと多い。さらに、ダイナミクスや報酬が時間とともに変化する場合もある。
テーブル形式での強化学習
行動価値関数
報酬の期待値が高い行動ができるようにするためには、まず行動を評価できるようにする必要がある。そのために「行動価値関数」を定義する。
行動価値関数とは状態と行動を渡すとその推定価値を返す関数で Q(s, a)
と表したりする。以下の画像でいうと Q(S1, a0)
と書くことで S1 の状態から行動 a0 をしたとき、将来的に得られる報酬の期待値が返るというもの。
完璧な行動価値関数が作れれば、現在の状態で一番価値が高い行動を選び続けることで最適な行動がとれるようになる。(もちろんここが難しい)
関数といっても一番単純な手法では、状態*行動の組み合わせごとに数値を保存しておくだけの形式が考えられる(テーブル形式)。3
当然ながら最初は行動価値が分からないので、とりあえず 0で初期化しておくとする。この行動価値関数をどのように改善していくのかを次の章で説明する。
行動価値関数の改善
パブロフの犬の実験がある。メトロノームの音を犬に聞かせた後エサを与えると唾液を出す。この手順を繰り返すことによって犬はメトロノームの音を聞くだけで唾液を出すようになる。
更にそのあと(エサは一切見せずに)黒い四角形の画像を見せる -> メトロノームの音を聞かせることを繰り返すと「黒い四角形の画像」を見ただけで唾液を出すようになるらしい。4
犬が唾液を出すのはエサを食べることを期待するからだが、本来関係のないメトロノームの音とエサを結び付けることでメトロノームの音を聞いただけでエサを期待できると学習した。また、この条件は経験で得たもので犬はメトロノームの音自体を求めてる訳ではない。にもかかわらず、メトロノームの音に関連付けされた黒い四角形の画像を、エサの期待に結びつけるように学習した。
恣意的な実験なので奇妙な結果になってしまっているが、自然状況下では例えばシマウマがライオンに捕食されないようにするために「捕食される事」と直接関係ないライオンの見た目、足跡や鳴き声、その他の雰囲気などを怖がって避けるようにすることで生存率は上がることは想像できる。
強化学習でも行動価値関数の更新を似たように行う。行動価値関数が初期値だと最適な行動が分からないためエージェントは最初はランダムに動く。そして正の報酬が得られた際には「その前の状態でとった行動」というのは高い価値(逆に報酬が負の場合は低い価値)と更新する。
例えばエージェントがランダムに行動を繰り返した結果、以下の図の様に S2 で行動 a0 をした際に正の報酬が発生したとする(既にとった行動を表しているためダイナミクスの考慮はしていない点に注意。S2 で行動 a0 を選択したからと言って必ず S3 に遷移できるとは限らない)。
すると、Q(S2, a0)
は報酬を期待できるので価値が高くなり、S2 状態に遷移する行動の価値 Q(S1, a1)
も少し高くなる。こういった更新を繰り返すことによりダイナミクスが未知だったとしても徐々に正の報酬が得やすい行動価値がより高く、報酬が得にくかったり負の報酬が得やすい行動価値がより低く更新されていく。
ちなみに、得られた報酬をどれだけ後ろに伝播させるかは手法によっては調整できたりする。この後説明する手法は1回のみの最も単純な方法になる。5
ε-greedy方策
行動は完全にランダムだったとしても評価の価値更新はできる。しかし目的は正しく行動価値を評価することではなく最適方策を探すことなので、明らかに価値が低いとわかっている行動も高い行動も平等に選択してしまうと学習効率が悪くなる。逆に、価値の推定値が高い行動ばかりをとっていると「現時点では低いと推定されているものの、実は価値が高い行動」が学習できないため、局所的な最適解からいつまでたっても抜け出せない。
この中間の行動の方策として ε-greedy方策 がある。これは確率 ε でランダムに行動を取り、(1 - ε) で「現時点で最も価値が高いと推定されている行動」をとるといったもの。ε は 0.1 とか小さい確率が使われることが多い。
学習が終わった後は、推定価値が高い行動だけをとる greedy 方策に切り替えればいい。
単純な問題を実際にとかせてみる
Q学習(TD法)のサンプルコード
非常に単純な問題を想定してみる。
このゲームでは S0 ~ S3 のマスがあり、行動は Right, Left の2つが選択できる。ゴール地点である S3 のマスにいる場合は Right, Left のどちらを選択したとしても報酬 +1 を得て S0 のマスに飛ばされる...といったもの。この程度の問題であればテーブル方式でも余裕で実装できる。
ちなみに、このゲームも前述したマルコフ決定過程(MDP)のモデル図として表すことができる。(行動時の確率的な遷移は存在しないので、遷移確率はすべて 1)
モデル図を見る
このコードでは以下のような処理を繰り返すことで、行動価値関数を改善する。
- エージェントが ε-greedy 方策を元に行動を選択する
- 行動によって得られる報酬と遷移先の状態を受け取る
- 報酬を用いてテーブルに保存されている行動価値を改善する
そしてこれを実際に TypeScript で実装したコードは以下にある。(TypeScript Playground ですぐ実行できる)
このプログラムでは実行すると、試行錯誤を行いながら報酬を 10回手に入れるまで動き続ける。初めのうちはランダムに行動を選択するためなかなか S3までたどり着けない。12回行動してやっと報酬が得られるようなケースも見られた。
学習を進めていくと、最後の方では最適方策(Right を選択し続ける)を学習でき、最小の4回の行動で報酬が得られるようになった。
処理内容は前述のステップの通りであるが、「3. 報酬を用いてテーブルに保存されている行動価値を改善する」部分が少し理解しにくいので説明する。
行動価値の更新を行っているのは updateQ(s, a, r, nextS)
関数である。Q(s, a)
関数は state と action を渡すとその現在の推定価値をテーブルから取得する関数。maxQ(s)
は state を渡すととれるすべての行動の中で一番高い推定価値を返す関数である。
function Q(s: State, a: Action): number { const actionValue = qTable.get(getKey(s, a)); if (actionValue === undefined) { return 0; } return actionValue; } function updateQ(s: State, a: Action, r: number, nextS: State): void { const step = 0.1; // 学習率 const discount = 0.9; // 割引率 const newQ = Q(s, a) + step * (r + discount * maxQ(nextS) - Q(s, a)); qTable.set(getKey(s, a), newQ); } function maxQ(s: State): number { const rightActionValue = Q(s, "Right"); const leftActionValue = Q(s, "Left"); return Math.max(rightActionValue, leftActionValue); }
updateQ 関数の newQ = Q(s, a) + step * (r + discount * maxQ(nextS) - Q(s, a));
は3ステップに分解できる。書き込んだコメントの様に Q(s, a)
を target に近づけるように更新を行っている。
// 報酬 + 次の状態で greedy に行動を選択した際得られる報酬の推定値を減衰させたもの const target = r + discount * maxQ(nextS); // target と現在の行動価値関数 Q(s, a) との誤差 const error = target - Q(s, a); // Q(s, a) を step 分だけ target に近づけるように更新する const newQ = Q(s, a) + step * error;
ちなみに、step は学習率で一度にどれくらい更新を行うかを決めるための 0 < step <= 1
のパラメーター。大きくしすぎると発散してしまいうまく学習できないし、小さくしすぎると収束に時間がかかるようになるような値である。
discount は割引率でどれくらい将来の報酬の価値を重視するかを決めるための、0 <= discount <= 1
のパラメーター。 0 に設定すると報酬 r だけが残るため近視眼的なエージェントになるし、1 に近づけていくほど長期的な視点で学習できるようになる。
エピソードタスクと連続タスク
チェスの様に終わりがあるようなタスクを「エピソード的タスク」といい、1回目のエピソードと2回目のエピソードは完全に独立している。逆に、不安定な道を歩き続けるロボットの様に明確な区切りが無く延々と学習させられるようなタスクを「連続タスク」と呼ぶ。
割引率を1に設定した場合、エピソードタスクの場合は問題ないが、連続タスクでは報酬がどんどん大きくなってしまってパラメーターがオーバーフローしてしまう可能性がある。状況にもよるが、一般的にそれを避ける意味で 1未満にしておいた方が良い。
テーブル形式の限界
先ほどのサンプルコードでは行動価値関数 Q(s, a) をテーブル形式で実装したが、テーブル形式には以下の欠点がある。
- 状態*行動の組み合わせが非常に小さい場合でのみ使用できる(強化学習を使いたい現実の問題のほとんどではメモリが溢れる)
- 状態行動価値を丸覚えしているため、学習時に現れる頻度が低かった状況については上手く判断できない(般化性能が無い)
こういった欠点を解消するために、行動価値関数には深層学習(ディープラーニング)をはじめとした教師あり学習が使われる。行動価値関数を関数近似してしまうというアイデアだ。
2015年に、囲碁で人間のプロを破ったことで話題になった AlphaGo には DQN (Deep Q-Network)という Q学習 & 深層学習 のアプローチが使われていた。
We trained this model using Reinforcement Learning from Human Feedback (RLHF), Introducing ChatGPT
2022年に発表された、非常に高性能なチャットボット ChatGPT では、GPT-3 や GPT-4 という言語モデルの精度を改善するために RLHF という強化学習の手法を用いているらしい。
応用の紹介に留め、踏み込むことは避けるが、実際に深層学習を行動価値関数として扱う場合には特有の問題があったりして、一筋縄ではいかないよう。
最後に
本記事では説明しやすい手法だったので Q学習(TD法)と ε-greedy方策を取り上げたが、学習時の方策や行動価値関数の更新方法のバリエーションはいくつか存在する6。また、Q学習(TD法)7では行動価値関数を学習することで最適方策を求めたが、方策を直接学習するような手法も存在しそれ特有のメリットがある。
状態をどう与えるかや報酬の与え方をいい感じに設定してあげないとうまく学習できないので、取り組むタスクごとに試行錯誤することも必要になる。
また、数学よりの説明を求めている方は以下の本が合うかもしれない(軽くページをめくっただけでくしゃみが止まらなくくなった)
- 強化学習の基本的なアルゴリズムではマルコフ性を仮定するので、仮定から大きく外れるタスクには弱かったりする↩
- ちなみに環境のダイナミクスが分かっている状態であればベルマン方程式を解くことで期待値を計算できるらしいが、めちゃくちゃ複雑な計算になり現実的じゃないので実際は動的計画法での近似を求める。↩
- 勘のいい方は察したかもしれないが、状態数や行動数が多くなると組み合わせ爆発を起こすので非常に単純な問題にしか使えない。詳しくは「テーブル形式の限界」で軽く説明する。↩
- この特性は古典条件付けの高次条件付けと呼ばれるらしい↩
- 『強化学習(第2版)』では伝播回数を一般化した TD(λ)法などが紹介されていた。本記事で紹介している手法はこれのもっとも単純な TD(0) といえるらしい。↩
- 例えばSARSA法というものがあり、行動価値関数の更新方法がQ学習と少し異なる。実装してみたものの結局使使わなかったコードがあるので共有しておく。blog-assets/reinforcement_learning/td-sarsa.ts at main · buri83/blog-assets · GitHub↩
- 急に出てきて、一切説明がないけれど結局 Q学習やTD法って何?と気になって、そのままここまで読み進めてしまった結果、睡眠の質が悪くなる運命が確定した方がいるかもしれない(可哀そうに)。しかし、ここはすでに「最後に」の章なのである。わざわざ大きな文字で「最後に」と題している以上はダラダラと説明するのも避けたいところだが、ここから用語の説明を始めてしまうと話が膨らんでしまいそうな予感がする。もしかすると、この人生でしてきた予感という予感の中でも相当大きなものかもしれない。そうじゃないかというほどに、ひしひし予感を感じてる。当然ながら、誠に当然のことながら説明したいのは山々なのだが、断念せざるを得ないことは非常に悔やまれる。あーあ残念だ、本当に。そしてここまで長々と文章を書き連ねてきたからかヘトヘトで、これ以上章を増やすのも、他の章との整合性を直すのも、新しい説明を考えたりすることも面倒くさくなってきた。ウダウダと書いてはいるが要するに、兎にも角にも疲れたのだ、そろそろ筆をおきたいな...。そういうことで、寝れないあなたは今流行りの ChatGPT にでも尋ねてみてほしい。グッナイ!!!!!!!!!!↩