SARSA

강화 학습의 시작의 기초 알고리즘은 SARSA를 공부한다. 

 

SARSA의 이름은 $\text {State}_t, \text {Action}_t, \text {Reward}_{t+1}, \text {State}_{t+1}, \text {Action}_{t+1}$에서 따왔다. 한번 학습할 때 하나의 세트로 위에 것들을 사용하기 때문에 이렇게 만들었다고 생각한다.

 

SARSA를 시작하기전에 간단하게 Temporal Difference (TD)를 알아야 한다. 

K번째의 평균을 구하려면 위와 같은 식을 이용해서 구하는데 이는 K-1번째 평균 값에 마지막에 나온 식을 이용해서 구할 수 있다.  그리고 K번째에 나온 x값을 이용해 estimate와 관련된 식으로 바꿀 수 있다.

 

Monte-Carlo(MC) 방법에서의 V값을 구해보면 위의 식과 같다. 하지만 정확한 G를 구하기 위해서는 하나의 에피소드가 완전히 끝나야 한다. 만약 에피소드가 굉장히 긴 task에 적용하면 이는 학습하는 시간이 길어지는 문제가 발생할 수 있다.

하지만 TD를 이용하면 에피소드가 끝나기 전에 위에서 설명한 x를 이용하여 estimate 하여 사용 가능하다. 따라서 더 빠른 학습이 가능해진다. 

위의 사진은 MC 방법을 적용하여 V를 업데이트하는 식이다. 에피소드가 끝나면 $\text {G}_{\text {new}}$를 이용하여 새로운 V값으로 업데이트 해준다. 

 

 

하지만 TD에서는 $\text {G}_{\text {new}}$를 이용해 학습하는 것이아닌 벨만 기대방정식을 이용하여 $\text{G}_{\text{new}}$를 estimate 해준다. 이렇게 보면 TD가 MC보다 좋은 거 아닌가 생각이 들긴 하지만 TD는 어디까지나 estimate이기 때문에 estimate 한 값이 좋지 않으면 학습 또한 발산할 가능성이 있다. 

 

최종 SARSA의 의사결정 코드를 보면 위의 사진과 같다. 의사결정 코드에서 갑자기 $\lambda$가 나와서 저건 또 뭔가 싶었는데 작성한 코드를 보니 아마 discount factor를 저렇게 표현했다고 생각한다. 이것이 정확한 내용은 아니지만 저 $\lambda$에 대해 제대로 공부해보고 싶은 분들은 forward-view Sarsa와 backward-view Sarsa에 대해 찾아보시면 관련 내용이 나오니 이를 봐도 괜찮을 것이다.

 

다시 Grid World를 이용하여 SARSA 알고리즘을 구현했다. 기존과 달라진 것은 장애물이 1개로 줄었는데 이는 SARSA의 한계 때문이다 SARSA는 $\text {Action}_{t+1}$을 사용하기 때문에 업데이트를 하다 보면 agent가 갇혀버리는 현상이 생긴다.

예를 들면 만약 장애물이 8번 state에도 있다고 가정한다. 그리고 agent가 2번 state에서 3번으로 가는 action을 하고 다음 스텝에 8번을 가는 action을 취했다고 하면 업데이트에서 2번의 오른쪽 action에 대한 Q값은 $-$를 가지게 된다. 이는 agent가 더 이상 2번에서 3번으로 가지 않게 만들어버린다. 똑같은 과정으로 6번 state에서 11번으로 가고 12번으로 가는 상황이 생기면 agent는 1,2,6,7번 states에 갇혀버리는 현상이 발생한다. 

이런 현상이 가끔 일어나는 게 아닌가??라고 생각을 했었는데 학습을 진행할 때마다 굉장히 자주 발생하게 된다. 따라서 어쩔 수 없이 장애물을 한 개만 사용했다. 

 

구현한 코드는 https://github.com/KwanWooPark97/RL_basic/tree/master/sarsa에서 확인 가능하다. 

 

모든 코드는 인터넷에서 기본적인 구조를 찾아서 이해한 다음 내 코딩 스타일대로 수정한 것들이다. 어디서 본 것 같은 코드인데??라고 생각한다면 그게 맞다.