이번 포스터에서는 이전 monte carlo에 이어 ε-greedy에 관해 알아보겠습니다!
Exploitation : 이미 알고 있는 정보 내에서 가장 최선의 선택을 하는 것
ex) 이미 알고 있는 밥집 중에서 가장 맛있는 집을 찾는 것
이미 맛있는 곳을 가기에 안전하지만 더 맛있는 집을 찾을 방법은 없습니다.
Exploration : 알고 있는 정보 이외에 더 최선의 방법을 찾아 떠나는 것
ex) 알고 있는 맛집 이외에 더 맛있는 맛집을 찾는 것
방문하지 않았던 식당을 찾기에 실패할 수도 있지만 새로운 맛집을 찾을 수 있습니다.
장기적으로 보면 Exploration이 좋습니다.
이를 강화학습에 적용합니다.
Exploitation : highest Q value를 갖는 action을 선택합니다. 기존에 배웠던 greedy policy와 같습니다. 이렇게 얻은 action들 즉 이 policy를 가지고 새로운 에피소드를 샘플링하게 됩니다. 취해보지 않은 state action pair에 대해서는 Q value 값을 모르기에 update가 되지 않습니다.
Exploration : 여기서는 ε만큼 다른 action을 취해봅니다. 예를 들어 ε=0.0001이라면, 1-ε=99.99%로 highest Q value를 택하고, ε만큼 새로운 action을 취하는 것 입니다. 이렇게 함으로 가보지 않았던 pair에 대해 방문하며 sampling해보는 것 입니다. ε확률만큼 손해볼 수도 있지만 여러 번 반복하다보면 더 좋은 Q value를 찾을 수도 있습니다.
이를 ε-greedy policy라고 합니다.
이 ε-greedy policy를 이용하여 MC policy improvement를 진행하겠습니다.
이를 MC control이라고 합니다.
random action은 어떻게 정하냐면 action의 개수가 m개면 ε/m으로 잡아줍니다. 다라서 ε-greedy policy는 stochastic policy가 됩니다.
DP에서는 highest Q value를 갖는 action을 무조건 하나 선택했지만, 이제는 확률적으로 선택하게 됩니다.
: 1-ε만큼 highest Q value를 갖는 action을, ε/m만큼 모든 action에 확률을 부여.
이제는 모든 action이 non zero probability입니다.
MC Control에서는 stochastic policy인 ε-greedy policy를 적용합니다.
여기서 이를 사용했을 때 policy improvement가 보장될까요?
DP의 policy improvement는 보장이 되었습니다.
여기서는 policy π에 대해 update 된 Q value ft qπ가 있을 때, ε-greedy policy를 적용한 policy π'는 항상 improve되냐?
이것이 보장이 됩니다! 그렇기에 ε-greedy policy를 사용할 수 있습니다.
policy improvement thm에 의해 q>=v 로 v>=v를 만족하게 됩니다!
이렇게 강화학습은 ε-greedy policy로 stochastic policy를 사용하기에 기존에 주어진 샘플 안에서의 가장 좋은 action을 취할 뿐 아니라, 가끔은 취하지 않았던 action도 취해보며 장기적으로는 더 좋은 action들을 선택하는 기회를 만들게 됩니다!
이번에는 Greedy in Limit with Infinite Exploration : GLIE를 알아보겠습니다.
지금 학습하고 있는 Learning policy가 있는데 아래 두 조건을 만족하면 이것을 GLIE라고 부릅니다. 이상적인 모습이 되는 것 입니다.
1) Infinite Exploration : Q table이 있을 때 q value sample이 무한히 많아야 값들을 알게 됩니다. (s,a) pair들이 무한히 많이 방문해야 한다입니다. n(s,a)->무한대
2) ε-greedy policy를 적용해서 점점 성능이 좋아진다고 할 때, 최종적으로 아주 성능이 좋은 모델을 구했다고 하더라도 끝까지 ε-greedy policy를 쓰면, 이미 최고인데 ε만큼 옳지 않은 선택을 할 수 있습니다. ε을 점점 줄여야 합니다.
ε-greedy policy -> greedy policy 로 하기 위해 learning policy가 결국 greedy policy 1로 가게 해야 합니다.
이 두 가지를 만족하는 것을 GLIE라고 합니다.
1)은 무조건 데이터 양으로 늘리기만 하면 됩니다. 2)는 ε값을 점점 0으로 수렴시키면 가능합니다.
ε을 1/k로 설정해도 됩니다.
이런 방식으로 MC가 GLIE를 만족하게 control할 수 있습니다.
마지막으로 MC method의 수도코드를 보겠습니다.
Q value 값을 임의의 값으로 initialization합니다. terminal의 Q value 값은 0으로 둡니다.
Return 값을 계산해야 하는데 이를 empty list로 만듭니다.
policy를 임의로 두는데 ε-soft로 하여 ε이 0이 되지 않게 해줍니다.
에피소드가 하나 주어지면
이 에피소드에 대해 policy evaluation과 policy improvement를 진행합니다.
return 값 G를 0으로 초기화한 후 pair들에 대해 반복합니다.
return값을 계산하기 편리하게 뒤에서 부터 감마를 곱하고 더하며 계산합니다.
first visit MC를 적용합니다. 만약 every면 매번 그냥 더하면 되기에 이 줄을 삭제해도 됩니다.
mean return
incremental MC : 횟수 n(St,At)로 나누기 / constant-a MC : a값을 곱하기
여기까지가 MC policy evaluation(prediction) 입니다.
에피소드 내의 state에서 highest Q value에 해당하는 action A 를 찾습니다.
이 A 에는 아래와 같은 확률을 적용하고 나머지는 아래와 같은 확률을 적용하여, ε-greedy policy를 적용하여 ε-greedy policy improvement를 실행합니다.
이 둘을 각 episode마다 반복적으로 사용합니다. 어느 순간 PE, PI 이 둘이 정체될 때 학습을 마치게 됩니다.
고려대학교 오승상 교수님 강화학습 강의 : https://www.youtube.com/watch?v=TF63tYx-fdk&list=PLvbUC2Zh5oJtYXow4jawpZJ2xBel6vGhC&index=12
