強化学習
強化学習とは
機械学習には、教師あり学習、教師なし学習のほかに、強化学習（Reinforcement Learning）とよばれる手法がある
ロボットの制御、ゲーム、レコメンドなど、幅広い分野で応用
2016年のAlphaGo（囲碁AI）で脚光を浴びる
強化学習のしくみ
強化学習の学習主体をエージェント（agent）とよび、このエージェントが環境（environment）と相互作用して得られる報酬（reward）の累積和である収益（return）を最大化する方策（policy）を見つける
どんな問題に使われるか
何をやればいいか（what）はわかっているが、どうやったらいいか（how）はわからない、というタスクに対して適用できる
例：「ロボットをある場所まで歩かせる」というタスク
ロボットの各関節の角度を制御しながら、転ばないように目的の場所へ移動させる、という「何をやるか（what）」は明確だが、その具体的な実行方法（how）はわからない
強化学習の実装例、動画いっぱいある
ゲームの例がとても多いが、この理由は後述
強化学習で用いられる概念
例として「迷路の攻略」というタスクを考える
https://gyazo.com/fb475dbe407e7e9e6ac6535921f70a2a
エージェントをゴールにたどりつかせるタスク
強化学習では、行動、状態、報酬、方策の4つの概念を考える
行動（action）
エージェントが環境に働きかけること
https://gyazo.com/3b5e906bf210b08c8fac0c9a2039204a
この例では、上下左右の4方向のうちいずれかに移動するという行動から1つを選択することになる
状態（state）
エージェントが環境において置かれた状態のこと
https://gyazo.com/36e434c6eb6393d44344a2ab85876cc1
この例では、エージェントの「位置」が状態となる（S1～S9の9通りの状態）
行動によって状態は変化する
報酬（reward）
ある状態におけるある行動に応じて得られる、「良さ」を表わす値
https://gyazo.com/713a90675b5f59b59a31245506221ef3
この例では、「ゴールに到達すれば+1」、「罠に到達すれば-1」、のような報酬の設定が考えられる
方策（policy）
エージェントがどのように行動するのかを定めたルールのこと
https://gyazo.com/94b4f84f571bbd1e8d9d12ba314d107e
ある状態に対して、取れる行動の選択肢からどの行動を取るべきか、ということを表わすルール
強化学習の内部的には、各状態に対して行動を選択する確率分布として与えられる
強化学習の目的
強化学習はつまるところ、良い方策を見つけ出すことが目的
方策に従って行動してみて、その結果に対して「良かった、悪かった」というフィードバックを報酬の形で与える
この繰り返しにより、報酬が高くなるような行動を取るように、方策（確率分布）が学習される
ただし、行動の直後の報酬だけでなく、何ステップも先の報酬も加味する必要がある場合も多く（遅延報酬という）、これが強化学習の難しさのひとつでもある
たとえば囲碁のようなゲームを考えるとすぐわかるように、ある時点の行動が「良い」かどうかをすぐに判定できることはなかなかない
「ある状態$ sにおいて、方策$ \pi(a|s)にしたがって行動選択と状態遷移を繰り返した場合の、収益（将来にわたっての報酬を総合したもの）の期待値」を価値関数とよび、これを$ v_\pi (s)とすると、「すべての状態$ sについて$ v_\pi (s)を最大化する方策$ \piを見つけること」が強化学習の目的となる
強化学習のアルゴリズム
強化学習にもさまざまなアルゴリズムがある
動的計画法（方策反復法、価値反復法）、TD学習、Q学習、SARSAなど
Q学習
状態と行動の組合せごとに、その良さを示すQ値（行動価値関数）を求め、Q-Tableという表にまとめる
最もQ値の高い行動を選択する方策になる
https://gyazo.com/a5bb2b0c6336707dee045114ecc3e6a7
上のような各状態についてのQ-Tableのイメージ
https://gyazo.com/89f9f1da566c3654b0b04bab7b98c82f
たとえばS1の状態にあるときには、「→」よりも「↓」が選ばれやすくなる
このQ-Tableを最適化するのがQ学習
Q値の更新
https://gyazo.com/7f4022c87a5171b559a079d386f039c0
$ tは時刻（$ t+1は次の時刻）、$ a_tは時刻$ tにおける行動、$ s_tは時刻$ tにおける状態、$ Q(s_t, a_t)はQ値、$ \etaは学習係数、$ R_{t+1}は時刻$ t+1で得られる報酬、$ \gammaは割引率
時刻$ tでの行動の結果得られた報酬$ R_tと、「次の時刻の状態でとりうる行動の中でQ値が最大になる行動のQ値に割引率をかけた値」の和から、現在のQ値を差し引き、それに学習係数をかけたぶんを更新量とする
Q学習のQ値の更新式を、次の時刻で実際に選択された行動のQ値を使用する以下のものにしたSARSAという方法もある
https://gyazo.com/df9ad760e6b1320061e7bc65f6243ceb
Deep Q-Network（DQN）
Q学習の問題点
扱う状態の数が増えると指数爆発し、学習できなくなる
上の迷路の例だと、マス目が100×100になるだけで状態が10000になる
このQ-Tableの代わりに深層学習を用いたのがDeep Q-Network（DQN）
要するに、行動価値関数を関数近似するということをやる
状態$ s_tと、各行動についてのQ値の間の関数近似を深層学習により行う
たとえばなんらかのゲームの自動プレイにDQNを用いる場合はこんなイメージ
https://gyazo.com/8e5c969cfceb5b1c65ab7e9f01fbbd03
Q学習のQ値の更新式の一部を用いて、以下のような誤差項を使ってバックプロパゲーションを行う
https://gyazo.com/1648ba64ac3af3cbb301ab4351760ead
強化学習の楽しい適用例
強化学習でマリオを攻略
マリオの操作の方策を強化学習により求める、という動画
https://youtu.be/qUjslOnP2jY
（参考）遺伝的アルゴリズムでマリオを攻略
強化学習は「最適な方略を見つける」しくみなので、数理最適化の一種ととらえられる部分もある
要するに、何が「良い」のかを定義し、解候補（強化学習では方策）の「良さ」を評価して、「良い解」を見つける、というプロセスである
問題によっては、定式化の工夫により、強化学習で解くことも、最適化手法で解くこともできるだろう
上のマリオの操作の方策を強化学習するものを、遺伝的アルゴリズムという最適化手法で解いた動画
https://youtu.be/Oakaeuz7KNE
（余談）強化学習のゲームへの応用例の多さについて
教師あり学習や教師なし学習と異なり、強化学習は、エージェントが行動することにより、学習のためのデータを「自ら生成していく」プロセスである
囲碁にせよマリオにせよ、コンピュータ上でシミュレーションすることで、学習に必要なデータを大量にいくらでも集めることができる
その意味で、ゲームというのは、コンピュータ上に「環境」が明確にあり、「行動」の組合せが決まっており、「状態」や「報酬」が定義しやすく、かつプレイを自動化してシミュレーションでき、学習の結果がビジュアルとして明確にわかる（これ重要）ので、強化学習に非常に向いている、といえる
というか、強化学習としての問題の定式化とプログラム化が用意であり、関心も生まれやすいため、キャッチーな例として多くの人が参入しやすい、ということ
探索と活用のトレードオフ
強化学習には探索（exploration）と活用（exploitation）のトレードオフと呼ばれる本質的現象がある
自らの行動によりデータを収集していく、という構造なので、行動が偏っていると、可能性を見逃しやすい
その時点で高い報酬を得られる行動を取ることを活用（exploitation）とよぶが、そればかりをしていると、それに応じた方策は学習できるが、「より高い報酬が得られる方策」があるかもしれないのにそれを見つける可能性が低くなる
たとえば将棋で「いま取れる駒を取る」に方策が偏ると結局は勝てないはず
数理最適化問題でいう「局所最適解」への陥りと同じ
https://gyazo.com/5b338b490b5d61b7114f831c03783fc7
なので、一定程度は、「現時点ではよくないかもしれないが、より良い解が見つかるかもしれない行動」を取る必要がある
「現時点での最適行動」ではないものをある程度入れて情報を集めることを探索（exploration）とよび、一定確率でランダムに行動を選択するなどして、これをある程度入れないといけない
しかし、やりすぎると、探索の効率が落ちる
現時点では最適ではないので、多くの場合高い報酬は得られない
このように、活用をしすぎると局所的な解に陥ってしまう（短期的にはよいものが見つかるが、長期的にさらによいものが見つかる可能性は低くなる）し、探索をしすぎると学習の効率が落ちてしまう（長期的にはよいものが見つかるかもしれないが、短期的にはよいものが見つかりにくくなる）
これを探索と活用のトレードオフ（ジレンマ）という
これは、最適化のための評価関数（目的関数）が非線形である場合には常に起こりうる話
なので、強化学習だけでなく、（非線形の）数理最適化全般にあらわれる現象である
上の例で出した「遺伝的アルゴリズム」に代表される進化計算の手法も、実はこの探索と活用のトレードオフに対応するためのしかけがアルゴリズムに内包されている
確率的に最適でない策をとる、というメカニズムが含まれたアルゴリズムになっており、これによって、良い解が得られるようになっている
（おまけ）
「Mario AI」は、AIのテスト問題になっていて、けっこう研究されていたりします
ChatGPTと強化学習
@stateofai_ja: ChatGPT を強力にしているコア技術「人間によるフィードバックを用いた強化学習 (RLHF; Reinforcement Learning from Human Feedback)」の非常に分かりやすい解説動画 (by HuggingFace)。 強化学習をもっと勉強したい場合、いろんな教材があります