证明指数族具自协调性，用于广义线性赌博机实现更优的后悔上界
Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits
- 发现子指数尾部指数族具有多项式规模的自协调参数
- 首次给出子高斯族自协调参数增长的精确刻画
- 使广义线性赌博机算法实现无指数依赖的二阶后悔界
我们证明，具有子指数尾部的单参数自然指数族具有多项式规模的自协调参数。对于子高斯自然指数族，我们给出了自协调参数增长速率的精确刻画。将这些结果应用于赌博机问题，填补了文献空白：我们证明，广义线性赌博机的乐观算法可实现既为二阶（与最优臂奖励分布方差相关）又在主导项中避免对问题参数有界值的指数依赖的后悔界。据我们所知，这是首个针对具有子指数尾部的广义线性赌博机的后悔界，扩展了适用问题类，包括泊松、指数和伽马赌博机。
原文摘要 · Abstract (English)
We prove that single-parameter natural exponential families with subexponential tails are self-concordant with polynomial-sized parameters. For subgaussian natural exponential families we establish an exact characterization of the growth rate of the self-concordance parameter. Applying these findings to bandits allows us to fill gaps in the literature: We show that optimistic algorithms for generalized linear bandits enjoy regret bounds that are both second-order (scale with the variance of the optimal arm's reward distribution) and free of an exponential dependence on the bound of the problem parameter in the leading term. To the best of our knowledge, ours is the first regret bound for generalized linear bandits with subexponential tails, broadening the class of problems to include Poisson, exponential and gamma bandits.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。