Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909332771176448 |
|---|---|
| author | Liu, Shuai Ayoub, Alex Sentenac, Flore Tan, Xiaoqi Szepesvári, Csaba |
| author_facet | Liu, Shuai Ayoub, Alex Sentenac, Flore Tan, Xiaoqi Szepesvári, Csaba |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_01112 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits Liu, Shuai Ayoub, Alex Sentenac, Flore Tan, Xiaoqi Szepesvári, Csaba Machine Learning 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. |
| title | Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.01112 |