1. On sparsity: Your comment that "The sparsity only holds when the basis vectors $b_i$ align with the row space of the matrix" is incorrect. The sparsity holds for any basis vectors $\{b_1, \ldots, b_{K-d}\}$ in $\mathrm{R}(\\mathbf{X})^\perp$. By definition, if $(I_K - P_X)U^\top\theta_\star^{(u)}$ lies in a subspace of dimension $d_h$, it can be expressed as a linear combination of at most $d_h$ nonzero coefficients for any set of basis vectors $\{b_1, \ldots, b_{K-d}\}$. While the specific coefficients $\mu_{\star,1}^{(u)}, \ldots, \mu_{\star,K-d}^{(u)}$ may vary depending on the choice of basis vectors, the sparsity itself (i.e., the presence of only $d_h$ nonzero entries) remains consistent across all bases.

2. On the dependency on $\tilde{\sigma}_{\min}$: We are glad to present an updated version of our work, which includes a slight modification to the estimator. This adjustment eliminates the dependency on $\tilde{\sigma}\_{\min}$ (and $\tilde{\sigma}\_{\max}$) in the analysis (see Theorem 3 and Appendix B.3 for details). As a result, the dependency on $\tilde{\sigma}_{\min}^{-1}$ is no longer a concern. This improvement is possible by normalizing the estimator with the Gram matrix as in Eq. (9) and Eq. (12).

3. On the number of exploration rounds: Thank you for pointing out the typo, and we have corrected $|\mathcal{E}_t| \le t$ to $|\mathcal{E}_t| \ge (\sqrt{16K} + 1)^2 2(1-p)^{-2} K^2 \log(2Kt^2/\delta)$.

Dear Reviewer,

We sincerely assure the reviewer that our results are correct. We appreciate the opportunity to clarify this point. Upon careful consideration, we find that the example provided in the comment does not serve as a counterexample to the results in our paper.

It is important to note that $d_h$ nonzero coefficients are needed with a basis constructed within the subspace $\mathrm{R}(\mathbf{X})^\perp$, NOT within the entire space $\mathbb{R}^K$. (Note that we can compute the subspace $\mathrm{R}(\mathbf{X})^\perp$ and we find the basis $\{\mathbf{b}\_1,\ldots,\mathbf{b}\_{K-d}\}$ within this subspace, rather than using the full space $\mathbb{R}^K$.) In your example, our algorithm identifies the basis in the subspace spanned by the vector $[1,1,\ldots,1]^\top$ but not the Euclidean basis in $\mathbb{R}^d$. As a result, our basis is $\mathbf{b}_1 = [1, 1, \ldots, 1]^\top$, meaning only one basis vector is required to represent $[1, 1, \ldots, 1]^\top$.

We are happy to make this distinction clearer in the revised manuscript to ensure there is no ambiguity. We sincerely hope that our explanation has addressed your concerns. Given the correctness of our results, we respectfully request that you reconsider your evaluation of our work in light of this clarification.

Thank you again for your time and consideration.

For [1], I still don't think it is correct in general. You should provide a proof if you believe it is correct in this scenario. Consider the following example: The vector $[1, 1, \dots, 1]^\top$ lies in the subspace spanned by the vector $[1, 1, \dots, 1]^\top$, which has dimension $1$. However, with respect to the standard basis $e_1, \dots, e_d$, you need $d$ non-zero coefficients to represent this vector.

Let us assume $K = n + 1$ and $X = [0, \dots, 0, 1]^\top$. In this case, $e_1, \dots, e_n$ form a feasible basis for the subspace $R(X)^\perp$. Furthermore, let us assume $U = [[1, \dots, 1, 0]]$ and $\theta_*^{(u)} = [1]$. Then, we have $(I_K - P_X) U^\top \theta_*^{(u)} = [1, \dots, 1, 0]^\top$. It is clear that $d_h := \mathrm{dim} (R((I_K - P_X) U^\top) ) = 1$. However, to express $(I_K - P_X) U^\top \theta_*^{(u)}$ under the Euclidean basis, $n$ non-zero coefficients are required to represent this vector.

[W1] On the boundedness assumption: We are pleased to share that, by removing the dependency of our regret bound on $\tilde{\sigma}_{\min}$, we have also eliminated the requirement for the bounded feature and parameter assumption in our problem setting. We kindly invite you to review the updated version of our paper for further details.

Answers to questions:

[Q1] On the typo in Line 1325: Thank you for bringing the typo to our attention; we have now corrected it.

[Q2] On the utilization of observable features: The observable part is utilized to identify $\mathrm{R}(\mathbf{X})^{\perp}$ and construct the basis vectors accordingly. Without leveraging the observed contexts, the algorithm would rely on arbitrary basis vectors, resulting in a regret of $\tilde{O}(\sqrt{K T})$.

[Q3-4] On the dependency on $\tilde{\sigma}_{\min}$: As mentioned in the first response, we have successfully removed the dependency on $\tilde{\sigma}_{\min}$ from our regret bound by normalizing the coefficients for the lasso estimator with the Gram matrix slightly as in Eq. (9) and Eq. (12).

Thank you for your question. We are happy to address it. When there is no observable part, we have $\mathrm{R}(\mathbf{X})^\perp = \mathbb{R}^K$, not $\mathbb{R}^d$, since we are considering the row space of features. Then our proposed algorithm uses the standard basis in $\mathbb{R}^K$ and the regret bound leads to $\tilde{O}(\sqrt{KT})$. We hope this clarifies your question. We sincerely hope that our explanation has clarified your concerns. In light of this clarification, we respectfully request that you reconsider your evaluation of our work.

Thank you again for your time and consideration.

Thank you for your question. To better address your question, could you please clarify what you mean by "just assign standard basis to the arms" and "select $d$ out of $K$ arms"? A more specific explanation of your question would help us provide a precise and relevant response.

1. Unfortunately, Abbasi-Yadkori (2009) does not require a fixed set of feature vectors. The set of feature vectors is arbitrary over time. If I understand correctly, you require the set of features to be the same over time. I don't think this is common. Some of the paper you listed do not even satisfy this requirement.
2. If I pull $x_{a*}$ and $x_{a'}$. the outcome $y$'s are different, why cannot I identify that these two arms are different and have different unobservable features?
3. Please add the explanations to the papers in more detail.

1. Fixed contexts assumptions are common in the parametric bandit literature: The parametric bandit literature includes several studies where the reward is modeled as a function of each action and an unknown parameter, with the action set fixed throughout the learning horizon—an approach that aligns with the problem setting of our paper. For instance, Abbasi-Yadkori (2009) investigates a linear bandit algorithm that employs forced sampling, achieving a regret bound of $O(d\sqrt{T})$ under a fixed set of observable features. Similarly, Filippi et al. (2010) analyze a stochastic bandit problem with a generalized linear model (GLM) reward structure, also considering fixed observable features. Additionally, this assumption has been applied to address practical problems, including model selection (Zhu & Nowak, 2022), asymptotic analysis (Lattimore & Szepesvari, 2017), and the development of experimental design-based algorithms (Wakenmaker et al., 2021), fairness-focused bandit algorithms (Chen et al., 2020), and bandit algorithms under safety constraints (Amani et al., 2019). These examples illustrate that the assumption imposed in our paper is widely adopted and holds significant relevance in practical applications.

Slightly modified analysis for time-variant contexts: Under the assumption that $\tilde{\sigma}\_{\min} := \min\_{t \in [T]} \lambda\_{\min} \left( \sum_{a \in [K]} \mathbf{x}\_{a,t} \mathbf{x}\_{a,t}^\top \right) > 0$ for deterministic contexts, or $\tilde{\sigma}\_{\min} := \min\_{t \in [T]} \lambda\_{\min} \left( \mathbb{E} \left[ \sum\_{a \in [K]} \mathbf{x}\_{a,t} \mathbf{x}\_{a,t}^\top \right] \right) > 0$ for stochastic contexts, repeatedly applying feature vector augmentation to $\mathbf{X}\_t := (\mathbf{x}\_{1,t}, \ldots, \mathbf{x}\_{K,t})$ for time-variant features $\mathbf{x}\_{a,t}$ produces the same theoretical results. While this setting accommodates general cases in bandit problems, for simplicity, we will address this in the Appendix. Note that the unobserved features $\mathbf{u}\_a$ must remain fixed over time; otherwise, the problem becomes so challenging that achieving sublinear regret with any algorithm is infeasible.

2. On the lower bound: Your comment "a linear regression will be able to distinguish these two actions" is incorrect. For any linear regression estimator $\widehat{\theta}$ for $\theta_{\star}$, the reward estimate for the two actions, $\mathbf{x}\_{a_\star}^\top \widehat{\theta}$ and $\mathbf{x}\_{a^\prime}^\top \widehat{\theta}$, are indistinguishable when $\mathbf{x}\_{a_\star}=\mathbf{x}\_{a^\prime}$, although the observed rewards, $y_{a_\star}$ and $y_{a^\prime}$, are distinguishable (note that we cannot use $\mathbf{z}\_{a_\star}^\top \widehat{\theta}$ and $\mathbf{z}\_{a^\prime}^\top \widehat{\theta}$ because of partial observability). Since our lower bound (Theorem 1) applies only to algorithms that use observed contexts (excluding multi-armed bandit algorithms that ignore the contexts), the algorithms cannot distinguish the two actions and suffer regret linear in the time horizon $T$.

3. How coupling eases the adaption of DR: Coupling replaces the $\epsilon_t$-greedy policy with a multinomial distribution $\phi_{1,t}, \ldots, \phi_{K,t}$. When we use DR estimation with the $\epsilon_t$-greedy policy, the inverse probability $\epsilon_t^{-1} := \sqrt{t}$ appears in the pseudo-reward (10), causing the variance of the pseudo-reward to explode. Therefore, we couple the $\epsilon_t$-greedy policy with the multinomial distribution (9) to bound the inverse probability weight $\phi_{a,t}^{-1} = O(K)$. We have included this in the revised manuscript.

4. On comparison with DR Lasso Bandit: We have already included the DR Lasso Bandit (Kim & Paik, 2019) in our comparison experiments, as clearly presented in Figures 2, 3, and 4 of the original manuscript.

References for first question

• Yasin Abbasi-Yadkori. Forced-exploration based algorithms for playing in stochastic linear bandits. 2009.
• Sanae Amani et al., Linear stochastic bandits under safety constraints. 2019.
• Yifang Chen et al., Fair contextual multi-armed bandits: Theory and experiments. 2020.
• Sarah Filippi et al., Parametric bandits: The generalized linear case. 2010.
• Tor Lattimore and Csaba Szepesvari. The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits. 2017.
• Andrew Wagenmaker et al., Experimental design for regret minimization in linear bandits. 2021.
• Yinglun Zhu and Robert Nowak. Pareto optimal model selection in linear bandits. 2022.

Response for the second comment

Note that the observed $y\_a = \langle \mathbf{z}\_{a}, \theta\_{\star} \rangle + \eta\_a$ includes the measurement error. Thus, although the observed $y$ is different, we do not know whether they have different expected values or not. With a sufficient number of reward samples, some MAB algorithms that do not depend on the features may distinguish $a_{\star}$ and $a^\prime$, but our lower bound does not consider those algorithms. We show that $a_{\star}$ and $a^{\prime}$ are indistinguishable for the algorithms whose policies operate on the observed features $\tilde{\mathbf{x}}\_a$ only. The lower bound is not about all algorithms. One example is the LinUCB (Li et al., 2010) algorithm using $\tilde{\mathbf{x}}\_a$, which clearly does not distinguish the two arms that have the same feature vectors even though the observed rewards are different.

For example, consider a specific case following the setting in Theorem 1. Let the dimension of observed features, $d$, be 3, and the total horizon, $T$, be 9. Following this setup, the observed features of each arm are calculated as follows: $\mathbf{x}\_{a\_\star} = [-1, -1, -1]^\top, \quad \mathbf{x}\_{a'} = [-1, -1, -1]^\top, \quad \text{and} \quad \mathbf{x}\_{a\_o} = [1, 1, 1]^\top$.

Based on the theorem, the expected reward for each arm, incorporating unobserved features, is given by $[1/3, -1, -1/3]^\top$. Now, consider, for example, the decision rule of LinUCB using ridge regression with a regularization parameter $\lambda = 1$. Using ridge regression, we obtain $\hat{\theta} = [1/30, 1/30, 1/30]^\top$, which results in: $\mathbf{x}\_{a\_\star}^\top \hat{\theta} = \mathbf{x}\_{a'}^\top \hat{\theta} = -1/10$.

For the uncertainty term, since the observed feature vectors for both $a\_\star$ and $a'$ are identical, their norms (even when weighted by the Gram matrix) are also identical. Consequently, linear bandit algorithms that rely solely on observable features are unable to distinguish between $a\_\star$ and $a'$.

Response for the third comment

We have already included the explanations of how coupling eases the adaption of DR in Section 4.2 (Page 7). We are more than happy to improve our manuscript.

Response for the first comment

Thank you for your comment.
At face value, the problem setup in Abbasi-Yadkori (2009) considers a fixed arm set. However, we acknowledge that their framework may also allow for time-varying features, as the reviewer has pointed out. While we of course recognize that allowing the feature set to vary over time is standard (that is not an issue at all) in conventional linear contextual bandit problems, we sincerely hope that the reviewer and we can agree on the following common grounds:

(1) Fixed arm sets are NOT uncommon in variants of linear bandit problems: in fact, natural with partial observability.

In many variants of linear bandit problems, assuming a fixed arm set is rather common (not uncommon), particularly in linear bandit settings with misspecification (which can be formulated as linear bandits with partially observable features). For instance:

• Ghosh et al. (2017) and Lattimore et al. (2020) assume fixed contexts over time in their analysis of linear bandits with misspecification.
• Other works, such as Park & Faradonbeh (2024) and Kim et al. (2023), consider stochastic contexts (e.g., Gaussian-distributed features), which are time-varying but impose additional assumptions on the latent features. Specifically:
  • Park & Faradonbeh (2024) assumes latent features have a mean of zero.
  • Kim et al. (2023) assumes that observed features are linear transformations of latent features via a full-rank matrix (in expectation). To the best of our knowledge, no existing work tackles linear bandits with misspecification or partially observable features under a setting where the feature vector varies arbitrarily over time without additional assumptions on the latent features. In our work, we assume fixed features but make no structural assumptions between observed and latent features, which justifies the fixed arm set setting.

(2) A fixed arm set is not necessarily easier (in general).

Even for the standard linear contextual bandit (note our problem is with partial observability: see Part (3) below), allowing a time-varying arm set does NOT inherently make the problem more challenging. On the contrary, assuming non-fixed, stochastic contexts (e.g., multivariate Gaussian features) can rather simplify and ease the problem, as shown in prior work:

• Kannan et al. (2018) and Bastani et al. (2021) demonstrate that stochastic contexts enable sharper regret bounds, with greedy policies achieving sub-linear regret performance.

In fact, these non-fixed stochastic contexts are often considered strong assumptions because they simplify the problem significantly. Thus, we respectfully object to the reviewer’s assertion that fixed features represent a “very strong” assumption.
If anything, there is no inherent "strong-ness" in assuming fixed features, as it neither simplifies the problem nor leads to better results. If the reviewer remains unconvinced, we encourage them to assume fixed contexts in the problem of Abbasi-Yadkori et al. (2011) (or any typical linear bandit analysis), work out the analysis, and examine the outcomes. Does it yield a sharper regret bound? Does it simplify the analysis? The answer is unequivocally, NO. Hence, a fixed feature set is not a strong assumption by any theoretical standard.

(3) Whether features are fixed or varying should not be grounds for rejection.

Most importantly, the choice between fixed and varying features alone is not a matter of strong-ness but a matter of problem suitability. Our problem setting involves unobservable portions of each feature vector. If these latent features were to change arbitrarily over time, the problem itself would become non-learnable, making the problem ill-posed. Hence, given this, assuming fixed features is natural and justified.

In fact, our problem setting with a fixed arm set and partial observability is much harder than the typical linear bandit settings with full observability, whether the features are fixed or even time-varying.
The presence of unobservable features introduces significant complexity. This is not a matter of opinion but rather a straightforward fact, and we sincerely hope that we can agree on this simple premise.

We firmly believe that our contributions under this challenging setting warrant recognition rather than rejection based solely on this assumption.

For time-varying observed features, we have included an algorithm in Appendix B that achieves $\tilde{O}(\sqrt{(d+K)T})$ regret bound.

References

• Ghosh et al. (2017), "Misspecified Linear Bandits"
• Kannan et al. (2018), A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
• Bastani et al. (2021), Mostly Exploration-Free Algorithms for Contextual Bandits
• Kim et al. (2023), "Contextual Linear Bandits Under Noisy Features: Towards bayesian oracles"
• Park & Faradonbeh (2024), "Thompson sampling in partially observable contextual bandits"

Dear Reviewer,

Upon reviewing the comments in the weaknesses that the reviewer had originally mentioned (along with the follow-up comments), we strongly believe that all the points have been addressed and clarified as follows:

1. On fixed features: Please refer to the detailed discussion in the section above (titled "Response for the first comment"). To summarize, our results are as follows:

We respectfully highlight that the revised version includes results for varying observable features (Appendix B). Penalizing our work for not addressing an unlearnable problem setting (e.g., varying observable and varying unobservable features) would be unwarranted. We sincerely hope the reviewer acknowledges that this issue has been fully resolved.

2. Lower bound: Regarding the lower bound, we confirm its correctness. If there are still any parts that remain unclear, please do not hesitate to let us know, and we will do our best to provide additional clarification within the remaining discussion period.

3. We have included further explanations on how coupling simplifies the adaptation of DR, as requested (page 7: Section 4.2).

4. The comparison with the DR Lasso Bandit was already included in the original submission (pages 9-10: Figure 2,3,4).

Given these clarifications, we sincerely believe that all points have been adequately addressed and are no longer issues—some were not issues even from the beginning. If our responses have sufficiently resolved your concerns, we kindly and respectfully request that you reconsider your assessment, reflecting the value and contributions of our work.

Thank you again for your time and consideration.

We are grateful for your invaluable feedback and acknowledgment of our contributions. We are more than happy to address each of your comments and questions.

Questions

1. About the burn-in period: Although the $K$-dependent burn-in period is necessary in our analysis, it remains unclear whether the same order of burn-in is required for the problem itself -- our results show the sufficiency of such a burn-in period. The dependency on $K^3$ in the burn-in period arises from three components: identifying the best arm, determining the nonzero entries in the augmented parameter $\mu\_{\star} \in \mathbb{R}^K$, and accounting for the importance weight from $\phi\_{k,t}$ as defined in equation (7). These components multiply to form the overall $K^3$ dependency. Please note that if an upper bound $D$ for $d + d_h$ is known and $D \ll K$, it may be possible to replace the second $K$ with $D$. For bandits with partially observable features, we believe it is hard to reduce dependency on $K$ in the burn-in period. Nonetheless, we would like to emphasize that the burn-in period grows only by $\log T$, making it a non-leading term in the overall analysis.

2. Contextualization of Theorem 2: We included the following after Theorem 2: "The consistency is proved by bounding the two components of the error in the pseudo-rewards defined in Eq. (11): (i) the noise of the reward and (ii) the error of the imputation estimator ${\check{\mu}}\_{t}$. Since (i) is sub-Gaussian, it can be bounded using martingale inequalities. For (ii), the imputation error $\tilde{x}\_a^\top (\check{\mu}^{L}\_{t} - \mu\_{\star})$ is multiplied by the mean-zero random variable $(1-\frac{\mathbb{I}(\tilde{a}\_t=a)}{\phi\_{a,t}})$ and thus it can be bounded by $\Vert \check{\mu}^L\_t - \mu\_{\star}\Vert\_1 / \sqrt{t}$."

3. On the forced uniform exploration: Forced "uniform" exploration is not strictly essential. As long as a sufficient number of samples are collected from the $K$ arms, it is acceptable for some arms to be sampled more frequently than others. Due to the partially observable nature of the problem, sufficient forced sampling remains necessary; however, it could be adapted to some extent. While uniform sampling is a standard approach, there may exist more effective adaptive sampling methods for exploration.

4. Various regret bounds over different features: When $\mathrm{R}(\mathbf{U}) = \mathbb{R}^K$, the regret could potentially be as bad as $O(\sqrt{KT})$. However, this is not always the case, such as in scenarios where $\mathrm{R}(\mathbf{U}) \subset \mathrm{R}(\mathbf{X})$, the relationship between the observable and unobservable parts can mitigate this issue. Specifically, if there is a linear correlation between the observable and unobservable features (as in \cite{park2022regret}), the unobservable dimensions may be inferred more effectively, achieving a $\tilde{O}(\sqrt{dT})$ regret bound.

5. On the sparsity of $d_h$: When $d_h \ll d_u$, the unobservable component is largely linear with respect to the observable component. Consequently, only $d_h$ basis vectors are needed to estimate the reward, rather than estimating all $d_u$ unobservable parameters. This leads to a regret bound of $\tilde{O}(\sqrt{(d + d_h)T})$, which is significantly better than $\tilde{O}(\sqrt{(d + d_u)T})$.

Suggestions

1. On adding a table for the range of regret: Thanks for your invaluable suggestion, and we have added a table for cases when $d_h = 0$ (linear bandit case) and $d_h = K-d$ (MAB case).

2. On examples for extrapolation between MAB and linear bandits: The DR approach uses every $K$ context vector, yielding a better gram matrix by replacing $\mathbf{x}\_{a_t}\mathbf{x}\_{a_t}^\top$ with $\sum\_{a \in [K]} \mathbf{x}\_{a}\mathbf{x}\_{a}^\top$.
   This improvement reduces the number of forced exploration rounds needed to satisfy the restrictive minimum eigenvalue condition, which is crucial for the convergence of the Lasso estimator.