DEVOCEAN

오늘은 Leetcode 문제 322.Coin Change 문제를 강화학습 알고리즘을 통해 해결해나가면서 강화학습의 기초를 학습해볼까 합니다.

[1] 문제 설명

Coin Change 문제는 정해진 금액을 만들기 위해 가장 작은 횟수로 동전의 조합을 찾아야 하고 이 횟수를 return하는 문제입니다.

이 문제를 해결하기 전 강화학습의 이론을 살펴보겠습니다.

[2] 강화학습 정의

강화학습는 환경과 Agent가 상호작용해나가면서 최적의 의사결정을 하는 프레임워크입니다. 이러한 방식은 위 강화학습 프로세스에 의해 설명이 될 수 있습니다.

• Agent는 Enviroment로부터 최초 State를 부여받습니다.

• Agent는 State를 Input값으로 받고 Action을 Output으로 생성하게 됩니다.

• Enviroment는 Action 값을 Input값으로 받고 Next State와 Reward를 생성하게 됩니다.

• Next State와 Reward는 다시 Agent Input 값으로 들어가게 되고 이를 기반으로 Agent는 Q-Value를 Update하고 다음 Action을 취하게 됩니다.

  
  

그러면 위 프로세스를 통해서 어떻게 최적의 의사결정을 내릴 수 있을까요?

이는 State상태에서 다양한 Action을 반복해나가면서 Reward를 받고 이를 기반으로 해당 State에서 Action이 얼마나 좋았는지를 판단하기 때문입니다.

얼마나 좋았는지를 수치화하여 표현한 값을 강화학습에서는 Q(Quality) Value라고 표현합니다.Q-Function은 State와 Action을 Input값으로 받아 이 Q-Value를 산출해 줍니다.

Q-Function은 여러 강화학습 방법론에 따라 Table형태, Neural Net 형태 등 다양한 형태로 나타나게 됩니다.

이 글에서는 가장 간단한 방식인 Table 형태를 취하여 Q-Learning 알고리즘으로 해결해보겠습니다.

Q-learnnig에서는 위 Q-Function을 Table형태로 구현하여 메모리에 관리하게 됩니다.

Agent는 이 State가 주어졌을때 이 Q-Table을 참조하여 최적 Action을 선택하게 됩니다.

[3] Q-Learning 기반 문제 접근

강화학습에서의 모델링은 MDP(Markov decision process) 구조를 정의하는 작업으로 보시면 됩니다.

이러한 모델링을 잘 하는 것이 사실 소스 개발을 하는 것보다 더 중요한 요소라고 볼 수 있습니다.

MDP를 정의한다는 것은 State,Action,Reward를 정의하는 과정으로 보시면 되겠습니다.

저는 이 문제에서는 위 3가지 요소를 아래와 같이 정의하였습니다.

1. State : Target 값 - 내가 현재까지 선택한 Coin값의 합

2. Action : 선택가능한 Coin 중 하나를 선택하는 것

3. Reward : Target 값 도달시 +20 점 부여. 단 State가 전이시 -1점을 부여하여 최소의 선택횟수로 조합을 만들도록 유도함

이를 기반으로 구성한 소스 구조는 아래와 같습니다.

[3-1] Agent 정의

아래 코드에서는 Agent를 정의합니다.

Agent에서는 학습을 위한 기본 정보인 Target 정보 그리고 사용 가능한 Coin List를 입력받아 객체로 생성하게 됩니다. 또한 위에서 정의한 Reward를 산출하는 함수를 구성하였습니다.

class Agent:
    def __init__(self, target_amount, coins, epsilon=0.1, learning_rate=0.1, discount_factor=0.9):
        self.Q = np.zeros((target_amount + 1, len(coins)))
        self.epsilon = epsilon
        self.actions = coins
        self.learning_rate = learning_rate
        self.discount_factor = discount_factor
        self.target = target_amount
        self.coins = coins

    def get_reward(self, remaining_target):
        reward = -1
        if remaining_target == 0:
            reward += 20
        return reward

[3-2] Simulator 정의

Q-Table를 Update해나가기 위한 Simulator와 Update된 Q-Table을 참조하여 최적 Policy를 생성하는 함수를 추가로 구성합니다.

Simulator함수에서는 epsilon-greedy 방식을 통해 Exploitation과 Exploration을 이용하여 탐색해나갑니다.

random 변수에 의해 생성된 값이 지정한 epsilon보다 작은 경우 Exploration 통해 새로운 시도를 하게 되고 아닌 경우 Exploitation 방식으로 Greedy Action을 취하게 됩니다.

이 과정을 통해 Agent는 다양한 경험을 쌓게 됩니다.

그러면 이 경험을 Q-Table에 기록을 해줘야 하는데요. 이는 Bellman Equation을 활용한 귀납적 형태를 통해 계산해나가게 됩니다.

Bellman 방정식의 기본 구조는 아래와 같습니다.

이 구조를 자세히 보시면 New Q Value는 현재의 Q Value와 보상값 그리고 다음 상태에서의 max Q-Value를 활용하여 Update하게 됩니다.

이 Bellman Equation은 수식적으로 중요한 의미를 갖지만 수식없이 의미적으로 심플하게 정의해본다면 1) 귀납적 형태 2) 수렴성 크게 2가지의 유용성을 가집니다.

귀납적 형태를 통해 우리는 현재 Step과 다음 Step만 고려해서 연산을 함으로써 연산량에서 이점을 확보하게 됩니다.

그리고 0~1 사이의 Discount Rate를 반영한 보상을 더해나감으로써 Q-Value는 수렴하게 되어 궁극적으로는 학습이 가능하게 됩니다.

    def simulator(self, iterations=80):
        total_rewards = []
        for iteration in range(iterations):
            total_reward = 0
            state = self.target
            remaining_target = state
            while state != 0:
                if np.random.rand() < self.epsilon:
                    action = np.random.choice(len(self.actions))
                else:
                    action = np.argmax(self.Q[state])
                remaining_target -= self.coins[action]
                if remaining_target < 0:
                    break
                reward = self.get_reward(remaining_target)

                next_state = remaining_target

                td_error = reward + self.discount_factor * (
                        np.max(self.Q[next_state]) - self.Q[state, action])

                self.Q[state, action] += self.learning_rate * td_error

                total_reward += reward
                state = remaining_target

            total_rewards.append(total_reward)

        return self.best_policy()

    def best_policy(self):
        policy = {}
        for i in range(self.target + 1):
            policy[i] = np.argmax(self.Q[i])
        return policy        

[3-3] 추론

마지막으로 학습된 최적 Policy 기반으로 문제를 풀어보겠습니다.

Agent 객체를 생성한 후 simulator를 통해 학습 및 최적 Policy를 Return하게 됩니다.

coin별 여러 시작점을 선정하여 가장 최소의 횟수로 target 수량을 만족하는 조합을 탐색하게 됩니다.

coins = [1,2,5]
target_amount = 13

agent = Agent(target_amount, coins)
policy = agent.simulator()
#print(policy)
min_coins_used = float('inf')
for coin in coins:
    comb = search(policy, coin, target_amount, coins)
    if comb :
        if sum(comb ) == target_amount:
            min_coins_used = min(min_coins_used, len(path))
print("Minimum coins required:", min_coins_used)

[4] 마무리

Coin이 [1,2,5]로 주어졌을때 13값을 만드려면 최소의 횟수는 5,5,2,1로 4회면 가능합니다.

위 강화학습 코드 수행시 결과를 확인해보겠습니다.

5회 정도 학습시에는 첫번째 그림처럼 값을 6으로 잘못 계산하였습니다.

하지만 반복횟수를 50회 정도로 늘리니 정상적으로 4를 Return하고 있습니다.

오늘은 LeetCode 문제 중 Coin Change 문제를 강화학습으로 풀면서 강화학습 알고리즘의 기본 구조에 대해 학습하였습니다.

오늘 다룬 Q-Learning은 아직 빙산의 일각이고 이외 DQN,A3C,PPO 등 다양한 알고리즘이 많이 있습니다.

앞으로 이런 항목들을 추가적으로 다뤄나갈까 합니다.

저도 새롭게 공부하는 분야라 혹시나 부족할 수 있지만 이 글이 강화학습을 학습해보고자 하시는 초심자분들이 도움이 되면 좋겠습니다.

긴 글 읽어주셔서 감사합니다.

출처

1.https://dnddnjs.gitbooks.io/rl/content/numerical_methods.html

2.https://huggingface.co/learn/deep-rl-course/unit2/introduction