[강화학습] Planning by Dynamic Programming

http://www.yes24.com/Product/Goods/92337949

바닥부터 배우는 강화 학습 - YES24

https://dnddnjs.gitbooks.io/rl/content/

https://sumniya.tistory.com/10

※본 내용은 위의 자료들을 참고하여 작성하였습니다.

 

 

 

강화학습에는 Dynamic programming, Monte-carlo method, Temporal difference method 등 다양한 방법론이 있습니다. 최신 강화학습 알고리즘은 주로 TD 방법을 기반으로 쓰이지만, 처음은 DP에 기반을 두고서 발전했기 때문에 DP를 이해하는 것이 상당히 중요합니다. (https://ai-sinq.tistory.com/entry/동적-프로그래밍-Dynamic-Programming-DP)

동적 프로그래밍 (Dynamic Programming, DP)

MDP 문제 크기와 조건에 따른 접근법

Planning vs Learning

먼저 Planning과 Learning의 차이를 보도록 하겠습니다.

Planning은 한마디로 MDP의 모든 정보를 알고 문제를 푸는 것입니다. 미래의 상황에 대한 최적의 행동 계획을 만드는 것을 의미합니다. 즉, agent가 주어진 상황에서 가능한 모든 행동을 고려하고, 각각의 결과에 대해 예상되는 보상을 계산하여 최적의 행동 계획을 수립하는 것입니다. Planning은 Model-Based 강화 학습에서 자주 사용됩니다.

 

Learning은 MDP를 모를 때, 주어진 환경에서 agent가 경험을 통해 최적의 행동을 배우는 것을 의미합니다. 즉, agent는 일련의 상황에서 가능한 행동을 시도하고, 이에 대한 보상을 받으며, 이러한 경험을 통해 최적의 행동을 결정하는 것입니다. Learning은 Model-Free 강화 학습에서 자주 사용됩니다.

Prediction & Control

강화학습에서 Dynamic Programming은 다음 두 step으로 나뉩니다. (1) Prediction (2) Control입니다.

• Prediction : MDP와 𝜋가 주어졌을 때 각 상태의 벨류를 평가하는 문제

• Control : MDP가 주어졌을 때, 최적 가치함수, 최적 정책을 찾는 문제

Prediction 문제는 강화 학습에서 매우 중요합니다. 왜냐하면 Prediction 문제를 해결하면 다음 단계에서 행동을 결정하는 문제인 Control 문제를 해결하는 데 도움이 되기 때문입니다.

Control은 보상을 최대화하는 policy를 찾는 문제를 말합니다. 이를 위해, 강화 학습 알고리즘은 예측 문제에서 얻은 value function을 사용하여 현재 state에서 선택할 최적의 행동을 결정합니다. 대표적인 Control 알고리즘으로는 SARSA, Q-Learning, DQN 등이 있습니다. 이러한 알고리즘은 exploration과 exploitation의 균형을 유지하면서 optimal policy를 학습합니다. exploitation(활용)은 주어진 정보를 가지고 최선의 결정을 내리는 것을 말하며, exploration(탐색)은 정보를 더 수집하는 것을 말한다.

Prediction과 Control에 대한 알고리즘

Policy evaluation

Policy evaluation은 prediction 문제를 푸는 것으로서 현재 주어진 policy에 대한 true value function. 즉, V𝜋(s)을 구하는 것이고 Bellman expectation equation을 사용합니다. 현재 Policy를 가지고 iterative backup을 통해 true value function을 구합니다.

next-state-value function으로부터 present-state-value function을 구하는 것을 backup이라고 합니다. k는 iteration 숫자입니다.

true value function이라 함은, 현재 따르는 policy가 옳냐 틀리냐를 판단하기 위해서(처음의 policy는 random policy이기 때문에 반드시 이를 판단하고 발전시켜야합니다) value function을 사용하는데, 처음 구한 state의 value function은 진짜 value function이 아닙니다. 현재의 policy대로 각 state별로 중요도가 존재하게 되는데 이를 agent는 알 길이 없습니다. 그래서 몇번이고 이 state 저 state를 왔다갔다하면서 value function을 계속해서 update해 최종적으로 중요한지 안한지를 판단할 수 있는 "진짜" value function을 찾는 것입니다. 하지만 이 true value를 처음부터 구하기가 어려우니 아래와 같이 iteration을 반복하며 점점 true value에 다가가자는 게 DP의 아이디어입니다.

 

이제 간단한 예시를 통해 Policy evaluation을 이해해보겠습니다. 4x4 Grid World 환경에서 policy가 모든 state에서 상, 하, 좌, 우로 동일한 확률로 움직이는 agent가 경험한 모든 state의 value를 계산할 수 있도록 하는 것입니다.

다음으로, value function을 초기화합니다. 4x4 Grid World에서는 모든 state의 value를 0으로 초기화합니다.

그리고 각 state에서 가능한 모든 action을 취했을 때의 reward를 정의합니다. 4x4 Grid World에서는 각 state에서 상, 하, 좌, 우로 이동했을 때 reward는 -1로 정의합니다. 또한, 목표 지점에 도달했을 때 reward는 0으로 정의합니다.

4x4 Grid World에서의 Policy evaluation

k, 즉 iteration을 value function이 수렴할 때까지 반복한 결과 Policy evaluation이 완료됩니다. 수렴된 value function을 사용하여 agent는 optimal policy를 찾거나, k를 n번 반복한 value function을 사용하여 policy를 개선할 수 있습니다.

Policy Iteration

policy iteration은 강화학습의 기초적인 알고리즘 중 하나로, 일단 초기 policy를 임의로 선택한 후, 이를 평가하고 개선하는 과정을 optimal policy로 policy가 수렴할 때까지 반복하는 방법론입니다. 각 반복에서는 현재 policy를 기반으로 state function을 평가한 후, 그 결과를 이용해 policy를 개선합니다.

Policy iteration

policy improvement 단계에서는 다음과 같은 방법으로 현재의 policy를 개선합니다.

1. 각 state에 대해, 가능한 모든 행동에 대한 value를 계산합니다.
2. 현재 state에서 가능한 모든 행동 가운데, value가 가장 높은 행동을 선택합니다. (즉, action value가 가장 높은 것)
3. 선택된 행동을 현재 state의 policy로 지정합니다.

즉, 각 state에서 가능한 모든 행동에 대해 value를 계산한 후, 현재 state에서 action value가 가장 높은 행동을 선택하고, 그 행동을 현재 state의 policy로 update하는 것입니다.

이후 다시 policy evaluation 단계로 돌아가서 update된 policy을 기반으로 value function를 다시 계산합니다. 이렇게 policy evaluation과 policy improvement 단계를 번갈아가며 반복하면서, optimal policy와 optimal value function을 찾아가는 것이 policy iteration입니다.

이와 같이, 원래의 policy를 greedy policy로 바꾸어줌으로써 policy improvement가 되는 것입니다.

 

| Greedy: 먼 미래까지 보지 않고 그저 눈 앞의 이익을 최대화하는 선택을 취하는 방식
| Greedy policy: 딱 한번만 greedy policy로 행동하고 나머지는 원래 policy로 행동하는 정책

 

각 state의 value와 그에 따른 greedy policy

위와 같은 경우는 policy evaluation을 반복해 수렴된 value function을 이용해 greedy policy를 생성했습니다. 하지만 한번의 수렴된 value function으로 생성한 greedy policy가 optimal policy라는 보장은 없습니다. 그래서 다음과 같은 구조를 갖게 되며, policy iteration이라는 루프 안에 policy evaluation이라는 루프가 있기 때문에 많은 연산을 필요로 합니다.

위 루프에서 가장 많은 연산을 필요로 하는 구간은 policy evaluation입니다. 중요한 것은 optimal poilcy를 찾는 것이 목적이지 정확한 value function을 찾는 것이 아닙니다. value function은 오로지 greedy policy를 생성할 때에만 쓰일 뿐 구체적인 값이 사용되지는 않습니다. 또한 새로운 policy를 얻은 순간 이전에 구했던 value function은 버려지게 됩니다. 그렇기 때문에 아래와 같이 policy evaluation 반복을 한번만 수행하는 것이 빠르고 효율적입니다.

Value Iteration

value iteration 또한 policy iteration과 유사한 접근 방식을 사용하여 optimal policy를 찾는 강화학습 알고리즘입니다. value iteration은 policy iteration과 달리, policy evaluation과 policy improvement 과정을 한 번에 처리하는 방식으로 optimal policy를 찾아갑니다. value iteration의 핵심 아이디어는 Bellman optimality equation을 이용한 것입니다. Bellman optimality equation은 optimal policy와 optimal value function 사이의 관계를 나타내는 방정식으로, 다음과 같이 정의됩니다.

이를 이용하면, optimal policy를 구하기 위해 수많은 iteration을 거쳤던 policy iteration과 달리 evaluation을 한번만진행하게 됩니다. 또한, update할 때 max를 취하기 때문에 greedy하게 improve하는 효과를 줍니다.

 

4x4 Grid World에서 value iteration을 적용해보면 다음과 같은 결과가 나옵니다.

value function이 수렴할 때까지 iteration한 이 결과가 각 state의 optimal value를 의미합니다.

optimal value function을 구했기때문에 우리의 목적이었던 optimal policy도 구할 수 있습니다. MDP를 모두 아는 상황에서는 일단 optimal value function을 알면 optimal policy를 곧 바로 얻을 수 있기 때문입니다. agent 입장에서 현재 state에서 갈 수 있는 다음 state가 무엇인지 모두 알고있습니다. 따라서 이들 중에 optimal value function이 가장 높은 칸으로 움직이면 끝입니다. 그게 바로 optimal policy입니다. 말하자면 optimal value function에 대한 greedy policy인 것입니다.

optimal policy를 구하는 과정은 위의 Bellman optimality equation을 이용해서 모든 action 중 가장 높은 value function을 갖는 action을 policy로 지정하여 구할 수 있습니다.

 

이렇게 Dynamic Programming을 이용한 Planning 대해서 살펴보았습니다. 처음에 언급했다시피 DP는 MDP에 대한 모든 정보를 알아야 optimal policy를 구할 수 있습니다. 또한 DP는 full-width backup(한 번 update할 때 가능한 모든 successor state의 value function을 통해 update하는 방법)을 사용하고 있기 때문에 단 한 번의 backup을 하는 데도 많은 계산을 해야합니다. 또한 위와 같은 작은 Grid World 같은 경우는 괜찮지만 state 숫자가 늘어날수록 계산량이 기하급수적으로 증가하기 때문에 MDP가 상당히 크거나 MDP에 대해서 다 알지 못할 때는 DP를 적용시킬 수 없습니다. 따라서 이를 보완하여, trial and error를 겪으며 sample backup(모든 가능한 successor state와 action을 고려하는 것이 아니고 sampling을 통해서 한 길만 가보고 그 정보를 토대로 value function을 update하는 것)을 하자는 것이 강화학습이고 다음에는 근간이 되는 Monte-carlo method, Temporal difference method에 대해 다루겠습니다.