IT研究メモ

流行りに便乗して、機械学習やAIの勉強を始めてみました。なかでも、強化学習は、伝統的なAIの世界（プランニング等々）と機械学習の融合のようで面白くいろいろと探求のしがいがありそうです。

とりかかりとしてこの本を読み始めています。

強くなるロボティック・ゲームプレイヤーの作り方プレミアムブックス版 ~実践で学ぶ強化学習~

作者: 八谷大岳,杉山将
出版社/メーカー: マイナビ出版
発売日: 2016/06/30
メディア: 単行本
この商品を含むブログ (2件) を見る

2008年の本なのでDQNなどはでていませんが、歴史的背景（「最適制御理論」最適化の観点から制御というものを考える、等々）から、基本的な技法の定式や実装イメージ（擬似コード的なものがある）まで網羅的に丁寧に記述されていて、大変勉強になります。

ただ読んでいるだけだとあまりわかった気になれないので、ところどころで具体的に値を計算してみたり、トイプロブレムを解いてみたりしたいと思います。

強化学習の概要:
チェーンウォーク決定問題
上記設定下での状態・行動価値の算出

強化学習の概要:

強化学習で取り組む問題は、有限マルコフ決定過程として定式化されます。

有限マルコフ決定過程

$\mathcal{S}$ : とりうる状態の集合 $\{s^{(0)}, s^{(1)}, \cdots ,\mathcal{S}^{|S|}\}$
$\mathcal{A}$ : とりうる行動の集合 $\{a^{(0)}, a^{(1)}, \cdots, \mathcal{A}^{|A|}\}$
$P_{T}(s_{t+1}|s_{t},a_{t}) \in [0, 1]$ ：状態 $s_{t}$ のときに、行動 $a_{t}$ を取った場合に、状態 $s_{t+1}$ に遷移する確率（状態遷移関数）
$\pi(a_{t}|s_{t})\in [0,1]$ ：エージェントが $s_{t}$ の状態のときに、行動 $a_{t}$ を取る確率（政策関数。方策関数という言い方もする。）
$R(s_{t},a_{t},s_{t+1})\in \mathbb{R}$ ：エージェントが状態 $s_{t}$ のときに、行動 $a_{t}$ を取り、状態 $s_{t+1}$ に遷移した場合に得られる報酬値を出力する関数（報酬関数）
$\gamma \in (0,1]$ ：割引率

学習者、いわゆるエージェントが、ある状態のときにある行動を取ることで、別の状態に遷移します。この状態遷移は「マルコフ性」を持つ確率過程、つまり直前の状態と行動のみに依存するものとします。普通のマルコフ確率過程と違うのは、単に各ステップごとに状態が確率的に遷移するのではなく、エージェントが行動を選択してそれによって状態遷移が起こることです。各状態でどの行動を行うかも確率分布として表現して、これにあたるのが政策関数です。

「ある状態のときにある行動を取ることで別の状態に遷移する」ことでエージェントは報酬を得ます。この報酬の値は(直前の状態、行動、次の状態)の三つ組を引数に取る関数の値として算出されます。この関数は問題に応じて人が設計するものです。

強化学習の目的は、「将来得られる報酬の総和が最大になるように、政策関数を学習すること」になります。ただし、「何があるかわからない（？）遠い将来に得られる報酬は、直近に得られる報酬より価値が低い」という考え方に基づき、将来得られる報酬には割引が適用されます。なので、「将来得られる報酬の総和」はtステップ後に得られる報酬を $r_{t}$ と表すとすると、

$r_{0} + \gamma r_{1} + \gamma^{2} r_{2} \cdots$

となります。

この最適化問題を解くために、「状態価値関数」あるいは「状態・行動価値関数」を利用するのが筋です。

状態価値関数

政策 $\pi$ のもとでの状態 $s$ の価値を出力する関数を $V^{\pi}$ とする： $V^{\pi}(s)\equiv \mathbf{E}_{\pi, P_{t}}[\sum_{t=0}^{\infty} \gamma^{t}R(s_{t},a_{t},s_{t+1})|s_{0}=s]$

状態・行動価値関数

政策 $\pi$ のもとでの状態と行動の対 $(s, a)$ の価値を出力する関数を $Q^{\pi}$ とする： $Q^{\pi}(s, a)\equiv \mathbf{E}_{\pi, P_{t}}[\sum_{t=0}^{\infty} \gamma^{t}R(s_{t},a_{t},s_{t+1})|s_{0}=s, a_{0} = a]$

状態価値関数はある状態を初期値とした場合の、将来の報酬の総和の期待値を算出します。状態・行動価値関数のほうはさらに行動も加えます。

状態価値関数と状態・行動価値関数には以下のような関係があります。

$V^{\pi}(s) = \mathbf{E}_{\pi(a|s)}[Q^{\pi}(s,a)]$

$Q^{\pi}(s, a) = \mathbf{E}_{P_{t}(s'|s,a)}[V^{\pi}(s')]$

チェーンウォーク決定問題

「強くなるロボティック・ゲームプレイヤーの作り方」4.2に、簡単な例題が載っております。

f:id:a-i-to:20161126175213p:plain

図は4状態チェーンウォークと呼ばれるマルコフ決定問題の、状態遷移を表しています。状態空間は $\mathcal{S} = \{ s^{(1)}, s^{(2)}, s^{(3)}, s^{(4)} \}$ 、行動空間は $\mathcal{A} = \{L, R\}$ （L=左に移動、R=右に移動）です。行動には"成功"と"失敗"があり、それぞれの場合にどう遷移するかが図に記されています。実線が成功時の遷移確率、点線が失敗時の遷移確率です。報酬関数は、状態S(4)を訪問したときに1、それ以外を0とします。

政策関数πを下記に、割引率γを0.9とした場合のQは下記のようになるとあります。

$\displaystyle \pi(a|s) = \begin{cases} 0.5 \;\; if\: a = L\\ 0.5 \;\; if\: a = R \end{cases}$

	s(1)	s(2)	s(3)	s(4)
L	1.46	1.46	1.82	2.63
R	1.71	2.42	3.72	3.72

上記設定下での状態・行動価値の算出

本では、結果だけが載っていますので、これを一から算出してみたいと思います。

この例では、ある状態から他の状態に遷移する確率を簡単に計算でき、4x4の行列（状態遷移行列）にまとめることができます。その行列の累乗を計算すると、各状態から各状態へのtステップ後に到達する確率を求めることができます。それを用いてtステップでの報酬の期待値を算出できます。ステップ数が増えていくと割引が効いてくることから、適当なステップ数までの期待値を算出し、それを合計して状態価値値とすることができます。

また状態・行動価値関数は、期待値の計算＝線形の処理なので

最初のステップ（0ステップ目）での各状態・行動の報酬期待値 + 1ステップ目以降の状態の報酬期待値

と分解できます。これをスクリプトに起こしたものが下記です。

coding: UTF-8                                                                  
"""                                                                             
「強くなるロボティックプレイヤーの作り方」4章のチェーンウォーク問題の           
Q関数の値を求める                                                               
"""

import numpy as np

### パラメータ                                                                  
n_iter = 100
discount = 0.9

# s(n=0)からLを選んでs(t=1)に遷移する確率 Pt(s(t=1)|s(t=0), L)                  
s0L = np.array([[0.9, 0.1, 0, 0],
                [0.9, 0.1, 0, 0],
                [0, 0.9, 0.1, 0],
                [0, 0, 0.9, 0.1]])

# s(t=0)からRを選んでs(t=1)に遷移する確率 pt(s(t=1)|s(t=0), R)                  
s0R = np.array([[0.1, 0.9, 0, 0],
                [0, 0.1, 0.9, 0],
                [0, 0, 0.1, 0.9],
                [0, 0, 0.1, 0.9]])

### 1. t=0の報酬期待値を求める                                                  

# t=0の期待報酬値は、ノード4への遷移確率そのものになる                          

s0L_value = s0L[:,3]
s0R_value = s0R[:,3]

### 2. t=1以降の報酬期待値を求める                                              

# 状態遷移行列                                                                  
A = np.array([[0.5, 0.5, 0, 0],
              [0.45, 0.1, 0.45, 0],
              [0, 0.45, 0.1, 0.45],
              [0, 0, 0.5, 0.5]])

# Aのべき乗を求めるために固有値と固有ベクトルを求める                           
la, v = np.linalg.eig(A)
# laでから対角行列を作る                                                        
D = np.diag(la)
# vの逆行列を求める         
inv_v = np.linalg.inv(v)

# iステップ後の期待得点を算出。それを足していく                                 
values = np.zeros(4)
for i in range(1, n_iter):
   expected = np.dot(np.dot(v, D ** i), inv_v)[:,3] * (discount ** i)
   values += expected

# t=0からt=1への遷移確率を掛けて、t=1以降の期待値を出す                         
s1L_values = np.dot(s0L, values)
s1R_values = np.dot(s0R, values)

### 3. 最終的な値を表示                                                         
print(s0L_value + s1L_values)
print(s0R_value + s1R_values)

実行結果は以下のようになります。

[ 1.46032168  1.46032168  1.82091047  2.63112231]
[ 1.71430161  2.41980141  3.72279858  3.72279858]

期待通りの値が計算できたようですね。

IT研究メモ

強化学習：簡単な例で状態価値関数の値を求める

強化学習の概要:

チェーンウォーク決定問題

上記設定下での状態・行動価値の算出

パーリンノイズ