*본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성하였습니다.
<Monte-Carlo Prediction_02>
|질문|
"MDP 모델을 알고 있는 경우에는 동적 프로그래밍 방식으로 정확한 값을 계산할 수 있지만, 모델을 모르는 경우에는 샘플링을 통해 값을 추정하는데 이럴 때는 어떻게 해야할까?"
1. Monte-Carlo Prediction의 Value Function 계산
- 여기서 Returns(s)는 상태 s에서의 샘플 반환값(return)들의 리스트이며, gt는 시간 t부터 에피소드 끝까지의 할인된 보상 합계.
- 이 식은 시간 t에서의 리턴 값을 계산한다. 현재 시점 t부터 에피소드 종료 시점 T까지의 모든 보상에 감가율(discount factor) γ를 적용하여 합산한 값이다.
- Monte-Carlo 방법은 실제 환경에서 여러 에피소드를 생성하고, 각 상태에서의 반환값을 평균내어 Vπ(s)를 추정한다. 이 과정은 MDP 모델을 알 필요 없이 경험만으로 학습할 수 있지만, policy가 방문하지 않는 상태는 평가할 수 없다는 한계가 있다.
-> 알고리즘 계산순서
- 정책 π를 입력으로 받는다.
- 모든 상태 s에 대해 V(s)와 Returns(s) 리스트를 초기화한다.
- 정책 π를 사용해 에피소드를 생성한다.
- 각 시간 단계 t에서 리턴 g_t를 계산한다.
- 계산된 리턴을 Returns(s_t)에 추가한다.
- V(s_t)를 Returns(s_t)의 평균으로 갱신한다.
2. Action-Value Function (Qπ(s,a))
- 여기서 Gt는 할인된 누적 보상이다.
- Value function 대신 action-value function을 추정하면, MDP 모델 없이도 최적 정책을 직접 도출할 수 있다. Qπ(s,a)는 상태 s에서 행동 a를 선택했을 때의 기대 반환값을 나타낸다.
3. Argmax Policy Improvement
- 현재 Qπk(s,a)를 기반으로 각 상태에서 가장 높은 값을 주는 행동을 선택하는 탐욕적(greedy) 정책을 생성한다. 이는 정책을 명시적으로 개선하는 방법이며, DP와 달리 MDP 모델이 필요하지 않다.
- 이 수식은 상태-행동 가치 함수로, 특정 상태 s에서 행동 a를 취한 후 정책 π를 따랐을 때의 기대 보상을 정의한다.
- 상태 s에서 행동 a를 취한 후 얻게 될 총 보상의 기대값을 의미한다.
- Q-함수는 상태 s에서 행동 a를 선택한 후, 환경의 전이 확률 p(s′∣s,a)과 다음 상태 s′의 가치 Vπ(s′)를 기반으로 계산됩니다.
- 모델 기반(Model-Based) 접근: 환경의 MDP 모델(전이 확률, 보상 함수)을 알고 있을 때 사용 가능.
- γ: 할인 계수(Discount Factor).
문제점과 보완 방법
몬테카를로 예측의 주요 문제점들은:
- 정책이 방문하지 않는 상태에 대해서는 가치 함수를 추정할 수 없음
- 몬테카를로 방법은 실제 환경에서 에피소드를 수행하여 경험하는 상태에 대해서만 가치를 추정한다.
- 보완: 탐색(Exploration)이 중요하다고 강조되어 있으며, 이를 통해 다양한 상태를 방문할 필요가 있다.
- 가치 함수를 계산해도 정책 개선이 어려움
- 가치 함수만으로는 최적 행동을 직접 결정하기 어렵다.
- 보완: argmax 정책 개선 시 행동-가치(action-value) 함수가 필요하다.
- MDP 모델의 부재
- 몬테카를로 방법은 기존에는 환경의 MDP 모델을 통해 가치 함수에서 행동-가치를 계산했지만, 이제는 MDP 모델을 모른다.
- 보완: 가치 함수 대신 직접 행동-가치 함수(Q-함수)를 추정하면 된다.
몬테카를로 정책 반복(Monte Carlo Policy Iteration)을 통한 해결
- 정책 개선의 문제:
- 수식 π_{k+1}(a|s) = { 1 if a = argmax_a Q^{π_k}(s,a), 0 else }는 현재 정책 π_k의 Q-함수를 기반으로 각 상태에서 최적의 행동만 선택하도록 정책을 결정적(deterministic)으로 개선하는 방법을 보여준다.
- 이는 "현재 Q^π_k(s,a)를 기반으로 각 상태에서 가장 높은 값을 주는 행동을 선택하는 탐욕적(greedy) 정책을 생성"한다.
- Q-함수 계산 문제:
- 수식 Q^π(s,a) = ∑_{s'} p(s'|s,a)[r + γV^π(s')]와 세 번째 수식 Q^π(s,a) = E[r + γV^π(s')|s,a]는 Q-함수를 계산하는 방법을 보여준다.
- 이는 "상태-행동 가치 함수로, 특정 상태 s에서 행동 a를 취한 후 정책 π를 따랐을 때의 기대 보상"을 정의한다.
MDP 모델 기반 vs 모델 프리 강화학습 프로세스 비교
0. MDP(Markov Decision Process) 정의
MDP는 다음과 같은 5가지 요소로 정의됩니다:
- S: 상태 집합 (가능한 모든 상태)
- A: 행동 집합 (가능한 모든 행동)
- P(s'|s,a): 상태 전이 확률 (상태 s에서 행동 a를 취했을 때 상태 s'로 전이될 확률)
- R(s,a,s'): 보상 함수 (상태 s에서 행동 a를 취하고 상태 s'로 전이될 때 받는 보상)
- γ: 감가율 (미래 보상의 중요성을 조절하는 계수, 0≤γ≤1)
1. MDP 모델 기반 (Model-Based) 프로세스
이 프로세스는 환경의 동작 방식(상태 전이 확률과 보상 함수)을 알고 있을 때 사용합니다.
정책 반복(Policy Iteration) 과정:
- 초기화: 초기 정책 π₀을 무작위로 초기화
- 정책 평가: MDP 모델을 사용하여 현재 정책 π₀의 가치 함수 계산
또는 Q-함수 계산:
- 정책 개선: 계산된 Q-함수를 기반으로 더 나은 정책 생성
- 정책 평가: MDP 모델을 사용하여 새 정책 π₁의 가치 함수 계산
- 정책 개선: 새로운 Q-함수를 기반으로 더 나은 정책 생성
- 정책이 더 이상 개선되지 않을 때까지 4-5 반복
특징:
- 벨만 방정식을 직접 계산하기 위해 MDP 모델(P와 R)을 알아야 함
- 계산이 정확하고 효율적이지만 모델을 알아야 하는 제약이 있음
- 복잡한 환경에서는 모델을 정확히 알기 어려움
2. MDP 모델 프리 (Model-Free) 프로세스
이 프로세스는 환경의 동작 방식을 모르지만, 환경과의 상호작용을 통해 학습합니다.
몬테카를로 정책 반복(Monte Carlo Policy Iteration) 과정:
초기화: 초기 정책 π₀을 무작위로 초기화, Q-함수를 임의의 값으로 초기화
정책 평가: 실제 환경에서 에피소드를 경험하고 샘플 리턴으로 Q-함수 추정
정책 개선: 추정된 Q-함수를 기반으로 더 나은 정책 생성
정책 평가: 새 정책 π₁으로 에피소드를 생성하고 Q-함수 추정
정책 개선: 새로운 Q-함수를 기반으로 더 나은 정책 생성
정책이 더 이상 개선되지 않을 때까지 4-5 반복
특징:
- MDP 모델(P와 R)을 몰라도 학습 가능
- 실제 경험을 통해 가치 함수를 추정
- 샘플링 기반이라 추정에 노이즈가 있을 수 있음
- 복잡한 환경에서도 적용 가능
두 프로세스의 핵심 차이점
- 정보 요구사항:
- 모델 기반: MDP 모델(P와 R)을 알아야 함
- 모델 프리: MDP 모델을 몰라도 됨
- 계산 방식:
- 모델 기반: 정확한 기대값 계산
- 모델 프리: 샘플링을 통한 추정
- 연산 효율성:
- 모델 기반: 상태 공간이 작을 때 효율적
- 모델 프리: 복잡한 환경에서 더 실용적
- 학습 방식:
- 모델 기반: 계획(planning) 기반
- 모델 프리: 시행착오(trial and error) 기반
|인증|
-------
패스트캠퍼스 링크