모델프리 학습 - Model Free Learning - Control technique on Off-Policy

Model Free 상황에서 Off-policy learning에 해당하는 학습 방법에 대해 알아보자.

---

이전 글 : 모델프리 on-policy Control

[Artificial Intelligence/Reinforcement Learning] - 모델프리 학습 - Model Free Learning - Control technique on On-Policy

모델프리 학습 - Model Free Learning - Control technique on On-Policy

 

Background Remind

이번 포스팅에서는 off-policy 상황에서의 control 문제를 다뤄 보려한다. 이에 앞서 off policy control 문제를 해결하기 위해 필요한 개념들을 키워드 위주로 간략히 정리해보면 아래와 같다. 모두 지금까지의 진행 과정에서 다루었던 개념들이다.

• Model free
  • Model free prediction
    • reward 와 state transition probaility 를 모르는 unknown MDP 에서 value funtion 을 추정
  • Model free control
    • unknown MDP에서 optimal 한 value funtion, policy를 찾아 최적화
• Monte-carlo (MC) Learning
  • Model free상황에서 실제 에피소드를 진행해본 경험으로 학습하는 기법. complete episodes 를 통해 받은 return 값으로 현재의 state value funtion 을 측정하고 업데이트
  • 반드시 ternimal state 가 있어야 하고, value 는 곧 N회 시행에 대한 mean 으로 추정
• MC control
  • MC과정에서 매 에피소드 종료시마다 policy를 개선하기 위하여 policy evaluation 을 통해 prediction. 이때 평가 척도는 Q가 되고 Q는 곧 state 별 action value funtion
  • 그 후 policy improvement를 통해 contro하여 최적 policy* 와 q* 에 수렴. $\epsilon$-greedy 기법
• Temporal-Difference (TD) Learning
  • Model free상황에서 실제 에피소드를 진행해본 경험으로 학습하는 기법. incomplete episodes 로 바로 다음 state에서의 예측값을 가지고 현재의 state value funtion 을 측정하고 업데이트
  • 반드시 terminal state 가 없어도 됨. 예측된 리턴을 TD target이라하며 MC에서의 확정적 리턴을 대체
• SARSA
  • TD target을 통해 현재 state의 action value funtion 을 업데이트 하는 법. 업데이트 대상은 Q이고 이게 곧 $Q(S,A)$ 임.
• SARSA control
  • TD과정에서 에피소드 내 매 time step 마다 policy를 개선하기 위하여 policy evaluation을 통해 pridiction. 이때 평가 척도 역시 Q가 되고 Q는 곧 state 별 action value funtion
  • 그 후 policy improvement를 통해 contro하여 최적 policy* 와 q* 에 수렴. $\epsilon$-greedy 기법
• $\epsilon$-Greedy Exploration
  • state 에서 action을 선택할때 항상 높은 value를 가진 곳으로 선택되나, 랜덤으로 다른 action을 선택 하여 exploration 해보는 테크닉
• On policy learning
  • 동일 agent 가 policy 따라 경험하고 해당 policy를 스스로 업데이트
  • MC, TD와 같은 방법으로 학습 진행
• Off policy learning
  • 다른 agent나 사람이 하는 행동 policy를 학습하여 해당 agent의 policy 를 업데이트
  • Q-learning

---

 

Off Policy Learning 에 대해서

Off policy learning 은 앞선 정리에서 확인 할 수 있듯이 학습하고자 하는 policy 를 위해 다른 제 2의 policy 를 활용하는 기법이다. 다시 말해 target policy를 따랐을 때, 어떤 state value funtion 이나 action value function을 얻을 수 있는 지를 평가 하고싶은 건데, 실제 이 에피소드는 behavior policy를 따르는 것이다.

• 학습해서 개선 시키고자 하는 target policy 를 $\pi(a|s)$라 하고, $\pi(a|s)$는 greedy를 따라 action을 선택하여 $V_{\pi}(a|s)$ 와 $Q_{\pi}(a|s)$ 를 계산 한다
• 타 agent의 경험으로 부터 이미 만들어져 학습에 사용되는 behavior policy 를 $\mu(a|s)$라 하고, $\epsilon$-Greedy 를 따라 action을 선택한다.

$$ \left\{ S_1, A_1, R_1, ..., S_T \right\} \sim \mu $$

optimal policy로 수렴 시키고픈 target policy는 greedy 를 따르고, 이 수렴 과정에서 사용 되는 exploratory policy 는 $\epsilon$-Greedy 를 따른 다는 점이 특이하다. 이러 한 off policy learning은 old policy 들로 부터 나온 경험을 재활용 한다거나, 하나의 behavior policy를 따라서 여러개의 policy를 동시에 학습 할 수 있다는 장점이 있다.

---

 

Importance Sampling - Prediction

통계 및 머신 러닝에서 많은 경우는 어떠한 확률분포 $P(x)$의 기댓값(expected value)를 구하는 것과 밀접하게연결되어있다. Importance sampling은 다른 확률분포의 기댓값을 효율적으로 추정하기 위해 고안되었으며, probability density estimation (확률 밀도 추정)이나 강화학습 등에 다양하게 활용 되고 있다.

목적은 기댓값을 계산하고자 하는 어떤 확률분포 $P(x)$의 PDF(Probability density function, 확률 밀도 함수)는 알고 있지만 $P(x)$에서 샘플을 생성하기가 어려울 때, 비교적 샘플을 생성 하기가 쉬운 $Q(x)$에서 샘플을 생성하여 $P(x)$의 기댓값을 계산 하는 것이다.

확률분포 $P(x)$를 따르는 함수 $f(x)$에 대한 기댓값을 구한다고 했을때, 새로운 확률 분포인 $Q(x)$ 를 의도적으로 1이 되는 형태로 앞에 곱해주어 $Q(x)$에 대한 $P(x)$ 의 비율 형태로 form 을 만들어 준다.

결국 $x$가 $P(x)$를 따랐을 때의 문제가 $x$가 $Q(x)$를 따랐을 때의 문제로 변하게 되며 이 것이 각각 target policy 인 $\pi$와 behavior policy인 $\mu$를 의미하는 것이다.

이는 학습 관점에서 해석해 본다면 episode를 진행할 때 $\mu$라는 확률분포를 따라서 action을 수행하고, 그때 받은 return을 가지고 우리가 실제 목표로 하는 target policy 인 $\pi$를 평가하는 흐름으로 볼 수 있다.

이제 return 에 주목하여 MC와 TD learning 방식을 고려해보자.

 

Importance sampling for Off-policy MC

$\mu$를 통해 받은 return은 $\pi$를 evaluate 하기 위해 사용 되는데 여기서 value funtion 업데이트 시 필요한 $G_t$에 두 policy의 similarity 를 담은 수식을 곱해주어 weight return 으로 만들어 줘야 하며 이것은 전체 에피소드에서 importance samling 에 대한 correction 을 하는 보정치로서 동작하게 된다.

이렇게 산출 된 weight return 은 bellman equation 에 따라 value update 과정에 아래와 같이 기여한다.

(Update value towards corrected return의 의미)

Importance sampling 을 통한 Off-policy MC기법의 핵심은,

Importance sampling 을 통해서 $\pi$와 $\mu$의 비율을 계속 곱해줌으로서 실제로는 $\mu$를 따랐지만 $\pi$를 따랐을 때의 return을 estimation 할 수 있다는 것이다.

하지만 이러한 방식을 적용 했을때 아래와 같은 두가지 문제점이 있다.

• $\pi$가 zero가 아닌경우, $\mu$가 만약 zero 라면 사용할 수 없다. (그냥 return이 0이 되므로)
• 매번 episode가 끝날때마다 확률적으로 action 을 선택하니 high variance. (MC의 고유 특성이기도 함)

 

Importance sampling for Off-policy TD

$\mu$를 통해 받은 return은 $\pi$를 evaluate 하기 위해 사용 한다는 것은 MC 와 동일하나, TD의 특성인 TD target을 return 으로 활용 한다는 점이 다르다. 즉, MC에서 사용한 weight return $G_t$ 대신에 weight TD target 인 $R+\gamma V(S')$ 를 importance sampling 으로 얻고 value function 업데이트에 활용 한다는 점이 다르다.

앞서 MC의 high variance 문제와 learning delay 문제를 해결하기 위해 TD를 적용한 바와 같이, 여기서도 TD로 Importance sampling 을 하게 되면 하나의 에피소드 내 바로 다음 time step뒤 한번의 확률 분포 연산에 따른 차이만 존재하게 되므로 variance 가 자연 감소하게 된다.

이는 한번만 $\mu$와 $\pi$의 비율을 적용하여 TD target 에 곱함으로서 value function 을 업데이트 하는 아래의 수식으로 표현 된다.

지금까지 Importance sampling을 통해 어떻게 off policy learning 을 하는지? off-policy에서 특히 실제 behavior policy를 통해 나온 값들을 통하여 어떻게 terget policy 를 평가하고 target policy 의 value 값들을 종합적으로 Prediction 할 수 있는지를 알아 보았다.

그럼 이제 어떻게 optimal 한 policy 까지 만들어 낼 수 있을까? 이제는 Control 문제다.

---

 

Q-Learning

앞서 Model based 상황에서 학습의 대상이 되는 value를 action value function인 $Q(s,a)$ 로 보고 학습하는 과정을 살펴 본 바 있다. 사실상 강화학습의 목적은 최적의 value function 을 만들어 내기 위한 action 의 선택 policy 를 최적화 하는 것이므로 value function 역시 action value function 그 자체로 정의하고 학습하는 것이 핵심이라 할 수 있다.

Model free 상황에서도 value function 을 action value function 으로 보고 이 action value funtion으로 업데이트를 진행하면 바로 Q-learning이 된다.

 

Q-Learning Prediction

Q-learning 을 사용하면 Importance sampling기법을 사용할 필요가 없다. 대신 현재의 상태에서 본 다음 action 을 behavior policy를 따라 선택 후 reward 와 state 를 얻는 대신 target policy 를 따라 후속 action을 고려하는 것으로 두 policy를 결합하여 학습한다.

• Behavior policy $A_{t+1} \sim \mu( \centerdot |S_t)$
• Target policy $A' \sim \pi(\centerdot|S_t)$

위 두가지 policy를 action value function 업데이트에 적용 해보면 아래와 같은 수식이 된다.

$$ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha(R_{t+1} + \gamma Q(S_{t+1}, A')-Q(S_t, A_t)) $$

앞서 살펴본 action value function 업데이트 수식을 그대로 따르고 있지만, $R_{t+1} + \gamma Q(S_{t+1}, A')$ 을 TD target 으로 활용 했다는 점이 다르다. 이는 곧 behavior policy $\mu$에서 나온 action 이 아니라 target policy 에서 나온 action에 대한 Q값을 기준으로 TD target을 구성 했다는 의미가 된다.

이 과정을 종합하면 아래와 같다.

Reward 는 behavior policy를 따른 action 으로 받은 reward이고,

State 역시 behavior policy 를 따른 action 에 따른 전이 결과 state’ 인데,

이 다음 state 에서 어떤 action을 선택 할 것인지는 target policy 인 $\pi$를 따른 것으로 다음 state 의 Q값을 예측 한다는 의미가 된다.

 

Q-Learning Control

이제 behavoir policy 와 target policy 둘다 활용 하여 improvement 를 수행 하고 optimality 를 확보 해야 한다. 여기서 각 policy 별로 off policy learing의 대전제를 따라 아래와 같은 룰을 부여 한다.

• behavior policy $\mu$ 는 $\epsilon$-Greedy 기법을 따라 랜덤 exploration 을 일부 수행
• target policy $\pi$는 greedy 기법을 따라 최대 Q를 가질 수 있는 action 을 확정적으로 선택

return 을 의미하는 TD target 에 대한 maximize는 아래와 같다.

뭔가 복잡해 보이지만, 좌변은 그냥 TD target 그 자체고 좌변에 활용된 $A'$는 target policy 에서 나온 action 임을 의미한다. 이 $A'$ 역시 action value function 인 $Q(s,a)$ 꼴로 바꿔 주고 이에 대해 greedy 한 방식의 maximize 를 입혀 주면 위 수식이 완성 된다.

이 과정의 흐름을 쭉 따른 방식이 SARSA Max 가 되며, 개념을 도식화 해서 표현하면 아래와 같이 정리 된다.

지금까지 다룬 내용으로 큰 범주에서 보면 강화학습의 기본 frame 은 모두 다뤘다고 보면 되는데,

지금까지 나온 개념들을 종합하면 아래와 같은 분류로 DP 와 TD관점에서 상호관계를 확인 해 볼 수 있다.

• MC는 현실 문제에서 적용 하기에는 variance 가 너무 크므로 TD를 주로 쓴다.
• Full backup 은 다수의 episode를 고려하는 방식이고,
• Sample backup 은 하나의 episode 단위로 학습을 하는 방식이다.

 

---

지금까지 RL 모델, Bellman Equation 과 같은 개념,

value iteration, policy iteration 과정을 통한 prediction / control 문제 해결의 기본 개념,

model based VS model free, on-polish VS off-policy 와 같이 상황에 따른 학습 방법과,

Importance sampling, $\epsilon$-Greedy 와 같은 테크닉,

DP, MC, TD, Q-learning 으로 종합적인 prediction, contol 문제를 해결 하는 방법에 대해 쭉 알아보았다.

 

다음 정리 부터는 지금까지 보다는 심화과정(?)이되는 여러 테크닉들을 정리할 계획인데,

일단 학습과정에서 실제 value function을 일일이 계산하지 않고 추정하는 value function approximation 을 소개 할 예정이다.