[RL] David Silver RL Lecture 9: Exploration and Exploitation

Date: 2025.01.21 Updated: 2025.01.22

카테고리: RL Lecture

태그: RL

1. Introduction

1.1 Exploration vs Exploitation Dilemma

online decision making은 중요한 선택을 해야한다.

Exploitation : 주어진 현재 정보에서 최선의 결정을 한다.
Exploration : 정보를 더 모은다.

최선의 long-term 전략은 short-term의 희생이 있어야하고, 최선의 결정을 하기 위해선 정보를 많이 모아야한다.

Example

Restaurant Selection

Exploitation : 좋아하는 레스토랑으로 간다
Exploration : 새로운 레스토랑을 시도한다.

Game Playing

Exploitation : 최고라고 생각하는 방식으로 플레이
Exploration : 실험적인 무빙으로 플레이

Principle

Random Exploration

Explore random actions (ε-greedy, softmax)

Optimism in the face of Uncertainty

value의 불확실성을 평가한다.
높은 불확실성을 가진 state/action 탐험을 선호한다.

Information State space

agent의 정보를 그 state의 일부분으로 고려
정보가 어떻게 reward를 돕는지 본다

1.2 State-action Exploration vs parameter Exploration

State-action exploration

시스템적으로 state space / action space를 탐험한다.
ex) time S마다 다른 action A를 한다.

Parameter exploration

파라미터화 된 policy $π(A∣S,u)$
장점 : 지속적으로 탐험을 할 수 있다.
단점 : state/action space에 대해서 모른다.

이번 강의에서는 state-aciton exploration에 집중을 한다.

2. Multi-Armed Bandit

2.1 The Multi-Armed Bandit

mulit-armed bandit은 튜플 <$A,R$>이다.

A는 m개의 action의 집합이고, R의 확률분포는 알지 못한다.

각 step t마다 agent는 action을 하고 env는 reward를 발생시킨다.

목표는 cumulative reward를 maximize하는 것이다.

2.2 Regret

action-value : action a에 대한 reward의 평균값 q(a) = E[R∣A = a]

optimal value $v_*$는 아래와 같다.

regret : 한 단계에 대한 opportunity loss, 즉 optimal value와의 차이

total regret : regret의 합산

Maximise cumulative reward = minimise total regret

Counting Regret

count $N_t(a)$는 action a를 한 횟수

gap $Δ_a$는 optimal action a*와 action a 사이의 value 차이 ($Δ_a$ = $V^*$ - $q(a)$)

regret은 count와 gap의 함수이다.

regret은 τ = 1부터 t까지 optimal value와 q(a)의 value 차이의 합이다.

즉 τ=1부터 t를 count로 바꿀 수 있고, optimal value와 q(a)의 value 차를 gap으로 바꿀 수 있다.

최고의 알고리즘은 높은 count를 하고 낮은 gap을 갖는것이다.
문제는 gap을 모른다는 것이다.(optimal action을 모름)

explore를 계속하는 것과 절대 하지 않는 것 둘다 linear total regret을 갖는다.

2.3 Greedy Algorithm and epsilon-greedy Algorithm

Greedy Algorithm

q를 추정할 수 있는 알고리즘을 안다고 가정하자.

MC evaluation으로 각 action마다 value를 추정한다.

greedy algorithm은 가장 높은 value를 하는 action을 선택한다.

그렇게 되면 greedy는 sub-optimal한 action에 평생 갇힐수있다.

⇒ Greedy는 total regret이 linear하게 올라감

ε-greedy Algorithm

ε-greedy algorithm은 평생 explore를 하는 것이다. (1-ε) 확률로 greedy, ε확률로 explore

지속적인 ε가 minimum한 regret을 보장한다.

⇒ ε-Greedy는 total regret이 linear하게 올라감

ε-Greedy Algorithm with Optimistic Initialization

value 초기화를 가능한 제일 큰 값으로 설정하고. ( Q(a) = $r_{max}$ ) greedily하게 act한다.

제일 큰 값으로 설정을 하고 bandit을 하면 value가 점점 내려간다. 그렇게 되면 거의 모든 모르는 value까지 exploration을 할 수가 있다. 하지만 운이 없는 경우 optimal action에 도달하지 못할 수도 있음

⇒ Optimistic greedy도 total regret이 linear하게 올라감

Decaying $ε_t$-greedy Algorithm

decay schedule ε1, ε2 … 를 고른다.

d : 1등 bandit과 2등 bandit의 차이, 즉 d가 커지면 ε은 작아진다.

⇒ ε확률을 상황에 맞게 조절이 가능하다. 초반에는 explore를 많이하다가 후반에는 줄일 수 있음

하지만 이를 위해서는 gap을 알아야한다. 이제 목표가 R에 대한 정보없이 모든 bandit에 적용가능한 sublinear regret을 가진 algorithm을 찾는 것이다.

Lower Bound

알고리즘의 성능은 optimal arm과 other arms의 유사도가 결정을 한다. 알고리즘을 아무리 잘짜도 total regret이 내려갈 수 없는 lower bound가 존재를 한다.

어려운 문제는 optimal arm과 other arms의 평균은 다른데 매우 유사하다.

유사도를 나타내기 위해서 KL divergence를 도입한다. $KL(R^a∣∣R^{a^∗})$

확률분포가 비슷할 수록 KL 값이 작아진다

2.4 Upper Confidence Bound

Optimism in the Face of Uncertainty

어떤 action을 골라야 할까?

파란색은 uncertainty가 큰 상태 (신뢰구간이 넓다 = 신뢰도가 낮다)
초록생은 uncertainty가 작은 상태 (신뢰구간이 좁다 = 신뢰도가 높다)

불확실성을 긍정적으로 바라보자, action-value에 대해서 정보가 없으면 없을수록 action을 explore하는 것이 중요하다. 정확한 정보를 모르니까 그것이 best action이 될 수도 있다.

파란색을 고른 후의 모습인데 value에 대해서 불확실성이 줄었고(신뢰구간이 좁아졌고), 최적의 action을 고를 때 까지 다른 action을 고를 확률이 올라갔다.

Upper Confidence Bounds

각 action value에 대해서 upper confidence bound를 추정한다.

95% 신뢰구간 : 실제값 Q(a)가 이 구간에 들어있을 확률이 95%

$N_t(a)$가 작아지면 $\bar{U}$는 커진다 → 불확실성 때문에 구간을 넓힘

$N_t(a)$가 커지면 $\bar{U}$는 작아진다 → 정확성하게 value 추정가능

⇒ 같은 정확도로 말하기 위해선 넓은 구간을 필요로하다.

UCB를 최대화 하는 action을 선택한다. 즉, 현재 추정된 가치의 합이 최대가 되는 행동을 선택한다.

그렇다면 Upper bound를 어떻게 구할수있을까?

Hoeffding’s Inequality

(모평균 > 표본평균 + u)일 확률 즉 모평균 - 표본평균이 u보다 클 확률이 우항값 이하이다.

직관적으로 이해해보면 u : 틀린정도이고, u가 커질수록, t가 많을수록 확률은 작아진다

이것을 앞서 구한것들을 넣어보면 다음과 같이 구할 수 있다.

적당한 p 값 설정을 하고 UCB를 계산해보면 $U_t(a)$를 구할 수 있다.

$p = t^{-4}$로 설정을 하고 값을 계산하면 다음과 같이 되고

이 값을 활용한게 UCB1 Algorithm이다.

Example: UCB vs ε-Greedy On 10-armed Bandit

놀랍게도 ε-greedy 가 생각보다 성능이 좋은 경우가 많다. 대신 tuning을 잘못하면 재앙이다.

반면 UCB는 systemically perform well

ε-greedy와 UCB의 성능이 비슷한 이유

⇒ hoeffding’s Inequality은 약한 부등식이다. 모분포에 대해서 가정하는 것이 많이 없다. 심지어 symmetric하지 않아도 된다. 딱 하나 있는게 reward가 bounded가 되어있다는 가정이 있어야 사용할 수 있다.

ex) bandit machine의 제일 높은 당첨금 10000$$이다. 라는 상한이 있어야됨

즉 hoeffding’s Inequality는 가정이 적은만큼 약한 부등식이다.

2.5 Bayesian Bandits

지금까지는 reward에 bound가 있다는 것 외에 reward에 분포에 대한 다른 가정이 없었다.

bayesian bandits는 reward 분포에 대한 prior knowledge를 사용한다는 것이다. 이를 통해 posterior distribution(사후 분포)를 구하는 것이다.

사후 분포를 통해 exploration을 guide하는 두가지 방식을 사용할 수 있다.

Upper confidence bounds (Bayesian UCB)
Probability matching (Thompson sampling)

prior knowledge가 정확할수록 성능이 좋아진다.

예컨데 각 bandit은 서로 independant한 gaussian 분포이다. (1번을 한다고 2번이 달라지지 않는다.)

가우시안 분포라고 prior를 잡고 실제 몇번 수행해서 posterior구하는 방식을 통해 신뢰구간을 구할 수 있다. 이것을 이용하면 baysian UCB가 된다.

Thompson sampling

probability matching의 한 예시

베이즈 법칙을 이용해 posterior 분포(Reward에 대한 분포)를 구하고 그를 통해 R을 sample한다. 가장 높은 reward를 가진 action을 선택하는 하는 것

선택된 action을 통해 sampling된 값으로 다시 분포를 계산하고 다시 sampling 반복

베르누이 bandit일 때는 thompson sampling이 Lai and Robbins lower bound가 achieve하다.

베르누이 bandit이 아니라 다른 bandit에서도 좋긴한대 애초에 prior가 좋아야 잘 작동을한다.

2.6 Information State Search

Value of Information

exploration은 정보를 얻을 수 있기 때문에 매우 유용하다.

우리가 정보의 가치를 정량화 할 수 있을까?

불확실한 상황에서 정보 gain이 크다 그러므로 불확실한 상황에서 exploration을 하는 것은 make sense하다.
만약 정보의 가치를 알수 있다면, exploration과 exploitation을 optimal하게 사용가능하다.

Information State Space

MDPs는 information state를 추가해 재정의할 수 있다.

확장된 상태는 < $s$, $\tilde{s}$ >로 표현하고

$s$는 MDP의 원래 state이고
$\tilde{s}$는 history(축적된 정보)의 통계이다.

각 action a에 따른 transition은

$s'$ : 확률 $P_{s,s'}^a$으로 이동하는 new State
$\tilde{s'}$ : 새로운 information state

information state space에서 MDP $\tilde{M}$는 다음과 같이 정의된다.

2.7 Summary

Random exploration
- $\epsilon$-greedy
- Softmax
- Gaussian noise
Optimisim in the face of uncertainty
- Optimistic initialisation
- UCB
- Thompson sampling
Information state space
- Gittins indices
- Bayes-adaptive MDPs

3. Contextual Bandits

context를 고려하여 최적의 reward를 받는 action을 선택하게 하는 것

context : 의사결정을 하는데 관측가능한 정보, action을 선택하는데 영향을 끼치는 요인

사용자에게 어떤 광고를 보여줘야 할지 선택하는 문제에 적용이 가능하다

Contextual bandit은 튜플 $<A,S,R>$ 이다.

A : actions의 집합

S : State에 대한 알려지지 않은 분포

R : reward에 대한 알려지지 않은 분포

각 단계 t마다

Environment는 state를 발생시킨다
Agent는 action을 선택하고
Environment는 reward를 발생시킨다.

Goal : 축적된 reward의 maximise

4. Conclusion

exploration/exploitation에 관한 여러 Principle들에 대해서 배웠다.

Naive methods such as $\epsilon$-greedy
Optimistic initialisation
Upper confidence bounds
Probability matching
Information state search

각 Principle은 bandit 상황에서 나온거지만 MDP에서도 적용이 가능하다.

맨 위로 이동하기

Ssong