Sarsa による行動価値関数の学習 ー ベルマン方程式から TD 誤差まで

公開:
強化学習 #Sarsa #TD学習 #価値ベース #ベルマン方程式

問題設定

環境はマルコフ決定過程（MDP）で表されるとします。MDP は

M=(S,A,P,R,γ)\mathcal{M} = (\mathcal{S}, \mathcal{A}, P, R, \gamma)

として、時刻 tt からの割引報酬を

Gt=∑k=0∞γkRt+k+1G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}

で定義します。ある方策 π(a∣s)\pi(a|s) のもとでの行動価値関数（state action value）は

Qπ(s,a)=Eπ[ Gt∣St=s,At=a ]Q^{\pi}(s,a) = \mathbb{E}_{\pi}\bigl[\, G_t \mid S_t = s, A_t = a \,\bigr]

です。価値観数はベルマン方程式を満たします。行動価値関数は

Qπ(s,a)=∑s′P(s′∣s,a)[R(s,a,s′)+γ∑a′π(a′∣s′)Qπ(s′,a′)](★)Q^{\pi}(s,a) = \sum_{s'} P(s' \mid s,a) \Bigl[ R(s,a,s') + \gamma \sum_{a'} \pi(a' \mid s') Q^{\pi}(s', a') \Bigr] \tag{★}

として書き表せます。このあたりの計算の詳細については

で議論していますのでご参考まで。

補足

価値関数のベルマン方程式の右辺は次のように書けます。

RHS of (★)=∑s′P(s′∣s,a)[R(s,a,s′)+γ∑a′π(a′∣s′)Qπ(s′,a′)]=∑s′∑a′P(s′∣s,a) π(a′∣s′) [R(s,a,s′)+γQπ(s′,a′)]=∑s′∑a′P(s′∣s,a) π(a′∣s′) f(s′,a′).\begin{aligned} \text{RHS of }(★) &= \sum_{s'} P(s' \mid s,a) \Bigl[ R(s,a,s') + \gamma \sum_{a'} \pi(a' \mid s') Q^{\pi}(s', a') \Bigr] \\ &= \sum_{s'} \sum_{a'} P(s' \mid s,a)\, \pi(a' \mid s')\, \bigl[ R(s,a,s') + \gamma Q^{\pi}(s', a') \bigr] \\ &= \sum_{s'} \sum_{a'} P(s' \mid s,a)\, \pi(a' \mid s')\, f(s', a'). \end{aligned}

ここで、MDP と方策の定義より

Pr⁡(St+1=s′,At+1=a′∣St=s,At=a)=P(s′∣s,a) π(a′∣s′)\Pr(S_{t+1} = s', A_{t+1} = a' \mid S_t = s, A_t = a) = P(s' \mid s,a)\, \pi(a' \mid s')

が成り立つので、上式は

RHS of (★)=∑s′∑a′Pr⁡(St+1=s′,At+1=a′∣St=s,At=a) f(s′,a′)=E[f(St+1,At+1) ∣ St=s,At=a]\begin{aligned} \text{RHS of }(★) &= \sum_{s'} \sum_{a'} \Pr(S_{t+1} = s', A_{t+1} = a' \mid S_t = s, A_t = a)\, f(s', a') \\ &= \mathbb{E}\bigl[ f(S_{t+1}, A_{t+1}) \,\big|\, S_t = s, A_t = a \bigr] \end{aligned}

となり、

Qπ(St,At)=E[Rt+1+γQπ(St+1,At+1)∣St,At]Q^\pi(S_t, A_t) = \mathbb{E}[R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) \mid S_t, A_t]

という条件付き期待値の形に書き換えられます。この式を眺めるとベルマン方程式では

  • 現時点で将来的に得ると思っている報酬（左辺）は、
  • 「1 ステップ実際に行動して得られた報酬と、現時点で予測できる将来の報酬」の期待値（右辺）

に等しいということが分かります。かなり噛み砕くと、現在見えている景色と Q(s,a)Q(s,a)と、実際に動いて見えた景色 Rt+1+Q(s′,a′)R_{t+1}+Q(s^\prime, a^\prime)とはだいたい平均的には等しい、という表現です。

行動価値関数の意味

強化学習の大目標は最良な方策 πθ\pi_\theta を見つけることですが、その時の基準となり方策の良し悪しを図るのが行動価値関数です。行動価値関数

Qπ(s,a)=E_π[Gt∣St=s,At=a]Q^\pi(s, a) = \mathbb{E}\_\pi \big[ G_t \mid S_t = s, A_t = a \big]

は

状態 ss で行動 aa をとり方策 π\pi に従って行動したときに、将来得られる割引累積報酬の期待値

を表します。ここで、ある 2 つの方策 π1,π2\pi_1, \pi_2 を比較するときには、

Qπ1(s,a)>Qπ2(s,a)Q^{\pi_1}(s, a) > Q^{\pi_2}(s, a)

のように方策における行動価値を比較してその大小で、「より大きな QπQ^\pi を与える方策」を、より良い方策とみなします。しかし実際には、

  • 環境の遷移確率 P(s′∣s,a)P(s' \mid s,a) や報酬関数 R(s,a,s′)R(s,a,s') が未知である
  • 状態・行動空間が巨大で、厳密な計算が現実的でない

といった理由から、行動価値関数をそのまま解析的に計算することはほとんどできません。そこで、サンプル（エピソード）からの推定と関数近似（テーブルやニューラルネットなど）を用いて、

Qπ(s,a)≈Qϕ(s,a)Q^\pi(s, a) \approx Q_\phi(s, a)

といった形で、行動価値関数を「近似的に学習する」というアプローチを取ります。行動価値関数さえ分かってしまえば

π(s)=arg max⁡aQϕ(s,a)\pi(s) = \argmax_a Q_\phi(s,a)

のように、行動価値を最大化するように方策を設定することができます。これは 価値ベースの手法（value based method）と呼ばれます[1]。

Sarsa

上記で議論したことを改めてまとめておきます。方策 π\pi のもとでの行動価値関数 QπQ^\pi は、ベルマン方程式として

Qπ(St,At)=E[Rt+1+γQπ(St+1,At+1)∣St,At]Q^\pi(S_t, A_t) = \mathbb{E}\bigl[ R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) \mid S_t, A_t \bigr]

という期待値レベルでの自己一致条件を満たします。 ここで等号で結ばれているのは、

  • 左辺：現在の行動価値 Qπ(St,At)Q^\pi(S_t, A_t)
  • 右辺：1 ステップ先の報酬と、その先の価値の期待値

です。

この式を次のように書き換えます。条件 St,AtS_t, A_t のもとで Qπ(St,At)Q^\pi(S_t, A_t) は定数であることに注意すると[2]

E[Rt+1+γQπ(St+1,At+1)−Qπ(St,At) ∣ St,At]=0\mathbb{E}\Bigl[ R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) - Q^\pi(S_t, A_t) \,\Big|\, S_t, A_t \Bigr] = 0

と移項することで =0=0 の形になります。中カッコの部分

Rt+1+γQπ(St+1,At+1)−Qπ(St,At)R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) - Q^\pi(S_t, A_t)

が、ベルマン方程式の「1 ステップあたりのズレ」を表しています。真の QπQ^\pi であれば 1 ステップあたりのズレの期待値は 0 になることが分かります。

TD 誤差の定義

「行動価値関数は実際には計算できないので近似する」という話を思い出すと、実際には何らかの形で QπQ^\pi を推定している（ニューラールネットワークなど）ことになります。この場合のズレ

δt:=Rt+1+γQ(St+1,At+1)−Q(St,At)\delta_t := R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)

を TD 誤差 (Temporal-Difference error) と呼びます。

  • δt>0\delta_t > 0 なら「右辺の方が大きい → Q(St,At)Q(S_t, A_t) を引き上げたい」
  • δt<0\delta_t < 0 なら「右辺の方が小さい → Q(St,At)Q(S_t, A_t) を下げたい」

という指標として解釈できます。ここで重要なのは、δt\delta_t は ベルマン方程式の右辺と左辺の差の「1 サンプルぶん」 だという点です。

TD(0) 更新則から Sarsa へ

ベルマン方程式を再現するようにこのズレが小さくするよう Q(St,At)Q(S_t, A_t) を更新する、という最も素直な一歩は

Q(St,At)←Q(St,At)+α δtQ(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\, \delta_t

です。すなわち

Q(St,At)←Q(St,At)+α[Rt+1+γQ(St+1,At+1)−Q(St,At)].Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \Bigl[ R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \Bigr].

ここで α\alpha は学習率です。この更新は

  • 右辺の Rt+1+γQ(St+1,At+1)R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) を「その時点でのターゲット（目標値）」とみなし、
  • 左辺の Q(St,At)Q(S_t, A_t)（現在の予測）を、ターゲットに近づけるよう一歩動かす

という形になっています。期待値 E[⋅]\mathbb{E}[\cdot] を直接計算する代わりに、実際に観測された Rt+1,St+1,At+1R_{t+1}, S_{t+1}, A_{t+1} から得られる 1 サンプルぶんのターゲットを使って確率的に探索していると解釈できます。

Sarsa アルゴリズムの流れ

上の TD 更新を、on-policy[3]に適用したものが Sarsa です。1 エピソード内の流れは次のようになります。

  1. すべての Q(s,a)Q(s,a) を初期化する。
  2. 初期状態 S0S_0 を観測し、QQ に基づく ε\varepsilon-greedy 方策などで A0A_0 を選ぶ。
  3. 各時刻 tt で以下を繰り返す：
    • 行動 AtA_t を環境に実行し、Rt+1,St+1R_{t+1}, S_{t+1} を観測する。
    • 終端状態でなければ、同じ方策（ε\varepsilon-greedy など）で At+1A_{t+1} を選ぶ。
    • TD 誤差 δt=Rt+1+γQ(St+1,At+1)−Q(St,At)\delta_t = R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) を計算する。
    • TD 更新則 Q(St,At)←Q(St,At)+α δtQ(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\, \delta_t で QQ を更新する。
    • St+1→StS_{t+1} \to S_t, At+1→AtA_{t+1} \to A_t として次ステップへ進む。

まとめ

今回は価値ベースの学習手法の一つである Sarsa について導入しました。Sarsa を理解するためには価値関数のベルマン方程式が、

和の形から条件付き期待値の形へと書き換えられ、Qπ(St,At)Q^\pi(S_t, A_t) と Rt+1+γQπ(St+1,At+1)R_{t+1} + \gamma Q^\pi(S_{t+1}, A_{t+1}) の平均的な一致を要求している

という解釈を抑えておく必要がありました。また、遷移確率 P(s′∣s,a)P(s' \mid s,a) や報酬関数 R(s,a,s′)R(s,a,s') は多くの場合未知であり、状態・行動空間も高次元なので QπQ^\pi を解析的に計算するのは現実的ではなく、サンプルから推定された Qϕ(s,a)Q_\phi(s,a) を用いる価値ベースの手法が重要になるということが Sarsa などの入口になっていることも議論できたと思っています。

脚注

  1. 行動価値関数の近似、にだけ目が行っていて強化学習の大目標が達成できないように感じていました。その後の、行動価値関数をそのまま方策として使用するという考え方までをしっかりと理解しておく必要がありました。 ↩︎
  2. 定数AA は A=E[A]A=E[A] という期待値の性質です。単に定数であればランダム性がない（確率変数ではない）ので期待値計算しても特に意味がないということです。 ↩︎
  3. 実際に行動を選んでいる方策と、学習している方策とが同じものであること。 ↩︎