[2025-2] 이루가 - A review of Q-learning methods for Markov decision processes

논문 링크: https://www.diva-portal.org/smash/record.jsf?pid=diva2%3A1877676&dswid=-1399

0. Abstract

연구 목적

상태-행동 문제(state-action problem)를 Markov Decision Process(MDP)로 모델링하고, Q-Learning과 Deep Q-Network(DQN)을 적용하여 최적 정책(optimal policy)을 찾는 방법을 탐구한다.

연구 방법

Q-Learning과 DQN 알고리즘을 각각 단순한 문제와 복잡한 문제에 적용하여 성능을 비교하고 각 알고리즘의 장점과 한계를 분석한다.

주요 결과

Q-Learning은 단순한 문제에서는 최적 정책을 성공적으로 찾았으나, 상태 공간이 사실상 무한한 복잡한 문제에서는 실패했다. 알고리즘이 단순하여 동작 원리를 이해하기 쉽다는 장점이 있다.
DQN은 단순 문제와 복잡한 문제 모두 해결 가능했으나, 내부 동작이 복잡하여 해석하기 어렵다는 단점이 있다.

1. Introduction

1.1. Background

Deep Q-Networks(DQN)에 대한 이해가 필요하다. Q-Learning과 DQN은 모두 마르코프 모델(Markov model)과 기대값 극대화(maximizing expected values)에 기반한 통계적 모델이다.

Q-Learning의 원리를 이해하는 것은 DQN을 배우는 데 기초가 된다. 단순한 상태-행동 문제를 Q-Learning으로 해결하는 과정을 통해 기본 지식을 쌓고, 이를 DQN으로 확장하여 동일 문제를 해결함으로써 두 방법 사이의 연결 고리를 제시한다. 이 과정은 DQN이 같은 문제에 어떻게 적용될 수 있는지를 보여주며, Q-Learning은 단순하지만 확장성이 떨어진다는 점을 대비시킨다.

1.2. Limitations

이 논문은 Q-Learning과 DQN만을 다루며, Double Q-Learning, Multi-agent Learning 등 관련 기법은 논의하지 않는다. 또한 두 가지 문제 상황에 대해서만 비교하는 한계를 갖는다. 두 문제는 이해하기 쉬운 수준이지만, 각 방법의 장단점을 보여주는 지표로는 충분하다.

1.3. Purpose

지난 10여 년간 기계학습(Machine Learning)은 크게 발전하여 사회 전반의 다양한 영역에서 활용되고 있다. 본 논문은 Q-Learning의 활용 방식과 그 한계를 보여줌으로써, 기계학습이 무엇이며 어디에 쓰일 수 있는지에 대한 이해를 제공하는 것을 목표로 한다.

2. Theory

2.1. Markov Decision Process

정의
MDP는 다음과 같은 4-튜플로 정의된다:

S+: 가능한 모든 상태(state)의 집합, 즉 상태 공간(state space).
A: 가능한 모든 행동(action)의 집합, 즉 행동 공간(action space). 상태에 따라 가능한 행동의 집합 As가 다를 수 있다.
Pa(s, s′): 상태 s에서 행동 a를 취했을 때, 다음 상태가 s′로 전이될 확률.
Ra(s, s′): 상태 s에서 행동 a를 통해 s′로 전이했을 때 얻는 즉각적인 보상.

정책 함수(policy function) π는 상태 공간 S에서 행동 공간 A로의 매핑으로, 각 상태에서 취할 행동을 결정한다.

예시

체스판에서 특정 위치 (e,4)가 하나의 상태로 정의될 수 있다.
날씨 문제에서는 (온도, 바람 세기, 맑음 여부)와 같은 변수를 묶어 하나의 상태로 표현할 수 있다.

특징

MDP는 단순한 마르코프 체인(Markov Chain)과 달리, 각 상태에서 다양한 행동을 선택할 수 있다.
어떤 상태 s에서 가능한 행동의 개수는 |As|로 표현되며, 각 행동은 다른 상태로 전이될 확률 Pa(s, s′)을 가진다.
또한, MDP에는 보상 함수 R(s,a,s′)가 포함되어 있어, 상태 전이에 따른 보상을 정의한다.
이러한 구조 덕분에 에이전트는 단순히 상태에 의존하지 않고, 자신의 행동을 통해 미래 상태 전이에 영향을 줄 수 있다.

2.2. Q-learning

개념
Q-Learning은 특정 상태(state)에서 특정 행동(action)을 선택했을 때 얻는 보상의 기대값을 학습하는 방법이다. 이를 Q-행렬(Q-matrix)로 표현할 수 있는데, 행은 상태를, 열은 행동을 나타내며, 각 원소는 상태-행동 쌍(state-action pair)의 가치를 의미한다.

훈련이 완료되면, 각 상태에서 가장 큰 기대 보상을 주는 행동을 선택하여 최적 정책(π*)을 얻는다. 이 정책은 각 단계에서 가장 높은 Q-value를 선택하는 탐욕적(greedy) 정책이다.

수학적 기초

Q-Learning은 유한한 MDP의 경우, 무한 반복(iterations)과 적절한 무작위성(randomness)을 포함하면 최적 정책을 보장한다.

핵심은 벨만 방정식(Bellman Equation)이다:

이를 Q-Learning에 적용하면 Q값 업데이트 식은 다음과 같다:

학습률 α의 의미

α = 0 → 새로운 정보 반영 없음 (Q값 그대로 유지)
α = 1 → 새로운 정보만 반영 (기존 정보 무시)

탐험과 활용 (Exploration vs Exploitation)
Q-Learning은 최적 정책에 수렴하기 위해 무작위성을 필요로 한다. 이를 위해 ε-탐욕적 정책(Epsilon-greedy policy)을 사용한다.

확률 ε → 무작위 행동 선택 (탐험, exploration)
확률 1−ε → 가장 큰 Q값을 주는 행동 선택 (활용, exploitation)

즉, 새로운 상태를 탐색하며 장기적으로 더 나은 정책을 찾는 과정과, 이미 알려진 최적 행동을 선택해 보상을 극대화하는 과정의 균형을 맞춘다.

2.3. Deep Q-Networks

개념
Deep Q-Networks(DQN)은 2013년에 제안된 방법으로, 신경망(Neural Network)을 이용해 상태-행동 쌍의 Q값을 근사한다. 이 Q값은 특정 상태에서 행동을 취하고 이후 최적 정책(탐욕 정책, greedy policy)을 따른다고 가정했을 때의 누적 기대 보상(cumulative expected reward)을 의미한다.

신경망 구조는 입력층, 여러 개의 은닉층, 출력층으로 구성된다. 각 노드는 가중치(weight)로 연결되어 있으며, 이 가중치는 출력에 영향을 미친다.

경험 리플레이 (Replay Memory)

훈련 전, 게임에서 얻은 관측값을 경험 et = (st, at, rt, st+1) 형태로 저장한다.
훈련 시에는 이 경험에서 무작위 샘플을 뽑아 사용한다.
무작위성은 데이터 간의 상관관계를 줄여 훈련의 안정성을 높인다.

Q값 추정

예측값 QPredict(s,a,θt): 신경망이 현재 시점 t에서 특정 상태 s와 행동 a에 대해 산출한 기대 보상 추정치.
관측값 QObserved(s,a): 실제 보상과 다음 상태의 최대 Q값을 기반으로 계산한 더 정확한 값.

관측값은 벨만 방정식으로 정의된다:

손실 함수와 최적화

손실 함수(Loss)는 MSE (Mean Squared Error)로 정의된다:

가중치 업데이트는 확률적 경사하강법(SGD)을 사용한다:

신경망 동작

입력층: 상태(state) 표현을 입력으로 받는다.
출력층: 각 가능한 행동(action)에 대한 Q값을 출력한다.
각 노드는 바이어스(bias) 항을 가질 수 있으며, 비선형 활성화 함수(non-linear activation function)를 통해 상태와 행동 간의 복잡한 관계를 학습할 수 있다.

3. Methods

3.1. Lava game

환경 설정

게임 보드는 4x4 격자(grid)로 이루어져 있다.
각 상태(state)는 s=(x,y)s = (x,y)로 표시되며, 좌상단은 (1,1), 우하단은 (4,4)이다.
오른쪽 끝선 x=4에 도달하면 보상을 얻고, 아래쪽 끝선 y=4에 도달하면 ‘용암(lava)’으로 간주되어 패널티를 받는다.

행동(Action) 정의

- stay: 게임을 종료하고 보상 −1을 받음.
- move: 상태 (x,y)에서 확률적으로 이동
  가능한 행동: As = {stay, move}
  - (x+1,y+1) → 확률 0.5
  - 즉, 오른쪽으로 이동하거나 대각선(오른쪽+아래)으로 이동

보상 함수 (Reward Function)

상태 공간 (State Space)

전이 확률 (Transition Probability)

의도
이 게임은 불확실성 속에서 최적의 의사결정을 학습하기 위한 단순하지만 직관적인 MDP 환경이다. Q-Learning 알고리즘을 실험하고, 탐험(exploration)과 활용(exploitation)의 균형을 통해 최적 정책을 학습하는 과정을 이해하는 데 유용하다.

3.1.1. Analytic solution of Lava game

분석적 해법의 필요성
Q-Learning의 결과를 평가하기 위해, 간단한 Lava 게임에 대한 분석적 최적 해(solution)를 도출한다.

stay를 선택하면 항상 보상은 −1이다. (게임이 종료되고 추가 보상이 없음)
move를 선택하면 벨만 방정식에 따라 계산된다. 이동 후 도달 가능한 상태들의 확률과 그 상태의 기대 보상을 합산하여 구한다.

해법 과정

게임의 종결 상태(terminal states)로부터 역추적(backward induction)하여 각 상태에서의 최적 행동을 결정한다.
각 상태에서 move를 선택하면:
- 0.5 확률로 오른쪽으로 이동
- 0.5 확률로 오른쪽+아래 대각선 이동
따라서 기대 보상은
만약 move의 기대 보상이 −1보다 작다면, stay를 선택하는 것이 최적이다.
따라서 각 상태에서의 최적 행동은
으로 결정

기대 보상 행렬 (Expected Rewards)

위 행렬에서 값이 클수록 그 상태에서의 기대 보상이 크다는 의미다.
−1인 경우에는 stay가 최적 행동이 된다.

최적 정책 (Optimal Policy)

즉, 대부분의 상태에서는 move가 최적 행동이지만, 용암 지역으로 떨어질 위험이 큰 일부 상태에서는 stay가 더 나은 선택이 된다.

3.2. Cart pole game

환경 설명
Cart Pole 게임은 수레(cart) 위에 막대기(pole)를 세워 균형을 유지하는 고전적인 강화학습 환경이다.

에이전트(agent)는 왼쪽(left) 또는 오른쪽(right)으로 일정한 힘을 가하는 두 가지 행동 중 하나를 선택할 수 있다.
수레의 수평 움직임은 직접적으로, 막대기의 각도 변화는 간접적으로 영향을 받는다.
막대기는 무작위 초기 각도에서 시작하며, 초기 속도는 없다.
이 환경은 Barto, Sutton, Anderson의 고전 논문 “Neuronlike Adaptive Elements That Can Solve Difficult Learning Control Problem” [8]에 기반한다.
구현은 Python의 Gymnasium 라이브러리 [9]를 통해 이루어진다.

시간 구조와 상태 정의

시간은 이산적 간격(discrete time steps)으로 나뉜다.
매 시점마다 시스템의 상태(state)가 평가되고, 에이전트는 그 상태를 바탕으로 행동(action)을 선택한다.
게임의 상태는 네 가지 변수로 정의된다:

수레의 위치 (cart position)
수레의 속도 (cart velocity)
막대기의 각도 (pole angle)
막대기의 각속도 (pole angular velocity)

이 네 가지 값이 결합되어 현재 시스템의 동적 상태를 설명한다.

에피소드 종료 조건 (Terminal States)
게임의 한 에피소드는 다음 두 조건 중 하나가 충족되면 종료된다.

막대기의 각도가 수직에서 크게 벗어날 경우 → 막대기가 쓰러짐을 의미
500 스텝(time steps) 제한에 도달할 경우

보상 구조 (Reward Structure)

막대기가 쓰러지지 않고 유지되는 매 시점마다 보상 +1을 받는다.
목표는 누적 보상(cumulative reward)을 최대화하는 것, 즉 막대기를 가능한 오래 세워두는 것이다.
이 단순한 보상 체계는 에이전트가 균형을 오래 유지할수록 더 나은 정책을 학습하도록 유도한다.

3.3. Implementing Q-learning

구현 환경

Lava Game은 Python 3.9.7로 구현

Q-행렬 초기화

Q-행렬(Q-matrix)은 상태-행동 쌍에 대한 값을 [0,1] 사이의 임의의 값으로 초기화한다.
종결 상태(terminal state)에서는 Q값을 항상 0으로 설정한다.

훈련 과정 (Training Process)

학습은 Q-행렬을 반복적으로 갱신하여, 각 상태에서 행동을 선택했을 때의 기대 보상(expected reward)을 근사하는 과정이다.
한 번의 학습 반복(iteration):

무작위 초기 상태에서 시작
행동을 선택하면서 진행
종결 상태에 도달하면 반복 종료

초기 상태는 9개의 가능한 비종결 상태(non-terminal states) 중에서 무작위로 선택된다.
이 방식은 모든 상태-행동 쌍이 유사한 빈도로 학습되도록 보장한다.
학습은 정해진 횟수(iterations)만큼 반복된다.

종결 상태 정의

게임에서 종결 상태는 다음 세 가지 상황이다:
오른쪽 끝에 도달한 경우
맨 아래(용암)에 도달한 경우
행동 stay를 선택한 이후의 상태
마지막 경우가 중요한데, 이 때문에 Q값 갱신 식(2.2)을 약간 수정해야 한다.

Q값 업데이트 식 (수정된 형태)

3.4. Implementing Deep Q-Networks

구현 환경

DQN은 Python 라이브러리 PyTorch를 사용하여 구현되었다.
PyTorch의 공식 문서와 튜토리얼을 참고해 DQN의 주요 구조를 작성하였다.

구현 구조

DQN의 기본 구조는 두 게임(Lava Game, Cart Pole Game)에서 동일하다.
차이는 훈련 시 상호작용하는 환경(environment)에서 발생한다.

Lava Game: 단순한 격자 기반의 MDP 환경
Cart Pole: 연속적인 상태 변수를 가진 동적 환경

즉, DQN의 신경망 구조 자체는 그대로 유지되지만, 입력(state representation)과 보상 구조가 환경에 따라 달라진다.

3.4.1. Lava game

구현 방식

Lava Game을 위해 Python 클래스(class)가 작성되어, DQN 학습 코드가 해당 환경과 상호작용하도록 설계되었다.
PyTorch 튜토리얼의 기본 구조를 참고해 DQN 학습을 적용하였다.

튜토리얼 코드와의 주요 차이점

최적화 함수 변경
- 원래 PyTorch 튜토리얼은 AdamW Optimizer를 사용.
- 본 구현에서는 Stochastic Gradient Descent (SGD)를 사용.
- 논문에서는 이 변경에 대한 자세한 논의는 다루지 않았다.
손실 함수 변경
- 원래 튜토리얼: torch.nn.SmoothL1Loss()
- 본 구현: 평균제곱오차(MSE, Mean Squared Error) - torch.nn.MSELoss()

즉, Lava Game에 맞게 PyTorch 튜토리얼의 구조를 유지하되, 최적화 함수와 손실 함수만 변경하여 실험을 진행한 것이다.

3.4.2. Cart Pole

구현 방식

Cart Pole 게임은 PyTorch 튜토리얼 [10]에서 사용된 동일한 예제 환경이다.
따라서 구현 방식은 튜토리얼 코드와 거의 동일하다.
차이점은 앞서 3.4에서 언급된 변경 사항과 동일하다:

최적화 함수: AdamW → SGD
손실 함수: SmoothL1Loss → MSELoss

즉, Cart Pole 구현은 PyTorch 예제를 거의 그대로 따르되, Lava Game과 동일하게 SGD + MSELoss 조합을 적용했다.

4. Results and Analysis

4.1. Results

4.1.1. Q-learning: Lava game

Q-Learning 행렬

상태-행동 집합 A\mathcal{A}: 각 상태에서 가능한 행동은 (stay,move)
학습된 Q-값 행렬 Q:

각 항목은 (Q(stay),Q(move))를 의미한다.

도출된 최적 정책 π*

최적 행동(가장 큰 Q값을 선택한 결과):

대부분의 상태에서 move가 최적 행동으로 선택되었다.
용암 지역(하단)에 가까운 일부 상태에서는 기대 보상이 낮아 stay가 더 안전한 선택으로 나타났다.
이는 분석적 해법(3.1.1)과도 유사한 경향을 보여준다.

4.1.2. DQN: Lava game

DQN 학습 결과

DQN은 각 상태를 입력받아, 가능한 행동의 기대 보상 값을 출력한다.
학습 후 각 상태-행동 쌍의 기대 보상(Q값)이 테이블에 저장된다.
아래 그래프는 최근 100게임의 평균 보상 변화를 보여주며, 학습이 진행됨에 따라 점차 안정화되는 모습을 확인할 수 있다.

상태-행동 집합

Q값 (학습률 α=10^(-3))