Eluder dimension: localise it!

We thank the reviewer for their careful read and helpful suggestions.

Localized eluder dimension. The localised eluder dimension is a purely analytic tool used to prove tighter regret bounds, and is not needed to run the $\ell$-UCB algorithm. Thus, there is no need to compute it.

The function class $\mathcal{F}$. The set of functions F do not need to be bounded or positive. The losses however need to be bounded, with known bounds. Hell will freeze over before the requirement that the losses are bounded from below (with a known bound) is removed: this is a feature of every small cost bound in the literature. And by the time this lower bound is known, we might as well offset by the lower bound and say that the loss is nonnegative. The assumption of an upper bound is not necessary: it can be replaced by, for example, the assumption that the right (upper) tail of the losses satisfies a moment condition (e.g. is subgaussian) for any choice of states/actions.

The number of rogue steps and tightness. The number of rogue steps (the card{} term) appears only additively and therefore is second order term— negligible for sufficiently large n (the horizon). Similar additive terms also appear in previous works on logistic bandits (which is an special case of our analysis), making this behavior consistent with existing literature (see, e.g., [1]). When specialized to the generalized linear bandit setting our regret bound matches the best bounds for the problem-specific algorithms, and indeed matches the lower bound of [1].

Experimental scope. Since the main focus of our work is the theoretical analysis of optimistic algorithms (i.e., eluder dimension) rather than proposing new algorithms, we focus on a comprehensive theoretical treatment of adaptive algorithms for decision making. However, given the reviewers’ interest, we will consider adding a synthetic experimental section in the final version.

[1] Abeille, Marc, et al. "Instance-wise minimax-optimal algorithms for logistic bandits."

We appreciate the reviewer’s time and thoughtful feedback on our work.

Broader Settings. Perhaps the situation would be more clear if we go through the role of each assumptions.

1. Self-concordance: This is a property of the loss function. Since the loss function is chosen by the algorithm designer, one can select a loss that is self-concordant. Many commonly used losses (e.g., logistic and Poisson and many more [1]) satisfy this property. Importantly, self-concordance is not required for our main theoretical result—it is rather used to compare with existing results in specilized settings such as logistic bandits, and to achieve computational efficiency through ellipsoidal relaxtion of the confidence set.
2. Triangle condition: This condition seems essential for achieving small-cost bounds. For example, the squared loss does not satisfy the triangle condition, and we know that small-cost regret bounds are not achievable with it (see [2]).
3. Realizability: This is a true modeling assumption. Removing it entirely is challenging; however, one could restate our results in terms of a “best-in-class” comparator and derive the corresponding regret bounds. The analysis of such misspecified settings would be possible but is beyond the scope of this paper.

Computational efficiency. Appendix C.5 describes an ellipsoidal relaxation of our confidence set (with a $2(1+SM)$ blowup), which reduces the computational complexity to that of LinUCB—a standard approach in the bandit literature. In practice, LinUCB requires solving a joint optimization over the parameter $\theta$ and action $a$, where $\theta$ lies in an ellipse. This optimization is computationally efficient for many common action sets, including finite sets, polytopes, and various other convex sets.

Experimental scope. Since the main focus of our work is the theoretical analysis of optimistic algorithms (i.e., eluder dimension) rather than proposing new algorithms, we focus on a comprehensive theorectial treatment of adaptive algorithms for decision making. However, given the reviewers’ interest, we will consider adding a synthetic experimental section in the final version.

General function classes. Yes, our analysis indeed naturally extend to general function classes. One should only provide the necessary "supervised learning" fast rate guarantees (See, e.g., [3] for the RKHS case).

[1] Liu, Shuai, et al. "Almost Free: Self-concordance in Natural Exponential Families and an Application to Bandits."

[2] D. J. Foster and A. Krishnamurthy. "Efficient first-order contextual bandits: prediction, allocation, and triangular discrimination."

[3] Akhavan, Arya, et al. "Bernstein-type dimension-free concentration for self-normalised martingales."

We appreciate the reviewer’s reading of our work and their helpful suggestions.

Experimental design-based approaches. We thank the reviewer for highlighting these relevant papers on experimental design–based approaches. We will include them in the related works section of the final version.

Comparison with similar results. Perhaps the explanation in Section 4.1 helps clarify this point. Our analysis removes the need for an explicit warm-up phase, which can be thought of as a forced experimental design step. Instead, we introduce the localized eluder dimension and handle the "experimental design" aspect analytically rather than algorithmically. Thus, our method achieves comparably strong instance-dependent regret bounds without requiring a warm-up, naturally generalizing beyond bandit settings to reinforcement learning scenarios where explicit warm-ups or optimal-design methods are less feasible.

Writing and examples. We appreciate the feedback and will work to better highlight the importance of the results in the final version. Regarding the motivating example, we would like to mention that the current example (“clickthrough rates in online advertising,” lines 164–169) is intended to address this point and provide an intuitive illustration. Nevertheless, we agree it would be helpful to further clarify why the information-gain factor can easily blow up, and we will make these scenarios more explicit in the final version.

Reinforcement learning. The RL result is indeed the most interesting; we will use the extra space afforded by the camera ready to include it in the main paper. We will also revisit the story-telling to emphasise the RL result more. Thank you for this feedback.

We thank the reviewer for their reading and helpful suggestions.

Number of rogue steps. The number of rogue steps appears only additively in the regret bound of Theorem 4.1 and is therefore a second-order term. Hence, even when $\kappa$ is large, its effect remains negligible for sufficiently long horizons.

Choice of localization radius r. The radius r is used solely in the analysis and does not need to be specified for the algorithm. For example, setting r=1/M, where M is the self-concordance parameter, ensures that the localized eluder dimension is bounded, as as well as the number of rogue steps, as stated in Proposition 4.3 and Proposition 4.4.

Experimental scope. Since the main focus of our work is the theoretical analysis of optimistic algorithms (i.e., eluder dimension) rather than proposing new algorithms, we focus on a comprehensive theoretical treatment of adaptive algorithms for decision making. However, given the reviewers’ interest, we will consider adding a synthetic experimental section in the final version.

Non eluder methods. Small-cost regret bounds exist in specific settings (e.g., logistic bandits) without using the eluder dimension. However, the eluder dimension remains a popular complexity measure in bandits and RL and as we show, when applied naively it prevents achieving small-cost bounds. Our contribution introduces localization to overcome this limitation, bringing eluder-based analysis closer to the behavior seen in specialized non-eluder approaches.

Computational efficiency. Appendix C.5 describes an ellipsoidal relaxation of our confidence set (with a $2(1+SM)$ blowup), which reduces the computational complexity to that of LinUCB—a standard approach in the bandit literature. In practice, LinUCB requires solving a joint optimization over the parameter $\theta$ and action $a$, where $\theta$ lies in an ellipse. This optimization is computationally efficient for many common action sets, including finite sets, polytopes, and various other convex sets.

Unbounded costs. While we do not provide a formal analysis for unbounded costs in this paper, we believe that our techniques could extend to settings with sub-Gamma costs (or other standard tail assumptions). We leave a detailed treatment of this extension as an interesting direction for future work.

Eluder dimension computation. The localised eluder dimension is a purely analytic tool used to prove tighter regret bounds, and is not needed to run the $\ell$-UCB algorithm. Thus, there is no need to compute it.