Ssong

반갑습니다 :)

[RL] Lecture 5: Model-Free Control

Date:     Updated:

카테고리:

태그:

1. Introduction

이번 강의에서는 Model-Free control에 대해서 배운다.
MDP에 대한 정보를 모르는 상황(환경을 알지 못하는 상황)에서 던져진 Agent를 이용하여 어떻게 최적의 value function, Poilcy를 찾을 것인가?

1.1 Uses of Model-Free Control

몇 가지 예시 문제들은 MDPs 모델화 될 수 있다.

  • Elevator, Robocup Soccer
  • Helicopter, Robot Walking 등등

대부분의 이러한 문제들은

  • MDP 모델을 모르지만, experience를 sampling 할 수 있다.
  • MDP 모델을 알아도, sampling 외에 사용하기에 너무 크다

⇒ Model-free control은 이러한 문제들을 풀 수 있다.

1.2 On and Off-Policy Learning

  • On-policy learning
    • “Learn on the job”
    • Learn about policy \(π\) from experience sampled from \(π\)
    • optimize하고 싶은 policy(target policy) = behavior policy일 때 (experience를 하는 policy와 optimize 하는 policy가 같을 때)
  • Off-policy learning
    • “Look over someone’s shoulder”
    • Learn about policy \(π\) from experience sampled from \(µ\)
    • 다른 사람이 만드는 experience를 통해 policy optimize

참고 : On/Off Policy

2. On-Policy Monte-Carlo Control

2.1 Monte-Carlo Control

image

Policy Iteration의 원리

  • policy evaluation과 policy improvement를 반복해서 수행하면서 점차 개선된 policy를 찾아내는 과정 ⇒ Control 문제를 푼다
  • Policy evaluation : Policy 평가
    • ex) Iterative policy evaluation
  • Policy improvement : 평가된 Policy를 통해 개선된 Policy 생성
    • ex) Greedy policy improvement

Model-Free 에서도 Model-based에서 사용한(Iterative, greedy)방식을 사용하면 되는 거 아닐까?

MDP를 모를 때 문제점 및 해결방안

  1. Iterative policy evaluation을 적용할 수 없다.

    • Iterative policy evaluation은 Bellman Expectation Equation을 기반으로 Value를 계산해나가는 과정

      image 2

    • 하지만 Bellman Expectation Equation에는 MDP를 알아야만 알 수 있는 요소들이 존재하기 때문에 MDP를 알 수 없는 Model-Free 환경에서는 이 식을 그대로 적용할 수 없다.

      • State s에서 Action a를 했을 때 받는 reward는 Agent가 경험해봐야 알 수 있음
      • state transition도 Agent가 경험해봐야 알 수 있음, 경험을 하더라도 구체적인 확률 분포를 정의하지 못한다.

    image 1

    • Iterative policy evaluation ⇒ Monte-Carlo Policy evaluation으로 진행한다.

  2. V를 기반으로는 Greedy Policy improvement을 할 수가 없다.

    • Greedy policy는 state-value function을 기반으로 가장 value가 높은 next-state에 도달하게 하는 action을 선택하는 방법으로 만들어진다.

    • 그런데 model-free 환경에서는 state transition도 실제 경험을 해봐야 알 수 있고, 구체적인 확률 분포로 정의하지 못한다.

    • 따라서 어떤 action을 했을 때 이동하는 state \(s'\) 에서의 value function값이 높은 곳을 선택하는 greedy policy를 정의할 수 없다.

image 3

  • MDP Model을 알아야 state마다의 value function : V에 대한 greedy improvement를 할 수 있다.
  • Policy Evaluation 단계에서 action에 대한 Q(s,a)를 학습했다고 하면, Q에 대한 greedy improvement는 가능하다.

image 4

Greedy policy improvement : 모든 State 들을 충분히 봐야 된다. 하지만 Greedy 하게 하면 exploration이 충분히 되지 않는다. (새로운 문제점)

Greedy policy improvement (문제점)

image 5

맨 처음 왼쪽 문을 열고 reward 0을 받음, 그 다음 오른쪽 문을 열고 reward 1을 받음
⇒ 다음 문을 선택할 때 Greedy 하게 생각하면 오른쪽을 열어야한다.
계속 그렇게 오른쪽 문만 여는 행동을 선택하는 것이 정말 최적의 행동을 선택을 한 것일까?

  • Exploration이 고려되어야하는 이유

    model-based와 달리 model-free환경에서는 실제로 Agent가 action을 선택하고 state사이를 이동하면서 환경에 대한 정보를 배우게 된다.
    그런데 학습의 초기 단계에서부터 greedy action만을 선택한다면 Agent가 다양한 state를 방문하지 못하고 이미 방문한 state만 계속 방문하게 될 수 있다.

\(ε\)-Greedy Exploration (해결책)

  • \(1-ε\)의 확률로 greedy한 action 선택 (Exploitation)
  • \(ε\)의 확률로 랜덤한 action 선택 (Exploration)

장점

  1. policy가 개선됨을 보장할 수 있다.

  2. 모든 action을 explor 한다는 것을 보장할 수 있다

    image 6

Policy 개선에 대한 증명

image 7

image 8

image 9

한 episode가 끝나면 한 episode만큼의 경험을 가지고 policy를 개선할 수 있다.

Q로 시작을 시작했을때 optimally 하게 수렴을 하는가?

⇒ 이렇게 할 때 잘 수렴하기 위한 성질이 존재한다.

2.2 GLIE Property

image 10

  • 모든 state-action pair들이 무한히 많이 explored 되어야 한다.
    • \(ε\)-greedy이기 때문에 무한히 많은 state를 충분히 explore 가능
  • 결국에 policy는 greedy policy로 수렴해야 한다. (exploitation)

image 11

  • GLIE Monte-Carlo control은 optimal action-value function으로 수렴한다.

3. On-Policy Temporal-Difference Learning

Temporal-difference(TD) learning 은 Monte-Carlo(MC)에 비해 장점들이 있다.

  • 낮은 분산
  • Online (episode가 안끝나도 학습 가능)
  • Incomplete sequences에도 적용가능

⇒ Control loop에서 MC대신에 TD를 넣을수 있지 않을까?

  • Q(S,A)에 TD를 적용하고
  • \(ε\)-greedy policy improvement를 사용하고
  • 매 time-step마다 update를 한다.

3.1 SARSA

image 12

SARSA: state S에서 action A를 수행하여 reward R을 받고 next state S’에 도달한 뒤, 다시 action A’를 수행하는 과정

TD이기 때문에 episode가 안끝나도 바로 사용이 가능하다.

One-step action을 하고, reward를 받고 Q(S,A)자리를 update한다.

image 13

전 슬라이드는 Every episode 였는데 Every time-step으로 바뀌었다.

  • Policy evaluation단계에서는 MC 대신 Sarsa로 Q를 evaluation
  • Policy improvement단계에서는 \(ε\)-greedy policy improvement

3.2 SARSA Algorithm

image 14

  1. 초기에는 랜덤한 값들로 Q table을 초기화한다.
  2. Q에 대한 \(ϵ\)-greedy방법을 이용하여 state S에서의 action A를 고른다.
  3. action A를 Agent가 시행하고, 그 결과로 받게되는 reward R과 도달한 next-state S’에 대한 정보를 받는다.
  4. Q에 대한 \(ϵ\)-greedy방법을 이용하여 이동한 state \(S'\)에서의 action \(A'\)를 선택한다.
  5. next state-action pair에 대한 Q-value를 이용하여 current Q-value를 TD방법으로 업데이트한다.
  6. current state, action에 \(S'\), \(A'\)를 대입한다.

image 15

Sarsa 는 optimal action-value function에 수렴한다.

  • GLIE 해야한다.
    • 모든 State-action pair를 방문한다.
    • 결국은 greey policy로 수렴한다.
  • Robbins-Monro sequence
    • \(α\)를 무한히 더하면 \(∞\) (α가 Q를 무한한 곳까지 데려갈 수 있도록 해야한다.)
    • \(α^2\)의 합이 \(∞\)보다 작다. (Q value를 수정하는 것이 점점 작아져서 수렴하게 한다.)

⇒ 실질적으로 두 조건을 고려해야 하는 것은 아님 실제로는 잘 수렴하더라

3.3 n-step SARSA(𝝺)

image 16

  • n만큼의 실제 reward와, t+n번째 step에서의 추정 value function의 합으로 표현한다.

image 17

  • episode가 끝나야 적용이 가능한 Foward-view Sarsa(𝝺)

image 18

  • TD(λ)에서 사용한 것처럼 SARSA도 eligibility traces를 적용할 수 있다.
  • 단, SARSA는 Q-function에 대해 TD를 적용하므로 각각의 state-action pair에 대해 대응되는 하나의 eligibility trace를 가진다.

eligibility trace

  • init : \(E_0(s,a)\)=0
  • time-step \(t\)에서 어떤 state \(s\)에서 어떤 action \(a\)를 수행하면, 1을 더해주고 방문하지 않았을 때는 \(t\)−1에서의 값에다가 \(γ∈(0,1)\)를 곱해줘서 값을 감소시킨다.

image 19

원래는 한 state에서 action을 한 뒤 그 칸만 update해주었지만, Sarsa(𝝺)는 과거의 지나갔던 칸도 Eligibility traces 값이 존재하기 때문에 모든 state를 update계산량이 많아지지만 정보전파가 빠르다.

image 20

  • one-step SARSA를 하면 도착하는 순간 reward를 받고, 이전 state만 update
  • Sarsa(𝝺)는 오기까지 거쳤던 모든 경로들에 대해 Eligibility traces 값만큼 reward update
    • 최근의 경로일 수록 많이 update된다.

4. Off-Policy Learning

4.1 Off-policy learning

off-policy 란?

target policy \(π\)를 따랐을 때의 Value를 계산하거나, policy를 개선하고 싶을 때 target과 다른 behavior policy \(µ\)를 따랐을 때의 경험적 정보를 활용하는 방법

  • target policy \(π(a∣s)\) : compute \(v_π(s)\) or \(q_π(s,a)\)
    • action을 sampling 하는 policy
  • behavior policy \(μ(a∣s)\) : {\({S_1,A_1,R_2,⋯,S_T}\) } ~ \(μ\)
    • 개선하고 싶은 policy
  • off-policy의 장점
    • 사람이나 다른 Agents를 관찰하면서 배울 수 있다.
    • old policies 인 \(π_1\) , \(π_2\) … \(π_t\) 가 생성한 경험도 재사용 할 수 있다.
    • exploratory policy를 따르면서 optimal policy를 학습할 수 있다.
    • 하나의 policy를 따르면서 여러 policy를 학습할 수 있다.

4.2 Importance Sampling for off-policy

  • Importance Sampling : 두 확률분포의 비율만 곱해주면 어떤 확률 분포를 기반으로 구한 값에 대한 기댓값을 다른 확률 분포를 기반으로 구했을 때에 대한 기댓값으로 표현할 수 있다.

image 21

P를 따를 때의 f(X)의 기댓값 = Σ P(X) * f(X)

→ 분모,분자에 Q(X) 곱한다.

→ Q를 밖으로 빼낸다.

→ Q를 따를 때의 기대값 = {P(X) / Q(X)} * f(X)

⇒ P 확률 분포 기반의 기댓값을 Q 확률 분포 기반의 기대값으로 표현했다.

image 22

  • \(G_t\)를 얻을 때까지 수행한 각각의 action이 ‘선택될 확률의 비’를 계속 곱해준다.

  • 그러나 MC는 전체 episode가 끝난 다음에 \(G_t\)를 받아 계산하기 때문에, 끝날 때까지 수행한 action의 수가 커지면 커질수록 \(G_t\)의 앞에 곱해지는 ratio가 너무 많아지기 때문에 실제로 이 방법을 써서 계산할 수 없다. (ratio들의 곱에 대한 variance가 너무 크다)

⇒ 1-step 후에 update가 가능한 TD는 어떨까?

image 23

TD의 경우에는 앞에 곱해지는 수가 훨씬 적기 때문에 Importance sampling을 이용하여 off-policy method로 학습할 수 있다.

4.3 Q-Learning

  • Importance sampling을 안쓰고 action value Q(s,a)을 off-policy로 학습하고 싶다.
  • Agent가 실행할 실제 next-action은 behavior policy를 따라 선택된다. \(A_{t+1}∼μ(⋅∣S_t)\)
  • 그러나 Q-function을 update할 때는 target policy를 따라 선택된 action \(A'\)에 대하여 계산한다. \(A'∼π(⋅∣S_t)\)
  • TD는 reward + 추측값의 차이를 이용하여 현재값을 update하는데, 추측값에서는 behavior policy를 따르지 않아도 상관없기 때문

image 24

  • \(A_{t+1}\)이 아니라 \(A'\)을 가져와서 \(Q\)(\(S_t\), \(A_t\))를 Update ⇒ Off-policy
  • Action은 behavior policy μ에서 선택을 하고, target policy π에서의 Q값을 update 한다.

4.4 Off-Policy Control with Q-Learning

  • behavior policy와 target policy 둘다 점차 improvement가 되지만, behavior policy는 여전히 exploration을 고려할 수 있도록 policy를 설정하고 싶다.

  • Target policy \(π\) : Greedy

image 25

  • behavior policy \(μ\) : \(ε\)-Greedy

image 26

target policy를 이용하여 선택된 action \(A'\)를 greedy policy에 대한 수식으로 바꾸어서 표현할 수 있다. ⇒ Q-Learning에서의 TD target이 된다

Q-Learning Update 식 :

image 27

  • max가 추가됐다.
  • Sarsa max라고도 불린다.

image 28

Summary

image 29

맨 위로 이동하기

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

댓글남기기

최근 글 10 개 :)