하쿠's 강화학습 :: [Ch. IV] Dynamic Programming

G포스팅에 앞서 이 게시글은 Reference의 contents를 review하는 글임을 밝힌다.

 

 

 

 

「Dynamic Programming(동적계획법)」

강화학습(이하 RL)의 해결방법에는 환경에 대한 정보를 얼마나 가지고 있느냐에 따라 구분할 수 있다.

 - 환경정보에 대해 완벽히 안다(Model Based) = Dynamic Programming(DP) = Planning
 - 환경정보에 대해 일부만 안다(Model Free) = Reinforcement Learning(RL) = Learning

 

'Dynamic Programming(동적계획법, 이하 DP)'은 MDP속성을 만족하며 환경에 대해 완벽한 정보가 주어진다는 전제하에 최적화 정책을 계산할 수 있는 알고리즘을 말한다.

 

환경에 대한 정보를 습득하며 최적의 수를 찾아가는 RL과 달리, 모든 정보를 알고 있는 DP의 경우는
이미 알고 있는 정보를 가지고 문제에 대한 해결책(순차적인 행동절차)을 결정하기 때문에,

Planning 즉, "계획을 세운다"라고 표현한다.

 

이와 반대로, 아직 찾지 못한 정보(규칙)를 검색하고 배워나간다는 의미에서, RL의 경우는

Learning 즉, "배운다"라고 표현하는 것이다.

 

이와 같이 DP는 완벽한 환경정보를 기반으로 한다는 점에서 적용에 한계가 있는 방식들이지만, 이론적으로 강화학습(이하 RL)을 이해하는데 중요한 역할을 한다.

 

설명하기 앞서, DP를 적용할 수 있는 과제(Task)는 유한 MDP환경을 가지고 있다고 전제한다.
이는 S(상태), A(행동), R(보상), S`(다음상태)가 이산값을 가진다고 전제한다는 말과 같다(Discrete Task).

 

물론 연속값을 갖는 Continuous Task에 대해서도 적용 가능하나, 통상 이러한 과제일지라도 근사화를 통한 해결책(Approximation Solution)을 찾기 위해서는 상태와 행동공간크기(State Space)를 정량화한 뒤, 유한 MDP속성을 정용하여 찾기 때문이다(결국은 Discrete Task 치환).

이 부분에서 공간크기(Space)라는 새로운 개념이 등장한다.

 

 

「공간크기(Space)」

공간크기(상태공간크기 or 행동공간크기)란, 각 관점에서 구별이 가능한 속성의 개수를 말한다.

예를 들어, RC 비행기 조종에 있어서 관찰해야 하는 부분(상태)은 풍속, 풍향, 배터리 잔량이고
수행 가능한 행동(행동)은 상승, 하강, 좌측으로 기체 회전, 우측으로 기체 회전일 경우,

상태공간크기는 '3', 행동공간크기는 '4'이다.

 

 

다시 돌아와서, DP나 RL 모두, 목표는 '가치함수를 활용하여 최적의 정책을 찾는 것'이다.
DP에서는 벨만방정식을 가치함수로서 활용하여 정책을 개선해나간다.

 

 

 

 

「Policy Evaluation(정책평가)」

임의의 정책을 찾기 위해 상태가치함수를 계산하는 것, 그것을 Policy Evaluation(정책평가)이라고 한다. 전에 배웠던 상태가치함수식을 다시 한번 보자.

 

State Value Function

 

상태가치함수는 상태(S)에서의 반환값(G)이고, 이는 각 행동에 대한 선택 가능한 행동들의 행동가치함숫값(q)의 평균(mean)이다(더 정확히는 단순한 산술평균(1/N)이 아니라, 정책ㅠ의 가중치를 곱해준 비율로 계산한다).

 

이것은 벨만기대방정식(Bellman Equation)을 기반으로 한 연산의 결과이며, 이러한 식은 모든 상태에 대해 동시성(Simultaneousity)을 가진 선형방정식(Linear Equation)이다.

추가적으로 '동시성을 가진 선형방정식'이란, 같은 단위시간 t에서 모든 상태가 위와 같은 식으로 동시에 계산된다는 뜻이다(모든 경우의 수 계산).

 

돌아와서, 아래와 같은 식으로 가치함수를 반복적으로 계산(평가)해나가는 것을 '(Iterative) Policy Evaluation((반복적) 정책평가)'이라고 한다(혼동을 피하기 위해 첨언을 하자면, 이해에 있어 우선시 되는 것은 '평가'이다.  '반복적'이라는 것은 평가를 단순히 반복한다는 뜻이므로 평가에 중심을 두고 설명을 따라가자).

 

State Value Function

 

항상 최적의 정책이 존재한다는 동일한 조건 하에, 어떠한 시점의 정책이건 간에 무한번에 가까운 시행을 거치면 대상 정책이 결국 최적의 정책으로 수렴한다(ㅠ -> ㅠ*).

 

이러한 계산 작업을 수행한 이후에, 모든 상태에 대해 갱신(Update)을 해준다.

 

이때, 보상을 받을 것으로 기대되는 다음상태(S`)와 그에 따르는 행동을 수행했을 때의 즉각보상을 중심으로 각 상태의 가치함숫값이 갱신되어나간다.

 

이러한 갱신을 'Expected Update(기대된 갱신)'라고 한다.

 

DP를 포함한 RL에 존재하는 갱신의 방법에는 상태기준(상태가치함수) 인지(= Policy Iteration), 상태-행동 쌍 기준(행동가치함수) 인지(= Value Iteration)의 여부와 갱신을 위한 다음상태들을 결합하는 방법(MonteCarlo Method, TD-Sarsa, TD-Q_learning)의 차이에 따라 몇 가지 다른 방법이 존재한다.

 

이에 대한 내용은 이어지는 설명과 다음 포스트에서 차차 설명을 이어나갈 예정이니, 우선 넘어가도록 하자.

 

아래는 앞서 설명한 (반복적) 정책평가의 의사코드와 예시인 Grid World이다.

 

(Iterative) Policy Evaluation의 의사코드

 

다음 예시에서 우리는 Agent를 격자판(Grid World) 좌측 최상단과 우측 최하단으로 움직이도록 하는 목표를 가지고 있다. 각 행동에 대한 보상체계(즉각보상)는 목표지점으로의 행동 시 '0', 그 이외의 지점으로의 행동 시 '-1'로 통일한다.

 

또한, 다음상태에 대한 반영 수식은 계산의 용이함을 위해 다음상태값의 단순 합산으로 진행한다(할인율을 활용한 정확한 다음상태가치계산 X). 추가로, 정책은 변동 없이 모든 행동에 대해 0.25의 확률을 갖는 것으로 가정한다.

 

따라서 이를 종합하면 각 상태에 대한 가치함수는 R+V(S`)로 표현한다.
또한 각 상태는 좌측 상단부터 좌측으로, 아래로 상태 번호를 넘버링하여 V(S0) ~ V(S15)로 지정하겠다.

 

 

시간 t = 0 에서는, 모든 상태가치함수와 정책이 각각 '0'과 무작위(1/선택가능 행동 수 = 0.25)로 초기화된다.

 

t = 0에서의 State Value Function

 

시간 t = 1 에서는, 각 상태의 가치함수를 계산한다.

V(S0)의 상태가치값을 같이 계산해보면,
 - Up 선택 = 0 + 0
 - Down 선택 = -1 + 0
 - Left 선택 = 0 + 0
 - Right 선택 = -1 + 0
 = V(S0) = -0.5
이는 V(S15) 값 역시, 동일하다.

이와 다르게 V(S1)의 상태가치값을 같이 계산해보면,
 - Up 선택 = -1 + 0
 - Down 선택 = -1 + 0
 - Left 선택 = 0 + 0
 - Right 선택 = -1 + 0
 = V(S1) = -0.75

V(S2)의 상태가치값은,
 - Up 선택 = -1 + 0
 - Down 선택 = -1 + 0
 - Left 선택 = -1 + 0
 - Right 선택 = -1 + 0
 = V(S2) = -1

결론적으로 모두 계산해보면, 이런 식의 가치함수값 배열을 확인할 수 있다.

 

t = 1의 State Value Function

 

 

동일한 방식으로 연산을 진행하면, t = 2에 대한 상태가치값 배열을 다음과 같이 얻을 수 있다(소수점 아래 3자리 이상 내림 연산). 주의할 점은 이전 시점에서의 상태가치값을 기준으로 연산을 진행해야 한다는 점이다(각 상태는 동시성을 갖기 때문).

 

t = 2의 State Value Function

 

 

 

 

「Policy Improvement(정책개선)」

위에서 정책에 대한 평가로서 각 상태의 가치함수를 계산하였으면, 이를 기준으로 기존 정책에 대한 개선을 해야 한다. Policy Improvement는 기준 지표인 '가치함수를 가지고 정책을 개선하는 것'을 말한다.

 

가치함수에는 State를 기준으로 하는 상태가치함수와 State-Action Pair를 기준으로 하는 행동가치함수가 존재한다고 했었는데, Policy Improvement에서는 상태가치함수를 활용한다.

 

여기서 '개선'이라는 단어에 집중해볼 필요가 있다.

개선이란 고쳐서 더 좋게 만든다는 의미를 지니는데, 문제는 현재 가치값에 비해 새로운 발견된 가치값이 좋음을 어떻게 판단하느냐는 부분이다.

 

우리는 상태가치값을 선택 가능한 행동들의 행동가치값의 평균(가중치를 고려한)으로 계산했었다.
어떠한 행동이 우수하다는 것은 그러한 평균값보다 가치가 크다는 뜻이다.

즉, 해당 행동가치값이 해당 상태가치값보다 클 경우에 우리는 해당 행동을 좋은 행동으로 평가할 수 있다.
또한, 이러한 행동가치값을 내포하여 계산한 새 상태가치값은 당연히 기존의 상태가치값보다 좋다.

 

결론적으로, 이러한 행동들로 더 많이 이루어진 정책이 더 우수한 정책이며, 계속해서 개선을 목적으로 갱신해나가는 과정을 거치는데 이를 'Policy Improvement(정책개선)'라고 한다.

 

아래는 Policy Improvement의 의사코드이다.

 

 

 

 

「Policy Iteration(정책반복)」

앞에서 언급한 Policy Evaluation(정책평가)과 Policy Improvement(정책개선)를 하나로 묶어, 아래와 같은 방식을 반복을 통해 최적의 정책을 이끌어내는 과정을 'Policy Iteration(정책반복)'이라고 한다.

 

Policy Iteration의 과정

 

E는 Evaluation이며, I는 Improvement이다. 가치함수를 기반으로 정책을 수정하고, 해당 정책을 통해 다시 가치함수를 재구성한다. 이러한 과정을 최적의 정책을 얻을 때까지 반복한다.

 

다음은 Policy Iteration의 의사코드이다.

Policy Iteration 의사코드

 

 

 

 

「Value Iteration(가치반복)」

Policy Iteration의 한 가지 단점은 매 시행(반복)마다 선택 가능한 모든 행동에 대한 가치함숫값에 대한 Evaluation을 실시한다는 것이다.

 

이러한 진행방식은 연산량이 너무 많아진다는 단점이 있다.
(위와 같이 한번의 시행에 모든 경우의 수를 계산하는 방식을 'Sweep-스위프 방식'이라고 함).

 

이를 대체하기 위한 방법으로, 최대가치행동에 대해서만 Iteration을 진행하는 방식을 선택할 수 있는데,
이를 'Value Iteration(가치반복)'이라고 한다.

 

Value Iteration의 아이디어는 간단하다.

 

Policy Iteration에서 최초의 Policy Evaluation을 거치고 난 이후의 진행에서, 가치함수의 측면에서는 최종 가치함숫값과 다소 차이가 있을지언정, 어떠한 행동이 최대가치행동인지는 Greedy Policy 구성의 측면에서 볼 때, 이후 여러 번의 개선을 거친 정책과 차이가 없다는 특징이 있다. (최초연산결과로 나온 최대가치행동 = 최종 최대가치행동)

 

이것이 가능한 이유는 단 한 번의 연산으로도 가장 좋은 행동은 결정이 되고, 이에 대한 변수가 없기 때문이다 (환경에 대한 완벽한=불변의 정보를 가지고 있기 때문).

 

이에, 최적의 행동에 해당하는 행동가치값을 기준으로 Iteration을 진행하는 방법이다.
이러한 방식은 선택 가능한 행동이 N개일 경우, 기존 연산량의 1/N로 연산량을 줄일 수 있다는 장점이 있다.

이는 달리 이해하면, 벨만최적방정식(Bellman Optimality Equation)을 기반으로 하는 연산이다.

 

다음은 Value Iteration의 의사코드이다.

 

Value Iteration의 의사코드

 

 

 

 

「Asyncronous Dynamic Programming(비동기 DP)」

앞서 살펴본 DP는 동시성을 가진 즉, 동기화 방식의 DP문제였다.

이를 위해서는 Sweep 방식의 연산을 통해 진행되는데 앞서 본 Policy Iteration이 그러했듯, 이러한 진행은 방대한 연산량 덕에 현실적으로 적용에 어려움이 따른다(사정이 좀 더 나은 Value Iteration일지라도 마찬가지이다).

 

따라서, 동시성을 무시한 채로 순서 없이 각 상태의 값을 가져와 자유롭게 진행해나가는 방식을
'Asyncronous Dynamic Programming(비동기식 DP)'이라고 한다.

 

이러한 비동기방식의 DP는 각 상태의 시점이 달라도 무관하다.
다시 말해, 갱신횟수가 다르거나 갱신 이전에 평가에 있어서도 각 수치들의 단위시간에 차이가 있어도 무관하다는 뜻이다.

 

이는 동기식보다 더 많은 Iteration 횟수가 소요되지만 결론적으로 최적의 정책에 도달한다는 점,
계산 수행에 있어 유연성(Flexibility)을 두어 상당한 부담을 줄인다는 점에서 사용에 무리가 없고, 이 때문에 현실에서 각광받는 방식이다.

비유하자면 우리가 딥러닝 지도학습에서 Epoch당 Full gradient방식의 연산 부담을 줄이기 위해
Mini-Batch 방식을 통한 Stochastic Gradient방식을 채택하는 이유와 정확히 동일하다.

 

또한, 이러한 방식은 앞선 이유와 더불어 실시간 상호작용을 더욱 쉽게 만들어준다는 장점이 있다
(다른 상태의 동기화를 기다릴 필요가 없이 의사결정이 가능하기 때문).

 

 

 

 

「Generalized Policy Iteration(GPI = 일반 정책반복)」

앞서 살펴보았던, Policy Evaluation과 Policy Improvement의 세부사항을 무시하고, 큰 틀에서 정책 평가와 개선의 상호작용 자체의 개념을 'Generalized Policy Iteration(이하 GPI)'이라고 한다.

 

Generalized Policy Iteration의 원리

 

이 둘은 언뜻 보기에는 '경쟁구도'를 가진 것처럼 보이지만,
결국 상호보완적이라는 측면에서 하나의 목표를 향해 수렴하는 '협력구도'라고 볼 수 있다.

 

이를 이해하기 위해 아래의 그림을 보자.

 

동일한 목표를 가지고 수렴하는 Value Function과 Policy

 

Value Function은 Evaluation마다 새로이 갱신된다. 이를 기준으로 Policy의 개선 역시 진행된다.

 

만일, Value Function만을 기준으로 한 즉, 무조건적인 변화를 추구할 경우에 정책 구성 과정에 다소 노이즈(가치함수에 대한 근시적인 결과값)가 끼어 잘못된 정책을 구성할 가능성이 있다.

반면, Policy만을 기준으로 한 즉, 기존의 정책에서 불변을 추구할 경우에 새로운 최적의 가치를 반영할 수 없기 때문에, 이 역시 최적의 정책을 찾을 수 없게 된다.

 

그렇지만, 이 둘의 적절한 조화를 통해서는 우리가 목표로 하는 최적의 정책(최대가치행동 만으로 구성된)을 구성할 수 있게 된다.

이는 마치 이전에 배웠던, 탐험-이용(Exploration-Exploitation) 알고리즘과 같은 맥락이라고 보면 쉽다.

 

 

 

 

「Dynamic Programming의 효율성」

DP의 효율성을 논하기 위해, 다른 최적화 이론과 비교해보려고 한다.
수학에는 DP 외에 선형계획법(Linear Programming)이라는 최적화기법이 있다.

 

선형계획법은 제약 조건이 연립일차부등식 또는 연립일차방정식으로 나타나고, 알고자 하는 값을 나타내는 목적함수(objective function)도 일차식인 경우에 이 일차식의 최댓값 또는 최솟값을 구하는 방법인데,

쉽게 말해 일차식으로 표현된 제약 조건을 고려하여 목적함수의 최적화를 꾀하는 방법이라고 생각하면 쉽다 (어려우면 어쩔 수 없... 네이버 설명 ㄱㄱ).

 

정의역인 상태값 양이 방대한 Task에 대하여 선형계획법이 갖는 효용성은 극대화되지만, 상태값 양이 적은 Task에 대해서는 적합하지 않다는 문제가 불거진다.

 

반면, DP는 상태값 양이 적은 경우에 우수한 성능을 보이지만 다수의 상태값을 갖는 Task에 대해서는 방대한 연산량이 문제가 된다. 이는 실제 적용에 어려움이 있다고 생각하는 입장에서 흔히들 'Curse of Dimention(차원의 저주)'이라고까지 불린다.

 

하지만 깊게 들어가 보면 연산량을 문제점으로 들어 DP알고리즘의 결점을 논하기에는 다소 무리가 있다.

왜냐하면 연산량 자체의 문제는 DP 알고리즘이 가지는 단점이 아닌 해결하려는 Task의 본질적 어려움(Difficulty)이기 때문에, 이를 근거로 DP 알고리즘의 비효율성의 논하기에는 다소 무리가 있다.

 

또한, 이런 경우 보통 비동기식 DP방식을 사용하면 수월하게 해결할 수 있다.

 

이에 결론적으로, DP는 Model Based 한 Task를 해결하기 위한 솔루션으로 선형계획법보다 적합하다고 할 수 있다.

 

 

 

 

「마무리」

MDP해결법으로서 DP를 알아보았다

 

Policy Evaluation은 '정책을 기반으로 한 상태가치값의 평가'를 말하고, 평가에 있어 벨만기대방정식을 활용한 가치함수를 기준으로 두며,
Policy Improvement에 있어서 선행돼야할 과정이다.

 

Policy Improvement는 '앞서 계산한 평가를 기반으로한 정책의 개선'을 말한다.

 

이 두 가지를 병행하며 최적의 정책을 찾아가는 Policy Iteration은 DP의 Planning의 한 종류이며, Value Iteration은 역시 같은 목표를 갖지만, 연산량 축소를 꾀하여 벨만최적방정식의 결과인 최적행동가치값을 기준으로 Evaluation과 Improvement를 진행하는 Planning 기법이라는 점에서 Policy Iteration과 차이가 있었다.

 

GPI는 사실상 RL의 가장 일반화된 최적화 방법으로 정책과 가치함수를 상호작용시켜 최적화를 얻는 개념을 말한다.

 

알고리즘의 효율성의 측면에서, DP는 Model Based 과제에 대해 선형계획법보다 더욱 적합한 솔루션임을 알 수 있었다.

 

다음 포스트에서는 RL(Model Free한 환경)의 솔루션 중 하나인 Monte Carlo Method에 대해서 알아볼 예정이다.

 

 

 

 

「참고」

Reinforcement Learning, Second Edition : An Introduction
Richard S. Sutton and Andrew G. Barto

https://mitpress.mit.edu/books/reinforcement-learning-second-edition

Reinforcement Learning, Second Edition