Reinforcemnce Learning

Bellman Equations

벨만 방정식은 동적 계획법(dynamic programming)에 사용
최적화 문제의 해를 재귀적인 방식으로 사용
재귀적인 구조 때문에 복잡한 문제를 여러 개의 더 간단한 하위 문제로 나누어 해결

개념

• 가치 함수(value function)와 최적 정책(optimal policy)을 구함
• 가치 함수는 특정 상태에서 얻을 수 있는 총 보상(reward)의 기댓값
• 정책은 특정 상태에서 어떤 행동을 취해야 할지 결정하는 규칙

재귀적 구조
"현재 상태의 최적 가치는 현재 상태에서 얻는 보상과 다음 상태의 최적 가치의 합으로 표현할 수 있다."

• 벨만 방정식의 논리:
  "미래를 보고 현재를 결정한다"

예시 (미로찾기)

• 가정: 미로의 특정 위치(상태)에서 탈출구까지 가는 최단 경로(최적 정책)를 찾음
• 내용 :
  • 현재 위치에서 한 칸 이동했을 때 얻는 보상(예: -1)과 다음 위치에서 탈출구까지 가는 최단 경로의 거리(최적 가치)를 더하면, 현재 위치에서 탈출구까지 가는 최단 거리.
  • 이 과정을 탈출구에 도달할 때까지 반복하면, 모든 위치에서 탈출구까지의 최단 거리를 알 수 있음
• 풀이
  • 출구: 가장 짧은 길의 거리는 당연히 0. (출구에 이미 도착)
  • 출구 바로 옆 칸: 출구까지 가려면 한 칸만 이동, 이때 거리는 1
  • 즉, "한 칸 이동 비용(1) + 다음 칸(출구)의 최단 거리(0) = 1"
  • 그 옆 칸: 여기서 출구까지 가려면, 바로 옆 칸(최단 거리 1인 곳)을 거쳐가는 것이 가장 효율적
  • 그러면 "한 칸 이동 비용(1) + 다음 칸(최단 거리 1인 곳)의 최단 거리(1) = 2"

(주요) 벨만 방정식 종류

1. 벨만 기대 방정식 (Bellman Expectation Equation)

특정 정책을 따를 때의 가치 함수를 계산
최적의 정책을 찾는 것이 아니라, 주어진 정책의 효율성을 평가

• 수식 :

$V^\pi(s) = \sum_{a \in A} \pi(a|s) \left( R(s,a) + \gamma \sum_{s' \in S} P(s'|s,a) V^\pi(s') \right)$
$V^\pi(s)$: 정책 $\pi$를 따를 때 상태 $s$의 가치
$\pi(a|s)$: 상태 $s$에서 행동 $a$를 취할 확률
$R(s,a)$: 상태 $s$에서 행동 $a$를 취했을 때 얻는 즉각적인 보상
$\gamma$: 미래 보상에 대한 할인율(discount factor) (0과 1 사이의 값)
* $P(s'|s,a)$: 상태 $s$에서 행동 $a$를 취했을 때 상태 $s'$로 전이될 확률

2. 벨만 최적 방정식 (Bellman Optimality Equation)

최적 정책을 따를 때의 가치 함수를 계산
모든 가능한 행동 중 최대의 가치를 가져오는 행동을 선택하는 것이 목표
가치 반복(value iteration)과 정책 반복(policy iteration)의 기초

• 수식:
  $V^*(s) = \max_{a \in A} \left( R(s,a) + \gamma \sum_{s' \in S} P(s'|s,a) V^*(s') \right)$
  $V^*(s)$: 최적 정책을 따를 때 상태 $s$의 최적 가치
  $\max_{a \in A}$: 모든 가능한 행동 $a$ 중에서 가장 큰 값을 선택