이번 포스팅에서는 Monte-Carlo와 같이 model-free한 방법으로써, Temporal Difference Methods에 대해 다루겠습니다. MC는 한 episode가 끝난 후에 얻은 return값으로 각 state에서 얻은 reward를 시간에 따라 discounting하는 방법으로 value function을 update합니다. 하지만, atrai게임이나 현실의 문제는 episode의 끝이 무한대에 가깝도록 길기 때문에 episode가 반드시 끝나야 학습을 하는 MC의 방법으로는 한계가 존재합니다. DP처럼 time-step마다 학습하면서 model-free한 방법이 바로 TD입니다.
Temporal Difference
TD는 MC와 DP의 idea를 조합한 방법으로써 MC처럼 model-free하게 raw experience를 통해 learning할 수 있고, DP처럼 episode의 끝을 기다리지 않고 value function을 update합니다.
Bootstrap
Bootstrap은 random sampling을 복원 추출의 방법으로 통계적인 추정이나 가설 검정을 수행하는데 활용됩니다. 작은 표본 데이터를 사용하여 모집단의 특성을 추정하기 위해 임의로 샘플을 추출합니다. 이를 통해 모집단의 평균이나 다른 통계량을 추정하고, 이 추정치들을 통해 모집단에 대한 정보를 얻을 수 있습니다. 중요한 점은 Bootstrap은 모집단의 분포에 대한 가정 없이도 효과적으로 추정을 수행할 수 있다는 것입니다.
예를 들어, 어떤 식품 회사에서 생산되는 쿠키의 무게를 알고자 한다고 가정해봅시다. 하지만 우리는 식품 공장에서 오직 100개의 쿠키만을 무작위로 선택하여 무게를 측정했습니다. 이 데이터만을 가지고 모든 쿠키의 평균 무게를 추정하는 것은 어려울 것입니다. 이 때, Bootstrap을 사용하여 무작위로 쿠키를 여러 번 뽑아내는 방법을 생각해볼 수 있습니다. 우리는 100개의 쿠키에서 무작위로 한 개를 선택하고 다시 넣은 후, 다시 무작위로 한 개를 선택합니다. 이 과정을 여러 번 반복하여 큰 수의 가상의 "샘플"을 생성합니다. 이렇게 생성된 가상의 샘플들을 사용하여 평균 무게를 계산할 수 있습니다. 이러한 과정을 여러 번 반복하면, 여러 개의 평균 무게가 생성됩니다. 이렇게 생성된 평균 무게들의 분포를 통해 모든 쿠키의 평균 무게에 대한 추정값과 신뢰구간을 계산할 수 있습니다.
위에서의 bootstrap은 통계학에서의 의미이고, 강화학습에서의 의미는 같은 종류의 추정값에 대해서 업데이트를 할 때, 한 개 혹은 그 이상의 추정값을 사용하는 것입니다. 예를 들어, "내일 날씨가 흐릴 것 같으니, 모레는 아마 비가 오겠네". 내일 날씨라는 추정값을 가지고 모레의 날씨를 추정했으므로, bootstrapping을 했다고 할 수 있습니다. 만약 내일의 날씨가 흐리지 않고 화창하다면, 모레의 날씨는 비가 올 확률이 아주 낮아집니다. 즉 첫 추정이 나쁘다면 두번째 추정은 더욱 나쁠것이므로 bootstrapping은 편향(bias)의 근원이 됩니다. 한편 추정값으로 또 다른 추정을 하면 일종의 자기 일관성(self-consistency)가 생기므로 분산(variance)은 낮아집니다.
MC의 방법은 episode가 끝나지 않으면 얻은 reward를 통해서 value function을 추정할 수 없습니다. 그리고 실제 얻은 reward들을 통해서 state들의 value function을 구하게 됩니다. 하지만 DP나 TD는 이와 달리 time-step별로 이전의 value function들을 통해 현재 value function을 추정하게 됩니다. sampling은 model-free한 속성과 관련되어 sample backup과 관련있습니다. DP는 full-width backup backup이므로 이에 해당하지 않습니다. 아래 그림은 DP와 MC, TD에 대해 비교한 표입니다.
TD Prediction
TD(0)
가장 basic한 TD에 대해서 알아보겠습니다. TD는 MC와 같은 sample backup이면서 time-step마다 update합니다. 아래 식은 MC에서 value function을 update하는 식입니다.
여기서 return Gt는 해당 state에서 episode의 끝까지 얻은 reward들을 시간에 따라 discount한 것입니다. 이것을 1 step에 대한 것으로 바꾸면 TD(0)가 됩니다. 따라서 TD(0)의 update 식은 아래와 같습니다.
위 두 식의 이론적 근거는 value function의 정의와 Bellman Equation에 있습니다.
대수의 법칙에 의해 Gt 또는 𝑟 + 𝛾v(𝑠)를 여러 번 샘플링 할 수록 평균은 value function에 수렴한다는 것입니다. Gt는 value function의 불편 추정량이지만, Bellman Equation은 true value function을 알 때 사용할 수 있는 것이고, 우리는 true value function을 모르기 때문에 편차가 발생합니다.
MC vs TD
MC와 TD의 장단점
- TD는 final outcome을 알지 않아도 학습할 수 있습니다.
- TD는 매 step마다 얻은 reward로 학습할 수 있습니다.
- MC는 return 값을 알기 위해, 즉 episode가 종료될 때까지 기다려야 합니다.
- TD는 incomplete sequence에서도 학습할 수 있습니다.
- MC는 complete sequence에서만 학습할 수 있습니다.
- TD는 non-episodic environment에서도 학습할 수 있습니다.
- MC는 episodic environment에서만 학습할 수 있습니다.
Bias & Variance
Bias
TD는 true value function을 알지 못하기에 바로 다음 step과의 error만 고려하여 update를 하기 때문에 학습이 한쪽으로 치우쳐 지게 됩니다. model로부터 실제로 얻는 정보는 바로 다음 state로 이동할 때의 reward뿐이기 때문입니다. V(St+1)가 이후의 reward들의 정보를 모두 포함하고 있다고 생각할 수도 있지만, 이는 실제로 얻은 reward를 바탕을 계산한 값이 아닌 추정한 값에 불과하여 후에 ture value로 update할 여지가 있는 기대값에 불과합니다. 따라서, TD는 bias가 큽니다. (아무리 샘플을 모아서 update해도 true value function에 다가간다는 보장은 없지만, 실제로 매우 잘 작동한다는 것으로 알려져 있습니다.)
Variance
이와 달리 MC는 episode가 끝나야만 update를 할 수 있지만 episode가 끝난 뒤에는 실제 얻은 reward의 정보를 반영할 수 있습니다. 하지만, 하나의 episode에는 수많은 확률적인 상태 전이와 정책으로 이루어져 있어 각각의 값이 평균으로부터 멀리 떨어져 있을 수 있습니다. 따라서 MC는 variance가 큽니다.
bias와 variance는 서로 trade-off 관계에 있으며 강화학습에서 학습에 방해되는 요소들입니다. 따라서 이를 줄이기 위해 다양한 방법들이 존재합니다.
n-step TD
이러한 방법 중 하나가 바로 n-step TD입니다. n-step TD는 update를 할 때, 하나의 step이 아니라 n개의 step을 보고 update를 하자는 것입니다. 만약, n을 terminal state까지 가져간다면 MC가 됩니다.
위와 같은 방법으로 MC와 TD의 장점을 부분적으로 취할 수 있습니다.
위와 같은 방법 외에도 TD(λ), forward-view TD(λ), Backward-view TD(λ) 등 방법이 존재합니다. 또한, MC Control처럼 TD Control이 존재해 SARSA, n-step SARSA, SARSA(λ) 등이 존재합니다.
Backup Diagram
TD Control
SARSA
TD prediction 방법을 control에 적용하기 위해 action-value function을 사용하고 ε-greedy policy improvement를 적용하면 SARSA가 됩니다. 아래는 q-function을 update하는 식과 control에 대한 backup diagram과 algorithm입니다.
여기서 현재 state, action(S, A) 그리고 이를 통해 얻은 reward(R)와 다음 state, action(S', A')까지 보고 update를 하기 때문에 SARSA라는 이름이 되었습니다.
on-policy TD control algorithm으로서 매 time-step마다 현재의 q value를 reward와 다음 action의 q value를 가지고 update합니다. policy는 따로 정의되지는 않고 이 q value를 보고 ε-greedy하게 움직이는 것 자체가 policy입니다.
Q-Learning
지금까지 MC와 TD 방법은 모두 on-policy control였습니다. 즉, 현재 action의 기반이 되는 behavior policy 𝜇 와 improve하는 target policy 𝜋가 같습니다. on-policy control의 경우 greedy improvement를 진행할 때 한계가 있고, 이를 ϵ-greedy improvement로 개선할 수 있었습니다. 이외에도 off-policy control로 문제를 해결할 수도 있습니다. off-policy control은 behavior policy와 target policy를 다르게 취하는 것입니다.
𝜋 : target policy (타깃정책, 목표정책) - 강화하고자 하는 목표가 되는 정책
- 학습대상이 되는 정책
- 학습자의 정책
𝜇 : behavior policy (행동정책)
- 실제로 환경과 상호작용하며 경험을 쌓고 있는 정책
- 행위실행자의 정책
off-policy control을 진행할 경우 장점은 아래와 같습니다.
- 인간이나 다른 agents로부터 학습이 가능합니다.
- 과거의 policy들부터 나온 경험을 재사용할 수 있습니다.
- exploratory(탐험적) policy를 따르는 동안에 optimal policy를 학습할 수 있습니다.
- OneToMany - 1개의 behaviour policy만 경험을 쌓게하고, 그로 부터 생성된 경험 데이터를 이용해 다른 여러 target policy를 학습시킬 수 있습니다.
- ManyToOne - 동시에 여러 개의 behaviour policy가 겪은 경험 데이터를 모아 한 개의 target policy를 학습할 수 있습니다.
Theoretical Background of Q-Learning
SARSA는 Bellman expected equation을 사용했지만, Q-learning은 Bellman optimization equation의 q-funcion으로 target policy를 improve합니다.
off-policy의 주된 장점은 exploratory policy를 따르면서도 optimal policy를 학습할 수 있다는 것인데, 이를 해낸 것은 아래의 알고리즘입니다.
- Behaviour policy: -greedy w.r.t Q(s,a)
- Target policy: greedy w.r.t Q(s,a)
아래는 optimal q-function을 update하는 식과 control에 대한 backup diagram과 algorithm입니다. optimal value function의 관계식을 이용하기 때문에 optimal action-value function에 수렴하게 됩니다.
SARSA vs Q-Learning
SARSA의 기댓값 (𝐸𝜋)
- policy 𝜋를 따라가는 경로에 대해서 기댓값을 취하라는 의미입니다. 즉, Bellman expected equation을 생각해보면 policy에 의한 확률적인 요소 𝜋(a|s)와 환경에 의한 확률적인 요소 transition probability 모두 고려하여 기댓값을 취하라는 것입니다.
Q-Learning의 기댓값 (𝐸𝑠′)
- policy 𝜋와 아무런 관련이 없는 항이며, 계산할 때에 어떠한 policy를 사용해도 상관 없다는 것을 의미합니다.
- 임의의 policy를 사용하여 주어진 환경 안에서 데이터를 모으면, 그 데이터 안에 transition probability 등 확률적인 요소가 모두 반영되어 sample이 모이고, 그 sample을 이용하여 기댓값을 계산합니다.
- Q-learning 수식에서 𝜋와 관련된 항들이 사라진 이유는 이 식이 Bellman optimization equation이기 때문입니다. 즉, optimal policy는 환경에 dependent하며, 환경이 정해지면 그에 따라 optimal policy도 정해집니다. 따라서 환경을 충분히 잘 exploration한다면 optimal policy를 구할 수 있으며 여기서 환경을 exploration하는데 사용하는 policy는 어떤 policy이든 상관없는 것입니다.
이 예제에서 목표는 S라는 start state에서 시작해서 goal까지 가는 optimal path를 찾는 것입니다. 그림에 나와있는 Cliff에 빠져버리면 -100의 reward를 받고 time-step마다 reward를 -1씩 받는 문제라서 절벽에 빠지지 않고 goal까지 가능한 한 빠르게 도착하는 것이 목표입니다.
SARSA와 Q-learning 모두 다 ϵ-greedy한 policy로 움직입니다. 따라서 Cliff에 빠져버리기도 합니다. 차이는 SARSA는 on-policy라서 그렇게 Cliff에 빠져버리는 결과로 인해 그 주변의 상태들의 value를 낮다고 판단합니다. 하지만 Q-learing의 경우에는 비록 ϵ-greedy로 인해 Cliff에 빠져버릴지라도 greedy한 policy로 q-function을 update합니다. 따라서 Cliff 근처의 길도 Q-learning은 optimal path라고 판단할 수 있어서 이 문제의 경우 SARSA보다는 Q-learning이 적합하다고 할 수 있습니다.
SARSA에서 탐험을 위해서 ϵ-greedy를 사용했지만 결국은 그로 인해서 정작 agent가 optimal로 수렴하지 못하는 현상들이 발생한 것입니다. 따라서 Q-learning의 등장 이후로는 많은 문제에서 Q-learning이 더 효율적으로 문제를 풀었기 때문에 강화학습에서 Q-learning은 기본적인 알고리즘으로 자리를 잡게 됩니다.
Reference
[1] "바닥부터 배우는 강화학습", http://www.yes24.com/Product/Goods/92337949
'Reinforcement Learning' 카테고리의 다른 글
| [강화학습] Monte-Carlo Methods (2) | 2023.05.23 |
|---|---|
| [강화학습] Planning by Dynamic Programming (1) | 2023.04.26 |
| Bellman Equation(벨만 방정식)이란? (0) | 2023.03.30 |
| Markov Decision Process (MDP)란? (0) | 2023.03.16 |
