发现稀疏性可显著提升非参数上下文强化学习的性能上限
Sparse Nonparametric Contextual Bandits
- 通过多臂老虎机还原法推导出最小最大后悔上界
- 提出改进版感觉良好汤普森采样算法，后悔率接近理论最优
- 适用于核方法和神经网络上下文带宽，适合大规模稀疏场景
我们研究了在候选特征集为可数或不可数无穷大的非参数上下文带宽问题中，稀疏性的优势。贡献有二：第一，通过一种新颖的多臂老虎机序列还原法，给出了最小最大后悔的下界，表明在此设定下对动作数的多项式依赖通常不可避免；第二，证明了一种改进的Feel-Good Thompson Sampling算法的后悔界与下界仅差对数因子，且对有效候选特征数呈对数依赖。当应用于核化和神经上下文带宽时，若时间跨度相对于稀疏性和动作数足够大，则稀疏性可带来更优的后悔界。
原文摘要 · Abstract (English)
We study the benefits of sparsity in nonparametric contextual bandit problems, in which the set of candidate features is countably or uncountably infinite. Our contribution is two-fold. First, using a novel reduction to sequences of multi-armed bandit problems, we provide lower bounds on the minimax regret, which show that polynomial dependence on the number of actions is generally unavoidable in this setting. Second, we show that a variant of the Feel-Good Thompson Sampling algorithm enjoys regret bounds that match our lower bounds up to logarithmic factors of the horizon, and have logarithmic dependence on the effective number of candidate features. When we apply our results to kernelised and neural contextual bandits, we find that sparsity enables better regret bounds whenever the horizon is large enough relative to the sparsity and the number of actions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。