[CS285] 4. Introduction to Reinforcement Learning
카테고리: CS285
태그: RL
💡 이 글은 『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단계로 이해할 수 있다.
- Generate sample: MDP에 따라 trajectory를 수집한다. Real world의 경우 이 단계에서의 cost가 매우 비싸지만, 가상환경에서는 저렴하게 수집할 수 있다.
- Fit a model/Estimate the return: trajectory를 이용하여 reward를 계산하거나 미래 state를 예측한다.
- 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의 경우 여러 옵션이 있다.
- No explicit policy: 다른 algorithm을 사용하여 action을 예측한다. 모델은 다음 state만 예측한다.
- Explicit policy: Backpropagation을 사용하여 policy를 업데이트한다.
- 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 |
댓글 남기기