[CS285] 4. Introduction to Reinforcement Learning

---

💡 이 글은 『2024 PseudoLab 전반기 강화학습팀』으로 진행되었으며, CS285 Fall 2023를 따라 정리했습니다.

1. Definitions

1.1. Terminology & Notation

1.1.1. Markov Chain

Markov chain $\mathcal{M} = \lbrace \mathcal{S}, \mathcal{T} \rbrace$은 state space $\mathcal{S}$와 transition operator $\mathcal{T}$로 구성된다. 여기서는 state $s_{t+1}$이 state $s_t$에만 의존한다. $\mathcal{T}$가 transition “operator”인 이유는 다음과 같다. 확률벡터 $\mu_ {t}$에 대하여 성분 $\mu_ {t, i} = p(s_t = i)$라 하자. $\mathcal{T}_ {i, j} = p(s_{t+1} = j \vert s_t = i)$로 정의하면 $\mu_{t+1} = \mathcal{T} \mu_t$가 성립한다. 즉, $\mathcal{T}$는 $\mu_t$를 $\mu_{t+1}$로 변환하는 선형 변환의 역할로 이해할 수 있다.

1.1.2. Markov Decision Process

그러나 Markov chain만으로는 RL을 설명할 수 없다. Action에 대한 정보가 없기 때문이다. MDP(Markov Decision Process)는 이를 보완하기 위해 action space $\mathcal{A}$를 추가하였다. 이때 transition operator는 tensor로 다음과 같이 확장된다.

\[\begin{aligned} \mu_ {t, j} &= p(s_t = j) \\ \xi_ {t, k} &= p(a_t = k) \\ \mathcal{T}_ {i, j, k} &= p(s_{t+1} = i \vert s_t = j, a_t = k) \\ \therefore \mu_{t+1, i} &= \sum_{j, k} \mathcal{T}_ {i, j, k} \mu_ {t, j} \xi_ {t, k} \\ \end{aligned}\]

그리고 reward function $r: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$를 추가한다. 이때 reward는 state-action pair $(s_t, a_t)$에 대한 함수 $r(s_t, a_t)$로 정의된다. 따라서 MDP는 $\mathcal{M} = \lbrace \mathcal{S}, \mathcal{A}, \mathcal{T}, r \rbrace$로 정의된다.

1.1.3. Partially Observed Markov Decision Process

POMDP(Partially Observed Markov Decision Process)는 observation space $\mathcal{O}$, emission probability $\mathcal{E}$를 추가하여 $\mathcal{M} = \lbrace \mathcal{S}, \mathcal{A}, \mathcal{O}, \mathcal{T}, \mathcal{E}, r \rbrace$로 정의된다. 조금 더 현실에 가까워졌다.

1.2. The Goal of Reinforcement Learning

이제 RL의 목표를 수학적으로 정의해보자. 일단 여기에서는 policy를 explicit하게 정의하였고, 유한한 time step 이후에 끝나는 finite horizon setting을 가정한다. 이때 trajectory $\tau$는 state와 action의 sequence로 정의되며, trajectory distribution $p_\theta$를 다음과 같이 나타낼 수 있다. 여기서는 MDP를 가정하였다.

MDP를 사용하여 나타냈지만 이를 augmented state $(s_t, a_t)$로 변환하면 Markov chain으로 재정의할 수 있다. 즉 trajectory distribution을 Markov chain 형태로 나타낼 수 있다는 것이다.

\[p((s_{t+1}, a_{t+1}) \vert (s_t, a_t)) = p(s_{t+1} \vert s_t, a_t) \pi_ \theta (a_{t+1} \vert s_{t+1})\]

이때 RL의 목표는 expected value of sum of rewards over trajectories를 최대화하는 것이다. 이를 수학적으로 나타내면 다음과 같다.

\[\theta ^ \ast = \arg \max _ \theta \mathbb{E} _ {\tau \sim p_ \theta(\tau)} \left[ \sum _ t r(s_t, a_t) \right]\]

현재의 reward가 좋은 것 뿐만 아니라 미래의 reward 또한 중요하다. RL에서는 지금의 선택(action)을 통해 나중에 좋은 reward를 받도록 훈련시키는 것이 중요하다.

1.2.1. Finite Horizon Case: state-action marginal

Finite horizon case에서는 trajectory의 길이가 유한하다. 이때 $\tau$에 대하여 모든 reward를 더해야 하는 것을 대신 marginalize하여 $(s_t, a_t)$에 대해 reward를 더하는 것으로 더 간단하게 나타낼 수 있다. 여기서 $p_\theta (s_t, a_t)$를 state-action marginal이라고 한다.

\[\begin{aligned} \theta ^ \ast &= \arg \max _ \theta \mathbb{E} _ {\tau \sim p_ \theta(\tau)} \left[ \sum _ t r(s_t, a_t) \right] \\ &= \arg \max _ \theta \mathbb{E} _ {(s_t, a_t) \sim p_ \theta(s_t, a_t)} \left[ r(s_t, a_t) \right] \end{aligned}\]

1.2.2. Infinite Horizon Case: stationary distribution

Infinite horizon case에서는 $T = \infty$이므로 위 식의 값이 무한대가 되어 계산이 불가능하다. 이때는 1/T로 평균을 내주어야 한다. 또한 marginal distribution이 수렴한다면, $\mathcal{T}$의 eigenvector가 되어 stationary distribution으로 수렴하게 된다. 즉, 확률분포 $\mu_ t = p_\theta(s_t, a_t)$가 수렴한다고 하면 다음과 같이 나타낼 수 있다.

\[\mu_ {t+1} = \mathcal{T} \mu_t, \mu_ {t+1} = \mu_t = \mu \quad \rightarrow \quad (\mathcal{T} - \mathbf{I}) \mu = 0\]

즉 $\mu$가 $\mathcal{T}$의 eigenvector가 되고, 이때의 $\mu = p_\theta(s, a)$를 stationary distribution이라고 한다. 항상 수렴하는 것은 아니나, 일정 제한 조건 하에서는 항상 수렴하도록 만들 수 있다. 참고로 여기서 state-action transition operator $\mathcal{T}$는 다음과 같은 역할이다. 앞의 Markov chain, MDP와 정의가 다름을 주의하자.

\[\begin{pmatrix} s_{t+1} \\ a_{t+1} \end{pmatrix} = \mathcal{T} \begin{pmatrix} s_t \\ a_t \end{pmatrix}\]

따라서 objective를 다음과 같이 쓸 수 있다.

\[\theta ^ \ast = \arg \max _ \theta \frac{1}{T} \sum _t \mathbb{E} _ {(s_t, a_t) \sim p_ \theta(s_t, a_t)} \left[ r(s_t, a_t) \right] \rightarrow \mathbb{E} _ {(s, a) \sim p_ \theta(s, a)} \left[ r(s, a) \right]\]

RL에서는 이와 같이 expectation value를 objective로 많이 사용한다. 단순 reward function은 gradient 계산이 어렵거나 불가능하기 때문이다. 예를 들어 아래와 같이 차의 위치 $x$를 state로 모델링한다면, reward function $r(x)$는 불연속적이어서 gradient를 계산할 수 없다.

하지만 만약 $\pi_\theta (a = \text{fall}) = \theta$로 정의하고, $\mathbb{E} _ {a \sim \pi_\theta} \left[ r(x) \right]$를 계산하면 $\theta$에 대한 gradient를 계산할 수 있다. 즉 sparse reward function을 계산하기 위해서는 expectation을 사용해야 한다.

2. Algorithms

2.1. Overview

RL의 알고리즘은 굉장히 다양하지만 대개 아래의 3단계로 이해할 수 있다.

1. Generate sample: MDP에 따라 trajectory를 수집한다. Real world의 경우 이 단계에서의 cost가 매우 비싸지만, 가상환경에서는 저렴하게 수집할 수 있다.
2. Fit a model/Estimate the return: trajectory를 이용하여 reward를 계산하거나 미래 state를 예측한다.
3. Improve the policy: reward를 이용하여 policy를 개선한다.

2.2. Value Functions

RL objective를 다시 확인하자.

\[\mathbb{E}_ {\tau \sim p_ \theta(\tau)} \left[ \sum _ t r(s_t, a_t) \right]\]

이를 trajectory를 따라 다시 쓰면 다음과 같이 풀어 쓸 수 있다.

\[\mathbb{E}_ {s_1 \sim p(s_1)} \left[\mathbb{E}_ {a_1 \sim \pi (a_1 \vert s_1)} \left[ r(s_1, a_1) + \mathbb{E}_ {s_2 \sim p(s_2 \vert s_1, a_1)} \left[ \mathbb{E}_ {a_2 \sim \pi (a_2 \vert s_2)} \left[ r(s_2, a_2) + \cdots \vert s_2 \right] \vert s_1, a_1 \right] \vert s_1 \right] \right]\]

다음과 같이 $Q(s_1, a_1)$을 정의하자.

\[Q(s_1, a_1) = r(s_1, a_1) + \mathbb{E}_ {s_2 \sim p(s_2 \vert s_1, a_1)} \left[ \mathbb{E}_ {a_2 \sim \pi (a_2 \vert s_2)} \left[ r(s_2, a_2) + \cdots \vert s_2 \right] \vert s_1, a_1 \right]\]

이때 objective를 다음과 같이 간단하게 나타낼 수 있다.

\[\mathbb{E}_ {s_1 \sim p(s_1)} \left[ \mathbb{E}_ {a_1 \sim \pi (a_1 \vert s_1)} \left[ Q(s_1, a_1) \right] \right]\]

만약 $Q(s_1, a_1)$을 알고 있다면 $\pi_\theta(a_1 \vert s_1)$을 쉽게 학습하여 바꿀 수 있을 것이다. 예를 들어 $a_1 = \arg \max _ {a_1} Q(s_1, a_1)$이라면 $\pi_\theta(a_1 \vert s_1)=1$으로 설정하는 등으로 말이다. 이때 $Q$를 Q function이라고 하며, 이는 결국 $s_t, a_t$ 이후의 total reward를 계산한 것이다.

\[Q^ \pi (s_t, a_t) = \sum _ {t' = t} ^ T \mathbb{E} _ {\pi_ \theta} \left[ r(s_{t'}, a_{t'}) \vert s_t, a_t \right]\]

이때 value function $V(s_t)$는 $Q(s_t, a_t)$와 유사하게 정의되며, $s_t$에만 conditioned된다. 이는 $s_t$ 이후의 total reward를 계산한 것이다. RL의 objective는 이제 $\mathbb{E}_ {s_1 \sim p(s_1)} \left[ V^ \pi (s_1) \right]$로 나타낼 수 있다.

\[\begin{aligned} V^ \pi (s_t) &= \mathbb{E} _ {\pi_ \theta } \left[ r (s_t, a_t) \vert s_t \right] \\ V^ \pi (s_t) &= \mathbb{E} _ {a_t \sim \pi (a_t \vert s_t)} \left[ Q^ \pi (s_t, a_t) \right] \end{aligned}\]

그렇다면 Q-function과 value function을 어떻게 사용할까? 여기에서는 두 가지 아이디어를 제시한다.

첫 번째는 $Q^ \pi (s, a)$를 알 때 policy $\pi$를 다음과 같이 업데이트하는 것이다. 다음과 같이 하면 policy $\pi ^ \ast$는 적어도 $\pi$ 이상의 reward를 받을 것이다.

\[\pi ^ \ast (a \vert s) 1 \text{ if } a = \arg \max _ a Q^ \pi (s, a)\]

두 번째는 good action $a$의 확률을 높이는 쪽으로 gradient를 계산하는 것이다. 만약 $Q^ \pi (s, a) > V ^ \pi (s)$이면 $a$는 평균 action보다 좋은 셈이다. ($V^ \pi (s) = \mathbb{E} \left[ Q^ \pi (s, a) \right]$) 따라서 policy $\pi(a \vert s)$를 $a$의 확률이 높아지도록 업데이트한다.

이 두 아이디어는 RL에서 아주 중요하고, 이후 강의에서도 계속 사용될 것이다. 이러한 방법은 algorithm 상에서 fit a model/estimate the return step에서 사용된다.

2.3. Classification of Algorithms

Algorithm은 크게 다음과 같이 분류할 수 있다.

• Direct Policy gradients: Explicit policy를 직접 업데이트한다.
• Value function based: Explicit policy가 없고, value function이나 Q function을 예측한다.
• Actor-critic: Policy를 업데이트하면서 value function을 예측한다. 일종의 hybrid이다.
• Model-based RL: Transition $\mathcal{T}$를 예측하는 모델을 만든다. Policy update의 경우 여러 옵션이 있다.
  1. No explicit policy: 다른 algorithm을 사용하여 action을 예측한다. 모델은 다음 state만 예측한다.
  2. Explicit policy: Backpropagation을 사용하여 policy를 업데이트한다.
  3. Etc: Model을 사용하여 value function을 학습한다. (Dynamic programming 등)

각 내용을 표로 정리하면 다음과 같다.

Algorithm	Direct Policy Gradients	Value function based	Actor-critic	Model-based RL
Fitting	evaluate $R_\tau = \sum_ t r(s_t, a_t)$	fit $V(s)$ or $Q(s, a)$	fit $V(s)$ or $Q(s, a)$	learn $s_{t+1} \approx f_\phi (s_t, a_t)$
Policy Improvement	$\theta \leftarrow \theta + \alpha \nabla _ \theta \mathbb{E} \left[\sum_t r(s_t, a_t) \right]$	set $\pi(s) = \arg \max _ a Q(s,a)$	$\theta \leftarrow \theta + \alpha \nabla _ \theta \mathbb{E} \left[Q(s,a) \right]$	a few options

2.4. Tradeoffs between Algorithms

Algorithm을 선택할 때는 다음과 같은 tradeoff를 고려해야 한다.

2.4.1. Sample Efficiency

Sample efficiency는 좋은 policy를 만들기 위해 얼마나 많은 sample이 필요한지를 의미한다. Off-policy보다 on-policy가 덜 효율적이다. Off-policy란 해당 policy로부터 샘플을 새로 생성하지 않아도 훈련이 가능한 것이고, on-policy는 해당 policy로부터 샘플을 새로 생성해야만 훈련이 가능한 것이다. 그렇다면 비효율적인 알고리즘을 사용하는 이유는 무엇인가? 만약 simulation 환경인 경우를 가정한다면, sample을 쉽게 생성할 수 있기 때문이다. 즉 wall clock time과 efficiency는 다르다. 예를 들어 체스 경기 시뮬레이션 학습 등에서는 off-policy를 사용해도 무방하다.

2.4.2. Stability and Ease of Use

Supervised learning과는 달리 RL은 gradient descent를 사용하여 학습하지 않을 때도 있다. Model-based RL에서는 model이 RL objective를 훈련하는 것이 아니라 정확도 있게 다음 state를 예측하는 것을 훈련한다. 즉 모델은 converge해도 RL algorithm 자체가 converge하지 않을 수 있다. Q-learning도 Q function을 훈련하는 것이지 RL 자체를 훈련하는 것이 아니다. Policy gradient는 gradient descent를 사용하지만 가장 덜 효율적이다. 이러한 문제로 다음과 같은 것들을 RL에서 고려해야 한다.

• 모델이 수렴하는가?
• 수렴한다면 어디로 수렴하는가?
• 항상 수렴하는가?

2.4.3. Assumptions

알고리즘에 따라 가정(assumption)하는 것이 다르다. 따라서 상황에 맞게 모델을 선택해야 한다. 알고리즘에 따른 일반적인 가정을 다음과 같이 정리하였다.

Assumption	Models
Full observability	Value function based
Episodic learning	Policy gradient, Model-based
Continuity or Smoothness	Continuous value function based, Model-based

CS285 카테고리 내 다른 글 보러가기