Multistep Q-Learning (HW3)

Eony_Jahng·2024년 5월 27일
REINFORCEMENTcs285
0

CS285

목록 보기
4/4

다음은 UC Berkely online-course CS285의 Assignment3에 대한 내용입니다.

Assignment3

1. TD-Learning Bias

Q^\hat{Q}이 unbiased estimator라면, E[Q^]=QE[\hat{Q}] = Q이다.

따라서 Bellman Backup을 적용한 BQ^=r(s,a)+γmax⁡a′Q^(s′,a′)\mathcal{B}\hat{Q} = r(s, a) + \gamma \max_{a'} \hat{Q}(s', a')에서 max Q^\hat{Q} 역시 unbiased 하는지가 문제이다.

그러나 "Q^\hat{Q}이 noisy (but unbiased) estimate for Q"라고 했기 때문에, 다음 수식이 성립한다.

E[max⁡a′Q^(s′,a′)]≥max⁡a′(E[Q^(s′,a′)])=max⁡a′Q(s′,a′)E[\max_{a'} \hat{Q}(s', a')] \geq \max_{a'} (E[\hat{Q}(s', a')]) = \max_{a'} Q(s', a')

이는 Q^\hat{Q}가 각 s′s'와 a′a'에서 Q의 unbiased estimate라고 하더라도, max 연산을 취함으로써 동치가 아닐 수 있다는 가능성이 발생한다는 것을 의미한다. 즉, max 연산이 비선형적이기 때문에 발생하는 현상이다.

비선형 연산의 특성

max 연산은 비선형적이다. 이는 max⁡(X,Y)\max(X, Y)의 기대값이 항상 max⁡(E[X],E[Y])\max(\mathbb{E}[X], \mathbb{E}[Y])보다 크거나 같음을 의미한다. 이를 통해, 기대값과 최대값 연산의 순서를 바꿀 수 없음을 알 수 있다.

예를 들어, 두 개의 독립적인 확률 변수 XX와 YY가 있을 때,

E[max⁡(X,Y)]≥max⁡(E[X],E[Y])E[\max(X, Y)] \geq \max(E[X], E[Y])

이 성립한다. 이로 인해, E[max⁡a′Q^(s′,a′)]E[\max_{a'} \hat{Q}(s', a')]는 max⁡a′Q(s′,a′)\max_{a'} Q(s', a')보다 크거나 같게 된다.

Bellman Backup 연산의 영향

Bellman Backup 연산은 강화 학습에서 가치 함수 QQ를 업데이트하는 방법으로, 다음과 같이 정의된다.

BQ^=r(s,a)+γmax⁡a′Q^(s′,a′)\mathcal{B}\hat{Q} = r(s, a) + \gamma \max_{a'} \hat{Q}(s', a')

여기서 Q^\hat{Q}가 QQ의 unbiased estimate일 때, BQ^\mathcal{B}\hat{Q}가 BQ\mathcal{B}Q의 편향 없는 추정치가 되는지 확인해보자. r(s,a)r(s, a)는 return function이고, γ\gamma는 discount factor이다.

Q^\hat{Q}가 QQ의 unbiased estimate라면,

E[Q^(s′,a′)]=Q(s′,a′)E[\hat{Q}(s', a')] = Q(s', a')

이 성립한다. 그러나, max⁡\max 연산을 적용하면,

E[max⁡a′Q^(s′,a′)]≥max⁡a′(E[Q^(s′,a′)])=max⁡a′Q(s′,a′)E[\max_{a'} \hat{Q}(s', a')] \geq \max_{a'} (E[\hat{Q}(s', a')]) = \max_{a'} Q(s', a')

이 성립한다. 이는 max 연산이 비선형적이기 때문이다.

결론

max 연산의 비선형성 때문에 BQ^\mathcal{B}\hat{Q}는 BQ\mathcal{B}Q의 편향 없는 추정치가 될 수 없다. 따라서, BQ^\mathcal{B}\hat{Q}는 BQ\mathcal{B}Q의 unbiased estimate가 아니다. 그래서 정답은 < NO >

2. Tabular Learning

풀이

State I: Qϕk+1Q_{\phi_{k+1}}는 현재 정책 πk\pi_k의 Q 함수에 대해 unbiased estimate입니다.

  • 설명: On-policy 학습에서는 에이전트가 현재 학습 중인 정책 πk\pi_k에 따라 데이터를 수집합니다. 따라서 수집된 데이터는 현재 정책에 대한 Q 함수의 unbiased estimate를 제공합니다. 반면, off-policy 학습에서는 다른 정책 π′\pi'로부터 데이터를 수집하므로, 학습 중인 정책과 일치하지 않아 bias가 생길 수 있습니다.
  • 결론: On-policy는 항상 옳지만, off-policy는 다른 정책 π′\pi'로부터 데이터를 수집하므로 unbiased estimate가 아닐 수 있다.

State II:

  • 설명: k→∞k \rightarrow \infty일 때, 충분히 많은 반복 후에 모든 상태-행동 쌍 (s,a)(s, a)가 무한히 자주 방문됩니다. 이는 결국 모든 batch BB에 대해 충분한 데이터를 수집할 수 있음을 의미합니다.
  • 결론: 따라서 on-policy와 off-policy 모두에서 무한 반복 후에는 수렴이 보장됩니다. 즉, QϕkQ_{\phi_k}는 최적 Q 함수 Q∗Q^*에 대해 unbiased estimate가 됩니다.

State III:

  • 설명: 진술 II와 동일한 논리가 적용됩니다. 충분히 많은 반복 후, 모든 상태-행동 쌍이 충분히 자주 방문되므로 QϕkQ_{\phi_k}는 최적 Q 함수 Q∗Q^*에 수렴합니다.
  • 결론: 따라서 State II와 동일하게 on-policy와 off-policy 모두에서 무한 반복 후에는 수렴이 보장됩니다.

예시: N→∞N \rightarrow \infty일 때

Multi-step Q-learning에서 NN이 무한대로 갈 때의 상황을 고려해봅시다:

yj,t=∑t′=tt+N−1γt′−trj,t′+γNmax⁡a′Qϕk(sj,t+N,a′)y_{j,t} = \sum_{t'=t}^{t+N-1} \gamma^{t'-t} r_{j,t'} + \gamma^N \max_{a'} Q_{\phi_k}(s_{j,t+N}, a')

여기서 γ\gamma는 할인 요인으로, 0<γ<10 < \gamma < 1입니다. N→∞N \rightarrow \infty일 때, γN\gamma^N은 0에 수렴합니다:

γN→0asN→∞\gamma^N \rightarrow 0 \quad \text{as} \quad N \rightarrow \infty

따라서 bootstrapping 효과가 사라지게 됩니다. 이 경우 Multi-step Q-learning의 업데이트 식은 다음과 같이 단순화됩니다:

yj,t=∑t′=tt+∞γt′−trj,t′y_{j,t} = \sum_{t'=t}^{t+\infty} \gamma^{t'-t} r_{j,t'}

이 식은 Monte Carlo 방법과 유사합니다. Monte Carlo 방법에서는 미래의 모든 보상을 고려하여 현재의 Q 값을 업데이트합니다. 따라서 N→∞N \rightarrow \infty일 때는 bootstrapping을 사용하지 않고, 실제로 수집된 보상들만을 기반으로 Q 값을 업데이트하게 됩니다.

  • 결론: N→∞N \rightarrow \infty일 때는 모든 진술에 대해 성립되지 않습니다. 이는 Multi-step Q-learning이 더 이상 bootstrapping을 사용하지 않고, 순수한 Monte Carlo 방법으로 변환되기 때문입니다.

3. Variance of Q Estimate

N의 값이 갖는 의미

Q 값을 업데이트할 때, single step ((N = 1)) 대신 (N)개의 step 동안 누적된 보상을 사용하여 더 장기적인 정보를 반영하는 것입니다.

yj,t=∑t′=tt+N−1γt′−trj,t′+γNmax⁡a′Qϕk(sj,t+N,a′)y_{j,t} = \sum_{t'=t}^{t+N-1} \gamma^{t'-t} r_{j,t'} + \gamma^N \max_{a'} Q_{\phi_k}(s_{j,t+N}, a')
  • 첫 번째 항은 현재부터 (N) step 동안의 누적 보상 (return)입니다.
  • 두 번째 항은 (N) step 이후의 예측된 보상 (predicted return)입니다.

Bootstrapping and Variance

NN이 클수록 더 장기적인 보상을 고려하지만, 부트스트래핑의 정도가 낮아집니다. 부트스트래핑이란 현재의 추정치를 미래의 예측에 반영하는 기법으로, 일반적으로 업데이트 과정에서 노이즈를 축적시킬 수 있습니다. 따라서, N=1N = 1일 때 부트스트래핑의 효과가 가장 강하게 작용하여 분산이 가장 높아집니다.

Variance를 단순히 "미래 가능성의 크기"라고 생각하면, N=1N = 1일 때 가장 크고, N→∞N \rightarrow \infty일 때 가장 작습니다.N→∞N \rightarrow \infty인 경우, 부트스트래핑 효과가 완전히 사라지며, 이는 Monte Carlo 방법과 유사합니다. 이 경우 실제로 수집된 보상만을 사용하게 되므로, 분산이 가장 낮아집니다.

결론

따라서, (N = 1)일 때 Q 추정치의 분산이 가장 크고, (N \rightarrow \infty)일 때 Q 추정치의 분산이 가장 작습니다.

4. Function Approximation

풀이

State 1: N=1N = 1일 때, Qϕk+1Q_{\phi_{k+1}}는 마지막 정책 QπkQ^{\pi_k}의 Q 함수에 대한 unbiased estimate입니다.

N=1N = 1일 때는 1-step Q-learning이 됩니다. 즉, 부트스트래핑이 가장 강하게 적용되기 때문에 함수 근사는 bias를 가지게 됩니다. 함수 근사는 정확한 Q 함수 값을 나타내지 못하고 편향된 추정치를 제공합니다. 따라서 이 state는 일반적으로 옳지 않습니다.

State 2: N=1N = 1일 때 B→∞B \rightarrow \infty이고, k→∞k \rightarrow \infty인 경우, QϕkQ_{\phi_k}는 Q∗Q^*에 수렴합니다.

데이터셋 크기 BB와 반복 횟수 kk가 무한대로 가면, 충분한 데이터와 학습 과정을 통해 함수 근사는 최적 Q 함수 Q∗Q^*에 수렴할 수 있습니다. 이는 함수 근사가 충분한 데이터를 사용하여 점차 정확한 Q 함수 값을 학습할 수 있음을 의미합니다. 따라서 이 state는 옳습니다.

State 3: N>1N > 1 (유한)일 때 B→∞B \rightarrow \infty이고, k→∞k \rightarrow \infty인 경우, QϕkQ_{\phi_k}는 Q∗Q^*에 수렴합니다.

다중 스텝 (N-step) 방법도 마찬가지로, 충분한 데이터와 반복 횟수가 주어지면 함수 근사는 최적 Q 함수 Q∗Q^*에 수렴할 수 있습니다. 다중 스텝 방법은 더 많은 장기적인 보상을 고려하므로 수렴 속도가 더 빠를 수 있습니다. 따라서 이 state도 옳습니다.

State 4: N→∞N \rightarrow \infty일 때 B→∞B \rightarrow \infty이고, k→∞k \rightarrow \infty인 경우, QϕkQ_{\phi_k}는 Q∗Q^*에 수렴합니다.

NN이 무한대로 갈 때 Monte Carlo 방법과 유사하게 작동하며, 충분한 데이터와 반복 횟수가 주어지면 함수 근사는 최적 Q 함수 Q∗Q^*에 수렴할 수 있습니다. Monte Carlo 방법은 모든 보상을 직접 사용하는 방식이므로 편향이 없는 추정치를 제공합니다. 따라서 이 state도 옳습니다.

5. Multistep Importance Sampling

ϕk+1←arg⁡min⁡ϕ∈Φ∑j,t(yj,t−Qϕ(sj,t,aj,t))2... (2)\phi_{k+1} \leftarrow \arg \min_{\phi \in \Phi} \sum_{j,t} (y_{j,t} - Q_\phi(s_{j,t}, a_{j,t}))^2 \quad \text{... (2)}

Importance sampling ratio

Importance sampling ratio:

∏t′=tt+N−1π(at′∣st′)π′(at′∣st′)\prod_{t'=t}^{t+N-1} \frac{\pi(a_{t'} \mid s_{t'})}{\pi'(a_{t'} \mid s_{t'})}

이므로 target value는 다음과 같습니다.

yj,t=∑t′=tt+N−1(∏t^=tt′π(at^∣st^)π′(at^∣st^))γt′−trj,t′+(∏t^=tt+N−1π(at^∣st^)π′(at^∣st^))γNmax⁡aQϕk(sj,t+N,aj,t+N)y_{j,t} = \sum_{t'=t}^{t+N-1} \left( \prod_{\hat{t}=t}^{t'} \frac{\pi(a_{\hat{t}} \mid s_{\hat{t}})}{\pi'(a_{\hat{t}} \mid s_{\hat{t}})} \right) \gamma^{t'-t} r_{j,t'} + \left( \prod_{\hat{t}=t}^{t+N-1} \frac{\pi(a_{\hat{t}} \mid s_{\hat{t}})}{\pi'(a_{\hat{t}} \mid s_{\hat{t}})} \right) \gamma^N \max_a Q_{\phi_k}(s_{j,t+N}, a_{j,t+N})

N=1N = 1일 때

yj,t=π(at∣st)π′(at∣st)⋅rj,t+π(at+1∣st+1)π′(at+1∣st+1)⋅γmax⁡aQϕk(sj,t+1,aj,t+1)y_{j,t} = \frac{\pi(a_t \mid s_t)}{\pi'(a_t \mid s_t)} \cdot r_{j,t} + \frac{\pi(a_{t+1} \mid s_{t+1})}{\pi'(a_{t+1} \mid s_{t+1})} \cdot \gamma \max_a Q_{\phi_k}(s_{j,t+1}, a_{j,t+1})

N→∞N \rightarrow \infty일 때

yj,t=∑t′=t∞(∏t^=tt′π(at^∣st^)π′(at^∣st^))γt′−trj,t′y_{j,t} = \sum_{t'=t}^{\infty} \left( \prod_{\hat{t}=t}^{t'} \frac{\pi(a_{\hat{t}} \mid s_{\hat{t}})}{\pi'(a_{\hat{t}} \mid s_{\hat{t}})} \right) \gamma^{t'-t} r_{j,t'}

Importance sampling을 적용한 식 (2)

위의 yj,ty_{j,t}를 식 (2)에 대입하면, 중요도 샘플링을 적용한 식은 다음과 같습니다:

ϕk+1←arg min⁡ϕ∈Φ∑j,t(∑t′=tt+N−1(∏t^=tt′π(at^∣st^)π′(at^∣st^))γt′−trj,t′+(∏t^=tt+N−1π(at^∣st^)π′(at^∣st^))γNmax⁡aQϕk(sj,t+N,aj,t+N)−Qϕ(sj,t,aj,t))2\phi_{k+1} \leftarrow \argmin_{\phi \in \Phi} \sum_{j,t} \left( \sum_{t'=t}^{t+N-1} \left( \prod_{\hat{t}=t}^{t'} \frac{\pi(a_{\hat{t}} \mid s_{\hat{t}})}{\pi'(a_{\hat{t}} \mid s_{\hat{t}})} \right) \gamma^{t'-t} r_{j,t'} + \left( \prod_{\hat{t}=t}^{t+N-1} \frac{\pi(a_{\hat{t}} \mid s_{\hat{t}})}{\pi'(a_{\hat{t}} \mid s_{\hat{t}})} \right) \gamma^N \max_a Q_{\phi_k}(s_{j,t+N}, a_{j,t+N}) - Q_\phi(s_{j,t}, a_{j,t}) \right)^2

따라서, 중요도 샘플링을 적용한 식을 얻을 수 있습니다.

profile
Eony_Jahng
7층에 사는 동언이
이전 포스트

Policy Gradients_Generalized Advantage Estimation _[CS285_HW2]

0개의 댓글