Greedy Action으로 알아보는 Q-Learning

기본골자는 다이스트라 방식과 같다. 해당 방식을 이해하고 있다면 쉽게 납득할 수 있다.

---

 

개요

 

문제를 해결할 때 각 단계에서 다음 단계를 검색하고, 가장 최적이라고 생각되는 선택을 하는 방식이다.

 

전체문제를 최적으로 해결하는데 중점을 두기 보단, 현재 각 순간마다의 선택을 최적화하는데 초점을 맞춘다.

---

원리

 

간단한 행동 원리를 가지고 있다.

상 하 좌 우 로 이동하는 알고리즘을 작성하였다고 가정한다.

 

상 하 좌 우 로 이동할 때 가중치를 가지고 가장 큰 가중치를 가진 방향으로 엑터는 움직이게 된다.

처음 시작시 모든 노드의 상 하 좌 우 가중치는 0이다.

 

같은 가중치를 가질 경우 무작위 방향으로 이동한다.

목표지점에 도달하였을 경우, 임의의 함수를 사용하여 해당 방향에 ENd가 존재함을 기입한다.

 

Greedy Action은 다양한 Action으로 연결되어진다. 예시를 들어 확인해보자.

지도

위 지도를 기준으로 Start가 End로 이동하는것 이 목표라고 가정하자. Start지점에서 End로 이동해야 성공한다.

 

처음에는 무작위로 Start가 이동할 것이다. 1Action이 완료되었고, 이동방향이 결정되었음을 다음 으로 확인해보자.

위와같이 이동에 성공하면, End의 바로 밑 단계에는 위로 이동하면 End가 존재한다고 방향에 1을 표기한다.

1Action이 완료되었음으로 2Action을 진행한다.

2Action에서 진행하였을 때, 오른쪽 노드의 최대값이 1 임을 확인할 수 있다.

여기에서 1이 존재하는 노드가 있음으로, 저 상황에서  엑터가 오른쪽으로 이동함을 예상할 수 있다.

 

오른쪽으로 이동할 때, 엑터는 자기자신의 위치에 오른쪽에 1이 있다고 표시하고 이동하게 된다.

이러한 방식을 반복해서, Start와 End를 반복하였을 때 천번, 만번 반복해도 같은 결과가 나타나는 연결경로가 생겼다고 생각하자. 이것이 기본적인 Greedy Action이다.

그러나, 여기에서 무언가 찜찜함을 알 수 있는데, 최단경로는 Start에서 End로 이동하기만 하면 나타나는게 최단경로인데,

학습결과상 일단 End로 도달하기는 하나 최적의 경로는 아니라는 점이다.

 

이를 해결하기 위해 다음 방식들을 추가한다.

---

탐험 Exploration

 

입실론 - Greedy

 

입실론 ; 0 ~ 1 만큼은 랜덤!

 

랜덤한 확률로 가중치에 해당되는 이동경로로 가지 않고 무작위로 선택된 이동경로로 이동하게 하는것 을 의미한다.

탐험하면서 새로운 가중치를 확인하고. 더 나은 경로를 찾을 수 있기 때문이다.

 

Exploration & Exploitation

 

Exploration

장점

새로운 경로를 찾을 수 있다.

새로운 End를 찾을 수 있다.

(Decaying) 입실론 - Greedy

처음에는 입실론 값을 0.9 정도로 잡다가. 어느정도 값이 잡히게 되면 0으로 수렴하게 한다.

 

그러나, 여기에서는 더 가까운 경로를 찾을 수 없을지도 모른다는 가능성이 생긴다.

---

Discount Factor

수학적인 수렴성에 있다.

감마 라는걸 추가하게 되는데 이는 다음과 같다.

 

감마 : 효율적인 패스를 찾게 해준다. 0 ~1 사이의 값이다.

바로 다음노드의 값을 가져오게 될때 는 감마를 곱해서 가져와라 라는 의미이다.

만약, 소숫점이 0.5라고 가정하면 1에서 0.5를 곱해서 가져오고.. 가져오고...가져오고 를 반복하게 됨으로

거리가 멀어질 수록 값이 점점 0에 가까워질것이다.

 

그럼으로써 거리값에 따라 멀수록 0에 수렴. 가까울수록 1에 수렴하게 된다.

 

엑터는 이로써 거리값에 따른 가중치를 판별할 수 있다.

 

장점

효율적인 Path를 가져올 수 있다.

현재 vs 미래 reward를 할 수 있다.

 

즉, 감마가 작을 수록 미래에 대한 가중치를 덜 확인한다. 설레발을 덜친다.

 

수식

$Q\left ( S_{t},Q_{t} \right )\leftarrow \left ( 1-\alpha \right )Q\left( S_t,Q_t\right ) + \alpha (R_t + \gamma  maxQ(S_t{''},Q_t{''}))$

 

쓰잘데기없이 복잡하게 되어있는데, 쉽게 말하면

 

현재 노드 = (1-가중치) * 현재값 + (가중치) * (시간상수[감마] * 미래값)

을 말한다.