Q-Learning

Reinforcement Learning, Q-Learning
Page content

강화 학습(Reinforcement Learning)에서 사용하는 Q-Learning에 대해서 알아 보고 Gym에서 제공하는 문제를 해결하기 위한 알고리듬을 만들어 보자.

실제로 돌려 보고 싶으면 구글 코랩으로 ~

Open In Colab

문제 (Problem)

👤 보스

SARSA에서 마지막 A를 수행을 안해도 되는 방법이 있다고 하네?
아래 체육관(Gym)에 가서
‘얼음 호수8X8’ 문제를 그걸로 풀어 보게

https://gym.openai.com/envs/FrozenLake8x8-v0/

⚙️ 엔지니어

네~ 네~

문제 분석 (Problem Anaysis)

‘얼음 호수8X8’은 살사(SARSA)에서 돌려 보았던 문제다. 이번에는 미끄러 지는 것을 추가해 보자!

import gym
import numpy as np
from time import sleep
from IPython.display import display, clear_output, Pretty
#
# Environment
#
env = gym.make('FrozenLake8x8-v0')
state = env.reset()

# Initial world display
world = env.render(mode='ansi')
display(Pretty(world))
sleep(0.5)

#
# Agent
#
for step in range(100):
    action =env.action_space.sample()
    next_state, reward, done, info = env.step(action)    
    state = next_state
    
    # updated world display
    world = env.render(mode='ansi')
    clear_output(wait=True)
    display(Pretty(world))
    sleep(0.5)
    
    if done: # an episode finished
        print("Episode finished after {} timesteps".format(step+1))
        break
  (Up)
SFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG



Episode finished after 43 timesteps

⚙️ 엔지니어

가끔 액션과는 다른 방향으로 가버린다.
과연 미끄러져서 구멍에 빠지지 않고
목표점에 도달할 수 있을까?

환경 (Environment)

‘얼음호수8X8’ 세계의 환경은 64개의 상태(State)와 4개의 액션(Action)으로 구성 되어 있다. 그리고 아래를 보자

env.P[55]
{0: [(0.3333333333333333, 47, 0.0, False),
  (0.3333333333333333, 54, 0.0, True),
  (0.3333333333333333, 63, 1.0, True)],
 1: [(0.3333333333333333, 54, 0.0, True),
  (0.3333333333333333, 63, 1.0, True),
  (0.3333333333333333, 55, 0.0, False)],
 2: [(0.3333333333333333, 63, 1.0, True),
  (0.3333333333333333, 55, 0.0, False),
  (0.3333333333333333, 47, 0.0, False)],
 3: [(0.3333333333333333, 55, 0.0, False),
  (0.3333333333333333, 47, 0.0, False),
  (0.3333333333333333, 54, 0.0, True)]}

해석을 해보면 다음과 같다.

55번 상태(state)에서,
왼쪽으로 이동하라는 액션을 주면, 1/3의 확률로 위로 이동하고, 1/3의 확률로 왼쪽으로 이동하고, 1/3의 확률로 아래로 이동한다.
아래로 이동하라는 액션을 주면, 1/3의 확률로 왼쪽으로 이동하고, 1/3의 확률로 아래로 이동하고, 1/3의 확률로 그 자리에 있는다.
오른쪽으로 이동하라는 액션을 주면, 1/3의 확률로 아래로 이동하고, 1/3의 확률로 그자리에 있고, 1/3의 확률로 위로 이동한다.
아래로 이동하라는 액션을 주면, 1/3의 확률로 그 자리에 있고, 1/3의 확률로 위로 이동하고, 1/3의 확률로 왼쪽으로 이동한다.

이렇게 미끄러짐이 추가 되면 1/3의 확률로 정상적인 액션을 수행한다.

Q-Learning

Q-Learning 의 원리는 서로 다른 정책(policy)으로 학습 시킨 데이터를 섞어도 최적화가 가능하다는 것이다.

SARSA + greedy

SARSA + greedy 방식으로 학습한 Q-value는 아래와 같다.

\(Q(S_t, A’_t) \leftarrow Q(S_t, A’_t) + \alpha \left( R_{t+1} + \gamma Q(S_{t+1}, A’_{t+1}) - Q(S_t, A’_t) \right)\)

greedy 방식은 다음 스텝의 액션을 선택하는 경우에 욕심쟁이(greedy)처럼 최고의 Q-value의 액션만을 선택한다. 따라서 다음 식을 만족한다.

\(Q(S_{t+1}, A’_{t+1}) = \max_{a’} Q(S_{t+1}, a’)\)

따라서 Q-value는 다음과 같다.

\(Q(S_t, A’_t) \leftarrow Q(S_t, A’_t) + \alpha \left( R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’) - Q(S_t, A’_t) \right)\)

SARSA + 𝜀-greedy

SARSA + 𝜀-greedy 방식으로 학습한 Q-value는 아래와 같다.

\(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left( R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \right)\)

여기서 \(Q(S_{t+1}, A_{t+1})\) 대신에 SARSA + greedy 방식으로 만들어진 \(\max_{a’} Q(S_{t+1}, a’)\)을 사용한다. 그러면…

Q-Learning

\(Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left( R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’) - Q(S_t, A_t) \right)\)

\(\alpha\) : learning rate
\(\gamma\) : 디스카운트 (discount factor)

Target

목표로 하는 값이다. 여기서 타겟은 \(R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’)\)이다.

Error (델타)

목표값과 현재값과의 차이를 \(\delta\) 라고 한다.

\(\delta_t = R_{t+1} + \gamma \max_{a’} Q(S_{t+1}, a’) - Q(S_t, A_t)\)

계속해서 에피소드를 실행 시키면서 \(Q(S_t, A_t)\)에다가 \(\alpha * \delta_t\) 를 업데이트 하면 결국 \(Q(s, a) \rightarrow q_*(s,a)\)가 된다.

⚙️ 엔지니어

SARSA에서 마지막 A를 수행할 필요 없이
Q 테이블에서 가장 큰 수의 액션을 선택하면
최적화가 가능하다는 것이 바로
Q-Learning이다!

학습 (Learning)

Q-Learning을 이용해서 최적의 Q-value를 찾아보자!

SARSA보다 코드가 깔끔하다!

from tqdm import tqdm

num_state = env.observation_space.n
num_action = env.action_space.n
num_episode = 5000

# Initialize Q_table 
Q_table = np.random.uniform(low=0.0, high=0.00000001, size=(num_state, num_action))
# Zero for terminate states
for s in [19, 29, 35, 41, 42, 49, 52, 54, 59, 63]:
    Q_table[s] = 0

# Hyper parameter
epsilon = 0.3
alpha = 0.1
gamma = 0.9

for episode in tqdm(range(num_episode)):
    state = env.reset()
    done = False
    while not done:
        if np.random.uniform() < epsilon:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q_table[state])
        next_state, reward, done, info = env.step(action)
        
        target = reward + gamma*Q_table[next_state, np.argmax(Q_table[next_state])] 
        delta = target - Q_table[state][action]
        Q_table[state][action] += alpha * delta
        state = next_state
100%|██████████| 5000/5000 [00:03<00:00, 1653.97it/s]

해결 (Solution)

state = env.reset()
done = False

# Initial world display
world = env.render(mode='ansi')
display(Pretty(world))
sleep(0.5)

while not done:
    action = np.argmax(Q_table[state]) # Optimal Policy
    state, reward, done, info = env.step(action)
    
    # updated world display
    world = env.render(mode='ansi')
    clear_output(wait=True)
    display(Pretty(world))
    sleep(0.5)
    
    if done and state == 63:
        print('\n 🎉👍 성공! 🍺🥇')
            
  (Right)
SFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG




 🎉👍 성공! 🍺🥇