강화학습 - TD control

BSH·2023년 5월 23일
0

강화학습_basic

목록 보기
9/12

MC 컨트롤에 이어 TD를 사용하는 방법에 대해 알아볼 차례입니다.

SARSA

TD를 이용해 q(s,a)q(s, a)를 구하는 방법은 SRASA라는 이름으로 불립니다.

상태 s에서 액션 a를 하고 보상 r를 받고 상태 s'에 도착해 다음액션 a'을 합니다. 이 알파벳을 연결해 SRASA가 되기 때문에 알고리즘 이름이 SRASA가 되는 것이었습니다.

학습에 사용되는 식은 아래와 같습니다. 모두 벨만 기대 방정식으로 부터 나왔습니다.
TD로 V학습 : V(S):=V(S)+α(R+γV(S)V(S))V(S) := V(S) + \alpha(R+\gamma V(S')-V(S))
TD로 Q학습 : Q(S,A):=Q(S,A)+α(R+γQ(S,A)Q(S,A))Q(S, A) := Q(S, A) + \alpha(R+\gamma Q(S', A')-Q(S, A))

SARSA 구현

이번에도 그리드 월드를 그래도 사용합니다.
환경은 그대로이고 업데이트 방식만 바뀌었습니다.

class QAgent:
    def __init__(self, nr, nc, obstacles):
        self.nr = nr
        self.nc = nc
        self.obstacles = obstacles

        self.q_table = np.zeros((nr, nc, 4))
        self.eps = 0.9
        self.alpha = 0.1
    
    def select_action(self, s):
        r, c = s
        coin = random.random()
        if coin < self.eps:
            action = random.randint(0, 3)
        else:
            action_val = self.q_table[r, c, :]
            action = np.argmax(action_val)
        return action

    def update_table(self, transition):
        s, a, reward, s_prime = transition
        r, c = s
        next_r, next_c = s_prime
        a_prime = self.select_action(s_prime) # s'에서 선택할 액션(실제로 가는건 아님)
        self.q_table[r, c, a] = self.q_table[r, c, a] + self.alpha * (reward + self.q_table[next_r, next_c, a_prime] - self.q_table[r, c, a])


    def anneal_eps(self):
        self.eps -= 0.01
        self.eps = max(self.eps, 0.01)
    
    def show_table(self):
        q_lst = np.argmax(self.q_table, axis=2).tolist()
        for r_idx, _r in enumerate(q_lst):
            for c_idx, _c in enumerate(_r):
                if (r_idx, c_idx) in self.obstacles:
                    q_lst[r_idx][c_idx] = '◼'
                elif _c == 0:
                    q_lst[r_idx][c_idx] = '→'
                elif _c == 1:
                    q_lst[r_idx][c_idx] = '←'
                elif _c == 2:
                    q_lst[r_idx][c_idx] = '↑'
                elif _c == 3:
                    q_lst[r_idx][c_idx] = '↓'
                
        for r in q_lst:
            for c in r:
                print(c, end=" ")
            print()

대부분 그대로이고 update_table만 변경되었습니다. MC에서는 전체 경로인 history를 인자로 받았지만 이제는 transition(상태 전이 한 번을 뜻함)을 인자로 받습니다. 상태 s에서 a를 하고 보상 r을 받고 상태s'에 도달하면 (s, a, r, s')가 하나의 트랜지션입니다.

메인 함수 코드도 보겠습니다.

def main():
    row_len = 5
    col_len = 7
    obstacles = [(0, 2), (1, 2), (2, 2), (2, 4), (3, 4), (4, 4)]
    env = GridWorld(row_len, col_len, obstacles)
    agent = QAgent(row_len, col_len, obstacles)
    
    for _ in range(1000):
        done = False
        s = env.reset()
        while not done:
            a = agent.select_action(s)
            s_prime, reward, done = env.step(a)
            agent.update_table((s, a, reward, s_prime))
            s = s_prime
        agent.anneal_eps()
    agent.show_table()
    
main()

### 출력 ###
↓ ↑ ◼ → → → → 
↑ ↓ ◼ → → → ↓ 
↓ ↓ ◼ ↑ ◼ ↓ ↓ 
→ → → ↑ ◼ ↓ ↓ 
→ ← → ↑ ◼ → → 

깔끔한 최적해 입니다. 그러나 최적해를 따라가긴하지만 학습 도중 탐색을 얼마나 했냐에 따라서 경로 바깥의 칸들, (0, 0), (4, 0)과 같은 칸들의 최적 앤션은 가끔 이상한 방향을 가리키기도 합니다. 그래서 충분히 탐색을 하는 것의 중요함을 알 수 있습니다.

Q-learning

Q러닝도 TD를 이용해 최적 정책을 찾는 방법입니다. 강화학습을 공부하기 전에도 Q-learning을 들어보기는 했습니다. 아마 Q-learning을 통해 강화학습을 접한 분들이 많을 것 같습니다. 우선 들어가기에 앞서 off-policy와 on-policy에 대해 알아보겠습니다.

Off-Policy & On-Policy

이해하기 쉽게 A, B가 PC방에서 게임을 하는 상황을 생각해보겠습니다. 둘은 같이 게임을 하려고 했는데 B는 돈이 없어 A만 게임을 하고 B는 A가 게임을 하는 것을 지켜봅니다. A는 본인이 직접 게임을 플레이하며 안 좋았던 플레이는 보완하고 좋았던 플레이는 다듬으면서 학습할 수 있습니다. 그런데 B는 A의 경험을 관찰만 하지만 그 관찰을 하면서 실력을 증진시킬 수 있습니다. A, B의 경우를 각각 on-policy, off-policy라고 합니다.

  • On-Policy : 타깃 정책과 행동 정책이 동일
  • Off-Policy : 타깃 정책과 행동 정책이 다름

타깃 정책(target policy)은 강화하고자 하는 목표가 되는 정책이고 학습을 통해 계속 업데이트하며 강화되는 정책입니다. 반면 행동 정책(behavior policy)은 실제로 환경과 상호작용하며 경험을 쌓고 있는 정책을 의미합니다. 이 때까지 배운 내용은 모두 on-policy상황이었습니다. off-policy와 지도학습이 비슷하게 보일 수 있지만 둘은 엄연히 다릅니다. 지도학습은 정답이 있고 그 정책을 그대로 따라서 학습하는 반면 off-policy 학습은 강화 학습에 해당하며 관찰하는 경험중에서 좋은 것은 반영하고 좋지않은 것은 수정하기도 합니다.

Off-Policy 학습의 장점

  1. 과거의 경험을 재사용할 수 있음
    on-policy는 타깃 정책과 행동 정책이 일치해야하지만 off-policy는 그럴 필요가 없습니다. 예를 들어 π0\pi_{0}를 통해 경험을 쌓고 π1\pi_{1}로 정책을 업데이트 하였습니다. on-policy의 경우에는 π1\pi_{1}을 학습하기 위해 다시 정책π1\pi_{1}으로 경험을 쌓아야하지만 off-policy의 경우에는 π0\pi_{0}에서 경험한 샘플을 다시 π1\pi_{1}학습에 사용할 수 있습니다.
  2. 사람의 데이터로부터 학습할 수 있음
    off-policy방법론에는 행동 정책에 어떤 정책을 가져다 놔도 됩니다. 초기에 무의미한 행동을 반복하는 단계에 전문가가 만든 좋은 데이터를 학습에 사용할 수 있습니다.
  3. 1:N, N:1 학습이 가능
    동시에 여러개의 정책을 학습시킨다고 가정할 때 이중에서 1개의 정책만 경험을 쌓게 하고, 나머지는 그로부터 생성된 데이터를 이용해 여러 개의 정책을 업데이트 할 수 있습니다. 반대로 여러 개의 정책이 겪은 경험을 모아서 한 개의 정책을 업데이트 할 수도 있습니다.

Q-learning의 이론적 배경

시작하기 전 벨만 최적방정식을 보면서 가도록 하겠습니다.

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

qq_{*}를 알게 되는 순간 MDP에서 최적의 행동을 선택합니다. 최적의 정책을 나타내는 식은 아래처럼 표현할 수 있습니다.

π=argmaxaq(s,a)\pi_{*}=argmax_{a}q_{*}(s, a)

벨만 최적 방정식을 풀어서 보겠습니다.

q(s,a)=rsa+γΣsSPssamaxaq(s,a)q_{*}(s, a)=r^{a}_{s}+\gamma \Sigma_{s' \in S}P_{ss'}^{a}max_{a'}q_{*}(s', a')

위는 q(s,a)q_{*}(s, a)q(s,a)q_{*}(s', a')어떤 관계에 있는지 재귀적으로 나타낸 식입니다. 그러나 MDP정보를 모르면 식을 그대로 사용할 수 없습니다.

그래서 아래처럼 샘플링을 통한 기댓값을 사용해야합니다.

q(s,a)=Es[r+γmaxaq(s,a)]q_{*}(s, a)=\mathbb{E_{s'}}[r+\gamma max_{a'}q_{*}(s', a')]

이제 위식을 사용해 TD학습을 하면 됩니다. q(s,a)q_{*}(s, a)의 값을 담기위한 테이블을 만들고 r+γmaxaq(s,a)r+\gamma max_{a'}q_{*}(s', a')을 정답으로 보고 그 방향으로 업데이트 하면 됩니다.
SARSA와 Q러닝의 식을 비교해 보겠습니다.

SARSA:Q(S,A):=Q(S,A)+α(R+γQ(S,A)Q(S,A))Qlearning:Q(S,A):=Q(S,A)+α(R+γmaxAQ(S,A)Q(S,A))SARSA:Q(S, A):=Q(S, A)+\alpha(R+\gamma Q(S', A')-Q(S, A))\\ Qlearning:Q(S, A):=Q(S, A)+\alpha(R+\gamma max_{A'}Q(S', A')-Q(S, A))

두식이 거의 비슷합니다. 어떤 점에서 차이가 있길래 SARSA는 on-policy이고 Q-learning은 off-policy일까요?

SARSA Q-learning
행동 정책 Q에 대해 ϵ-greedy Q에 대해 ϵ-greedy
타깃 정책 Q에 대해 ϵ-greedy Q에 대해 greedy

SARSA의 경우 행동정책과 타깃정책이 동일하지만 Q-learning의 경우에는 타깃 정책이 순수하게 가장 Q값이 높은 액션을 선택합니다.

SARSA는 벨만 기대 방정식이 근본이고 Q-learning은 벨만 최적 방정식이 근본입니다.

SARSA:qπ(st,at)=Eπ[rt+1+γqπ(st+1,at+1)]Qlearning:q(s,a)=Es[r+γmaxaq(s,a)]SARSA: q_{\pi}(s_{t}, a_{t})=\mathbb{E_{\pi}}[r_{t+1}+\gamma q_{\pi}(s_{t+1}, a_{t+1})]\\ Q-learning: q_{*}(s, a)=\mathbb{E_{s'}}[r+\gamma max_{a'}q_{*}(s', a')]

두 식 모두 기댓값 연산자이지만 Eπ\mathbb{E_{\pi}}의 경우에는 정책 함수 π\pi를 따라가야 합니다. 그리고 벨만 기대 방정식에 정책에 의한 확률적 요소 π(as)\pi(a|s)와 환경에 의한 확률적 요소 PssaP_{ss'}^{a}가 포함되어 있습니다. 그래서 샘플링시 이 두 가지를 고려하여 기댓값을 구하는 것입니다.
반면 Es\mathbb{E_{s'}}의 경우에는 PssaP_{ss'}^{a}와 관련있을 뿐 정책π\pi와 아무런 관련이 없습니다. 다시말해 어떤 정책을 써도 상관없다는 얘기입니다. 임의의 정책을 통해 주어진 환경에서 데이터를 모으면 PssaP_{ss'}^{a}가 모두 반영되도록 샘플링을 할 수 있습니다. 벨만 최적 방정식에서 π\pi는 없는데 이는 환경에 존재하는 모든 정책에서 최적의 정책은 환경에 의존적이기 때문입니다. 따라서 환경을 잘 탐험한다면 최적 정책을 찾을 수 있으며 환경을 탐험하는데 어떤 정책을 쓰던 상관이 없습니다.

Q-learning 구현

class QAgent:
    def __init__(self, nr, nc, obstacles):
        self.nr = nr
        self.nc = nc
        self.obstacles = obstacles

        self.q_table = np.zeros((nr, nc, 4))
        self.eps = 0.9
        self.alpha = 0.1
    
    def select_action(self, s):
        r, c = s
        coin = random.random()
        if coin < self.eps:
            action = random.randint(0, 3)
        else:
            action_val = self.q_table[r, c, :]
            action = np.argmax(action_val)
        return action

    def update_table(self, transition):
        s, a, reward, s_prime = transition
        r, c = s
        next_r, next_c = s_prime
        # Q-learning
        self.q_table[r, c, a] = self.q_table[r, c, a] + self.alpha * (reward + np.amax(self.q_table[next_r, next_c, :]) - self.q_table[r, c, a])

    def anneal_eps(self):
        self.eps -= 0.01
        self.eps = max(self.eps, 0.01)
    
    def show_table(self):
        q_lst = np.argmax(self.q_table, axis=2).tolist()
        for r_idx, _r in enumerate(q_lst):
            for c_idx, _c in enumerate(_r):
                if (r_idx, c_idx) in self.obstacles:
                    q_lst[r_idx][c_idx] = '◼'
                elif _c == 0:
                    q_lst[r_idx][c_idx] = '→'
                elif _c == 1:
                    q_lst[r_idx][c_idx] = '←'
                elif _c == 2:
                    q_lst[r_idx][c_idx] = '↑'
                elif _c == 3:
                    q_lst[r_idx][c_idx] = '↓'
                
        for r in q_lst:
            for c in r:
                print(c, end=" ")
            print()

SARSA에서 update_table만 바뀌었습니다. 나머지는 SARSA 코드와 동일합니다.

학습 결과는 아래와 같습니다.

↑ → ◼ ↑ ← ← → 
← ↓ ◼ → → → ↓ 
↓ ↓ ◼ ↑ ◼ ↓ ↓ 
→ → → ↑ ◼ ↓ ↓ 
← → → ← ◼ → → 

귀퉁이 부분은 SASRA와 조금 다르지만 가는 길은 똑같습니다. 두 방법 모두 최적 정책에 도달했습니다.

이제 강화학습에서 작은 문제에 대해 다룰 때의 방법론에 대한 것은 끝이 났습니다. 앞으로의 내용은 실제 세계에서 테이블 룩업방법으로는 불가능한 큰 문제에 대한 접근법을 배웁니다.

profile
컴공생

0개의 댓글