acceptodds
Under review as a conference paper at ICLR 2027

Improved Dimension Dependence for Logistic Bandits via Secant Estimation

Abstract

We study logistic bandits with arms and -dimensional features, where rewards are binary and their means follow an unknown logistic model. Existing algorithms attain a leading regret term either with a large additive 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 without a feature covariance assumption. First, SupSplitLog+ reduces the additive term to 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 . Finally, we provide an algorithm based on a doubling rule that achieves both regret bounds with replaced by a data-dependent complexity measure of the revealed features, yielding smaller bounds when these features lie in a low-dimensional subspace.

Primary area:
reinforcement learning
Keywords:
contextual bandits, logistic bandits, effective dimension

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7qtDOpenReview ↗
Rating
3
Confidence
1
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies finite-armed logistic bandits without a full-rank feature-covariance assumption. In this paper, the authors proposed two methods: SupSplitLog+ uses a level-based sample-splitting framework and SupSecantLog constructs a secant using two independent, bias-adjusted initial estimates and normalizes responses by the secant slope.

Critical strengths
  1. This paper proposed a substantive mechanism for controlling nonlinear estimation errors.

  2. The theoretical results provided in this paper allow time-varying candidate sets, and the manuscript appropriately distinguishes this setting from fixed-arm experimental-design results.

Critical weaknesses
  1. Large curvature factors limit the scope of the dimension improvement, and the crossover regime is not made explicit.

  2. The computational cost of the estimator is insufficiently characterized.

Questions for authors
  1. Could you provide conditions or representative regimes where SupSecantLog improves on the bounds for SupSplitLog+ and the prior SupSplitLog? Is 4/3 an exponent achieved by the analysis rather than one known to be unimprovable?

  2. What solver is intended for Eq. (12), and what are its time and memory costs?

  3. How small must its residual be as a function of level and horizon to preserve the main regret guarantee?

  4. Could you clarify that time-varying contexts do not include general reward-dependent adaptive contexts, and identify the conditional-independence step that fails without Assumption 2?

5 comments

In the revised PDF, the key changes are highlighted in blue.

[W1] Large curvature factors limit the scope of the dimension improvement, and the crossover regime is not made explicit.

[Q1(a)] Could you provide conditions or representative regimes where SupSecantLog improves on the bounds for SupSplitLog+ and the prior SupSplitLog?

  • We agree that SupSplitLog+ and SupSecantLog carry curvature-dependent factors in the additive term. Our focus was improving the dimension dependence of the additive term, so we did not discuss curvature dependence in detail.

  • First, simple modifications reduce the additive term from O~(κ7d3/2)\widetilde{\mathcal O}(\boldsymbol{\kappa^7}d^{3/2}) to O~(κ5d3/2)\widetilde{\mathcal O}(\boldsymbol{\kappa^5}d^{3/2}) for SupSplitLog+, and from O~(κ15/2d4/3)\widetilde{\mathcal O}(\boldsymbol{\kappa^{15/2}}d^{4/3}) to O~(κ5d4/3)\widetilde{\mathcal O}(\boldsymbol{\kappa^5}d^{4/3}) for SupSecantLog. Briefly, we tightened the bounds on the regularization bias induced by λp\lambda_p and the nonlinear remainder, then updated the design matrices and parameters. The steps of Algorithms 1 and 2 are unchanged; both now use the updated design matrices (Eq. (1) and the definitions of VV and VkV_k on pp. 4 and 8) and parameters (Section H), and Theorems 1 and 2 state the resulting bounds. The key bounds are in Eq. (29) (p. 22) and Eqs. (56) and (58) (p. 27). Section and page numbers refer to the revised PDF.

  • Based on this improvement, the additive terms of SupSplitLog+ and SupSecantLog are smaller than that of SupSplitLog when d≳κ5/2d\gtrsim\kappa^{5/2} and d≳κ15/7d\gtrsim\kappa^{15/7}, respectively. In the leading term, both match or improve on SupSplitLog. The new Section B.4 gives the comparison of these regret bounds.

  • For the comparison between SupSecantLog and SupSplitLog+, SupSecantLog has leading order 1+Bκ1/2dT(log⁡T)3/2\sqrt{1+B}\boldsymbol{\kappa^{1/2}}\sqrt{dT}(\log T)^{3/2}, while SupSplitLog+ has leading order κdT(log⁡T)3/2\boldsymbol{\kappa}\sqrt{dT}(\log T)^{3/2}. The leading factor favors SupSecantLog since κ≥2(1+B)\kappa\ge2(1+B). Its additive term has better dependence on dd but worse dependence on log⁡T\log T. For fixed K,δK,\delta and T≥d2T\ge d^2, SupSecantLog has a smaller additive term than SupSplitLog+ when d≳(log⁡T)5d\gtrsim(\log T)^5. Details are in the new Section B.4.

  • Next, our additional experiments show practical advantages even outside these regimes. In the experiments below varying κ\kappa, SupSecantLog has the lowest mean regret in four of the five settings. Full settings and additional results are in Sections K.1--K.5, with the curvature results in Figure 2 and Table 2.

Table. Final cumulative regret (mean ±2\pm2 SD over 10 runs) as κ\kappa varies, with T=104T=10^4, d=10d=10, and K=5K=5. Our algorithms are in bold. In each column, the lowest mean regret is in bold and the second lowest is underlined.

Algorithmκ=5\kappa=5κ=10\kappa=10κ=20\kappa=20κ=40\kappa=40κ=100\kappa=100
SupSplitLog$^{+}$363.12±136.51\mathbf{363.12 \pm 136.51}368.21±249.01368.21 \pm 249.01365.18±108.34365.18 \pm 108.34292.71±90.21292.71 \pm 90.21710.21±38.53710.21 \pm 38.53
SupSplitLog$^{+}$ + doubling476.73±199.17476.73 \pm 199.17693.07±260.39693.07 \pm 260.39689.93±60.94689.93 \pm 60.94806.62±103.06806.62 \pm 103.061516.86±46.511516.86 \pm 46.51
SupSecantLog506.74±362.49506.74 \pm 362.49315.52±275.56\mathbf{315.52 \pm 275.56}214.98±216.06\mathbf{214.98 \pm 216.06}221.53±224.52\mathbf{221.53 \pm 224.52}204.86±205.91\mathbf{204.86 \pm 205.91}
SupSecantLog + doubling526.06±210.40526.06 \pm 210.40377.81±329.41377.81 \pm 329.41299.74±169.11‾\underline{299.74 \pm 169.11}238.15±153.96‾\underline{238.15 \pm 153.96}264.62±166.24‾\underline{264.62 \pm 166.24}
SupSplitLog363.54±130.48‾\underline{363.54 \pm 130.48}367.34±248.35‾\underline{367.34 \pm 248.35}364.11±108.95364.11 \pm 108.95292.25±90.69292.25 \pm 90.69710.21±38.53710.21 \pm 38.53
SupSplitLog + doubling425.08±141.87425.08 \pm 141.87711.94±360.29711.94 \pm 360.29688.74±60.26688.74 \pm 60.26806.62±103.06806.62 \pm 103.061516.86±46.511516.86 \pm 46.51

[W2] The computational cost of the estimator is insufficiently characterized.

[Q2] What solver is intended for Eq. (12), and what are its time and memory costs?

We thank the reviewer for pointing out that the submission did not sufficiently characterize the computational cost of the estimator, and we agree. In the revision, we added (i) a description of the solver for Eq. (12), a damped Newton-type iteration, with its time and memory costs (new Section K.1), and (ii) experiments measuring running time and memory usage (Section K.2). Details are below.

  • We solve Eq. (12) with a damped Newton-type iteration that repeats two steps: (i) compute its left-hand side FPk(θj)F_{P_k}(\theta^j) and the regularized Hessian HPk(θj)H_{P_k}(\theta^j), and (ii) update

    θj+1=θj−ajHPk(θj)−1FPk(θj).\theta^{j+1}=\theta^j-a_jH_{P_k}(\theta^j)^{-1}F_{P_k}(\theta^j).

    We choose the step size aja_j to decrease the residual and repeat until ∣FPk(θj)∣Vk−1≤10−10\\|F_{P_k}(\theta^j)\\|_{V_k^{-1}}\le10^{-10}.

  • For computational cost, computing one estimate with mm evaluations of FPkF_{P_k} takes O(m(∣Pk∣d2+d3))O(m(|P_k|d^2+d^3)) time and O(∣Pk∣d+d2)O(|P_k|d+d^2) memory. SupSecantLog computes two such estimates. For numerical accuracy, the new Section B.2 shows that a score residual at most (4κˉT2)−1(4\bar\kappa T^2)^{-1} at each level, where κˉ=1/μ˙(B+1)\bar\kappa=1/\dot\mu(B+1), preserves the regret order after updating the constants.

  • We also conducted experiments to evaluate computational cost and memory use in practice by recording wall-clock time and mean and peak memory usage.

Table. Final cumulative regret (mean ±2\pm2 SD), running time, and memory usage over 10 runs for d∈5,20,80d\in\\{5,20,80\\}, with T=104T=10^4, κ=10\kappa=10, and K=5K=5. These are three of the five dimensions d∈5,10,20,40,80d\in\\{5,10,20,40,80\\} reported in Table 1. Our algorithms are in bold. For each dd, the lowest mean regret is in bold and the second lowest is underlined.

ddAlgorithmRegret (mean ±2\pm2 SD)Time (s)Mean RSS (MiB)Peak RSS (MiB)
5SupSplitLog$^{+}$335.82±295.46335.82 \pm 295.461.18693.7695.18
5SupSplitLog$^{+}$ + doubling427.30±214.65427.30 \pm 214.651.14392.9993.77
5SupSecantLog239.10±387.92‾\underline{239.10 \pm 387.92}1.48993.8095.73
5SupSecantLog + doubling194.58±136.76\mathbf{194.58 \pm 136.76}1.44393.5195.40
5SupSplitLog336.44±295.33336.44 \pm 295.331.01892.4093.32
5SupSplitLog + doubling477.45±238.75477.45 \pm 238.750.90493.6894.43
20SupSplitLog$^{+}$559.92±283.00559.92 \pm 283.000.75499.76104.74
20SupSplitLog$^{+}$ + doubling684.15±218.24684.15 \pm 218.240.80199.16104.70
20SupSecantLog399.96±155.42\mathbf{399.96 \pm 155.42}1.594100.39104.71
20SupSecantLog + doubling525.43±104.98‾\underline{525.43 \pm 104.98}1.52899.88104.76
20SupSplitLog557.45±288.20557.45 \pm 288.200.68798.69104.75
20SupSplitLog + doubling683.76±218.34683.76 \pm 218.340.724100.09105.98
80SupSplitLog$^{+}$539.43±65.76539.43 \pm 65.761.139125.94150.61
80SupSplitLog$^{+}$ + doubling612.15±34.32612.15 \pm 34.321.139123.77150.53
80SupSecantLog484.20±85.85‾\underline{484.20 \pm 85.85}3.517127.20150.54
80SupSecantLog + doubling477.21±65.01\mathbf{477.21 \pm 65.01}3.539126.85150.54
80SupSplitLog539.43±65.76539.43 \pm 65.760.997126.81150.47
80SupSplitLog + doubling612.15±34.32612.15 \pm 34.320.877125.28150.28
  • For d∈5,20,80d\in\\{5,20,80\\}, SupSecantLog and its doubling version have mean runtimes below 3.63.6 seconds and memory usage similar to the baselines, and they have the lowest two mean regrets. Full results are in Section K.2.

[Q1(b)] Is 4/3 an exponent achieved by the analysis rather than one known to be unimprovable?

We thank the reviewer for raising this important point. We do not provide a matching lower bound for the d4/3d^{4/3} dependence, and it remains open whether other estimation methods can further improve the dependence on dd; we leave this question for future work. However, our result matches the dimension dependence conjectured by Mason et al. (2022). Below, we explain why this exponent arises and why it is the best order obtained by optimizing the bias and remainder bounds in our analysis. We added this discussion to the new Section B.1.

  • Mason et al. (2022, Section 4 and Appendix F) conjecture a d4/3d^{4/3} warmup sample complexity by comparing the prediction bias and standard deviation of the Krichevsky--Trofimov (KT) estimator. In their example, each of the dd coordinates of θ⋆\theta_\star is estimated from NN observations, giving n=dNn=dN observations in total. The MLE of each coordinate has bias of order N−1N^{-1}, while the KT estimator reduces it to order N−2N^{-2}. For the prediction x⊤θ^x^\top\widehat\theta with x=(1,…,1)/dx=(1,\ldots,1)/\sqrt d, the KT estimator has bias of order d/N2\sqrt d/N^2 and standard deviation of order N−1/2N^{-1/2}. Balancing them gives

    \quad\Longrightarrow\quad N\asymp d^{1/3}, \qquad n=dN\asymp d^{4/3}.$$ However, they left this rate as a conjecture because the required finite-sample concentration bound for the bias-corrected estimator with arbitrary feature vectors remained open.
  • Our score adjustment, like the KT correction, reduces the leading nonlinear estimation bias. We combine this adjustment with secant estimation to attain the conjectured exponent. When estimating a coordinate of θ⋆\theta_\star in Mason et al.'s example, let SS count successes among its NN observations. Applying the adjustment in Eq. (12) to the unregularized logistic score gives

    \quad\Longrightarrow\quad \widehat\theta=\log\frac{S+1/2}{N-S+1/2}.$$ This is the KT estimator, defined by adding $1/2$ to both the success and failure counts before taking log odds. Like KT, our initial estimates $\bar\theta_k$ retain a residual bias after correction. Eq. (**13**) writes $\bar\theta_k-\theta_\star=\zeta_k+b_k$ with $\mathbb E[\zeta_k]=0$, so this bias is $\mathbb E[b_k]$. Lemma **7** bounds $\\|b_k\\|_{V_k}^2$ using a squared regularization bias term $\lambda_p$ and a nonlinear remainder term $d/\lambda_p^2$. Balancing these terms gives $$\lambda_p\asymp\frac{d}{\lambda_p^2} \quad\Longrightarrow\quad \lambda_p\asymp d^{1/3}, \qquad \lambda_p+\frac{d}{\lambda_p^2}\asymp d^{1/3}.$$ The regret bound for collecting observations for the $d$-dimensional initial estimates introduces an additional factor $d$, yielding the additive dimension dependence $d\cdot d^{1/3}=d^{4/3}$.
Reviewer_zyMvOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies finite-armed logistic contextual bandits and improves the dimension dependence of regret bounds without requiring a positive lower bound on the feature covariance. It introduces two algorithms: SupSplitLog*, which sharpens the accumulated approximation-error analysis of sample-split one-step estimation, and SupSecantLog, which replaces tangent approximation with secant interpolation through two independent, bias-adjusted predictions. The secant construction changes the leading approximation error from a squared prediction error to a product of independent errors, enabling cancellation after bias reduction. Suppressing logarithmic and curvature factors, the algorithms improve the additive regret term from d5/2d^{5/2} to d3/2d^{3/2} and d4/3d^{4/3}, respectively, while preserving the leading dT\sqrt{dT} term. A doubling procedure further adapts the guarantees to a log-determinant complexity measure, yielding smaller bounds when the offered features occupy a low-dimensional subspace. These theoretical guarantees apply to bounded logistic models with exogenous, time-varying contexts.

Critical strengths
  1. Improved dimension dependence: Reduces the additive regret term from d5/2d^{5/2} to d4/3d^{4/3}, retaining the leading dT\sqrt{dT} rate without covariance-diversity assumptions, with logarithmic and curvature factors suppressed.

  2. Innovative estimation mechanism: Combines secant interpolation, independent sample splitting, and bias correction to exploit cancellation in approximation errors.

  3. Adaptation to feature geometry: Provides data-dependent regret guarantees that benefit from low-dimensional feature structure without prior knowledge of the subspace.

Critical weaknesses
  1. Strong curvature dependence: Large curvature-dependent factors may outweigh the improved dimension scaling, limiting the practical advantage of the regret bounds.

  2. Limited practical validation: The paper provides no numerical experiments or end-to-end computational complexity analysis, leaving practical performance and scalability unclear.

  3. Unresolved optimality: No matching lower bound establishes whether the additive d4/3d^{4/3} dependence is optimal or can be further improved.

Questions for authors

See the weakness.

4 comments

In the revised PDF, the key changes are highlighted in blue.

[W1] Strong curvature dependence: Large curvature-dependent factors may outweigh the improved dimension scaling, limiting the practical advantage of the regret bounds.

We thank the reviewer for pointing out that SupSplitLog+ and SupSecantLog carry curvature-dependent factors in the additive term. However, we emphasize again that the focus of this paper is to improve the dimension dependence of the additive term. Nevertheless, in the revision, we (i) reduced the curvature factor of the additive term to κ5\kappa^5 for both algorithms, (ii) added a comparison of the regret bounds (new Section B.4), and (iii) added experiments that vary κ\kappa (Section K.3). Details are below.

  • First, simple modifications reduce the additive term from O~(κ7d3/2)\widetilde{\mathcal O}(\boldsymbol{\kappa^7}d^{3/2}) to O~(κ5d3/2)\widetilde{\mathcal O}(\boldsymbol{\kappa^5}d^{3/2}) for SupSplitLog+, and from O~(κ15/2d4/3)\widetilde{\mathcal O}(\boldsymbol{\kappa^{15/2}}d^{4/3}) to O~(κ5d4/3)\widetilde{\mathcal O}(\boldsymbol{\kappa^5}d^{4/3}) for SupSecantLog. Briefly, we tightened the bounds on the regularization bias induced by λp\lambda_p and the nonlinear remainder, then updated the design matrices and parameters. The steps of Algorithms 1 and 2 are unchanged; both now use the updated design matrices (Eq. (1) and the definitions of VV and VkV_k on pp. 4 and 8) and parameters (Section H), and Theorems 1 and 2 state the resulting bounds. The key bounds are in Eq. (29) (p. 22) and Eqs. (56) and (58) (p. 27). Section and page numbers refer to the revised PDF.

  • Based on this improvement, the additive terms of SupSplitLog+ and SupSecantLog are smaller than that of SupSplitLog when d≳κ5/2d\gtrsim\kappa^{5/2} and d≳κ15/7d\gtrsim\kappa^{15/7}, respectively. In the leading term, both match or improve on SupSplitLog. The new Section B.4 gives the comparison of these regret bounds.

  • Next, we show that our algorithms can outperform the baselines in practice despite their theoretical curvature dependence. We vary κ\kappa to directly examine its effect on regret.

Table. Final cumulative regret (mean ±2\pm2 SD over 10 runs) as κ\kappa varies, with T=104T=10^4, d=10d=10, and K=5K=5. Our algorithms are in bold. In each column, the lowest mean regret is in bold and the second lowest is underlined.

Algorithmκ=5\kappa=5κ=10\kappa=10κ=20\kappa=20κ=40\kappa=40κ=100\kappa=100
SupSplitLog$^{+}$363.12±136.51\mathbf{363.12 \pm 136.51}368.21±249.01368.21 \pm 249.01365.18±108.34365.18 \pm 108.34292.71±90.21292.71 \pm 90.21710.21±38.53710.21 \pm 38.53
SupSplitLog$^{+}$ + doubling476.73±199.17476.73 \pm 199.17693.07±260.39693.07 \pm 260.39689.93±60.94689.93 \pm 60.94806.62±103.06806.62 \pm 103.061516.86±46.511516.86 \pm 46.51
SupSecantLog506.74±362.49506.74 \pm 362.49315.52±275.56\mathbf{315.52 \pm 275.56}214.98±216.06\mathbf{214.98 \pm 216.06}221.53±224.52\mathbf{221.53 \pm 224.52}204.86±205.91\mathbf{204.86 \pm 205.91}
SupSecantLog + doubling526.06±210.40526.06 \pm 210.40377.81±329.41377.81 \pm 329.41299.74±169.11‾\underline{299.74 \pm 169.11}238.15±153.96‾\underline{238.15 \pm 153.96}264.62±166.24‾\underline{264.62 \pm 166.24}
SupSplitLog363.54±130.48‾\underline{363.54 \pm 130.48}367.34±248.35‾\underline{367.34 \pm 248.35}364.11±108.95364.11 \pm 108.95292.25±90.69292.25 \pm 90.69710.21±38.53710.21 \pm 38.53
SupSplitLog + doubling425.08±141.87425.08 \pm 141.87711.94±360.29711.94 \pm 360.29688.74±60.26688.74 \pm 60.26806.62±103.06806.62 \pm 103.061516.86±46.511516.86 \pm 46.51
  • SupSecantLog has the lowest mean regret in four of the five settings, showing good practical performance even for large κ\kappa. The full results are in Section K.3 (Figure 2 and Table 2).

  • Finally, as the reviewer notes, reducing κ\kappa dependence is important in logistic bandits. We leave further reductions to future work.

[W2] Limited practical validation: The paper provides no numerical experiments or end-to-end computational complexity analysis, leaving practical performance and scalability unclear.

In the revision, we added (i) four numerical experiments comparing six algorithms in regret, running time, and memory usage (new Section K), and (ii) the time and memory complexity of computing the initial-point estimates (Section K.1). Details are below.

  • We conducted experiments to evaluate practical performance. We compare six algorithms: SupSplitLog (Bae and Lee, 2026, Algorithm 1), SupSplitLog+, SupSecantLog, and their versions using the doubling wrapper (Algorithm 3).

  • We vary (i) the feature dimension dd, (ii) the curvature parameter κ\kappa, (iii) the confidence coefficient used for exploration, and (iv) the coefficient of the routing threshold τs\tau_s.

  • In addition to regret, we record wall-clock time and mean and peak memory usage to measure end-to-end computational cost.

Table. Final cumulative regret (mean ±2\pm2 SD), running time, and memory usage over 10 runs for d∈5,20,80d\in\\{5,20,80\\}, with T=104T=10^4, κ=10\kappa=10, and K=5K=5. These are three of the five dimensions d∈5,10,20,40,80d\in\\{5,10,20,40,80\\} reported in Table 1. Our algorithms are in bold. For each dd, the lowest mean regret is in bold and the second lowest is underlined.

ddAlgorithmRegret (mean ±2\pm2 SD)Time (s)Mean RSS (MiB)Peak RSS (MiB)
5SupSplitLog$^{+}$335.82±295.46335.82 \pm 295.461.18693.7695.18
5SupSplitLog$^{+}$ + doubling427.30±214.65427.30 \pm 214.651.14392.9993.77
5SupSecantLog239.10±387.92‾\underline{239.10 \pm 387.92}1.48993.8095.73
5SupSecantLog + doubling194.58±136.76\mathbf{194.58 \pm 136.76}1.44393.5195.40
5SupSplitLog336.44±295.33336.44 \pm 295.331.01892.4093.32
5SupSplitLog + doubling477.45±238.75477.45 \pm 238.750.90493.6894.43
20SupSplitLog$^{+}$559.92±283.00559.92 \pm 283.000.75499.76104.74
20SupSplitLog$^{+}$ + doubling684.15±218.24684.15 \pm 218.240.80199.16104.70
20SupSecantLog399.96±155.42\mathbf{399.96 \pm 155.42}1.594100.39104.71
20SupSecantLog + doubling525.43±104.98‾\underline{525.43 \pm 104.98}1.52899.88104.76
20SupSplitLog557.45±288.20557.45 \pm 288.200.68798.69104.75
20SupSplitLog + doubling683.76±218.34683.76 \pm 218.340.724100.09105.98
80SupSplitLog$^{+}$539.43±65.76539.43 \pm 65.761.139125.94150.61
80SupSplitLog$^{+}$ + doubling612.15±34.32612.15 \pm 34.321.139123.77150.53
80SupSecantLog484.20±85.85‾\underline{484.20 \pm 85.85}3.517127.20150.54
80SupSecantLog + doubling477.21±65.01\mathbf{477.21 \pm 65.01}3.539126.85150.54
80SupSplitLog539.43±65.76539.43 \pm 65.760.997126.81150.47
80SupSplitLog + doubling612.15±34.32612.15 \pm 34.320.877125.28150.28
  • SupSecantLog and its doubling version have the lowest two mean regrets for d∈5,20,80d\in\\{5,20,80\\}, with memory usage similar to the baselines and mean runtimes below 3.63.6 seconds. The full results for (i)--(iv) are in Sections K.2--K.5 (Figures 1--4 and Tables 1--4), and the experimental settings are in Section K.1.

  • For computational complexity, computing one initial-point estimate from Eq. (12) with mm evaluations of its left-hand side takes O(m(∣Pk∣d2+d3))O(m(|P_k|d^2+d^3)) time and O(∣Pk∣d+d2)O(|P_k|d+d^2) memory, where PkP_k is the initial-point set. SupSecantLog computes two such estimates. Implementation details are in Section K.1.

[W3] Unresolved optimality: No matching lower bound establishes whether the additive d4/3d^{4/3} dependence is optimal or can be further improved.

We thank the reviewer for raising this important point. We do not provide a matching lower bound for the d4/3d^{4/3} dependence, and it remains open whether other estimation methods can further improve the dependence on dd; we leave this question for future work. However, our result matches the dimension dependence conjectured by Mason et al. (2022). Below, we explain why this exponent arises and why it is the best order obtained by optimizing the bias and remainder bounds in our analysis. We added this discussion to the new Section B.1.

  • Mason et al. (2022, Section 4 and Appendix F) conjecture a d4/3d^{4/3} warmup sample complexity by comparing the prediction bias and standard deviation of the Krichevsky--Trofimov (KT) estimator. In their example, each of the dd coordinates of θ⋆\theta_\star is estimated from NN observations, giving n=dNn=dN observations in total. The MLE of each coordinate has bias of order N−1N^{-1}, while the KT estimator reduces it to order N−2N^{-2}. For the prediction x⊤θ^x^\top\widehat\theta with x=(1,…,1)/dx=(1,\ldots,1)/\sqrt d, the KT estimator has bias of order d/N2\sqrt d/N^2 and standard deviation of order N−1/2N^{-1/2}. Balancing them gives

    \quad\Longrightarrow\quad N\asymp d^{1/3}, \qquad n=dN\asymp d^{4/3}.$$ However, they left this rate as a conjecture because the required finite-sample concentration bound for the bias-corrected estimator with arbitrary feature vectors remained open.
  • Our score adjustment, like the KT correction, reduces the leading nonlinear estimation bias. We combine this adjustment with secant estimation to attain the conjectured exponent. When estimating a coordinate of θ⋆\theta_\star in Mason et al.'s example, let SS count successes among its NN observations. Applying the adjustment in Eq. (12) to the unregularized logistic score gives

    \quad\Longrightarrow\quad \widehat\theta=\log\frac{S+1/2}{N-S+1/2}.$$ This is the KT estimator, defined by adding $1/2$ to both the success and failure counts before taking log odds. Like KT, our initial estimates $\bar\theta_k$ retain a residual bias after correction. Eq. (**13**) writes $\bar\theta_k-\theta_\star=\zeta_k+b_k$ with $\mathbb E[\zeta_k]=0$, so this bias is $\mathbb E[b_k]$. Lemma **7** bounds $\\|b_k\\|_{V_k}^2$ using a squared regularization bias term $\lambda_p$ and a nonlinear remainder term $d/\lambda_p^2$. Balancing these terms gives $$\lambda_p\asymp\frac{d}{\lambda_p^2} \quad\Longrightarrow\quad \lambda_p\asymp d^{1/3}, \qquad \lambda_p+\frac{d}{\lambda_p^2}\asymp d^{1/3}.$$ The regret bound for collecting observations for the $d$-dimensional initial estimates introduces an additional factor $d$, yielding the additive dimension dependence $d\cdot d^{1/3}=d^{4/3}$.

References

[1] Mason et al., "An Experimental Design Approach for Regret Minimization in Logistic Bandits", AAAI, 2022.

Dear Reviewer zyMv

Thank you for your thoughtful comments and questions. We have addressed each of them in our rebuttal and would be grateful if you could take a moment to review our responses.

Thanks, Authors

Reviewer_rGPkOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies finite-armed logistic bandits without a feature-covariance lower bound. SupSplitLog+ reduces the additive dimension dependence from d5/2d^{5/2} to d3/2d^{3/2} with a revised sample-splitting rule and tighter error bounds. SupSecantLog further reduces it to d4/3d^{4/3} by combining secant estimation with two independent, bias-adjusted initial estimates. Both retain the leading dT\sqrt{dT} dependence.

Critical strengths
  1. The sample-splitting rule in SupSplitLog+ controls both pointwise uncertainty and accumulated approximation error.
  2. The secant approximation replaces a squared initial-point prediction error with a product of independent errors. Combined with bias correction, this gives a concrete mechanism for reducing the approximation error and improving the dimension dependence.
  3. The improved bounds hold for time-varying context sets without requiring a positive lower bound on the feature covariance.
Critical weaknesses
  1. The improvement in dimension dependence is theoretically meaningful, but its benefit at finite horizons is unclear given the large constants and initial sampling requirements.
  2. The paper provides limited guidance on computing the bias-adjusted estimates in practice. The computational cost and the numerical accuracy needed to preserve the guarantees remain unclear.
Questions for authors
  1. Are there conditions where SupSplitLog+ has a smaller regret bound than SupSecantLog once constants and initial sampling costs are included?
  2. Can the initial sampling requirements be further reduced while preserving the regret guarantees?
3 comments

[W1] The improvement in dimension dependence is theoretically meaningful, but its benefit at finite horizons is unclear given the large constants and initial sampling requirements.

[Q2] Can the initial sampling requirements be further reduced while preserving the regret guarantees?

We answer [W1] and [Q2] together, as both concern the initial sampling requirements and their effect on the regret bound. First, we show that the additive terms of SupSplitLog+ and SupSecantLog are smaller than that of SupSplitLog when d≳κ5/2d\gtrsim\kappa^{5/2} and d≳κ15/7d\gtrsim\kappa^{15/7}, respectively, with the same or better leading order. Second, the initial sampling requirements can indeed be reduced: in the revision, we lowered the curvature factor of the additive term from κ7\kappa^7 to κ5\kappa^5 for SupSplitLog+ and from κ15/2\kappa^{15/2} to κ5\kappa^5 for SupSecantLog. Third, our additional experiments show practical advantages even outside these regimes. Details are below.

  • We added a comparison of the regret upper bounds of SupSplitLog, SupSplitLog+, and SupSecantLog (new Section B.4). We interpret the reviewer's “initial sampling requirements” as the number of observations collected in the initial-point sets PP or P1,P2P_1,P_2, and compare the associated additive regret terms.

  • Simple modifications reduce the additive term from O~(κ7d3/2)\widetilde{\mathcal O}(\boldsymbol{\kappa^7}d^{3/2}) to O~(κ5d3/2)\widetilde{\mathcal O}(\boldsymbol{\kappa^5}d^{3/2}) for SupSplitLog+, and from O~(κ15/2d4/3)\widetilde{\mathcal O}(\boldsymbol{\kappa^{15/2}}d^{4/3}) to O~(κ5d4/3)\widetilde{\mathcal O}(\boldsymbol{\kappa^5}d^{4/3}) for SupSecantLog. Briefly, we tightened the bounds on the regularization bias induced by λp\lambda_p and the nonlinear remainder, then updated the design matrices and parameters. The steps of Algorithms 1 and 2 are unchanged; both now use the updated design matrices (Eq. (1) and the definitions of VV and VkV_k on pp. 4 and 8) and parameters (Section H), and Theorems 1 and 2 state the resulting bounds. The key bounds are in Eq. (29) (p. 22) and Eqs. (56) and (58) (p. 27). Section and page numbers refer to the revised PDF.

  • Our additional experiments show practical advantages even outside these regimes. In the experiments below varying κ\kappa, SupSecantLog has the lowest mean regret in four of the five settings. Full settings and additional results are in Sections K.1--K.5, with the curvature results in Figure 2 and Table 2.

Table. Final cumulative regret (mean ±2\pm2 SD over 10 runs) as κ\kappa varies, with T=104T=10^4, d=10d=10, and K=5K=5. Our algorithms are in bold. In each column, the lowest mean regret is in bold and the second lowest is underlined.

Algorithmκ=5\kappa=5κ=10\kappa=10κ=20\kappa=20κ=40\kappa=40κ=100\kappa=100
SupSplitLog$^{+}$363.12±136.51\mathbf{363.12 \pm 136.51}368.21±249.01368.21 \pm 249.01365.18±108.34365.18 \pm 108.34292.71±90.21292.71 \pm 90.21710.21±38.53710.21 \pm 38.53
SupSplitLog$^{+}$ + doubling476.73±199.17476.73 \pm 199.17693.07±260.39693.07 \pm 260.39689.93±60.94689.93 \pm 60.94806.62±103.06806.62 \pm 103.061516.86±46.511516.86 \pm 46.51
SupSecantLog506.74±362.49506.74 \pm 362.49315.52±275.56\mathbf{315.52 \pm 275.56}214.98±216.06\mathbf{214.98 \pm 216.06}221.53±224.52\mathbf{221.53 \pm 224.52}204.86±205.91\mathbf{204.86 \pm 205.91}
SupSecantLog + doubling526.06±210.40526.06 \pm 210.40377.81±329.41377.81 \pm 329.41299.74±169.11‾\underline{299.74 \pm 169.11}238.15±153.96‾\underline{238.15 \pm 153.96}264.62±166.24‾\underline{264.62 \pm 166.24}
SupSplitLog363.54±130.48‾\underline{363.54 \pm 130.48}367.34±248.35‾\underline{367.34 \pm 248.35}364.11±108.95364.11 \pm 108.95292.25±90.69292.25 \pm 90.69710.21±38.53710.21 \pm 38.53
SupSplitLog + doubling425.08±141.87425.08 \pm 141.87711.94±360.29711.94 \pm 360.29688.74±60.26688.74 \pm 60.26806.62±103.06806.62 \pm 103.061516.86±46.511516.86 \pm 46.51

[Q1] Are there conditions where SupSplitLog+ has a smaller regret bound than SupSecantLog once constants and initial sampling costs are included?

  • Comparing SupSplitLog+ and SupSecantLog, SupSplitLog+ has a leading term no larger than SupSecantLog's when α1≤α2\alpha_1\le\alpha_2. Comparing the additive terms, SupSplitLog+ has a smaller additive term when Md1/6<4C2Lρ/α1M_d^{1/6}<4C_2L\rho/\alpha_1. Together, these conditions ensure a smaller regret upper bound for SupSplitLog+. Both conditions can hold simultaneously. An example and details are given in the new Section B.4. The definitions of the parameters can be found in Sections 4.3 and H.

[W2] The paper provides limited guidance on computing the bias-adjusted estimates in practice. The computational cost and the numerical accuracy needed to preserve the guarantees remain unclear.

We thank the reviewer for pointing out that the submission gave limited guidance on computing the bias-adjusted estimates, and we agree. In the revision, we added (i) a description of how we compute the bias-adjusted estimates, with its time and memory costs (new Section K.1), (ii) a sufficient numerical accuracy for preserving the regret order (new Section B.2), and (iii) experiments measuring running time and memory usage (Section K.2). Details are below.

  • We solve Eq. (12) by repeating two steps: (i) compute its left-hand side FPk(θj)F_{P_k}(\theta^j) and the regularized Hessian HPk(θj)H_{P_k}(\theta^j), and (ii) update

    θj+1=θj−ajHPk(θj)−1FPk(θj).\theta^{j+1}=\theta^j-a_jH_{P_k}(\theta^j)^{-1}F_{P_k}(\theta^j).

    We choose the step size aja_j to decrease the residual and repeat until ∣FPk(θj)∣Vk−1≤10−10\\|F_{P_k}(\theta^j)\\|_{V_k^{-1}}\le10^{-10}.

  • For computational cost, computing one estimate with mm evaluations of FPkF_{P_k} takes O(m(∣Pk∣d2+d3))O(m(|P_k|d^2+d^3)) time and O(∣Pk∣d+d2)O(|P_k|d+d^2) memory. SupSecantLog computes two such estimates. For numerical accuracy, the new Section B.2 shows that a score residual at most (4κˉT2)−1(4\bar\kappa T^2)^{-1} at each level, where κˉ=1/μ˙(B+1)\bar\kappa=1/\dot\mu(B+1), preserves the regret order after updating the constants.

  • We also conducted experiments to evaluate computational cost and memory use in practice by recording wall-clock time and mean and peak memory usage.

Table. Final cumulative regret (mean ±2\pm2 SD), running time, and memory usage over 10 runs for d∈5,20,80d\in\\{5,20,80\\}, with T=104T=10^4, κ=10\kappa=10, and K=5K=5. These are three of the five dimensions d∈5,10,20,40,80d\in\\{5,10,20,40,80\\} reported in Table 1. Our algorithms are in bold. For each dd, the lowest mean regret is in bold and the second lowest is underlined.

ddAlgorithmRegret (mean ±2\pm2 SD)Time (s)Mean RSS (MiB)Peak RSS (MiB)
5SupSplitLog$^{+}$335.82±295.46335.82 \pm 295.461.18693.7695.18
5SupSplitLog$^{+}$ + doubling427.30±214.65427.30 \pm 214.651.14392.9993.77
5SupSecantLog239.10±387.92‾\underline{239.10 \pm 387.92}1.48993.8095.73
5SupSecantLog + doubling194.58±136.76\mathbf{194.58 \pm 136.76}1.44393.5195.40
5SupSplitLog336.44±295.33336.44 \pm 295.331.01892.4093.32
5SupSplitLog + doubling477.45±238.75477.45 \pm 238.750.90493.6894.43
20SupSplitLog$^{+}$559.92±283.00559.92 \pm 283.000.75499.76104.74
20SupSplitLog$^{+}$ + doubling684.15±218.24684.15 \pm 218.240.80199.16104.70
20SupSecantLog399.96±155.42\mathbf{399.96 \pm 155.42}1.594100.39104.71
20SupSecantLog + doubling525.43±104.98‾\underline{525.43 \pm 104.98}1.52899.88104.76
20SupSplitLog557.45±288.20557.45 \pm 288.200.68798.69104.75
20SupSplitLog + doubling683.76±218.34683.76 \pm 218.340.724100.09105.98
80SupSplitLog$^{+}$539.43±65.76539.43 \pm 65.761.139125.94150.61
80SupSplitLog$^{+}$ + doubling612.15±34.32612.15 \pm 34.321.139123.77150.53
80SupSecantLog484.20±85.85‾\underline{484.20 \pm 85.85}3.517127.20150.54
80SupSecantLog + doubling477.21±65.01\mathbf{477.21 \pm 65.01}3.539126.85150.54
80SupSplitLog539.43±65.76539.43 \pm 65.760.997126.81150.47
80SupSplitLog + doubling612.15±34.32612.15 \pm 34.320.877125.28150.28
  • For d∈5,20,80d\in\\{5,20,80\\}, SupSecantLog and its doubling version have mean runtimes below 3.63.6 seconds and memory usage similar to the baselines, and they have the lowest two mean regrets. Full results are in Section K.2.

[Previous Q2] Is the additive d4/3d^{4/3} dependence optimal, or can it be improved further?

We thank the reviewer for raising this important point. We do not provide a matching lower bound for the d4/3d^{4/3} dependence, and it remains open whether other estimation methods can further improve the dependence on dd; we leave this question for future work. However, our result matches the dimension dependence conjectured by Mason et al. (2022). Below, we explain why this exponent arises and why it is the best order obtained by optimizing the bias and remainder bounds in our analysis. We added this discussion to the new Section B.1.

  • Mason et al. (2022, Section 4 and Appendix F) conjecture a d4/3d^{4/3} warmup sample complexity by comparing the prediction bias and standard deviation of the Krichevsky--Trofimov (KT) estimator. In their example, each of the dd coordinates of θ⋆\theta_\star is estimated from NN observations, giving n=dNn=dN observations in total. The MLE of each coordinate has bias of order N−1N^{-1}, while the KT estimator reduces it to order N−2N^{-2}. For the prediction x⊤θ^x^\top\widehat\theta with x=(1,…,1)/dx=(1,\ldots,1)/\sqrt d, the KT estimator has bias of order d/N2\sqrt d/N^2 and standard deviation of order N−1/2N^{-1/2}. Balancing them gives

    \quad\Longrightarrow\quad N\asymp d^{1/3}, \qquad n=dN\asymp d^{4/3}.$$ However, they left this rate as a conjecture because the required finite-sample concentration bound for the bias-corrected estimator with arbitrary feature vectors remained open.
  • Our score adjustment, like the KT correction, reduces the leading nonlinear estimation bias. We combine this adjustment with secant estimation to attain the conjectured exponent. When estimating a coordinate of θ⋆\theta_\star in Mason et al.'s example, let SS count successes among its NN observations. Applying the adjustment in Eq. (12) to the unregularized logistic score gives

    \quad\Longrightarrow\quad \widehat\theta=\log\frac{S+1/2}{N-S+1/2}.$$ This is the KT estimator, defined by adding $1/2$ to both the success and failure counts before taking log odds. Like KT, our initial estimates $\bar\theta_k$ retain a residual bias after correction. Eq. (**13**) writes $\bar\theta_k-\theta_\star=\zeta_k+b_k$ with $\mathbb E[\zeta_k]=0$, so this bias is $\mathbb E[b_k]$. Lemma **7** bounds $\\|b_k\\|_{V_k}^2$ using a squared regularization bias term $\lambda_p$ and a nonlinear remainder term $d/\lambda_p^2$. Balancing these terms gives $$\lambda_p\asymp\frac{d}{\lambda_p^2} \quad\Longrightarrow\quad \lambda_p\asymp d^{1/3}, \qquad \lambda_p+\frac{d}{\lambda_p^2}\asymp d^{1/3}.$$ The regret bound for collecting observations for the $d$-dimensional initial estimates introduces an additional factor $d$, yielding the additive dimension dependence $d\cdot d^{1/3}=d^{4/3}$.

References

[1] Mason et al., "An Experimental Design Approach for Regret Minimization in Logistic Bandits", AAAI, 2022.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.