強化学習
Q学習
OpenAIGym

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

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

https://gym.openai.com/envs/FrozenLake8x8-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

https://github.com/namakemono/openai-gym-benchmark/blob/master/envs/frozen_lake_v0.py

# -*- 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