9장 강화학습과 게임지능

9.4 학습기반 알고리즘

  • 앞선 동적 프로그래밍은 상태 전이 확률 분포(모델)를 완벽하게 알아야함
  • 모델을 모르는 경우에 학습에 필요한 에피소드가 필요함
  • 에피소드를 얻는 방법
    • 환경 및 이론을 시뮬레이션
    • 프로그램 대 프로그램의 대결 방법 등
  • 학습 기반 algorithm : episode를 tarining data로 활용

9.4.1 몬테카를로 방법

  1. 과정
    1. agent가 환경과 상호작용하면서 episode를 진행
      • 초기 상태에서 시작하여 종료 상태(실패,성공)에 이르기 까지 상태, 행동, 보상을 저장
    2. episode가 종료되면 수집된 보상을 바탕으로 각 상태의 가치함수를 업데이트함. (평균을 이용)
      • episode로 부터 훈련에 사용할 데이터를 추출할 때 상태 중심으로 에피소드를 잘라 추출함
      • episode : {[상태,보상]행동[상태,보상]행동[상태,보상]행동[상태,보상]행동 …}
      • training data Z 추출 : {[상태,보상]행동[상태,보상]} -> 어떤 상태에서 시작했는지 별로 모으기
      • 가치함수 업데이트 방법

        • 상태가치 함수 $v_\pi (S) = \frac{1}{Z(S)} \sum_{z \in Z(S)} r(z), \forall s \in S$

        • 행동가치 함수 $q_\pi (s, a) = \frac{1}{Z(s, a)} \sum_{z \in Z(s, a)} r(z), \forall s \in S, \forall a \in A$

    3. 단순하게 설명
      • 난수를 이용해 episode 발생시켜 훈련 데이터를 수집하고 식을 이용해 가치함수를 계산함
  2. 특징
    • 모델 의존 x
    • epdisode에서 얻은 모든 경험을 활용하여 정책을 개선함
    • 이웃 상태의 정보를 전혀 고려하지 안힉 때문에 bootstrap 방법이 아님
  3. 장점
    • 단순, episode에서 얻은 경험을 효율적으로 활용
  4. 단점
    • episode가 길거나 종료되지 않는 환경에서는 사용하기 어려움
    • 변동성이 크고 데이터가 많이 필요함

9.2.4 시간차 학습 알고리즘 (Sarsa, Q learning)

학습 기반 알고리즘 + bootstrap

  • 종료 순간 까지 가보지 않고 이웃 상태로 변경했을 때 가치함수를 개선하고싶음
  • time difference(TD) learning
  1. TD learning을 위한 공식 유도
    • 현재 상태 $s$에서 행동 $a$을 취했을 때 다음 상태 $s’$와 다음 상태의 보상$r’$에 접근할 수 있어야함
    • 기존 몬테카를로 식에서 $s’$, r’$에 관련된 식으로 유도함

    • episode + bootstrap

    • 상태가치 함수 $v(s_t) = v(s_t) + \rho (r_{t+1} + \gamma v(s_{t+1}) - v(s_t))$
    • 행동가치 함수 $q(s_t, a_t) = q(s_t, a_t) + \rho (r_{t+1} + \gamma q(s_{t+1}, a_{t+1}) - q(s_t, a_t))$
  2. Sarsa
    • on policy
    • agent가 현재 학습하고 있는 정책에 따라 행동을 선택함
    • $s$-$a$-$r$-$s’$-$a’$
    • 현재상태 $s$에서 행동 $a$를 결정 -> 결과로 보상 $r$과 다음 상태 $s’$를 얻음 -> 다음 행동 $a’$를 결정
    • 과정
      1. Q-value $q(s,a)$ 초기화
      2. episode 시작
      3. $a = \arg\max_a q(s,a)$에 따라 행동 $a$를 선택 / 필요시 e-greedy 적용
      4. 선택한 행동 $a$를 실행하여 보상 $r$과 다음 상태 $s’$를 얻음
      5. $q(s, a) \leftarrow q(s, a) + \rho [r + \gamma q(s’, a’) - q(s, a)]$
      6. $s$와 $a$를 업데이트하고 3번으로 돌아가 반복
  3. Q learning
    • off policy
    • agent가 현재 정책을 따르지 않고, 최적의 행동을 선택하는 것을 의미
    • 과정
      1. Q-value $q(s,a)$ 초기화
      2. episode 시작
      3. $a = \arg\max_a q(s,a)$에 따라 행동 $a$를 선택 / 필요시 e-greedy 적용
      4. 선택한 행동 $a$를 실행하여 보상 $r$과 다음 상태 $s’$를 얻음
      5. $q(s, a) \leftarrow q(s, a) + \rho \left[ r + \gamma \max_a q(s’, a) - q(s, a) \right]$
        • $\max_a q(s’, a)$ : 다음 상태에서 가능한 모든 행동 중 최대 q-vqlue를 의미
      6. $s$를 업데이트하고 3번으로 돌아가 반복
  4. 각각의 특징
    • Sarsa
      • 정책에 따라 행동을 선택하므로 안정적
    • Q-learning
      • 최적의 행동을 추구하므로 더 빠르게 최적의 해를 찾음
      • 불안정할 수 있음