[CS294] Lecture 2 : Supervised Learning and Imitation

UC Berkeley의 강화학습 강의 CS294(2018 Fall semester)를 정리한 포스트입니다.

코스 전체에서 다루는 주제입니다. (자세한 항목은 syllabus 참조하시기 바랍니다.)

  1. From supervised learning to decision making
  2. Model-free algorithms: Q-learning, policy gradients, actor-critic
  3. Advanced model learning and prediction
  4. Exploration
  5. Transfer and multi-task learning, meta-learning
  6. Open problems, research talks, invited lectures


포스트 목차

지도학습과 강화학습 용어 정리

CS294-02-01 기존 지도학습중에서 Classification task를 강화학습의 표기로 이어서 설명한다.

매 시각 \( t \)마다 관측과 분류를 한다고 가정하면, 기존 이미지 input은 관측(observation) \( o_{t} \)로 표기되고, 동물의 종류를 구분하는 대신 agent의 행동(action)을 구분한다면 output은 \( a_{t} \)가 된다. observation \( o_{t} \)가 주어졌을 때 action \( a_{t} \)의 확률분포를 내뱉는 것은 policy \( \pi_\theta(a_{t}|o_{t}) \)이고, \( \theta \)는 뉴럴넷과 같은 파라미터가 된다. \(o_{t}\)는 state \(s_{t}\)로부터 나온다.

CS294-02-02

\( o_{t} \)와 \( s_{t} \)의 관계를 좀 더 설명하면, 위 그림을 보면 영양이 치타에게 쫓기고 있는데, 이 사진은 픽셀로 표현된 관측 \( o_{t} \)이고, state \( s_{t} \)는 두 객체의 (역학적) 상태라고 볼 수 있다. 우리는 똑똑하게도 사진 \( o_{t} \)만 보고도 state \( s_{t} \)를 알 수 있지만 기계는 그렇지 못하다. (학습을 해야한다.) 이 때 누군가 운전해와서 자동차가 치타를 가리게되면 관측 \( o_{t} \)는 변하지만 치타와 영양의 상태 \( s_{t} \)는 변하지 않는다.

CS294-02-03

따라서 state \( s_{t} \), observation \( o_{t} \) 그리고 action \( a_{t} \) 의 관계를 그래프로 그려보면 위와같다. 그리고 state \( s_{t} \)에서 action \( a_{t} \)를 취했을때 \( s_{t+1} \)로 가는 확률을 \( p(s_{t+1}|s_{t},a_{t}) \)로 나타낸다. 이때 \( s_{t} \)에서 \( s_{t+1} \)로 갈때 \( s_{t-1} \)과는 독립적이다. 이를 Markov property라고 한다. 다시말해, 과거 상태 \( s_{t-1} \)와 현재 상태 \( s_{t} \)가 주어졌을 때의 미래 상태의 조건부 확률 분포 \( p(s_{t+1}|s_{t},a_{t}) \)가 과거 상태와는 독립적으로 현재 상태 \( s_{t} \)에 의해서만 결정된다는 것을 뜻한다.

간혹 어떤 논문에서는 state를 unknown variable 이라 x로 두고, 러시아어에서 앞글자를 따 action을 u라고 표기하기도 한다. (feat. Lev Pontryagin)


Imitation Learning

CS294-02-04

운전하는 사람으로부터 observation \( o_{t} \)와 사람의 action \( a_{t} \)의 데이터를 쌓아서, \( \pi_\theta(a_{t}|o_{t}) \) 를 지도 학습하는 것을 behavior cloning이라고 한다. 일반적으로는 잘 안된다. training data에 없던 data가 test에 나온다던지, 애초에 학습데이터의 사람의 action이 bad action이었던지, 사람이 비슷한 상황 \( o_{t} \)에 대해 서로 다른 action \( a_{t} \)를 취한다던지, 여러 이유가 있을 수 있다.

CS294-02-05

distributional drift (distribution mismatch) problem

그러나 본질적인 문제는 여기에 있다. 학습 알고리즘이 아무리 좋다해도 약간의 오차가 발생 할 수 있는데, 처음에는 매우 미세한 차이로 시작하더라도, 그 차이들이 계속 반복되면 결국엔 원래의 학습 데이터와 큰 차이로 나타나게 되는 것이다. 자율주행을 예로들면, 학습데이터의 패턴 및 경로를 따라서 잘 운전해 나가다가 아주 조금씩만 핸들이 틀어져도 종점에서는 크게 차이나는 것이다. 위 그림에서 검정색 선이 학습데이터의 경로 \( p_{data}(o_{t}) \)이고, 빨간 선이 학습된 경로 \( p_{\pi_{\theta}}(o_{t}) \)이다. 이때 우리는 어떻게 해야 \( p_{data}(o_{t}) = p_{\pi_{\theta}}(o_{t}) \)로 만들 수 있을까?


Imitation Learning 개선

Stability

CS294-02-06 End to End Learning for Self-Driving Cars,Bojarski et al. ‘16, NVIDIA 논문에서는 왼쪽, 중앙, 오른쪽 카메라를 놓고 학습을 시켰다. 왼쪽 카메라는 오른쪽으로 핸들을 틀도록 bias를 갖게 될 것이고, 오른쪽 카메라는 왼쪽으로 핸들을 틀도록 bias를 갖게 될 것이다. 따라서 상호보완을 해주므로 중앙만 보고 갈때보다 안정적으로 학습이 가능하다고 한다. 이것은 자율주행에 한정적인 방법이지만, 일반화시켜 말한다면 오른쪽 그림과 같다. Trajectory distribution에서 sampling하고 Noise를 Correct 해나가는 것이다.

DAgger: Dataset Agrregation

A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning, Ross et al. ‘11

DAgger은 distributional drift 문제를 해결하였다.

목표 : 학습데이터를 $ p_{data}(o_{t}) $ 대신에 $ p_{\pi_{\theta}}(o_{t}) $에서 모으는 것이다.
어떻게? 그냥 $ \pi_{\theta}(a_{t}|o_{t}) $를 돌린다.
그러나 labels $ a_{t} $가 필요하다.

  1. 사람의 데이터 $ \mathcal{D} = \{ o_{1},a_{1},…,o_{N},a_{N} \}$ 을 모아서(사람이 직접 운전을 해서) $ \pi_{\theta}( a_{t} | o_{t} ) $ 를 학습시킨다.
  2. $ \pi_{\theta}(a_{t} | o_{t}) $를 돌려서 (자율주행을 시켜서) $ \mathcal{D_{\pi}} = \{ o_{1},…,o_{M} \}$ 을 얻는다.
  3. 사람이 $ \mathcal{D_{\pi}} $에 대해 action $ a_{t} $ label을 달아준다.
  4. $ \mathcal{D} \leftarrow \mathcal{D} \cup \mathcal{D_{\pi}} $ 원래의 데이터셋과 합쳐준다.
  5. 1~4를 반복한다.
  • 문제점 : 사람의 노동력이 너무 많이 들어간다.

어떻게 해야 더 많은 데이터(노동력) 없이 성능을 올릴 수 있을까?

Mimic Expert

만약 우리 모델이 전문가를 정확하게 모방하되 overfit 하지 않는다면 성능을 올릴 수 있을 것이다. 그렇다면 왜 전문가를 모방하는데 실패하였는가?

  1. Non-Markovian behavior:
    • Markov property를 이용한다면 과거의 상태에 독립적으로 현재상태에서 최적의 선택을 해야하는데, 사람은 그렇지 못하다. 즉, Markovian behavior인 $ \pi_{\theta}(a_{t} | o_{t}) $에서는 현재 상태에만 의존해서 행동해야하는데, 실제로는 지난 관측들까지 고려하는 $ \pi_{\theta}(a_{t} | o_{1},…,o_{t}) $인 것이다.
    • 개선: 지난 상태들(history)을 반영하기위해 RNN(Recurrent Neural Network)을 사용한다. 그 중 LSTM이 주로 사용된다. CS294-02-07
  2. Multimodal behavior:
    • 사람은 가끔 왼손으로 운전했다가, 오른손으로 운전했다가, 슬펐다가 기뻤다가 등등 데이터에 영향을 주는 많은 (예측할 수 없는) 요인을 갖고 있다. 따라서 같은 상황에서도 다른 선택을 한다.
    • 개선:
      1. Output Mixture of Gaussians : 최종 행동을 뽑을때 하나의 Gaussian에서 뽑는 것이 아니라 여러개의 Gaussian을 합쳐서 뽑는다. 단순한 방법이다.

      2. Latent variable model : 일반적으로 사용되긴 하지만 다소 복잡하다. Output 은 하나의 Gaussian을 내뱉도록 그대로 두고, 중간에 random noise를 더하여 학습시킨다.
        • Conditional variational autoencoder
        • Normalizing flow/realNVP
        • Stein variational gradient descent
      3. Autoregressive discretization : setup이 약간 지저분하지만 Latent variable model보다는 단순하다. softmax를 통해 이산화된 확률분포를 뽑아낸다. 이 확률분포를 통해 샘플링을 한다. 또다른 네트워크에 입력으로 넣어주고 다시한번 확률분포를 뽑아낸다. (첫번째 뽑아준 값을 condition으로 하여 두번째 값을 뽑아내는 셈이다.) 이 과정을 n번 반복하여 n dimension의 출력을 뽑아내게 된다.

CS294-02-08


Case study

Trail following as classification

A Machine Learning Approach to Visual Perception of Forest Trails for Mobile Robots, Giusti et al., ‘16 논문에서는 Quadrotor을 모방 학습을 통해 숲속길을 따라 주행할 수 있게 하였다. input으로는 Monocular RGB 카메라만을 사용하면서도 Distributional drift문제를 개선하였다. 이를 CNN을 통해 처리하였고, output은 왼쪽, 오른쪽, 앞 세가지의 label을 사용하였다. 해결 포인트는 End to End Learning for Self-Driving Cars에서 언급한것중 하나대로 카메라를 왼쪽, 앞, 오른쪽 세개를 사용하는 것이다. 사람이 머리에 카메라를 달고 숲속을 걸어다니며 약 20k 장의 학습데이터를 모았다. CS294-02-09

Imitation with LSTMs

From virtual demonstration to real-world manipulation using LSTM and MDN, Rahmatizadeh et al., ‘16 논문에서는 박스 옮기는 로봇을 학습시키는 연구를 소개한다. 가상세계에서 로봇을 학습시킨 후 현실세계에서 테스트한다. Non-Markovian behavior를 LSTM으로 다루었다. 또한 Mixture Density Network(MDN)을 사용하여 Multimodal behavior문제 또한 개선하였다. CS294-02-10

Multi-Task manipulation with inexpensive robots

Vision-Based Multi-Task Manipulation for Inexpensive Robots Using End-To-End Learning from Demonstration, Rahmatizadeh et al., ‘17 논문은 바로 위에 언급한 논문의 저자와 본 강의의 교수가 함께 작성한 논문이다. 일단 제목에서도 나타내듯이 비교적 저렴한 비용으로 장비 셋팅을 하였다. 집게가 달린 6-axis Lynxmotion AL5D robot을 사용하였고, 로봇팔에 카메라를 달아 input으로 사용하였다. Leap motion, Playstation controller까지 합쳐서 총 500달러가 들었다고 한다. 코드까지 공개하며 독자들에게 실험셋팅을 해볼 것을 권유하고 있다. 이러한 셋팅을 이용하여 사람이 로봇을 컨트롤 한 것을 학습하였다. 시도한 테스크는 물건을 집고 옮기고, 밀고, 닦고 등 다섯가지이다. 윗 논문과 마찬가지로 LSTM을 사용하였고, One-hot vector을 함께 넣어줌으로써 multi task를 제어하였다. 또한 VAE-GAN구조를 결합하여 좀더 안정적인 학습을 한다. CS294-02-11

Other topics in imitation learning

  • Structured prediction:
    • 번역 테스크에서, where are you?라는 질문에 I'm in work라는 대답은 적절치 않다. 따라서 work를 지우고 I'm in school로 바꾸어준다. 요점은, output간의 관계를 고려해서 의사결정에 도움을 준다는 것이다. DAgger을 이용해 더 적절한 답안을 찾아내도록 보완가능하다.
  • Inverse reinforcement learning
    • 행동을 모방하는 대신, 목표가 무엇인지 추론한다. (나중에 다시 다룬다.)

Imitation Learning의 한계

  • 사람이 데이터를 가공해야하는데, 보통은 한계가 있다.
    • 그러나 딥러닝은 데이터가 많아야 잘 작동한다.
  • 어떤 테스크는 사람조차 제대로 못한다. (하늘을 날아다니거나, 모터를 제어하는 등)
  • 사람은 알아서 학습하는데 기계는 그러기 힘들다.
    • 스스로의 경험에 의한 무제한적인 데이터가 필요하다.
    • 연속적으로 스스로 학습해야한다.

Reward and Cost Function

agent가 한 행동에 대한 평가를 하기위해 보상(reward)과 처벌(cost)을 정의한다. cost function을 $ c(s_{t},a_{t}) $로 표기하고, reward function을 $ r(s_{t},a_{t}) $로 표기한다.

$ r(s_{t},a_{t}) = -c(s_{t},a_{t}) $

두가지 형태의 정의가 있다. 하나는 log probability 로 정의하는 것이고, 또하나는 zero-one으로 정의하는 것이다.

$ r(s,a) = \log p(a=\pi^\star (s) | s) $

action $ a $ 가 state $ s $ 에서의 optimal일 확률 (정답일 확률)에 $ \log $를 씌워서 정의한다. classification task에서의 loss function과 유사하다.

$ c(s,a) = $

action $ a $ 가 state $ s $ 에서의 optimal인 경우 (정답인 경우) 0점을 주고, mismatch인 경우 (틀린 경우) 1점의 처벌을 준다.

Distribution mismatch analysis with cost function

Cost function을 이용해서 위에서 보았던 distribution mismatch(drift)에 대한 분석을 해보자.

CS294-02-12

DAgger이 없다면 distribution mismatch에 의해 빨간 선처럼 어긋난 경로로 가게될 것이다. 이것이 얼마나 어긋났는지, 얼마나 잘못된 것인지 cost function을 통해 나타내보자. time 축을 time step $ T $로 정의하고, cost function은 아래와 같이 정의한다. $ r(s,a) = \log p(a=\pi^\star (s) | s) $을 이용해 log likelihood loss로 사용해도 되지만, 분석하기 쉬운 zero-one loss를 사용한다.

$ c(s,a) = $

CS294-02-13

줄타기를 예로 들면, 줄위에서 사람이 떨어질 때만 cost가 발생한다.

학습 알고리즘이 잘 돌아가서 모든 $ s \in \mathit{D_{train}} $에 대해 $ \pi_{\theta}(a \ne \pi^\star (s) | s) \leq \epsilon $ 이라 가정하자. 학습데이터상의 모든 상태 $ s $ 에서 optimal과 다를(줄 위에서 떨어질) 확률이 $ \epsilon $이하인 것이다. 즉, $ \epsilon $이하의 확률로 실수하는 것이다. 이때 total cost 기댓값의 upper bound는 다음과 같다.

$ \mathbb{E} \left[\ \mathsf{\underset{t}{\sum}}\ c(s_{t},a_{t})\right] \leq \epsilon T + (1-\epsilon)(\epsilon(T-1) + (1-\epsilon)(…)) $

$ T $ step을 간다고 했을 때, 첫 step에서 떨어질때의 cost 기댓값이 $ \epsilon T $이고 (줄에서 한번 떨어지면 그 이후 step에서는 계속 떨어져있는 상태이므로), 한 step은 무사히 지나고 두번째 step에서 떨어질 때의 cost 기댓값이 $ (1-\epsilon)\epsilon(T-1) $이고, 세번째 step에서 떨어질 때의 cost 기댓값이 $ (1-\epsilon)(1-\epsilon)\epsilon(T-2) $…. 이렇게 $ T $ step만큼의 항이 나온다. 그리고 각각의 항이 $ O(\epsilon T) $ (Order of $ T $) 이기 때문에 전체 $ \mathbb{E} [\ \mathsf{\underset{t}{\Sigma}}\ c(s_{t},a_{t})] $ 의 bound는 $ O(\epsilon T^2) $가 된다.

이 때, $ O(\epsilon T^2) $ 는 좋지 않다. $\epsilon$이 아무리 작다해도 경로가 길어질수록 cost가 지나치게 커지기 때문이다. 이것이 빨간 선이 초반에는 검정 선과 미세한 차이여도 종점에는 큰 차이가 나게 되는 distribution mismatch에 대한 cost 측면에서의 해석이다.



*아래는 3강 강의의 첫부분에서 보강한 내용이다.

More general analysis

위에서 했던 가정

모든 $ s \in \mathit{D_{train}} $ 에 대해

라는 것은

$ s \sim p(\mathit{D_{train}}) $

으로 바꾸자. image observation을 예로들면, 한번 봤던 이미지는 비슷한 이미지는 보아도 완전히 똑같은 이미지는 두번 다시 보지 않는다는 뜻이다. 현실적으로 합리적인 가정이라 한다.

if $p_{train}(s) \ne p_{\theta}(s)$ :

즉, 학습데이터의 상태분포와 학습된 상태분포가 다르다면:

$p_{\theta}(s_{t}) = (1-\epsilon)^t p_{train}(s_{t}) + (1-(1-\epsilon)^t)p_{mistake}(s_t)$

이 때, $(1-\epsilon)^t$ 는 실수를 하지 않을 확률, $p_{\theta}(s_{t}) = p_{train}(s_{t})$ 일 확률이다. $p_{mistake}(s_{t})$ 는 실수했을때 나타나는 어떠한 확률분포이다.

두 확률분포의 차이의 절댓값 $\left| p_{mistake}(s_{t})-p_{train}(s_{t}) \right|$ 이 가질수 있는 최댓값은 2이고, 아래의 대수적인 대소관계에 의해 결국 로 bound 된다.

$\because -(1-\epsilon)^t \leq -(1-\epsilon t)$ for $\epsilon \in \left[0,1\right] $

cost의 기댓값은 아래와 같이 전개된다.

$c_{max}$는 cost function definition에 의해 1이다.

$p_{train}$의 cost 기댓값 $\underset{s_{t}}{\sum}p_{train} (s_{t})c_{t}(s_{t}) $ 은 $\epsilon$ 이기때문에 아래와 같이 전개된다.

결국 $O(\epsilon T^{2})$이다.

더 상세한 내용은 아래 논문에 나와있다. A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning, Stephane Ross, Geoffrey J. Gordon, J. Andrew Bagnell

DAgger analysis with cost function

DAgger 에서는 $p_{train}(s) \rightarrow p_{\theta}(s)$이 되므로,아래와 같이 cost function이 bound 된다.

$ \mathbb{E} \left[\ \mathsf{\underset{t}{\sum}}\ c(s_{t},a_{t}) \right] \leq \epsilon T $

그 이유는 기존의

$ \mathbb{E} \left[\ \mathsf{\underset{t}{\sum}}\ c\left(s_{t},a_{t}\right)\right] \leq \epsilon T + (1-\epsilon)(\epsilon(T-1) + (1-\epsilon)(…)) $

와는 달리, 매번 실수할 확률이 $\epsilon$ 으로 동일하기 때문이다.