Contents

Ch1. 강화학습이란?

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

  • action value : 어떤 action($A$)에 대한 reward($R$)의 기댓값이다.
\[q(a)=\mathbb{E}[R\mid A=a]\]

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

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

$\epsilon$-greedy policy : $\epsilon$의 확률만큼 exploration을 하고 나머지 $(1-\epsilon)$의 확률만큼 exploitation을 하는 전략

  • $Q(a)$ 계산법 (sample mean)
\[Q_{t-1}(a)=\frac{\sum_{i=1}^{t-1} R_i(a)}{t-1}\] \[\begin{flalign}Q_t(a)&=\frac{\sum_{i=1}^t R_i(a)}{t}\\&=\frac{(t-1)Q_{t-1}(a)+R_t(a)}{t}\\&=Q_{t-1}(a)+\frac{1}{t}(R_t(a)-Q_{t-1}(a)) \end{flalign}\]

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

  • $Q(a)$ 계산법 (exponential moving average)
\[\begin{flalign}Q_{t-1}(a)&=Q_{t-2}(a)+\alpha(R_{t-1}(a)-Q_{t-2}(a))\\Q_t(a)&=Q_{t-1}(a)+\alpha(R_t(a)-Q_{t-1}(a))\\&=Q_{t-2}(a)+\alpha(R_{t-1}(a)-Q_{t-2}(a))+\alpha(R_t(a)-(Q_{t-2}(a)+\alpha(R_{t-1}(a)-Q_{t-2}(a))))\\&=\alpha R_t(a)+\alpha (1-\alpha)R_{t-1}(a)+(1-\alpha)^2Q_{t-2}(a)\\&=(1-\alpha)^tQ_0(a)+\sum_{i=1}^t \alpha (1-\alpha)^{t-i}R_i(a)\end{flalign}\]

$\frac{1}{n}$을 $\alpha$($0\lt\alpha\lt 1$)로 고정하여 최근의 reward에 더 높은 가중치를 부여한다. 다만 $Q_0(a)$항 설정이 필요해진다.

MDP (Markov Decision Process)

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

\[\begin{flalign}a&\sim\pi(a\mid s)\\s^\prime&\sim p(s^\prime\mid s,a)\\r&=r(s^\prime,a,s) \end{flalign}\]

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

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

\[S_0,A_0,R_0,S_1,A_1,R_1,S_2,A_2,R_2,\cdots\]

강화학습 문제는 크게 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를 통해 직접 데이터를 수집하여 추정해야하는 문제를 말한다.

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

\[\begin{flalign}G_t&=\sum_{i=0}^\infty \gamma^{i}R_{t+i}\\ v_\pi(s)&=\mathbb{E}[G_t\mid S_t=s,\pi]=\mathbb{E}_\pi[G_t\mid S_t=s] \end{flalign}\]

$G_t$는 return으로 앞으로 받을 rewards를 나타낸다. $\gamma$는 discount rate로 $(0,1)$ 사이의 값으로 설정할 수 있다.

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

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

\[q_\pi(s,a)=\mathbb{E}[G_t\mid S_t=s,A_t=a,\pi]=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]\]

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

Bellman equation

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

\[\begin{flalign} v_\pi(s)&=\mathbb{E}_\pi[R_t+\gamma G_{t+1}\mid S_t=s]\\&=\mathbb{E}_\pi[R_t\mid S_t=s]+\gamma \mathbb{E}_\pi[G_{t=1}\mid S_t=s]\\&=\sum_{a,s^\prime} \pi(a_i\mid s)p(s^\prime_j\mid a_i,s)r(s^\prime_j,a_i,s)+\gamma\cdot\sum_{a,s^\prime} \pi(a_i\mid s)p(s^\prime_j\mid a_i,s)v_\pi(s^\prime_j)\\&=\sum_a\pi(a_i\mid s)\sum_{s^\prime} p(s^\prime_j\mid a_i,s)\lbrace r(s^\prime_j,a_i,s)+\gamma\cdot v_\pi(s^\prime_j)\rbrace\end{flalign}\]

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

\[\begin{flalign}q_\pi(s,a)&=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]\\&=\mathbb{E}_\pi[R_t\mid S_t=s, A_t=a]+\gamma\cdot\mathbb{E}_\pi[G_{t+1}\mid S_t=s,A_t=a]\\&=\sum_{s^\prime} p(s^\prime_j\mid s,a)r(s^\prime_j,a,s)+\gamma\cdot \sum_{a^\prime,s^\prime} p(s^\prime_j\mid s,a)\pi(a^\prime_i\mid s^\prime_j)q_\pi(s^\prime_j,a^\prime_i)\\&=\sum_{s^\prime} p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot\sum_{a^\prime} \pi(a^\prime_i\mid s^\prime_j)q_\pi(s^\prime_j,a^\prime_i)\rbrace\\&\text{or} \\&=\sum_{s^\prime} p(s^\prime_j\mid s,a)r(s^\prime_j,a,s)+\gamma\cdot \sum_{s^\prime}p(s^\prime_j\mid s,a) v_\pi(s^\prime_j)\\&=\sum_{s^\prime} p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot v_\pi(s^\prime_j)\rbrace \end{flalign}\]

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

\[v_\ast(s)=\operatorname*{max}_a \sum_{s^\prime} p(s^\prime_j\mid a,s)\lbrace r(s^\prime_j,a,s)+\gamma\cdot v_\ast(s^\prime_j)\rbrace\] \[\begin{flalign}q_\ast(s,a)&= \operatorname*{max}_{a^\prime} \sum_{s^\prime}p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot q_\ast(s^\prime_j,a^\prime)\rbrace\\&=\sum_{s^\prime} p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot v_\ast(s^\prime_j)\rbrace \end{flalign}\]

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

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

\[\begin{flalign} \mu_\ast(s)&=\operatorname*{arg max}_{a}\ q_\ast(s,a)\\ &= \operatorname*{arg max}_{a} \sum_{s^\prime} p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot v_\ast(s^\prime_j)\rbrace \end{flalign}\]

$\operatorname*{arg max}\limits_a$를 통해서 최선의 action을 찾기 때문에 위 표현을 greedy policy라고 한다.

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

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

\[\begin{flalign}V_{k+1}(s)&=\sum_{a,s^\prime} \pi(a_i\mid s)p(s^\prime_j\mid a_i,s)\lbrace r(s^\prime_j,a_i,s)+\gamma\cdot V_{k}(s^\prime_j)\rbrace\\ &\text{or}\\ a&=f(s)\\V_{k+1}(s) &=\sum_{s^\prime}p(s^\prime_j\mid a,s)\lbrace r(s^\prime_j,a,s)+\gamma\cdot V_k(s^\prime_j)\rbrace \end{flalign}\]

다음 state의 $V_{k}$를 이용하여 현재의 $V_{k+1}$을 갱신하는 방법이다. 모든 state에 대해 해당 과정을 반복하면 $V_k(s)$가 $v_\pi(s)$에 가까워 진다. 여러 $V_k$를 통해 $V_{k+1}$을 갱신하는 것을 bootstraping이라고 한다. bootstraping 과정에서 $V_k(s^\prime_j)$ 대신에 $V_{k+1}(s^\prime_j)$를 사용할 수도 있다.

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

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

\[\mu^\prime(s)=\operatorname*{arg max}_a \sum_{s^\prime} p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot v_\mu(s^\prime_j)\rbrace\]

다음과 같이 $\mu^\prime(s)$를 갱신하면 $v_{\mu^\prime}(s)\ge v_{\mu}(s)$가 성립한다.

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에서 $\pi$가 아닌 $\mu$를 사용할 수 있게 되며 다음과 같이 식을 표현할 수 있다.

\[V_{k+1}(s)=\operatorname*{max}_a \sum_{s^\prime}p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot V_k(s^\prime_j)\rbrace\]

value iteration을 반복하면 $V(s)$가 $v_\ast(s)$에 가까워진다. 이렇게 구한 $V_\ast(s)$를 통해 optimal policy를 구하면 된다.

\[\mu_\ast(s)= \operatorname*{arg max}_a \sum_{s^\prime} p(s^\prime_j\mid s,a)\lbrace r(s^\prime_j,a,s)+\gamma\cdot V_\ast(s^\prime_j)\rbrace\]

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

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

\[\begin{flalign}v_\pi(s)=V_n(s)&=\mathbb{E}_\pi[G_t\mid S_t=s]\\&=\mathbb{E}_\pi[R_t+\gamma R_{t+1}+\gamma^2 R_{t+1}+\cdots\mid S_t=s]\\ &\approx \frac{G^1+G^2+\cdots+G^n}{n}\\G_t&=R_t+\gamma\cdot G_{t+1} \end{flalign}\]

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

\[\begin{flalign}q_\pi(s,a)=Q_n(s,a)&=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]\\ &=\mathbb{E}_\pi[R_t+\gamma R_{t+1}+\gamma^2 R_{t+1}+\cdots\mid S_t=s,A_t=a]\\&\approx \frac{G^1+G^2+\cdots+G^n}{n}\\&=Q_{n-1}(s,a)+\frac{1}{n}(G^n-Q_{n-1}(s,a)) \end{flalign}\]

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

\[\mu(s)=\operatorname*{arg max}_a\ q_\pi(s,a)\]

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

\[\pi(a \mid s) = \begin{cases} \displaystyle\frac{\epsilon}{\lvert \mathcal{A}(s)\rvert}+1-\epsilon, & \text{if } a = \operatorname*{arg max}\limits_{a'}\,q_\pi(s,a'), \\[8pt] \displaystyle\frac{\epsilon}{\lvert \mathcal{A}(s)\rvert}, & \text{otherwise}. \end{cases}\]

* $\lvert\mathcal{A}(s)\rvert$는 $s$에서 가능한 action의 개수이다.

$\epsilon$-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은 어떤 확률 분포에 의한 기댓값을 다른 확률 분포에 의한 기댓값으로 구하는 것을 말한다.

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

\[\begin{flalign} \mathbb{E}_\pi[x]&=\sum x\cdot\pi(x)\\&=\sum x\cdot\frac{b(x)}{b(x)}\cdot\pi(x)\\&=\sum x\cdot\frac{\pi(x)}{b(x)}\cdot b(x)\\&=\mathbb{E}_b[x\cdot\frac{\pi(x)}{b(x)}]\\&=\mathbb{E}_b[x\cdot\rho(x)] \end{flalign}\]

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

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

\[\begin{flalign}\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a]&=\mathbb{E}_b[\rho\cdot G_t\mid S_t=s,A_t=a]\\&\rho=\frac{\Pr(\text{trajectory}\mid \pi,S_t=s, A_t=a)}{\Pr(\text{trajectory}\mid b,S_t=s,A_t=a)} \end{flalign}\]

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

\[\text{trajectory}=(S_t,A_t,S_{t+1},A_{t+1},\dots,S_T)\]

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

따라서

\[\begin{flalign}q_\pi(s,a)&=\mathbb{E}_b[\rho\cdot G_t\mid S_t=s,A_t=a]\\&=\mathbb{E}_b[\frac{p(S_{t+1}\mid A_t,S_t)\prod_{i=t+1}^{T-1}\lbrace\pi(A_{i}\mid S_{i})p(S_{i+1}\mid A_{i},S_{i})\rbrace}{p(S_{t+1}\mid A_t,S_t)\prod_{i=t+1}^{T-1}\lbrace b(A_{i}\mid S_{i})p(S_{i+1}\mid A_{i},S_{i})\rbrace}\cdot G_t\mid S_t=s,A_t=a]\\&=\mathbb{E}_b[\frac{\prod_{i=t+1}^{T-1}\pi(A_{i}\mid S_{i})}{\prod_{i=t+1}^{T-1} b(A_{i}\mid S_{i})}\cdot G_t\mid S_t=s,A_t=a]\end{flalign}\]

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

Ch2. Head 2

Head 2

Head 2

Head 2