[Deep Reinforcement Learning Hands On] Chapter.01

Chapter 1. What is Reinforcement Learning?

 💡 Reinforcement Learning (RL) : an approach that natively incorporates extra dimension (which is usually time, but not necessarily) into learning equations

강화학습 : 어떤 환경 안에서 정의된 에이전트가 현재의 상태를 인식하여, 선택 가능한 행동들 중 보상을 최대화하는 행동 혹은 행동 순서를 선택하는 방법을 통해 학습

 

Learning - supervised, unsupervised, and reinforcement

지도, 비지도 학습과 비교를 통해 강화 학습의 특징을 정의

1. supervised learning 지도 학습

• main objective : we have many examples of the input and desired output, and we want to learn how to generate the output for some future, currently unseen inputs
• ex) text classification, image classification, regression problems etc
• 2. unsupervised learning 비지도 학습

• main objective : to learn some hidden structure of the dataset at hand
• assumes no supervision that has no known labels assigned to our data
• ex) clustering, GANs

1. reinforcement learing 강화학습

• lays somewhere in between full supervision and a complete lack of predefined labels
• uses many well- established methods of supervised learning, but in a different way

 📝 강화학습은 머신러닝의 한 영역으로, 지도학습의 방법론을 이용하면서 비지도학습처럼 라벨링을 필요로 하지 않는 독특한 학습법이다.

Figure 1 : Robot mouse maze world

1. environemnt : a maze with food at some points and electricity at others
2. robot mouse : can take actions such as turn left/right and move forward
3. can observe the full state of the maze to make a decision about the actions
4. trying to find as much food as possible, while avoiding an electric shock whenever possible

final goal of the agent is to get as much total reward as possible

• RL doesn’t work with predefined labels, so there’s no label for good or bad or the best direction
• three state in reward system : positive, negative, neutral
• what makes RL tricky?
  1. having non-i.i.d data (i.i.d : independent and identically distributed) 각각의 랜덤 변수들이 동일한 확률분포를 가지지 않음 sqential 시계열성이 중요
     1. observation in RL depends on an agent's behavior and to some extent, it is the result of their behavior
     2. the observations tell nothing about the action of your agent even it decides to do inefficient things
     3. if the agent is stubborn and keeps making mistakes, the observations can make the false impression, which is totally wrong
  2. exploration/exploitation dilemma 이용과 탐험 사이의 균형
     1. your agent needs to not only exploit the policy they have learned, but to actively explore the environment
     2. by doing things differently we can significantly improve the outcome we get but, too much exploration may also seriously decrease the reward
     3. need to find a balance between these two activities
  3. reward can be seriously delayed from actions 행동에 대한 피드백이 즉각적이지 않고 지연 가능
     1. we need to discover such casualties, which can be tricky to do over the flow of time and our actions

 

RL formalisms and relations

- Figure 2 : RL entities and their communications

 

• Reward 보상
  • a scalar value we obtain periodically from the environment
  • purpose : to tell our agent how well they have behaved
  • don't define how frequently the agent receives this reward
  • local - reflects the success of the agent's recent activity
  • reinforce agent’s behavior in a positive or negative way - agent’s goal is to achieve the largest accumulated reward over its sequence of actions
• The agent 에이전트
  • somebody or something who/which interacts with the environment by executing certain actions, taking observations, and receiving eventual rewards for this
  • supposed to solve some problem in a more-or-less efficient way
• The environment 환경
  • everything outside of an agent
  • agent’s communication with the environment is limited by rewards, actions and observations
• Actions 행동
  • things that an agent can do in the environment
  • two types of actions - discrete or continuous
• Observations 관찰
  • pieces of information the the environment provides the agent
  • may be relevant to the upcoming reward or not, even include reward information

 

Markov decision processes

Markov process 파트에서는 RL(Reinforcement Learning) 문제를 해결하는 데 사용되는 방법으로 이동을 가능하게 하는 RL의 이론적 토대를 익힐 것

 

먼저 방금 논의한 formalisms(reward, agent, actions, observations, and environment)의 수학적 표현과 개념을 소개하고,  이것을 기초로 하여 우리는 state, episode, history, value, gain을 포함한 RL언어의 2차적 개념을 소개하는데, 이는 책의 후반부에서 다른 방법을 설명하는데 반복적으로 사용됨. 그리고 Markov decision process에 대한 우리의 설명은 러시아 마트료시카 인형과 같음

 

<러시아 마트료시카 인형>

우리는 Markov Process(MP : Markov chain)의 가장 단순한 사례에서 시작하여 rewards로 확장하여 Markov reward processes로 전환

 

그런 다음 actions을 추가하여 이 아이디어를 다른 봉투에 넣음으로써 Markov Decision Processes(MDPs)로 이어질 것

 

 Markov processes와 Markov decision processes는 computer science와 다른 공학분야에서 널리 사용됨

 

 

 

Markov process

Markov process는 Markov chain이라고도 알려져 있음

 

당신 앞에 오직 여러분이 관찰할 수 있는 어떤 시스템이 있다고 상상해보고, 여러분이 관찰하는 것을 states라고 하며, 시스템은 역학 법칙에 따라 전환할 수 있다고 함.

 

이때 당신은 시스템에 영향을 줄 수 없고 오직 상태가 변화하는 것을 지켜볼 뿐이며, 시스템에 대한 가능한 모든 상태는 state space라는 집합을 형성하는데 Markov processes에서 우리는 이 상태 집합이 유한해야 한다고 가정(그러나 매우 클 수 있음)

 

관측치는 일련의 states 또는 체인을 형성(이 때문에 Markov processes를 Markov chains라고도 함)

 

예를 들어, 어떤 도시의 가장 간단한 날씨 모델을 보면, 우리는 주 공간인 현재 날을 맑거나 비가 오는 것으로 관찰할 수 있음

 

시간에 따른 일련의 관측은 [sunny, sunny, rainy, sunny, ...]와 같은 일련의 체인을 형성하며 이것을 history라고 부름

 

이러한 시스템을 Markov Process라 부르기 위해서는 Markov property를 충족해야 하는데, 이는 어떤 상태에서도 미래의 시스템 역학은 이 상태에만 의존해야 한다는 것을 의미

 

Markov property의 요점은 시스템의 미래를 설명하기 위해 관측 가능한 모든 상태를 스스로 포함시키는 것

 

다시 말해, Markov property는 시스템 상태가 서로 구별될 수 있고 고유해야하며, 시스템의 미래 역학을 모델링하는 데 하나의 상태만 필요하며 전체 history는 아니어야 함

 

우리의 날씨 예제의 경우, Markov property는 우리가 과거에 봤던 맑은 날의 양에 상관없이 같은 확률로 맑은 날이 비가 오는 날 뒤에 올 수 있는 경우에만 모델을 나타내도록 제한함

 

상식적으로 내일 비가 올 가능성은 현재 상태뿐만 아니라 계절, 위도, 그리고 근처의 산과 바다의 존재와 같은 많은 요소들에 달려있다는 것을 알고 있기 때문에 그다지 현실적인 모델은 아님

 

태양 활동조차도 날씨에 큰 영향을 미친다는 것이 최근에 증명되었고, 따라서 우리의 예는 정말 순진하지만 한계를 이해하고 그것에 대한 의식적인 결정을 내린다는 것이 중요함

 

물론, 모델을 더 복잡하게 만들고 싶다면, 우리는 항상 state space를 확장할 수 있고 이것은 우리가 더 많은 의존성을 포착할 수 있게 할 것

 

예를 들어, 여름과 겨울 동안 비가 올 확률을 별도로 확보하려면 해당 계절을 상태에 포함할 수 있음

 

이 경우의 state space는 [sunny+summer, sunny+winter, rainy+summer, rainy+winter]이 됨

 

시스템 모델이 Markov property를 준수하므로 NxN 크기의 제곱행렬인 transition matrix를 사용하여 확률을 확보할 수 있음

 

여기서 N은 모델의 상태 수를 의미하고 행렬의 행 i와 열 j에 있는 모든 셀은 시스템이 상태 i에서 상태 j로 전환된 확률을 포함

 

예를 들어, sunny/rainy가 오는 예시에서 전이 행렬은 다음과 같을 수 있음

 

	sunny	rainy
sunny	80%	20%
rainy	10%	90%

이 경우, 맑은 날이 있다면, 다음 날이 맑을 확률은 80%이고, 다음 날이 비가 올 확률은 20%이고 만약 우리가 비가 오는 날을 관찰한다면, 날씨가 좋아질 확률은 10%이고, 다음날 비가 올 확률은 90% 임

 

Markov process의 공식적 정의는 다음과 같음

• 시스템이 있을 수 있는 상태 집합(S)
• 시스템 역학을 정의하는 전이 확률과 전이 행렬(T)

MP의 유용한 시각적 표현은 시스템 상태와 가장자리에 해당하는 노드가 있는 그래프이며, 상태에서 상태로의 가능한 전환을 나타내는 확률로 레이블이 지정됨

 

전이 확률이 0이면 가장자리를 그리지 않고(한 상태에서 다른 상태로 이동하는 방법은 없음) 이러한 종류의 표현은 automata theory에서 연구되는 finite state machine에서도 널리 사용됨

 

sunny/rainy 날씨 모델의 경우 그래프는 다음과 같음

<Sunny/Rainy weather model>

 

더 복잡한 예를 들어보면, 직장인의 또 다른 모델(Scott Adams의 유명한 만화에 나오는 주인공 Dilbert가 좋은 예)을 소개해봄

 

이 예시에서 state space는 다음과 같음

• Home : 사무실에 없음
• Computer : 사무실에서 컴퓨터로 일하고 있음
• Coffee : 사무실에서 커피를 마시고 있음
• Chatting : 사무실에서 동료들과 무언가를 의논하고 있음

상태 전환 그래프는 다음과 같음

<State transition graph>

우리는 그의 근무일이 보통 Home에서 시작되며 예외 없이 항상 Coffee와 함께 근무를 시작하길 기대함(no Home → Computer edge and no Home → Chatting edge)

 

위 다이어그램은 또한 근무일이 항상 컴퓨터 상태에서 종료됨을 나타내고 이전 다이어그램의 전이 행렬은 다음과 같음

	Home	Coffee	Chat	Computer
Home	60%	40%	0%	0%
Coffee	0%	10%	70%	20%
Chat	0%	20%	50%	30%
Computer	20%	20%	10%	50%

 

전환 확률은 다음과 같이 상태 전이 그래프에 직접 배치할 수 있음

<State transition graph with transition probabilities>

실제로, 우리는 정확한 전이 행렬을 아는 것은 거의 불가능함

 

훨씬 더 실제적인 상황은 시스템 상태에 대한 관찰만 있을 때이며, 이를 episode라고 함

• home -> coffee -> coffee -> chat -> chat -> coffee -> computer -> computer -> home
• computer ->  computer -> chat -> chat -> coffee -> computer -> computer -> computer
• home -> home -> coffee -> chat -> computer -> coffee -> coffee

우리의 관찰에 의해 전이 행렬을 추정하는 것은 복잡하지 않음; 우리는 단지 모든 상태에서 모든 전이를 세고 그것들을 1의 합으로 정규화하면 됨

관측 데이터가 많을수록 추정치는 실제 기본 모형에 더 가까울 것

또한 Markov property는 stationarity(즉, 모든 상태에 대한 기본 전이 분포는 시간이 지남에 따라 변하지 않음)을 의미한다는 점에 주목할 필요가 있음

 

Nonstationarity는 우리의 시스템 역학에 영향을 미치는 숨겨진 요인이 있다는 것을 의미하며, 이 요인은 관찰에 포함되지 않음

 

그러나 이는 전이 이력에 관계없이 동일한 상태에 대해 기본 확률 분포가 동일해야 하는 Markov property와 모순됨

 

한 에피소드에서 관찰된 실제 전이와 전이 행렬에서 주어진 기본 분포 사이의 차이를 이해하는 것이 중요

 

우리가 관찰하는 구체적인 에피소드는 모델의 분포에서 무작위로 샘플링되므로 에피소드마다 다를 수 있으나 표본이 추출될 구체적인 전이 확률은 동일하게 유지, 그렇지 않으면 Markov chain formalism은 적용되지 않음

이제 더 나아가 Markov process 모델을 확장하여 RL 문제에 더 가깝게 만들 수 있음 :)

 

Markov reward process (MRP; 강화학습을 표현하기 위한 확률 모델)

• 의사결정 과정을 확률과 그래프를 이용하여 모델링한 것으로, 기존의 MP에 R 과 감마(Discount factor; 할인요소)가 추가된 모델이다.

-MP란 Markov Process의 줄임말로 MP(아래 MP)가 전제된 상황(다음 상태는 현재상태에만 의존하며, 확률적으로 변하는 경우)의 상태 변화

cf.MP(Markov Property): ‘확률’ state에서 미래 상태 예측 시 과거가 아닌, ‘현재 상태’만을 고려하겠다는 가정

MDP에서의 Reward는 아래 이미지와 같음 :

위와 같은 식을 따르며 이식의 조건부 평균(기댓값)을 구하게 되면

 

2. 추가설명(추가요소)

-Reward 함수(R): 현재 state에 대한 reward의 기댓값을 표현하는 함수

-Gamma 값(감쇄인자) : 불확실성을 표현하며, 0~1 사이의 값을 가지면서 미래의 보상(return)을 최소화하는 역할을 한다.

-최종적으로 미래의 보상을 작게 하는 것이 강화학습의 목적이기 때문(최소 경로로 간다고 생각하면 됨)

2-1. 교재 예시 (A diagram with rewards); figure 7

*Interpretation: v(s) - 기댓값(MRP로 얻을 수 있을 것으로 예상되는 평균값)

위 그림에서의 숫자는 return values를 의미한다.

가. Dilbert Reward Process (DRP)를 사용한 추정

Q. Gamma(감쇄인자) = 0일 때 , Chat 상태에서의 변화 생각하기

A. Depends on chance(Gamma를 모를 때). But 지금은 Gamma=0임을 아니까 계산해보자.

Why ?

• Dilbert Process에 의하면 Chat 상태에선 크게 3가지 진로(?)가 가능
• 50%(0.5) - Chat
• 30%(0.3) - Computer
• 20%(0.2) - Coffee
• 이때, 전제에서 감마값=0이라고 하였으므로, 오로지 확률만으로 Chat 상태에서의 value를 측정해야 함.

측정(계산) 방식은 우리가 아는 ‘기댓값 구하는’ 방식과 똑같다:

: 가장 valuable state는Computer이 되는 것

마찬가지 방식으로 감마값=1일 때의 value를 측정해 본다면?

-이런 경우 미래 상태의 무한한 가능성에 대해 추론하게 되기에 ‘infinite for all states’라는 결론이 도출

 

3.Markov decision process(MDP; 마르코프 결정과정)

: MRP + Decision(결정)을 결합한 것으로, reward values와 decisions를 같이 고려하는 과정이다.

: MRP와의 가장 큰 차이는 agent(state)에게 선택지가 주어지는지 그 여부라고 볼 수 있다(action).

MRP에선 학습이 불가하다. 정해진 확률에 의해 transition(전이)되고, 정해진 양의 보상을 받기 때문.

MDP에선 action으로부터 얻은 reward를 통해 value(가치)를 매기고, 이를 다음 같은 상태(state)에서의 선택 시에 참고하게 된다.

3-1. action(Agent의 action)

: agent의 관점에서 value를 평가한다. state에 대한 value뿐 아니라, agent가 하는 action에 대해서도 value를 측정하게 되는 것.

3-2. policy: action을 정하는 함수(Mapping 함수)

수식으로는 아래 이미지와 같다.