Q-learningの収束性について

はじめに#

このエントリは機械学習の数理 Advent Calendar 2018の12日目の記事の転載です。

今回はよく知られている強化学習のアルゴリズム: Q-learningについて説明したいと考えています。追記程度でSoft Q-learningの基礎となっているSoft Bellman方程式が縮小写像になっていることを示します。

有限マルコフ決定過程#

以下の条件を満たす5つの組 $\mathcal{P} = (\mathcal{S}, \mathcal{A}, \mathcal{R},p, \pi)$ を有限マルコフ決定過程と呼び，その $p$ を特に遷移確率関数もしくは単に遷移確率と呼ぶ．そして $\pi$ を方針分布または方針と呼ぶ．

$p(s_0, a_0, r_0, \cdots, s_T, a_T, r_T) = p(s_0) \prod_{t=0}^{T} \pi(a_t|s_t)p(s_{t+1}, r_{t}|s_t,a_t)$
状態 $s, s' \in \mathcal{S}$ , 行動 $a \in A$ , 報酬 $r \in \mathcal{R}$ .
報酬関数 $r(s,a) = \sum_r r p(r|s,a)$

リターン(割引付き報酬の総和)を $G_t = \sum_{t=0}^{\infty} \gamma^t r_t$ とする．このとき $r_t = r(s_t,a_t), \gamma \in [0, 1]$ とする．続いて価値関数の定義をしていく．

価値関数#

期待リターンとして状態価値関数を

V_\pi(s) = \mathbb{E_{\pi,p}} \left[\sum_{t=0}^{T} \gamma^t r_t \middle| s_0 = s \right],

と定義し， $Q$ 関数(行動価値関数)を

Q_\pi(s, a) = \mathbb{E_{\pi,p}} \left[r_0 + \sum_{t=1}^{T} \gamma^t r_t \middle| s_0 = s, a_0 = a \right],

と定義する．最適状態価値関数と最適行動価値関数をそれぞれ

V^\ast (s) = \max_{\pi} V_{\pi}(s) \\\ Q_{\pi}^\ast (s, a) = r(s,a) + \gamma \mathbb{E}_{s' \sim p} [V^\ast(s)]

とする．

Bellman方程式は縮小作用素#

最適行動価値関数 $Q_{\pi}^\ast (s, a)$ は関数 $q:\mathcal{S} \times \mathcal{A} \to \mathbb{R}$ について

\mathcal{T}_\pi [q] (s,a) = \mathbb{E}\_{(r,s') \sim p} \left[r + \gamma \mathbb{E}\_{a' \sim \pi}[q(s', a')] \right],

として定義される縮小作用素 $\mathcal{T}_\pi$ の不動点である．次のことから $\mathcal{T}_\pi$ は連続であることがわかる．

\begin{align*} \|\mathcal{T}_\pi [q_1] - \mathcal{T}_\pi [q_2] \| & = \max_{s,a} \left| \mathcal{T}_\pi [q_1] - \mathcal{T}_\pi [q_2] \right| \\\ & = \max_{s,a} \left| \left[\mathbb{E}_{(r,s') \sim p} [r + \gamma \mathbb{E}_{a' \sim \pi}[q_1(s', a')] ] \right] - \left[\mathbb{E}_{(r,s') \sim p} [r + \gamma \mathbb{E}_{a' \sim \pi}[q_2(s', a')] ]\right] \right| \\\ & = \max_{s,a} \left| \gamma \mathbb{E}_{s' \sim p, a' \sim \pi} [q_1(s',a') - q_2(s',a')] \right| \\\ & = \leq \max_{s,a} \gamma \mathbb{E}_{s' \sim p, a' \sim \pi} \left[ \left| q_1(s',a') - q_2(s',a') \right| \right] \\\ & \leq \max_{s',a'} \gamma \left| q_1(s',a') - q_2(s',a') \right| \\\ & = \gamma \|q_1 - q_2 \|_\infty \end{align*}

すなわち，

\| \mathcal{T}_\pi [q_1] - \mathcal{T}_\pi [q_2] \|_\infty \leq \gamma \|q_1 - q_2 \|_\infty

である．続いてQ-learningについての収束性について議論するにあたって先程のbellman方程式の $\pi$ の期待値から新たな方針 $\mathcal{G}[q] \, (s) = \arg\max_{a} q(s,a)$ に置き換える．この新たな方針は貪欲方針(greedy policy)と呼ばれるものである．

\mathcal{T}_\pi [q] (s,a) = \mathbb{E}_{(r,s') \sim p} \left[r + \gamma \max_{a'}q(s', a') \right],

少し議論がずれるが，なぜQ-learningがoff-policyであるのかという質問に対してサンプルを集める方針 $\pi$ とそれを活用するgreedy policy $\mathcal{G}[q]$ が異なるからであると答えるのが適切かと思う．私自身，よくわからず悩んでいた点だったので補足させていただいた．

続いてBellman方程式の縮小写像としての性質を用いたQ-learningの定理について説明する．

Q-learning#

有限マルコフ決定過程が与えられたとき，Q-learningは次の更新則

Q_{t+1}(s_t,a_t)=Q_{t}(s_t,a_t)+\alpha_{t}(s_t,a_t) \left[r_t + \gamma \max_{a'}Q_{t}(s_{t+1},a') - Q_{t}(s_t,a_t) \right], \tag{2}

Q_{t+1}(s_t,a_t)=Q_{t}(s_t,a_t)+\alpha_{t}(s_t,a_t) \left[r_t + \gamma \max_{a'}Q_{t}(s_{t+1},a') - Q_{t}(s_t,a_t) \right], \tag{2}

とし，そして

\sum_{t} \alpha_{t}(s_t,a_t) = \infty, \hspace{10pt} \sum_{t} \alpha_{t}^{2}(s_t,a_t) < \infty　\tag{3}

\sum_{t} \alpha_{t}(s_t,a_t) = \infty, \hspace{10pt} \sum_{t} \alpha_{t}^{2}(s_t,a_t) < \infty　\tag{3}

である限り確率１で最適行動価値関数 $Q_{\pi}^\ast$ に収束する． $0 \leq \alpha_t(s,a) < 1$ であるためQ-learningは全ての状態-行動の組に無限に訪れる必要があることを留意していただきたい．

次の3つの仮定のもと確率過程 $\\{\Delta_t: \Delta_{t+1}(x) = (1 - \alpha_{t}(x))\Delta_{t}(x) + \alpha_{t}(x)o_t(x) \\}$ は確率１でゼロに収束する.

$0 \leq \alpha_t \leq 1, \sum_t \alpha_t (x) = \infty, \sum_t \alpha_t^2(x)< \infty$
$\| \mathbb{E}[o_t(x)] \|\infty \leq \gamma \left \|\Delta{t}(x) \right \|\_{\infty}, \gamma \in [0, 1]$
$\text{var}[o_t(x)] \leq C(1 + \left\|\Delta_{t} \right\|\_{\infty}^{2}), C > 0$

この補題を証明したかったのだが，参考した論文を理解できなかったのでこの補題の結果のみ使わせていただく（不甲斐ない）

[追記] 筆者の勉強不足で確かなことは言えないんですが、「リプシッツ条件」「線形増大度条件」がキーワードになっていると思います。勉強でき次第、また追記したいと思います

証明#

Q-learningの更新則(2)から

Q_{t+1}(s_t,a_t)= (1 - \alpha_{t}(s_t,a_t))Q_{t}(s_t,a_t)+\alpha_{t}(s_t,a_t) \left[r_t + \gamma \max_{a'}Q_{t}(s_{t+1},a') \right],

と書き換え，両辺から $Q^\ast(s_t,a_t)$ を減算する．

\Delta_{t+1}(s_t,a_t) = (1 - \alpha_{t}(s_t,a_t))\Delta_{t}(s_t,a_t) + \alpha_{t}(s_t,a_t)\left[r_t + \gamma \max_{a'}Q_{t}(s_{t+1},a') - Q^\ast(s_t,a_t) \right].

このとき $\Delta_{t}(s_t,a_t) \overset{\text{def}}{=} Q_{t}(s_t,a_t) - Q^\ast(s_t,a_t)$ ．次に

o_t(s,a) = r(s,a) + \gamma \max_{a'}Q_{t}(s,a') - Q^\ast(s,a),

とおいたとき関数 $o_t(s,a)$ の期待値は

\begin{align*} \mathbb{E}[o_t(s,a)] & = \mathbb{E}_{(r,s') \sim p} \left[r + \gamma \max{a'}Q_t (s,a') - Q^\ast(s,a) \right] \\\ & = \mathcal{T}_\pi [Q_t] (s,a) - Q^\ast(s,a), \end{align*}

となる*．Bellman方程式の性質 $Q^\ast = \mathcal{T}_*\pi [Q^\ast]$ と式(1)から，

\begin{align*} \| \mathbb{E}[o_t(s,a)] \|_\infty & = \left\| \mathcal{T}\_{\pi} [Q_t] (s,a) - \mathcal{T}_\pi [Q^\ast] (s,a) \right\|_\infty \\\ & \leq \gamma \left \|Q_t - Q^\ast \right \|_\infty \\\ & = \gamma \left \|\Delta_t (s_t,a_t) \right\|_{\infty}. \end{align*}

続いて $o_t(x)$ が有界であることを示す．

\begin{align*} \text{var}[o_t(x)] & = \mathbb{E}_{(r,s') \sim p} \left[\left( r + \gamma \max_{a'}Q_{t}(s,a') - Q^\ast(s,a) - \mathcal{T}_{\pi} [Q_t] (s,a) + Q^\ast(s,a) \right)^2 \right] \\\ & = \mathbb{E}_{(r,s') \sim p} \left[\left( r + \gamma \max_{a'}Q_{t}(s,a') - \mathcal{T}_\pi [Q_t] (s,a) \right)^2 \right] \\\ & = \text{var} [ r + \gamma \max_{a'}Q_{t}(s,a')]. \end{align*}

報酬 $r$ は有界なため，

\text{var}[o_t(x)] \leq C(1 + \left \|\Delta_{t} \right \|\_{\infty}^{2}), \hspace{10pt} C > 0

であることが確認できた．さきほどの補題により $\Delta_t$ は確率１でゼロに収束する．すなわち， $Q_t$ は最適行動価値関数 $Q^\ast$ に確率１で収束する．

\blacksquare

Soft Bellman方程式は縮小作用素#

エントロピー正則化強化学習は筆者の中で話題になっています．この部分は追記程度に載せたいと思います．（追記なので口調を変えます）

一般的な強化学習ではリターンを $G_t = \sum_{t=0}^{\infty} \gamma^t r_t$ とするのに対して、エントロピー正則化強化学習ではリターンを $R_t = \sum_{t=0}^{\infty} \gamma^t r_t + \tau \mathcal{H}(\pi(\cdot|s_t))$ とします．このとき $\tau$ は温度（係数）であり、 $\mathcal{H}(\pi(\cdot|s_t)) = -\sum_{a}\pi(a|s_t) \log \pi(a|s_t)$ です。後者はエントロピーとも呼ばれています．

特にどこかで言及されていたわけではないんですが，筆者はこの式を見て「ギブスの自由エネルギー」に似ているなと考えています．熱力学に詳しい方，教えてください．

続いて価値関数とsoft bellman作用素の定義をします(なぜこうなるかは，需要があれば別の記事で書きます)

\begin{align*} Q_\pi^{\text{soft}}(s, a) & = \mathbb{E_{\pi,p}} \left[r_0 + \sum_{t=1}^{T} \gamma^t (r_t + \tau \mathcal{H}(\pi(\cdot|s_t))) \middle| s_0 = s, a_0 = a \right], \\\ \mathcal{T}_{\pi}^{\text{soft}} [q] (s,a) & = \mathbb{E}_{(r,s') \sim p} \left[r + \gamma \log \mathbb{E}\_{a' \sim \pi}[\exp q(s', a')] \right]. \end{align*}

このsoft bellman作用素が縮小写像であることを証明します．

任意の $q_1, q_2$ に対して $\epsilon = \\| q_1 - q_2 \\|\_\infty$ とする． $\exp$ と $\log$ の単調性から次の不等式がわかる．

\begin{align*} \log \mathbb{E}_{a' \sim \pi}[\exp q_1(s', a')] & \leq \log \mathbb{E}_{a' \sim \pi}[\exp (q_2(s', a') + \epsilon] \\\ & = \log \left( \exp(\epsilon) \mathbb{E}\_{a' \sim \pi}[\exp (q_2(s', a')] \right) \\\ & = \epsilon + \log \mathbb{E}\_{a' \sim \pi}[\exp (q_2(s', a')] \end{align*}

$\mathcal{T}\_{\pi}^{\text{soft}} [q_1] - \mathcal{T}\_{\pi}^{\text{soft}} [q_2]$ が $(s,a)$ に依らず $\gamma \epsilon$ で押さえることができるので，左辺の $\max$ を取って

\| \mathcal{T}_{\pi}^{\text{soft}} [q_1] - \mathcal{T}_{\pi}^{\text{soft}} [q_2] \|_\infty \leq \gamma \|q_1 - q_2 \|_\infty

となる．よって，Soft Bellman方程式は無限ノルムに対して縮小写像といえる．

\blacksquare