[강화학습 기초] 벨만 방정식과 다이나믹 프로그래밍

 

※ 본 글은 '[도서]파이썬과 케라스로 배우는 강화학습'의 내용을 통해 작성한 글입니다.

 

1. 벨만 기대 방정식

이번 글에서는 다이나믹 프로그래밍을 통해 최적 정책을 찾는 방법을 알아볼 것이다.

 

이에 앞서 벨만 기대 방정식을 다시 살펴보자.

 

$ v_{\pi}(s) = E_{\pi}[R_t + \gamma v_{\pi}(s_{t+1}) | s] $

벨만 기대 방정식

 

여기서 실제로는 등호가 아니라, 대입 연산자를 적용하면, '참가치 함수'로 수렴한다.

이렇게 참가치 함수를 찾는 과정을, 다이나믹 프로그래밍을 통해 해결할 수 있다. 

 

2. 다이나믹 프로그래밍

다이나믹 프로그래밍은 큰 문제를 작은 문제들의 중첩으로 해결하는 방식이다.

가장 간단한 예시가 팩토리얼, '!' 연산 과정이다.

 

예를 들어, 1차원 배열 arr[n] = n!이 되도록 계산하고 싶다고 해보자.

 

for n in range(1, 100):
  value = 1
  for j in range(1, n):
    value = value*j
  arr[n] = value

가장 직관적인 구현은 위와 같을 것이다. 

이 경우의 시간 복잡도는 $ O(n^2) $이다.

 

그런데 생각해보면, 이전 문제의 답을 이용해 현재 문제의 답을 조금 더 쉽게 구할 수 있다.

예를 들어, 4! = 3!*4 이다.

즉, arr[n] = arr[n-1]*n 으로 간단하게 계산할 수 있다.

 

arr[1] = 1
for n in range(2, 100):
  arr[n] = arr[n-1]*n

코드 상으로는 위와 같고, 이 경우의 시간 복잡도는 $ O(n) $이다.

 

이처럼 다이나믹 프로그래밍을 적용하면, 작은 문제의 답을 통해 점점 더 큰 문제의 답을 효율적으로 구할 수 있다. 

 

※ 다이나믹 프로그램을 사용한다고 항상 시간 복잡도가 O(n)인 것은 아니다.

 

위의 팩토리얼 예시와 같은 경우를 bottom-up 방식이라고 하고, 반대로 top-down 방식도 존재한다.

예를 들어, arr[5] = 120을 기준으로 arr[4] = 120/5 와 같이 계산하면, top-down 방식을 이용했다고 생각할 수 있다. 

 

3. 그리드 월드에 적용하기

5x5 크기의 그리드 월드

위와 같은 5x5 크기의 그리드 월드를 기준으로 생각해보자. 

이 예시에서는 빨간 네모가 이동하는 물체이고, 세모는 -1, 파란색은 +1의 보상을 의미한다. 

 

여기서 각 state의 가치를 다이나믹 프로그램으로 계산할 수 있다.

이때는 top-down 방식이 적용된다. 

 

다이나믹 프로그래밍에서는, 한 step에서 모든 상태에 대한 정보를 알고, 모든 상태의 가치를 업데이트한다. 

 

이를 의사코드로 나타내면 다음과 같다.

new_value = []

for state in states : # 모든 state
  new_value[state] = 0
  for action in actions: # 가능한 모든 action
    next_state = get_next_state(state, action)
    
    # 상태 가치 함수 계산 수식
    new_value[state] += get_policy(state, action)*(get_reward(state, action) + discount_factor*value[next_state])
    
value = new_value

상태 가치 함수 수렴 의사코드

※ 편의상 1차원 배열의 형태로 표현했다.

 

$ v(s) \leftarrow \sum_{a \in A}^{}{\pi (a|s)(r(s, a) + \gamma v(s'))} $

상태 가치 함수

위 수식을 코드로 표현한 것 뿐이다.

(매 state 별로 가치를 바로 업데이트 하지는 않고, new_value로 저장해두었다가 한 step이 지난 후 한번에 업데이트한다.)

 

다만 앞선 글에서 살펴봤듯이, 위 과정을 반복하면 참가치 함수로 수렴할 뿐이지, 최적 가치 함수를 찾는 것은 아니다.

따라서 이 방식에서는 최적 가치 함수를 찾기 위해 업데이트하는 과정도 존재해야 한다.

 

for state in states: # 모든 상태
  
  action_value_list = []
  policy = [0, 0, 0, 0] 
  
  for action in actions: # 모든 행동에 대해, 행동을 통해 얻는 가치를 계산
    next_state = get_next_state(state, action)
    reward = get_reward(state, action)
    
    action_value = reward + discount_factor*value[next_state]
    action_value_list.append(action_value)
    
  # 가치가 가장 큰 행동만 추출(동점 가능), 행동 확률 100%를 나눠갖기
  max_idx_list = get_index_of_max(action_value_list)
  prob = 1 / len(max_idx_list) 
  
  for idx in max_idx_list:
    policy[idx] = prob

정책 업데이트 의사코드

 

이후의 보상이 최대인 행동을 선택하는 방식으로 정책을 업데이트한다. 

 

이 두 가지 과정을 아래와 같이 적절하게 이용하면, 최적 정책을 찾을 수 있다.

 

1. 모든 상태에 대해 상태 가치 함수를 계산한다. 

2. 모든 상태에 대해, 보상이 최대인 행동을 선택하는 방식으로 정책을 업데이트한다.

3. 정책이 바뀌었으므로, 상태 가치 함수를 다시 계산한다.

4. 2~3 과정을 반복한다.

 

반드시 상태 가치 함수를 계산하는 과정과 정책을 업데이트 하는 과정을 1번씩 교차할 필요는 없다.

ex) 상태 가치 함수를 3번 계산하고, 정책을 업데이트 

 

이렇게 하면 최적 정책으로 수렴한다.

Top-down 방식을 이용한다고 했는데, 직관적으로만 살펴보고 넘어가자. 

 

할인률을 0.9로 가정한 예시이다.

가장 먼저 보상의 아래와 오른쪽에 있는 상태의 가치가 수렴할 것이다. 

정책을 업데이트할 때, 가장 초기 단계에서 최적 정책이 고정될 곳이 두 위치임은 자명하다. 

 

이렇게 수렴된 값을 기준으로 다시 주변 값들이 수렴하고, 최종적으로는 전체적으로 최적 정책에 수렴할 수 있다.

 

4. 다이나믹 프로그래밍의 문제점

다이나믹 프로그래밍으로도 최적 정책을 찾을 수 있다면, 왜 강화학습이 필요할까?

 

다이나믹 프로그램은 다음과 같은 한계를 지니고 있다.

 

① 계산량

매번 모든 state, 모든 action의 조합에 대해 계산하므로 계산량이 매우 많아진다.

 

물론 앞선 팩토리얼 예시나, 그리드 월드같은 경우라면 충분히 계산이 가능하지만, 

경우의 수가 많은 문제는 오래 걸리는 수준이 아니라, 풀 수 없다.

 

② 차원의 저주

①과 이어지는 얘기이다. state의 좌표가 z 축으로 한 축만 늘어난다고 하더라도, 경우의 수가 훨씬 늘어난다.

다양한 feature로 정의되는 현실의 문제는 state가 많을 것이고, 다이나믹 프로그램으로 해결할 수가 없다.

 

③ 상태에 대한 정보

위 예시에서는 보상이나 상태 변환 확률을 완전히 제어할 수 있는 상태였지만, 현실의 많은 문제는 그렇지 않다.

이 경우 다이나믹 프로그래밍을 통해 수렴하는 것 자체가 어려울 수 있다. 

 

정리

• 다이나믹 프로그래밍으로도 최적 정책을 찾을 수 있다.
• 그러나 현실의 많은 문제를 풀기에는 한계가 많다.
• 따라서 강화학습이 필요하다.