리만 매니폴드의 개념

 

## 리만매니폴드의 정의

- 미분가능한 매니폴드를 리만 매니폴드라고 정의한다.

## 리만공간과 유클리디안 공간

- 유클리디안 공간에서의 이차미분(곡률) = 리만 공간에서의 일차미분(Natural Gradient)

- 유클리디안 공간에서 보면 곡률을 따르는 일직선은 곡선으로 보인다.

- 유클리디안 공간에서의 이차미분 = 리만공간에서의 일차미분

-> Natural Gradient에서는 Policy가 리만 manifold를 따른다는 가정을 하고

이에 근거하여 Gradient를 계산하며 이 결과를 Natural Gradient라고 한다.

 

## 결론

- PPO가 나온 이유를 알기 위해서는 NPG를 알아야 한다.

-> NPG(2001) -> TRPO(2015) -> PPR(2017)

- Natural Gradient에서는 Policy가 리만 매니폴드를 따른다는 가정을 한다.

- Riemannian Manifold(리만매니폴드)란?

-> 매니폴드중에서도 매니폴드가 각지지 않고 부드럽게 생긴, 미분 가능한 매니폴드이다.

- Natural Policy Gradient는 리만공간(굽은공간)에서의 일차미분(일차근사)을 이용하여 Gradient를 계산하고 이를 이용하여 Policy를 업데이트한다.

------------------------------------------------

I. Optimization

## 최적화 문제

- 방법 : 대상 목적함수의 1차 미분을 이용하여 0이 되는 지점을 찾아 최적값 여부를 확인하는 방법

- 문제 : 초기와는 달리 최적점에 가까워질수록 step이 줄어들어 여러 iter을 진행하더라도

최적값을 찾지 못하는 문제점이 발생한다.

x_(k+1)=x_(k) - λf'(x_(k))

- 해결안 : 1차 미분 이외에도 2차 미분결과를 이용하여 iter을 진행할 경우 보다 빨리 최적값을 찾아낼 수 있다.

아래 식은 테일러 급수와 관련이 있음(원래 함수를 테일러급수로 추정하고

x_(k+1)= x_(k) - f'(x_(k)) / f''(x_(k))

## Natural Gradient와 Gradient의 차이

- Gradient Method는 파라미터의 값에 큰 변화를 만들어 낼 수 없음

- Natural Gradient는 Better Action보다는 Greedy Optimal Action을 선택하는 방향으로 나아감

 

II. Policy Gradient

## 폴리시 그레디언트란?

- 미래 보상에 그레디언트를 취해 최적의 폴리시를 찾는 방법임

- 유클리드 공간을 전제로 이루어졌던 기존의 방법(SGD) : Non-covariant

- 리만 공간을 전제로 이루어졌던(NPG) : Covariant

## 폴리시 최적화

- 업데이트 방향(steepest descent direction)

-> sutton의 PG와 별차이 없음

- 업데이트 크기(distance)

-> 크기가 중요하다.

## 방향과 크기

- 유클리드 공간에서는 파라미터 θ간의 거리는 |dθ|^2 = dθ dθ으로 표현할 수 있다.

- 파라미터 θ가 새로 업데이트 됨에 따라 매니폴드 모양이 계속 변경될 수 있다.

-> 이러한 경우 θ1과 θ2간의 거리가 일정하지 않으므로 이에 대한 general한 거리계산법이 필요하다.

-> KLD를 이용하여 두 분포간 차이를 최소화하는 방향으로 constraint를 걸어 연산하는 방향으로 전개한다.

## 거리계산식

|dθ|^2 = ∑ij Gij (θ) dθi dθj = dθT G(θ) dθ

G(θ)가 identity matrix면 이 식은 유클리드 공간에서 거리를 계산하는 것과 같다.

- Natural Gradient : 리만공간(리만 매니폴드)을 기반으로 하여 거리를 측정하는 방법

-> 매니폴드 모양이 계속 변경되면 같아야 할 θ간의 거리가 달라지게됨(variant)

-> 동일한 대상간의 거리가 매번 바뀌면 폴리시 최적화에 어려움을 겪을 수 있어 이를 invariant하게 만드는 것이 필요함

-> 이와 같은 방법은 FIM(Fisher Information Matrix)을 G(θ)로 쓰는 것이다.

-> FIM : 리만공간에 적용가능한 Positive Definite Matrix중 하나이다.

좌표축의 선택과 상관없이 두 점간의 거리를 동일하게 만드는 방법이다.

- xAxT : x로 무엇을 넣어도 행렬연산의 결과를 양의 값으로 만드는 것을 positive definite matrix라고 한다.

- Natural Gradient : 리만공간(리만 매니폴드)을 기반으로 거리를 재는 방법

-> 문제는 매니폴드의 모양이 바뀌면 거리가 달라지므로 이를 방지(invariant)할 수 있는 방법이 필요함

-> 방지할 수 있는 방법이 FIM(Fisher Information Matrix)임

## Natural Gradient란?

1) 리만 공간을 기반으로 하여 거리를 재는 방법을 Natural Gradient라고 한다.

2) 이 경우 매니폴드의 모양이 계속 바뀔때마다 같아야 할 θ간의 거리가 variant하게 되면

policy optimization이 intractable하기 때문에

NG를 invariant하게 만드는 것이 매우 중요하다.

-> NG를 invariant하게 만드는 방법이 FIM이다.

3) 어떤 좌표를 선택하더라도 두 포인트간의 거리를 동일하게 만드는 방법

## FIM이란?

리만 공간에 적용가능한 Positive Definite Matrix중의 하나이다.

FIM을 Natural Gradient에서 G(θ)으로 사용한다.

## NPG란?

Policy Gradient + Natural Gradient를 의미함

FIM이라는 Positive-Definite Matrix를 써서 리만공간을 고려한 방향 및 크기로

목표함수를 업데이트 함

## NPG에서 PPO까지 진행이력

NPG(2001) -> TRPO(2015) -> PPO(2017)

## 매니폴드의 이해

1. policy는 몇 차 함수일까?

- parameter(sigma)로 이루어진 함수라고 정의함

## NGM

- 어떤 파라미터 공간에서의 가장 가파른 방향을 강조함

- 파라미터 공간은 리만 매니폴드로 정의할 수 있다.

- 리만 매니폴드는 각지지 않고 미분가능하게 부드러운 곡률을 가진 면이다.

## NG

- NG에서는 폴리시가 리만매니폴드를 따른다는 가정을 한다.

- 리만 매니폴드? 매니폴드 중에서도 부드럽게 생긴, 미분 가능한 매니폴드라고 이해하고 넘어가자.

## 매니폴드의 이해

- Natural Policy Gradient는 리만공간에서의 일차미분을 이용한 gradient로 policy를 업데이트하는 것이다.

- 쉽게말해서 유클리디안 공간에서의 이차미분 = 리만 공간에서의 일차미분이라고 생각할 수 있다.

## 참고문헌

1. https://www.slideshare.net/SooyoungMoon3/natural-policy-gradient

2. https://talkingaboutme.tistory.com/entry/RL-Policy-Gradient-Algorithms

3. https://medium.com/@jonathan_hui/rl-natural-policy-gradient-actor-critic-using-kronecker-factored-trust-region-acktr-58f3798a4a93