강화 학습

보상을 최적화하기 위한 학습

강화 학습^{reinforcement learning}(RL)에서 소프트웨어 에이전트^agent는 관측^observation을 하고 주어진 환경^environment에서 행동^action을 하고 그 결과로 보상^reward을 받는다.
에이전트의 목적은 보상의 장기간 기대치를 최대로 만드는 행동을 학습하는 것
간단히 말해 에이전트는 환경 안에서 행동하고 시행착오를 겪으며 기쁨(양^positive의 보상)이 최대가 되고 아픔(음^negative의 보상)이 최소가 되도록 학습
양의 보상이 전혀 없을 수도 있다. (e.g. 에이전트가 미로 속을 움직인다면 매 타임 스텝마다 음의 보상을 받기 때문에 가능한 한 빨리 탈출구를 찾는 것이 좋을 것)

---

정책 탐색

소프트웨어 에이전트가 행동을 결정하기 위해 사용하는 알고리즘을 정책^policy이라고 한다.

---

신경망 정책

신경망은 관측을 입력으로 받고 실행할 행동을 출력
조금 더 정확히 말해 각 행동에 대한 확률을 추정하고 추정된 확률에 따라 랜덤하게 행동을 선택
이런 방식은 에이전트가 새로운 행동을 탐험^exploring하는 것과 잘 할 수 있는 행동을 활용^exploiting하는 것 사이에 균형을 맞춘다.

---

행동 평가 : 신용 할당 문제

각 스텝에서 가장 좋은 행동이 무엇인지 알고 있다면 평소처럼 추정된 확률과 타깃 확률 사이의 크로스 엔트로피를 최소화하도록 신경망을 훈련
이는 일반적인 지도 학습과 같지만 강화 학습에서 에이전트가 얻을 수 있는 가이드는 보상뿐
보상은 일반적으로 드물고 지연되어 나타나고 이는 에이전트가 보상을 받았을 때 어떤 행동 덕분인지 (혹은 탓인지) 알기 어렵다. (이를 신용 할당 문제^{credit assignment problem}라고 한다.)
이 문제를 해결하기 위해 흔히 사용하는 전략은 행동이 일어난 후 각 단계마다 할인 계수^{discount factor} $\gamma$(감마)를 적용한 보상을 모두 합하여 행동을 평가하는 것 (할인된 보상의 합을 행동의 대가^return라고 부른다.)
할인 계수가 0에 가까우면 미래의 보상은 현재의 보상만큼 중요하게 취급되지 않을 것이고 반대로 할인 계수가 1에 가까우면 먼 미래의 보상이 현재의 보상만큼 중요하게 고려될 것 (전형적인 할인 계수의 값은 0.9에서 0.99 사이)
평균적으로 다른 가능한 행동과 비교해서 각 행동이 얼마나 좋은지 혹은 나쁜지를 추정 (이를 행동 이익^{action advantage}이라고 부른다.)
이렇게 하려면 많은 에피소드를 실행하고 모든 행동의 대가를 (평균을 빼고 표준편차로 나누어) 정규화
그런 후 행동 이익이 음수인 행동은 나쁘고, 양수인 행동은 좋다고 가정

---

정책 그레이디언트^{policy gradient}(PG)

PG 알고리즘은 높은 보상을 얻는 방향의 그레이디언트를 따르도록 정책의 파라미터를 최적화하는 알고리즘
다음은 많이 사용하는 REINFORCE 알고리즘 방식

1. 먼저 신경망 정책이 여러 번에 걸쳐 에피소드를 실행하고 매 스텝마다 선택된 행동이 더 높은 가능성을 가지도록 만드는 그레이디언트를 계산한다. 하지만 아직 이 그레이디언트를 적용하지는 않는다.
2. 에피소드를 몇 번 실행한 다음, 각 행동의 이익을 계산
3. 한 행동의 이익이 양수이면 이 행동이 좋은 것임을 의미하므로 미래에 선택될 가능성이 높도록 앞서 계산한 그레이디언트를 적용한다. 그러나 행동 이익이 음수이면 이 행동이 나쁜 것임을 의미하므로 미래에 이 행동이 덜 선택되도록 반대의 그레이디언트를 적용한다. 이는 각 그레이디언트 벡터와 그에 상응하는 행동의 이익을 곱하면 된다.
4. 마지막으로 모든 결과 그레이디언트 벡터를 평균 내어 경사 하강법 스텝을 수행

---

마르코프 결정 과정

마르코프 연쇄^{Markov chain}

메모리가 없는 확률 과정^{stochastic process}
이 과정은 정해진 개수의 상태를 가지고 있으며, 각 스텝마다 한 상태에서 다른 상태로 랜덤하게 전이
상태 $s$에서 상태 ${s}'$로 전이하기 위한 확률은 고정되어 있으며, (시스템에 메모리가 없으므로) 과거 상태에는 상관없이 $(s,{s}')$ 쌍에만 의존

마르코프 결정 과정^{Markov decision process}(MDP)

마르코프 연쇄와 비슷하지만 각 스텝에서 에이전트는 여러 가능한 행동 중 하나를 선택할 수 있고, 전이 확률은 선택된 행동에 따라 달라진다.
또한 어떤 상태 전이는 보상(음수 또는 양수)을 반환
그리고 에이전트의 목적은 시간이 지남에 따라 보상을 최대화하기 위한 정책을 찾는 것

벨먼 최적 방정식^{Bellman optimality equation}

어떤 상태 $s$의 최적의 상태 가치^{state value} $V\ast (s)$를 추정하는 방법
이 값은 에이전트가 상태 s에 도달한 후 최적으로 행동한다고 가정하고 평균적으로 기대할 수 있는 할인된 미래 보상의 합
이 재귀적인 식이 의미하는 것은 에이전트가 최적으로 행동하면 현재 상태의 최적 가치는 하나의 최적 행동으로 인해 평균적으로 받게 될 보상과 이 행동이 유발할 수 있는 가능한 모든 다음 상태의 최적 가치의 기대치를 합한 것과 같다는 것
$V^\ast (s)=\underset{a}{\text{max}}\sum_ {{s}'}T(s,a,{s}')[R(s,a,{s}')+\gamma\cdot V^\ast({s}')]$ 모든 $s$에 대해

• $T(s,a,{s}')$는 에이전트가 행동 $a$를 선택했을 때 상태 $s$에서 상태 ${s}'$로 전이될 확률
• $R(s,a,{s}')$는 에이전트가 행동 $a$를 선택해서 상태 $s$에서 상태 ${s}'$로 이동되었을 때 에이전트가 받을 수 있는 보상
• $\gamma$는 할인 계수

가치 반복^{value iteration} 알고리즘

이 식은 알고리즘이 가능한 모든 상태에 대한 최적의 상태 가치를 정확히 추정할 수 있도록 도와준다.
먼저 모든 상태 가치를 0으로 초기화하고 가치 반복 알고리즘을 사용하여 반복적으로 업데이트
충분한 시간이 주어지면 이 추정값이 최적의 정책에 대응되는 최적의 상태 가치에 수렴하는 것을 보장
$V_ {k+1}(s)\leftarrow \underset{a}{\text{max}}\sum_ {{s}'}T(s,a,{s}')[R(s,a,{s}')+\gamma\cdot V_ {k}({s}')]$ 모든 $s$에 대해

• $V_ {k}(s)$는 알고리즘 $k$번째 반복에서 상태 $s$의 추정 가치

Q-가치 반복^{Q-value iteration} 알고리즘

최적의 상태 가치를 아는 것은 특히 정책을 평가할 때 유용하지만 에이전트를 위한 최적의 정책을 알려주지는 않는다.
다행히 Q-가치^Q-value라고 부르는 최적의 상태-행동 가치^{state-action value}를 추정할 수 있는 매우 비슷한 알고리즘을 발견
상태-행동 $(s,a)$쌍에 대한 최적의 Q-가치인 $Q\ast (s,a)$는 에이전트가 상태 $s$에 도달해서 행동 $a$를 선택한 후 이 행동의 결과를 얻기 전에 평균적으로 기대할 수 있는 할인된 미래 보상의 합 (여기서는 에이전트가 이 행동 이후에 최적으로 행동할 것이라고 가정)
먼저 Q-가치의 추정을 모두 0으로 최기화하고 Q-가치 반복 알고리즘을 사용해 업데이트
$Q_ {k+1}(s,a)\leftarrow \sum_ {{s}'}T(s,a,{s}')[R(s,a,{s}')+\gamma\cdot\underset{{a}'}{\text{max}} Q_ {k}({s}',{a}')]$ 모든 $(s,a)$에 대해
최적의 Q-가치를 구하면 최적의 정책인 $\pi \ast(s)$를 정의하는 것은 간단 (에이전트가 상태 $s$에 도달했을 때 가장 높은 Q-값을 가진 행동을 선택)
$\pi^{\ast}(s)=\underset{a}{\text{argmax}}Q^{\ast}(s,a)$

---

시간차 학습^{temporal difference learning}(TD 학습)

가치 반복 알고리즘과 비슷하지만, 에이전트가 MDP에 대해 일부 정보만 알고 있을 때를 다룰 수 있도록 변형한 것
일반적으로 에이전트가 초기에 가능한 상태와 행동만 알고 다른 것을 모른다고 가정한다면 에이전트는 탐험 정책^{exploration policy}을 (e.g. 완전히 랜덤한 정책을) 사용해 MDP를 탐험
탐험이 진행될수록 TD 학습 알고리즘이 실제로 관측된 전이와 보상에 근거하여 상태 가치의 추정값을 업데이트

TD 학습 알고리즘

$V_ {k+1}(s)\leftarrow (1-\alpha )V_ {k}(s)+\alpha (r+\gamma\cdot V_ {k}({s}'))$
또는 다음과 같이 쓸 수 있다.
$V_ {k+1}(s)\leftarrow V_ {k}(s)+\alpha\cdot\delta_ {k}(s,r,{s}')$ 여기에서 $\delta_ {k}(s,r,{s}')=r+\gamma\cdot V_ {k}({s}')-V_ {k}(s)$

• $\alpha$는 학습률 (e.g. 0.01)
• $r+\gamma\cdot V_ {k}({s}')$는 TD 타깃이라 부른다.
• $\delta_ {k}(s,r,{s}')$는 TD 오차라고 부른다.

이 식의 첫 번째 형태를 더 간단히 쓰는 방법은 $a\underset{\alpha}{\leftarrow}b$ 표기법을 사용하는 것 (이 표기는 $a_ {k+1}\leftarrow (1-\alpha)\cdot a_ {k}+\alpha\cdot b_{k}$를 뜻한다.)
$V(s)\underset{\alpha}{\leftarrow}r+\gamma\cdot V({s}')$
각 상태 $s$에서 이 알고리즘은 에이전트가 이 상태를 떠났을 때 얻을 수 있는 당장의 보상과 (최적으로 행동한다고 가정하여) 나중에 기대할 수 있는 보상을 더한 이동 평균을 저장

---

Q-러닝^Q-learning

비슷하게 Q-러닝 알고리즘은 전이 확률과 보상을 초기에 알지 못한 상황에서 Q-가치 반복 알고리즘을 적용한 것
Q-러닝은 에이전트가 플레이(e.g. 랜덤하게)하는 것을 보고 점진적으로 Q-가치 추정을 향상하는 방식으로 작동
정확한 (또는 충분히 근접한) Q-가치 추정을 얻게되면 최적의 정책은 가장 높은 Q-가치를 가지는 행동을 선택하는 것 (i.e. 탐욕적 정책)

Q-러닝 알고리즘

$Q(s,a)\underset{\alpha}{\leftarrow}r+\gamma\cdot\underset{{a}'}{\text{max}}Q({s}',{a}')$
각 상태-행동 (s,a) 쌍마다 이 알고리즘이 행동 $a$를 선택해 상태 $s$를 떠났을 때 에이전트가 받을 수 있는 보상 $r$과 기대할 수 있는 할인된 미래 보상의 합을 더한 이동 평균을 저장
미래 보상의 합을 추정하기 위해서는 타깃 정책이 이후로 최적으로 행동한다고 가정하고 다음 상태 ${s}'$에 대한 Q-가치 추정의 최댓값을 선택

훈련된 정책을 반드시 실행에 사용하지 않기 때문에 Q-러닝 알고리즘을 오프-폴리시^off-policy 알고리즘이라고 한다.
훈련된 정책은 항상 가장 높은 Q-가치를 가진 행동을 선택하는 것
반대로 정책 그레이디언트 알고리즘은 온-폴리시^on-policy 알고리즘이고 훈련된 정책을 사용해 환경을 탐험

탐험 정책

완전한 랜덤 정책이 결국에는 모든 상태와 전이를 여러 번 경험한다고 보장하지만, 이렇게 하려면 극단적으로 오랜 시간이 걸릴 수 있다.
그러므로 더 나은 방법은 각 스텝에서 $\varepsilon$ 확률로 랜덤하게 행동하거나 $1-\varepsilon$ 확률로 그 순간 가장 최선인 것으로 (가장 높은 Q-가치를 선택하여) 행동하는 $\varepsilon$-그리디 정책^{$\varepsilon$-greedy policy}($\varepsilon$은 입실론)을 사용하는 것
$\varepsilon$-그리디 정책의 장점은 (완전한 랜덤 정책에 비해) Q-가치 추정이 점점 더 향상되기 때문에 환경에서 관심 있는 부분을 살피는 데 점점 더 많은 시간을 사용한다는 점이지만 여전히 MDP의 알려지지 않는 지역을 방문하는 데 일정 시간을 사용할 것
$\varepsilon$의 값은 높게 (e.g. 1.0) 시작해서 점점 감소되는 것(e.g. 0.05)이 일반적
다른 방법으로는 탐험의 가능성에 의존하는 대신 이전에 많이 시도하지 않았던 행동을 시도하도록 탐험 정책을 강조하는 방법 (Q-가치 추정에 보너스를 추가하는 방식으로 구현)
$Q(s,a)\underset{\alpha}{\leftarrow}r+\gamma\cdot\underset{{a}'}{\text{max}}f(Q({s}',{a}'),N({s}',{a}'))$

• $N({s}',{a}')$는 상태 ${s}'$에서 행동 ${a}'$를 선택한 횟수를 카운트
• $f(Q,N)$은 $f(Q,N)=Q+_ {K}\textrm{/(1+N)}$와 같은 탐험 함수^{exploration function}이다. 여기에서 $_ {K}$는 에이전트가 알려지지 않는 곳에 얼마나 흥미를 느끼는지 나타내는 하이퍼파라미터

근사 Q-러닝과 심층 Q-러닝

Q-러닝의 주요 문제는 많은 상태와 행동을 가진 대규모 (또는 중간 규모)의 MDP에 적용하기 어렵다는 것
해결책은 어떤 상태-행동 $(s,a)$ 쌍의 Q-가치를 근사하는 함수 $Q_ {\theta }(s,a)$를 (파라미터 벡터 $\theta$로 주어진) 적절한 개수의 파라미터를 사용하여 찾는 것 (이를 근사 Q-러닝^{approximate Q-learning}이라고 한다.)
오랫동안 상태에서 직접 뽑아낸 특성들을 선형 조합하는 방식이 권장 되었지만 심층 신경망 사용이 특히 복잡한 문제에서 훨씬 더 나은 결과를 냈고, 이는 어떤 특성 공학도 필요하지 않다.
Q-가치를 추정하기 위해 사용하는 DNN을 심층 Q-네트워크^{deep Q-network}(DQN)라 하고, 근사 Q-러닝을 위해 DQN을 사용하는 것을 심층 Q-러닝^{deep Q-learning}이라 한다.
Q-가치는 상태 $s$에서 행도 $a$를 실행했을 때 관측된 보상 $r$과 그 이후에 최적으로 행동해서 얻은 할인된 가치를 더한 값에 가능한 가깝게 되어야 한다.
이 미래의 할인된 가치를 추정하기 위해서는 간단하게 다음 상태 ${s}'$와 모든 가능한 행동 ${a}'$에 대해 DQN을 실행하면 모든 가능한 행동에 대한 미래의 근사 Q-가치를 얻을 수 있다.
그다음에 (최적으로 행동할 것이라고 가정하기 때문에) 가장 높은 것을 고르고 할인을 적용하면 할인된 미래 보상의 추정을 얻을 수 있고 보상 $r$과 미래의 할인된 가치 추정을 더하면 상태-행동 쌍 $(s,a)$에 대한 타깃 Q-가치 $y(s,a)$를 얻게 된다.
$Q_ {\text{target}}(s,a)=r+\gamma\cdot\underset{{a}'}{\text{max}}Q_ {\theta}({s}',{a}')$
이 타깃 Q-가치로 경사 하강법을 사용해 훈련 단계를 수행할 수 있다. (구체적으로 말하면 추정된 Q-가치 $Q(s,a)$와 타깃 Q-가치 사이의 제곱 오차를 최소화하고 또는 알고리즘이 큰 오차에 민감하지 않도록 후버 손실을 사용)

---

심층 Q-러닝의 변종

고정 Q-가치 타깃

기본 심층 Q-러닝 알고리즘에서 모델은 예측을 만들고 타깃을 설정하는 데 모두 사용되고 이런 피드백 순환 과정은 네트워크를 불안정하게 만들 수 있다. (발산, 진동, 동결 등의 문제)
이 문제를 해결하기 위해 한 개가 아니라 두 개의 DQN을 사용
첫 번째는 각 스텝에서 학습하고 에이전트를 움직이는 데 사용하는 온라인 모델^{online model}이고 두 번째는 타깃을 정의하기 위해서만 사용하는 타깃 모델^{target model}이다. (타깃 모델은 온라인 모델의 단순한 복사본)
훈련 루프에서 일정한 간격(e.g. 50 에피소드)으로 온라인 모델의 가중치를 타깃 모델로 복사
타깃 모델이 온라인 모델보다 자주 업데이트 되지 않으므로, Q-가치 타깃이 더 안정적이면 앞서 언급한 피드백 반복을 완화하고 이에 대한 영향이 감소

더블 DQN^{double DQN}

모든 행동이 동일하게 좋다고 가정할 때 타깃 모델이 추정한 Q-가치가 동일해야 하지만 근삿값이기 때문에 우연히 다른 것보다 조금 높은 값이 있다.
타깃 모델이 항상 가장 큰 Q-가치를 선택하므로 평균 Q-가치보다 조금 더 커지고 실제 Q-가치를 과대평가할 가능성이 높다.
이를 개선하기 위해 다음 상태에서 최선의 행동을 선택할 때 타깃 모델 대신 온라인 모델을 사용하도록 제안 (타깃 모델은 최선의 행동에 대한 Q-가치를 추정할 때만 사용)

우선 순위 기반 경험 재생^{prioritized experience replay}(PER)

재생 버퍼에서 경험을 균일하게 샘플링하는 것이 아니라 중요한 경험을 더 자주 샘플링하는 아이디어 (중요도 샘플링^{importance sampling}이라고도 한다.)
TD 오차 $\delta=r+\gamma\cdot V({s}')-V(s)$의 크기를 재고 큰 TD 오차는 전이 $(s,a,{s}')$에서 배울 가치가 있다는 것을 의미
경험이 재생 버퍼에 기록될 때 적어도 한 번 샘플링 되기 위해 매우 높은 우선 순위 값으로 설정
하지만 샘플링된 후 (그리고 샘플링될 때마다) TD 오차 $\delta$를 계산하여 경험 우선 순위를 $p=|\delta|$로 설정 (경험의 샘플링 확률이 0이 되지 않도록 작은 상수를 더한다.)
우선 순위 $p$의 경험을 샘플링 확률 $P$는 $p^{\zeta }$에 비례하고 $\zeta$는 우선 순위 샘플링을 얼마나 탐욕적으로 할 것인지 제어하는 하이퍼파라미터 ($\zeta=0$이면 균등하게 샘플링 하고 $\zeta=1$이면 완전환 중요도 샘플링)
샘플이 중요한 경험에 편향되어 있으므로 훈련하는 동안 중요도에 따라 경험의 가중치를 낮춰서 이 편향을 보상해주어야 한다. (중요한 경험이 더 자주 샘플링되기를 원하지만 이는 훈련 과정에서 이 샘플에 낮은 가중치를 주어야 한다는 의미)
이렇게 하기 위해 가 경험의 훈련 가중치 $w=(nP)^{-\beta}$를 정의
$n$은 재생 버퍼에 있는 경험의 개수이고 $\beta$는 중요도 샘플링 편향을 얼마나 보상할지 조정하는 하이퍼파라미터 (0은 보상이 전혀 없고 1은 그 반대를 의미)
둘 중 하나를 증가시키면 일반적으로 다른 값도 증가시켜야 한다.

듀얼링 DQN^{dueling DQN}

이 알고리즘의 작동 방식을 이해하려면 먼저 상태-행동 쌍 $(s,a)$의 Q-가치가 $Q(s,a)=V(s)+A(s,a)$처럼 표현될 수 있다는 것을 알아야 한다.
여기에서 $V(s)$는 상태 $s$의 가치이고 $A(s,a)$는 상태 $s$에서 다른 모든 가능한 행동과 비교하여 행동 $a$를 선택했을 때 이득^advantage이다.
또한 상태의 가치는 최선의 행동 $a^{\ast}$의 Q-가치와 같다. (최적의 정책은 최선의 행동을 선택한다고 가정하기 때문)
따라서 $V(s)=Q(s,a^{\ast})$이고 이는 $A(s,a^{\ast})=0$을 의미
듀얼링 DQN에서는 모델이 상태의 가치와 가능한 각 행동의 이익을 모두 추정하고 최선의 행동은 이익이 0이기 때문에 모델이 예측한 모든 이익에서 모든 최대 이익을 뺀다.
더블 듀얼링 DQN을 만들고 우선 순위 기반 경험 재생과 연결할 수 있다. (일반적으로 많은 강화 학습 기법은 합칠 수 있다.)

---

실습코드링크 : reinforcement learning