SARSA Learning

Reinforcement Learning, Temporal-Difference Learning
Page content

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

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

Open In Colab

문제 (Problem)

👤 보스

몬테 카를로와 같이 한 판이 끝날때 까지 기다리지 않고
한 칸 앞으로만 가도 학습이 되는게 있다고 하네?
아래 체육관(Gym)에 가서
‘얼음 호수8X8’ 문제를 그걸로 풀어 보게

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

⚙️ 엔지니어

또 다른 알고리듬이 등장 하겠군…
배움에는 끝이 없구냥…

문제 분석 (Problem Anaysis)

일단 Gym을 돌려 보자!

import gym
import numpy as np
from time import sleep
from IPython.display import display, clear_output, Pretty
#
# Environment
#
env = gym.make('FrozenLake8x8-v0', is_slippery=False) # 얼음위에서 미끄러지지 않도록 설정
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
  (Right)
SFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG



Episode finished after 7 timesteps

환경 (Environment)

‘얼음호수8X8’ 의 환경은 64개의 상태(State)와 4개의 액션(Action)으로 구성 되어 있다.

액션 (Action)

env.action_space
Discrete(4)

‘얼음호수8X8’ 에서는 4개의 액션이 존재한다. 그리고 각각의 액션이 번호로 지정 되어 있다.

\(A = \{0, 1, 2, 3\}\)

Num Action
0 왼쪽으로 이동 (Move Left)
1 아래로 이동 (Move Down)
2 오른쪽으로 이동 (Move Right)
3 위로 이동 (Move Up)

상태 (State)

env.observation_space
Discrete(64)

‘얼음호수8X8’의 상태(State) \(S\)는 다음과 같이 각 상태가 0과 63까지 번호로 지정되어 있다.

\(S = \{0, 1, \cdots , 63\}\)

\(\begin{vmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\ 24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\ 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 \\ 40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 \\ 48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 \\ 56 & 57 & 58 & 59 & 60 & 61 & 62 & 63 \end{vmatrix}\)

그리고 각 상태마다 액션(action), 확률(probability), 다음 상태(next state), 보상(reward), 종료(done)가 {action: [(probability, nextstate, reward, done)]} 형식으로 정의 되어 있다.

에피소드가 종료되는 상태를 기록해 놓자

\(S_{\text{terminate}} = \{19, 29, 35, 41, 42, 49, 52, 54, 59, 63\}\)

보상 (Reward)

55번의 상태를 까보자

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

63번 상태로 이동하면 \(R = 1.0\) 을 얻고 에피소드가 끝이난다.

에이전트 (Agent)

에이전트는 환경에서 부터 주어진 상태(\(S\)), 액션(\(A\)), 보상(\(R\))을 가지고 가치(Q-value)를 계산하고 정책(Policy)을 수립해서 최적의 액션을 수행해야 한다.

정책 (Policy)

에이전트가 주어진 상태에서 액션을 선택하는 확률이다.

\(\pi(s,a) = \pi (a|s) = \mathbb P[A_t = a | S_t = s]\)

상태 가치 (State Value)

상태 가치는 상태 s 에서 기대되는 미래 보상의 합이다. 여기서 \(G_t\)는 벨만 방정식(Bellman Equation)에 의해서 보상(Reward)값과 다음 스텝의 상태 가치로 분해 할 수 있다.

\(\begin{align} v_{\pi}(s) & = \mathbb E_{\pi} [G_t | S_t = s] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots | S_t = s] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \cdots) | S_t = s] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma G_{t+1} | S_t = s] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s] \end{align}\)

Q-value (State Action Value)

Q-value는 상태 s 에서 액션 a 를 수행할 경우에 기대되는 미래 보상의 합이다. 여기서 \(G_t\)는 벨만 방정식(Bellman Equation)에 의해서 보상(Reward)값과 다음 스텝의 Q-value로 분해 할 수 있다.

\(\begin{align} q_{\pi}(s,a) & = \mathbb E_{\pi} [G_t | S_t = s, A_t = a] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots | S_t = s, A_t = a] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + \cdots) | S_t = s, A_t = a] \\ & = \mathbb E_{\pi} [R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a] \\ &= \mathbb E_{\pi} [R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a] \end{align}\)

최적 가치 (Optimal Value)

상태 s 에서 가장 큰 Q-value이다.

\(q_*(s,a) = \max_{\pi} q_{\pi}(s,a)\)

최적 정책 (Optimal Policy)

\(q_*(s,a)\)가 결정 되면 \(\pi (a|s) = 1\) 이 된다. 즉 상태 s일때는 100% 액션 a를 수행 한다.

\(\pi_*(s,a) = \begin{cases} 1 & \text{if } a= \text{argmax}_{a \in A} q_\star(s,a) \\ 0 & \text{otherwise} \end{cases}\)

⚙️ 엔지니어

에이전트는
각 상태(state)의 액션(action)마다
Q-value를 계산한다.

몬테 카를로 방법은
에피소드가 끝나고 나서 \(G_t\)를 이용해서 Q-value를 계산했다.

그런데
\(G_t\) 대신에 \(R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1})\)을 이용하면
한 스텝만 이동해도 Q-value를 계산할 수 있는
신묘한 알고리듬이 된다.
그것은 바로…

살사 (SARSA)

State-Action-Reward-State-Action의 줄임말로서 미래 보상의 합 \(G_t\) 대신에 보상(Reward)값과 다음 스텝의 Q-value를 이용해서 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)\)

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

Target

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

Error (델타)

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

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

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

𝜀-greedy

다음 스텝의 액션을 선택하는 경우에 욕심쟁이(greedy)처럼 최고의 Q-value의 액션만을 선택하면 오류가 발생할 수 있다. 따라서 적당히 램덤하게 액션을 선택하는 경우를 추가한 것이 𝜀-greedy이다.

\(\pi \leftarrow \epsilon \text{-greedy(Q)}\)

𝜀의 확률로 랜덤 액션을 수행하고 (1-𝜀)의 확률로 Q-value가 가장 큰 액션을 수행한다.

학습 (Learning)

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

from tqdm import tqdm

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

# 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

for episode in tqdm(range(num_episode)):
    state = env.reset()
    done = False
    # Hyper parameter
    epsilon = 0.3
    alpha = 0.1
    gamma = 0.9
    
    if np.random.uniform() < epsilon:
        action = env.action_space.sample()
    else:
        action = np.argmax(Q_table[state])
    
    while not done:
        next_state, reward, done, info = env.step(action)
        if np.random.uniform() < epsilon:
            next_action = env.action_space.sample()
        else:
            next_action = np.argmax(Q_table[next_state])
        
        target = reward + gamma*Q_table[next_state, next_action] 
        delta = target - Q_table[state][action]
        Q_table[state][action] += alpha * delta
        state, action = next_state, next_action
100%|██████████| 1000/1000 [00:00<00:00, 3752.20it/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 🎉👍 성공! 🍺🥇')
  (Down)
SFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG




 🎉👍 성공! 🍺🥇