TRPO (Trust Region Policy Optimization)

Optimizing Policy 에 중점을 둔 논문이다.

Natural Policy Gradient 와 유사하지만, Large Nonlinear Policy 를 optimizing 하는 것을 목표로 하고 있다.

Policy Optimization 의 종류

RL 에서는 state 에 대한 action 을 뱉는게 정책의 역할이다. 이 정책을 업데이트하면 Agent 가 상황에 더 맞는 action 을 취하게 된다.

Policy Iteration Method

• 최근 policy 를 이용해 value function 을 평가하고, policy 를 업데이트하는 것을 반복

Policy Gradient Method

• Sample Trajectory 로부터 수집한 expected return 의 Gradient estimator 를 사용하는 방법

• Policy 자체의 Gradient 를 이용해서 Objective Function 을 최대화할 수 있도록 $\pi_\theta$ 를 업데이트한다.

Derivative-Free Optimization Method

• Gradient 를 사용하지 않고 Optimal solution 을 찾는 방법
• Reward Function 을 Black box function 이라고 취급하고 최적화를 진행

Derivative-Free Optimization Method

cross-entropy method , covariance matrix adaption method 등등이 해당하는데, 구현과 이해가 쉽지만, 좋은 결과를 내기 때문에 다양한 문제에 사용된다.

Gradient based 최적화는 Gradient-free 기반 최적화보다 sample complexity 측면에서는 유리하다. (더 적은 샘플을 가지고 빠르게 최적해를 찾을 수 있다.)

TRPO 알고리즘은 수만개의 파라미터를 사용하는 task 에서도 강건하게 동작한다.

TRPO

두가지 Variants 알고리즘을 소개한다.

Single-path : model-free 알고리즘, Agent 가 상호작용하며 겪은 하나의 Rollout 데이터를 기반으로 최적화

Vine : 특정한 state 를 저장해두었다가, 해당 state 를 restore 하고 다양한 action 들을 실험하며 최적화 (Variance 를 줄일 수 있다.)

Terminology + formula

$$Tuple = (S, A, P, r, \rho_0, \gamma)$$

    - $S$ : finite set of states     - $A$ : finite set of actions

• $P : S \times A \times S \rightarrow \R$ : transition probability distribution
  • $(s_t,a_t) \text{를 받아서} s_{t+1} \text{를 반환할 확률}$
• $r : S \rightarrow \R$ : reward function
• $\rho_0 : S \rightarrow \R$ : initial state $s_0$'s distribution
• $\gamma$ : discount factor

$$\pi , \tilde\pi , \eta, A(s,a)$$

• $\pi$ : policy, state $s$ 에 따른 action $a$ 의 확률 분포
• $\tilde\pi$ : new policy
• $\eta$ : Policy 의 기대 보상
• $A(s,a)$ : (s,a) 에 대한 Advantage 값
  • Advantage : Agent 의 Policy 와 비교했을때, $s$ 에서 $a$ 의 행동을 취한게 얼마나 이점이 있는지를 수치화

$\eta(\pi) = \mathbb{E}_{s_0a_0,...}[\sum_{t=0}^\infty \gamma^tr(s_t)]$

• reward function 과 discount factor 로 이루어진, policy 평가 함수

$\eta(\tilde\pi) = \eta(\pi) + \mathbb{E}_{s_0,a_0,...\sim\tilde\pi}[\sum_{t=0}^\infty \gamma^t A_\pi(s_t,a_t)]$

• new policy 에 대한 평가 함수는 위와 같이 구성된다.
• new policy 로 부터 샘플링한 Action 을 이용해서 Advantage 함수를 적용해 기존 정책과 얼마나 이점을 갖는지를 계산한다.

TRPO 에서 기본적으로 사용하는 함수들의 standard definition 들을 꼭 익히고 가야할 것 같다. 논문 처음 읽을때는, 대충 이해하고 넘어갔는데, 후반부 내용을 이해하는데 너무 어려워서 추가한다.

$Q_\pi$ : state-action value function

Q 함수는 state-action pair 를 입력으로 받아서, 해당 특정 state 에서 특정 action 을 취했을때 얻을 수 있는 기대 보상 기댓값 (현재보상과 미래보상 모두를 아우르는) 을 출력해준다.

$$Q_\pi(s_t, a_t) = \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) \right]$$

그리고 기댓값의 성질을 이용해서 위 수식을 다음과 같이 변형이 가능하다.

$V_\pi$ : Value function

Value function 은 state 만 받아서, 해당 state 에서 취할 수 있는 모든 action 을 고려했을때의 기대 보상 기댓값을 의미한다.

$$V_\pi(s_t) = \mathbb{E}_{a_t,s_{t+1},\dots}\left[ \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) \right]$$

Q 함수랑 완전 똑같아 보이는데 다른 점은 $\mathbb{E}$ 아래에 $_{a_t}$ 가 추가되어 있다. 이는 기댓값을 계산하는데 $s_t$ 에서 선택할 수 있는 무작위 행동들 $a_t$ 에 대해서도 기댓값 처리를 적용하겠다는 것이다.

즉, $a_t$ 에 대한 기댓값 처리 부분을 덜 추상적인 수식으로 expand 하면 다음과 같다.

$$V_\pi(s_t) = \sum_{a_t} \pi(a_t | s_t) \cdot \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) \right]$$

위 수식은 그냥 기댓값의 정의에 의해서 식을 확장한 것이다.

• 간단한 예) 주사위를 던지는 행위의 기댓값를 생각해보면, x=주사위의 눈, f(x)=x

  • $\mathbb{E}_x \left[ f(x)\right] = \sum_x P(x)\cdot f(x)$

• $a_t$ 는 policy 확률분포에 의해서 결정됨으로 위 식의 P(x) 를 policy 로 바꾼 것 뿐이다.

그리고 위와 같이 수식을 변형하면 다음과 같은 등식이 성립한다는 것을 알 수 있다.

$$V_\pi(s_t) = \sum_{a_t} \pi(a_t | s_t) \cdot \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) \right] \\ = \sum_{a_t} \pi(a_t | s_t) \cdot Q_\pi (s_t, a_t)$$

다음으로, $Q_\pi$ 수식을 변형해보자.

• 1.$\mathbb{E}$ 아래첨자에 포함된 변수들이 기댓값 적용 대상이기 때문에, 여기 해당하지 않는 변수들은 모두 상수취급이 가능하다.

• 2.기댓값은 하나씩 벗겨낼 수가 있다. $s_{t+1}$ 에 의해 $a_{t+1}$ 을 결정하고, 쭊쭊 연쇄적으로 발동되다보니, 바깥쪽에서부터 벗겨낼 수가 있다.

$$Q_\pi(s_t, a_t) = \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) \right] \\ = r(s_t) + \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ \gamma r(s_{t+1}) + \gamma^2 r(s_{t+2}) + \dots \right] \\ = r(s_t) + \gamma \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ r(s_{t+1}) + \gamma r(s_{t+2}) + \dots \right] \\ = r_(s_t) + \gamma \mathbb{E}_{s_{t+1}} \textcolor{blue}{\mathbb{E}_{a_{t+1}, s_{t+1},\dots} \left[ r(s_{t+1}) + \gamma r(s_{t+2}) + \dots \right]} \\ = r_(s_t) + \gamma \mathbb{E}_{s_{t+1}} \textcolor{blue}{V_\pi(s_{t+1})}$$

위 식도 추상적인 E 기호를 sum 으로 변환하면 아래와 같이 Q 와 V 의 관계를 표현할 수 있다.

$$Q_\pi(s_t, a_t) = \mathbb{E}_{s_{t+1},a_{t+1},\dots}\left[ \sum_{l=0}^{\infty} \gamma^l r(s_{t+l}) \right] \\ = r(s_t) + \gamma \sum_{s_{t+1}} p(s_{t+1} | s_t, a_t) V_\pi(s_{t+1})$$

p 는 MDP 에서 상태 전이 확률을 의미한다.

Visitation Frequency

확률 분포가 아닌, 방문 빈도를 이용

$\mathbb{I(s_t=s)} \begin{cases} 1 & \text{if } s = s_t \\ 0 & \text{otherwise} \end{cases}$ 이와 같은 지표함수가 있을때, $\sum_{t=0}^\infty \mathbb{I}(s_t=s)$ 는 총 방문 빈도를 의미하게 된다.

이때, 방문 빈도의 기댓값은 아래와 같이 표현할 수 있다. (기댓값의 Linearity)

$$\mathbb{E}[\sum_{t=0}^\infty \mathbb{I}(s_t=s)] = \sum_{t=0}^\infty \underbrace{\mathbb{E}[\mathbb{I}(s_t=s)]}_{확률} = \sum_{t=0}^\infty P(s_t=s)$$

위를 이용해서 $\rho$ 를 다음과 같이 표현할 수 있다. ( $\rho_\pi$ : policy $\pi$ 를 따를때, state 에 대한 확률 분포)

$\rho_\pi(s) = P(s_0 =s) + \gamma P(s_1=s) + ... \rightarrow \text{아래의 (1)}$

위 수식을 이용해서 $\eta$ 수식을 아래와 같이 Visitation Frequency 로 표현할 수 있다.

$$\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0,a_0,...\sim\tilde{\pi} }[\sum_{t=0}^\infty \gamma^t A_{\pi}(s_t,a_t)] \\ = \eta(\pi) + \sum_{t=0}^\infty \gamma^t \mathbb{E}_{s_0,a_0,...\sim\tilde{\pi}}[A_\pi(s_t,a_t)] \\ = \eta(\pi) + \underbrace{\sum_{t=0}^\infty \gamma^t\sum_s p(s_t=s|\tilde{\pi})}_{(1)} \sum_a \tilde\pi(a|s) \cdot A_\pi(s,a) \\ = \eta(\pi) + \sum_{s} \rho_{\tilde{\pi(s)}} \underbrace{\sum_a \tilde{\pi(a|s)}A_\pi(s,a)}_{(2)}$$

그리고 위 수식을 통해서 새로운 Policy $\tilde\pi$ 는 항상 기존 policy $\pi$ 보다 적어도 같거나, gain 을 얻게 된다는 것을 알 수 있다.

• $(2) \ge 0$ 이기 때문이다.

하지만, 우리는 Advantage 를 계산할때, Agent 가 경험한 Experience 를 기준으로 샘플링을 해오는 것이기 때문에 Agent 가 실제로 취한 Action 에 대해서, 정확한 보상을 계산하지 못한다.

그래서, 이론상으로는 항상 새로운 Policy 가 기존 Policy 보다 우월해야하지만, 실제로는 Advantage 가 음수가 되는 경우가 발생하기 때문에 새로 update 한 policy 가 오히려 성능이 떨어지는 경우가 발생한다.

그래서 논문에서는 Local Approximation 을 통해 업데이트를 한다.

$$L_\pi(\tilde\pi)= \eta(\pi) + \sum_{s} \textcolor{blue}{\rho_\pi}(s) {\sum_a \tilde\pi(a|s)A_\pi(s,a)}$$

Conservative Policy Iteration

$\eta$ 를 업데이트하기 할때, lower bound 를 제공하는 Policy update 기법이다.

$$\pi' = \arg max_{\pi'} L_{\pi_{old}}(\pi') \\ \pi_{new}(a|s) = (1-\alpha)\pi_{old}(a|s) + \alpha\pi'(a|s)$$

• $L$ 은 Policy 를 Evaluate 하는 Approximator 이고, $\pi_{old}$ 를 기준으로 평가했을때, 가장 점수가 높은 $\pi'$
• 위에서 구한 $\pi'$ 를 이용해서, Policy 를 기존 Policy 와 가중합을 진행해서 새로운 Policy 를 구한다.

위 공식을 이용해서 구한 new policy 의 lower bound 는 다음과 같다.

$$\eta(\pi_{new}) \ge L_{\pi_{old}}(\pi_{new}) - \frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2$$

$\alpha$ 를 Distance measure 로 대체해 이를 General stochastic policy 로 확장한다.

여기서 사용한 Distance Measure 는 Total Variation Divergence 이다. $D_{TV}$ 는 바로 아래에서 기술

중간 정리

우선 여기서, 수식들을 모아서 한번 정리하고 상세 설명을 덧붙이고자한다. 내가 이해한 대로 적는 거다보니 틀린 부분이 있을 수도 있다.

우선 State 에 대해서 State 가 발생할 확률 이 아닌, 빈도를 기반으로 수식을 한번 변형했다.

$$\rho_{\pi}(s) = p(s_0=s) + \gamma p(s_1=s) + ... \\ = \sum_s \rho_\pi(s)$$

그리고, 이 빈도 계산 수식을 이용해서, $\pi$ 정책의 Expected Reward 를 계산한다.

$$\eta(\tilde\pi) = \eta(\pi) + \sum_s\rho_{\tilde\pi(s)} \sum_a \tilde\pi(s|a) A_\pi(s|a)$$

위 수식에 의해서 새로 생성한 policy 가 항상 기존 policy 보다 우월하다는 것이 이론적으로 맞지만, Advantage 함수가 샘플링 데이터를 기반으로 구해지는 것이기 때문에, 실제와는 상이할 수 있다.

그리고 위 수식에서 사용한 $\tilde\pi$ 는 아래 수식에 의해서 계산한다.

$$\tilde\pi(s) = \arg max_a A_\pi(s,a)$$

정책은 state 에 대해 Action 을 뱉는 함수이기 때문에, old policy 를 기준으로 가장 뛰어난 Action 을 Advantage 를 기준으로 계산해서 $\tilde\pi$ 의 값으로 사용한다.

그런데, 위 $\tilde\pi$ 의 수식의 complexity 때문에, 쉽사리 최적화할 수 없고, 그래서 Approximate 수식을 제안한다. Approximate 수식의 기반은 "old Policy 와 Updated Policy 는 크게 다르지 않을 것이다" 라는 가정에서 출발한 것이다.

그래서, $\tilde\pi$ 정책에 대한 평가 척도를 아래와 같이 수정해서 사용한다.

$$L_\pi(\tilde\pi) = \eta(\pi) + \sum_s\rho_\pi(s) \sum_a \tilde\pi(s|a) A_\pi(s|a)$$

얼마나 큰 Step Size 를 가져야하는가? 에 대한 증명을 위해서 사용된 것이 Conservative Policy Iteration 이다.

$\pi' = \tilde\pi, \pi_{old} = \pi$ 라고 설정하고, 아래와 같이 $\pi'$ 를 설정한다.

$$\pi' = \arg max_{\pi'} L_{\pi_{old}}(\pi')$$

그리고, $\pi_{new}$ 는 아래 수식에 의해서 구한다.

$$\pi_{new}(a|s) = (1-\alpha)\pi_{old}(a|s) + \alpha\pi'(a|s)$$

위 수식에 의해서 $\eta$ 향상에 대한 Lower Bound 를 보장할 수 있다.

$$\eta(\pi_{new}) \ge L_{\pi_{old}}(\pi_{new}) - \frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2$$

Total Variation Divergence

$D_{TV}(p||q) = \frac{1}{2}\sum_i|p_i-q_i|$

부호와 관계없이, 절대적으로 p 와 q 가 얼마나 다른가? 를 나타내는 거리 척도이다.

논문에서는 $D_{TV}^{MAX}(\pi, \tilde\pi) = \max_s D_{TV}(\pi(\cdot|s) ||\tilde\pi(\cdot|s)) \rightarrow \alpha$ 를 추가로 정의하고, 이를 $\alpha$ 로 정의한다.

• 두 Policy 가 가장 큰 차이가 나는 State 에서의 값

그리고 서로 다른 분포에 속하는 두 Random Variables 를 Coupling 할 수 있다.

바로 위에서 정의한 $\alpha$ 는 두 분포가 가장 큰 차이가 날때의 값을 의미하는 것이고. 이를 통해서 아래처럼 두 분포를 커플링할 수 있다고 한다.

• (1) 두 분포는 최대 $\alpha$ 만큼 다르다.
• (2) 두 분포는 최소 $1-\alpha$ 만큼 같다.

KL Divergence 와의 관계는 다음과 같이 정의된다.

$$D_{TV}(p||q)^2 \le D_{KL}(p||q)$$

그리고 논문은 아래 수식에서 $\alpha$ 를 Distance Measure 로 대체한다.

$$\eta(\pi_{new}) \ge L_{\pi_{old}}(\pi_{new}) - \frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2 \\ \ge L_{\pi_{old}}(\pi_{new}) - C D_{TV}^{max} (\pi_{old}, \pi_{new})^2 \\ \ge L_{\pi_{old}}(\pi_{new}) - C D_{KL}^{max} (\pi_{old}, \pi_{new})$$

아래 수식은 위 Lower Bound 를 그대로 가져온 것이다.

$$M_i(\pi) = L_{\pi_i}(\pi) - C D_{KL}^{max}(\pi_i, \pi) \\$$

이를 다시 말하면, time step 을 t 라고 했을때 아래의 식이 성립하고,

$$\eta(\pi_{t+1}) \ge M_t(\pi_{t+1}), \\ \eta(\pi_t) = M_t(\pi_t)$$

위 식을 아래로 변형할 수 있다.

$$\eta(\pi_{t+1}) - \eta(\pi_t) \ge M_t(\pi_{t+1}) - M_t(\pi_t)$$

그리고 최종적으로 $M_i$ 를 반복적으로 Maximizing 함으로써, Objective Function 인 $\eta$ 를 단조증가 시킬 수 있다.

즉, 아래 수식을 통해 최적화가 이루어진다.

$$\pi_{t+1} = \underset{\pi}{\arg \max} [L_{\pi_t}(\pi) - CD_{KL}^{max}(\pi_t, \pi)]$$

바로 위에서 다룬 최적화 수식을 Minorization-Maximization 알고리즘 이라고한다.

논문에서는 위 알고리즘의 KL divergence 에 제약조건을 추가하여 Trust Region Policy Optimization 을 제안한다.

TRPO

Trust Region Constraint 는 KL divergence 에 Coefficient 인 C 를 사용하는게 아니라 아래와 같이 크기에 제약 조건을 달아준다.

$$\underset{\theta}{\text{maximize }} L_{\theta_{old}}(\theta) \\ \text{subject to } D_{KL}^{max}(\theta_{old}, \theta) \le \delta$$

• $C=\frac{2\epsilon\gamma}{(1-\gamma)^2}$ 를 사용할 경우, 이 값을 최적화하기 어렵다.

이론적으로는 위 최적화 기법을 사용하면 되지만, 실제로는 여러 제약조건에 의해 휴리스틱한 Average KL Divergence 를 사용했다.

$$\bar{D}_{KL}^{\rho}(\theta_1, \theta_2) := \mathbb{E}_{s\sim\rho}[\ D_{KL}(\pi_{\theta_1}(\cdot|s)\ ||\ \pi_{\theta_2}(\cdot|s))\ ]$$

• $\rho$ 는 state 에 대한 확률분포 → $\rho$ 로 특정 state 에 방문할 확률 분포를 확인할 수 있다.
• $\pi_{old} \text{ 에서 뽑은 }s$ 를 이용해 $\pi_{\theta_1}, \pi_{\theta_2}$ 의 KL Divergence 의 평균값을 이용한다.
  • KL divergence : 두 확률분포의 차이를 재는 measure

$L_{\theta_{old}} = \text{{maximize}}_\theta \sum_s \rho_{\theta_{old}}(s) \sum_a \pi_{\theta_{old}}(a|s) A_{\theta_{old}}(s,a) \\ \text{subjetc to } \bar{D_{KL}}^{\rho_{\theta_{old}}}(\theta_{old}, \theta) \le \delta$

이제 위 식을 조금씩 변형한다.

먼저, 기댓값의 정의를 생각해보면

$E[f(x)] = \sum_{x \sim P} f(x)P(x) \\ = \int_{-\infty}^{\infty} f(x)p(x)dx$

(1) 위 정의를 적용해

$\sum_s\rho_{\theta_{old}}[...] \rightarrow E_{s\sim\rho_{\theta_{old}}}[...]$

(2) sampling distribution q 를 새롭게 도입해 식을 아래처럼 변형

$\sum_a \pi_{\theta_{old}}(a|s)[...] = \sum_a \pi_{\theta_{old}}(a|s) \frac{q(a|s)}{q(a|s)} \\ = E_{s\sim q} [\frac{\pi_{\theta_{old}}(a,s)}{q(s|s)}[...]]$

(3) Advantage 는 $Q_{\theta_{old}}$ 로 치환

$A_\pi(s,a) = Q_\pi(s,a) - V_\pi(s)$ 이기 때문에, Advantage 를 Q 로 변경해도 상수항 만큼의 차이만 발생한다. 따라서, 단순히 치환하는것만으로 최적화 방향에 영향을 주지 않는다.

(1) , (2) , (3) 을 적용하면 $L_{\theta_{old}}$ 는 아래 식과 동치

$$\text{maximize}_\theta E_{s\sim \rho_{\theta_{old}}, a\sim q}[\frac{\pi_{\theta_{old}}(a,s)}{q(a|s)}Q_{\theta_{old}}(s,a)] \\ \text{subject to } D_{KL}(\pi_{\theta_{old}}( \cdot | s) || \pi_\theta ( \cdot | s)) \le \delta$$

이제, 기댓값과 Q-value function 을 바꿔주면 되는데 TRPO 에서는 여기서 2가지 방식으로 나뉜다.

• Single path
  • Policy Gradient Estimation 방식
• Vine
  • Policy Iteration 방식
  • state 에서 시뮬레이션을 통해 Trajectory 를 수집한 것을 Rollout set 이라고 한다.
  • rollout set 의 각 state 에서 여러 action 을 취해보는 방식

Single-path

single-path 의 동작 과정을 간략히 살펴보면 다음과 같다.

• $\rho_0$ 에서 initial state 를 샘플링 $s_0$
• $\pi_{old}$ 를 이용해서 $s_0$ 부터 시작하는 Trajectory 를 생성
  • $s_0, a_0, s_1, a_1, ..., a_{T-1}, s_T$
• $q(a|s)=\pi_{old}(a|s)$
• $Q_{\pi_{old}}(s,a)$ 를 위에서 수집된 $(s_t, a_t)$ pair 에 대해 discounted reward sum 진행
  • $Q(s_0, a_0)$ : 0시점 ~ T시점까지 받은 보상의 가중합
  • $Q(s_1, a_1)$ :1시점 ~ T시점까지 받은 보상의 가중합

Vine

Vine 의 동작 과정을 간략히 살펴보자.

• $\rho_0$ 에서 $s_0$ 샘플링
• $\pi_{\theta_i}$ 를 이용해서 복수개의 Trajectory 를 생성
• Trajectories 에서 N개의 state 를 선택
  • $s_0, s_1, ..., s_N$
• 각각의 state 에서 K개 action 을 선택
  • $a_{n,k} \sim q(\cdot | s_n)$
  • 이때, $q(\cdot|s_n)$ 의 support 가 $\pi_{\theta_i}(\cdot|s_n)$ 을 포함한다면, $q$ 는 일정한 estimator 를 제공한다고 볼 수 있다.
  • support : 확률이 0 이 아닌 입력값들의 집합
  • 목적함수의 importance weight 에서 샘플링 분포인 q 가 0 이 되면 함수가 터져버린다. 이를 방지하기 위한 안전장치 역할을 한다.
  • Continuous 한 action space 에서는 샘플링 분포를 기존 분포 그대로 사용했을때 good 이였고, Atari 게임같은 환경에서는 Uniform Distribution 을 사용했을때 good 이였다고 한다.
    • 위 안전장치 역할만 할 수 있으면 어떤 함수를 가져다 써도 괜찮다는 장점

$s_n$ 에서 파생된 $a_{(n,k)}$ 이 있을때, $Q$ 함수를 이용해 각 파생 Trajectory 를 평가하게 된다.

• $\hat{Q_{\theta_i}}(s_n, a_{(n,k)})$

RL 에서는 MDP 를 기반으로 Environment 를 정의하고, MDP 에서 Transient Probability $P(s_{t+1} | s_t, a_t)$ term 에 의해 다음 state 가 확률적으로 정해진다.

즉, 특정 state 에서 특정한 action 을 취한다고해도 그 다음 state 는 무작위성을 가지고 있다.

이때, 위 Vine 메소드는 $s_n$ 에서 파생된 $K$ 개의 action $a_{n,k}$ 을 $q$ 를 기반으로 뽑아낸다고 했고, 이때 전이확률에 의해, 그 다음 state 는 확률적으로 무작위성을 띄기 때문에 다양한 Trajectory 가 생성되게 된다.

여기서 각 여러 Trajectory 를 rollout set 이라고 부르고, 하나의 rollout set 에 대해 $Q$ 를 통해 Reward 를 계산하게 되는데, 이를 통해 특정한 state 에서 reward 가 높은 action 을 구할 수 있게 된다.

그런데, 여기에 Random Noise 에 의해서 Action 이 아닌 Noise (환경의 무작위성) 에 의해서 점수가 높게 나왔을 수도 있으니 이를 제한하기 위해서

CRN (common Random Number) 를 기반으로 해 난수 = Noise 를 생성하고, 같은 Rollout 에서 나온 K개 Action 에 대해서는 동일한 난수를 적용해 $Q-value$ 의 Variance 를 줄이게 된다.