강화 학습 중간 정리 4 - MC, 벨만 방정식, planning, 최적 정책 찾기, value 평가

순차적 의사 결정 문제 해결 방식 - 시간 순서대로 주어진 상황에서 목적을 이루기 위해 행동을 하는 것의 반복

마르코프 성질 - 미래 (t+1)은 오로지 현재(t)에 의해 결정된다.

마르코프 리워드 프로세스 - 마르코프 프로세스 + 보상
리턴(G, 에피소드가 끝날 때 까지 보상의 합)의 최대화
v - s에서 시작하여 G의 기대값 측정
상태 가치 함수v - s의 v 알기 - s에서 G 기댓값

마르코프 결정 프로세스 - MRP + action
상태 가치 함수 v - 정책(a를 정해준다)에 따라 G가 달라진다.
액젼 가치 함수 q - s에서 a에 대한 평가

벨만 방정식 - 위의 v와 q를 식으로 작성한것

벨만 기대 방정식 - v와 q를 구하는 법
v(s) = E(G) = E(R + v(s)) - s가 다른 시점임을 유의해야 한다.
q를 이용해 v 계산하기 - v는 현 상태의 G의 기대값이므로 모든 a에 대한 q를 구하면 된다.
v를 이용해 q 계산하기 - s에서 a를 한게 q니까 a 한 것에 대한 보상을 더해주고, s에서 a를 실행하면 갈 수 있는 모든 경우의 수의 s의 v를 전이 확률, 감쇠 인자와 곱해서 더해주면 된다.
위 식을 활용하면 v로 v를 구할 수 있고, q로 q를 구할 수 있다.

벨만 최적 방정식 - 최대값과 v, q를 이용해 좋은 액션 선택
q로 v 구하기 - v*(s) = max q*(s,a)이다.
v로 q 구하기 - 보상을 더하고, a를 했을 때 갈 수 있는 모든 s의 v 합

반복적 정책 평가 - 벨만 기대 방정식을 통해 s에 대한 v 반복 계산 가능

벨류 이터레이션 - 벨만 최적 장정식을 통해 v* 계산 가능

몬테카를로 학습 알고리즘 - 에피소드가 끝날 때 까지 진행 후 v를 작성하고, 지나간 곳의 N도 1씩 늘린다.

TD - s가 변할 때 마다 그 다음 환경의 v값을 통해 v를 업데이트 한다.

편향성 - 잘 못된 길로 빠질 수 있냐 -> TD가 크다.
분산 - 변동성이 큰다 -> MC가 크다.

강화학습에서 n-step return과 TD(λ) (Temporal Difference Lambda)는 서로 다른 방법으로 가치 함수를 업데이트하며, 강화학습 알고리즘의 효율성과 효과성을 향상시키는 데 사용됩니다.

N-step Return

n-step return은 한 시점에서 행동을 취한 후 n개의 시간 스텝이 지난 후의 보상을 기반으로 가치 함수를 업데이트하는 방법입니다. 이 방법은 단일 보상(1-step TD) 뿐만 아니라 더 긴 시간 동안의 보상을 함께 고려합니다. n-step return을 사용하면 더 안정적이고 정보적인 업데이트가 가능하지만, 적절한 n의 값을 선택하는 것이 중요합니다.

n-step TD target의 계산은 다음과 같습니다:
[ G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n}) ]
여기서 ( G_t^{(n)} )은 t 시점에서 n-step 후의 반환값이고, ( R_{t+k} )는 t+k 시점에서 받은 보상, ( \gamma )는 감가율(discount factor), ( V(S_{t+n}) )은 t+n 시점의 상태 가치 추정입니다.

TD(λ)

TD(λ)는 n-step return을 일반화한 방식으로, 여러 n-step returns의 가중 평균을 사용합니다. λ는 0과 1 사이의 값으로, 반환값에서 각각의 n-step return에 얼마나 중점을 두어야 하는지를 결정하는 매개변수입니다. TD(λ)는 λ가 0일 때는 일반적인 TD(0) (1-step TD)와 같고, λ가 1일 때는 무한한 horizon으로의 Monte Carlo 방식과 유사합니다.

TD(λ)의 가치 함수 업데이트는 eligibility traces라는 개념을 사용하여 수행됩니다. eligibility trace는 각 상태가 최근 방문된 빈도와 중요성을 추적합니다. trace는 각 스텝마다 감소하며, 새로운 상태를 방문할 때마다 증가합니다.

TD(λ)의 핵심 아이디어는 반환값을 계산할 때 다음과 같은 가중치를 적용하는 것입니다:
[ G_t^\lambda = (1-\lambda) \sum_{n=1}^\infty \lambda^{n-1} G_t^{(n)} ]
여기서 ( G_t^\lambda )는 t 시점에서의 λ-return입니다.

TD(λ) 업데이트 규칙은 다음과 같습니다:
[ V(S_t) \leftarrow V(S_t) + \alpha \delta_t E_t ]
여기서 ( \alpha )는 학습률, ( \delta_t )는 시간차 오차(time difference error), ( E_t )는 t 시점에서의 eligibility trace입니다.

요약

• n-step return: 보다 긴 시간 동안의 보상을 반영하여 가치 함수를 업데이트합니다.
• TD(λ): 여러 n-step returns의 가중 평균을 이용하여 가치 함수를 업데이트하며, 모든 길이의 에피소드에 대한 통합적인 정보를 반영합니다. 이 방법은 좀 더 일반적이고 유연하며, 다양한 타임스케일의 정보를 효율적으로 통합할 수 있습니다.

강화학습에서는 다양한 방법을 사용하여 에이전트가 환경으로부터 학습할 수 있도록 합니다. TD(Temporal Difference), MC(Monte Carlo), TD(λ), 그리고 n-step return은 이러한 방법 중 몇 가지입니다. 각각의 기법은 환경으로부터 정보를 수집하고 이를 이용해 가치 함수를 업데이트하는 방식에서 차이가 있습니다.

1. Monte Carlo (MC)

• 특징: 에피소드가 완전히 끝나야 가치 함수를 업데이트할 수 있습니다. 즉, 에피소드의 결과(반환값)를 통째로 관찰한 후에 가치 추정을 업데이트합니다.
• 장점: 반환값에 기반한 정확한 추정이 가능합니다.
• 단점: 각 에피소드가 끝날 때까지 기다려야 하므로, 특히 에피소드 길이가 길거나 끝이 정의되지 않는 태스크에서는 비효율적일 수 있습니다.

2. Temporal Difference (TD)

• 특징: 실시간으로, 즉 에피소드가 진행되는 동안에 가치 함수를 업데이트합니다. TD(0), 즉 1-step TD는 다음 상태의 가치 추정과 즉시 받은 보상을 사용하여 현재 상태의 가치를 업데이트합니다.
• 장점: 에피소드가 완료되기를 기다리지 않고, 부분적으로 결과를 관찰하며 학습할 수 있습니다.
• 단점: 추정이 부분적 정보에 기반하기 때문에 때때로 불안정하거나 부정확할 수 있습니다.

3. TD(λ) (Temporal Difference Lambda)

• 특징: TD와 Monte Carlo의 중간 형태로, 여러 길이의 n-step returns을 ( \lambda ) 매개변수로 가중 평균하여 사용합니다. ( \lambda )의 값에 따라 더 많이 Monte Carlo 스타일이거나 TD 스타일에 가깝습니다.
• 장점: 단일 TD보다 안정성이 높으며, Monte Carlo의 정확성과 TD의 신속성을 일정 부분 결합합니다.
• 단점: eligibility traces와 같은 추가적인 메커니즘을 관리해야 하므로 구현이 복잡할 수 있습니다.

4. n-step Return

• 특징: n-step TD는 1-step TD의 일반화 형태로, n개의 보상을 더하고 n+1번째 상태의 가치 추정을 사용합니다.
• 장점: 보상과 상태 변화의 중간 범위를 통합하여 가치 추정을 할 수 있으므로, 1-step TD보다 정보를 더 잘 활용할 수 있습니다.
• 단점: 적절한 n 값을 선택하는 것이 중요하며, n이 크면 큰 만큼 더 많은 정보를 필요로 합니다.

요약

• MC: 에피소드 완료 후 가치 업데이트.
• TD: 단계별 가치 업데이트.
• TD(λ): 여러 n-step returns의 가중 평균을 사용.
• n-step TD: n 스텝 후의 반환값으로 가치 업데이트.

각 방법은 특정 시나리오와 문제 유형에 따라 장단점이 있으므로, 목표하는 학습 성능과 환경 특성에 맞게 적절한 방법을 선택하는 것이 중요합니다.

MDP를 모르면 P를 모르기 때문에 벨만 기대 방정식을 사용하는 정책 이터레이션을 사용할 수 없다.

MC를 통해 경험적으로 v를 구하고, q를 사용하여 입실론 그리디를 사용한다.

TD - SARSA
on policy를 통해 정책에 대한 q 구하기

Q learning - 벨만 최적 방정식 == q*가 되는 a를 취한다.