인공지능

Dynamic Programming

강원대학교 컴퓨터공학과 최우혁

지난 시간에…

• Markov Process?
• 마르코프 성질을 따르는 확률적 프로세스

​

• 강화 학습은 마르코프 결정 프로세스로 정의된 문제를 푸는 방법

2

지난 시간에…

• Bellman Equation
• 가치 함수: 주어진 상태에서 앞으로 얻을 수 있는 이익의 기대값을 추정

​

​

• 최적의 정책: 주어진 상태에서 이익이 최대(= 가치 함수의 값이 최대)가 되는 행동을 선택하는 정책

3

지난 시간에…

• Bellman Equation
• 벨만 기대 방정식: 상태/행동 가치 함수를 재귀적으로 정의

4

지난 시간에…

• Bellman Equation
• 벨만 최적 방정식: 최적의 상태/행동 가치 함수를 재귀적으로 정의

​

​

​

​

​

​

5

지난 시간에…

• Bellman Equation
• 벨만 기대 방정식을 푼다 = 가치 함수를 정확히 추정한다 = 현재 정책의 가치를 평가한다
• 벨만 최적 방정식을 푼다 = 최적의 가치 함수를 정확히 추정한다 = 최적의 정책을 찾을 수 있다

6

강의 순서

• Dynamic Programming?
• Value Iteration
• Policy Iteration
• Dynamic Programming vs. Reinforcement Learning

7

이번 시간에…

• Dynamic Programming?
• (이미 알고리즘 시간에 배웠겠지만) 동적 계획법의 개념과 적용하기 위한 제약 사항을 소개
• Value Iteration
• 벨만 최적 방정식을 활용하여 마르코프 결정 프로세스를 푸는(= 최적의 가치 함수를 찾음 = 최적의 정책을 학습) 방법을 학습
• Policy Iteration
• Dynamic Programming vs. Reinforcement Learning

8

Dynamic Programming?

9

어원

Dynamic Programming?

• 응용수학자 Richard Ernest Bellman이 고안한 수학, 컴퓨터 과학, 경제학 분야의 문제 해결 방법

​

​

10

나는 RAND에서 1950년의 가을을 보냈다. 여기에서 내게 주어진 첫 과제는 다단계Multi-stage 의사 결정 프로세스에 대해 적절한 용어를 명명하는 것이었다. '동적 계획법'이라는 이름이 어디에서 왔는지 궁금하지 않은가? 1950년대는 내가 수학에 대해 연구하기에는 좋지 못한 시기였다. 우리는 그 때 워싱턴에서 윌슨이라는 사람과 함께 일하고 있었다. 윌슨은 연구라는 것에 대해 굉장히 병적인 공포를 가지고 있었다. 사람들이 그 앞에서 연구라는 단어를 쓰면 그는 완전히 미치다시피 했다. 그러나 불행히도 RAND는 공군 소속의 회사였고, 윌슨은 그 공군의 간부인 국방 위원장 이었다. 그래서, 나는 윌슨과 공군으로부터 내가 수학을 연구하고 있다는 사실을 숨길 필요가 있었다. 어떤 단어를 선택해야 했을까? 처음에는 Planning. Decision Making, Thinking 등의 단어를 고려했었다. 하지만, 몇 가지 이유로 해당 단어들이 좋은 선택이 아님을 깨달았고, 대신 사람들이 알지 못하게 Programming이라는 단어를 선택했다. 또한 나는 이 방법이 다단계Multi-stage로 이루어져 있고, 시가변적Time-varying이며, 동적Dynamic이라는 개념이 전달되길 원했다. 특히, 동적Dynamic이라는 형용사는 어떤 단어와 조합해도 긍정적인 의미가 있다고 생각했다. 그래서, 동적 계획법Dynamic Programming이 좋은 이름이라고 생각했으며, 내가 하는 연구를 윌슨과 공군으로부터 숨기는 데 사용했다.

​

- Richard E. Bellman의 자서전, 태풍의 눈Eyes of Hurricane 중

Richard Ernest Bellman, 응용수학자

동적 계획법Dynamic Programming, 벨만 방정식Bellman Equation, 차원의 저주Curse of Dimensionality 등을 제시

특징

Dynamic Programming?

• Substructure
• 큰 문제를 작은 문제로 분할
• Table structure
• 작은 문제를 해결한 결과를 테이블 또는 변수 등에 저장
• Bottom-up Computation
• 저장된 작은 문제에 대한 해결책을 합쳐서 큰 문제에 대한 해결책을 생성

11

동적 계획법을 적용할 수 있는 문제

Dynamic Programming?

• Optimal Substructure & Overlapping Subproblems
• 작은 문제에 대한 최적의 해결책을 사용해서 큰 문제에 대한 최적의 해결책을 찾을 수 있거나, 작은 문제에 대한 해결책이 반복적으로 재사용되는 경우
• 예. Floyd의 최단 경로 알고리즘
• S → E 까지의 최단 경로: S → V₂ 까지의 최단 경로 + V₂ → E 까지의 최단 경로
• S → V₂ 까지의 최단 경로: S → V₁ 까지의 최단 경로 + V₁ → V₂까지의 최단 경로

12

동적 계획법과 벨만 방정식

Dynamic Programming?

• 벨만 방정식은 재귀적으로 정의되므로, 이전에 계산한 가치 함수의 값을 저장하고 재사용해야 함

​

13

Value Iteration

14

(Recap) 벨만 최적 방정식

Value Iteration

​

​

• 현재 상태에서의 최적의 상태 가치 함수 값

15

(Recap) 벨만 최적 방정식

Value Iteration

​

​

• 현재 상태에서의 최적의 상태 가치 함수 값
• 현재 선택한 행동으로 인한 보상의 기대값

​

16

(Recap) 벨만 최적 방정식

Value Iteration

​

​

• 현재 상태에서의 최적의 상태 가치 함수 값
• 현재 선택한 행동으로 인한 보상의 기대값
• 다음 상태에 대한 최적의 상태 가치 함수( = 수익의 기대값)의 기대값

​

17

(Recap) 벨만 최적 방정식

Value Iteration

​

​

• 현재 상태에서의 최적의 상태 가치 함수 값
• 현재 선택한 행동으로 인한 보상의 기대값
• 다음 상태에 대한 최적의 상태 가치 함수( = 수익의 기대값)의 기대값
• 두 값의 합이 최대가 되는 것

18

(Recap) 벨만 최적 방정식

Value Iteration

​

​

• 최적의 상태 가치 함수 = 주어진 상태에서 최적의 행동을 선택했을 때의 이익의 기대값

19

(Recap) 벨만 최적 방정식

Value Iteration

​

​

• 최적의 상태 가치 함수 = 주어진 상태에서 최적의 행동을 선택했을 때의 이익의 기대값
• 최적의 상태 가치 함수 값을 알고 있다 = 최적의 행동을 알 수 있다

20

최적 상태 가치 함수의 추정

Value Iteration

​

​

​

• 알고 있는 것
• 모델
• 현재 상태의 최적의 행동
• 현재 상태에서 수행한 최적의 행동으로 인해 얻을 수 있는 보상

21

최적 상태 가치 함수의 추정

Value Iteration

​

​

​

• 알고 있는 것
• 모델
• 현재 상태의 최적의 행동
• 현재 상태에서 수행한 최적의 행동으로 인해 얻을 수 있는 보상
• 모르는 것
• 현재 상태의 최적의 상태 가치 함수
• 다음 상태의 최적의 상태 가치 함수

22

최적 상태 가치 함수의 추정

Value Iteration

​

​

​

• 과거의 추정치

23

최적 상태 가치 함수의 추정

Value Iteration

​

​

​

• 과거의 추정치
• 새로운 추정치

24

최적 상태 가치 함수의 추정

Value Iteration

​

​

​

• 과거의 추정치
• 새로운 추정치
• 과거의 추정치로부터 새로운 (더 정확한) 추정치를 계산

25

최적 상태 가치 함수의 추정

Value Iteration

​

​

​

• 과거의 추정치
• 새로운 추정치
• 과거의 추정치로부터 새로운 (더 정확한) 추정치를 계산
• 과거의 추정치와 새로운 추정치 간의 차이가 (거의) 없을 때(= 가치 함수의 추정치가 수렴할 때)까지 반복

26

최적의 정책

Value Iteration

​

​

​

• 최적 상태 가치 함수의 계산이 완료되면, 행동 가치 함수의 값이 최대가 되는 행동을 선택하는 최적의 정책을 학습할 수 있음

27

예.

Value Iteration

28

예. 최적 상태 가치 함수의 추정

Value Iteration

• 상태 가치 함수의 값은 0 (또는 무작위값)으로 초기화
• 종료 상태(예. Overheated)에서는 얻을 수 있는 보상 및 수익이 없으므로, 상태 가치 함수의 값이 0이 됨

29

예. 최적 상태 가치 함수의 추정

Value Iteration

30

예. 최적 상태 가치 함수의 추정

Value Iteration

31

예. 최적 상태 가치 함수의 추정

Value Iteration

32

예. 최적 상태 가치 함수의 추정

Value Iteration

33

예. 최적의 정책

Value Iteration

34

예. 최적의 정책

Value Iteration

35

Pseudocode

Value Iteration

36

상태 가치 함수를 임의의 값으로 초기화;

단 종료 상태의 상태 가치 함수는 0으로 둠

최적 상태 가치 함수의 값이

수렴할 때까지 업데이트

행동 가치 함수의 값을 최대화하는 행동을 선택하는 정책 생성

Synchronous vs. Asynchronous Backups

Value Iteration

37

Synchronous vs. Asynchronous Backups

Value Iteration

• Synchronous Backups
• 매 단계가 끝나고 난 후에 가치 함수의 값을 업데이트
• 현재 단계의 가치 함수 업데이트에는 이전 단계의 가치 함수를 활용

38

Synchronous vs. Asynchronous Backups

Value Iteration

• Asynchronous Backups
• 매 상태마다 가치 함수의 값을 업데이트
• 현재 단계의 가치 함수 업데이트에는 최신의 가치 함수를 활용
• 보다 정확한 가치 함수 추정이 가능하므로, 더 많이 사용됨

39

단점: 비효율적

Value Iteration

• 보통, 가치 함수의 값이 수렴되기 전에 이미 최적의 정책을 찾는 경우가 많으므로, 불필요한 연산이 수반됨

40

단점: 비효율적

Value Iteration

• 또한, 매 상태에 대한 가치 함수 업데이트는 많은 연산량을 필요로 함: O(|S|²|A|)

41

다음 시간에…

• Dynamic Programming?
• Value Iteration
• Policy Iteration
• 벨만 기대 방정식을 활용하여 마르코프 결정 프로세스를 푸는(= 최적의 가치 함수를 찾음 = 최적의 정책을 학습) 방법을 학습
• Dynamic Programming vs. Reinforcement Learning
• 마르코프 결정 프로세스를 풀기 위한 동적 계획법과 강화 학습의 차이를 이해

​

42

인공지능

Dynamic Programming

강원대학교 컴퓨터공학과 최우혁

강의 순서

• Dynamic Programming?
• Value Iteration
• Policy Iteration
• Dynamic Programming vs. Reinforcement Learning

44

지난 시간에…

• Dynamic Programming?
• 큰 문제를 작은 문제로 분할하고Substructure, 작은 문제의 해결책을 저장하며Table structure, 저장된 작은 문제에 대한 해결책을 합쳐서 큰 문제에 대한 해결책을 생성Bottom-up Computation
• 마르코프 결정 프로세스에 대한 벨만 기대/최적 방정식은 재귀적으로 정의되므로, 동적 계획법을 활용하여 풀 수 있음

45

지난 시간에…

• Value Iteration
• 벨만 최적 방정식을 풀어서 최적의 정책을 찾는 방법

46

이번 시간에…

• Dynamic Programming?
• Value Iteration
• Policy Iteration
• 벨만 기대 방정식을 활용하여 마르코프 결정 프로세스를 푸는(= 최적의 가치 함수를 찾음 = 최적의 정책을 학습) 방법을 학습
• Dynamic Programming vs. Reinforcement Learning
• 마르코프 결정 프로세스를 풀기 위한 동적 계획법과 강화 학습의 차이를 이해

47

Policy Iteration

48

(Recap) 벨만 기대 방정식

Policy Iteration

​

​

• 현재 상태에서의 상태 가치 함수 값

​

49

(Recap) 벨만 기대 방정식

Policy Iteration

​

​

• 현재 상태에서의 상태 가치 함수 값
• 선택한 행동으로 인한 보상의 기대값

​

50

(Recap) 벨만 기대 방정식

Policy Iteration

​

​

• 현재 상태에서의 상태 가치 함수 값
• 선택한 행동으로 인한 보상의 기대값
• 다음 상태에 대한 상태 가치 함수( = 수익의 기대값)의 기대값

​

51

(Recap) 벨만 기대 방정식

Policy Iteration

​

​

• 현재 상태에서의 상태 가치 함수 값
• 선택한 행동으로 인한 보상의 기대값
• 다음 상태에 대한 상태 가치 함수( = 수익의 기대값)의 기대값
• 두 값의 합을 현재 정책에 기반한 기대값으로 계산

52

(Recap) 벨만 기대 방정식

Policy Iteration

​

​

• 상태 가치 함수 = 주어진 상태에서 주어진 정책을 기반으로 행동을 선택했을 때 얻을 수 있는 이익의 기대값

53

(Recap) 벨만 기대 방정식

Policy Iteration

​

​

• 상태 가치 함수 = 주어진 상태에서 주어진 정책을 기반으로 행동을 선택했을 때 얻을 수 있는 이익의 기대값
• 상태 가치 함수 값을 알고 있다 = 현재 정책의 가치를 알 수 있다

54

벨만 기대 방정식: 추정

Policy Iteration

​

​

​

• 알고 있는 것
• 모델
• 현재 상태에서 행동을 할 확률(= 정책)
• 현재 상태에서 한 행동으로 인해 얻을 수 있는 보상

​

55

벨만 기대 방정식: 추정

Policy Iteration

​

​

​

• 알고 있는 것
• 모델
• 현재 상태에서 행동을 할 확률(= 정책)
• 현재 상태에서 한 행동으로 인해 얻을 수 있는 보상
• 모르는 것
• 현재 상태의 상태 가치 함수
• 다음 상태의 상태 가치 함수

56

벨만 기대 방정식: 결정적 정책

Policy Iteration

​

​

​

​

• 문제의 단순화를 위해, 확률적 정책 대신 결정적 정책을 사용한다고 가정

57

Policy Evaluation

Policy Iteration

​

​

​

• 과거의 추정치

58

Policy Evaluation

Policy Iteration

​

​

​

• 과거의 추정치
• 새로운 추정치

59

Policy Evaluation

Policy Iteration

​

​

​

• 과거의 추정치
• 새로운 추정치
• 과거의 추정치로부터 새로운 (더 정확한) 추정치를 계산

​

60

Policy Evaluation

Policy Iteration

​

​

​

• 과거의 추정치
• 새로운 추정치
• 과거의 추정치로부터 새로운 (더 정확한) 추정치를 계산
• 과거의 추정치와 새로운 추정치 간의 차이가 (거의) 없을 때(= 가치 함수의 추정치가 수렴할 때)까지 반복

61

Policy Improvement

Policy Iteration

​

​

​

​

• 벨만 기대 방정식의 계산이 완료되면, 현재 주어진 정책에서 추정된 행동 가치 함수의 값이 최대가 되는 행동을 선택Greedy하는 더 나은 정책을 생성할 수 있음

​

62

Evaluation ⇆ Improvement = Policy Iteration

Policy Iteration

​

​

​

• Policy Evaluation과 Policy Improvement를 번갈아가면서 반복
• 정책에 변화가 없다
• 정책이 수렴했다
• 최적의 정책을 찾았다
• 최적의 가치 함수를 찾았다
• 벨만 최적 방정식을 풀었다

63

Policy Evaluation

Policy Improvement

Generalized Policy Iteration, GPI

Policy Iteration

• 대부분의 강화 학습 기법은 Policy Evaluation과 Policy Improvement를 번갈아가면서 반복
• 정책 또는 가치 함수가 수렴하면 최적의 정책 및 최적의 가치 함수를 찾은 것

64

Pseudocode

Policy Iteration

65

정책이 수렴할 때까지 반복

Policy Evaluation

Policy Improvement

Policy Improvement?

Policy Iteration

​

​

​

• 단순히 가치 함수의 값이 큰 행동을 선택Greedy하는 게 과연 이전보다 더 나은 정책이 되는지?

66

Policy Improvement Theorem

Policy Iteration

• 아래의 조건을 만족하는 두 정책이 존재할 때, 한 정책이 다른 정책보다 개선되었다고 할 수 있음

67

Policy Improvement Theorem

Policy Iteration

• 가치 함수의 값이 큰 행동을 선택하는 정책은 Policy Improvement Theorem을 만족하므로 이전보다 개선된 정책이 됨!

68

Policy Improvement Theorem: Proof

Policy Iteration

69

Policy Improvement Theorem: Proof

Policy Iteration

70

Value Iteration vs. Policy Iteration

Policy Iteration

• k = 3에서 이미 정책이 수렴되었으나, 상태 가치 함수의 값은 아직 수렴하지 않음
• Policy Iteration에선 정책의 변화가 없을 때 종료되므로 불필요한 계산을 줄일 수 있음

71

Dynamic Programming vs.

Reinforcement Learning

72

동적 계획법 vs. 강화 학습

Dynamic Programming vs. Reinforcement Learning

• 동적 계획법

​

• 환경의 모델을 알고 있음Model-Based
• 환경에 대한 완벽한 지식을 바탕으로 최적의 정책을 계획Planning

73

동적 계획법 vs. 강화 학습

Dynamic Programming vs. Reinforcement Learning

• 동적 계획법

​

• 환경의 모델을 알고 있음Model-Based
• 환경에 대한 완벽한 지식을 바탕으로 최적의 정책을 계획Planning
• 강화 학습

​

• 환경의 모델을 모름Model-Free
• 환경에 대한 불완전한 지식을 바탕으로 최적의 정책을 학습Learning

74

동적 계획법 vs. 강화 학습

Dynamic Programming vs. Reinforcement Learning

• Backup Diagram
• 마르코프 결정 프로세스에 대한 상태-행동-보상의 에피소드를 시각적으로 표현
• 상태는 백색 원, 행동은 흑색 원으로 표현
• 상태 - 행동 간에는 정책, 행동 - 상태 간에는 보상을 표현
• Backup: 현재 상태에서 전이할 수 있는 다음 상태를 표현

75

동적 계획법 vs. 강화 학습

Dynamic Programming vs. Reinforcement Learning

• 동적 계획법: Full Backup

​

​

• 현재 상태에 대한 가치 함수는 현재 상태에서 전이 가능한 모든 다음 상태에 대한 가치 함수를 활용하여 업데이트
• 모든 상태에 대해 가치 함수의 값을 계산해야 하므로, 상태의 개수가 많다면 많은 연산이 필요

76

동적 계획법 vs. 강화 학습

Dynamic Programming vs. Reinforcement Learning

• 몬테 카를로Monte-Carlo 학습: Sample Multi-Step Backup

​

• 현재 상태에 대한 가치 함수는 현재 상태에서 시작한 에피소드가 종료된 후에 관측된 수익을 활용하여 업데이트
• 에피소드 내에서 발생한 상태에 대해서만 가치 함수의 값을 계산하므로, 연산량은 상태의 개수와는 독립적

77

동적 계획법 vs. 강화 학습

Dynamic Programming vs. Reinforcement Learning

• 시간차Temporal Difference 학습: Sample Backup

​

• 현재 상태에 대한 가치 함수는 보상과 바로 다음 상태에 대한 가치 함수를 활용하여 업데이트
• 바로 다음 상태만을 활용하여 가치 함수의 값을 계산하므로, 연산량은 상태의 개수와는 독립적

78

다음 시간에…

• Tutorial on Gymnasium
• 강화 학습을 위한 환경을 제공하는 API인 Gymnasium의 기본적인 사용법을 학습하고, Policy Iteration 및 Value Iteration을 구현

79