Lecture 4: Q-Learning (table)

전 게시글에서 봤던 Dummy Q-Learning algorithm입니다. 이것은 문제가 있습니다.. 이 문제가 어떠한 문제인지 알아보겠습니다.

우리는 Q값을 다음과 같이 업데이트 시켰습니다.

결과를 보게 되면 문제가 있다는 것을 눈치채실 겁니다.

이것을 현재값을 이용하는 Exploit과 탐험을 통해 더 좋은 Q값을 찾아 나서는 Exploration이 있습니다.

식당을 예로 들어보겠습니다. 많은 식당들 중 처음에는 아무곳도 가보지 않았기 때문에 전부 0점입니다.

어느 시점에서 이 식당들을 1번 씩 다 갔을 때 평일은 Exploit을 하고, 주말에는 Exploration을 하자라는 예가 있습니다.

Q-Learning에서도 어떤 길을 갈 것인가에서 Exploit과 Exploration이 충돌합니다. 이것을 저희는 $\epsilon-greddy$라고 합니다.

e = 0.1로 지정했다고 하면

랜덤한 값을 주사위를 던져서 찾은 다음 이 값이 e보다 작다면은 랜덤하게 갑니다.

만약 이 값이 e보다 크다면은 알고 있는 값 중 최댓값을 따라가게 됩니다.

학습 초기에는 랜덤하게 많이 가고, 즉 e값이 큰 값이고, 학습 후반부에는 좀 작게 가자라는 것을 우리는 decaying이라고 부릅니다.

Exploit과 Exploration에는 많은 방법이 있지만 이 방법은 랜덤한 노이즈를 추가하는 방법입니다.

• 점수가 주어져 있다고 가정합시다.

• 위에서 값이 주어져 있을 때, 이 값에다 노이즈를 추가를 합니다.
• 노이즈를 랜덤한 값으로 주는데 랜덤값이 더해진 값들 중에서 argmax값을 고르는 것입니다.

물론 여기에도 우리는 decaying하는 방법을 사용할 수 있습니다.

• 처음에는 높은 값의 value를 더할 수 도 있지만 나중에 갈수록 작은 값의 랜덤 value를 더합니다.
• 대체로 $\epsilon - greddy$방법은 decaying하게 되면 가장 낮은 값이 선택될 수도 있지만, random noise는 대체로 첫번째가 선택이 안된다면 두번째로 높은값이나 세 번째로 높은 값들이 많이 선택됩니다.

위에서 말한 방법들을 사용하게 되면 여러 갈래의 최적 길들을 찾아낼 것입니다.

Action을 어떻게 선택하느냐라는 것에 대해 궁금증을 가지실 수 있습니다. 그렇다면 우리는 이 Action을 어떻게 선택할까요?

• Exploit과 Exploration의 방법으로 선택하게 됩니다.

우리가 Exploit과 Exploration을 통해서 여러가지의 갈래 길을 찾았다고 가정합시다.

Agent가 다음과 같은 위치에 있게 되면 어디로 가야 할지 헷갈리게 됩니다.

이것을 해결하기 위해 우리는 Dicounted Reward라는 것을 사용합니다. 이 말은 다른 책에서 나오는 Discount Factor(감가율)과 같은 말입니다.

• 즉 늦게 보상을 받았다면 같은 값이더라도 늦게 받은 것에 대해 0 ~ 1 사이의 실수값을 곱해주게 됩니다. 곱하게 되면은 값이 작아지겠습니다.
• 가치의 기반으로 생각하시면 쉽습니다.
• $\gamma$로 표시하며 할인률 또는 감가율이라고 불립니다.(r이 아니라 gamma입니다.)

미래의 보상을 보면 그냥 미래의 보상의 값들을 다 더하는 것입니다.

하지만 감가된 미래의 보상을 보게 되면 현재 time-step $t$에서의 보상은 위에서와 같이 $\gamma$값이 지속해서 제곱값으로 곱해지게 됩니다.(현재의 보상은 그대로 받으면서 다음보상부터 감가율을 곱하게 됩니다.)

위의 수식이 결과적으로 핵심적인 Q-Learning알고리즘을 수식으로 정리한 값입니다.

위의 Q-Learning을 계산해 보았습니다.

위의 그림은 총 Q-Learning에 대해서 정리한 부분입니다.(Dummy에서 Discount Factor 부분만 변화가 있습니다.)

Q라는 함수를 통해서 Table을 구현했고, 최적의 Policy는 위와 같이 구해졌습니다.

앞으로 공부를 하면서 hat이라는 것을 많이 볼것입니다.(ex) ... $\hat{Q}$)

hat은 Q값을 모르기 때문에 근사치로 표현을 했습니다.

 

과연 $\hat{Q}$는 $Q$에 수렴해 가나요?라고 궁금증을 가지실 수도 있습니다.

• 결정론적인 세계에서만 수렴합니다.(어떤 방향으로 움직였을 때 항상 같은 보상을 받는다.)
• 유한한 State에서만 수렴을 합니다.