Written by LSM
on July 25, 2019

RL : AI KOREA 2019

AIKOREA 2019

알기 쉬운 강화 학습 (1), 강의자 : 성균관대학교 이종욱 교수

이전부터 유명했지만 AlphaGo(Supervised Learning + Reinforcement Learning)를 통해 더 유명해짐
Super Mario, Atari 게임 등을 강화학습을 이용해 문제를 풀어감
ICLR에서도 강화학습이 활발히 연구되고 있음

강화학습

Learning
- 정답을 알려주지는 않지만 상대적 반응(좋은 반응, 덜 좋은 반응, 나쁜 반응 등)을 통해 좋은 행동을 찾아감
- 이런 배우는 것을 모방하는 것을 강화학습이라 함
환경과 interaction 하는 것이 강화학습
Supervised가 아님
피드백이 나중에 올 수 있음(시간의 개념이 들어감)
- 상대적 피드백
Agent가 피드백에 의해 Action을 수행

=> 어떻게 좋은 결정을 내릴지 학습하는 과정

State : 연속적인 상황
Reward : 상대적인 반응 (좋은 거 나쁜거는 한 스텝으로는 알 수 없음)
Action : Reward를 잘 얻기 위해 주체적으로 하는 행동
Agent : state마다 action을 수행해 reward 값을 얻어오는 것

action 정의는 어렵지 않지만 state, reward 정의가 어려울 수 있음
- 복잡한 게임은 정의에 따라서 성능이 달라질 수 있음

기본 용어

MDP
Policy Value, Model
Planning vs Learning
Prediction vs Control
Exploration vs Exploitation

MDP

마르코프 가정
- 미래를 예측할 때 과거의 한 스텝 전만 고려해서 미래를 예측
  - p(s_t+1 s_t) = p(s_t+1 s_1, s_2 …, s_t)
Markov Processes (MP)
- 환경과 Interaction이 Action 없이 진행되는 것
- Reward 역시 없음
- State, State Transition Probability만 존재함
- 정의
  - s : state 집합
  - p : 다른 상태로 갈 확률
    - Transition Probability를 행렬로 표현하면 각 행의 확률 합이 1이 되어야 함
- MC Episodes
  - 발생할 수 있는 Sequential Event를 의미
Markov Reward Process (MRP)
- Reward가 존재하는 모델
- Expectation을 통해 Reward가 적용됨 (평균적으로 어느 정도 값을 얻을 것인가)
- Action은 없음
- Agent가 주체적으로 움직이지 않음
- Discount Factor : 현재 스텝과 그 다음 스텝에서 얻는 reward에 대해 차이를 두겠다는 의미
  - Discount Factor = 1, 에피소드가 무한일 경우 끝나지 않을 수 있음
  - 에피소드가 무한이 아닐 경우 Discount Factor = 1이라도 상관은 없음
- Value Function
  - state에 대해 Expected return 값의 함수
  - 현 state에서 수많은 에피소드를 통해 평균적으로 이 정도의 값을 얻을 것이다라는 것
  - v(s) = E[G_t S_t = s] => v(s) = E[R_t + gamma*v(s_t+1) s_t = s]
  - 무한정하게 에피소드가 많게 되면 예측을 해야함
  - Analytic을 통해 복잡도는 O(n^3)
    - n 이 작아야 함을 가정
    - P를 의미 안다고 가정
  - Dynamic Programming을 통해 계산 복잡도는 O(n^2)으로 줄일 수 있음
Markov Decision Process (MDP)
- Action이 추가된 모델
- p, r은 state와 action에 의해 값이 결정되게 됨
- MDP 튜플 : (S, A, P, R, gamma)
- policy : 각 state마다 어떻게 이동할 것인지 결정하는 것
- MDP Policy
  - state 마다 전략을 만드는 것
  - state들의 전략을 묶어놓은 것이 Policy
  - Policy는 여러개 존재할 수 있음
  - π(a s) = p(A_t = a S_t = s)
  - state-value function
    - Policy를 이용해서 value를 계산하는 것
    - state에 도달했을 때 어떤 value를 얻을 것인가
  - action-value function
    - action 마다 분류해 실제로 얻는 value 값이 얼마냐를 계산
    - 이것을 정확히 아는 것이 중요
    - 이것을 알면 state-value function 역시 구할 수 있을 것
Bellman Equation
- Bellman Expectation Equation
  - Optimal Policy
    - pi >= pi’, 더 좋은 policy를 찾지 못하는 과정
    - 매 state 마다 자신 취하는 것이 최적이라는 것을 의미
    - state-value : action을 최대화 하는 것을 찾음
    - action-value : π를 최대화하는 것을 찾음
Expectation : 모든 것들을 평균
Optimaility : 모든 것들 중 최대화한 값

알기 쉬운 강화학습 (2), 강의자 : 성균관대학교 김유성 교수

Bellman Expectation Equation
- 각 state로 부터 value가 어느정도 될 것이라고 기대되는 것
Bellman Optimality Equation
- Optimal value를 안다고 가정
  - state에서 action을 취했을 때 값을 정할 수 있음
Index
1. Planning with a known Model
  - Dynamic Programminng
2. Model-free Learning
  - Montel-Carlo
  - Temporal Difference

1. Dynamic Programming

Perfect하게 모델을 알고 있다면 문제를 풀 수 있음
- Policy Predicition
  - Policy가 어떤 값들이 가지고 있다고 가정
- Policy Control
  - Policy 값들을 조정해 더 나은 성능이 나오게 함
Iterative Policy Evaluation을 진행할 수 있음
- 무수히 많이 돌려 value가 수렴하게 됨
- (쉬운 문제의 경우) Greedy하게 policy를 뽑아도 최적의 policy에 따라 가게됨
Policy Iteration
- 각각의 Policy를 greedy하게 뽑아냄
- 뽑아낸 Policy를 통해 현재의 Policy를 업데이트
- 업데이트를 해도 달라지지 않으면 Optimal Policy (수학적으로 증명됨 !!!!!!!)
Modified Policy Iteration
- 수렴을 위해서는 몇 번이나 돌려야 하는가?
  - 수렴하지 않아도 Policy가 적합한 경우가 있었음
- dp 1번만 돌린 경우에도 optimal policy가 찾아진다는 것이 증명됨
  - 무수히 많이 돌릴 필요가 없음. 1번만 돌려도 optimal policy를 얻을 수 있는 것이 증명됨 =>value iteration
Value Iteration
- dp를 1번만 돌려서 optimal policy가 나옴
- bellman equation을 그냥 가져다 쓰는 거와 같은 결과가 나옴

2. Model-Free Reinforcement Learning

Model-Free
- prediction
  - state, value를 찾음
- control
  - 찾은 값을 기준으로 policy 업데이트
- 모델을 알지 못해도 value evaluation이 가능
- 모델을 알고 있어도 규모가 큰 경우 model-free 방법을 이용함
- ex) 헬리콥터 비행, 로봇 축구, 자율주행 등
Monte-Carlo Method
- 모르는 것에 대해 결과를 샘플링 하면 정답에 가깝게 가게 됨
- bootstraping 작업은 없음
  - bootstraping : 다음 state 값을 가져와 사용
- 에피소드를 끝까지 끝낸 후 다음 에피소드 진행시 업데이트 된 값을 기준으로 진행
Monte-Carlo Policy Evaluation
- 샘플링을 많이 할 수록 state에 대한 기댓값은 정확해짐
- 동일 스텝을 재방문시 대응 방법
  - First Time step
    - 처음 방문했을 때만 값을 증가
  - Every Time step
    - 방문할 때마다 값을 증가
Incremental Mean Update
- 새로운 에피소드를 진행할 때마다 평균 값이 나오게 됨
- 데이터가 너무 많게 되면 평균이 의미가 없어질 수 있음
  - 환경이 계속 변하면 안 좋을 수 있음
  - 적절한 hyper-parameter가 필요하긴 함
Temporal-Difference Learning
- Monte-Carlo는 에피소드가 끝날 때마다 업데이트하기 때문에 바로 업데이트가 힘듦
  - 자율 주행, 에피소드가 긴 게임(스타크래프트?), 에피소드가 끝나지 않는 작업
  - Monte-Carlo를 변형시키는 예외가 있긴 함
- Monte-Carlo는 얻어지는 기댓값이 다름
  - 길게 하고 끝날 수도 있고 짧게 하고 끝날 수 있음 => Variance가 매우 큼
- TD는 매 step마다 value 값을 업데이트 해줌
- 지속적 task라도 value가 게속적으로 업데이트 됨 => Variance가 낮음
- Bootstraping을 사용
Model-Free Control
- Model-Free의 경우 State Transition Probability를 모르기 때문에 Greedy Policy를 그대로 쓸 수 없음
- Q를 이용하면 Transition Probability를 알지 못해도 계산이 가능
- Monte-Carlo로 Q를 계산 후 Greedy Policy를 통해 업데이트 가능
- Q) Policy를 Greedy 하게 뽑아도 될까?
  - 문제가 크지 않으면 작아도 괜찮음
  - 샘플링에 따라 영향을 많이 받음
Exploration & Exploitation
- Exploration
  - 최적의 길이 아님에도 도전하는 것
- Exploitation
  - 지금까지의 결과를 가지고 최적의 길을 선택
- ε-greedy
  - 일정 % 이상은 학습한 최적의 결과에 따라 움직임
  - 일정 % 이하는 탐험하는 것
  - 초반에 학습 시 ε을 크게 하여 탐험을 많이하고 후반에는 ε을 적게 하여 최적의 길에 따라 움직임
  - 환경이 Dynamic 시 ε을 채택, 환경이 Stable 하다면 ε을 0으로 설정하고 진행해도 됨

알기 쉬운 강화학습 (3), 강의자 : 성균관대학교 김유성 교수

Value Function Approximation
- Q-table을 그대로 이용하는 것은 불가 => Q-table을 근사해주는 방법이 필요
- Q-Network Prediction : ex) Neural Network
- 학습법
  - Optimal한 Q 값을 안다는 가정
  - (Optimal한 값 - Estimation 값)을 줄일 수 있도록 학습하는 것
  - 차가 적으면 Optimal한 값을 구한 것
- Optimal한 Q가 무엇인가??????
  - MC을 사용해서 샘플링을 통해 구함
  - (DQN 등에서 실제 사용) TD를 사용해 다음 상태에서 가져올 수 있는 가장 큰 Q 값을 가져옴
문제점
- Sequential한 학습 -> 학습의 편향을 일으킨다!!!!! (데이터 Correlation)
- Prediction을 이용한 Prediction을 함 -> 정말 믿을만 하니????????
  - Non-Stationary Target
    - J(w)의 Q-perediction을 업데이트 하게 되면 Q-target 역시 업데이트 하게 됨 (Moving Target)
    - Error가 계속 유지가 되고 수렴이 되지 않는 이슈가 발생
Deep Q-Networks
- 딥뉴럴 네트워크
  - 너무 깊게 쌓으면 Inference 시간이 길어짐 -> Atari 류에서는 긴 시간이 별로 좋지는 않음
- Experience Replay
  - Correlation 문제를 해결
  - Experience Replay Buffer
    - 과거의 데이터를 쌓아놓는 버퍼
    - 채워지기 전까지는 학습을 진행하지 않음
    - 샘플을 통해 학습하나 랜덤하게 뽑아 mini-batch가 진행됨
- Fixed Target
  - Moving Target의 문제를 해결
  - 네트워크가 같으면 학습이 어렵다 => 뉴럴 네트워크를 2개로 구성(w, w’)
  - w에 대한 네트워크만 학습, w’는 학습을 시키지 않음
  - 일정시간 이후에 w로 부터 w’ 값을 업데이트
Value-based RL vs Policy-based RL
- Actor-Critic
  - Policy 기반으로 학습하되 Value 역시 참조해 문제를 품
  - 현재 가장 많이 사용되는 방법
- value-based의 문제
  - action이 discrete 해야 함 (ex. 오른쪽, 왼쪽 이동)
  - action이 continous 하는 경우 잘 안 됨(ex. 회전을 30도로 꺾어라)

← → Top