[CS294] Lecture 4 : Reinforcement Learning Introduction

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


포스트 내용

  1. Definition of a Markov decision process
  2. Definition of reinforcement learning problem
  3. Anatomy of a RL algorithm
  4. Brief overview of RL algorithm types
    • Goals:
      • Understand definitions & notation
      • Understand the underlying reinforcement learning objective
      • Get summary of possible algorithms

Definitions

Notations from imitation learning

Imitation Learning (Lecture 2 강의 내용) 중…

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} \)에 의해서만 결정된다는 것을 뜻한다.

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} \)를 취한다던지, 여러 이유가 있을 수 있다.

Reward functions

어떤 행동이 좋고, 어떤 행동이 나쁜가?

이에 대한 기준이 reward function $r(s,a)$ 이다. state와 action이 얼마나 좋은지에 대한 함수다. 만약 자율주행차가 길을 잘 달리면 높은 reward를 받을 것이고, 사고가 난다면 낮은 reward를 받을 것이다.

Markov chain

  • $\mathcal{M} = {\mathcal{S,T}}$
  • $\mathcal{S}$ - state space
    • states $s \in \mathcal{S}$ (discrete or continuous)
  • $\mathcal{T}$ - Transition operator(Matrix)
    • $p (s_{t+1}|s_t)$
    • 이전 state에서 다음 state로 갈때(상태가 전이될 때)의 확률분포를 나타낸다. 상태가 전이 될 때는 오직 이전 상태에만 영향을 받는다.

CS294-04-01

Markov decision process

Markov chain 는 state밖에 없었는데, 여기에 action과 reward가 추가된다.

  • $\mathcal{M} = {\mathcal{S,A,T,r}}$
  • $\mathcal{S}$ - state space
    • states $s \in \mathcal{S}$ (discrete or continuous)
  • $\mathcal{A}$ - action space
    • actions $a \in \mathcal{A}$ (discrete or continuous)
  • $\mathcal{T}$ - Transition operator(Tensor!)
    • $p (s_{t+1}|s_t,a_t)$
  • $r$ - reward function
    • $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$
    • $r(s_t,a_t)$ - reward

CS294-04-02

Partially observed Markov decision process

대부분의 강화학습 환경에서는 agent가 state를 모두 보는 것이 아니라, 부분적으로만 관찰할 수밖에 없는 경우가 많다. 위의 Markov decision process 에서 observation과 emission probability(특정 state에서 특정 observation이 나올 확률)가 추가된다.

  • $\mathcal{M} = {\mathcal{S,A,O,T,\varepsilon,r}}$
  • $\mathcal{S}$ - state space
    • states $s \in \mathcal{S}$ (discrete or continuous)
  • $\mathcal{A}$ - action space
    • actions $a \in \mathcal{A}$ (discrete or continuous)
  • $\mathcal{O}$ - observation space
    • observations $o \in \mathcal{O}$ (discrete or continuous)
  • $\mathcal{T}$ - Transition operator(Tensor!)
    • $p (s_{t+1}|s_t,a_t)$
  • $\varepsilon$ - emission probability $p(o_t|s_t)$
  • $r$ - reward function
    • $r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$
    • $r(s_t,a_t)$ - reward

CS294-04-03

The goal of reinforcement learning

CS294-04-04 $\tau$ 는 state와 action의 trajectory $s_1,a_1,…,s_T,a_T$이고, $\pi_{\theta}$는 state $s_t$를 입력으로 받아 action $a_t$를 내뱉는 policy network이다. state와 policy가 내뱉은 action을 world(환경)에 집어 넣으면 transition operator $p(s_{t+1}|s_t,a_t)$에 의해 다음 state $s_{t+1}$가 나오고 $s_{t+1}$을 policy network에 넣으면 action $a_{t+1}$이 나온다. 그리고 $\theta$는 policy network의 학습 파라미터이다. 우리는 이 때, 최적의 파라미터 $\theta^{\star}$를 찾는 것이 강화학습의 목표다. 최적이라는 것은, reward를 가장 많이 받는 것이므로, 결국 policy를 따라 행동했을 때의 reward 기댓값 $\mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left[ \underset{t}{\sum} r(s_t,a_t) \right]$ 을 최대로 하는 $\theta^{\star}$를 찾는 것이다.

Finite horizon case: state-action marginal

Time $t$가 유한한 경우다. CS294-04-05 위에서 언급했듯, $\tau$ 는 state와 action의 trajectory $s_1,a_1,…,s_T,a_T$인데, Markov chain에서 $\tau$는 결국 transition probability 와 policy에 따라 결정된다. 즉, state-action간의 transition probability는 $p((s_{t+1},a_{t+1})|(s_t,a_t)) = p(s_{t+1}|s_t,a_t)\pi_{\theta}(a_{t+1}|s_{t+1})$ 이고, $p_{\theta}(s_t,a_t)$ 로 표현할 수 있는 것이다. 이를 state-action marginal이라고 부른다. state-action marginal에 따라 다시 정리하자면, 강화학습의 목표는 최적의 파라미터 $\theta^{\star}$를 찾는 것인데, 이것은 모든 time step에 대한 reward $r(s_t,a_t)$의 합을 최대로 만드는 파라미터 $\theta$이다. 그리고 reward를 산출하는 state-action들 은 transition probability $p(s,|s,a)$ 와 policy $\pi_{\theta}(a|s)$에 의해 결정 되는데, 이를 state-action marginal 하게 $(s_t,a_t) \sim p_{\theta}(s_t,a_t)$로 나타낸다.

Infinite horizon case: stationary distribution

Time $t$가 무한한 경우다. $T \rightarrow \infty$ CS294-04-06 이전 state-action $(s_t,a_t)$ 에서 다음 state-action $s_{t+1},a_{t+1}$으로 가는 것을 transition operator을 이용해서 표기하면, 로 표기할 수 있다. $k$ 번 transition을 하면 이다. 이 때, $p(s_t,a_t)$ 가 stationary distribution으로 수렴하면 transition을 해도 state의 분포가 일정하고, state $\mu$는 transition operator의 eigenvalue가 1인 eigenvector이다. 이러한 eigen pair은 mild condition에서 항상 존재하기 때문에, $p(s_t,a_t)$는 stationary distribution으로 수렴한다고 한다. 즉, t가 변함에 따라 $(s,a)$가 일정하고, $r(s,a)$ 또한 일정하다. 그렇기 때문에 우리는 argmax의 대상을 T로 나누어주는 단순한 방법으로 수식을 바꾸어 줄 수 있다. 이래서 finite case와 infinite case의 objective 수식이 다르다.

CS294-04-07

reward function은 그 자체로는 smooth하지 않고 미분 불가능하기 때문에 직접적으로 최적화 할 수 없다. 따라서 distribution에 대한 expectation으로 접근한다. 예를 들면 아래 예시에서 자동차가 잘 달리면 reward가 +1이고, 절벽 아래로 떨어지면 -1이다. 이는 discrete하다. 그러나 distribution을 따르는 expectation을 구하게 되면, $\theta$에 대해 smooth해진다. CS294-04-08

Algorithms

The anatomy of RL algorithm

RL 알고리즘은 대개 아래와 같은 세 부분으로 돌아간다고 볼 수 있다. 기본적으로 trial and error 방식으로 학습한다. 각각에 대한 자세한 내용은 추후에 다시 다룬다. CS294-04-09

  • [주황색 박스] : agent가 행동하면서 sample들(trajectories)을 만들어낸다.
  • [초록색 박스] : sample들에 대해 평가를 한다. 좋은 trajectory에 대해서는 높은 reward를, 안좋은 trajectory에 대해서는 낮은 reward를 준다.
  • [파란색 박스] : state에 대한 action의 distribution인 policy $\pi_{\theta}$를 업데이트 한다. 이러한 학습방식을 policy gradient라고 한다. 다음시간에 다시 다룬다.

RL by backprop

CS294-04-10 state $s_t$와 action $a_t$가 들어왔을 때 다음 state $s_{t+1}$을 내뱉는 예측 모델 $f_{\phi}$를 학습한다. $f_{\phi}$가 예측한 다음 state와 실제 다음 state간의 오차에서도 loss가 발생한다. 이를 model-based RL이라 한다. 그러나 실제로 이렇게 하면 잘 안되고, 이는 단지 이해를 돕기 위한 예시일 뿐이다. 이 역시 추후에 다시 다룬다.

  • Which parts are expensive?

    통상적으로 각 부분마다 cost가 많이 발생하는 부분들이다. 그러나 풀고자 하는 문제에 따라 다른다.

    • [주황색 박스] : MuJoCo등으로 시뮬레이션을 돌리는 경우는 현실의 시간보다 충분히 빠르게 학습을 돌릴 수 있으므로 큰 문제가 안되지만, 실제로 자율주행이나 로봇 등을 학습하는 경우는 시간을 빠르거나 느리게 조절할 수 없으므로 곧이 곧대로 시간을 소모해야 한다.
    • [초록색 박스] : reward를 계산하는 것은 쉽고 빠르게 구현가능하지만, 다음 state $s_{t+1}$을 예측하는 모델 $f_{\phi}$ 를 학습하고 최적화하는 것은 오래걸린다. 물론 알고리즘에 따라 다르긴 하다.
    • [파란색 박스] : $f_{\phi}$나 r을 통해 $\pi_{\theta}$를 학습하는 것인데, 알고리즘에 따라 다르다.
  • Why is this not enough?

    • 오직 deterministic dynamic만 다룰 수 있다.
    • 오직 deterministic policy만 다룰 수 있다.
    • gradient의 연산을 통해 학습하기 때문에 연속적인 state와 action만 다룰 수 있다.
    • gradient vanishing 문제 등 최적화에 대한 문제들이 있다.

Q-function and value function

CS294-04-11 초기 state $s_1$으로부터 시작해서, policy에 따라 action $a_1$을 하고, transition probability distribution $p(s_2|s_1,a_1)$에 따라 다음 state $s_2$로 가고, 거기서 다시 policy에 따라 action $a_2$를 하고… 이렇게 time step $T$까지 진행되고나면 trajectories 따른 reward $r(s_1,a_1), r(s_2,a_2), r(s_3,a_3) …$ 을 반환받고 그에 맞게 학습이 된다.

CS294-04-12 그런데 만약 state $s_1$와 action $a_1$에 대해서 앞으로 받을 보상을 예측할 수 있다면? 그렇다면 time step $T$까지 기다릴 필요 없이 바로 policy를 앞으로의 보상에 맞게 학습할 수 있을 것이다. 즉, 앞으로의 보상이 최대가 되는 action $a_1$이라 할때, policy가 $a_1$을 내뱉을 확률을 $\pi(a_1|s_1)=1$로 학습하는 것이다. 이 때, 앞으로 받을 보상을 예측해주는 함수를 Q-function이라 한다. $Q(s_1,a_1)$은 state $s_1$에서 action $a_1$을 했을때 앞으로 받을 보상에 대한 예측값을 나타낸다.

$Q^{\pi}(s_t,a_t)$ 는 state $s_t$에서 action $a_t$을 했을 때, 앞으로 받을 보상들에 대한 예측이고, $V^{\pi}(s_t)$는 state $s_t$에서 앞으로 받을 보상들에 대한 예측이다. 앞으로 자주 나올 개념들이다.

만약 $Q^{\pi}(s_t,a_t) > V^{\pi}(s_t)$라면, action $a_t$는 다른 action들에 비해 평균이상으로 좋은 action이다. 이렇게 Q값에 기반해서 더 나은 행동을 하도록 policy를 학습 할 수 있는 것이다.

Types of RL algorithms

강화학습의 목표인, $\theta^{\star}$를 찾아가는 여러 갈래의 방법을 간략하게 소개한다.

$\theta^{\star} = \mathbb{E}_{\tau \sim p_{\theta}(\tau)} \left[ \underset{t}{\sum} r(s_t,a_t) \right]$

Direct policy gradients

CS294-04-15 reward 계산을 하고, reward를 최대로 하는 action을 뽑도록 gradient backpropagation을 통해 policy $\pi_{\theta}$를 학습한다.

Value function based algorithms

CS294-04-14 policy를 직접적으로 학습하진 않지만, optimal policy의 value function이나 Q-function을 학습한다. value function $V(s)$나 Q-function $Q(s,a)$를 학습한 다음, $\pi(s)$는 $Q(s,a)$값을 최대로 하는 $a$로 정한다.

Actor-critic

CS294-04-16 현재 policy에서 value function이나 Q-function을 구해 policy를 학습시킨다.

Model-based RL algorithms

CS294-04-13 Model을 학습시킨다는 것은 transition model $p(s_{t+1}|s_t,a_t)$를 학습시키는 것인데, 이 model을 이용해서 다음과 같이 이용한다.

  • planning을 한다.(no policy)
    • Discrete action space에서 Monte Carlo tree search 같은 discrete planning을 한다.
    • Continuous space에서 backpropagation을 통해 trajectory 를 최적화한다.
  • Backpropagation을 통해 policy를 학습한다.
  • model을 이용해 value function을 학습한다.
    • Dynamic programming
    • Simulated experience를 만들어낸다. (Dyna- 모델을 실제 경험으로부터 학습하고, value function이나 policy를 simulated 경험과 실제경험 둘다로부터 학습함.)

Trade-off

이처럼 여러가지 강화학습 알고리즘이 있지만, 풀고자 하는 문제의 성격이나 제약조건에 따라 적절한 알고리즘을 선택해야한다. 각각 알고리즘마다 장단점이 있기 때문이다.

Different tradeoffs

  • Sample efficientcy

    성능을 위해 어느정도의 sample이 필요한지에 대한 이슈다. 일반적으로는 on policy를 사용한다. sample cost가 많이 들긴 하지만, 사용하기 쉽고 효과적이기 때문이다.

    • off policy : policy로부터 sample을 뽑아내지 않고도 policy를 학습할 수 있다.
    • on policy : policy가 조금이라도 변할 때마다 새로운 sample을 뽑아낸다.

    CS294-04-17 More efficient한 방법이 항상 더 좋은것은 아니다. simulation 비용이 많이 들지 않는다면, less efficient하더라도 더 나은 성능을 위해 많은 sample을 얻어서 학습하는 것이 효율적일 수 있다.

  • Stability & ease of use

    수렴하는지, 어디에 수렴하는지, 항상 수렴하는지에 대한 이슈다. 기존의 supervised learning에서는 gradient descent를 사용하기 때문에 대개 수렴하지만, RL에서는 대체로 gradient descent를 사용하지 않는다.

    • Q-learning: fixed point iteration. 단순한 함수에는 수렴하지만, 복잡한 함수에 수렴하는지는 보장되지 않는다.
    • Model-based RL: model이 reward에 대해 최적화되는 것이 아니다. 그저 다음 state를 예측하기 위해 학습한다. 더 나은 model이 더 나은 policy를 만들어주는지는 보장되어있지 않다.
    • Policy gradient: objective에 대해 직접적으로 gradient descent를 사용하긴 하지만, local optima에 수렴할 가능성이 있다.

Different assumptions

  • Full observation or patially observation?

    state를 모두 관측할 수 있는 경우($s_{t} = o_{t}$)가 있고, 부분만 관측 가능한 경우가 있다. 주로 value function fitting에서 full observability를 가정한다.

  • Stochastic or deterministic?

    Dynamic system 이나 policy에 대한 가정으로, stochastic은 분포를 따르긴 하지만 매번 할 때마다 결과가 달라질 수도 있고, Deterministic은 파라미터가 같다면 같은 입력일때 결과가 매번 같다.

  • Continuous or discrete?

    action space나 state space가 연속적인지 불연속적인지에 따라서도 적용하는 알고리즘이 달라진다. 주로 continuous value function learning 이나 model-based RL 에서 continuitysmoothness를 가정한다.

  • Episodic or infinite horizon?

    하나의 (끝이 있는)episode로 구성되는 환경인지, 시간제약없이 끝없이 이어지는 환경인지에 따라서도 적용하는 알고리즘이 달라진다. 주로 policy gradientmodel-based RL에서 episodic learning을 가정한다.

CS294-04-18

Different settings

  • Easier to represent the policy or model?

    환경이나 task에 따라서 policy나 model을 표현하기 힘든 경우가 있다.

Examples of specific algorithms

CS294-04-19