首个针对逻辑回归博弈的高效纯探索算法，逼近理论最优样本复杂度。
Near Optimal Pure Exploration in Logistic Bandits
- 提出基于跟踪-停止框架的逻辑回归纯探索算法
- 渐近匹配实例相关下界，样本复杂度仅差对数因子
- 适合需要高效探索的强化学习与实验设计场景
贝叶斯博弈算法因其在现实场景中的广泛应用而受到广泛关注。然而，在多臂或线性博弈之外的复杂设置中，最优算法仍然稀缺。特别是对于广义线性模型（GLM）博弈中的纯探索问题，目前尚无最优解。本文填补这一空白，提出了首个适用于逻辑回归博弈的纯探索跟踪-停止算法，称为逻辑跟踪-停止（Log-TS）。该算法在实例相关的期望样本复杂度下，渐近地逼近一个近似下界，仅相差一个对数因子。
原文摘要 · Abstract (English)
Bandit algorithms have garnered significant attention due to their practical applications in real-world scenarios. However, beyond simple settings such as multi-arm or linear bandits, optimal algorithms remain scarce. Notably, no optimal solution exists for pure exploration problems in the context of generalized linear model (GLM) bandits. In this paper, we narrow this gap and develop the first track-and-stop algorithm for general pure exploration problems under the logistic bandit called logistic track-and-stop (Log-TS). Log-TS is an efficient algorithm that asymptotically matches an approximation for the instance-specific lower bound of the expected sample complexity up to a logarithmic factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。