- 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
-
This paper proposed a substantive mechanism for controlling nonlinear estimation errors.
-
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
-
Large curvature factors limit the scope of the dimension improvement, and the crossover regime is not made explicit.
-
The computational cost of the estimator is insufficiently characterized.
Questions for authors
-
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?
-
What solver is intended for Eq. (12), and what are its time and memory costs?
-
How small must its residual be as a function of level and horizon to preserve the main regret guarantee?
-
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
[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 and the regularized Hessian , and (ii) update
We choose the step size to decrease the residual and repeat until .
-
For computational cost, computing one estimate with evaluations of takes time and memory. SupSecantLog computes two such estimates. For numerical accuracy, the new Section B.2 shows that a score residual at most at each level, where , 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 SD), running time, and memory usage over 10 runs for , with , , and . These are three of the five dimensions reported in Table 1. Our algorithms are in bold. For each , the lowest mean regret is in bold and the second lowest is underlined.
| Algorithm | Regret (mean SD) | Time (s) | Mean RSS (MiB) | Peak RSS (MiB) | |
|---|---|---|---|---|---|
| 5 | SupSplitLog$^{+}$ | 1.186 | 93.76 | 95.18 | |
| 5 | SupSplitLog$^{+}$ + doubling | 1.143 | 92.99 | 93.77 | |
| 5 | SupSecantLog | 1.489 | 93.80 | 95.73 | |
| 5 | SupSecantLog + doubling | 1.443 | 93.51 | 95.40 | |
| 5 | SupSplitLog | 1.018 | 92.40 | 93.32 | |
| 5 | SupSplitLog + doubling | 0.904 | 93.68 | 94.43 | |
| 20 | SupSplitLog$^{+}$ | 0.754 | 99.76 | 104.74 | |
| 20 | SupSplitLog$^{+}$ + doubling | 0.801 | 99.16 | 104.70 | |
| 20 | SupSecantLog | 1.594 | 100.39 | 104.71 | |
| 20 | SupSecantLog + doubling | 1.528 | 99.88 | 104.76 | |
| 20 | SupSplitLog | 0.687 | 98.69 | 104.75 | |
| 20 | SupSplitLog + doubling | 0.724 | 100.09 | 105.98 | |
| 80 | SupSplitLog$^{+}$ | 1.139 | 125.94 | 150.61 | |
| 80 | SupSplitLog$^{+}$ + doubling | 1.139 | 123.77 | 150.53 | |
| 80 | SupSecantLog | 3.517 | 127.20 | 150.54 | |
| 80 | SupSecantLog + doubling | 3.539 | 126.85 | 150.54 | |
| 80 | SupSplitLog | 0.997 | 126.81 | 150.47 | |
| 80 | SupSplitLog + doubling | 0.877 | 125.28 | 150.28 |
- For , SupSecantLog and its doubling version have mean runtimes below 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 dependence, and it remains open whether other estimation methods can further improve the dependence on ; 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 warmup sample complexity by comparing the prediction bias and standard deviation of the Krichevsky--Trofimov (KT) estimator. In their example, each of the coordinates of is estimated from observations, giving observations in total. The MLE of each coordinate has bias of order , while the KT estimator reduces it to order . For the prediction with , the KT estimator has bias of order and standard deviation of order . 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 in Mason et al.'s example, let count successes among its 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}$.
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) to O(κ5d3/2) for SupSplitLog+, and from O(κ15/2d4/3) to O(κ5d4/3) for SupSecantLog. Briefly, we tightened the bounds on the regularization bias induced by λ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 V and Vk 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/2 and d≳κ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(logT)3/2, while SupSplitLog+ has leading order κdT(logT)3/2. The leading factor favors SupSecantLog since κ≥2(1+B). Its additive term has better dependence on d but worse dependence on logT. For fixed K,δ and T≥d2, SupSecantLog has a smaller additive term than SupSplitLog+ when d≳(logT)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 κ, 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 SD over 10 runs) as κ varies, with T=104, d=10, and K=5. Our algorithms are in bold. In each column, the lowest mean regret is in bold and the second lowest is underlined.