Dynamic Programming

Bellmean Optimality Equation

\[
v_* (s) = \max_{a} \sum_{s',r} p(s', r | s, a) \left[ r + \gamma v_* (s') \right]
\]

\[ q_* (s,a) = \sum_{s',r} p(s', r \mid s, a) \left[ r + \gamma \max_{a'} q_* (s',a') \right] \]

정책 평가 (Policy Evaluation)

정책 평가의 목적은 주어진 정책 \( \pi \)에 대해 각 상태 ( s )에서 기대되는 총 보상, 즉 상태-가치 함수 ( v_\pi(s) )를 계산하는 것이다. 이는 다음과 같은 벨만 기대 방정식으로 표현된다:
\[
v_\pi(s) = \sum_{a} \pi(a|s) \sum_{s',r} p(s', r | s, a) \left[ r + \gamma v_\pi(s') \right]
\]

여기서 \( \gamma \)는 할인율, \( p(s', r | s, a) \)는 상태-전이 확률, \( \pi(a|s) \)는 상태 ( s )에서 행동 ( a )를 선택할 확률이다.

 

\[
v_{k+1} (s) = \sum_{a} \pi(a|s) \sum_{s',r} p(s', r | s, a) \left[ r + \gamma v_k(s') \right]
\]

 

\( v_{k+1}(s) \): 상태 \( s \)에 대한 새로운 가치 추정치로, 반복 \( k+1 \) 단계에서의 상태-가치 함수 값이다.

\( v_k(s') \): 이전 반복 \( k \) 단계에서의 상태 \( s' \)에 대한 가치 추정치이다.

이 식은 상태-가치 함수 \( v_k(s) \)를 반복적으로 갱신하여 주어진 정책 \( \pi \)에 대한 상태-가치 함수 \( v_\pi \)를 점진적으로 추정하는 과정을 나타낸다.

 

반복적 정책 평가 (Iterative Policy Evaluation)

반복적 정책 평가 알고리즘은 초기 상태-가치 함수 ( V(s) )를 임의로 설정하고 다음 업데이트 규칙을 통해 점진적으로 개선한다.

Iterative Policy Evaluation.

 

이를 코드로 알고리즘을 구현해 보았다.

def policy_evaluation(pi, theta, gamma, states, actions, transition_probabilities, rewards):
    # 상태-가치 함수 초기화
    V = {s: 0 for s in states}
    
    while True:
        delta = 0
        # 모든 상태에 대해 반복
        for s in states:
            v = V[s]  # 이전 가치 저장
            # 새로운 가치 계산
            V[s] = sum(
                pi(a, s) * sum(
                    transition_probabilities(s, a, s_prime) * 
                    (rewards(s, a, s_prime) + gamma * V[s_prime])
                    for s_prime in states
                )
                for a in actions
            )
            # 변화의 최대값 갱신
            delta = max(delta, abs(v - V[s]))
        
        # 수렴 여부 검사
        if delta < theta:
            break

    return V

 

정책 개선 (Policy Improvement)

정책 개선은 현재 정책을 사용하여 더 나은 정책을 찾는 과정이다. 현재 정책의 상태-가치 함수 \( v_\pi \)를 사용하여 새로운 정책 \( \pi' \)을 생성할 수 있다:
\[
q_\pi (s,a) = \sum_{s',r} p(s', r \mid s, a) \left[ r + \gamma v_\pi (s') \right]
\]
여기서 \( q_\pi (s, \pi'(s)) \geq v_\pi(s) \)이면, \( \pi' \)이 \( \pi \)보다 더 좋은 정책임을 알 수 있다.

새로운 정책 \( \pi' \)은 다음과 같이 정의할 수 있다:
\[
\pi'(s) = \arg\max_a \sum_{s',r} p(s', r \mid s, a) \left[ r + \gamma v_\pi(s') \right]
\]
이 조건을 만족하면, 정책 개선 정리에 의해 새로운 정책 \( \pi' \)이 이전 정책 \( \pi \)보다 항상 더 나은 결과를 보장한다.

그러면 이는,

\( v_\pi' (s) \geq v_\pi(s) \) 로 표현이 가능하다.

 

정책 반복 (Policy Iteration)

정책 반복은 정책 평가와 정책 개선을 반복적으로 수행하면서 최적의 정책을 찾는 알고리즘이다:

Policy Iteration

1. 초기 정책 \( \pi_0 \)을 설정한다.
2. 정책 평가를 통해 \( v_{\pi_k} \)를 계산한다.
3. 정책 개선을 통해 새로운 정책 \( \pi_{k+1} \)을 생성한다.
4. 정책이 더 이상 변하지 않을 때까지 반복한다.

이 알고리즘은 유한한 MDP에서 최적의 정책으로 수렴한다.

이를 코드로 알고리즘을 재표현해봤다.

def policy_iteration(states, actions, transition_probabilities, rewards, gamma, theta):
    """
    정책 반복 알고리즘을 통해 최적의 정책과 상태-가치 함수를 찾는다.
    
    states: 상태 공간의 리스트
    actions: 행동 공간의 리스트
    transition_probabilities: 상태 전이 확률을 반환하는 함수, p(s', r | s, a)
    rewards: 보상을 반환하는 함수, r(s, a, s')
    gamma: 할인율
    theta: 정책 평가의 수렴 기준 임계값
    """
    
    # 1. 초기화
    V = {s: 0 for s in states}  # 상태-가치 함수 초기화
    policy = {s: actions[0] for s in states}  # 모든 상태에서 임의의 행동 선택으로 초기화
    
    while True:
        # 2. 정책 평가
        while True:
            delta = 0
            for s in states:
                v = V[s]  # 현재 가치 저장
                # 정책에 따른 가치 계산
                V[s] = sum(
                    transition_probabilities(s, policy[s], s_prime) *
                    (rewards(s, policy[s], s_prime) + gamma * V[s_prime])
                    for s_prime in states
                )
                # 최대 변화량 갱신
                delta = max(delta, abs(v - V[s]))
            # 수렴 여부 검사
            if delta < theta:
                break

        # 3. 정책 개선
        policy_stable = True
        for s in states:
            current_action = policy[s]
            # 상태 s에서 가능한 모든 행동에 대해 q값 계산 후 최대값 선택
            policy[s] = max(
                actions,
                key=lambda a: sum(
                    transition_probabilities(s, a, s_prime) *
                    (rewards(s, a, s_prime) + gamma * V[s_prime])
                    for s_prime in states
                )
            )
            # 정책이 변경되었는지 확인
            if current_action != policy[s]:
                policy_stable = False

        # 정책이 안정되면 반복 종료
        if policy_stable:
            break
    
    return policy, V

요약 설명: 

1. 정책 평가: 주어진 정책 $\pi$에 따라 각 상태의 가치 함수 $V(s)$를 계산한다. 이 단계에서는 현재 정책이 고정된 상태에서 해당 정책이 얼마나 좋은지를 평가하기 위해 $V(s)$ 값을 반복적으로 갱신하면서 수렴할 때까지 계산한다.
2. 정책 개선 : 평가된 가치 함수 $V$를 바탕으로 각 상태에서 최적의 행동을 선택하여 정책 $\pi$를 업데이트한다. 이때 각 상태 $s$에서 가치 함수 $V(s)$에 따라 가능한 행동 중 최대의 기대 보상을 제공하는 행동을 선택하여 새로운 정책 $\pi(s)$를 찾는다.

이 과정을 반복하면서 점점 더 나은 정책을 찾게 되며, 최종적으로 정책이 더 이상 변경되지 않을 때(정책이 안정적일 때), 최적의 정책과 그에 따른 최적의 가치 함수에 도달하게 된다.

 

 

 

 

 

출처: Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). The MIT Press.