Contextual Bandits
Lipschitz Bandits
Continuum-armed bandits
先考虑 arm 是连续变量的特殊情况（CAB），不妨假设 arm 是 $X=[0, 1]$，其均值 $\mu(x)$ 满足 Lipschitz 条件： $$ |\mu(x)-\mu(y)| \leq L \cdot|x-y| \quad \text { for any two arms } x, y \in X, $$ CAB 的可处理性源于均值函数的 Lipschitz 性。
Simple solution: fixed discretization
一个很简单的思路是将连续的 arm 离散化。选取 $X$ 的一个有限子集 $S \subseteq X$，在这个子集上做有限 arm 的 bandit 算法 $\texttt{ALG}$ ，记 $\mu^{\ast}(S) = \displaystyle\sup _{x \in S} \mu(x)$，这个算法的 regret 可以分解为： $$ \begin{aligned} \mathbb{E}[R(T)] &=T \cdot \mu^\ast(X)-W(\mathtt{ALG}) \\ &=\left(T \cdot \mu^\ast(S)-W(\mathtt{ALG})\right)+T \cdot\left(\mu^\ast(X)-\mu^\ast(S)\right) \\ &=R_S(T)+T \cdot \operatorname{DE}(S) \end{aligned} $$ 这里 $\mathrm{DE}(S)=\mu^\ast(X)-\mu^\ast(S)$ 是离散化导致的误差。
一种很自然的做法是等间距地选取 $k$ 个 arm，记 arm 的间距为 $\epsilon = \displaystyle\frac{1}{k-1}$，根据 Lipschitz 性有 $\mathrm{DE}(S) \leq L \epsilon$，选取 $\epsilon=\left(T L^2 / \log T\right)^{-1 / 3}$，此时的 regret 界为： $$ \mathbb{E}[R(T)] \leq O\left(L^{1 / 3} \cdot T^{2 / 3} \cdot \log ^{1 / 3}(T)\right) $$
Lower Bound
最坏情况下的 regret 界是 $\Omega(T^{2/3})$