Year: 2021

Abstract:
We focus on the setting of contextual batched bandit (CBB), where a batch of rewards is observed from the environment in each episode. But these rewards are partial-information feedbacks where the rewards of the non-executed actions are unobserved. Existing approaches for CBB usually ignore the potential rewards of the non-executed actions, resulting in feedback information being underutilized. In this paper, we propose an efficient reward imputation approach using sketching in CBB, which completes the unobserved rewards with the imputed rewards approximating the full-information feedbacks. Specifically, we formulate the reward imputation as a problem of imputation regularized ridge regression, which captures the feedback mechanisms of both the non-executed and executed actions. To reduce the time complexity of reward imputation on a large batch of data, we use randomized sketching for solving the regression problem of imputation. We prove that the proposed reward imputation approach obtains a relative-error bound for sketching approximation, achieves an instantaneous regret with a controllable bias and a smaller variance than that without reward imputation, and enjoys a sublinear regret bound against the optimal policy. Moreover, we present two extensions of our approach, including the rate-scheduled version and the version for nonlinear rewards, which makes our approach more feasible. Experimental results demonstrated that our approach can outperform the state-of-the-art baselines on a synthetic dataset, the Criteo dataset, and a dataset from a commercial app.

heading: 1 INTRODUCTION
text: Contextual bandits have been widely used in real-world sequential decision-making problems (Li et al., 2010; Lan & Baraniuk, 2016; Yom-Tov et al., 2017; Yang et al., 2021), where the agent updates the decision-making policy fully online (i.e., at each step) according to the context and corresponding reward feedback so as to maximize the cumulative reward. In this paper, we consider a more complex setting—contextual batched bandits (CBB), where the decision process is partitioned into N episodes, the agent interacts with the environment for B steps in one episode, collects the reward feedbacks and contexts at the end of the episode, and then updates the policy using the collected data for the next episode. CBB is more practical in some real-world applications, since updating the policy once receiving the reward feedback is rather unrealistic due to its high computational cost and decision instability.
In bandit settings, it is inevitable that the environment only reveals the rewards of the executed actions to the agent as the feedbacks, while hiding the rewards of non-executed actions. We refer to this category of limited feedback as the partial-information feedback (also called “bandit feedback”). Existing batched bandit approaches in the CBB setting discard the information contained in the potential rewards of the non-executed actions, address the problem of partial-information feedback using an exploitation-exploration tradeoff on the context space and reward space (Han et al., 2020; Zhang et al., 2020).But in the CBB setting, the agent usually estimates and maintains reward models for the action-selection policy, and the potential rewards of the non-executed actions have been somehow captured by the policy. This additional reward structure information is estimated and available in each episode, however, are not utilized by existing batched bandit approaches.
In contextual bandit settings where the policy is updated fully online, several bias-correction approaches have been introduced to address the partial-information feedback. Dimakopoulou et al.
(2019) presented linear contextual bandits integrating the balancing approach from causal inference, which reweight the contexts and rewards by the inverse propensity scores. Chou et al. (2015) designed pseudo-reward algorithms for contextual bandits, which use a direct method to estimate the unobserved rewards for the upper confidence bound (UCB) strategy. Kim & Paik (2019) focused on the feedback bias-correction for LASSO bandit with high-dimensional contexts, and applied the doubly-robust approach to the reward modification using average contexts. Although these approaches have been demonstrated to be effective in contextual bandit settings, little efforts have been spent to address the under-utilization of partial-information feedback in the CBB setting.
Theoretical and experimental analyses in Section 2 indicate that better performance of CBB is achievable if the rewards of the non-executed actions can be received. Motivated by these observations, we propose a novel reward imputation approach for the non-executed actions, which mimics the reward generation mechanisms of environments. We conclude our contributions as follows. • To fully utilize feedback information in CBB, we formulate the reward imputation as a problem of imputation regularized ridge regression, where the policy can be updated efficiently using sketching. • We prove that our reward imputation approach obtains a relative-error bound for sketching approximation, achieves an instantaneous regret with a controllable bias and a smaller variance than that without reward imputation, has a lower bound of the sketch size independently of the overall number of steps, enjoys a sublinear regret bound against the optimal policy, and reduces the time complexity from O(Bd2) to O(cd2) for each action in one episode, where B denotes the batch size, c the sketch size, and d the dimensionality of inputs, satisfying d < c < B. • We present two practical variants of our reward imputation approach, including the rate-scheduled version in which the imputation rate is set without tuning, and the version for nonlinear rewards. • We carried out extensive experiments on the synthetic data, public benchmark, and the data collected from a real commercial product to demonstrate our performance, empirically analyzed the influence of different parameters, and verified the correctness of the theoretical results.
Related Work. Recently, batched bandit has become an active research topic in statistics and learning theory including 2-armed bandit (Perchet et al., 2016), multi-armed bandit (Gao et al., 2019; Zhang et al., 2020; Wang & Cheng, 2020), and contextual bandit (Han et al., 2020; Ren & Zhou, 2020; Gu et al., 2021). Han et al. (2020) defined linear contextual bandits, and designed UCB-type algorithms for both stochastic and adversarial contexts, where true rewards of different actions have the same parameters. Zhang et al. (2020) provided methods for inference on data collected in batches using bandits, and introduced a batched least squares estimator for both multi-arm and contextual bandits. Recently, Esfandiari et al. (2021) proved refined regret upper bounds of batched bandits in stochastic and adversarial settings. There are several recent works that consider similar settings to CBB, e.g., episodic Markov decision process (Jin et al., 2018), LASSO bandits (Wang & Cheng, 2020). Sketching is another related technology that compresses a large matrix to a much smaller one by multiplying a (usually) random matrix with certain properties (Woodruff, 2014), which has been used in online convex optimization (Calandriello et al., 2017; Zhang & Liao, 2019).

heading: 2 PROBLEM FORMULATION AND ANALYSIS
text: First, we introduce some notations. Let [x] = {1, 2, . . . , x}, S ⊆ Rd be the context space, A = {Aj}j∈[M ] the action space containing M actions,[A;B] = [Aᵀ,Bᵀ]ᵀ, ‖A‖F, ‖A‖1 ‖A‖2 denote the Frobenius norm, 1-norm, and spectral norm of a matrix A, respectively, ‖a‖1 and ‖a‖2 be the `1-norm and the `2-norm of a vector a, σmin(A) and σmax(A) denote the minimum and maximum of the of singular values of A. In this paper, we focus on the setting of Contextual Batched Bandits (CBB) (see Algorithm 1), where the decision process is partitioned into N episodes, and in each episode, CBB consists of two phases: 1) the policy updating approximates the optimal policy based on the received contexts and rewards; 2) the online decision selects actions for execution following the updated and fixed policy p for B steps (also called the batch size is B), and stores the contextaction pairs and the observed rewards of the executed actions into a data buffer D. The reward R in CBB is a partial-information feedback where rewards are unobserved for the non-executed actions.
Different from existing batch bandit setting (Han et al., 2020; Esfandiari et al., 2021), where the true reward feedbacks for all actions are controlled by the same parameter vector while the contexts received differ by actions at each step, we assume that in the CBB setting, the mechanism of true reward feedback differs by actions and the received context is shared by actions. Formally, for any context si ∈ S ⊆ Rd and action A ∈ A, we assume that the expectation of the true reward Rtruei,A
Algorithm 1 Contextual Batched Bandit (CBB) INPUT: Batch size B, number of episodes N , action space A = {Aj}j∈[M ], context space S ⊆ Rd 1: Initialize policy p0 ← 1/M , sample data buffer D1 = {(s0,b, AI0,b , R0,b)}b∈[B] using initial policy p0 2: for n = 1 to N do 3: Update the policy pn on Dn {Policy Updating} 4: for b = 1 to B do 5: Observe context sn,b 6: Choose AIn,b ∈ A following the updated policy pn(sn,b) {Online Decision} 7: end for 8: Dn+1 ← {(sn,b, AIn,b , Rn,b}b∈[B], where Rn,b denotes the reward of action AIn,b on context sn,b 9: end for is determined by an unknown action-specific reward parameter vector θ∗A ∈ Rd: E [ Rtruei,A | si ] = 〈θ∗A, si〉 (the linear reward will be extended to the nonlinear case in Section 5). This setting for reward feedback matches many real-world applications, e.g., each action corresponds to a different category of candidate coupons in coupon recommendation, and the reward feedback mechanism of each category differs due to the different discount pricing strategies.
Next, we provide deeper understandings of the influence of unobserved feedbacks on the performance of policy updating in the CBB setting. We first conducted an empirical comparison by applying the batch UCB policy (Han et al., 2020) to environments under different proportions of received reward feedbacks. In particular, the agent under full-information feedback can receive all the rewards of the executed and non-executed actions, called Full-Information CBB (FICBB) setting. From Figure 1, we can observe that the partial-information feedbacks could be damaging in terms of hurting the policy updating, and batched bandit could benefit from more reward feedbacks, where the performance of 80% feedback is very close to that of FI-CBB.
Then, we demonstrate the difference of instantaneous regrets between the CBB and FI-CBB settings as in Theorem 1. The detailed description and proof of Theorem 1 can be found in Appendix A. Theorem 1. For any action A ∈ A and context si ∈ S, let θnA be the reward parameter vector estimated by the batched UCB policy in the nth episode. The upper bound of instantaneous regret (defined by |〈θnA, si〉 − 〈θ∗A, si〉|) in the FI-CBB setting is tighter than that in CBB setting (i.e., using the partial-information feedback).
From Theorem 1, we can conclude that the price paid for having access only to the partial-information feedbacks is the deterioration in the regret bound. Ideally, the policy would be updated using the fullinformation feedback. In CBB, however, the fullinformation feedback is unaccessible. Fortunately, in
CBB, different reward parameter vectors need to be maintained and estimated separately for each action, and the potential reward structures of the non-executed actions have been somehow captured. So why don’t we use these maintained reward parameters to estimate the unknown rewards for the non-executed actions? Next, we propose an efficient reward imputation approach that uses this additional reward structure information for improving the performance of the bandit policy.

heading: 3 EFFICIENT REWARD IMPUTATION FOR POLICY UPDATING
text: In this section, we present an efficient reward imputation approach tailored for policy updating in the CBB setting.
Formulation of Reward Imputation. Since the true reward parameters differ by actions in the CBB setting, we need to maintain a different estimated reward parameter vector for each action. As shown in Figure 2, in contrast to CBB that ignores the contexts and rewards of the non-executed steps of Aj , our reward imputation approach completes the missing values using the imputed contexts and rewards, approximating the full-information CBB setting. Specifically, in the (n+1)-th episode, for
each action Aj ∈ A, j ∈ [M ], we store context vectors and rewards corresponding to the steps in which the action Aj is executed, into a context matrix SnAj ∈ R
Nnj ×d and a reward vector RnAj ∈ RN
n j , respectively, whereNnj denotes the number of steps (in episode n+1) in which the actionAj is executed. Additionally, for anyAj ∈ A, j ∈ [M ], we store context vectors corresponding to the nonexecuted steps of action Aj (denote the number of non-executed steps by N̂nj , i.e., N̂ n j = B−Nnj ), into an imputed context matrix ŜnAj ∈ R N̂nj ×d, and compute the imputed reward vector as follows:
R̂nAj = {rn,1(Aj), rn,2(Aj), . . . , rn,N̂nj (Aj)} ∈ R N̂nj , j ∈ [M ],
where rn,b(Aj) := 〈θ̄nAj , sn,b〉 denotes the imputed reward for each step b ∈ [N̂ n j ], and sn,b is the b-th row of ŜnAj . Then, we obtain several block matrices by concatenating the context and reward matrices from the previous episodes: LnAj = [S 0 Aj ; · · · ;SnAj ] ∈ R Lnj ×d, T nAj = [R 0 Aj
; · · · ;RnAj ] ∈ RL
n j , Lnj = ∑n k=0N k j , L̂ n Aj = [Ŝ0Aj ; · · · ; Ŝ n Aj ] ∈ RL̂ n j ×d, T̂ nAj = [R̂ 0 Aj
; · · · ; R̂nAj ] ∈ R L̂nj , L̂nj =∑n
k=0 N̂ k j . In the (n + 1)-th episode, the estimated parameter vector θ̄ n+1 Aj of the imputed reward for action Aj can be updated by solving the following imputation regularized ridge regression:
θ̄n+1Aj = arg min θ∈Rd ∥∥∥LnAjθ − T nAj∥∥∥2 2︸ ︷︷ ︸
Observed Term
+ γ ∥∥∥L̂nAjθ − T̂ nAj∥∥∥2
2︸ ︷︷ ︸ Imputation Term +λ‖θ‖22, n = 0, 1, . . . , N − 1, (1)
where γ ∈ [0, 1] is the imputation rate which controls the degree of reward imputation and measures a trade-off between bias and variance (Remark 1&2), λ > 0 is the regularization parameter, yielding
θ̄n+1Aj = ( Ψn+1Aj )−1 ( bn+1Aj + γb̂ n+1 Aj ) , (2)
that can be obtained by the closed least squares solution, where Ψn+1Aj := λId + Φ n+1 Aj + γΦ̂n+1Aj ,
Φn+1Aj = Φ n Aj + S nᵀ Aj SnAj , b n+1 Aj = bnAj + S nᵀ Aj RnAj , (3)
Φ̂n+1Aj = ηΦ̂ n Aj + Ŝ nᵀ Aj ŜnAj , b̂ n+1 Aj = ηb̂nAj + Ŝ nᵀ Aj R̂nAj , (4)
and η ∈ (0, 1) is the discount parameter which controls how fast the previous imputed rewards are forgotten, and can help guaranteeing the regret bound in Theorem 2.
Efficient Reward Imputation using Sketching. As shown in the first 4 columns in Table 1, the overall time complexity of the imputation for each action is O(Bd2) in each episode, where B represents the batch size, and d the dimensionality of the input. Thus, for all the M actions in one episode, reward imputation increases the time complexity from O(Bd2) of the approach without imputation to O(MBd2). To address this issue, we design an efficient reward imputation approach using sketching, which reduces the time complexity of each action in one episode from O ( Bd2
) to O ( cd2 ) , where c denotes the sketch size satisfying d < c < B and cd > B. Specifically, in
the (n+ 1)-th episode, the imputation regularized ridge regression Eq.(1) can be approximated by a sketched ridge regression as
θ̃n+1Aj = arg min θ∈Rd ∥∥∥ΠnAj (LnAjθ − T nAj)∥∥∥2 2 + γ ∥∥∥Π̂nAj (L̂nAjθ − T̂ nAj)∥∥∥2 2 + λ‖θ‖22, (5)
where θ̃n+1A denotes the estimated parameter vector of the imputed reward using sketching for action A ∈ A,CnAj ∈ R c×Nnj and ĈnAj ∈ R c×N̂nj are the sketch submatrices for the observed term and the imputation term, respectively, and the sketch matrices for the two terms can be represented as
ΠnAj = [ C0Aj ,C 1 Aj , · · · ,C n Aj ] ∈ Rc×L n j , Π̂nAj = [ Ĉ0Aj , Ĉ 1 Aj , · · · , Ĉ n Aj ] ∈ Rc×L̂ n j .
We denote the sketches of the context matrix and the reward vector by ΓnAj := C n Aj SnAj ∈ R
c×d
and ΛnAj := C n Aj RnAj ∈ R c, the sketches of the imputed context matrix and the imputed reward vector by Γ̂nAj := Ĉ n Aj ŜnAj ∈ R c×d and Λ̂nAj := Ĉ n Aj R̂nAj ∈ R c, and obtain the solution of Eq.(5):
θ̃n+1Aj = ( W n+1Aj )−1 ( pn+1Aj + γp̂ n+1 Aj ) , (6)
where η ∈ (0, 1) denotes the discount parameter,W n+1Aj := λId +G n+1 Aj + γĜn+1Aj , and
Gn+1Aj = G n Aj + Γ nᵀ Aj ΓnAj , p n+1 Aj = pnAj + Γ nᵀ Aj ΛnAj , (7)
Ĝn+1Aj = ηĜ n Aj + Γ̂ nᵀ Aj Γ̂nAj , p̂ n+1 Aj = ηp̂nAj + Γ̂ nᵀ Aj Λ̂nAj . (8)
Using the parameter θ̃n+1Aj , we obtain the sketched version of imputed reward as r̃n,b(Aj) := 〈θ̃nAj , sn,b〉 at step b ∈ [N̂ n j ]. Finally, we specify that the sketch submatrices {CnA}A∈A,n∈[N ] and {ĈnAj}A∈A,n∈[N ] are the block construction of Sparser Johnson-Lindenstrauss Transform (SJLT) (Kane & Nelson, 2014), where the sketch size c is divisible by the number of blocks D1. As shown in the last 4 columns in Table 1, sketching reduces the time complexity fromO(MBd2) toO(Mcd2) for reward imputation of all M actions in one episode, where c < B. When Mc ≈ B, the overall time complexity of our reward imputation using sketching is even comparable to that without reward imputation which has a O(Bd2) time complexity.
Updated Policy using Imputed Rewards. Inspired by the UCB strategy (Li et al., 2010), the updated policy for online decision of the (n+ 1)-th episode can be formulated using the imputed rewards (parameterized by θ̄n+1A in Eq.(2)) or the sketched version of imputed rewards (parameterized by θ̃n+1A in Eq.(6)). Specifically, for a new context s, origin policy p̄n+1 selects the action following A← arg max
A∈A 〈θ̄n+1A , s〉+ ω[sᵀ(Ψ n+1 A ) −1s] 1 2 ,
sketched policy p̃n+1 selects the action following A ← arg max A∈A 〈θ̃n+1A , s〉 + α[sᵀ(W n+1 A ) −1s] 1 2 , where ω ≥ 0 and α ≥ 0 are the regularization parameters in policy and their theoretical values are given in Theorem 4. We summarize the reward imputation using sketching and the sketched policy into Algorithm 2, called SPUIR. Similarly, we call the updating of the original policy that uses reward imputation without sketching, the Policy Updating with Imputed Rewards (PUIR).
1Since we set the number of blocks of SJLT as D < d, we omit D in the complexity analysis.
Algorithm 2 Sketched Policy Updating with Imputed Rewards (SPUIR) in the (n+ 1)-th episode INPUT: Policy p̃n, Dn+1, A = {Aj}j∈[M ], α ≥ 0, η ∈ (0, 1), γ ∈ [0, 1], λ > 0, W 0Aj = λId, G 0 Aj =
Ĝ0Aj = Od, p 0 Aj = p̂0Aj = 0, θ̃ 0 Aj = 0, j ∈ [M ], batch size B, sketch size c, number of block D OUTPUT: Updated policy p̃n+1 1: For all j ∈ [M ], store context vectors and rewards corresponding to the steps in which the action Aj is
executed, into ΓnAj ∈ R Nnj ×d and ΛnAj ∈ R Nnj
2: For all j ∈ [M ], store context vectors corresponding to the steps in which the action Aj is not executed into Γ̂nAj ∈ R
N̂nj ×d, where N̂nj ← B −Nnj 3: r̃n,b(Aj)← 〈θ̃nAj , sn,b〉, for all Aj ∈ A and b ∈ [N̂ n j ], where sn,b is the b-th row of Γ̂ n Aj 4: Compute imputed reward vector R̂nAj ← {r̃n,1(Aj), . . . , r̃n,N̂nj (Aj)} ∈ R N̂nj for any j ∈ [M ] 5: for all action Aj ∈ A do 6: Gn+1Aj ← G n Aj + ΓnᵀAjΓ n Aj , pn+1Aj ← p n Aj + ΓnᵀAjΛ n Aj {Eq.(7)} 7: Ĝn+1Aj ← ηĜ n Aj + Γ̂nᵀAj Γ̂ n Aj , p̂n+1Aj ← ηp̂ n Aj + Γ̂nᵀAj Λ̂ n Aj {Eq.(8)} 8: W n+1Aj ← λId +G n+1 Aj + γĜn+1Aj , θ̃ n+1 Aj ← (W n+1Aj ) −1(pn+1Aj + γp̂ n+1 Aj
) {Eq.(6)} 9: end for
10: p̃n+1(s) selects action A← argmaxA∈A〈θ̃ n+1 A , s〉+ α[s ᵀ ( W n+1A )−1 s] 1 2 for a new context s
11: return {θ̃n+1A }A∈A, { ( W n+1A )−1}A∈A

heading: 4 THEORETICAL ANALYSIS
text: We provide the instantaneous regret bound, prove the approximation error of sketching, and analyze the regret in the CBB setting. The detailed proofs can be found in Appendix B. We first demonstrate the instantaneous regret bound of the original solution θ̄nA in Eq.(1). Theorem 2 (Instantaneous Regret Bound). Let η ∈ (0, 1) be the discount parameter, γ ∈ [0, 1] the imputation rate. In the n-th episode, if the rewards {Rn,b}b∈[B] are independent2 and bounded by CR, then, for any b ∈ [B] and ∀A ∈ A, with probability at least 1− δ,∣∣〈θ̄nA, sn,b〉− 〈θ∗A, sn,b〉∣∣ ≤ [λ‖θ∗A‖2 + ν + γ 12 η− 12CImp] [sᵀn,b (ΨnA)−1 sn,b] 12 , (9) where ΨnA = λId + Φ n A + γΦ̂ n A, ν = [2C 2 R log(2MB/δ)] 1 2 , and CImp > 0. The first term on the right-hand side of Eq.(9) can be seen as the bias term for the reward imputation, while the second term is the variance term. The variance term of our algorithm is not larger than that without the reward imputation, i.e, for any s ∈ Rd, [sᵀ (ΨnA) −1 s] 1 2 ≤ [sᵀ (λId + ΦnA) −1 s] 1 2 . Further, a larger imputation rate γ leads to a smaller variance term [sᵀ (ΨnA) −1 s] 1 2 . Remark 1 (Smaller Variance). From Theorem 2, we can observe that the proposed reward imputation achieves a smaller variance ([sᵀn,b (Ψ n A) −1 sn,b] 1 2 ) than that without the reward imputation. Remark 2 (Controllable Bias). Our reward imputation approach incurs a bias term γ 12 η− 12CImp in addition to the two bias terms λ‖θ∗A‖2, ν that exist in every UCB-based policy. But this additional bias term is controllable due to the presence of imputation rate γ that can help controlling the additional bias. Moreover, the term CImp in the additional bias can be replaced by a function fImp(n), and fImp(n) is monotonic decreasing w.r.t. number of episodes n provided that the mild condition√ η = Θ(d−1) holds (the definition and analysis about fImp can be found in Appendix B.1). Overall, the imputation rate γ controls a trade-off between the bias term and the variance term, and we will design a rate-scheduled approach for choosing the imputation rate γ in Section 5.
Although some approximation error bounds using SJLT have been proposed (Nelson & Nguyên, 2013; Kane & Nelson, 2014; Zhang & Liao, 2019), it is still unknown what is the lower bound of the sketch size while applying SJLT to the sketched ridge regression problem in our SPUIR. Next, we prove the approximation error as well as the lower bound of the sketch size for the sketched ridge regression problem. For convenience, we drop all the superscripts and subscripts in this result. Theorem 3 (Approximation Error Bound of Imputation using Sketching). Denote the imputation regularized ridge regression function by F (θ) (defined in Eq.(1)) and the sketched ridge regression
2The assumption about conditional independence of the rewards is commonly used in the bandits literature, which can be ensured using a master technology as a theoretical construction (Auer, 2002; Chu et al., 2011).
function by F S(θ) (defined in Eq.(5)) for reward imputation, whose solutions (i.e., the estimated reward parameter vectors) are θ̄ = arg minθ∈Rd F (θ) and θ̃ = arg minθ∈Rd F
S(θ). Let γ ∈ [0, 1] be the imputation rate, λ > 0 the regularization parameter, δ ∈ (0, 0.1], ε ∈ (0, 1), Lall = [L; √ γL̂], and ρλ = ‖Lall‖22/(‖Lall‖22+λ). If Π and Π̂ are SJLT, assuming thatD = Θ(ε−1 log 3(dδ−1)) and
the sketch size c = Ω ( d polylog ( dδ−1 ) /ε2 ) ,with probability at least 1−δ, F (θ̃) ≤ (1+ρλε)F (θ̄)
and ‖θ̃ − θ̄‖2 = O (√ ρλε ) hold.
To measure the convergence of approximating the optimal policy in sequential decision-making, we define the regret of SPUIR against the optimal policy as follows:
Reg ( {AIn,b}n∈[N ],b∈[B] ) := maxA∈A ∑ n∈[N ],b∈[B][〈θ∗A, sn,b〉 − 〈θ∗AIn,b , sn,b〉],
where In,b denotes the index of the executed action using the sketched policy p̃n (parameterized by {θ̃nA}A∈A) at step b in the n-th episode. Finally, we demonstrate the regret bound of SPUIR. Theorem 4 (Regret Bound of SPUIR). Let T = BN be the overall number of steps, η ∈ (0, 1) be the discount parameter, γ ∈ [0, 1] the imputation rate, λ > 0 the regularization parameter, Cmaxθ∗ = maxA∈A ‖θ∗A‖2, CImp be a positive constant. Assume that the conditional independence assumption in Theorem 2 holds and the upper bound of rewards is CR, M = O(poly(d)), T ≥ d2, ν = [2C2R log(2MB/δ1)]
1 2 with δ1 ∈ (0, 1), ω = λCmaxθ∗ + ν + γ 1 2 η− 1 2CImp, α = ωCα,
where Cα > 0 which decreases with increase of 1/ε and ε ∈ (0, 1). Let δ2 ∈ (0, 0.1], ρλ < 1 be the constant defined in Theorem 3, and Creg be a positive constant that decreases with increase of 1/ε. For the sketch matrices {ΠnA}A∈A,n∈[N ] and {Π̂}A∈A,n∈[N ], assuming that the number of blocks in SJLT D = Θ(ε−1 log3(dδ−12 )), and the sketch size satisfying c = Ω ( d polylog ( dδ−12 ) /ε2 ) , then, for an arbitrary sequence of contexts {sn,b}n∈[N ],b∈[B], with probability at least 1−N(δ1 + δ2),
Reg({AIn,b}n∈[N ],b∈[B]) ≤ 2αCreg √ 10M log(T + 1)( √ dT + dB) +O ( T √ ρλ d/B ) . (10)
Remark 3. Setting B = O( √ T/d) and ρλ = 1/d yields a sublinear upper bound of regret of order Õ( √ MdT )3 provided that the sketch size c = Ω(ρ2λd
3 polylog(dδ−12 )). We can observe that the lower bound of c is independent of the overall number of steps T , and a theoretical value of the batch size is B = CB √ T/d = C2BN/d, where setting CB ≈ 25 is a suitable choice that has been verified in the experiments in Section 6. In particular, when ρλ = O(1/d), the sketch size of order c = Ω(d polylogd) is sufficient to achieve a sublinear regret, which has been demonstrated in our experimental results. Since the lower bound of regret for contextual batched bandit in (Han et al., 2020) assumes that there are only two actions and both the actions share the same true reward model, it can not be applied to our CBB setting where each action corresponds to a different reward model. Despite the lack of the lower bound in CBB setting, from the theoretical results of regret, we can observe that our SPUIR admits several advantages: (a) The order of our regret bound is not higher than those in the literature of contextual bandits in the fully-online setting (i.e., B = 1) (Li et al., 2019; Dimakopoulou et al., 2019), which is a more simple setting than ours; (b) The first term in the regret bound Eq.(10) measures the performance of policy updating using imputed rewards (called “policy error”). From Theorem 2 and Remark 1&2, we obtain that, in each episode, our policy updating has a smaller variance than the policy without the reward imputation, and incurs a decreasing additional bias under mild conditions, leading to a tighter regret (i.e., smaller policy error) after some number of episodes. (c) The second term on the right-hand side of Eq.(10) is of order O(T √ ρλ d/B), which is incurred by the sketching approximation using SJLT (called “sketching error”). This sketching error does not have any influence on the order of regret of SPUIR, which may even have a lower order with a suitable choice of ρλε, e.g., setting ρλε = T−1/4d−1 yields a sketching error of order O(T 3/8d1/2) provided that c = Ω(ρ2λd 3 polylog(dδ−12 ) √ T ).

heading: 5 EXTENSIONS OF OUR APPROACH
text: To make the proposed reward imputation approach more feasible and practical, we tackle the following two research questions by designing variants of our approach following the theoretical results:
3We use the notation of Õ to suppress logarithmic factors in the overall number of steps T .
RQ1 (Parameter Selection): Can we set the imputation rate γ without tuning? RQ2 (Nonlinear Reward): Can we apply the proposed reward imputation approach to the case where the expectation of true rewards is nonlinear? Rate-Scheduled Approach. For RQ1, we equip PUIR and SPUIR with a rate-scheduled approach, called PUIR-RS and SPUIR-RS, respectively. From Remark 1&2, a larger imputation rate γ leads to a smaller variance while increasing the bias, while the bias term includes a monotonic decreasing function w.r.t. number of episodes under mild conditions. Therefore, we can gradually increase γ with the number of episodes, avoiding the large bias at the beginning of reward imputation. Specifically, we set γ = X% for episodes from (X − 10)%×N to X%×N , where X ∈ [10, 100]. Application to Nonlinear Rewards. For RQ2, we provide nonlinear versions of reward imputation. We use linearization technologies of nonlinear rewards, rather than directly setting the rewards as nonlinear functions (Valko et al., 2013; Chatterji et al., 2019), avoiding the linear regret or curse of kernelization. Specifically, instead of using the linear imputed reward r̃n,b(Aj) := 〈θ̃nAj , sn,b〉, we use the following linearized nonlinear imputed rewards, denotes by Tn,b(θ, A): 1) SPUIR-Exp. We assume that the expected reward is an exponential function as GE(θ, s) = exp (θᵀs) . Then Tn,b(θ, A) = 〈θ,∇θGE(θ, sn,b)〉 , where∇θGE(θ, sn,b) = exp (θᵀsn,b) sn,b. 2) SPUIR-Poly. When the expected reward is a polynomial function as GP(θ, s) = (θᵀs) 2 . Then Tn,b(θ, A) = 〈θ,∇θGP(θ, sn,b)〉 , where∇θGP(θ, sn,b) = 2 (θᵀsn,b) sn,b. 3) SPUIR-Kernel. Consider that the underlying expected reward in a Gaussian reproducing kernel Hilbert space (RKHS). We use Tn,b(θ, A) = 〈θ, φ(sn,b)〉 in random feature space, where the random feature mapping φ can be explicitly defined as in (Rahimi & Recht, 2007). For SPUIR-Exp and SPUIR-Poly, combining the linearization of convex functions (Shalev-Shwartz, 2011) with Theorem 4 yields the regret bounds of the same order. For SPUIR-Kernel, using the approximation error of random features (Rahimi & Recht, 2008), we can obtain a regret bound with an additional error of order O(B/ √ dr), where dr is the dimension of the random features.

heading: 6 EXPERIMENTS
text: We empirically evaluated the performance of our algorithms on 3 datasets: the synthetic dataset, publicly available Criteo dataset4 (Criteo-recent, Criteo-all), and dataset collected from a real commercial app for coupon recommendation (commercial product). Experimental Settings. We compared our algorithms with: Sequential Batch UCB (SBUCB) (Han et al., 2020), Batched linear EXP3 (BEXP3) (Neu & Olkhovskaya, 2020), Batched linear EXP3 using Inverse Propensity Weighting (BEXP3-IPW) (Bistritz et al., 2019), Batched Balanced Linear Thompson Sampling (BLTS-B) (Dimakopoulou et al., 2019), and Sequential version of Delayed Feedback Model (DFM-S) (Chapelle, 2014). We implemented all the algorithms on Intel(R) Xeon(R) Silver 4114 CPU@2.20GHz, and repeated the experiments 20 times. We tested the performance of algorithms in streaming recommendation scenarios, where the reward is represented by a linear combination of the click and conversion behaviors of users. According to Remark 3, we set the batch size as B = C2BN/d, the constant CB ≈ 25, and the sketch size c = 150 on all the datasets. The average reward was used to evaluate the accuracy of algorithms. Performance Evaluation. Figure 3(a)–(c) reports the average reward of SPUIR with its variants and the baselines. We observed that SPUIR and its variants achieved higher average rewards, demonstrating the effectiveness of our reward imputation. Moreover, SPUIR and its rate-scheduled version SPUIR-RS had similar performances compared with the origin PUIR, which indicates the practical effectiveness of our variants and verifies the correctness of the theoretical analyses. The results on commercial product in Table 2 indicate that SPUIR outperformed the second-best baseline with the improvements of 1.07% CVR (conversion rate) and 1.12% CTCVR (post-view clickthrough&conversion rate). Besides, our reward imputation approaches were more efficient than DFM-S, BLTS-B. The variants using sketching of our algorithms (SPUIR, SPUIR-RS) significantly reduced the time costs of reward imputation, and took less than twice as long to run compared to the baselines without reward imputation (SBUCB, BEXP3, BEXP3-IPW). Figure 3(d) illustrates performances of SPUIR and its nonlinear variants, where SPUIR-Kernel achieved the highest rewards indicating the effectiveness of the nonlinear generalization of our approach. For different decision tasks, a suitable nonlinear reward model needs to be selected for better performances. Parameter Influence. From the regret bound Eq.(10), we can observe that a larger batch size B results in a larger first term (of order O(B), called policy error) but a smaller second term (of order
4https://labs.criteo.com/2013/12/conversion-logs-dataset/
O(1/B), called sketching error), indicating that a suitable batch sizeB needs to be set. This conclusion was empirically verified in Figure 3(e), where B = 1, 000 (CB = 25) yields better empirical performance in terms of the average reward. Similar phenomenon can also be observed on Criteo dataset and commercial product. All of the results verified the theoretical results in Remark 3: B = CB √ T/d = C2BN/d is a suitable choice while setting CB ≈ 25. From the results in Figure 3(f) we observe that, for our SPUIR and SPUIR-RS, the performances significantly increased when the sketch size c reached 10%B (≈ d log d), which demonstrates the conclusion in Remark 3 that only the sketch size of order c = Ω(d polylogd) is needed for satisfactory performance.

heading: 7 CONCLUSION
text: Partial-information feedback is ubiquitous in real-world applications, where reward feedback is usually underutilized for learning. This paper proposes a theoretically sound and computationally efficient reward imputation approach for contextual batched bandits, which mimics the reward generation mechanism of the environment approximating the setting of full-information feedback. The proposed reward imputation approach reduces the time complexity of imputation on large batches of data using sketching, achieves a relative-error bound for sketching approximation, has an instantaneous regret with a controllable bias and a smaller variance, and enjoys a sublinear regret bound against the optimal policy. The theoretical formulation and algorithmic implementation may provide an efficient reward imputation scheme for online learning under limited feedback.

heading: ETHICS STATEMENT
text: To verify the effectiveness and efficiency of our algorithms on real products, we conducted experiments on a real dataset collected from a commercial social app. We call this dataset commercial product, where the data were collected after the users gave consent, and did not contain any personally identifiable information or offensive content.

heading: REPRODUCIBILITY STATEMENT
text: The source code of the proposed algorithms is submitted as supplementary materials. For theoretical results, clear explanations of any assumptions and a complete proof of the claims are included as an appendix. The detailed experimental settings are also provided in the appendix. Since the dataset commercial product is non-public, we did not provide a URL. We will release this non-public dataset after the publication of this paper, and the link to download this non-public dataset is to be included in the final paper.

heading: A DETAILED PROBLEM FORMULATION AND DETAILED PROOF IN PROBLEM ANALYSIS
text: In this part, we give the detailed problem formulation and the detailed proof of Theorem 1 in problem analysis in Section 2.

heading: A.1 DETAILED PROBLEM FORMULATION OF CBB
text: In this paper, we focus on the setting of contextual batched bandits (CBB), which can be formulated as a 6-tuple 〈S,A, p, R,N,B〉: Context space S ⊆ Rd means a vector space containing the context information received at each step, e.g., context summarizes the information of both the user and items in recommendation scenarios. Action space A = {Aj}j∈[M ] contains M candidate actions for execution. As an example, in recommender systems, each action corresponds to a candidate item, and selecting an action means that the corresponding item is recommended. Policy p determines which action to take at each step, which is a function of the context s ∈ S and outputs an action for execution (or a selection distribution over action space A). Reward R in CBB is a partial-information feedback where rewards are unobserved for the nonexecuted actions. Consider a stochastic bandit setting, where the expectation of the true reward is assumed to be a function of the context s ∈ S . In particular, different from the shared expectation function of true rewards in existing batch bandits (Han et al., 2020), we assume that the expectation functions of true rewards are different for each action, where each expectation function corresponds to an unknown parameter vector θ∗A ∈ Rd, A ∈ A. This setting for rewards matches many realworld applications, e.g., each action corresponds to a different category of candidate coupons in coupon recommendation. Number of episodes N . The decision process in CBB is partitioned into N episodes. Within one episode, the agent updates the policy using the collected data, and then interacts with the environment for multiple steps using the updated and fixed policy. Batch size B is the number of steps in each episode. That is, in each episode, the agent interacts with the environment B times using a fixed policy, and stores the contexts, executed actions, and observed rewards into a data buffer D at the end of each episode.

heading: A.2 DETAILED DESCRIPTION AND PROOF OF THEOREM 1 IN PROBLEM ANALYSIS
text: We present some theoretical findings about the regret difference between the partial-information feedback and the full-information feedback. Assuming that the agent in the CBB setting can observe the rewards of all the candidate actions from the environment at each step, we apply the batched UCB policy (Han et al., 2020) to this setting (see Algorithm 3), We demonstrate an instantaneous regret bound in Theorem 5, where Theorem 5 is a detailed version of Theorem 1 in Section 2.
Algorithm 3 Batch UCB Policy Updating in the (n+1)-th episode in Full-Information CBB Setting INPUT: Policy pn, data buffer Dn+1, action space A = {Aj}j∈[M ], θ0Aj = 0, j ∈ [M ], batch size B OUTPUT: Updated policy pn+1 1: Let L̃n ∈ R(n+1)B×d be the matrix that stores all the context vectors till the n-th episode as the row
vectors 2: For ∀A ∈ A, let T̃ nA ∈ R(n+1)B be the reward vector that stores all the rewards of action A ∈ A till the n-th episode 3: // Policy Updating 4: Υn+1 ← L̃ᵀnL̃n 5: for all action A ∈ A do 6: θn+1A ← (Id + Υn+1) −1L̃ᵀnT̃ n A 7: end for 8: For a new context s, pn+1(s) is to choose the action following: A← argmax
A∈A
〈 θn+1A , s 〉 9: return { θn+1A } A∈A
Theorem 5 (Instantaneous Regret Bound in Full-Information CBB Setting, Detailed Version of Theorem 1). Let L̃n−1 ∈ RnB×d be the matrix that stores all the context vectors till the (n− 1)-th episode as the row vectors, and T̃ n−1A ∈ RnB be the reward vector that stores all the rewards of action A ∈ A till the (n − 1)-th episode. Given the action space A = {Aj}j∈[M ], in the n-th episode, assume that the rewards are independent and bounded by CR. Then, with probability at least 1 − δ, for any b ∈ [B] and ∀A ∈ A, we have the following instantaneous regret bound in the n-th episode
|〈θnA, sn,b〉 − 〈θ∗A, sn,b〉| ≤ [ ‖θ∗A‖2 + √ 2C2R log(2MB/δ) ]√ sᵀn,b (Id + Υn) −1 sn,b, (11)
where Υn = L̃ ᵀ n−1L̃n−1 and the parameter of reward model θ n A in the batched UCB policy is obtained by
θnA := arg min θ∈Rd ∥∥∥L̃n−1θ − T̃ n−1A ∥∥∥2 2 + ‖θ‖22 = (Id + Υn) −1 L̃ᵀn−1T̃ n−1 A .
Further, the instantaneous regret bound Eq.(11) in FI-CBB setting is tighter than that in CBB setting (i.e., using the partial-information feedback). In particular, the variance term√ sᵀn,b (Id + Υn) −1 sn,b is smaller than that in CBB setting.
Proof of Theorem 1. By the formulation of θnA and the triangle inequality, we first obtain that
|〈θnA, sn,b〉 − 〈θ∗A, sn,b〉| = ∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1T̃ n−1A − sᵀn,bθ∗A∣∣∣
= ∣∣∣sᵀn,b (Id + Υn)−1 [L̃ᵀn−1T̃ n−1A − (Id + Υn)θ∗A]∣∣∣
= ∣∣∣sᵀn,b (Id + Υn)−1 [L̃ᵀn−1T̃ n−1A − (Id + L̃ᵀn−1L̃n−1)θ∗A]∣∣∣
= ∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1 (T̃ n−1A − L̃n−1θ∗A)− sᵀn,b (Id + Υn)−1 θ∗A∣∣∣
≤ ∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1 (T̃ n−1A − L̃n−1θ∗A)∣∣∣+ ∣∣∣sᵀn,b (Id + Υn)−1 θ∗A∣∣∣
(12)
Next, we bound the two terms in the last row of Eq.(12).

heading: Bounding
text: ∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1 (T̃ n−1A − L̃n−1θ∗A)∣∣∣:
Since E [ T̃ n−1A ] = L̃n−1θ ∗ A and the received rewards are independent, by the Azuma-Hoeffding bound, we have
Pr {∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1 (T̃ n−1A − L̃n−1θ∗A)∣∣∣ ≥ ν√sᵀn,b (Id + Υn)−1 sn,b} ≤ 2 exp { − ν2sᵀn,b (Id + Υn) −1 sn,b
2C2R‖L̃n−1 (Id + Υn) −1 sn,b‖22
} ,
(13)
where ν > 0 is some constant. Since ‖L̃n−1 (Id + Υn)−1 sn,b‖22 = s ᵀ n,b (Id + Υn) −1 L̃ᵀn−1L̃n−1 (Id + Υn) −1 sn,b
≤ sᵀn,b (Id + Υn) −1 ( Id + L̃ ᵀ n−1L̃n−1 ) (Id + Υn) −1 sn,b
≤ sᵀn,b (Id + Υn) −1 (Id + Υn) (Id + Υn) −1 sn,b = sᵀn,b (Id + Υn) −1 sn,b,
combing with Eq.(13) implies the following results
Pr {∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1 (T̃ n−1A − L̃n−1θ∗A)∣∣∣ ≥ ν√sᵀn,b (Id + Υn)−1 sn,b} ≤ 2 exp { − ν 2
2C2R
} .
(14)
Combing Eq.(14) with the union bound, yields that, with probability at least 1− δ, for any b ∈ [B] and ∀A ∈ A,∣∣∣sᵀn,b (Id + Υn)−1 L̃ᵀn−1 (T̃ n−1A − L̃n−1θ∗A)∣∣∣ ≤ ν√sᵀn,b (Id + Υn)−1 sn,b, (15) where the failure probability is
δ = 2MB exp { − ν 2
2C2R
} ,
yielding that ν = √
2C2R log(2MB/δ).

heading: Bounding
text: ∣∣∣sᵀn,b (Id + Υn)−1 θ∗A∣∣∣:
Since Υn is positive semi-definite, combining with the Hölder inequality, we obtain∣∣∣sᵀn,b (Id + Υn)−1 θ∗A∣∣∣ ≤ ‖θ∗A‖2 ∥∥∥(Id + Υn)−1 sn,b∥∥∥ 2
= ‖θ∗A‖2 √ sn,b (Id + Υn) −1 (Id + Υn) −1 sn,b
≤ ‖θ∗A‖2 √ sn,b (Id + Υn) −1 (Id + Υn) (Id + Υn) −1 sn,b
= ‖θ∗A‖2 √ sn,b (Id + Υn) −1 sn,b.
(16)
Combing Eq.(15) and Eq.(16) concludes the proof.
Similarly to the proof of Eq.(29), we can obtain that the variance term in full-information setting is smaller than that in partial-information setting.

heading: B DETAILED PROOFS IN THEORETICAL ANALYSIS
text: In this section, we provide the instantaneous regret bound in each episode, prove the approximation error of sketching, and analyze the regret for policy updating in the CBB setting. Figure 4 describes the dependence structure of our theoretical results.

heading: B.1 PROOF OF THEOREM 2
text: Before we provide the detailed proof of Theorem 2, we first demonstrate a lemma about the convergence and monotonicity of the sum of functions, which is the main tool for analyzing the additional bias of reward imputation.
Lemma 1 (Convergence and Monotonicity). Let f(n) = ∑n j=1 a
n−j · g(j), where a ∈ (0, 1) and n is a positive integer. Then,
1) when g(j) is convergent, the limit limn→∞ f(n) exists. Moreover,
lim n→∞
f(n) = 1
1− a lim n→∞ g(n). (17)
2) f(n) is a monotonic decreasing function if and only if g(j) satisfies, for any positive integer j ≥ 2,
g(j) ≤ (j − 1)a j−1g(1) a = 1/2, (1− a) [ aj−1 − (1− a)j−1
] 2a− 1 g(1) a 6= 1/2. (18)
Proof. Letting b(j) = a−j · g(j),∀j ∈ [n], and S(n) = ∑n j=1 b(j), f(n) can be rewritten as f(n) = anS(n).
1) Rewriting f(n) = S(n)/a−n, from the Stolz’s theorem, we have
lim n→∞ f(n) = lim n→∞ S(n)− S(n− 1) a−n − a−(n−1)
= lim n→∞
b(n)
a−n − a−(n−1)
= lim n→∞ a−n · g(n) a−n − a−(n−1)
= 1
1− a lim n→∞ g(n).
2) The condition that f(·) is a monotonic decreasing function is equivalent to the following condition: for and positive integer n,
f(n+ 1) ≤ f(n) ⇔ an+1S(n+ 1) ≤ anS(n)
⇔ a[S(n) + b(n+ 1)] ≤ S(n) ⇔ b(n+ 1) ≤ (1/a− 1)S(n). (19)
From the equivalent condition Eq.(19), we obtain the following recursion formula:
b(n+ 1) ≤ (1/a− 1)S(n)
b(n) ≤ (1/a− 1) n−1∑ j=1 b(j)
... b(3) ≤ (1/a− 1) [b(1) + b(2)] b(2) ≤ (1/a− 1) b(1),
yielding that, for any positive integer j ≥ 2, b(j) ≤ [ (1/a− 1) + (1/a− 1)2 + · · ·+ (1/a− 1)j−1 ] b(1). (20)
From Eq.(20) , for a 6= 1/2,
b(j) ≤ (1/a− 1)
[ 1− (1/a− 1)j−1 ] 1− (1/a− 1) b(1)
= (1− a)
[ 1− (1/a− 1)j−1 ] 2a− 1 b(1),
(21)
and substituting the definition of b(j) into Eq.(21) yields the equivalent condition
g(j) ≤ (1− a)
[ 1− (1/a− 1)j−1 ] 2a− 1 aj−1 g(1).
For a = 1/2, we have the condition b(j) ≤ (j − 1)b(1), which is equivalent to
a−j · g(j) ≤ (j − 1)a−1 · g(1) ⇔ g(j) ≤ (j − 1)aj−1g(1).
Next, we provide the detailed proof of Theorem 2.
Proof of Theorem 2. From the formulation of θ̄nA and the triangle inequality, we can obtain that, for each action A ∈ A,∣∣〈θ̄nA, sn,b〉− 〈θ∗A, sn,b〉∣∣
= ∣∣∣sᵀn,b (ΨnA)−1 (bnA + γb̂nA)− sᵀn,bθ∗A∣∣∣
= ∣∣∣sᵀn,b (ΨnA)−1 [(Ln−1A )ᵀ T n−1A + γ (L̂n−1A )ᵀ T̂ n−1A −ΨnAθ∗A]∣∣∣
= ∣∣∣sᵀn,b (ΨnA)−1 [(Ln−1A )ᵀ T n−1A + γ (L̂n−1A )ᵀ T̂ n−1A − (λId + ΦnA + γΦ̂nA)θ∗A]∣∣∣
= ∣∣∣sᵀn,b (ΨnA)−1 {(Ln−1A )ᵀ T n−1A + γ (L̂n−1A )ᵀ T̂ n−1A −[ λId + ( Ln−1A )ᵀ Ln−1A + γ ( L̂n−1A )ᵀ L̂n−1A ] θ∗A
}∣∣∣ = ∣∣∣sᵀn,b (ΨnA)−1 (Ln−1A )ᵀ (T n−1A −Ln−1A θ∗A)− λsᵀn,b (ΨnA)−1 θ∗A+ sᵀn,b (Ψ n A) −1 γ ( L̂n−1A )ᵀ ( T̂ n−1A − L̂ n−1 A θ ∗ A
)∣∣∣ ≤ ∣∣∣sᵀn,b (ΨnA)−1 (Ln−1A )ᵀ (T n−1A −Ln−1A θ∗A)∣∣∣︸ ︷︷ ︸
X (1) A
+λ ∣∣∣sᵀn,b (ΨnA)−1 θ∗A∣∣∣︸ ︷︷ ︸
X (2) A
+
∣∣∣sᵀn,b (ΨnA)−1 γ (L̂n−1A )ᵀ (T̂ n−1A − L̂n−1A θ∗A)∣∣∣︸ ︷︷ ︸ X
(3) A
.
Next, we bound X(1)A , X (2) A , and X (3) A . For convenience, we drop all the superscripts and subscripts about n and b. Similarly to the proof of Theorem 1, we bound X(1)A + X (2) A as follows: with probability at least 1− δ,
X (1) A +X (2) A ≤ (λ‖θ ∗ A‖2 + ν) √ sᵀΨ−1A s, (22)
where ν = √
2C2R log(2MB/δ). For X (3) A , using the Cauchy-Schwarz inequality, we have
X (3) A ≤ γ ∥∥∥L̂AΨ−1A s∥∥∥ 2 ∥∥∥T̂A − L̂Aθ∗A∥∥∥ 2
= √ γ √ sᵀΨ−1A ( γL̂ᵀAL̂A ) Ψ−1A s ∥∥∥T̂A − L̂Aθ∗A∥∥∥ 2
≤ √γ √ sᵀΨ−1A s ∥∥∥T̂A − L̂Aθ∗A∥∥∥ 2 .
(23)
Now we need to bound the term ∥∥∥T̂A − L̂Aθ∗A∥∥∥
2 . Since using the discount parameter η ∈ (0, 1)
in Eq.(4) is equivalent to multiplying both the imputed contexts and the imputed rewards by the parameter
√ η in each episode, we have, in the n-th episode,∥∥∥T̂ n−1A − L̂n−1A θ∗A∥∥∥ 2 = ∥∥∆ηn−1∥∥2 , (24)
where ∆ηn−1 = {η(n−i−1)/2 IRi,b}i∈[n−1],b∈[B] denotes an exponential-decay vector of the instantaneous regrets, and IRi,b denotes the instantaneous regret at step b in the i-th episode, i.e, IRi,b = ∣∣〈θ̄iA, si,b〉− 〈θ∗A, si,b〉∣∣. From Eq.(24), letting CIRi =
∑ b∈[B] IRi,b (25)
be the cumulative instantaneous regret in the i-th episode, we can obtain the upper bound of Eq.(24) as follows: ∥∥∥T̂ n−1A − L̂n−1A θ∗A∥∥∥ 2 = ∥∥∆ηn−1∥∥2
≤ ∥∥∆ηn−1∥∥1
= ∑
i∈[n−1],b∈[B] ∣∣∣η(n−i−1)/2 IRi,b∣∣∣ =
∑ i∈[n−1] η(n−i−1)/2 CIRi
= η− 1 2 fImp(n),
(26)
where fImp(n) := ∑ i∈[n−1] ( √ η) n−i CIRi. (27)
From monotone bounded theorem, we have that the limit of CIRi exists. From Eq.(17) in Lemma 1, we get that fImp(n) is convergent and then has an upper bound. We denotes the upper bound of fImp(n) by CImp > 0, and then from Eq.(26) we have∥∥∥T̂ n−1A − L̂n−1A θ∗A∥∥∥
2 ≤ η− 12CImp. (28)
Substituting Eq.(28) into Eq.(23) yields the upper bound of X(3)A . Then, we prove that √ sᵀ (ΨnA) −1 s ≤ √ sᵀ (λId + ΦnA) −1 s. (29)
holds, which is equivalent to sᵀ ( λId + Φ + γΦ̂ )−1 s ≤ sᵀ (λId + Φ)−1 s. (30)
Letting Θ = λId + Φ, by Sherman-Morrison-Woodbury formula, we have( Θ + γΦ̂ )−1 = ( Θ + γŜᵀŜ )−1 = Θ−1 − γΘ−1Ŝᵀ ( Id + γŜΘ −1Ŝᵀ )−1 ŜΘ−1
= Θ−1 −Θ−1Ŝᵀ ( Id γ + ŜΘ−1Ŝᵀ )−1 ŜΘ−1,
(31)
yielding that Eq.(30) is equivalent to sᵀΓs ≥ 0, (32)
where Γ = Θ−1Ŝᵀ ( Id/γ + ŜΘ −1Ŝᵀ )−1 ŜΘ−1.
Let S = UdΣ 1/2 d V ᵀ d , Ŝ = ÛdΣ̂ 1/2 d V̂ ᵀ d be the Singular Value Decomposition (SVD) of S and Ŝ, respectively. Note that Φ = VdΣdV ᵀ d , Φ̂ = V̂dΣ̂dV̂ ᵀ d . We can obtain that Γ is a square symmetric positive semi-definite matrix, since Γ can be decomposed into Γ = QᵀQ,
where PγΛγP ᵀγ is the SVD of Id/γ + ŜΘ −1Ŝᵀ and
Q = Λ−1/2γ P ᵀ γ ŜΘ −1.
Thus, Eq.(32) holds, yielding that Eq.(30) also holds. Finally, we prove that a larger imputation rate γ leads to a smaller variance term √ sᵀ (Ψ) −1 s.
From Eq.(31), the variance term can be represented as follows:√ sᵀ (Ψ) −1 s = [ sᵀΘ−1s− sᵀΘ−1ŜᵀM−1γ ŜΘ−1s ]1/2 , (33)
where Mγ = Id/γ + ŜΘ−1Ŝᵀ. Letting Mγ = UMγΛMγU ᵀ Mγ be the SVD of Mγ , and z = UᵀMγ ŜΘ −1s, from Eq.(33) we can written the variance term as follows:√
sᵀ (Ψ) −1 s = [ sᵀΘ−1s− zᵀΛ−1Mγz ]1/2 . (34)
In Eq.(34), we can observed that zᵀΛMγz = ‖(ΛMγ )−1/2z‖22 ∈ [
1
σmax(M) + 1/γ ‖z‖22,
1
σmin(M) + 1/γ ‖z‖22 ] where M = ŜΘ−1Ŝᵀ, which indicates that a larger imputation rate γ leads to a smaller variance term.
Finally, we provide a deeper understanding of the additional bias in Theorem 2.
Remark 4 (Controllable Bias). Our reward imputation approach incurs a bias term γ 12 η− 12CImp in addition to the two bias terms λ‖θ∗A‖2 and ν that exist in every UCB-based policy. But this additional bias term is controllable due to the presence of imputation rate γ that can help controlling the additional bias. Moreover, from the proof of Eq.(26), we can obtain that, the term CImp in the additional bias can be replaced by a function fImp(n) (defined in Eq.(27)), and the additional bias term turns out to be γ 1 2 η− 1 2 fImp(n). Since fImp(n) has the same functional form as the function f(n) in Lemma 1, we can find the conditions that fImp(n) is monotonic decreasing following Eq.(18) in Lemma 1. Specifically, letting CIRi be the cumulative instantaneous regret in the i-th episode defined in Eq.(25),
1) when √ η 6= 1/2, the condition of a monotonic decreasing function fImp(·) is equivalent to, for
any positive integer i ≥ 2,
CIRi ≤ (1−√η)
[√ ηi−1 − (1−√η)i−1 ] 2 √ η − 1 CIR1,
indicating that the regret after N episodes satisfies
∑ 2≤i≤N CIRi ≤ CIR1 ∑ 2≤i≤N
(1−√η) [√ ηi−1 − (1−√η)i−1 ]
2 √ η − 1
= CIR1 1−√η 2 √ η − 1 ∑ 2≤i≤N [√ η i−1 − (1−√η)i−1 ] = CIR1
1 √ η(2 √ η − 1)
[ 2 √ η − 1 + (1−√η)N+1 − (√η)N+1 ] = CIR1
1 √ η
[ 1 + (1−√η)N+1 − (√η)N+1
2 √ η − 1
] . (35)
2) for the case √ η = 1/2, the condition of a monotonic decreasing function fImp(·) is equivalent
to CIRi ≤ (i − 1)( √ η)i−1CIR1 for any positive integer i ≥ 2, indicating that the regret after
N episodes satisfies∑ 2≤i≤N CIRi ≤ CIR1 ∑ 2≤i≤N (i− 1)(√η)i−1
=
√ η
(1−√η)2 CIR1 −
[ 1
(1−√η)2 + N − 1 1−√η
] ( √ η)NCIR1
= ( 2− 1 +N
2N−1
) CIR1
= [ 1 √ η − (1 +N)√ηN−1 ] CIR1. (36)
From Eq.(35) and Eq.(36), we can conclude that a monotonic decreasing function fImp(·) indicates the upper bound of regret after N episodes is of order O(CIR1/ √ η). The conclusion also indicates that setting the discount parameter as √ η = Θ(CIR1/N) achieves a O(N) regret bound (i.e., a Õ( √ dT ) regret bound following Remark 3). Note that setting the discount parameter as √ η = Θ(CIR1/N) is a mild condition, since the cumulative instantaneous regret CIR1 is typically of order O(B) (B = O( √ T/d) in Remark 3) yielding that √ η = Θ(d−1). Overall, since a larger imputation rate γ leads to a smaller variance while increasing the bias (variance analysis can be found in Remark 2), γ controls a trade-off between the bias term and the variance term. When fImp is a monotonic decreasing function w.r.t. number of episodes n, the additional bias term γ 1 2 η− 1 2 fImp(n) can be easily controlled, e.g., gradually increasing γ with the number of episodes, avoiding the large bias from fImp(n) at the beginning of reward imputation. We design a ratescheduled approach for choosing the imputation rate γ in Section 5. Remark 5 (Relationship to Exploration and Exploitation Trade-off). Exploration-exploitation dilemma is the key challenge in online learning under bandit settings. In the full-information setting, agent (e.g., UCB policy) receives the rewards from all the actions, does not need to consider the choice of exploring the feedback mechanisms, and achieves a lower variance part in the regret upper bound (Theorem 1). Along this line, our reward computation approach is proposed to approximate the setting of full-information feedback, which somewhat relaxes the explore/exploit dilemma and also brings a lower variance part and a controllable additional bias part in the regret. Extra information that pushes the policy towards exploitation and away from exploration comes from the estimated reward structures of the non-executed actions maintained in each episode, and the proposed reward imputation can be seen as an effective and efficient tool to capture this extra information.

heading: B.2 APPROXIMATION PROPERTIES OF SKETCHING
text: Although some error bounds of approximation using SJLT have been proposed (Nelson & Nguyên, 2013; Kane & Nelson, 2014; Bourgain et al., 2015), it is still unknown what is the lower bound of the sketch size while applying SJLT to the sketched ridge regression problem in our SPUIR. To address this issue, we first prove two approximation properties of SJLT which are necessary to achieve approximation error bound of the sketched ridge regression using SJLT. For convenience, we drop all the superscripts and subscripts in these theoretical results. Lemma 2 ((Nelson & Nguyên, 2013)). Let U ∈ RL×d be a matrix with orthonormal columns, Π ∈ Rc×L the SJLT. Assuming that D = Θ(ε−1σ log
3(dδ−10 )) for Π, εσ ∈ (0, 1) and d ≤ c, with probability at least 1− δ0 all singular values of ΠU
σi(ΠU) = 1± εσ, i ∈ [d], as long as
c ≥ d log8
( dδ−10 ) ε2σ .
Further, this holds if the hash function h and σ defining the Π is Ω ( log(dδ−10 ) ) -wise independent. Theorem 6 (Approximation Properties of SJLT). Let U ∈ RL×d be a matrix with orthonormal columns, andA be a matrix of any proper size. If Π ∈ Rc×L is the SJLT satisfying the assumptions in Lemma 2, and d ≤ c ≤ L, then Π has the following two properties:
1) Subspace embedding property: set c = Ω ( d polylog ( dδ−1s ) /ε2s ) , for εs ∈ (0, 1), with proba-
bility at least 1− δs, ‖UᵀΠᵀΠU − Id‖2 ≤ εs;
2) Matrix multiplication property: set c = Ω(d/(εmδm)), for εm ∈ (0, 1), with probability at least 1− δm,
‖UᵀΠᵀΠA−UᵀA‖2F ≤ εm‖A‖ 2 F.
Proof of Theorem 6. 1) From Lemma 2, by setting c = Ω ( d polylog ( dδ−1s ) /ε20 ) , we can obtain
the upper bounds of eigenvalues: with probability at least 1− δs,
λi (U ᵀΠᵀΠU) = σ2i (ΠU) ∈ [(1− εσ)2, (1 + εσ)2] ⊆ [1− 2εσ, 1 + 3εσ], (37)
which yields that |λi (UᵀΠᵀΠU − Id)| ≤ 3εσ. (38)
Eq.(39) is equivalent to ‖UᵀΠᵀΠU − Id‖2 ≤ 3εσ. Letting εs = 3εσ and εσ ∈ (0, 1/3) yields the subspace embedding property.
2) From Lemma 1 in (Zhang & Liao, 2019), we have
E [ ‖UᵀΠᵀΠA−UᵀA‖2F ] ≤ 2 c ‖U‖2F‖A‖2F = 2d c ‖A‖2F. (39)
Combining Eq.(39) with the Markov’s inequality, we obtain that, with probability at least 1−δm,
‖UᵀΠᵀΠA−UᵀA‖2F ≤ 2d
δmc ‖A‖2F.
Letting εm = 2d
δmc yields the matrix multiplication property.

heading: B.3 PROOF OF THEOREM 3
text: Next, using the approximation properties of SJLT in Theorem 6, we prove that the objective function value of the imputation regularized ridge regression problem for reward imputation can be approximated well with a relative-error bound. Moreover, we prove that the solution solving the sketched ridge regression problem for reward imputation is also a good approximation of the solution solving the imputation regularized ridge regression. The following theorem is a detailed version of Theorem 3.
Theorem 7 (Approximation Error Bound of Imputation using Sketching, Detailed Version of Theorem 3). Let γ ∈ [0, 1] be the imputation rate, λ > 0 the regularization parameter, Π ∈ Rc×L
and Π̂ ∈ Rc×L̂ be the SJLT, and L ∈ RL×d, L̂ ∈ RL̂×d,T ∈ RL, T̂ ∈ RL̂,θ ∈ Rd. Denote the imputation regularized ridge regression function F and sketched ridge regression function F S for reward imputation by
F (θ) = ‖Lθ − T ‖22 + γ ∥∥∥L̂θ − T̂∥∥∥2
2 + λ‖θ‖22, F S(θ) = ‖Π (Lθ − T )‖22 + γ ∥∥∥Π̂(L̂θ − T̂)∥∥∥2
2 + λ‖θ‖22,
and the solutions of these regression problems by
θ̄ = arg min θ∈Rd F (θ) and θ̃ = arg min θ∈Rd
F S(θ).
Let δ ∈ (0, 0.1], ε ∈ (0, 1), ρλ = ‖Lall‖22/(‖Lall‖22 + λ). For Π and Π̂, assuming that D = Θ(ε−1 log3(dδ−1)) and
c = Ω ( d polylog ( dδ−1 ) /ε2 ) ,
with probability at least 1− δ,
F (θ̃) ≤ (1 + ρλε)F (θ̄), (40)
‖θ̃ − θ̄‖2 ≤
√ ρλεF ( θ̄ )
σmin ( Lλall ) , (41) where Lλall = [ L; √ γL̂; √ λId ] ∈ R(L+L̂+d)×d. Furthermore, if there is a constant fraction of
the norm of T 0all lies in the column space of L λ all, then Eq.(41) can be strengthened. Formally, assuming that a mild structural assumption on the context matrix and the reward vector is satisfied, i.e., ‖UallUᵀallT 0all‖2 ≥ ξ‖T 0all‖2 with a constant ξ ∈ (0, 1], then with probability at least 1− δ,
‖θ̃ − θ̄‖2 ≤ ( κ(Lλall) √ ξ−2 − 1 )√ ρλ ‖θ̄‖2, (42)
where κ(A) denotes the condition number of A, T 0all = [T ; T̂ ; 0d] ∈ R(L+L̂+d), and Lλall = UallΣallV ᵀ all is the SVD of L λ all.
Proof of Theorem 7. We first introduce some more notation of block matrices that will simplify the proof of the theorem:
Πall =
( Π O
O Π̂
) , Lall = ( L √ γL̂ ) , Tall = ( T T̂ ) . (43)
Then the regression functions can be rewritten as follows:
F (θ) = ‖Lallθ − Tall‖22 + λ‖θ‖ 2 2, F S(θ) = ‖Πall (Lallθ − Tall)‖22 + λ‖θ‖ 2 2.
Obviously, Πall is still an SJLT. Combining Theorem 6 with theorem 19 in (Wang et al., 2017), we can obtain, setting c = Ω ( max{d polylog ( dδ−1s ) /ε2s , d/(εmδm)} ) ,
with probability at least 1− (δs + δm),
F (θ̃)− F (θ̄) ≤ ρλτF (θ̄), (44)
where ρλ = ‖Lall‖22 ‖Lall‖22+λ and τ = 2 max{ε 2 s ,εm} 1−εs . Letting εs = εm := ε0, Eq.(44) can be rewritten as
F (θ̃)− F (θ̄) ≤ 2ρλε0 1− ε0 F (θ̄), (45)
Assuming that δs = δm := δ/2 ∈ (0, 0.1] and ε0 ∈ (0, 1/3), setting = 2ε01−ε0 ∈ (0, 1), from Eq.(45) we obtain the upper bound Eq.(40).
Next, we bound the difference between the solutions solving the sketched ridge regression problem and the original regression problem. Since σ2min(A)‖x‖22 ≤ ‖Ax‖22 for any A and x with proper sizes, we have
σ2min(Lall)‖θ̃ − θ̄‖22 ≤ ∥∥∥Lall(θ̃ − θ̄)∥∥∥2
2 . (46) The key ingredient of bounding ‖θ̃−θ̄‖2 is to bound ‖Lall(θ̃−θ̄)‖2. LetLλall = [ L; √ γL̂; √ λId ] ∈
R(L+L̂+d)×d, T 0all = [T ; T̂ ; 0d] ∈ R(L+L̂+d), Lλall = UallΣallV ᵀ all be the SVD of L λ all, and denote a matrix with orthonormal columns by U⊥all ∈ R(L+L̂+d)×(L+L̂) which satisfies
UallU ᵀ all +U ⊥ all(U ⊥ all) ᵀ = IL+L̂+d and U ᵀ allU ⊥ all = O.
Then, we can rewrite the solution θ̄ as follows:
θ̄ = arg min θ∈Rd F (θ) = arg min θ∈Rd ∥∥Lλallθ − T 0all∥∥22 = (Lλall) †T 0all = VallΣ −1 allU ᵀ allT 0 all,
which yields that T 0all −Lλallθ̄ = T 0all −LλallVallΣ−1allU ᵀ allT 0 all
= T 0all −UallΣallV ᵀ allVallΣ −1 allU ᵀ allT 0 all = T 0all −UallU ᵀ allT 0 all = U⊥all(U ⊥ all) ᵀ T 0all.
(47)
Thus, T 0all − Lλallθ̄ is orthogonal to Uall, and consequently to Lλall(θ̃ − θ̄), and we can obtain the following equality by Pythagoras’s theorem:∥∥∥Lλall(θ̃ − θ̄)∥∥∥2 2 = ∥∥∥Lλallθ̃ − T 0all∥∥∥2 2 − ∥∥Lλallθ̄ − T 0all∥∥22 . (48)
Combining Eq.(48) with Eq.(40) yields that∥∥∥Lλall(θ̃ − θ̄)∥∥∥2 2 = F (θ̃)− F (θ̄) ≤ ρλεF (θ̄). (49)
Substituting Eq.(49) into Eq.(46) concludes the proof of Eq.(41).
If we make a mild structural assumption on the context matrix and the reward vector, we can provide a stronger bound of ‖θ̃ − θ̄‖2. Specifically, assuming that ‖UallUᵀallT 0all‖2 ≥ ξ‖T 0all‖2 with a constant ξ ∈ (0, 1], from Eq.(47) and Pythagoras’s theorem we have
F (θ̄) = ‖Lλallθ̄ − T 0all‖22 = ‖T 0all‖22 − ‖UallU ᵀ allT 0 all‖22
≤ (ξ−2 − 1)‖UallUᵀallT 0 all‖22 = (ξ−2 − 1)‖Lλallθ̄‖22 ≤ (ξ−2 − 1)‖Lλall‖22 ‖θ̄‖22 ≤ (ξ−2 − 1)σ2max(Lλall)‖θ̄‖22.
(50)
Combining Eq.(50) with Eq.(41) yields Eq.(42).

heading: B.4 PROOF OF THEOREM 4
text: Proof of Theorem 4. In our sketched policy, letting Cmaxθ∗ = maxA∈A ‖θ∗A‖2, CImp > 0, ν =√ 2C2R log(2MB/δ), and
ω = λCmaxθ∗ + ν + γ 1 2 η− 1 2CImp,
from Eq.(9) in Theorem 2 we obtain that∣∣〈θ̄nA, sn,b〉− 〈θ∗A, sn,b〉∣∣ ≤ ω√sᵀn,b (ΨnA)−1 sn,b. (51) Before proving the upper bound of
∣∣∣〈θ̃nA, sn,b〉− 〈θ∗A, sn,b〉∣∣∣, we need to provide a technical tool as follows. For convenience, we also drop all the superscripts and subscripts. The goal is to find a constant Cα such that √
sᵀΨ−1s ≤ Cα √ sᵀW−1s, (52)
which is equivalent to the condition that the matrix C2αW −1 − Ψ−1 is positive semidefinite. Let Lall and Πall be the matrices defined in Eq.(43), Lall = ŨallΣ̃allṼ ᵀ
all be the SVD of Lall, and σ̃1 ≥ σ̃2 · · · ≥ σ̃d be the singular values of Lall. Then the i-th eigenvalue of Ψ−1 = (λId + L ᵀ allLall)
−1 can be represented as λi(Ψ−1) = 1/(σ̃2i + λ), and the i-th eigenvalue of W−1 = (λId +L ᵀ allΠ ᵀ allΠallLall)
−1 is λi(W−1) = 1/(λ̂i + λ), where λ̂i is the i-th eigenvalue of Σ̃allŨ ᵀ allΠ ᵀ allΠallŨallΣ̃all.
From the Lidskii’s theorem and Eq.(37), we have
λ̂i ∈ [σ̃2d(1− 2εσ), σ̃21(1 + 3εσ)]. (53)
Assuming that the positive semi-definiteness of C2αW −1 − Ψ−1 is satisfied, we obtain that C2αλi(W −1)− λi(Ψ−1) ≥ 0 for i ∈ [d], and combining this inequality with Eq.(53) yields that
Cα = √ [σ̃21(1 + 3εσ) + λ]/(σ̃ 2 d + λ).
From the proof of Theorem 6 and Theorem 3, we can obtain that εσ = ε/(6 + 3ε), yielding that
Cα =
√ σ̃21 [1 + ε/(2 + ε)] + λ
σ̃2d + λ ,
which decreases with increase of 1/ε. Similarly to the proof of Cα satisfying Eq.(52), we can obtain that
√ sᵀW−1s ≤ Creg √ sᵀΨ−1s, (54)
provided that
Creg =
√ σ̃21 + λ
σ̃2d[1− 2ε/(6 + 3ε)] + λ .
Obviously, Creg also decreases with increase of 1/ε.
Then, letting α = ωCα, from Eq.(51) and Eq.(52) we have∣∣∣〈θ̃nA, sn,b〉− 〈θ∗A, sn,b〉∣∣∣ ≤ ∣∣∣〈θ̃nA, sn,b〉− 〈θ̄nA, sn,b〉∣∣∣+ ∣∣〈θ̄nA, sn,b〉− 〈θ∗A, sn,b〉∣∣ ≤ ∣∣∣〈θ̃nA − θ̄nA, sn,b〉∣∣∣+ ω√sᵀn,b (ΨnA)−1 sn,b
≤ Yn,b + α √ sᵀn,b (W n A) −1 sn,b,
(55)
where Yn,b denotes the upper bound of ∣∣∣〈θ̃nA − θ̄nA, sn,b〉∣∣∣ for any A ∈ A.
Next, using the compatibility of norm, we give a specific representation of the sum of Yn,b as follows:∑ b∈[B] Yn,b = max A∈A ‖SnA(θ̃nA − θ̄nA)‖1
≤ max A∈A ‖SnA‖1‖θ̃nA − θ̄nA‖1
≤ max A∈A ‖SnA‖1
√ d‖θ̃nA − θ̄nA‖2.
(56)
Further, we give a more specific upper bound in Eq.(56) under mild structural assumption in Theorem 3. Let κmaxall denote the maximum of the condition numbers of L λ all(A,n) for A ∈ A, n ∈ [N ], and Lλall(A,n) = [ LnA; √ γL̂nA; √ λId ] , and Uall(A,n) be the left singular matrix of Lλall(A,n).
Letting T 0all(A,n) = [T n A ; T̂ n A ; 0d], assuming that ‖Uall(A,n)Uall(A,n)ᵀT 0all(A,n)‖2 ≥ ξ‖T 0all(A,n)‖2 with a constant ξ ∈ (0, 1], substituting the upper bound Eq.(42) in Theorem 3 into Eq.(56) yields that ∑
b∈[B]
Yn,b ≤ ( κmaxall √ ξ−2 − 1 ) CSC max θ̄ √ ρλ d, (57)
where CS = maxn∈[N ],A∈A ‖SnA‖1, Cmaxθ̄ = maxA∈A,n∈[N ] ‖θ̄ n A‖2.
From Eq.(54), Eq.(55), Eq.(57) and the definition of our sketched policy, letting CY =( κmaxall √ ξ−2 − 1 ) CSC max θ̄ , we obtain that
Reg({AIn,b}n∈[N ],b∈[B]) = ∑
n∈[N ],b∈[B]
[ max A∈A 〈θ∗A, sn,b〉 − 〈 θ∗AIn,b , sn,b 〉]
≤ ∑
n∈[N ],b∈[B]
[ max A∈A (〈 θ̃nA, sn,b 〉 + α √ sᵀn,b (W n A) −1 sn,b ) + Yn,b − 〈 θ∗AIn,b , sn,b 〉]
= ∑
n∈[N ],b∈[B]
[〈 θ̃nAIn,b , sn,b 〉 + α √ sᵀn,b ( W nAIn,b )−1 sn,b + Yn,b − 〈 θ∗AIn,b , sn,b 〉]
≤ 2α ∑
n∈[N ],b∈[B]
√ sᵀn,b ( W nAIn,b )−1 sn,b + 2 ∑ n∈[N ],b∈[B] Yn,b
≤ 2αCreg √ B ∑ n∈[N ] √√√√∑ b∈[B] sᵀn,b ( ΨnAIn,b )−1 sn,b + 2NCY √ ρλ d = 2αCreg √ B ∑ n∈[N ] √√√√∑ b∈[B] 〈 sn,b s ᵀ n,b, ( ΨnAIn,b )−1〉 + 2NCY √ ρλ d = 2αCreg √ B ∑ n∈[N ] √∑ A∈A 〈 SnᵀA S n A, (Ψ n A) −1 〉 + 2NCY √ ρλ d
= 2αCreg √ B ∑ n∈[N ] √∑ A∈A tr ( SnᵀA S n A (Ψ n A) −1 ) +O(N √ ρλ d),
≤ 2αCreg √ BM ∑ n∈[N ] √ max A∈A { tr ( SnᵀA S n A (Ψ n A) −1 )} +O(N √ ρλ d). (58)
When the structural assumption in Theorem 3 is not satisfied, from Eq.(41), we can obtain that the second term in Eq.(58) is also of order O( √ ρλ d), which does not influence the order of the final regret bound. Finally, combining Eq.(58) with lemma 3 in (Han et al., 2020) gives the final regret bound.

heading: C DETAILED EXPERIMENTAL SETTINGS AND MORE EXPERIMENTAL RESULTS
text: In this section, we provide more details and results in the experiments.

heading: C.1 DESCRIPTION OF DATASETS
text: Table 3 summarizes the description of datasets used in the experiments.
Next, we provide more details about the three datasets.
Synthetic Data. Inspired by the experiments in (Saito et al., 2020), the synthetic data generation procedure was formulated as follows, which simulates the streaming recommendation environment.
• Context si ∈ Rd: we drew elements of si independently from a Gaussian distribution N (0.1, 0.22), where d = 40;
• Click-Through-Rate (CTR): the CTRs for the 5 actions were respectively set as {10%, 15%, 25%, 20%, 30%};
Criteo Data. We used the publicly available Criteo dataset5, consisting of Criteo’s traffic on display ads over a period of two months (Chapelle, 2014), where each context consists of 8 integer features and 9 categorical features. Following the experiments in (Yoshikawa & Imai, 2018), the categorical features were represented as one-hot vectors and then concatenated to the integer features. We reduced the dimensionality of the feature vectors to 50 using principal component analysis (PCA). All of the algorithms were tested in a simulated online environment that was trained on users’ logs in the Criteo dataset. Specifically, we chose several campaigns from the Criteo dataset, where each campaign represents a category of items and corresponds to an action. This online environment contains a prediction model for the CVR, which was well trained by applying DFM (Chapelle, 2014) using the true user feedbacks. This environment model was trained for each chosen campaign, whose AUCs are ranging from 70% to 90%, assuring that the online environment can provide nearly realistic feedbacks. To simulate the uncertainty of user behaviors, Gaussian noises with zero-mean were added to the model parameters. At each step, the online environment randomly selected a campaign and samples one context from this campaign, and revealed the context to the agent with a preset CTR. To generate a reasonable sequence of instances, the environment kept the order of timestamps of the contexts in each campaign. We tested our algorithms and the baselines with the following two online environments on the Criteo dataset: Criteo-recent contains 5 campaigns (75, 000 instances) chosen from the recent campaigns, corresponding to 5 actions; Criteo-all contains 15 campaigns (1, 276, 000 instances) chosen from all the campaigns, corresponding to 15 actions.
Data Collected from a Real Commercial App for Coupon Recommendation. To verify the effectiveness and efficiency of our algorithms on real products, we conducted experiments on a real dataset collected from a commercial social app. We call this dataset commercial product, where the data were collected after the users gave consent, and did not contain any personally identifiable information or offensive content. Since this dataset from a commercial app is proprietary, we did not provide a URL. We will release this dataset after the publication of this paper. In this commercial app, after clicking a recommended coupon, a user may convert the coupon after some time, or just leave it there. The dataset was collected during a 1-month period with a subsampling, and consists of 216, 568 instances from 5 categories of coupons, where each context is described by 86 numerical features and 16 categorical features. The timestamps of clicks and conversions were
5https://labs.criteo.com/2013/12/conversion-logs-dataset/
also recorded. Following the settings on the Criteo data, we also represented the categorical features as a one-hot vector, reduced the dimensionality of the feature vectors to 50 by PCA. The action space contains 5 actions, where each corresponding to one coupon category. Due to the limitation of real online experiments, in this experiment, we still trained DFM using the true user feedbacks as the online environment, where AUCs range from 75% to 90%.
To simulate the real environment under partial-information feedback, The experiments were conducted in environments where the distribution of the initialization data is atypical. Specifically, in the experiments, we set different numbers of the initialization instances for each action. In the synthetic environment, we set the number of the initial instances as 140, 210, 350, 280, 420 for the 5 actions, respectively. In Criteo-recent, we set the proportion of the initial instances as 0.1, 0.15, 0.25, 0.2, 0.3 for the 5 actions, and set the number of the initial instances as [100 : 23 : 423] for the 15 actions in Criteo-all.

heading: C.2 DETAILED SPECIFICATION OF HYPERPARAMETERS
text: In these experiments, the true reward is defined by Rtruei,A = λcCi,A + (1− λc)Vi,A (Ci,A and Vi,A denote true binary variables of user click and conversion when executing action A given context si), where λc = 0.01 on the synthetic data, Criteo Data, and commercial product data, respectively. As in most contextual bandit literature (Li et al., 2010; Chu et al., 2011), we set the regularization parameter λ = 1 in the Euclidean regularization. According to theoretical analysis in Remark 3, we set the batch size as B = C2BN/d, set the constant CB ≈ 25 and the sketch size c = 150 on all the datasets (B = 1400, 1000, 4000, 1700 for synthetic data, Criteo-recent, Criteo-all, and commercial product). The regularization parameters ω, α in our policy and that in the batch UCB policy were tuned in [0.2 : +0.2 : 1.2]. For the SJLT in SPUIR and its variants, sketch size was set as c = 150 and the number of block D was selected in {1, 2, 4, 6}. Except for the rate-scheduled variants of our approaches, the imputation rate γ was selected in [0.1 : +0.2 : 0.9]. Besides, the discount parameter η was tuned in [0.1 : +0.2 : 0.9]. In the nonlinear variant of our approach SPUIR-Kernel, we selected the dimension of the random features dr in {50, 100, 200} and the kernel width of Gaussian kernel in {2−(i+1)/2, i = [−12 : 2 : 12]}. Rate-Scheduled Approach. We equip PUIR and SPUIR with a rate-scheduled approach, called PUIR-RS and SPUIR-RS, respectively. We design a rate-scheduled approach following the theoretical results about the imputation rate γ. From Remark 1&2, we can obtain that a larger imputation rate γ leads to a smaller variance while increasing the bias. From Remark 4, we conclude that the additional bias term includes a monotonic decreasing function w.r.t. number of episodes under mild conditions. Therefore, instead of using a fixed imputation rate, we can gradually increase γ with the number of episodes, avoiding the large bias at the beginning of the reward imputation while achieving a small variance. Specifically, we set γ = X% for episodes from (X − 10)%×N to X%×N , where X ∈ [10, 100].

heading: C.3 MORE EXPERIMENTAL RESULTS
text: For better illustration, in Figure 3 of the manuscript, we omitted the curves of algorithms whose average rewards are 5% lower than the highest reward. Now we provide the curves of all the algorithms in Figure 5.

Review summaries:
This paper addresses batched contextual bandits, with a fixed set of actions, and separate unknown parameters for each action. The authors propose an approach where the unobserved rewards (i.e. the rewards that would have been obtained if actions that hadn’t been selected for a given context) are imputed, and these imputed values are incorporated in to the regularization of the parameter estimates in a Lin-UCB-like algorithm. For reasons of computational efficiency, the authors also design a process to approximate this regularized estimator via a ‘sketching’ technique. For the approaches with and without sketching, the authors derive a $O(\sqrt{dMT})$ regret bound, where M is the number of actions, and d is the dimensionality of the parameter vectors, which broadly matches what is expected in the non-batched setting. They argue that the proposed algorithms have uniformly lower variance in the instantaneous regret than approaches without imputation and any increase in bias decreases exponentially quickly. Versions with time-adaptive parameters, and for non-linear functions are proposed without a full theoretical treatment, and all the proposed algorithms are shown to perform well in an empirical study.

The paper considers the contextual batched bandit setting and introduces the idea of imputation utilizing the non-executed actions in each batch. This provides better regret properties than without and also further speedup is provided by considering the sketch version.  Theoretical results in terms of sketching performance are also provided such as going down from O(Bd^2) to O(cd^2) for sketch size c as well as the regret bounds of the sketched approach SPUIR.  Experimental results are shown on a couple of datasets to showcase the improved performance over state-of-the-art batched bandit algorithms such as BEXP3, BLTS-B.

The paper considers the behavior of a series of algorithms for learning in a batched bandit setting, where parameters are arm/action specific, rather than shared across arms/actions.   These algorithms are based on UCB like techniques with the addition of a regularization term that aims to use information from imputed, unobserved rewards. Such techniques are present in the linear regression and dimensionality reduction literature where one aims to use either prior information or  data distribution information to aid prediction. However, to my knowledge, these formalisms are quite  new to online settings like bandits, thus making the presented approach appealing.