最適制御と強化学習のつながりを理解する 

# はじめに

近年の深層学習のブームに乗っかる形で、DQNに代表されるような深層強化学習手法が話題になっています。
下の、DQN（もしくはAtariをプレイするAIの映像）などを見て、強化学習すごそう！なんか面白そう！と思って勉強を始めた方も多いのではないでしょうか？

![A3C FF Breakout](https://raw.githubusercontent.com/yuishihara/A3C-tensorflow/master/trained_results/breakout/breakout_result.gif) <img height="210" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/43125/84987196-abf1-b93c-8463-a2e200da7b15.gif">

ちなみに、自分もその一人であることに間違い有りません。
しかし、強化学習の反対側に制御工学の理論が見えることは実はあまり知られていなかったり、制御工学を勉強していても、強化学習が制御工学と関係があると知らなかったりすることがあると思います。
もし、そのつながりを知り、両者の違い、良さをそれぞれ知れれば、今まで見てきたものがもっと広い視野で見えるようになることは間違い有りません。
そこで、このQiita制御工学アドベントカレンダー2019 22日目の投稿は、制御工学の分野の１手法である最適制御と強化学習のつながりを解説します。
本記事では、まず最初に最適制御の目的と解法を思い出すために解説し、その後で強化学習の目的と解法を最適制御との対応が取れる形で説明します。そして、最後にその２つのつながりを簡単にまとめます。最初の説明では何がどうつながっているのかよくわからなかったとしても、後半ではそれが当然のようにつながっていると思えるようになる予定です。
ぜひ最後まで読んでいただければ幸いです。

# 最適制御
## 最適制御の目的

最適制御の目的はある初期状態$x_{0}$が与えられたときに、次のコストを最小化するような制御入力の系列$u_{0:T}:=u_{0},u_{1},\cdots,u_{T}$を求めることです。

```math
J=\phi(x_{T})+\sum_{t=0}^{T-1}L(x_{t},u_{t})
```

$T$は制御をするのを止める最終の時刻、$L(x_{t}, u_{t})$はステージコストと呼ばれ、各時刻$t$での状態$x_{t}$と与える制御入力$u_{t}$から決まる量です。また、$\phi(x_{T})$は最終時刻でのコストで、終端コストと呼ばれる量です。通常、終端コストは最終状態が目標からずれていたら大きく、ずれが少なかったら小さい量なので、（有限時間）最適制御は、有限回しか制御入力を与えられない状況で、途中までにかかるコストとそれが行き着いた先のコストをあわせて、一番コストが小さい入力を決定する問題なのだと理解することができます。
さらに、最適制御では、上の最適化問題を解くにあたり、次の状態方程式を制約条件として与えます。

```math
x_{t+1}=f(x_{t},u_{t})
```

これは、ある状態$x_{t}$で制御入力$u_{t}$を与えると、次の状態が$x_{t+1}$になるということを表していて、通常は制御対象の動作モデルにあたります。
状態方程式があることで、$x_{0}$が与えられた下で、$u_{0:T}$が決まれば、$x_{1},\cdots,x_{T}$が決まるので、制御入力に着目して、コストを最小化するだけでよいことがわかります。

## ベルマン方程式

価値関数$V(x,k)$を次のように定義します

```math
V(x_{k},k)=\min_{u_{k:T-1}}\biggr(\phi(x_{T})+\sum_{t=k}^{T-1}L(x_{t},u_{t})\biggl)
```

これは時刻$k$から$x_{k}$を起点として最適制御入力を与えた場合のコストを表しています。ここで、コスト$L(x_{k},u_{k})$はそれよりも未来の入力$u_{k+1:T}$の影響を受けないことを考慮すると、

```math
\begin{align}
V(x_{k},k)
&=\min_{u_{k:T-1}}\biggr(\phi(x_{T})+\sum_{t=k}^{T-1}L(x_{t},u_{t})\biggl) \\
&=\min_{u_{k:T-1}}\biggr(L(x_{k},u_{k})+\phi(x_{T})+\sum_{t=k+1}^{T-1}L(x_{t},u_{t})\biggl) \\
&=\min_{u_{k}}\biggr[L(x_{k},u_{k})+\min_{u_{k+1:T-1}}\biggr(\phi(x_{T})+\sum_{t=k+1}^{T-1}L(x_{t},u_{t})\biggl)\biggl] \\
&=\min_{u_{k}}\biggr[L(x_{k},u_{k})+V(f(x_{k},u_{k}),k+1)\biggl]
\end{align}
```

と表現することができます。
そしてこの

```math
V(x_{k},k)=\min_{u_{k}}\biggr[L(x_{k},u_{k})+V(f(x_{k},u_{k}),k+1)\biggl]
```

を（最適）ベルマン方程式といいます。最終時刻$T$については、明らかに$V(x_{T}, T)=\phi(x_{T})$となっているので、任意の最終状態$x_{T}$に対応する終端コスト$\phi(x_{T})$が与えられたとき、各状態の価値関数を次のように再帰的に計算することができます。この計算方法を動的計画法と言います。

```math
\begin{align}
&V(x_{T},T)=\phi(x_{T}) \\
&V(x_{T-1},T-1)=\min_{u_{T-1}}\biggr[L(x_{T-1},u_{T-1})+V(f(x_{T-1},u_{T-1}),T)\biggl] \\
&\dots \\
&V(x_{0},0)=\min_{u_{0}}\biggr[L(x_{0},u_{0})+V(f(x_{0},u_{0}),1)\biggl]
\end{align}
```

ところで、今、$\min_{u_{k:T}}$として、最適制御入力を与えた場合に、価値関数がどのように表現されるかをみたところ、ベルマン方程式が現れました。したがって、最適制御入力が存在するならば、最初に定義した価値関数はベルマン方程式を満たさなければならないと言えます。つまり、ベルマン方程式が満たされることは、最適制御が行われるための必要条件だということができます。
さらに、証明は省きますが、この逆、すなわち、ベルマン方程式を満たすような価値関数$V(x_{k},k)$が見つかり、ベルマン方程式を満たす制御入力列$u_{0:T}$は、元の評価関数

```math
J=\phi(x_{T})+\sum_{t=0}^{T-1}L(x_{t},u_{t})
```

を最小化する制御入力になることも示せます。このときの評価関数の値は$V(x_{0},0)$に等しくなります。
したがって、ベルマン方程式が解ければ、最適制御問題が解けたことと等価になります。
実際、動的計画法を利用すれば、価値関数が計算できるので、最適制御問題を解くことが可能ですが、状態の次元が大きいと現実的には計算できなくなります。

## 離散時間LQ制御

前項のベルマン方程式では任意のコストと、状態方程式を仮定し、動的計画法を利用すれば最適制御問題が解けることを示しましたが、次元が大きくなると、現実的ではありませんでした。一方、最適制御では非常によく利用される制御手法として、LQ制御があります。実は、これは特殊な形のコストと状態方程式を仮定することで、解析的に最適制御入力を計算できるようにしている手法だとみることができます。
そこで、強化学習の話に入る前に、一般的なLQ制御をみて、LQ制御では特殊な状況を想定していたことを感じてみましょう。
まずLQ制御では、コスト$L(x_{t},u_{t})$として、次のような形式のものを考えます。

```math
L(x_{t},u_{t})=\frac{1}{2}\biggr(x_{t}^{\top}Qx_{t}+u_{t}^{\top}Ru_{t}\biggl)
```

これは、$x_{t}$および$u_{t}$の二次形式(Quadratic form、イメージとしては二次関数と同じようなものと思って構いません)と呼ばれる形で、行列$Q$および行列$R$はそれぞれ準正定、正定とLQ制御では仮定するのですが、このとき$x_{t}^{\top}Qx_{t}\geq0$、$u_{t}^{\top}Ru_{t}>0$がなりたち（コストは常に掛かる）、またこれらを最小にする値$x^{\ast}$や$u^{\ast}$を解析的に簡単に求めることができるという特徴があります。
そして、さらにLQ制御では状態方程式が次の形式で表されるとします。

```math
x_{t+1}=f(x_{t},u_{t})=Ax_{t}+Bu_{t}
```

状態$x_{t}$と入力$u_{t}$に対して線形(Linear)な形になっています。
Linearな状態方程式と、Quadratic formをしているコスト関数に対して最適制御を行うので、LQ制御と呼ばれます。
さて、上記のコスト関数と状態方程式を仮定した場合、ベルマン方程式は次のように表されます。

```math
V(x_{k},k)=\min_{u_{k}}\biggr[\frac{1}{2}\biggr(x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k}\biggl)+V(Ax_{k}+Bu_{k},k+1)\biggl]
```

また、終端コストは次のように表されるとします。

```math
\phi(x_{T})=\frac{1}{2}x_{T}^{\top}S_{f}x_{T}
```

ここで、終端コストの$S_{f}$は既知であるものとします。
あとはベルマン方程式を解けばよいのですが、ここで少しトリックを使い、価値関数$V(x_{k}, k)$が次のような形になると仮定して解を求めます。

```math
V(x_{k},k)=\frac{1}{2}x_{k}^{\top}S_{k}x_{k}
```

このような形を仮定して解を求めますが、ベルマン方程式が満たされるのであれば、この仮定は正しかったことになるので問題有りません。
まず、最終時刻$k=T$における状態$x_{T}$の場合を考えると、$V(x_{T},T)=x_{T}^{\top}S_{f}x_{T}$なので、$S_{f}=S_{T}$とすればよく、たしかに最終状態で仮定は少なくとも成り立つことがわかります。
次に、$k \neq T$のときを考えると、ベルマン方程式は次のように表せます。

```math
\begin{align}
V(x_{k},k)=\frac{1}{2}x_{k}^{\top}S_{k}x_{k}
&=\min_{u_{k}}\biggr[\frac{1}{2}\biggr(x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k}\biggl)
+\frac{1}{2}V(Ax_{k}+Bu_{k},k+1)\biggl]\\
&=\min_{u_{k}}\biggr[\frac{1}{2}\biggr(x_{k}^{\top}Qx_{k}+u_{k}^{\top}Ru_{k}\biggl)+
\frac{1}{2}(Ax_{k}+Bu_{k})^{\top}S_{k+1}(Ax_{k}+Bu_{k})\biggl]\\
&=\min_{u_{k}}\biggr[\frac{1}{2}\biggr(x_{k}^{\top}(Q+A^{\top}S_{k+1}A)x_{k}
+u_{k}^{\top}(R+B^{\top}S_{k+1}B)u_{k}\biggl)
+x_{k}^{\top}A^{\top}S_{k+1}Bu_{k}\biggl]\\
\end{align}
```

これに対し、最小化する入力$u_{k}$を求めると次のようになります。

```math
\frac{1}{2}\biggr(x_{k}^{\top}(Q+A^{\top}S_{k+1}A)x_{k}
+u_{k}^{\top}(R+B^{\top}S_{k+1}B)u_{k}\biggl)
+x_{k}^{\top}A^{\top}S_{k+1}Bu_{k}
```

この式は、$R$および$S_{k+1}$がそれぞれ、正定、準正定であれば、$u_{k}$の凸関数であり、今$R$は仮定より正定、$S_{k+1}$は証明は省きますが、最終時刻での$S_{f}$が準正定であれば、任意の時刻$k$でも準正定になることが示せます。したがって、上記を最小化する$u_{k}$は偏導関数が0の点なので、

```math
u_{k}^{\top}(R+B^{\top}S_{k+1}B)+x_{k}^{\top}A^{\top}S_{k+1}B=0
```

から、最適入力$u_{k}^{\ast}$は($R$、$S_{k+1}$は対称行列なので)

```math
u_{k}^{\ast}=-(R+B^{\top}S_{k+1}B)^{-1}B^{\top}S_{k+1}Ax_{k}
```

が、ベルマン方程式を最小化する入力であるとわかります。つまり、$S_{k+1}$と$x_{k}$が分かれば、最適入力が決定できます。$S_{k+1}$は$k+1=T$のとき、$S_{f}$であることと、最適入力の式をベルマン方程式に代入した結果から逐次的に計算できます。具体的には、

```math
\begin{align}
\frac{1}{2}x_{k}^{\top}S_{k}x_{k}
&=\frac{1}{2}\biggr(x_{k}^{\top}(Q+A^{\top}S_{k+1}A)x_{k}
+{u_{k}^{\ast}}^{\top}(R+B^{\top}S_{k+1}B)u_{k}^{\ast}\biggl)
+x_{k}^{\top}A^{\top}S_{k+1}Bu_{k}^{\ast}\\
\end{align}
```

なので、求めた$u_{k}^{\ast}$を代入して、

```math
\begin{align}
x_{k}^{\top}S_{k}x_{k}
&=x_{k}^{\top}\biggr(Q+A^{\top}S_{k+1}A
-A^{\top}S_{k+1}B(R+B^{\top}S_{k+1}B)^{-1}B^{\top}S_{k+1}A\biggl)x_{k} \\
\end{align}
```

左右が一致すればベルマン方程式は成り立つので、次の有名なリカッチ方程式が導出できます。

```math
S_{k}=Q+A^{\top}S_{k+1}A
-A^{\top}S_{k+1}B(R+B^{\top}S_{k+1}B)^{-1}B^{\top}S_{k+1}A
```

これを用いると、各時刻$S_{k}$の計算が$S_{T}=S_{f}$から出発して計算ができ、状態の次元数によらず、$T$から$0$まで計算すれば、あとは各時刻の状態から最適制御入力が決定できます。これがLQ制御です。


# 強化学習

## 強化学習の目的

強化学習の目的は、マルコフ決定過程として定式化される確率過程において、エージェントと呼ぶ意思決定を行う存在が、各時刻で行動した後に得られる報酬$r_{t}$の和の期待値を最大化するような、方策$\pi^{\ast}$を求めることです。
具体的に最大化する目標は次式で表現されます。

```math
J=\mathbb{E}\bigl[\gamma^{T-1}\phi(s_{T})+\sum_{t=0}^{T-1}\gamma^{t}r_{t+1}\bigr]
```

ここで、$\mathbb{E}$は期待値、$\gamma$は割引率と呼ばれる定数で、$0\leq\gamma\leq1$の範囲の値、そして$r_{t+1}$は時刻$t$で行動をした後に得られた報酬です。最適制御とは異なり、確率的に遷移する環境を扱っているため、期待値を最大化する問題を解くことになります。
強化学習では、最適制御で拘束条件として設定した状態方程式に相当する、状態遷移確率が次式で定義されます。

```math
p(s_{t+1}|s_{t},a_{t})
```

状態を$x_{t}$の代わりに$s_{t}$、制御入力$u_{t}$の代わりに行動$a_{t}$で、エージェントが取れる状態と行動を表します。この状態遷移確率は、ある状態$s_{t}$で行動$a_{t}$をとったときに到達する状態が確定せず、あくまでも確率的に決定されるということを表現しています。

## 強化学習版ベルマン方程式

価値関数$V(s_{k},k)$を最適制御のときと同様に次のように定義します。

```math
V(s_{k},k)=\max_{\pi}\mathbb{E}\bigl[\gamma^{T-1-k}\phi(s_{T})+\sum_{t=k}^{T-1}\gamma^{t-k}r_{t+1}\bigr]
```

$\max_{\pi}$は、様々考えられる方策の中から、右辺の期待値を最大化するように行動(=制御入力)することができる方策を選んで、その時の評価関数の値を価値とすることを表しています。
強化学習で定義した価値関数も最適制御の場合と同様に変形していくことで再帰的な形にすることができます。

```math
\begin{align}
V(s_{k},k)
&=\max_{\pi}\mathbb{E}\bigl[\gamma^{T-1-k}\phi(s_{T})+\sum_{t=k}^{T-1}\gamma^{t-k}r_{t+1}\bigr] \\
&=\max_{\pi}\mathbb{E}\bigl[r_{t+1}+\gamma^{T-1-k}\phi(s_{T})+\gamma\sum_{t=k+1}^{T-1}\gamma^{t-(k+1)}r_{t+1}\bigr] \\
&=\max_{a}\mathbb{E}\biggl[r_{t+1}+\gamma\max_{\pi}\mathbb{E}\bigl[\gamma^{T-1-(k+1)}\phi(s_{T})+\sum_{t=k+1}^{T-1}\gamma^{t-(k+1)}r_{t+1}\bigr]\biggr] \\
&=\max_{a}\mathbb{E}\biggl[r_{t+1}+\gamma V(s_{k+1},k+1)\biggr] \\
&=\max_{a}\sum_{s'}p(s'|s_{k},a)\sum_{r'}p(r'|s_{k},a,s')\biggl[r'+\gamma V(s',k+1)\biggr] \\
\end{align}
```

ここで、$p(r'|s_{k},a,s')$は状態$s_{k}$で行動$a$を選択し、$s'$に移ったときに得られる報酬の確率を表しています。
最適制御のときと形は変わっていますが非常に似た形が出てきました。これもやはりベルマン方程式とよばれます。実際、確率的な要素がなくなれば(そして$\gamma=1$なら)最適制御のベルマン方程式と同じです。
実際の強化学習では上のような形の式ではなく、終端状態を吸収状態とよぶ、時間の経過によらず状態遷移せず、得られる報酬もすべて0とする特別な状態を仮定することで、終端時刻を無限にしたときの極限の形

```math
\begin{align}
V(s)=\max_{a}\sum_{s'}p(s'|s,a)\sum_{r'}p(r'|s,a,s')\biggl[r'+\gamma V(s')\biggr]
\end{align}
```

を利用して問題が解かれることが多いです。この後の説明もこちらの形を利用します。
さて、強化学習でも、$p(s'|s_{k},a)$、$p(r'|s_{k},a,s')$と終端状態での価値関数$V(s_{T},T)$を与えれば、動的計画法を利用することで価値関数を求めることが可能です。そして、最適制御と同様に、価値関数が求まれば、あとはベルマン方程式に従って行動$a$を選択することが求める最適方策になります。
しかしながら、強化学習はよく試行錯誤的に学習すると言われますが、ここまでは学習の要素があまり見当たらず、最適制御とほとんどなにも変わりません。そこで次に最適制御との違いをみるために、強化学習の学習に関連する部分を見ていくことにしましょう。

## モデルフリー強化学習

強化学習の最大の特徴は名前にもある通り、なんと言っても学習をすることができるところにあります。学習という言葉は広いのでいろんな解釈が考えられますが、ここでは環境がどのように振る舞うかわからない状態から、データをサンプルすることで最適な方策を得ることを「学習した」と考えることにして話をすすめます。
さて、環境の振る舞いがわからないと書きましたが、強化学習では、状態遷移確率$p(s'|s_{k},a)$と報酬の分布$p(r'|s_{k},a,s')$を環境の振る舞いと考え、この２つが未知であることとして問題を解くことを考えます。
一見不可能なようにも見えますが、強化学習のエージェントは、自身がどの状態$s\in S$にいるか、どんな行動$a\in A$をとれるか、受け取った報酬$r$はいくつか、目標状態に到達したかといったことは知ることで、最適な方策を得ることができるようになります。
状態遷移確率$p(s'|s_{k},a)$と報酬の分布$p(r'|s_{k},a,s')$といったモデルを知ることなく学習が行われるので、モデルフリー強化学習と呼びます。

### 強化学習問題で解決しなければいけないこと

強化学習の目標は依然として変わっていないので、次を最大化する方策$\pi$を求めることを目指します。

```math
J=\mathbb{E}\bigl[\gamma^{T-1}\phi(s_{T})+\sum_{t=0}^{T-1}\gamma^{t}r_{t+1}\bigr]
```

しかし、状態遷移確率$p(s'|s_{k},a)$と報酬の分布$p(r'|s_{k},a,s')$の２つが未知なので、動的計画法はもはや利用することができません。つまり、状態$s$や行動$a$を与えたときの期待値がいくつになるか計算できません。これは2つの問題を引き起こします。一つは仮にある方策$\pi$を与えたとしても、その期待値が直接的にはいくつになるか計算できないということ、そしてもう一つが、期待値が不明である限り方策の良さを比較できず、$\max_{\pi}$を達成する方策がどれかこのままではわからないということです。
強化学習は、試行錯誤して学習すると形容されることがありますが、環境内で行動をし、データ$(s_{0},a_{0},r_{0},s_{1},a_{1},r_{0},\dots)$を集めることが問題設定上可能です。
そこで強化学習では、今述べた２つの問題を、データをサンプルし、そのサンプルしたデータから解決することを試みます。ここでは、モンテカルロ法とSARSAと呼ばれる強化学習手法を2つ紹介します。

### モンテカルロ法

モンテカルロ法のアイデアは非常にシンプルです。まず、適当な確率的方策$\pi(a|s)$を作成し（例えばランダム）、最初の状態からタスクの終端状態に到達するまで（これをエピソードと呼ぶ）の全部の状態、行動と得られた報酬$(s_{0},a_{0},r_{0}\dots,s_{T})$をたくさん(ここでは$N$エピソード分)記録します。
そして、この記録したエピソードのデータをデータサンプル$D=\\{(s_{0,1},a_{0,1},r_{0,1}\dots),(s_{0,2},a_{0,2},r_{0,2}\dots),\dots,(s_{0,N},a_{0,N},r_{0,N}\dots)\\}$を使って、行動価値関数$Q(s,a)$と呼ばれる関数を近似することを試みます。行動価値関数は価値関数とほぼ一緒なのですが、

```math
Q(s,a)=\mathbb{E}\biggl[r'+\gamma V(s',k+1)\big|a\biggr]
```

と表現される量で、状態$s$で行動$a$を起こした場合に得られる報酬の総和の期待値を指します。価値関数$V(s)$との差がわかりにくいですが、$Q$と$V$は次のような関係になっています。

```math
V(s)=\sum_{a}\pi(a|s)Q(s,a)
```

簡単のために終端状態の価値$V(s_{T})=\phi(s_{T})=0$とすると、今、適当に設定した方策$\pi$の元でのある時刻$t$における状態$s_{t}$の価値$Q^{\pi}(s_{t},a_{t})$は、

```math
\begin{align}
Q^{\pi}(s_{t},a_{t})=\mathbb{E}\bigl[r_{t}+\gamma{r_{t+1}}+\cdots+\gamma^{T-1}{r_{T}}\big|a\bigr]
\end{align}
```

なので、大数の法則から次のように近似できます。

```math
\begin{align}
Q^{\pi}(s_{t},a_{t})\approx\frac{1}{N}\sum_{D}(r_{t,i}+\gamma{r_{t+1,i}}+\cdots+\gamma^{T-1}{r_{T,i}})
\end{align}
```

実際に求めたいのは適当な方策$\pi$の価値関数ではなく、得られる報酬の総和の期待値を最大化するような最適方策$\pi^{\ast}$（とその行動価値関数)なので、モンテカルロ法では、次に、今得られた行動価値関数$Q^{\pi}$を使って、$\pi$を次のように変更します。

```math
\begin{align}
\pi^{new}(s)={\arg\max}_{a}Q^{\pi}(s,a)
\end{align}
```

証明は省きますが、上のように方策を更新すると方策改善定理とよばれる定理により、$\pi^{new}(s)$は一つ前の方策$\pi(s)$よりも、得られる報酬の総和が大きい方策になっています。
このように、方策$\pi$でデータを集め、行動価値関数を計算、方策を改善を繰り返すことで、最適な方策$\pi^{\ast}$に漸近的に近づきながら最適方策$\pi^{\ast}$を求めるのがモンテカルロ法です。

### SARSA

SARSAもモンテカルロ法と同様に行動価値関数$Q(s,a)$を求めつつ、方策を更新していくことで最適方策を求めることを目指します。まず、モンテカルロ法では、次のような行動価値関数を次のように解釈してデータから価値を推定していました。

```math
\begin{align}
Q^{\pi}(s_{t},a_{t})=\mathbb{E}\bigl[r_{t}+\gamma{r_{t+1}}+\cdots+\gamma^{T-1}{r_{T}}\big|a_{t}\bigr]
\end{align}
```

SARSAでは代わりに、これと等価な次の式を利用して行動価値関数を近似しながら、方策を更新していき、最適方策を得ることを目指します。

```math
\begin{align}
Q^{\pi}(s_{t},a_{t})=\mathbb{E}\bigl[r_{t}+\gamma{\sum_{a'}\pi(a'|s')Q^{\pi}(s',a')}\big|a_{t}\bigr]
\end{align}
```

具体的には、ある方策$\pi$で行動を行うエージェントがデータサンプル$(s_{t},a_{t},r_{t},s_{t+1},a_{t+1})$を得たとき、次式にしたがって、行動価値関数を更新します。

```math
\begin{align}
Q(s_{t},a_{t})\leftarrow{Q(s_{t},a_{t})+\alpha\bigl[r_{t}+\gamma{Q(s_{t+1},a_{t+1})}-Q(s_{t},a_{t})\bigl]}
\end{align}
```

$\alpha$は直感的には更新の割合を決めている係数で、$\alpha=0$のときには何も更新せず、$\alpha=1$のときは、次の状態の推定値を信用して更新します。また、$\sum$や$\pi$が消えていますが、これはサンプルされたデータから更新しているためです。サンプルとして必要なデータが$(s_{t},a_{t},r_{t},s_{t+1},a_{t+1})$の5つであるため、SARSAと呼ばれます。
SARSAでは、すべての状態と行動を無限回観測しつつ、その極限で方策$\pi$が$\arg\max_{a}Q(s,a)$となるように変化させたとき、極限(実用上は行動価値関数に変化がなくなったとき)で最適方策が得られることが知られています。
そこでSARSAでは確率$\epsilon$で探索的なランダム行動、$1-\epsilon$で推定中の行動価値関数に従って${\arg\max}_{a}Q(s,a)$を行動として選ぶ$\epsilon$グリーディ方策がよく利用されます。
具体的には、最初は探索的な行動をとるため$\epsilon=1$から始めて、徐々に$\epsilon=0$に近づけながら、データを収集、行動価値関数を更新することが多いです。

# おわりに

いかがでしたでしょうか。
最適制御からはじまり、強化学習まで見てきましたが、結局のところ、両者はどちらも同じで、ある量を最小化/最大化する制御入力/方策を求める手法だと感じられたのではないでしょうか？
また、最適制御はモデルを利用することで解析的（近似的の場合もありますが)に制御入力を計算しようと試みるのに対して、強化学習はモデルが未知という状態からデータを得ることで方策を決定しようとするといった違いも見えたのではないでしょうか？
最後までお読みいただきありがとうございました。この記事が最適制御と強化学習という2つのアルゴリズムに対して、皆様の興味と理解を少しでも促進できていたら嬉しいです。

# 参考文献

- 非線形最適制御入門 (2011)、大塚敏之、コロナ社
- Richard S. Sutton and Andrew G. Barto (2018), Reinforcement Learning an Introduction, The MIT Press
- 森村哲郎 (2019)、強化学習、講談社
- 上田隆一 (2019)、詳解確率ロボティクス、講談社