My data lab

RL 에 대해서 여러가지 리뷰를 진행 하였고, 정리하였다.

일단 RL 쪽에 계속 발전하고있고, 기존방식의 문제점들을 보완하려는 노력을 하고있다.

RL 같은경우 아래와 같은 한계점들이 존재한다고한다.

1. State 가 무수히 많을 경우

2. 수렴성의 보장

3. 높은 분산값 

이런것들을 보완하기위해서 새로운방법들이 나오고있고, 현재 진행형 인 듯 하다.

강화학습을 나중에 더 깊게 파고들 수도있지만. 정확히말해서 그렇게 까지 잘 될것 인지에 대한 확신 이 없다.

적절한 보상을 주고 알아서 판단하게 만들려고하는게 강화학습인데 어디까지 더 생각을 해야될까? 라는 의문점을..

아무튼 키워드위주로 정리하겠다.

DQN - state 가 무수히 많을 경우 Q-Value 를 state마다 정의하지않고,  네트워크를 만들어서해결

Policy gradient -  DQN 과 이어서 생각해보았을때 seta 가 일종의 DQN 의 parameter이라 생각해보자, 기존에는 policy 가 Q_seta 에 의해 결정되었다면,  policy 자체를 seta 에 대한 직접적인 output 이라 생각한다.

그 다음 Q_pi 의 값이 늘어나는쪽으로 (gradient) 가게되면 전체적으로 value function 이 높아지는 쪽으로 수렴한다.

cost function 은 대체로 보상 들의 합의 기대값으로 놓고 그것을 최대로 하는 seta 를 찾는게 목표이다.

이 식으로 인해 grad(log_pi_seta(타우=경로) ) 의 기대값을 계산하면 costfunction 의 그라디언트를 구할 수 있는데,

이 값(grad(log_pi_seta(타우=경로) )은 기대값이기 때문에 MC - method 등으로 인해 경험적으로 구할 수 있다.

하는이유 : DQN 에 비해 좋은 수렴성

Baseline - 강화학습에서 미리 계산된 Value Function 을 사용 할 수도 있다.

A = Q - V 이렇게 놓고 A 를  수렴 시키기도한다. (분산이줄음)

Actor-Critic

위의 policy gradient 의 경우에는 MC 로 진행 햇을경우 높은 분산값을 갖는데 그값을 줄이기위해서

ACtor Q 를 수렴

Critic V 를 수렴 ( Q 의 action 선택을 비평)

Critic은 action value function을 approximate하는 w를 update하고

이때 Ciritic 도 network 를 사용하는 이유는 모든 경우를 trial 하지 않고 적은 sample 로도 기대값의 합을 알수 있게 되는 효과가 있다.

Actor는 policy를 approximate하는 seta를 update 따라서 w와 seta, 두 개의 weight parameter 를 갖는 강화학습 방법 

DDPG

NAtural Policy

TRPO PPO 등이 더있는데. 나중에 정리하겠다.

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 에는 큰 영향이 없다.

우리가 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/

Ref - ReinForcement 2nd Edition.pdf

Richard S. Sutton

일단 해석학과 대수로 고통받던 나날중에 프로젝트를 위해 강화학습을 따로 스터디를 진행하였다.

바이블이라고 하는 Richard Sutton 의 책을 보면서 배운내용을 정리하고자 한다.

다만 수학을 보다가 이쪽 내용을 봐서 그런지 모르겠는데

전체적으로 Markov 전재를 하고 다룬다는 점에서 일반적인 문제를 특수한 경우로 정의하여 다루는 것 같고

일종의 점화식들 : 이렇게 돌리면 최적의 가치함수로 수렴할것 이다 라는 내용이 중간중간에 자주 나오는데

바이블이란 책을 보는데도  이 것들이 이유가 없이 애매하다. 일단 내가 잘몰라서 그런것이라 생각하고 넘어가긴했지만 생각해 볼점이 많을것 같다.

실제로 강화학습이 문제에 잘안쓰이는 이유도 이쪽으로 투영시키기 위해서는 첫번째로 State 로 상태를 정의할수 있는 문제 여야하며 두번째는 수렴성이 명확히 보장되지 않아서가 아닐까 싶다. (아니면 내가 잘 이해못했거나.. 책을 보고도 명확히 이해가 안되는건 역시 문제가 있다. )

chapter 3 MDP 

강화학습 에이전트 란 행동(Action)을 하면서 보상(Reward)을 얻는다. 내부적인 값은 상태(State) 값을 갖는다.

MDP

1. 상태를 갖는다. 상태를 갖음으로써, 즉각적인 보상외에 전이된 상태의 보상, 즉 Delay Reward 를 고려해야한다.

2. 지연된 보상을 고려하기위해서 v* q* 등을 고려한다. 

3. p 는 State-Trainsition Property 로 볼 수 있는데 바로 전 상태에만 영향을 받는다(Markov) 및 MDP 의 Dynmaics 이라고 불리기도한다.

4. 위로 부터 보상의 기대값 r(s,a) = Ra * sigma_s'( p(s',r | s,a)를 구할 수 있다.

5. 장기적 보상을 최대로 갖는 목표(goal)를 갖는다.

6. Policy 정책(pi) 에 대한 가치 함수 ( value function) 를 정책 pi 를 따랏을 경우 예상되는 이득의 기대값으로 정의한다.

7.  6 에서 정의한 내용들은 Bellman Equation(3.12), 아래와 같이 가치 함수(s) = 시그마(가치함수(s')* 상태전이확률) 을 만족해야한다. 이때 이후 가치함수를 이용함으로써 현재 가치를 알아내기 때문에 Bootstrap 기법이라고 하기도한다.

8. 6,7의 에 정의한 value Function 에 대해서는 최적 정책함수 (Optimal Value Function) 이 Uniquae 하게 존재 하고, 아래의 최적 Bellman Equation 을 만족해야한다.

7과 비교했을 때, 기대값이 아닌 최대값으로 Update 를 해야 하는것이 중요하다.

v의 경우 action 을 수행한 다음의 얻게될 전이확률 * 보상의 합 (action 수행뒤 다음 State 가 꼭 1개는 아니다)이 최대가 되야한다.

q 의 경우 현재 상태와 액션을 결정 되 있고 (s,a) s' 도 전이확률로써 결정되어있다. 그렇기 때문에 각각의 다음 state s' 에 대해서 취할수 있는 action a' 들 중 최대의 값을 갖는 a' 를 택한다. 즉 다음 State s' 에서 할 수 있는 action 중에서 최대 q* 를 가져와서 업데이트한다.

9. 8에 대해서 풀게되면, v* 또는 q* 를 알 수 있고, 최적정책은 탐욕적으로 결정하면된다.

9. MDP 라는 것은 보통 p 를 알고있다라는 것을 뜻한다. 즉 상태 와 상태전이확률에 대한 이해가 확실하고, MDP 에서 M(markov) 은 p 자체 를 정의 할수 있다는 것을 뜻한다.