MDP를 알 때의 플래닝

강화 학습 스터디) 바닥부터 배우는 강화학습을 읽고 정리하였습니다.

 

chat GPT로 만든 썸네일. 스펠링 왜 자꾸 틀리지

Chapter 4는 간단한 MDP(상태나 액션의 개수가 많지 않은)를 푸는 법에 대한 내용임

내용은 주로 테이블 기반 방법론(tabular method)에 기반하는데, 이는 모든 상태 s 혹은 상태와 액션의 페어(s,a)에 대한 테이블을 만들어서 값을 기록해 놓고, 그 값을 조금씩 업데이트 하는 방식을 의미

밸류 평가하기 - 반복적 정책 평가[정책이 고정인 상황]

이 문제를 해결하기 위해서는 반복적 정책 평가(iterative policy evaluation)라는 방법론을 도입

→ 이 방법론은 MDP에 대한 모든 정보를 알 때 사용할 수 있음

문제 상황

• 정책 함수 $\pi$는 4 방향 랜덤
• 보상 함수 $r^a_{s}$는 -1로 고정, 전이 확률은 액션이 정해질 때 100%
• MDP를 모두 아는 상태임

1 단계: 테이블 초기화

테이블의 각 그리드에는 상태별 밸류 $v(s)$를 기록한다.

이때 각 그리드의 값을 일단 0으로 초기화!!

→ 어떤 값으로 초기화해도 상관은 없지만, 실제 정답과 멀수록 업데이트 횟수가 더 많이 필요함(딥러닝 모델의 weight, bias 와 마찬가지)

지금은 아무 의미가 없는 값이지만 반복적 과정을 거치면서 점차 실제 각 상태의 가치에 해당하는 값으로 수렴해 갈 것임

2 단계: 한 상태의 값을 업데이트

4-3 처럼 파란색으로 칠해진 상태 $s_{5}$를 업데이트 한다고 생각해보면, MDP를 다 알기 떄문에 이상태의 다음 상태가 어디가 될지 그 후보를 알 수 있음(아래의 수식을 이용)

$v_{\pi}(s) = \sum_{a \in A} \pi(a|s)(r^a_{s} + \gamma \sum_{s’ \in S} P^a_{ss’}v_{\pi}(s’))$

• 일단 어떤 state 든 선택할 수 있는 액션에 대해 4방향으로 균등하기 때문에 $\pi(a|s)$ = 0.25
• 보상은 어느 액션을 하든 -1이므로 $r^a_{s}$의 값 또한 항상 -1
• $\gamma$는 -1로 계산
• 전이 확률은 항상 1 (액션에 따라 100% 정해짐)

따라서 다음과 같이 간단하게 계산할 수 있음

$v_{\pi}(s)$ = 0.25 * (-1 + 0.0) + 0.25 * (-1 + 0.0) + 0.25 * (-1 + 0.0) + 0.25 * (-1 + 0.0) = -1

3 단계: 모든 상태에 대해 2단계의 과정을 적용

종료 상태의 가치가 0으로 초기화 → 맨 마지막 상태의 입장에서는 뒤의 미래라는 것이 존재하지 않기 때문에 정확한 값임

질문: 만약에 초기화를 0으로 하지 않으면, 종료 state의 가치는 어떻게 0으로 바뀌나요?

→ 어떻게 설정하든 상관이 없다.

4 단계: 앞의 과정을 계속해서 반복

• 이 과정을 계속 반복하면 각 상태의 값이 어떤 값에 수렴하게 됨
• 그 값이 바로 해당 상태의 실제 밸류
• 그리드를 통해 해석
  • S1 에서는 대략 60번 랜덤하게 움직여야 종료 상태에 도달한다.
  • S11의 경우 대략 30번 랜덤하게 움직여야 종료 상태에 도달한다.
  • → 정책 $\pi$가 랜덤하게 액션을 선택하기 때문에

 

최고의 정책 찾기 - 정책 이터레이션[최적 정책을 찾는 상황]

정책 이터레이션은 기본적으로 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때 까지 반복하는 방법론임

• 반복적 정책 평가를 통해 모든 상태의 가치를 계산해 놓은 상황에서 S5에 있을 때, 가치 값을 보고 해당 상태에서 어디로 가는 것이 더 좋은지 알 수 있음
• 위 그림에서는 S5 에서 오른쪽 혹은 아래쪽으로 이동하는 것이 더 좋은 액션일 것임
• 따라서 다음과 같은 정책 $\pi’$을 생각해 볼 수 있음
  • $\pi’(a_{east}|s_{5}) = 1.0 or \pi’(a_{south}|s_{5}) = 1.0$
  이렇게 만들어진 $\pi’$은 원래의 정책 보다는 나은 정책임
• → 그리디 정책

모든 상태에 대해 그리디 정책을 표시한 결과는 다음과 같음

(이 그리디 정책은 최적 정책과 동일함)→ 예시가 너무 간단해서 그럼

아무튼 중요한 부분은 $\pi’$이 $\pi$에 비해 개선되었다는 점

정책 이터레이션은 위 그림과 같이 총 2 단계로 이루어져 있음

1. 정책 평가: 반복적 정책 평가(반복적 정책 평가 방법론 사용)
2. 정책 개선: 그리디 정책 생성

이 과정을 계속 반복하면 어느 순간 정책도 변하지 않고, 그에 따른 가치도 변하지 않는 단계에 도달하게 됨 → 최적 정책(optimal policy), 최적 가치(optimal value)

문제점 1. 이터레이션 내 계산량이 가장 많은 부분은 정책을 평가하는 과정

→ early stopping으로 해결할 수 있음

우리는 지금 최고의 정책을 찾는 것이 목적이지 정확한 가치를 평가하고자 하는 것이 아님

게다가, 가치 함수가 오로지 그리디 정책을 찾는 데에만 쓰일 뿐 테이블에 적혀질 구체적 값을 필요로 하지는 않음

→ 조금만 반복해서 정책을 평가하고, 기존 밸류와 조금이라도 값이 다르다면 → “개선”할 수 있고, 이전의 테이블은 버릴 수 있음 ! (Memory 절약)

 

최고의 정책 찾기 - 밸류 이터레이션[최적 정책을 찾는 상황]

정책 이터레이션은 단계마다 서로 다른 정책의 가치를 평가했음

개선 단계를 지날 때마다 새로운 정책이 튀어나오고, 평가 단계에선 방금 만들어진 새로운 정책의 밸류를 평가했기 때문

이번엔 이미 최적의 가치 테이블이 있다고 가정하고 최적 밸류만으로 최적 정책을 찾을 것임

임의로 초기화 된 값이지만 업데이트를 진행함에 따라 점차 실제 최적 밸류의 값으로 수렴해 감

(처음에는 최적 밸류를 알 수 없으니 일단 0으로 초기화)

주의할 점: 주어진 정책이 따로 없음 !

아래의 식으로 각 state에서의 최적 밸류를 계산

$v_{}(s) = max_{a} [r^a_{s} + \gamma\sum_{s’ \in S} P^a_{ss’} v_{}(s’)]$

이미 최적의 정책이 있다고 가정이 된 상황, 즉 모든 액션에 대해 max 값을 반환 하는 액션을 선택하고, 그 때의 가치를 계산

이렇게 해도 최적의 정책을 찾을 수 있는 이유

• MDP를 모두 아는 상황에서는 일단 최적 밸류를 알면 최적 정책을 곧바로 얻을 수 있기 때문
• 에이전트 입장에서 현재 상태에서 갈 수 있는 다음 상태가 무엇인지 모두 알고 있고, 이에 따라 가능한 액션 중 밸류를 최대화할 수 있는 액션만 선택하면 됨 → 곧 최적 정책

질문: MDP를 모두 아는 상황에서, 최적 정책을 찾기 위해 밸류 이터레이션을 쓰는 상황과 정책 이터레이션을 쓰는 상황을 선택해야할 때 → 무엇을 기준으로?

• 전이 확률이 stochastic일 경우 비교가 가능할 듯
• 보상 함수도 고정인 쉬운 문제여서 비교하기 어려움

 

참고 문헌

바닥부터 배우는 강화 학습 - 노승은