Reinforcement Learning - Lecture #2 : Markov Decision Process

Behumble.log·2024년 1월 8일

reinforcement learning

Reinforcement Learning

목록 보기

2/4

"앞으로 강화학습에 다루게 될 포스팅은 Google DeepMind에서 제공하는 RL Cource by David Silver 강의를 듣고 강의자료를 참고하여 개인적으로 리뷰하는 내용입니다. 개인적인 학습 및 리뷰가 주된 목적이므로 강의의 모든 내용을 포함하지 않을 수 있으며 핵심적이거나 제가 이해하기 어려웠던 내용들을 다룰 것임을 포스팅에 앞서 알립니다."

Introduction to MDPs

MDP(Markov decision process)에 대해 간략하게 소개하자면 다음과 표현할 수 있습니다.

"Markov decision processes formally descirbe an environment for reinforcement learning where the environment is fully observable."

1강에서는 RL에 관한 introduction으로써 Sequential Decision Making 문제 정의를 위한 뇌모양의 Agent와 지구 모양의 environment간의 상호작용(observation, reward, action) 개념에 관하여 공부하고 관련 용어를 정리하였습니다.

Lecture#2에서는 1장에서 다뤘던 개념을 바탕으로 순차적 문제 해결을 위한 MDP 문제 정의 방법을 상세하게 다룹니다.

Markov Reward Process(MRP)

MDP의 정의 이전에 강의에서는 Markov Process(MP), Markov Reward Process(MRP)에 대하여 다루고 있습니다. 각각의 개념은 MDP tuple과 비교했을 때 MRP의 경우 Action, MP의 경우 Action과 Reward function의 개념이 포함되지 않은 개념이라고 생각하시면 됩니다. 그 중 MRP에 관한 개념을 정리하고 넘어가겠습니다.

Markov Property

"The future is independent of the past given the present."

Markov Property는 Lecture1에서 간략하게 다뤘던 Markov state 성질과 같은 내용입니다.

위 식과 같이 조건부확률로 다음 state에 대한 정보를 표현해보면 현재 시간 t에 대한 state인 St에만 dependent하게 다음 state로 갈 확률이 표현됩니다.

즉, Markov Property란 어떤 시간 t에 대하여 거쳐온 과거의 state에 관계없이 오직 현재 state에만 dependent하게 특정 state로 갈 확률은 같다는 성질입니다.

Return & Value Function

Reinforcement Learning에서의 목적은 Culmulative Reward-return-를 최대로 하는 Policy를 찾는 것입니다.

MDP에서는 Culmulative Reward에 관해 "Return"개념을 활용하여 재정의합니다.

Return(Gt)값은 step t에 대하여 discount factor γ에 의한 total discounted reward입니다. 여기서 discount facotr γ는 0에서 1사이의 스칼라값입니다.

* Why discount?

그렇다면 RL에서 discount factor를 활용하는 이유는 무엇일까요?
Silver교수님께서 가장 중점적으로 이야기하신 두 가지 이유는 다음과 같습니다.

1. Mathematically convenient to discount rewards

강화학습의 전제조건에 맞게 실제 상황을 모델링하기 위해서는 수학적인 모델링이 중요합니다. 이러한 측면에서 discount factor는 보상의 감소에 대해 수학적으로 표현하기 용이합니다.

2. Avoids infinite returns in cyclic Markov processes

강화학습의 optimal policy를 찾기 위하여 value function을 계산하는 과정에서는 값이 수렴할 때까지 recursive한 계산이 필요합니다. 이러한 과정에서 [0,1] 사이의 discount factor γ값은 급수를 수렴하도록 하여 발산하지 않도록 수학적인 모델링이 가능합니다.

return개념을 포함한 최종적인 MRP에서의 (state)value function의 정의는 다음과 같습니다.

((state)는 MDP에서 차후 action-state function의 개념과 구분되므로 괄호로 표현하였습니다.)

Bellman Equation for MRPs

정의에 입각하여 value function을 변형하고 이를 matrix식으로 정리한 내용은 다음과 같습니다. 아래와 같이 value function은 다음 step 시간인 (t+1)에서의 state에 대한 value function으로 표현될 수 있습니다.

기댓값을 직접적인 계산을 위해 식으로 표현해보면,

와 같이 정리할 수 있습니다. 위 식은 간단한 예제의 value값 계산에 유용하게 사용될 수 있습니다.

마지막으로 Bellman (expected) Equation은 행렬 표현에서 역행렬을 활용하여 식을 정리할 수 있다는 장점이 있습니다.

하지만 O(n^3)의 거대한 시간복잡도를 가지기 때문에 직접적인 활용의 경우 크지 않은 MRPs에만 적용하는 것이 바람직합니다.

이러한 시간복잡도 문제는 뒤에 공부할 "Iterative methods"를 활용하면 해결할 수 있습니다.
EX) Dynamic programming, Monte-Carlo evaluation, Temporal-Difference learning

Markov Decision Process(MDP)

Markov Decision Process(MDP)는 Markov속성을 가지는 environment의 표현 방법입니다.
즉, 순차적 문제 Sequential Decision Making 의 정의하는 방법입니다. MDP는 5가지 속성을 갖는 tuple로써 아래와 같이 정의할 수 있습니다.

총 5개의 속성으로 State, Action, State transition probability matrix, reward function, discount factor로 문제가 정의됩니다.

* 관련 용어는 이전 포스팅을 참고해주시길 바랍니다.

Policy

Policy란 주어진 state에 대해 해당 action을 취할 확률분포입니다. 정의는 다음과 같이 조건부확률로 표현됩니다. policy값에 따라서 해당 action을 지시하더라도 해당 action을 할 수도, 하지 않을 수도 있습니다.

MDP에서 Policy는 Agent의 행동을 정의하는 값이라고 보시면 됩니다. 이 외에도 Policy는 stationary(time-independent)하다는 특징이 있습니다.

MDP에서는 MRP와 비교했을 때, Action에 관한 속성이 추가되므로 MDP에서의 value function은 policy π값을 아래첨자로 추가하여 표현합니다.

Value Function

MDP에서의 value function은 state에 대한 미래 보상에 대한 기댓값인
"state-value function"과 state에서 특정 action을 취했을 때의 미래 보상에 대한 기댓값인
"action-value function(q-function)"으로 나눌 수 있습니다.

"Value Function이란 Agent가 어떤 action이 더 좋은 Policy가 될 것인지 판단하는 기준으로, Value Function은 현재 state로부터 policy π를 취했을 때 받을 것으로 예상되는 보상의 합, return이다."

- State-value function : vπ(s)

- Action-value function : qπ(s,a)

각각의 value function이 의미하는 바를 구분하여 이해할 필요가 있습니다.

* 특히, q-function의 경우 어느 s에서 특정 action a를 했을 때 기댓값을 의미하므로 Dynamic Programming에서 Policy Improvement에 활용된다는 점을 미리 알아두면 좋겠습니다.

Bellman Expectation Equation

MDP에서의 state-value function, action-value function(q-function)의 정의의 return값을 수식적으로 풀어보면 다음과 같이 표현할 수 있습니다.

이를 직접적인 계산을 위한 수식으로 풀어보면 다음과 같습니다. 각각의 식은 정의한 값에 대하여 Policy π값을 곱한 값의 합을 나타내어 기댓값을 수식으로 표현합니다.

EX) Bellman Expectation Equation in Student MDP
이해를 돕기 위한 예시는 아래와 같습니다. 해당 예시는 강의를 수강하는 학생에 대한 MDP 모델로 강의 내내 MP,MRP 등의 예시 설명을 위해 사용되었던 모델입니다. 다이어그램에서 R은 특정 state에서 특정 action을 취했을 때 reward값에 해당하고 원에 해당하는 state에 표시된 값은 value function값을 의미합니다.
(문제에서 policy값과 discount factor값은 1로, state transition probabilty는 0.5로 설정되었습니다.)

빨간색으로 표시된 state에서 state-value function값을 계산하면,
7.4 = 0.5 (1 + 0.2 -1.3 + 0.4 2.7 + 0.4 7.4) // action "Pub"에 대한 state-value 계산
+ 0.5 * 10 // action "Study"에 대한 state-value 계산
과 같이 계산되어 등호가 성립함을 확인할 수 있습니다.

Optimal Value Function

MDP에서 최종적으로 구하고자하는 것이 바로 이 Optimal Value Function과 이를 기반한 Optimal Policy입니다. Optimal value function은 Policy를 판단하는 기준인 Value Function을 기준으로 각각 max함수를 사용하여 다음과 같이 정의됩니다.