概要

前回は有限MDPにおける基本的な問題設定と報酬に関する定式化を行った。今回はそれを受け、ポリシーおよび価値関数をベルマン方程式として定式化する。また、同様にそれらの最適解についても考え、厳密解を求めることの限界を示す。

目次

ポリシーと価値関数
最適ポリシーと最適化値関数
最適性と近似
有限MDPまとめ

3.4まで

生涯報酬(の現在価値)

G_t = R_{t+1} + \gamma G_{t+1}\ \ \ \ (3.9)

3.5 ポリシーと価値関数

ほとんどの強化学習アルゴリズムは、その状態がいかに「良い」かということを示す価値関数の推定を行う。この価値関数は特定の行動規範(=ポリシー)に対応して定義される。

ポリシー

ポリシーとは状態から行動確率へのマッピングである。つまり、状態によって条件付けしたときの行動の確率分布であり、時刻tにおいて$S_t = s$のとき$A_t = a$となる確率は$\pi(a|s)$と表される。

状態価値関数

毎時刻ポリシー$\pi$で行動をとるときの、状態sにおける価値$v_{\pi}(s)$は$\pi$の分布(および報酬の分布)にける期待値で表される。

v_{\pi}(s) \doteq \mathbb{E}_{\pi,p}\left[G_{t} | S_{t}=s\right]=\mathbb{E}_{\pi,p}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} | S_{t}=s\right], \text { for all } s \in \mathcal{S}

ただし、終了状態においてはいずれにせよ0であることに注意する。この本ではこの$v_{\pi}$のことを$\pi$に対する状態価値関数(state-value function)と呼ぶ。

行動価値関数

同様にして、状態sにおいて行動aをとる価値を$q_{\pi}(s,a)$を以下のように定義できる。

q_{\pi}(s, a) \doteq \mathbb{E}_{p}\left[G_{t} | S_{t}=s, A_{t}=a\right]=\mathbb{E}_{p}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} | S_{t}=s, A_{t}=a\right]

この本ではこの$q_{\pi}$のことを$\pi$に対する行動価値関数(action-value function)と呼ぶ。

ベルマン方程式

価値関数の基本的な性質は(3.9)式と同様に再帰的な関係を持つ式として表されることである。

\begin{aligned} v_{\pi}(s) & \doteq \mathbb{E}_{\pi,p}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi,p}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\sum_{a\in A(s)} \pi(a | s) \sum_{s^{\prime}} \sum_{r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma \mathbb{E}_{\pi,p}\left[G_{t+1} | S_{t+1}=s^{\prime}\right]\right] \\ &=\sum_{a\in A(s)} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right], \quad \text { for all } s \in \mathcal{S} \end{aligned}

このベルマン方程式は唯一解を持つ。
このような式を$v_{\pi}$のベルマン方程式と呼ぶ。現在の状態価値と後続の状態価値の関係を表す式となる。また、このような関係は下のような図を用いるとわかりやすい。

○が状態、●が行動を表していて、$\pi$によって○からどの●に遷移するかを決定する。そして、●の行動を起こした時に環境がどのような反応をして報酬を返し、次の状態に遷移するかを表す。この図はバックアップダイアグラムと呼ばれ、強化学習の根幹となる更新操作やバクアップ操作の基礎となる関係性を示している。

Example3.6 Gridworld

以下の図は、単純な有限MDPとして表されるgridworldを表す。

状態：グリッドの位置
行動：東西南北のどれか
報酬
- 四角の外に出たら-1
- A:+10
- B:+5
- そのほか０
次の状態：
- Aではどれを選ぼうがA'へ移動
- Bではどれを選ぼうがB'へ移動
- 外に出る選択肢を選んだらその場にとどまる
- そのほかは１マスその向きへ移動

仮にエージェントがどの行動も同一な確率でランダムに選択するポリシーを持つとすると、状態価値は右図のように推定できる。

ここで面白い性質は、

Aは10より小さい
Bは5より大きい

という結果である。これは後に続くA'およびB'の状態から受け取れる報酬の期待値の違いが影響していると考えられる。

Example 3.7 Golf

次の例はゴルフである。簡単のため、以下のようにMDPとして定義する。

状態：フィールド内での位置
行動：
- どの方向に打つか
- どれくらいの強さで打つか
- ドライバーorパター
報酬
- 行動するごとに-1
- ホールに入ったら0
次の状態：
- 狙ったところに正確に打つ
- フェアでの飛距離はドライバー>パター
- グリーンでの飛距離はドライバー<パター
- バンカーに入ったらパターでは抜け出せず留まる

以下の図はこの有限MDPにおいて、パターしか使わないというポリシーを決めると、ピン位置における行動価値関数は以下の図のようになる。

3.6 最適ポリシーと最適化値関数

簡単に言えば、強化学習のタスクは長期的な報酬を最大化するポリシーを決めることだと言える。有限MDPにおいては、以下で示すような方法によってその最適なポリシーを定義する。

ポリシーの比較と最適ポリシー

二つのポリシー$\pi,\pi'$があり、$\forall s \in S, \ v_{\pi}(s) \geq v_{\pi'}(s) $であるとき$\pi \geq \pi'$と表す。
また、有限MDPsにおいて、必ず$\exists \ \pi_{\ast}, \forall\ \pi,\ \pi_{\ast} \geq \pi$が成り立つ。この$\pi_{\ast}$を最適ポリシー(optimal policy)と呼ぶ。

最適状態価値関数

以下のように$v_{\ast}$を最適状態価値関数(optimal state-value function)と定義する。

v_{\ast}(s) \doteq \max_{\pi} v_{\pi}(s), \ \ \text{for all} \  s \in S.

つまり、$v_{\ast} = v_{\pi_{\ast}}$である。

最適行動価値関数

同様に、最適行動価値関数(optimal action-value function)を以下のように定義する。

q_{\ast}(s,a) \doteq \max_{\pi} q_{\pi}(s,a), \ \ \text{for all}\ s \in S\  \text{and} \ a \in A(s).

また、最適状態価値関数との以下のような関係が導かれる。

\begin{aligned}
q_{*}(s, a)
&=\max_{\pi} q_{\pi}(s,a) \\
&= \max_{\pi} \mathbb{E}_p\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s, A_{t}=a\right]\\
&= \mathbb{E}_p\left[R_{t+1}+\gamma v_{*}\left(S_{t+1}\right) | S_{t}=s, A_{t}=a\right]
\end{aligned}

最適価値関数でのベルマン方程式

以上の定義および関係式から最適状態価値関数と最適行動価値関数のベルマン方程式を導く。

\begin{aligned}
v_{\ast}(s) 
&= \max_{\pi} v_{\pi}(s)\\
&= \max_{\pi}\mathbb{E}_{\pi,p}\left[G_t |S_t=s, A_t = a\right]\\
&= \max_{\pi} \sum_{a\in A(s)}\pi(a|s)\mathbb{E}_{p}\left[G_t |S_t=s, A_t = a\right]\\
&= \max_{a\in A(s)}\mathbb{E}_{p}\left[G_t |S_t=s, A_t = a\right]\\
&= \max_{a\in A(s)}q_{\ast}(s,a)\\
&= \max_{a\in A(s)}\mathbb{E}_p\left[R_{t+1}+\gamma v_{*}\left(S_{t+1}\right) | S_{t}=s, A_{t}=a\right]\\
&= \max_{a\in A(s)}\sum_{s',r}p(s',r|a,s) \left[r+\gamma v_{*}(s') | S_{t}=s, A_{t}=a\right]\ \ \ \  ...(\ast)
\end{aligned}

1行目から2行目は状態価値関数の定義。
2行目から3行目は期待値の計算を展開。
3行目から4行目は、最も期待報酬が高い行動に確率1で動く$\pi(a|s)$のときに最大値をとることを用いる。
4行目から5行目は行動価値関数の定義。
5行目から6行目は上記の関係式($\ast$)。
6行目から7行目は期待値の計算を展開。

また、行動価値関数のベルマン方程式は以下のように導かれる。

\begin{aligned}
q_{\ast}(s,a) 
&=\max_{\pi} q_{\pi}(s,a)\\
&=\mathbb{E}_p\left[R_{t+1}+\gamma v_{*}\left(S_{t+1}\right) | S_{t}=s, A_{t}=a\right]\\
&=\mathbb{E}_p\left[R_{t+1}+\gamma \max_{a'}q_{\ast}\left(S_{t+1},a'\right) | S_{t}=s, A_{t}=a\right]\\ 
&= \sum_{s',r}p(s',r|a,s)\left[r + \gamma\max_{a'}q_{\ast}(s',a')\right]
\end{aligned}

1行目から2行目は関係式($\ast$)。
2行目から3行目は状態価値関数の5行目の結果を使う。
3行目から4行目は期待値の計算を展開。

以上の結果はバックアップダイアグラムを用いても説明ができる。
$v_{\ast}(s)$は

最適ベルマン方程式の性質

上記のような、最適状態価値関数や最適行動価値関数のベルマン方程式を最適ベルマン方程式(Bellman optimality equation)と呼ぶ。この最適ベルマン方程式は、一つの状態について、$|S|$元の非線形方程式を作り出す。つまり、最適解は$|S|$元、$|S|$本の連立非線形方程式を解くことによって求めることができる。

最適状態価値関数や最適行動価値関数が求められれば、ポリシーも自動的に決定する。なぜなら、このベルマン方程式によって得られる解は、短期的な最適解をgreedyに「活用」することが長期的な最適となっていることが保証されているからである。

最適状態価値関数か最適行動価値関数を求めることの差は動的な環境の情報を必要とするか否かである。
最適状態価値のみであるとき環境の情報が必要であるが、最適行動価値を知っていればエージェントは環境の情報を知っている必要がない。

Example 3.8

ゴルフの例における最適行動価値関数は以下のような図である。

これより、ティーからの最適な行動は２回のドライバーと1回のパターを打つことだと言える。

Example 3.9

(前回)Example3.4で紹介されたリサイクリングロボットについて最適状態価値関数に関するベルマン方程式を導く。
(状態・行動・報酬は以下の表)

この表と最適状態価値関数のベルマン方程式を用いると、状態"high"における価値関数を以下のように解くことができる。

\begin{aligned} v_{*}(\mathrm{h}) &=\max \left\{\begin{array}{l}p(\mathrm{h} | \mathrm{h}, \mathrm{s})\left[r(\mathrm{h}, \mathrm{s}, \mathrm{h})+\gamma v_{*}(\mathrm{h})\right]+p(1 | \mathrm{h}, \mathrm{s})\left[r(\mathrm{h}, \mathrm{s}, 1)+\gamma v_{*}(1)\right] \\ p(\mathrm{h} | \mathrm{h}, \mathrm{w})\left[r(\mathrm{h}, \mathrm{w}, \mathrm{h})+\gamma v_{*}(\mathrm{h})\right]+p(1 | \mathrm{h}, \mathrm{w})\left[r(\mathrm{h}, \mathrm{w}, 1)+\gamma v_{*}(1)\right]\end{array}\right\} \\ &=\max \left\{\begin{array}{l}\alpha\left[r_{\mathrm{s}}+\gamma v_{*}(\mathrm{h})\right]+(1-\alpha)\left[r_{\mathrm{s}}+\gamma v_{*}(1)\right] \\ 1\left[r_{\mathrm{w}}+\gamma v_{*}(\mathrm{h})\right]+0\left[r_{\mathrm{w}}+\gamma v_{*}(1)\right]\end{array}\right\} \\ &=\max \left\{\begin{array}{l}r_{\mathrm{s}}+\gamma\left[\alpha v_{*}(\mathrm{h})+(1-\alpha) v_{*}(1)\right] \\ r_{\mathrm{w}}+\gamma v_{*}(\mathrm{h})\end{array}\right\} \end{aligned}

また同様に、状態"low"についても、

v_{*}(1)=\max \left\{\begin{array}{l}\beta r_{\mathrm{s}}-3(1-\beta)+\gamma\left[(1-\beta) v_{*}(\mathrm{h})+\beta v_{*}(1)\right] \\ r_{\mathrm{w}}+\gamma v_{*}(1) \\ \gamma v_{*}(\mathrm{h})\end{array}\right\}

というように解くことができる。
$r_s,r_w,\alpha,\beta,\gamma$を適切に定めれば$v_{\ast}(h),v_{\ast}(l)$の値が１組求められる。

Example3.10

Example3.6で挙げたGridworldについて状態価値を求めると以下のようになる。

3.7 最適性と近似

以上の例では最適ベルマン方程式を明示的に解くことによって、最適な状態に動くように最適ポリシーを見つけることができ、強化学習問題を解くことができている。しかし、この方法は以下の3つが必要となるため、多くの場合有用ではない。

確実に環境がどう振る舞うかを知っている。
十分な計算リソースがある。
マルコフ特性を満たす。

例えばチェスやバックギャモンなどは1,3を満たすものの、$10^{20}$以上の状態が存在するため、２において現実的でない。
つまり、現実の問題を解けるような強化学習アルゴリズムを考えるにはこのベルマン方程式の近似解を求める必要がある。このような近似解法を続く紹介していく。

また、計算に使うメモリも大きな問題である。Gridworldやリサイクルロボットの問題は状態が多くないため、全状態に関する価値を計算し、表を作ることができた。しかし、状態の数が膨大であったり、連続な値として表されるとき、表を作ることはできず、パラメータで決定された関数の形でコンパクトに表す必要がある。

このフレーミングは近似解法における大きな問題であると同時にあるメリットももたらす。それは、必要な状態、すなわちよく発生する状態のみを学習することができるという点である。この点は強化学習とそのほかの手法が区別する一つの要素である。

3.8 まとめ

強化学習：　エージェントが目標を達成するためにどのように行動するかを相互作用から学習すること
行動：エージェントによって行われる選択
状態：選択を行う状況
報酬：選択を評価するための基準
ポリシー：状態の関数として行動を選択する確率的なルール
MDP：状態の遷移確率が定式化される強化学習
有限MDP：有限の状態、行動、報酬を設定されたMDP
リターン：累積将来報酬の関数(タスクの性質や割引率によって様々)
価値関数：あるポリシーにおいて状態もしくは状態と行動の組に対して定義されるリターンの期待値
最適ポリシー：価値関数が最大化されるようにとるポリシー
最適価値関数：最適ポリシーのときの価値関数(MDPにおいて唯一解を持つ)
ベルマン方程式：再現在の価値関数を次のタイムステップでの価値関数で再帰的に表された式
最適ベルマン方程式：最適価値関数に関するベルマン方程式(原理的には解くことができるが、現実的には近似が必要)