Contextual Bandits for Unbounded Context Distributions
<|reference_start|>Contextual Bandits for Unbounded Context Distributions: Nonparametric contextual bandit is an important model of sequential decision making problems. Under $\alpha$-Tsybakov margin condition, existing research has established a regret bound of $\tilde{O}\left(T^{1-\frac{\alpha+1}{d+2}}\right)$ for bounded supports. However, the optimal regret with unbounded contexts has not been analyzed. The challenge of solving contextual bandit problems with unbounded support is to achieve both exploration-exploitation tradeoff and bias-variance tradeoff simultaneously. In this paper, we solve the nonparametric contextual bandit problem with unbounded contexts. We propose two nearest neighbor methods combined with UCB exploration. The first method uses a fixed $k$. Our analysis shows that this method achieves minimax optimal regret under a weak margin condition and relatively light-tailed context distributions. The second method uses adaptive $k$. By a proper data-driven selection of $k$, this method achieves an expected regret of $\tilde{O}\left(T^{1-\frac{(\alpha+1)\beta}{\alpha+(d+2)\beta}}+T^{1-\beta}\right)$, in which $\beta$ is a parameter describing the tail strength. This bound matches the minimax lower bound up to logarithm factors, indicating that the second method is approximately optimal.<|reference_end|>
@article{zhao2024contextual,
    title={Contextual Bandits for Unbounded Context Distributions},
    author={Puning Zhao, Jiafei Wu, Zhe Liu, Huiwen Wu},
    journal={arXiv preprint arXiv:2408.09655},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.09655},
    primaryClass={cs.LG stat.ML}
}