[강화학습] 3. 다이나믹 프로그래밍

• 이 포스트는 '파이썬과 케라스로 배우는 강화학습'이라는 책을 바탕으로 스스로 공부한 내용을 정리한 포스트입니다.

다이나믹 프로그래밍, 정책 이터레이션과 가치 이터레이션에 관하여 공부한다.

 

 

다이나믹 프로그래밍

다이나믹 프로그래밍이란 큰 문제 안에 동일한 작은 문제가 여러개 있을 때, 하나의 문제를 풀고 나머지 동일한 문제는 정답만 이용하는 프로그래밍을 말한다.

다이나믹 프로그래밍으로 벨만 기대 방정식을 푸는 것이 정책 이터레이션,

벨만 최적 방정식을 푸는 것이 가치 이터레이션이다.

 

순차적 결정 문제 해결 과정

1. MDP로 엄밀하게 정의

2. 벨만 기대 방정식과 벨만 최적 방정식을 계산

3. 2번을 통해 최적 가치함수와 최적 정책을 찾기.

 

벨만 방정식을 푼다는 것

벨만 방정식을 푼다는 것은 식을 만족하는 변수의 값을 찾는 것을 말한다. (이것을 방정식의 해 라고 말한다)

벨만 최적 방정식을 푼다는 것은 v*(s)값을 해로써 구하는 것이다.

출처: 파이썬과 케라스로 배우는 강화학습

여기서 다이나믹 프로그래밍을 적용해 문제를 쪼갠다는 것은, 참 가치함수를 구하기 위해 그 값을 한번에 구하는게 아니라 timestep이라는 개념을 도입해 iteration계산을 하는 것이다.

-> timestep이 k인 시점에 모든 상태에 대하여 각자의 벨만 방정식의 해를 찾는다. 그리고 다 찾으면 k시점에서 찾은 해로 값을 갱신하고 다음 timestep으로(k+1) 넘어간다.

 

 

정책 이터레이션

MDP로 정의된 순차적 행동 결정 문제의 목표는 에이전트가 받을 보상의 합을 최대로 하는 것이다.

가치함수를 통해 자신이 이 목표에 얼마나 다가갔는지를 알 수 있다.

-> 보상의 합이 최대가 되도록 하는 정책이 최적 정책이고 이때의 가치함수가가 최적 가치함수이다.

 

정책 이터레이션을 통해 초기 정책을 최적 정책으로 점진적으로 바꾸어야 한다. 이때 매 timestep마다 정책의 "평가"가 필요한데 이것을 정책 평가, 갱신하는 것을 정책 발전 이라고 한다.

 

정책 평가

그렇다면 정책은 어떻게 평가하는가? 정책의 평가 기준은 바로 벨만 기대 방정식으로 변형하기 전인 가치함수이다.

출처: https://velog.io/@cherry611

반환값

현재의 정책을 반영하여 반환값을 구하고 그것의 기댓값을 구함으로써 v(s)를 구할 수 있다.

-> 즉 가치함수의 함숫값은 현재 상태 s에서 현재 정책을 따른다고 했을 때 받게될 모든 보상의 기댓값이다.

->-> 하지만 모든 보상을 구하는 것이 현실적으로 너무 어렵고 오래 걸린다. 그래서 다이나믹 프로그래밍 기법을 사용하는 것이다.

 

다이나믹 프로그래밍을 사용함으로써, 최적의 가치함수 값을 직접 구하는 대신 벨만 기대 방정식을 사용하여 점진적으로 최적 가치함숫값을 구한다.

벨만 기대 방정식

핵심은 현 시점에서 모든 행동에 의해 될 수 있는 모든 상태들의 가치함수와 다음 timestep의 보상만 고려해서 현재 상태의 다음 timestep가치함수를 찾겠다는 것이다.

-> '현재'의 '다음 상태'의 가치함수를 통해 '다음'의 '현재 상태'의 가치함수를 구한다.

계산 가능한 벨만 기대 방정식

(중요!) 만약 상태변환확률이 정해져 있다면(즉 어떤 행동a를 해서 무조건 한 특정한 상태s'으로 전이된다면), 두번째 시그마 기호옆에 있는 P는 특정 s'이 아니면 다 0이된다. 따라서 시그마 기호와 P가 없어지고 rv(s')항으로 남게된다.

 

정책 발전

정책 발전의 방법이 한 가지로 정해져 있는 것은 아니다. 여기서는 가장 널리 알려진 탐욕 정책 발전을 배운다.

탐욕 정책 발전이란 현재 상태 중에서 다음으로 가능한 상태 중 가장 큰 보상을 받게 될 곳을 향하도록 정책을 수정하는 방법이다.

큐함수의 정의

큐함수와 가치함수 사이의 관계

큐함수의 정의 변형

큐함수의 정의를 변형하면 right-side의 큐함수가 가치함수로 변경되어 있는 것을 알 수 있는데, 이것은 v(s)가 q(s, a)에 대해 특정 상태 s에 대한 모든 행동에 대한 기댓값, 즉 v(s) = E[q(s, a)]이기 때문이다.

원래의 큐함수의 정의를 변형해 보면

q(s, a) = E[R(t+1) | St = s, At = a] + rE[q(s', a') | St = s, At = a]이다. (S(t+1) = s'이고 A(t+1) = a'로 표기한다)

v(s) = E[q(s, a)]를 구체적으로 풀어서 설명하면 v(s) = E[q(s, a) | St = s, At = a]이고, v(s') = E[q(s', a') | St = s, At = a]이기 때문에(timestep이 달라도 공식은 동일), 첫번째 식에 대입하면,

q(s, a) = E[R(t+1) | St = s, At = a] + rv(s')이다.

그런데 v(s')은 그 자체로 기댓값이기 때문에, 확률변수가 아니므로 v(s') = E[v(s')]이다. 따라서,

q(s, a) = E[R(t+1) | St = s, At = a] + rE[v(s')]

q(s, a) = E[R(t+1) + rE[v(s')] | St = s, At = a]가 된다.

 

(복습) 대문자 S와 A는 집합을 말하는 것이고, 소문자 s와 a는 집합의 임의의 원소를 말하는 것이다.

 

출처: 파이썬과 케라스로 배우는 강화학습

탐욕 정책 발전은 특정 s상태에서, 가능한 모든 a에 대한 큐함수들을 각각 구한 뒤 가장 높은 큐함수 값을 갖는 행동을 가장 좋은 행동으로 판단하고 그 행동의 확률을 높인다(정책 갱신).

(참고) r(s, a) 기호는 현재 상태 s에서 특정 행동 a를 했을 때 받게 될 보상값을 말한다.

 

 

가치 이터레이션

만약에 정책이 결정적인 형태만(특정 정책은 특정 행동확률이 1)으로 정의된다면 어떨까?

일단 최적 정책은 결정론적이다.

최적 정책

현재의 가치함수가 최적은 아니지만 그럼에도 불구하고 그냥 최적이라고 가정하고 결정적인 행동의 정책을 적용한다면 어떨까?

뭔가 말이 안되는 소리라고 할 수도 있겠지만, iteration을 구현하는 다이나믹 프로그래밍에서 연산의 끝에는 결국 최적 정책을 찾게 되기 때문에 말이 안되는 것은 아니다.

이것이 바로 가치 이터레이션이다. 그래서 가치 이터레이션은 벨만 최적 방정식을 사용한다.

-> 가치함수를 최적 가치함수로 '가정'하고 가치함수를 업데이트하면 정책은 '알아서 최적 정책'으로 맞춰진다는 뜻

 

(주의!) 정책 이터레이션에서는 명시적으로 정책이 표시되었지만, 가치 이터레이션에서는 정책이 가치함수 안에 암묵적으로 포함되어있다.

-> 가치함수를 업데이트하면 정책은 자동으로 발전된다는 뜻.

 

벨만 기대 방정식을 통해 구하는 것은 현재 정책에 대한 참 가치함수이고, -> 정책 이터레이션

벨만 최적 방정식을 통해 구하는 것은 최적 정책에 대한 최적 가치함수이다. -> 가치 이터레이션

 

벨만 최적 방정식

그저 현재 상태에서 가능한 R(t+1) + rv(S(t+1))의 값들 중에서 최고의 값을 대입하기만 하면 된다.

-> 여기서 기댓값 연산자 E가 무시되었는데, 그 이유는 정책을 반영할 필요가 없기 때문이다. 즉 현재 상태에 대해서 R(t+1) + rv(S(t+1))를 최대로 하는 행동 하나만 고르기 때문에(기댓값을 구하려는 항이 단 1개) 기댓값 연산을 해도 결과는 동일한 것이다.

이것이 바로 가치 이터레이션이다.

 

 

다이나믹 프로그래밍의 한계 그리고 강화학습

다이나믹 프로그래밍은 계산을 빠르게 하는 프로그래밍 기법이지, 결코 '학습' 기법이 아니다.

사실, 다이나믹 프로그래밍을 통해 최적 정책을 구하는 것에는 3가지 치명적인 한계가 존재한다.

1. 계산 복잡도가 크게 증가

2. 차원의 저주

3. 환경에 대한 완벽한 정보가 필수

 

위의 한계를 극복하기 위해 근본적으로 문제에 대해 접근 방식이 달라야 한다. 그 다른 방식이 바로 강화학습이다.

 

실제 세계에서는 자연이나 환경에 대해 정확한 모델을 만드는 것이 불가능하다. 그래서 모델을 정확히 알기 어려운 경우에, 특정 시스템(모델의 대상)의 입출력 관계를 알기 위해서 두 가지 방법으로 접근해 볼 수 있다.

1. 일단 최대한 근사된 모델을 먼저 만들고 오차를 조금씩 보정하는 방법 (모델->조정)

2. 모델을 먼저 만들지 말고 입출력 사이의 관계를 학습하여 모델을 잠재적으로 새기는 방법 (조정->모델)

 

1번 방법은 학습개념 없는 고전적인 방법이다. 안정성이 높지만 문제가 복잡해지면 금방 한계가 보인다.

2번 방법은 안정성은 떨어지지만 복잡한 문제에서 굳이 모델을 만들 필요가 없다.