동적 계획법

동적 계획법 Dynamic Programming

• 큰 문제를 작은 문제로 나누어 부분적 답을 구한 후, 부분적 답을 합쳐서 전체적 답으로 만드는 풀이법
• 다음의 두 가지 속성을 가진 문제에 적용할 수 있음:
  • 최적 부분 구조(Optimal Substructure): 큰 문제의 최적 해결 방법이 그 문제를 구성하는 작은 문제들의 최적 해결 방법으로 구성됨
  • 중복되는 부분 문제(Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 부분 문제가 여러 번 발생하는 것

MDP와 동적 계획법

• 마코프 결정 과정(MDP)은 위의 두 가지 속성을 만족함
• 최적 부분 구조: 벨만 방정식은 상태 $s$에서의 최적 값이 다음 상태 $s^{\prime }$의 최적 값들의 결합으로 표현될 수 있음
• 중복되는 부분 문제: $s^{\prime }$으로 전이하는 상태 $s_1,s_2,s_3,\dots$ 등등이 있을 때 이들의 가치는 모두 $V(s^{\prime })$이 중복
• 강화학습에서 MDP에 대해 알고 있을 때, 동적 계획법으로 풀 수 있음

미끄러운 보행의 경우

• 5번의 상태 가치 = 4번 갈 확률 * 4번의 상태 가치 + 5번에 그대로 있을 확률 * 5번의 상태 가치 + 골을 할 확률 * 골의 상태 가치
• 4번의 상태 가치 = 3번 갈 확률 * 3번의 상태 가치 + 4번에 그대로 있을 확률 * 4번의 상태 가치 + 5번 갈 확률 * 5번의 상태 가치
• ...
• 확률은 정책과 전이 함수에 따라 결정되므로 각 상태 가치를 방정식으로 풀면 되지만, 풀기가 어려움 -> 부트스트래핑을 이용

반복적 정책 평가법 iterative policy evaluation

• 정책에 대한 V-함수를 추정하는 방법
• 전이 함수, 보상 함수 등 MDP를 알고 있을 때 사용
• V-함수들이 서로 얽혀 있으므로 바로 풀기가 어려움
• 비종료 상태의 상태 가치 함수 $v_0(s)$를 임의의 값으로 초기화하고 종료 상태의 가치는 0으로 설정. 아래 코드는 전체를 영벡터로 초기화
• $v_0$을 이용하여 $v_1$을, $v_1$을 이용하여 $v_2$를 추정하는 방식으로 추정치를 반복하여 업데이트
• 위의 과정을 반복하면 해당 정책의 가치 함수로 수렴
• 정책 평가 방정식

부트스트래핑 bootstrapping

• 강화학습에서 어떤 함수의 추정치를 구하기 위해 그 함수의 다른 추정치를 사용하는 방법
• 반복적 정책 평가법도 부트스트래핑
• 이전 추정치의 오차가 새 추정치에 전달될 수 있으므로 수렴 전에는 초기값의 영향을 받음
• 반복적 정책 평가법은 적절한 조건에서 반복하면 해당 정책의 가치 함수로 수렴
• "pull yourself up by your own bootstraps"라는 표현에서 유래
• 비슷한 용법:
  • 컴퓨터의 부팅(bootstrapping): 컴퓨터의 전원을 켰을 때 운영체제(OS)가 스스로를 불러오는 과정
  • 통계에서 부트스트래핑: 모집단에서 표본 추출 과정을 시뮬레이션 하기 위해, 현재 가지고 있는 표본에서 새로운 표본을 다시 추출

동적 계획법과 부트스트래핑

• 동적 계획법: 전이 확률과 보상 등 환경 모델을 이용해 가능한 다음 상태에 대한 벨만 갱신을 수행
• 부트스트래핑: 가치 함수의 이전 추정치 $v_k$를 이용해 새 추정치 $v_{k+1}$을 계산
• 반복적 정책 평가법은 동적 계획법이면서 부트스트래핑을 사용하는 방법

반복적 정책 평가법

def policy_evaluation(pi, P, gamma=1.0, theta=1e-10):
    # pi: 정책, P: 전이 함수, gamma: 할인율, theta: 수렴 판정 조건
    prev_V = np.zeros(len(P))  # 상태의 수와 크기가 같은 영(0)벡터
    gap = True
    while gap:
        V = np.zeros_like(prev_V)  # prev_V와 모양이 같은 영벡터
        for s in range(len(P)):  # 모든 상태에 반복
            for prob, next_state, reward, done in P[s][pi[s]]:
                V[s] += prob * (reward + gamma * prev_V[next_state] * (not done))
        gap = np.max(np.abs(prev_V - V)) > theta  # 기존 V와 차이가 작으면 중단
        prev_V = V.copy()
    return V

무조건 왼쪽으로 걷는 정책

LEFT, RIGHT = 0, 1
pi = {
    s: LEFT
    for s in range(env.observation_space.n)
}

평가

V = policy_evaluation(pi, env.P)