元バイオ系

元バイオウェット系がデータサイエンスやらを勉強していくブログ。 基本自分用のまとめ。

強化学習を理解したい #1

統計 強化学習

仕事でDeep Learningを使う機会がちょいちょい出てきたので、tensorflowやPyTorchの練習も兼ねて強化学習を勉強中。

手法が色々あってよくわからなくなってきたので記事にまとめます。

  • 全体を俯瞰することに努めます。
  • 正確性よりわかりやすさを優先します。
  • 基本的な統計・機械学習の知識があることを前提にまとめます。

問題設定

目的

状態 \displaystyle s に対して行動 \displaystyle a を起こし、得られる報酬の総和 \displaystyle \sum r を最大化する。

方法

価値評価と戦略を学習する

  • 価値評価
    • 価値の算出方法のこと。
    • 価値とは、得られる報酬の総和の見積値のこと（期待報酬*とも呼ぶ）。
  • 戦略
    • 状態を受け取り行動を出力する関数のこと（いわゆるモデルのこと）

*期待報酬とは言うものの、実際は「割引現在価値」の総和 で、いわゆる統計的な期待値計算とは異なります。 現在時点から将来にわたって得られる報酬を見積もるわけですから、 未来の不確実性を考慮して、得られる（と期待されている）報酬に対して割引率を掛けて和をとります。

登場用語

大まかな問題設定がわかったところで、強化学習に登場する基本的な用語をまとめておきます。

  • 環境とエージェント
    • 問題設定を規定するものと、問題設定に従って行動する主体のことです。
    • 自動運転で例えるなら、道路と車の関係になります。
  • 状態 \displaystyle s
  • 行動 \displaystyle a
  • 遷移確率 \displaystyle T
    • transitionのTです。
    • 行動が決まれば遷移先が決まる...というわけでは無いので分けて考える必要があります。
      • 歩こうと思っても躓いたり転んだりすることだってあるということです。
  • 即時報酬 \displaystyle R
    • rewardの頭文字です。
    • 状態が遷移したときに実際に得られる報酬（行動1回分の報酬の）です。

「価値評価」と「戦略」

強化学習では「価値評価」と「戦略」を学習するわけですが、「価値」とは何でしょうか？

ここの理解を疎かにするとこの後混乱するだけなので、価値とは何かについてまとめます。

結局のところ、報酬によって定義されるということを知っておくとこの後がわかりやすくなると思います。

強化学習における「価値」

現時刻を \displaystyle t として、戦略 \displaystyle \pi に基づいた行動 \displaystyle a_t によって 現状態 \displaystyle s_t から 次の状態 \displaystyle s_{t+1}へ遷移することを考えます。

この時、 \displaystyle s_t から \displaystyle \pi に基づいて行動して得られる価値は、以下のように定義されます。

\displaystyle V_\pi(s_t) = \text{E}_{\pi}\left[r_{t+1} + \gamma V_{\pi}(s_{t+1}) \right]

なぜこの式で良いのかというと、再帰的に定義された式を書き下してみると

\displaystyle V_\pi(s_t) = \text{E}_{\pi}\left[r_{t+1} + \gamma \text{E}_{\pi}\left[r_{t+2} + \gamma V_{\pi}(s_{t+2}) \right] \right]

となり、行動 a_t によって得られる即時報酬 r_{t+1} と、その後に得られるであろう価値の期待値を取ったものになっています（ \gamma は上で説明した割引率です）。

これが、「 s_t から \pi に基づいて行動して得られる価値」なわけですが、式を見てわかる通り、 「価値」とは割引率を考慮した報酬の期待値です。つまり、状態が遷移する際の報酬が決まっていれば、自然と定まるものになっています。

ValueベースとPolicyベース

「価値」が何かわかったところで、次はエージェントの行動指針である「戦略」についてまとめます。

戦略には大きく分けてValueベースとPolicyベースの２つが存在します。

  • Valueベース
    • 各状態で常に最大価値の行動を取る手法のこと。
  • Policyベース
    • 各状態で確率的に価値の高い行動を取る手法のこと。

要は決定論的か確率的かという違いですね。 言葉にすると簡単ですが、Policyベースの方は最適化のプロセスが少々複雑です。

Value iteration と Policy iterateion

さて。ValueベースとPolicyベースについては一言でまとめてしまいましたが、それぞれの戦略が機能するのは価値を正しく見積もれる場合のみです。

最初から正しい価値など知るはずもありませんから、ここからが強化学習の本領となります。

では、価値の定義を思い出してみましょう。

\displaystyle V_\pi(s_t) = \text{E}_{\pi}\left[r_{t+1} + \gamma V_{\pi}(s_{t+1}) \right]

先ほどは説明のために「期待値」という言葉で \text{E} の表記をそのままにして置きましたが、展開すると

\displaystyle V_{\pi} (s_t) = \sum_{a} \pi(a|s) \sum_{s'} T(s'|s, a)\left\{R(s, s`) + \gamma V_{\pi} (s')\right\}

と書き直すことができます。ここで、新しく登場した表記について書いておくと、

  • \pi(a|s)
    • 状態 s で行動 a を選択する確率
  • T(s'|s, a)
    • 状態 s で行動 a を選択したときに状態 s' へ遷移する確率（遷移確率）
  • R(s, s')
    • 状態 s から s' へ遷移した際に得られる即時報酬

となっています。ちなみにこの式をBellman equationといいます。この式において、ValueベースとPolicyベースは以下のような関係になっています。

f:id:hotoke-X:20220206041638p:plain:w600

Bellman equationと戦略の関係がわかったところで、それぞれの戦略の最適化方法についてまとめます。

Value iteration

まず、Valueベース手法の最適化についてですが、Bellman equationでは、状態 s から s' へ遷移したときの価値を定義しているのでした。

つまり \pi (a|s) と T(s'|s, a) さえ定義されていれば全ての遷移について価値の計算が可能ということです。

そこで、Valueベース手法は以下の式を繰り返し計算するだけで最適化が完了します。

\displaystyle V_{i+1} (s) \overset{\text{def}}{=} \sum_{s'} T(s'|s, a)\left\{R(s, s') + \gamma V_{i} (s')\right\}

ここで、 i は最適化の繰り返し数を表しています。

つまり、上式で全状態について一通り価値を計算し、それを次の最適化計算へ利用しているだけです。それぞれの状態について価値の更新が行われなくなったら計算終了とします。

価値を繰り返し計算するので、この最適化プロセスをValue iterationと呼びます。

Policy iteration

次に、Policyベース手法の最適化についてです。

同じBellman equationが基礎となっていますから、Value iterationと同様繰り返し計算で最適化が完了しますが、計算のプロセスは少々複雑です。

Policyベースでは、得られる価値を最大化するように戦略を更新する必要がありますがエージェントは戦略に従って確率的に行動します。

確率的に行動するのに最大化？と思う方も居るかもしれませんが、要は戦略に従った場合に得られる価値の期待値を最大化すれば良いということです。

しかし、困ったことにそもそも正確な価値がわかっていないのでした。そこで、Policyベースの最適化 （Policy iteration）では

  1. 価値の推定
  2. 戦略の評価

の２段構えで繰り返しの最適化が行われます。価値と戦略の両方が交互に最適化されるわけですね。

価値の推定はほとんどValue iterationと同じ形の式ですが、最大価値を求めるのではなく期待値を求めるのが異なる点です。具体的には以下のようになります。

\displaystyle V_{\pi} (s_t) = \sum_{a} \pi(a|s) \sum_{s'} T(s'|s, a)\left\{R(s, s`) + \gamma V_{\pi} (s')\right\}

つまり、素直にBellman equationの計算をしているだけですね。あとはValue iterationと同じ要領で価値が収束するまで計算を繰り返せば価値の推定は完了します。

価値の推定ができたら、戦略の評価を行います。戦略の評価では、それぞれの状態 s について以下のアルゴリズムで戦略を更新します。

1. 現在の戦略に従った場合最も価値の高い行動を取得する（ a_{\text{policy}}とおく）
2. 推定価値に基づいて各行動の価値を計算し、最大価値の行動を取得する（ a_{\text{best}}とおく）
3. a_ {\text {policy}} と a_ {\text {best}} が異なっていたら a_ {\text {best}}を選ぶように戦略を更新する

戦略の更新が終わったら再び価値の推定に戻り、戦略の更新が行われなくなるまで以下繰り返しです。

まとめ

以上が強化学習の基礎となる考え方でした。

結局どの手法でも価値の計算が必要で、その価値は報酬によって規定されていることを理解すると全体像が見えてくると思います。

また、今回まとめた方法は \pi (a|s) と T(s'|s, a) が定義可能である前提でした。

これらが定義可能な問題を、強化学習モデルが明らかであるということからモデルベースと呼びます。

これらが定義できないモデルフリーの問題にどう対処するのかについては今回触れませんが、基本となる考え方は同じです。

モデルベースの問題をちゃんと理解していれば理解に困ることは少ないでしょう（多分）。

参考書籍

Pythonで学ぶ強化学習