기록: UCL Course on RL 요약 및 정리 (Lecture 8: Integrating Learning and Planning)

This post covers Lecture 8: Integrating Learning and Planning (davidsilver.uk):


Lecture Goal
  • Opening remarks:
    • 지금껏 known MDP의 경우, model을 알고 있으므로 dynamic programming등 planning 기법을 이용하여 최적의 value function이나 policy를 구할 수 있었다 (이를 MDP를 푼다고 표현한다). 
    • 지금껏 unknown MDP의 경우, environment와의 상호작용(experience)을 통해 최적의 value/policy를 학습하였다 (learning). 
    • Unknown MDP를 풀 때도 experience를 통해, policy나 value만 학습하는 게 아니라, model (i.e., expected rewards and transition probability) 자체를 학습한다면 planning 기법을 사용하여 좀 더 효율적으로 MDP를 풀 수 있지 않을까? 
  • 본 강의에서는 unknown MDP를 풀기 위해 learning과 planning을 통합적으로 이용하는 model-based reinforcement learning 방법을 배운다.
    • Learning, simulation & planning, Dyna-Q, Monte-Carlo tree search

Model
  • Given an MDP \((S,A,T,R)\), a model \(M=(T,R)\) represents state transitions and expected rewards:
    • \(S_{t+1} \sim T(S_{t+1}|S_t,A_t)\)
      \(R_{t+1} = R(S_t,A_t)\)
  • Note: model은 환경 그 자체가 아니다. 환경에서 MDP를 최적화할 때 가장 핵심 요소들만 뽑아 구성한 것이라고 보면 된다. 예를 들어, 실제로 immediate reward는 random variable이지만 model은 expectation만 알면 되므로 scalar인 expected reward만 포함한다.

Value vs. Model
  • 일반적으로 value function은 state에 대한 (e.g., Chess에서 각 장기말의 현재 위치) 변화가 크다. 
    • 학습하기 어렵고 approximator를 쓸 때도 문제가 있다. Linear model은 smooth하기 때문에 pluctuation이 심한 value function을 제대로 근사하지 못할 수도 있다.
    • 또한 한 state의 value는 해당 state의 reward에만 관련있는 게 아니라, Bellman expectation equation에 따라 여러 state의 reward와 큰 연관이 있고, 어떤 transition path를 취하냐에 따라서 return의 noise도 매우 심하다.
  • 그러나 model은 environment를 더 compact하게 해석할 수 있도록 정보를 제공한다. 
    • 예를 들어, Chess에서 model은 Chess의 승리 조건(reward)과 움직이는 규칙(action을 취한대로 deterministic하게 결정) 뿐이다.
    • 또한, 한 state의 reward와 transition은 오직 그 state에서의 경험에만 의존하므로 학습하기가 상대적으로 쉽다.
    • 따라서 model은 value보다 학습하기 더 쉽고, model을 알 경우 DP나 tree search (곧 배울 Monte Carlo tree search 등) 등 planning을 통해 좋은 정책을 세울 수 있다.

Model-Free and Model-Based RL
  • Model-free RL
    • No model
    • Learn value function (or policy) from experience
  • Model-based RL
    • Learn a model from experience
    • Plan value function (or policy) from model
    • Assumptions:
      • State space and action space are known
        • 상태의 종류, 액션의 종류에는 뭐가 있는지 정도는 알아야 함
      • Typically assume conditional independence between state transitions and rewards.
        • \(\mathbb{P}[S_{t+1},R_{t+1}|S_t,A_t] = \mathbb{P}[S_{t+1}|S_t,A_t]\mathbb{P}[R_{t+1}|S_t,A_t] \)
    • Pros
      • Can efficiently learn model by supervised learning methods
        • Any supervised learning method can be used.
      • Can reason about model uncertainty
      • 실제로 풀려는 문제가 정확히 MDP인 건 아닐 때, model learning을 통해 대충 근사할 수 있다.
    • Cons
      • Two sources of the approximation error
        • Learn a model first, then construct a value function

Model Learning
  • Estimate the model from experiences (or episodes)
    • Episode \(= \{S_1, A_1, R_2, \cdots, S_T\}\)
    • Estimator \(M_{\eta} \approx M\)
  • This is nothing but a supervised learning problem
    • \(S_1, A_1 \rightarrow R_2, S_2 \\ 
         S_2, A_2 \rightarrow R_3, S_3 \\
         \vdots \\
         S_{T-1}, A_{T-1} \rightarrow R_T, S_T \)
  • Learning \(s,a \rightarrow r\) is a regression problem
  • Learning \(s,a \rightarrow s'\) is a density estimation problem
  • Pick loss functions (e.g., mean-squared error, KL divergence, etc.)
  • Find parameters \(\eta\) that minimize empirical loss

Model-based RL in a Nutshell
  • Model을 학습(learning)하여 simulation and planning으로 MDP를 풀어내는 기법
  • Learning
    • DQN (Lecture 6) 등에서 활용한 experience replay는 (one-step) experience를 (state, action, reward의 순열) 단순히 array 등의 형태로 저장공간(replay buffer)에 보관해둔 다음 minibatch를 구성할 때 저장공간에서 필요한 만큼 뽑아서 쓰는 기법
    • Model learning은, experience replay처럼 단순히 replay buffer를 쓰는 대신에, data-driven하게 experiences로 부터 environment 작동 원리를 파악하는 것
    • \((s,a,s',r)\)을 단순히 암기하는 것과, \(s,a \rightarrow s', r\)의 규칙(전이 확률)을 학습하는 것의 차이
    • Note: learning은 실제 환경과 상호작용을 통해 이루어지므로, 로봇을 움직여서 정보를 얻는 것처럼, 비용이 상대적으로 많이 든다.
  • Simulation
    • Model learning을 한단 건 결국 transition probabilities와 rewards를 예상할 수 있단 것
    • 이를 이용하여 환경과의 직접적인 상호작용 없이 임의로 experience를 생성
    • Machine learning에서 자주 활용하는 data augmentation과 비슷한 역할
    • Experience replay와 batch sampling이 DQN의 학습 안정화에 큰 역할을 하는 것처럼, simulation을 통해 임의로 experiences를 찍어낼 (augmentation) 수 있다면 학습이 자명하게 안정됨
    • Overshoot이긴 하지만 generative model, variational model을 끼얹는 것도 재밌을 듯
    • Note: simulation은 기존 학습한 model을 통해 컴퓨터 레벨에서 experience를 만들어 내는 것이므로, 비용이 상대적으로 적게 든다.
  • Planning
    • (Model learning을 통해 구한) transition probabilities와 rewards를 알면 Bellman expectation and maximization equations으로 MDP를 풀 수 있음
      • Value iteration
      • Policy iteration
      • Dynamic programming
      • Monte Carlo tree search (this lecture)
      • Minimax tree search (last lecture)
      • \(\vdots\)
    • 이미 모든 정보를 다 아는 (또는 추정한) 상태에서 최적의 경로나 policy를 계획하는 것

Examples of Models (Model Estimators)
  • 이제부터 본 강의에서 model은 model estimator이다.
  • Table lookup model
  • Linear expectation model
  • Linear Gaussian model
  • Gaussian process model
  • Deep Belief Network model

Learning: Table Lookup Model
  • \(s,a \rightarrow s', r\)을 학습하기 위해, hashmap등을 이용해서 cumulative reward at \((s,a)\), \(N(s,a), N(s,a,s')\)을 매 transition마다 저장 및 업데이트한다. 그러면:
  • \(R(s,a) = \mathbb{E}[R_{t+1}|S_t=s,A_t=a] \approx (\mathrm{cumulative\; reward})/N(s,a) \\
       T(s'|s,a) = \mathbb{P}[S_{t+1}=s'|S_t=s, A_t=a] \approx N(s,a,s')/N(s,a)\)

    • 오른쪽은 experience, 왼쪽은 table lookup을 사용해 만든 estimated MDP를 시각화한 것

Simulation
  • Model을 학습하여 예측한 transition probabilities와 rewards를 이용해 experience를 무작위로 생성할 수 있음
  • State \(s\)에서 random하게 action \(a\)를 고른 다음,
  • Table lookup 등으로 \(T(s'|s,a)\)를 모든 \(s' \in S\)에 관해 구한다. 이때 기본 가정에 의해 \(S\)에 어떤 element \(s\)가 있는지는 알 수 있으므로 for-loop 등을 돌 수 있다.
  • State transition에 관한 probability mass function을 구해서 그에 맞춰 sampling하여 다음 상태 \(s'\)를 뽑는다. Reward도 table에서 계산한다.
  • 이 과정을 반복하여 experience를 생성한다.

Simulation-Based Planning (Sample-Based Planning)
  • 사실 table lookup model등 model만 세워도 transition probabilities와 rewards를 추정하여 Bellman equations (matrix form)을 푸는 것 만으로 MDPs의 최적 policy/value를 구할 수 있다.
  • 그러나 보통은 아래와 같은 simulation-based planning (iterative methods)가 더 시간 효율적이다.
  • Simulation-based planning
    • Use the model only to generate samples
    • Sample experiences from model
    • Apply model-free RL to samples, e.g.:
      • MC/TD control
      • Sarsa
      • Q-learning

Integrating Learning and Planning
  • 당연하게도, model은 환경과 상호작용을 통한 experiences로 배우기 때문에 experiences 수가 너무 적거나 하는 이유로 (estimated) model 자체가 실제 model과 너무 차이가 많으면 estimated model을 기반으로 planning하는 model-based RL의 성능은 나빠진다.
  • 따라서 learning, planning, real experience 모두 통합적으로 사용해야 한다.
  • 이번 챕터를 통해 two sources of experience를 배웠다:
    • Real experience (sampled from true MDP)
    • Simulated experience (sampled from estimated MDP)
  • RL revisited
    • Model-free RL
      • No model
      • Learn value/policy from real experience
    • Model-based RL
      • Learn a model from real experience
      • Plan value/policy from simulated experience
        • Data augmentation을 통해 학습 안정화
    • Dyna
      • Learn a model from real experience
      • Learn and plan value/policy from real and simulated experience

Dyna-Q Algorithm


    • Model-based Q-learning이라고 보면 된다 (off-policy).
    • 참고로 Q-learning 알고리즘은 다음과 같다:
    • Dyna-Q는 real experience를 value update에 한 번만 사용하고 버리거나, DQN처럼 단순히 replay buffer에 저장하는 게 아니라, \((r,s')\)를 생성해낼 수 있는 모델을 real experience로 학습시킨다.
    • 그런 다음, 모델을 이용해 (현재 상태와 다음 상태에 관한) simulated experience를 생성해낸 뒤 다시 value를 update해서 기존 real experience에서 습득한 과거의 지식을 계속 value가 상기하도록 한다 (calibration).
    • 따라서 과거의 경험을 매우 잘 활용할 수 있다. 사골처럼.
    • 또한, 바로 다음 action을 덥썩 덥썩 취하는 게 아니라 agent 스스로 과거의 경험을 반추하는 시뮬레이션을 통해 액션을 결정하므로써 action 하나 하나의 파급력과 리스크가 큰 문제를 풀 때 유용하다.
  • 결론은, 더 발전된 Dyna-Q+나 Dyna-2 사용하는 게 좋다.
    • Exploration을 잘해서 중간에 환경이 바뀌어도 RL 잘 수행 (방문하지 않은 state에 방문하는 것을 장려함)

Simulation-Based Search
  • Opening comment: Dyna-Q 등 지금껏 배운 model-based RL은, 전체 MDP를 모사하기 위해 model을 학습하였고, 이를 통해 experience를 인공적으로 만들어내면서 value function을 update하였다. 그러나 현재 상태에서 당장의 액션을 잘 취하기 위해 learned model을 사용할 방법은 없을까? Simulation-based search가 한 가지 해법을 제공한다.
  • Simulation-based search:
    • 학습한 model을 이용해 episode sampling을 (simulation) 하면서, 
    • 현재 state를 root로 하는 tree를 만들어
    • 미래 state들의 value를 (implicit/explicit하게) 저장 및 업데이트하고,
    • 최종적으로는 가장 value가 높은 action을 찾는 (search) 방법론
    • Dyna-Q는 one-step experience만 sampling 하지만, simulation-based search는 (예를 들어 Monte-Carlo evaluation을 쓴다면) termination state까지 쭉 simulation을 하여 full episode 전체를 샘플링한다.
  • Note: search 자체는 RL이 아니다. RL 알고리즘 내부의 state update 단계를 위해서 쓰는 것.
  • Forward search
  • Simulation-based search
    • Apply model-free RL to simulated episodes
      • Monte-Carlo control을 사용하면 Monte-Carlo search
      • Sarsa를 사용하면 TD search
  • Simple Monte-Carlo search
    • Goal: current state \(S_t = s\)의 각 action의 value를 추정하여 어떤 action을 취하는 게 가장 좋을지 판단 (max search)
    • Assumption: 학습한 model은 있고, simulation 중 사용할 policy도 있음 (random policy 등)
    • For each action \(a \in A\) at \(s_t\),
      • Simulate multiple episodes (\(K\)-times) from current state \(s_t\) and action under given model simulation policy \(\pi\)
        • \(\left\{s_t,a,R^{k}_{t+1},S^{k}_{t+1},A^{k}_{t+1},\cdots,S^{k}_{T}\right\}^{K}_{k=1}\sim M_{\eta},\pi\)
      • 각 episode에서 얻은 결과 (return) 취합 (Monte-Carlo evaluation)
        • \(Q(s_t, a) = \frac{1}{K}\sum_{k=1}^{K}G_t\)
        • 이는 \(q_{\pi}(s_t,a)\)로 수렴
    • \(Q(s_t,a)\) 최댓값을 주는 액션 하나를 택한다.
    • Note: learned model이 아니라 실제 환경과 상호작용을 통해 최댓값을 찾아내려 한다면 매 episode 마다 state \(s_t\)로 실제 물리적으로 되돌아가야 한다 (예: 로봇 옮기기). Model learning을 통해 이런 번거로운 과정을 줄일 수 있다. 이게 기존 Monte-Carlo value iteration 과의 실질적인 차이점이다. 실제 물리 공간에서 환경과 상호작용하는 게 컴퓨터로 시뮬레이션하는 것 만큼 매우 빠르고 위험요소도 없다면 (교통사고 등) 굳이 모델을 학습하고 시뮬레이션할 필요가 없을지도.

Monte-Carlo Tree Search
  • Opening comment: 굳이 simple MC search에서 complete episode를 sampling 해놓고 시작 state의 action-value만을 추정하고 episode 중간에 선택한 수많은 action에 관한 정보는 다 날려버릴 필요가 있을까? 중간에 방문한 state와 action에 관한 정보도 search 과정에서 tree에 저장해두면 좀 더 efficient하게 search할 수 있을 것이다 (즉, simulation policy \(\pi\)를 개선).
  • MCTS: episode sampling하면서 episode 내의 \((s, a)\)에 관한 정보도 (action-value) 저장해두자. Simulation policy \(\pi\)도 가만히두지 말고 점진적으로 개선하자. MCTS를 이용하면 주어진 model에 관해 최적의 \(q_{*}(s_t,a)\)에 수렴하는 \(Q(s_t,a)\)를 구하여 action 선택에 사용할 수 있다.
  • Algorithm
    • AlphaGo의 알고리즘과 모델
    • Note: 실제 AlphaGo 알고리즘은 MCTS와 단순한 RL보다 더 복잡한 구성 요소들이 많다. 여기서는 간략하게 나마 RL 분야에서 MCTS와 simulation-based forward search의 이점만 이해하고 넘어가자.
  • 위 알고리즘은 다음처럼 evaluation과 simulation 부분으로 나눠서 생각할 수 있다.

  • 이렇게 현재 state에서 모든 action에 대한 \(Q(s_t,a)\)를 구한 뒤 Monte-Carlo control을 통해 최종 action 선택 (global policy improvement)
  • Pros
    • A highly selective best-first search
    • Uses sampling to break the curse of dimensionality
      • 굳이 모든 state-/action-space 탐험할 필요가 없고, sampling을 하면서 얻어걸린 space(와 \(\epsilon\)-greedy로 무작위로 선택된 space)만 탐험하면 됨
    • Computationally efficient, anytime, parallelizable 
      • Anytime: an anytime algorithm is an algorithm that can return a valid solution to a problem even if it is interrupted before it ends (즉, 알고리즘을 언제든지 종료해도 최적은 아니지만 그래도 쓸만한 유효한 해를 뱉어냄).
  • Other great materials

TD Search
  • Using TD instead of MC (bootstrapping)
  • TD search applies SARSA control to sub-MDP from the current state
    • MC tree search applies MC control
  • MC vs. TD
    • TD learning reduces variance but increases bias
    • TD learning is usually more efficient than MC
    • TD(\(\lambda\)) can be much more efficient than MC
  • TD search

Dyna-2
  • Long-term memory is updated from real experience
  • Short-term memory is updated from simulated experience

댓글

댓글 쓰기

이 블로그의 인기 게시물

기록: UCL Course on RL 요약 및 정리 (Lecture 6: Value Function Approximation)

이미지
This post covers  Lecture 6: Value Function Approximation (davidsilver.uk)   The entire course materials can be found on the following page:  Teaching - David Silver . Lecture Goal Learn how to deal with a large-scale (potentially continuous) state space with RL Learn value function approximation Learn Deep Q-Network (DQN) and batch methods Credit:  Find order of polynomial approximation and LeastSquares for given datapoints Value Function Approximation Lookup table Table store an entry for each lookup index. Value-state Index = \(\forall s \in S\), where \(S\) is a finite and discrete state space Entry = \(V(s)\) Action-state Or every state-action pair \(s, a\) has an entry \(Q(s,a)\) Or every state \(s\) has entries \(Q(s,a)\) for all actions \(a \in A\) So far, we have represented a value function by a lookup table. Large MDPs Memory inefficiency : too many states or actions to store in memory Too slow to learn the value of each state individually Note: neighboring states might st
자세한 내용 보기

기록: UCL Course on RL 요약 및 정리 (Lecture 9: Exploration and Exploitation)

이미지
This post covers not only  Lecture 9: Exploration and Exploitation (davidsilver.uk)  but also : 'Reinforcement Learning' 카테고리의 글 목록 (yjjo) The Multi-Armed Bandit Problem and Its Solutions (lilianweng.github.io) Bayesian Bandits - Thompson Sampling (tistory.com) The entire course materials can be found on the following page:  Teaching - David Silver . Lecture Goal MDP를 풀 때 exploration과 exploitation 중 어느 한 쪽만 사용하면 optimality에 도달하지 못한다 (trade-off). 본 강의에서는 둘 사이의 균형을 맞추는 알고리즘을 소개한다. Credit: UC Berkeley Intro to AI course lecture 11 Takeaway Use (Bayes-) UCB algorithms Exploration vs. Exploitation Dilemma Exploitation: make the best decision given current information E.g., go to your favorite restaurant Exploration: gather more information E.g., try a new restaurant Dilemma The best long-term strategy may involve short-term sacrifices and risks How does an agent obtain enough information to make the best overall decisions with the lowest sacrifices? [In-A-Nutshell] Key Principles an
자세한 내용 보기

KAIST 회고 (1): 공부법 정리

이미지
(2021-08-29 초안 작성) 성적을 잘 받기 위한 기본 정리 1: 시험과 과제 마감일은 우리를 기다려주지 않는다 내용) 오늘 들은 강의는 이틀 내에 복습하라 해설) 엘리베이터 앞에 몇 초만 늦게 도착해도 먼저 엘리베이터에 타고 올라간 사람보다 많게는 수 분 가량 늦을 수 있다. 학교는 학생의 학습 능력을 매 초 마다 연속적으로 체크하지 않는다. 억울하지만, 시험 당일이나 과제 제출 당일에 퍼포먼스를 제대로 못 보여주면 그 후폭풍은 거대하다. 예를 들어, 한 학기 동안 매번 당일 수업 내용으로 다음 날 시험을 보는 상황을 가정하자. 매일 복습을 하는 학생과 항상 수업 이틀 뒤에 복습을 하는 (즉, 시험치고 다음 날) 학생이 있다면, 해당 학기가 끝난 뒤 두 학생의 이해도는 별반 차이 없을 것이다. 둘 다 공부를 제대로 했다는 가정 하에, 복습을 며칠 미룬다고 큰 차이가 날 리가. 다만 시험 성적은, 앞의 학생은 충분히 높을 것이고, 뒤의 학생은 비교적 낮을 것이다 (수업을 듣자마자 모든 걸 깨닫지 않는 이상). 이 예시에서 두번째 전략을 취한 학생은 매우 억울할 것이다. 그러나 이게 현실이다. 시험은 '당일까지'의 이해도를 측량한다. 과제도 마찬가지다.  현실에서는 시험이나 과제 전까지 충분히 시간을 주지 않느냐 반문할 수 있다. 그러나 매 강의는 시간 의존적이다. 오늘 듣는 강의는 필연적으로 지난 수업 일이나 저번 주, 심지어 선수 과목의 내용과 밀접한 연관이있다. 따라서, 당연히도, 오늘 들은 강의 내용을 다음 수업일까지 복습하지 않는다면, 다음 수업일의 강의 내용을 이해하는 게 매우 힘들어지고, 수업 시간에 제대로 이해하지 못하니 복습할 내용과 다시 공부할 내용은 눈덩이처럼 불어난다. 더 심하게는, 수업 시간에는 하나도 이해 못하고 시간을 날린 뒤, 방에 돌아와서 당일 강의록을 보면서 스스로 처음부터 공부해야 할 수 있다. 실제로 KAIST에서도 많은 학생들이 이런 식으로 공부하면서 강의 하나를 이해하는 데에 드는 시간을 두 배 혹은 그
자세한 내용 보기