[강화학습] Monte-Carlo Methods

Model-Free

이전 포스팅에서 Dynamic Programming, policy iteration과 value iteration에 대해 알아보았습니다. Dynamic programming은 Bellman Equation을 통해서 optimal한 해를 찾아내는 방법으로서 MDP에 대한 모든 정보를 가진 상태에서 문제를 풀어나가는 방법입니다. 특히 environment의 MDP인 reward function과 state transition probabilities를 알아야하기 때문에 Model-based한 방법이라고 할 수 있습니다. 이러한 방법에는 아래과 같은 문제점이 있습니다.

• Full-width Backup ⇒ expensive computation
• Full knowledge about Environment

하지만 DP는 우리가 Machine Learning에서 다루는 Learning이 아니라 Planning입니다. 따라서, 계산 복잡도가 state의 크기 3제곱에 비례하기때문에 grid world보다 차원의 크기도 크고 state가 무수히 많은 실제 문제와 적용하기에는 많은 한계가 있습니다. 이를 보완한 것이, environment의 MDP을 몰라도 trial and error를 시행해보며 environment와 상호작용을 통해 알아가는 강화학습입니다. environment로부터 MDP을 learning하는 것입니다. 그래서 강화학습은 full-width backup이 아닌 sample backup입니다. sample backup은 이어지는 모든 state들을 고려하지 않고 그 중에서 sampling을 통해 한 길만 선택해서 가보는 것입니다. 그리고 이를 통해 value function을 update하게 됩니다. 이렇게 실제로 경험한 정보들을 사용함으로서 처음부터 environment에 대해서 모든 것을 알 필요가 없습니다. Environment의 MDP을 모르고 학습하기 때문에 Model-free라는 말이 붙게 됩니다.

 

현재의 policy로 value function을 sample backup으로 구하는 prediction과 이를 통해 policy를 update하는 control이 있습니다. 이렇게 Sampling을 통해서 학습하는 model-free 방법에는 다음 두 가지가 있습니다.

1. Monte-Carlo
2. Temporal Difference

Monte-Carlo는 episode마다 update하는 방법이고 Temporal Difference는 time step마다 update하는 방법입니다.

Monte-Carlo Approximation

Monte-Carlo의 기본적인 concept을 이해하기 위해 이 방법으로 원주율을 구하는 예제를 먼저 설명하겠습니다.

1. (0,0), (0,1), (1,0), (1,1) 로 이루어진 좌표 상에 임의의 점 (x, y)를 sampling한다.
2. sampling한 점이 중심이 (0,0)이고 반지름이 1인 사분원 내에 속하는 점인지를 판단한다.
3. 이 과정을 충분히 반복한다.

Estimate 𝜋 by Monte-Carlo Approximation

Indicate function, I는 주어진 조건이 만족하면 1, 아니면 0을 반환하는 함수입니다. Monte-Carlo의 핵심은 "추정하고 싶은 값을 random sampling을 통해 근사한다" 정도로 이해하면 충분합니다.

import random

def estimate_pi(n):
    points_inside_circle = 0
    points_inside_square = 0

    for _ in range(n):
        x = random.uniform(0, 1)
        y = random.uniform(0, 1)
        distance = x**2 + y**2

        if distance <= 1:
            points_inside_circle += 1
        points_inside_square += 1

    pi = 4 * (points_inside_circle / points_inside_square)
    return pi

# 시뮬레이션 횟수 설정
num_simulations = 1000000

# 원주율 추정
estimated_pi = estimate_pi(num_simulations)

print("Estimated Pi:", estimated_pi)

위 코드로 간단하게 테스트 해볼 수 있습니다.

생성된 점들 중 사분원 내부에 위치한 점들의 비율을 구하고 이를 원의 넓이와 정사각형의 넓이의 비로 해석합니다. 즉 원의 넓이와 정사각형의 넓이의 비는 사분원 내부에 위치한 점들과 sampling한 점의 수의 비와 같다는 점입니다. 따라서 다음과 같은 수식으로 𝜋를 구할 수 있습니다. pi = 4 * (points_inside_circle / points_inside_square)

Monte-Carlo Prediction

Model-Free 방법에는 Monte-Carlo 방법과 Temporal difference 방법이 있음을 언급했습니다. 이 둘의 가장 큰 차이는 value function을 estimate하는 방법입니다. MC는 episode가 끝날 때 마다, 즉, state sampling 결과 선택된 state들을 끝까지 가보고 update를 합니다. TD는 time-step마다 한 단계씩 update합니다. 이렇게되면 Monte-Carlo 방법은 terminal state까지 step별로 얻은 reward를 모두 저장하고나서 terminal state에서는 이를 바탕으로 state들의 value function들을 구하게 됩니다. 이렇게 Monte-Carlo 방법으로 true value function을 얻는 과정을 Monte-Carlo Prediction이라고 합니다.

value function을 얻을 때 agent는 sampling한 state를 골라가며 terminal state까지 갑니다. 그리고 이때 받은 reward들을 저장해두었다가 이를 시간 순서대로 discounting한 것이 바로 value function입니다. DP에서는 이를 Bellman equation으로 구했고 계산 가능한 형태로 바꾸어 풀었는데, Monte-Carlo 방법에서는 이 reward들의 합(discounted)의 평균으로 value function을 근사하게 됩니다. 우리는 MDP를 다룰 때, 미래에 받을 reward들을 현재 가치로 discounting하여 모두 더한 값을 return이라고 정의했습니다. 또한, value function은 state s에서의 return의 기댓값이라고 정의했습니다. Monte-Carlo prediction은 multiple episodes를 마치고 얻은 return들의 평균값으로 value function를 근사하고 이를 반복해서 true value function을 찾자는 아이디어입니다.

이를 식으로 나타내면 다음과 같습니다.

N(s): total episode동안 state s를 방문한 횟수

G(s): episode i에서 state s의 return 값

Incremental mean

위의 평균을 취하는 식을 좀 더 발전시켜보면 다음과 같습니다. 저희가 학습하는 방법은 여러개를 모아놓고 한 번에 평균을 취하는 것이 아니고 하나 하나 더해가며 평균을 계산하기 때문에 아래와 같은 Incremental mean의 식으로 표현할 수 있습니다.

Incremental mean

Incremental mean과 같은 방식으로 아래와 같이 수식을 변형할 수 있습니다.

이 식은 새로운 return 값을 받았을 때, Vn에서 Vn+1로 value function을 update하는 방법을 나타냅니다. 이렇게 return값을 모두 모으고 한번에 평균을 내는 것이 아니라 새로운 return값을 얻을 때마다 update 할 수 있습니다.

N(St)를 α로 고정시키는 것은 각 state의 중요도를 동일하게 취급하기 위한 목적이 있습니다. 각 state의 value function estimation에 동등한 weight를 부여하여 불필요한 bias를 피할 수 있는 효과를 가지게 됩니다. 이는 보다 정확하고 일반화된 value function estimation을 가능하게 합니다. 이와 같이 하는 이유는 강화학습이 stationary problem이 아니기 때문입니다. 매 episode마다 새로운 policy를 사용하기 때문에(아직 policy의 update에 대해서는 이야기하지 않았습니다) non-stationary problem이므로 update하는 상수를 일정하게 고정하는 것입니다.

위의 업데이트 과정에서, 한 episode 내에서 같은 state를 두 번 이상 방문할 경우, 첫 방문 시의 return 값을 고려할 것인지 방문할 때마다 생긴 모든 return 값을 고려할 것인지에 따라 first-vist MC와 Every visit MC로 나뉩니다.

Backup Diagram

Dynamic Programming Approach(좌), Monte-Carlo Approach(우)

Monte-Carlo는 처음에 random process를 포함한 방법이라고 말했었는데 episode마다 update하기 때문에 처음 시작이 어디었냐에 따라서 또한 같은 state에서 왼쪽으로 가냐, 오른 쪽으로 가냐에 따라서 전혀 다른 experience가 됩니다. 이러한 random한 요소를 포함하고 있어서 MC는 variance가 높습니다. 대신에 random인 만큼 bias는 낮은 편입니다.

Monte-Carlo Control

DP에서 Policy Iteration은 policy evaluation과 (greedy)policy improvement로 나누어집니다. 여기서 policy evaluation에 MC를 이용하면 Monte-Carlo policy Iteration이 됩니다. (Monte-Carlo Policy Evaluation = Prediction)

• Policy Iteration = policy evaluation + policy improvement
• Monte-Carlo Policy Iteration = MC policy evaluation + policy improvement

하지만 MC policy Iteration은 다음과 같은 문제점들이 존재하는데, 이를 해결한 것이 Monte-Carlo Control입니다.

1.  Value function
2.  Local optimum

Value function

MC로 policy evaluation을 하는 부분에서 value function을 이용합니다. MC를 이용하는 것은 model-free의 속성을 이용하기 위해 도입했지만 value function을 사용하게 되면 policy를 improve할 때, 아래의 bellman equation(q-function)을 이용해야 하기 때문에 reward와 transition probability 등 MDP를 알아야만 합니다.

따라서, value function 대신에 q-function을 이용하면 이를 해결할 수 있습니다. 근데 q-function의 식에 MDP가 있어서, 이 말이 이해가 안가실 수도 있는데 이렇게 생각해보겠습니다.

 

return이 아닌 agent가 episode마다 random하게 움직이며 얻은 reward들 그리고 transition probability를 통해서

q-function을 계산할 수 있습니다. 이렇게 되면 policy를 improve할 때, MDP를 굳이 알지 못해도 이미 전 과정에서

q-function을 이용함으로써 MDP의 정보가 다 담겨있습니다. 따라서 improve할 때는 이를 선택만 해주면 되는 문제이므로 MDP를 몰라도 improve할 수 있습니다. 정리하자면 model-free하다는 개념은 policy를 improve할 때의 관점이고,

q-function 자체는 MDP를 알아야지만 구할 수 있는 것은 맞습니다. 다만 trial and error의 과정 속에서 모든 정보가

q-function에 담겨있으므로 policy improvement의 과정에서는 model-free합니다.

 

Local Optimum

현재는 policy improve는 greedy policy improvement를 사용하고 있습니다. 하지만 계속 현재 상황에서 최고의 것만 보고 판단을 할 경우에는 optimal로 가는 것이 아니고 local optimum에 빠져버릴 수가 있습니다. 충분히 exploration을 하지 않았기 때문에 global optimum에 가지 못했던 것입니다. 현재 action a가 가장 높은 value function을 가진다고 측정이 되어서 action을 a만 하면 사실은 b가 더 높은 value function을 가질 수도 있는 가능성을 배제해버리게 됩니다. 따라서 그에 따른 대안으로서 일정 확률로 현재 상태에서 가장 높은 value를 가지지 않은 다른 action을 하도록 합니다. 그 일정 확률을 ε(epsilon)이라 하며, 그러한 improve 방법을 ε-greedy policy improvement라고 합니다. 이로써 부족했던 exploration을 할 수 있게 된 것 입니다.

ε을 0.1이라고 한다면, policy는 90%의 확률로 q-function 값이 가장 높은 action을 선택할 것이고, 나머지 10%의 확률로 여러 action중 random하게 하나의 action을 선택합니다. 즉, 10%의 확률로 다양한 action을 해보면서도 90%의 확률로 가장 좋은 action을 선택합니다. greedy하면서도 어느 정도 exploration을 보장해주는 알고리즘인 것입니다.

 

여기서 조금 더 좋은 방법론은 ε의 값을 처음에는 높게 하다가 점점 줄여주는 것입니다. 처음에는 아무래도 environment에 대해 아는 것이 없기 때문에 다양한 action들을 선택하면서 environment에 대한 정보를 충분히 얻어야 하고, 학습이 어느정도 진행되고 나면 이미 얻은 정보를 바탕으로 조금 더 optimal action을 선택하는데에 집중합니다. 이런 방법론을 줄여 나간다는 단어인 decay라는 단어를 이용하여 decaying e-greedy라고 부릅니다.

 

Reference

[1] "바닥부터 배우는 강화학습", http://www.yes24.com/Product/Goods/92337949

[2] https://dnddnjs.gitbooks.io/rl 

[3] https://sumniya.tistory.com/11?category=781573