[Remark] 강화학습 Return에 대한 이해와 n-step Return

 

강화학습 Return에 대한 이해와 n-step Return 

 

Return 과 n-step return

강화학습에서는 순간적인 보상을 최대화하는 것보다 한 단계 더 나아가서 미래에 받게 되는 보상까지 더한 값을 최대화합니다. Return은 미래보상까지 더해진 값을 나타내며 다음과 같이 쓸 수 있습니다. 이 때, $\gamma$ 는 미래에 대한 패널티로 discount factor입니다.

$$G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots$$

$t$ 시간에 보상은 그 후에 발생되는 미래의 사건들의 보상을 모두 더하기 때문에, 에피소드가 길다면, 굉장히 먼 미래까지 고려해야 합니다. 심지어는 끝나지 않는 에피소드의 경우, $G_t$ 값을 구하기 위하서 무한에 가까운 값들을 더해주게 됩니다. 이러한 한계를 해결하기 위해서 n-step return은 미래를 n-step 까지만 고려하고 그 이후에 대해서는 근사치로 값을 구합니다. 근사하는 방법은 다음과 같이 세 가지가 있습니다.

 

1. $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n V_{t+n-1} (S_{t+n})$
2. $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n Q_{t+n-1} (S_{t+n}, A_{t+n})$
3. $G_{t:t+n} = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^n \bar{V}{t+n-1} (S{t+n})$

• Expected approximate value of state $s$ : $\bar{V}_t(s) = \sum_a \pi(a|s) Q_t (s,a)$

 

첫 번째는 상태에 대해서 근사치를 구하고, 두 번째는 (상태 + 행동)에 대해서 근사치를 구하게 됩니다. 근사를 많이 할 경우, Return값을 좀더 정확하게 근사할 수 있습니다. 1번과 2번으로 구한 근사치로부터 Value function을 업데이트 하는 두 개의 알고리즘은 다음과 같습니다. 3번의 경우는 Q로부터 V 값을 근사하는 방식입니다. 

 

n-step TD prediction    $V(s)$

$V_{t+n}(S_t) = V_{t+n-1}(S_t) + \alpha [G_{t:t+n} - V_{t+n-1}(S_t)]$

n-step Sarsa   $Q(s,a)$

$Q_{t+n}(S_t, A_t) = Q_{t+n-1}(S_t, A_t) + \alpha [G_{t:t+n} - Q_{t+n-1}(S_t, Q_t)]$

두 알고리즘은 똑같은 형태로 value function을 어떤 걸로 하냐는 차이만 있습니다. 여기서 $\alpha$ 는 learning-rate로 value function을 업데이트 하는 정도를 나타냅니다. 두 가지 방법 모두 업데이트를 진행하면서 어떤 값으로 수렴하게 됩니다.

---

더욱 다양한 Return 사용 방법들  (Advanced)

앞에서 근사된 Return을 사용하는 두 가지 방법을 살펴봤는데, 추가적으로 3가지가 더 있습니다. 

 

off-policy n-step Sarsa 

n-step Sarsa와 형태가 굉장히 유사한 off-policy n-step Sarsa는 Q-value를 업데이트 하는데 사용되는 샘플이 현재 policy와 다를 경우 사용합니다. 예를 들어서 게임 실력에 대해서 적합한 value function이 있는데, 게임 실력이 향상된다면, 이전 value function으로 근사할 경우 문제가 생깁니다. 그래서 이 알고리즘은 선택되는 행동의 확률에 대한 비율을 곱함으로써, 현재 행동 $\pi$ 에 더 많이 나오는 행동에 가중치를 더욱 주고, 더 적게 나오는 경우는 가중치를 줄이는 방식으로 업데이트 양을 조절합니다.

$$\rho_{t:t+n-1} = \prod_{k=t}^{\min(t+n-1,~ T-1)}\frac{\pi(A_k|S_k)}{b(A_k|S_k)}$$

$$Q_{t+n}(S_t, A_t) = Q_{t+n-1} (S_t, A_t) + \alpha \rho_{t+1:t+n} [G_{t:t+n} - Q_{t+n-1}(S_t, A_t)]$$

n-step Tree Backup Algorithm 

tree backup은 행동 실제로 택한 행동 $A_t$ 와 실제로 택하지 않은 행동 $a$ 들에 대해서 return 값을 평균내는 방식으로 업데이트를 진행합니다. 예를 들어서, 100 time step 만큼 시뮬레이션을 했다면, 각 time step $k$ 에 대해서 선택한 행동과 나머지 행동들이 있을 것이고, 선택한 행동에 대해서는 정확한 $G_{t_k:t+n}$ 값을 구하고, 선택하지 않은 행동 $a$ 에 대해서는 $Q_{t+n-1} (\cdot, a)$ 로 값을 예측합니다.

$$G_{t:t+n} = R_{t+1} + \gamma \Big( \pi (A_{t+1}| S_{t+1}) G_{t+1:t+n} + \sum_{a \ne A_{t+1}} \pi(a |S_{t+1} ) Q_{t+n-1} (S_{t+1}, a) \Big)$$

n-step $Q(\sigma)$ 

$Q(\sigma)$ 는 0 또는 1의 값을 가지는 $\sigma$ 를 샘플링해서, $\sigma = 0$ 인 경우는 샘플링 없이 Expectation을 하고, $\sigma =1$ 인 경우는 샘플링을 통해서 importance sampling ratio를 곱한 값을 사용해서 업데이트 합니다.

 

$$\begin{aligned} G_{t:t+n} &=R_{t+1} + \gamma \bar{V}_{t+n-1} (S_{t+1}) \\ & + \gamma \Big( \sigma_{t+1} \rho_{t+1} +(1-\sigma_{t+1}\pi(A_{t+1} | S_{t+1})) \Big) \cdot\Big( G_{t+1:t+n} - Q_{t+n-1} (S_{t+1}, A_{t+1}) \Big) \end{aligned}$$

 

Sutton 책에 나와있는 그림으로 이해하면 다음과 같이 구분됩니다.

 

Sutton 책에 있는 그림으로 이해하면 다음과 같습니다 .

여기서 총 5가지의 Return을 근사하는 방법에 대해서 살펴보았습니다. 해당 업데이트 방식은 Return 값을 찾는데 목적이 있으며 value function $V$ 나 $Q$로부터 어떻게 컨트롤을 하는지는 다루지 않았습니다. 근사하는 방식이 다양하기 때문에 하는 역할이나 장점에 대해서 혼동이 있을 수 있습니다. 그러나 공통적인 목적은 Return 값을 추정하는 것 입니다.

---

😀included n-step methods

• n-step TD prediction
• n-step Sarsa
• off-policy n-step Sarsa
• n-step Tree Backup Algorithm
• n-step $Q(\sigma)$

---