Zenn
🌟

[強化学習][ゼロつく] 強化学習基礎ワード整理（～動的計画法）

2024/04/07に公開
強化学習
tech

強化学習ってなに？

収益を最大化するために状態に応じた適切な行動を学習する手法

例）将棋の場合

収益 = 勝率

状態 = 局面

行動 = 指し手

教師あり学習との違い

  • 状態が変わる

    強化学習：行動によって状態が変わっていく

    教師あり学習：ラベルを推論してもデータは変化しない

  • 収益を得るまでに時間がかかる

    強化学習：複数回の行動によって収益を得る

    教師あり学習：推論ひとつひとつに正解がある

  • 学習箇所がいろいろある

    強化学習：状態→行動、行動→収益、状態→収益など様々な関係を学習

    教師あり学習：データ→ラベルの学習のみ

マルコフ決定過程（MDP）

行動によって次の状態が決まったり、報酬がもらえたりする形式のこと

⇒状態遷移や報酬のもらえ方が決まる

⇒強化学習の問題設定が決まる

  • マルコフ性：次の状態が現在の状態のみによって決まる性質
  • 行動→次の状態：p (s' | s, a)で決まる
  • 行動→報酬：p (r | s, a)で決まる

方策

状態に応じてどのような行動を選ぶか決める部分

関数板 a = f (s) と確率版 π (a | s)がある

以下の理由から、確率の方を採用する

  • マルコフ決定過程が確率を用いて定義されるから
  • 関数の方も表現できるから
  • 最善以外の行動も織り交ぜたいから
  • 行動が連続値の場合もあるから　例）電圧やトルク

報酬

行動をした結果もらえるポイントみたいなもの

rで表す

収益

報酬の累積の合計

G = \sum^{}_{t≧0} r_t

ただし、収益は確率的に変動するので分かりやすくするために期待値にする（期待収益）

※Rは確率変数

E(G)=E[ΣR_t]=ΣE[R_t]

また上記の期待収益は無限和なので発散してしまうため、割引率γを使って収束させる(期待割引収益)

G = \sum^{}_{t≧0}γ^t r_t

E(G)=E[Σγ^tR_t]=Σγ^tE[R_t]

価値関数

本来状態や行動の良し悪しは、ある程度時間が立たないと分からないが

価値関数によってすぐに評価することができ学習しやすくなる。

また、価値関数の値は方策の良さも表しており、方策の評価にも使われる。

状態価値関数

初期状態がsの時に、方策πに従って行動を選択した場合に得られる収益

⇒状態sからどれくらいの収益が見込めるか

⇒その状態のよさ

V^π(s)=E^π[G｜S_0=s]

行動価値関数

初期状態がsで最初に行動aを選択した時、その後方策πに従って行動を選択した場合に得られる収益

⇒状態sで行動aをしたら、その後どれくらいの収益が見込めるか

⇒ある状態におけるその行動のよさ

Q^π(s,a)=E^π[G｜S_0=s,A_0=a]

ベルマン方程式

状態価値関数や行動価値関数を再帰的に定義するための方程式。

特定の状態と方策についていくつか式を出すことで、連立方程式で価値関数を求めることができる。

状態価値関数Vを式変形することで導出できる。

状態価値関数のベルマン方程式

V^{\pi}(s) = E^{\pi}[R_{t}| S_t = s]+γE^{\pi}[G_{t+1}|S_t=s]
=\sum_{a,s'}{\pi}(a|s)p(s'|s,a)r(s,a,s')+\gamma \sum_{a,s'} \pi (a|s)p(s'|s,a)V^{\pi}(s')
=\sum_{a,s'} {\pi}(a|s)p(s'|s,a) \{ r(s,a,s')+{\gamma}V^{\pi}(s')\}

行動価値関数のベルマン方程式

Q^{\pi}(s, a) = E^{\pi}[R_{t}| S_t = s,A_t=a]+γE^{\pi}[G_{t+1}|S_t=s,A_t=a]
=\sum_{s'}p(s'|s,a)r(s,a,s')+\gamma \sum_{s'} p(s'|s,a)V^{\pi}(s')
=\sum_{s'} p(s'|s,a) \{ r(s,a,s')+{\gamma}\sum_{a'}\pi(a'|s')Q^{\pi}(s',a')\}

ベルマン最適方程式

最適方策（全ての状態において状態価値関数が最大となる方策）において成り立つ特別なベルマン方程式。

ベルマン方程式との違いとして、最適な方策の関数をひとつに断言しているため、\sum_{a}{\pi}(a|s)の部分が\max_{a}に置き換わっている。

V^{*}(s)=\max_{a}\sum_{s'} p(s'|s,a) \{ r(s,a,s')+{\gamma}V^{*}(s')\}
Q^{*}(s,a)=\sum_{s'} p(s'|s,a) \{ r(s,a,s')+{\gamma}\max_{a'}Q^{*}(s',a')\}

強化学習の最終的な目標は最適方策を得ることであり、上記を得ることができれば容易に最適方策が得られる。

最適方策：

\mu_*(s)=\argmax_{a}Q^*(s,a)

=\argmax_{a}\sum_{s'}p(s'|s,a)\{r(s,a,s')+\gamma V^*(s')\}

上記の式は、最適行動価値関数の値が最大となる行動aが最適方策になることを示している。

方策反復法

方策評価と方策更新の繰り返しで最適方策\pi^{*}を得る手法。

以下のような特徴がある

  • MDPが既知の場合に使える
  • 状態数が大きすぎない場合に使える
  • データを集めて使うことはせず、MDPから直接\pi^*をつくる

具体的な流れは以下の通り

  • 方策\piと状態価値Vを初期化する。
  • 反復方策評価を用いて価値関数Vを計算する(方策評価)
  • Vによって新たな方策\pi_{new}を計算する(方策改善)
  • 上記をある程度繰り返し、方策が更新されなくなったら最適方策と最適価値関数が得られている

反復方策評価には、ベルマン方程式を更新式としたものを用いる。

V_{k+1}(s)=\sum_{a,s'} {\pi}(a|s)p(s'|s,a) \{ r(s,a,s')+{\gamma}V_{k}(s')\}

また方策の改善は、方策評価によって得られた価値関数VもしくはQを用いて、以下の式で行う

\mu^{'}(s)=\argmax_a Q_\mu(s,a)

=\argmax_a \sum_{s'}p(s'|s,a)\{r(s,a,s')+\gamma V_{\mu}(s')\}

価値反復法

価値反復法も、MDPが既知の場合のみ使えるなど方策反復法と同じ特徴を持つ。

ただし評価フェーズで価値関数を何度も更新して収束させていた方策反復法と違って、価値反復法では評価フェーズでの更新は一度ずつ行う。つまり、価値関数を一度更新したらすぐに改善フェーズに移行する。

また以下のように改善と評価の式に重複した計算があるため、1つにまとめた式で価値関数を更新する。

【改善】

\mu(s)=\argmax_{a} \sum_{s'}p(s'|s,a){r(s,a,s')+\gamma V(s')}

【評価】

a=\mu(s)として

V^{'}(s)=\sum_{s'}p(s'|s,a){r(s,a,s')+\gamma V(s')}



【融合バージョン】

V^{'}(s)=max_a \sum_{s'}p(s'|s,a){r(s,a,s')+\gamma V(s')}

【融合バージョン（更新式っぽく）】

V_{k+1}(s)=max_a \sum_{s'}p(s'|s,a){r(s,a,s')+\gamma V_k(s')}

上記の式で更新を繰り返すことで、最適価値関数と最適方策が得られる

参考

Discussion