기록: UCL Course on RL 요약 및 정리 (Lecture 9: Exploration and Exploitation)

This post covers not only Lecture 9: Exploration and Exploitation (davidsilver.uk) but also:


Lecture Goal
  • MDP를 풀 때 exploration과 exploitation 중 어느 한 쪽만 사용하면 optimality에 도달하지 못한다 (trade-off). 본 강의에서는 둘 사이의 균형을 맞추는 알고리즘을 소개한다.
Credit: UC Berkeley Intro to AI course lecture 11

Takeaway
  • Use (Bayes-)UCB algorithms

Exploration vs. Exploitation Dilemma
  • Exploitation: make the best decision given current information
    • E.g., go to your favorite restaurant
  • Exploration: gather more information
    • E.g., try a new restaurant
  • Dilemma
    • The best long-term strategy may involve short-term sacrifices and risks
  • How does an agent obtain enough information to make the best overall decisions with the lowest sacrifices?

[In-A-Nutshell] Key Principles and Intuitions for Balancing Exploration and Exploitation
  • Random exploration
    • E.g., \(\epsilon\)-greedy: naive exploration adding noise to greedy policy
  • Optimism in the face of uncertainty
    • Method 1: optimistic initialization
      • Initialize action-value function \(Q(s,a)\) to some large value
      • 처음부터 initial value를 과하게 큰 값으로 주면, experience를 통해 이미 방문해본 action의 value는 initial value보다 작아진다.
      • 이렇게 아직 선택해보지 않은 액션의 value가 선택해본 액션의 value보다 항상 크다면 exploration을 장려할 수 있다.
    • Method 2: upper confidence bounds
      • 자주 방문해본 action은 return을 상당히 정확하게 추정할 수 있는 반면, 몇 번 방문해보지 않은 action은 return 추정이 불확실하다. 따라서, 불확실성(uncertainty)을 정량화 한 뒤에, 불확실성이 더 큰 action을 취하도록 하면 exploration을 장려할 수 있다.
      • 불확실성을 정량화하는 도구가 confidence bounds/interval
      • \(\Rightarrow\) UCB algorithm, Bayesian UCB
    • Method 3: probability matching
      • Select an action according to the probability that the action is best among other actions
      • 최종 보상을 높이기 위한 아주 직관적인 방법
      • 이것도 upper confidence bounds를 고려한 exploration처럼, 얼마 방문해보지 못한 action은 return의 분산이 크므로, 다른 action보다 평균적인 return이 더 클 수도 있다는 직관을 활용
      • Bayesian bandit
      • \(\Rightarrow\) Thompson sampling
    • Cons of the optimism
      • 로봇이나 헬리콥터 등 심각한 음의 reward를 갖는 (접촉사고, agent 파손 등) RL 문제에서는 오히려 아주 안전한 선택을 위해 uncertainty에 비관적인 선택을 해야 하기도 한다.
      • 또한, action space가 무한해서 아무리 exploration을 해도 더 explore해야 하는 space가 남아 있다면 영원히 알고리즘이 수렴하지 못한다.
  • Information state space search
    • Exploration is useful because it gains information
    • Can we quantify the value of information? 
    • If we quantify the value of information, we can trade-off exploration and exploitation optimally.
    • Bernoulli bandit
    • \(\Rightarrow\) Bayes-adaptive MDP, Gittins indices

Simplified Setting: Bandit
  • We first develop each of the above principles in several simplified settings, called bandit problems.
  • But the same principles also apply to the MDP settings.

Multi-Armed Bandit Problem

Def. Regret
    • 세번째 bullet point에서 기댓값은 (당연히도) 각 time-step에서 어떤 action을 선택할 확률에 (즉, policy) 의해 결정된다: \(\pi(a)=\mathbb{P}[a_t=a]\).

  • 문제는, optimal value를 모르기 때문에 regret도 정확히 구할 수 없으므로, 결국 각 액션의 gap을 추정하는 문제로 귀결된다.
  • 직관적으로, 안 좋은 (gap이 큰) 액션을 최대한 적게 뽑고 좋은 액션을 최대한 자주 뽑아야 totol regret이 줄어든다.

Linear or Sublinear Total Regret
  • \(\epsilon\)-greedy policy은 대표적인 exploration 방법이다. 그러나 끊임없이 일정한 빈도로 무작위한 액션을 선택하기 때문에, 최고의 액션 하나만을 선택하지 못하고 끊임없이 sub-optimal 액션 혹은 아주 나쁜 액션을 선택하게 된다. 따라서 선형적으로 total regret이 증가한다.
  • Greedy policy는 처음에 선택한 (또는 각 액션마다 몇 회의 exploration을 한 뒤 얻은 value의 평균값으로 선택한) 액션이 운좋게 best action이 아닌 이상에야, 계속 total regret이 증가할 수 밖에 없다.
  • 일반적으로 \(\epsilon\)-greedy의 \(\epsilon\) 값을 시간이 지남에 따라 점차 줄여 나가면 sublinear total regret을 얻을 수 있다.

Optimistic Initialization
  • Initialize action-value function \(Q(s,a)\) (e.g., approximation function, tabular data structure, etc.) larger than the maximum possible reward.
    • E.g., \(Q(s,a) \leftarrow \frac{r_{\max}}{1-\gamma} \forall s,a\)
    • Note: \(r+\gamma r + \gamma^2 r + \cdots = \frac{r}{1-\gamma}\) if \(0 \le \gamma < 1\)
  • It encourages an agent to explore unproven actions.
  • 아직 선택해보지 않은 액션의 value는 선택해본 액션의 value보다 항상 크므로, exploration을 장려할 수 있다.
  • But can still lock onto suboptimal action
    • 초반에만 exploration을 하고, 시간이 지난 후에는 exploitation만 수행하게 됨
    • Greedy + optimistic init. \(\rightarrow\) linear total regret
    • \(\epsilon\)-greedy + optimistic init. \(\rightarrow\) linear total regret

Lower Bound of Total Regret over Time
  • \(\Rightarrow\) 의미: 잘해봐야 regret은 시간에 대해 지수적으로 증가한다. 혹은, 지수적으로 증가하는 exploitation-exploration 알고리즘을 만들었다면 꽤 잘하는 축에 드는 것이다.
  • 분자: action끼리 서로 reward 평균값이 다를수록 total regret 상승
  • 분모: action끼리 서로 reward 분포가 비슷할수록 total regret 상승
  • \(\Rightarrow\) (직관적으로도) 차선과 최선의 action이 모양은 비슷하나 평균이 크게 다른 reward 분포를 가지면, 차선과 최선의 action을 구분하기 어려워 total regret을 줄이기 힘들다.

Decaying \(\epsilon_t\)-Greedy Algorithm

Upper Confidence Bounds
  • 자주 방문해본 action은 return을 상당히 정확하게 추정할 수 있는 반면, 몇 번 방문해보지 않은 action은 return 추정이 불확실하다. 따라서, 불확실성(uncertainty)을 정량화 한 뒤에, 불확실성이 더 큰 action을 취하도록 하면 exploration을 장려할 수 있다.
  • 이를 수식으로 보충 설명하면 아래와 같다:
    • Multi-armed bandit 문제에서 action \(a\)를 \(N_t(a)\)회 선택했다고 하고 그 return을 \(\hat{Q}_t(a) = \frac{1}{N_t(a)}\sum_{\tau=1}^{t}r_{\tau}\mathbb{1}(a_\tau=a)\)로 추정하는 상황을 가정하자. Reward 분포는 0과 1사이에서만 정의된다 가정하자 (따라서, bounded distribution에만 적용 가능).
    • 즉, \(\hat{Q}_t(a)\)는 모평균 \(Q(a) = \mathbb{E}[r|a]\)를 근사하는 표본 평균이다.
    • 그러면 아래 Hoeffding의 정리에 따라, 실제 알고자 하는 \(Q(a)\)가 지금까지 샘플링으로 알아낸 \(\hat{Q}_t(a)\)보다 \(U_t(a)\) 만큼 클 가능성은 \(\exp(-2N_t(a)U_t(a)^2)\)보다 낮거나 같다.
    • 달리 말하면, 실제 \(Q(a)\)가 존재할 가능성이 최소 \(1-\exp(-2N_t(a)U_t(a)^2)\)만큼 되는 구간을 찾자면, \(\hat{Q}_t(a)+U_t(a)\) 이하의 구간이다. 즉, \(Q(a) \le \hat{Q}_t(a)+U_t(a)\)임을 최소 \(1-\exp(-2N_t(a)U_t(a)^2)\)만큼의 자신감으로 주장할 수 있다. 따라서 \(\hat{Q}_t(a)+U_t(a)\)를 upper confidence bound라고 한다.

  • UCB1 algorithm
    • Select an action maximizing \(\hat{Q}_t(a)+\sqrt{\frac{2\log{t}}{N_t(a)}}\) (아래 수식 hat 틀림)

  • UCB vs. \(\epsilon\)-greedy
    • \(\epsilon\)을 잘 선택하면 UCB만큼 잘할 수 있다. 그러나 \(\epsilon\)을 잘 선택하는 게 어렵다.
  • Others than Hoeffding's inequality
    • Hoeffding의 부등식은 확률 변수 \(X_i\)에 거의 아무런 조건도 가정하지 않는다. 범용성이 높다는 장점도 있지만, 모든 케이스에서 다 적용되는 부등식이다 보니 bound \(\exp(-2N_t(a)U_t(a)^2)\)가 너무 헐겁다는 단점도 있다. Reward \(R_t\)의 분포에 관해 이미 알고 있는 쓸만한 정보가 있다면 (e.g., Bernoulli), UCB에 다른 부등식 공식을 적용해 더 엄격한 bound를 구할 수 있다:
    • Bernstein's inequality
    • Empirical Bernstein's inequality
    • Chernoff's inequality
    • Azuma's inequality

Model-Free RL: Upper Confidence Bounds
  • MDP에도 UCB를 거의 그대로 적용할 수 있느나, 실은 미래에 policy improvement가 진행되면서 얼마나 각각의 action-value가 향상될 것인지도 고려해야 한다. 즉, 아직 탐색하지 않은 action은 향후 policy improvement가 진행되면서 더욱 향상될 가능성이 있다고 보는 것이다.


Model-Based RL: Bayesian UCB
  • Disclaimer: UCL 강의에서 Bayes 관련 내용들을 (BayesUCB 등) 제대로 설명하지 않고 굉장히 추상적이고 비유적으로만 해석하고 넘어간다.
  • 위 UCB 알고리즘에서는 단순히 시점 \(t\)까지 action \(a\)를 선택한 횟수 \(N_t(a)\)만 저장해서 upper confidence bound를 계산하였다.
  • 그리고 Hoeffding의 정리는 확률 변수의 범위를 제외하고는 아무것도 가정하지 않기 때문에 confidence interval이 상당히 성기다. 확률 변수의 모양이나 분포에 관해 좀 더 정확한 정보를 RL experience를 통해 얻을 수 있다면, confidence interval을 좀 더 정확하게 파악할 수 있다.
  • Model-based RL에서는 transition probabilities와 rewards 정보를 학습 과정(experience)에서 저장하므로 이걸 이용해보자는 게 Bayesian bandit과 Bayesian UCB
  • Bayesian UCB
    • Likelihood: Transition probabilites와 rewards의 모수가 주어질 때 둘은 어떤 분포(e.g., Gaussian, Bernoulli)를 따른다고 가정하자.
    • Prior: likelihood가 특정 분포라고 할 때, 해당 분포의 모수가 어떤 분포를 띌지도 가정해야 한다. 예를 들어, likelihood를 카테고리 분포로 둔다면, 이 분포의 모수는 0부터 1사이의 값을 가지므로 prior를 디리클레 분포라고 가정할 수 있다.
    • Posterior: 우리가 원하는 건, model이 추적한 현재까지의 history에 근거했을 때 rewards(와 transition)가 어떤 모수를 가질지 알아내는 것이다. 가장 그럴 듯한 모수를 찾아내면 likelihood의 가정에 따라 reward 분포를 알아낼 수 있다. 베이즈 정리에 따르면, \(\mathrm{(posterior)} \propto \mathrm{(likelihood)\cdot (prior)}\)이다.
    • 이런 과정을 통해, 현재까지 학습한 정보인 history를 관찰함으로써 rewards와 transition probabilities 분포를 추정할 수 있다.
  • Bayesian UCB example: independent Gaussians
    • Suppose reward distribution is Gaussian \(\mathcal{R}^a(r) = \mathcal{N}(r;\mu_a,\sigma_a^2)\).
      • 따라서 모수만 정확히 알면 \(\mathcal{R}^a(r)=\mathbb{P}[r|a]\)의 분포를 알 수 있고 그럼 기댓값을 계산할 수 있으므로 \(Q(a)=\mathbb{E}[r|a]\)를 알 수 있다. 문제는 모수를 모른다는 것. 따라서 현재까지의 history와 Bayes law를 근거로 이 모수를 추정해보자.
    • Compute Gaussian posterior by Bayes law:
      • \(\mathrm{(posterior)} \propto \mathrm{(likelihood)\cdot (prior)}\)
      • \(\mathbb{P}[\mu_a,\sigma_a^2|h_t] \propto \mathbb{P}[h_t|\mu_a,\sigma_a^2] \cdot \mathbb{P}[\mu_a,\sigma_a^2]\)
        \(\mathbb{P}[\mu_a,\sigma_a^2|h_t] \propto \prod_{t|a_t=a} \mathcal{N}(r_t;\mu_a,\sigma_a^2) \cdot \mathbb{P}[\mu_a,\sigma_a^2]\)
      • \(h_t\)는 이때까지 어떤 액션과 어떤 reward를 얻었는지에 관한 기록 (action \(a\)에 관한 reward 기록만 있으면 되긴 함)
    • \(\mathbb{P}[\mu_a,\sigma_a^2|h_t]\)는 \(\mu_a,\sigma_a^2\) 만의 함수 이므로 미분한다거나 해서 posterior를 최대화하는 (즉, 가장 가능성 높아보이는) 모수를 찾는다 (maximum a posteriori).
    • Pick action that maximize UCB:
      • \(a_t = \mathrm{argmax}\;\mu_a+c\sigma_a/\sqrt{N_t(a)}\)
  • Cons of Bayesian UCB
    • Prior나 likelihood에 관한 가정을 하기 힘들 때, 그냥 UCB를 사용하는 게 낫다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

기록: UCL Course on RL 요약 및 정리 (Lecture 6: Value Function Approximation)

이미지
This post covers  Lecture 6: Value Function Approximation (davidsilver.uk)   The entire course materials can be found on the following page:  Teaching - David Silver . Lecture Goal Learn how to deal with a large-scale (potentially continuous) state space with RL Learn value function approximation Learn Deep Q-Network (DQN) and batch methods Credit:  Find order of polynomial approximation and LeastSquares for given datapoints Value Function Approximation Lookup table Table store an entry for each lookup index. Value-state Index = \(\forall s \in S\), where \(S\) is a finite and discrete state space Entry = \(V(s)\) Action-state Or every state-action pair \(s, a\) has an entry \(Q(s,a)\) Or every state \(s\) has entries \(Q(s,a)\) for all actions \(a \in A\) So far, we have represented a value function by a lookup table. Large MDPs Memory inefficiency : too many states or actions to store in memory Too slow to learn the value of each state individually Note: neighboring states might st
자세한 내용 보기

KAIST 회고 (1): 공부법 정리

이미지
(2021-08-29 초안 작성) 성적을 잘 받기 위한 기본 정리 1: 시험과 과제 마감일은 우리를 기다려주지 않는다 내용) 오늘 들은 강의는 이틀 내에 복습하라 해설) 엘리베이터 앞에 몇 초만 늦게 도착해도 먼저 엘리베이터에 타고 올라간 사람보다 많게는 수 분 가량 늦을 수 있다. 학교는 학생의 학습 능력을 매 초 마다 연속적으로 체크하지 않는다. 억울하지만, 시험 당일이나 과제 제출 당일에 퍼포먼스를 제대로 못 보여주면 그 후폭풍은 거대하다. 예를 들어, 한 학기 동안 매번 당일 수업 내용으로 다음 날 시험을 보는 상황을 가정하자. 매일 복습을 하는 학생과 항상 수업 이틀 뒤에 복습을 하는 (즉, 시험치고 다음 날) 학생이 있다면, 해당 학기가 끝난 뒤 두 학생의 이해도는 별반 차이 없을 것이다. 둘 다 공부를 제대로 했다는 가정 하에, 복습을 며칠 미룬다고 큰 차이가 날 리가. 다만 시험 성적은, 앞의 학생은 충분히 높을 것이고, 뒤의 학생은 비교적 낮을 것이다 (수업을 듣자마자 모든 걸 깨닫지 않는 이상). 이 예시에서 두번째 전략을 취한 학생은 매우 억울할 것이다. 그러나 이게 현실이다. 시험은 '당일까지'의 이해도를 측량한다. 과제도 마찬가지다.  현실에서는 시험이나 과제 전까지 충분히 시간을 주지 않느냐 반문할 수 있다. 그러나 매 강의는 시간 의존적이다. 오늘 듣는 강의는 필연적으로 지난 수업 일이나 저번 주, 심지어 선수 과목의 내용과 밀접한 연관이있다. 따라서, 당연히도, 오늘 들은 강의 내용을 다음 수업일까지 복습하지 않는다면, 다음 수업일의 강의 내용을 이해하는 게 매우 힘들어지고, 수업 시간에 제대로 이해하지 못하니 복습할 내용과 다시 공부할 내용은 눈덩이처럼 불어난다. 더 심하게는, 수업 시간에는 하나도 이해 못하고 시간을 날린 뒤, 방에 돌아와서 당일 강의록을 보면서 스스로 처음부터 공부해야 할 수 있다. 실제로 KAIST에서도 많은 학생들이 이런 식으로 공부하면서 강의 하나를 이해하는 데에 드는 시간을 두 배 혹은 그
자세한 내용 보기