Cliff exploration, Sarsa vs Q-Learning

6장 TD 에서 매인 컨셉으로 나온 알고리즘 2개를 돌려보는 시간을 가졌다.

2개의 의사코드를 보고 아무것도 참고안해보고 직접 구현을 해보았다.

느낀점은 같은 Reinforce Learning 도 컨셉이나 구현 방식에 따라 성능이 많이 달라질것 같다. 

왜냐면 예를들면 경로 탐색의 경우 visit 체크를 하느냐 마느냐, Backward 로 갱신하느냐

Episode 를 직접 만드냐, 아니면 Episode 를 사용자로부터 입력을 받느냐, Random 한 출발을 하느냐,

종단조건을 어디서 줄거냐.( 일종의 Reward 가 Threshold 값(-100?) 이 넘게되면 종단 하는것도 방법이다.

이러한 세세한 사항 하나하나에 의해 수렴도 결정되고 수행 속도도 결정될듯 하다.

 

또한 이러한 간단한 예제를 구현하는대로 부가적인 프로그래밍요소가 많이 필요하였다. 

고로 RL 은 일반적인 솔루션을 만들기가 어려울것이다. 그 이유는 문제가 복잡할 수록 예외상황이나 Agent 세부적인 것들을 다 손을 봐줘야 하기 때문이다. 

 

아래의사코드를 바탕으로 구현하였다.

1. SARSA

2.Q-Learning

 

 

구현 후기는 일단 2가지 차이를 생각히보자면,

QLearning 이 조금더 Greedy 하고 미리 다음 step 을 보고 움직인다고할까? 

ODE 미분방정식을 풀때 다음 항의 미분값을 가져와서 평균내는 것처럼 (Runge kutta)

QLearning 은 다음 state 에서 Action 중에 일종의 max_a (Q(S',a)) 값을 가져와서 그 값으로 갱신 하기 때문에,

좀더 implict 한 method 이고 Convergence order (수렴속도) 가 빨라질 수 밖에 없을 것 같다고 생각 이 들었다.

한편 그 값은 가장 dominant 한 Q(S,A) 값이 기 때문에  

Q 가 수렴해야 할 방향중 가장 큰 Gradient 값을 가져와서 갱신 시켰다고 보는것과 유사 할 듯하다.

 

Sarsa 는 주어진 epidode 에 대해 오로지 그대로 움직이면서 주어진 State , Action 값 만 새롭게 갱신한다.

QLearning 은 주어진 Episode 의 1step 뒤의 주변 환경을 고려하여 갱신하다.

 

이러한 차이 때문에 , 절벽문제 같은 경우에 있어서는, 

Sarsa 에서는 Episode 중 절벽을 가는 Episode (다음 Action)가 존재하다면

Q(S,A) = Q(S', A) + 절벽으로 가는 Action 의 (-100) 업데이이트 가 이루어지기 떄문에

절벽 근처에 State 에 대해서도 낮은 Q 값을 갱신하는 반면 

한편 Q_Learning 에서는 Episode 다음 step에서 절벽쪽으로 가는 Action 이 있어도

Q(S,A) = Q(S', A) 절벽으로 가는 Action 의 (-100) 의 업데이트가 이루어지지 않기 떄문이다.

 

최적의 길 측면에서는 Q_Learning 은 주변을 흝는 대신, 미리 최적이 어디 일 것이다라는 assumption 을 포함한 더 공격적인 update 가 이루어질 것이며,

Q_Sarsa 는 정해진 Episode 의  State, Action 의 값 대로 epside 그대로 방어적이지만 정해진 길을 확실히 가는 update 가 이루어진다.  이 문제의 최적의 길 측면에서는 Q_Learning 이 유리 할 수 밖에없다.

 

다만 Episode 가 모든 State 를 골고루 스쳐간다고 가정하면

Q 값의 갱신은 Q_learning 은 좀더 정해진 (max) 값을 불러 오기 때문에 Q_sarsa 가 좀 더 episodic 에 의존하여 잘 이루어 질 수 있다.

하지만 종단 최적(?)의 경로 측면에서는 Q_Learning 이 좋을 수도 있다.

 

다만 Q_Sarsa 는 우리가 겪은 episode 의 경험으로부터 학습 하기 떄문에 , 좀더 Determinestic 하게 움직일 것이며,

'경험' 에 의존 한 다는 것이 '상태 전이 확률' 을 고려한 움직임이 될 수 밖에없다. 만약 Q_Learning 이 다음 상태의 max 값을 잘가져왔다 쳐도, 그 상태로 갈 확률이 거의 0 에 가깝다면, 사실 잘못된 Q 갱신이 이러날 수도있다.

 

그렇기 때문에 , 내가 환경을 잘모른다고 가정하면, 나는 Q_Sarsa 를 선호 할 것이다.

그리고 부족한 SARSA 를 위해 random 하게 탐색하는 episode 를 최대한 generate 할 것이다.

 

Risk 를 회피하는 측면에서도 SARSA 가 유리할 듯싶은데,

그렇다면 Q_Learning 을 왜쓰는 것일 까?

 

아래 결과를 보면 Q_Learning 이 최적 경로를 찾는 부분에 있어서 더욱 빠른 길을 찾아낸다. Q를 더 빠르게 수렴시킨다.

맨 아래 최종 그래프의 값을 보면 Q 값도 더욱 안전히 빠르게 수렴한 듯 싶다.

그래프는 Episode 별로 평균 Reward 를 구한 것인데,  Sarsa 는 Eps 에 의해서 절벽으로 가는 현상도 일어난다.

반면에 Q는 다음 step 에서의 Q 값은 절대 절벽으로 가는것으로 일어나지 않기 떄 문에 Episode 별 평균 Reward 에는 큰 영향이 없다.

SARSA

Q

우리가 Random 한 Episode 에서 보상을 최대로 알아내는 알아내는 길을 찾는 것이 목표라 할 때 

무엇이 목표일까?

1.(Risk 회피의 안전 제일)  vs 최적 보상의 경로를 Clear하게 얻고 싶은가

2.경험으로 부터 최적의 값을 알고싶느냐 vs 경험을 따르되 좀더 generate 하게 최적을 알고 싶으냐 

2.상태/환경 를 잘아느냐 vs 상태/환경를 잘모르느냐

 

뭐이런 측면에서 두가지 method 는 계속 비교당하지 않을 까싶다.

 

 

아래 구현/소스 과정에 있어서 부연 설명을 하자면

 

* 0,0>10,0 으로 가기위한 Random한 Episode 의 정의~

 

구현 방법에 있어서 Epsidode 를 대입 한 방식이 사람들과 다른점이 있을 수도 있다.

사실 나는 Episode 의 정의가 무엇이냐 부터 구현과정에 있어서 혼돈이 있다.

나는 Episode 를 시작에서 종단까지 의 한 Route 라고 생각하고 

0 0 > 10.0 으로 가는 random 한 경로에 대해서 모두 임의로 Generate 하였고, 

그것을 기반으로 RL  을 돌렸다. 

인터넷에보면 그렇지 않은 경우가 많다. 그냥 0, 0 으로 시작해서 절벽에 떨어지는 경우

종단 하는 경우의 코드가 있었고, -100을먹고 다시 처음 state 로 강제로 오게 하는 부분도 있다.

시작점은 항상 0,0 이였고, 10,0 까지 가는것이 계속 Episode 로 보더라..

물론 나는 그렇게 해도 좋을 것 같았으나, Episode 가 이렇게 깔끔하게 정의 되지 않는 경우도  있고, 

최초에 10,0 까지 가는 것도 시간이 너무 오래걸릴 것 같다는 생각도 분명히 있어서

 

일반적으로 한개의 시작상태 > 종단 상태로 가는 상태 변이의 집합을 한개의 Episode 라고 가정하고

그 path 자체를 Sarsa,Qlearning 의 input으로 대입 하였다.

 

* 나는 절벽에 떨어진다고 해도, 계속 -100 보상을 얻고 지속 한다고 가정하였다.

* 0,0>10,0 으로 가기위한 Random한 Episode 의 정의를 아래와 같이 정의한다.

EPisode 란 0 > 10,0 까지 의 임의에 경로를 온 사용자의 '경험' 이라는 측면에서 구현을 하였고,

그렇기 때문에 완성된 Path 를 역순으로 대입 시켜가면서 시작하여 종단 까지 탐색하였다. 

그리고 path 를 뒤에서 부터 돌면서 Q 탐색을 시작하면서 업데이트 시켰다.

Q 를 거꾸로 업데이트 시킨 이유는 1번의 갱신이후 바로 다음 갱신이 바로 전값을 가져올 수 있어서 이다.

 

출발점이 0,0 1개가 아니라면? 

State 를 정의하기 힘든경우라면?

그럼으로 Episode 를 명확히 할 필요가있다.

 

2. 완성된 Q 값 그래프

위는 SARSA 밑에는 Q 뭐가 맞는 것 같은가?

1000번이나 돌리긴 했지만 Q_Learning 의 경우 저렇게 어느정도 규칙적으로 수렴한(?)모습으로서 최적을 보장한다.

SARSA 의 경우 에는 좀더 Episode 의존적 이며 아직 더 수렴 할것(?) 같은 모습을 보인다. 

 

 

github.com/Sangil55/ReinforceLearning_ex/

Sangil55/ReinforceLearning_ex