Reinforcement Training (強化学習)

Youtube 「強化学習の探検」 AIcia Solid Project を視聴したときのメモ

強化学習とは

• ロボット制御
おいしさ(収益)を最大化するために、その日の天候や生地の具合(状態)で作業を調整(行動の選択)する。
• 動画のレコメンド
総視聴時間(収益)を最大化するためい、ユーザの好みや視聴履歴(状態)に応じて、推薦する動画を決める(行動の選択)。
• ゲーム (囲碁・将棋)
対局に勝つ(勝率が収益で、収益を最大化する)ため、 局面(状態)に応じて、着手を選択(行動を選択)する。

教師あり学習とどこが違うのか?

• 教師あり学習 ... データに対してラベルを推論する → 正解率を高める
• 強化学習 ... 状態に応じて行動を選択する → 収益を高める

• 状態・行動のあとに「次の状態」がくる。「現在の状態」と「次の状態」の間に相関がある。
• 収益が分かるまで時間差がある。

• 教師あり学習 ...「データ → ラベル → 正解率」のうち「データ → ラベル」の部分を学習する
• 強化学習 ... 「状態 → 行動 → 収益」のうち 「行動 → 収益」 「状態 → 収益」 「状態 → 行動」 など、いろいろな部分(関係)を学習する。

強化学習の全体像

• 状態 (State)
• 行動 (Action)
• 報酬 (Reward)
• 収益 ... 報酬の合計 $\displaystyle g = \sum r_t$

マルコフ決定過程 (Markov Decision Process, MDP)

マルコフ決定過程は強化学習の問題設定を与える。 環境 (Environment) と呼ばれる。

マルコフ決定過程では、行動の次の状態と報酬を条件付き確率で設定している。

マルコフ決定過程は5個の要素から成る。 大事なのは次の2個。

(1)行動 → 次の状態

(2)行動 → 報酬

マルコフ決定過程の定義

マルコフ決定過程は、以下の5つのデータから成る。
$S$, $A_s$, $p(s'|s,a)$, $p(r|s,a)$, $p(s_0)$

強化学習の方策 (Policy, $\pi$)

強化学習: 収益最大化のため、状態に応じて、「方策 (Policy)にしたがって」行動を選択する。

• 状態 $s$ を入力すると行動 $a$ を出力する関数 $a=f(s)$
• 状態 $s$ と行動 $a$ を入力すると、「状態 $s$ で行動 $a$ を選択する確率 $\pi(a|s)$」を与える確率分布    ← こちらを採用する

1. マルコフ決定過程が確率を用いて定義されるので、方策も確率分布
2. 確率分布を考えると、関数で定義した場合を含むことができる。
関数 $a=f(s)$ は
$\pi(a|s) = \begin{cases} 1 & \mbox{if} ~~ a = f(s) \\ 0 & \mbox{otherwise} \\ \end{cases} $ と定義した場合と同じである。
3. 探索
データ収集のときは、最善以外の行動も大事である。 (例) 「95\% は最善手を選択するが、5\% はランダムな手を選択する」など。
4. 行動が連続値の場合
行動の数値はある程度ずれてもよい場合 → 連続確率分布を使う。

強化学習の収益

1. エピソードと軌跡
2. 収益と価値関数
3. 収益とは

1. エピソードと軌跡

MDP と方策があると
$s_0$ → ($a_0$, $r_0$) → s_1 → ($a_1$, $r_1$) → $s_2$ $\cdots$ のように状態が遷移していくが、すべて確率的に決定されていく。

この系列データを「エピソード (episode)」という。 また、データ全体を「軌跡 (trajectory)」という。

2. 収益と価値関数

3. 収益

記号のおさらい

内容

収益 $\displaystyle g=\sum{t \geqq 0} r_t$ を最大化したい。 しかし、$g$ はランダムに変動する。 そこで、期待値を調べる。

$\mathbb{E}[G]$ は無限和なので発散する場合がある。 そこで、 割引率 $\gamma$ ($0 \leqq \gamma \leqq 1$)を考えて収束させる。

割引率の妥当性: 学習がうまくいくのでよい(工学的態度)

問題にあわせて割引率 $\gamma$ を調整 (= 先読み範囲の調整)すると、学習を効率化できる。

• $\gamma=0.9$ のとき、「$t=10$ までの報酬和の最大化」と大まかに等しいとみなせる。
• $\gamma=0.99$ のとき、「$t=100$ までの報酬和の最大化」と大まかに等しいとみなせる。
• $\gamma=1.0$ のとき、「ずっと先までの報酬和の最大化」と大まかに等しいとみなせる。←囲碁将棋の場合など、最後に報酬(勝ち/負け)が得られる

割引率の妥当性2 : 遠い将来の価値は価値が下がるのが自然(経済学的態度)

金利が 1\% だと、今日の100万円は、1年後に101万円になる。
すなわち、1年後の100万円は、現在の100万円よりも価値が下がる。

まとめ

期待割引収益は、割引率を考えた「報酬の累積和」の期待値。 以降、「期待割引収益」を単に「収益」と呼ぶことにする。

方策 $\pi$ を明記したいときは $\mathbb{E}$ を $\mathbb{E}^{\pi}$ と書くことにする。

価値関数

1. 価値関数とは
2. 価値関数の使い方

1. 価値関数とは

2. 価値関数の使い方

Generalized Policy Iteration

1. Generalized Policy Iteration
2. 強化学習4つの対象

• Q-learning
• Policy-Iteration
• Alpha Go

1. Generalized Policy Iteration

$s_t$ → ($a_t$, $r_t$) → s_{t+1}
「状態 $s_t$ に応じて方策 $\pi$ に従って行動 $a_t$ を選択し、報酬 $r_t$を得る」ことを繰り返し「データを集める」。 集めたデータを使って「学習して方策 $\pi$ を改善する」。 これを繰り返すことが Generalized Policy Iteration である。

Generalized Policy Iteration は「方策改善 (Policy Improvement)」と「方策評価 (Policy Evaluation)」の繰り返しである。

方策改善では、パラメータを変えて $\pi$ を改善する。 方策評価では、価値関数 $V^{\pi}$, $Q^{\pi}$ を推定(学習)する。

「価値関数の値が大きい」ことはすなわち「収益が大きい」ということ。 → 価値関数の大きさで方策の良し悪しが評価できる。

強化学習の勉強の難しさ

1. 部分問題が非常に多い。
• データと $V$, $Q$ から $\pi$ を学習する。
• $\pi$ とデータから価値関数 $V$, $Q$ を学習する。
• $\pi$ から価値関数 $V$, $Q$ を学習する。
2. 注力場所が異なる
• $Q$ だけを学習する手法がある。
$Q$ をきちんと学習すると → 各状態 $s$ で $Q(s,a)$ が最大になる行動 $a$ を選択すｒばよい。
• $\pi$ だけを学習する手法がある。
• $\cdots$

2. 強化学習4つの対象

ベルマン方程式: ベルマン期待方程式 (Bellman Expectation Equation)

「2手先の未来を読む」。

定理 (ベルマン期待方程式)

ベルマン方程式を理解する2つのポイント

• 次に何が起きる?
• $V$, $Q$ は $G$ の期待値
$\begin{align} G & = R_0 + \gamma R_1 + \gamma^2 R_2 + \gamma^3 R_3 + \cdots \\ & = R_0 + \gamma ~ (R_1 + \gamma R_2 + \gamma^2 R_3 + \cdots) \\ \end{align}$

Step 1: 「状態」の次は「行動」

• 行動 $a$ が確率 $\pi (a|s)$ で選択される。
• 行動 $a$ のあとの収益は $Q^{\pi}(s,a)$

したがって、$V$ は $Q$ の期待値として計算できる。

Step 2: 「行動」の次は、「報酬」と「次の状態」

• 確率 $p(r|s,a)$ で報酬 $r$ がもらえる。
• 確率 $p(s|s,a)$ で次の状態が $s'$ になる。

Step 3: ベルマン方程式は2手先を見る

ベルマン状態方程式の証明

まとめ:[基本公式] (1手先の未来)

まとめ[ベルマン方程式] (2手先の未来)

$\begin{align} V^{\pi}(s) &= \sum_a {\pi}(a|s) (\sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) V^{\pi} (s')) \\ Q^{\pi}(s,a) &= \sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) \sum_{a'} {\pi}(a'|s') Q^{\pi}(s',a') \\ \end{align}$

---

ベルマン方程式: ベルマン最適方程式 (Bellman Optimality Equation)

最適方策 $\pi^{*}$

たいていのマルコフ決定過程においては、最適方策 $\pi^{*}$ という方策があって、すべての状態について価値関数が最大になる。

強化学習の目的は、最適方策(または、その近似解)を発見すること。

定理: ベルマン最適方程式

最適方策 $pi^{*}$ についての価値関数 $V^{*}$, $Q^{*}$ は次の式を満たす。

「ベルマン期待方程式の」「期待値」(すなわち、$\displaystyle \sum_a \pi(a|s)$ や $\displaystyle \sum_{a'} \pi(a'|s')$ の部分) を最大値 $\max$ に変更したものが「最適方程式」といえる。

Step 1: 状態の次は行動

$\displaystyle \sum_a \pi(a|s)$ の部分は「様々な行動を選択する確率」(に報酬を乗算した)の和(=期待値)を意味している。

Step 2: 行動の次は報酬と次の状態

$\displaystyle \sum_r p(r|s,a)$ や $\displaystyle \sum_{s'} p(s'|s,a)$ の部分はマルコフ決定過程が支配している。 したがって、 $V^{\pi} (s') $ を最適に変更すれば、$Q^{\pi}$も最適になる。

Step 3: ベルマン最適方程式

まとめ: [基本公式] (1手先の未来)

まとめ: [ベルマン最適方程式] (2手先の未来)

方策反復法 (Policy Iteration)

1. 方策反復法とは

• 方策評価(= 価値関数を推定する)と方策更新の繰り返しで最適方策 $\pi^{*}$ を得る。
• マルコフ決定過程が既知の場合に使える。
$p(r|s,a)$ や $p(s'|s,a)$ などが既知の場合。たとえばボードゲームのAIを作るときに使える。
• 状態数が大きすぎない時に利用可能。
たとえば、「行列の逆行列が計算できる」とか「行列の乗算を繰り返し計算できる」くらいのサイズ。
• データ集めはしない。マルコフ決定過程から $\pi^{*}$ を直接作る。

多くの強化学習アルゴリズムが、「方策評価と方策更新の繰り返し」である。

方策評価

価値関数の推定。今回は状態価値関数 $V^{\pi}(s)$ を推定する。

• マルコフ決定過程は既知。すなわち$p(r|s,a)$ や $p(s'|s,a)$ などが既知。
• 方策 $\pi$ から $V^{\pi}$ を計算したい → ベルマン方程式が使える。
$\begin{align} \color{blue}{V^{\pi}(s)} &= \sum_a \color{magenta}{{\pi}(a|s)} (\sum_r \color{magenta}{p(r|s,a) r} + \color{magenta}{\gamma} \sum_{s'} \color{magenta}{p(s'|s,a)} \color{blue}{V^{\pi} (s')}) \\ \end{align}$
上記式中では、未知の項は青、既知の項はマゼンタで表している。
これは $\color{blue}{V^{\pi}(s)}$ の連立1次方程式であるので、解くと $\color{blue}{V^{\pi}(s)}$ が求まる。

連立一次方程式

1次連立方程式の解の存在

$\gamma < 1$ なら解がただひとつ存在する。
$\gamma = 1$ のときは、場合による。

1次方程式を解くには逆行列の計算が必要となる。

1. 逆行列が(現実的な時間で)計算できる。
2. 無理な場合は、ベルマン作用素を利用する。
3. それでも無理な場合は、別の方法を使う。

2. 方策評価とベルマン作用素

ベルマン作用素

ベルマン作用素は $\color{blue}{\widehat{V}^{\pi}(s)}$ から以下の式で $\color{green}{\widehat{V}^{\pi, new}(s)}$ を作る変換。

誤差を $\gamma$ 倍に減らすことができる。

$\gamma < 1$ のとき、ベルマン作用素を繰り返し適用することで精度が向上できる。
充分に繰り返したあとの推定値 $\widehat{V}^{\pi}(s)$ を(ほぼ真の)価値関数として、方策評価を完了する。

3. 方策更新

• $p(r|s,a)$, $p(s'|s,a)$ は既知。$
• 状態価値関数の推定値 $V^{\pi}(s)$ がある
• より収益の大きい方策 $pi^{new}$ がほしい。
→ $\displaystyle\begin{align} \pi^{new} &= \mbox{argmax} \widehat{Q}^{\pi} \end{align}$ で求まる。

$\widehat{Q}^{\pi}(s,a)$ とは

$\mbox{argmax} \widehat{Q}^{\pi}$ とは

$\mbox{argmax} \widehat{Q}^{\pi}$ とは、 状態 $s$ で $\widehat{Q}^{\pi}(s,a)$ が最大となる行動 $a$ を選択する方策

まとめ: 方策反復法

以下の手順を繰り返す。

1. 方策評価: ベルマン作用素を連続適用することで状態価値関数の推定値 $\color{orange}{\widehat{V}^{\pi}(s)}$ を得る。
   
2. 方策更新: $\color{magenta}{\pi = \mbox{argmax} Q}$ で新しい方策 $\color{magenta}{\pi}$ を得る。
   

マルコフ決定過程なので $p$, $r$ は既知である。 初期状態において $\pi$, $V$, $Q$ は適当に初期化しておいて良く、繰り返しによって、 次第に精度が向上していく。

価値反復法 (Value Iteration)

1. 価値反復法とは

• 最適状態価値関数 $V^{*}$ の推定値 $\widehat{V}^{*}$ を計算する。
• $\widehat{V}^{*}$ から $\widehat{Q}^{*}$ を計算し、 $\pi = \mbox{argmax} \widehat{Q}^{*}$ で最適方策 $\pi^{*}$ を求める。
• 方策反復法と同様に、以下の条件を満たすときに利用が可能である。
• マルコフ連鎖過程であり、$p$, $r$ が既知。
• 状態数が少ない。
• data を使用しない。

2. 価値反復法とベルマン最適作用素

状況

• マルコフ連鎖過程であり、$p$, $r$ が既知。
$p(r|s,a)$, $p(s'|s,a)$ は既知。
• 最適状態価値関数 $V^{*}$ を計算したい。
• 方策反復法では、ベルマン期待作用素を使って $V^{\pi}$ の推定値 $\widehat{V}^{\pi}$ を計算した。

復習

ベルマン最適作用素

ベルマン最適作用素は、 $\widehat{V}^{*}(s)$ に以下の式を適用して $\widehat{V}^{*, new}(s)$ を計算する変換

誤差を $\gamma$ 倍に減らすことができる。

3. 最適方策を計算する

Step 1: $\widehat{Q}^{*}$ を計算する

ベルマン最適方程式の1手先読みで
$\begin{align} \widehat{Q}^{*}(s,a) & = \sum_r p(r|s,a) r + \gamma \sum_{s'} p(s'|s,a) \widehat{V}^{*}(s') \end{align}$
を計算する。

Step 2: $\pi = \mbox{argmax} \widehat{Q}^{*}$

$\mbox{argmax}$ は, 「状態 $s$ で、 $\widehat{Q}^{*}(s,a)$ が最大になる行動 $a$ を選択する」ことを意味する。 したがって、$\pi$ は 「状態 $s$ で、 $\widehat{Q}^{*}(s,a)$ が最大になる行動 $a$ を選択する」 方策となる。

まとめ

最適状態価値関数の更新を繰り返し、最後に一度だけ方策の更新を行う。

$\gamma < 1$ ならば、推定値 $\widehat{V}^{*}(s)$ を適当に初期化して、 ベルマン作用素を何回も適用すれば $V^{*}(s)$ に近い(= 誤差の小さない) 推定値 $\widehat{V}^{*}(s)$ が得られる。

1. 最適状態価値関数の推定値の更新を繰り返す: ベルマン作用素を連続適用することで最適状態価値関数 $V^{*}(s)$ の推定値 $\color{orange}{\widehat{V}^{*}(s)}$ を得る。
   
2. 方策更新: $\widehat{V}^{*}$ から $\widehat{Q}^{*}$ を計算し、 $\color{magenta}{\pi = \mbox{argmax} \widehat{Q}^{*}}$ で新しい方策 $\color{magenta}{\pi}$ を得る。
   

価値反復法が方策反復法を決定的に違う点は、「繰り返しが無い(= 方策更新は最後に1度だけ行われる)」である。