Contextual Bandits - LinUCB

금번 포스팅을 시작하면서 multi-armed bandit 포스팅의 초반부를 상기시켜보겠습니다. Bandit을 크게 stochastic, non-stochastic으로 분류했고, 그 다음 분류는 context-free, context로 분류했습니다. 지금까지 살펴본 ε-greedy, UCB, Thompson Sampling의 알고리즘은 context-free에 해당하는 방법이었습니다. 즉 action을 선택하기 앞서 주어진 환경을 전혀 고려하지 않고 매시도 독립적으로 의사결정을 해왔습니다. 이번 포스팅에서는 context를 고려하는 contextual bandits, 그 중에서도 가장 유명한 Li, Lihong, et al., 2010의 LinUCB를 살펴보겠습니다.

어떠한 형태의 co-work도 환영합니다:) yjjo.tistory@gmail.com

Contextual Bandits?

Contextual bandits이란 매 trial의 의사결정 전, 관측 가능한 정보를 활용하여 최적의 의사결정을 하는 Bandits을 의미합니다. $r_{t}\overset{iid}{\sim}\mathbb{P}(a_{t})$가 context-free라면, $r_{t}\overset{iid}{\sim}\mathbb{P}(a_{t}|x_{t})$가 contextual한 상황을 말하며, 여기에서 $x_{t}$가 사전에 관측가능한 정보인 context가 됩니다.

Motivation and What is Context?

Contextual Bandits은 사실 자연스러운 고민의 결과라고 할 수 있습니다. 예를 들어, 뉴스기사를 제공하는 플랫폼을 상상해보겠습니다. 이 플랫폼의 목표는 접속하는 유저에게 가장 관심이 있을법한 뉴스를 노출시키고, 유저가 해당기사를 click하는 것입니다. 평균적인 이야기를 해보면, 20대 유저에게 시사/정치와 관련된 뉴스를 노출시키는 것 보단, 스포츠/생활/문화와 관련된 기사를 노출시키는 것이 click까지 이어지는데 유리할 것 입니다. 만약 40대 유저에게는 반대의 경우가 좀 더 유리할 수 있겠습니다. 위와 같은 상황에서 성별, 연령대가 사전에 관측가능하다면 그에 대응하는 최적의 의사 결정을 하는 알고리즘을 구축해보자는 것이 동기입니다. 여기에서 성별, 연령대가 Context가 됩니다.

일반적으로 context는 아래와 같은 것들이 고려될 수 있습니다.

• User Profile
  • Demo Graphical Information
  • Pattern of Usage
• Feature of Environment
  • Day of week
  • Time of the day
  • Season
• Actions
  • Feature of Their Own
  • Some actions are unavailable in a given round

더 다양한 것들이 고려될 수 있지만, 몇 가지를 요약해봤습니다. 크게는 두가지로 나누어서 해석해볼 수 있습니다. 첫번째는 agent의 특성이나, 놓인 환경을 고려할 수 있고, 두번째는 해당 round에서 선택할 수 있는 actions 자체의 특성입니다.

Regret Function for Contextual bandits

Contextual Bandits의 학습목표인 frequentists관점의 regret function에 대해서 살펴보겠습니다. $x_{t}$, $a_{t}$를 각각 $t$ 라운드의 context, action이라고 하겠습니다. reward는 $\mathbb{P}(a_{t}|x_{t})$의 확률분포에서 얻어진다고 했을때, Contextual Bandits을 적용한 algorithm, ALG에 대한 $T$ 라운드까지의 total expected reward은 다음과 같습니다. $$\mathbb{E}\left[Rew(ALG)\right]=\sum_{t=1}^{T}\mu(a_{t}|x_{t})$$ 최적의 reward를 얻는 정책을 $\pi(x)^{*}=\max_{a\in\mathcal{A}}\mu(a|x)$라고하면, regret function은 다음과 같이 정의됩니다. $$R(T)=Rew(\pi^{*})-Rew(ALG)$$ 다시 말하면, 주어진 context아래 최적의 의사결정대비 algorithm에서 선택한 actions의 reward 총합의 차입니다.

Contextual Bandits Frame-work
(linear expected reward)

어떤 round에서 관측 가능한 context는 대게 여러가지로 벡터의 형태로 표현할 수 있습니다. 그렇다면 context, trial, reward 세 가지를 어떻게 유기적인 연결을 고민하는 것이 자연스럽습니다. 이 세가지를 유기적으로 연결하는 것을 Contextual Bandits Frame-work이라고 이름을 붙였습니다. 앞서 말씀드린 것 처럼 다양한 contextual bandits 중 LinUCB에서는 이를 linear expected reward로 나타냅니다. $x_{t,a}\in\mathbb{R}^{d}$를 $t$ round의 $a$ arm에 대한, $d$차원 context라고하고, context vector의 elements의 강도를 arm별로 나타내는 coefficient vector를 $\theta_{a}$라고 하겠습니다. $x_{t}$ context에서 $a$ arm을 선택했을 때 기대 보상을 다음처럼 나타낼 수 있습니다. $$\mathbb{E}\left[r_{t}|x_{t,a}\right]=x_{t,a}^{\top}\theta_{a}$$기대 보상을 선형 함수로 나타내어 linear expected reward라고 부릅니다. Li Lihong, et al., 2010에서는 coefficient vector인 $\theta$를 arm별로 따로 구성하면 disjoint model, 공유하면 hybrid model이라고 구분했습니다. 이번 포스팅에서는 disjoint model 위주로 설명하려고 합니다.

예를 들어 보겠습니다. (아주 지극히 주관적으로 구성했습니다.) Context로 연령대에 대한 정보가 있고, 10대, 40대, 60대를 가정해봤습니다. Arm으로는 음식을 고려했고, 아이스크림, 햄버거, 치킨이 있습니다. 각 라운드에 연령대를 알 수 있고, 알맞는 음식을 추천해줘야하며, 긍정적일 경우 1의 reward를, 아닌 경우 0의 reward를 얻는 상황입니다.

Fig 1. Linear Expected Reward

$t$ round에 10대에게 음식을 추천해줘야 한다면, 기대 보상은 아이스크림, $[1, 0, 0]\theta_{1}=0.8$, 햄버거, $[1,0,0]\theta_{2}=0.2$, 치킨, $[1,0,0]\theta_{3}=0.1$이 됩니다. 따라서 아이스크림을 추천해주는 것이 최적의 선택이라고 할 수 있겠습니다. 이렇듯 Linear Expected Reward는 context와 reward를 유기적으로 연결시켜는 방법입니다.

linUCB

linUCB는 Li, Lihong, et al., 2010이 제안한 방법으로 Context의 Linear Expected Reward를 계산할 coefficient vector를 Ridge Regression의 방법으로 추정하여 모델링한 방법입니다.

Apply Ridge Regression

$D_{a}\in\mathbb{R}^{m\times d}$를 $t$라운드의 design matrix, $b_{a}$를 response vector, 즉 arm을 선택한 이후 관측된 reward vector를 의미합니다. 이 상황에서 coefficient vector를 아래와 같이 ridge regression의 solution을 이용하여 계산합니다. $$\hat{\theta}_{a}=\left(D_{a}^{\top}D_{a}+I_{d}\right)^{-1}D_{a}^{\top}b_{a}$$ 여기에서 $I_{d}$는 $d\times d$의 identity matrix입니다. Ridge Regression에 대한 내용은 나중에 시간이 되면 다룰 예정입니다. (당장 급하시다면 구글링을..) Ridge Regression의 solution을 이용했을 경우 다음을 만족합니다. $$\mathbb{P}\left(\left|x_{t,a}^{\top}\hat{\theta}_{a}-\mathbb{E}[r_{t,a}|x_{t}]\right|\le\alpha\sqrt{x_{t,a}^{\top}\left(D_{a}^{\top}D_{a}+I_{d}\right)^{-1}x_{t,a}}\right)\ge 1-\delta$$ 여기에서 $\forall\delta>0$, $\alpha=1+\sqrt{\log(2/\delta)/2}$입니다. 눈치채셨겠지만, 위 부등식은 UCB 관련 포스팅에서 살펴본 것과 유사합니다. 즉 $x_{t,a}^{\top}\hat{\theta}_{a}+\alpha\sqrt{x_{t,a}^{\top}\left(D_{a}^{\top}D_{a}+I_{d}\right)^{-1}x_{t,a}}$를 UCB로 이용할 수 있고, UCB가 최대인 arm을 선택하는 전략을 취할 수 있습니다. $$a_{t}=\underset{a\in\mathcal{A}_{t}}{\operatorname{argmax}}\left(x_{t,a}^{\top}\hat{\theta}_{a}+\alpha\sqrt{x_{t,a}^{\top}\left(D_{a}^{\top}D_{a}+I_{d}\right)^{-1}x_{t,a}}\right)$$

Why Confidence Interval?

왜 Confident Interval일까요? LinUCB는 Frequentist의 관점에서 접근한 algorithm으로, 해당 관점으로 유도하는 과정은 Agrawal, Rajeev, 1995로 확인할 수 있습니다. 본 포스팅에서는 좀 더 직관적으로 살펴보기 위해서 Bayesian Linear Regression을 살펴보겠습니다.

$b_{t,a}=D_{t,a}\theta_{a}+\epsilon$, $\epsilon\sim N(0,\sigma^{2})$의 linear regression model을 고려해보겠습니다. 그러면, $b_{t,a}|D_{t,a}, \theta_{a}\sim N(D_{t,a}\theta_{a}, \sigma^{2}I)$를 만족합니다. 이때 Coefficient vector $\theta_{a}$가 $N(0, \tau^{2} I_{d})$의 prior를 가정하면, $\theta_{a}$의 posterior는 아래와 같이 얻을 수 있습니다. $$\begin{align*}\mathbb{P}(\theta_{a}|b_{t,a}, D_{t,a})&\propto\mathbb{P}(\theta_{a})\mathbb{P}(b_{t,a}|D_{t,a}\theta_{a})\\&\propto exp\left[-\theta_{a}^{\top}\frac{1}{\tau^{2}}\theta_{a}\right]exp\left[-\left(b_{t,a}-D_{t,a}\theta_{a}\right)^{\top}\frac{1}{\sigma^{2}}\left(b_{t,a}-D_{t,a}\theta_{a}\right)\right]\\&\propto exp\left[-\|b_{t,a}-D_{t,a}\theta_{a}\|^{2}-\frac{\sigma^{2}}{\tau^{2}}\|\theta_{a}\|^{2}\right]\\&=exp\left[-\left(b_{a}^{\top}b_{a}-b_{a}^{\top}D_{t,a}\theta_{a}-\theta^{\top}D_{t,a}^{\top}b_{a}+\theta^{\top}_{a}D_{t,a}^{\top}D_{t,a}\theta_{a}+\frac{\sigma^{2}}{\tau^{2}}\theta_{a}^{\top}\theta_{a}\right)\right]\\&=exp\left[-\left(\theta^{\top}_{a}\left(D_{t,a}^{\top}D_{t,a}+\frac{\sigma^{2}}{\tau^{2}}I\right)\theta_{a}+b_{a}^{\top}b_{a}-b_{a}^{\top}D_{t,a}\theta_{a}-\theta^{\top}D_{t,a}^{\top}b_{a}\right)\right]\\&=exp\left[-\left(\theta^{\top}_{a}A_{t,a}\theta_{a}+b_{a}^{\top}b_{a}-b_{a}^{\top}D_{t,a}A_{t,a}^{-1}A_{t,a}\theta_{a}-\theta^{\top}D_{t,a}^{\top}A_{t,a}^{-1}A_{t,a}b_{a}\right)\right]\\&\propto exp\left[-\left(\theta^{\top}_{a}A_{t,a}\theta_{a}+b_{a}^{\top}D_{t,a}A_{t,a}^{-1}D_{t,a}b_{a}-b_{a}^{\top}D_{t,a}A_{t,a}^{-1}A_{t,a}\theta_{a}-\theta^{\top}D_{t,a}^{\top}A_{t,a}^{-1}A_{t,a}b_{a}\right)\right]\\&=exp\left[-\left(\theta_{a}-A_{t,a}^{-1}D_{t,a}b_{t,a}\right)^{\top}A_{t,a}\left(\theta_{a}-A_{t,a}^{-1}D_{t,a}b_{t,a}\right)\right]\end{align*}$$ 여기에서 $A_{t,a}=\left(D_{t,a}^{\top}D_{t,a}+\frac{\sigma^{2}}{\tau^{2}}I\right)$입니다. 즉, $\mathbb{P}(\theta_{a}|b_{t,a},D_{t,a})\sim N(A_{t,a}^{-1}D_{t,a}^{\top}b_{t,a},A_{t,a}^{-1})$과 같습니다. $\frac{\sigma^{2}}{\tau^{2}}=1$이면 linUCB와 상황이 같습니다. 이제 Gaussian Distribution의 confidence interval을 계산하는 것처럼 생각할 수 있습니다. $$x_{t,a}^{\top}\hat{\theta}_{a}\sim N\left(x_{t,a}^{\top}\left(D_{t,a}^{\top}D_{t,a}+I\right)^{-1}D_{t,a}b_{t,a}, x_{t,a}^{\top}\left(D_{t,a}^{\top}D_{t,a}+I\right)^{-1}x_{t,a}\right)$$

LinUCB Disjoint Algorithm 

LinUCB Algorithm은 위 과정을 online-update로 나타낸 것과 같습니다.

Fig 2. LinUCB Disjoint Algorithm (출처. Li, Lihong, et al., 2010)

Line 5은 ridge regression의 solution의 $I_{d}$를 담당하며, line 12에서 $x_{t,a}x_{t,a}^{\top}$은 $D_{t,a}^{\top}D_{t,a}$를 담당합니다.

Summary

이렇게 이번 포스팅에서는 contexutal bandit의 컨샙과 지향하는 바에 대해서 간략하게 설명하고, frequentist 관점의 contextual bandits인 LinUCB알고리즘에 대해서 살펴봤습니다. 긴글 읽어주셔서 감사합니다:)

어떠한 형태의 co-work도 환영합니다:) yjjo.tistory@gmail.com

References

Slivkins, Aleksandrs. "Introduction to multi-armed bandits."arXiv preprint arXiv:1904.07272(2019).

Agrawal, Rajeev. "Sample mean based index policies with O (log n) regret for the multi-armed bandit problem." Advances in Applied Probability (1995): 1054-1078.

Wikipedia contributors. "Multi-armed bandit." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 22 Oct. 2020. Web. 30 Nov. 2020.

Li, Lihong, et al. "A contextual-bandit approach to personalized news article recommendation." Proceedings of the 19th international conference on World wide web. 2010.

Agrawal, Shipra, and Navin Goyal. "Thompson sampling for contextual bandits with linear payoffs." International Conference on Machine Learning. 2013.