[RL] David Silver RL Lecture 7: Policy Gradient

1. Introduction

1.1 Value-Based and Policy-Based RL

저번 강의에서는 V(s)와 Q(s,a)를 파라미터 θ로 근사하고 Gradient discent를 통해 update하는 방식으로 학습했다.
policy는 value function으로부터 바로 만들어진 policy였다. (\(ε\)-greedy)
이번 강의에서는 policy를 파라미터 방식으로 표현한다.

model-free RL에 집중한다.

• Value Based : value function을 구하고, 절대적인 policy 사용
  • Learn Value Function
  • Implicit Policy (\(ε\)-greedy)
• Policy Based : value function을 구하지 않고 바로 policy 학습
  • No Value Function
  • Learn Policy
• Actor-Critic : policy, value function 둘다 학습
  • Learn Value Function
  • Learn Policy

Policy Based RL

• Advantages:
  • 수렴성이 좋다.
  • 고차원적 또는 continuous action에 효과적이다.
  • Stochastic policies를 학습할 수 있다.
• Disadvantages:
  • 주로 global 이 아닌 local optimum에 수렴한다.
  • policy 평가가 비효율적이고, 높은 분산을 가진다.

1.2 Example

가위바위보

두명이 가위바위보를 한다고 하면

• deterministic policy는 쉽게 활용될 수 있다. (바위만 내는 Policy이면 상대는 보만 낸다)
• 일정한 랜덤 (모두다 33% 확률) policy가 최적이다. (이런 경우를 Nash equilibrium라고 함)

Aliased Gridworld

• agent는 회색 state를 구분할 수 없다. (위 아래가 벽이고, 좌우가 뚫려있음)

• optimal deterministic policy는 두 회색 state에서 W로 가거나 E로 가는 것
• 물론 둘다 보상은 절대 얻지 못한다.
• Value-Based RL은 near-deterministic policy를 학습한다. (greedy or \(ε\)-greedy)

• optimal stochastic policy는 회색 state에서 E나 W로 랜덤하게 이동하는 것이다.
• 높은 확률로 몇 단계 후에 goal state에 도착할 것이다.
• Policy-based RL은 optimal stochastic policy를 학습할 수 있다.

fully observable MDP에서는 항상 최적의 deterministic policy가 존재하지만, partialy observable한 상황이고 state도 구분이 안가서 가능한 상황

1.3 Policy Objective Functions

Goal : action \(a\)를 할 확률을 output으로 하는 함수 \(π_θ(s,a)\)에서의 최적의 θ를 찾는 것

• 어떻게 policy \(π_θ\)의 quality를 측정할 수 있을까? (이것을 알아야 policy update가 가능)

  1. episodic 환경에서 start value를 사용할 수 있다.

     

     시작위치 \(s_1\)는 정해져있고 \(π\)를 따라 이동해 terminate 됐을 때까지 얻을 수 있는 reward의 기댓값 (사실상 Value)
     start state는 하나여도 되고, 고정된 분포를 가진 여러개여도 됨

  2. continuing 환경에서는 average value를 사용할 수 있다.

     

     \(d^{π_θ}(s)\) : stationary distribution : markov chain에서 policy를 따라서 무한히 움직이다 보면 각 state 별로 머무는 확률분포가 일정확률로 수렴한다.

     d(s) : 각 state 에 있을 확률 x 그 때의 Value의 총합

  3. average reward per time-step

     

     각 state에서 policy로 action을 하고 얻는 reward들을 π 확률 가중치를 곱해서 더하고 state distrbution 가중치를 곱해서 더한다.

  ⇒ 결국 3가지 방법 다 value를 최대화하기 위해 하는 과정, 목적함수 J(θ)를 정의한 표현이다.

Policy optimization

Policy-based RL은 Optimisation 문제이다. 즉 J(θ)를 최대화 하는 최적의 θ를 찾아야한다.
Policy \(π\): θ로 표현된 함수, θ가 바뀌면 Policy가 바뀌고 그러면 얻는 reward가 바뀌고 J가 바뀐다.
즉 θ를 조정해서 J를 Maximize 하는 것이 최적화 문제를 푸는 것이다.

gradient 안쓰는 방법

• Hill climbing
• Simplex / amoeba / Nelder Mead
• Genetic algorithms

Gradient 쓰는 방법

• Gradient descent
• Conjugate gradient
• Quasi-newton

Gradient descent에 집중할 예정이다.

---

2. Finite Difference Policy Gradient

2.1 Policy Gradient

목적함수 J(θ)가 있어서 J에 대한 gradient를 구할 수 있는 상황이다.
(무조건 구할수 있는 이유가 policy \(π\)를 우리가 정한 것이기 때문에 gradient가 계산 되는 함수로 정하면 된다)

gradient를 구해서 θ가 가장 급격하게 변하는 방향으로 $$α$$만큼 update를 해주는 방법

2.2 Computing Gradients By Finite Differences

변경 전의 값을 알고있고 \(θ_1\)부터 값이 1이었으면 1.01으로 변경후 계산해 변경 전후의 값 비교를 통해 \(θ_1\)에 대한 편미분(기울기값)을 계산한다. (0.01만큼 바뀌었을 때 J가 얼마나 바뀌나)

마찬가지로 \(θ_n\)까지 총 n번 반복하면 길이 n인 vector인 gradient 계산이 된다.

• n차원의 policy gradient를 계산하려면 n번 계산해야됨
• Simple, noisy, inefficient - 하지만 가끔 효과적
• 어떤 정책에 대해서도 심지어 미분 불가능이어도 동작한다.
  • 내가 직접 다 값을 구하면 되기 때문

---

3. Monte-Carlo

3.1 Likelihood Ratios

• Policy gradient를 수학적으로 계산해본다. Policy \(π_θ\)는 미분가능하다고 가정한다.
  (함수를 내가 정할 수 있는 것이기 때문에 터무니없는 가정이 아님)
  그리고 \(π\)에 대한 gradient를 안다고 가정. (NN, linear combination of feature를 사용하던)

  

• 갑자기 log가 등장한 이유는 log를 미분하면 위의 식과 같이 나온다.

Softmax policy

• Neural net에 많이 쓰이는 형태인 softmax policy를 example로 사용한다.
• Weight는 feature의 linear combination을 사용해 동작한다.

• action의 확률은 exponentiated weight에 비례한다.

  

  • 확률 형태로 각 action들이 표현되는 softmax policy가 있다고 가정하면 위 gradient처럼 수식 전환이 가능
• score function : softmax에 log를 취하면 \(π\)가 앞으로 나오면서, 분모와 분자가 계산됨

Gaussian Policy

어떤 평균이 있고, 어떤 state에서 대체로 이 action을 하는데, variance를 줘서 다른 액션의 확률도 있게 하는 policy

• continuous action spaces에서 Gaussian policy를 쓰는 것이 자연스럽다.
• 평균은 상태 features 들의 linear combination이다.

• 분산은 \(σ^2\)로 고정되고, 파라미터화 될 수 있다.
• policy는 gaussian이다.

• score function

3.3 Policy Gradient Theorem

One-step MDPs

• 어떤 분포를 따르는 Start State s에서 시작한다
• 딱 one time-step후에 reward r을 받고 종료된다

• likelihood ratios를 통해 gradient J가 expectation(기대값)으로 묶일 수 있어짐

실제로 J의 gradient를 구하는 것은 어렵다. 하지만 기대값으로 묶이면서 그냥 sampling만 해서 sample을 구하면 그 값이 J의 gradient의 sample이 된다.

J에 대한 gradient에 대한 unbiased sample들을 얻고, 여러번 update하면 대수의 법칙에 의해 J가 수렴한다.

Policy Gradient Theorem

이전까지 one-step MDP, likelihood ratio를 이용한 방법론을 multi-step MDP까지 일반화 시켜주는 Theorem

• one-step MDP에서의 r 자리를 Q로 대체한다.
  • one-step : r이 cumulative reward → episode가 끝날 때까지 받은 reward의 총합
  • multi-step : Q가 cumulative reward → 그 step에서 a를 했을 때 얼마를 받을지에 대한 총합

Monte-Carlo Policy Gradient

Stochastic Gradient Ascent로 파라미터를 update하고, policy gradient theorem을 사용한다.

• 현재 Q를 모른다. 그러므로 return이 Q의 unbiased sample이기 때문에 return v를 이용한다.
• r이 sample이기 때문에 계속 sampling 하다보면 unbiased estimate가 보장되어 평균이 Q로 간다.
• gradient J에 step-size \(α\)를 곱해 그 방향으로 θ를 update 시킨다.

REINFORCE Algorithm

• θ를 임의로 초기화 → θ를 이용한 policy \(π\)가 존재 → \(π\)를 기반으로 episode 생산 → 첫 step부터 마지막까지 θ를 update

3.4 Puck World Example

• 아이스 하키의 puck을 움직이는 continuous action space가 존재한다.
• target에 가까워 질수록 reward를 받고 30초마다 target location이 변경
• Policy는 MC policy gradient를 통해 학습되었다.

강조할 점 2가지

1. value-based와는 다르게 Learning curve가 지그재그 하지 않게 올라간다. policy-based는 θ를 조금씩 바꾸기 때문에 stable하다.
2. iteration이 \(10^7\) 단위인데 이것은 MC를 사용해 Variance가 매우 크기 때문에 수렴이 엄청 느리다.

---

4. Actor-Critic Policy Gradient

4.1 Action-Value Actor-Critic

• MC policy gradient는 아직 Variance가 높다.
• action-value function을 계산하기 위해 Critic 방식을 사용한다.
  • 앞선 REINFORCE Algorithm에서 Q자리에 return으로 대체를 했는데 그럴 것 없이 Q를 따로 학습을 해서 넣어준다.
• Actor-Critic algorithm은 두개의 파라미터 세트를 유지한다.
  • Critic : action-value function 파라미터 w를 update
  • Actor : Critic에 의해 제안된 Policy 파라미터 θ Update

• Actor-Critic algorithm은 approximate policy gradient에 기반한다.

  

Q함수는 어떤 \(π\)를 따라서 진행했을 때의 기대값, 따라서 Q는 \(π\)에 종속적인데 \(π\)가 계속 바뀐다.

Q학습, \(π\) Update → \(π\) 학습, Q Update→ 반복

Q Prediction 문제

• Critic은 policy evaluation과 비슷한 문제를 풀어야한다.
• 어떻게 policy \(π\)가 좋은지 알 수 있을까?
  • MC policy evaluation
  • TD Learning
  • TD(λ)

앞서 배운 방식 아무거나 사용 가능하다. 심지어 least-squares policy evaluation도 가능

sudo code

• linear value function approximation 사용하면 다음과 같이 표현할 수 있다.

  

  • Critic : linear TD(0)로 w update

  • Actor : policy gradient로 θ update

    

1. s, θ 초기화
2. policy \(π_θ\)로 \(a\) sampling 한다.
3. 매 step마다, reward와 다음 state s’, 다음 state에서의 action a’를 알기 때문에 TD error가 계산이 된다.
4. 그렇게 δ와 θ를 계산한다. β : learning rate
5. policy 파라미터 θ Update → 행동 확률 \(π_θ(s,a)\)를 최대화하도록 조정
6. w = w + learning rate * TD error * (linear value function approximation을 통한 feature)를 통해 Q함수의 파라미터 w Update
7. 현재 상태와 행동을 다음 상태 s′와 행동 a′로 업데이트하고 위 과정을 반복한다.

4.2 Reducing Variance Using a Baseline

policy gradient로 부터 baseline function B(s)를 뺀다.

이것은 기대값을 바꾸지 않으면서 분산을 줄일수있다

likelihood ratio 방법을 역으로 써서 log가 gradient π로 바뀐다.

B(s)는 s에 대한 함수이기 때문에 a랑은 상관이 없다. ⇒ 앞으로 뺄 수 있음

뒤에 부분은 \(π_θ(s,a)\)의 합은 1이기 때문에 θ로 미분하면 0이 된다.

• 좋은 Baseline은 state value function B(s) = \(V^{π_θ}(s)\)이다.
  • B(s)는 s에 대한 함수임 어떤 것이든 될 수있다.

• 우리는 advantage function \(A^{π_θ}(s,a)\)를 사용할 수 있다.

  

4.3 Estimating the Advantage Function

advantage function은 policy gradient의 분산을 확연히 줄일 수 있다.

그래서 critic은 advantage function을 측정할 수 있어야 한다. (그래야 쓸수 있음)

policy를 학습하기 위한 θ, Q학습하기 위한 weight, V학습하기 위한 함수까지 총 3쌍의 parameter가 필요하다.

• δ(TD error)의 기대값이 A이기 때문에 δ라는 sample들은 A의 unbiased sample이다.
  • δ를 계속 취하다 보면 평균은 A와 같게 된다.
  • A자리에 δ(TD error)를 대신 넣어 policy gradient를 계산할 수 있다.

  

• 실제에서는 true value function을 모방한 Advantage라도 그걸 그냥 쓰면 동작한다.
  • TD error가 Advantage의 sample이기 때문에 A자리에 학습해서 배운 TD error를 쓰면 된다.

  

• Q를 학습할 필요없이 parameter v만 사용하면 된다.

4.4 Different time-scales

Critic과 Actor 따로 학습해야되기 때문에 Critic 학습할 때 여러 방식을 쓸 수 있다.

Critic을 different time-scales마다 쓸 수 있다.

Actor도 different time-scales마다 쓸 수 있다.

• MC는 complete 됐을 때의 return을 사용
• Actor-critic은 one step TD error를 사용

Actor는 different time-scales에 사용이 가능하기 때문에 TD(λ)에도 가능하다.

• forward-view TD(λ)

• backward-view TD(λ)

backward-view TD(λ)는 eligibility traces가 score에 대해 traces가 계산된다.

5. Summary

• Policy gradient는 여러 형태가 존재한다.
  • REINFORCE : return \(V_t\) 추가, Policy-based method로 critic이 필요 없는 actor방식
  • Q Actor-Critic : policy gradient theorem으로 return(MC)이 variance가 너무 커서 Q를 학습
  • Advantage Actor-Critic : variance가 너무 커서 baseline을 추가해 A = Q-V를 사용한다.
  • TD Actor-Critic : Advantage를 쓰기 위해서 Q와 V까지 총 3개를 학습. Parameter가 너무 많아 TD error가 Advantage의 sample이므로 Advantage자리에 TD error를 사용한다.
  • TD(λ) Actor-Critic : 여러 time-scale을 고려하는 score 함수에 축적되는 eligibility traces 값을 써서 TD(λ) 사용한다.
• stochastic gradient ascent algorithms에 위 학습방법을 이용해 gradient를 구하면 gradient ascent가 가능하다.
• Critic 학습은 policy-evaluation 방식으로 MC, TD 상관없이 사용하면 된다.

맨 위로 이동하기

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