深層学習以前の強化学習をまとめる

強化学習の観点

  • 何を学習するか
    • 状態や行動の価値を学習: Valueベース
    • 戦略を学習: Policyベース


  • 学習に使う環境をモデル化できるか
    • できる: モデルベース
    • できない: モデルフリー


  • 学習に用いる実績情報はなにか


  • 価値を見積もる際に戦略を考慮するか
    • する: On-Policy
    • しない: Off-Policy


主要な手法をこれらの観点で分類するとこんな感じ

Value/Policyベース モデルベース/フリー モンテカルロ/TD法 On/Off-Policy
Value Iteration Value モデルベース なし なし
Policy Iteration Policy モデルベース なし なし
モンテカルロ法 Value モデルフリー モンテカルロ法 Off-Policy
Q-learning Value モデルフリー TD法 Off-Policy
SARSA Value モデルフリー TD法 On-Policy
Actor-Critic法 両方 モデルフリー TD法 On-Policy

何を学習するか

強化学習では環境が以下の変数で表される。

  • $s$: 現在の状態
  • $a$: 現在の状態からとれる行動
  • $T(s'|s,a)$: 状態$s$で行動$a$をとったときの状態$s'$の遷移確率
  • $R(s,a,s')$: 状態$s$で、行動$a$をとり, 次の状態$s'$に遷移したときに得られる報酬

図にするとこんな感じ

強化学習の目的は指定の期間中(無限でもOK)での報酬の総和を最大化するような制御を得ること。

強化学習では価値と戦略によってエージェントの制御がなされる

  • 価値: エージェントの状態や行動の良否を評価する機構
  • 戦略: エージェントの行動の選択する機構

これらを学習することによってより良い制御を得るが、このどちらを学習するかで分類がされる

Valueベース

  • 状態や行動の価値を学習することで制御を得る
  • このとき行動は戦略に$\epsilon$-greedy法などを用いることで間接的に価値から制御される
  • 手法: 後述のValue Iteration, モンテカルロ法, Q-learning, SARSA, Actor-Critic法など

Policyベース

  • 戦略を学習することで制御を得る
  • 戦略に基づいた状態や行動の価値も学習するが、制御は戦略によってなされる
  • 手法: 後述のPolicy Iteration, Actor-Critic法など

環境をモデル化できるか

モデルベース(環境をモデル化できる場合)

  • エージェントを動かさずシミュレートだけで学習が可能
  • どの行動をするとどういう結果が得られるかのモデルが存在する場合(遷移関数や報酬関数が明らかの場合)に使える
  • 例: 迷路とか

モデルベースの手法: Value/Policy Iteration

Bellman方程式を用いれば強化学習の目的である状態や行動の価値が導出できる。

ValueベースのBellman方程式


\displaystyle
V(s) = R(s) + {\gamma} {\max}_a \sum_{s'} T(s'|s,a) V(s')

PolicyベースのBellman方程式


\displaystyle
V_{\pi}(s) = \sum_{a}\pi(a|s)\sum_{s'}T(s'|s,a)(R(s)+{\gamma}V_{\pi}(s'))
  • $s$: 現在の状態
  • $a$: 現在の状態からとれる行動
  • $s'$: 次の状態
  • $V(s)$: 状態$s$の価値関数
  • $R(s)$: 状態$s$で得られる報酬
  • $T(s'|s,a)$: 状態$s$で行動$a$をとったときの状態$s'$の遷移確率
  • $\gamma$: 報酬の割引率
  • $\pi(a|s)$: 状態$s$で行動$a$をとる確率(戦略を表現)
  • $V_{\pi}(s)$: 戦略$\pi$で行動する場合の状態$s$の価値関数

Bellman方程式を使えば一つ先の状態の価値から今の状態の価値が計算できる。 これを利用して一番最後の状態から逆向きに価値を導出していくことで価値関数が求められる(動的計画法を使って効率的に解ける)。

ただし、この方法では以下のように計算コストが膨大になる。

  • 今の状態$s$の価値$V(s)$の導出には先に全ての行動$a$に関して先の状態の価値$V(s')$を計算する必要がある
  • 先の状態$s'$の価値$V(s')$の導出には先に全ての行動$a'$に関してさらに先の状態の価値$V(s'')$を計算する必要がある
  • さらに先の状態$s''$の価値$V(s'')$の導出には・・・

Value Iteration

これに対し、予め全ての状態に対する価値関数$V(s)$に適当な値が入っていればこの計算をしなくて済み、適当な値が入った$V(s)$はBellman方程式により逐次正確な値に更新していけば計算コストを抑えて$V(s)$が学習できる。 この手法をValue Iterationという。

アルゴリズム

  1. 価値関数$V(s)$を適当な値で初期化する
  2. Bellman方程式を用いて全状態$s$に関して$V(s)$を更新
  3. 2.による更新を繰り返し、$V(s)$に変化がなくなったら終了

2.の更新時に真の価値関数の元となる報酬$R(s)$や遷移関数$T(s'|s,a)$が関与するので、段々真の値に近づいていくイメージ(かな?)。
証明は「UCL Course on RL」のLecture3にあるそうな。

Policy Iteration

先述のValue Iterationのようにして学習した価値関数に基づいて、価値を最大化するような戦略になるようにすれば戦略も学習できる。このようにして価値関数と戦略を同時に学習する手法をPolicy Iterationという。

アルゴリズム

  1. 価値関数$V(s)$と戦略$\pi(a|s)$を適当な値で初期化する
  2. 今の$\pi(a|s)$に基づいて価値関数を学習する(PolicyベースのBellman方程式を使ってValue Iterationを行う)
  3. 学習した価値関数に基づいて価値を最大化するよう$\pi(a|s)$を更新する
  4. 2.,3.を繰り返し、$\pi(a|s)$に変化がなくなったら終了

モデルフリー(環境をモデル化できない場合)

  • エージェントを実際に動かして得た経験から学習
  • どの行動をするとどういう結果が得られるかのモデルが不明、もしくはうまくモデル化できない場合(遷移関数や報酬関数がが不明、もしくはうまくモデル化できない場合)
  • 例: ゲーム、囲碁とか(フィールドや相手が何するかによって環境が変わる)

モデルフリーの手法

後述のモンテカルロ法, Q-learning, SARSA, Actor-Critic法など

学習に用いる実績情報はなにか

モデルフリーで得た経験のうち、何の情報を使って学習するかで分類される

報酬のみから学習(モンテカルロ法)

  • 現在からエピソード終了時刻$T-t$までの報酬を学習に使用する
  • 現在の価値関数が上記の報酬に近づくよう両者の誤差を算出して学習する

※価値関数は解く問題に応じて状態価値関数$V(s_t)$でも状態行動価値関数$Q(s_t, a_t)$でも良い


\displaystyle
Error(s_t, a_t) = (r_{t+1}+{\gamma}r_{t+2}+{\gamma}^{2}r_{t+3}+\dots+{\gamma}^{T-t-1}r_{T-t}) - Q(s_t, a_t)


アルゴリズム

※簡単のため価値関数$Q(s, a)$を行列$Q[s][a]$として考える

  1. 戦略($\epsilon$-greedy法など)に従ってエピソード終了まで行動
  2. エピソード$e$中の状態$s_{t}^{e}$と行動$a_{t}^{e}$について報酬を使って価値行列$Q[s_{t}][a_{t}]$をそれぞれ更新(下式) $$ Q[s_{t}^{e}][a_{t}^{e}] = Q[s_{t}^{e}][a_{t}^{e}] + \alpha Error(s_{t}^{e}, a_{t}^{e}) $$ $\alpha \in (0, 1)$は学習係数

  3. 1., 2.を繰り返す

報酬と見積った価値から学習(TD法)

  • 現在から1時刻先の報酬とそのときの状態価値を学習に使用する
  • 現在の価値関数が上記の報酬と状態価値の和に近づくよう両者の誤差を算出して学習する $$ Error(s_t, s_{t+1}) = r_{t+1} + \gamma V(s_{t+1}) - V(s_t) $$

    • 前述のモンテカルロ法の$r_{t+1}$だけを実際の報酬として観測し、残りは次時刻の状態価値$V(s_{t+1})$で近似しているイメージ
    • この誤差のことをTD誤差(Temporal Difference Error)という
  • 上記は1時刻先の場合であるがこれを$n$時刻先で拡張して考えることができる→Multi-step Learning

    • 一般的に$n=2,3$がよく使われるらしい

TD($\lambda$)法

1時刻〜エピソード終了時刻$T$までのTD誤差を組み合わせる方法


\displaystyle
\begin{eqnarray}
1時刻先での価値&:& W_t^1 = r_{t+1} + {\gamma}V(s_{t+1})\\
2時刻先での価値&:& W_t^2 = r_{t+1} + r_{t+2} + {\gamma}^{2}V(s_{t+2})\\
\vdots\\
T-t時刻先での価値&:& W_t^{T-t} = r_{t+1} + r_{t+2} + \dots + {\gamma}^{T-t}V(s_{T-t})
\end{eqnarray}

としてこれらを$\lambda \in [0, 1]$で重み付けする


\displaystyle
TD(\lambda)法での価値: W_t^{\lambda} = (1-\lambda)\sum^{T-t-1}_{n=1}{\lambda}^{n-1}W^{n}_t + {\lambda}^{T-t-1}W^{T-t}_t
  • 将来の時刻ほど影響が少なくなるようになっている
  • $\lambda=0$のときはTD法, $\lambda=1$のときはモンテカルロ法の価値となるようになっている

Q-learning

TD法を用いて状態価値関数(or行列)$Q$を学習するValueベースの方法

アルゴリズム

  1. 戦略($\epsilon$-greedy法など)に従って1時刻先まで行動
  2. 1時刻先の報酬とそのとき最大の価値を価値となる行動をしたときの価値$Q$を使って価値行列$Q[s_{t}][a_{t}]$を更新(下式) $$ Q[s_{t}][a_{t}] = Q[s_{t}][a_{t}] + \alpha \{(r_{t+1} + \gamma {\max}_{a^{'}} Q[s_{t+1}][a^{'}]) - Q[s_{t}][a_{t}]\} $$
  3. 1., 2.をエピソード終了まで繰り返す
  4. 3.を繰り返す

価値を見積もる際に戦略を考慮するか

学習などで価値を見積もる際に戦略を考慮するかどうかで分類される

Off-Policy

  • 価値を見積もる際に戦略を考慮しない
  • 次の行動は常に価値が最大となる行動を選択する(例: 下式) $$ Q[s_{t}][a_{t}] = Q[s_{t}][a_{t}] + \alpha \{(r_{t+1} + \gamma {\max}_{a^{'}} Q[s_{t+1}][a^{'}]) - Q[s_{t}][a_{t}]\} $$
    • そのため楽観的な価値の見積もりになりやすい
  • 手法: 前述のモンテカルロ法, Q-learningなど

On-Policy

  • 価値を見積もる際に戦略を考慮する
  • 次の行動は常に戦略によって選択される(例: 下式) $$ Q[s_{t}][a_{t}] = Q[s_{t}][a_{t}] + \alpha \{(r_{t+1} + Q[s_{t+1}][a_{t+1}]) - Q[s_{t}][a_{t}]\}\\ a_{t+1} = Policy(s_{t+1}) $$ ※Policy: 戦略(ϵ-greedy法など)
    • そのため比較的現実的な価値の見積もりになりやすい

SARSA

Q-learningの学習に使う1時刻先の価値をとる行動を戦略によって選ぶようにした方法

アルゴリズム

  1. 戦略($\epsilon$-greedy法など)に従って1時刻先まで行動
  2. 1時刻先の報酬とそのとき戦略によって選択された行動をしたときの価値$Q$を使って価値行列$Q[s_{t}][a_{t}]$を更新(下式) $$ Q[s_{t}][a_{t}] = Q[s_{t}][a_{t}] + \alpha \{(r_{t+1} + Q[s_{t+1}][a_{t+1}]) - Q[s_{t}][a_{t}]\}\\ a_{t+1} = Policy(s_{t+1}) $$ ※Policy: 戦略(ϵ-greedy法など)
  3. 1., 2.をエピソード終了まで繰り返す
  4. 3.を繰り返す

Actor-Critic法

戦略と価値関数を別々に学習する手法

  • 戦略担当のActorと価値評価をするCriticがそれぞれ価値関数$Q_A$, $V_C$を持っている
  • ValueベースとPolicyベース双方の性質を持つ
    • Criticの価値関数$V_C$の学習は$V_C$のみによって完結する→Valueベース
    • Criticのよる評価価値と実際の報酬によって算出されたTD誤差によって戦略を学習→Policyベース
  • SARSAとの違い: SARSAの学習対象は価値関数のみ→Valueベース
    • 戦略はϵ-greedy法などを用いることで$Q$の学習によって間接的に更新される
  • SARSAに比べて安定した学習ができる
    • おそらく価値評価と戦略の学習が独立しているから
    • 「価値更新→間接的に戦略が変わる→選択される行動が変わるため価値も変わる→これまで学習目標としていた価値がずれる」
      というのが起こりにくいのだと

アルゴリズム

  1. 戦略($sotfmax(Q_A[s][a])$のような価値関数に依存するもの)に従って1時刻先まで行動
  2. 1時刻先の報酬と$V_C$を用いてTD誤差を算出 $$ Error(s_t, s_{t+1}) = (r_{t+1}+{\gamma}V_C[s_{t+1}])-V_C[s_t] $$
  3. $V_C$を更新 $$ V_C[s_t] = V_C[s_t] + {\alpha}Error(s_t, s_{t+1}) $$ ※${\alpha}$: 学習係数
  4. $Q_A$を更新 $$ Q_A[s_t][a_t] = Q_A[s_t][a_t] + {\beta}Error(s_t, s_{t+1}) $$ ※${\beta}$: 学習係数
  5. 1.~4.をエピソード終了まで繰り返す
  6. 5.を繰り返す

特に3.でValueベースのように$V_C$が更新できている点、4.でPolicyベース戦略に従って選択した$a_t$(1.で選択)に関して$Q_A$が更新できている点がポイント