Lecture 1: Introduction to Reinforcement Learning

본 글은 David Silver 교수님의 강의를 기반으로 작성하였습니다.

Branches of Machine Learning

Machine Learning의 종류는 3가지종류로 분류됩니다.

• Supervised Learning(지도학습) : 지도학습의 핵심은 Supervisor가 존재한다는 것입니다. 정답을 주고 학습을 시킨다고 보면 되겠습니다. 기계는 정답지와 자신이 추론한 정답의 오차를 비교하면서 학습하게 되는 것입니다.
• Unsupervised Learning(비지도 학습) : 비지도학습의 핵심은 정답이라고 말하는 Label이 존재하지 않습니다. 기계는 정답이 없이 학습을 통해 입력 데이터들의 패턴을 찾아내어 그 데이터들의 분류를 찾아내는 것입니다.
• Reinforcement Learning(강화 학습) : 본 주제가 강화학습이니 만큼 강화학습은 다른 기계학습들의 패러다임과 어떤 차이가 있는지 알아보겠습니다.

Characteristics of Reinforcement Learning

• 강화학습에는 정답을 알려주는 Supervisor가 없습니다. 오직 보상 신호만 존재합니다.
• 피드백이 즉각적이지 않습니다. 예를 들어 어떠한 행동(Action)을 했을 때 그 행동에 대한 보상이 바로 주어지지 않을 수 있습니다.
• 시간이 매우 중요합니다. (순차적인 데이터이며, 독립항등분포의 데이터가 아닙니다.)
• 에이전트의 행동이 그 이후에 우리가 받게 되는 데이터에 영향을 줍니다.

Examples of Reinforcement Learning

위처럼 다양한 경우에 강화학습이 사용될 수 있습니다.

Reward

• 보상은 $R_{t}$로 표시하며 스칼라 값의 신호입니다.
• step $t$의 상황에서 에이전트가 얼마나 잘하고 있는지 나타내는 지표입니다.
• 에이전트의 목적은 축적된 보상을 최대화하는 것입니다.

강화학습은 보상이론(Reward Hypothesis)을 기반으로 하고있습니다.

Definition (Reward Hypothesis)

• 모든 목적은 축적된 보상을 극대화하는것으로 말할 수 있습니다.

Examples of Rewards

현재 그림은 위의 Examples of Reinforcement Learning에 대한 Reward 예시입니다.

Sequential Decision Making

• 순차적 결정의 목표는 미래의 보상을 최대화하는 행동을 선택하는 것입니다.
• 행동은 때때로 장기적인 결과를 가져올 수도 있습니다.
• 보상은 지연될 수도 있습니다.
• 현재의 즉각적인 보상을 희생하더라고 장기적인 보상을 얻는것이 더 좋을 수도 있습니다.

Agent and Environment

Agent and Environment

• 여기서는 뇌를 Agent 지구를 Environment로 예시를 들었습니다.
• 어떤 $time-step$인 $t$에서의 Agent의 상태에 대해서 보겠습니다.
  • $A_{t}$ 의 행동을 실행합니다.
  • 환경으로부터 관찰값 $O_{t}$를 전달받습니다.
  • 환경으로부터 스칼라 보상값인 $R_{t}$를 전달받습니다.
• 환경의 상태에 대해서 보겠습니다.
  • Agent로부터 $A_{t}$라는 행동값을 전달받습니다.
  • 환경은 다음 $time-step$에 대한 관찰값 $O_{t+1}$값을 Agent에게 방출합니다.
  • 환경은 다음 State에 대한 보상값인 $R_{t+1}$를 Agent에게 방출합니다.

$time-step$인 $t$는 각 스텝마다 환경에서 증가하게 됩니다.

History and State

• history라고 불리는 것은 기록이며 관찰, 행동, 보상들이 포함됩니다.

$$H_{t} = O_{1}, R_{1}, A_{1}, ..., A_{t-1}, O_{t}, R_{t}$$

• 그 다음에 일어나게 될 일은 History에 의해서 결정됩니다.
• State는 다음에 어떤 것을 할지 결정하기 위해서 쓰이는 모든 정보입니다.(State는 History의 함수입니다.)

$S_{t} = f(H_{t})$

Environment State

• 환경의 State는 $S_{t}^{e}$입니다.
• 환경의 State는 Agent에게 표시되지 않습니다.
• 만약에 보이게 되더라도 관련없는 정보들을 표시할 수 있기 때문에 별로 보는것이 좋지 않습니다.

Agent State

• Agent의 State는 $S_{t}^{a}$입니다.
• Agent의 State는 Agent가 다음 행동을 결정하는 중요한 정보입니다.

 $$S_{t}^{a} = f(H_{t})$$

Information State

• information state라고 하는것은 Markov state라고 불리며 history로부터 중요한 정보를 가져올 수 있는 것입니다.

Definition

• $A$ $state$ $S_{t}$는 Markov하다라는 가정하에 수식을 보겠습니다.
• 여기서 Markov하다는 것은?
  • 현재의 State를 알고있는 것은 모든 과거의 State를 아는 것과 같다는 말입니다.

$$P[S_{t+1}\mid S_{t}] = P[S_{t+1}\mid S_{1}, ..., S_{t}]$$

• 현재가 주어져 있다고 가정할 때 미래는 과거와는 독립적입니다.

$$H_{1:t}\rightarrow S_{t}\rightarrow H_{t+1:\infty }$$

• 현재의 State를 알면, 과거의 State는 필요가 없습니다.
• State는 미래에 대한 충분한 통계치입니다.
• 환경 $S_{t}^{e}$는 Markov합니다.
• 역사 $H_{t}$는 Markov합니다.

Rat Example

State에 대한 정의에 따라서 받을 수 있는 보상이 달라질 수 있습니다.

• 전구, 레버, 전구를 예로 들면 마지막에 받을 수 있는 보상은 감전을 당하는 것입니다.
• 전 State의 레버의 개수 종의 개수를 맞춘다면 Agent는 치즈를 보상으로 받을 것입니다.
• 현재의 State 모두를 정의한다면 보상은 알 수 없습니다.

Fully Observable Environment

• Agent가 환경의 State를 볼 수 있는 경우 Fully Observable이라고 합니다.

$$O_{t} = S_{t}^{a} = S_{t}^{e}$$

• 흔히 이것을 MDP(Markov Decision Process)라고 부릅니다.

Partially Observable Environments

• 이때는 Agent State와 Environment State가 같지 않은 상황입니다.
• 이것은 POMDP(Partially Observable Markov Decision Process)라고 부릅니다.
• Agent는 자신이 가진 상태$S_{t}^{a}$에 대해서 표현해야 합니다 
  • history에 대해서 표현 : $S_{t}^{a} = H_{t}$
  • 환경의 State에 대한 표현 : $S_{t}^{a} = (P[S_{t}^{e} = s^{e}], ..., P[S_{t}^{e} = s^{n}])$
  • 순환신경망(RNN) : $S_{t}^{a} = \sigma(S_{t}^{t-1}W_{s} + O_{t}W_{o})$

Major Components of an RL Agent

• 정책 : Agent의 행동함수에 대해서 정의합니다.
• 가치함수 : 각각의 State또는 Action에 대해서 얼마나 좋은 지 평가하는 것에 대해 정의합니다.
• 모델 : 환경에 대해서 Agent의 표현에 대해 정의합니다.

Policy

• 정책은 Agent의 행동을 나타내는 것입니다.
• 결정론적 정책 : $a = \pi(s)$
• 확률론적 정책 : $a = \pi(a\mid s) = P[A_{t} \mid S_{t} = s]$

Value Function

• 가치함수는 미래의 보상을 예측하는 것입니다.
• State에 대한 좋고 나쁨을 평가하는데 사용됩니다.

$$v_{\pi}(s) = E_{\pi}[R_{t+1} + \gammaR_{t+2} + \gamma^{2}R{t+3} + ... \mid S_{t} = s}$$

Model

• $A$ 환경에 대해서 예측합니다.
• $P$는 다음 상태를 예측합니다.
• $R$ 즉각적인 보상을 예측합니다.

$$P_{ss'}^{a} = p[S_{t+1} = s' \mid S_{t} = s,A_{t} = a}]$$

$$P_{s}^{a} = E[R_{t+1}  \mid S_{t} = s,A_{t} = a}]$$

Maze Example

• 보상은 1칸을 갈때마다 -1의 보상을 받습니다.
• 행동은 북쪽, 동쪽, 남쪽, 서쪽이 있습니다.
• State는 Agent의 위치입니다.

Maze Example : Policy

Maze Example : Model

• 위의 그림은 Agent가 본 Environment의 State입니다.(완벽하지 않은 모델)
• 밑의 길은 Agent가 가보지 않았기 때문에  알 수 없습니다.

Categorizing RL agnets (1)

• Value Based : Value Function만 존재합니다.(value Function만 있어도 Agent가 역할을 할 수 있습니다.)
• Policy Based : Policy만 존재합니다.
• Actor Critic : Policy, Value Function 두개 다 존재합니다.

Categorizing RL agnets (2)

• Model Free : 모델을 만들지 않는 것(Policy나 Value Function만 가지고 수행)
• Model Based : 모델 등을 가지고 있는 것

RL Agent Taxonomy

Learning and Planning

순차적 의사 결정의 두가지 근본적인 문제들(fundamental problems)에 대해 보겠습니다.

• 강화 학습:
  • 환경이 어떤 지 모릅니다.
  • Agent는 환경과 상호작용합니다.
  • Agent는 정책을 개선합니다.
• 계획:
  • 환경을 잘 알고 있습니다.
  • Agent는 모델을 통해 계산을 수행합니다.
  • Agent는 정책을 개선합니다.

Atari Example : Reinforcement Learning

• 게임의 규칙을 알지 못합니다.
• 게임을 플레이하면서 환경과의 상호작용을 통해서 바로 배웁니다.
• 조이스틱을 움직이는 행동을 선택하고, 그 행동에 따라서 픽셀이나 점수가 바뀌는 것을 볼 수 있습니다.

Atari Example : Planning

• 게임에 대한 룰을 알고 있습니다.
• 에뮬레이터가 있어 에뮬레이터에 쿼리를 날립니다.
  • Agent의 뇌속에 완벽한 모델이 있습니다.

Exploration and Exploitaion (1)

• environment와 상호작용을 하면서 좋은 Policy를 찾는 과정입니다.
• environment로 부터 경험을 합니다.

Exploration and Exploitaion (2)

• 탐험이라는 것은 환경으로부터 더 많은 정보를 찾아내고자 하는 것 입니다.
• Exploitation은 알고 있는 정보로부터 보상을 극대화하고자 하는 것 입니다.
• Exploration과 Exploitation은 Trade-off 관계에 있습니다.

Example

위의 예시는 Exploration과 Explotaion의 예시입니다.

Prediction and Control

• Prediction : 미래에 대해 평가를 하는 것입니다.
  • 정책을 줍니다.
• Control : 미래를 최적화하는 것입니다. 
  • 최고의 정책을 찾습니다.

Gridworld Example : Prediction

Prediction은 State에 대한 Value Function을 찾는 것이므로 그에 대한 예시를 설명 해놓았습니다.

Gridworld Example : Control

Control문제는 State에 대한 Policy를 찾는 것이므로 그에 대한 예시를 설명 해놓았습니다.