[RL] David Silver RL Lecture 8: Integrating Learning and Planning

1. Introduction

지난 강의까지는

1. 경험으로부터 직접 policy를 학습. (agent가 경험을 쌓고, 그 경험으로부터 적집적으로 policy update)
2. 경험으로부터 직접 value function을 학습.

이번 강의의 목표는 다음과 같다.

1. 경험으로부터 model을 학습하는 것
2. planning(model을 알고있을 때 Value function, policy를 학습하는 것)을 통해 value function과 policy를 만든다.
3. learning과 planning을 하나의 아키텍쳐로 합치는 것

1.1 Model-Based and Model-Free RL

Model-Free RL

• No model
• 경험으로부터 value function (혹은 policy)를 Learn한다.

• 환경과 상호작용을 통해 동작한다.

Model-Based RL

• 경험으로부터 모델을 학습한다.
• 모델로부터 value function(혹은 policy)를 plan한다.

• Model이 간소화됐다. → 실제 환경이 아니다. (실제 환경과 다른 부분이 있을 수도 있다.)
• 실제 환경을 모방한 것과 상호작용

---

2. Model-Based Reinforcement Learning

2.1 Model-Based RL

Policy → action → experience

만들어진 경험을 통해 바로 policy/value를 수정 : direct RL
경험으로부터 model을 만들고 planning을 통해 policy/value를 수정 : model-based RL (planning : model을 아니까 MDP를 푼다는 것)

Advantages:

• supervised learning 방법에 의해 model을 효율적으로 학습이 가능
• model의 불확실성에 대해서도 사용할 수 있다.
  • 모델 자체가 환경의 동작을 명시적으로 학습하기 때문에
  • 학습한 모델이 얼마나 정확한지 평가 가능
  • 결정 내릴 때 불확실성을 반영 가능

Disadvantages:

• model을 학습하고, value function을 만들어야함
  • error의 가능성을 2번 거쳐야한다.

What is Model?

• Model \(M\)은 \(η\)로 파라미터화 된 MDP <\(S,A,P,R\)>의 표현형이다.
• 우리는 State S와 action A를 알고 있다고 가정한다. (ex 체스)
• 그래서 model M = <\(P_η, R_η\)>을 나타내는 것이다.

• state transitions와 reward는 서로 독립적이라고 가정한다. (즉, 따로 구할 수 있다.)

2.2 Model Learning

• 목표 : model \(M_η\)을 경험 {\(S_1, A_1, R_2, ... ,S_T\)}로 부터 추정한다.
• 이것은 supervised learning 문제로 생각할 수 있다. (input과 output을 앎)

• s,a → r은 regression 문제
• s,a → s’ 은 density estimation 문제
• 손실 함수를 설정한다 (ex. MSE, KL divergence)
• empirical 손실을 최소화하는 파라미터 \(η\)를 찾는다.

Examples of Models

• Table Lookup Model
• Linear Expectation Model
• Linear Gaussian Model
• Gaussian Process Model
• Deep Belief Network Model
• …

Table Lookup Model

• 방문하는 곳마다 기록을 해 평균을 구한다.
• 단점 : 경험하지 못한 transition에 대해서는 알 수 없다.

비슷한 방식

• 각 time-step t마다 experience tuple을 기록한다. <\(S_t, A_t, R_{t+1}, S_{t+1}\)>
• <\(s,a,.,.\)>를 알려면 기록된 s,a를 하는 tuple중에서 sampling하면 된다.

AB Example

• 이것이 table lookup model을 경험으로부터 만든 것이다.

2.3 Model Planning

• 모델 \(M_η\) = <\(P_η, R_η\)>이 주어졌고, MDP <\(S,A,P_η,R_η\)>을 푼다.
• 원하는 planning alrogithm을 사용한다.
  • Value iteration (MDP를 알 때, DP 사용)
  • Policy iteration (MDP를 알 때, DP 사용)
  • Tree search

DP가 아니라 Sample-Based Planning을 사용할 수도 있다.

Sample-Based Planning

• 간단하지만 강력한 접근법이다.
• Model을 만들어서 MDP를 아는데, Model은 sample을 만들어내는데만 사용을 하고 model-free 방식으로 sample을 활용한다.

• Monte-Carlo control
• Sarsa
• Q-learning 등을 활용 할 수있다.

Sample-based planning은 효과적일 때가 많다.

• Naive full-width backup은 일어날 수 있는 모든 경우를 다 찾아보는 것이다.
• Sample-based planning은 자주 일어나는 사건들에게 집중을 할 수 있다.
  • 자주 발생하는 sample은 더 많이 발생하기 때문
  • curse of dimensionality에서 벗어날 수 있다. 모든 상태를 계산하지 않아도 되고 중요 부분만 효율적으로 탐색해 계산량이 안늘어나기 때문

Back to the AB Example

우리가 모델을 만든다면, 우리는 무한한 데이터를 얻는것과 같다.

Planning with an Inaccurate Model

imperfect model <\(P_η, R_η\)> ≠ <\(P, R\)>

model-based RL의 성능은 모방한 MDP <\(S,A,P_η, R_η\)>의 optimal policy가 최대이다.
즉, Model-based RL은 추정 모델이 좋은 만큼 좋다.

모델이 부정확하다면, planning process도 suboptimal policy로 계산될것이다.

해결책

1. model이 틀렸다면, model-free RL을 사용
2. model의 부확실성까지 설명한다. (정확도는 몇 %이다.)

---

3. Integrated Architectures

3.1 Real and Simulated Experince

경험은 두가지 종류가 있다.

• Real experience : environment로부터 sampled (true MDP)

• Simulated experience : model로부터 sampled (approximate MDP)

3.2 Integrating Learning and Planning

• Model-Free RL
  • No model
  • real experience로 부터 value function(또는 policy) 학습
• Model-Based RL (using Sample-Based Planning)
  • real experience로 부터 모델을 학습한다.
  • 학습된 모델로부터 simulated experience을 만들고 value function(또는 policy) Plan한다.
• Dyna
  • real experience로 부터 모델을 학습
  • real and simulated experince로 부터 value function(또는 policy)를 Learn and Plan

3.3 Dyna Architecture

• Model-based learning에서는 experience를 directly하게 value/policy로 가는 것이 없었는데, Dyna는 두 방식이 다 있다.

Algorithm sudo code

d. (direct RL) Q-learning

• a~d까지 과정은 배운 model-free 과정

e. (Model Learning) 새롭게 생긴 부분, R, S’를 통해 Model(S,A)를 update 계산을 쉽게 하기 위해서 deterministic environment 이라고 가정

• Model을 알게 되었으니 Planning 방법이 나온다.

f. (Planning) planning을 통해 Q Update, 가봤던 state중 S를 뽑고, S에서 했던 action중 A를 뽑아서 Model(S,A)를 통해 R, S’를 만들어 Q를 Update한다.

그럼 이것을 왜하느냐? → 실제 환경과의 교류가 너무 비싸다.

실제 환경과의 교류가 값이 싸다면 실제 데이터 가지고 학습을 하면 되지만,
실제 데이터를 얻기가 너무 힘들어 한번 얻고 그걸로 모델을 만들고 그것을 통해 샘플을 뽑아 여러번 업데이트한다.

Dyna-Q on a Simple Maze

아주 적은 data를 가지고 squeeze해 학습을 할 수 있다.

지금 그래프는 episode가 2일 때부터 나와있는데 1일 때는 어떨까?
⇒ 문제마다 성능이 다르다.

이 문제에서는 1일 때도 똑같다.
하지만 만약 벽이 아니라 함정이라서 -1의 reward를 받는 것 이었다면 이동 마다 planning을 통해서 가면 안된다는 것을 알고 Dyna의 성능이 더 좋았을 것이다.

4. Simulation-Based Search

Forward Search

예를들어 바둑을 두는데 170수를 고려할 때 30번째 수는 고려 안해도 된다.

current state is particularly important

• Forward search algorithm은 lookahead(미래를 보는 것)를 통해 최선의 action을 선택한다.
• current state \(s_t\)를 root로 search tree를 생성, MDP의 model을 통해 미래 경우의 수를 생성한다.
• 전체 MDP를 풀 필요 없이, 지금 시작하는 sub-MDP만 풀면 된다.

4.1 Simulated-Based Search

• sample-based planning을 이용해 forward search를 한다.
• model을 통해 현 시점인 \(s_t\)로 시작하는 여러 episode를 생성한다.

• 생성된 episodes에 대해서 model-free RL을 적용한다.

4.2 Monte-Carlo Search

Simple Monte-Carlo Search

Model \(M_v\)가 있고 simulation policy \(π\)가 있다.

각각의 모든 action a에 대해서

• 현재 (real) state \(s_t\)로 부터 K개의 episodes를 simulate한다.

• 평균 return으로 actions를 평가한다. (Monte-Carlo evaluation)

최대 value를 만드는 (real) action을 선택한다.

Monte-Carlo Tree Search (Evaluation)

Model \(M_v\)가 있고 simulation policy \(π\)를 통해 \(s_t\)에서 시작하는 K개의 episode simulate한다.

visited state와 actions를 포함하는 search tree를 만든다.

states Q(s,a)를 episode의 평균 return으로 평가한다.

search가 끝난후 최대 value를 만드는 현재의 (real) action을 선택한다.

Monte-Carlo Tree Search (Simulation)

MCTS에서 simulation policy인 \(π\)도 improve 하고 싶다.

각 simulation은 두 단계로 구성되어있다. (in-tree, out-of-tree)

• Tree policy (improves) : Q(S,A)를 최대화 하는 action 선택
  • tree안에 있기 때문에 다 아는 값
• Default policy (fixed) : 랜덤하게 action 선택
  • tree 밖에 있기 때문에 Q값을 모른다.

Repeat(each simulation)

• Evaluate : MC evaluation으로 state Q(S,A) evaluation
• Improve : tree policy, ε-greedy (Q)
  • ε-greedy하게 선택하므로 improve된다.

Monte-Carlo control은 simulated experience가 적용된다.

Q(S,A)는 optimal serach tree(\(q_*(S,A)\))로 수렴한다.

• Tree Policy에서는 greedy하게 선택을 하고
• Default Policy에서는 random하게 action을 선택한다.
• 좋은 결과가 나온다면 Tree policy로 올라가고
• 안좋은 결과가 나온다면 새로운 node 생성해 다시 action

Advantages of MC Tree Search

• 처음 선택하는 수는 굉장히 강력하다. (많은 simulation을 통해)
• state를 dynamically하게 평가한다. (DP는 full-width backup이라 다르다.)
  • 전체를 평가하는 것이 아닌, 현재만 평가하기 때문이다.
• sampling을 이용하기 때문에 차원의 저주를 벗어날 수 있다.
• Model이 black-box여도 상관 없다.
  • 동작 방식을 몰라도 sample이 나올 수만 있으면 된다.
• 계산이 효과적이고, 병렬성이 좋다.

4.3 Temporal-Difference Search

MC인지 TD인지는 중요하지 않다. 현재 상황으로 국한지어서 forward search로더 나은 선택을 하는게 목표

• Simulation-based search
• TD대신에 MC를 쓴다. (boostrapping)
• MC tree search는 현재부터의 sub-MDP에 MC control를 적용한다.
• TD search는 현재부터의 sub-MDP에 Sarsa를 적용한다.

MC vs TD search

• model-free RL에서 bootstrapping은 효과적이다.
  • TD learning은 분산은 줄이지만 bias는 올린다.
  • TD learning은 주로 MC보다 효과적이다.
  • TD(λ)는 MC보다 훨씬 더 효과적이다.
• simulation-based search에서도 bootstrapping은 효과적이다.
  • TD search는 분산은 줄이지만 bias는 올린다.
  • TD search는 주로 MC search보다 효과적이다.
  • TD(λ) search 는 MC search 보다 훨씬 더 효과적이다.

TD Search

• 현재 (real) state \(s_t\)로 부터 episode를 simulate한다.
• action-value function Q(s,a)를 평가
• simulation의 매 단계마다 Sarsa를 통해 action value를 update

• action-value Q(s,a)를 기반으로 action 선택 (ε-greedy)
• Q에 대한 function approximation을 할 수도 있다.

4.4 Dyna-2

Dyna-2에서 agent는 2개의 feature weights를 저장한다.

• Long-term memory
• Short-term (working) memory

Long-term memory는 TD learning을 통해 real experience에 의해 update된다.

• 일반적인 영역의 어떤 episode에도 적용이 가능하다.

Short-term memory는 TD search를 통해 simulated experience에 의해 update된다.

• 현재 상황에 대한 특정 지식만 적용이 가능하다

value-fuction은 long and short-term memories의 합이다.

맨 위로 이동하기

RL Lecture 카테고리 내 다른 글 보러가기