단단한 강화학습 Chapter3_(1) _유한 마르코프 결정 과정(Finite Markov DecisionProcesses)

Chapter 2에서 다룬 다중선택 문제는

비연합구조의 문제 (State-> Action -> Reward가 한번의 학습이 이루어지는 상황)의 상황이었습니다.

https://roboharco12.tistory.com/54?category=1064282 

단단한 강화학습 Chapter2_(1) _다중선택(Multi-armed Bandits)

https://roboharco12.tistory.com/55

단단한 강화학습 Chapter2_(2) _다중선택(Multi-armed Bandits)

Chapter 3부터 다룰 문제는 연합구조(여러번의 State-> Action -> Reward -> ...의 학습이 이루어지는 상황)이고, 다중 선택 문제와 마찬가지로 평가적인 피드백을 포함하는 상황에서의 문제해결을 다룹니다.

 

그리고 이 문제를 풀기위한 솔루션이 바로 그 유명한 MDP(Marcov Decision Process)입니다.

 

연속된 의사 결정의 고전적 형식인 MDP에서는

현재의 행동이 즉각적인 보상에만 영향을 미치는 것이 아니고, 이어지는 상황이나 상태에 영향을 미쳐서 결국 미래의 보상에도 영향을 주게됩니다.

 

따라서 MDP에서는 지연된 보상의 기대값을 포함하며,

즉각적인 보상과 지연된 기대값 사이의 균형을 잡아줄 필요가 생기게됩니다.

 

 다중 선택 문제에서는,

각 행동 a에 대해서 q*(a)를 추정하도록 계산이 진행되지만,

 MDP에서는,

각 상태 s에 있는 각 행동 a에 대한 q*(a)를 추정하거나,

최적의 행동선택을 가정한 채로 각 상태의 가치 v*(s)를 추정합니다.

 

 

MDP는 강화학습 문제를 이론적으로 정교하게 설명할 수 있도록 해주는 이상적인 수학적 형태입니다.

이번 Chapter3에서는 이득 (Return), 가치함수 (Value Function),  벨만 방정식 (Bellman Equation)같은 이 문제의 수학적 구조를 이루는 핵심 요소들을 설명합니다.

 

 

 

◆목차

◎ 에이전트-환경 인터페이스 (The Agent-Environment Interface) : MDP

◎ 목표와 보상 (Goals and Rewards) , 보상과 에피소드 (Returns and Episodes)

 

 

 

 

 

 

 

◎ 에이전트-환경 인터페이스 (The Agent-Environment Interface) : MDP

- Agent ~ Environment Interface

MDP는 기본적으로 최적의 Policy를 찾기 위해

주변 환경과 상호작용으로부터 학습하는 문제의 간단한 틀(frame)로 고안되었습니다. 

 

강화학습에서는 학습자와 의사 결정자를 에이전트(Agent)라고 부르며,

에이전트와 상호작용하는 에이전트 이외에 모든 것을 환경(Environment)라고 합니다.

그리고 Agent와 Environment는 지속적으로 상호작용하게됩니다.

 

Agent는 Action을 선택하고, 

Environment는 그 Action에 반응하여 Reward를 주고, Agent에게 새로운 상황(State)을 제시합니다.

모든시간단계 t에서, Agent는 Environment의 상태(St)를 나타내는 어떤 것을 받고,

그것을 기반으로 Action(At)를 선택합니다.

 

다음 시간 단계 t+1에서,

부분적으로는 이전 행동의 결과로서 Agent는 숫자로된 Reward(Rt+1)를 받고,

스스로가 새로운 상태(St+1)에 있다고 인식합니다.

 

즉, Agent는 다음과같은 Trajectory를 그리며 Environment와 상호작용하게됩니다.

 

이름에서 유추할 수 있듯, 유한(Finite) MDP 에서는 

상태(S), 행동(A), 보상(R)의 집합은 항상 유한한 값의 숫자원소를 가지고 있습니다.

 

이 경우,

확률변수 Rt와 St는 오로지 이전의 State (St-1)와 Action(At-1)에만 의존하는 잘 정의된 이산확률분포를 갖습니다.

(이전 시간단계에만 의존한다는 것을 기억해둡시다.

 

책에 정리된 Notation으로 이를 표현하면 

s`은 s의 다음 시간단계의 State이며,

함수 p는 MDP의 Dynamics를 정의하는 4개의 변수(s`,r,s,a)를 가진 함수입니다.

 

다시말하면,

"시각 t-1에서의 State에서 해당 Action을 취할때, 시각 t에서의 State와 Reward가 발생할 조건부 확률"

이 됩니다.

 

 

** 말이 좀 어려워서 다시 정리해보겠습니다.

> 어떤 특정 state s에서, 어떠한 행동 a를 취했을때 도달할 수 있는 다른 state중 하나를 s`라 할때,

Reward역시 어떤 특정한 state에서 확률 분포에의해 주어진다고 하면,

s에서 a라는 action을 취했을때(조건),  s`이라는 state에서 r이라는 reward를 받게 될 획률?

을 수학적 기호로 표현하면

p{s`,r | s,a} 가 되는 것입니다.

 

 

s라는 state에서 a라는 action을 취했을시, 

이때 도달할 수 있는 모든 state s`과 받을 수 있는 모든 reward에 합은 

s,a에대한 s`,r 조건부확률의 총합이 되므로,

이는 1이됩니다.

 

 

 

 

 

- MDP(Marcov Decision Process)와 마르코프 특성(Marcov Property)

MDP에서 확률 과정은 마르코프 특성을 따릅니다.

일반적인 확률과정과 다른, Marcov Process(Marcov Property를 갖는 확률과정)의 특성은,

St와 Rt가 어떤 값을 가질 확률은, 바로 이전 시간단계의 상태와 행동인 St-1, Rt-1에만 의존한다는 것입니다.

 

과거의 모든 Agent - Environment간 상호작용에 대한 정보가 바로 직전 State에 담겨있다는 전제하에 진행되는 과정으로,

책의 저자에 해석에 따르면 이는 결정과정에 대한 제약이 아니라 상태에 대한 제약으로 바라보는 것이 적합하다고 합니다.

 

 

아래에 블로그에 마르코프 특성에대해 자세히 잘 정리되어 있습니다.

https://sumniya.tistory.com/3

[Ch.2] Markov Decision Process

 

네개의 변수를 갖는 함수 p로부터,

모든 환경에대한 정보를 아래와같이 간단하게 계산할 수 있습니다.

 

- 상태 전이 확률, State Transition Probablity  (s`, s, a)

- '상태→행동' 쌍에대한 보상의 기대값 (s, a)

- '상태→행동→다음상태' 에대한 보상의 기대값 (s, a, s`)

 

＊r은 보상의 기대값, p는 확률

 

 

 

 

 

<MDP에 대한 추가적인 설명>(참고)

-  Timestep / Action / State

MDP 구조는 추상적이고 유동적이어서, 많은 문제에 다양한 방식으로 적용할 수 있습니다.

 

가령, 시간간격이 꼭 Discrete한 고정된 간격을 나타내지 않고 임의의 연속적인 의사결정과 행동의 단계일 수도 있고, 상태와 행동역시 다양한 형태일 수 있습니다.

 

 상태의 경우, 직접 센서값을 읽는 것과 같은 낮은 수준의 감각으로 완벽히 결정 가능한 것일수도있고,

방안의 물건에 대한 상징적 묘사와 같이 수준이 높고 추상적인것일 수도 있습니다.

상태를 구성하는 무언가는 과거의 감각에 기반한 것일 수도 있고, 전적으로 정신적이고 주관적인 것일 수도 있습니다.

예를들면, 에이전트는 물건이 어디에 있는지 확실하지 않은 상태일 수도 있고, 분명히 정의된 감각을 통해 물건의 위치를 확인한 후 지금 막 놀란 상태일 수도 있습니다.

 

 유사하게, 행동 역시 전적으로 정신적이거나, 계산적인 수치일 수 있습니다.

예를 들면 어떤 행동은 에이전트가 생각하고자 하는 것이 무엇인지를 제어할 수도 있고,

에이전트가 초점을 어디에 두고있는지도 제어할 수도 있습니다.

 

일반적으로, 행동(Action)은 결정하는 방법을 알고자 하는 모든 결정이 될 수 있고,

상태(State)는 그 결정을 내리는데 있어서 유용하다고 알려진 모든것이 될 수 있습니다.

 

- Agent / Environment 

에이전트와 환경사이 경계는 보통 로봇이나 동물 몸체의 물리적 경계와는 의미가 다릅니다.

대개는 몸체의 물리적 경계보다는 에이전트 쪽에 더 가깝게 그어지는데,

예를들어 로봇의 모터와 기계적 접합부, 측정 센서들은 에이전트의 일부라기보다는 환경의 일부로 간주됩니다.

이에대한 일반적인 규칙은, 에이전트에 의해 임의로 변경될 수 없는 모든 것은 에이전트 밖에 있다고 간주하는 것입니다.

 

 목적에 따라서 Agent ~ Environment간 경계를 다른 위치에 둘 수 있는데,

예를들어 복잡한 로봇의 경우 많은 다양한 에이전트가 자신만의 경계를 가지고 동시에 작동할 수도 있습니다.

한 에이전트가 높은 수준의 결정을 하여 State의 일부를 형성하고, 그 State에 놓이게된 낮은 수준의 결정을 하는 Agent가 이미 행해진 높은 수준의 결정통해 MDP를 풀 수도 있습니다.

 

▷정리하면,

 

MDP 구조는 목표 지향적인 Agent ~ Environment 상호작용 으로부터의 학습문제를 상당히 추상화 한것입니다.

MDP 구조에서는 그 세부내용이 어떻건간에, 

Agent와 Environment 간 상호작용을 Action  /  State  /  Reward  세가지의 신호로 축약해서 나타낼 수 있게되고,

이 구조가 모든 의사결정 학습문제를 효과적으로 표현하는데 충분하지 않을 수는 있으나, 폭넓은 문제에 유용하게 적용 가능하다는 사실이 입증되었습니다.

 

 

◎ 목표와 보상 (Goals and Rewards) , 보상과 에피소드 (Returns and Episodes)

- Agent의 궁극적인 목표

강화학습에서 Agent의 궁극적인 목표는 바로 '보상'신호를 최대화하는 것입니다.

 

보상을 신호로 형식화하여 이를 최대화 하는 것이라는 아이디어가 한계점이 많아보일 수 있으나,

이런 형식화가 많은 분야에서 유용하고 폭넓게 사용될 수 있다는 사실이 입증되었습니다.

이에대한 예시는 아래와 같습니다.

 

º 로봇이 걸음을 학습하도록 하기위해 연구자들은 매 Time step마다 로봇이 앞으로 가는 움직임에 비례하여 보상을 제공함

º 로봇이 미로를 탈출하는 방법을 학습하도록 할 경우, 로봇이 출구를 앞에두고 지나칠 때마다 종종 -1의 보상을 부여함

º 재활용을 위해 로봇이 빈 소다캔을 찾아서 수집하도록 학습시키려면, 대부분의 시간에는 0이라는 보상을 주고, 캔이 하나 수집될때마다 +1의 보상

 

 

- Episodic Task  /  Continous Task

강화학습이 다루는 Task는 크게 Episodic Task와 Continous Task로 나뉘는데,

Episodic Task란 상호작용에서 끝이 존재하는 상황, '종료'에 대한 State가 존재하는 Task를 의미하며,

미로찾기나, 승패에따라 종료되는 모든종류의 게임이 이에 해당합니다.

 

이와 반대로 Continous Task란 상호작용의 끝이 존재하지 않는 상황을 의미하는데,

가장 대표적인 예시로 주식 투자 인공지능 Agent가 여기에 해당합니다.

 

* 강화학습에서 Episode란 시간단계와는 다른것으로,

Episodic Tasks에서 시작부터 끝까지 한번의 과정을 Episode라고 표현합니다.

 

- Reward에 대한 정리

 보상에 대해 구체적으로 다시 한번 더 다뤄보도록 합시다.

Agent의 궁극적인 목표는 "'보상'신호를 최대화하는 것"이라고 했는데,

이를 달리표현하면 '보상의 총합을 최대화 하는 행동을 선택하는 것'

즉,

t시간 이후에 받는 연속된 보상값을

위와같이 정의했을때, Gt값이 최대가 되는 행동을 선택하도록 하는것이 Agent의 궁극적인 목표가 됩니다.

 

다만, 위와같이 Gt를 정의해버린다면, 종단상태가 존재하는 Episodic Tasks에서만 

Gt를 정의할 수 있게되는 치명적인 문제가 발생하게 됩니다.

 

그렇기 때문에, 시간에 따른 가중치를 부여하는 Discounting Factor (γ) 개념을 도입해서 아래와같이 Gt를 정의해주어야 합니다.

이렇게 할 경우, Episodic Tasks와 Continous Tasks 모든 경우에서 Gt를 정의할 수 있게됩니다.

 

Discounting Factor은 현재 시각 t에서 미래의 보상에 대한 가치들을 결정하는데, 

k시간 만큼 앞선 미래의 보상을 지금 당장 받는다고 하면, 미래 보상의 γ^(k-1)배만큼의 보상을 받게됩니다.

γ값이 작을 수록 Agent는 더 근시안적으로, 미래보다 현재 당장의 보상을 최대화하는 방향으로 학습됩니다.

 

 

이를 아래와같이 한번더 단순화해서 정리할 수 있습니다.

 

- Episodic / Continuing 작업의 통합 표기법(Unified Notation for Episodic and Continuing Tasks)

지금까지 두가지 종류의 강화학습 Task를 설명했는데,

한가지는 종단상태가 정해진 Episodic Tasks, 다른 한가지는 끝이 존재하지 않는 Episodic Tasks입니다.

 

책에서는 두가지 문제를 한번에 다루기도 해서 이를 통합해서 표기하는 것으로 정리했는데요,

다음과같은 과정을통해 하나로 통합했습니다.

 

º Continous Tasks와 다르게, Episodic Tasks는 Agent-Environment간 상호작용이 Discrete하게 각각의 Episode로 분리되어 존재하므로,

원래대로라면 하나의 긴 시간단계의 나열로 표현하는게 아니라 에피소드별로 구분해서 표현할 필요가 있다.

-> Episide i의 시각 t에서의

상태,행동, 확률,종단시각 등 에이전트와 환경사이 표현되는 신호를 아래와같이 표기해야함

º 단, 책에서는 거의 항상 특별한 하나의 에피소드를 고려하거나 모든 에피소드에 적용되는 무언가를 언급하기에,

에피소드를 표현하기위한 무언가는 거의항상 누락하여 표현할 것임.

-> Episodic Tasks라도 단순히 St, At등으로 표현

º Episodic Tasks는 유한개의 Trajectories를 가지고, Continous Tasks는 무한개의 Trajectories를 가지므로, 두개를 통합하기위한 무언가가 필요함.

위의 그림처럼, Episodic Tasks에서 종단상태를

Reward를 0으로 발생시키면서 자기자신으로 무한히 회귀하는 일종의 'Absorbing State'로 정의하면 해결가능.

 

 

 

 

즉,

책에서는 아래와 같이 표기를 통합해서 사용합니다.

 

 

 

다음 포스팅에서 이어집니다.