CodeDrive

다음 논문을 읽고 작성한 내용이며 잘못 해석한 내용이 있을 수도 있습니다. 초록색으로 칠한 내용은 이해

를 하지 못한 내용입니다.

https://arxiv.org/abs/1606.01541

Deep Reinforcement Learning for Dialogue Generation

Abstract

• Dialogue Generation을 RNN으로 하는 것이 좋은 가능성을 보인기는 했지만, 근시안적으로 바라보며 미래에 다가올 영향을 생각하지 않고 대화를 생성하는 경향이 있다.
• 이러한 문제점이 발생했기 때문에 NLP 모델에 RL을 넣으려는 시도를 해보려고 한다.
• 이 모델은 두 개의 가상 agent로부터 대화를 생성한다.
  • policy gradient 방법을 사용한다.
  • 대화의 품질을 높힐 수 있는 세 가지 reward를 도입했다.
    • informativity
    • coherence
    • ease of answering
• 우리는 이 모델을 diversity와 length를 지표로 평가를 할 것이다.

1. Introduction

• Neural response generation에 대해서 많은 연구가 이루어졌다.

• Seq2Seq 모델이 Dialogue Generation에서 성공을 이뤘음에도 불구하고 두 가지 문제점이 있다.

  1. SEQ2SEQ 모델은 MLE를 사용해서 주어진 대화 문맥을 통해서 다음 단어를 예측한다.

     • 그러나 MLE는 실생활에 chatbot을 도입하기에는 적합하지 않다.
       • 사람에 의해 학습이 되는 것인데, 다양성을 보장하기 어렵다.
     • 가장 대표적인 예시로 "I don't know"와 같이 input과 상관없이 사용할 수 있는 답변을 가장 많이 하게 된다.
       • 이러한 것들이 다양성을 낮추게 되는 것이다.

          

         

  2. 위 테이블의 왼쪽 예시처럼 같은 말이 반복되는 무한 루프에 빠지게 될 가능성이 높다.

     • 이것도 역시 MLE-based SEQ2SEQ 모델로 인해 발생하게 되는 문제이다.

• 이러한 문제를 해결하기 위해서 다음 두 가지를 도전 과제로 잡았다.

  1. chatbot 개발을 잘하기 위해서 개발자가 직접 정의한 reward를 도입한다.
  2. 대화가 진행되면서 long-term influence를 해결하도록 한다.

• 이러한 목표를 달성하기 위해서 이번 논문에서는 MDP나 POMDP dialogue system의 개념을 사용하도록 한다.

  • 이 방법을 사용하면 long-term reward를 최적화할 수 있을 것이다.

• 우리 모델은 encoder-decoder 구조를 기본으로 가지고 있으며, reward를 최대화 하는 방향으로 2개의 가상 에이전트가 대화를 시뮬레이션으로 하는 방법을 사용한다.

• 좋은 대화를 만들기 위해서 reward에 관해 간단한 heuritic한 가정을 정의했다.

  • 좋은 대화란 forward-looking하고 interactive, informative, coherent라고 한다.

• encoder-decoder RNN은 policy로 정의되며, long-term developer-defined reward를 최적화하기 위해서 policy gradient 방법을 사용해 학습한다고 한다.

• SEQ2SEQ에 RL의 강점을 부여한 모델이라고 생각하면 되고, 일반적인 SEQ2SEQ와 비교해본다.

2. Related Work

생략

3. Reinforcement Learning for Open-Domain Dialogue

• learning system은 2개의 agent로 구성되어 있으며, p를 첫 agent가 생성한 문장, q를 두번째 agent가 생성한 문장으로 정의한다.
  • 2개의 agent는 서로 교대로 대화를 하며 진행을 한다.
    • 즉 p1,q1,p2,q2,...,pi,qi와 같이 진행한다.
  • action은 대화를 생성하는 것으로 정의를 한다.
  • policy는 encoder-decoder RNN을 사용한다.
• 파라미터는 뒤에서 이야기 하도록 한다.
• Policy gradient 방법이 Q-learning보다 더 적합하다고 생각한다.
  • Q-learning은 각 행동에 대해서 바로 미래 가치 reward를 추정하는데, 이는 long-term reward를 최대화 하려고 하는 목적과 다르기 때문이다?

3.1 Action

• action a는 문장을 생성하는 것으로, action space는 생성하려는 문장이 가변적이고 의미적으로도 다양하므로 무한하다.

3.2 State

• state는 이전 두 dialogue [pi,qi]로 정의되며 이를 encoding해서 vector representation으로 input으로 넣어주게 된다.

3.3 Policy

• LSTM Encoder-decoder의 형태를 가져온다. 그리고 stochastic representation of the policy를 사용한다.

3.4 Reward

• r은 each action에서 얻어지는 것이며, 대화의 성공을 위해 중요한 요소이다. 이러한 요소들을 어떻게 추정할 것인지에 대해 이야기 한다.

Ease of answering

• 기계가 대답하는 것이 쉽게 하는 것이다. 이는 앞서 말한 forward-looking function과 연관있다.

• 이 것을 dull response의 대답에 대한 negative log likelihood를 사용해서 측정한다.

  • SEQ2SEQ에서 발생했던 dull response S list를 사용한다.

• reward function은 다음과 같이 생겼다.

  

• NS는 dull response의 수이다.

Information Flow

• 각 agent가 대화가 진행되고, 반복을 피하면서 새로운 말을 하는 것을 원한다.

• 따라서 같은 agent로 부터의 연이은 대화 사이의 의미론적 유사도를 사용한다.

  • hpi, hpi+1를 encoder로 부터 얻을 수 있으며, reward는 negative log of the cosine similarity를 사용해서 구한다.

    

Semantic Coherence

• 문법적으로 틀리거나 일관성이 없는 문장을 제외하고는 높은 보상을 주도록 해야 한다.

• 생성된 응답이 일관성이 있고 적절함을 보장하기 위해서 action a와 previous turn 사이의 mutual information을 고려하도록 한다.

  

  • 첫번째 term은 probability of generating response a given the previous dialogue utterance이다
  • 두번째 term은 backward probability of generating the previous dialogue utterance qi based on response a 이다.

Final

• 최종적으로는 다음과 같이 reward를 계산한다.

• λ1+λ2+λ3=1을 만족해야 하며, 이번 모델에서는 λ1=0.25, λ2=0.25, λ3=0.5로 설정했다.

4. Simulation

• main idea는 두 개의 가상 agent가 서로 대화를 하면서 state-action space를 탐색하고, policy를 배워 optimal expected reward를 이끌어내는 것이다.

4.1 Supervised Learning

• training을 하기 위해 supervised SEQ2SEQ model을 사용해서 주어진 dialogue history로 target sequence를 생성하는 예측 사전작업을 한다.
• attention을 가진 SEQ2SEQ을 학습한다.
  • dataset에 있는 each turn을 target으로 간주한다.
  • 두 이전의 sentence의 결합은 source input으로 간주한다.

4.2 Mutual Information

• SEQ2SEQ의 sample은 dull 하고 generic하다.(ex)"i don't know")

  • pre-trained된 SEQ2SEQ 모델로 policy model을 초기화하는 것을 원하지 않는다.
    • 왜냐하면 이 것은 RL 모델의 경험에서 다양성의 부족을 이끌어내기 때문이다.

• Li et al(2016a)에서 source와 target의 mutual information이 dull한 대답을 확실하게 줄이고, 일반적인 대답의 품질을 향상시켰다.

  • 따라서 mutual information response를 최대화하는 encoder-decoder 모델을 사용하였다.
  • 이 논문에서 소개된 것은 실현 불가능하다. 왜냐하면 Eq3에서 second term은 완전하게 생성된 target sentence가 필요하기 때문이다.
  • sequence level learning에 관한 최근 연구에 영감을 받아 maximum mutual information response를 생성하는 문제를 mutual information value의 reward가 model이 sequence의 끝에 도달하는 RL 문제로 취급한다.

• Ranzato와 유사하게 최적화를 위해서 policy gradient 방법을 사용한다. 우리는 pre-trained model을 사용해서 policy model을 초기화하고, input source를 넣어서 candidate list를 생성한다.

  • 생성된 값들을 mutual information score을 가지게 된다.

    • 이 mutual information score은 reward로 사용이 되고, encoder-decoder의 back-propagated로 사용된다.

  • expected reward는 다음과 같이 주어진다.

    

  • likelihood ratio를 사용해 추정한 gradient는 다음과 같다.

    

• stochastic gradient descent를 사용해서 encoder-decoder 속의 parameter를 업데이트 한다.

• curriculum learning 전략을 사용해서 모든 T 길이의 sequence 중 첫 L개 token은 MLE loss를 사용하고, reinforcement 알고리즘으로 T-L개 token을 사용한다. 점차적으로 L을 0으로 줄이도록 한다.

• baseline 전략은 variance를 줄이기 위한 방법이다.

  

4.3 Dialogue Simulation between Two Agent

• 2개의 가상 agent 사이에서 대화를 simulation 하는 방식으로 진행한다.
  1. training set에서 뽑은 message를 1번 agent에게 준다.
  2. agent는 input message를 vector representation으로 encoding 한 후, response output을 생성하기 위해 decoding 한다.
  3. 생성된 output을 dialogue history에 넣고 다음 agent가 2번을 수행한다.

Optimization

• mutual information model의 parameter로 p_RL을 초기화 한다.

• 더 큰 expected reward를 얻기 위해 policy gradient를 사용한다. objective 함수는 다음과 같다.

  

• likelihood ratio trick을 사용해 gradient는 다음과 같이 구한다.

  

4.4 Curriculum Learning

• dialogue의 2 turn을 simulating 하는 것으로 부터 시작해서 5개까지 늘리는 것을 목표로 한다.

5. Experimental Results

• human judgments와 two automatic metric를 사용해서 비교한다.
  • conversation length
  • diversity

5.1 Dataset

• dialogue simulation은 high-quality initial input이 필요하다.
  • 만약 첫 시작부터 "why?", "i don't know what you are taking about"와 같은 것이 들어오게 된다면 훈련이 잘 안될 것이다.

5.2 Automatic Evaluation

• true response quality보다는 long-term success of the dialogue이 목표이기 때문에 BLEU나 perplexity를 평가지표로 활용하지 않는다.

Length of the dialogue

• 이 논문에서 제안하는 first metric은 simulated dialogue의 length이다.

  • "i don't know"와 같은 dull response를 생성하거나 같은 agent로 부터의 응답이 같을 경우 end라고 한다.

• test set은 1,000개의 input message로 구성되어 있다.

  • circular dialogue의 위험을 줄이기 위해서 turn을 8개로 제한했다.

  • 결과는 다음 표와 같다.

    

  • mutual information이 SEQ2SEQ보다 더 긴 대화를 나누었고, mutual information으로 훈련을 하고 RL의 장점을 추가한 RL 모델이 가장 좋은 결과를 얻었다.

Diversity

• generated response에서 distinct unigram과 bigram의 수를 계산하는 것으로 diversity를 본다.

• value를 favoring long sentence를 피하기 위해서 생성된 toal number로 scaled 했다. (by Li et al. (2016a).)

• SEQ2SEQ 모델과 RL 모두 beam size를 10으로 해서 beam search를 수행했다.

  • mutual information model은 pSEQ2SEQ(t|s)를 사용해서 n-best list를 생성하고 pSEQ2SEQ(s|t)를 사용해서 linearly re-rank했다.

    

• RL 모델이 diversity가 가장 높다는 것을 알 수 있다.

Human Evaluation

• human evaluation에 three setting이 있음.

  1. crowdsourced judge to evaluate a random sample of 500 items (by Li et al (2016a))

     • single-turn general quality에 해당

     • input message 와 generated output을 3단계로 나타냄.

     • 어떤 output이 better인지 물어본다. (Tie도 허용)

     • 동일한 string은 같은 점수를 부여한다.

     • RL 모델로 mutual information보다 좋은 점수를 받음

  2. judge는 다시 input message와 system outpus으로 표현한다.

     • single-turn ease to answer에 해당

     • 그리고 어떤 output이 respond하기 easy한지 물어본다.

     • 500 items을 다시 3 judge로 평가한다.

  3. 두 agent 사이에 simulated conversation으로 표현한다.

     • multi-turn general quality에 해당
     • 각 대화는 5개의 turn으로 구성되고 200개의 시뮬레이션된 대화가 있다.
     • 이 역시 3 judge로 수행한다.

  

  • 사람들이 평가한 표를 위와 같다.
    • 대답을 잘 했는지에 대한 비교는 40퍼 승, 36퍼 패로 비슷하다.
    • 하지만 얼마나 장기적으로 대화를 했는가 문제에서는 RL이 훨씬 좋은 성능을 보였다.

Qualitative Analysis and Discussion

• random sample에 대해 응답한 mutual information model과 RL 모델의 비교이다.

  • RL 모델로 생성한 것이 더 interactive한 응답을 했다.
  • 그리고 RL 모델이 대답을 다른 질문을 하는 것으로 sentence를 끝내는 경향이 보인다.

• error analysis를 할 때 발견된 것으로 반복되는 응답에 패널티를 부여했지만 다음과 같이 긴 cycle이 존재하는 반복이 존재한다.

  

  • 우리가 생각할 수 있는 대화의 양이 제한되어 있기 때문인 것 같다?

• 다른 문제로는 모델이 가끔 관계 없는 주제를 이야기 하는 경우도 있다.

• 중요한 문제는 당연하게도 우리가 임의로 정해준 reward로 이상적인 대화를 만들기 위해서 모든 면을 cover할 수는 없다.

• 현재 모델의 다른 문제점은 적은 수의 candidate를 고려할 수 밖에 없다는 것이다.

6. Conclusion

• RL 과 SEQ2SEQ의 각각 강점을 dialogue에 적용해보았다.
• 이전의 SEQ2SEQ와 같이 dialogue turn의 의미와 적절한 응답을 할 수 있었다.
• RL의 특성으로 봤을 때, 미래 지향적인 점을 충분히 잡았다.
• 우리의 모델이 간단하다는 사실에도 불구하고, global 특성을 잡았고, 더 다양하고 interactive한 응답을 보여주었다.

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

6. Value Function Approximation

지금까지는 Grid World를 통해서 작은 상황을 설정했고 table로 저장하는 것이 가능했다. 그리고 value function과 policy를 구하는 과정을 살펴보았다. 이러한 문제들을 Tabular Method라고 부른다. 하지만 실제 문제에 대해서 강화학습을 적용하기에는 너무 크다.

지금 강화학습으로 해결할 수 있거나 해결하려고 하는 문제에 대해서 state의 갯수를 알아보면 다음과 같다. Backgammon은 10²⁰, 알파고는 10¹⁷⁰, 헬리콥터(자율주행)은 사실상 무한대의 상태들을 가지고 있다. 따라서 이러한 문제에 대해서 value function과 policy를 구하고자 하는 것은 어렵다. 따라서 이 값들을 추정하는 방법들에서 배우도록 한다.

function approximation을 하는 방법은 어렵지 않다. 새로운 변수 w를 대입해서 이 변수가 table의 정보를 대변하도록 만들면 된다. 즉 다음과 같이 함수화 할 수 있다.

w는 학습을 통해서 update하며, true value와 근사하도록 맞춰나간다. 최근에는 이 학습을 하는 과정에 deep learning을 사용하기도 한다.

Value Function Approximation에는 다음과 같은 종류들이 있다고 한다.

function approximator에는 여러 개가 있지만 그 중 미분가능한 Linear combinations of features, Neural network를 이번 장에서 소개하도록 한다. 그리고 이들은 non-stationary, non-iid한 data라고 하는데, 분포가 계속해서 바뀌며 독립적이지 않다.

Incremental Methods

w를 업데이트를 하는 방법중 가장 좋은 것은 Gradient Descent이다. 이 방법은 간단하고 프로그램 상으로도 강력하다. 하지만 시작점에서 조금만 달라져도 다른 점에 도착할 수 있고, 이 점이 local optima일 수도 있다.

w로 표현되는 loss function인 J(w)는 true value와의 error로써 이를 최소화하는 것이 목적이다.

이를 미분해서 값을 update 할 수 있는데 expectation을 쓰는 방법과 sampling을 하는 방법이 있고 다음과 같다.

MC와 TD에서 했던 것처럼 v_π(S)를 대체해서 사용할 수 있다.

MC with Value Function Approximation

MC의 G_t는 unbiased 하고, true value의 noisy sample이다. 그러므로 training data를 지도학습으로 적용할 수 있다. 그래서 위와 같이 사용가능하며, local optimum으로 수렴하게 된다. 그리고 non-linear한 경우에도 적용할 수 있다고 한다.

TD Learning with Value Function Approximation

TD-target은 guess를 사용하는 것이기 때문에 true value의 biased sample이다. 하지만 여전히 training data를 지도학습으로 적용이 가능하고 위에서 소개한 것처럼 TD(0)를 적용할 수 있다.

Linear TD(0)는 (거의) global optimum에 수렴한다.

TD(λ) with Value Function Approximation

G_t^λ도 true value의 biased sample이다. 그러므로 역시 training data를 지도학습으로 적용할 수 있으며 Forward view linear TD(λ), Backward view linear TD(λ)로 각각 적용할 수 있고, 서로 equivalent하다.

Control with Value Function Approximation

하지만 value function을 사용하면 control 문제를 다룰 때 발생했던 model-free가 발생한다. 따라서 이번에도 value function을 q-function으로 바꾸도록 한다.

그리고 그 뒤로는 value function을 했던 내용과 동일합니다.

Batch Methods

Gradient descent는 간단하고 매력적이지만 한번 쓰고 버린다. 따라서 sample efficient하지 않다고 한다. 따라서 Batch method는 1000개의 데이터가 있으면 그 중 10개를 sample로 해서 사용하는 방식이다. 이를 통해 value function의 best fitting을 찾을 수 있다고 한다.

value function approximation을 사용하고, experience D는 <state, value>의 쌍으로 구성된다. 이 때 best fitting value인 파라미터 w를 찾기 위해서 Least squares 알고리즘을 사용한다.

Least squares 알고리즘은 추측값과 참값 사이의 sum-squared error를 최소화하는 w를 찾는 알고리즘이다.

Stochastic Gradient Descent with Experience Replay

<state, value>로 쌍이 묶어진 experience D가 있을 때, 다음을 반복한다.

그러면 이는 다음과 같이 수렴한다.

이러한 방법을 Experience replay라고 하며 강화학습에서 자주 사용하는 방법이다.

Experience replay in Deep Q Networks

Non-linear랑 off-policy일 때 학습을 진행하면 수렴을 하지 않고 발산한다는 문제점이 발생한다. 따라서 이러한 문제를 해결하기 위해 DQN은 experience replay와 fixed Q-target을 사용한다고 한다.

• Experience reaply: 어떤 action에 어떤 reward와 그 state등 정보들이 있는 transition을 replay memory에 저장하고, random하게 mini batch를 뽑는다. 그리고 MSE를 통해 학습한다.
• Fixed Q-target: target을 계산할 때에 예전 parameter를 쓰는 것, 두 개의 파라미터 set이 있다. 하나는 고정시키고 다른 하나는 업데이트 중인 파라미터 set을 가진다. non-linear 함수일 때에 업데이트 방향이 계속 바뀌기 때문에 수렴되기 어렵다. 따라서 1000번 정도는 고정된 parameter set을 사용하며 진행하다가 그 이후에 고정된 parameter set을 업데이트 하던 parameter set으로 바꾼다. 예전 버전을 w^-, 현재 버전을 w라 했을 때, target에서는 고정된 것을 사용하기 때문에 fixed Q-target이라 한다.

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

5. Model Free Control

• Model Free : MDP에 대한 정보가 없는 경우, 즉 environment에 대한 정보를 가지고 있지 않다.
• Control : value function을 최적화 하는 것, 즉 최적의 정책을 찾는 것

Model Free Control에서는 다양한 예제들이 있으며, 주로 다음 특징을 가지는 문제들을 해결한다,

• MDP를 모르지만, 경험을 sampling 할 수 있다.
• MDP는 알지만, sample들을 제외하고는 사용하기에는 너무 크다.

On Policy & Off Policy

• On Policy learning
  • "Learn on the job"
  • 학습하는 policy와 행동하는 policy가 같은 경우
    • ex)Sarsa
• Off Policy learning
  • "Look over someone's shoulder"
  • 학습하는 policy와 행동하는 policy가 반드시 같지 않아도 된다.
    • ex)Q-learning

On-Policy Monte-Carlo Control

• Generalised Policy Iteration

  

  • 3장에서 배웠던 내용으로 최적의 정책을 찾는 문제를 해결하기 위한 일반적인 방법론이다.
    • 임의의 정책으로 시작하여 value function을 추정하는 단계를 거친다.
    • 추정한 value를 바탕으로 정책을 발전시킨다.
    • 다시 맨처음으로 돌아간다.
    • 이는 EM 알고리즘과 같은 형태를 가지고 있다.
      • 따라서 Policy evaluation을 E단계, Policy improvement를 M 단계라 지칭한다.

• 4장에서 value function을 estimate 하는 방법들에 대해서 배웠는데 이를 E 단계에 적용해보도록 한다.

  • 하지만 그대로 적용한다면 다음과 같은 3가지 문제가 발생하게 된다.
    1. Value funcion의 model-based
    2. Local optimum
    3. Inefficiency of policy evaluation

1. Model-based

MC로 E단계를 수행하게 된다면 state value function을 사용해야 한다. 하지만 value function을 사용하면 M단계를 진행할 때 문제가 발생하게 된다. MC를 사용했던 이유가 Model-Free이기 때문이지만 value function으로 policy를 improve하려면 MDP의 model을 알아야 한다.

즉 위와 같이 reward와 state transition probaility를 알아야 한다. 즉 Model-based이어야 한다는 것이다.

따라서 이를 해결하기 위해서 value function을 action value function으로 바꾸게 되면 Model-Free 성질을 만족할 수 있다.

• return이 아닌 agent가 episode마다 random하게 움직이며 얻은 reward들 그리고 state transition prob.를 통해서 action-value function을 계산할 수 있다.

2. Local optimum

그러면 이제 Policy evaluation에서 value function을 action value function으로 바꾼다면 On policy MC를 사용할 수 있는 것일까? 다음 예시를 살펴보도록 한다.

• 두 개의 문이 내 앞에 있다.

  • 처음 왼쪽 문을 열었고, reward 0을 받았다.

    • V(left) = 0

  • 두번째에는 오른쪽 문을 열었고, reward 1을 받았다.

    • V(right) = +1

  • 세번째에 오른쪽 문을 열었고, reward 3을 받았다.

    • V(right) = +2

  • 네번째에 오른쪽 문을 열었고, reward 2를 받았다.

    • V(right) = +2

  • 그러면 지금까지 상황을 보았을 때 어느 문을 여는 것이 최선의 선택일까?

    • 아마도 이 네가지 상황으로만 본다면 오른쪽 문을 여는 것이 최선의 선택으로 보인다. 하지만 다음에 왼쪽 문을 열었을 때 reward를 100을 받을 수도 있는 것이다. 즉 지금 탐험과 탐사 trade-off에 빠지게 된 상황이다.

  • exploration(탐험) : environment에서 더 많은 정보를 알아내고자 하는 방법으로, 모든 행동을 할 때 일정 확률로 다른 곳으로 이동한다.

  • exploitation(탐사) : 알고 있는 정보를 바탕으로 보상을 최대화하고자 하는 것이다.

즉 지금 greedy 하게 improve 하는 것은 탐사에 빠지게 되는 것이다. 따라서 탐험을 어느정도 보장함으로써 model을 모르는 상황에서 더 좋은 성능을 낼 수 있을 것이다.

따라서 policy를 최적화 할 때 다음과 같이 일정한 확률을 부여해서 정하도록 한다.

3. Inefficiency of policy evaluation

하지만 MC 방법의 경우에 모든 episode들을 다 마친 후에 evaluation을 하면 너무 오랜 시간이 걸린다는 단점이 존재하게 된다. 따라서 이를 줄이기 위해서 매 episode들이 끝난 후에 policy evaluation을 수행하는 것으로 바꾸도록 한다.

즉 최종적인 On-Policy Monte-Carlo Control은 다음과 같다.

On- Policy Temporal-Difference Learning

TD가 MC보다 적은 variance를 가지고 online으로 학습가능하며, Incomplete sequence라는 장점들을 가지고 있기 때문에 control 문제에 적용해볼 수 있다.

Prediction에서 TD는 다음과 같이 표현을 했었다.

MC와 같은 이유로 value function을 사용할 수 없으므로 해당되는 부분들을 action value function으로 수정하도록 하자. 따라서 S에서 A 행동을 하면 보상 R을 받고 S'이라는 상태로 이동한다. 이 상태 S'에서 A'이라는 임의의 행동을 할 때의 action value function 값이 필요한 것이므로 다음과 같이 표현할 수 있다.

따라서 이를 앞부터 철자를 따서 Sarsa라고 부른다. Policy evaluation 부분에 MC 대신에 sarsa를 적용하면 다음과 같다.

n-step Sarsa

Sarsa가 애초에 TD의 개념에서 나온 것이므로 TD(λ)와 마찬가지로 Sarsa(λ)로 사용할 수 있다.

• forward view Sarsa(λ)

  • MC와 TD의 절충안이 n-step인 것처럼, 여러 개의 n-step을 선택하여 이의 평균을 취하면 각 n-step의 장점을 모두 가질 수 있게 된다. 이 때, 단순히 산술평균을 사용하는 것이 아니라 λ라는 weight를 이용해서 가중 평균을 취하도록하고 이를 Forward-view라고 한다.

  • episode가 모두 끝나야 계산이 가능하다. 따라서 TD의 장점을 많이 잃게 된다.

    

• backward view sarsa(λ)

  • 이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 알아본다. 여기서 eligibility trace라는 개념이 나오게 된다. 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단해, 현재 얻게 되는 reward를 해당 state에 나누는 것이다.

    

Off- Policy learning

자신의 policy가 아니라 다른 사람의 policy를 통해서 학습을 하는 것이다. 이는 다음과 같은 관점으로 인해 중요하다.

1. 다른 agent를 관찰하는 것으로부터 배운다.
   • 다른 사람의 policy를(행동을) 따라 하는 것이 아닌, 경험만을 받아 학습해서 새로운 행동을 한다.
2. On policy의 경우에는 경험을 통해 policy를 업데이트를 했다면 사용한 경험은 버린다. 하지만 off policy는 이를 버리지 않고 재사용한다.
3. 탐험적인 행동을 하면서 최적의 policy를 찾을 수 있다.
4. 한 policy를 따르면서 여러 개의 policy를 학습할 수 있다.

Importance Sampling

X는 확률분포 P상에서 sampling 되는 것이고, Q는 P와 다른 확률분포를 의미한다. f(X)는 모든 함수를 넣을 수 있다. (f(X)=x, f(X)=3x...) 따라서 P를 따를 때의 f(X)의 기댓값을 구하고 싶은 것이다. 그런데 이를 이용해서 Q를 사용했을 때의 기댓값을 구하고 싶은 것이다.

이는 확률 분포 P와 Q의 비율을 곱해서 얻을 수 있는 것이다. 이를 Monte-Carlo에 적용해보자.

• Importance Sampling for Off-Policy Monte-Carlo

  • Monte Carlo를 수행할 때, 지나온 모든 행동들에 대해서 비율을 곱해준다.

  • 하지만 µ가 0이면 되면 사용할 수 없고, variance가 엄청 크기 때문에 사실상 사용할 수 없다.

• Importance Sampling for Off-Policy TD

  • 따라서 MC의 단점을 보완하기 위해서 TD를 사용하도록 한다.

Q-learning

Importance learning을 하지 않으면서 off-policy를 사용하기 위한 방법이다. 다음 행동은 behavior policy로 고르고, 다음 state S'에서 action A'은 target policy를 통해서 선택하는 것이다. 즉 다음과 같이 q-function이 업데이트가 된다.

Off-policy control with Q-learning

Q-learning에서는 behavior policy와 target policy를 동시에 improve 할 수 있다. Q-learning에서는 behavior policy μ는 ε-greedy로 target policy π는 greedy하게 선택하도록 한다. 각각 수렴 속도가 느리고, local optima에 빠질 수 있다는 단점을 해결하기 위해 적용된 절충안이다.

따라서 이제 다음과 같이 Q-learning이 진행된다.

1. 현재 state S에서 behavior policy μ( ε-greedy)에 따라 action A를 선택한다.

2. q-function을 이용해서 다음 state S'에서의 action A'은 π(greedy)에 따라 선택한다.

   

3. Q-learning의 target은 다음과 같이 구한다.

4. 다음과 같이 최종 update를 수행한다.

   

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

Model Free Prediction

• Model Free : MDP에 대한 정보가 없는 경우, 즉 environment에 대한 정보를 가지고 있지 않다.

• Prediction : value function을 학습하는 것

즉 Model Free Prediction은 MDP에 대한 정보가 없을 때 value function을 학습해야 하는 문제이고, 다음 장에서 Model Free Control에 대해서 알아보도록 한다.

이번 강의에서 소개한 Model Free Prediction 방법으로 크게 Monte-Carlo Learning(MC), Temporal-Difference Learning(TD)가 있다.

Monte-Carlo Learning

몬테 카를로 방법(다음 부터 MC라 부른다.)은 episode들로 부터 직접적으로 학습한다. 즉 모두 종료가 되는 episode들의 return의 평균을 통해서 학습을 진행한다는 것이다. 그러므로 MC는 완전한 episode들로 부터 학습을 하며 이를 no bootstrapping(추측치로 업데이트 하기)이라고 부른다.

• Goal : Prediction 문제이므로 policy는 π로 정해져 있고, 이를 통해 나온 episode들을 통해 vπ 를 학습하는 것

• return은 Gt=Rt+1+γRt+2+ ... + γT−1RT 와 같이 정의 했으며 vπ(s) = Eπ [Gt | St = s] 로 정의했었다.

MC 방법은 state들을 방문한 것을 바탕으로 다시 크게 First와 Every로 나뉘게 된다.

First- Visit MC Policy Evaluation

terminate까지 도달하기 위해서 state들을 여러번 방문할 수 있는데, , 이때 해당 state에 처음 접한 후 얻은 return 값의 평균을 사용하여 구한다.

Every-Visit MC Policy Evaluation

First와는 달리 state들을 방문할 때마다 return을 계산하고 이를 평균을 내는 방식이다. 보통 first-visit을 사용한다고 한다.

Incremental mean

평균을 구하는 식은 다음과 같이 현재의 값을 뺀 평균의 식으로 바꿀 수 있게 된다. 이를 통해 incremental update를 할 수 있게 된다.

따라서 이를 이용해서 MC 방법에서 V를 계산하는데 사용할 수 있다.

N(S)는 episode를 수행한 횟수에 해당하며 에피소드를 수행하고 나서 v(s)를 바로바로 추정가능하게 된다.

non-stationary 문제의 경우에는 평균을 낼 때 이전의 횟수를 사용하는 것이 아니라 일정한 값인 a로 고정해서 계산을 한다.

Temporal-Difference Learning(TD)

TD방식도 episode들로 부터 직접적인 경험을 하면서 학습을 하는 알고리즘이며 model-free에서 사용한다. 하지만 MC와는 다르게 episode들이 완전히 끝나지 않아도 학습이 가능하며 DP에서 사용하던 bootstrapping 방법을 사용한다. 즉 MC방법과 DP 방법을 적절히 조합한 아이디어라고 할 수 있다. 그리고 추측치에서 다음 추측치를 추정함으로써 업데이트가 가능하다.

MC vs TD

MC와 TD에서 가장 다른 부분은 return Gt이다. MC에서는 종료가 된 episode들로 부터 학습을 하기 때문에 정확한 Gt값을 알 수 있다. 하지만 TD는 그렇지 않기 때문에 return Gt를 추정한 값을 사용해야 한다. 따라서 TD(0)이라고 가정했을 때(뒤에서 이 용어에 대해 자세히 설명한다.),Gt 에 해당하는 부분을 Rt+1+γV(St+1)로 바꿔서 사용하도록 한다.

• 빨간색 term을 TD target이라고 부르고, a 뒤에 있는 항을 TD error라고 부른다고 한다.

TD는 final outcome이 나오기 전에 학습을 할 수 있지만 MC는 결과가 나올 때까지 기다려야 한다. 하지만 TD는 바로바로 학습을 하지만 이 episode가 실제로 종료될 것이라는 보장이 없고, MC는 애초에 끝난 결과를 가지고 학습하므로 확실히 종료된다는 보장을 가지고 있게 된다.

Bias/Varaince Trade-off

v가 실제 Gt에 대해서 unbiased하다고 하면 TD target도 unbiased하다고 할 수 있다. 하지만 TD target은 추정치인 V(St+1)를 사용하기 때문에 bias가 생길 수 밖에 없다.

대신 TD target은 하나의 step에서 계산을 하기 때문에 작은 variance를 가지게 된다. 반면 MC는 episode가 어떤 state sequence로 이루어졌는가에 따라서 value function이 달라지기 때문에 variance가 높게 된다.

즉 종합해보면 MC는 높은 variance를 가지지만 bias가 아예 존재하지 않는다.(정확히 구해진 값들을 사용하기 때문에) 따라서 좋은 수렴 조건을 가지고 있으며, 초기값에 영향을 받지도 않는다.

TD는 낮은 variance를 가지고 있지만 bias가 생기게 된다. 보통 MC보다 더 효과적이고 TD(0)은 수렴을 하지만 항상 그렇다고 볼 순 없다. 또한 초기값에 영향을 받게 된다.

Batch MC and TD

MC, TD 방식 모두 episode를 무한하게 반복하면 실제 value에 수렴할 수 있다. 하지만 batch 방식으로 유한한 episode들을 가지고 학습을 하면 어떻게 될까?

위 예시를 통해서 살펴보도록 한다. 이 예시에서는 8개의 episode들이 있고, 첫번째 episode에서는 A가 reward 0을 받고, B로 가서 reward 0을 받게 된다. 2~7번째 episode들에서는 B에서 reward 1을 받고, 마지막엔 0을 받게 된다.

즉 위 내용을 종합해보면 A는 100% 확률로 B로 가게 될 것이고 이 때 return은 0이 될 것이다.

그러므로 MC에서는 A는 1번 episode에서만 나타나고 이 때 최종 보상이 0이기 때문이다. TD에서는 다른 episode들이 진행이 되면서 A의 value도 같이 업데이트가 될 것이다.

MC는 최종적으로 완료한 episode들의 보상을 사용해서 학습을 하므로 V(A) = 0이 되었다. TD(0) 방식은 max likelihood Markov 방식을 사용하여 수렴하는 알고리즘이기 때문에 V(A) = 0.75가 된다.

이를 보아 TD는 MDP 특성을 가지는 알고리즘이므로 MDP 환경에서 더 유용하고, MC는 그렇지 않기 때문에 MDP가 아닌 환경에서 더 유용하게 된다.

다음은 backup과 bootstrapping에 따른 RL의 분류이다.

TD(λ)

지금까지 설명한 TD들은 TD(0)에 해당하는 것들이었다. 이제 이를 확장해서 TD(λ)로 사용하도록 한다. TD는 guess로 guess를 예측하는 것인데, λ는 steps들에게 얼만큼의 가중치를 부여할지에 대한 값이다. 즉 수식으로 표현하면 다음과 같다.

n=1에 해당하는 것이 우리가 지금까지 보았던 TD(0)에 해당한다. n=2는 G⁽²⁾t와 같이 표현이 될 것이다. 그리고 n이 무한대까지 간다면 이는 종료가 될 때까지 진행한다는 것과 같으므로 MC와 같아지게 된다.

따라서 적당한 n을 잘 선택할 수 있으면 TD와 MC의 장점을 모두 취할 수 있게 된다.

n step에서 n을 고르는 방법은 크게 두 가지 방법이 있다.

• Forward-view TD(λ)

  • MC와 TD의 절충안이 n-step인 것처럼, 여러 개의 n-step을 선택하여 이의 평균을 취하면 각 n-step의 장점을 모두 가질 수 있게 된다. 이 때, 단순히 산술평균을 사용하는 것이 아니라 λ라는 weight를 이용해서 가중 평균을 취하도록하고 이를 Forward-view라고 한다.

    

• Backward-view TD(λ)

  • 이제는 다시 forward-view TD(λ)에서 time-step마다 update할 수 있는 방법을 알아본다. 여기서 eligibility trace라는 개념이 나오게 된다. 이는 과거에 방문했던 state 중에서 현재 얻게 되는 reward에 영향을 주는 state를 판단해, 현재 얻게 되는 reward를 해당 state에 나누는 것이다.

  • 이 때, 영향을 준 것 같은 idx를 credit이라고 하고, 이 credit을 배정할 때 다음 두 개를 사용한다.

    • Frequency heuristic, Recency heuristic

Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

3. Planning by Dynamic Programming

• Model Free : environment에 대한 정보를 가지고 있지 않을 경우
• Model Based : environment에 대한 모델이 있는 경우
  • 이러한 경우에 대해서 Planning, Dynamic Programming을 사용한다.

Introduction

• What is Dynamic Programming?

  알고리즘 문제 기법에서 사용하는 DP, 동적 계획법과 같은 뜻을 가지고 있다. 복잡한 문제에 사용하는 방법으로써 문제를 여러 subproblem으로 쪼갠 뒤에 이 문제를 해결하고 합쳐가면서 풀어가는 방식이다.

  • 다음과 같이 두 가지 특성을 가지는 문제에 대해서 DP를 사용하는 것이 일반적이다.
    • Optimal substructure
      • Optimal한 해는 subproblems들로 분해될 수 있다는 것이다.
    • Overlapping subproblems
      • Subproblem 들이 많이 사용되어서 이를 저장해두었다가 사용할 수 있다.
  • MDP는 위 두 가지 속성을 가지고 있으므로 DP를 사용할 수 있다.
    • Bellman equation은 재귀적으로 분해가 가능하고, value function은 해를 저장하고 재사용할 수 있도록 한다.

• Planning by Dynamic Programming

  DP는 MDP의 모든 것을 알고 있다고 가정한다. 즉 Planning 문제를 해결하는 것이다.

  DP는 크게 두 가지 방법으로 나뉘게 된다.

  • Prediction
    • value function을 학습하는 것
    • MDP, policy가 있을 때 그 policy를 따를 경우의 value function이다.
    • policy evaluation 문제
  • Control
    • optimal 한 policy를 찾는 문제
    • MDP만 있고 optimal 한 policy를 찾아야 한다.
    • policy Iteration, value Iteration

Policy Evalutation

주어진 policy를 평가하는 문제, 이 policy를 따라 간다면 return을 얼마 받는가. 즉 value function을 찾는 문제

초기 value 값을 랜덤하게 초기화 한 후 Bellman Equation을 이용해서 다음 상태 s'를 이용해서 각각의 상태 s의 value 값을 반복적으로 업데이트 한다. 이 때 synchronous backup을 사용한다.

Example

위와 같이 계속해서 반복하다보면 정책이 수렴하는 것을 알 수 있다.

Policy Iteration

위와 같이 반복적인 업데이트를 통해서 모든 상태 s에 대해 value 값을 구할 수 있다.(Evaluate) value 값이 최대가 되는 방향으로 greedy하게 행동하면 초기에 만들었던 Random한 Policy를 개선된 Policy로 만들 수 있다.(Improve) 위와 같은 예시에서는 금방 최적의 Policy로 찾아가는 것을 알 수 있다.

따라서 일반적인 경우에는 Policy를 evaluation해서 value들을 구하고, 그 value들을 바탕으로 Policy를 improvement하는 방향으로 발전시키면 된다.

그런데 과연 greedy 하게 정책을 개선시키는 것이 성능을 항상 좋게 만들까?

다음과 같은 이유들로 항상 그렇다고 하며, 수렴을 하는 포인트는 optimal 하다고 한다.

• Modified Policy Iteration

  하지만 꼭 수렴할 때까지 계속해서 반복해서 진행해야 하는가? 에 대한 의문을 가질 수 있다. 실제로 무한히 반복해서 수렴할 때까지 진행을 하지 않고, k번을 반복해서 그 점을 사용해도 충분히 합리적으로 사용할 수 있다고 한다.

Value Iteration

Value Iteration은 Policy Iteration과는 다르게 Bellman Optimal Equation을 이용하는 것이다.

• Deterministic Value Iteration
  • subproblem의 solution을 알면 Bellman Optimal Equation을 이용해서 s에서의 solution을 알 수 있다.
  • 이러한 반복을 계속해서 한다.
• 아래는 위의 Grid world의 Value Iteration을 적용한 것이다.

• 반복해서 진행하면 세번째 iteration에서 converge 하는 것을 알 수 있다.

Summary of DP Algorithms

*Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

Markov Decision Process을 지난 강의에서 배웠던 내용으로 설명하면, 강화학습을 위해 환경을 완전하게 알고 있는 것을 의미한다. 즉 full observable해야 한다. 이러한 이유로 RL의 거의 모든 문제는 MDP로 설계가 되어 있고, MDP하지 않다면 MDP하도록 조건을 더 추가시켜줘야 한다.

Markov Property

이전 강의에서 잠시 다뤘던 내용이다. "Markov하다" 라는 것은 다음 상태는 과거 상태에는 독립적이고 현재 상태에만 종속을 한다는 것이다. 즉 다음과 같다.

예시로 설명하면 다음과 같다. 현재 내가 장기(체스)를 두고 있다고 하자. 그러면 지금 현재 기물들이 어떻게 놓여져 있는지가 다음 수를 두는 것에 영향을 줄 뿐, 이전에 어떻게 움직였는지는 전혀 다음 수에 도움이 되지 않는다.

State Transition Matrix

Markov를 설명하기 위해 도움이 되는 정의 중 하나이다. state transition probability는 Markov한 state s에서 다음 상태 s'으로 이동할 확률을 뜻하고, Matrix는 이러한 확률을 행렬꼴로 모아둔 것이다.

Markov Process

앞으로 다룰 Markov 대한 성질들의 가장 기본이 되는 과정이다. memoryless random process라고 하는데, 이는 Markov의 특징을 말하는 것이다. Markov Process는 <S,P>로 정의되고, S는 state들의 집합, P는 state transition probability matrix이다. 다음은 아기가 잠에 드는 과정을 도식화한 것이다.

여기서 각 행동은 다 타원형으로 표시되어 있고, '잔다' 라는 상태만 네모로 표시되어 있는데 이는 terminate state, 종료 상태를 의미한다. 각 행동으로 이동하는 화살표에 확률이 써져 있는데, 아직은 모든 상태는 확률에 의해서만 바뀐다. 즉, '눕는다.' 라는 상태에서는 70% 확률로 논다. 라는 상태로 이동하고, 30%으로 확률로 잠에 들기 시작하는 상태로 이동하는 것이다.

상태를 이동하는 상황이 여러가지 있는데 이들을 episodes라고 부른다.

Markov Reward Process

Markov Process에 Reward function이 추가된 개념으로 <S,P,R,r>와 같으며 R은 reward function으로 R_s=E[R_t+1|S_t=s]이고, r 은 감쇠인자로써, 0과 1 사이의 값을 가진다. 이 단계에서 새로 정의되는 개념들이 있어 이를 정리하고 진행한다.

Return

return Gt는 t 시간이 지난 뒤에 얻은 총 보상을 의미한다. 

• Why discount? 감쇠인자를 사용하는 이유는 무엇일까?
  • 수학적으로 편리하다. 감쇠 인자를 0과 1 사이의 값으로 설정을 했기 때문에 return 값이 무한히 커지는 것을 막을 수 있다. 즉 bounded하게 만들 수 있다.
  • 사람이 선호하기 때문이다.
    • 만약 누군가 당신에게 지금 커피를 사줄지? 아님 10달 뒤에 커피를 사줄지 물어볼 수 있다.
      • 대부분 지금 사달라고 할 것이다.
  • 불확실성을 표현하기 위해서
    • 위의 예시로 생각하보면 지금 사달라고 선택을 하는 이유가 10달 뒤에 진짜 커피를 사줄지는 불확실했기 때문일 것이다.

Value Function

value function은 현재 상태 s로 부터 시작했을 때 return의 기댓값을 의미한다.

지금까지 예시에서 감쇠인자 값을 0이라 가정했을 때, 다음과 같이 value function 값이 구해진다.

지금은 state들이 단순해서 충분히 손으로도 계산을 할 수 있지만 더 많은 state들이 복잡하게 연결된다면 손으로 하는 것은 어렵게 될 것이다. 따라서 이를 위해 Bellman Equation이라는 것을 사용한다.

Bellman Equation

value function을 다음과 같이 표현할 수 있다.

Bellman Equation으로 value function을 그림으로 표현하면 다음과 같다. 현재 상태의 value function은 현재 보상을 받은 뒤(Rs)에 다음 상태들의 value function 합(sigma Pss'v(s'))에 감쇠 인자를 곱한 값을 얻는다는 것이다.

 따라서 이와 같이 value function으로만 구성된 식을 matrix form으로 변환한다면 역행렬을 통해서 한번에 구할 수 있게 된다.

하지만 이 연산은 O(n^3)에 해당하는 복잡도를 가지고 있다. 따라서 작은 MRP에서만 계산이 가능하고, 큰 경우는 DP, Monte-Carlo 방법등으로 구하게 된다.

Markov Decision Process

Markov Reward Process에서 action이 추가된 단계이다. <S,A,P,R,r>와 같이 정의 하며 A는 action들의 집합을 의미한다.

또한 action이 추가되었기 때문에 상태천이행렬 P와, reward function R에 a에 관한 식이 들어가게 되었다. 따라서 슬라이드에서 소개한 내용에 action을 추가하면 다음과 같다.

그리고 Action이 생김에 따라서 몇 가지 용어를 정의해야 한다.

Policy

정책 π 는 현재 주어진 상태에서 action a를 수행할 분포를 의미한다.

따라서 정책은 agent 행동을 정의한다고 할 수 있다. 그리고 이 정책을 이용해서 상태천이행렬 P와 reward function R을 다음과 같이 다시 정의할 수 있다.

Value Function

• state-value function

state value function은 현재 상태 s가 주어졌고, 정책을 따른다고 했을 때 얻을 수 있는 return의 기댓값을 의미한다.

• action-value function

action value function은 현재 상태가 s이고, action a를 한다. 그리고 정책을 따른다고 했을 때, 얻을 수 있는 return의 기댓값을 의미한다.

Bellman Expectation Equation

위에서 정의했던 state value function과 action value function을 Bellman equation을 사용하기 위해서 Immediate reward와 future reward 형태로 분해할 수 있게 된다.

하지만 위 식으로는 실제로 구현을 하는 것이 힘들기 때문에 직접 구현을 위해 조금 더 명백한 형태로 변형이 필요하게 됩니다.

 위 그림에서 흰색 원은 state를 의미하고, 검은색 원은 action을 의미합니다. 위 그림을 해석해 보면 현재 상태 s에서 가능한 action들은 2개가 있는 것입니다.(실제로는 더 많은 검은색 점이 있을 수 있습니다.) 그러면 agent가 선택한 당시의 정책에 따라 action을 할 확률이 정해질 것이고, 그 때마다 action-value function을 구할 수 있게 됩니다. 

 따라서 위 그림으로 보아 우리는 현재 state s에서의 state value function을 구하기 위해서 각 action을 할 확률(정책)과 그 action에서 발생하는 value state function을 곱한 것들의 합으로 표현을 할 수 있게 됩니다.

즉 다음과 같이 식을 얻을 수 있습니다.

하지만 아직 이 형태로는 현재 state value function과 다음 state value function과의 관계를 알 수 없습니다. 그러므로 action value function에 대해서 식을 전개해보도록 하겠습니다.

state s에서 action a를 했을 때의 그 action에 대한 value는 두 가지로 나뉘게 됩니다. state s에서 action a를 했을 때의 reward와 그 다음 state의 value function입니다. 그런데 이 중 다음 state value function은 다음 시점의 value function이므로 감쇠 인자를 적용시켜줘야 합니다. 또한 상태가 변한 것이므로 상태 전이 확률도 적용시켜줘야 합니다. 따라서 다음과 같이 식을 구성할 수 있습니다.

따라서 위 두 내용을 모두 한 번에 합치면 다음과 같이 됩니다.

지금까지 state value function을 설명하기 위해 전개를 한 것처럼 이를 action value function을 설명하기 위해 전개를 진행하면 다음과 같이 됨을 알 수 있습니다.

이제 식을 state, action value function 하나씩으로만 표현을 할 수 있기 때문에 이전에 matrix form으로 변경해서 구했떤 것처럼 구할 수 있게 된다.

Bellman Optimal Equation

강화학습은 기본적으로 최대의 보상을 얻는 정책을 찾는 것을 목표로 하고 있기 때문에 얻을 수 있는 기댓값보다는 최대 보상을 얻을 수 있는 것이 더 중요합니다. 따라서 앞서 정의했던 value function들을 다음과 같이 정의할 수 있습니다.

위의 식으로 optimal한 value function을 구할 수 있다면 주어진 state에서 value가 가장 높은 action을 선택할 수 있고, 이를 통해서 optimal한 정책을 구할 수 있게 됩니다. optimal한 값을 항상 얻도록 만들어야 하므로 다음과 같이 정책을 수식을 적을 수 있습니다.

앞서 Expectation Equation에서 진행했던 것처럼 Optimal도 진행을 할 수 있고 다음과 같이 얻을 수 있다.

하지만 Bellman Optimality Equation은 max 연산때문에 non-linear하다. 그렇기 때문에 일반화된 해법을 제공할 수는 없고, 이를 위한 여러가지 다른 방법들을 제시한다.

• Value Iteration
• Policy Iteration
• Q-learning
• Sarsa

*Youtube에 있는 David Silver의 Reinforcement Learning 강의를 보고 작성하였습니다.

강화학습은 여러 분야에서 사용가능하다. 컴퓨터 과학, 공학, 수학, 경제학 등 여러 분야에서 사용 가능하다.

• 머신러닝은 지도 학습, 비지도 학습, 강화 학습 세 분야로 나눌 수 있는데, 강화 학습에 대해 자세히 알아보도록 한다.

• 강화학습이 다른 머신러닝 분야들과 다른점은 무엇일까?

  • supervisor가 존재 하지 않는다.(y 값이 존재하지 않는다.) 대신 reward라는 값이 존재한다.
  • Feedback을 바로 받는 것이 아니라 일련의 행동들이 모두 마친 뒤에 나타난다.
  • 내가 이전에 한 행동에 따라 결과가 바뀌게 된다. 즉 시점에 따라 행동이 다르다.
  • agent의 행동에 따라 얻는 데이터가 달라지게 된다. (agent는 뒤에 다시 소개한다.)

• 강의에서 다음과 같은 예시들을 소개하고 있다.

  • Fly stunt manoeuvres in a helicopter(자율주행)
  • Defeat the world champion at Backgammon(유럽의 보드게임)
  • Manage an investment portfolio(주식)
  • Control a power station(발전소 관리)
  • Make a humanoid robot walk(로봇이 걷도록 하는것)
  • Play many different Atari games better than humans(알파고(Atari 게임))

• Reward (Rt)

  • scalar 피드백 값, 얼마나 agent가 t 단계에서 잘 수행했는지를 나타낸다.
  • agent의 임무는 누적 보상을 최대화 하는 것.
  • 강화 학습은 reward hypothesis에 기반을 두고 있다.
    • reward hypothesis?
      • 기대 누적 보상을 최대화하는 것이 agent의 목표이다.

• Sequential Decision Making

  • Goal : 총 reward를 최대화 하는 행동을 고르는 것.
  • 행동은 긴 기간 동안 연속적으로 발생하며 보상은 이 행동들이 마친 뒤에 얻게 된다.
  • 이로써 나중에 더 큰 보상을 얻을 수 있다면 지금 당장은 적은 보상을 선택하거나 손해를 볼 수도 있음을 의미한다.

Agent and Environment

• agent
  • environment의 observation, reward를 받아서 agent가 action을 수행한다.
• Environment
  • agent의 action을 받아서 바뀐 observation, reward를 agent에 전달해준다.

즉 agent는 사람, envionment는 지구로써 사람이 어떤 행위를 취하면 지구에 영향을 주게 되고 지구의 환경에 변하며 이는 다시 사람에게 영향을 주게 된다.(지구 온난화?)

History and State

• history는 observation, actions, rewards를 일련적으로 표현한 것.

• state는 다음에 어떤 것을 해야 하는지 결정에 도움을 주는 정보, 이 것은 history에 특정한 함수를 취함으로써 얻는다.

Environment state and Agent State

agent, environment가 각각 가지고 있는 상태, 정의상으로는 agent state는 알고 있지만 envionment state는 모른다.( ex) 사람은 자신의 정보를 바탕으로 행동을 하지만, 그렇다고 지구의 환경이 어떻게 변할지는 예측할 수 없다.(또는 매우 힘들다)

Markov state(information state)

'Markov하다' 라는 정의로 미래는 과거에 어떤 상태였는지는 관계 없이 현재 상태만이 영향을 준다는 것이다. 다음 강의에서 Markov에 대해서 자세히 설명하기 때문에 이번엔 정의만 보고 넘어간다.

• Full observability : agent가 agent state, environment state를 모두 아는 것, 이러한 경우에 Markov decision Process라고 부르며 다음 강의에서 자세히 다룬다.

RL's major components

• Policy
  • agent의 행동을 의미한다. 어떤 현재 상태에 있을 때 어떠한 행동을 할지를 나타낸다.
  • 결정론적 정책
    • 상태 s에 도달하면 항상 a라는 행동을 한다.
  • 통계학적 정책
    • 상태 s에 있을 때 일정한 확률에 따라 특정한 행동 a를 한다.
• Value Function
  • 미래 reward의 예측을 하는데 사용한다.
  • 이 값으로 상태가 좋은지/나쁜지 판단할 수 있다.
• Model
  • 환경에 다음에 어떠한 것을 할 지 예측하는 것
  • 즉 다음에 어떤 상태가 발생되고, reward가 발생하는지 알려준다.

Categorizing RL agent

• Value Based
  • Value Function
• Policy Based
  • Policy
• Actor Critic
  • Policy
  • Value Function
• Model Free
  • Policy and Value Function
• Model Based
  • Policy and Value Function
  • Model

Learning and Planning

• Reinforcement Learning
  • 환경은 초기에 알려져 있지 않다.
  • agent는 환경과 상호작용한다.
  • agent는 정책을 발전시킨다.
• Planning
  • 환경의 모델을 알고 있다.
  • agent는 그 모델에서 계산을 수행한다.
  • agent는 정책을 발전 시킨다.

Exploration and Exploitation

• Exploration(탐험)
  • 탐험은 전체 공간을 골고루 찾아보는 전략이며 항상 같은 방향으로 진행하지 않는다.
• Exploitation(탐사)
  • 탐사는 특정한 곳 주위를 집중적으로 찾아보는 전략으로 보상이 최대화 되는 방향으로만 진행한다.
• 이들은 trade-off 관계에 있으며, 탐험은 시간이 너무 오래 걸리고, 탐사는 지역 최적해에 머무는 문제가 발생한다.

https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ

강화학습으로 가장 유명한 알파고가 있으며 알파고를 만든 회사인 deepmind에서 David Silver가 강화학습에 대해 강의한 자료를 제공하고 있다. 따라서 이 강의를 보면서 정리한 내용들을 앞으로 올려보도록 한다.

https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PLqYmG7hTraZDM-OYHWgPebj2MfCFzFObQ