하쿠's 강화학습 :: [Ch. III] Finite Markov Decision Process

포스팅에 앞서 이 게시글은 Reference의 contents를 review하는 글임을 밝힌다.

 

 

 

「Finite Markov Decision Process 란?」

Finite Markov Decision Process(유한 마르코프 결정 과정)란, 말 뜻에서 알 수 있듯
유한한 환경내에서의 Markov Decision Process를 말한다.
MDP를 설명하기위해서 아래와 같은 절차를 밟아나가도록 하겠다.

 

Markov Process(이하 MP) → Markov Reward Process(이하 MRP) → Markov Decision Process(이하 MDP)

 

유한 마르코프 결정 과정은 고전적인 절차적 결정 문제의 정석이며, 강화학습 문제를 서술하는데 효과적이다.
또한, 즉각보상 뿐만 아니라 다음 상태와 지연보상에도 영향을 끼친다.

 

각 상태에서의 최적 판단을 찾는 Bandits 문제, 각 상태에서의 최적행동가치값(q_value)과 최적행동선택시의 다음 상태가치를 찾는 Markov Decision Process 등 이러한 상태 의존적 수치들은 강화학습이 지향하는 장기적인 측면에서의 우수성을 보이는 알고리즘이다.

 

강화학습에서 다루는 대부분의 문제가 이 Markov Decision Process 조건을 성립하지만, 그렇지 않은 경우도 더러 있다.
이는 추후 다른 포스트에서 다룰 예정이다.

 

그럼 지금부터 이러한 마르코프 결정 과정에 대해 알아보도록 한다.

 

 

 

 

「Markov Process」

Markov Process(마르코프 과정, MP)는 'Markov Property(마르코프 속성)을 충족시키는 확률적 과정'을 말한다.

 

Markov Property란,  확률론적 과정의 기억할 수 없는 속성 즉, '망각'의 속성이라고 보면 된다.
조건부 확률 분포가 이전 이벤트와 무관하게 현재 상태에만 의존하는 경우 마르코프 속성을 가지고 있다고 말한다.

 

따라서, MP를 해설하면 '현재 상태에만 의존하여 변화하는 확률적 과정'을 말한다(수식은 다음과 같다).

 

마르코프 속성을 나타내는 수식

 

 

State Transition Probability(상태변환확률)

MP에서 상태변화 시에 기준이 되는 확률을 State Transition Probability(상태변환확률)라고 한다.

 

상태변환확률

 

상태변환확률은 비결정적 환경에서 활용되는 확률인데, 다음 상태를 결정하는 확률 값이다.
이는 강화학습에서는 어떤 행동에 대한 결과를 확률로 나타낸 것이다.

 

예를 들어, 강화학습에서는 비결정적 환경의 예시로 'Frozen Lake(얼음 호수)'라는 예제가 있다.
빙판 위에서의 걸음은 의도한 방향과는 다르게 이동할 수가 있는데, 이렇게 어떤 결정의 의도와 다르게 예외의 결과가 나타날 수 있는 환경을 비결정적 환경이라고 한다.

 

 

 

 

「Markov Reward Process」

Markov Reward Process(마르코프 보상 과정, MRP)는 'Reward가 가미된 MP'이다.

 

MP가 확률적 변화과정을 거칠 때, 이에 보상을 가미해 각 변화에 보상값이 부여되는 과정을 말한다.
이렇게 보상을 수여함으로써 각 상태의 가치를 계산할 수 있게 된다.이는 차후 행동 결정의 기준값으로 활용한다.

 

파란색은 양의보상, 빨간색은 음의보상

 

 

Discounting Factor(할인율)

이전 포스트에서 할인율에 대해서 알아보았다.

단순히 미래보상을 할인하기 위해 쓰인다고 설명했었는데, 더 정확하게는 현재를 기준으로 미래 가치를 현재 가치로 환산할 때 사용하는 값이다.

또한 이렇게 현재의 보상값으로 환산한 결과 값이 앞서 보상의 종류에서 소개되었던 '지연보상'이다.

 

이러한 할인율과 지연보상이 등장하게 된 계기는 결국 지엽적 학습을 피하기 위함이다.
적절한 타이밍에 적절한 양(amount)을 수여함으로써 학습방향을 목표 쪽으로 유도해야 하기 때문이다.

 

이뿐만이 아니라, 이러한 할인율의 필요성은 Episode(에피소드)의 종결성에서도 찾아볼 수 있는데,
Episode는 종결 상태의 유무에 따라 1) 유한 에피소드와 2) 무한 에피소드로 나눌 수가 있다.

유한의 Step횟수를 가진 Episode의 반환값은 연산에 큰 무리가 없지만, 문제는 무한의 길이를 가진 Episode의 경우 반환값이 계속해서 무한히 커진다는 문제가 있다.

 

이때, 할인율을 적용하면 할인율 곱 축적에 의해 무한에 가까운 Step 뒤의 보상을 0으로 수렴시킬 수가 있게 된다.

 

연속적 과제(Continuous Task)에서의 반환값

 

 

Return(총보상=반환값)

보상을 최대화하겠다고 줄기차게 이야기하는데 정작 이 최대화를 어떻게 이끌어내야 할지 감이 안 올 수 있다.

이전 포스트에서 우리는 반환값이라는 개념에 대해 본 적이 있는데, 바로 이것이 이러한 최적화를 달성하기 위해 우리는 기준이 되는 수치이다. 지금부터 반환값에 대해 자세히 알아보도록 하겠다.

 

반환값이란, 한번의 Episode(에피소드)가 끝날 때까지의 모든 즉각보상을 총합한 값이다.

 

총보상

 

허나, 이런 식으로 계산한 보상들은 즉각보상과 미래보상의 구분이 없어 학습의 결과가 지엽적인 방향으로 흘러갈 가능성이 큰데, 앞서 우리는 이러한 지엽적 학습(Local Optimum)을 피하기 위해 보상에 할인율의 개념을 도입하여 미래의 즉각보상을 현재가치로 환산하는 법을 배웠고 이를 지연보상이라고 하였다.

 

이렇게 지연보상과 현재의 즉각보상을 총합하여 현재상태의 가치로 환산한 값을 Return(총보상=반환값)이라고 한다.
이는 향후 행동을 결정하는 기준인 정책을 강화할 때 활용하기도 한다(수식은 다음과 같다).

 

할인율을 반영한 총보상

 

총보상의 수식을 살펴보면 각 시점의 즉각보상들을 현재 시점을 기준으로 할인율을 적용해서 모두 합한 결과임을 알 수 있다.

 

 

 

 

「Markov Decision Process」

Markov Decision Process(마르코프 결정 과정, MDP)는 'Decision이 추가된 MRP'이다.

MRP가 확률적 변화과정에서 보상을 부여했다면, 이번에는 변화과정에 의사가 개입되어야 한다.
강화학습은 확률적 변화과정에서 최적화라는 목표를 가지고 보상을 최대화하기 위한 의사결정(Decision)을 해야 한다.

 

여기서의 의사결정이 바로, 행동(Action)이다. 아래의 그림을 함께 보자.

 

비결정적 환경에서의 상태-행동 쌍

 

초기 상태(좌상단 백색원)에서 어떠한 의사결정(중앙 흑색원)을 통해 확률(상태변환확률)에 기반하여 다음 상태(우측 백색원 혹은 하단 백색원)로 변화함을 알 수 있다.

MDP에서는 행동을 통해 상태가 변화하기 때문에 이러한 그림으로 상태-행동 쌍을 나타낼 수 있다.
이러한 행동은 이전 포스트에서 다뤘던 Policy(정책)을 통해서 결정하게 된다.

 

 

Agent(학습자)와 Environment(환경)의 인터페이스

앞으로의 모든 Agent(학습자) 내부에 존재하여 Agent가 조정 가능한 변수를 Agent 변수라고할 것이다.
반대로 Agent(학습자) 외부에 존재하며, Agent가 조정 불가한 변수를 환경변수라고할 것이다.

 

갑작스레 이러한 설명을 하는 이유는 한 가지 개념적 오해를 방지하기 위한 부가설명을 하기 위해서이다.

앞서 State Transition Probability(상태변환확률)와 Policy(정책)에 대한 개념들을 살펴보아왔다. 이는 혼동을 불러일으킬 여지가 있는데, State Transition Probability(상태변환확률)은 행동의 결과를 결정하는 확률 값이고 이는 환경변수이다.  즉, Agent(학습자)가 조정할 수 없는 변수이다.

반면, Policy(정책)은 행동을 결정하는 확률 값이고 이는 Agent(학습자)가 학습을 거듭하여 최적화라는 목표를 두고 갱신해나가는 조정 가능한 변수이다. 이는 환경변수가 아니다.

 

 

결론

돌아와서 앞선 결과들을 종합해보면, MDP는 '어떠한 상태에서 다음 상태로 가기 위해 보상 최대화라는 목표를 고려하여 행동을 선택해나가는 과정'이라고 정리할 수 있다.

 

 

 

 

「정책과 가치함수」

이전 포스트에서 Value Function의 두 종류인 State Value Function(상태가치함수)과 Action Value Function(행동가치함수)를 잠시 소개한 바 있었다.

 

좀 더 면밀히 각 Value Function을 설명하자면,
State Value Function(상태가치함수)는 해당 상태가 얼마나 목표 달성하기 좋은지에 대한 함숫값이다.

 

상태가치 값

 

상태가치 값 = State(상태)에서의 Return(총보상=반환값)의 기댓값을 말한다.

 

Action Value Function(행동가치함수)는 해당 행동이 얼마나 목표 달성하기 좋은지에 대한 함숫값이다.

 

행동가치 값

 

행동가치 값 = State-Action(상태-행동)의 Return(총보상=반환값)의 기댓값을 말한다.

 

이후, 이러한 가치함숫값들을 통해 구성한 정책은 '상태당 선택 가능한 행동의 가치 값에 가중치를 두어 확률을 구성한 것'이라고 정리할 수 있다.

 

 

MonteCarlo Method(몬테카를로 방법)

이러한 가치함수들을 구성할 때, Agent는 경험에 기반하여 가치함수를 구하게 된다.

이 과정은 다음과 같은데, Episode가 시작되면 그때마다 정책에 따른 행동을 선택하고 이에 대한 보상을 받는다.
이후 여러 Episode를 거치면서 각 State에서의 평균적인 보상값이 계산 가능해지는데,

 

이것이 곧 State value function(상태가치함수 : V-value = V(s))이다. 이는 경험한 Episode 수가 많아질수록 더욱 정확한 값이 된다.

 

또한, 각 상태가치함숫값을 분리하여 각 행동단위의 가치값으로 생각하면 이것은 해당 상태에서의 각각의 Action value function(행동가치함수 : q-value = q(s))이 되는데, 이 역시 경험한 Episode 수가 많아질수록 더욱 정확한 값이 된다.

 

이렇게 경험에 근거하여 평균치의 값을 기준으로 계산하는 방식을  'MonteCarlo(몬테카를로) 알고리즘'이라고 한다
(이후 포스트에서 더 자세히 다룰 예정이다).

 

 

Bellman Expected Equation(벨만기대방정식)

벨만기대방정식은 현재상태와 다음상태간의 관계를 나타내는 방정식이다

 

벨만기대방정식

 

수식을 천천히 뜯어보면, 현재상태의 가치식은 다음과 같이 구할 수 있다.

 

1. 어떤 행동을 통해 얻어진 즉각보상 + 지연보상(= 할인율 × 다음상태가치값)을 계산함으로써,
   현재 행동의 결과에 대한 가치함숫값을 구할 수 있다.
2. 이러한 행동의 결과에 따르는 가치함숫값은 비결정적 환경에서는 확률적 결과를 표출하기 때문에,
   발생 가능한 모든 결과들의 가치함숫값을 모두 더한다( p(s`,r | s, a)[~] ).

 

행동 a에 대한 2가지 결과(불확실한 환경)

 

3. 여기까지 왔다면, 어떠한 행동을 했을 때의 결과에 대한 가치함숫값을 구한 것이다.
   이후에는 정책에서 정의하는 각 행동에 대한 가중치를 부여하여 각각의 행동의 행동가치함숫값을 구해야 한다.
4. 마지막으로 이 각각의 행동가치함숫값을 합산해 평균을 내게되면 해당 상태에서의 상태가치함숫값을 구할 수 있다.

 

 

 

 

「최적 정책과 최적가치 함수」

Bellman Optimality Equation(벨만최적방정식)

위에서 우리는 상태가치함숫값과 행동가치함숫값을 구할 수 있게 해주는 벨만기대방정식에 대해 알아보았다.

하지만, 우리의 목표는 '최적화'이다.
따라서, 가장 큰 상태가치함숫값(최적상태가치함수)과 가장 큰 행동가치함숫값(최적행동가치함수)을 찾아야 한다.

 

최적상태가치함수

최적행동가치함수

 

 

이 둘은 결국에는 같은 것인데,
최적의 정책 아래에 존재하는 상태가치함숫값은 결국 최적의 행동만을 선택했을 때의 행동가치함숫값과 같기 때문이다
(아래 두 수식의 마지막 줄은 동일하다).

 

최적상태가치함수

최적행동가치함수

 

 

이것을 벨만최적방정식이라고 한다.
이를 활용하여, 최적의 상태가치함수와 최적의 행동가치함수를 찾으면 최적의 정책을 찾을 수 있다.

 

 

 

 

「최적화와 근사화」

우리가 환경의 모든 정보를 다 알고 있다고 가정했을 때, 최적화를 위해 모든 상태에 대한 가치 값을 '표'로 정리하여 메모리에 저장해두었다가 사용하는 방식을 Tabular Solution(테이블 방식의 해결책)이라고 한다.

 

그러나 이것은 이상적인 해결 방식일 뿐, 현실에서는 적용에 다소 무리가 있다.

 

이것이 불가능한 이유 중 하나는 메모리 사용량인데, 우리는 이러한 연산과정을 보다 현실적으로 가능한 수준에서 진행하기 위해 'Approximation(근사화)'를 통해 최적화에 근접한 답을 도출한다.

 

이것을 우리는 Approximate Soluion(근사화 방식의 해결책)이라고 한다.

이러한 Approximation에 대해서는 이후 포스트에서 알아볼 예정이다.
다만, 향후 자주 등장할 유용한 개념이니 눈에 담아두도록 하자.

 

 

 

 

「마무리」

강화학습은 목표를 성취하기 위한 상호작용을 배우는 것이다.

 

Environment와 Agent는 이산 시간의 흐름에서 학습을 진행(MDP)한다.

 

Agent의 선택 : Action
선택에 대한 상태 : State(Next state)
선택에 대한 평가 : Reward로 정리할 수 있다.

 

Agent의 내부 변수는 Agent가 제어 가능하고,
Agent의 외부 변수는 Agent가 제어 불가능하다는 점도 알아보았다.

 

Policy은 가치함수를 활용한 행동선택에서의 확률적 규칙이고, 목표는 보상 최대화이다.

 

또한, Return은 Agent가 최대화하려는 총보상함수이다.
우리는 Value Function를 활용하여 Return을 계산해냈고, 이 과정에서 Discounting Factor를 활용했다.

 

이러한 Value Function을 구할 때, 활용하는 방정식을 Bellman Expectation Equation이라고 하고,
최적의 Value Function을 구할 때, 활용하는 방정식을 Bellman Optimality Equation이라고 한다.

 

강화학습 문제는 Agent가 가용 가능한 초기 정보의 양에 따라 해결책을 다양하게 가져갈 수 있다.
그렇지만, 실질적으로 구현에 다양한 제약이 있어 우리는 근사화한 연산 값을 활용할 수밖에 없다.

 

 

 

 

「참고」

Reinforcement Learning, Second Edition : An Introduction
Richard S. Sutton and Andrew G. Barto

https://mitpress.mit.edu/books/reinforcement-learning-second-edition

Reinforcement Learning, Second Edition