Partial Information as Full: Reward Imputation with Sketching in Bandits
Authors: Xiao Zhang
Ninglu Shao
Zihua Si
Jun Xu
Wenhan Wang
hanjing su
Ji-Rong Wen
Venue: ICLR 2022 Submitted (2022)
Keywords: reward imputation
bandit
sketching
regret analysis

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 an exponentially-decaying 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.

Under review as a conference paper at ICLR 2022
PARTIAL INFORMATION AS FULL: REWARD IMPUTATION WITH SKETCHING IN BANDITS
Anonymous authors Paper under double-blind review
ABSTRACT
We focus on the setting of contextual batched bandit (CBB), where a batch of re- wards is observed from the environment in each episode. But these rewards are partial-informatie 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 sketch- ing in CBB, which completes the unobserved rewards with the imputed rewards approximating the full-information feedbacks. Specifically, we formulate the re- problem of imputation regularized ridge regression, which
ward imputation captures the feedback mechanisms of both the non exeeuexe and executed actions. To reduce the time complexity of reward imputation 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 ex- tensions 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 dataset from commercial app.
large batch of data, we
INTRODUCTION
Contextual bandits have been widely used in real-world sequential decision-making problems (Li (ct al. 2010 Lan & Baraniuk 2016 Yom-Tov et al., 2017; Yang et al.) 202I), where the agen- t 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 con- sider more complex setting-conten 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, actions to the agent as the feedbacks, while hiding the rewards of non-exeee executed actions. We refer to this category of limited feedback as the porriallinffrmaation 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 ipploitation-xxplrrannet
inevitable that the environment only reveals the rewards of the executed
tradcoff on the context space and reward space (Han et al.) 2020) Zhang et al. (2000_00oo 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, not utilized by existing batched bandit approaches.
In contextual bandit settings where the policy is updated fully online, several bias- correction ap- proaches have been introduced address the partial-information feedback. [Dimakopoulou et al.

---

Under review as a conference paper at ICLR 2022
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) de- signed 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 (019) 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 ap- proaches have been demonstrated be effective in contextual bandit settings, little efforts have been spent to address the under- sudle-utiiizaiion of partial-informan 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 observa- tions, 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 ap- proximation, achieves instantaneous regret with 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 sublinear regret bound against the optimal policy, and reduces the time complexity from (Bd2) to (ced²) for each action in one episode, where B denotes the batch size, the sketch size, and d the dimensionality of inputs, satisfying
< 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 col- lected from a real commercial product 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 statistics and learn- ing theory including 2-armed bandit (Perchet et al.) 2016), multi-armed bandit (Gao et al.) 2019 Zhang ct al., 2020 Wang & Cheng (020), and contextual bandit (Han et al. 2020 Ren & Zhou 2020 Gu et al. 2021) Han et al. (020)) 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 al. (2020) provided methods for inference data collected in batch- es using bandits, and introduced a batched least squares estimator for both multi-arm and contextual bandits. Recently, [Bsfandiari 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, c.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.
PROBLEM FORMULATION AND ANALYSIS
First, we introduce some notations. Let [x] = [Aj)e the action space containing M actions. [A; B] [[AT, BUJT, || || || denote the Frobenius norm, 1-norm, and spectral norm of matrix A, respectively, ||a/| and ||ll| be the l f-normm and the f2-norm of a vector a, min (A) and maxx (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 D. where the decision process is partitioned into N episodes, and in each episode, CBB consists 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 context- action pairs and the observed rewards of the executed actions into data buffer D. The reward R in CBB is a partial-informatun feedback where rewards are unobserved for the non-executed actions.
S C Rd be the context space, A =
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 8; E S C IRd and action A E A. assume that the expectation of the true reward Ri
2

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Contextual Batched Bandit (CBB)
INPUT: Batch size B, number of episodes N, action space A = { (As)seIM) context space S S R
1: Initialize policy + 1/M, sample data buffer D2 = {(Su,a, Ato,s be(()) using initial policy po
2: for n 1 to N do
Update policy pn on 2n. (Policy Updating) B do
4: b
5: Observe context 8r.6
6: Choose AI E A following the updated policy (*..)).)) {Ont ie Decision)
7: end for
D 4- ((Sn,hh Arn, Ro, RoED) where Ba,s denotes reward of action Ar,, on context Sn,b
9:
end for
determined by an unknown action-specific reward parameter vector 0'A E R4: E [ 8.] =
(07,8;) s:) (the linear reward will be extended to the nonlinear case in Section 5 This setting for reward feedback matches many real-world applications, c.g., each action corresponds to 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 perfor- mance of policy updating in the CBB setting. We first conducted empirical comparison by applying the batch UCB policy (Han et al., (020) to environments under different proportion- of received reward feedbacks. in particular, the agent under full-information feedback ceive all the rewards of the executed and non-executed actions, called Full-Information CBB (FI- CBB) setting. From Figure [ 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 Theorem D The detailed description and proof of Theorem I can be found in Appendix
Theorem 1. For any action A E and contex- t E S. let 0% be the reward parameter vec- tor estimated by the batched UCB policy in the n-- th episode. The upper bound of instantaneous regret (defined by (0"), &,) (0'A, 8;) in the FI-CBB set- ting is tighter than that in CBB setting (i.e., using the
Average
6240
0335
Number of Episodes
Figure 1: Average rewards of batch UCB policy (Han et al. 2020) under different pro- portions of received reward feedbacks, in- teracting with the synthetic environment in Section 66 where a% feedback means that x% of actions can receive their true rewards
conclude that the price paid for having access only to the partial-informatio feedbacks is the deterioration in the regret bound. Ideally, the policy would be updated using the full- information feedback. In CBB, however, the full- information 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 cap- tured. So why don't we use these maintained reward parameters estimate the unknown rewards for the non-executed actions? Next, we propose efficient reward imputation approach that uses this additional reward structure information for improving the performance of the bandit policy.
From Theorem
EFFICIENT REWARD IMPUTATION FOR POLICY UPDATING
In this section, present 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 different estimated reward parameter vector for each action. As shown in Figure2 2, in contrast 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
3

---

Under review as a conference paper at ICLR 2022
Imputed Context S Matrix No
Reward Vector
Context SR Matrix
Reward
Context S Matrix
N
Nj
Vector
R
B
Reward Vector
Imputed
ÑJ Vector
Reward
R
R
B Full- Full-Information
CB8
CBB with Reward Imputation
Figure 2: Comparison of the stored data corresponding to the action A, E A CBB, CBB with our reward imputation, and full-information CBB, in the (n + 1 episode
each action A, E A.j E [M], we store context vectors and rewards corresponding to the steps in which the action A5 is executed, into context matrix S'A R2 xd and reward vector R", RR respectivelly where NJ denotes the number of steps (in episode n- in which the action Aj is executed. Additionally, for any A, J E [M], we store context vectors corresponding to the non- executed steps of action A, (denote the number non-executed steps by Nz i... Ny B NT)), into an imputed context matrix S% E 83 xd and compute the imputed reward vector as follows:
RA
(r.2))) ...., nn (A₂)) E R
[M),
where rn.b (A,) = (0% 8n,b) denotes the imputed reward for each step E [Ny). and 8n,6 is the b-th row of 5% Then, we obtain several block matrices by concatenating the context and reward matrices from the previous episodes: L%, [S S : E RL Th
5x R T
[R]
Ra,
R4, -"=
DA A
.................. i.
R
R 25 L
En=o NA. In the (n + 1)-th episode, the estimated parameter vector 0% of the imputed reward for action Aj can be updated by solving the following imputation regularized ridge regression:
n = arg min OE
L7 0 Tx
LA
1 Tx, +
n = O,.,..,NNN 1 (1)
Observed Term
Impulation Term
where 7 E [0, 1] the imputation rate which controls the degree of reward imputation and measures a trade-off between bias and variance (Remark [ À > O the regularization parameter, yielding
0,
PA 787,
that can be obtained by the closed least squares solution, where A = AI $ n1
+
n+1
A,
A
T ++ Φ + S AA A
A, = b4, =b); + +S R' i i=+1= nb% + + Rea
a+ = 1 S S Sm Ay
(4)
and v (0, is the discount parameter which controls how fast the previous imputed rewards forgotten, and can help guarantecing the regret bound in Theorem
Efficient Reward Imputation using Sketching. As shown in the first columns in Table [ the overall time complexity of the imputation for each action is O(Bd) in each episode, where B represents the batch size, and the dimensionality episode, reward imputation increases the time complexity from O(Bd²) of the approach without imputation (M Bd2). address this issue, we design an efficient reward imputation approach using sketching, which reduces the time complexity of each action one episode from O (Bd) to (cd²), where e denotes the sketch size satisfying < c and od > B. Specifically, in the (n+ + 1) episode, the imputation regularized ridge regression Eq.[ can be approximated by [
the input. Thus, for the M actions one
sketched ridge regression as
@n+1 arg min [I's (I7,0 11 ir,, [2% 0 1,x,--Tx)] +
(5)
DER
4

---

Under review as a conference paper at ICLR 2022
Table 1: The time complexities of the original reward imputation in (T (first 4 columns) and the reward imputation using sketching in 5 (last 4 columns) for action Aj in the (n+1))th episode, where N (Nz) denotes the number of steps in which the action A₃ is executed (non-executed) in episode n n 1, No + +N = B, and the sketch size e satisfying d < < B and cd > B (MM: matrix multiplication; MI: matrix inversion; Overall: overall time complexity for action Aj in one episode)
Original reward imputation in 1
Reward imputation using sketching in E5.
Item
Operation
Eq.
Time
Item
Operation
Time
Bu+i bot
MM
(Bd²)
G G
MM
O(ed?)
bat
MM
O(Bd)
PAj PA (W (WA+1)
MM
O(ed)
MI
O(d)
MI
Odd))
Sketching
O(N) d)
T A%
Sketching
O(Nyd)
Overall
(
Overall
(
where 0x+1 denotes the estimated parameter vector of the imputed reward using sketching for action A E A, C2 E == and T* Rxx 83 are the sketch submatrices for the observed term and the imputation term, respectively, and the sketch matrices for the two terms can be represented
I [Cay. CA,,.... ,.",
.. ER
πr [ Ch,,... C%,] &RexI
We denote the sketches of the context matrix and the reward vector by A := C", S', E Rexd and A,, : C²A, Ra, E RR, the sketches of the imputed context matrix and the imputed reward vector by A, :- 0% Sy E Rexd and AA, Č*,, R2, E R., and obtain the solution of Eq.
0471 (WA+1) -1 n+1
PAj + +1px) m2+11)
(6)
where 7) E (0, 1) denotes the discount parameter, W = Aaa + G + GG++1 A, and
Gxtt G + +
A,
PΛ
a+1 = -P', + + A,
(7)
Gutll A = G + A, Ag
PAj
putl = mP', + A, A
(8)
Using the parameter 0xt1, we obtain the sketched version of imputed reward as (n)) =
(0% A,. sn,b) at step b E [N.]]. Finally, we specify that the sketch submatrices (CA)AEE and Transform (SJLT) Kane Nelson 2014), where the sketch size is divisible by the number of blocks DJTl As shown in the last 4 columns in Table sketching reduces the time complexity from O(M Bd ) to (df for reward imputation of all M actions in one episode, where e < B. When Me Rs B, the overall time complexity of our reward imputation using sketching is even comparable to that without reward imputation which has a O(dd²) time complexity.
( CAAAAEA are the block construction of Sparser
Updated Policy using Imputed Rewards. Inspired by the UCB strategy (Li et al. 2010), the updat- ed policy for online decision of the (n + 1)-th episode can be formulated using the imputed rewards (parameterized by 0x in Eq. )2) or the sketched version of imputed rewards (parameterized by 07+1 in (6). Specifically, for a new context
origin policy pu+1 selects the action following A +- arg s) wisT -
AEA
sketched policy po+1 selects the action following A <- arg (0 8) + als (W s)} AEA
where wt 2 and a 2 are the regularization parameters in policy and their theoretical values are given in Theorem We summarize the reward imputation using sketching and the sketched poli- cy into Algorithm called SPUIR. Similarly, we call the updating of the original policy that uses reward imputation without sketching, the Policy Updating with Imputed Rewards (PUIR).
Since the numher of blocks of SJLT as d, we omit D in the complexity analysis.
5

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Sketched Policy Updating with Imputed Rewards (SPUIR) in the (n 1) episode
INPUT: Policy Pr. Da+1, A = sejr, a 2 0, E (0.1), 7 [0. 1. A 0. A ALa. G'A,"
Gn Ou. p², Pa, OUTPUT: Updated policy Pn+1
0% j E [MM]. batch size B, sketch size c, number of block
I: For all j [M,, store context vectors and rewards corresponding the steps in which the action Aj executed, into Ta E R xd and A2, E R
2: For all j E [M], store context vectors corresponding to the steps in which the action A, is not executed into F2, E A xd where NY +- B - -N
3: Fn,)(As) + (0%, for all A₂ E A and & E [NT], where An,6 à is the b-th row of T7
4: Compute imputed reward vector Ra,- (fr,1 -........................ f 8n. (A₂)} R for any j E [M]
5: for all action A; E A do
6:
GAAj < Gd, + T PAj
n+1 + Pd, + + A {Eq.77
7: G G + FATTA
gu41 + -p + + A
{Eq.88)
Ay:
8: WA Aaa + G2y +70A,1 dy
En-1, oxti (WX) (W (pA) + +xPx5
(Eq
9: end for
10: (s) selects action A arg max Max ( 00 8) a (WX+1)-1 s]
for new context
return (0 JAEA, JAEA, ((Wxt!) -1 AAEA
11:
4 THEORETICAL ANALYSIS
We provide the instantancous regret bound, prove the approximation error of sketching, and analyze the regret in the CBB setting. The detailed proof' can be found in Appendix B We first demonstrate the instantaneous regret bound of the original solution 0% in Eq. [..
Theorem (Instantaneous Regret Bound). Let 1j E (0.1) be the discount parameter, Y E [0. 1] the imputation rate. In the n-th episode, if the rewards (Rn,b) (D(B) are independen and bounded by CR. then, for any b E [B] and VA E A, with probability at least 1 8.
10% sn,b) (0 sn,t)) S [1111ll A ++ 2 & Cimpp] [s/ (4%) sn,b),
where Ln = "" + +, B == [20 log (2) and Ctmp > 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 the variance term. The variance term of our algorithm is not larger than that without the
reward imputation, i.e, for any a Rd, [sT (PT) s]² < [ST (Ala + 22)) "Ja.hurheer a larger imputation rate 7 leads to smaller variance term [ST (L s]a.
Remark (Smaller Variance). From Theorem we can observe that the proposed reward impu- tation achieves a smaller variance ([ (V))
sn,,] ) than that without the reward imputation.
Remark 2 (Controllable Bias). Our reward imputation approach incurs a bias term 7 Cimp in addition to the two bias terms X xl v that exist in every -CB--asee policy. But this additional bias term is controllable due to the presence of imputation rate 7y that can help controlling the addi- tional bias. Moreover, the term Cimp the additional bias can be replaced by a function fimp(n), and Simp (n) is monotonic decreasing w.r.l. number of episodes n provided that the mild condition /11 = (dd=1) holds (the defimition and analysis about fimp can be found in Appendix B. I). Over- all, the imputation rate 7y 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 Ty in Section 5
Although some approximation error bounds using SJLT have been proposed (Nelson & Nguyên 2013 Kane& & Nelson, 2014 Zhang & Liag 2019), it is still unknown what the lower bound of the sketch size while applying SILT 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 (0) (defined in Eq. 11) and the sketched ridge regression
The assumption about conditional independence of the rewards is commonly used in the bandits literature, which can he ensured using a master technology a thcoretical construction (Auer 2002 Chu al. 201T).

---

Under review as a conference paper at ICLR 2022
function by (0) (defined in Eq.
( for reward imputation, whose solutions (f.e., the estimated re- ward parameter vectors) are i arg min F(0) and 0 = arg minggs" (S)) Let y E [0, 1] be the imputation rate, X > 0 the regularization parameter, 8 E (0,0.1), & E (0, aMl = [L; /TL), and px | /l/ (l] | | + A). II and II are SJLT, assuming that D O - (d8-1) and
the sketch size c Ω (d polylog (dō-1) / with probability at least 1- (() - (L+PXE)
and |10 0||2 - 0 (vxx)) 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
== maxAAA [nE(N] (0 8n,b) - -00 (f'.,..' sn,b)),
where InD denotes the index of the executed action using the sketched policy P., (parameterized by (0%) AEA) step b in the n-th episode. Finally, we demonstrate the regret bound of SPUIR. Theorem 4 (Regret Bound of SPUIR). Lei T = BN be the overall number of steps, n E 10, be the discount parameter. Y [0, 1] the imputation rate, X > O the regularization parameter, Cimp be a positive constant. Assume that the conditional independence 2 holds and the upper bound of rewards is CR. M (poly(d)), T 2 d?,
C = maхĄAA |
assumption in Theorem
v- == [ log(2M B/ ( with 61 E (0,1),
XCg + v + + Cimps a a= wCa.
where Co > O which decreases with increase of 1/s and E E (0, 1). Let E (0, PA < be the constant defined in Theorem 3 and Creg be a positive constant that decreases with increase of 1/s. For the sketch matrices (IT A AmA.E)) and (î. AEAMELN) assuming that the number of blocks in SJLT D = ( log (dō² "), and the sketch size satisfying e = Q2 (d polylog (d5z') / then, for an arbitrary sequence of contexts (Sn,bnne[M] dE(B) with probability at least N + 82).
Reg({A (erg((An.o I.E(N),E)))) S 22aCreg
M.CregVIOM VIOM log(T + 1)(vaT - dB) + + (T PXDxx B)- (10)
Remark 3. Setting B = =((TTT)) and pxe = 1/d yields a sublinear upper bound of regret of order Ö provided that the sketch size c= (p polylog(d5,')) We can observe that the lower bound of is independent of the overall number of steps T, and a theoretical value of the batch size is B Cn/TTd Cj,NN/l where setting Cn R 25 is suitable choice that has been verified in the experiments in Section 6 In particular, when pX = O(1/d), the sketch size of order Di(d polylogd) is sufficient to achieve sublinear regret, which has been demonstrated in our experimental results. Since the lower bound of regret for contextual batched bandit in (Han eet 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.) [209 Dinakopoulou et al.) 2019). which is more simple setting than ours; (b) The first term in the regret bound (Q. measures the performance of policy updating using imputed (emmar((ss) 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 tighter regret (i.e., smaller policy error) after some number of episodes. (c) The second term on the right-hand side of Eq. (T)) is of order O(T pxedd 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 pxe, e.g., setting PxE --11/A yields sketching error of order O(T3/8 /2) provided that = 2(p3 d3 (ayylo((dz")/T)
rewards (called "policy error"). From Theoremaaand
5 EXTENSIONS OF OUR APPROACH
To make the proposed reward imputation approach more feasible and practical, we tackle the follow- ing two research questions by designing variants of our approach following the theoretical results:
We use the notation of Ô suppress logarithmic factors in the overall number of steps T.

---

Under review as a conference paper at ICLR 2022
RQ1 (Parameter Selection): Can 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 [ larger imputation rate y leads to 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. Specifi- cally, we set y = X% for episodes from (X- 10)% N to X% x N, where X E [10, 100). Application to Nonlinear Rewards. For RQ2, we provide nonlinear versions of reward imputa- tion. 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 (n. =- (0%,, 8n,b), we use the following linearized nonlinear imputed rewards, denotes by (0, A))
1) SPUIR-Exp. We assume that the expected reward is an exponential function as GE(O, s) = exp (OTs). Then (0, A) = (0, VoGE(O, sn,b)) where VoGg(0, 8n,b) = exp (OT 8n,b) Sn.b- 2) SPUlR-Poly. When the expected reward is a polynomial function as Gp 8) = (0T 8) Then Th. (0 A) (0, VoGr(0, 8n,b)) where VoGr(0, 8,,b)) 2 (OT 8n.b) 8n,b-
3) SPUIR-Kernel. Consider that the underlying expected reward in a Gaussian reproducing kernel
Hilbert space (RKHS). We use T0, A) (0, o( ((s,,))) in random feature space, where the ran- dom feature mapping & can be explicitly detined as in (Rahimi & Recht 2007).
For SPUIR-ExP and and SPUIR-Poly, combining the linearization of convex functions SShale--Swarrd
2011) with Theorem 4 yields the regret bounds of the same order. For SPUIR-Kemel, using the approximation error of random features (Rahimi & Recht 2008), we can obtain a regret bound with an additional error of order O(B/Vd,), where de is the dimension of the random features.
6 EXPERIMENTS
We empirically evaluated the performance of our algorithms on 3 datasets: the synthetic dataset, publicly available Criteo datasef (Criteo- secriteo-rrcent,.. 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 lt al. 2020 Batched linear EXP3 (BEXP3) (Neu & Olkhovskayal 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) X- con(R) Silver 4114 CPU@ 2.20GHH, and repeated the experiments 20 times. We tested the perfor- mance 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- C3 (2N/dd /d, the constant C3 R 25, and the sketch size 150 all the datasets. The average reward was used to evaluate the accuracy of algorithms.
Performance Evaluation. Figure 3 (c) reports the average reward of SPUIR with its variants and the baselines. We observed that SPUIR and its variants achieved higher average rewards, demon- strating 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 practi- cal 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 base- line with the improvements of 1.07% CVR (conversion rate) and 1.12% CTCVR (post-view click- through&&conversion rate). Besides, our reward imputation approaches were more efficient than DFM-S, BLTS-B. The variants using sketching of our algorithms (SPUIR, SPUIR-SS) 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 IPW). Figure () illustrates per- formances of SPUIR and its nonlinear variants, where SPUIR-Keraa achieved the highest rewards indicating the effectiveness of the nonlinear generalization of our approach. For different decision tasks, a suitable nonlinear reward model needs be selected for better performances.
Parameter Influence. From the regret bound Eq. (1), we can observe that larger batch size B results in a larger first term (of order OB), called policy error) but a smaller second term (of order
thups://labss.co wttp:a/w..rrrrrr.c/010.1.a. 1/1 32ma////mmmmmmoooooooaoaaaaaaa
8

---

Under review as a conference paper at ICLR 2022
Table 2: Performance comparison of coupon recommendation commercial al product
Algorithm
CVR (mean + std)
CTCVR (mean + std)
Time (sec., mean std)
DFM-S
0.8656 + 0.0473
0.3317 + 0.0218
302.3140 1 8.3045
SBUCB
0.8569 + 0.0037
0,4277 0.0084
43,5435 1 0.3659
BEXP3
0.4846 + 0.0205
0.2425 + 0.0116
53,5001 = 0.9220
BEXP3-IPW
0,4862 = 0.0187
0,2436 + 0.0113
56,0101 = 1,4142
BLTS-B
0.8663 + 0.0178
0,4285 + 0.0157
218,2109 = 1.8198
PUIR
0.8807 = 0.0053
0,4411 0.0029
184.3575 = 2.2346
SPUIR
0,8770 + 0.0059
0.4397 + 0.0032
81.5753 + 1.5879
PUIR-RS
0.8763 + 0.0056
0,4389 + 0.0030
180.4999 = 1.7763
SPUIR-RS
0.8758 + 0.0058
0.4391 + 0.0031
80.8003 + 2.9030
ANNERAR Rowazd
224
600
1948
328
Number Eplacces
Number Eploodas
Episodes
(a) synthetic data
(b) Criteo-al
(c) commercial product
Average Reword
Fxve tge Beowerd
can
coc
zonn Jaaa ane cown Jther sown vit Wha
Episndes
(d) nonlinear reward
(c) batch size B
sketch size
Figure 3: (a), (b), (c): Average rewards of the compared algorithms, the proposed SPUIR and its variants on synthetic dataset, Criteo dataset, and the real commercial product data, where we omitted the curves of algorithms whose average rewards are 5% lower than the highest reward; (d): SPUIR and its three nonlinear variants on synthetic dataset; (e): SPUIR with different batch sizes on Criteo-recent (f): SPUIR and SPUIR-RS with different sketch sizes synthetic dataset
O(1/B), called sketching error), indicating that a suitable batch size B needs be set. This conclu- sion was empirically verified in Figure Be). where B 1, 000 (Cn 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 CB/TTd= = C2,N/C is a suitable choice while setting CB s 25. From the results in Fig- ( observe that, for our SPUIR and SPUIR-RS, the performances significantly increased when the sketch size e reached 10%B (= dloog d), which demonstrates the conclusion in Remark that only the sketch size of order c Q(d polylogd) is needed for satisfactory performance.
CONCLUSION
Partial-ine intiialliffrmationn feedback is ubiquitous in real-world applications, where reward feedback is usu- ally underutilized for learning. This paper proposes a theoretically sound and computationally ef- ficient reward imputation approach for contextual batched bandits, which mimics the reward gen- cration mechanism of the environment approximating the setting of full-information feedback. The proposed reward imputation approach reduces the time complexity of imputation large batches of data using sketching, achieves a relative-error bound for sketching approximation, has an instan- taneous regret with controllable bias and smaller variance, and enjoys 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.

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
To verify the effectiveness and efficiency of our algorithms on real products, we conducted experi- ments real dataset collected from a commercial social app. We call this dataset commereil a product, where the data were collected after the users gave consent, and did not contain any personally identifiable information or offensive content.
REPRODUCIBILITY STATEMENT
The source code 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 commer acimercia a product is non-public, we did not provide 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.
REFERENCES
Peter Auer. Using confidence bounds for exploitation-eexllrraion trade-offs. Journal of Machine Learning Research, 3:397-422 2002.
Iaii Bistritz,, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet, Online EXP3 learn- ing in adversarial bandits with delayed feedback. Advances in Neural Information Processing Systems 32, pp. 11399-11358, 2019.
Jean Bourgain, Sjoerd Dirksen, and Jelani Nelson. Toward a unified theory of sparse dimensionality reduction in Euclidean space. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, pp. 499-508, 2015.
Daniele Calandriello, Alessandro Lazarie, and Michal Valko. Efficient second-order online kernel learning with adaptive embedding. In Advances in Neural Information Processing Systems 30, pp. 6140-6150, 2017.
Olivier Chapelle. Modeling delayed feedback in display advertising. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1097- 1105, 2014.
Niladri S. Chatterji, Aldo Pacchiano, and Peter L. Bartlett. Online learning with kernel losses. In Proceedings of the 36th International Conference on Machine Learning, pp. 971-980, 2019.
Ku-Chun Chou, Hsuan- Tien Lin, Chao-Kai Chiang, and Chi-Jen Lu. Pseudo-reward algorithms for contextual bandits with linear payoff functions. In Proceedings of the 6th Asian Conference on Machine Learning, pp. 344-359, 2015.
Wei Chu, Lihong Li, Lev Reyzin, and Robert E. Schapire, Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens. Balanced linear contextu- al bandits. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, pp. 2019.
Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab S. Mirrokni. Regret bounds for batched bandits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 7340- 7348, 2021.
Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou. Batched multi-armed bandits problem. In Advances in Neural Information Processing Systems 32, pp. 501-511, 2019.
Quanquan Gu, Amin Karbasi, Khashayar Khosravi, Vahab Mirrokni, and Dongruo Zhou. Batched neural bandits. arviv preprint 102i 2021.
10

---

Under review as a conference paper at ICLR 2022
Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose H. Blanchet, Peter W. Glynn, and Yinyu Ye. Sequential batch learning in aate-nctiion linear contextual bandits. CoRR, abs/2004.06321, 2020.
Chi Jin, Zeyuan Allen-Zhu Sébastien Bubeck, and Michael Jordan. q-learning provably effi-
cient? In Advances in Neural Information Processing Systems 31, 2018.
Daniel M Kane and Jelani Nelson. Sparser JonnsoonnLnndddesstuuu transforms. Journal of the ACM, 61(1):4:1-4:23 2014.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. Advances in Neural Informa- fion Processing Systems 32, pp. 5869-58855588 5079, 2019.
Andrew S. Lan and Richard G. Baraniuk. A contextual bandits framework for personalized learning action selection. Proceedings of the 9th International Conference on Educational Data Mining, pp. 424 429, 2016.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th International Conference World Wide Web, pp. 661-6770 2010.
Shuai Li. Wei Chen, Shuai Li, and Kwong- Sak Leung. Improved algorithm online clustering of bandits. In Sarit Kraus (ed.), Proceedings of the 28th International Joint Conference on Artificial Intelligence, volume Li20191mproved, pp. 2923-2929, 2019.
Jelani Nelson and Huy L Nguyén. OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proceedings of the 54th Annual Symposium on Foundations of Comput- er Science, pp. 117-126, 2013.
Gergely Neu and Julia Olkhovskaya. Efficient and robust algorithms for adversarial linear contextual bandits. In Proceedings of the 33rd Conference on Learning Theory, pp. 4049-3068, 2020.
Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg. Batched bandit prob- lems. The Annals Statistics, 44(2):660 681, 2016.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems 20, pp. 1177-1184, 2007.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances in Neural Information Processing Systems 21, pp- 1313-1320, 2008
Zhimei Ren and Zhengyuan Zhou. Dynamic batch learning in high-dimensional sparse linear con- textual bandits. arXiv preprint arXiv:2008. 1918, 2020.
Yuta Saito, Gota Morishita, and Shota Yasui. Dual learning algorithm for delayed conversions. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 1849-1852. 2020.
Shai Shalev-Shwarz... Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194 2011.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias N. Flaounas, and Nello Cristianini. Finite-time analysis of kernelised contextual bandits. In Proceedings of the 29th Conference Uncertainty in Artificial Intelligence, 2013.
Chi-Hua Wang and Guang Cheng. Online batch decision secciion-mmaking with high-dimensional covariates. In Proceedings of the 23rd International Conference Artificial Intelligence and Statistics, pp- 3848-3857, 2020.
Shusen Wang. Alex Gittens, and Michael W. Mahoney. Sketched ridge regression: Optimization perspective, statistical perspective, and model averaging. In Proceedings of the 34th International Conference on Machine Learning, pp. 3608-3616, 2017.
David P Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 10(1-2):1-157, 2014.

---

Under review as a conference paper at ICLR 2022
Jiaqi Yang, Wei Hu, Jason D. Lee, and Simon Shaolei Du Impact of representation learning in linear bandits. In Proceedings of the 9th International Conference on Learning Representations, 2021.
E. Yom-Tov, G. Feraru, M. Kozdoba, S. Mannor, and Hochberg. Encouraging physical activity in patients with diabetes: Intervention using reinforcement learning system. Journal of Medical Internet Research, 19110),333, 2017.
Yuya Yoshikawa and Yusaku Imai. A nonparametric delayed feedback model for conversion rate prediction. OrXiv:1802.00255:0 2018.
Kelly W. Zhang, Lucas Janson, and Susan A. Murphy. Inference for batched bandits. In Advances in Neural Information Processing Systems 33, pp. 9818-9828 2020.
Xiao Zhang and Shizhong Liao. Incremental randomized sketching for online kernel learning. In Proceedings of the 36th International Conference on Machine Learning, pp. 7394-7403, 2019.
12

---

Under review as a conference paper at ICLR 2022
A DETAILED PROBLEM FORMULATION AND DETAILED PROOF IN PROBLEM ANALYSIS
In this part, we give the detailed problem formulation and the detailed proof of Theorem in problem analysis in Section 2
A.1 DETAILED PROBLEM FORMULATION OF CBB
In this paper, we focus on the setting of contextual batched bandits (CBB), which can be formulated as 6-tuple (S, A. p, R, N, B):
Context space S C Rd means vector space containing the context information received at each step, e.g. context summarizes the information of both the user and items in recommendation sce- narios.
Action space A {A, [E[]] contains M candidate actions for execution. As an example, in rec- ommender systems, each action corresponds candidate item, and selecting action means that the corresponding item is recommended.
Policy p determines which action to take each step, which function of the context 8 S and outputs an action for execution (or a selection distribution over action space A). Reward R in CBB is a purtial-information feedback where rewards are unobserved for the non- executed actions. Consider stochastic bandit setting, where the expectation of the true reward is assumed be function of the context 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 unknown parameter vector 0% E Rd A E A. This setting for rewards matches many real- world applications, c.g., each action corresponds to 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 environ- ment 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 data buffer D at the end of each episode.
A.2 DETAILED DESCRIPTION AND PROOF OF THEOREM DIN PROBLEM ANALYSIS
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) this setting (see Algorithm 3). We demonstrate an instantaneous regret bound in Theerrm 5 where Theorem 5 is detailed version of Theorem | in Section
Algorithm 3 Batch UCB Policy Updating in the (n-+1)-th episode in Full-Information CBB Setting
INPUT: Policy po, data buffer Dr.1,, action space A {A₃ {AM) 0%, 0, E [M]. batch size B OUTPUT: Updated policy px+1
1: Let L. [(a+1)Bxd be the matrix that stores all context vectors till the n-th episode as the row vectors
2: For VA E AA, let TA E R(++1) be the reward vector that stores all the rewards of action A E -A till the
n-th episnde
3: // Policy Updating
4: Y.41 + L.IL,
do 6: @ + (Ia Yo+1) LATA
for all action
7: end for
8: For new context 8, Pn+1(#) (a) is choose the action following: A argmax (0 .8)
AEA
9: return {0 AEA
13

---

Under review as a conference paper at ICLR 2022
Theorem 5 (Instantaneous Regret Bound in Full-Informatic CBB Setting, Detailed Version of Theorem [. Let Ln-1 RnBxxd be the matrix that stores all the context vectors fill the (n 1 episode as the row vectors, and TA-1 E RuB be the reward vector that stores all the rewards of action A A till the (n 10--1--s 1) episode. Given the action space A {Aj je(My, in the n-th episode, assume that the rewards are independent and bounded by CR. Then, with probability at least 1 - 6. for any b E [B] and VA A. we have the following instantaneous regret bound in the n-th episode
- (0,, 8n,o)l 110 + /202 log(2MB88) Voh. (La + xx)
Sn.b.
(11)
where Yn obtained by
DT =I - En- and the parameter of reward model 0%2 in the batched UCB policy is
0a = arg min OER
T 122 1010 (Ia + r..) LT TT
Further, the instantaneous regret bound (T. in FI-CBB setting is tighter than that in CBB setting (iee., using the partial- inrrialliffommaioon feedback). In particular, the variance term V (Ia + n Sn,6 is smaller than that in CBB setting.
Proof of Theorem
4 By the formulation of 0 and the triangle inequality, we first obtain that 10%, 8n.b) (0) 8n,b2
Th (Ia T..)
LT Tn-1 sT 07
TT (Ia r,, -1
LT n-1 Tn-1 (Ia + .n, 02]1
(12)
1 (La + r,)
LT T
La + (i-i)bn-) 02
1, (Ia + rr,)
-
Tm-1 L 1
T nn (Ia + xx,) 0%
21 (Ia + r.,) x.) E
T
In-
+ 11 (Ia + r,) -,,0 0
Next, we bound the two terms in the last row Eq.
Bounding ss (Ia + rx,) D T
L L_ 0 10
T In-10% and the received rewards are independent, by the Azuma- Hoeff-iggg
Since E
bound, we have
(Ia rn,) -.n (TT- En-10h) 2 UV sT (Ia + xn) Sn.b
Pr
TT n.b
(13)
128 n.h (Ia + xa) 8n.b
< 2exp
20 R
Ln-1 1 (La + xnn) sn,bll
where V > is some constant. Since
[ (Ia r.,) sn,bll 1 = n.h (Ia + rnn)
IT n- 1 In (Ia + xnn) 8n,b
< TT (La + rnn)
[Is+ _ (Is + rx,) sn.
< s (Ia + xn) -1 (Ia + Yn)) (Ia + xnn) Sm,b
% (Ia + nn) 8n.b:
combing with Eq. 13 implies the following results
Pr
f T
(Ia r..
_ (Tm-1 In. 00)00)) 2 UV 8 (Ia + r,)) 8
In-10%)
(14)
< <2exp {
v²
20
14

---

Under review as a conference paper at ICLR 2022
Combing Eq 14 with the union bound, yields that, with probability at least 6, for any b E [B] and AA E A,
sT n,6 (Ia r..) _ (TA-)
1n-107)
u s7 (La + xn) 8n,b.
(15)
where the failure probability is
v²
8 6=2MBexp
202
yielding that 2 (2M
Bounding s4 (La + nx 0%
Since Y, is positive semi-definite, combining with the Hölder inequality, we obtain
TT.6 (Ia xx,) 0% < 110%|12 (La r,,) 8v.h
1001l22 8n.b (Ia xn,) (Ia + xr,) 8n,b
(16)
< |101112 sn, (Ia + xn) (Ia nn, (Ia r.)) 8n,
||01l22 V 8n,6 (La + xn) nn)=1 8n.b.
Combing Eq. 15) and Eq. 16 concludes the proof.
obtain that the variance term in full nall-information setting is smaller than that in partial-informatie setting.
Similarly the proof of 2q.29 29
B DETAILED PROOFS IN THEORETICAL ANALYSIS
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 the CBB setting. Figure describes the dependence structure of our theoretical results.
Approximation Properties of Sketching
Approximation Error Bound of Reward Imputation
Instantaneous Regret Bound
Regret Bound of SPUIR
Figure 4: The dependence structure of theoretical results, where the proof of instantaneous re- gret bound (Theorem 2) is provided in Appendix B.I the analysis of approximation properties of sketching (Theorem 6) given in Appendix B.2] the approximation error bound of reward imputa-
tion (Theorem 3) is proven in Appendix B.3 and the regret of SPUIR (Theorem 4) is analyzed in Appendix B.4
15

---

Under review as a conference paper at ICLR 2022
B.1 PROOF OF THEOREM! 2
Before we provide the detailed proof of Theorem 2 we first demonstrate a lemma about the conver- gence and monotonicity the sum of functions, which the main tool for analyzing the additional bias of reward imputation.
Lemma 1 (Convergence and Monotonicity). Let f(n) a"= where (0,1) and is a positive integer. Then,
1) when 9(j is convergent, the limit lim (n) exists. Moreover,
lim f(n) 1
lim g(n).
(17)
2) f(n) is monotonic decreasing function if and only if g(5) satisfies, for any positive integer j 2
- 1)at-19(1) 9(1)
==1 1/2,
9(1) -
(1 - a) a (1--a3-11
(18)
g(1) 1/2.
2a -
Proof. Letting b(j) a- bjj) E [m]. and S(n) Σド= b(j), f(n) can be rewritten as f(n) = a" S(n).
1) Rewriting f(n) S(n)/a from the Stolz's theorem, we have
S(n) S(n 1)
lim f(n) = lim n-000
n-+00 a n a 1)
b(n)
lim
n-000
n a (n-1)
a m g())
lim
R-+00 a a (n-1)
lim g(n). a n-000
2) The condition that f(-) is a monotonic decreasing function equivalent to the following condi- tion: for and positive integer
f(n)
+ a * ((m+1)mm)))) <a"(()
< a(S(n) + +1] S(n)
b(n +1) S (1/a - 1) S(m).
(19)
From the equivalent condition Eq
19
we obtain the following recursion formula:
b(n + 1) S (1/a - S)
n-1
(()) < (1/a Σ
b(i)
6(3) < (1/a 1) [6(1) + b(2)
6(2) < (1/a- 1/la-16601) 6(1),
yielding that, for any positive integer j 2 2,
b(j) [(1/a + (1/a a- 1)2
+ 111a-118 1)1- M(1.
(20)
16

---

Under review as a conference paper at ICLR 2022
From Eq. 20) for # 1/2,
b(j) - (1/a - 1) [1 (1/a-1)
(1/a / - 1)5-1
6(1) (1-a) a) [1 (1/a 1)5-1 b(1);
1 (1/a 1)
(21)
2a
and substituting the definition of b(j) into (q. yields the equivalent condition
وOو (1 - a) 1 - (1/a 133
a 9(1)
2a
For 1/2, have the condition b(j) S (j - 1)6(1), which is equivalent to
((ه) S (j - 1)a= - 9(1) + g(t) s (1 1)a2 9(1).
Next, we provide the detailed proof of Theorem
Proof of Theorem each action A E A.
From the formulation of 0% and the triangle inequality, obtain that, for
00 8,,b)
(0) sn,
1 (VA)
(b) + +bbb)/
T 0
Nho (PA)
(D T + [
T Tm-1 0202
(I -x + [Ix ) Tm-1
(Na 2 + + 02
h {(1--1)) T---1 + (ia-)
T
AAaa + (L% 1)_ LA +7 [ ) 1/ 02]
T
sh (DX-1) (TA-1 Ld 0%a) -As -1
0
TT, (P)) "1> (ix-1) )
1 (fX-1- 1 08) 10-10))
< hh (VA) 1 1IT-1) (TA-1
-n--000 02))
+ 8 (VD")) -1 0% +
x
x(
n, (P)) -1 7 (D' [ n1 T (Tn-1 Σ -2-10)
x
(3) Next, we bound ( x and X A For convenience, we drop all the superscripts and subscripts
about n and b. Similarly to the proof of Theorem we bound x-() x(() as follows: with probability at least 1
x +
(2)
S (Al1021la 1) ST
(22)
where V = log (2M /0. For x (3)
A using the Cauchy- Schwarz inequality, we have
x
Ż v V
s 1|| | I
A
-v
STU (xtYEA) wn²o
TT -LLLOi
(23)
5 STV &
L, 0
17

---

Under review as a conference paper at ICLR 2022
[ - Since using the discount parameter vj E (0,1) in Eq. 4 equivalent multiplying both the imputed contexts and the imputed rewards by the parameter vij in each episode, we have, in the n-th episode,
Now we need to bound the term
| D 0 || -
(24)
where A -1 (n/(n-i-1)/ 11/2 (ejn) 1e, denotes an exponential-decay vector of the in- stantaneous regrets, and IR4, denotes the instantaneous regret at step in the i-th episode, i., IR = (0,0
81,0) (0) 8,,0)| From 24 letting
CIR:
IR4,5
(25)
BE[
be the cumulative instantancous regret the i-th episode, we can obtain the upper bound of Eq. (24 as follows:
T LA
0
A 47
l1
Σ
(n-i-1)/2 11/2
IRg.
(26)
1 [B]
Σ 17 (n
1n/1-11/2 CIR,
sE/n-11
= fimp(n))
where
fimp (n)
Σ (vn)) CIR. iE(n-1)
(27)
From monotone bounded theorem, we have that the limit of CTR, exists. From Eq. 17 Lemma T we get that fimp (n) is convergent and then has an upper bound. We denotes the upper bound of (n) by Cimp > 0, and then from (2. we have
T
0
Sn - Cimp-
(28)
Substituting 28)
28 into Eq. 23) yields the upper bound of x(
Then, we prove that
ST (1))
8 V ST (Ala + 2b)) 8.
(29)
holds, which is equivalent to
ST AI + +
I T (AI + $)
(30)
Letting + >Ia Φ. by Sherman-Morrison Mordrssooooooooaaubry formula, have
4 + + @0 1 = 19-1-70-15 [a + 11555-0-55 SO-1
= - 0- Ia S0 ST -1
(31)
S0-1
yielding that (3) is equivalent to
TT 2 0,
(32)
where
r T -I
[Ia/7 S0- 80-1
Let S UUS-- 0,51/3 V be the Singular Value Decomposition (SVD) of and S, respectively. Note that + = V. $ V. We can obtain that I is a square symmetric positive semi-definite matrix, since can be decomposed into
r QQQ..
18

---

Under review as a conference paper at ICLR 2022
where P. is the SVD of Ia/y
and
Q 1/ PAA
Thus, Eq.(22) holds, yielding that Eq. 30) also holds.
Finally, we prove that larger imputation rate " leads to a smaller variance term V (V) (V) 8.
From Eq. (.. the variance term can be represented as follows:
s M, 80 1/2
V 8T (V))
(33)
where My = Ia/7 + 50-15 ST. Letting M, = UM, MM, UM, be the SVD of My, and
UM, S0-1s from Eq. 333 we can written the variance term as follows:
1/2
ST V 8
8 T z AAA, M,
(34)
In Eq.34) we can observed that
1
= A'A, z (A 1/22 E
o max (M) + 1/7 11 min (M) + 1/7 1
where M- term.
which indicates that larger imputation rate y leads smaller variance
Finally, we provide a deeper understanding of the additional bias in Theorem
Remark (Controllable Bias). Our reward imputation approach incurs a bias term 7,21 Ctmp in addition the two bias terms Al10 ll2 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. Eq.(26), we can obtain that, the term Cimp in the additional bias can be replaced by a function ftmp (1. (defined in Eq. (7))), and the additional bias
term turns out be - Since (nmp(n) has the same functional form the function I (() in Lemmal 7 we fanf the conditions that [1)p(1) is monotonic decreasing following Eq. (8)) in Lemma 7 Specifically, letting CIR, be the cumulative instantaneous regret the i-th episode defined in 25).
1) when + 1/2, the condition of a monotonic decreasing finctioonn fimpl-) is equivalent to, for any positive integer 2 2,
(1- (
(ITT vT)
CIR, S
CIR1,
2
indicating that the regret after N episodes satisfies
/
v1j (nT-1 - v1))
CIR, S CIR1
Σ
2 -1
2SISN
25i5N
1 V
CIR
V
(1- -1)
2 25i5N
-CIR1 TT[2 - 1) 12/7 1+ (1 N+)
N+1]
1 [1 (1- -V) (V7)
N+1
CIR1 vn
1+
(35)
2 -1
2) for the case /1j 1/2, the condition of monotonic decreasing function fimp()) is equivalent to CIR, (i 1)((m))-IIII) for any positive integer > 2, indicating that the regret after
19

---

Under review as a conference paper at ICLR 2022
N episodes satisfies
Σ 2
CIR, S CIR1
Σ (i - (1-1)))))*
25iSN
VT
TT2 + N 1
CIR1
(VT)
(1 VT)
1 - v
1+N
2 2N-1
CIR1
1 vī (1 -1+ (1+NNTT
CIR1.
(36)
From Eq. 35) and 36). we can conclude that a monotonic decreasing duunetiingfunccioon fimp(.) indicates the upper bound of regret after N episodes is of order O(CIR1 /T). The conclusion also indicates that setting the discount parameter as vij = ((CIR,/N) achieves a O(N) regret bound (i.e., a O(VdT) regret bound following Remark 3 Note that setting the discount parameter / (CCRR, /NN is a mild condition, since the cumulative instantaneous regret CIR₁ is typically of order O(B) (B = O(dT/d) in Remark 3 yielding that vn O(d=)). Overall, since a larger imputation rate 7 leads 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.rt. number of episodes n, the additional bias term y 1 à fimp(n) can be easily controlled, e.g., gradually increasing ? with the number of episodes, avoiding the large bias from limp(()) the beginning of reward imputation. We design rate- scheduled approach for choosing the imputation rate 7 in Section
Remark 5 (Relationship to Exploration and Exploitation Trade-off). Exploration- dilemma is the key challenge in online learning under bandit settings. In the fall-information set- ting, 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 lower variance part in the re- gret 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 capture this extra information.
B.2 APPROXIMATION PROPERTIES OF SKETCHING
Although some error bounds of approximation using SJLT have been proposed (Nelson & Nguyên 2013 Kane & Nelson 2014 Bourgain et al.] 2013). it is still unknown what is the lower bound 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, drop all the superscripts and subscripts in these theoretical results.
of the sketch size while applying SJLT to the sketched ridge regression problem
Lemma 2 Nelson Nguyēn 2013). Let U E Rxd be a matrix with orthonormal columns, II E L the SJLT. Assuming that D = O log" (do, for II, Ea E 10, and d S c, with probability at least - ôn all singular values of IIU
(I(IIU) = So, i [d],
as long as
e> dlog (d5)1)
Further, this holds if the hash function h and a defining the II is Z (log(d5) -wise independent.
Theorem 6 (Approximation Properties of SILT). Let U E Rixd be matrix with orthonormal colunns, and A be a matrix of any proper size. If E Bext, is the SJLT satisfying the assumptions in Lemma 2 and d S S T,, then II has the following two properties:
20

---

Under review as a conference paper at ICLR 2022
1) Subspace embedding property: set Q (d polylog (dō,') / for (0, 1), with proba- bility at least
8g.
|U'TIT Tall2 S Exi
2) Matrix multiplication property: set ((dd/((mmm))) for Em (0, 1), with probability at least mm
IUIIIAA- U 1 cm |A
Proof of Theorem 6 1) From Lemma
2 by setting Ω (d polylog (do / can obtain
the upper bounds of eigenvalues: with probability at least 8gz
A (U'NTHU) of (TU) E [(1 - -=) E,r ) [ [ 25,, 3ea),
(37)
which yields that
a IU'IUUUU -aa) S 35a
(38)
Eq 39 is equivalent to
I Iall2 S 3Eg
Letting 6 3 and ea E (0, 1/3) yields the subspace embedding property.
2) From Lemma I in Zhhang & Liao 2019) we have
2d E C U CUBIA - |A
(39)
Combining Eq.
39
with the Markov's inequality, obtain that, with probability least 1 - 8m
2d
A
8m
2d c
Letting Em
yields the matrix multiplication property.
B.3 PROOF OF THEOREM 3
Next, using the approximation properties of SJLT Theorem we prove that the objective function value of the imputation regularized ridge regression problem for reward imputation can be approx- imated well with a relative-error bound. Moreover, we prove that the solution solving the sketched ridge regression problem for reward imputation is also good approximation of the solution solving the imputation regularized ridge regression. The following theorem is a detailed version of Theo- rem 3
Theorem (Approximation Error Bound of Imputation using Sketching, Detailed Version of The- IRexL
orem 3 Let 7 E [0, 1] be the imputation rate, X O the regularization parameter, and II R be the SJLT, and L E R L E goxdd T E R2 T E Rº_ 0 E Rdd Denote the imputation regularized ridge regression function F and sketched ridge regression function E$ for reward imputation
F(Ø) = Le - -T +7
[o
T 1
+ 1110
F8 (0) = - fî
[ï x) l1
+ 1110
and the solutions of these regression problems by
0 arg min F(0) and 0 = arg min (0))
Oe
BERa
Let (0,0.1). E (0, Ps
| 1/ Lan A). For II and πI assuming that D
( (lgg-log3( 1og"(d06 (dō-1) and
Ω (d polylog (d5-1) /62)
21

---

Under review as a conference paper at ICLR 2022
with probability at least 1 6.
F(O) S (1 + P(E)
(40)
|xeF (0)
110 0 S mmn (L
(41)
where Lan L; VII E RLLLI+d)xd Furthermore, if there is a constant fraction of the norm of Tall lies in the column space of Ta then Eq.441) can be strengthened. Formally, assuming that a mild structural assumption on the context matrix and the reward vector is satisfied, i.e. [|Uan U Talll 2 Tullll with a constant & E (0, 1}, then with probability at least 1 - 6,
010-0 (N(E vpxe 0112
(42)
where x(A) denotes the condition number of A, Tu T:T:Oa R(++ttd) and L
Un VT the SVD of a
Proof of Theorem 7 We first introduce some more notation of block matrices that will simplify the proof of the theorem:
II 00) a = 0 i
)
L.
(ELL Tall =
T T
(43)
Then the regression functions can be rewritten as follows:
F(0)= 0 -Tall 0
F² [al (L.10 Tan)ll + 1/101
Obviously, Mnn is still an SJLT. Combining Theorem 6 with theorem 19 in (Wang et al. 2017). we can obtain, setting
c Ω (max(d polylog (dd / (E(mmm)))
with probability at least
(ō_ + km.),
F F(O) - F(0) S PATF(())
(44)
[ 13 and where PA = [[ +x
max(fe (e_mmm 1-t.
Letting 6s = 6m == cp Eq. 44) can be rewritten as
F(O) - F(O) - 2pxcD F(O),
(45)
25a E (0, 1), from Assuming that 6g = 6m := 8/2 E (0,0.1) and Eo E 1/31 setting = T-50 (4.) 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 oi (A) sizes, we have
))le x
1 I || for any A and x with proper
(a 1
mii (Lan) 01
(46)
The key ingredient of bounding R(L+L+d)xd To = (T:T: 0a] E (L++ L = Eanl all be the SVD of L and denote a matrix with orthonormal columns by U EI which satisfies
0 to bound || Lan (0 (0-0000-)))) 0)112 Let L
[L; LLV VLL
E
U all + U. = I+t+d and U all = O.
Then, we can rewrite the solution 0 as follows:
θ arg min F(Ø) arg min [ - 1 BE
AERd
(LA) 'T00 = Van all
U T
all:
22

---

Under review as a conference paper at ICLR 2022
which yields that
T 0
T
L Val1 UT
all
T.
Enl Vall Van U T
(47)
T
Unn U II
U (U.)) T Th
Thus, Tui - 1 O is orthogonal to Unn and consequently to 2 -0), and we can obtain the following equality by Pythagoras's theorem:
Lan (0- 0)
L Tol 1|2
| Tual 1
(48)
Combining Eq.448) with Eq. 40 yields that
L ( 1 - F S PxeF(().
(49)
Substituting Eq. 49 into Eq. 46) concludes the proof of Eq. 41
we make a mild structural assumption on the context matrix and the reward vector, we can provide stronger bound of ||0
1122. Specifically, assuming that ||nn an Til llz Ell lla with
constant & (0, 1), from Eq. (47 and Pythagoras's 's theorem we have
F())
L 0 Till
| 112 |U TO
S (5 -1)]lUan1 U T
(50)
(5- - L all 012
$ (5 - 1) L a.l 12 |0
(5 1)0 max L 0012
Combining (5. with Eq. 41 yields Eq. (4
B.4 PROOF THEOREM 4
Proof of Theorem 4 In our sketched policy, letting Cunax maxAEA 10 Cimp 0,
/2C (20gg(2(MM)) B/8), and
W AC + + 2 Cmmp:
from (9) in Theorem 2 we obtain that
( (0 Sn,b) (0).. sn,bl S Swy/ ST,6 (DR))- 8n.b-
(51)
Before proving the upper bound of (Øg. sn.b) (0 (0%, sn,)) we need provide a technical tool follows. For convenience, also drop all the superseripts and subscripts. The goal is to find constant C² such that
VSTw-ls C, V ST
(52)
which is equivalent to the condition that the matrix C W- - 4-1 is positive semidefinite. Let Lall and Ial be the matrices defined in Eq. 43). Lall U Ean I be the SVD of La and ō_ 2 82 ... 2 ōa be the singular values of Lall- Then the i-th eigenvalue of -- (Ala + L Lan) can be represented as - = 1/(5? + A), and the i-th eigenvalue of
w- = (AI + L a11 Han
A = 1/( A), where ò is the i-th eigenvalue of
Ean all IIT Unn Eanl
From the Lidskii's theorem and Eq. 37 we have
Å [0 28x), of 3e,))
(53)
23

---

Under review as a conference paper at ICLR 2022
Assuming that the positive semi-definiteness of C C-w-- T is satisfied. obtain that C2 ( () 2 for i E [d], and combining this inequality with Eq. (3) yields that
C. Voo
-/ \\ A).
From the proof of Theorem 6 and Theorem
obtain that E, c/(6 + 3z), yielding that
o + + +2)] + C,
0 +
which decreases with increase of 1/e. Similarly to the proof of Co satistying Eq. we can obtain that
ST S Creg V sTW-18
(54)
provided that
07 + A
Creg 7
(6 6 + 32)] + X
Obviously, Creg also decreases with increase of 1/E.
Then, letting wCa. from (5. and Eq. (52) have
(0%) - (0%, 8n,b)
$ | (0% Bm.)) - (0" kn,b)
+ 100% 8n,n)
(0 on,)
< 00% 0¹ 82..8.)) ) + wy
% (VD
8n.
(55)
S Yu. + av 80 (Wx)
8n.d:
- 02 8n,b) for any A E A. where Yn, denotes the upper bound of (0a-
Next, using the compatibility of norm, give specific representation of the sum of Yn,b as follows:
Σ bE [23
Yn max
1
0%)]]
AEA
< max AEA
| 10
0%
(56)
$ max
| 0
0%
AEA
Further,
we give a more specific upper bound in Eq. under mild structural assumption in Theo-
rem 3 Let max denote the maximum of the condition numbers of (A, n) for A E A. n E [N],
and L (A,
LAi Vii; vALa] and Ua)(A,n) be the left singular matrix of L (A, n). Letting T (A, = IT: T Ozl, assuming that (A) U) (A. TT
all (A, n) >
< < A, n) 2 with a constant & (0, 1). substituting the upper bound Eq. 42) in Theorem into (56) yields that
Σ B
Yn. Yn <
[aall
maxx
2 2 CsC Vpxed.
(57)
where Cs maxne[N]_AEA
||S C max 0
24

---

Under review as a conference paper at ICLR 2022
From
Eq 54
and the definition of our sketched policy, letting Cy 2-2 1) OsC we obtain that
Eq. 55
Eq. (57)
.max all
Reg({Ar InINNMEEM))))
E
max (0 Sn,b) - ( (0 smo)
AEA
bE|M
E
+ Ynb YYnos(0''nn (0%% (mb) + tay/ 8/ ( (Wx) 8mb
-0 (
max AEA
nE(N),
E
(0%m... 8n.)) + cap 8/. (W (inio
8n, + Yn, (OArmn smo)
dE[M)
< 20 Σ
Sn,b b +2
Yn,b
WE(M
< 220 reg B Σ
Σ
8n,6 + 2NCr V pred
NE[N]
BE[B]
2aCreg VB Σ
Σ
Sn,b ss
+ +2NCy / pxed
NN(N]
BE[B]
20Crre
B Σ
Σ
S S (VR)) + +NNC V pxed
RE(N]
AEA
22Crreg VB Σ
Σ lr (SA (W2) +ON Vpxed).
NEIN)
AEA
< 2aCrreg V /BM
max tr (S S (VR) O(N vexed).
(58)
When the structural assumption in Theorem is not satisfied, from Eq. 41). we can obtain that the second term in (58) is also of order Ol (VPxxd), which does not influence the order of the final regret bound. Finally, combining Eq. (58) with lemma (Han et al., (020) gives the final regret bound.
C DETAILED EXPERIMENTAL SETTINGS AND MORE EXPERIMENTAL RESULTS
In this section, we provide more details and results in the experiments.
C.I DESCRIPTION DATASETS
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 s; E Rd. we drew elements of s; independently from a Gaussian distribution N0001, 0.2%), where d = 40;
Bhcck-Throggh-ae Rate (CTR): the CTRs for the 5 actions were respectively set as (10%, 15%, 25%, 20%, 30%);
25

---

Under review as a conference paper at ICLR 2022
Table 3: Description of datasets in the experiments (7: number of instances; B: batch size; N:
number of episodes; d: dimensionality of context; M: number of actions; CB satisfying B = //d)
Dataset
T
d
M
CB
synthetic data
126,000
1,400
90
40
5
25.00
Criteo-recent
75,000
1,000
75
50
5
25.82
Criteo-all
1,276,000
4,000
319
50
25.04
connercial product
216,568
1,700
128
50
5
25.83
The indicator variables of click events:
C { 0
click occurs in context 8;,
otherwise.
We sampled the click index set according the uniform distribution. Conversion rate (CVR) in context 8;: when C
(s) == sigmoid s;)), 1 exp(- (we,, st))*
where the coefficient vector we E Rd is sampled according to Gaussian distribution as We ((s d,, Ia), and set different means and standard deviations for different action with K. E [0: -02 -0.8] and oe E [0.01 +0.01 0.05);
Criteo Data. We used the publicly available Criteo datase consisting of Criteo's traffic on display ads over period of two months (Chapelle] 2014), where each context consists of 8 integer features and categorical features. Following the experiments in (Yoshikawa & Imai 2018), the categorical features were represented 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). tested in simulated online environment that was trained users' logs
All of the algorithms in the Criteo dataset. Specifically, we chose several campaigns from the Criteo dataset, where each campaign represents a category of items and corresponds 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 campaign and samples one context from this campaign, and revealed the context to the agent with preset CTR. To generate a reasonable sequence of instances, the environment kept the order of timestamps the contexts in each campaign. We tested our algorithms and the baselines with the following two online environments the Criteo dataset: Criteo-recens 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 Real Commercial App for Coupon Recommendation. To verify the ef- fectiveness and efficiency of our algorithms on real products, we conducted experiments on a real dataset collected from commercial social app. We call this dataset commercias product, where the data were collected after the users gave consent, and did not contain any personally iden- tifiable information or offensive content. Since this dataset from a commercial app 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, user may convert the coupon after some time, or just leave it there. The dataset was collected during a 1-month period with subsampling, and consists of 216, 568 instances from categories of coupons, where each context is described by 86 numerical features and 16 categorical features. The timestamps of clicks and conversions were
hhups://labss.c http::///aasscctteocooo wwtp:/c.rii.t..///.0000 httpmmmmm0......mmmmmmmmooooaaao
26

---

Under review as a conference paper at ICLR 2022
also recorded. Following the settings on the Criteo data, 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 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-informatee ducted 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 stances as 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.
feedback, The experiments were con-
we set the proportion of the initial in-
C.2 DETAILED SPECIFICATION OF HYPERPARAMENE
In these experiments, the true reward is defined by A = +1 (C2,A and V denote true binary variables of user click and conversion when executing action A given context 8;), where X = 0.01 on the synthetic data, Criteo Data, and commercial product data, respectively. As in contextual bandit literature (Li al. 2010 Chu 2011), we set the regularization parame- ter À = in the Euclidean regularization. According to theoretical analysis in Remark 3 we set the batch size as B C22N N d, set the constant Cв 25 and the sketch size c = 150 on all the dataset- s (B = 1400, 1000, 4000, 1700 for synthetic data, Criteo-recent, commercial product). The regularization parameters w, a in our policy and that the batch UCB policy were tuned in [02 -0.2 1.2]. For the SJLT in SPUIR and its variants, sketch size was set as e = 150 and the number of block 1) was selected rate-scheduled variants of our approaches, the imputation rate was selected in [0.1 +0.2 0.9]. Besides, the discount parameter 7 was tuned in [0.1 : +0,2 0.9]. In the nonlinear variant of our approach SPUIR- Kernel, selected the dimension of the random features in (50, 100, 200} and the kernel width of Gaussian kernel in {2 (1+1)/2
Criteo-all, and
{1, 2, 6). Except for the
12 12]].
Rche-lcheduled Approach. We equip PUIR and SPUIR with rate-schedules approach, called PUIR-RS and SPUIR-RS, respectively. We design rate-scheduled approach following the theoret- ical results about the imputation rate 7. From Remark [ we can obtain that larger imputation rate y leads to smaller variance while increasing the bias. From Remark 4 conclude that the additional bias term includes a monotonic decreasing function w.r.t. number of episodes under mild conditions. Therefore, instead of using fixed imputation rate, can gradually increase 7 with the number of episodes, avoiding the large bias at the beginning of the reward imputation while achiev- ing a small variance. Specifically, we set 7 X% for episodes from (X 10)% N to X% N, where X E [10, 100].
C.3 MORE EXPERIMENTAL RESULTS
For better illustration, in Figure 3 of the manuscript, we omitted the curves of algorithms whose av- erage rewards are 5% lower than the highest reward. Now provide the eurves of all the algorithms in Figure
27

---

Under review as a conference paper at ICLR 2022
0.25
Average Reward
RUR
Average Reward
PAR
SP38
SPUR
3.20
PUILRS
MUR-RS
SPU86-R5
0.29
SPUR-55
2:10
BLTS-8
BLT5-
SBJICS
NE3P7-4PM
0.22
SBUCH
DDXP3-P9)
3.36
DPV
DRH 5
BEXP3
BEXP3
0.14
0.20
3.22
0.19
10
20
30
40
50
60
70
80
90
29
40
50
60
70
Number Episodes
Number Episodes
(a) synthetic data
(b) Criteo-recent
3.20
0.450
0.423
Average Reward
2.24
Average Roward
9.23
PUB--S
SPU15-R5
3.350
BLTS-8
2.21
SOUCa
SEAP3-I7
DRM-5
3.325
BEXP1
BEXPS
33355
0.25
3.38
50
300
150
200
230
300
20
65
50
100
123
Number of Episodes N
Number of Episades N
(c) Criteo-all
(d) commercial product
Figure 5: Average rewards of the compared algorithms, the proposed SPUIR and its variants synthetic dataset, Critco dataset, and the real commercial product data
28


Reviews:
[{"review_id": "s-BwyVNt9p6", "reviewer": "Reviewer_cFbQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "\nPositive points:\n* the paper is well written and generally easy to follow;\n* the results are clearly communicated; both means and standard deviations are provided (e.g in Tables);\n* in my biased opinion, the problem proposed  and the chosen approach are both interesting;\n\n\nMajor issues:\n* details regarding the imputation procedure itself were scarce and hard to parse;\n* the effect of different imputation methods could be rather large, this goes unaddressed in the current paper;\n* comparisons are performed with methods where the parameters are shared across arms/actions. While this assumption is restrictive application wise, it is important to understand the benefits, if any, of imputation in those cases as well;\n* there is little intuition regarding the support/rank of the context matrix, arm specific parameters and their interaction, and how this can impact  whether imputing contexts is helpful or not;\n* simple Thompson Sampling seems to be performing comparatively well;\n\nMinor issues:\n* the number of iterations used to compute the means and standard deviations should be made explicit (10? 100?);\n* for the top performing algorithms, it would be interesting to see the standard deviation bands throughout the plots;\n* claiming that most literature ignores potential rewards is slightly misleading: Bayesian methods aim to model distributions over  rewards given contexts, hence there is an implicit \n* occasional spelling\n\nSuggestions for improvement\n* assess the impact of imputation when different imputation methods are considered, be explicit about how the imputation is achieved\n* assess the performance of the algorithms in settings where the arm/action parameters are the same across arm/actions\n* consider synthetic experiments where the distributions of contexts and action parameters are made explicit, and where the rewards are modeled as explicit functionals of context and actions. I believe [1] could be a great basis for such experiments.\n* address minor issues; \n\n\n[1] Lloyd, James, et al. \"Random function priors for exchangeable arrays with applications to graphs and relational data.\" Advances in Neural Information Processing Systems 25 (2012): 998-1006.", "summary_of_the_paper": "The paper considers the behavior of a series of algorithms for learning in a batched bandit setting,\nwhere parameters are arm/action specific, rather than shared across arms/actions. \n\nThese algorithms are based on UCB like techniques with the addition of a regularization term that aims\nto use information from imputed, unobserved rewards. Such techniques are present in the linear regression\nand dimensionality reduction literature where one aims to use either prior information or \ndata distribution information to aid prediction. However, to my knowledge, these formalisms are quite \nnew to online settings like bandits, thus making the presented approach appealing. ", "summary_of_the_review": "Recommendation: weak reject.\nThe paper addresses an interesting question, and is generally well written, with a promising algorithmic direction. However,\nI believe the central imputation idea gets lost in the many variants considered. I believe having sketching variants\nis important and I liked that facet of the paper. However, I believe that there isn’t sufficient clarity on how the actual imputation is accomplished, and what is the impact of such imputation. Further, the paper does not provide intuition on what modeling assumptions and statistical data features are behind the performance improvements when imputation is used.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ogCpE3f5TYP", "reviewer": "Reviewer_FYMj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "PROS:\nThe theoretical work is complex and, besides the comment I make in the major comments section, accurate as far as I can tell. The paper has compared its approaches to a number of sensible benchmarks on a nice mix of simulated and real dataset and for several realistic extensions of the model. The problem studied is of genuine interest and the approach taken to derive a new algorithm is an interesting combination of ideas from the literature.\n\nMAJOR COMMENTS ON CONS:\nMy main issues are that the explanations of the main algorithm are not sufficiently detailed to convince me that it is as effective as suggested. There is also an error in the theory which once corrected weakens the contributions. See more details below.\n\n•\tConstruction of the imputation regularized ridge regression: \no\tThe paper is mostly accessible (with some omissions of detail as described in the more minor comments below) until this point where it stops being as user-friendly. Some more textual explanation of the terminology is needed here to help guide the reader as to the function and interpretation of matrices L, T, \\Phi, \\Psi, and b. This kind of discussion is provided prior to equation (1).\n\no\tThe jump from equation (1) to equation (2) is not obvious and could do with some further explanation.\n\no\tRelated to this, it’s not obvious where $\\eta$ comes from – is it a function of $\\gamma$ and $\\lambda$? If not why does it not enter explicitly in to eq (1) somewhere? Are there infinitely many solutions and a particular choice of \\eta parameterises a specific one?\n\no\tAt a more conceptual level, it’s hard to understand what this complex process of imputation achieves that is more than just reducing the importance of the regularization term and increasing the importance of the data-driven term. Since the imputed values for a batch are deterministic functions of the observed data in that batch, is the entire imputation process not equivalent to a very specific means of reducing $\\lambda$?\n\n•\tComments on the high-level idea of reward imputation and the exploration-exploitation trade-off:\no\tSomething that came to my mind upon reading the abstract but I couldn’t find directly addressed in the paper is the idea that reward imputation could feasibly push an algorithm towards exploitation and away from exploitation. I’m imagining a scenario where we draw a small number of samples for a particular action in an early round which are not particularly representative of its true value and lead to a biased estimate. Through deterministic imputation of the rewards that would have been observed on the other contexts, this bias will propagate further and would seem to only encourage the algorithm to favour this action less. If this happens to be a good action there would be a concern that this could lead to sticking in suboptimal actions and incurring more regret than algorithm which does not impute on the basis of biased estimates. \n\no\tA particular concern in this setting would be that it leads to heavy tails on the regret distribution (as the sticking will only happen sometimes) and by reporting only means and standard deviations, this phenomenon is somewhat obscured.\n\n•\tTHIS ISSUE HAS BEEN RESOLVED IN THE NEW VERSION: Error in the theory at eq (19)\no\tI believe, unfortunately, that there is an error at eq (19) in the proof of Theorem 2. It has (nested within a square root) for $\\eta \\in (0,1)$ the equality \\[\n\\sum_{i=0}^N \\eta^{N-i} = \\eta^N(1-\\eta^{N+1})/(1-\\eta)\n\\]\n\nWhich is not correct. It should be, with some simplification added for clarity,\n\n\\[\n\\sum_{i=0}^N \\eta^{N-i} = 1+\\sum_{i=1}^N \\eta^N = 1+(1-\\eta^N)\\(1-\\eta).\n\\]\n\nThis unfortunately cannot then be bounded as a decreasing function of N and, I believe, leads to a constant order additional bias, perhaps bounded as $(C_\\theta \\gamma (1+1/(1-\\eta)))$ in the final statement of the Theorem.\n\nIf I am not mistaken, and there is not some other technique that can be used to remove this additional bias – from a conceptual viewpoint this seems unlikely as it makes sense for a reduction in variance to be necessarily traded off against an increase in bias – this necessitates some modifications to the discussion and reframing of the contributions. The exponentially decreasing bias is sold as a major contribution (indeed arguably oversold, as it is only the additional bias which would exponentially vanish, not the entire bias), and therefore the loss of this does affect the message of the paper somewhat.\n\n\nMINOR COMMENTS ON CONS:\n•\tThe related work section may be improved and made more useful by indicating how these papers link to your work (principles of making a batched decision, optimism vs other methods, similarities or inspiration in the theoretical analyses). \n\n•\tThe sketching approach is quite an important concept to the paper, but one that is not commonly used in bandits and therefore potentially unfamiliar to prospective readers of the paper. It would be nice to make it clearer what it involves (conceptually) when it’s first mentioned in the introduction.\n\n•\tI don’t think $M$ is defined? Further to this, it may be useful to give a sense of the likely values of $M, B, d$ early in the paper? For instance, I found myself worrying about situations where B is close to M and some actions are not used at all in some early rounds which seems to be less relevant when you get later in the paper and realise the intended setting is M<<B?\n\n•\tThe definition of a policy $\\pi$ could be more mathematically precise – the text seems to suggest that $\\pi_n$ is a single sampling distribution on $\\mathcal{A}$ used for all elements of the n^th batch. But it is not clear how precisely it maps from the contexts and history to actions, and whether it can vary across the batch depending on, say, the earlier selections in the batch.  \n\n•\tThe distribution of the rewards is not made clear in section 2, only the functional form of their expectation – is this deliberate?\n\n•\tThe experiment in Figure 1 isn’t fully reproducible, as the experimental parameters (reward distributions, context distribution, and batch size) aren’t specified. This also makes it harder to interpret what level of feedback the algorithm could expect without any additional information. Finally, it’s not clear what modifications are made to the Han et al. algorithm to adapt to the action-specific reward parameters, or whether this is all conducted in the setting of a shared reward parameter.\n\n•\tOn page 4 you say “for $\\forall A_j$” which reads as saying ‘for’ twice.\n\n•\tFrom Section 4 the amount of whitespace seems to have been reduced between paragraphs? This makes things quite dense and hard to read.\n\n•\tAt the start of the proof of theorem 2: *triangle inequality\n\n•\tI don’t think you need the $s \\neq 0$ condition in Thm 2 since $\\Gamma$ is positive semi-definite not positive-definite?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "There is a substantial amount of work which has gone into this paper, and the authors have combined several different ideas – contextual bandits, batched bandits, sketching approximations for efficiency – together in a mostly careful manner. This is non-trivial work. My concerns are that there several areas where the explanations feel limited and not user friendly, where the interesting features of the method are not fully explained, and where there are slip-ups in the theory and reproducibility. The latter two of these points mean that I’m not fully convinced of the effectiveness and utility of the method.\n\nI also question whether ICLR is the right venue for this work. It seems that it has been difficult to adequately explain the method, its theoretical guarantees and its place within the literature within 9 pages, and a more accessible discussion may be achievable in a journal paper. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VmfZPcrI1SA", "reviewer": "Reviewer_yEx1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "Pros:\nThe paper is well-written and considers an important problem of batched linear bandits in the literature. \n\n(A) The authors introduce the idea of imputation to further speedup the learning process. Regret bounds showing that the lower variance of the imputation approach over the vanilla version further strengthens the paper.\n(B) Sketching is then introduced to further speed up the computation of the regression problem. The introduced sketching error is further tuned by appropriately setting the sketch size to provide a sublinear regret of O(\\sqrt{MDT}). \n(C) Experimental results are pretty convincing on the provided datasets of both improved regret performance as well as in terms of sketching time. Better regret performance is achieved by SPUIR compared to other approaches but roughly less than half the  time of PUIR. \n\nQuestions: \n\n(1) Why are the Theta's for each of the actions in the episodes computed afresh? Could we reuse the previously computed theta's to regularize the solution in the current batch and get rid of the imputation which is expensive? \n(2) This uses the classic ``sketch and solve'' paradigm. Can we utilize the ``iterate and sketch'' to further speed up the approach?[a]\n\n[a] Oblivious Sketching-based Central Path Method for Linear Programming. ICML 2021", "summary_of_the_paper": "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. \nTheoretical 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. \nExperimental 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.", "summary_of_the_review": "Overall, the paper solves an important problem in the literature of contextual batched bandits. The proposed approach of imputation of unobserved actions is sound and both theoretical results in terms of regrets bounds and superior practical performance on real-world datasets are shown in the paper. \nStill unsure about the imputation approach taken and if we can further improve the sketching approach considered in the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper the authors consider a contextual batched bandit setting where they rely on  imputationin order to estimated the non-executed actions in each batch. Even though the idea is quite ineteretsing, and can lead to new methods, there is still a lof of issues raised by the reviwers. In particular, part of the proof was incorrect (and the authors tried to fix it) but given the short time, the reviwers felt that this part should be rewritten and scrutanized further. Also, there are many suggestions by reviewers that the authors need to apply in order to make this work publishable.
Decision: Reject