We are thankful for your careful review and for acknowledging the impact of our contributions. We will address the following questions one by one, and we believe that the answers will collectively provide a comprehensive response.

• On Use of Compatibility Condition
  • It is well known that the full rank matrix implies the compatibility condition. Without loss of generality, we assume that the observed features are full rank (lines 187-188, left column) and the augmented vectors are orthogonal each other and to the observed feature space. Please refer to Lemma 4 for the detailed proof starting from line 1486 in the last page of appendix. Because the Gram matrix of the augmented features has positive minimum eigenvalue, it satisfies the compatibility condition for the convergence of the lasso estimator.
• Ensurability of Full Rank Gram Matrix under Our Exploration Strategies
  • Our exploration method ensures full rank in two ways: (i) by randomly sampling a $K$ augmented feature vector for predetermined number of round $\mathcal{E}\_t$, and (ii) by performing resampling and coupling based on the multinomial distribution defined in (9). These two strategies explore over all $K$ arms efficiently. Additionally, as we have indicated in the footnote 3 in the manuscript (lines 217-219, left column), even though the observed feature Gram matrix is not full rank, we can apply singular value decomposition on the observed features to reduce the feature dimension to $\bar{d} \le K$ with $R(X)=\bar{d}$.
• Selection of Orthonormal Basis
  • Theoretically, our regret bound holds for any choice of basis in $R(X)^\perp$. In practice, we perform singular value decomposition (SVD) of the observed feature matrix $X = \sum\_{i=1}^{r}\sigma\_i u\_i v\_i^\top$ and select the right singular vectors corresponding to zero singular values, i.e., ${v\_i\in\mathbb{R}^K:\sigma\_i=0}$, as $b\_1,\ldots,b\_{K-d}$ in our experiments. Then $b\_1,\ldots,b\_{K-d}$ form an orthonormal basis that is orthogonal to the row space of $X$.
• Other Corrections
  • Regret definition in Eq. (2)
    • Thank you for pointing this out. We will revise the notation in the revision.
  • At the end of page 6 you wrote "To the best of our knowledge,Theorem 3 is the first regret bound sublinear in $T$ for the latent features without any structural assumption." Technically this is not correct since the regular UCB algorithm for stochastic bandits would also achieve a sublinear bound.
    • We appreciate your clarification. We intended to state that our result is the first of its kind in linear parametric bandit problems. If by "regular UCB algorithms" you are referring to the algorithms for non-feature-based multi-armed bandit (MAB) settings, we agree that the original sentence may be misleading. We will revise it for clarity as follows: "To the best of our knowledge, Theorem 3 presents the first regret bound faster $\tilde{O}(\sqrt{KT})$, particularly for algorithms that account for unobserved features, without relying on any structural assumptions."
  • In lines 228 to 231 you wrote that for the compatibility condition to hold the minimum eigenvalue has to positive, which does not have to be true in general. In some instances the compatibility condition is a more relaxed condition than having a positive minimum eigenvalue.
    • Thank you for pointing this out. We agree with your observation and will revise the sentence, for accuracy, as follows: "For the estimator in Eq. (8) to correctly identify the zero entries in $\mu\_{\star}$, the compatibility condition must hold (van de Geer & Bühlmann, 2009). While the compatibility condition does not necessarily require a positive minimum eigenvalue in general, in our setting, in our setting, the Gram matrix $\lambda\_{\min}\left(t^{-1}\sum\_{s=1}^{t}\tilde{x}\_{a\_s}\tilde{x}\_{a\_s}^\top\right)$ has a positive minimum eigenvalue. Thus, the compatibility condition is implied without any additional assumption."

In this work, we study linear bandits with partially observable features, where rewards depend on both observed and unobserved features, a common situation in real-world applications. Our problem setting is more general than prior works, and it remains underexplored. We directly tackle challenges arising from unobserved features. Specifically, we propose a novel algorithm equipped with a new estimation technique, and a novel analytical framework distinct from existing approaches. Our method achieves regret not only sublinear but also converges faster than those reported in previous studies, which also shows superior empirical performance in numerical experiments. We believe these contributions are significant.

Reference: van de Geer, S. A. and Bühlmann, P. (2009), On the conditions used to prove oracle results for the lasso.

We appreciate your feedback on page usage. We will make full use of the page limit and avoid leaving unused space in the revision.

• On Explanation and Mislocation of Table 1
  • We appreciate you for giving us an opportunity to clarify Table 1. We will relocate the table to a more suitable position (e.g., below Section 3, line 159, right column) and add clarifying explanation.
  • Table 1 summarizes how the regret bound of our algorithm varies with the relationship between the row space of observed features (span(observed), i.e., $R(X)$) and that of unobserved features (span(latent), i.e., $R(U)$).
  • Specifically, if span(latent) is fully included in span(observed), the quantity $d\_h$ becomes 0 since the unobserved reward component can be expressed by the observed features. For the opposite case, $d\_h=K-d$. A detailed discussion can be found from line 206 (left column) to line 177 (right column).
  • We also provide the experimental results for Case 1 and 2 in Table 1: (i) $R(U)\subseteq R(X)$ and (ii) $R(U)\supseteq R(X)$, respectively. For (i), we sample $X\in\mathbb{R}^{d\times K}$ from $N(0\_d,I\_d)$ and a coefficient matrix $C\in\mathbb{R}^{d\_u\times d}$ from $\text{Unif}(-1/\pi,1/\pi)$, and compute $U$ as $CX$, where $d\_u=d\_z-d$ (line 91, right column). In case (ii), we sample $U\sim N(0\_{d\_u},I\_{d\_u})$, then construct $X$ via multiplication with a coefficient matrix, as in (i). The full feature matrix $Z$ is formed by concatenating $X$ and $U$.
  • The experiments are conducted with the following setups: (i) $d\_z=30,d=15$, and $K$, the number of arms, varies by 20, 30, and 40; (ii) $d\_z=40,d=10$, with $K=10,30,50$; (iii) $d\_z=20,d=10$, with $K = 15, 25, 35$. Results are available at: https://tinyurl.com/RoLFFigs1
• On Notation of $z\_{\star}$ and $z\_t$
  • We appreciate the opportunity to clarify the definition of the given notation. In Eq. (2), $z\_\star$ denotes the true feature vector associated with the optimal action $a\_\star$, as defined in lines 139–140 on the left column, and $z\_t$ denotes the true feature vector corresponding to the action selected in round $t$, i.e., $a\_t$. As defined in Eq. (1) (line), both vectors consist of a combination of observed and unobserved components. We will include this clarification in the revision.
• Clarification of Theoretical Results
  • We appreciate the opportunity to clarify the results regarding $d\_h$.
  • Before providing clarification, we would like to emphasize that the first scenario in Table 1 does not imply that the unobserved features are unimportant; rather, as you have correctly pointed out, it indicates that they can be linearly expressed by the observed features.
  • The formal definition of $d\_h$ is provided in (6) (line 216, the left column). To clarify, $d_h$ is not the dimension of unknown features; $d\_h$ is the number of required basis vectors to express the unknown portion of reward, $(I\_K-P\_X)U^\top \theta\_{\star}^{(u)}$.
  • Even if the dimension of the unobservable features, $d\_u$, increases, the problem does not become more difficult -- as long as the unobserved component of the reward can still be expressed using only $d\_h$ basis vectors. However, if the increment of the unobservable feature increases $d\_h$, then the problem becomes harder as it requires additional parameter to express the unknown portion of reward. Thus, $d\_h$ characterizes the intrinsic difficulty of the problem, which supports our $O(\sqrt{(d + d\_h)T})$ regret bound. We will include the details in the manuscript.
• Clarification of Experimental Results on Curve Flattening
  • We appreciate your careful observation. While the cumulative regret curve of our algorithm may appear to flatten suddenly, it is not completely flat -- this impression comes from the steep growth of the regret curves of baseline algorithms. In fact, it continues to grow slowly over time. The apparent flattening is due to the forced exploration phase (lines 5-6 in Algorithm 1), which ensures sufficient coverage of the action space early on. After this phase, resampling and coupling strategies both enhance the efficiency of the doubly robust (DR) estimation, resulting in slower regret growth. A shorter exploration phase would yield a more gradual and adaptive flattening.

We would like to emphasize the significance of the problem: linear bandits with partially observable features, where rewards depend on both observable and unobservable features -- common in practice, yet underexplored. Our work addresses core challenges with a new algorithm for partial observability, equipped with a novel estimation strategy. Our method achieves sublinear regret bounds with faster convergence rate than prior work, and shows superior empirical performance. We believe these contributions are substantial and hope they are recognized.

We are grateful for your valuable feedback and acknowledgment of our contributions. We are happy to address each of your comments.

• On Descriptions of Notation and Methods

  • Thank you for the opportunity to clarify this point. Definitions of $p$ and $\delta$ are given after Eq. (9) (lines 263-270, left column) and Algorithm 1 (lines 276-277, right column), respectively. We will add explanations immediately after Eq. (8) in the revision. As described in Algorithm 1, both quantities are hyperparameters: (i) $p$ is the coupling probability used to define the multinomial distribution for pseudo-action sampling; (ii) $\delta$ is the algorithm's confidence parameter.
  • Our exploration method uses coupling of an action $a\_t$ from $\epsilon\_t$-greedy policy with a counterfactual action $\tilde{a}\_t$, drawn from the multinomial distribution in Eq. (9). While Xu & Zeevi (2020) also use counterfactual actions for exploration, our method differs in two points: (i) they sample counterfactuals from the previous policy, whereas ours conditions on $a\_t$; (ii) we explicitly resample $\tilde{a}\_t$ for coupling. A minimum of $C\_e\log (2Kt^2/\delta)$ exploration rounds ensures the imputation estimator $\check{\mu}^L$ is accurate enough for use in the main estimator $\widehat{\mu}^L$. Fewer rounds may cause error accumulation in $\widehat{\mu}^L$.

• On Experimental Setups and Comparison with Baselines

  • Our experimental setting is the "otherwise" case in Table 1, where neither $R(X)$ nor $R(U)$ fully contains the other.
  • We also examine cases (i) $R(U)\subseteq R(X)$ and (ii) $R(U) \supseteq R(X)$. For (i), we sample $X\in\mathbb{R}^{d\times K}$ from $N(0\_d,I\_d)$ and a coefficient matrix $C\in\mathbb{R}^{d\_u\times d}$ from $\text{Unif}(-1/\pi,1/\pi)$, and computed $U$ as $CX$, where $d\_u=d\_z-d$ (see line 91, right column). In case (ii), we first sample $U\sim N(0\_{d\_u},I\_{d\_u})$, then construct $X$ analogously as in case (i). $Z$ is formed by concatenating $X$ and $U$.
  • Additional experiments are conducted for both cases, with the following setups: (i) $d\_z=30,d=15$, and $K$, the number of arms, varies by 20, 30, and 40; (ii) $d\_z=40,d=10$, with $K = 10, 30, 50$; (iii) $d\_z=20,d=10$, with $K=15,25,35$. Results are available at: https://tinyurl.com/RoLFFigs1
  • For the case with no unobserved features, results are already included in the manuscript (lines 416–426, left column; Fig. 4), where $d\_z = d$, thus removing latent potions from rewards. As shown in the figure, our algorithm still outperforms the baselines with no overfitting observed.

• On Regression Equations

  • As noted in the manuscript(line 123, left column), the true mean reward is $x\_a^\top \theta^{(o)}\_\star+u\_a^\top\theta^{(u)}\_\star$, where $x\_a$ is observed and $u\_a$ is latent. Baseline methods (e.g., OFUL, LinTS, DRLasso) only use $x\_a$, modeling the regression as $f\_{base}(x\_a) = x\_a^\top \theta^{(o)}\_\star$. However, ours augments $x\_a$ with $b\_1,\ldots,b\_{K−d}$ to model as $f_{ours}(x\_a, b\_1,\ldots,b\_{K-d})=[x\_a\;e\_a^\top b\_1\cdots e\_a^\top b\_{K-d}] \mu\_\star,$ which recovers the true mean reward as argued in Eq. (4) (lines 194–200, left column) and Eq. (7) (lines 184–187, right column).

• On Unbiasedness of Estimators

  • The pseudo-reward (Eq. (10) in lines 237-240, right column) is unbiased as it involves no regularization. In contrast, the main estimator is biased due to the inclusion of lasso/ridge regularization.

• Comprehensive Literature Review

  • Comparisons with Linear Bandits: Due to space limitations, we deferred the comparison with linear bandits to appendix, but we are more than happy to move it to the main text in the revision. Regarding linear bandits with fixed features, we have also discussed comparisons with linear bandits under model misspecification (lines 96-108, right column) as well as in Appendix A.
  • Tennenholtz, Guy, et al. (2021): We appreciate your pointer to this related work. Upon inspection, while their setting appears similar to ours -- the true features and rewards contain both observed and unobserved components -- their work differs from ours in two points. First, they assume access to offline partially observed dataset to reduce the dimensionality of the problem, whereas partial observability arises naturally in ours, with no offline access. Second, they leverage the correlation between observed and unobserved features, which requires estimation; ours is agnostic to such correlation. Moreover, we exploit the observed features via feature augmentation and doubly robust estimation, resulting in faster regret convergence than their UCB-based approach. We will include this comparison in the revision.

Reference: Xu, Y. and Zeevi (2020), A. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits.