ai theory

강화학습 기초 (9) - 아는 선택과 새로운 선택 사이

Junyoung Park · 2024-05-10 · 7 min

들어가며...

첫 글에서 Exploration과 Exploitation을 점심 메뉴로 짧게 소개했다.

Exploitation: 지금까지 가장 좋았던 단골집으로 간다.
Exploration: 아직 잘 모르는 새 식당을 시도한다.

SARSA와 Q-Learning에서도 $\epsilon$ -greedy Policy를 사용했지만, 왜 탐색이 필요한지는 자세히 다루지 않았다.

Q값이 가장 큰 Action을 고르는 것이 합리적으로 보인다. 문제는 학습 중인 Q값이 진짜 Action value가 아니라 지금까지 모은 경험으로 만든 추정값이라는 점이다.

처음 두 번 우연히 높은 Reward를 준 Action이 가장 좋아 보일 수 있다. Greedy action만 계속 고르면 다른 Action을 시도하지 않고, 더 좋은 선택이 있다는 사실을 영원히 모를 수도 있다.

탐색은 당장의 Reward 일부를 포기하고 정보를 사는 행동이다. 그 정보가 이후 더 좋은 선택으로 이어질 수 있으므로 장기적으로는 가치가 있다.

이번 글에서는 State transition이 없는 가장 단순한 환경인 Multi-Armed Bandit부터 시작한다.

Multi-Armed Bandit

Bandit은 여러 개의 손잡이가 달린 Slot machine에서 이름이 왔다. 각 Action, 즉 Arm을 선택하면 어떤 확률 분포에서 Reward 하나가 나온다.

\text{Bandit} = \langle \mathcal{A}, \mathcal{R} \rangle

$\mathcal{A}$ : 선택할 수 있는 Action 집합
$\mathcal{R}^a$ : Action $a$ 가 만드는 알려지지 않은 Reward 분포

MDP와 달리 Next State가 없다. 매 Step 현재 State가 달라지지 않는다고 생각해도 된다. Agent는 Action 하나를 고르고 Reward 하나를 관찰하는 일을 반복한다.

Action $a$ 의 진짜 값은 평균 Reward다.

Q(a) = \mathbb{E}[R \mid A=a]

하지만 Reward 분포를 모르므로 실제로 Action을 선택해본 Sample로 추정한다.

\hat{Q}_t(a) = \frac{1}{N_t(a)} \sum_{i=1}^{N_t(a)} R_i(a)

$N_t(a)$ 는 시간 $t$ 까지 Action $a$ 를 고른 횟수다.

많이 시도한 Action의 평균은 믿기 쉽지만, 거의 시도하지 않은 Action은 나쁜지 좋은지조차 아직 모른다.

그림에서 A의 추정값은 $4.8$ , B는 $4.2$ 다. Greedy하게 고르면 A를 선택한다. 하지만 C는 한 번밖에 시도하지 않아 값 자체가 불확실하다. 실제 평균이 $8$ 일 수도 있다.

Exploration은 이 불확실성을 줄이기 위해 C를 시도하는 일이다.

Greedy가 첫인상에 갇히는 경우

두 Action의 실제 평균 Reward가 다음과 같다고 하자.

Q(A)=5, \qquad Q(B)=7

첫 Sample에서 우연히,

R(A)=8, \qquad R(B)=2

가 나왔다고 하자.

현재 추정은 A가 $8$ , B가 $2$ 이므로 Greedy policy는 계속 A만 고른다. A를 반복하면서 추정값은 실제 평균 $5$ 에 가까워지지만, B는 더 이상 선택되지 않아 $2$ 에 멈춘다.

결국 실제로 더 좋은 B를 발견하지 못한다. Greedy action은 현재 추정에 대해서만 최선이지, 아직 모르는 실제 Reward 분포에 대해 최선이라는 보장은 없다.

Regret은 놓친 기회의 비용이다

Bandit에서는 탐색 방법을 Cumulative reward로 비교할 수 있다. 같은 내용을 Regret으로 표현하기도 한다.

가장 좋은 Action의 값은,

V_* = \max_{a \in \mathcal{A}} Q(a)

다.

시간 $t$ 에 Action $A_t$ 를 골라 놓친 기대 Reward를 Instantaneous regret이라고 생각할 수 있다.

\ell_t = V_* - Q(A_t)

전체 Regret은 이를 시간에 따라 더한 것이다.

L_T = \sum_{t=1}^{T} \ell_t

가장 좋은 Action만 알 수 있다면 Regret은 $0$ 이지만, 실제로는 무엇이 최선인지 모른다. 탐색 때문에 낮은 Reward의 Action을 고르면 당장 Regret이 생긴다. 반대로 전혀 탐색하지 않으면 잘못된 Action에 갇혀 오랫동안 Regret이 쌓일 수 있다.

좋은 Exploration Algorithm은 정보를 얻는 비용과 잘못된 선택을 계속하는 비용 사이를 조절한다.

ε-greedy: 가끔은 무작위로 시도하기

$\epsilon$ -greedy는 가장 단순하고 널리 쓰이는 탐색 방법이다.

확률 $1-\epsilon$ 으로 현재 Greedy action을 선택한다.
확률 $\epsilon$ 으로 전체 Action 중 하나를 Random하게 선택한다.

Action이 $m$ 개라면 Greedy action의 최종 선택 확률은,

1-\epsilon+\frac{\epsilon}{m}

이고 다른 각 Action은,

\frac{\epsilon}{m}

이다. Random 선택에서도 Greedy action이 다시 뽑힐 수 있기 때문이다.

예를 들어 Action이 $4$ 개이고 $\epsilon=0.1$ 이라면,

P(\text{greedy}) = 0.9+\frac{0.1}{4} = 0.925

다른 각 Action의 확률은,

\frac{0.1}{4}=0.025

다.

$92.5\%$ 는 현재 최선의 Action을 고르고, 나머지 세 Action은 각각 $2.5\%$ 확률로 선택한다.

ε-greedy는 단순한 Random 탐색을, UCB는 추정값에 불확실성 보너스를 더한 탐색을 사용한다.

ε을 계속 같은 값으로 둘까?

고정된 $\epsilon$ 을 쓰면 학습이 오래 진행된 뒤에도 같은 비율로 Random action을 고른다. 이미 모든 Action을 충분히 알아도 탐색을 멈추지 않는다.

초기에는 큰 $\epsilon$ 으로 넓게 탐색하고 시간이 지나면서 줄이는 Decaying $\epsilon$ 을 사용할 수 있다.

\epsilon_1 > \epsilon_2 > \cdots

하지만 너무 빠르게 줄이면 충분히 탐색하기 전에 잘못된 Action에 굳을 수 있다. 너무 느리게 줄이면 좋은 Action을 찾고도 불필요한 탐색을 오래 계속한다.

Tabular control의 수렴 조건에서 자주 등장하는 GLIE는 다음 두 성질을 함께 요구한다.

모든 State-Action을 무한히 자주 탐색한다.
극한에서는 Policy가 Greedy해진다.

이론적 조건을 실제 유한한 학습에 그대로 적용하기는 어렵지만, “탐색 기회는 충분히 주되 결국 좋은 Action을 더 자주 골라야 한다”는 방향을 보여준다.

Optimistic Initialisation

Q값을 처음부터 실제보다 높게 초기화하는 방법도 있다.

모든 Action의 실제 평균이 대략 $0$ 에서 $5$ 사이라고 예상되는데,

\hat{Q}_0(a)=10

으로 시작한다고 하자.

한 Action을 선택해 Reward $3$ 을 받으면 그 Action의 추정값은 내려간다. 아직 선택하지 않은 Action은 여전히 $10$ 이므로 Greedy policy라도 자연스럽게 다른 Action을 시도한다.

처음에는 “혹시 이 Action이 매우 좋을지 모른다”는 낙관적인 추정을 넣어 탐색을 유도하는 방식이다.

구현이 간단하지만 한계도 있다.

초기값을 얼마나 낙관적으로 둘지 정해야 한다.
모든 Action을 한 번씩 시도한 뒤에는 탐색 효과가 약해진다.
환경이 나중에 바뀌면 초기 낙관성이 다시 생기지 않는다.

UCB: 잘 모르기 때문에 높게 평가하기

$\epsilon$ -greedy의 Random 탐색은 지금까지 많이 시도한 나쁜 Action과 거의 시도하지 않은 Action을 구분하지 않는다. 탐색 Step에서는 둘 다 Random 후보가 된다.

Upper Confidence Bound, 줄여서 UCB는 각 Action의 추정값에 불확실성 Bonus를 더한다.

A_t = \arg\max_a \left[ \hat{Q}_t(a) + c \sqrt{ \frac{\ln t}{N_t(a)} } \right]

첫 항은 Exploitation이다.

\hat{Q}_t(a)

두 번째 항은 Exploration bonus다.

c \sqrt{ \frac{\ln t}{N_t(a)} }

$N_t(a)$ 가 작으면 Bonus가 크다.
많이 선택해 $N_t(a)$ 가 커지면 Bonus가 줄어든다.
$c$ 가 크면 불확실성을 더 중요하게 본다.

예를 들어 두 Action이 다음과 같다고 하자.

Action	추정값 $\hat{Q}$	Bonus	UCB
A	$5.0$	$0.2$	$5.2$
B	$4.2$	$1.5$	$5.7$

A의 평균은 더 높지만 B를 거의 시도하지 않아 Bonus가 크다. UCB는 B를 선택한다. B를 관찰하면 불확실성이 줄고 Bonus도 내려간다.

이 원리를 Optimism in the Face of Uncertainty라고 부른다. 모르는 선택이 실제로 좋을 가능성을 낙관적으로 평가하되, 경험이 쌓이면 낙관성을 자동으로 줄인다.

Bandit에서 MDP로 돌아오기

Bandit에는 State transition이 없지만 탐색 원리는 MDP에도 이어진다.

$\epsilon$ -greedy Q-Learning에서는 State $s$ 마다 Q값을 기준으로 Random action을 시도한다.

\pi(a \mid s) = \begin{cases} 1-\epsilon+\epsilon/m, & a=\arg\max_{a'}Q(s,a') \\ \epsilon/m, & \text{otherwise} \end{cases}

UCB 방식이라면 State-Action value에 방문 횟수나 불확실성 Bonus를 더해 Action을 고를 수 있다.

다만 MDP의 탐색은 Bandit보다 어렵다. 지금 선택한 Action이 즉시 Reward뿐 아니라 앞으로 방문할 State와 모을 Data까지 바꾼다. 문 하나를 열어봐야 그 뒤의 새로운 State들을 탐색할 수 있는 환경도 있다.

그래서 Random action만으로 충분하지 않은 Sparse reward 환경에서는 Count-based exploration, Curiosity, Intrinsic reward 같은 더 구조적인 방법이 사용된다. 이 내용은 이후 현실적인 RL을 다룰 때 다시 돌아볼 예정이다.

Exploration이 많을수록 좋은 것은 아니다

탐색은 공짜가 아니다.

의료나 Robot 환경에서는 잘못된 Action이 위험할 수 있다.
서비스 추천에서는 나쁜 Item을 보여주는 동안 사용자가 떠날 수 있다.
Offline RL에서는 새로운 Action을 실제로 시도할 수 없다.

“충분한 탐색”이 무조건 Random action을 많이 고른다는 뜻은 아니다. 불확실성을 줄이는 정보의 가치와 시행 비용을 함께 고려해야 한다.

초보 단계에서는 다음 질문을 먼저 확인하면 좋다.

모든 Action이 최소한 경험되고 있는가?
$\epsilon$ 이 너무 빨리 작아지지 않았는가?
평가할 때도 탐색 Noise가 켜져 있지는 않은가?
학습 환경에서 허용할 수 없는 위험한 Action은 없는가?
Reward 변화로 예전 Q값이 낡지는 않았는가?

이번 글에서 기억할 것

이번 글의 핵심은 다음과 같다.

Exploration은 당장의 Reward 일부를 정보와 교환해 장기적으로 더 좋은 Action을 찾는 과정이다.

조금 더 나누면 다음과 같다.

Greedy policy는 초기의 틀린 추정에 영원히 갇힐 수 있다.
$\epsilon$ -greedy는 대부분 Greedy action을 고르고 작은 확률로 Random 탐색한다.
고정된 $\epsilon$ 은 학습이 끝나도 탐색을 계속한다.
Optimistic initialisation은 높은 초기값으로 미방문 Action을 유도한다.
UCB는 추정값에 불확실성 Bonus를 더한다.
MDP에서는 Action이 앞으로 방문할 State까지 바꾸므로 탐색이 더 어렵다.

다음 글에서는 Update target의 시간 길이로 돌아간다. TD(0)는 한 Step, Monte Carlo는 Terminal까지 본다. 그 사이의 2-step, 3-step Return과 모든 길이를 섞는 TD( $\lambda$ ), Eligibility trace를 살펴볼 예정이다.