f:id:shirakonotempura:20190314233006p:plain

では、前回の記事に引き続き線形関数近似を使った迷路問題を扱っていきます．
今回はまとめきる予定です．コードは写経が多いので余り見せられるものではないのですが、公開する予定です．

！！これは私の勉強用ノートです！！

はじめに

前回の続きなので、細かいことは省いていきます．
その２となる今回は、迷路問題についてざっくり説明を行い、学習条件などを整理して、結果まで一気にいきます．
かなり残念な結果が出ているのですが気にしない．これから考えます．

迷路問題をざっくりおさらい

学習の対象とする迷路問題についてざっくりと概要を示します．（このときの設定とほぼ同じです）

f:id:shirakonotempura:20190209000458p:plain

環境は上に示す6×9マスの格子世界の迷路
図中Sはスタート地点、Gはゴールを示しています．グレーのマスは通過できない壁を意味します．
エージェントの行動は4種類（Up, Down, Left, Right）
壁のある方向または迷路外へ動こうとする場合は、その場にとどまり１ステップが経過します．
報酬はゴールに到達する行動に対してのみ＋１が与えられ、それ以外は０とします．（つまり、壁にぶつかろうが、ゴールまでのステップ数が多かろうがぺナルディはありません）
ゴールに到達したらエピソードは終了し、スタート地点に戻り次のエピソードがスタートします

実装

細かい説明は省略し、関数近似の部分についてのみ説明をしていきます．

近似関数および基底関数の設定

価値関数の近似は、線形近似で行います．よって行動価値 $\hat q(s, a ; \boldsymbol{w})$ は以下のように書けます．

$$ \hat q(s,a ; \boldsymbol{w}) = \boldsymbol{w} \boldsymbol{\phi}^T$$

ここで、 $\boldsymbol{w}$ は求めるパラメータ $[w_1, w_2. \cdots, w_N$ ]、 $\boldsymbol{\phi}$ は基底関数 $[\phi_1, \phi_2, \cdots , \phi_N$ ]を示します．

基底関数には、前回の説明で扱ったガウス分布を用います．

いくつ関数を組み合わせるかという点については、余り深く考えずにグリッドの数を使いました．今回のケースでは６×９=５４個の基底関数を使います．基底関数の分布の中心もグリッドの座標を使いました．分散は0.05で固定としています．この辺の設定が良くないのかもしれません．

近似関数のイメージを以下に示します．左図はパラメータを全て１にした場合の局面、右図がパラメータを適当に与えた場合の曲面になります．

f:id:shirakonotempura:20190315073956p:plain

５４個の基底関数をセットしたので、近似関数に対して求めるパラメータの数も５４個になるのですが、厳密にいうと下図右の手法（※）を用いているので５４ ×４のパラメータを計算していることになります．

f:id:shirakonotempura:20190213035604p:plain

※：状態 $s$ を入力にして、行動 $a_m$ の数だけ行動価値を関数 $\hat q (s,a_m,w)$ で表す方法

行動 $a$ も含めた関数にすることも考えられますが、ちょっと３変数を入力とするガウス分布の式が良く分からず断念しました．
基底関数の形状は何でもいいと割りきってしまえば、３変数を入力とするそれっぽい式に改良すればいいだけだとは思いますが．

コード部

基底関数の定義、ｑ値の計算および行動選択部分のコードを示します．

class LinearFunc:
    
    maze = Maze() # 迷路の情報を持つコンストラクタ
    # episodes数以外は、共通
    params = DynaParams() # パラメータ情報を持つコンストラクタ
    
    N1 = maze.WORLD_WIDTH # X方向のグリッド数
    N2 = maze.WORLD_HEIGHT # Y方向のグリッド数
    
    eps = params.epsilon # 探索割合：ε
    gamma = params.gamma # 割引率
    alpha = params.alpha # 学習率
    
    ts = 2 # total states # 基底関数に使う入力変数の数
    NUM_ACTION = 4 # エージェントがとる行動の数

    # 基底関数の中心（μ）をリストで作っておく
    # 中心は、座標のインデックス[X, Y]の組み合わせ
    myu_dist_wid = np.linspace(0.0, N1-1, N1)
    myu_dist_hei = np.linspace(0.0, N2-1, N2)
：
省略
：
    # 基底関数の計算
    # 入力:状態（X座標とY座標）
    # 出力:基底関数の出力*４行動分
    def rbfs(self, s):
        s = s.reshape(len(s),1) # 2次元配列に整形
        return np.exp(-np.square(LA.norm((self.mu_list-s)/self.norm_factor, axis=1))/(2*self.var)) 

    # φ×ωでQ値を計算する関数
    def getQ(self, s, a):
        return (self.rbfs(s)[a]).dot(self.omega_list[a])

    def select_action(self, s):
        # e-greedyによる行動選択   
        if np.random.rand() < self.eps:
            action = np.random.randint(self.NUM_ACTION)
            return action
        else:
            # getQで、各行動に対する近似計算値qs = q(s)を取得
            qs = [self.getQ(s,i) for i in range(self.NUM_ACTION)]
            # qsの中でqs(a)が最大となるaを選択
            action = np.argmax(qs)
            # qsが2つ以上ある場合は、その中でランダムに選ぶ
            is_greedy_index = np.where(qs == action)[0]
            if len(is_greedy_index) > 1:
                action = np.random.choice(is_greedy_index)
            return action

学習条件の設定

学習・パラメータ更新に関する値は以下のように設定します．

割引率は0.9
学習率αは0.1（固定）
行動選択はε-greedy法で行い、εは0.05（固定）
1000エピソードを1エポックとし、同じ条件で3エポックの学習を行う．

1エピソードごとに、ゴールに至るまでに要したステップ数を記録しておき、3エポックの平均をグラフ化する．

ほぼ同じ条件でTabular型のQ学習による学習を行い、結果の比較を行います．

超絶注意：
前回のプランニングのケースのコードをベースに関数近似部分を追加しています．プランニングモデルは更新にQ学習を使っているのですが、今回追加した関数近似の関数の更新は以下のOn-line 更新を使っています．比較と言いつつ更新の考え方が異なっています．気づいたときには、修正する気力がありませんでした．ご容赦ください・・・．

$$\boldsymbol{w_{t+1}} \leftarrow \boldsymbol{w}_{t} + \alpha \Bigl[R_{t+1} + \gamma \hat{q}_(s_{t+1}, a_{t+1}:\boldsymbol{w}) - \hat{q}(s_t, a_t; \boldsymbol{w}_{t})\Bigr] \nabla \hat{q}(s_t, a_t; \boldsymbol{w}_t)$$

Sutton本　p.244 (10.2)式より

パラメータの更新

パラメータ $w$ の更新部分のコードを示します．

# パラメータθの更新
def train(self, s, a, reward, s_dash, a_dash):
    phi = self.rbfs(s)
    Q_val = self.getQ(s,a)
    Q_val_dash = self.getQ(s_dash,a_dash)

    DELTA = reward + self.gamma*Q_val_dash - Q_val
    # パラメータの更新式
    self.omega_list[a] = self.omega_list[a] + self.alpha * DELTA * phi[a]