论文标题
逻辑匪徒共同有效且最佳的算法
Jointly Efficient and Optimal Algorithms for Logistic Bandits
论文作者
论文摘要
逻辑匪徒最近由于其理论和实际相关性而进行了仔细的审查。这项研究工作提供了统计上有效的算法，通过指数级的因素改善了以前的策略的遗憾。但是，这种算法的昂贵算法很高，因为它们每轮都需要$ω（t）$操作。另一方面，一系列的研究重点是计算效率（$ \ MATHCAL {O}（1）$每轮成本），但要取决于上述指数改进的代价。不幸的是，获得两者兼而有之的是结婚这两种方法。取而代之的是，我们为物流匪徒介绍了一个新的学习过程。它产生了信心集，可以轻松地在线维护足够的统计数据，而无需牺牲统计紧密。结合有效的计划机制，我们设计的快速算法遗憾的性能仍然与Abeille等人的问题相关的下限相匹配。 （2021）。据我们所知，这些是同时享有统计和计算效率的第一个物流匪徒算法。
Logistic Bandits have recently undergone careful scrutiny by virtue of their combined theoretical and practical relevance. This research effort delivered statistically efficient algorithms, improving the regret of previous strategies by exponentially large factors. Such algorithms are however strikingly costly as they require $Ω(t)$ operations at each round. On the other hand, a different line of research focused on computational efficiency ($\mathcal{O}(1)$ per-round cost), but at the cost of letting go of the aforementioned exponential improvements. Obtaining the best of both world is unfortunately not a matter of marrying both approaches. Instead we introduce a new learning procedure for Logistic Bandits. It yields confidence sets which sufficient statistics can be easily maintained online without sacrificing statistical tightness. Combined with efficient planning mechanisms we design fast algorithms which regret performance still match the problem-dependent lower-bound of Abeille et al. (2021). To the best of our knowledge, those are the first Logistic Bandit algorithms that simultaneously enjoy statistical and computational efficiency.
