[강화학습] 2주차 3강 ~ 4강

혁펜하임님의 트이는 강화학습을 보고 학습 중 입니다.

Optimal Policy

• State Value function을 Maximize하는 policy
• $V(s_t) \triangleq \int G_t P(a_t...a_{\infty})da_t:a_{\infty}$을 최대화하는 $P(a_t,s_t)$. $= \int Q(s_t,a_t)p(a_t|s_t)da_t$
• 현재의 optimal policy를 구하는 게 목적, 미래의 optimal policy가 주어져 있다고 가정.
• $P^*(a_t|s_t) = \underset{p(a_{t+1}|s_{t+1})}{argmax} \int Q^*(s_t,a_t)da_t$
  • $P^*$ : 현재 상태에서의 optimal policy
  • 즉, 미래의 Q를 최대화하는 action을 선택하는 pdf
  • $a^*_t \triangleq \underset{a_t}{argmax}Q^*(s_t,a_t)$ -> greedy action의 근거
  • $P^*(a_t|s_t) = \delta(a_t-a^*_t) \rightarrow a^*_t$를 선택하는 policy

$Q^*$를 구하는 법

1. Monte Carlo Method

• $Q(s_t,a_t) \triangleq \int G_tP(s_{t+1},a_{t+1},...|s_t,a_t)ds_{t+1}:a_{\infty} \simeq \frac{1}{N}\sum G^{(i)}_t$
  • why? : $E[x] = \int xp(x)dx \simeq \frac{1}{N}x_i$
• $Q^*$를 구하기 위해 아주 많은 epi를 진행하여 샘플을 수집한뒤에 이들을 평균을 내서 가치 함수로 사용함.
• Incremental Monte Carlo
  • $$\sum \overline{Q_{N-1}} + \frac{1}{N}(G_t^n-\overline{Q_{N-1}})$$
  • TD에서 식을 정리해서 얻을 수 있음. 앞에까지 평균 내어둔 것에 이번에 얻은 샘플을 더해 점진적으로 평균을 업데이트 해나감.
  • 수 많은 에피가 다 끝날 때까지 기다리지 않아도 됨. 매 에피마다 업데이트 할 수 있음.

2. Temporal Difference (TD)

• $Q(s_t,a_t) = \int (R_t+\gamma Q(s_{t+1},a_{t+1})) \overbrace{p(s_{t+1}|s_t,a_t)}^{transition} \overbrace{ p(a_{t+1}|s_{t+1}}^{policy})ds_{t+1},a_{t+1}$
  $\simeq \frac{1}{N} \sum (R_t^{(i)}) + \gamma Q(s_{t+1}^{(i)},a_{t+1}) \rightarrow$ 1stpe만 더 가봄 => 1-step TD
• 에피 종결까지 기다리지 않고 지금까지의 샘플들을 이용해서 다음 스테이트를 보고 업데이트를 진행함.
• SARSA Algorithm
  • Incremental Monte Carlo update식에서 $\frac{1}{N}$을$\alpha$로 표현
  • $$\overline{Q_N} = (1-\alpha)\overline{Q_{N-1}} + \alpha(R_t^{(N)}+\gamma Q(s_{t+1}^{(N)},a_{t+1}^{(N)})$$
  • 새로운 업데이트 값을 $\alpha$만큼의 비율만 받아들임

MC vs TD

1. MC
   • Unbias (장점)
   • Variance$\uparrow$ (단점)
2. TD
   • Bias (단점)
   • Variance$\downarrow$ (장점)

On-policy and Off-policy

• On-policy : behavior policy = Target policy
• Off-policy : behavior policy $\neq$ Target policy

Behavior Policy?

• 실제 행동을 하여 다음 state를 얻는 것. 실제로 취하는 행동의 pdf

  Target Policy?

• TD Target을 얻기위한 policy
  

  

  off-policy를 사용하는 이유?

1. Targetploicy 를 사람/ other agents 가 생성한 policy를 사용할 수 있음.
2. 실컷 탐험하면서도 optimal policy로 sample을 얻을 수 있음.
3. 재평가가 가능함

• Q-learning
  • Target policy : Greedy Action
  • Behavior Policy : $\epsilon$-greedy
  • $\int (\overbrace{R_t+\gamma max Q(s_{t+1},a_{t+1})}^{TD-target})p(s_{t+1}|s_t,a_t)ds_{t+1}$

SARSA vs Q-learning

• 음수의 return과 goal이 가까이 있을 때
  • SARSA는 처음에 음수를 피해 매우 멀리 달아남. 많은 반복을 통해 최적의 길을 찾음
  • Q-learning은 max만을 취하기 때문에 음수를 멀리 피하지 않음. SARSA보다 빠르게 최적의 길을 찾을 수 있음.

2Step-TD

$Q(s_t,a_t) = \int (R_t + \gamma R_{t+1} + \gamma^{2} Q(s_{t+2},a_{t+2}))p(a_{t+2}|s_{t+2})p(s_{t+2}|s_{t+1},a_{t+1})p(a_{t+1}|s_{t+1})p(s_{t+1}|s_t,a_t)ds_{t+1}a_{t+1}s_{t+2}a_{t+2}$

• $p(s_{t+1}|s_t,a_t)$의 $a_t$ $\rightarrow$ behavior policy
• $p(s_{t+2}|s_{t+1},a_{t+1}$의 $a_t$ $\rightarrow$ target policy를 이용해 구하고 싶으나, 실질적으로 behavior policy를 이용해야함.
  • 이를 해결하기위해 importance sampling을 사용함
  • $\int xp(x)dx \simeq \frac1N\sum x_i$ => $x_i$~$p(x)$
    $\int x\frac{p(x)}{q(x)}q(x)dx \simeq \frac1N \sum x_i\frac{p(x)}{q(x)}$ => $x_i$ ~ $q(x)$
• Target policy -> greedy : $p(a_{t+2}|s_{t+2}) = \delta(a_{t+2}-a_{t+2}^*)$
  $$Q(s_t,a_t) = \int (R_t + \gamma R_{t+1} + \gamma^{2} max Q(s_{t+2},a_{t+2})) p(s_{t+2}|s_{t+1},a_{t+1}) \frac{p(a_{t+1}|s_{t+1})}{\textcolor{red}{q(a_{t+1}|s_{t+1})}}p(s_{t+1}|s_t,a_t)\textcolor{red}{q(a_{t+1}|s_{t+1})}ds_{t+1}a_{t+1}s_{t+2}a_{t+2}$$
• 이렇게 해서 $p(s_{t+2}|s_{t+1},a_{t+1}$의 $a_t$가 Target policy를 따르는 것 처럼 할 수 있음.
• TD-Target : $\textcolor{red}{\frac{p(a_{t+1}^{(N)}|s_{t+1}^{(N)})}{q(a_{t+1}^{(N)})|s_{t+1}^{(N)}}}R_t+\gamma R_{t+1} \gamma^2maxQ(s_{t+2}^{(N)},a_{t+2}^{(N)})$ : 빨간색 부분은 사용하지 않음. pdf에서 많은 문제가 존재하기 때문.