---
tags: paper reading
---

# LinUCB 筆記

## 概念
想像你的面前有很多很多台不同的老虎機，而你的手上有各式各樣的籌碼，你想要用手中的籌碼從機台中獲取最大利益，但你不知道每台老虎機的特性，因此你需要***LinUCB***

## 參數
- T: 回合數
- K: 機台個數
- d: 籌碼種類
- $r_{t,a}$: 在0到1之間，代表在第t回合，選擇第a個機台的收益
- $x_{t,a}$: 為d維的向量，代表在第t回合，想要使用的籌碼組合
- $||x_{t,a}||$: 代表$x_{t,a}$在L2 norm的數值
- $L2 norm$ = $({\Sigma}_{i=1}^{n}|x_i|^2)^{\frac{1}{2}}$
- norm: 範數
假設V是域F上的向量空間，V的半範數(seminorm)為一函數$P:V{\rightarrow}{\mathbb{R}}$; $x{\rightarrow}{P(x)}$，其中，滿足：$\forall a \in F$, $\forall u,v \in V$，則有以下特性：
1. $P(v) \geq 0$ (半正定性 positive semidefinite)
2. $P(av) = |a|P(v)$ (絕對一次性)
3. $P(u+v) \leq P(u) + P(v)$ (三角不等式)
4. $P(v)=0$ if and only if v is a zero vector

## 流程
1. 選擇一組要使用的籌碼
2. 計算每個機台可能獲得的回報
3. 選擇最高的那一個機台
4. 更新計算回報的矩陣($\theta^*$)，回到step 1

在一開始時，每一台機器的回報都為1，而計算回報的公式為
${{\theta}_t^\mathit{T}}{x_{t,a}}+{{\alpha}{\sqrt{{x_{t,a}^{\mathit{T}}A^{-1}}{x_{t,a}}}}}$

${{\alpha}{\sqrt{{x_{t,a}^{\mathit{T}}A^{-1}}{x_{t,a}}}}}$
- $\alpha$：探索的趨勢，越大代表越傾向於探索新的機器，越小代表越傾向於使用當前的回報矩陣所得出的機器
- ${{x_{t,a}^{\mathit{T}}A^{-1}}{x_{t,a}}}$：計算當前的籌碼組合與曾經用這台機器的籌碼組合相似度