Linear Bandits with Partially Observable Features

Authors: Wonyoung Kim, Sungwoo PARK, Garud Iyengar, assaf zeevi, Min-hwan Oh
Primary area: reinforcement learning
Keywords: Linear Bandits, Partially Observable Features, Doubly Robust

Abstract:
We introduce a novel linear bandit problem where a subset of features is latent, resulting in partial access to reward information and spurious estimates.
Without properly addressing the latent features, the regret grows linearly over the decision epoch $T$ while improving the regret bound is challenging because their dimension and relationship with rewards are not available.
We propose a novel analysis to handle the latent features and an algorithm that achieves a regret bound sublinear in $T$.
The core of the algorithm lies in (i) augmenting basis vectors orthogonal to the observable feature space, and (ii) developing an efficient doubly robust estimator that further improves the regret bound.
With these two ingredients, our algorithm achieves a regret bound of $\tilde{O}(\sqrt{(d + d\_h)T})$, where $d$ is the dimension of observable features, and $d_h$ is the _unknown_ dimension of the unobserved features that affects the reward. 
Crucially, our algorithm does not rely on prior knowledge of the unobserved feature space, which expands as more features become hidden.
Numerical experiments confirm that our algorithm outperforms both non-contextual multi-armed bandits and other linear bandit algorithms.

Decision: reject
Reviewer scores: 8, 3, 6, 3

Reviews and discussion:
<thread>
creation date:
1730322362354

thread_type:
official_review

<thread_object>
creator: reviewer_shzc

<content>
summary:
The paper studied linear bandits where the feature vectors of the actions are partially observable, specifically in the setting where there are no additional assumptions about the unobserved features. The authors observed that the reward of all actions lies in a subspace of $d$ dimensions, allowing for an assignment of the hidden vectors such that the corresponding unknown parameter $\mu_*$ is $d$-sparse. Based on this insight, the authors proposed a bandit algorithm that employs the Lasso estimator to leverage this sparsity. They showed that their algorithm achieves a regret bound of order $\sqrt{\tilde \sigma_{\min}^{-1} T d \log K}$, where $\tilde \sigma_{\min}$ denotes the minimum eigenvalue of the Gram matrix of the assigned feature vectors. Experiments are included to demonstrate the practical performance of the algorithm.

strengths:
I think linear bandits with partially observed features is an interesting topic to study.

weaknesses:
I feel there are critical theoretical flaws in the paper.

1. Even if $(I_K - P_X)U^{\top} \theta_*^{(u)}$ lies in a subspace of dimension $d$, it does not imply that $\mu_*^{(u)}$ is $d$-sparse. The sparsity only holds when the basis vectors $b_i$ align with the row space of the matrix. It seems to me that $b_i$ is arbitrarily chosen, so I do not think this claim generally holds.

2. The regret bound of the algorithm has a polynomial dependence on $\tilde \sigma_{\min}^{-1}$. However, since $\tilde \sigma_{\min}^{-1}$ is the minimum eigenvalue of the Gram matrix of a $K \times d$ matrix, it might still scale as $K$. Although the authors claim that the minimum eigenvalue is not always $O(1/K)$ because they assume $\|\tilde x_a\|_\infty \leq 1$ instead of $\|\tilde x_a\|_2 \leq 1$, I still cannot see the correspondence.

3. In Theorem 2, it is stated that $\mathcal{E}_t \subseteq [t]$, and it is also assumed that $|\mathcal{E}_t| \geq t$. I do not see how both conditions can hold unless $\mathcal{E}_t = [t]$.

questions:
Please refer to the Weaknesses section above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730644006329

thread_type:
official_review

<thread_object>
creator: reviewer_ezt5

<content>
summary:
The paper studies a novel linear contextual bandits problem, which differs from the standard finite-arm linear contextual bandits problem in the following way. 
1. There are $K$ arms in total and the contextual vector of each arm is fixed through horizon $T$.
2. Among all dimensions $d$, there are a few of them are not observed by the player.
3. The contextual vector has bounded $\ell_\infty$-norm and the parameter $\theta^\star$ has bounded $\ell_1$-norm.

The paper presented an algorithm for the problem, gave matching lower and upper bounds up to logarithmic factors, and demonstrated the effectiveness of the paper in numerical experiments.

strengths:
1. The paper gave a rather complete study on the proposed problem. As mentioned before, the paper included algorithm designs, proofs to the lower and upper bounds, and numerical experiments.
2. The lower and upper bounds are matching up to log factor.

weaknesses:
1. The paper made a rather strong assumption that $(\mu,\theta)$ are bounded in $(\ell_\infty, \ell_1)$ which is different from the standard $(\ell_2, \ell_2)$ setup. This limits the comparison of this work over previous ones.

questions:
1. Line 1325: "Cauchy-Schwartz" should be "Cauchy-Schwarz".
3. Is the observed part of the feature space really used? What would happen if we just pretend all features are not observable and apply the algorithm, i.e. replace $d,d_h$ by $d'=0$ and $d'_h=d+d_h$? It confused me a lot that the regret bound only depends on $d+d_h$.
2. I suggest the authors make more explicit about the regret bound's dependency on $\widetilde \sigma_{\min}^{-1}$ to avoid confusion.
3. At Line 475-480, I don't see why $\widetilde \sigma_{\min}$ is constant.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730704158507

thread_type:
official_review

<thread_object>
creator: reviewer_rtzc

<content>
summary:
This paper consider a bandit setting with a fixed set of arms and with unobservable features. The authors propose to augment the feature space with basis vectors and propose algorithms to provide sublinear regret guarantee.

strengths:
Designing algorithms to tackles unobservable confounding factors is important for bandit problems.

weaknesses:
1. Assumption 1 requires features of all arms to be fixed over time, which is not common and very strong. I don't think this assumption matches practices. Besides, I didn't see how this can be "slightly modified" into a time-varying feature setting as claimed by the authors. If it's simple, please use the time-varying feature setting as the main setting, which is common in the bandit literature. 
2. The lower bound analysis doesn't seem right to me. The last step relies on the argument that the agent cannot identify $x_{a_*}$ from $x_{a'}$. However, the observed outcome $y$ for these two arms $a_*$ and $a'$ will be different since $\langle z_{a_*}, \theta_*\rangle \ne $\langle z_{a'}, \theta_*\rangle$, even though $x_{a_*}=x_{a'}$. Therefore, a linear regression will be able to distinguish these two actions. Intuitively, even if there are unobservable features, linear regression will still be able to tell one action from others since the unobservable values will be projected into the observable feature space. Thus, it's hard to believe the lower bound will scale as T. 
3. The coupling steps require more explanations and intuition as well. The authors only argue adaptation of the existing DR method is challenging but didn't explain the intuition. Why coupling can help with the analysis when arms are fixed?
4. The comparison in the experiments does not seem fair. The benchmarks in the experiments are not of the same type of bandit algorithm with the proposed ones. I would suggest the authors at least add DR Lasso Bandit (Kim & Paik, 2019).

questions:
See my comments above.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731261712486

thread_type:
official_review

<thread_object>
creator: reviewer_44d2

<content>
summary:
The authors consider a regret minimizing linear bandits with K arms. Unlike the standard linear bandit setting, they assume that each arm has a set of unseen or latent features which affect the reward. As a result, standard linear bandit algorithms (eg OFUL) can’t be applied. The authors address this issue by projecting the problem to an appropriate space where an orthogonal complement to the span of the arms is augmented, and then performing an epsilon greedy style approach in this space. Critical to the solution is the use of Doubly robust estimation procedures. They show strong empirical results.

strengths:
Overall I rather enjoyed this paper and thought the approach of the authors was clever. Intuitively, in an extreme case, if you do not observe any features, you can’t hope for better than O(\sqrt(KT)) regret coming from standard MAB results. However, by projecting the feature vectors appropriately, the authors can exploit linear dependencies between the unseen components and seen components to do better. 

What’s perhaps most impressive is Theorem 2, which provides an estimator that can effectively bound the estimation error using a doubly robust estimator.

weaknesses:
I think there are some technical weaknesses and gaps:
a) It seems unfortunate that Theorem 2 has a burn in period that depends on K. Can the authors argue that this is necessary? (It seems so?)
b) I think some contextualization of Theorem 2 would be helpful - for example, which components of the error come from the bias of using 10 to estimate rewards? c) Forced uniform exploration seems critical to your method - do you think you could have avoided it?
D) It feels like the regret could be as bad as O(sqrt(KT)) - for example, if the seen features all have the same inner product with theta_s, and the unseen dimension encodes a basis. Can you clarify those cases?

Comments on Structure:
Overall I thought the paper was well written, but there were some gaps in exposition that would have helped. Here’s some concrete suggestions
a) Perhaps add a table contextualizing the regret in different ranges. Eg, how big can d_h get?
b) I think some concrete examples explaining your extrapolation between MAB and the linear bandit and how DR estimation helps this can help.

Finally I thought the discussion on sparsity was interesting…but I failed to understand it. d_h could be much smaller than d_u, but this does not imply sparsity?

questions:
see above
</content>
</thread_object>

</thread>
<thread>
creation date:
1739250369347

thread_type:
public_comment

<thread_object>
creator: ~sungwoo_park5

<content>
title:
Notification of Revision Update

comment:
We emphasize that, despite some of the concerns raised, the essence of our lower bound statement and the central arguments in the initial version remain valid. Despite the correctness of our results, to prevent any misunderstanding, we further significantly improved the scope and presentation of our lower bound (with new analysis). The rest of the revisions primarily clarify our assumptions, define the scope more rigorously, and incorporate additional analyses and comparisons to resolve any ambiguity.

A revised version of our manuscript has been posted on arXiv (http://arxiv.org/abs/2502.06142). We invite the reader to refer to the updated text, especially the new lower bound, newly added appendices, definitions, and tables. We appreciate the time and effort invested by the area chair and the reviewers, and **we strongly believe that the revisions address all points raised**.

We summarize the key improvements as follows:

1. On Clarity and Scope of the Lower Bound (Theorem 1)
    * Despite the correctness of the lower bound, some comments indicated that the presentation of the theorem may have been unclear to readers. We are happy to address this.
    * **Improvement**: We have provided a formal definition of a policy that depends solely on observed features (see Definition 1 in Appendix D). Additionally, we present novel analyses, showing that the regret bound grows linearly when unobserved features are ignored, in two cases: (1) for the well-known linear bandit algorithms `OFUL` and `LinTS` (see Appendix C.1) and (2) for policies that satisfy Definition 1.

2.  Explanation on Fixed Feature Assumption and Relaxation to Varying Observed Features
    * **Improvement**: We have introduced a setting and an algorithm that handle time-varying observed features (see Appendix B). Additionally, we have added a table (Table 2) summarizing learnability and our results across different cases, considering whether observed and unobserved features are fixed or varying. Furthermore, we have clarified that while the fixed feature assumption is standard in linear bandits with model misspecification, allowing unobserved features to change arbitrarily over time would make the problem fundamentally non-learnable (see Section 3.2).

3. On Sparsity and Justification of Introducing Lasso Estimator
    * **Improvement**: We have added a formal definition of the quantity $d\_h$, the number of nonzero coefficients that express the projection of the latent portion of reward, and have clarified how this quantity varies under different circumstances (see Section 4.1). To further improve clarity, we have also included a table summarizing the regret bounds of our algorithm depending on $d\_h\in[0, K-d]$ (see Table 1).

4. Other improvements
    * We have included the `DRLasso` (Kim \& Paik, 2019) in our comparison experiments (see Section 6).
    * We have clarified our explanation about how the coupling steps eases the adaptation of doubly robust estimator (see Section 4.2). 
    * We have eliminated the dependency of our algorithm's regret bound on $\tilde{\sigma}\_{\min}$, the minimum eigenvalue of the Gram matrix of augmented feature vectors (see Theorem 3 and Appendix C.3 for proof). 
    * We have corrected typos.

===========

References

* Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári (2011). Improved algorithms for linear stochastic bandits.
* Shipra Agrawal and Navin Goyal (2013). Thompson sampling for contextual bandits with linear payoffs.
* Gi-Soo Kim and Myunghee Cho Paik (2019). Doubly-robust lasso bandit.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This papers has received reviews with high variance. A point that was raised that I found particularly problematic concerns the lower bound. It took multiple interactions between a reviewer and the authors to clarify why arms cannot be identified. The problem lies, in my opinion, in the way the theorem is phrased. It gives the impression that it is a `normal' lower bound but, in fact, it holds only for some algorithms. The phrase `that are dependent on observed features' is meant to convey this. But strictly speaking it should have been `only on observed features'. It is then unclear which algorithms  are actually covered by this lower bound since it essentially does not allow you to look at the pay-off. The sentence below the theorem also gives the impression that this is typical lower bound. All of this is very misleading and is used as a motivation for what follows. I therefore believe that the paper is not ready for publication in this current form.