> For the complete documentation index, see [llms.txt](https://hci-project.gitbook.io/reinforcement-learning-of-n-puzzle/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hci-project.gitbook.io/reinforcement-learning-of-n-puzzle/n-puzzle-problem.md).

# N-puzzle problem 설계하기

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

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

![Google Atari Breakout](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-LsjeC_Uq4tnaQlgwuDW%2Fimage.png?alt=media\&token=24d2937f-6021-4c6c-a91a-d06cf96c0716)

![StarCraft 2 - Alphastar](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-Lsjeat55DLHiNWebQt8%2Fimage.png?alt=media\&token=02b04512-fcb1-493f-8e7c-ead6ff5c2815)

## State와 Action을 정의해보자.

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

![N-puzzle State](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-LsjfLWiy6VPoO3pmGqt%2F1.JPG?alt=media\&token=3aea29fd-dbbc-4343-8f50-92462cd16235)

## 여기서 잠깐. Monte Carlo VS Temporal Difference

### Monte Carlo 이란?

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

### Temporal Difference 이란?

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

![](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-Lsjhb6rHuCDWKQqPWn5%2Fimage.png?alt=media\&token=765f632e-aabc-4c24-b400-0b4049ad177d)

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

## On-policy VS Off-policy

![](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-LsjiWCbLevCIRqerVZr%2F1.png?alt=media\&token=78ac282b-aeda-42d7-a9dc-02b2db4fb290)

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

![](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-LsjhHez5en8dmlqiTRf%2Fimage.png?alt=media\&token=64f4ac23-9fcb-433e-86d2-ded3ef071217)

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

## Off-policy with Q-learning

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

![기본개념](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-Lsjj1zt1hdp5f0mLuj4%2Fimage.png?alt=media\&token=22f3ed7a-866f-48b2-b5f8-840043930ba9)

![](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-LsjjEx4F83fAlI9i8BB%2Fimage.png?alt=media\&token=145f0383-a416-4054-a764-5c56412de59e)

## N-puzzle Reward??

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

### 2. Manhatten 거리를 Reward로 준다.

![](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-LsjkCDbk1rqJR0jqRt9%2Fimage.png?alt=media\&token=96ed0b01-8e15-4952-904f-375a2b7cdb32)

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

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

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

![](https://2049597759-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-Lsa-Uyh66jwfKddkd55%2F-LsjbguUzAkqERxU74u5%2F-Lsjkc0C1YoEb9d-eEAq%2Fimage.png?alt=media\&token=7a9b0061-d6a7-4915-b0f8-25812ac0f643)

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

### \*\* 문제점

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

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

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