Ssong

반갑습니다 :)

[RL] Lecture 2: Markov Decision Process

Date:     Updated:

카테고리:

태그:

1. Markov Processes

1.1 Introduction to MDPs

  • Markov decision processes는 environment를 설명한다.
  • environment는 fully observation 가능한 상황
    • 현재 State가 현재의 프로세스를 완전히 표현할 수 있는 == Markov 한 상황
  • 거의 모든 RL 문제들은 MDP형태로 나타낼 수 있다.
    • ex) Optimal control, Bandits

Markov Property

image

  • 현재가 주어져 있다면, 미래는 과거와는 독립적이다.
  • state가 모든 history와 관련된 모든 정보를 가지고 있기 때문에, state를 아는 순간 history를 버릴 수 있다.

  • state는 미래에 대한 충분한 통계적 표현형이다.

  • State transition probability(\(P_{ss'}\)) : s에서 s’으로 갈 확률

    image 1

  • State transition matrix : \(P_{ss'}\) 을 matrix 형식으로 나타낸 것
    • 모든 각 row의 합은 1

    image 2

1.2 Markov Process

image 3

  • memoryless : 과거 상태와 상관 없이 현재의 상태만이 future state에 영향을 준다 ⇒ Markov property
    • Next state가 previous state에 대해서 독립이면 memoryless property를 가졌다고 볼 수 있다.
  • random process : 동일한 state에서 시작하더라도 어떤 state를 거치는지에 따라 여러가지 episode를 sampling 할 수 있다.
    • random한 state들의 sequence는 Markov property를 따른다.
  • S : state들의 유한한 집합
  • P : state transition 확률 matrix

1.3 Example: Student Markov Chain

image 4

  • 위 예시에서 State는 7개, State의 transition 확률은 화살표로 표기
  • Episode : Agent가 start state → terminal state까지 가는 과정
    • ex) C1 C2 C3 Pass Sleep ⇒ episode
  • Sampling : episode를 만든다.

image 5

2. Markov Reward Processes

2.1 Markov Reward Process

image 6

  • Environment에는 reward가 존재하므로 Markov Process \(<S,P>\)에 \(R\)과 \(γ\)를 추가하면 Markov reward Process를 정의 가능
  • \(R\) : reward function : 어떤 state에 도달하면 reward 축적

  • \(γ\) : discount factor

  • Markov Process + Reward + discount factor ⇒ Markov Reward Process
    • MRP에서는 action이 존재하지 않고 (action에 대한 reward가 아닌 state에 reward 이므로) 확률적으로 state만 선택한다.

Example : Student MRP

image 7

2.2 Return

image 8

  • discount \(γ ∈ [0,1]\)
    • K + 1 time-step 이후의 reward는 \(γ^kR\)의 reward로 표현한다
    • immediate reward가 delayed reward보다 더 큰 영향을 줄 수 있게 한다
  • \(γ\) 값에 따른 효과
    • 0에 가까울수록 “myopic” evaluation (근시안적)
    • 1에 가까울수록 “far-sighted” evaluation (미래지향적)
  • RL의 목적
    • cumulative reward를 maximize 하는 것이 목표
    • 이때 cumulative reward를 return \(G_t\) 라고 한다. ⇒ return의 maximize
  • Discount를 사용하는 이유
    • 수학적으로 편리하다.
      • discount로 수렴성이 증명된다.
    • sampling 중 만약 모든 sequence가 terminal state로 끝나는 것이 보장된다면, \(γ\) = 1이 가능할 수도 있다.
  • discount가 없을 때 발생할 수 있는 문제점
    • infinite한 time-step을 가질 때, 매 time step마다 0.1의 reward를 받는 episode와 1의 reward를 받는 episode를 구분할 수 없다. (∞ 크기비교 불가)
    • Agent가 시작할 때 1을 받은 경우와 종료할 때 1을 받은 경우 둘 중에 어떤 episode가 더 나은지를 판단할 수 없다.

⇒ 문제마다 discount가 필요할 수도 있고 없을 수도 있다. 잘 판단해서 사용해야한다.

2.3 Value Function

image 9

  • MRP에서의 State Value function v(s)은 state s에서 시작하는 return의 기대값

image 10

  • sampling 시에 같은 state에서 시작해도 episode마다 다른 return 값들이 생성되고 이에 대한 평균치가 v(s)

Example: State-Value Function for Student MRP

image12

  • \(γ\)=0이기 때문에, reward와 v(s)가 같은 결과를 보인다 (myopic)
  • \(γ\)=1일 때는 더 far-sighted한 결과

2.4 Bellman Equation for MRPs

  • Value function은 다음의 2가지 part로 분리할 수 있다.
    • immediate reward \(R_{t+1}\)
    • discounted value of successor state \(γv(S_{t+1})\)
  • 유도과정

image 13

  • Bellman Equation의 직관적인 이해

image 14

Bellman Equation

  • 현재 State s가 Transition할 수 있는 다음 state s’들의 후보는 여러가지가 있을 수 있다.
    여러가지 후보 중에서 확률에 따라 next state를 결정하게 된다.
    따라서 가능한 여러가지 episode들에 대한 기대값으로서 Return을 계산하며, 이때 같은 value-function을 사용하여 재귀 형태로 표현할 수 있게된다.

image 15

  • Expectation을 제거한 형태
    • MRP에서 Reward는 현재의 State s에 따라 고정된 상수이기 때문에 그대로 나옴 \(R_{t+1}\), \(R_{t+2}\) … 다 같다.
    • v(s’)은 s’가 무엇인지에 따라 달라지는 값이기 때문에 Expectation을 적용

      • Definition of Expectation : Probability X Value

        image 16

      • Example: Bellman Equation for student MRP

      image 17

Solving the Bellman Equation

  • for Matrix form

image 18

  • Solving Bellman Equation

image 19

  • 넘기고, 역행렬 곱

⇒ Bellman Equation을 linear equation으로 표현하여 directly solve할 수 있다.

  • 단점
    • Computational complexity가 \(O(n^3)\)이다.
    • state가 커질수록 계산량이 매우 커지기 때문에 direct solution은 small MRPs에만 적용한다.
  • 대부분의 경우 MRPs는 iterative method를 이용하여 해결한다.
    • Dynamic Programming
    • Monte-Carlo evaluation
    • Temporal-Difference learning

3. Markov Decision Processes

3.1 Markov Decision Process

image 20

  • MP, MRP에서는 State의 변화가 오로지 Environment의 transition probability \(P\)에 의해 결정
  • MDP에서는 State의 변화가 Agent의 Action \(A\)에 의해 결정 (환경의 불안정함은 존재)

image 21

MDP는 enviroment 꺼고, policy는 agent에 속하므로 위 그림은 policy없이 MDP 상태만 표시

  • Agent가 어떠한 Action을 취했을 때, Agent가 인식하는 State가 deterministic 하게 결정되지 않고 확률적으로 정해지게 된다.
  • 또한 해당 State에서 그 Action을 할 확률도 정해진다.
  • ex) 무인이동체가 우회전이라는 action을 결정했지만, 그 순간 빨간불로 신호가 바뀌어 우회전을 하지 못하고 정지하는 경우

3.2 Policy

image 22

  • policy는 agent의 행동을 결정한다.
  • MDP policy는 현재 state만을 의지한다 (Markov 하다)
  • policy는 stationary하고 시간에 독립적이다.

MRP에서는 action이 없기 때문에 policy가 없었음, 확률에 의해 다음 state로 이동

MDP에서는 action을 어떤 policy로 결정하는지 중요함

⇒ MDP를 푼다 = 어떤 Policy를 통해 reward를 최대로 만들 것인가 = Optimal Value Function을 구했다 = MDP Solved!

MDP에서 Agent의 policy가 고정이라면 Agent가 없는 Markov Process로 표현할 수 있다.

Given an MDP \(M=<S,A,P,R,γ>\) and a policy \(π\)

  • State sequence \(S_1,S_2\),⋯ → Markov process \(<S,P^π>\) 로 표현할 수 있다.
  • State and Reward sequence \(S_1,R_2,S_2\),⋯ → Markov reward process \(<S,P^π,R^π,γ>\) 로 표현할 수 있다.

MDP에서 agent가 어떤 고정된 policy를 가지고 움직인다고 가정 어떤 action 선택하고 transition probability에 따라 최종적으로 어떤 state가 next state가 되는지를 확률로서 계산할 수 있다.

transition probability

image 23

agent가 policy로 s → s’ 이동하려면 두가지가 필요하다.

  1. state s에서 action a를 할 확률
  2. action a를 했을 때 state가 s → s’ 으로 이동할 확률

위 1,2번의 곱을 합산하면 agent가 policy로 s → s’ 이동할 확률이 나온다. ⇒ transition probability

reward

image 24

s의 return은

  1. state s에서 action a를 할 확률
  2. state s에서 action a를 했을 때 reward

위 1,2번의 곱을 합산하면 s의 return이 나온다.

3.3 Value Function

어떤 “Policy”를 따라서 episode를 진행하는지에 따라 Value가 달라질 수 있기 때문에,
Agent가 어떻게 행동하는지를 나타내는 Policy \(π\)를 함께 기술한다.

image 25

  • 현재 State s에서 선택하는 action a는 Policy를 따라 선택한 것이 아닐수도 있음 단 이후부터는 Policy \(π\)를 따라감
  • action-value function이 정의된다면, Agent가 어떤 action을 선택할 지 결정할 때 Action value function의 값을 보고 선택하기만 하면 됨 ⇒ 문제를 간단하게 표현할 수 있다.
  • Q-Learning이나 DQN에서의 Q가 바로 action-value function이다.

3.4 Bellman Expectation Equation

MRP에서 value function을 2가지 part(immediate reward, discounted value)로 분리했던 과정을 동일하게 적용하면 MDP에서도 Bellman Equation을 구할 수 있다.

image 26

Bellman Expectation Equation for \(V^π\)

image 27

  • \(V_π(s)\) = (state에서 action을 할 확률 X action-value function인 \(Q_π\) )의 합

Bellman Expectation Equation for \(Q^π\)

  • State s에서 action a를 하고 Policy를 따라갔을 때 얻을 수 있는 Value의 기대값

image 28

  • \(Q_π(s)\) = state s에서 action a한 reward + \(γ\) X (s’ 될 확률 X s’의 value)의 합

MRP에서의 Bellman Equation과 달리, MDP에서는 action의 존재로 인하여 가장 초기의 Bellman Equation을 바로 표현하기 힘들다, 따라서 action-value와 state-value간의 관계를 이용하여 Bellman Expectation Equation을 표현한다.

Bellman Expectation Equation for \(V^π\) (2)

image 29

  • Q자리에 V넣음

Bellman Expectation Equation for \(Q^π\)(2)

image 30

  • V자리에 Q넣음

Example : Bellman Expectation Equation in Student MDP

image 31

Bellman Expectation Equation(Matrix Form)

MDP에서 Agent의 Policy가 고정이라면 Agent가 없는 MRP로 표현할 수 있기 때문에, 그대로 matrix form을 적용해서 direct solution을 얻을 수 있다.

image 32

  • Bellman Equation을 이용하여 MDP에서 Value function을 풀었으나 big MDP에서는 direct solution 사용 불가능 (계산복잡도 크다)

⇒ 지금까지 Value function을 구한 것이고 Action에 대한 것은 구하지 않음 주어진 Policy에 대한 Value function 만을 구했음(Sampling) ⇒ Bellman Expectation Equation

4. Optimal Value Functions

4.1 Optimal Value Function

  • Definition of Optimal Value Function
    • 가능한 모든 Policy에 대하여 계산했을 때, 그 중에서 가장 maximum 값을 갖는 value function

    image 33

  • Optimal Value Function
    • optimal value function은 MDP에서 가능한 최고의 성능을 나타낸다.
    • 해당 MDP의 optimal value function을 찾았다면, 그 MDP는 “Solved”되었다고 한다
    • 일반 Value function과 달리 bellman optimality equation은 matrix form으로 표현되지 않기 때문에 directly solve가 불가능하다.
  • Example

image 34

image 35

4.2 Optimal Policy

image 36

Policy가 두 개가 있을 때 항상 더 나은 Policy를 찾을 수 있는 건 아님, 근데 찾을 수 있는 경우가 있음

  • 모든 State에 대해서, \(v_π(s)\) 가 \(v_{π'}(s)\)보다 같거나 크다면 π ≥ π’ 이다.

image 37

MDP에서 Optimal Policy \(π_*\)가 존재한다는 것은 이미 증명되어있음

  • 다른 모든 Policy보다 더 같거나 좋은 \(π_*\) ≥ \(π\), \(∀π\) optimal policy \(π_*\)가 존재한다.
    • optimal policy를 따르는 Value function은 optimal value function과 동일하다.

    • 모든 optimal policy는 그 optimal policy를 따르는 optimal value function을 가진다.

      image 38

    • 모든 optimal policy는 그 optimal policy를 따르는 optimal action-value function을 가진다.

      image 39

Finding an Optimal Policy

optimal action-value function에 대하여 max가 되게 하는 action만을 계속해서 하는 policy

image 40

\(q^*(s,a)\)를 아는 순간 최소 1개의 Optimal Policy를 알 수 있음 ⇒ \(q^*\)가 s에서 어떤 a를 해야할지 알려주기 때문 (⇒ 그 action을 할 확률이 1이고 나머지가 0인 policy가 optimal policy)

  • 즉 optimal action-value function $$q_*(s,a)$$를 알고있으면 그 즉시 deterministic optimal policy를 구할 수 있다. ⇒ MDP를 solve!
  • 모든 MDP 문제에서 결국 deterministic optimal policy가 존재 (실제로는 Stochastic한 문제여도)
    • 원래 policy는 각각의 action을 수행할 확률로 정의되기 때문에 stochastic하다.
    • 하지만 optimal action-value function을 사용하여 구한 optimal policy는 하나의 action만을 하도록 결정된 deterministic한 policy이다.

image 41

4.3 Bellman Optimality Equation

image 42

기본적으로 Bellman Expectation Equation과 동일한 구조.

하지만 optimal policy를 알지 못해서 모든 수식을 Expectation으로부터 표현하기 시작했던 것과 달리
여기서는 optimal policy를 알고 있기 때문에 max가 추가됨

⇒ maximise하는 action을 선택하는 policy

⇒ State에서의 optimal value = \(q_*\)의 max action을 선택하면 됨

image 43

  • 똑같은 식인데 *가 추가됨

image 44

image 45

  • 이 식은 max 때문에 Linear equation이 아니다. (max는 최대값을 고르는 것이기 때문에)
    • Bellman Expectation Equation과 Bellman Optimal Equation이 다른 점
    • 역행렬으로 풀수없음 X, Closed form으로 풀 수 없음

image 46

Q. 빨간색 state의 value가 6이라고 알려져 있을 때, Bellman Optimality Equation을 만족하는가?

Bellman Optimally Equation을 푸는 방법

  • Bellman Optimally Equation은 non-linear equation이다. (max 때문)
    • 그래서 closed form solution을 가지지 않는다. (in general)
  • 따라서 여러 방법적인 Solution들이 존재
    • value iteration (DP)
    • policy iteration (DP)
    • Q-learning
    • Sarsa

맨 위로 이동하기

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

댓글남기기

최근 글 10 개 :)