素人のための本格的強化学習 #4 強化学習基礎理論① マルコフ決定過程とベルマン方程式

強化学習理論ことはじめ

今回は、強化学習の基礎理論であるベルマン方程式を中心に解説していく。
抽象度の高い数学的な話は避けられず、数学が特別好きだという方以外は敬遠しがちな内容だが、個人的には「強化学習を知っている」かどうかの基準は、こういう話を知っているかどうかだと思っている。すぐに理解するのは難しいが、慣れの面もあるのでなるべく根気よく論理展開を追ってほしい。
どうしても数式が多くなるが、Q学習を知っている状態なら、前回示した実例において各変数が具体的に何を表すかの対応を見ていくことで、イメージがわきやすくなると思う。

多少脱線になるが、強化学習に限らず、sklearn, tensorflow, kerasといった機械学習ライブラリは、どのようなロジックで学習が可能になるのかを内部的に包み込んで隠してくれる。一から実装する必要がなくなるのは便利だが、根底のロジックを一度も見たことがない状態でこのようなライブラリを用いて機械学習を扱うのは個人的には危険だと思っている。理論を厳密な意味で全て理解する必要は必ずしもないが、大きな流れくらいは知っておくべきだ。自動車をカスタマイズするときに、自動車にただ乗れるだけではダメで、少なくとも主要な部品の役割くらいは知っていないといけないのと同じである。

以降では、ある環境における状態s(state)と、Agentが観測できる情報obs(observation)を同じものとして話を進める。

状態、行動、報酬

まあここはほぼ自明なのであえて説明もいらないかもしれないが、一応定義を書いておく。興味がなければこの項は読み飛ばしてもらっても大きな問題はない。

ある環境における状態集合をS、行動集合をAとする。その個々の要素をそれぞれ小文字のs, aとする。

一般の強化学習環境では、Sの要素数をmとして、それぞれの$${s_{i}}$$(i=1, 2, ..., m)に対して固有の$${a_{i1}}$$, $${a_{i2}}$$, ..., $${a_{in}}$$が存在するため、Aの要素全体は
$${\sum_{i=1}^{m}\sum_{j=1}^{n}a_{ij}}$$
となる。

4x4のFrozenLakeの例なら、sはマス目の座標に相当し、Sの要素数は16である。aは上下左右の移動方向に相当し、これをそれぞれ$${a_{1}}$$〜$${a_{4}}$$とおくと、どのsも共通の$${a_{1}}$$〜$${a_{4}}$$が対応している点で一般的なactionの集合としては特殊である。この点でもFrozenLakeの例に対して(s, a)の組み合わせを2次元の表として表現するQTableが適していたことがわかる。

r(s, a)は状態sで行動aを取った時に環境からフィードバックされる報酬=rewardで、エピソード全体における総報酬の期待値$${E(r_{total})}$$を最大化することが強化学習の目的である。
厳密には、学習そのものに用いるrは、環境から与えられるrと必ずしも同じである必要はない。後者を外的報酬$${r_{e}}$$ (eはextrinsic)とし、学習で固有に設定する内定報酬$${r_{i}}$$ (iはintrinsic)を考えると、学習に用いるreward$${r_{l}}$$は
$${r_{l} = r_{e} + r_{i}}$$
と表せる。
(特に$${r_{e}}$$が疎な環境(アクションゲームやRPGのゴールでのみ報酬が与えられる場合など)では、内定報酬$${r_{i}}$$の設定が重要となることがあり、curiosity driven explorationなどの巧みな手法も考案されている。
前回のQ学習の例では、常に$${r_{i} = 0}$$として学習が成功したので特に意識することはなかったが、学習が進めにくい環境では$${r_{e}}$$と$${r_{i}}$$を意識する必要がある。)

行動ポリシー

s, a, rについて話したが、ここまではQ学習を見た人なら特に厳密な議論をしなくても直感的にイメージできるだろう。

行動ポリシーは、ほぼ名前の通りだが、各状態に対して特定の確率分布で行動を選択するロジックを表す。
ある状態sにおいて行動ポリシー$${\pi}$$で行動選択したとき、考えられる可能な行動$${a_{1}}$$, $${a_{2}}$$, ...$${a_{n}}$$から$${a_{i}}$$が選択される確率を$${\pi(a_{i} | s)}$$と定義する。

マルコフ決定過程

Wikipediaの説明を見てみると、

A Markov decision process is a 4-tuple(S, A, P, R)...

とあり、これまた集合論のお出ましである。
正直定義はこれそのままで、説明も何もないのだが、もう少し補足すると、「状態s, 行動a, に対して報酬r, 次の状態s'が(確率分布として)定まる環境」のことで、これは一般に強化学習に用いることのできる環境そのものである。

マルコフ性

上記のマルコフ決定過程で表せる環境のように、(r, next_s)が直前の(s, a)にのみ依存する性質を「マルコフ性」という。
じゃあマルコフ性を満たさない環境って何？というと、直前の状態sだけでなくそれ以前の状態も状態遷移確率に影響したり、過去の行動も影響したりする場合がそうだ。
具体的には、「2個のサイコロを振った時、出目の和を順番に記録していき、その配列の中央値をsとする」例は、マルコフ性を満たさない。過去の出目が[3, 4, 10, 2, 12]の場合と、[2, 2, 12, 4, 11]の場合では、どちらもs=4だが、次の出目の合計が11だった場合、前者ではs=7, 後者ではs=7.5と異なる。
一方、配列の最大値をsとする場合は、当然直前のsのみを参照すれば次の出目の合計に対してnext_sが一意に求まるので、マルコフ性を満たす。

マルコフ性を満たすかどうかで、行動ポリシーの包含関係はどう変わるか、最善の行動ポリシーはどうなるか、などのより高度に数学的な議論に興味のある数学強(狂?)者の方々は、強化学習などの書籍を参照してほしい。

重要なことは、基本的には「マルコフ性を満たす」ことが強化学習の前提である、ということである(詳細は本記事では割愛するが、マルコフ性を満たさない=履歴依存性の環境では(r, next_s)を求めるのに必要な情報の組み合わせ数が爆発的に増えることに起因する)。強化学習を実際に行う前には、検討する環境がマルコフ性を満たすかどうか、満たさないならばマルコフ性を満たす環境にどう近似するか、といったことを念頭に置く必要がある。
このあたりも、「中身はよく分からないけど機械学習ライブラリでなんとなく学習してみたが、うまく学習が進まない」場合に適切に対処できない部分だ。基礎を何も知らない人がハイパーパラメータの意味をなんとなく調べた程度では適切な学習などできない、ということは知っておいていただきたい。

状態価値関数、行動状態価値関数

状態価値関数は、状態s(時刻t)において、特定の行動ポリシー$${\pi}$$に従った結果、時刻tからエピソード終了までに受け取る総報酬の期待値で定義され、 $${v_{\pi} (s)}$$で表す。

行動状態価値関数は、状態s(時刻t)で行動aを選択し、その後はすべて特定の行動ポリシー$${\pi}$$に従った結果、時刻tからエピソード終了までに受け取る総報酬の期待値で定義され、$${q_{\pi} (s, a)}$$で表す。
状態価値関数との違いは、時刻tのときだけ行動ポリシーに関係なく行動aを選択した、という点である。どちらも「報酬の期待値」を表す、という点で、数式で比較することもできる。

Q学習の例でいうと、q(s, a)は、時刻t+1以降においてQTableで最善と考えられる行動を選択し続ける行動ロジック(epsilon=0でのget_action(obs))で受け取る$${E(r)}$$、というわけだ。

具体的なコード例で示すと若干わかりやすいかもしれない。以下では、任意の(s, a)の組み合わせに対してreward, next_sが一意に定まり、かつ任意のstateに対する行動ポリシーの結果も一意な(deterministicな)環境を前提とする。

#  行動ポリシー  
def policy(state):
    # ... some logic
    action = ...
    
    return action
    
    
# 状態価値関数
def calc_value(state, done, policy):
    value = 0
    
    while not done:
        action = policy(state)
        state, reward, done, _ = env.step(action)
        value += reward
           
    return value


# 行動状態価値関数
def calc_q(state, done, policy, action):
    if done: return 0
    
    q = 0
    
    #  以下の2行が状態価値関数との違い
    state, reward, done, _ = env.step(action)
    q += reward
    
    while not done:
        action = policy(state)
        state, reward, done, _ = env.step(action)
        q += reward
    
    return q

この処理の中で、policy(state)やenv.step(action)の結果を確率的にして一般化すると、valueやqも期待値で表すことになり、上記の定義となるわけだ。

ベルマン方程式

行動ポリシーの定義から、特定の状態sに対し行動ポリシー$${\pi}$$に従って行動した結果、行動aを選択する確率は、$${\pi (a | s)}$$である。
状態sで行動aを選択した結果、報酬rを受け取り、次の状態s'に遷移する確率を$${p(r, s' | s, a)}$$で表現すると、状態価値関数$${V_{\pi} (s)}$$は、次の式で表せる。

$${V_{\pi} (s) = \sum_{a}^{} \pi (a | s) \sum_{(r, s')}^{} p(r, s' | s, a)\{r + V_{\pi} (s')\}}$$  (4.1)

これが、「状態価値関数に対する(補正前の)ベルマン方程式」である。
シグマ式と条件付き確率が合わさってなんのこっちゃ？となった人は、前述のdeterministicな環境で考えてみるとよい。

$${V_{\pi} (s) = r + V_{\pi} (s')}$$  ($${\pi (a | s) = p(r, s' | s, a) = 1}$$)  (4.2)

状態sで行動ポリシー$${\pi}$$に従うと必ずaが選択され、その結果必ずrの報酬を受け取って状態s'に遷移する前提なら、状態価値関数の意味は非常にわかりやすい。「今からエピソード終了までにもらえる報酬は、次の報酬rと、それ以降からエピソード終了までにもらえる報酬の和だよ」という当たり前のことを言っているだけだ。これを確率的に拡張したのが(4.1)のベルマン方程式だ。
つまり、(4.1)はおおざっぱにいうと(数学的には微妙な表現ではあるが)、

$${V_{\pi} (s) = E_{\pi} \{r + V_{\pi} (s')\}}$$

という期待値のイメージで捉えればよいと思う。

ここで、(4.1)の両辺に対し1stepだけ行動aで進める場合を考えると、

$${q_{\pi} (s, a) = \sum_{(r, s')}^{} p(r, s' | s, a)\{r + V_{\pi} (s')\}}$$  (4.3)

となることがわかる。これが「行動状態価値関数に対する(補正前の)ベルマン方程式」である。これも、deterministicな環境に単純化すると、

$${q_{\pi} (s, a) = r + V_{\pi} (s')}$$  ($${p(r, s' | s, a) = 1}$$)  (4.4)

となる。状態価値関数の場合とほぼ同じ形だ。

(4.1), (4.3)の将来の報酬期待値$${V_{\pi} (s')}$$を、それぞれ割引率γを考慮して補正した式は次の通りで、これが正式なベルマン方程式だ。

$${V_{\pi} (s) = \sum_{a}^{} \pi (a | s) \sum_{(r, s')}^{} p(r, s' | s, a)\{r + \gamma V_{\pi} (s')\}}$$  (4.5)

$${q_{\pi} (s, a) = \sum_{(r, s')}^{} p(r, s' | s, a)\{r + \gamma V_{\pi} (s')\}}$$  (4.6)

できる限り噛み砕いた説明をしたかったが、それでも抽象的な議論と数式は避けられず、なかなかイメージが掴めなかった、という方もいるかもしれない。ただ、単純に時間と経験が解決する部分も大きいので、どうか挫折しないでいただきたい。実際私もこのあたりの話は書籍を何度も読んで、実装を繰り返しながら数週間かけて少しずつ理解していった。
次は、Q学習でこれらがどのように活用されているかを見ていくこととする。

次回: #5 強化学習基礎理論② Q学習をベルマン方程式で紐解く