N-puzzle problem 설계하기

Q-learning 적용을 목표로 한다.

Sliding Puzzle은 연속적? 불연속적?

Google Atari Breakout

StarCraft 2 - Alphastar

State와 Action을 정의해보자.

State는 퍼즐의 상태, Action은 상화좌우로 퍼즐을 움직이는 행위로 정의할 수 있다.

N-puzzle State

여기서 잠깐. Monte Carlo VS Temporal Difference

Monte Carlo 이란?

Episode를 끝까지 수행한 후에 받은 Reward로 각 State의 Value Function 을 거꾸로 계산하는 방법이다. Model Free 라는 점에서 환경을 잘 모르더라도 Value Function을 구할 수 있다.

Temporal Difference 이란?

Episode를 끝까지 수행하지 않더라도 MC + DP 아이디어로 Time step 마다 학습할 수 있다.

Question. 슬라이딩 퍼즐 문제는 MC일까 TD로 해결할까?

On-policy VS Off-policy

MC와 TD는 모두 On-policy 알고리즘이다. On-policy 는 현재 Policy에서 Greedy하게 최적의 Policy를 찾는데 한계가 있다. Optimal 한 답을 못 찾을 수 있다. 따라서 움직이는 policy와 학습하는 policy를 분리시킨 것이 off-policy다.

하지만 Importance Sampling이라는 통계학적 문제가 있어서 Q-learning을 제안하게 된다.

Off-policy with Q-learning

greedy한 policy로 학습을 진행하면 수렴은 빠르지만 충분히 탐험을 하지 않았기 때문에 local에 빠지기 쉽다. $\epsilon$-greedy policy를 사용하면 수렴속도가 느려져서 학습속도가 느려지게 된다. $\epsilon$을 시간에 따라 decay시키고 아래와 같이 Q learning을 사용하면 그 문제를 해결할 수 있다.

기본개념

N-puzzle Reward??

1. Puzzle을 움직였을 때 밖으로 나가면 패널티를 준다.

2. Manhatten 거리를 Reward로 준다.

3. 퍼즐 정렬완료시 보상을 준다.

* Deep Q-learning 으로 문제 해결하기

Action Value Function 을 딥 뉴럴넷으로 Approximation 할 수 있다. 또한 Nonlinear Function을 Mapping할 수 있는 장점이 있다.

Replay Memory 에다가 샘플들을 저장한 후에 Batch 단위로 샘플링하여 학습한다.

** 문제점

Catastrophic forgetting 문제가 있다. 망각이라고도 하는데 앞에서 좋은 함수를 학습해도 뒤에서 이상한 걸 학습하는 경우가 있을 수 있다.

** 논문거리 : 도전해보세요!

ICCV 2019 : Continual Learning by Asymmetric Loss Approximation with Single-Side Overestimation 의 손실함수를 적용해서 강화학습 Task의 성능 Up!