Amoogae

[강화학습] Markov Decision Process

—

by

amoogae
in ,

강화학습에서 국밥처럼 든든한 개념인 Markov Decision Process에 대해서 소개한다.

  1. Introduction
  2. Markov Chain
  3. Markov Reward Process
  4. Markov Decision Process
  5. Optimal Values and Optimal Policies
  6. Pratially Observable Markov Decision Process
  7. 정리
  8. 참고

Introduction

강화학습은 주어진 환경 내에서 에이전트가 최적의 행동 전략을 학습하는 방법론이다. 이 과정에서 마르코프 결정 프로세스(Markov Decision Process, MDP)가 중요한 역할을 한다. 본 글에서는 MDP의 기본 구조와 그 구성 요소들을 살펴볼 것이며, 최적 정책을 찾는 데 사용되는 벨만 방정식에 대해서도 탐구한다.

Markov Chain

먼저, 마르코프 모델은 다음과 같은 특징을 지닌다:

  • 시간에 따라 변화하는 시스템을 수학적으로 표현한 모델
  • 시스템의 상태와 이들 간의 전이(transition), 전이확률(transition probability)를 포함한다.
  • 마르코프 특징(markov property) : 다음 단계의 상태는 오직 현재 상태에 의해서만 결정된다는 특징

이러한 마르코프 모델의 기본 형태에는 Markov Chain이 있다. Markov Chain은 러시아 수학자 Andrey Markov가 처음으로 제안한 아이디어이다. Andrey Markov는 동료 수학자와 ‘대수의 약한 법칙을 증명하기 위해 반드시 사건들이 독립적일 필요가 없다’는 것을 증명하고자 했다.

대수의 약한 법칙이란, 충분히 많은 시행을 거치면 특정 사건의 평균 결과가 어떤 기대값(확률값)에 수렴한다는 법칙이다. 예를 들어 동전을 던져서 앞면이 나올 확률과 뒷면이 나올 확률을 각각 0.5라고 했을 때, 무수히 많은 시행을 거치면 실제로 사건의 평균 결과가 0.5에 수렴한다는 것이다.

앞서 동전 던지기 문제처럼 대부분의 확률 모델링 문제에서는 사건이 독립적이라는 가정이 필요했지만, Andrey Markov의 정리 덕분에 이전 사건과 다음 사건이 종속성을 갖는 문제들도 확률 모델링을 할 수 있게 되었다.

Markov Chain을 정리하면 다음과 같다:

  • 유한한 수의 상태가 있고 이들 간의 전이는 전이 확률에 따라서 시행되는 수학적 모델
  • <S, P> 로 구성됨 (S : state, P : Transition Probability)

Markov Reward Process

마르코프 체인에 ‘보상’ 개념을 추가하면 마르코프 보상 프로세스(Markov Reward Process, MRP)가 된다. MRP는 보상이라는 개념을 통해 각 상태의 가치를 수치화할 수 있다.

MRP에서는 에이전트가 어떤 결정을 통해 행동을 하지 않는다. 그저 전이 확률에 의해 상태가 전이 되며 ‘현재 상태에 종속된 보상값’을 받는다. 에이전트가 환경과 상호작용한다기 보다는, 환경에 의해 에이전트가 어떻게 영향을 받는지를 확인할 수 있다.

Markov Reward Proces을 정리하면 다음과 같다:

  • 마르코프 체인에서 보상이 추가된 모델
  • <S, P, R, 𝜸>로 구성됨 (R: Reward, 𝜸 : Discount factor)
  • 보상을 통해 각 상태의 가치를 수치화할 수 있다.

강화학습의 목표는 에이전트가 최대의 보상을 얻게하는 것이다.

앞서 보상이라는 것이 상태에 대한 가치를 수치화한 것이라고 했다. 이는 현재 상태에서 다음 상태로 전이될 때 얻게되는 ‘즉각보상값’을 의미한다.

강화학습에서는 에이전트가 시작 상태에서, 종료 상태까지 얻게되는 보상의 합을 최대화하는 것을 목표로 한다. ‘시작 상태에서, 종료 상태까지 얻게되는 보상의 합’을 리턴(Return)이라고 한다. 즉각보상값이 단기적인 보상이라면 리턴은 장기적인 보상이라고 할 수 있다.

상태에 대한 장기적인 가치를 수치화한 것을 상태가치값(State Value Function)이라고 한다.

상태가치값은 해당 상태에서 얻을 수 있는 리턴 기대값으로 표현된다.

이제 에이전트를 상태가치값이 높은 상태로 이동하게 하는 것이 강화학습의 목표가 된다. 그러기 위해서는 상태가치값을 계산해야하는데, 위 식을 보면 알 수 있듯이 종료 상태까지의 보상을 모두 계산해야만 해당 상태의 가치값을 계산할 수 있다. 이러한 계산 비효율을 해결하기 위해 제안된 것이 벨만 방정식이다.

벨만 방정식의 특징은 다음과 같다:

  • 가치값을 즉각적인 보상값과 다음 단계의 가치값으로 분할하여 계산
  • 상태가치값 또는 행동가치값들 간의 관계를 재귀적 방법으로 표시

이를 수식으로 표현하면 다음과 같다.

이제 이 식을 행렬식으로 표현하면 행렬 연산을 통해 상태가치값을 계산할 수 있다.

하지만, 위와 같이 계산하려면 모든 상태에 대한 보상값과 전이확률을 알고 있어야한다. 반면 보상값과 전이 확률을 모르는 상태를 강화학습에서는 ‘모델 프리’라고한다.

행렬 연산 외에도 반복적인 방법(Iterative method)를 통해서도 계산할 수 있다. 이에 대해서는 다른 포스트에서 정리한다.

Markov Decision Process

이제 MRP 모델보다 조금 더 복잡한 모델인 MDP에 대해서 설명한다.

Markov Decision Process는 다음과 같은 특징을 갖는다:

  • MRP에서 행동이 추가된 모델이다.
  • 에이전트가 행동을 결정하는 규칙을 정책이라고 한다.
  • <S, A, P, R, 𝜸> (A: Action)

확률 모델에서 MRP와 MDP의 차이:

  • MRP에서는 현재 상태에 의해 {상태 전이 확률, 보상}이 결정되지만,
  • MDP에서는 현재 상태에서 취할 행동에 의해 {상태 전이 확률, 보상}이 결정된다.

MDP에서는 행동이 추가되어, 행동에 대한 가치를 표현하는 행동가치값(Action Value Function)을 추가로 정의할 수 있다.

MDP 모델에서의 가치값을 계산하기 위해 먼저, MDP 모델을 보다 단순한 MRP 모델로 치환한다.

MDP 모델에서 정책 𝜋가 정해진 경우, 전이 확률과 보상값을 다음과 같이 표현할 수 있다.

위 식을 MRP의 상태가치값에 대입한다. MRP 모델에서 상태가치값을 다음과 같이 보상값과 다음 상태에 대한 가치값으로 표현했었다.

P, R을 대입하여 식을 정리하여 다음과 같이 가치값들을 표현할 수 있다.

v(s)에 대한 식을 q(s,a)에 대입하면, 행동가치값을 재귀적으로 표현할 수 있고,

q(s,a)에 대한 식을 v(s)에 대입하면, 상태가치값을 재귀적으로 표현할 수 있다.

이렇게 표현된 식은 MRP에서 본 것 처럼, 행렬식으로 표현하여 행렬연산을 통해 계산 가능하다.

Optimal Values and Optimal Policies

앞에서 정리한 상태가치값, 행동가치값을 통해 우리는 정책 𝜋에 대해서 평가할 수 있게 되었다.

다시 강화학습의 목표로 돌아오면, 우리의 목표는 가치값을 최대화할 수 있는 정책을 찾는 것이다. 이런 정책을 최적 정책(Optimal policy)라고 한다.

최적 정책은 상태가치값, 행동가치값을 최대화하는 행동만 선택하는 정책이다.

최적 정책은 다음과 같은 명제를 갖는다:

  • 최소한 한 개 이상의 결정적인 최적 정책이 존재한다.
  • 여러 개의 최적 정책이 존재하는 경우에도 이들의 최적 가치값들은 동일하다.
  • 최적 정책에 따라서 생성되는 상태가치값은 항상 최적 상태가치값과 같고, 행동가치값도 최적 행동가치값과 같게 된다. 

상태가치값을 이용하여 최적 정책을 구하기 위해서는 보상과, 전이 확률을 모두 알아야 한다. (위 벨만 기대 방정식 참조) 만약 그렇지 않은 모델 프리환경에서는 행동가치값을 통해 최적 정책을 구한다.

이를 표현식으로 정리하면 다음과 같다.

Pratially Observable Markov Decision Process

MDP에서는 에이전트가 환경을 정확히 알고 있다고 가정하지만 실제 문제에서는 대부분이 그렇지 못하다.

POMDP는 에이전트가 상태를 정확히 알지 못하고 관측값을 이용하여 상태를 추정하는 모델이다.


POMDP 참조를 위한 그림 [1]

POMDP에 대해서는 다음 포스트에서 다룰 예정이다.

정리

이 글에서는 강화학습의 기반을 이루는 마르코프 결정 프로세스(MDP)와 그 이전 단계인 마르코프 체인, 마르코프 보상 프로세스(MRP)를 학습하였다. 이러한 개념와 수학적 모델을 통해 최적의 결정을 도출하는 방법을 탐색하였다. 그 과정에서 벨만 방정식의 특징과 계산 방법을 알아봤다. 이 글에서는 행렬 연산만을 다뤘지만 향후에는 동적 프로그래밍 방법에 대해서도 다룰 예정이다.

참고

참고 도서

  1. 이창환. (2023). 심층강화학습. 도서출판 홍릉

참고 논문

[1] Lauri, M., Hsu, D., & Pajarinen, J. (2022). Partially observable markov decision processes in robotics: A survey. IEEE Transactions on Robotics, 39(1), 21-40.

Comments

Leave a comment