RL 최적 정책 찾는 법: Value Iteration vs. Policy Iteration 완전 분석!

정책 반복 알고리즘 (Policy Iteration) 쉽게 알아보기

이 알고리즘은 최고의 정책을 찾기 위한 방법이야. 마치 게임에서 이기기 위한 최적의 전략을 찾는 것과 같다고 생각하면 돼.

정책 반복 알고리즘이란?

1. 시작: 처음에는 아무 정책(π₀)이나 정해. 이게 좋은 정책일 수도 있고 아닐 수도 있어.

2. 반복: 이 정책을 계속해서 더 좋게 만들어나가. 이 과정은 두 단계로 나뉘어.

   • 정책 평가 (Policy Evaluation, PE): 지금 가지고 있는 정책(πk)이 얼마나 좋은지 평가하는 거야. 마치 게임에서 현재 전략으로 얼마나 점수를 얻을 수 있는지 계산하는 거지. 이걸로 각 상태(state)의 가치(value)를 알아내.
   • 정책 개선 (Policy Improvement): 평가한 결과를 바탕으로 더 좋은 정책(πk+1)을 만드는 거야. 마치 현재 전략보다 더 나은 수를 찾는 거지.

이 과정을 계속 반복하면 결국 가장 좋은 정책을 찾을 수 있어.

왜 이렇게 할까?

• 정책 평가: 현재 정책으로 각 상태에서 얻을 수 있는 기대값을 계산하는 거야. 이걸로 현재 정책의 성능을 알 수 있지.
• 정책 개선: 평가 결과를 보고, 각 상태에서 가장 기대값이 높은 행동을 선택해서 새로운 정책을 만들어. 이렇게 하면 이전 정책보다 무조건 좋아지거나 같아져.
• 최적 정책 찾기: 정책을 계속 개선하다 보면 언젠가는 더 이상 개선되지 않는, 즉 가장 좋은 정책에 도달하게 돼.

알고리즘 어떻게 작동해? (구현 방법)

1. 정책 평가 (PE):

   • 주어진 정책(πk)에 대해 각 상태의 가치(vπk)를 계산해야 해.
   • 이건 벨만 방정식이라는 걸 풀어서 할 수 있어.
   • 두 가지 방법이 있는데, 하나는 바로 계산하는 거고 (닫힌 형태 해법), 다른 하나는 여러 번 반복해서 계산하는 거야 (반복 해법). 보통은 반복해서 계산하는 방법을 많이 써.
   • 중요한 건, 정책 평가는 또 다른 반복 알고리즘 안에 포함된 반복 알고리즘이라는 거야. 즉, 큰 반복 안에 작은 반복이 있는 거지.

2. 정책 개선:

   • 정책 평가로 얻은 각 상태의 가치(vπk)를 이용해.
   • 각 상태에서 할 수 있는 모든 행동 중에서, 했을 때 가장 높은 가치를 얻을 수 있는 행동을 선택해서 새로운 정책(πk+1)을 만들어.
   • 이걸 수학적으로 표현하면, 각 상태에서 'q값'이 가장 높은 행동을 선택하는 거야. q값은 특정 상태에서 특정 행동을 했을 때 얻을 수 있는 기대값이야.

요약하면:

• 반복 1회:
  • 정책 평가: 현재 정책으로 각 상태의 가치를 계산해. (반복 계산)
  • 정책 개선: 계산된 가치를 바탕으로 더 좋은 행동을 선택해서 새로운 정책을 만들어.
• 이걸 계속 반복하면 돼.

궁금증 해결!

1. 정책 평가에서 상태 가치는 어떻게 구해?
   • 벨만 방정식을 풀어서 구해. 닫힌 형태 해법이나 반복 해법을 쓸 수 있어.
2. 새로운 정책(πk+1)이 왜 더 좋아?
   • 정책 개선 단계에서 각 상태에서 가장 기대값이 높은 행동을 선택하기 때문에, 이전 정책(πk)보다 무조건 좋거나 같아져.
3. 왜 반복하면 최적 정책을 찾을 수 있어?
   • 정책이 계속 개선되기 때문에 언젠가는 더 이상 좋아지지 않는 상태, 즉 최적 정책에 도달하게 돼. 수학적으로도 이게 증명되어 있어.
4. 가치 반복 알고리즘이랑 뭐가 달라?
   • 정책 반복 알고리즘은 정책을 먼저 개선하고 평가하는 반면, 가치 반복 알고리즘은 가치를 먼저 업데이트하고 정책을 나중에 결정해. 둘 다 최적 정책을 찾지만, 접근 방식이 조금 달라. 사실 둘 다 더 일반적인 알고리즘의 특별한 경우라고 볼 수도 있어.

예시로 이해하기

간단한 예시:

• 두 칸짜리 세상이 있어. 오른쪽 칸은 목표 지점이야.
• 처음 정책(π₀)은 두 칸 모두 왼쪽으로 가라고 해. (별로 좋지 않겠지?)
• 1단계:
  • 정책 평가: 현재 정책으로 각 칸의 가치를 계산해.
  • 정책 개선: 계산된 가치를 보고, 첫 번째 칸에서는 오른쪽으로 가는 게, 두 번째 칸에서는 가만히 있는 게 더 좋다는 걸 알아내. 이게 새로운 정책(π₁)이야.
• 이 예시에서는 한 번 만에 최적 정책을 찾았어!

조금 더 복잡한 예시 (5x5 격자):

• 처음에는 정책이 좀 엉망이야.
• 하지만 반복할수록 정책이 점점 좋아져.
• 특히 목표 지점에 가까운 칸들의 정책이 먼저 좋아지는 경향을 보여. 왜냐하면 가까운 칸들은 목표 지점으로 가는 길을 아는 주변 칸들의 도움을 받을 수 있기 때문이야.
• 결국에는 모든 칸에서 최적의 행동을 하는 정책(π₁₀)을 찾게 돼.

이처럼 정책 반복 알고리즘은 처음에는 무작위적인 정책에서 시작해서, 평가와 개선을 반복하며 점점 더 좋은 정책을 찾아가는 똑똑한 방법이야!