2019.2.25　追記：SARSAおよびExpected SARSAのコーディングに誤りがあります．修正したら記事も修正するか別の記事で修正版を出すようにします．

はじめに

今回は、以前やった内容の復習が主になります．
タイトルにあるとおり、TD学習の手法であるQ学習、SARSAおよびExpected SARSAの３つを実装してみて、結果の比較を行います．

Q学習、SARSAは以前扱った内容なので、理論の説明は少な目、コード多めになる予定です．

shirakonotempura.hatenablog.com

これは、私の学習用ノート．メモ、備忘録です

Open AI Gym

今回の学習ではOpen AI Gymを利用しています．

Open AI Gymは、強化学習の研究者向けに提供されている開発環境で、自分で学習させたAI（エージェント）を実際に動かすことができるシミュレータを提供してくれます．Cart PoleやMountan Carなどは有名なので見られたことがあるかと思います．

f:id:shirakonotempura:20190223040602p:plain

今回はその中から、Taxi-v2を使ってみたいと思います．

Taxi-v2

Taxi-v2ではタクシー運転手が乗客をピックアップして、降車させるタスクを扱います．
学習の目的は、ちゃんとした場所で乗客を乗せ、できるだけ短い距離を通って目的地に連れていくことです。

環境

フィールドは、以下に示す５×５の格子世界になります． - 黄色いシンボルがタクシーを示しており、乗客をピックアップすれば緑色に変わります． - R, G, B, Yの文字が示された4マスのいずれかが、乗客の位置および目的地となります． - " | " は壁を意味しており、そこを通りぬけることはできません．

f:id:shirakonotempura:20190223042509p:plain

状態について

まず状態 $s$ について説明します．

これまで扱ってきたようなGrid Worldの問題ではグリッド数＝状態数であることが多いのですが、今回は少し異なります．

乗車位置、目的地がエピソードごとに変化するということは、同じマスであっても取るべき行動は変わってきます．そこで、乗車位置と目的地も状態を表す要素の１つと考えることで以下のように考えることができます．

５（縦）×５（横）×４（乗車位置）×４（目的地）＝４００（総状態数）

実はこれでは不十分で、このままでは、乗客を乗せる前と後で同じ状態が現れてしまいます．そこで、乗車位置を乗客の位置にしてしまい車の中という状況を加えることで、同じ環境で乗車前と乗車後を考えることができます．

５（縦）×５（横）×５（乗客の場所）×４（目的地）＝５００（総状態数）

行動について

次に行動[text:a]について説明します．

格子世界なので、移動アクションは上下左右の4方向を考えます．これまでと違う点として、乗客のピックアップ（pick up）および降車（drop off）がこれに加わり、行動は全部で６種類となります．

Taxi-v2で与えられた順番と名前のとおりに書くと以下のようになります．

行動 $a$ = ["South", "North", "East", "West", "Pickup", "Dropoff"]

報酬とエピソードの終了について

最後に報酬について説明します．

乗客を目的地まで運ぶことで報酬＋２０を受け取ります．
乗客のいない場所でpick upの行動をとると‐１０の報酬を受け取ります．
目的地でない場所、乗客がいない状態でdrop offの行動をとった場合も‐１０の報酬を受け取ります．
１マス進むたびに‐１の報酬を受け取ります

乗客を目的地で降車した場合エピソードが終了し、タクシーの位置、乗客の位置、目的地がランダムに決められます．
‐１０の報酬を受け取る行動をとったとしても、エピソードは終了しません．

ただし、２００ステップが経過した時点でエピソードは強制的に終了となります．（デフォルトの設定）．これは環境を定義する際に回避することもできるようですが、時間がかかる場合もありますので個々の判断にお任せします．（私はデフォルトのままにしてます）

上限を２００ステップにした環境設定方法 env = gym.make("Taxi-v2")
２００ステップの制限なしの環境設定方法 env = gym.make("Taxi-v2").env

やっとTaxi-v2の説明が終わりました・・．長くなってしまいました．

学習アルゴリズム（Qテーブルの更新式）

前回、関数近似について整理しましたが、今回は単純にQテーブルを使って行動価値 $Q(s,a)$ の更新を行っていきます．

まずは、以下に、Q学習とSARSAのQテーブルの更新式を示します．

Q-Learning $$Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma \; argmax_{A} Q(s', a) - Q(s, a)]$$
SARSA $$Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma Q(s', a') - Q(s, a)]$$

Q-Learningの場合は、次の状態 $s'$ における最も高い行動価値 $\; argmax_{A} Q(s', a)$ を更新式に使い、SARSAでは方策に従って実際に選択した行動の行動価値 $Q(s', a')$ を更新式に使っていました．~~（１ステップで２回行動するわけではありません．あくまで選択したという仮定です）~~

2019.2.25追記
1ステップに２回行動するわけではないですが、選択した行動 $a'$ は、次のステップの行動になります．間違っていました．
コードは、次のステップでまた行動選択をsoftmax法で行っているので、誤っています．すいません．

Expected SARSAについて

Expected SARSAについてはこれまで説明してこなかったのですが、上の２つと大きく変わりません．

Expected SARSA $$Q(s, a) \leftarrow Q(s, a) + \alpha [R + \gamma \sum_{a} \pi (s', ) Q(s', a) - Q(s, a)]$$

$\sum_{a} \pi (s', ) Q(s', a)$ の部分が、Expectedの名前のとおり状態 $s'$ における行動価値の期待値を示しています．

行動選択方法→温度付きsoftmax行動選択法

もう１つこれまでと違うことをやっているので、簡単に説明します．

これまでは行動選択にε-greedy法を用いてきました．ε-greedy法は、確率1-εでこれまでで最良の行動を選び、確率εでランダムに行動を選択するというものでした．

今回は、softmax関数を使った行動選択方法を採用しています． softmax関数は、多クラス分類問題において、そのクラスである確率を計算するときに使われる関数です．

具体的な数式を以下に示します． $$\pi(Q(s, a_i))= \frac {e^{Q(s, a_i)}} {\sum {e^{Q(s, a)}}}$$

左辺の $\pi(Q(s, a_i))$ が状態 $s$ が、行動 $a_i$ を選ぶ確率になります．
この式を直接使うことも可能ですが、今回は上記の式を若干修正した、温度付きsoftmax関数を使用します．

$$\pi(Q(s, a_i))= \frac {e^{\frac{Q(s, a_i)}{T}}} {\sum {e^{\frac{Q(s, a)}{T}}}}$$

ここでTは温度パラメータで、Tが大きいほど確率の差が縮まり（ランダム性が強くなり）、Tが小さいほど高い確率が強調される（greedyな行動選択）ようになります．ステップ数やエピソード数を温度の変数に使うことで、学習初期はランダム性を高めたりすることができます．

温度付きsoftmax関数について、もう詳しく見たい方は以下の記事を参考にしてください

温度付きsoftmax 覚書 - Qiita

実装

では、実装した内容とについて説明します．パラメータである温度と学習率の影響も見たかったので、パラメータスタディができるようにしています．

共通条件
- １０エピソードを１セグメントとし、１００セグメントで１タスクとしています．
- １つの学習タスクに対して、同じ条件の検討を10回行い、平均値をプロットするようにしています
- 更新時の割引率 $\gamma$ は0.8
- 学習率は0.01および0.2
- 温度は0.2および2.0

学習部分

学習部分のコードは以下に示します．
見ればわかると思いますが、パラメータごとにfor文で回しまくってます．見た目はいまいちですね．
１セグメント終わるごとに、あらかじめ用意しておいた空の配列リストに必要な結果をappendし、１タスクが終わればQテーブル(q_table)を初期化しています．

# TRAINING PHASE
for episode in range(episodes):
    #initiralize
    state = env.reset()
    steps, penalties, reward, = 0, 0, 0
    total_rewards = 0
    done = False
                    
    # Loop for 1 episode(max 200 steps in default)
    while not done:
                        
        #Choose Softmax
        act_prob = softmax(q_table[state], temper)
        action = np.random.choice(len(q_table[state]), p= act_prob)
               
        # Get reward, next_s
        next_state, reward, done, info = env.step(action)
                  
        # Count Penalty (for illegal pickup and drop off)
        if reward == -10: #bad perform gets negative reward and penalty
            penalties += 1

        # common data for updating
        old_value = q_table[state, action]
        act_prob_n = softmax(q_table[next_state], temper)
            
        # update action_value(q_learning)
        if method == "q_learn":
            next_max = np.max(q_table[next_state])
            new_value = old_value + alpha * (reward + gamma * next_max - old_value)
                        
        # update action_value (sarsa) 
        elif method == "sarsa":
            action_n = np.random.choice(len(q_table[next_state]), p= act_prob_n)
            new_value = old_value + alpha * (reward + gamma * q_table[next_state, action_n] - old_value)
                            
        # update action_value (ex_sarsa)
        elif method == "ex_sarsa":
            expected = np.dot(act_prob_n, q_table[next_state])
            new_value = old_value + alpha * (reward + gamma * expected - old_value)
                
        q_table[state, action] = new_value
                          
                            
        # change current state
        state = next_state
        steps += 1
        total_rewards += reward
                    
        # add 10th episode's result to results list
        if episode == episodes -1:
            train_results[i][j][run].append(total_rewards)
    return train_results, test_results

各更新式の部分だけ少し詳細に見ます．

Q-Learning

# update action_value(q_learning)
    if method == "q_learn":
        next_max = np.max(q_table[next_state])
        new_value = old_value + alpha * (reward + gamma * next_max - old_value)

nex_maxで次の状態 $s'$ における最良の行動のQ値を取得し、更新式で使用しています．

SARSA

# update action_value (sarsa) 
    elif method == "sarsa":
        action_n = np.random.choice(len(q_table[next_state]), p= act_prob_n)
        new_value = old_value + alpha * (reward + gamma * q_table[next_state, action_n] - old_value)

SARSAで必要になるのは、次の状態 $s'$ において選択した行動 $a'$ の行動価値なので、まず行動 $a'$ （action_n）の選択を行っています．なお、この行動選択も温度付きsoftmax関数を使って行っています．

Expected SARSA

# update action_value (ex_sarsa)
    elif method == "ex_sarsa":
        expected = np.dot(act_prob_n, q_table[next_state])
        new_value = old_value + alpha * (reward + gamma * expected - old_value)

先に期待値（expected）の計算をしてから、更新を行っています．期待値は次の状態 $s'$ における各行動の選択確率（act_prob_n）×各行動のQ値（q_table[next_state]）で計算しています．当然、選択確率の計算はsoftmax法になります．

全体的にfor ループが多すぎるせいか、めちゃくちゃ遅いです．

colaboratoryのノートはコチラです．

結果

学習結果を示します．

下の図は、Q学習のみでパラメータによる学習曲線の違いを示したものになります．学習率 $\alpha = 0.01$ のケースは学習率が小さすぎて学習の進捗が遅いですね．温度に関してはT=2.0よりはT=0.2としてランダム性を強くした方がよさげですが、では0.2が最適なのかどうかについては、パラスタをして決める必要があります．

f:id:shirakonotempura:20190223072055p:plain

下の図は、3手法による結果を重ね書きしたものです．更新方法ごとの違いが、結果に全然現れてないですね．
これはコーディングが合っているのか不安になるレベルです．

f:id:shirakonotempura:20190223071712p:plain

まとめ

今回はOpen AI gymにあるTaxi-V2を使ってQ学習、SARSA、Expected SARSAの実装を行いました．
比較の部分がまだ改善の余地ありですが、自分でコードを書いてみると手法による計算の違い・共通部分がよくわかりました．
ただし、上記の結果のとおり正しく実装できているのか不安です．

また、前回勉強したクラスを全く使っていませんので、まだまだですね．

もう少し今回の内容を見直した後は、今度こそ関数近似の問題をやるつもりです．