1 of 81

인공지능

Planning & Learning

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

2 of 81

지난 시간에

  • n-Step Temporal Difference Prediction
    • 현재 상태의 가치 함수를 업데이트 하기 위하여, n-Step Return (n회의 타입 스텝에서 얻는 실제 보상 + n회 이후의 타임 스텝에서 전이할 수 있는 상태에 대한 가치 함수)을 활용

​

​

2

3 of 81

지난 시간에

  • n-Step Temporal Difference Control

​

3

4 of 81

강의 순서

  • Model-Based Reinforcement Learning
  • Experience Sampling
  • Trajectory Sampling
  • Decision-Time Planning

​

4

5 of 81

이번 시간에…

  • Model-Based Reinforcement Learning
    • 환경의 모델 또한 학습하여 최적의 정책을 찾는데 활용하는 모델 기반 강화 학습 기법의 기본 개념을 소개
  • Experience Sampling
    • 모델에서 상태-행동-다음 상태-보상을 추출하여 학습에 활용하는 강화 학습 기법을 이해
  • Trajectory Sampling
  • Decision-Time Planning

​

5

6 of 81

Model-Based Reinforcement Learning

6

7 of 81

(Recap) 동적 계획법 vs. 강화 학습

Model-Based Reinforcement Learning

  • 동적 계획법

​

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

7

8 of 81

(Recap) 동적 계획법 vs. 강화 학습

Model-Based Reinforcement Learning

  • 동적 계획법

​

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

​

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

8

9 of 81

Model-Based + Reinforcement Learning?

Model-Based Reinforcement Learning

  • 환경의 모델을 정확히 알지 못하더라도, 에이전트가 실제로 경험한 상태-행동-보상을 바탕으로, 실제 모델을 따라하는 모델Simulated Model을 학습
    • 즉, 환경의 모델처럼 주어진 상태-행동에 대해서 다음 상태 및 보상을 예측하는 함수를 훈련
  • 실제 경험Real Experience + 학습된 모델로부터 생성할 수 있는 모조 경험Simulated Experience을 모두 활용하여 최적의 정책을 학습

9

10 of 81

Planning vs. Learning

Model-Based Reinforcement Learning

  • (Pure) Planning (e.g., Dynamic Programming)

​

​

10

11 of 81

Planning vs. Learning

Model-Based Reinforcement Learning

  • (Pure) Planning (e.g., Dynamic Programming)

​

  • Learning (e.g., MC and TD)

​

​

11

12 of 81

Planning vs. Learning

Model-Based Reinforcement Learning

  • (Pure) Planning (e.g., Dynamic Programming)

​

  • Learning (e.g., MC and TD)

​

  • Integrating Learning and Planning

12

13 of 81

Simple Model-Based RL: Q-Planning

Model-Based Reinforcement Learning

13

환경에서 얻는 실제 경험 대신, 모델이 제공하는 경험으로 가치 함수를 업데이트

14 of 81

Rough Categories of Model-Based RL

Model-Based Reinforcement Learning

  • Experience Sampling
    • 상태-행동-보상-다음 상태를 모델로부터 추출하여 가치 함수를 학습

14

15 of 81

Rough Categories of Model-Based RL

Model-Based Reinforcement Learning

  • Trajectory Sampling
    • 임의의 상태에서 시작하여, 주어진 정책과 모델을 따라 에피소드를 진행하면서 방문하는 상태-보상에 대해 가치 함수를 학습

15

16 of 81

Rough Categories of Model-Based RL

Model-Based Reinforcement Learning

  • Decision-Time Planning
    • 현재 상태에서 모델을 바탕으로 에피소드를 끝까지 진행하여 얻을 수 있는 수익으로 행동을 선택
    • 보통, 가치 함수를 학습하지는 않음

16

17 of 81

Experience Sampling

17

18 of 81

Dyna-Q

Experience Sampling

  • Planning과 Learning을 통합한 강화학습 알고리즘
  • 환경으로부터 얻어지는 실제 경험은 정책의 학습 및 모델의 학습에 활용
  • 정책의 개선은 실제 경험과 모델이 생성하는 모조 경험에 의해 이루어짐

18

19 of 81

Dyna-Q: Pseudocode

Experience Sampling

19

Model: 주어진 상태-행동에 대해,

관측된 다음 상태-보상의 쌍을 저장하는 배열

Learning: 실제 경험으로

가치 함수 학습

Planning: 무작위로 선택된 행동-상태에 대해 저장된 다음 상태-보상으로 가치 함수를 학습

20 of 81

Q-Learning vs. Dyna-Q

Experience Sampling

  • Q-Learning: 한 타임 스텝에 하나의 상태에 대한 가치 함수를 업데이트
  • Dyna-Q: 한 타입 스텝에 최대 n개의 상태에 대한 가치 함수를 업데이트

​

20

21 of 81

Q-Learning vs. Dyna-Q

Experience Sampling

  • Q-Learning: 한 타임 스텝에 하나의 상태에 대한 가치 함수를 업데이트
  • Dyna-Q: 한 타입 스텝에 최대 n개의 상태에 대한 가치 함수를 업데이트
  • (매 타입 스텝마다 연산량은 많으나) 환경과 적은 수의 상호작용으로도 최적의 정책을 학습할 수 있음

21

22 of 81

Dealing with Incorrect Model

Experience Sampling

  • 비정상 문제Non-Stationary Problem의 경우, 환경의 모델이 시간이 지남에 변할 수 있음
  • 따라서, 현재 학습된 모델은 부정확할 수 있으며, 학습된 정책 또한 최적이지 않을 수 있음

22

23 of 81

Dealing with Incorrect Model

Experience Sampling

  • 다행히도, ε-Greedy 정책 등을 활용하여 여러 상태-행동을 충분히 탐험하면 이러한 문제는 어느 정도 해결됨

​

​

23

24 of 81

Dealing with Incorrect Model

Experience Sampling

  • 다행히도, ε-Greedy 정책 등을 활용하여 여러 상태-행동을 충분히 탐험하면 이러한 문제는 어느 정도 해결됨

​

​

24

25 of 81

Dealing with Incorrect Model

Experience Sampling

  • 다행히도, ε-Greedy 정책 등을 활용하여 여러 상태-행동을 충분히 탐험하면 이러한 문제는 어느 정도 해결됨

​

​

25

26 of 81

Dealing with Incorrect Model

Experience Sampling

  • 하지만, 환경이 이전보다 더 나은 보상을 얻을 수 있도록 변화된다면, ε-Greedy 정책이 가진 특성(현재 상태에서 상태 가치 함수가 가장 높은 행동을 선택)상, 새로운 최적의 정책을 학습하기는 어려움

26

27 of 81

Dealing with Incorrect Model

Experience Sampling

  • 하지만, 환경이 이전보다 더 나은 보상을 얻을 수 있도록 변화된다면, ε-Greedy 정책이 가진 특성(현재 상태에서 상태 가치 함수가 가장 높은 행동을 선택)상, 새로운 최적의 정책을 학습하기는 어려움

27

28 of 81

Dealing with Incorrect Model

Experience Sampling

  • 하지만, 환경이 이전보다 더 나은 보상을 얻을 수 있도록 변화된다면, ε-Greedy 정책이 가진 특성(현재 상태에서 상태 가치 함수가 가장 높은 행동을 선택)상, 새로운 최적의 정책을 학습하기는 어려움

​

28

29 of 81

Dealing with Incorrect Model

Experience Sampling

  • 하지만, 환경이 이전보다 더 나은 보상을 얻을 수 있도록 변화된다면, ε-Greedy 정책이 가진 특성(현재 상태에서 상태 가치 함수가 가장 높은 행동을 선택)상, 새로운 최적의 정책을 학습하기는 어려움
  • ε-Greedy가 보장하는 탐험외에도, 추가적인 탐험을 보장할 필요가 있음
  • ​

29

30 of 81

Dyna-Q+

Experience Sampling

  • Planning 단계에서 오래전에 확인된 상태에 대해서는 추가적인 보상Bonus Reward을 받을 수 있도록 설정
  • 이를 통해, 오래된 상태가 앞으로 선택될 가능성을 높이고, 실제 경험으로부터 가치 함수를 업데이트하도록 장려

30

31 of 81

Dyna-Q+: Pseudocode

Experience Sampling

31

Model: 주어진 상태-행동에 대해,

관측된 다음 상태-보상-관측 시간의

쌍을 저장하는 배열

현재 시점보다 관측 시점이

오래될 수록 보상의 양을 증가

32 of 81

Priority of Experiences

Experience Sampling

  • Dyna-Q 및 Dyna-Q+는 Planning 단계에서 이전 경험(상태-행동)을 무작위로 추출하여 그에 대한 가치 함수를 업데이트
  • 하지만, 어떤 경험은 다른 경험보다 중요할 수/하지 않을 수 있음

32

33 of 81

Priority of Experiences

Experience Sampling

33

  • 새로운(더 정확한) 추정치New Estimate
  • 과거의 추정치Old Estimate
  • 학습하고자 하는 목표값Target
  • 과거의 추정치와 목표값의 차이Error
  • 스텝 사이즈Step Size

34 of 81

Priority of Experiences

Experience Sampling

34

  • 가치 함수는 목표값과 과거의 추정치 간의 차이를 최소화하는 방향으로 업데이트
  • 만약, 목표값과 과거의 추정치가 일치하면 더 이상 가치 함수의 값은 업데이트 되지 않음

​

35 of 81

Priority of Experiences

Experience Sampling

35

  • 가치 함수는 목표값과 과거의 추정치 간의 차이를 최소화하는 방향으로 업데이트
  • 만약, 목표값과 과거의 추정치가 일치하면 더 이상 가치 함수의 값은 업데이트 되지 않음
  • 목표값과 과거의 추정치가 일치하는 상태-행동에 대해서는 가치 함수의 업데이트가 더 이상 불필요함

36 of 81

Priority of Experiences

Experience Sampling

36

  • 반대로, 목표값과 과거의 추정치가 크게 차이 난다면, 해당 상태-행동에 대해서는 가치 함수의 업데이트가 시급히 필요함

37 of 81

Priority of Experiences

Experience Sampling

37

  • 반대로, 목표값과 과거의 추정치가 크게 차이 난다면, 해당 상태-행동에 대해서는 가치 함수의 업데이트가 시급히 필요함
  • 목표값과 과거의 추정치간의 차이가 큰 상태-행동의 경우 가치 함수의 업데이트의 우선 순위가 높음

38 of 81

Prioritized Sweeping: Pseudocode

Experience Sampling

38

39 of 81

Prioritized Sweeping: Pseudocode

Experience Sampling

39

상태-행동의 쌍을 Error를 우선 순위로 하는 우선 순위 큐Priority Queue에 넣음

Error가 큰 상태-행동의 쌍부터

선택해서 상태 가치 함수를 업데이트

새로 업데이트 된 상태로 전이할 수 있는 상태-행동의 쌍을 뽑아서 우선 순위 큐에 넣음

40 of 81

Prioritized Sweeping: Pseudocode

Experience Sampling

  • Q(s, a)가 업데이트되면, 해당 값을 Backup으로 사용하는 이전 상태-행동에 대한 가치 함수 또한 크게 변할 가능성이 있음

40

새로 업데이트 된 상태로 전이할 수 있는 상태-행동의 쌍을 뽑아서 우선 순위 큐에 넣음

41 of 81

다음 시간에…

  • 2024. 10. 24 (목): 휴강
    • 시험 공부 열심히 하세요 :)

41

42 of 81

그 다음 시간에…

  • Model-Based Reinforcement Learning
  • Experience Sampling
  • Trajectory Sampling
    • 정책을 따라 임의의 상태에서 시작하여 에피소드 종료까지 생성된 모조 경험을 학습에 활용하는 알고리즘을 이해
  • Decision-Time Planning
    • 가치 함수를 학습하는 대신, 모델로부터 추정된 수익을 활용해 행동을 선택하는 강화 학습 기법을 소개

42

43 of 81

인공지능

Planning & Learning

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

44 of 81

강의 순서

  • Model-Based Reinforcement Learning
  • Experience Sampling
  • Trajectory Sampling
  • Decision-Time Planning

​

44

45 of 81

지난 시간에

  • Model-Based Reinforcement Learning: 에이전트가 추정한 모델로부터 얻어지는 경험을 활용하여 최적의 정책을 찾는 강화 학습 기법

​

​

45

46 of 81

지난 시간에

  • Experience Sampling: 모델로부터 이전 경험(상태-행동-보상-다음 상태)를 추출하여 학습에 활용
    • Dyna-Q: 무작위로 이전 경험을 추출
    • Dyna-Q+: 무작위로 이전 경험을 추출하나, 확인된 지 오래된 상태에 대해서는 추가적인 보상을 산정
    • Prioritized Sweeping: 목표값과 과거의 추정치간의 차이가 큰 가치 함수부터 우선적으로 업데이트

​

46

47 of 81

이번 시간에…

  • Model-Based Reinforcement Learning
  • Experience Sampling
  • Trajectory Sampling
    • 정책을 따라 임의의 상태에서 시작하여 에피소드 종료까지 생성된 모조 경험을 학습에 활용하는 알고리즘을 이해
  • Decision-Time Planning
    • 가치 함수를 학습하는 대신, 모델로부터 추정된 수익을 활용해 행동을 선택하는 강화 학습 기법을 소개

47

48 of 81

Trajectory Sampling

48

49 of 81

Disadvantages of Dyna-Q

Trajectory Sampling

  • 학습된 모델에서 무작위로 이전의 경험 (상태-행동-보상- 다음 상태)를 추출하여 가치 함수를 업데이트

​

49

50 of 81

Disadvantages of Dyna-Q

Trajectory Sampling

  • 굉장히 큰 상태 공간을 가지는 문제의 경우, 가치 함수를 충분히 업데이트 하기 위하여 많은 횟수의 이전 경험 추출이 필요
  • 하지만, 대다수의 경험은 실제 문제를 해결하는 데 직접적으로 필요하지 않음

​

50

51 of 81

On-Policy Trajectory Sampling

Trajectory Sampling

  • 무작위로 이전 경험을 추출하는 대신, 임의의 시작 상태들 중 하나에서 종료 상태까지 현재 정책과 모델을 따라 생성되는 에피소드 (또는 궤적Trajectory) 내의 경험들을 가치 함수 업데이트에 활용

51

52 of 81

On-Policy Trajectory Sampling

Trajectory Sampling

  • 현재 정책을 따랐을 때 도달하지 못하는 상태에 대해서는 가치 함수의 업데이트가 불필요하므로, 가치 함수의 연산 횟수가 감소

52

53 of 81

On-Policy Trajectory Sampling

Trajectory Sampling

  • 단, 한 상태에서 다른 상태로 도달할 수 있는 경우의 수가 적다면, 전체 연산량은 Dyna-Q 와 비슷할 수 있음

53

54 of 81

(Recap) Bellman Optimality Equation

Trajectory Sampling

54

55 of 81

(Recap) Value Iteration

Trajectory Sampling

55

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

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

최적 상태 가치 함수의 값이

수렴할 때까지 업데이트

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

56 of 81

Real-Time Dynamic Programming (RTDP)

Trajectory Sampling

  • Bellman Optimality Equation을 활용하여 가치 함수를 업데이트하는 Trajectory Sampling 알고리즘
  • 모든 행동 선택은 ε-Greedy가 아닌 Greedy로 이루어짐
    • 즉, 행동 가치 함수가 가장 큰 행동을 선택
  • DP의 Value Iteration과의 차이?
    • 가치 함수의 값이 수렴될 때까지 기다릴 필요가 없음
    • 모든 상태에 대해서 가치 함수의 값을 계산하는 게 아니라, Trajectory 상에 있는 상태에 대해서만 가치 함수의 값이 계산됨

​

56

57 of 81

RTDP: Pseudocode

Trajectory Sampling

57

Trajectory 내에서 전이된 상태에 대해서만

Bellman Optimality Equation을 활용하여 가치 함수를 업데이트

58 of 81

RTDP: Optimal Policy

Trajectory Sampling

  • RTDP는 다음의 조건을 만족하면 무조건 최적의 정책을 학습하는 것으로 증명됨
    • 목표 상태(예. Frozen Lake의 목적지)의 가치 함수의 값은 0으로 초기화
    • 어떤 시작 상태에서든 목표 상태로 무조건 도착할 수 있는 정책이 최소 하나 이상 존재
    • 목표 상태로 전이하는 것을 제외한 나머지 상태의 전이에는 음의 보상을 지급
    • 모든 상태에 대한 가치 함수의 초기값은 같아야 함

58

59 of 81

Decision-Time Planning

59

60 of 81

Background Planning vs. Decision-Time Planning

Decision-Time Planning

  • Background Planning
    • 현재 상태와는 상관없이, 전체적인 상태에 대한 가치 함수의 값을 업데이트하기 위하여 모델을 활용
  • Decision-Time Planning
    • 현재 상태에서 최적의 행동을 선택하기 위하여 모델을 활용

​

60

61 of 81

Heuristic Search

Decision-Time Planning

  • 고전적인 Planning 문제에서 많이 활용되었던 방법
  • 가치 함수 대신 전이한 상태의 가치를 추정하는 휴리스틱 함수Heuristic Function을 활용하여 행동을 선택
    • 가치 함수: 환경과의 상호 작용을 통해 학습되는 함수
    • 휴리스틱 함수: 인간에 의해 설계되며 별도로 학습되지 않음

​

61

62 of 81

Heuristic Search: 예. A* 알고리즘

Decision-Time Planning

  • 그래프 순회 및 경로 탐색 등에 활용되는 알고리즘
  • 총 비용 함수 f(s) = g(s) + h(s)가 핵심
    • 실제 비용 함수 g(s): 상태 s까지 실제로 확인된 비용(예. 상태 s까지의 이동 거리)
    • 추정 비용 함수, 또는 휴리스틱 함수 h(s): 상태 s에서 미래에 소요될 것이라고 예측되는 비용(예. 상태 s부터 목표 상태까지의 거리)
  • f(s)의 값이 낮은 상태부터 방문하면서, 실제 비용 함수 및 추정 비용 함수를 업데이트

62

63 of 81

Heuristic Search: 예. A* 알고리즘

Decision-Time Planning

63

Closed set, C 는

상태의 방문 여부를 기록

현재 상태에서 도달할 수 있는 상태들 중 추정된 실제 비용 함수 값보다 작은 비용을 가진 상태가 있다면 우선 순위 큐, PQ에 넣음

64 of 81

Rollout Algorithm

Decision-Time Planning

  • Trajectory Sampling: 임의의 시작 상태들 중 하나에서 종료 상태까지 현재 정책과 모델을 따라 생성되는 에피소드 (또는 궤적Trajectory) 내의 경험들로 가치 함수 및 현재 정책을 업데이트하고, 이 정책에 따라 행동을 선택
  • Rollout Algorithm: 매 행동 선택 시, 현재 상태에서 종료 상태까지 학습되지 않는 임의의 정책Rollout Policy or Default Policy과 모델을 따라 생성되는 에피소드 (또는 궤적Trajectory)에서 얻은 수익에 따라 행동을 선택
    • 보통 Rollout Policy는 무작위 또는 특정한 휴리스틱에 따라 행동을 선택

64

65 of 81

Rollout Algorithm

Decision-Time Planning

65

66 of 81

Rollout Algorithm: Pseudocode

Decision-Time Planning

66

67 of 81

Monte-Carlo Tree Search

Decision-Time Planning

  • Rollout Algorithm: 매 행동 선택 시, 현재 상태에서 종료 상태까지 학습되지 않는 임의의 정책Rollout Policy or Default Policy과 모델을 따라 생성되는 에피소드 (또는 궤적Trajectory)에서 얻은 수익에 따라 행동을 선택
  • Monte-Carlo Tree Search: 매 행동 선택 시, 현재 상태에서 종료 상태까지 학습되지 않는 임의의 정책Rollout Policy or Default Policy, 학습되는 정책Tree Policy, 그리고 모델을 따라 생성되는 에피소드 (또는 궤적Trajectory)에서 얻은 수익에 따라 행동을 선택

67

68 of 81

Monte-Carlo Tree Search: Tree Policy

Decision-Time Planning

  • 현재 상태에서 전이 가능한 모든 다음 상태에 대한 가치 함수의 값을 추정했다면, UCBUpper Confidence Bound의 응용인 UCTUpper Confidence Boundary of Tree를 활용하여 행동을 선택하는 정책

68

69 of 81

Monte-Carlo Tree Search: Phase

Decision-Time Planning

  1. [Tree Policy] Selection: (모든 전이 가능한 상태에 대한 수익의 추정이 되었다면) 하나의 상태를 UCT를 통해 선택

69

70 of 81

Monte-Carlo Tree Search: Phase

Decision-Time Planning

  • [Tree Policy] Selection: (모든 전이 가능한 상태에 대한 수익의 추정이 되었다면) 하나의 상태를 UCT를 통해 선택
  • [Tree Policy] Expansion: 선택된 상태에서 전이할 수 있는 다음 상태를 확장

70

71 of 81

Monte-Carlo Tree Search: Phase

Decision-Time Planning

  • [Tree Policy] Selection: (모든 전이 가능한 상태에 대한 수익의 추정이 되었다면) 하나의 상태를 UCT를 통해 선택
  • [Tree Policy] Expansion: 선택된 상태에서 전이할 수 있는 다음 상태를 확장
  • [Rollout Policy] Simulation: 확장된 상태에 대해서 Monte-Carlo Simulation을 통해 수익을 추정

​

71

72 of 81

Monte-Carlo Tree Search: Phase

Decision-Time Planning

  • [Tree Policy] Selection: (모든 전이 가능한 상태에 대한 수익의 추정이 되었다면) 하나의 상태를 UCT를 통해 선택
  • [Tree Policy] Expansion: 선택된 상태에서 전이할 수 있는 다음 상태를 확장
  • [Rollout Policy] Simulation: 확장된 상태에 대해서 Monte-Carlo Simulation을 통해 수익을 추정
  • Backups: 추정된 수익으로 이전 상태들의 수익 추정값을 업데이트

72

73 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

73

74 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

74

75 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

75

76 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

76

77 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

77

78 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

78

79 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

79

80 of 81

Monte-Carlo Tree Search: 예.

Decision-Time Planning

80

81 of 81

다음 시간에…

  • Function Approximation
    • 상태-행동 공간을 테이블 형태로 다루는 대신, 임의의 큰 상태 및 행동 공간을 함수적으로 근사하여 처리할 수 있는 강화 학습 기법을 소개

81