파이썬과 케라스로 배우는 강화학습 | 강화학습 기초 6
파이썬과 케라스로 배우는 강화학습 Chapter 3 정리
책 정보 📖
- 책 제목: 파이썬과 케라스로 배우는 강화학습
- 글쓴이: 이웅원, 양혁렬, 김건우, 이영무, 이의령
- 출판사: 위키북스
- 발행일: 2020년 04월 07일
- 챕터: Chapter 3. 강화학습 기초 2 : 그리드월드와 다이내믹 프로그래밍
책소개
강화학습의 기초부터 최근 알고리즘까지 친절하게 설명합니다! ‘알파고’로부터 받은 신선한 충격으로 많은 사람들이 강화학습에 관심을 가지기 시작했다. 하지만 처음 강화학습을 공부하는 분들을 위한 쉬운 자료나 강의를 찾아보기 어려웠다. 외국 강의를 통해 어렵게 이론을 공부하더라도 강화학습을 구현하는 데는 또 다른 장벽이 있었다. 이 책은 강화학습을 처음 공부하는 데 어려움을 겪는 독자를 위해 이론부터 코드 구현까지의 가이드를 제시한다.
특히 이번 개정판에서는 텐서플로 버전업에 맞춰서 코드를 업데이트하고 전반적인 이론 및 코드 설명을 개선했다. 그리고 실무에서 많이 활용될 수 있는 연속적 액터-크리틱 알고리즘을 추가했다.
주요 내용
강화학습의 기초 - 다이내믹 프로그래밍, 가치 이터레이션, 가치 이터레이션 예제, 다이내믹 프로그래밍의 한계와 강화학습
이번 포스트에서는 가치 이터레이션의 개념과 구현, 그리고 다이내믹 프로그래밍의 한계점에 대해 알아본다. 또한 정책 이터레이션과는 다른 접근 방식을 통해 최적 정책을 찾는 방법을 이해해본다.
명시적인 정책 vs 내재적인 정책
정책 이터레이션의 특징
정책 이터레이션은 명시적인 정책이 있으며 그 정책을 평가하는 도구로 가치함수를 사용한다. 정책의 형태는 다양하며 가치함수로 평가하는 정책은 이터레이션을 반복할수록 최적에 도달해간다.
정책과 가치함수는 명확히 분리돼 있으며 이는 정책 이터레이션이 벨만 기대 방정식을 이용하는 이유가 된다.
정책 이터레이션이 벨만 기대 방정식을 사용하는 이유
정책이 독립적이므로 결정적인 정책(어떠한 상태에서 오직 하나의 행동만 선택하는)이 아니라 어떤 정책도 가능하다.
대다수의 정책은 확률적인 정책이며 이러한 확률적인 정책은 가치함수를 계산하려면 당연히 기댓값이 들어갈 수밖에 없고 때문에 정책 이터레이션은 벨만 기대 방정식을 사용하는 것이다.
가치 이터레이션의 아이디어
하지만 결정적인 형태만으로 정의된다면? 현재의 가치함수가 최적은 아니지만 최적이라 가정하고 그 가치함수에 대해 결정적인 형태의 정책을 적용한다면?
DP는 반복적인 계산을 수행하기에 처음의 가치함수는 최적이 아니므로 최적 정책의 형태를 가정하는 것은 틀린 가정이지만 반복적으로 가치함수를 발전시켜 최적에 도달한다면 문제가 되지 않으며 실제로 최적 가치함수에 도달하고 최적 정책을 구할 수 있다.
이를 가치 이터레이션이라고 한다.
정책 이터레이션에서처럼 명시적으로 정책이 표현되는 것이 아니고 가치함수 안에 내재적으로 포함되어 있다. 정책이 내재돼 있으므로 가치함수를 업데이트하면 자동으로 정책 또한 발전되는 것이다.
벨만 최적 방정식과 가치 이터레이션
벨만 기대 방정식 vs 벨만 최적 방정식
벨만 기대 방정식의 결과
벨만 기대 방정식을 통해 전체 문제를 풀어서 나오는 답은 바로 현재 정책을 따라갔을 때 받을 참 보상이다.
- 가치함수를 현재 정책에 대한 가치함수라고 가정
- 반복적으로 계산
- 현재 정책에 대한 참 가치함수가 된다
벨만 최적 방정식의 결과
벨만 최적 방정식을 통해 전체 문제를 풀어 나오는 답은 최적 가치함수다.
- 가치함수를 최적 정책에 대한 가치함수라고 가정
- 반복적으로 계산
- 최적 정책에 대한 참 가치함수, 최적 가치함수를 찾게 된다
벨만 최적 방정식
$v_*(s) = \underset{a}{max}E[R_{t+1} + \gamma v_ *(S_{t+1}) | S_t = s, A_t = a]$
벨만 최적 방정식을 통해 구하는 것은 최적 가치함수다. 따라서 가치 이터레이션에서는 따로 정책 발전이 필요없다.
- 시작부터 최적 정책을 가정했기 때문에 한 번의 정책 평가과정을 거치면 최적 가치함수와 최적 정책이 구해지고 MDP가 풀린다
- 벨만 기대 방정식과 다르게 max를 취한다
- 새로운 가치함수를 업데이트할 때 정책의 값을 고려할 필요가 없다
- 현재 상태에서 가능한 가치함수의 값들 중에서 최고의 값으로 업데이트하면 된다
계산 가능한 벨만 최적 방정식
$v_{k+1}(s) = \underset{a \in A}{max}(r_{(s,a)} + \gamma v_k(s^\prime))$
이것이 바로 계산 가능한 벨만 최적 방정식이다.
가치 이터레이션 코드 구현
코드 구조
가치 이터레이션 구현은 다음과 같이 구성된다:
- value_iteration.py: ValueIteration 클래스를 포함하며, 클래스에는 가치 이터레이션의 알고리즘 관련 함수와 main 함수가 정의돼 있다
- environment.py: 그리드월드 예제의 화면을 구성하고 상태, 보상 등을 포함한 환경에 대한 정보를 제공하기 위한 함수로 구성돼 있다
정책 이터레이션과의 차이점
정책 이터레이션과 가치 이터레이션의 중요한 차이점은 정책 이터레이션에서 정책 평가와 정책 발전으로 단계가 나뉘어져 있다면 가치 이터레이션에서는 그렇지 않다는 것이다. 정책을 발전하는 함수가 따로 필요하지 않다.
메인 루프
1
2
3
4
5
if __name__ == "__main__":
env = Env()
value_iteration = ValueIteration(env)
grid_world = GraphicDisplay(value_iteration)
grid_world.mainloop()
ValueIteration 클래스 상세 분석
주요 멤버 변수
- value_table: 가치함수 테이블
- discount_factor: 할인율
정책 이터레이터와는 다르게 정책 테이블이 없다.
value_iteration 메소드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def value_iteration(self):
# 다음 가치함수 초기화
next_value_table = [[0.0] * self.env.width
for _ in range(self.env.height)]
# 모든 상태에 대해서 벨만 최적방정식을 계산
for state in self.env.get_all_states():
# 마침 상태의 가치 함수 = 0
if state == [3, 3]:
next_value_table[state[0]][state[1]] = 0.0
continue
# 벨만 최적 방정식
value_list = []
for action in self.env.possible_actions:
next_state = self.env.state_after_action(state, action)
reward = self.env.get_reward(state, action)
next_value = self.get_value(next_state)
value_list.append((reward + self.discount_factor * next_value))
# 최댓값을 다음 가치 함수로 대입
next_value_table[state[0]][state[1]] = max(value_list)
self.value_table = next_value_table
다음 가치함수를 계산하는 메소드로, 정책 평가와 정책 발전이 함수 하나로 대체되었다.
get_action 메소드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def get_action(self, state):
if state == [3, 3]:
return []
# 모든 행동에 대해 큐함수 (보상 + (감가율 * 다음 상태 가치함수))를 계산
value_list = []
for action in self.env.possible_actions:
next_state = self.env.state_after_action(state, action)
reward = self.env.get_reward(state, action)
next_value = self.get_value(next_state)
value = (reward + self.discount_factor * next_value)
value_list.append(value)
# 최대 큐 함수를 가진 행동(복수일 경우 여러 개)을 반환
max_idx_list = np.argwhere(value_list == np.amax(value_list))
action_list = max_idx_list.flatten().tolist()
return action_list
가치함수를 토대로 자신이 할 행동을 반환하는 메소드다:
- 최적 정책이 아니더라도 현재 가치함수에 대한 탐욕 정책을 볼 수 있다
- 탐욕 정책을 위해 큐함수를 비교해야 하므로 모든 행동에 대해 큐함수를 구한다
- 가장 큰 value가 여러 개인 경우도 고려해 action_list에 저장한다
가치 이터레이션 실행 결과
첫 실행 화면
첫 실행 화면
가치함수 수렴 과정
몇 번의 Calculate를 수행하면 가치함수가 수렴한다.
최적 정책 확인
최적 정책(최적 가치함수)가 구해졌으니 Print Policy와 Move를 차례로 눌러준다.
다이내믹 프로그래밍의 한계
한계점 개요
DP는 계산을 빠르게 하는 것이지 학습을 하는 것은 아니며 머신러닝이 아니다. DP가 한계를 가지고 있기에 강화학습을 통해 순차적 행동 결정 문제에서 최적 정책을 찾는다.
DP의 3가지 주요 한계
1. 계산 복잡도
문제의 규모가 커지면 커질수록 계산 복잡도가 기하급수적으로 늘어난다. DP의 계산 복잡도는 상태 크기의 3제곱에 비례하기 때문이다.
2. 차원의 저주
그리드월드는 2차원으로 상태가 (x, y)로 표현되지만 차원이 늘어나면 상태의 수가 지수적으로 증가한다.
3. 환경에 대한 완벽한 정보가 필요
DP는 프로그래밍을 풀 때 보상과 상태 변환 확률을 정확히 안다는 가정하에 풀었다. 하지만 이러한 환경의 모델에 해당하는 보상과 상태 변환 확률을 정확히 아는 것은 불가능하다.
위의 세 가지 한계가 치명적으로 작용하는 현실 세계의 환경에 놓은 문제를 풀기 위해서는 환경을 모르지만 환경과의 상호작용을 통해 경험을 바탕으로 학습하는 방법인 강화학습이 등장했다.
모델 없이 학습하는 강화학습
환경의 모델
MDP에서 환경의 모델은 상태 변환 확률과 보상이다.
\[환경의 모델 = P_{ss^\prime}^{a}, r_{(s,a)}\]모델이라는 말은 공학의 여러 분야에서 사용된다. 이 책에서 다루는 모델은 수학적 모델로 시스템에 입력이 들어왔을 때 시스템이 어떤 출력을 내는지에 대한 방정식이다. 이처럼 입력과 출력의 관계를 식으로 나타내는 과정을 모델링이라고 한다.
입력과 출력 사이의 방정식은 정확할 수가 없다. 모델은 정확하면 정확할수록 복잡하며 자연현상을 모델링하는 것은 불가능에 가깝다.
두 가지 접근법
이러한 모델을 정확히 알기 위해 두 가지 접근법이 있다:
1. 전통적 접근법
할 수 있는 선에서 정확한 모델링을 한 다음에 모델링 오차에 대한 부분을 실험을 통해 조정한다.
- 학습의 개념 없이 고전적으로 많이 적용하는 방법이다
- 고전적인 만큼 시스템의 안정성을 보장한다
- 하지만 문제가 복잡해지고 어려워질수록 한계를 가진다
2. 강화학습 접근법
모델 없이 환경과의 상호작용을 통해 입력과 출력 사이의 관계를 학습한다.
- 학습의 개념이 들어간다
- 학습의 특성상 모든 상황에서 동일하게 작동한다고 보장할 수 없다
- 하지만 많은 복잡한 문제에서 모델이 필요없다는 것은 장점이며 이것이 강화학습이다
정리
다이내믹 프로그래밍과 그리드월드
순차적 행동 결정 문제를 벨만 방정식으로 푸는 것이 다이내믹 프로그래밍이다. 다이내믹 프로그래밍은 여러 번으로 쪼개서 가치함수를 구한다. 벨만 기대 방정식을 이용한 것은 정책 이터레이션, 벨만 최적 방정식을 이용한 것이 가치 이터레이션이다.
다이내믹 프로그래밍 1: 정책 이터레이션
정책 이터레이션은 현재 정책에 대한 참 가치함수를 구하는 정책 평가와 평가한 내용을 가지고 정책을 업데이트하는 정책 발전으로 이루어진다. 정책 평가 시 벨만 기대 방정식을 이용하며 정책을 발전할 때는 구한 가치함수를 토대로 최대의 보상을 얻게 하는 행동을 선택하는 탐욕 정책 발전을 이용한다.
다이내믹 프로그래밍 2: 가치 이터레이션
가치 이터레이션은 최적 정책을 가정하고 벨만 최적 방정식을 이용해 순차적 행동 결정 문제에 접근한다. 정책 이터레이션과 달리 정책이 직접적으로 주어지지 않으며 행동의 선택은 가치함수를 통해 이루어진다.
다이내믹 프로그래밍의 한계와 강화학습
다이내믹 프로그래밍은 계산 복잡도, 차원의 저주, 환경에 대한 완벽한 정보가 필요하다는 단점이 있다. 이러한 문제를 극복하고자 모델 없이 학습하는 강화학습에 대한 연구가 진행되었다.