[CS229] [18] Lecture 18 - Continous State MDP & Model Simulation

1. State Space

- Lecture 17에선 이산적인 MDP에 대해서 알아보았다면, 이번 lecture에선 연속적인 MDP에 대해서 다뤄본다고 한다.

 

- 우선 예를 들어 자율주행 자동차를 모델링한다고 가정해보자.

- 자동차의 state를 모델링하기위해서, (위도,경도)로 좌표를 나타낸다. 이를 (x,y)로 치환하자.

- 그리고 자동차가 어떤 방향으로 나아가는지 궁금할 것이다. 이를 가속도로 나타낸다. theta

- 만약 자동차의 속력이 달라진다면 이때 (x',y',theta')으로 정의해보자.

 

- 이제 자동차에 대해 모델링을 진행할 건데, 모델링은 엔지니어들마다 다를 것이다.

- 누군가는 타이어의 마모가 중요하다고 생각할 것이고, 누군가는 자동차의 엔진의 온도를 중요하다고 생각할 것이다.

- 즉, 모델링은 어디에 apply할것인지에 따라 달라지게 된다.

 

2. Discretizaiton

- 연속적인 state space를 다루는 가장 직접적인 방법은 연속적인 공간을 이산적인 공간으로 만드는 것일 것이다.

- 다음과 같이 s2,s1이라는 연속적인 state를 구간을 나눠서 이산적으로 만들어주면 된다.

- 한개의 사각형은 전부 같은 값을 가지게 된다.

- 이러한 이산화의 단점은 무엇일까?

- 첫 번째 단점은 V*나 ㅠ*를 계산할 때 너무 Naive하게 구해지게 된다는 것이다.

- 두 번째 단점은 curse of dimensionality를 갖게 된다는 것이다.

- S = R^n에 있고, 각 차원을 k 값으로 이산화하면, k^n개의 이산화한 공간을 얻게 된다.

- 즉, 차원이 커지면 커질수록 매우 많은 공간을 요구하게 된다는 것이다.

 

3. Guidelines

- 만일 S가 2,3차원이라면 그냥 이산화하면된다고 한다.

- 4~6차원이라도 그냥 이산화하면되는데, s1~s6까지 민감하게 반응하는 아이가 있다면, 그 부분은 세밀하게 쪼개면 된다.

- 7~ 부턴 이산화하지 않는게 좋다고 한다.

 

4. Value Function Approximation

- 이제 연속 MDP에서 policy를 찾는 대안적인 방법을 설명한다. 이 방식에는 V*을 직접 Approximation하여

- discretization을 사용한다. 이 접근법을 value function approximation이라고 불린다.

 

4.1. Using a model or simulatior

- value function approximation을 구현하기 위해, 우리는 MDP에 대한 model 혹은 simulator가 있다고 가정하자

- simulator는 black box 모델로서 어떤 연속적인 s_t와 a_t를 입력받아 다음 상태 s_t+1를 출력한다.

- 이 출력은 state transition probability P_stat에 따라 sampling된다.

 

- 모델을 구축하는 방법에는 여러 가지가 있다.

- 그 중 하나는 "physics simulation"을 사용하는 것이다.

- 또 다른 방법은 기성 물리 시뮬레이션 소프트웨어를 사용하는 것이다.

- "기계 시스템의 전체적 물리적 설명, s_t, a_t"를 입력으로 받아 짧은 시간 후의 상태 s_t+1를 계산한다.

 

- 또 다른 방법은 MDP에서 수집된 데이터로부터 모델을 학습하는 것이다.

- 예를 들어, "m번의 시뮬레이션"을 실행하고, 각 시뮬레이션에서 T번의 timesteps동안 MDP에서 행동을 수행한다고 가정하자.

 

- 이러한 실험은 random actions, policy실행, 또는 기타 다른 방식으로 실행될 수 있다.

- 이를 통해 다음과 같은 m개의 state sequence를 관찰 가능하다.

 

- 이제 학습 알고리즘을 사용하여 다음 상태 s_t+1를 s_t와 a_t의 함수로 예측하게 된다.

 

- 또 다른 방법은 linear model을 학습한다.

- 즉, 다음 상태를 아래와 같이 linear equation을 근사할 수 있다.

- 이는 lienar regression과 유사한 알고리즘을 사용하여 학습된다.

- 모델의 parameters는 행렬 A와 B이며, 실험에서 수집한 데이터부터 다음 최적화 문제를 풀어 추정할 수 있다.

(MLE를 통해 parameter를 구하게 된다.)

 

- A와 B를 학습한후, 다음 상태 s_t+1를 결정하는 방법에는 두 가지가 존재한다.

 

1) deterministic model

- 주어진 s_t와 a_t에 대해 정확히 하나의 s_t+1를 출력하다.

 

2) stochastic model

- 다음과 같이 nosie term epsilon_t를 추가하여 모델링한다.

- 여기서 epsilon_t ㅌ N(o,COV)를 따른다.

 

- linear regression으로 학습할 수 있다면, non-linear regression도 가능하다.

- 예를 들어, s_t와 a_t에 대한 non-linear feature mapping을 적용할 수 있다.

- 각각의 함수는 non-linear feature mapping을 하는 함수를 의미한다.

 

4.2. Fitted value iteration

- 이제 연속 MDP의 value function를 근사하는 방법에 대해서 알아보자.

- 이를, fitted value iteration이라고 한다.

- 우리는 이제 state space S가 연속적인 공간이며, activation space A는 작고 이산적이라고 가정하자

- value iteration은 다음과 같은 update를 수행한다고 하자.

- 이를 다음과 같이 정의할 수 있다.

 

- fitted value iteration의 핵심 아이디어는 위의 update를 finite sample of states에서 근사적을 수행하는 것이다.

- supervised learning algorithm을 사용하여 value function을 state로 근사시킬것이다.

- 여기서 phi는 feature mapping을 의미한다.

- 각 state에서 fitted value iteration은 다음 값을 계산한다.

- 우리는 supervised learning algorithms을 적용하여 V(s)가 y에 가깝도록 학습시킨다.

 

- 알고리즘은 다음과 같다.