강화학습_(7) - Markov Decision Process (MDP)

시간이 없으니까 쫙 쓰고 주말에 정리를 해보자.

 

1 Markov Decision Process

: 강화 학습은 MDP로 표현되는 문제를 푸는 알고리즘의 집합이다.

 

1) Markov chain, Markov Reward Process

 

- Markov 하다가 무엇일까?

 

-> 현재는 처음 상태부터 바로 직전 상태까지의 결과로부터 도출되었다.

-> 바로 직적도 그 이전의 상태까지의 결과로부터 도출되었다.

-> 즉, 바로 직전 상태는 그 이전 상태의 모든 결과를 포함한다.

 

=> 따라서 현재는 바로 직전 상태의 결과로만 표현될 수 있다.

(아주 작은 미생물의 독성이 먹이 사슬 끝까지 이어지는 것과 비슷하다.)

 

-> 윗 식과 같이 처음 어떠한 상태에서 시작하여 현재 상태까지 올 확률이 전 상태에서 현재 상태까지 올 아래의 확률과 같을 때 state는 Markov하다고 말할 수 있다.

 

=> 강확학습은 기본적으로 value라는 어떠한 가치가 현재의 state의 함수로 표현되고 이 state가 Markov하다고 가정된다.

 

 

 

 

2) MDP 문제의 정의

 

 

-> state   //   action   // state transition probability matrix   //   reward   //   discount factor로 이루어져 있다.

 

-> 간단하게 정리해보자.
: state는 현재 상태, action은 취한 행동, state transition probability matrix는 내가 어떤 action을 취했을 때 발생될 다음 state에 대한 확률, reward는 특정 state에서 어떠한 action에 대한 보상, discount factor는 눈 앞의 보이는 reward와 미래에 받을 수 있는 reward에 대한 가중치!

 

1] State
: agent가 인식하는 자신의 상태.

 

-> state는 다양하게 정의될 수 있다.

ex)

 

- 차의 종류와 탑승객 수, 속도

 

- pixel

 

- x, y, z 축으로부터의 거리 등

 

 

2] Action
: environment에서 특정 state에 갔을 때 action을 지시하는 것.

 

- agent는 action을 취함으로써 자신의 state를 변화시킬 수 있다.

 

 

3] State transition probability matrix

: state가 어떤 action을 취했을 때 다음 state가 deterministic하게 딱 정해지는 것이 아닌 stochastic하게 정해진다.

(environment에 대해 agent는 observable하다.)

 

 

 

4] Reward

: agent가 action을 취했을 때 받는 reward.

- reward의 총합이 가장 큰 policy를 학습하는 것의 강화학습의 목표이다.

 

 

 

 

5] Discount factor
: reward에 대한 가중치를 부여한다.

 

- reward의 총합을 계산하는 강화학습의 특성 상 다음의 두 가지 문제 점이 발생한다.

 

-> 0.1의 reward를 무한히 받거나 1의 reward를 무한히 받거나 어쨌든 총합은 무한대이다.

 

-> 당장 받는 1의 reward와 나중에 받는 1의 reward의 가치 차이

 

=> 즉, 비교 불가

 

 

 

 

3) Policy

: agent는 각 state 마다 action을 결정하게 된다. 특정한 목표가 정의되어 있을 때 이것을 만족하는 state->action의 일련의 과정이 진행되는데, 이때 어떤 state에서 어떤 action을 할지를 policy라고 한다.

 

- 강화학습은 이러한 policy 중에서 reward를 최대 (또는 최소)로 하는 optimal policy를 찾는 것이다.

 

-> state s에서 action a를 할 확률을 말한다.

 

 

4) MDP Graph

 

 

 

- 다음의 MDP의 graph는 state 사이의 transition이 아닌 action을 통해 변화하는 state와 그때의 reward를 표현하고 잇다.

 

 

 

 

2. Value Function

 

 

1) Return : agent가 state를 시작하고 끝날 때까지 받은 reward를 다 더한 것을 말한다.

 

-> discount factor를 고려한 reward의 총합입니다.

 

 

 

2) State value function : return에 대한 expectation이다.

 

-> 어떤 state s의 value를 말해준다. (높은 value를 가진 state로 이동하는 것이 optimal policy인 듯)

 

 

- 만약 agent가 policy를 고려하여 action을 한다고 가정할 때 value function은 policy 마다 달라지게 된다. 
-> policy에 대한 value function은 다음과 같다.

 

 

-> 강화학습의 알고리즘에서는 value function을 얼마나 bias하지 않고 variance가 낮으며 true값에 가깝게 잘 찾는지가 중요하다. (+ 효율적이고 빠르게)

 

 

 

3) Action value function

- state에 대한 value는 그 state에서 어떤 action을 했는지에 따라 달라지는 reward에 대한 정보를 포함하고 있다. 

 

- agent는 다음의 행동을 다음으로 가능한 state들의 value function으로 판단한다. 

 

->  따라서 action에 대한 value function을 구할 수 있다.

 

=> action value function은 어떤 action을 할지를 해당 function을 보고 판단할 수 있게 한다.

 

=> 현재 state의 다음 state들의  value function을 알고 어떤 action을 했을 때 가게 될 state에 대한 확률을 고려하지 않아도 된다.

 

==> 쉽게 말해서 그냥 여타 고려할게 없어지고 각 action에 대한 가치를 알려주기 때문에 높은 가치의 action만 따라가면 된다.  (위의 state value function에서 policy를 고려하는 게 있었나..? -> 정확히는 나오지 않았는데 following policy라고 되어있네)

 

 

-> 어떤 state s에서 action a를 선택했을 때 return되는 expectation 값.

 

 

** policy를 고려하지 않아서 더 편리하다? 정도인가

 

 

 

 

3. Bellman Expectation Equation

 

 

 

- 2번에서 살펴본 value function은 다음과 같은 2종류가 있다.

 

 

 

          1. 어떤 state에서 policy를 고려했을 때 받게 되는 reward의 총합

 

          2. 어떤 state에서 특정 action을 했을 때 받게되는 reward의 총합

          -> 1번은 policy에 따라 결과가 바뀌고 optimal policy를 따랐을 때 최댓값이 나온다.

          -> 2번은 다음의 action들 중 가장 높은 값을 가지는 action을 선택하면 optimal policy를 따르는 것과 동일한

          결과를 가진다.

 

1) Bellman equation for Value function

: 다음 state와 현재 state의 value function 사이의 관계를 식으로 나타낸 것을 Bellman equation이라고 한다.

 

-> 해당 식의 4번째와 5번째 등호를 보면 현재 상태에서 return될 수 있는 reward의 총합은 이전 상태의 reward의 총합에 discounting factor를 고려해준 것과 동일하다.  (Markov process와 동일한 꼴을 가지는 것 같네)

 

 

-  value function (policy를 포함한)과 action value function도 Bellman equation의 형태로 다음과 같이 표현될 수 있다.

 

 

 

- 위의 정의들이 추상적이고 비직관적일 수 있어서 state-action pair (어떤 state에서 특정 action을 한 것을 하나의 새로운 state로 생각하는 개념)에 대해서 관계를 나눠볼 수 있다. (위의 정의가 제일 직관적이지 않나..)

 

 

-> 흰 원은 state, 검은 점은 action을 말한다. 이 둘은 policy로써 함께 묶이게 된다.

 

=> 중요한 점은 state value function이 각 action을 선택했을 때의 action value function과 각 action을 취할 policy를 곱한 총합이라는 점이다. (이게 위의 정리를 다 아우르는구먼)

 

 

 

- 이제 action을 취했을 때 갈 수 있는 state들을 표현해보자.

 

 

=> 여기서 중요한 점은 특정한 action을 취했을 때 하나의 state로만 수렴하지 않는다는 것이다. 이때 각각의 state로 갈 확률을 state transition probability matrix라고 한다.

(만약 하나의 state에만 수렴한다면 deterministic하거나 state transition probability matrix에서 해당 값이 1일 것이다.)

 

=> action value function은 해당 이전 state에서 해당 action을 선택했을 때 얻게 되는 (immediate return)과 (다음 state들의 state value function의 state transition probability matrix를 고려한 총합)에 (discounting factor)를 곱하여 더한 값이다.

 

 

 

- 따라서 위의 두 도식을 종합하면 다음과 같다.

 

-> 어떤 state에서 policy (state->action에 대한 확률)를 고려한 state value function은 특정 action을 취했을 때 얻게되는 action value function에 policy를 곱한 총합이다.

 

=> 실제 강화학습을 진행할 때 reward와 state transition probability는 미리 알 수가 없다.

=> 전부 알 수 있을 때 MDP를 모두 안다고 하며, 이것이 MDP의 model이 된다.

 

=> 강화학습의 큰 특징은 model을 몰라도 학습을 할 수 있다.

=> 즉, reward function과 state transition probability를 모르고 학습을 진행하는 강화학습에서는 Bellman equation으로 결과를 구할 수 없다. (그럼 왜 지금까지 정의했지?)

 

 

 

2) Bellman equation for Q-function

 

 

- 위와 같은 식을 action value function에 대해 정의하면 다음과 같다.

 

 

-> 현재 action의 value는 지금 갈 수 있는 state들에서 선택할 수 있는 action들의 value의 총합이다.

 

 

 

3) Bellman Optimality Equation

: Bellman eqation은 앞서 설명한 Bellman expectation equation과 이제 설명을 시작할 Bellman optimality eqation으로 구분된다.

 

 

- 앞서 설명한 Bellman expectation equation은 다음과 같다.

 

 

-> expectation으로 표현되어 있으며 그냥 Bellman eqation이라고 한다.

 

=> 여기서 Backup의 개념이 나온다.

 

 

-> Backup이란 코딩에서 등호의 의미에 가까우며 오른쪽의 식을 왼쪽에 대입하는 개념이다.

 

=> 즉, 위의 그임에서 미래의 값을 대입하여 현재의 값을 구한다는 것이 backup이다.

 

=> Backup은 one step backup과 multi-step backup이 있다. 또한 Full-width backup (가능한 모든 다음 state들의 value function을 사용함)과 sample backup (실재의 경험을 사용함)이 있는데 전자는 dynamic programming이고 후자는 reinforcement learning이다.

 

 

1] Optimal value function
: 가장 많은 reward를 받을 policy를 따랐을 때의 value function을 말한다.

 

- optimal action value function도 마찬가지로 현재 (s, a)에서 얻을 수 있는 최대의 value function을 말한다.

 

 

 

-> 따라서 environment에서 얻을 수 있는 가장 큰 reward의 총합이다.

 

=> \( q_{*] \) 가장 높은 action만을 따라가면 되기 때문에 optimal action-value function을 알고있을 때 최적화 문제가 풀렸다고 할 수 있다.

 

=> 따라서 optimal policy는 가장 높은 action만을 고르기 때문에 deterministic하다.

 

 

 

-> 해당 그림에서 optimal action value function이 가장 높은 값을 따라가면 optimal한 결과값을 얻을 수 있다.

 

 

 

2] Bellman Optimality Equation

: Bellman optimality equation은 위의 optimal value function 사이의 관계를 나타내주는 식이다.

 

 

- backup diagram과 다른 점은 호의 모양으로 표시된 max 이다.

 

 

-> 어떤한 상태에서의 optimal state value function은 optimal action value function을 가지는 action을 선택했을 때의 reward와 그 action을 취한 뒤 얻게되는 다음 state의 optimal action value function에 state transition probability matrix를 고려한 값의 총합에 discounting factor를 더 값이다.

 

 

 

 

 

** 모든 value function은 다음 선택에 대한 종합적인 값을 더한 총합이다.

이 때 중요한 점은 state에서 action을 선택할 때는 policy를 곱해주고,

action을 선택한 다음 state로 넘어갈 때는 state transition probability matrix를 고려해주어야 한다는 점이다. 

 

그리고 당연히 현재 immediate reward를 제외한 이전 reward의 총합에 대해선 discounting factor가 적용된다.

 

 

출 처   : Fundamental of Reinforcement Learning

저 자   : Woong won, Lee