이번 포스팅은 reinforcement learning unit을 통해 진행했던 과제를 소개합니다.
과제는 실제생활의 어플리케이션 중 하나를 Environment로 구현하고, 적절한 Agent를 골라서 문제를 해결하는 방식으로 진행했습니다.

Reinforcement Learning에는 다양한 알고리즘이 존재하지만, 우리는 Contextual Multi-Armed bandits을 선정하여 진행했습니다.

과제를 구현하기 전, 필요한 사전지식 및 정보들을 우선 공유합니다.

---

Multi-Armed Bandits (MABs)?

Contextual Multi-Armed bandits을 소개하기 전 이것의 바탕이 되는 MABs를 알아보도록 합시다.

MABs는 카지노에서 어떤 슬롯머신에서 게임을 해야 최대한 많은 수익(보상)을 얻을 수 있을까에 대한 아이디어에서 고안되었습니다.

위의 그림에서 문어를 게임을 진행하는 player이라고 예를 들어보면, 이 player는 한 라운드당 한개의 슬롯머신의 arm을 당겨 게임을 진행할 수 있습니다. 각 슬롯머신의 arm을 당길때마다, 우리는 다른 수익률을 얻게 될 것입니다.

처음엔 수익률을 알지 못하니 모든 슬롯머신을 플레이 하다가, 어느순간 특정 슬롯머신이 높은 수익률을 가진다는 것을 알고, 그 기계로만 플레이를 하게 될 것입니다. MABs는 모든 슬롯머신을 플레이하며 탐색 하는 과정과 최적의 슬롯머신을 계속 활용하는 단계로써 진행될 것입니다.

즉, 어떤 슬롯머신이 어떤 수익률을 가지는지 모를때 Exploration(탐색)과 Exploitation(활용)을 적절히 사용하여 최적의 Reward을 찾고자 하는 RL의 알고리즘 중 하나입니다.

Exploration vs Exploitation

흔히 Exploration과 Exploitation이 trade-off 관계에 있다고 말합니다. 알고리즘이 계속 Exploration만 진행하다보면 최적의 행동을 고르지 않게 되어 보상이 낮을 것이며, Exploitation만 하다보면 우리는 미래의 더 나은 선택지를 알 수 없게 되겠죠. 그렇기 때문에, RL에서는 이 exploration과 exploitation을 적절한 비율로써 사용해야 합니다.

---

Contextual Bandits

간략하게 MABs의 정의에 대해서 살펴보았습니다. 그렇다면 Contextual Bandits은 어떤것을 의미할까요?

Contxtual Bandits은 Context을 고려하여 최적의 Reward를 받는 action을 선택하게 하는 것입니다. Context란 의사결정을 하는데 관측가능한 정보를 일컫는데, action을 선택하는데 영향을 끼치는 요인입니다. Contextual Bandits을 활용해서 실제생활의 어플리케이션을 만들 수 있습니다.

온라인 광고 선택 어플리케이션을 예로 들었을 때, 사용자의 Feature(검색어, 나이, 성별 등)을 고려하여 어떤 광고를 보여줄지 선택하는 문제에 사용할 수 있습니다.

Contextual Bandit Terms

컨텍스트 밴딧 문제는 다양한 알고리즘(agent)을 사용해서 실행될 수 있습니다. 이것을 소스화 하기 위해서는 여러가지 사항이 고려되어야 합니다.

• Number of actions $A$: 선택가능한 action의 수
• Context feature dimensions $d$: 컨텍스트의 차원입니다. 온라인 광고 선택 어플리케이션을 예로 들었을 때, context는 user가 될 것이며, feature는 user의 검색어, 나이, 성별 등이 되겠죠. 이 때, $d$의 크기는 3이 될 것입니다.
• Context generator: Context를 어떻게 생성 혹은 선택하느냐에 대한 방법입니다. 정규분포를 따르는 난수를 context로 사용할 수도 있고, user의 데이터가 있다면, 유저를 고르는 방법 등이 generator로 사용될 수 있을 것입니다.
• Expected Reward function (action-values function) $q(a_t, x_t)$: Time step $t$에서, context $x_t$가 주어졌고 action $a_t$를 선택했을 때, 예상되는 reward를 나타냅니다. 실제 agent가 취한 action을 통해 받는 reward와는 다른 값이며, 예상되는 reward의 값의 분포입니다. 에이전트는 이 값을 통해서, 리워드가 최대화되는 action을 선택하는 방식으로 학습됩니다. 주로 이 값은 매트릭스로 표현되는데, 이 때, 값을 expected reward라고 하고, 이 값의 index가 action으로 표현됩니다.
• Reward $r_t(a)$: 실제 agent가 Time step $t$에서 action $a_t$를 취했을 때 받는 reward값입니다.
• Alpha: NN에서 흔히 사용되는 Learning Rate와 같은 개념입니다.
• Agents or Algorithms: 그리고 action을 선택하게하는 Agent가 필요합니다 (e.g., LinUCB, $\epsilon$-greedy)

Contextual Bandit Algorithm

알고리즘에 대해 소개합니다.

1. Build the Environment
   응용하고자 하는 application의 정보를 구축하기 위해 environment를 초기화 및 설계합니다. 이 단계에서, 선택가능한 action의 수 $A$, 컨텍스트의 차원 $d$를 설정합니다. 또한, 컨텍스트($x$)와 특정 action($a$)이 주어졌을 때, 예상되는 expected reward $q(x,a)$를 설계합니다. 만약 optimal한 action이 있다면 q[optimal action]=maximum value가 되겠죠.

2. Receive context $x_t$
   context generator를 통해 Receive context $x_t$를 받습니다. 이 $x_t$는 state로 설명되기도 합니다.

3. Receive expeced reward using environment
   environment를 활용해서, 컨텍스트 $x_t$가 주어졌고, $a_t$을 취했을 때 예상되는 reward들을 확인합니다.

4. Select the action
   에이전트는 위에서 얻은 정보로, expected reward가 가장 큰 값의 index(action)를 고르게 될 것입니다.

5. Update information
   agent를 업데이트해줍니다

이 과정을 T 라운드만큼 반복해줍니다.

---

Reference:

• https://hackernoon.com/contextual-multi-armed-bandit-problems-in-reinforcement-learning
• https://towardsdatascience.com/contextual-bandits-and-reinforcement-learning-6bdfeaece72a