Timezone: »
Poster
Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits
Kwang-Sung Jun · Lalit Jain · Blake Mason · Houssam Nassif
We propose improved fixed-design confidence bounds for the linear logistic model. Our bounds significantly improve upon the state-of-the-art bound by Li et al. (2017) via recent developments of the self-concordant analysis of the logistic loss (Faury et al., 2020). Specifically, our confidence bound avoids a direct dependence on $1/\kappa$, where $\kappa$ is the minimal variance over all arms' reward distributions. In general, $1/\kappa$ scales exponentially with the norm of the unknown linear parameter $\theta^*$. Instead of relying on this worst case quantity, our confidence bound for the reward of any given arm depends directly on the variance of that arm's reward distribution. We present two applications of our novel bounds to pure exploration and regret minimization logistic bandits improving upon state-of-the-art performance guarantees. For pure exploration we also provide a lower bound highlighting a dependence on $1/\kappa$ for a family of instances.
Author Information
Kwang-Sung Jun (University of Arizona)
Lalit Jain (University of Washington)
Blake Mason (University of Wisconsin, Madison)
Houssam Nassif (amazon)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Spotlight: Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits »
Wed. Jul 21st 02:25 -- 02:30 PM Room
More from the Same Authors
-
2023 Poster: Revisiting Simple Regret: Fast Rates for Returning a Good Arm »
Yao Zhao · Connor J Stephens · Csaba Szepesvari · Kwang-Sung Jun -
2021 Poster: Improved Algorithms for Agnostic Pool-based Active Classification »
Julian Katz-Samuels · Jifan Zhang · Lalit Jain · Kevin Jamieson -
2021 Spotlight: Improved Algorithms for Agnostic Pool-based Active Classification »
Julian Katz-Samuels · Jifan Zhang · Lalit Jain · Kevin Jamieson -
2021 Poster: Improved Regret Bounds of Bilinear Bandits using Action Space Analysis »
Kyoungseok Jang · Kwang-Sung Jun · Se-Young Yun · Wanmo Kang -
2021 Spotlight: Improved Regret Bounds of Bilinear Bandits using Action Space Analysis »
Kyoungseok Jang · Kwang-Sung Jun · Se-Young Yun · Wanmo Kang -
2020 : Short Talk 1 - Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimality »
Kwang-Sung Jun -
2020 Poster: Identifying the Reward Function by Anchor Actions »
Sinong Geng · Houssam Nassif · Charlie Manzanares · Max Reppen · Ronnie Sircar