이번 포스터부터는 Reinforcement Learning에 대해 알아보겠습니다!
우선 DP와 RL에 대해 알아보겠습니다.
가장 큰 차이는 DP는 planning, RL은 learning입니다.
value ft table을 잘 업데이트 하는 것이 중요합니다.
모든 state에 대한 값들을 update합니다. 이를 효율적으로 하기 위해 DP를 사용하고 planning을 합니다. bellman eq를 통해 update를 하는데 model-based입니다. 각 state의 value ft을 업데이트할 때 next state으로 모든 state을 고려하기에 full backup을 사용합니다.
반대로 RL의 경우는 transition prob을 알 수 없기에 직접 환경에서 action을 취한 후 얻는 sample data로 진행합니다. model-free입니다. 특정한 state에서 얻어진 action에 대해서만 고려해여 backup합니다. 따라서 learning이라고 하는데, policy를 진행하면 sample data가 나오는데 이를 통해 value ft을 update합니다.
DP는 모든 값을 알기에 정확히 bellman optimal eq를 만족하는 값을 찾아가는데, RL의 경우는 샘플로만 하기에 정확히 bellman optimal eq를 만족하지 않습니다. 따라서 approximation을 적용하여 해결합니다.
강화학습은
1) Monte Carlo method
2) Temporal Difference learnings : Sarsa, Q-learning
로 나위어 있습니다.
bellman expectation eq는 현재 state에서 가능한 모든 return값들의 기댓값이었습니다. bellman eq를 통해 바로 다음에 주어지는 immediate reward Rt+1과 next state St+1을 통해 구성할 수 있었습니다. 이렇게 식이 바뀌면 게임이 끝날 때까지 가지 않아도 됩니다. online에 사용하기 유용합니다. 현재 상황에 맞게 적합한 식을 사용하면 됩니다.
DP의 경우는 앞의 식을 사용하는 것이 거의 불가능합니다. 모든 계산을 하는 것은 방대하기에 무리가 있습니다. 따라서 return을 계산하는 것 보다, 다음 것만 계산하면 되는 뒤의 식을 사용합니다. 또한 model-based로 모든 값을 알기에 expectation도 쉽게 구할 수 있습니다.
강화학습의 경우는 transition prob를 모르기에 샘플만을 가지고 계산해야합니다. 그렇기에 강화학습은 return값을 이용해도 괜찮고, next reward와 state value ft값을 이용해서 계산해도 괜찮습니다.
모든 reward들에 대해 total discounted reward를 한 ruturn값을 사용하는 방법을 monte carlo라고 하고, 바로 한 step만 가서 계산한 값을 이용하는 것을 temporal difference learning이라고 합니다.
temporal difference learning에서
sarsa는 state action reward next state next action 5가지를 하나로 보는 것이고,
Q-learning은 state action reward next state 4가지만 사용합니다. 강화학습에서는 주로 Q-learning이 핵심적입니다. 이를 Deep과 합한 것이 DQN입니다.
두가지 다 tabular updating methods입니다.
즉, value ft의 테이블을 만든 후 이를 업데이트하고 이를 통해 optimal policy를 찾아가는 것 입니다. 여기서 사용되는 것이 bellman eq라고 했습니다.
구체적으로 진행할 때는 차이가 있습니다.
1 iteration은 테이블을 한 번 업데이트 하는 것을 의미합니다.
한 번 update할 때 DP의 경우는 테이블 안의 모든 state에 대해 update를 진행합니다. 여기서는 full backup을 사용하는데 V2의 cool을 update할 때 v1의 모든 값들을 사용한다는 것 입니다. 모든 state에 대한 state value값들을 업데이트해야하고 각 state value값을 update할 때 next state값으로 full backup을 사용합니다.
그렇기에 (s,a)pair를 모두 계산해야 하는 Q ft보다는 V ft을 사용합니다.
어느정도 update한 후에 policy를 improve할 때는 one step lookahead로 value ft을 업데이트 하는 식을 한번 더 사용합니다. 이 식을 maximize하는 action을 찾으며 optimal policy를 찾는 것 입니다. 그렇기에 action은 하나이므로 optimal policy는 deterministic이기에 greedy ppolicy improvement라고 했습니다.
또한 DP는 known MDP이어야 계산이 가능합니다.
강화학습의 경우는 샘플 데이터로 iteration을 돌린다고 했습니다.
예를 들어 하나의 에피소드에 대해 얻은 return 값들(G0,G1,...)로 Q table을 업데이트 한다면, 모든 정보를 가지고 있지 않기에 갖고 있는 부분만 업데이트를 진행합니다. 그렇기에 당연히 이전에 갖고 있는 것들로만 계산하기에 sample backup입니다.
model-based면 state value ft 테이블로 policy를 잘 찾아 action을 구할 수 있지만, 강화학습은 model-free이기에 state value ft 테이블로는 어떤 action을 취해야 하는지 알 수 없습니다. 따라서 action value ft을 사용하여 action이 나와있는 Q ft 테이블을 사용해야 하는 것 입니다!
DP에서는 full backup을 하기에 모든 state에 대해 고려해야 합니다. 하지만 계산량이 너무 많습니다. 하지만 강화학습에서는 샘플밖에 없기에 당연히 sample backup을 진행합니다. 따라서 state개수에는 상관이 없고 몇 개의 샘플을 갖고 있느냐에 따라 달라지는 것입니다. 따라서 훨씬 효율적으로 계산을 합니다.
지금까지 DP와 RL의 차이점에 대해 알아보았습니다.
이번에는 Generalized Policy Iteration : GPI에 대해 알아보겠습니다.
대부분의 모든 강화학습은 GPI를 기본으로 하고 있습니다.
policy iteration은 policy evaluation과 policy improvement를 반복적으로 사용했습니다. policy evaluation는 현재까지 업데이트 된 current policy가 있다면 이것을 기준으로 value ft값들을 계속 converge 할 때 까지 업데이트해가는 것 입니다. 그런 다음 value ft을 업데이트해서 모든 state에 대해 value ft값들이 converge한다면 value ft테이블을 가지고 policy improvement를 진행합니다. 현재까지 얻어진 value ft값을 이용하여 greedy 방법을 통해 update합니다.
여기서 중요한 핵심은 iteration마다 모든 정보를 사용하는 full backup을 통해 converge할 때 까지 갑니다. 이를 complete이라고 합니다.
하지만 state value ft값은 계쏙 converge하고 있지만 , optimal policy에는 이미 도달하여 필요이상으로 계산하여 비효율적이라고 있습니다.
GPI는 Sample backup을 하기 때문에 샘플에 주어진 데이터에 대해서만 value ft값을 업데이트 하는 것 입니다. current policy에 대해서 정확한 true value값을 찾을 수는 없고 거기에 approximation하는 value ft을 갖는다는 의미입니다. value ft이 근사치에 간다.
하나의 에피소드에서 100개의 샘플을 얻었다면 100개만 적용하고 끝나는 것 입니다. 이 value ft이 policy에 맞춰 converge할때까지 계산하는 것이 아닙니다. 그냥 주어진 샘플 다 계산했으면 끝!
Q valeu table을 가지고 policy improvement를 합니다. greedy policy 사용
이렇게 얻은 새로운 policy를 가지고 policy evaluation합니다. evaluation할 때는 sampled data를 가지고만 하기에 converge할 때 까지 갈 수 없습니다. 따라서 approximate만 하게 되어 가다가 멈추게 됩니다. 그 다음에 그렇게 얻은 Q값을 이용하여 다시 policy improvement를 합니다. (best action을 각 state마다 찾는 것이죠) 그 다음 다시 policy evaluation을 통해 approximate를 하며 반복합니다.
PE, PI 를 반복하며 더 이상 변화가 생기지 않을 때 까지 update합니다. maximize시키는 action이 더이상 없으면 더이상 policy가 바뀌지 않습니다.
결국 Q ft은 bellman optimal eq를 만족하게 됩니다. 즉, 이 value ft이 optimal이라는 것 입니다. 샘플들만 가지고도 optiaml을 찾은 것 입니다.
고려대학교 오승상 교수님 강화학습 강의 : https://www.youtube.com/watch?v=NH3lKBzXBUA&list=PLvbUC2Zh5oJtYXow4jawpZJ2xBel6vGhC&index=10
