Linear Bandits with Partially Observable Features
Authors: Wonyoung Kim
Sungwoo PARK
Garud Iyengar
assaf zeevi
Min-hwan Oh
Venue: ICML 2025 poster (2025)
Keywords: Linear Bandits
Partially Observable Features
Doubly Robust
Primary area: theory->online_learning_and_bandits
TL;DR: This work proposes an algorithm for linear bandits with latent features, achieving sublinear regret by augmenting orthogonal basis vectors and using a doubly-robust reward estimator, without requiring prior knowledge of the unobserved feature space.

Abstract: We study the linear bandit problem that accounts for partially observable features. Without proper handling, unobserved features can lead to linear regret in the decision horizon $T$, as their influence on rewards is unknown.
To tackle this challenge, we propose a novel theoretical framework and an algorithm with sublinear regret guarantees.
The core of our algorithm consists of (i) feature augmentation, by appending basis vectors that are orthogonal to the row space of the observed features; and (ii) the introduction of a doubly robust estimator.
Our approach achieves a regret bound of $\tilde{O}(\sqrt{(d + d\_h)T})$, where $d$ is the dimension of the observed features and $d_h$ depends on the extent to which the unobserved feature space is contained in the observed one, thereby capturing the intrinsic difficulty of the problem.
Notably, our algorithm requires no prior knowledge of the unobserved feature space, which may expand as more features become hidden.
Numerical experiments confirm that our algorithm outperforms both non-contextual multi-armed bandits and linear bandit algorithms depending solely on observed features.

Linear Bandits with Partially Observable Features
Wonyoung Kim Sungwoo Park 2
Garud Iyengar
Assaf Zeevi Min-hwan Oh
Abstract
advertising without personalization-iiee when serving gen- eral users- advertisement is associated not only with observable features such as its category, format, or display time, but also with unobservable factors such as emotional appeal, creative design quality, and brand familiarity. These latent factors influence users' click-through rates, yet they are not directly quantifiable. Similarly, in clinical trials, treatment outcomes depend not only observable features like dosage and formulation, but also on unobserved fac- tors such manufacturing variability and potential side effect risks. Hence, accurately incorporating latent features is essential for providing precise recommendations.
We study the linear bandit problem that accounts for partially observable features. Without proper handling, unobserved features can lead to linear regret in the decision horizon T, their influence on rewards is unknown. To tackle this challenge, we propose a novel theoretical framework and an algorithm with sublinear regret guarantees. The core of our algorithm consists of (i) feature aug- mentation, by appending basis vectors that are orthogonal to the row space of the observed fea- tures; and (ii) the introduction of doubly robust estimator. Our approach achieves a regret bound of Ö( the observed features and d, depends on the ex- tent to which the unobserved feature space con- tained in the observed one, thereby capturing the intrinsic difficulty of the problem. Notably, our al- gorithm requires prior knowledge of the unob- served feature space, which may expand as more features become hidden. Numerical experiments confirm that our algorithm outperforms both non- contextual multi-armed bandits and linear bandit algorithms depending solely on observed features.
To address latent features, Park & Faradonbeh (2022; 2024); Kim et al. (2023a); Zeng al. (2025) typically assume that the true features follow specific distribution, such Gaussian distribution. Establishing sublinear regret bound in the decision horizon without such structural as- sumptions on the latent features remains a significant chal- lenge and has not been accomplished yet. Key challenges in the bandit problem with partially observable features arise from the complete lack of information about the latent features-indeed, the agent does not even know whether the features partially observed. We tackle these chal- lenges by proposing novel linear bandit algorithm that is agnostic to partial observability. Despite having no knowl- edge of the unobserved features, our algorithm achieves a tighter regret bound than both linear bandit algorithms that consider only observed features and multi-armed bandit (MAB) algorithms that ignore features entirely. For brevity, we will refer to linear bandit algorithms relying solely on observed features "OLB algorithms" henceforth. Specif- ically. our proposed algorithm achieves a VT -rte regret bound, without requiring any prior knowledge of the unob- served features, where is the decision horizon.
Ö(V (d + d,) where d is the dimension of
1. Introduction
We consider a linear bandit problem where the learning agent has access to only subset of the features, while the reward is determined using the complete set of features, including both observed and unobserved elements. Conven- tional linear bandit problems rely on the assumption that the rewards are linear in only observed features, without accounting for the potential presence of unobserved features. However, in many real-world applications, rewards are of- ten affected by the unobserved hennce latent- features that are not observable by the agent. For example, in online
The key idea of our proposed algorithm can be summarized in the following two procedures: (i) reconstructing feature vectors via feature augmentation capture the influence of unobserved features rewards, and (ii) introducing novel doubly robust (DR) estimator to mitigate information loss due to partial observability. For (i), we decompose the reward into two additive components: one projected onto the row space spanned by the observed features, and the other projected onto its orthogonal complement. The former term maximally captures the effect of observed features, while
'Equal contribution 'Chung-Ang University, Seoul, Korea "Seoul National University, Scoul, Korea "Columbia Univer- sity, New York, USA. Correspondence to: Min-hwan Oh <mi- noh @ acr..
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Lincar Bandits with Partially Observable Features
the latter minimizes the impact of unobserved features. We then augment observed features with orthonormal basis from the complementary space, which is orthogonal to the row space of observed features. This formulation enables us to reformulate the problem within a conventional linear bandit framework, where the reward function is defined as a dot product of the augmented features and an unknown parameter, without any additional additive term.
Our numerical experiments confirm that our algorithm
consistently outperforms OLB (Li et al., 2010; Agrawal & Goyal, 2013; Kim & Paik, 2019) and MAB (Latti- more & Szepesvári, 2020) algorithms, validating both its practicality and theoretical guarantees (Section 6).
2. Related Works
While our setting appears similar to prior works on bandit problems with (i) model misspecification and (ii) partial observability, it differs from both lines of research in several aspects, including the nature of the unobserved features and the strategies used to address the problem.
However, since these augmented features are not identical to the unobserved features, estimation errors may arise from information loss. To mitigate such errors, we leverage (ii) a DR estimator, which is widely used in the statistical lit- erature for its robustness to errors caused by missing data. These two approaches allow our algorithm to compensate for missing information due to partial observability, im- proving both estimation accuracy and adaptability to the environment.
First, our problem setting is more general and challeng- ing than misspecified linear bandit problems, where the reward model deviates from the true reward due non- linearity (Lattimore & Szepesvári, 2020) or additive devia- tion terms (Ghosh et al., 2017; Bogunovic et al., 2021; He et al., 2022). While prior works incorporate cumulative mis- specification error into the regret bound, we obtain a regret bound that remains unaffected by such deviations. In particu- lar, Ghosh et al. (2017) employ hypothesis testing for model selection and obtain a regret bound of O VT log T) under high misspecification. In contrast, our algorithm achieves regret bound of O( ((v(d + dr log T) without such tests, while handling partial observability in a unified framework.
Our main contributions are summarized as follows:
We propose a linear bandit problem with partially ob- servable features. Our problem setting is more general and challenging than those in the existing literature on linear bandits with latent features, which often rely on specific structural assumptions governing the re- lationship between observed and latent features. In contrast, our approach assumes no additional structure for the unobserved features beyond the linearity of the reward function, which is commonly adopted in the linear bandit literature (Section 3).
Second, in bandit problems with partially observable fea- tures, prior works often rely on structural assumptions. For example, Park & Faradonbeh (2022: 2024); Kim et al. (2023a) assume the true features drawn from Gaussian distribution, while Zeng et al. (2025) model them as evolv- ing according to a linear dynamical system with additive Gaussian noise, where observed features are generated via a known linear mapping, also corrupted by Gaussian noise. These methods typically aim to recover the true features- via decoders (Park & Faradonbeh, 2022; 2024), Bayesian oracles (Kim et al., 2023a), or Kalman filtering (Zeng et al., 2025). In contrast, our approach makes no structural as- sumptions about the relationship between observed and un- observed features and does not attempt to recover the latter. Instead, we mitigate the information loss from partial ob- servability by projecting the latent part of the reward using only the observed features. A more detailed and comprehen- sive literature review is provided in Appendix A.
We introduce a novel estimation strategy by (i) aug- menting the features that maximally capture the effect of reward projected onto the observed features, while minimizing the impact of unobserved features (Sec- tion 4), and (ii) constructing a DR estimator that miti- gates errors from unobserved features. By integrating augmented features with the DR estimator, we guaran- tee a Vi-convergence rate on the rewards for all arms in each round t (Theorem 2).
We propose an algorithm named Robust to Latent Fea- tures (RoLF) for a general linear bandit framework with latent features (Algorithm 1). The algorithm achieves a regret bound of Ō( (d + d (Theorem 3), where dp is the number of nonzero coefficients associated with the component of the reward projected onto the orthogonal complement of the row space of observed features (Section 4.2). RoLF requires no prior knowl- edge or modeling of unobserved features, yet achieves, to the best of our knowledge, a sharper regret bound than OLB and MAB algorithms, as well as existing methods accounting for partial observability or model misspecification within the linear bandit framework.
3. Preliminaries
3.1. Notation
For any n E N, let [n] denote the set 21, n). For a vector v. we denote its L,, Le and supremum norms by ||v|las |/v|]2, and ||v|| respectively. The n-gmnorm weighted by a positive definite matrix D is denoted by
10() is the Big-O notation omitting logarithmic factors.
2

---

Lincar Bandits with Partially Observable Features
|v|D-- For two vectors V1 and V2, the inner product is defined as the dot product, i.e., (V1, v2) == vi V2, and we use both notations interchangeably. For matrix M. its min- imum and maximum eigenvalues are denoted by Amia (M) and Amax (M), respectively. We let R(M) denote the row space of M, i... the subspace spanned by the rows of M.
Table I. Summary of problem settings covered in this paper and the corresponding results. Note that if latent features arbitrarily change over time, the problem itself would become non-leamable, making the problem ill-posed (see Appendix D for details).
Observed Features
Unobserved
Learnable?
Results
Features
Fixed
Fixed
Yes
Theorem 3 Theorem 6
3.2. Problem Formulation
Varying
Fixed
Yes
Varying
Varying
No
In this section, we outline our problem setting and introduce several key assumptions. Each arm a E [K] is associated with a true feature vector Zo E Rd= that determines its re- wards. However, the agent can observe only a subset of its elements, with the others remaining unobserved. Specifi- cally, Za is defined as follows:
e.g, (a) Moj.ls.......................M 0t-1, (ot-1,9a,--0 1. az). The reward noise e, is conditionally o-sub-Gaussian i.e., for all E E.
1x202
E(exp(>et)) [F--1 S exp
2
Zg = 2 (1)
(d.))
(1)
Since e is sampled after at is observed, ct is meaasurrab Under Assumption I, it follows that Ele, [F,-1] 0, thus E (a,, [(-1] = (zu. 0.). For brevity, we use 1 [-] to de- note B[-1F:-1] henceforth. To eliminate issues of scale for analysis, we assume that the expected reward ( 0.)1 < 1 for all a E [K], and we do not assume any bound on the norm of Zu as well.
For elarity, we highlight the observed components in blue and the unobserved components in red. Note that the di- mensions of the latent feature vector, d, = d= d, and the true feature vector, de, are both unknown to the agent. As a result, the agent is unaware of how many features, if any. are unobserved, or even whether partial observability exists at all. This lack of structural information presents funda- mental challenge, as it prevents the agent from explicitly modeling or compensating for the unobserved components when selecting an appropriate learning strategy.
Let a, := argmax (Ze: 0.) denote the optimal action, considering both observed and latent features. Moreover, we denote by z. and ye the true feature vector and the realized reward associated with the optimal action a,, respectively. We evaluate the theoretical performance of our algorithm using cumulative regret, which is defined as the expected sum of the differences between the reward of a, and a;:
It is worth noting that the setting with fixed observed fea- tures² includes linear bandits with misspecification error (Ghosh et al., 2017; Bogunovic et al., 2021; He et al., 2022) as special cases. In Appendix D. we present setting with varying observed features and an algorithm that achieves -T-rete regret bound. Moreover, if latent features were allowed to change arbitrarily over time, the problem would become non-learnable and thus ill-posed. Consequently, assuming fixed features is both natural and well-justified (see Table 1 for comparisons).
T (0,, 2. Zar)
Reg(7) =
t=1
T
(E, ( - E2 [)),,,))-
Considering the composition of z, defined in Eq. (1), we de- compose the parameter vector as 0 = [(0 (((0)),
The reward associated with arm a is defined as the dot product between its true feature vector n., and an unknown
where (()) E Rd and @(n) Rdd. correspond to the pa- rameters associated with the observed and latent features, respectively. Adopting this decomposition of o., the re- ward ya,, defined in Eq. (2) can be decomposed into the following three terms:
parameter 0, Rd, namely
yo.t (Za. 0.) + 6
VAE [aE]K),
where a, E [K] denotes the action selected by the agent at round L. Here, é represents a random noise term that captures the inherent stochasticity in the reward generation process. We make the following assumption on 6, which is commonly adopted in bandit problems.
Bas,t (Xor 0.0)² + Ee + (Uay O("))
(3)
The last term of Eq. (3) corresponds to the inaccessible portion of the reward. This reward model equivalent to that imposed in the linear bandits with misspecification er- ror (Ghosh et al., 2017; Lattimore et al., 2020). While the regret bound in Lattimore et al. (2020) includes misspecifi- cation error that grows linearly with decision horizon, our proposed method (Section 4) addresses this misspecification error and achieves a regret bound that is sublinear in T.
Assumption 1 (Sub-Gaussian noise). Let F. denote the history at round t, represented by a filtration of o-algebras,
This assumption is standard in linear bandits with model mis- specification (Ghosh et al., 2017: Lattimore al., 2020), which is a special case of our partially observable feature setting.
3

---

Lincar Bandits with Partially Observable Features
Before presenting our method and algorithm, we first es- tablish lower bound on the regret of linear bandit al- gorithms that disregard the unobserved portion of the re- wards. In particular, the following theorem provides lower bounds for two OLB algorithms: OFUL (Abbasi-yadkori et al., 2011) and LinTS (Agrawal & Goyal, 2013).
tend to suffer higher regret than Teature-based algorithms, particularly when the number of arms is significantly larger than the dimension of the feature vectors, i.e., K > dg.
To tackle this dilemma, we propose a unified approach that handles partial observability and ensures efficient estima- tion. Let us define X := (xI,..., xx) E RR as the matrix formed by concatenating the observed part of the E IR x as the matrix formed by concatenating their latent complements for each arm. Without loss of generality, we assume a set of K vectors {xI,..... ,x),, spans Rd.3 We denote by Px X (XXT)- the projection matrix onto the row space of X, denoted by R(X). Then the vector of rewards for all arms, Y, (V1, .UK,))) is decomposed as:
Theorem 1 (Regret lower bound of OFUL and LinTS ignor- ing latent features), Under partial observability, there exists a problem instance where both OFUL and LinTS suffer from cumulative expected regret that grows linearly with T due to their disregard for the unobserved components.
true features, and U :- (uf*) .....
ux) (u..)...,
Sketch of proof. Consider linear bandit problem instance with an action set A := {1, 2). where d = du = I, implying that d₂ = 2. The true feature vectors are given by 2 == {11,3] [2, ] C IR,, with the agent observing only the first element of each vector, while the second element remains unobserved. In this setting, we take arm to be the optimal action. However, an estimator relying solely on the observed features is inconsistent, leading OFUL and LinTS to select the suboptimal arm with probability ((1), and thereby incur regret that grows linearly in T.
Y.
X o + o telk
Px X (T +U 0(())
+ +IK - PPx)
X ((0)) + UTO!!)) + +e,l
=x (0 (XX I
Theorem 1 shows that neglecting the latent portion of the reward in decision-makee making may cause the agent to fail in identifying the optimal action. The comprehensive proof is deferred to Appendix E. While Theorem I specifically considers OFUL and LinTS-which are known to achieve the most efficient regret bounds for UCB- and Thompson sampling-basee based policies in the linear bandit framework- we additionally present an algorithm-agnosti lower bound based on different analysis (see Appendix F for details).
+ (Ix-Px)U oLt0) + cllk:
(4)
where the first term corresponds to the reward projected onto R(X), whereas the second term is the reward projected onto R(X) the subspace of IR orthogonal to R(X). We
reparametrize o()) (XX - @(#) as v26 repre- senting the parameter associated with the observed features.
To handle the second term in Eq. (4), we consider a set of row vector bases {b, [bT...., bk-a) E R(X)-, where b, E R for i E [K- - d]. Given the set, there exist coefficients P.
4. Robust Estimation for Partially Observable Features
...k- ..I........kk- E R such that the term can be expressed as a linear combination:
4.1. Feature Vector Augmentation with Orthogonal Projection
K-d by.
- PX) 0 = Σ
(1)
(5)
In the linear bandit framework, accurate estimation of the known reward parameter 0, contributes to optimal decision- making. However, in our problem setting, the learner lacks access to the latent reward component maaronnnntnammly...... the last term in Eq. (3). Consequently, without an appropriate mech- anism to compensate for the absence of 0("), the agent fails to accurately estimate 0., resulting in ineffective learning, as demonstrated in Theorem 1.
We define the number of nonzero coefficients as:
du (b] .b. bJ -
d) = (i - :4!. + 03}. (6)
Note that dh. for any basis set {bT ...., bk-a) when the latent feature space is completely included in the ob- served feature space, i.e., R(U)- C R(X). In this case, (Ix Px) = 0Oxx which means that the projected rewards onto R(X) can be linearly expressed by the ob- served features. If R(U) 2 R(X). on the other hand, then d, K d for any basis set
That said, minimizing regret-that is, selecting the optimal arm-does not require recovery of the true reward parameter 0. entirely; rather, it suffices to estimate the K expected rewards { 0. a E [K]}- A straightforward approach is to ignore the features altogether and apply MAB algorithms such as UCB1 (Auer et al., 2002), which are known to achieve a regret bound of Ö(VKT). However, these algorithms
'hhen d > K, can apply singular value decomposition (SVD) on X reduce the feature dimension d < K with R(X)= = d.
4

---

Lincar Bandits with Partially Observable Features
Figure 1. Illustration comparing OLB algorithms and our approach in estimating rewards of K = 3 arms. OLB algorithms find estimates within R(X) thus accumulating errors from unohserved features. However, our approach utilizes the projection of the latent reward. b pa(") onto the orthogonal complement of R(X), thereby enabling reward estimation in R.
of (VKTT) (see Appendix C). However, when K > d and du 0, the regrett is the regret is higher than that of OLB algorithms. To address this challenge, we propose novel estimation strategy in the following section that eliminates the dependence on K in the regret bound.
q3
q3
4.2. Doubly Robust Lasso Estimator
B [Y]
E 1 [
In Eq. (7), the parameter μ. is sparse, with its sparsity de- pending on the number of nonzero elements required to rep- resent the inaccessible portion of the reward projected onto R(X)+, namely dn defined in Eq. (6). Recall from Eq. (5) that this projection can be expressed using at most dy, basis vectors, implying that Ju, has at most d₁, nonzero entries.
bT P
X A.00)
R(X)
qu
R(X)
X
(o)
q2
91
q1
(a) OLB algorithms: Estima- tion confined R(X)
(b) Ours: Projection onto or- thogonal complement
Let j denote the Lasso estimator of μ. using the aug- mented feature vectors, defined as follows:
In other cases, the quantity d, depends on the choice of the basis (bj ..... b and tends to be smaller when larger portion of R(U) is included within R(X). For any choice of the basis, our algorithm achieves Ö(v dT) regret without prior knowledge of d,, which does not exceed the Ö(VKT) KT) regret bound achieved by MAB algorithms ig- noring features. Further details are provided in Section 5.2.
1 == argmin
(yars x 12)2
(8)
2K |||||,,
+ 2T max
2pl log 8
where p is the coupling probability used to define the multi- nomial distribution for pseudo-action sampling (as defined in Eq. (9)), and 5 is the confidence parameter of the algo- rithm. Note that 7 max == max e (ZoE(k) Xxx] Je i.e., the largest diagonal entry of the Gram matrix con- structed from the augmented feature vectors X. over A.
Similar to the reparametrization of 1,)), we denote p1(") [p_.)..... P..k -al"
(w) T. By concatenating p!." and μu (w) we
define μ. := [( ((u()),, (TT E IK so that the re- ward for each a E [K] can be rewritten as follows:
For the estimator in Eq. (8) to correctly identify the zero entries in J4,, the compatibility condition needs to be satis- fied (van de Geer & Bühlmann, 2009). Although the com- patibility condition does not, in general, require a positive minimum eigenvalue for the Gram matrix, in our setting, Amia (t Σ'= Xx. x O. Therefore, the compatibil- ity condition is implied without any additional assumption. However, ensuring a sufficiently large minimum eigenvalue typically requires collecting a large number of exploration samples, which in turn increases regret. Achieving this with fewer exploration samples remains a key challenge in the bandit literature, as the minimum eigenvalue affects the con- vergence rate of the estimator and, consequently, the regret bound (Soare et al., 2014; Kim et al., 2021).
Ya,t = co Y
= c [ T b bb + ee
=[xa eg b ... e bl- + es-
The decomposition in Eq. (7) implies that Eq. (4) takes the form Y, X b....b--i bll, + Glg. Note that ea R denotes the a-th standard basis vector. With this modification, the rewards are now represented as linear function of the augmented feature vectors: Xa == [x, c, b c., c bx E RK, without any misspecifica- tion error. A toy example illustrating our strategy is shown in Figure 1.
In terms of regret minimization, while SupLinUCB (Chu et al., 2011) achieves regret bound of Ö(VdT), it is of- ten considered impractical as it computes log T distinct batches and estimators, requiring knowledge of T and, more critically, discards a significant portion of samples at each parameter update. To retain the theoretical efficiency while improving practicality, we adopt the doubly robust (DR) estimation framework, which is known to achieve O(VdT) (Kim et al., 2021; 2023c). Given that X, E k we propose an efficient algorithm that employs a DR esti- mator with ridge regularization and obtains a regret bound
We introduce doubly robust (DR) estimator that employs the Gram matrix constructed from the augmented feature vectors over the entire action space, Σ 1 Eee(K) X rather than only from the chosen actions, Ei=1 Xa, "T, Originating in the missing-data literature (Bang & Robins, 2005), DR estimation yields consistent estimators if either the imputation or the observation probability model is cor- rect (Kim et al., 2021). In the bandit setting, only the reward of the chosen arm is observed for each decision round, leav- ing the other K - 1 as missing. Hence, DR estimation im- putes these K missing rewards and incorporates all the
5

---

Lincar Bandits with Partially Observable Features
associated feature vectors into the estimation process. Since the observation probabilities are determined by the policy- which is known to the learner-the DR estimator remains robust to errors in the reward estimation. While Kim & Paik (2019) proposed a DR Lasso estimator under IID features satisfying the compatibility condition, we propose a novel DR Lasso estimator that does not rely on such assumptions.
event that the pseudo-action a matches the chosen action 0 within a specified number of resamples. For given 8' E (0, 1), we set the maximum number of resamples to Pe := log((t + /))/ log(1/(1 - -p)); then M, occurs with probability at least 1 - 8' /t+ 1)2. Resampling allows the algorithm to further explore the action space to balance regret minimization with accurate reward estimation.
We improve the DR estimation by incorporating resampling and coupling methods. For each let & S [t] denote the set of exploration rounds such that for any E ε,, the action a, is sampled uniformly over [K]. The set & is constructed recursively: starting with Eo- = 0. we define
For a A ār, i.c. an arm that is not selected in the round t, we impute the missing rewards using x juj'. For oe, in contrast, the term I(ā,- = predicted reward to ensure the unbiasedness of the pscudo- rewards for all arms. Given that Ez, [T); = a)] = P(ā,- =
thatt calibrates the
a) = 0a.t. taking the expectation over ag on both sides of Eq. (10) gives Ra, [Va..] = [V,.] = x_ 14, for all a E [K]. Although the estimate x, ie, may have a large error, it is multiplied by the mean-zero random variable (1 1(m =a//0,,), which makes the resulting pseudo- rewards defined in Eq. (10) robust to errors of X_ P4- The pseudo-rewards can only be computed-ard thus can only be when the pseudo-action ã matches the actual action a,, that is, when the event MM occurs. Since M, occurs with high probability, we are able compute pseudo- rewards for almost all rounds.
2K
E Ut if & C. log & =
8
EC-1
otherwise.
Here, C. is defined as (8K) min max (1 - p) p)² where Th := Amin Mani((Caelk (Eee[k) xxxx) denotes the minimum eigen- value of the Gram matrix constructed from the augmented feature vectors over the entire action space.
At each round t & E,, the algorithm selects a according to an g-greed strategy: with probability E, = t-1/2, it selects à argmax, x L P 1: with 1- Et, it selects an action uniformly random from [K] \ {ā.). Given at, a pseudo- action ãt is sampled from multinomial distribution:
Incorporating the pseudo-rewards, To, into estimation, we define our DR Lasso estimator as follows:
Duat == P(ā, at ax)= = P.
i == argmin I(M Σ (Tair - X3_ 11)
Φx, : P(ā. = k ax) = 1-p
(9)
KE(K]
(11)
K--1
40
2K12
2t log 8
||14|12,
for all k E [K] \ fa+), where p E (1/2,1) is the coupling probability specified by the algorithm. To couple the poli- cies for the actual action a and the pscudo-action āz we repeatedly resample both of them until they match.
and note that our estimator uses the Gram matrix aggregated over all actions at each round, Σ X,x, instead of the one built only from the chosen actions, Σt= X xT.
With the pseudo-actions coupled with the actual actions, we construct unbiased pseudo-rewards for all a E [K] as:
The following theorem guarantees convergence of the esti- mator, across all arms, to the true parameter, after sufficient number of exploration rounds.
Jo.. = XI 1. + I(ā= = a) (yo,t X f.)
(10)
Theorem 2 (Consistency of the DR Lasso estimator). Let d, denote the dimension of the projected latent rewards defined in Eq. (6). Then with probability at least 1- 35,
da.1
where ju! is the imputation estimator that fills in the missing rewards of unselected arms at round f, as defined in Eq. (8).
800max
2(d + dr)
2kt
As shown in Eq. (10), the pseudo-rewand includes an inverse probability term. Hence, when DR estimation is applied under the 4-greedy policy with 4 = 11/2, its variance can grow unbounded over time. To mitigate this issue, we propose a resampling and coupling strategy: by coupling the c--gredy policy with the multinomial distribution (Eq. (9)), we ensure that each inverse probability weight d for a E [K], remains bounded by O(K). This strategy effectively stabilizes the variance of the pseudo-rewards.
max X AE []
(Rt -M,)l
po
t log
8
for all rounds 1. such that t 2 [1
Although the DR Lasso estimator leverages K K-dimensional feature vectors, its error bound depends only logarithmi- cally on K. Such fast convergence is typically achieved under classical regularity conditions, including the compat- ibility condition and the restrictive minimum eigenvalue condition (van de Geer & Bühlmann, 2009; Bühlmann & van de Geer, 2011). Existing Lasso- based bandit ap- proaches (Kim & Paik, 2019; Bastani & Bayati, 2020; Oh
Moreover, one can show that the resampling succeeds with high probability for each round. Let M, denote the
6

---

Lincar Bandits with Partially Observable Features
Algorithm 1 Robust to Latent Feature (RoLF)
Table 2. An overview of regret bound range of our algorithm, RoLF, depending d [0, K d]. the number of nonzero elements to effectively capture the unobserved part of reward projected onto R(X)+ Note that Ô denotes the big-O notation omitting logarithm factors.
1: INPUT: Observed features {x, : [K]], coupling probability p (1/2, 1), confidence parameter 6 > O.
2: Initialize Mo = Ok, exploration phase Eo = 0, and exploration factor Ce := (8K)* "ii T max
m (1- p)? 3: Find orthogonal basis {b) ..... bx-a) C and construct {xa : a E {-]}-
Feature space
Regret bound
span(observed) 2 span(latent)
Õ dT Ō KT
4: for(=1,..., T do
span(observed) C span(latent)
5:
if if| S C. 18g(2++)))) then
otherwise
(d dR)TT)
6: Randomly sample ag uniformly over [K] and &
E
vectors [bJ bk-a) S R(X)* to augment each ob- served feature vector. The algorithm first selects a candidate action â--eether uniformly at random or greedily based the estimated reward- and then resamples a, and ã un- til they match or the maximum number of trials allowed for each round, P: := log((t + / log(1/(1 ()),, is reached. Once the resampling phase ends, the algorithm selects a and the corresponding reward yo,,t is observed. If a and āg match within Pr. then both the imputation and the main estimators are updated; otherwise, neither is updated.
7: else
8:
Compute ār == arg m
[K] X2 1
9:
end if
10:
while ūt # at and count S P: do
11:
Sample at with P( = āt) = 1 (1-1/2) and
P(a, - k) = 1-11/2 /(K - 1), vk + Ct.
12:
Sample de according to Eq. (9).
13:
count = count + 1.
14:
end while
15:
Play a, and observe yout
16:
if āz * a, then
Our proposed algorithm does not require knowledge of the dimension of the unobserved features du, nor the dimension of the reward component projected onto R(X) Although we present the algorithm for fixed feature vectors, the algo- rithm is also applicable to time-varying feature vectors, In such cases, we estimate the bias caused by unobserved fea- tures by augmenting the standard basis. For further details, refer to Appendix D.
17:
Set jt : M-11- else
18:
19:
Update j.. following Eq. (11) with N., and update ju following Eq. (8).
20:
end if
21:
end for
et al., 2021: Ariu et al., 2022; Chakraborty et al., 2023; Lee et al., 2025) generally impose these conditions directly on the feature vectors. Our approach, on the other hand, does not require such assumptions, as the augmented fea- tures are orthogonal vectors lying in R(X)-. Moreover, their average Gram matrix satisfies Amin (E xxx,) 2 min (1, Amin [ne(K] x,x,)), ). Thus, the convergence rate scales only as vlog K with respect to K.
5.2. Regret Analysis
Theorem 3 (Regret bound for I Lasso ROLF). Let de denote the number of nonzero coefficients in the representation of the projected latent reward defined in Eq. (6). Then for any ô E (0, 1) and (1/2, 1), with probability at least - 68, the cumulative regret of RoLF is bounded by
2KT2
The consistency is proved by bounding the two components of the error in the pseudo-rewards (Eq. (10)): (i) the noise of the reward and (ii) the error of the imputation estimator iu, Since (i) is sub-Gaussian it can be bounded using mar- tingale concentration inequalities. For (ii), the imputation error X (i/ - (u.) is multiplied by the mean-zero random variable (1 - T( = a)/ (a.t)) and thus the magnitude of the error can be bounded by p m. lli/ The detailed proof is deferred to Appendix E.2.
RTg(T) 22.88 -p)
-2 -2log 8
4VT
+ K-1 + +21
2T log 46
320ōmaxx max
2KT
+
2(d log 8
pomin
To the best of our knowledge, Theorem 3 provides the first regret bound that converges faster than Ö(VKT), specif- ically for algorithms that account for unobserved features without relying any structural assumptions. Assuming | aox < 1 (instead of ||x,|12 S 1), o and G are con- stant independent of d or K. Note that the number of rounds required for the exploration phase is O(K3 log KT), which grows only logarithmically with the time horizon T. The factor K is irreducible, as the algorithm needs information
5. Proposed Algorithm and Regret Analysis
5.1. Robust to Latent Features (RoLF) Algorithm
In this section, we present our algorithm RoLF in Algo- rithm I. In the initialization step, given the observed fea- tures, our algorithm constructs set of orthogonal basis
7

---

In the simulation, after constructing the true features z, E ddd= and observed features x, E Rdd we apply singular value decomposition (SVD) to the observed feature matrix X to derive orthogonal basis vectors (bT,... b or- thogonal to R(X). These vectors are then concatenated Lincar Bandits with Partially Observable Features
about all K biases from the missing features. By employing the Gram matrix of the augmented feature vectors over the action space A. > X.X_' when combined with DR esti- mation, we reduce the required exploration phase time from O log KT) to O O(K log KT), thereby improving the sample complexity by a factor of K.
and the rewards are generated following Eq. (2). For the hyperparamters in our algorithms, the coupling probabil- ity p and the confidence parameter 6, are set to 0.6 and 10 -4 respectively. The total decision horizon is T = 1200. Throughout the experiments, we fix the number of arms at K = 30 and the dimension of the true features at d2 = 35, ensuring d2 2 d to cover both scenarios. Further details on the experimental setup are provided in Appendix B.
As demonstrated in Theorem 2, the last term on the right- hand side of the regret bound is proportional to vd + dn rather than V K, resulting in an overall regret bound of O(v(d + loog KT). The specific value of da is de- termined by the relationship between R(X) and R(U), as discussed in Section 4.1. Table 2 summarizes how the regret bound varies under different relationships between these subspaces. The formal proof of Theorem is deferred to Appendix E.3.
6.2. Experimental Results
6.2.1. SCENARIO 1
In this scenario, is set to [d=/2], so that the agent observes only about half of the full feature dimension. From Figure 2, we observe that the baseline OLB Soorithms-LinUCe LinTS, and DRLasso -erffor worse than our algorithms in terms of both the level and robustness of cumulative re- gret. This pattern is consistently observed across all three cases, implying that linear bandit algorithms fail to identify the optimal arm in the presence of unobserved components, as they cannot capture the portion of the reward associated with the unobserved features. However, our algorithms show almost the same performance regardless of the relationship between RXX) and R(U), indicating the robustness to vari- ations in feature observability structure.
6. Numerical Experiments
6.1. Experimental Setup
In this experiment, we simulate and compare our algo- rithms, Algorithm 1 and Algorithm 2 (Appendix C), with baseline OLB algorithms: LinUCB (Li et al., 2010) and LinTS (Agrawal& & Goyal, 2013). These algorithms adopt UCB and Thompson sampling strategies, respectively, as- suming linear reward model based on observed features.
(Algo- Note that for all cases our Soporithns-RooF---e rithm 1) and RoLF- RRdde (Algorithm --chiiiit a sharp decline in the growth rate of cumulative regret after cer- tain number of rounds. This behavior is primarily due the forced-exploration phase built into the algorithms, which ensures sufficient coverage of the action space in the early stages. Following this phase, the resampling and coupling strategies further enhance the efficiency of the DR estima- tion, leading to slower regret accumulation over time. This pattern is commonly shown from experimental results of other bandit algorithms employing the forced- eerredeexploration strategy (Goldenshluger & Zeevi, 2013; Hao et al., 2020; Chakraborty et al., 2023).
We also include DRLasso (Kim & Paik, 2019) since our algorithm employs DR estimation with Lasso estimator, and UCB (Lattimore& & Szepesvári, 2020), an MAB al- gorithm that ignores features, to assess the effectivencss of using feature information, even under partial observability.
To provide comprehensive results, we consider two scenar- ios: one with partial observability and one without. For each scenario, we conduct experiments under three cases, classified by the relationship between the row spaces of the observed and unobserved features, R(X) and R(U), which determines the value of dn: (i) Case 1, the general case where neither R R(X) nor R(U)) fully contains the other; (ii) Case 2. R(U) C R(X), where the row space spanned by the unobserved features lies entirely within that spanned by the observed features, thus dy, O; (iii) Case 3, R(X) C R(U), where the row space spanned by the observed feature space is fully contained within that spanned by the unobserved features, implying d, = K - d. Note that in Scenario 2, Case is excluded because R(U)= = 0 implies R(X)= = 0, which violates our problem setup.
Furthermore, in Case 2 (Figure 2(b)), the cumulative regret grows more slowly than in other cases. This behavior is explained by the relationship R(U) S R(X), implying the reward components projected onto R(X)- can be fully ex- pressed by the observed features. As a result, the augmented features fully capture the underlying reward structure, en- abling faster convergence relative to the other scenarios.
6.2.2. SCENARIO 2
In Scenario 2, we set d = dg = 2K, implying that no latent features remain and allowing us to evaluate our algorithms under the condition d > K. As discussed in Section 4,1, we apply SVD to reduce the dimensionality of the observed features before constructing the augmented feature set. Fig- ure 3 shows that our algorithms perform well even without
with X to form the augmented feature matrix. The reward parameter 0, E Rdd is sampled from 1nif()1/211/2),
8

---

Lincar Bandits with Partially Observable Features
RoLF-Lesso (Ours)
RoLF-Lasso (Ours)
RoLF-Lasso (Ours)
HoLF-Ridge (Ours)
HoLF-Ridge (Ours)
RoLF-Ridge (Ours)
560
DRLasso
DRLasso
DRLasee
LinUca
LinUCB
LinUC
LinTS
600
LinTS
500
UCB(d)
UCB(B)
UCB(8)
200
200
200
200
200
110
2013
401
402
1.000
1205
200
432
110
1.00
1250
200
420
800
1000
3285
(a) Case (General Case)
(b) Case 2 (R(U) S R(X))
(c) Case (R(X) C R(U))
Figure 2. Cumulative regrets of the algorithms with partial observability (Scenario 1).
RoL Lassa (Ours)
Rol Lasso (Ours)
RoLF-Ridge (Ours)
560
RoLF-Ridge (Ours)
DRLasso
DRLasso
LinTS
LinTS
Cond
UCBI6)
UCB(6)
300
Round 10
Aaand m
(a) Case (General Case)
(b) Case (R(U) S R(X))
Figure 3. Cumulative regrets of the algorithms without partial observability (Scenario 2).
unobserved features, both in terms of the level and robust- ness of the cumulative regret. Moreover, by incorporating dimensionality reduction, our algorithms remain effective even when the feature matrix is not full rank. Lastly, similar to Figure 2, cumulative regret in Case 2 converges slightly more slowly than in Case 1.
7. Conclusion
In this work, we addressed the problem of partially ob- servable features within the linear bandit framework. We showed that conventional algorithms that ignore unobserved features may suffer linear regret due to information loss, and introduced RoLF, novel algorithm that accounts for latent features using only observed data without requiring prior knowledge. Our algorithm achieves a tighter regret bound than existing methods, and this improvement supported by our numerical experiments.
Meanwhile, the baseline OLB algorithms continue to strug- gle in identifying the optimal arm throughout the horizon. For LinUCB and LinTS, this behavior may be attributed to the curse of dimensionality, where regret scales linearly with the feature dimension d-a well-known limitation of linear bandit algorithms (Oswal et al., 2020; Tran et al., 2024). Additionally, since the true rewards are bounded by the resulting small reward gaps between arms may further hinder the identification of the optimal arm. In the case of DRLasso, similar behavior arises from the fixed feature set- ting: the algorithm uses "averaged" context vector across the action space at each round for parameter estimation. Consequently, under the fixed-feature setting, this strategy becomes effectively equivalent to using single fixed vector throughout the entire learning horizon, thereby limiting the expressiveness of the estimation.
For future work, from the perspective that feature aug- mentation strategy reformulates the problem as another lin- ear bandit problem without model misspecification, extend- ing this approach to other reward models, e.g., generalized linear models, would an interesting direction. Addition- ally, although we assumed the latent reward component to be linear in the unobserved features, we can relax this as- sumption by viewing the latent reward component an exogenous factor that interferes with the learning process. This perspective allows for modeling the latent reward using general function class without structural assumptions.

---

Lincar Bandits with Partially Observable Features
Impact Statement
Bang, H. and Robins, J. M. Doubly robust estimation in missing data and causal inference models. Biometrics, 61 (4):962-973, 2005.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bastani, H. and Bayati, M. Online decision making with high-dimensional covariates. Operations Research, 68 (1):276-294, 2020.
Acknowledgements
Bogunovic, L,, Losalka, A., Krause, A., and Scarlett, J. Stochastic linear bandits robust to adversarial attacks. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Pro- ceedings of Machine Learning Research, pp. 991-999. PMLR, 2021.
This work was supported by the National Research Foun- dation of Korea (NRF) grant funded by the Korea govern- ment (MSIT) (RS-2022-NR0718355 RS-2023-00222663; RS-2025-16070886) by grant of Korean ARPA-H Project through the Korea Health Industry Development Institute (KHIDI), funded by the Ministry of Health & Welfare, Re- public of Korea (RS-2024-0051237)
Bühlmann, P. and van de Geer, S. Statistics for High- Dimensional Data: Methods, Theory and Applications. Springer Berlin Heidelberg, 2011.
by AI-Bio Research Grant through Seoul National University, and by the Insti- tute of Information & Communications Technology Plan- ning Evaluation (IITP) grant funded by the Korea gov- ernment (MSIT) (RS-2025-022637544 RS-2021-I121 1341, Artificial Intelligence Graduate School Program, Chung- Ang University). Garud Iyengar's research was partially supported by ONR grant N000142312374 and NSF grant EFMA-2133142.
Chakraborty, S., Roy, S., and Tewari, A. Thompson sam- pling for nigh-dimensional sparse linear contextual ban- dits. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Ma- chine Learning Research, pp. 3979-4008. PMLR, 2023.
Chu, W., Li. L., Reyzin, L., and Schapire, R. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pp. 208-21 214. PMLR. 2011.
References
Abbasi-yadkori, Y., Pál, D., and Szepesvári, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
Dani, V., 9, Hayes, T., and Kakade, S. M. Stochastic linear optimization under bandit feedback. 21st Annual Conference Learning Theory- COLT 2008, Helsinki, Finland, pp. 355 355-366, 2008.
Abe, N. and Long, P. M. Associative reinforcement learning using linear probabilistic concepts. In Proceedings of the Sixteenth International Conference on Machine Learning, ICML 199. pp. 3-11. Morgan Kaufmann Publishers Inc., 1999.
Dimakopoulou, M., Zhou, Z., Athey, S., and Imbens, G. Balanced linear contextual bandits. Proceedings of the AAAI Conference Artificial Intelligence, 33(05):3445- 3453, 2019.
Agrawal, S. and Goyal, N. Thompson sampling for contex- tual bandits with linear payoffs. In Proceedings of the 30th International Conference on Machine Learning, vol- 28 of Proceedings of Machine Learning Research, pp. 127-135. PMLR, 2013.
Ghosh, A., Ray Chowdhury, S., and Gopalan, A. Misspeci- fied linear bandits. Proceedings of the AAAI Conference Artificial Intelligence, 31(1), 2017.
Goldenshluger, A. and Zeevi, A. A linear response bandit problem. Stochastic Systems, 3(1):230 261, 2013.
Ariu, K., Abe, K., and Proutiere, A. Thresholded lasso ban- dit. In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 878 928. PMLR, 2022.
Hao, B., Lattimore, T., and Wang, M. High-dimensional sparse linear bandits. In Advances in Neural Informa- tion Processing Systems, volume 33, pp. 10753-10763. Curran Associates, Inc., 2020.
Auer, P. Using confidence bounds for exploitation- exploration trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
He, J., Zhou, D., Zhang, T., and Gu, Q. Nearly optimal algorithms for linear contextual bandits with adversarial corruptions. In Advances in Neural Information Pro- cessing Systems, volume 35, pp. 34614-34625. Curran Associates, Inc., 2022.
Auer, P., Resa-Bianchh, N., and Fischer, P. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 2002.
10

---

Lincar Bandits with Partially Observable Features
Kim, G.-S. and Paik, M. C. Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
Oh, M.-H., Iyengar, G., and Zeevi, A. Sparsity-agnostic lasso bandit. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pp. 8271-8280 PMLR, 2021.
Kim, J.-H., Yun, S.-Y., Jeong, M., Nam, J., Shin, J., and Combes, R. Contextual linear bandits under noisy fea- tures: Towards bayesian oracles. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 1624-1645. 1645. PMLR, 2023a.
Oswal, U.. Bhargava, A., and Nowak, R. Linear bandits with feature feedback. In The Thirty- Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Secons Innovative Applications of Artificial Intelligence Confer- ence, IAAI 2020, The Tenth AAAI Symposium on Edu- cational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pp. 5331-5338. AAAI Press, 2020.
Kim, W., Kim, G.-S,, and Paik, M. C. Doubly robust thomp- son sampling with linear payoffs. In Advances in Neural Information Processing Systems, volume 34, pp. 15830- 15840. Curran Associates, Inc., 2021.
Park, H. and Faradonbeh, M. K. S. A regret bound for greedy partially observed stochastic contextual bandits. In Decision Awareness in Reinforcement Learning Workshop at 2022, 2022.
Kim, W., Lee, K., and Paik, M. C. Double doubly robust thompson sampling for generalized linear contextual ban- dits. Proceedings of the AAAI Conference on Artificial Intelligence, 37(7):8300-2 -3070 2023b.
Park, H. and Faradonbeh, M. S. Thompson sampling in partially observable contextual bandits. arXiv preprint arXiv:2402. 10289, 2024.
Kim, W., Paik, M. C., and Oh, M.-H. Squeeze all: Novel estimator and self-normalized bound for linear contextual bandits. In Proceedings of The 26th International Con- ference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp- 3098 3124. PMLR, 2023c.
Robbins, H. E. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58:527-535, 1952.
Rusmevichientong, P. and Tsitsiklis, J. N. Linearly parame- terized bandits. Mathematics of Operations Research, 35
Kim, W. Iyengar, G., and Zeevi, A. A doubly robust ap- proach to sparse reinforcement learning. In Proceed- ings of The 27th International Conference on Artificial Intelligence and Statistics, volume 238 of Proceedings of Machine Learning Research, pp. 1305-23313 PMLR, 2024.
(2):395-411, 2010.
Soare, M., Lazaric, A., and Munos, R. Best-arm identifica- tion in linear bandits. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Lai, T. and Robbins, H. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, pp. 4-22, 1985.
Tennenholtz, G., Shalit, U., Mannor, S., and Efroni, Y. Ban- dits with partially observable confounded data. In Pro- ceedings of the Thirty- Seventh Conference on Uncertainty Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 430-439. PMLR, 2021.
Lattimore, T. and Szepesvári, C. Bandit algorithms. Cam- bridge University Press, 2020.
Lattimore, T., Szepesvari, C., and Weisz, G. Learning with good feature representations in bandits and in RL with generative model. In Proceedings of the 37th Interna- tional Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5662- 5670. PMLR, 2020.
Tran, N. P., Ta, T. A., Mandal, D., and Tran-Thanh, L. Sym- metric linear bandits with hidden symmetry. In Advances in Neural Information Processing Systems, volume 37, pp. 28699-128733 Curran Associates, Inc., 2024.
Tropp. J. A. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):389-44, 2012.
Lee, H., Hwang, T., and Oh, M.-h Lasso bandit with compatibility condition on optimal arm. In International Conference on Learning Representations, 2025.
Tropp, J. A. An introduction to matrix concentration in- equalities. Found. Trends Mach. Learn., 8(1-2):1-230, 2015.
Li, L., Chu, W., Langford, J., and Schapire, R. E. A contextual-bandiy approach to personalized news article recommendation. In Proceedings of the 19th Interna- tional Conference on World Wide Web, WWW '10. pp- 661-670. Association for Computing Machinery, 2010.
van de Geer, S. A. and Bühlmann, P. On the conditions used to prove oracle results for the Lasso. Electronic Journal of Statistics, 3:1360 1392, 2009.

---

Lincar Bandits with Partially Observable Features
Zeng, S., Bhatt, S., Koppel, A., and Ganesh, S. Partially observable contextual bandits with linear payoffs. In ICASSP 2025 2025 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), 2025.
12

---

Lincar Bandits with Partially Observable Features
A. Related Works
In bandit problems, the learning agent learns only from the outcomes of chosen actions, leaving unchosen alternatives unknown (Robbins, 1952). This constraint requires a balance between exploring new actions and exploiting actions learned to be good, known as the sxploration-exploitttii towards the optimal policy. To address this, algorithms based on optimism in the face of uncertainty (Lai & Robbins, 1985) employ the Upper Confidence Bound (UCB) strategy, which encourages the learner to select actions with the highest sum of estimated reward and uncertainty. This approach adaptively balances exploration and exploitation, and has been widely and studied in the context of linear bandits (Abe & Long, 1999; Auer, 2002; Dani et al., 2008; Rusmevichientong & Tsitsikkis, 2010). Notable examples include LinUCB (Li et al., 2010; Chu et al., 2011) and OFUL (Abbasi-yadkong et al., 2011), which are known for their practicality and performance guarantees. However, existing approaches differ from ours in two key aspects: (i) they assume that the learning agent can observe the entire feature vector related to the reward, and (ii) their algorithms have regret that scales linearly with the dimension of the observed feature vector, i.e., O(dVT).
tradeoff. Efficiently managing this tradeoff is crucial for guiding the agent
In contrast, we develop an algorithm that achieves sublinear regret bound by employing the doubly robust (DR) technique, thereby avoiding the linear dependence on the dimension of the feature vectors. The DR estimation in the framework of linear contextual bandits was first introduced by Kim & Paik (2019) and Dimakopoulou et al. (2019), and subsequent studies improve the regret bound in this problem setting by a factor of vd (Kim et al., 2021; 2023b). A recent application (Kim et al., 2023c) achieves a regret bound of order (VVTT Vlllo under IID features over rounds. However, the extension to non-stochastic or non-IID features remains an open question. To address this issue, we develop novel analysis that applies the DR estimation to non-stochastic features, achieving regret bound sublinear with respect to the dimension of the augmented feature vectors. Furthermore, we extend DR estimation to handle sparse parameters, thereby further improving the regret bound to be sublinear in the reduced dimension.
Our problem is more general and challenging than misspecified linear bandits, where the assumed reward model fails to accurately reflect the true reward, such as when the true reward function is non-linear (Lattimore & Szepesvári, 2020), or when a deviation term added to the reward model (Ghosh et al., 2017: Bogunovic et al., 2021; He et al., 2022). While our work assumes that the misspecified (or inaccessible) portion of the reward is linearly related to certain unobserved features, misspecified linear bandit problems can be reformulated as a special case of our framework. While the regret bounds in Lattimore & Szepesvári (2020), Bogunovic et al. (2021) and He et al. (2022) incorporate the sum of misspecification errors that may accumulate over the decision horizon, our work establishes a regret bound that is sublinear in the decision horizon T and is not affected by misspecification errors. Ghosh et al. (2017) proposed a hypothesis test to decide between using linear bandits or MAB, demonstrating an ((KYTlog) T) regret bound when the total misspecification error exceeds (dvT). In contrast, our algorithm achieves an (VV (d + dx)7 log T) regret bound without requiring hypothesis tests for misspecification or partial observability.
Last but not least, our problem appears similar to the literature addressing bandit problems with partially observable features (Tennenholtz et al., 2021; Park & Faradonbeh, 2022; 2024; Kim et al., 2023a; Zeng et al., 2025). In particular, Park & Faradonbeh (2022; 2024); Kim et al. (2023a) assume that the true features follow a specific distribution, typically Gaussian. Zeng et al. (2025) further assume that the true features evolve according to a linear dynamical system with additive Gaussian noise. Park& & Faradonbeh (2022; 2024) and Zeng et al. (2025) construct the observed features as emissions from the true features via a known linear mapping, also corrupted by additive Gaussian noise, whereas Kim et al. (2023a) first corrupt the true features with Gaussian noise and then generate the observed features by masking elements of the corrupted features following unknown Bernoulli distribution. In addition, all of these approaches aim to recover the true features: Park & Faradonbeh (2022; 2024) introduce a known decoder mapping from the observed features to the corresponding latent features; Kim et al. (2023a) leverage Bayesian oracle strategy for estimation; and Zeng et al. (2025) estimate the true features using a Kalman filter. In contrast, our setting imposes no structural assumptions on either the observed or latent features, making the problem more general and challenging than those addressed in the aforementioned works. Furthermore. our approach does not attempt to recover any information related to latent features. Instead, we compensate for the lack of reward information due to unobserved features, in the sense that we project the inaccessible portion of the reward onto the orthogonal complement of the row space spanned by the observed feature vectors.
On the other hand, Tennenholtz et al. (2021) assume that partially observed features are available as an offline dataset, and leverage the dataset to recover up to L dimensions of the d-dimensional true features, where L < d is the dimension of the partially observed features. This setting is different from ours in which partial observability arises naturally and no offline access is available. In their framework, the correlation between the observed and unobserved features is used to model the
13

---

Lincar Bandits with Partially Observable Features
relationship between the estimator based the observed features and that based on the features, which requires further estimation of the unknown correlation. In contrast, our method is agnostic such correlation, which makes our approach more practical. Moreover, we exploit the observed features via feature augmentation and DR estimation, resulting in a faster convergence rate of regret compared to their UCBB-bsed approach.
B. Detailed Experimental Setup
For both scenarios, the cestures--inludingg the true features Za. observed features Xg. and unobserved features u. are constructed differently based the relationship between the row space spanned by the observed features, R(X), and the row space spanned by the unobserved features, R (U). In Case the general case, the true features Zu for each arm [K] are sampled from (0, Ia,). ), and the observed features X, are obtained by truncating the first d elements of 2g. following the definition given in Eq. (1).
In Cases and 3, on the other hand, the features are generated in a way to explicitly reflect the inclusion relationship between R(X) and R(U), Particularly, in Case 2, where R(U) S R(X), the observed features X, are sampled from (0, Ia) for each a [K]. Then, we generate coefficient matrix Cu E id. where each element is sampled from Unif(-1, 1), and construct Ua by computing u, = Cu This construction ensures that R(U) lies within R(X). In Case 3, where (XX) R().. reverse the process by sampling ua (O, generating Cx Rdxd from Uni 1), and we set X = Cxu,, Ua. thereby ensuring R(X)= S R(U). In both Case 2 and Case 3, the true features Za are formed by concatenating Xa and U..
After the construction of the features, the orthogonal basis vectors [b] b bb_a) are derived via singular value de- composition (SVD) on the observed feature matrix X, ensuring orthogonality to R(X). These basis vectors are linearly concatenated to X to form the augmented feature matrix. The reward parameter 0, E R is sampled from the uniform distribution (nif(-1/2,1) 1/2), and the rewards generated via dot products following the definition Eq. (2). The coupling probability p. hyperparameter used in the sampling distribution of ā₁ is set to 0.6 (see Eq. (9)). The confidence parameter 5, which is also a hyperparameter, is set to 10 and the total decision horizon is T 1200.
Throughout the experiments, we fix the number of arms at K = 30 and the dimensionality of the true features d₂ = 35. Furthermore, to accommodate both partial and full observability, we set dg 2 d. Specifically,
Scenario 1, is set to
[d./2] = 17, indicating that only about half of the full feature space is observable to the agent. In Scenario 2, on the other hand, set d = 2K 60 and d d, implying that latent features allows evaluate algorithm in the case where d > K. For each of the three structural cases (i.e., the relationships between RX) and R(U) considered under both scenarios, we conduct five independent trials using different random seeds. The results are presented in terms of the sample mean and one standard deviation of the cumulative regret.
absent. The setup of the second scenario also
C. Robust to Latent Feature Algorithm with Ridge Estimator
Our Doubly robust (DR) ridge estimator is defined as follows:
Ph = Σ T(M+) Σ
X + I
Σ
T(M+) Σ aE(K]
XaHlat
(12)
[E[K]
where No.r is the DR pseudo reward:
T(ā aa)
Va.1 = x p
(Ya,t - (n!))
Du.
and the imputation estimator ü& is defined as
t Ex.,
R i
X
pIx
Xa, Yay.r
(13)
ar
The following theorem shows that this Ridge estimator is consistent, meaning it converges to the true parameter μ,, with high probability as the agent interacts with the environment.
14

---

Lincar Bandits with Partially Observable Features
Algorithm 2 Robust to Latent Feature with Ridge Estimator (RoLF-Ridge)
INPUT: Observed features (x, a E [ coupling probability p (1/2, 1). confidence parameter d 0.
2: Initialize Po Ox, exploration phase & 0 and exploration factor C. 32(1 -2 ???
3: Find orthogonal basis {b} ..... bk- b a C R(X)+ and construct (xa [K]].
4: for ( 1, 1, do
5: if [&r] C. log(2tt)))) then
6: Randomly sample a, uniformly over [K] and & = E U (t).
7: else
8:
Compute ā. == arg max X 11-1-
9:
end if
10:
while de # a, and count s Pr do
11:
Sample de with P(a, = (x)
(1-1/2) and P((a k) = 1-1122/ -
1), 4k: #**0 a
12:
Sample â according to Eq. (9).
13:
count = count + 1.
14:
end while
Play ag and observe yo
if ar + dr then Rt
R Set ft 11
17:
18: else
Update ū. R following Eq. (12) with Fo,t and update ju following Eq. (13).
19:
20:
end if
21:
end for
Theorem 4 (Consistency of the DR Ridge estimator). For each t, let & S [t] denote an exploration phase such that for each + E & the action O, is sampled uniformly over [K]. Assume that ||,,, S and | S for all a E [K]. Then with probability at least 35,
2 (a p.ll
1+1 Klog
max
X
(1L
K
+ VKK
aE[K] [E]
Vi p
for all rounds such that [&g] 2 32(1 - p) p)pp)22'' log(2Kt2
With & = O(K2 log Kt) exploration rounds, the DR Ridge estimator achieves an O ((VK/t) convergence rate over all K rewards. This is possible because the DR rswudd-rewards defined in Eq. (10) impute the missing rewards for all arms E [K] using x, ft. based on the samples collected during the exploration phase, & With this convergence guarantee, we establish regret bound for RoLF-u RoLF-Ridge, which is an adaptation of Algorithm I using the Ridge estimator.
Theorem (Regret bound for Ridge RoLF). Suppose ||p.1l S and [zll S for all a E [K]. For ô E (0, with probability least 46, the cumulative regret of the proposed algorithm using the DR Ridge estimator is bounded by
32K
2dT
2
4vT K-1 + 48+8VKK
T log 8 +1).
Reg(T) < (1-p)2 log
+ +2
2T log
log
+
p
The first and second terms come from the distribution of a,, which is combination of the 1-122/grreedy policy and resampling up to P: := log((t 1)2 / log(1/p) trials. The third term determined by the size of the exploration set, &,, while the last term arises from the estimation error bounded by the DR estimator as described in Theorem 4. The hyperparameter p (1/2, balances the size of the exploration set in the third term and the estimation error in the last term. Overall, the regret is O KKT which shows significant improvement compared to the regret lower bound in Theorem 1 for any linear bandit algorithm that does not account for unobserved features and unobserved rewards.
D. A Modified Algorithm for Time- Varying Observed Features
In this section, we define the problem of linear bandits with partially observable features under a setting where the observed features vary over time, describe proposed method, and provide theoretical guarantees.
15

---

Lincar Bandits with Partially Observable Features
D.I. Problem Formulation
Let ,i, xK, denote the observed features and ui..... uk denote the unobserved features. Now the observed features arbitrarily change over but the unobserved features are fixed over time. When the algorithm selects an dz, the reward is
Va (Xai,t: 0 + (Maz) 0()) E2:
where E, Sub-Gaussian noise that follows Assumption 1. The expected reward of each arm is stable over time, where MAB algorithms without using features are applicable for achieving a ( /TT) regret bound. When the observed features vary over time, the expected reward of each arm Elya,,t] (xa,.t: 0 + (ua,: ( also arbitrarily changes over time, and MAB algorithms suffer regret linear in T. To our knowledge, there is no other work that addresses this challenging setting.
D.2. Proposed Method: Orthogonal Basis Augmentation
We address the problem by augmenting standard basis e ......, ek in K to estimate bias caused by the unobserved features. Let Xa.t = e Xx el ... ex] ex. E dR and let Aa == (ua, 0! denote the bias that stems from the latent features. Then,
Va.t (x ( + (ud. 0l t
= (e [x el ... ex], 10 A Ax]) +
Therefore, applying the RoLF-Ridge algorithm the augmented features Ra,t == e (x, el ... ek] yields the following regret bound.
Theorem 6 (Regret bound for Ridge-RoLF- with time-varying observed features). the observed features are vary over time, then for any 8 (0, 1), with probability at least 1- 46, the cumulative regret of the proposed algorithm Ridge-RoLF using DR Ridge estimator is bounded by
2vT d K
32(K + d)² p)2 log
2(K + d)T
T 8 +1
Reg(T) <48
+ (d((+++ KYT
log
8
The proof follows similar arguments given in Theorem 5 and is therefore omitted. The resulting regret bound achieves a rate ((v(d + K)T), which, to the best our knowledge, is the first sublinear regret guarantee for partially observable linear bandits (as well as misspecified linear bandits) with arbitrarily time-varying observed features.
E. Missing Proofs
E.1. Proof of Theorem
Throughout this paper, we consider a bandit problem where the agent observes only a subset of the reward-generatin generating feature vector and cannot access or estimate the unobserved portion. If the agent uses online decision-making algorithms that rely solely on observed features, as defined in Definition 1, the resulting issue can be interpreted as a model misspecification. Therefore, in this theorem, we present problem instance where "misspecified" algorithms, considering only observed features, may incur regret that grows linearly in T.
Following the statement of Theorem 1, assume that d = d, 1, which means d, 2. Given the true feature set 2 {[1, 3] [2, 19/4]"] }. let the first element of each vector is observed to the agent; while the second element remains 21 = 3 and uy u2 = 19/4. We set the true parameter as 0. E _ [2, - meaning (( -(*) and ((a) of -1. Using the reward function from Section 3.2 and
unobserved. This results in X1 = z = 1, X2 = = 2,
considering Assumption 1, the expected reward for each arm is given by
= E [ = z zTTo. 0. = 2.0 + w Vie E {1,2}.
Plugging the values in, the true mean reward for each arm is directly computed as 71 2 - and 72 = 4 - -19/4 = -3/4, which satisfies the assumption that its absolute value does not exceed (Section 3.2), and since ?1 < 72, arm 2 is the
16

---

Lincar Bandits with Partially Observable Features
optimal action. We further assume that the total learning horizon T 2566² max (log 2, (1/())))) for any 8' (0,1/2), where is the Gau-Gaa parameter of the reward noise.
For brevity, we denote the latent reward components as 9i == 055 and 02 == uz(! yielding 9i = -3 and 92 = - 19/4. Since "22 # 2n and [gs| 2 3 > 0 for all E {1, our problem setup satisfies the "large deviation" criterion Definition I and Theorem 2 of Ghosh et al. (2017), with I and 3 = O. Applying the theorem, it follows that OFUL (Abbasi-yadee yabkoii-yadkori et al., 2011) suffers linear regret in this problem instance, i.e., ((T).. Motivated by this result, further show that LinTS (Agrawal & Goyal, 2013) is similarly affected.
For each round E [T], LinTS estimates the true parameter using the ridge estimator, given by:
0.- = (X X + AId) A Y) Y))
(X, X, + AL.) - (x,0 ( + gt + 61)
= - - AV. 0 V x g: + V, X, E
(14)
where X, : (x], ...., xI,) E Rixd a matrix containing features chosen up to round t, Y, == (Yay No:) E IR vector of observed rewards, and E, == (cI....,c ,......,,E)) (e) R' contains noise attached each reward. Unlike a typical ridge estimator, here the term gi == (Bar.-.-,
TR! the vector containing the latent portion of observed rewards is introduced due to model misspecification. Note that V. (X, X, ALa) 0.
For this problem instance, since d = 1, Eq. (14) is equivalent to:
Et EapEr
0, (00)
Fa-Ju- 2 a E
Σ
- x2 +1
1. Note that also denote O, and (0)) by Og and 9! respectively, since both are scalars, Hence,
where we assume À the estimation error is computed as:
())
Σ 9a-
Σt=1 E Σ
0, 0
(15)
Σ
22 +
Σt=
+1
x2 +1
Let N1 and N₂ denote the number of times arms 1 and 2 have been played up to round f, respectively. This implies that N1 + N2 = L. Then, for the numerator of the second term, since
Fa Sa, = (91 + .... + 91 + 2g2 + .... + 292) N1 + N2,
Ni
N₂
we can observe that
Ta Ma, = N1 + 22
2 N + +2gN2
NN + 2g(t N1)
= 2gt gN1
2 gl
(::N5
19
where g = min = 19/4. which implies that Σx= Ia.9a- = (t)). For the denominator, Σ'= 2. + 1. which
grows at a rate of (t), implying that the second term of the hight-hand side in Eq. (15) is @(1), and that 0 is not consistent
since it does not converge to (( as t + xc.
For arm 2, which is optimal, to be selected in round t under LinTS, the condition 2z0, 2 21 must hold, where 0, N (0., v2 ( 2ă, + +))- Given the assumptions that # = 1 and 22 = 2, arm 2 is selected whenever 0, 2 0.
17

---

Lincar Bandits with Partially Observable Features
Thus, for arm to be chosen, we require 0g < O. We will show that the probability of 02 < 0 does diminish sufficiently to be ignored, even when the agent plays for sufficiently large amount of time. To clarify, let define the two events
Bj = [0, 2 0} and E = { 2 0}. We revisit Eq. (14) as follows:
0. Σ == Va.
E Ia,
Er Cia Er
0.
+
Σ 2e +1
Σ Ei=1 I ar
Σ -- x
+
< ( N1 + Ng
No,
(:001) >0) 0)
+ N1 + 4N2 +1
Ni + 4.22 +1
< (
N + +292N2
2
+
(16)
N1 + 4N2 +1
N1 + 4N2 +
where the last inequality holds since E Er I m1 Fa Σ Er and maX Ta 2. For the second term of Eq. (16), for t 2 19,
N1 + 292N22
-3N1 N₂ 2
N1 4N2 +1
N1 + 4.2 +1
19 (N1 + 4N2)
S
8
N1 + 4N₂ +1
19
19/8
8 + 3N22 +1
19 19
+
8 8t"
which is upper bounded by -9/4. This bound is followed by:
0. s (
91 N1 N1 + 2g2
Σ G
+
N1 + 4N2 +1
N1 + 4N₂ +1
9
2
2
(17)
4
t 3.2
T=1
1
$ - + Cr.
4
r=1
Thus, we have the following:
P(O, > 0) P
( 1
4 +
Σ 6 > 0 = P
1
2
G
1)
Since e, is an IID sub- aab-Gaussian random variable for all E [t], by applying Hoeffding inequality we obtain: 0) < exp (-t/128o²). Given this, we now bound the probability of the event Lig:
P(E P(E Eg) +(EE n ET)
= -PE EØ) P(E3) + P(E Eg) P(E))
P(O0 2 1 0, 2 0) P(O,, 2 0) + P(0. 20 0, < PPO, <)
128 ) + P( 2 0 0 < <)) I cxp
(18)
Since the second term of Eq. (18) is calculated under a Gaussian distribution, thus its value does not exceed 1/2 for all
t E [T], it follows that ((E 2 1/2 exp (-1/12800)) Note that the total decision horizon T > 2560 log(1 (1/8",, thus
18

---

Lincar Bandits with Partially Observable Features
for any / > 128o² (1g0)) have P(Eg) > 1/2 - 8'. This implies that for rounds beyond 7/2, the suboptimal arm will be played at least (1/2- - 82 times for any 8' E (0, 1/2), thus incurring
1 2
T 2
E RegLLinss (T) 2 ( - 71)
8'
4
2
2
For OFUL, we also present another analysis that does not require the assumption that the suboptimal arm played for initial t rounds, which is taken in Theorem 2 of Ghosh et al. (2017). The optimal arm, arm is selected when
x2
I1
(19)
V 1 +
x2
1++
- 7- o+
where 0, is the same ridge estimator as in LinTS. The inequality Eq. (19) is equivalent to 0, (1 E1=1 1 which implies 0, 1/v2t. By Eq. (17),
P
8
1
I
+
2
Σ
1
21
4
211
T=1
2
P
Σ
2t
4
7=1
2
cxp (- 128002
$ P
(-12802)
4
Thus, fort 2 128o² log 2, the probability of selecting arm 2 is less than 1/2 and for T 256x2 log2.
1 T
T
E [eegro.. (T) (72 71)
2
2 16'
and the algorithm suffers expected regret linear in T.
E.2. Proof of Theorem 2
Let V, Σt= EaeiK] X Then
max KE|K]
X (P
11)l
Σ KE[K]
XJ (fst = - lll.
To use Lemma 3, we prove a bound for E ExE(K] (Ja.r X (4) Xalloo. By definition of Vo.r.
(Norr 1.. Xa
[=10E|K]
(1
I[ār =a)
I(ā,
aa) =a)
Σ
XaXa -T (ity (r.)
(Yarr X H.) xa
Da.7
Par
dE|K]
I(0r =a)
1(0, - a)
Σ
1
Xx (ith' 14.)
+
(yarr X H.. xo
(20)
Qa.7
Oar
r=
r=laE[K]
19

---

Lincar Bandits with Partially Observable Features
With probability least 1 6/(r + 1)²; the event M, happens for all 2 and obtain pair of matching sample ä and 0,. Under Mr, the second term in Eq. (20) is equal to,
I(ā, = a)
Iia,, = a) (ya.r - -x v..) Xo
Σ r=
(yarr - X (e,) Xa
Pa,t
Da.t
7=1 [K[
Xar
Because ||v|l0o = ma lo v| for any v E Rdd
1
xa=
max p a K
GoO Xay
Applying Lemma 1, with probability at least - 6/12,
max K
T e Xu-
S max 0 aE[K]
2
(e xar)
'log x
2K12
2Kt
max 0 aε[K]
Te
Σ Xa, XT
ea log
2Kt²
< max [E[R]
2e Viea log
8
2KP
max
2t log
where the last equality follows by the definition 2
max K] e (Eee[K) XxX, )ea Thus,
max
1
Σ
00
2t
2Kt
(21)
p
p
8
x
Now we turn the first term in Eq. (20). Define A, = Ei=1 EoE[K] I(ā, x0, Then the first term is rearranged
I(ā, = =a)
Σ Σ
NaXo (it me)) -M.)
=I(Ve Ai) (i! - H.)l
(22)
Do.
r=1 [E[K]
Since lov = maxiedd]
lc. v| for any V E Rd.
[[V, - Ar) (1+ - p4.) 11.00
le (V, - -A)) (A) - 1e.)1
= max [k(K]
T (V, A.) A, -1/2 |||||| [1lit 14 -M,llA,"
< max aE[K]
Because ji! is minimizer of Eq. (8), by Lemma 3 and Eq. (21),
4aōmax p
21(d + dn) log(2K(2/8)
j Malla,
Amin (A,)
By Corollary I, with E (0. 1) to be determined later, for t > Sc -2-2(1 -2 loggo((2))) /8), with probability least
1 1- 18/22
Ik - V. 1/2 A. V. 1/2 S.
(23)
20

---

Lincar Bandits with Partially Observable Features
Eq. (23) implies (1 - I V, V. 1/2 and (1 v) 3 A,. Thus,
mox p
2t(d + dn) (2Kt//))
400max
2(d + dn. (2Kt2//)
j -M111
(1- em (V,) pon
1-6
and Eq. (22) is bounded by,
(V. - Ad) (it (4))
T e (V. A,) A,) 1/2
m
2(d + dn) (ogl loglooo(2)))) (2K(215)
max iE|K]
po
1-c
max
p((1 e (v, 1/2
400
V 2(d + dh) log
2Kt
(24)
[
e)o
8
For the first term in Eq. (24), we have that
(V,- - A.) V,) V 1/2
e V! 1/2 V/ 1/2 (V, - AA)
1/2
max E
e
max KE
S mmxx Vt V A.V, 1/2
S mmax Vic,
where the last inequality holds due Eq. (23). Combining this result with Eq. (24), we obtain that
I(V. - Av) (at m4.) 1lm0 S 4e00 max
2kt²
21(d + d,) log
p(1 c)omin
5
Setting e 1/22 min/ max yields that 1 2 1/2 and that
IIV, Ar) (it mm)
max
21
d + dn
log
2K12
K
mm
2Kt
21 log
Now we conclude that for / 22 K3
min F (1- p) 2 log 22)22/8).
Σ
Taar - X 122
Jomax
21 log 8
2Kt²
KE[K]
by Lemma 3 and taking union bound on the both terms Eq. (20), with probability least -25/t2
SoTmax
2f(d + dr) log(2K(20))
Saāmax pormi
2kt²
1n L
1l <
2(d + dr) log
Amin (V,)
8
which completes the proof.
E.3. Proof of Theorem
Since we have shown that the reward defined in Eq. (2) is equivalent to its form obtained via the projection and augmentation strategy in Eq. (7), henceforth calculate the regret bound based on Eq. (7). Under the assumption that the expected reward is bounded by 1 (Section 3.2), the instantaneous regret EE- [y,1, E,- [Baa, is bounded above by 2 for any E [Z'] and that the number of rounds for the exploration phase satisfies |Er|
< 83 K 3 log((2TT 25). Given these bounds, the
21

---

Lincar Bandits with Partially Observable Features
cumulative regret is bounded as:
Reg( T
E2 [ye,e] - Be-1(Baa,11)
1=1
Σ
[E [1 19,,1] - Ei-1(Var, +
Σ (Be-1lVe,c) BB- 183a,))))
1EET
1E(T)\ET
2KT
$2.8 - p)-
2 log
Σ (L:-1 - -IE--1 (y
8
2KT
= 2. =2.8* - p) 2lo
Σ
[T(a = (Ra-(1e Ee (y-1(ya,,)))
5
(25)
Σ
[I(a +
1x-1(aar)))
(EITNVEr
We first consider the second term of Eq. (25). By Theorem 2, on the event far = =ū}h
Ex-18 11-1(Waa.
xx, H. - Ka. pe
XT u4 + xx. po6 X pi- + X2 1i-1 X3 aL
Lh
X2 M, 82, I. 1i-1
xT. (n. -ml-1) x (14, p + xx_ pui
max oE [K]
_ (u, p x p
X M1-1
X2 (1t, - -pt-
max [E[K]
1600
2(d dn)
2Kt
log
mi
with probability at least 1 - 2 for each t E (7) \ Er. Summing over t and applying union bound, we obtain that, with probability at least 1 - 46,
3200 max
2KT2
Σ
(T(a+ Te) (R,-1 [0+.e] E. (V) s
2(d dr) log 8
(26)
poin
EETT
For the last term of Eq. (25),
Σ
(I(ar & ā.) (E, (Er-ilye,r E, I
2 Σ (E[T]
T(a # ā.) P (a, +ā,) +P (a, # az)
(:: EE- 11-1yaand S 2)
2
4VT
$ 2
2T log
48.
(27)
8
K
1
where the first term in Eq. (27) holds with probability at least 1 8 by Hoeffding's inequality, and the remaining terms follow from Lemma 5. Taking a union bound over Eq. (26), Eq. (27), and Mr, we obtain, with probability at least 65,
2KT
4VT
Reg(T) 82
K
-2
log
8
K
2
320 max
2KT2
+ +22/
2T log
+ 48
2(d + TT)
8
pomii
8
which concludes the proof.
22

---

Lincar Bandits with Partially Observable Features
E.4. Proof of Theorem
Let Vr == E==1 1(M,) EmE[K] 2oXo Ix and v= Er=1 EaE[K] LaXa + Ix. By definition of p. presented in Eq. (12),
X (fL M.) = & V
1(M)) Σ
Xa (Ja,r - H.) Me
aE[K]
By definition of the pseudo-rewards,
[( =
X (ite -H,) + T( = a)
Yarr X2 14,
Cr.
P
Pa,t
Let Ar = Er= (MM)) [aE(K]
[(ā,= T + 1x and A. == Et=l Ene(K]
0a, Xax
[āa==) m T
XxX + Ix Then,
Oo.t
x (Pr R m.) x V. (v. A.) (at m,) + Σ I(M) Σ
[( = =a)
%acr Mx s:
(28)
Par
aE|K]
By definition of the imputation estimator j4,
f u4
Xa, Xa, + +lk
Σ
X2. Ey PH4
Xa x T + IK
Ra, Er M.
Darit
Parit
l(, Xa, Xa,
+Ix
Σ Xa, er - 11,
PO.r
[E[
where the second equality holds because dan. and the coupling event dr= Thus,
Xa Er M ).)
it R
p.
A
A,
Plugging in (28),
{ (v.- A."
t
1
I(ā, = a)
__ (p f p.) = x V.'
Σ
Xu, Er - M.
+ I(,)
Dur xalt - Hx
p
RE[R]
Under the coupling event, Ä, Ar, V. V, and EnE[K] 2o,tiia a)Za = -p..pp It follows that
X (p. R
-,.) v 1 {(V, A,) [Ik]
Σ
1
Ray Er pb
p
xI 1/2 VV//"A, V.
Xn, et 11,
p
Taking absolute value on both sides, by Cauchy-Schwarz. inequality.
<E(K] max X (T 14.)l S max
IlVl A,
/V -
1
Xa, tr ue m.
(29)
[E[K]
p
23

---

Lincar Bandits with Partially Observable Features
Corollary implies that, for / Se 8 -)- 2K² 1og(2K(2/0), with e to be determined later,
Ix - V A. 1/2 3 elk,
with probability at least - 8 for all t 1. Rearranging terms gives
v/ A 1 (1 Ix-
Combining this with Eq. (29),
max [K] | xlll
max [
Xa (Dt, m.,)l 5
Σ
- Xax Er 1x vi
1-6
m
|/olll.''
Σ
Xa, Eg
+ lll..lll.
1-c
V.7
where the last inequality follows from the triangle inequality. Note that V. is deterministic, both V. and X +IK are positive definite, and V ž Ei= Xa, least 1 8,
+ Ix. Then, by Lemma 9 of (Abbasi-yadkorii et al., 201 1), with probability
Σ Xa,Cr c
Xay E+
Vi
r=1
(Ei-) Na XJ, +Ix) +Ix)
det D1 --= Na, XT 1/2
S o
2 log
8
det det(E
XT Ix) Xx,
s <ov1n log
5
Applying Lemma 10 of Abbasi-yadkori al. (2011) yields
K
Tr Et Ka.Xa,
+ K
det Σ Xx, XJ. + Ix
tmax
1R ll2 + K
K
{t + 11*
for all 2 1, where the last inequality holds by |اx 1l2 V Xu, 1100
K. Hence,
I+1
XarEr Ex
So
K log
v.1
which follows that,
max [K]
|
(+1
[ (it - -.)1 [E[K]
max
V K log
+ -111e, 1l:st
1 1
++1 K log
< Vt
+ llu.llve
-
p
Since || S 1|lalla 5 KK, choosing 1/2 completes the proof.
24

---

Lincar Bandits with Partially Observable Features
E.5. Proof of Theorem
Similar to the proof of Theorem 3 (Appendix E.3), the instantaneous regret is bounded above by 2 for any t [T', and the number of rounds for the exploration phase satisfies Erl I 32(1 p) RK² log(2dT /5). Consequently, the cumulative regret is bounded above follows:
2dT
Reg(T) S 32(1 2? log
E 12-1 [Wr.e] - 1E-- [yar.s]
NE[T]VEr
2dT
= =32(1 p) 22 log
Σ
(I(a = ae)
6
NE[T]VET
(30)
{I(a, + ã.) (Bx-1
Ex- 11-1))
(E[TIVET
We first consider the second term in Eq. (30). On the event {at āet.
[yv.el EE,- [v
x 14, X Me
x ,4 + x,, pc--1 - X,, 2 + X, Rt
ph-
xx Rt
p1-1
Xx, M+
X1. (u. -x [6
X (u, -pap1))
+ +x,,
11
11
8 1
max
x
[4, -
-1 )
R
+ [x___ R
p
T -
xx, 1
aE [K]
x |4, -1 11-1)
max kE(K]
4 VI
K log t 8
+ vK
with probability least 1 - 36, for all t such that t EEel (Theorem 4). Summing gives, with probability least 1 - 35.
Σ (T(a, = a.) (Te E S 8V KT
log T
+1)
(31)
EE(T]
For the last term in Eq. (30), we have that
Σ
(T(a # @.) (R2 (E2-1(Un,a) E, EE-1 (yc
2
Σ
I(aa * ā.)
(a: * a.) +P (a # a+)
(E(T)
2
4VT
< 2/2
27 log
K-1 + 46,
(32)
where the first term in Eq. (32) holds with probability least 1 5 by Hoeffding's inequality, and the remaining terms follow from Lemma 5. Finally, by taking union bound over Eq. (31) and Eq. (32), obtain, with probability least 1 48,
32K² log + +2 2T 2o
2dT2
4VT + 45 +8 +
T V log 8 +1).
Reg(T) < (1 11-p1 p)2
+
p
which completes the proof.
F. Algorithm-Agnostic Lower Bound of Regret Ignoring Unobserved Features
In this section, extending our argument in Theorem 1, we show that there exists problem instance such that linear bandit algorithms relying solely on observed features can incur regret that grows linearly in T. We begin by formally defining such algorithms.
25

---

Lincar Bandits with Partially Observable Features
Definition (Policy dependent on observed features). For each E (T), let n.. Rd x R [0, 1] be a policy that maps
an observed feature vector {xa a E [K]], given past reward observations (Ya,,s E [t 1]}, to a probability of selection. Then the policy ne is dependent only observed features if, for any Youdsrr. -dt- it holds that x1 X2 implies Ty (xxllaa......... V....r,- = ne 2x.x.lle.........aa... V.a.......)......
For instance, the UCB and Thompson sampling-base based policies for linear bandits (with observed features), considered in Theorem 1, satisfy Definition I, as they assign the same selection probability as long as the observed features are the same. In contrast, policies in MAB algorithms (which disregard observed features) may assign different selection probabilities even when the observed features are equal, and thus are not dependent on the observed features. In the theorem below, we particularly provide lower bound for algorithms that employ policies that are dependent on the observed features.
Theorem 7 (Regret Lower Bound under Policies Dependent on Observed Features). For any algorithm 11 := ( TT)
that consists of the policies {mT : E [T]} that are dependent on observed features, there exists set of features , .
and a parameter 0, E Rd= such that the cumulative regrel
T 6
Regn (T, Z1.
Z1.
ZK)
Proof. We start the proof by providing a detailed account of the scenario described in the theorem. Without loss of generality, we consider the case where K = 3. As stated in the theorem, a, represents the index of the optimal action when considering the entire reward, including both observed and latent components. In contrast, a, denotes the index of the optimal action when considering only the observed components. We introduce an additional notation, a', which refers to an action whose observed features are identical to those of a.. but with distinct latent component. Specifically, this implies that a' * a, and v.,' # Pa,, but X Xa.. By definition of the policy T. that depends on the observed features, ne (xa.) ) = Te. <x(Xx') and the probability of selecting the optimal arm is गe Te( (X..) S 1/2.
Taking this scenario into account, the observed part of the features associated with a,, a', and O are defined as follows:
1
Xa.
Xx
Xa.
2
Additionally, we define the unobserved feature vectors for actions a,, a', and a follows:
= [1,....1]] 1]T ua == [-1,..., Ua, = (-1,
where in ua., the number of I's and -1's are equal. This ensures that the scenario aligns with the assumption imposed on the feature vectors throughout this paper. We further define the true parameter as follows:
1
2 3d,
2
0.
Rdd.
3d
3d
3dl
2/3d,] E R..... Note that it is straightforward to verify that (z.,, 0.)l < 1, thereby satisfying the assumption on the mean reward (Section 3.2). With this established, we can also observe that the expected rewards for the three actions are defined as:
thus it follows that 0 = [1/3d..... 1/,....,1/3d]]
1/3d] E Rd and =
(Zo., O.) (Xo. !( + (uo. O(n)
1
2
1
+
6
2
(za'; 0.) = (Xa': 0(0)} + (ua', 0 (u))
1
2
5
6
3
6'
(Za,, 0.) = (Xa,, ((0)) + (ua,, 0(w)) = 0=
6'
respectively, and it is straightforward to verify that (zo., 0-) (Z..: 0.) = 2/3 > 0 and that (Za,, (za' 0.) = 4/3 > 0.
which confirms that a, is optimal when considering the full feature set.
At each round & [T'] for any policy n. satisfying Definition we have
Te (Xa, yay.1,.... 1.t-1, = Te Tx( 1ya,, ... Day (o--1,
26

---

Lincar Bandits with Partially Observable Features
which implies P(a, a.) P( d') and
P(a: a.) P( a') P(a: a.) 1 P(a d') = P(a = a.),
hence the probability of selecting an optimal arm cannot exceed 1/2. Thus, the expected regret,
T
Regn (T, 0x, Zo. Zoo' Zo.) 2
( 2
1
Σ
Pl + a+) 2 6'
6
which completes the proof.
G. Technical Lemmas
Lemma 1. (Exponential martingale inequality) If martingale (X;; 2 0), adapted to filtration Fr. satisfie E( & exp(X2o? (2) for some constant oe for all t, then for any a 2 0.
a
P( Xol
N a) S 2exp
2 2 T
Thus, with probability least 5,
T
[X - Xols
of log
t=1
G.1. A Hoeffding bound for Matrices
Lemma 2. Let (M, T { be Tedxd stochastic process adapted to the filtration {F, : E [t]}. ie., M, is F.- measurable for E [t]. Suppose that the matrix M, is symmelric and the eigenvalues of the difference M, - -E[M, [ lie in [-b, b) for some 0. Then for x > 0,
222
Σ M, - E,M F
2 x
< 2d exp
2th
Proof. The proof adapts Hoeffding's inequality to a matrix stochastic process, following the argument Tropp (2012). Let D, M, E[M, F--I]. 1]. Then, for 0,
Σ
D
S
Amax
Σ
D,
2 r
+ IP
Amax
-E
ΣED
D, 2Φ
(33)
r=1
We bound the first term of Eq. (33); a similar argument applics to the second term. For any v > 0,
}
}
P Amax
ΣD, D,
2 x
< P
exp
udmax
ΣD,
2 u
Se e E
exp
vd
ΣD, D,
r=1
r=1
Since D - D, is real symmetric matrix,
ΣD.
}
> D. )} <
D.
1
exp
Vdmaax
Amax
exp
exp
v > D-
27

---

Lincar Bandits with Partially Observable Features
where the last inequality holds since exp(v Σx= D,) has nonnegative eigenvalues. Taking expectations both sides yields
)
ΣD,
E
exp
Udmax
S
E
Tr
exp
D
r=
7=1
TrE
exp
D,
Trl
exp
Σ
D
log (ogeep((DD))
By Lieb's theorem (Tropp. 2015), the map D - Trexp log D) is concave over the set of symmetric positive definite matrices for any symmetric positive definite H. Applying Jensen's inequality, we obtain
L- Σ D. + logexp(uD.))
L-1 Σ
log E [exp(vxxD F--1))
TrE
exp
s TrlE
exp
v
D,
(34)
By convexity of ex and Hoeffding's 's lemma, for all [-b,
pm
b
+
x
+
mb
2h
2h
Since the eigenvalues of D, lie within [-b, b). follows that
e-
e
[expp(eD:)) Fi-1]
(bl
D.)
(De + (Id)
Fi-1
26
2b
+
eb
Id
2
22
exp(
2 Id.
Now we recursively upper bound Eq. (34) as follows:
H
exp
vdmax
ΣD, D.
TrE
exp
D, + log E (x
TrE
exp
D,
L
2-2 D, +
b2b²
La + log E [exp(uD,-1) 1)1 F Fi-a))
TrE
exp
v
1-2 Σ
20
TrE
exp
v
D +
I
1u212 )a
Trexp
2
tv
exp
Tr (I,
11u212
dexp
28

---

Lincar Bandits with Partially Observable Features
Thus have
IP
mmxx
Σ
Dr
2
I exep
(-uxt +
tu
2
Minimizing over > 0 gives x/ atb² and
t ΣD,
x²
IP
Amax
Dr
2 x
dexp
2112
T=
which proves the lemma.
G.2. A Bound for the Gram Matrix
The Hoeffding bound for matrices (Lemma 2) implics the following bound for the two Gram matrices A, == Er= Xa, Xar and V, : Σi= Lne(k] 8,80
Corollary 1. For any e E (0,1) 1) and 86 2c - p) 122 log(2K(2/)) /8), with probability at least 1 - 8/12,
| - 1.1 A, 1/2
S.
Proof. Note that
V 1/2 A, V, II 1-2/2 1/2
I(a, = a)
-
8ax
V V.1/22 1/2
Da.T
r=
and the martingale difference matrix for each E [4]
Σ RE[K]
I(ā, =() a0) -1 1) V, x Xx V 1/2
Σ
[(a, a)
-1
1
max aE(K]
V
1/2 ~ X
1/2
Da.r
Da.
aE[K]
K 1
K
max aE[K]
V
1/2
V
1/2
2
2K
|T,, v.
1- p RE[K]
2K
$ 1 p t.
Note that the second inequality holds under the assumption p (1/2, 1), which implies Φ5,1 S (K 1)/(1 -p), and the last inequality is obtained via the Sherman-Morrison formula. By Lemma 2, for 0, we have
s 2K exp (-11 (-1--)) (1-p)
([ 1/2 A.
1/2
>x) Ix 2
8K2
Setting x E (0, 1), fort 2 8c - p) 2 kx² log (2Kt// /8) with probability at least 1 - 8/t2,
|I - 1, A. V, 1/2 Sec
2
G.3. An error bound for the Lasso estimator
Lemma 3 (An error bound for the Lasso estimator with unrestricted minimum eigenvalue). Let X,T & [4 c [-1, denote the covariates, and let yt = x w + e, for some w E Rd and e, E R. For O, consider the estimator
w
argmin
Σ (vr x xw2 + A A//w/I
W
7=1
29

---

Lincar Bandits with Partially Observable Features
Define S = i E [d] w(i) + 0 and E, = Er= X, Suppose that En has strictly positive minimum eigenvalue and
that Σ exX, S A/2. Then,
0c
2 S
Amin (E.)
Proof. The proof follows a similar structure to Lemma B.4 in Kim et al. (2024). but we provide a new argument for the unrestricted minimum eigenvalue condition. Let X = (x1,-.., xx) denote by (j) the j-th column of X₁ and by ()(j) the j-th entry of w. By definition of Wt.
[-1,1]dxt and e, (x) E R We
X w W.) + ea 12 + A/ _ | + A/[w/11.
which implies
[ (w w. + Al S 2 w) T X, C₁ + A//w|12
S 2/ - w|1 | ex + A/w/I
Al A/|: w|| X w I|,
where the last inequality uses the bound on A. On the left hand side, by triangle inequality,
[well
wi(1))+
+
Σ
2
Σ
(x(( Σ
(1) - w(i)++ +
Σ w())
iES
iES
|
|||
Σ
(1) w(1) Σ
(w((i),
iES
iE(d)S
and for the right-hand side,
[w:-
w|11 Σ
(i)( w(1)+ Σ
[w)()))
iES
sE(d]\s
Plugging in both sides and rearranging the terms,
[ (w w.) 13 < 21
W. - w())-
(35)
iES
Because X X, is positive definite,
Ix (w We) 12 Amin (X, X.)
Σ
(i( - (1))
iES
Amin (X, [S]
Σ
iES
where the last inequality holds by Cauchy-Schward inequality. Plugging in Eq. (35) gives.
|X (w w.) 11 < 2A
(.(1) w())
ies
SS
2A
X (w ww) 1|2
Amin Ex
2x2 S
+
X, (w 12
Amin E,) 2
where the last inequality uses ab < a2/2+ + 62/2. Rearranging the terms,
4
X, (w w: < Xmnin Σ,
which proves the result.
30

---

Lincar Bandits with Partially Observable Features
G.4. Eigenvalue bounds for the Gram matrix.
Lemma 4. For E [ let xa [x] e, Pi.... pK-] E denote augmented features. Then, an eigenvalue of
Eae(K] X,X, is in the following interval
min
Amin
Σ [E|A]
xox
11
max
Amax
Σ
Xa Xa
.1
aE(K]
Proof. Let := (PI..... Px-a) E [K
Because the columns in P are orthogonal each other and to X1, XKx
Ene(K XXx Ene(K) PT
EaelK] x T
Σ xxx
P
[E(R]
Ene(K' X,X
Ene[K] e P IK-d
Eme(K] PTcxx Cax
Ene(K) XaXo Exe(K] PTege X
Ene[K] Xexed P TK-d
EnE(K) XaXa P X
XP
IK-d
Exe(K] Xax
O IK-d
Thus, for any À det( E [ie(K]
[K] X,X, ~Ix) det (ee(k)) xxx
AL)((1 - A)K-d, Solving det det(E (uE(K] Xxx
ALa((1 X)K 0 gives the eigenvalues and the lemma is proved.
G.S. A Bound for the Probability of Exploration
Lemma 5. For each let ā. argmax [] X ir denote the maximizing action based on the estimator i.g Then the action chosen by the resampling scheme in Algorithm I and Algorithm satisfies,
T
2VT
Σ
P(a: a - (K - 1)
+
Proof. Since the algorithm resamples at most times, for fixed / E [7].
Piaa * â.) (fā = a; {ar * a,)) + P (fāz * at} n far + act)
P (ā. = a.) fat * a,)) P(ā. az)
(( = a.) far k))+ P( + at)
for k: + àz,
(36)
resampling
where P(a,- k)) 1///2/(K- 1) and P(ã = a,) p. defined by Algorithm and Eq. (9), respectively. For the first term in Eq. (36), by applying the union bound, we obtain
(ā = ar) n (a+ k)) = (Resampling success at trial m) n {ut = k)}
IP ((Resampling success at trial m3 n {ar k})
((a = k)
Vi(K -1)
31

---

Lincar Bandits with Partially Observable Features
which, combined with Eq. (36), gives
P( # az) 2 VI(K + P(Resampling failure)
By the definition of Pt, the probability that the resampling fails is bounded by 5/(1 1)2. Thus, the probability of the event {ar # ā,} } is
8
P(ae F a.) S V((K-1 +
1)
Summing up over 1 E (T] completes the proof.
32


Reviews:
[{"review_id": "pSjHRabpBV", "reviewer": "Reviewer_tArs", "summary": "This paper studies linear bandits with partially observable features. The authors suggest an epsilon greedy type algorithm based on a doubly robust estimator. A regret bound of the algorithm is provided with supporting numerical experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your valuable feedback and acknowledgment of our contributions. We are happy to address each of your comments.\n\n* **On Descriptions of Notation and Methods**\n    - 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.\n    - 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$.\n* **On Experimental Setups and Comparison with Baselines**\n    - Our experimental setting is the *\"otherwise\"* case in Table 1, where neither $R(X)$ nor $R(U)$ fully contains the other.\n    - 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 $. \n    - 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\n    - 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.\n* **On Regression Equations**\n\n    - 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).\n* **On Unbiasedness of Estimators**\n\n    - 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.\n\n* **Comprehensive Literature Review**\n    * **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.\n    * **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.\n\n\nReference: Xu, Y. and Zeevi (2020), A. Upper counterfactual confidence bounds: a new optimism principle for contextual bandits.", "claims_and_evidence": "The authors claim that the basis of orthogonal space to feature space can be used for the estimation of rewards to fill the absence of information due to partial observability. The reviewer believes that this is convincing.", "methods_and_evaluation_criteria": "The regret is a widely used evaluation criterion. It makes sense.", "theoretical_claims": "I have not checked all proofs. But, the claims make sense and fit my intuition.", "experimental_designs_or_analyses": "The experiment should be more neutral to other benchmark methods. The space of (significant) unobserved vectors should be a small subset of R(X)^t for fair comparisons. If no unobserved vectors are associated with rewards, regret could be worse than other methods due to overfitting, even though the lasso/ridge estimator provides some shrinkage. This part is not fully described, so hard to figure it out.", "relation_to_broader_scientific_literature": "As this work addresses linear bandits (not contextual bandits), for literature review, could you please compare it with others about linear bandits, not with ones about contextual bandits? If no literature about linear bandits is available, the authors should clarify it.", "essential_references_not_discussed": "The following work is similar to this work.\n\nTennenholtz, Guy, et al. \"Bandits with partially observable confounded data.\" Uncertainty in Artificial Intelligence. PMLR, 2021.", "other_strengths_and_weaknesses": "This work's idea and method are great. Also, the quality of English is good. \n\nWeakness:\n\nMethods are not fully described.\nIn (8), what is p and \\delta? How do we determine it?\nCould you please more specifically describe the details about the method, such as the reference of the provided exploration method and the constants C_e log(2Kt^2/\\delta)?", "other_comments_or_suggestions": "NA", "questions_for_authors": "Could you provide more details about the experiment setups, especially the space R(X) and R(U)? Also, could you please provide the regression equations of rewards?\n\nHow (10) is unbiased even though lasso/ridge is used?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "NA"}}, {"review_id": "sLN3pvFSku", "reviewer": "Reviewer_qdeK", "summary": "### ​Problem Setting\nThe paper studies the ​**linear bandit problem with partially observable features**, where rewards depend on a full set of features, but the learner only observes a subset of them. This setting models real-world scenarios (e.g., recommendation systems) where unobserved latent features (e.g., user preferences) influence outcomes. Existing linear bandit algorithms fail here because they either assume full feature observability or impose restrictive structural assumptions (e.g., linear mappings) between observed and latent features. The paper relaxes these assumptions, allowing latent features to have arbitrary relationships with observed ones, and formalizes the problem through geometric relationships between the subspaces spanned by observed and latent features.\n\n---\n\n### Main Algorithmic Ideas\nThe proposed ​**RoLF (Robust to Latent Features)** algorithm addresses partial observability via two key innovations:  \n1. ​**Feature Space Decomposition**: RoLF explicitly decomposes the reward into components spanned by observed features and their orthogonal complement, enabling estimation of both observable and latent effects without prior knowledge of latent dimensions.  \n2. ​**Doubly Robust Estimation**: A novel estimator combines ridge regression on observed features with importance weighting to correct for bias from unobserved factors, ensuring robustness to arbitrary latent feature interference.  \nCritically, RoLF requires no prior knowledge of latent feature properties (dimensions, alignment with observed features) and dynamically adapts to the geometric relationship between feature subspaces.\n\n---\n\n### ​Main Results\n1. ​**Regret Bounds**:  \n   - If observed features span the latent space ($ \\text{span(observed)} \\supseteq \\text{span(latent)} $), RoLF achieves $ \\widetilde{O}(\\sqrt{dT}) $ regret, matching the optimal rate for standard linear bandits.  \n   - If latent features dominate ($ \\text{span(observed)} \\subseteq \\text{span(latent)} $), regret scales as $ \\widetilde{O}(\\sqrt{KT}) $, aligning with multi-armed bandit limits.  \n   - In the general case, regret is $ \\widetilde{O}(\\sqrt{(d + d_h)T}) $, where $d_h$ is the effective latent dimension orthogonal to observed features.  \n2. ​**Empirical Validation**: Experiments confirm RoLF outperforms baseline algorithms when latent features are present.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback on page usage. We will make full use of the page limit and avoid leaving unused space in the revision.\n\n* **On Explanation and Mislocation of Table 1**\n    * 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.\n    * 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)$). \n    * 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). \n    * 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$.  \n    * 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\n* **On Notation of $z\\_{\\star}$ and $z\\_t$**\n    * 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.\n* **Clarification of Theoretical Results**\n    * We appreciate the opportunity to clarify the results regarding $d\\_h$.\n    * 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. \n    * The formal definition of $d\\_h$ is provided in (6) (line 216, the left column). To clarify, $d_h$ is not the \\emph{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)}$. \n    * 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.\n* **Clarification of Experimental Results on Curve Flattening**\n    * 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.\n\nWe 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.", "claims_and_evidence": "All claims in the paper are supported by theoretical proofs.", "methods_and_evaluation_criteria": "The method design is sensible and supported by experiments. The evaluation tests the algorithm's handling of unknown features by varying latent feature dimensions and their impact, which appears reasonable.", "theoretical_claims": "The theory appears to be sound, but I have not had the time to thoroughly check the proofs.", "experimental_designs_or_analyses": "I’m a bit confused about the experimental results. In each graph, the cumulative regret of the proposed RoLF-Lasso algorithm suddenly flattens at a certain point and stays flat afterward. This doesn’t align with my understanding of how regret typically grows in bandit experiments. I think the authors might need to explain why the regret suddenly becomes flat.", "relation_to_broader_scientific_literature": "This paper is the first to study partially observable features in linear bandits. It shows that when too few features are observable, the linear bandit will recover to multi-armed bandits (MAB), linking the two frameworks and identifying the point where linear modeling and additional context advantages weaker.", "essential_references_not_discussed": "To my knowledge, I haven’t found any references that were left undiscussed.", "other_strengths_and_weaknesses": "I believe the strength of this work lies in introducing a meaningful new topic within the linear bandit setting and providing what appears to be a solid theoretical analysis. However, the weakness lies in the presentation of the paper, as many parts lack clear explanations. Below are my specific comments and questions for further clarification.", "other_comments_or_suggestions": "The paper can be further improved in terms of writing and presentation. For instance, there are excessive blank lines between lines 326-329, and page 8 is not fully utilized. While these issues are not strictly necessary, the paper does not convincingly demonstrate that the content can be fully explained without filling these spaces. \n\nSpecifically, several key concepts and definitions are left unexplained: \n\n1.the content of Table 1 is not well-explained, and the accompanying text does not align with the table. \n\n2.In line 147, the regret formula includes $ z_* $ and $ z_t $, neither of which is defined. Based on the notation in the regret formula, these appear to be $ d $-dimensional vectors rather than full feature vectors, but this is not clearly explained. \n\nTherefore, I believe the work could be further improved in terms of clarity and writing.", "questions_for_authors": "I have some question about the result of regret bound. Regarding the results in Table 1, I understand the first scenario: it suggests that even though there are some unknown parts of the features, these features are either unimportant or can be linearly expressed by the known features, thus reducing the problem to standard linear bandits. The second scenario indicates that the unknown features are so numerous that even with some side information, it’s insufficient, causing the problem to degenerate into a multi-armed bandit setting, where the features essentially useless. Both scenarios make sense to me. \n\nHowever, I find the third result less clear. Based on my understanding, the bound includes $ d $ as the dimension of known features and $ d_h $ as the dimension of unknown features. Intuitively, as the proportion of unknown features increases relative to known features, the problem should become more challenging. That is, if $ d + d_h $ remains constant, increasing $ d_h $ should make the problem harder. Yet, according to the bound, as long as $ d + d_h $ remains unchanged, the final performance is the same. This seems confused to me, and I believe the authors may need to discuss this problem.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EWBsurKfvj", "reviewer": "Reviewer_4X4v", "summary": "The paper proposes a method to solve the linear bandit problem with only a subset of features per arm visible to the learner without assuming any structural property beforehand. The authors do this by transforming each context vector onto an augmented space with dimension $K$ and learn the respective augmented feature vector to minimize the regret. They apply a doubly robust algorithm (robust wrt. estimated model and rewards). The authors provide a sublinear regret upper bound, a lower bound and proof the consistency of their estimator. Experiments showcase the effectiveness of their algorithm to other baselines.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n* **On Use of Compatibility Condition**\n    * 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.\n* **Ensurability of Full Rank Gram Matrix under Our Exploration Strategies**\n    * 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}$.\n* **Selection of Orthonormal Basis**\n    * 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$.\n* **Other Corrections**\n    * Regret definition in Eq. (2)\n        * Thank you for pointing this out. We will revise the notation in the revision.\n    * 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.\n        * 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.\"\n    * 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.\n        * 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.\"\n\nIn 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.\n\nReference: van de Geer, S. A. and Bühlmann, P. (2009), On the conditions used to prove oracle results for the lasso.", "claims_and_evidence": "I did not check all of the proofs but from what I saw they look mostly clear and convincing I list some concerns in the weakness/questions section.", "methods_and_evaluation_criteria": "Comparing regret bounds for different compositions of number of arms and dimension make sense in this setting.", "theoretical_claims": "I only skimmed through the proofs, with more focus on theorem 3.", "experimental_designs_or_analyses": "I read through the experimental section and the scenarios explained for each plot. I have no issues there, though I did not check any code.", "relation_to_broader_scientific_literature": "The key contribution is a new model for the partially observable features setting without any additional assumptions on the structure of the problem through feature augmentation and the respective regret bound.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "Strength: I like the idea of using augmentation to mitigate the missing information and exploiting the observable features. The fact that no further assumptions are made makes the model quite powerful.\n\nWeakness: I find the paper in section 3.2 hard to follow. For example it is not quite clear to me wether a compatibility condition is used or not for the oracle inequality. Also the exploration aspect of the algorithm is not quite clear to me, what is the benefit to random exploration for instance? Also I don't see how the basis vectors $b_i$ for the augmented context vectors are determined, I assume they have to minimize $d_h$?", "other_comments_or_suggestions": "I think there is a small error in the regret definition in equation (2). Shouldn't it be just $\\theta^\\star$  and $z_{a^\\star}$ instead of $z_\\star$?\n\nAt 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.\n\nIn 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.", "questions_for_authors": "Do you actually use a compatibility condition or do you rely on a full rank gram matrix?\n\nIf you use a full rank gram matrix in the augmented space, how does you exploration strategy ensure full rank?\n\nHow do you select the set of orthogonal basis vectors $b_i$ ?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the linear bandit problem under partial feature observability, proposing an algorithm based on feature augmentation and doubly robust estimation. The authors provide regret bounds under various relationships between observed and latent features, supported by theoretical analysis and experimental results.

During the rebuttal and the discussion, the reviewers and I generally agree that the theoretical contribution is strong. In particular, the paper proposes a novel modeling framework and achieves regret bounds that generalize existing results without relying on strong structural assumptions. This provides a meaningful step forward in the study of linear bandits with latent features.

However, there remain some concerns about the experimental section, especially regarding the behavior of the regret curves and the clarity of the problem motivation. While the authors offered plausible explanations and additional results during the discussion phase, some questions remain. I strongly encourage the authors to clarify the experimental setup and presentation in the camera-ready version, particularly to help readers better understand the flattening of regret curves in the experiments and the real-world relevance of the problem.

Overall, despite these caveats, I find that the core contribution is novel and well-executed, and that the concerns raised do not outweigh the value of the work.
Decision: Accept (poster)