Improved Dimension Dependence for Logistic Bandits via Secant Estimation

We study logistic bandits with $K$ arms and $d$-dimensional features, where rewards are binary and their means follow an unknown logistic model. Existing algorithms attain a leading $\sqrt{dT}$ regret term either with a large additive $d^{5/2}$ term or under the assumption that the feature covariance has a strictly positive minimum eigenvalue. We propose two algorithms that reduce the dependence of the additive term on $d$ without a feature covariance assumption. First, SupSplitLog+ reduces the additive term to $d^{3/2}$ using one-step estimation with splitting samples according to their roles. One subset provides an initial parameter estimate, whose prediction is used to approximate the logistic function with a tangent line. The other subset is used to compute a one-step estimate based on this tangent line. Our improvement comes from a sharper analysis of the error introduced by the tangent approximation. Second, SupSecantLog replaces the tangent line with a secant line through two independent predictions. The leading approximation error then changes from the square of one prediction error to the product of two independent prediction errors. Reducing the bias of both estimates lets us exploit cancellation between positive and negative products, further reducing the additive term to $d^{4/3}$. Finally, we provide an algorithm based on a doubling rule that achieves both regret bounds with $d$ replaced by a data-dependent complexity measure of the revealed features, yielding smaller bounds when these features lie in a low-dimensional subspace.