ExpectedSarsaでOpenAI GymのTaxi問題を解く

OpenAI Gym

gym.openai.com

強化学習アルゴリズムを開発して比較するためのツールキット。 シンプルなものからAtariのゲームのような複雑なものまで、様々なシチュエーションが用意されています。

今回は、そこから「Taxi-v2」環境を使って、強化学習によるAIを作成してみました。

（OpenAI Gymはpip経由で簡単に入れることができます。詳細は本家ドキュメントをご確認下さい）

Taxi-v2

概要

Taxi-V2の目的は、5x5のフィールドでタクシーを運転し、乗客を乗せ目的地で下ろす一連の流れをなるべく素早く行う事です。

タクシーは1マス進むたびに、-1の報酬を受け取りますが、乗客を目的地まで運ぶと+20の報酬を受け取る事ができます。
また、乗客のいない所で客を拾ったり、乗客がいないのに客を下ろす動作をしたりすると、-10の報酬を受け取ってしまいます。

黄色い長方形がタクシーになります。開始位置はランダムです。

青色の文字が乗客の位置で、赤色の文字が目的地を表しています。
乗客の位置と目的地の位置はR,G,B,Yのどこか、ランダムに決まります。

「:」は通れる通路、「|」は壁になっており、タクシーは通れません。

状態

観測できる状態はただ1つの整数値のみです。
この数値で「現在の位置」「乗客の位置」「目的地の位置」を表現しています。

具体的にはこちら gym/taxi.py at master · openai/gym · GitHub の実装をご覧下さい。

行動

取れる行動は「東/西/南/北に移動」「乗客を拾う」「乗客を下ろす」の6種類になります。
0~5の数値が割り当てられており、順に「"South", "North", "East", "West", "Pickup", "Dropoff"」になります。

ExpectedSarsa

学習は ExpectedSarsaという手法を使用して行いました。詳細は割愛します。

ExpectedSarsaでは、以下の更新式によりQ関数を更新します。

ちなみに、Q学習の更新式は以下でした。

γがかかっている部分を見ると、Q学習ではQ関数が最大となるようなactionを選択しますが、ExpectedSarsaは文字通り、期待値を取っている事がわかります。

実装

Agentの実装です。

行動選択はε-greedyを用い、活用と探索のバランスをとっています。

最も期待値の高いactionを1-ε + ε/nAで選択し、それ以外のactionをそれぞれ確率ε/nAで選択します。

εは学習を進めるごとに小さくしていき、活用の割合を増やしていきます。

class Agent:
    def __init__(self, nA=6):
        self.nA = nA
        self.Q = defaultdict(lambda: np.zeros(self.nA))
        self.sum_step = 1
        
    def epsilon_greedy_probs(self, state):
        epsilon = 1.0 / self.sum_step
        policy_s = np.ones(self.nA) * epsilon /self.nA
        policy_s[np.argmax(state)] = 1 - epsilon + (epsilon / self.nA)
        return policy_s
        
    def select_action(self, state):
        policy_s = self.epsilon_greedy_probs(self.Q[state])
        return np.random.choice(self.nA, p = policy_s)

    def step(self, state, action, reward, next_state, done):
        self.sum_step += 1
        alpha = 0.1
        gamma = 0.999
        policy_s = self.epsilon_greedy_probs(self.Q[state])
        self.Q[state][action] += self.Q[state][action] + (alpha * (reward + (gamma * np.dot(self.Q[next_state], policy_s)) - self.Q[state][action]))

次に、学習を走らせる部分の実装です。

特に言及するところはありませんが、後に報酬の推移をグラフ化するために、キューを使って報酬の平均値をサンプリングしています。

def interact(env, agent, num_episodes=20000):
    avg_rewards = deque(maxlen=num_episodes)
    sampling_rewards = deque(maxlen=100)

    for i_episode in range(1, num_episodes+1):
        state = env.reset()
        total_reward = 0
        while True:
            action = agent.select_action(state)
            next_state, reward, done, _ = env.step(action)
            agent.step(state, action, reward, next_state, done)
            total_reward += reward
            state = next_state

            if done: 
                sampling_rewards.append(total_reward)
                if (i_episode >= 100):
                    avg_reward = np.mean(sampling_rewards)
                    avg_rewards.append(avg_reward)
                break
    return avg_rewards

結果

2万エピソードまでの報酬の推移のグラフです。

2500エピソードあたりで収束したように見えますが、15000エピソードあたりで更に一気に得られる報酬が増えていることがわかります。
大体平均報酬9~10程度になったら最短ルートを辿っていると言えそうです。

次は、実際に動かしてみてランダム（未学習）のタクシーの挙動と、学習後タクシーの挙動を比べてみます。

未学習

学習済み

学習済みモデルの方はほぼ最短ルートで送迎できています。よかったー。

次はDQNでインベーダーとかブロック崩しとかさせたいんだけど、全然ちゃんと学習してくれなくて詰んでます。。
インベーダーはUFOに飛び付くし、ブロック崩しは左右端で待機しちゃう・・・。学習量の問題なんだろうか・・・。
いい感じになったら公開したいです。