Contents

  • TOC {:toc}

Ch1. 강화학습이란?

강화학습 모델은 agent, action, reward, environment 4가지로 구성된다. environment는 어떠한 state를 갖으며 agent의 action에 대해서 적절한 reward를 준다. 현재의 state를 바탕으로 미래에 최대의 reward를 얻을 수 있는 action을 찾는 것이 강화학습의 목표이다.

  • action value : 어떤 action()에 대한 reward()의 기댓값이다.

agent는 실제 를 구할 수 없기 때문에 근사 를 계산한다. agent가 선택할 수 있는 action은 2가지로 분류할 수 있다.

  • exploration : 각 action value를 추정하기 위해서 여러 action들을 시도해보는 것
  • exploitation : 이전의 exploration을 바탕으로 최적의 action을 선택하는 것

-greedy policy : 의 확률만큼 exploration을 하고 나머지 의 확률만큼 exploitation을 하는 전략

  • 계산법 (sample mean)

강화학습 문제는 stationary problem과 non-stationary problem으로 구분된다. stationary problem은 action 이후에 가 달라지지 않지만 non-stationary problem에서는 가 달라질 수 있다. 따라서 non-stationary problem에서는 최근 얻은 reward에 더 높은 가중치를 부여하는 것이 유리하다.

  • 계산법 (exponential moving average)

을 ()로 고정하여 최근의 reward에 더 높은 가중치를 부여한다. 다만 항 설정이 필요해진다.

MDP (Markov Decision Process)

MDP는 강화학습에서 문제를 정의하는 구조이다. MDP에서 state transition과 reward를 얻는 것은 Markov property를 따른다. MDP는 다음 수식과 같이 나타낼 수 있다.

MDP에서는 agent의 policy()에 따라 action()이 결정된다. environment에서는 agent의 action에 따라 적절한 reward()를 제공하며 time step 단위로 state transition이 발생한다. 은 다음 state를 의미한다. 위 식에서는 action과 state transition을 probabilistic하게 나타냈지만 함수 형태로 표현하여 deterministic하게 나타낼 수도 있다. policy의 경우 로 state transition은 일반적인 함수의 형태 처럼 표현한다. reward 역시 probabilistic하게 표현하는 것이 가능하다.

이러한 규칙에 따라 state, action, reward가 결정되는 것을 시간 흐름에 따라 나타낼 수 있다.

강화학습 문제는 크게 planning problem과 learning problem(online problem)으로 구분할 수 있다. 강화학습 모델에서 environment에 속하는 reward나 state transition의 function이나 probability들을 environment model이라고 한다. planning problem은 이러한 environment model이 주어진 문제를 말한다. 반면 learning problem은 environment model이 주어지지 않아서 agent가 trial and error를 통해 직접 데이터를 수집하여 추정해야하는 문제를 말한다.

강화학습 알고리즘에서 environment model을 사용하면 model-based method라고 하고 사용하지 않으면 model-free method라고 한다.

policy의 성능을 평가하기 위해서 state-value function()을 정의한다.

는 return으로 앞으로 받을 rewards를 나타낸다. 는 discount rate로 사이의 값으로 설정할 수 있다.

MDP에서 적어도 하나의 optimal state-value function()이 존재한다. 는 deterministic하며 모든 state에 대해서 다른 policy 보다 같거나 더 높은 기댓값을 갖는다.

state-value function에 action 조건을 추가하여 action-value function(Q-function)을 정의한다. Q-function은 에서 조건인 action을 택하고 그 이후부터 policy를 따를 때 return의 기댓값이다.

MDP에서 다루는 문제는 episodic task와 continuous task로 나눌 수 있다. episodic task는 종료 시점이 존재하여 episode 단위로 종료 이후 새롭게 진행이 되는 문제이다. 반면 continuous task는 종료 시점이 존재하지 않는 문제를 지칭한다.

MDP에서 observation은 environment에 대한 부분적인 정보를 의미한다. 반면 state는 environment에 대한 완전한 정보를 의미한다. POMDP(Partially Observable Markov Decision Process)는 state를 알 수 없어서 observation을 통해 action을 결정해야하는 MDP의 확장된 형태이다.

강화학습 알고리즘은 크게 policy-based methods와 value-based methods와 두 가지 방법을 모두 사용한 methods로 나눌 수 있다. policy-based methods는 policy 자체를 모델링하는 방법이고 value-based methods는 policy를 평가하는 state-value function이나 Q-function을 기반으로 policy를 간접적으로 도출하는 방법이다. 먼저 value-based methods를 기반으로 한 방법들을 소개한다.

Bellman equation

state-value function에서 Bellman equation을 유도할 수 있다.

마찬가지로, action-value function에서 Bellman equation을 유도할 수 있다.

적어도 하나의 optimal state-value function이 존재하므로 그에 대응되는 Bellman optimality equation(optimal action-value function)이 존재한다. optimal state-value function의 policy는 deterministic하기 때문에 Bellman optimality equation을 다음과 같이 나타낼 수 있다.

각 state에 대한 Bellman optimality equation 값을 미지수로 생각하면 state의 개수만큼의 연립 방정식이 나온다. 연립 방정식의 해를 구하여 각 state에 대한 Bellman optimality equation 값을 구할 수 있다.

이를 통해, optimal policy를 다음과 같이 나타낼 수 있다.

를 통해서 최선의 action을 찾기 때문에 위 표현을 greedy policy라고 한다.

Bellman optimality equation을 통해 optimal policy를 구하는 것은 만큼의 연산이 필요하기 때문에 실용적이지 않다. 따라서 이를 대체할 다른 방법이 필요하다. 먼저 optimal policy를 구하는 과정(policy control)을 policy의 성능을 평가하는 policy evaluation과 이를 바탕으로 policy를 개선하는 policy improvement로 나누어 접근한다.

다음은 dynamic programming(DP)를 이용해서 policy evaluation을 하는 방법이다.

다음 state의 를 이용하여 현재의 을 갱신하는 방법이다. 모든 state에 대해 해당 과정을 반복하면 가 에 가까워 진다. 여러 를 통해 을 갱신하는 것을 bootstraping이라고 한다. bootstraping 과정에서 대신에 를 사용할 수도 있다.

Q1. DP를 이용한 policy evaluation의 원리

다음은 policy evaluation을 바탕으로 policy improvement를 하는 과정이다.

다음과 같이 를 갱신하면 가 성립한다.

Q2. 탐욕화를 하면 왜 policy가 개선되는가? (policy improvement theorem)

따라서 policy evaluation과 policy improvement를 번갈아 실행하면 policy가 optimal policy에 가까워진다. 이러한 방식을 policy iteration이라고 한다.

policy iteration의 한 가지 특징은 모든 state에 대해서 policy evaluation과 policy improvement를 진행하지 않아도 policy가 개선된다는 점이다. 이를 generalized policy iteration이라고 하는데 이 점을 이용하여 딱 하나의 state에 대해서 evaluation과 improvement를 진행하여 개선을 이루는 value iteration이라는 방법을 도출할 수 있다.

policy improvement를 먼저 진행하면 policy evaluation에서 가 아닌 를 사용할 수 있게 되며 다음과 같이 식을 표현할 수 있다.

value iteration을 반복하면 가 에 가까워진다. 이렇게 구한 를 통해 optimal policy를 구하면 된다.

policy iteration이나 value iteration은 planning problem에만 적용할 수 있다. 따라서 learning problem에서는 policy를 evaluation하고 improvement하는 다른 방법이 필요하다. episodic problem에 대해서 이를 해결하는 방법을 소개한다.

먼저 policy evaluation을 하는 방법이다. state-value function과 Q-function을 Monte Carlo method를 통해 구할 수 있다. 정책 를 따라 종료 조건까지 탐색을 진행한다.

state-value function으로는 policy improvement가 불가능하기 때문에 learning problem에서는 Q-function으로 policy evaluation을 해야된다. 하나의 episode가 끝난 후 를 갱신하고 policy improvement를 하면 를 얻을 확률이 달라지므로 non-stationary problem이다. 따라서 sample mean보다는 exponential moving average를 사용해서 기댓값을 추정하는 것이 유리하다.

다음은 policy improvement를 할 차례이다.

greedy policy를 적용하면 이후 최적화 과정에서 모든 state에 대한 탐색이 안될 수 있다. 따라서 약간의 randomness를 추가한 -greedy policy를 사용한다.

* 는 에서 가능한 action의 개수이다.

-greedy policy를 사용하게 되면 탐색 과정에 randomness가 들어가므로 원래 구하고자 하는 optimal policy와 차이가 발생한다. 따라서 이를 보정해줄 방법이 필요하다.

강화학습에서 policy는 목적에 따라서 target policy와 behavior policy로 구분할 수 있다. behavior policy는 실제 environment와 상호작용을 통해 데이터를 수집할 때 따르는 policy이고 target policy는 behavior policy를 통해 모은 데이터를 바탕으로 improvement를 진행하는 policy이다.

학습 모델의 설계에 따라 target policy와 behavior policy는 동일하거나 다를 수 있다. 하나의 policy를 통해 데이터 수집과 improvement를 모두 수행하는 것을 on-policy라고 한다. 지금까지 소개한 학습 방식은 모두 on-policy에 속한다. 반면 off-policy는 두 policy를 구분하여 학습을 진행한다.

off-policy를 이해하기 위해서는 importance sampling에 대한 이해가 필요하다. importance sampling은 어떤 확률 분포에 의한 기댓값을 다른 확률 분포에 의한 기댓값으로 구하는 것을 말한다.

예를 들어 에 대한 의 기댓값을 에 대한 기댓값으로 구하고 싶다면 에 적절한 가중치 를 곱해주면 된다.

importance sampling으로 기댓값을 구할 때 Monte Carlo method를 사용하면 와 의 차이가 클수록 추정 기댓값의 분산이 커진다. 따라서 더 적은 샘플로 더 정확한 추정을 하고 싶다면 와 가 비슷한 것이 좋다.

importance sampling을 action-value function에 적용하면 다음과 같아진다. 는 behavior policy이고 는 target policy이다.

이때, trajectory는 에 따라 이루어진 action과 그에 따른 state transition의 연속이다. 는 종료 시점의 state를 의미한다.

Q3. 왜 가 trajectory가 발생할 확률의 비가 되는가?

따라서

target policy에 대한 action value function을 구할 수 있게 된다. 이를 통해 behavior policy는 -greedy policy로 target policy는 greedy policy로 policy improvement를 진행하면 더 나은 optimal policy를 구할 수 있다.

Monte Carlo method 기반 policy evaluation의 문제점은 목표에 도달해야 state-value function(Q-function)의 갱신이 가능하다는 점이다. continuous task를 해결하는데 사용할 수 없고 목표에 도달하기까지의 trajectory가 길어질 수록 학습 결과가 불안정해질 수 있다.

이를 해결하기 위해서 TD method(Temporal Difference method)을 사용한다. TD를 기반으로 한 학습 방법에는 SARSA와 Q-learning이 있다. SARSA는 Bellman equation을 바탕으로 하고 Q-learning은 Bellman optimality equation을 바탕으로 한다.

TD method는 agent가 생성한 experience data를 바탕으로 학습이 진행된다.

먼저 TD method가 무엇인지 설명하겠다.

이때, exponential moving average에서 갱신시키는 대상()을 TD target이라고 한다. 실제 policy control까지 이어지기 위해서는 Q-function에 적용이 필요하다.

위에서는 까지 조사하여 Q-function에 반영했지만 n-step TD로 확장하여 다음과 같이 TD target을 둘 수도 있다. 의 경우 Monte Carlo method를 사용한 것과 같다.

TD를 바탕으로 위와 같이 policy evaluation을 진행하고 policy improvement를 진행하는 것을 SARSA라고 한다. SARSA는 에서 그 이름이 붙었다. on-policy SARSA는 -greedy policy를 바탕으로 policy improvement를 진행하면 된다. off-policy SARSA는 importance sampling을 바탕으로 behavior policy에는 -greedy policy를 적용하고 target policy에는 greedy policy를 적용하면 된다.

다음은 Q-learning이다. Q-learning은 Bellman optimality equation을 바탕으로 하며 off-policy로 학습이 진행된다. off-policy로 진행되기 때문에 behavior policy는 아무것이나 사용해도 좋다.

Q4. Q-learning의 증명

모델의 구현 방식은 distribution model과 sample model이 있다. distribution model은 조건에 따른 모든 확률 분포를 저장하는 방식이고 sample model은 주어진 조건에 대해 적절한 변수를 샘플링만 하는 방식이다.

신경망을 통해 Q-function을 구현할 수 있다. 구현하는 방식에는 state를 입력으로 받고 모든 action에 대한 Q-function 값을 출력으로 하는 방식과 state와 action을 입력으로 받고 대응되는 Q-function 값을 출력으로 하는 방식이 있다. Q-learning의 경우 next state의 max를 구해야하기 때문에 첫 번째 방식으로 구현하는 것이 유리하다.

Q-learning 식의 의미를 생각하면 Q함수를 에 가깝게 이동시키는 것이기 때문에 둘을 비교(MSE)하는 함수를 loss function으로 사용할 수 있다.

Ch2. DQN (Deep Q Network)

DQN의 이전의 Q-learning 바탕의 심층 강화학습은 크게 2가지 문제점이 있었다. 첫번째는 experience data 사이의 의존성에 따른 학습 편향이다. behavior agent가 이동한 순서대로 학습이 진행되므로 편향이 발생한다. 두번째는 Q-function을 갱신하는 과정에서 TD target이 계속 변화한다는 점이다. 추정치로 추정치를 갱신하는 것이기 때문에 갱신 과정에서 자꾸 TD target이 바뀌게 되면 학습이 불안정해진다. DQN에서는 이러한 문제들을 experience replay와 target network를 도입하여 개선했다.

experience replay의 아이디어는 간단하다. behavior agent가 탐색을 하는 동안 만들어진 experience data()를 queue에 저장하고 탐색을 마친 후에 random sampling을 통해 데이터를 추출하여 target agent를 학습시킨다. experience replay는 데이터를 반복 추출하여 학습 효율성을 높일 수 있는 장점도 갖는다.

target network는 기존의 target agent 신경망() 외에 동일한 구조의 target network(를 추가하는 방법이다. target network는 TD target을 계산할 때만 사용하며 일정 횟수의 episode 간격으로 target agent 신경망과 가중치를 동기화시킨다. target network를 통해 TD target이 고정되므로 학습이 안정화된다.

다음으로 DQN에서 추가적인 개선을 이루어낸 기법을 소개하겠다.

PER(prioritized experience replay)은 말 그대로 experience data에 우선순위()를 부여한 것이다. 우선순위는 target TD와 Q-function의 차이이므로 우선순위가 크면 클수록 모델이 학습을 해야할 필요가 큰 데이터가 된다.

기존의 experience data에 우선순위를 추가하여 queue에 저장한다.

queue에 n개 데이터가 들어있다고 할 때 특정 experience data 가 뽑힐 확률은 다음과 같다.

PER은 더 중요한 데이터를 먼저 학습하여 수렴 속도를 높히는 효과가 있다.

Double DQN은 DQN에서 발생하는 overestimation을 완화시키기 위해 등장한 방법이다. DQN의 overestimation은 max 연산자에 의해 발생한다. 모델이 예측한 Q-function은 예측값이기 때문에 오차가 포함되어 있는데 최대값을 뽑으면 실제로 더 좋은 action이 아닌데 좋게 평가되는 overestimation이 발생한다.

Double DQN에서는 target agent의 Q-function에서 최대가 되는 action을 골라서 target network에서 Q-function 값을 구하는 방식으로 overestimation을 개선했다. 두 모델의 예측값에 포함된 오차가 서로 독립이라고 하면 target agent의 Q-function에서 최대가 되는 action을 바탕으로 target network에서 Q-function 값을 구할 때 오차에 의한 편향이 줄어든다.

Dueling DQN은 Q-function을 advantage function()과 state-value function()으로 나누어 학습시키는 방식이다. advantage function은 action을 취했을 때와 policy대로 움직였을 때 return 기댓값의 차이이다. advantage function과 state-value function 각각이 개별 신경망으로 구성되어 더해지는 구조로 되어있다.

Dueling DQN을 도입하면 어떤 state에서 특정 action을 했을 때만이 아니라 state 자체에 대한 학습도 이루어지기 때문에 더 나은 성능을 보인다.

-decay는 학습이 진행됨에 따라 값을 점차 감소시키는 기법이다. 학습이 진행될수록 신경망이 optimal Q-function에 가까워질 것이기 때문에 탐색을 줄이는 것이 학습에 더 유리할 것으로 기대할 수 있다.

Ch3. Policy gradient

policy gradient는 policy를 신경망으로 모델링하는 policy-based method이다.

신경망의 출력은 softmax를 통과하여 각 action space에 속한 action들의 확률이 나오도록 한다. action space가 continuous한 경우도 action 자체를 샘플링하도록 하거나 정규분포의 평균을 추정하도록 하여 처리할 수 있다.

가 policy 를 따를 때 발생하는 trajectory라고 할 때

이때 의 gradient는 다음과 같다.

따라서 다음과 같이 매개변수를 갱신하면 된다.

시점 에서 policy를 평가할 때 이전 시점의 reward를 사용하는 것은 불필요하기 때문에 가중치 를 곱하는 것보다 를 곱하는 것이 더 나은 성능을 보인다. 대신 를 곱하는 학습 방식을 REINFORCE 알고리즘이라고 한다.

말고 나 를 사용하는 알고리즘도 있다.

에 대한 임의 함수 에 대하여

왜냐하면

따라서 대신 를 사용해도 식이 성립하며 이렇게 를 빼는 기법을 baseline이라고 한다.

는 임의 함수가 올 수 있지만 를 다른 신경망을 이용해 만든 state-value function 로 둔 모델을 Actor-Critic 알고리즘이라고 한다. Actor-Critic 알고리즘은 value-based method와 policy-based method를 동시에 활용하는 방식이다.

action space가 continuous한 경우에 Q-learning 기반 알고리즘은 사용하기 어려운데 반해 policy gradient 기반 알고리즘은 적용이 가능하다. policy gradient 기반 알고리즘은 policy에 비해 가치 함수가 복잡한 경우에 효과적이다. Q-learning은 학습 과정 중에 Q-function 신경망의 가중치가 변화함에 따라 action이 급격하게 바뀌게 될 수 있지만 policy gradient는 policy 자체를 학습하기 때문에 action이 부드럽게 변화한다는 장점이 있다.

Ch4. 더 발전된 알고리즘 소개

policy gradient 기반 알고리즘

A3C나 A2C같은 분산 학습 알고리즘이 있다. 분산 학습 알고리즘은 서로 독립적인 environment에서 서로 다른 state로부터 학습을 진행하는 방법이다. 서로 다른 agent에서 얻은 기울기를 사용하여 비동기적으로 target policy의 가중치를 갱신하는 방식이 있고 하나의 agent에서 batch 처리를 해서 가중치를 갱신하는 방식이 있다.

DDPG(Deep Deterministic Policy Gradient)는 신경망으로 모델링한 Q-function을 통해 deterministic policy에서 나온 action을 평가하여 Q-function 값을 최대화하는 방향으로 학습을 진행한다. Q-function은 일반적인 DQN 방식과 동일하게 학습하는데 를 로 대체하여 계산 효율성이 높다. action space가 continuous한 경우에 사용하기 좋은 방법이다.

DQN 기반 알고리즘

categorical DQN은 distributional reinforcement learning의 일종으로 의 기댓값이 아닌 의 이산확률분포 를 예측하는 기법이다. 일반적인 DQN보다 더 나은 성능을 보였다고 한다.

noisy network는 순전파할 때 신경망의 출력 부분의 fully connected layer의 가중치를 정규분포에서 추출하는 방식으로 noise를 추가하여 -greedy policy를 대신하는 방법이다. 을 설정할 필요가 없다는 장점이 있다.

misc

offline reinforcement learning은 environment와 상호작용없이 과거에 축적된 데이터만으로 모델을 학습시키는 방법이다.

imitation learning은 숙련자의 결정같은 예시 답안이 있는 경우에 이를 모방하는 학습 방법을 말한다. 아타리 문제 같은 경우 인간 숙련자가 플레이한 데이터를 experience replay에 활용하는 방법이 여기에 속한다.