Linear Thompson sampling, Contextual Bandits

1. założenie - liniowość

W algorytmie zakładamy, że istnieje pewien wektor $\mu \in {\mathbb{R}}^d$ taki, że $b_i^T\mu$ to oczekiwana nagroda z zagrania bandytą $i$.

Cel

Minimalizacja regret.

Problem

Algorytm zwraca liczbę pochodzącą z rozkładu normalnego, więc nie ma żadnego ograniczenia na wartość tej liczby, w szczególności może być poza przedziałem $[0,1]$. W przypadku CTR, CVR prediction problem wartości nagrody to 0 i 1, więc średnia nagroda nie może wychodzić poza ten przedział. W dodatku rozkład normalny jest symetryczny, a prawdziwy rozkład nad CTR, szczególnie przy niskich CTRach już symetryczny nie jest.

Powyższy problem najbardziej będzie bolał w momencie gdy będziemy chcieli losować wartość CTR z rozkładu, bo nawet jeśli średnia rozkładu będzie znajdować się w przedziale $[0,1]$ to w przypadku niskich CTRów często będziemy losować wartość ujemną.

Przy wyborze kampanii powyższy problem nie ma znaczenia, ale przy wycenie już ma.

Uczenie

Publikacja Thompson Sampling for Contextual Bandits with Linear Payoffs podaje algorytm uczenia (aktualizacji wag), ale nie wyjaśnia ani nie linkuje skąd się wziął.