OpenAI GymのFrozenLake-v0をQ学習で解く

OpenAI Gymにある迷路探索問題FrozenLake-v0を解いてみました．

ルール

• 4x4の盤面を移動する．
• Sが開始地点で，Gがゴール．
• Hが落とし穴でゲーム失敗で，Fは床で移動できる．
• 隣接4方向に移動可能
• 現在の位置とゲームオーバーかどうかが分かる．
• 意図した方向に進める確率は1/3で，それ以外だと90度直角に進む．
• env.reset()してもマップは変わらない．

クリア条件

• Gに到達したら+1,落とし穴に落ちたら-1として，直近100回のスコアの平均が0.78以上獲得
• 意図した方向に1/3の確率でしか進めないので，1.0になることはまずない．

表示

SFFF
FHFH
FFFH
HFFG

• S: ゲーム開始地点
• G: クリア地点(移動できれば成功)
• H: 落とし穴(落ちると失敗)
• F: 移動できる場所

解法

Q学習を使って解きました．

Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha (r_{t+1} + \gamma \max_{a' \in A(s')} Q(s_{t+1}, a') - Q(s_t, a_t))

下記値をハイパーパラメータとしました．

• $\alpha = 0.03$
• $\gamma = 0.90$
• $\epsilon = 0.001$

Code

# -*- coding: utf-8 -*-
import logging
logging.basicConfig(level=logging.INFO)
logger = logging.getLogger(__name__)
import numpy as np
import gym
from gym import wrappers

def run():
    env = gym.make("FrozenLake-v0")
    env = wrappers.Monitor(env, directory="/tmp/frozenlake-v0", force=True)
    logger.info("Observation Space: %d, Action Space: %d" % (env.observation_space.n, env.action_space.n))
    max_episode = 10000
    Q = np.zeros((env.observation_space.n, env.action_space.n)) # Action Values
    Gs = [] # Revenues
    best = -1
    for episode in range(max_episode):
        x = env.reset()
        X = [] # States
        done = False
        alpha, gamma = 0.03, 0.9
        while not done:
            if np.random.random() < 0.001:
                a = np.random.randint(env.action_space.n)
            else:
                a = np.argmax(Q[x,:])
            X.append(x)
            x, r, done, info = env.step(a)
            if done:
                r = (2*r - 1) * 100.0
            logger.debug("State: %d, Reward: %d, Done: %s, Info: %s" % (x, r, done, info))
            x_pre = X[-1]
            Q[x_pre,a] += alpha * (r + gamma * np.max(Q[x,:]) - Q[x_pre,a])
        Gs.append(int(r > 0))
        avg = np.mean(Gs[-100:])
        best = max(best, avg)
        logger.info("Episode: %d, End of turn: %d, Revenue: %.2f, Average: %.2f, Best: %.2f" % (episode, len(X), r, avg, best))

if __name__ == "__main__":
    run()

Score

• Episodes to solve: 1909
• Best 100-episode average reward: 0.80 ± 0.04.

References

1. Q学習
2. squirrelinhell's algorithm
3. sakib-shahriyar's algorithm