[강화학습 기초지식] Part 1: Key Concepts in RL (2)

본 포스트는 OpenAI에서 공개한 강화학습 교육자료인 Spinning Up의 도움을 받아, 강화학습(Reinforcement Learning, RL)에 대한 기초개념을 정리해보고자 제작한 시리즈의 일환입니다.

1)기초 지식 2)주요 논문, 3)최신 논문 의 순서로 시리즈를 정리하고자 합니다.

아래 링크에서 더 상세한 내용을 찾아볼 수 있습니다.

Part 1: Key Concepts in RL - Spinning Up documentation

Welcome to our introduction to reinforcement learning! Here, we aim to acquaint you with the language and notation used to discuss the subject, a high-level explanation of what RL algorithms do (although we mostly avoid the question of how they do it), and a little bit of the core math that underlies the algorithms. In a nutshell, RL is the study of agents and how they learn by trial and error.

https://spinningup.openai.com/en/latest/spinningup/rl_intro.html

Key Concepts and Terminology (cont'd)

지난 시간엔, state와 observation, action space, policy, trajectory에 대해 살펴보았습니다. 이번 시간엔 reward와 return부터 함께 살펴보도록 하겠습니다.

Reward and Return

Time step $t$에서의 reward는 $r_t=R(s_t,a_t,s_{t+1})$로 나타낼 수 있으며, 종종 $r_t=R(s_t,a_t)$와 같이 간소화됩니다. 지난 포스트에서, agent의 목표는 trajectory $\tau$동안의 누적 reward를 최대화시키는 것이라고 했었죠? 이 누적 reward를 return이라 정의하겠습니다. 그런데 이 reward를 유한한 시간동안만 누적시킬 지, 혹은 무한히 누적시킬 지 구분해야 합니다. 만약 reward를 유한시간 $T$동안만 누적시킨다면 이를 finite-horizon undiscounted return라 하고, 아래와 같이 정의됩니다.

$R(\tau)=\sum_{t=0}^T r_t$

반면에 reward를 무한히 누적시킨다면, 발산할 가능성이 있겠죠? 때문에 누적값이 발산하지 않고 수렴할 수 있도록 discount factor $\gamma\in(0,1)$을 사용하겠습니다. 이 discount factor는 현재에 가까운 reward일 수록 더 큰 가치를, 미래에 가까울수록 더 작은 가치를 부여하는 역할을 맡습니다. Infinite-horizon discounted return은 아래와 같이 정의합니다.

$R(\tau)=\sum_{t=0}^\infty \gamma^tr_t$

The RL Problem

이제 본격적으로 강화학습문제를 정의해보도록 하겠습니다. 우리의 최종 목표는 agent가 expected return을 최대화할 수 있도록 policy를 선택하도록 하는 것입니다. Expected?? 평균짓는다고?? 대체 무엇에 대해 평균짓는거지? 우리는 agent가 수행할 수 있는 모든 경우의 trajectory에서 획득된 return을 평균지을 것입니다. 따라서 특정 trajectory가 observe될 확률을 먼저 구해보겠습니다.

State transition probability와 policy가 stochastic(확률로 표현가능)하다고 가정합시다. 그렇다면 $T$-step trajectory $\tau$가 observe될 확률은 아래와 같습니다.

$P(\tau|\pi)=\rho_0(s_0)\prod_{t=0}^{T-1}P(s_{t+1}|s_t,a_t)\pi(a_t|s_t)$

우리가 최대화하고싶은 expected return $J(\pi)$는 아래와 같이 정의할 수 있겠죠.

$J(\pi)=\int_\tau P(\tau|\pi)R(\tau)=\underset{\tau\sim\pi}{\mathbb{E}}[R(\tau)]$

따라서 Agent가 선택할 이상적인 policy의 값, 즉 optimal policy $\pi^*$는 아래와 같습니다.

$\pi^*=\argmax_\pi J(\pi)$

Value Functions

Value function은 state에 대한 함수로, 특정 state $s$에서 trajectory가 시작될 때의 expected return을 나타냅니다. 만약 첫 번째 state뿐만 아니라, 첫 번째 action $a$까지 동시에 고려하여 expected return을 계산한다면, action-value function라 정의합니다.

Value function은 항상 agent의 policy $\pi$에 영향을 받는데, policy가 agent의 action을 선택한다는 사실을 떠올려보면 당연한 사실이겠죠? 이를 on-policy라고 표현합니다. 만약 agent가 action을 선택하는데 있어, optimal policy $\pi^*$를 사용한다면 함수에 *를 붙여줍니다.

이에 따라 아래와 같은 4가지의 value function을 정의할 수 있습니다.

1. On-policy value function: $V^\pi(s)=\underset{\tau\sim\pi}{\mathbb{E}}[R(\tau)|s_0=s]$

2. On-policy action-value function: $Q^\pi(s,a)=\underset{\tau\sim\pi}{\mathbb{E}}[R(\tau)|s_0=s,a_0=a]$

3. Optimal value function: $V^*(s)=\underset{\pi}{\max}\underset{\tau\sim\pi}{\mathbb{E}}[R(\tau)|s_0=s]$

4. Optimal action-value function: $Q^*(s,a)=\underset{\pi}{\max}\underset{\tau\sim\pi}{\mathbb{E}}[R(\tau)|s_0=s,a_0=a]$

Value function $V^\pi(s)$와 action-value function $Q^\pi(s)$ 사이엔 아래와 같은 관계가 형성됩니다.

$V^\pi(s)=\underset{a\sim\pi}{\mathbb{E}}[Q^\pi(s,a)]$

Optimal policy의 경우, 위의 $\argmax$식에서 볼 수 있듯, 가장 큰 expected return을 생성할 단 한 개의 action만을 선택합니다. 그 말인즉슨 $\pi^*(a|s)$의 probability density function(PDF, action이 연속인 경우) 혹은 probability mass function(PMF, action이 불연속인 경우)이 $\delta$-function꼴을 가진다는 의미입니다. 또한, optimal value function $V^*(s)$와 optimal action-value function $Q^*(s)$ 사이에 아래와 같은 관계가 형성되며, $\max$함수를 사용하게 됩니다.

$V^*(s)=\underset{a}{\max}Q^*(s,a)$

더 나아가 가장 높은 expected return을 제공하는 최적의 선택, optimal action $a^*$은 아래와 같이 얻어집니다.

$a^*=\argmax_a Q^*(s,a)$

Action-value function을 State-action value function이나 Q-function으로 부르기도 합니다.

Bellman Equations

조금이라도 강화학습 관련 서적을 본 적이 있는 분이라면 너무나도 익숙할 이 방정식은, 위에서 서술한 4가지의 value function 모두에 적용되는 방정식입니다. Recursive한 성질을 띠는 이 방정식은 아래의 아이디어에서 출발합니다.

현재 state에서의 value값은 현재 state에서 기대되는 reward값과 다음 state에서의 value값의 합과 같다.

자세히 살펴볼까요? $P$는 state transition probability입니다.

1. On-policy value function: $V^\pi(s)=\underset{s'\sim P}{\underset{a\sim\pi}{\mathbb{E}}}[r(s,a)+\gamma V^\pi(s')]$

2. On-policy action-value function: $Q^\pi(s,a)=\underset{s'\sim P}{\mathbb{E}}\left[r(s,a)+\gamma \underset{a'\sim \pi}{\mathbb{E}}[Q^\pi(s',a')]\right]$

3. Optimal value function: $V^*(s)=\underset{a}{\max}\underset{s'\sim P}{\mathbb{E}}[r(s,a)+\gamma V^*(s')]$

4. Optimal action-value function: $Q^*(s,a)=\underset{s'\sim P}{\mathbb{E}}\left[r(s,a)+\gamma \underset{a}{\max}[Q^*(s',a')]\right]$

여기서도, on-policy value function과 optimal value function과의 차이는 $\max$함수의 유무임을 알 수 있습니다.

특정 state 혹은 state & action에서의 Bellman backup은 위에서 서술한 Bellman equation의 오른쪽 변을 의미합니다.

Advantage Functions

현재 state $s$에서, 우리가 선택할 action $a$가 대체 얼마나 좋은 선택인지 비교할 수 있을까요? 이때 필요한 것이 바로 advantage function입니다. 아래와 같이 정의합니다.

$A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s)$

Agent는 현재 state $s$에서만 policy $\pi$에서 벗어난 action $a$를 선택하고, 그 이후엔 policy를 추종한다는 점을 잊지 마세요.

Formalism

수고하셨습니다! MDP의 개괄적인 terminology를 전부 익히셨습니다.

대개 MDP는 $\left< S,A,R,P,\rho_0 \right>$의 5-tuple의 구성으로 표현합니다.

• State space $S$

• Action space $A$

• Reward function $R:S\times A\times S \to \mathbb{R}$ with $r_t=R(s_t,a_t,s_{t+1})$

• State transition probability function $P:S \times A \to \mathcal{P}(S)$ with state transition probability $P(s'|s,a)$into state $s'$

• Starting state distribution $\rho_0$

Markov decision process의 이름의 유래는 이 process가 Markov property를 따름에서 유래합니다. 즉, state의 transition이 가장 최근의 state와 action에만 의존한다는 의미죠. 과거의 state와 action은 다음 state에의 transition에 영향을 주지 않습니다.

다음 포스트에선 다양한 강화학습 알고리즘을 간단하게 분류하는 과정을 정리해보겠습니다.

Reference

[1] R. S. Sutton, A. G. Barto, et al., Introduction to reinforcement learning, vol. 135. MIT press Cambridge, 1998.

[2] OpenAI. Spinning Up, [Online]. Available: https://spinningup.openai.com/