Reward Imputation with Sketching for Contextual Batched Bandits
Authors: Xiao Zhang
Ninglu Shao
Zihua Si
Jun Xu
Wenhan Wang
Hanjing Su
Ji-Rong Wen
Venue: NeurIPS 2023 poster (2023)
Keywords: batched bandit
sketching
reward imputation
regret bound
ridge regression
TL;DR: An efficient sketching-based reward imputation method with controllable bias and smaller variance for contextual batched bandit.

Abstract: Contextual batched bandit (CBB) is a setting where a batch of rewards is observed from the environment at the end of each episode, but the rewards of the non-executed actions are unobserved, resulting in partial-information feedback. Existing approaches for CBB often ignore the rewards of the non-executed actions, leading to underutilization of feedback information. In this paper, we propose an efficient approach called Sketched Policy Updating with Imputed Rewards (SPUIR) that completes the unobserved rewards using sketching, which approximates the full-information feedbacks. We formulate reward imputation as an imputation regularized ridge regression problem that captures the feedback mechanisms of both executed and non-executed actions. To reduce time complexity, we solve the regression problem using randomized sketching. We prove that our approach achieves an instantaneous regret with controllable bias and smaller variance than approaches without reward imputation. Furthermore, our approach enjoys a sublinear regret bound against the optimal policy. We also present two extensions, a rate-scheduled version and a version for nonlinear rewards, making our approach more practical. Experimental results show that SPUIR outperforms state-of-the-art baselines on synthetic, public benchmark, and real-world datasets.

Reward Imputation with Sketching for Contextual Batched Bandits
Xiao Zhang" Ninglu Shao! Zihua Si Si Jun Jun Xu Xu!
Wenhan Wang", Hanjing Ji-Rong Wen 1.2
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China 2 Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China Tencent Inc., Shenzhen, China
(zhangx89, ninglu_shen zihua_si, junxu, jrwen) @ruc. edu, on (justinsu, ezewang) @tencent com
Abstract
Contextual batched bandit (CBB) is a setting where a batch of rewards is ob- served from the environment the end of each episode, but the rewards of the non-executed actions are unobserved, resulting in partial-information feedback. Existing approaches for CBB often ignore the rewards of the non-executed actions, leading to underutilization of feedback information. In this paper, we propose an efficient approach called Sketched Policy Updating with Imputed Rewards (SPUIR) that completes the unobserved rewards using sketching, which approximates the full- millrinffommtion feedbacks. We formulate reward imputation as an imputation regularized ridge regression problem that captures the feedback mechanisms of both executed and non-executed actions. To reduce time complexity, we solve the regression problem using randomized sketching. We prove that our approach achieves an instantaneous regret with controllable bias and smaller variance than approaches without reward imputation. Furthermore, lincar regret bound against the optimal policy. We also present two extensions, a rate-scheduled version and version for nonlinear rewards, making our approach more practical. Experimental results show that SPUIR outperforms state-of-the-art baselines synthetic, public benchmark, and wallworld datasets.
approach enjoys sub-
1 Introduction
Contextual bandits have gained significant popularity in solving sequential decision-making problems et al. 2010 Lan and Baraniuk] 2016 Yom- Tov et al. 2017 Yang et al., 2021). where the agent continuously updates its decision-maakin context and the received reward feedback to maximize cumulative rewards. In this paper, we address more general setting called contextual batched bandits (CBB). In CBB, the decision process is divided into N episodes, and within each episode, the agent interacts with the environment for a fixed number of B steps. At the end of each episode, the agent collects reward feedbacks and contexts. Subsequently. the policy is updated using the collected data to guide the decision-making process in the subsequent episode. CBB offers a practical framework for real-world streaming applications (e.g.. streaming recommendation (Zhang et al. 2021 2022)). In the context of CBB settings, the batch size B, can be adjusted by the agent to achieve improved regret guarantees and meet the data throughput requirements based on the available computing resources (Zhou 2023
policy fully online (i.e., each step), considering the
Ninglu Shao and Zihua Si have made equal contributions to this paper.
1 "Corresponding author:
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

In bandit settings, it is common for the environment to only provide feedback on the rewards of executed actions to the agent, while concealing the rewards of non-executed actions. This type of limited feedback is referred to as CBB setting, existing approaches tend to overlook the potential rewards associated with non-executed actions. Instead, they address the challenge of partialinnformatio exploitation tradeoff in both the context space and reward space (Han et al., 2020 Zhang et al., 2020). However, CBB agents typically estimate and maintain reward models for the cetion-selection policy, thereby capturing some information about the potential rewards of non-executed actions. This additional reward structure information is available for policy updating in each episode but remains untapped by existing batched bandit approaches.
feedback (also called "bandit feedback")) In
feedback through an exploration-
In the context of contextual bandit settings where the policy is updated online, several bias- approaches have been introduced to tackle the issue of partial-informatin feedhack. [iimakopoulou et al.] (2019) presented linear contextual bandits integrating the balancing approach from causal inference, which reweight the contexts and rewards by the inverse propensity scores. [Chou et al. (2015) designed pseudo-reward algorithms for contextual bandits using upper confidence bound (UCB) strategy, which use a direct method to estimate the unobserved rewards. Kim and Paik (2019) focused on the correction of feedback bias for LASSO bandit with high-dimensional contexts, and applied the doubly-roben robust approach to the reward modification using average contexts. While these approaches have demonstrated effectiveness in contextual bandit settings, little attention has been given to addressing the uudei-ttiliztionn partial- informatiioo feedback in CBB setting.
Theoretical and experimental analyses in Section 2 indicate that better performance of CBB is achievable the rewards of the non-executed actions can be received. Motivated by these observations, we propose novel reward imputation approach for the non-executed actions, which mimics the reward generation mechanisms of environments. We conclude our contributions as follows.
(1) 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.
(2) We prove that our reward imputation approach obtains a relative-error bound for sketching approximation, achieves an instantaneous regret with a controllable bias and 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 O (Bd²) ) to (cd²)) for each action in one episode, where B denotes the batch size, the sketch size, and d the dimension of the context space, satisfying d < c < B.
(3) We present two practical variants of our reward imputation approach, including the rate-scheduled version that sets the imputation rate without tuning, and the version for nonlinear rewards.
(4) We carried out extensive experiments on a synthetic dataset, the publicly available Criteo dataset, and a dataset from a commercial app to demonstrate our performance, empirically analyzed the influence of different parameters, and verified the correctness of the theoretical results.
Related Work. Recently, batched bandit has become an active research topic in statistics and
learning theory including 2-armed bandit (Perchet et al.) (0166), multi-armed bandit (Gao et al. 2019 Zhang et al.| [2020] Wang and Cheng (2020). and contextual bandit (Han et al. [2200] Ren and Zhou
2020 Gu al. [02 Han et al. (2020) defined linear contextual bandits, and designed UCB-type algorithms for both stochastic and adversarial contexts, where true rewards of different actions have
the same parameters. Zhang et al. (2020) provided methods for inference on data collected in batches using bandits, and introduced a batched least squares estimator for both multi-arm and contextual bandits. Recently, [Esfandiari et al.) (202T) proved refined regret upper bounds of batched bandits in stochastic and adversarial settings. There are several recent works that consider similar settings to CBB, e.g., episodic Markov decision process (Jin et al. 2018), LASSO bandits (Wang and Cheng 2020). Sketching is another related technology that compresses large matrix to much smaller one by multiplying a (usually) random matrix while retaining certain properties [Woodruff] 2014), which has been used in online convex optimization (Calandriello et al.] 2017 Zhang and Liao 2019
2 Problem Formulation and Analysis
Let [z] (1. 2), S Rdd be the context space whose dimension is d, A = (Aybee M| the action space containing M actions.[A: B] [AT, BTJT, ||A]|E, ||A|| ||A||2 denote the Frobenius

---

Protocol Contextual Batched Bandit (CBB)
INPUT: Batch size B, number of episodes N, action space A = {Ay]se[M) context space S C R 1: Initialize policy Ps t- 1/M, sample data buffer D2 {(Su,a, Alo,s
using initial policy pu
2: for n 1 to N do
3: Update the policy pn on Dn
4: for b = 1 to B do
5: Observe context An,6 and choose AI, E A following the updated policy Pr (#n,6)
6: end for
7: Dn+1 +- [(Sn,h, Ar Rm,s) RoED) where Ra,s denotes the reward of action Ar,,s on context Su,6
8: end for
norm, 1-norm, and spectral norm of matrix A, respectively, ||]]] and ||a|| be the E norm and the (2-norm of a vector a, minn (A) and maax (m) 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) in Protocol T where the decision process is partitioned into N episodes, and in each episode, CBB consists of two phases: (I) the policy updating approximates the optimal policy based on the received contexts and rewards; (2) the online decision chooses actions for exccution following the updated and fixed policy for B steps (B is also called the batch size), 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 cartial-information feedback where rewards are unobserved for the non-executed actions.
In contrast the existing batched bandit setting (Han al. 2020 Estandiari et al. 2021 where the true reward feedbacks for all actions are controlled by the same parameter vector while the received contexts differ across actions at each step, we make the assumption that in CBB setting, the mechanism of true reward feedback varies across actions, while the received context is shared among actions. Formally, for any context 8; E C Id and action A E A, we assume that the expectation of the true reward Re is determined by an unknown action-specific reward parameter
vector 0% E IRd: E. | s;] (0) 8;) (the linear reward will be extended the nonlinear case in Section This setting for reward feedback matches many real-world applications, e.g., each action corresoonds 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 delve deeper into understanding the impact of unobserved feedbacks the perfor- mance of policy updating in CBB setting. We first conducted an empirical comparison by ap- plying the batch UCB policy (SBUCB) (Han al., 2020) to environments under different pro- portions of received reward feedbacks. In particular. the agent under full-information feedback can receive all the rewards of the executed and non-executed actions, called Full- mull-Infomaatin CB- (FI-CBB) setting. From Figure [ we can observe that the partial-information feedbacks are damaging in terms of hurting the policy updating, and batched bandit policy benefit from more reward feedbacks, where the performance 80% feedback is very close to that of FI-CBB. Then, prove the difference of instantaneous grets between the CBB and FI-CBB settings in Theorem D (proof can be found in Appendix A).
1250
Theorem 1. For any action A E and context 8, E S, let 0 be the reward parameter vector estimated by the batched UCB policy in the n-th episode. The upper bound of instantaneous regret (defined by K0%, 8;) (0) 8;)l) in the FI-CBB setting is tighter than that in CBB setting (i.e., using the partial-ing intiialliifrmaatinn feedback). feeddbacc.
Average Reward
2.20
2200-
partadietomaicn Truchusk (C16)
1230
1236
00% hesteeck
TaBle Taadback 71-2
From Theorem I we can infer that utilizing partial- information feedbacks leads to a deterioration in the regret of the bandit policy. Ideally, the policy would be updated using full-information feedback. However, in CBB, full-information feedback is u- navailable. Fortunately, in CBB, different reward parameter vectors are maintained and estimated separately for each action, and the potential reward
30 40
Number of Episodes N
Figure Average rewards of batch UCB policy (Han et al.] (020) under different proportions of received reward feedbacks, interacting with the synthetic environment in Section where x% feedback means that x x% of actions can receive their true rewards
3

---

Imputed Context 5 Matrix
Reward
Context
Reward Vactor R
Context SP
N
N,
N
Matrix
Context Matrix
Reward
Imputed
B
NJ
Vector
NJ
Reward
R
N
B
B Full-information CBB
CBB
CBB with Our Reward Imputation
Figure 2: Comparison of the stored data corresponding to the action A, = [Ay)j in CBB, CBB with reward imputation, and full-information CBB, in the (n 1)-th episode
structures of the non-executed actions have been captured to some extent. Therefore, why not utilize these maintained reward parameters estimate the unknown rewards for the non-executed actions? In the following, we propose an efficient reward imputation approach that leverages this additional reward structure information enhance the performance of the bandit policy.
3 Reward Imputation for Policy Updating
In this section, we present an efficient reward imputation approach tailored for policy updating in CBB setting.
Formulation of Reward Imputation. As shown in Figure contexts and rewards of the non-executed steps of each action, our reward imputation approach completes the missing values using the imputed contexts and rewards, approximating the full- information CBB setting. Specifically, at the end of the (n + 1)-th episode, for each action A, E A, E [M], the context vectors and rewards received at the steps where the action Aj is executed are observed, and are stored into a context matrix 5 E IR NJ xd and a reward vector R E RVV,, respectively, where NJ denotes the number of executed steps of A; in episode n + 1. More importantly, the steps (in episode n + where the action Aj is NOT executed, the following imputations need to be performed for action Ay: (1) since the contexts are shared by all the actions, A3 N where N7 denotes the number of non-executed steps of Aj (i.e., Ny = B - N ; (2) since the rewards of A, are unobserved at the non-executed steps, we estimate them using an imputed reward vector: for any j E [M]]
contrast to CBB that ignores the
we directly store them into an imputed context matrix Sm
R (A,), ( (A.))....,rr ,u,yy (4,)) RR
where (A,) = 10) &n,b) denotes the imputed reward parameterized by 0%, E Rd and 8n,b is the b-th row of 5% Next, we introduce the updating process of the reward parameter vector 07 We first concate- nate the context and reward matrices from the previous episodes: L" [S R xd Th
R R xd T' i R3 R Ly Ek- No. Then, the updated parameter vec-
R
R LÝ Ex Nà. En [ 2
S
of the imputed reward for action A, can be obtained by solving the following imputation for A. regularized ridge regression: for n = 0, N 1,
@x+1 arg min DERd
12,0 T
L 12
0 T
-110013
Observed Term
Imputation Term
where y E [0, 1] is the imputation rate that controls the degree of reward imputation and measures
trade-off between bias and variance (Remark) 2 X >> O is the regularization parameter. The
discounted variant of the closed least squares solution of I is used for computing 0u+1,
(Va)).
-1
(ba)) +76%74 (
A3

---

where L p++ = Ald + 1 + +, n+ and
A,
4 n-+
24 + A b b%, SA R',,'
(3)
n- 7 Aj + S" bA, =,b + i Ray,
(4)
and 7) E (0, 1) is the discount parameter that controls how fast the previous imputed rewards are forgotten, and can help guaranteeing the regret bound in Theorem
Efficient Reward Imputation using Sketching. As shown in the first 4 columns in Table TT the overall time complexity of the imputation for each action is O(Be²) in each episode, where B represents the batch size, and d the dimensionality of the input. Thus, for all the M actions one episode, reward imputation increases the time complexity from O Bd2) of the approach without imputation to (MM Bd²). To address this issue, we design an efficient reward imputation approach using sketching, which reduces the time complexity of each action in one episode from O (Bd)) to O (cdt), where denotes the sketch size satisfying d < e < B and cd > B. Specifically, in the (n + 1) episode, the formulation in [T) can be approximated by a sketched ridge regression as:
02,1 arg min I BER
0 ( ) l: +7 D (i2,0 - Tx, 1; 2lll
0
(5)
where 0% denotes the updated parameter vector of the imputed reward using sketching for action A E A. Ca E R and C% E Rex8; are the sketch submatrices for the observed term and the imputation term, respectively, and the sketch matrices for the two terms can be represented as
I7 = C[,,, C'A,,"'. "., ,r,, " E ER
fr, A [ CA,, C%,] E RexII.
We denote the sketches of the context matrix and the reward vector by Г == Ca, E Box and A C% RA, IR, the sketches of the imputed context matrix and the imputed reward vector by 17 Cū Sx Rexd and A = C% R' E R.. Similarly to (2), the discounted variant of the closed solution of ( as follows:
0%11 = )
PAj x+1 + +1p%t1
(6)
where 1) E (0, 1) denotes the discount parameter, W = Ala + G + +1G Gm+1
and
A,
Gat = 1, T P n+| Pa + A
(7)
11+1 nP', + F AT G = G + T P
(8)
Using the parameter A, obtain the sketched version of imputed reward as (n))(A))
(0" A, Sn,b) at step b [Ny). Finally, we specify that the sketch submatrices (C%) (CA)EE)) and the block construction of Sparser
Transform (SJLT) Kane and Nelson 2014). where the sketch size is divisible by the number of blocks T As shown in the last 4 columns in Table [ sketching reduces the time complexity of reward imputation from O(M Bdd) to O(M ) for all M actions in one episode, where e < B. When Me z B, the overall time complexity of our reward imputation using sketching is even comparable that without reward imputation, i.c., (Bd?) time complexity.
(C JAEMMEEM
Updated Policy using Imputed Rewards. Inspired by the UCB strategy Li et al. 2010). the updated policy for online decision of the (n + 1)-th episode can be formulated using the imputed rewards (parameterized by @x+1 in 2 or the sketched version of imputed rewards (parameterized
1 in (6)). Specifically, for a new context s, by Øx+1
origin policy 1 selects the action A arg max (0u+1 s) + w w[s
sketched policy Pn+1 selects the action as A <- arg max A (0) .) + a aisT( [
where w 0 and > 0 are the regularization parameters in policy and their theoretical values
given in Theorem 4 We summarize the reward imputation using sketching and the sketched policy
into Algorithm 2 called SPUIR. Similarly, we call the updating of the original policy that uses reward imputation without sketching, the Policy Updating with Imputed Rewards (PUIR).
Since set the number of blocks of SJLT D < d, omit D in the complexity analysis.
5

---

Table 1: The time complexities of the original reward imputation in ① (first 4 columns) and the reward imputation using sketching in ( (last 4 columns) for action A, in the (n + 1)-th episode, where N (NT3) denotes the number of steps at which the action Aj is executed (non-executed) in episode n. + 1, N7 + No = B, and the sketch size satisfying d < < B and ed > B (MM: matrix multiplication; MI: matrix inversion; Overall: overall time complexity for action Aj in one episode)
Original reward imputation
Reward imputation using sketching in (
Item
Operation
Equation
Time
Item
Operation
Equation
Time
$ b
MM
(
G G
MM
(ladP)
MM
(
PAj
PA
MM
O
MI
((d))
A;
MI
O(d")
F A
Sketching
O(N)
T A, A%
Sketching
O
Overall
O
Overall
Olcdf)
Algorithm 2 Sketched Policy Updating with Imputed Rewards (SPUIR) in the (n 1)-th episode
INPUT: Policy pa., data buffer Du+1, A = {A,}se M) 2 0,77 E (0, 1). 7 E [0. 1], X > 0, W A; ATa,
Go, 22 = Oa. Pa2 = =pa; = 0, 0% = 0, [M]. batch size B, sketch size c, number of block OUTPUT: Updated policy Pm+1
1: For all [M], store context vectors and rewards corresponding the steps which the action AA executed, into F4 E R xd and A2, E R
2: For all E M), store context vectors corresponding to the steps at which the action Ay is not executed into T3 R xd where NT +- B Nÿ
3: (A,) +-
for all Ay and & E [N where Sn, a is b-th row F 4: Compute imputed reward vector Rū,- (A,, 8.. (A,)3 e CR Vj [M]
for all action A; E do 6: G + GA + r
PA; n+1 + PA, + A
Gotl G + F A, PA,
sntl < upa, + + Aa,
7: W AIa + G + +7GA, A;
An-1 0ut1 (W + + )
(
8: end for
9: (s) selects action <- arg maxxaxxaaaa AEA (0xt1 .s) tajs (Wx+1)-1 $f for context
10: Return (0% JAEA: ((WT*1) Aed
Theoretical Analysis
We provide the instantaneous regret bound, prove the approximation error of sketching, and analyze the regret of SPUIR in CBB setting. The detailed proofs can be found in Appendix B. We first demonstrate the instantaneous regret bound the original solution 0% in ①
Theorem 2 (Instantaneous Regret Bound). Let 1 E (0, 1) be the discount parameter, 7 [0, 1] the imputation rate. In the n-th episode, if the rewards (Rn,obeeL are independen A and bounded by CR. then, for any b E [B], AA E A. there exists Cimp > O such that, with probability at least 6,
100%: Sn,b) (0) s,,,)l 2110211a + v + + Ciipp
[TT (VR) sn,bl=,
(9)
The first term on the right-hund side of ( 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 s E Rd.
where D = = 4h D.% -= 12C log(2MB/0))
TT (TA)
8] < 1TT (Al 4'
8)
Further, a larger imputation rate 7 leads to a smaller variance term [&T (V%) 8]
'The assumption about conditional independence of the rewards is commonly used in the bandits literature. which can be ensured using master technology theoretical construction (Auer 2002 Chu al. 2011 l).

---

Remark 1 (Smaller Variance). From Theorem 2 we can observe that our reward imputation achieves a smaller variance ((s (V sn,b]²) than that without the reward imputation. By combining Theorem 2 and the proof of Theorem 7 we can obtain that the variance in instantaneous regret between the variances in full and partial information scenarios. Thus, reward imputation in SPUIR provides a promising way to use expert advice approaches for bandit problems.
bound of SPUIR
Remark (Controllable Bias). Our reward imputation approach incurs a bias term - in addition to the two bias terms X|10a allz and that exist in every existing UCB-based policy. But the additional bias term 2 2imp is controllable due the presence of imputation rate 7/ that can help controlling the additional bias. Moreover, the term Cimp in the additional bias can be replaced by a function fimp(n), and fimp (nz) is monotonic decreasing w.E.t. number of episodes n provided that the mild condition /n = (dd=1) holds (the definition and analysis about fimp can be found in Appendix B. Overall. the imputatioo rate 7 controls a trade-off between the bias term and the variance term, and we will design a rate-scheduled approach for automatically setting Y in Section 5
Remark 3 (Relationship with Existing Instantaneous Regrets). According to the original definition in the context of online learning, the definition of instantaneous regret should be max (0" 8n.b)
(0% ..,.b) However, in the specific setting of contextual batched bandit (CBB) that is the focus of this paper, as derived in Appendix (second inequality of Eq. (48)), if we denote the upper bound of 10% bn,b) (0 Sn,b) as U, then 2U serves as an upper bound for instantaneous regret. Thus, in the context of CBB explored in this paper, we are interested in an upper bound for (00 Sn,b) (0) sn,bll and define it as the instantaneous regret bound.
Although some approximation error bounds using SJLT have been proposed (Nelson and Nguyên 2013] Kane and Nelson| 2014, Zhang and Liao, 2019), it is still unknown what is the lower bound of the sketch size while applying SJLT to the sketched ridge regression problem in our SPUIR. Next, we prove the approximation error as well as the lower bound of the sketch size in SPUIR. For convenience, we drop all the superscripts and subscripts in this result.
Theorem 3 (Approximation Error Bound of Imputation using Sketching). Denote the imputation regularized ridge regression function by F(0) (defined in ① and the sketched ridge regression function by F0{() (defined in ( reward imputation, whose solutions are 0 = arg mingeRs F())
and O arg min F0))). Let y E [0, be the imputation rate, X > 0 the regularization parameter, E (0, 0.1], E E (0, 1). Lall = [L; L.). and px = |
/ ((I L 12 + >). II and fi
are SJLT, assuming that D = O(g-1 log" (d8-1)) and the sketch size e = Ω (d polylog (d8-1) /E²),
with probability at least 5, the following results hold:
F(0) S (1 + F(E)
0 O (VpxE).
To measure the convergence of approximating the optimal policy in an online manner, we define the regret of SPUIR against the optimal policy as
Reg(N (N, B) = max AEA
Σ
10'), 8m,6) - (0 8n,ill
[E(
where L,,6 denotes the index of the executed action using the sketched policy p.. (parameterized by (EA) step b in the n-th episode. We final prove the regret bound of SPUIR.
Theorem 4 (Regret Bound of SPUIR). Let BN be the overall number of steps, n E (0, 1) be the discount parameter, y E [0, 1] the imputation rate, X > O the regularization parameter, Cmmax max 1 llz. Cimp be the positive constant defined in Theorem [ Assume that the conditional independence assumption in Theorem [ holds and the upper bound of rewards is Cr.
M- = O(poly(d)) T 2 d. V = [2C] log(2M B /5))] with 51 E (0, (), w = >C + V y - &Cimp, = wCn, where C. > O which decreases with increase of 1/s and s E (0, 1). Let 82 E (0,0.1), PA < 1 be the constant defined in Theorem 3 and Creg be a positive constant that decreases with increase of l/e. For the sketch matrices {IT A HAEAME[N] and {īT AE assuming that the number of blocks in SJLT D O(E 'loog'''d )), and the sketch size satisfying
= Ω (d polylog (do, /=2),
7

---

then, for an arbitrary sequence of contexts (nn.bine(M with probability at least 1 1 N(1 +
Reg(N,B) B) I 20Creg V 10M + [)( + dB) + + (TV
(10)
a sublinear regret bound of order Ö( (d) provided that the sketch size ( polylog (olyyoo(dd2))) d)) We can observe that the lower bound of e independent of the overall number of steps T, and theoretical value of the batch size is
Remark 4. Setting B O PxC 1/d
B = CnyTid Cj,N/d /d, where setting CB 25 suitable choice that has been verified in the experiments in Section 6 In particular, when Px = O(1/d), the sketch size of order c (d polylogd) sufficient to achieve sublinear regret.
From the theoretical results of regret, we can observe that our SPUIR admits several advantages: (a) The order of our regret bound (w.r.t. the overall number of steps) is not higher than those in the literature in the fully-online setting (Li et al. 2019, Dimakopoulou et al., 2019) that is a more simple setting than ours; (b) The first term the regret bound (10) measures the performance of policy updating using imputed rewards (called "policy error"). "). From Theorem and demark[[][] we obtain that, in each episode, our policy updating has 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-hant side of (10) is of order ( /pxed/ 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 pxc, e.g., setting PXE = 1/4// yields a sketching error of order OTT3/5/1/2) provided that c = 2p polylog(d6,) VVT))
At a fundamental level, the effectiveness of the proposed reward imputation can be attributed to the following two key factors:
(I) Leveraging contextual bandit structure: Traditional bandit methods only consider the structural assumptions for executed actions, leaving out non-executed ones. Our reward imputation approach incorporates a wide range of reward function structural assumptions, covering both executed and non-executed actions. By imputing missing rewards with observed data, reduce the impact of missing data for a more accurate reward estimation.
(2) Balancing exploration and exploitation:
Reward imputation's 'ss effectiveness arises from its impact on the exploration-exploiaaiio trade-off. By incorporating imputed rewards, our proposed algorithms can make informed decisions even when observed rewards are incomplete. This enhances the agent's s exploration strategy, helping it discover more valuable actions and reducing cumulative regret. Essentially, our reward computation approach approximates full-information feedback. mitigating the explorc/cxploit dilemma.
5 Extensions of Our Approach
To make the proposed reward imputation approach more feasible and practical, we tackle the following two research questions by designing variants of our approach following the theoretical results:
RQ1 (Parameter Selection): Can we set the imputation rale 7 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 RQI, we equip PUIR and SPUIR with rate-scheduled approach, called PUIRRRS and SPUIR-RS, respectively. From Remark 2 a larger imputation rate - leads to a smaller variance while increasing the bias, while the bias term includes a monotonic decreasing function w.r.t. number of episodes under mild conditions. Therefore, we can gradually increase with the number of episodes, avoiding the large bias at the beginning of reward imputation. Specifically, we set y X% for episodes from (X 10)% N to X% x N, where X E [10, 100).
Application Nonlinear Rewards. For RQ2, we provide nonlinear versions of reward imputation. We use linearization technologies of nonlinear rewards, rather than directly setting the rewards as nonlinear functions (Valko et al.) 2013 Chatterji et al. 2019), avoiding the linear regret or curse of
We use the notation of Ô suppress logarithmic factors in the overall number of steps T'.
8

---

Table 2: Performance comparison of coupon recommendation commercial product
Algorithm
CVR (mean + std)
CTCVR (mean + std)
Time (sec., mean + std)
DFM-S
0.8656 1 0.0473
0.3317 1 0.0218
302.3140 1 8.3045
SBUCB
0.8569 + 0.0037
0,4277 + 0.0084
43.5435 + 0.3659
BEXP3
0,4846 + 0.0205
0.2425 + 0.0116
53.5001 = 0.9220
BEXP3-IPW
0,4862 + 0.0187
0.2436 1 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 1 0.0059
0,4397 0.0032
81.5753 1 1,5879
PUTR-RS
0.8763 + 0.0056
0.4389 + 0.0030
180.4999 + 1.7763
SPUIR-RS RS
0.8758 = 0.0058
0,4391 + 0.0031
80.8003 = 2.9030
kernelization. Specifically, instead of using the linear imputed reward (n,)(A)) =- 10%, .n,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, = exp (QTs). Then (0, A) = (0, VoGg sn,b)) where VoGr(0, sn,b) = exp (0T 8n.b) Sn.b-
(2) SPUIR-Poly. When the expected reward a polynomial function as Gr 8) (0T s)² Then T (0, A) (0, VoGp(0, sn,b)), where VeGp sn,b) (0TT,,,)) sn, 8n,b-
(3) SPUIR-Kernel Consider that the underlying expected reward in a Gaussian reproducing kernel Hilbert space (RKHS). We use (0, A) = (0, ((8,,))) in random feature space, where the random feature mapping é can be explicitly computed.
For SPUIR-ExP and SPUIR-Poly combining the linearization of convex functions Shalev-Shwarde 2011) with Theorem yields the regret bounds of the same order. For SPUIR- -ernel, using the approximation error of random features (Rahimi and Recht 2008), we can also obtain that, SPUIR- Kernel has the same regret bound SPUIR under mild conditions (see proofs in Appendix B).
Experiments
We empirically evaluated the performance of our algorithms on 3 datasets: the synthetic dataset, publicly available Criteo d (Critee-recent,, Criteo-all and dataset collected from Tencent's WeChat app for coupon recommendation (commercial product).
Experimental Settings. We compared our algorithms with: Sequential Batch UCB (SBUCB)
(Han et al.) 2020). Batched linear EXP3 (BEXP3) (Neu and Olkhovskaya 2020). Batched linear EXP3 using Inverse Propensity Weighting (BEXP3-IPW (Bistritz et al. 2019), Batched Balanced Linear Thompson Sampling (BLTS-B) (Dimakopoulou et al. 2019). and Sequential version of Delayed Feedback Model (DFM-S) (Chapelle 2014). We applied the algorithms to CBB setting and implemented
Intel(R) Xeon(R) Silver 4114 CPU@@ @2. 2. 2.20GHz, and repeated the experiments 20 times. We tested the performance of algorithms in streaming recommendation scenarios, where the reward is represented by linear combination of the click and conversion behaviors of users. According to Remark 4 we set the batch size as B = C2 N/d, /d, the constant CB ss 25, and the sketch size c 150 on all the datasets. The average reward was used to evaluate the accuracy of algorithms.
Performance Evaluation. Figure (C) reports the average reward of SPUIR with variants and the baselines. We observed that SPUIR and its variants achieved higher average rewards, demonstrating the effectiveness our reward imputation. Moreover, SPUIR and its rate-scheduled version SPUIR-RS RS had similar performances compared with the origin PUIR, which indicates the practical effectiveness of our variants and verifies the correctness of the theoretical analyses. The results commercial product in Table 2 indicate that SPUIR outperformed the second-best baseline with the improvements of 1.07% CVR (conversion rate) and 1.12% CTCVR (post-view

---

c07
PLE
Aver Nowaard
420
320
PICC
Number Estovits
Number Edisodes N
Namber Epiendes
(a) synthetic data
(b) Criteo-all
commercial product
234
C118
2.31
2014
X234
435
530
0n
DAR
1965 Juaa 1ec Kokc Nik sais wis
(d) nonlinear reward
(c) hatch size B
(f) sketch size
Figure 3: (a), (b), (c): Average rewards of the compared algorithms, the proposed SPUIR and its variants synthetic dataset, Criteo dataset, and the real commercial product data, where omitted the curves of algorithms whose average rewards are 5% lower than the highest reward; (d): SPUIR and its three nonlinear variants synthetic dataset; (e): SPUIR with different batch sizes Priteo-recent, (f): SPUIR and SPUIR-RS with different sketch sizes on synthetic dataset
dliccthrough&cconversion rate). Besides, our reward imputation approaches were more efficient than DFM-S, BLTS-B. The variants using sketching of algorithms (SPUIR, SPUIR-RS) significantly reduced the time costs of reward imputation, and took less than twice as long to run compared to
the baselines without reward imputation (SBUCB, BEXP3, BEXP3-IPW). Figure 3 d) illustrates performances of SPUIR and its nonlinear variants, where SPUIR Kernel achieved the highest rewards indicating the effectiveness of the nonlinear generalization of our approach. For different decision tasks, a suitable nonlinear reward model needs to be selected for better performances.
observe that larger batch size B results larger first term (of order OBB), called policy error) but a smaller second term (of order (1/B), called sketching error), indicating that suitable batch size B needs to be set. This conclusion was empirically verified in Figure e),, where
Parameter Influence. From the regret bound (O),
1, 000 (Cn 25) yields better empirical performance in terms of the average reward. Similar phenomenon dataset and comme r i product. All of the results verified the theoretical results Remark 4
also be observed
Criteo
B CB / /Td Cß /d is suitable choice while setting CB 25. From the results in Figure we observe that, for our SPUIR and SPUIR-RS the performances significantly increased when the sketch size e reached 10%. (ss d log d), which demonstrates the conclusion in Remark 4 that only the sketch size of order c Q(d polylogd) is needed for satisfactory performance.
7 Conclusion
This paper presents a computationally efficient reward imputation approach for contextual batched bandits that addresses the challenge of purial-information feedback real-world applications. The proposed approach mimics the reward generation mechanism of the environment, approximating full-information feedback. reduces time complexity using sketching, achieves a relative-error bound for approximation, and exhibits regret with controllable bias and reduced variance. The theoretical formulation and algorithmic implementation may provide an efficient reward imputation scheme for online learning under limited feedback.
10

---

Acknowledgments and Disclosure of Funding
This work was funded by the National Key R&D Program of China (2022ZD01 14802), the Na- tional Natural Science Foundation of China (62376275, U2001212, 62377044), Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Fine Class" Initiative, Renmin University of China. Supported by fund for building world-class universities (disciplines) of Renmin University of China. Supported by Public Computing Cloud, Renmin University of China. Supported by the Fundamental Research Funds for the Central Universities, and the Research Funds of Renmin University of China (23XNKJ13).
References
Auer, (2002). Using confidence bounds for exploitation-explorraion trade-offs. Journal of Machine Learning Research, 3:397-422
Bistritz, Zhou, Z., Chen, Bambos, N., and Blanchet, (2019). Online EXP3 learning adversarial bandits with delayed feedback. Advances Neural Information Processing Systems 32, pages 11349-11355 13588.
Calandriello, D., Lazaric, A., and Valko, M. (2017). Efficient second-order online kemnel learning with adaptive embedding. Advances Neural Information Processing Systems 30, pages 6140-6150.
Chapelle, O. (2014). Modeling delayed feedhack in display advertising. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1097-1105.
Chatterji. N. S., Pacchiano, A., and Bartleu, P. L. (2019). Online learning with kernel losses. In Proceedings of the 36th International Conference on Machine Learning, pages 1990
Chou, K.-C., Lin, H.-T., Chiang, C.-K., and Lu, C.-J. (2015). Pscudo-reward algorithms for contextual bandits with linear payoff functions. In Proceedings of the 6th Asian Conference on Machine Learning, pages 344-359.
Chu. W., Li, L.. Reyzin, L.. and Schapire. R. E. (2011), Contextual bandits with linear payoff functions. In Proceedings of the 14th International Conference on Artificial Intelligence and Statistics, pages 208-214.
Dimakopoulou, M., Zhou, Z., Athey, S., and Imhens, G. (2019). Balanced linear contextual bandits. In Proceedings of the 33rd AAAI Conference Artificial Intelligence, pages 3445-3453.
Esfandiari, H., Karbasi, A., Mchrabian, A., and Mirrokni, S. (2021). Regret bounds for batched bandits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 7340-7348.
Gao, Z., Han, Ren, Z., and Zhou, (2019). Batched multi-armed bandits problem. Advances Neural Information Processing Systems 32, pages 501-511.
Q.. Karbasi, A., Khosravi, K., Mirrokni, V., and Zhou, D. (2021). Batched neural bandits. arXiv preprint arXiv:2102.1 132.8
Han, Y., Zhou, Z., Zhou, Z., Blanchet, H., Glynn, P. W., and Ye, Y. (2020). Sequential batch learning in finite-action linear contextual bandits. CoRR, hos/2204406321..
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is q-learning provably efficient? In Advances in Neural Information Processing Systems 31.
Kane, D. M. and Nelson, J. (2014). Sparser 4:23.
transforms. Journal of the ACM, 61(1):4:1-
Kim, G. and Paik, M. C. (2019). Doubly-robust lasso bandit. In Advances in Neural Information Processing Systems 32, pages 5869-5879.
Lan, A. S. and Baraniuk, R. G. (2016). A contextual bandits framework for personalized learning action selection. In Proceedings of the 9th International Conference on Educutional Data Mining, pages 429-429.
Li, I.., Chu, W., Langford, J., and Schapire, R. F. (2010). contextual-handit approach to personalized news article recommendation. In Proceedings of the 19th International Conference on World Wide Web, pages 661-670.
Li. S., Chen, W., Li. S., and Leung. K. (2019). Improved algorithm on online clustering of bandits. In Kraus, S., editor, Proceedings of the 28th International Joint Conference on Artificial Intelligence, volume Li2019Improved, pages 2923-222222 2929.

---

Nelson, J. and Nguyên, H. L. (2013). OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings. In Proceedings of the 54th Annual Symposium Foundations Computer Science, pages 117-126.
Neu, G. and Olkhovskaya, J. (2020). Efficient and robust algorithms for adversarial linear contextual bandits. In Proceedings of the 33rd Conference on Learning Theory, pages 3049-3068.
Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2016). Batched bandit problems. The Annals of Statistics, 44(2):600 681.
Rahimi, A. and Recht, B. (2008). Weighted sums of random kitchen sinks: Replacing minimization with randomization learning. Advances Neural Information Processing Systems 21, pages 1313-1320.
Ren, Z. and Zhou, Z. (2020). Dynamic batch learning in high-dimensional sparse linear contextual bandits. arXiv preprint Xiviii2000..1111 11918.
Shalev-Shwartz, S. (2011). Online learning and online convex optimization. Foundations and Trends Machine Learning, 4(2):177-19.
Valko, M., Korda, N., Munos, R., Flaounas, N., and Cristianini, N. (2013). Finite-time analysis of kemelised contextual bandits. Proceedings of 29th Conference on Uncertainty in Artificial Intelligence.
Wang, C. and Cheng, G. (2020). Online batch decision-making with high-dimensional covariates. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pages 3848-3857.
Woodruff, D. (2014). Sketching tool for numerical linear algebra. Foundations and Trends Theoretical Computer Science, 10(1-2):1-157.
Yang, J., Hu, W., Lee, J. D., and Du, S. (2021). Impact of representation learning in linear bandits. In Proceedings of the 9th International Conference on Learning Representations.
Yom-Tow non-Tov, Feraru, G., Kozdoba, M., Mannor, S., and Hochberg, (2017). Encouraging physical activity patients with diabetes: Intervention using a reinforcement learning system. Journal of Medical Internet Research, 19110):338.
Zhang, K. W., Janson, I.., and Murphy, S. (2020). Inference batched bandits. In Advances in Neural Information Processing Systems 33, pages 9818 9818-9829.
Zhang, X., Dai, S., Xu, J., Dong. Z., Dai, Q., and Wen, J. (2022). Counteracting user attention bias music streaming recommendation via reward modification. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2504-2514.
Zhang, X., Jia, H., Su, H., Wang, W., Xu, J., and Wen, J. (2021). Counterfactual reward modification for streaming recommendation with delayed feedback. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 41-50.
Zhang, X. and I. Liao, S. (2019). Incremental randomized sketching for online kernel learning. In Proceedings of the 36th International Conference Machine Learning, pages 7394-7403.
Zhou, Z. (2023). Stream efficient learning. CoRR, abs/2305.02217.
12


Reviews:
[{"review_id": "86xspUjhin", "reviewer": "Reviewer_PXsH", "summary": "This paper studies the contextual batched bandits (CBB) setting, where compared to classical online CB, a batch of actions is played and the reward being observed in an episode. Motivated from the benefit of full-information feedback, it tries to perform the reward imputation for unlabelled data, and optimizes the reward parameter by minimizing the combined MSE loss of observed data and imputed data. To further reduce computational complexity, it uses sketching to compress the matrix used in linear regression. Empirically, it shows better performance in both synthetic and real-world experiments. ", "questions": "See weakness part. ", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- In the batch bandit literature, the bias-variance trade-off is mostly happened between IPS and reward modeling approaches. This paper focus on another level of bias-variance trade-off within the reward model estimate. It performs reward imputation on unlabelled data then doing regression on top of that. The overall objective contains both the observed fitting loss and the weighted imputed loss, where increasing the weight increases the bias, but potentially decreasing the variance, which gives another level of bias-variance trade-off within the reward model. The idea is interesting.\n\n- The paper is well-written and easy to follow. The method is supported by the theoretical analysis of the instantaneous regret bound. \n\n- To further reduce the complexity, the paper introduces using sketching based on the SJLT, which significantly reduces the time complexity, without losing too much performance. ", "weaknesses": "- Intuitively, the imputed data in early rounds seem less important (i.e., in terms of accuracy) compared with the imputed data in later rounds, which this requires we basically weigh the imputed data differently, instead of using a fixed $gamma$ for all imputed data. I am not sure how the authors think about this aspect? It would be interesting to see how it works empirically.\n\n- The imputed method seems a way to improve reward models. Fitting a reward model is like a supervised learning problem and there are bunch of ways to reduce variance, like ensemble-based, it would be great to add these baselines, and arguing how the current method helps.\n\n- It seems from Eq 9, the $\\gamma$ term could be optimized to minimize the instantaneous regret bound, instead of using a heuristics on this.\n\n- Given there exists synthetic experiments, is it possible to plot the bias, variance, regret for each method? and visualize how the PUIR/SPUIR helps, and how they support the theory.\n\n- I am actually curious to see whether this way of improving reward model also translates to doubly robust based method, where it combines with IPS weighting based approach? \n\n ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer PXsH\n\nThank you for your comments and suggestions.\n\n**1. Response to Weakness 1: Setting of Imputation Rate $\\gamma$**\n\nIndeed, we have identified the consideration you mentioned regarding the setting of the imputation rate $\\gamma$. We have introduced rate-scheduled versions of our PUIR and SPUIR approaches in Section 5 lines 261-266, termed as PUIR-RS and SPUIR-RS.\n\nPUIR-RS and SPUIR-RS eliminate the need for preseting and tunning the imputation rate $\\gamma$. Instead of employing a fixed imputation rate, we dynamically adjust the weights of the imputed data by gradually increasing $\\gamma$ as the number of episodes increases. This approach helps to mitigate the significant bias that might occur at the initial stages of reward imputation. More specifically, we set $\\gamma= X\\%$ for episodes ranging from $(X-10)\\% \\times N$ to $X\\% \\times N$, where $X \\in [10, 100]$.\n\nThe experimental results, showcased in Table 2 and Figure 3 within the article, reveal that PUIR-RS and SPUIR-RS perform equally well in terms of reward improvement when compared to PUIR and SPUIR with manually tuned $\\gamma$ values. Notably, SPUIR-RS even outperforms SPUIR on the Criteo-all dataset. These experimental findings further validate the analyses we provided concerning the reward imputation bias in Theorem 2.\n\nFor additional experimental results regarding rate-scheduled $\\gamma$, please refer to Table 3, Table 4, and Figure 2 in Appendix C.3.\n\n**2. Response to Weakness 2: Ensemble-based Baselines**\n\nThank you for your suggestion. We have incorporated experiments related to \"ensemble-based baselines\" in the newly uploaded PDF (UCB-AdaBoost and UCB-Bagging in Table 1 and Table 2). In these experiments, \"UCB-AdaBoost\" refers to utilizing AdaBoost to train the reward model for the batched UCB policy, and \"UCB-Bagging\" involves employing Bagging to train the reward model for the batched UCB policy.\n\nFrom the experimental results, it is evident that, in terms of rewards, the improvements brought by ensemble-based baselines are only marginal compared to SBUCB, while introducing additional computational cost. This phenomenon can be primarily attributed to the fact that in the bandit setting, ensemble methods can only enhance the accuracy of reward model estimation based on the limited observed feedback. They do not sufficiently leverage the structural information underlying unobserved reward feedback, thus failing to significantly benefit the exploration-exploitation tradeoff of bandit policy. In contrast, the reward imputation approach proposed in our paper effectively utilizes the structural information of the reward function, thereby enhancing the effectiveness of the exploration-exploitation tradeoff.\n\n**3. Response to Weakness 3: Experimental Curves depicting Bias, Variance, and Regret**\n\nIn the newly uploaded PDF, Figure 1 and Figure 2 present experimental curves showcasing bias, variance, and regret. Based on the experimental results, the following conclusions can be drawn:\n\n* The additional bias introduced by our approaches gradually diminishes with increasing episodes, as depicted in Figure 1(a). Moreover, the additional bias in comparison to the inherent bias (bias of SBUCB without reward imputation) is only a marginal fraction, approximately $2\\%$, as illustrated in Figure 1(b).\n\n* The proposed reward imputation plays a pivotal role in significantly reducing variance. This achievement is evidenced by a nearly $10\\%$ reduction in variance when compared to the variance of SBUCB, as shown in Figure 2(b).\n\n* The regret associated with PUIR and SPUIR is notably smaller compared to the baseline SBUCB without reward imputation. This distinction is illustrated in Figure 2(a).\n\n\n**4. Response to Weakness 4: Optimization Imputation Rate $\\gamma$**\n\nWe have indeed considered optimizing the imputation rate, denoted as $\\gamma$, but encountered significant challenges in doing so. The primary obstacle arises from the fact that, as shown in Equation (9), $\\gamma$ is embedded within the inverse matrix in the variance term. This inherent complexity makes a direct optimization of the imputation rate $\\gamma$ extremely difficult.\n\nHowever, we have introduced a parameter-free approach targeting the imputation rate $\\gamma$, referred to as the \"rate-scheduled approach,\" which is presented in line 261 of Section 5. This approach has yielded promising results by gradually increasing the value of $\\gamma$. Detailed information regarding this approach can be found in the *Response to Weakness 1: Setting of Imputation Rate $\\gamma$*.\n\n**5. Response to Weakness 5: IPS Weighting Extension**\n\nThank you for your valuable insights. As you rightly pointed out, our work distinguishes itself by focusing on a distinct dimension of the bias-variance trade-off within the reward model estimate, achieved through reward imputation on unlabeled data. Our reward imputation approach has the potential to seamlessly integrate with the IPS weighting approach, leading to the development of a novel doubly robust-based methodology. However, such an extension requires some refinements to our approach. For instance, transforming our deterministic policy into a stochastic one. \n\nIn existing experimental results, our reward imputation-based bandits exhibited superior performance compared to existing IPS-based baselines (BEXP3-IPW, BLTS-B). In the newly uploaded PDF (PUIR-DR in Table 1 and Table 2), we have added preliminary experimental validation, indicating that our reward imputation-based doubly robust bandit achieved further enhancements in rewards, albeit with an increase in computational cost. The theoretical analysis and efficient algorithm design for the doubly robust bandit based on our reward imputation approach remain a challenging yet promising open research avenue. We look forward to collaborating with domain experts in addressing this intriguing question in the future.\n\n"}, {"review_id": "euYFEok4Sw", "reviewer": "Reviewer_wPev", "summary": "This paper studies the contextual batched bandit (CBB) problem, where the learner interacts with the environment in an online manner through $N$ episodes. In episode $n$, the learner selects the policy $p_n$,  receives $B$ contexts $s_{n,b}\\in \\mathbb{R}^d$,  decides the action $A_{I_{n,b}}$ according to $p_n(s_{n,b})$, receives the feedback and updates the policy. The reward is determined by an unknown action-specific reward parameter vector $\\theta_{A}^\\star$ such that $\\mathbb{E}[ R_{i,A} ] = \\langle \\theta_{A}^\\star, s_i  \\rangle$ for context $s_i$. \n\nTheorem 1 states the fact that the upper bound of instantaneous regret in the FI-CBB setting is tighter than that in CBB setting, where \"FI\" means full-information feedback, that is, the learner is able to observe all the losses of both executed and non-executed actions. \n\nThen, this paper proposes reward imputation to estimate the reward feedbacks for the non-executed actions. Roughly speaking, the learner estimates the reward for the non-executed actions by using an imputed reward vector in Line 144. Then, the parameter vector is updated of the imputed reward and the observed reward together (with respect to $\\gamma$, the imputation rate) as shown in Equation. (1). To further improve the efficiency, the paper utilizes the sketching technique to reduce the computational cost from $\\mathcal{O}(Bd^2)$ to $\\mathcal{O}(cd^2)$ where $c$ is the sketch size and assumed to be $d<c<B$ and $dc>B$. \n\nThe instantaneous regret bound is stated in Theorem 2. The approximation error bound of using sketching is described in the Theorem 3, and the final regret bound of the reward imputation with sketching is stated in Theorem 4. \n\n", "questions": "My questions are raised in the weakness section. I am willing to re-evaluate the score if the questions are answered properly. ", "limitations": "This work is pure theoretical, and does not have any potential negative societal impact. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper is clearly-written and self-contained. The notations are well-defined prior to the usages. \n2. The paper has some nice experiment results for demonstration. ", "weaknesses": "1. The comparison between the regret bound with/without reward imputation is a little vague: from line 248 to line 250, the authors claim that \"in each episode, our policy updating has a smaller variance than the policy without the reward imputation, and incurs a decreasing additional bias under mild conditions, leading to a tighter regret (i.e., smaller policy error) after some number of episodes\". I wonder if the authors could be more specific that which algorithm they are comparing to? \n2. The assumption \"if $\\Pi$ and $\\widehat{\\Pi}$ are SJLT, assuming that $D=\\Theta(...)$\" is not very clear.  Does this assumption hold usually or with high-probability? \n3. Is the batch size $B$ a tunable hyper-parameter? In Remark 3, the authors set $B = \\mathcal{O}(\\sqrt{T/d})$, while in Protocol 1, the batch size $B$ seems to be fixed prior to the interaction? In addition, the condition that $d<c<B$ and $cd>B$ is not reasoned in details. \n\n[Minor Issues] \n1. The problem setting is not well-organized. The interaction protocol is described separately in the introduction and problem formulation sections. I would like to suggest putting all the notations into one section for better readability. \n  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer wPev\n\nThanks for your comments and suggestions.\n\n**1. Response to Weakness 1: Regret Comparison**\n\nIn the discussion of the regret bound theory, we compare our proposed \"policy with reward imputation\" to a \"policy without the reward imputation\" that corresponds to the Batch UCB Policy (as described in Algorithm 1 in Appendix A.2). In Eq. (1), if we do not use the imputation term during parameter updating, the policy will degrade to a Batch UCB Policy. The discussion following Theorem 1 (lines 248 to 250) demonstrates that our reward imputation approach tightens the regret bound on the original policy. This is achieved by maintaining a decreasing additional bias while simultaneously reducing variance.\nAs empirical validations of the theoretical findings, we have added illustrations of bias, variance, and regret for the proposed algorithm in the newly uploaded PDF (Figure 1 and Figure 2). From the experimental results, it is evident that the proposed reward imputation approach has a positive impact on both reducing additional bias and decreasing variance.\n\nWe will incorporate the aforementioned discussion and results into the final version of the paper.\n\n**2. Response to Weakness 2: Assumption on SJLT**\n\nIn Theorem 3, the assumption about SJLT is guaranteed to be satisfied. Specifically, $D$ (defined in line 178) represents the number of sub-matrices used during the construction of SJLT. Given the preset values of the error tolerance $\\varepsilon$, failure probability $\\delta$, and input dimension $d$, the value of $D$ can be determined according to Theorem 3 as follows: $D = \\Theta ( \\varepsilon^{-1} \\log^3 ( d \\delta^{-1} ) )$. This theoretical recommendation for $D$ ensures the required properties of SJLT.\n\n**3. Response to Weakness 3: The Batch Size $B$**\n\nThe batch size $B$ can be set based on the theoretical value provided in Remark 3. Specifically, the theoretical value of the batch size is $B = C_B \\sqrt{T / d}$. In our experiments, given the number of round $T$ and the input dimension $d$, we found that a suitable choice for the constant $C_B$ is approximately 25 for all the datasets (for more details, refer to Table 1 in Appendix C.1).\n\nAdditionally, the two conditions for the sketch size $c$, namely $d < c < B$ and $cd > B$, are easily satisfied. Here are the specific settings for the sketch size $c$ for various experiments, as described in Table 1 in Appendix C.1 and Table 2 in Appendix C.2:\n\n* Synthetic data: $B = 1,400$, $d = 40$, $c = 150$.\n\n* Criteo-recent dataset: $B = 1,000$, $d = 50$, $c = 150$.\n\n* Criteo-all dataset: $B = 4,000$, $d = 50$, $c = 150$.\n\n* Commercial product dataset: $B = 1,700$, $d = 50$, $c = 150$.\n\nAll of the above experimental settings satisfy the conditions $d < c < B$ and $cd > B$.\n\n**4. Response to Minor Issue**\n\nThank you for the valuable feedback. We sincerely appreciate your suggestions and will make the necessary changes to improve the organization of the final version. Specifically, we will consolidate the interaction protocol and related notations into one dedicated section titled \"Problem Formulation\" to enhance readability and clarity for the readers.\n\nWe look forward to the possibility of receiving a higher score based on the provided responses. With the limited time remaining, we kindly request you to inform us of any lingering concerns you may have. We are fully committed to addressing any remaining issues to the best of our abilities, and we greatly value the opportunity to refine our work further.\n"}, {"review_id": "92G16HE4RH", "reviewer": "Reviewer_mYi5", "summary": "This paper uses imputation to improve the learning of the reward parameters, even for nonexecuted steps. This results in better variance and empirical benefits over many existing algorithms. ", "questions": "1. I think the paper could be improved by reducing the amount of time discussing the difference between full and partial feedback. I don't believe it adds much to the paper. \n2. How does the regret analysis in Theorem 4 compare to recent algorithms tackling Contextual Batched Bandits?", "limitations": "The limitations could have been a bit more developed and further extensions could be discussed more. \n\nOverall, I currently vote for acceptance. However, if the authors do not provide a good rebuttal and fix the issues with the limitations, I may have to reduce my score. However, I believe the issues are fixable.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The empirical benefit seems quite strong over existing algorithms on real datasets.\n2. The proposed idea is clear and intuitive. \n", "weaknesses": "1. I found the notation quite difficult to parse, especially at the beginning of page 4. For example, $L_j^n$ was discussed before it was defined.  Moreover, what is $\\nu$ in Theorem 2?\n2. The improvement seen by imputation is a little tricky to see without knowledge of $C_{\\text{imp}}$ in the bound. I find it a little dubious that the amount in which the bias increases by using imputation is hidden by this mysterious constant $C_{\\text{imp}}$. The fact that it is monotonically decreasing is not sufficient. I would like to see a more in-depth analysis of this term to understand better whether imputation truly improves our bounds. \n3. A similar problem is in Theorem 4. The constant $C_{\\text{reg}}$ is presented without a true interpretation. The improvement of the regret seen here over traditional algorithms is unclear. I believe the dependence on $d$ and $T$ achieved here are similar to what is achieved in the literature already. Therefore, understanding the other constants here is important. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer mYi5\n\nWe are grateful for the time you took to review our paper and grasp the gist of its content. \n\n**1. Response to Weakness 1: Notations**\n\nWe have checked and refined the order of symbol introductions and will include a new notation introduction in the final version. In fact, $\\nu$ was introduced in line 200. We acknowledge that due to the placement of Table 1, the presentation might have caused confusion.\n\n**2. Response to Weakness 2: Constant $C_{\\mathrm{Imp}}$ in Additional Bias**\n\nIn fact, we have devoted significant effort to obtain a comprehenscive theoretical analysis of the additional bias, with the details in Appendix B.1. However, for the sake of reader comprehension, we have streamlined it into a constant denoted as $C_{\\mathrm{Imp}}$ in the main text.\n\nNow, we summarize the theoretical analysecs for the additional bias:\n\n* During the proof of Thm.2 (Appendix B.1 Line 115-117), it was revealed that in the $n$-th episode, the upper bound of the additional bias can be represented by a function $f_{\\mathrm{Imp}}(n):=\\sum_{i \\in [n-1]}(\\sqrt{\\eta})^{n-i}CIR_i,$ where $CIR_i $ stands for the cumulative instantaneous regret in the $i$-th episode. Thus, the analysis of the additional bias is transformed into the analysis of the properties of $f_{\\mathrm{Imp}}(n)$.\n\n* Lemma B.1 in Appendix B.1 analyzes the convergence and monotonicity of $f_{\\mathrm{Imp}}(n)$, revealing that under mild conditions (Remark B.1 of Appendix B.1), $f_{\\mathrm{Imp}}(n)$ is monotonically decreasing. This property allows the additional bias to be expressed as $\\gamma^{\\frac{1}{2}}\\eta^{-\\frac{1}{2}}f_{\\mathrm{Imp}}(n)$, controllable by the imputation rate $\\gamma$. This result indicates that the additional bias decreases as the number of episodes increases, which aligns intuitively with the notion that reward imputation leverages an estimated reward model that becomes more accurate with an increasing sample size.\n\nMoreover, we validate theoretical findings with bias, variance, and regret curves in the uploaded PDF (Fig.1 and Fig.2). Our empirical analysis yields these conclusions:\n\n* The additional bias of our approaches diminishes gradually with increasing episodes, and the additional bias compared to the inherent bias (SBUCB's bias) is only a minimal fraction.\n\n* Our reward imputation significantly decreases variance, achieving a nearly 10% reduction compared to the variance of SBUCB.\n\n* The regret of PUIR and SPUIR is smaller compared to SBUCB.\n\n**3. Response to Weakness 3: Cumulative Regret**\n\nThe constant $C_{\\mathrm{reg}}$ is defined as  $C_{\\mathrm{reg}}=\\sqrt{\\dfrac{\\tilde{\\sigma}_1^2+\\lambda}{\\tilde{\\sigma}_d^2[1-2\\varepsilon/(6+3\\varepsilon)]+\\lambda}}$ (Appendix, line 269). Here, $\\varepsilon$ represents the sketching approximation error, $\\tilde{\\sigma}_1$ and $\\tilde{\\sigma}_d$ are the maximum and minimum singular values of context matrix (Appendix B.3, line 227), and $\\lambda$ is a regularization parameter. The source of $C{\\mathrm{reg}} \\geq 1$ is the sketching approximation:\n\n* When sketching is not used for acceleration ($\\varepsilon=0$), $C_{\\mathrm{reg}}$ reduces to 1, meaning it has no impact on the cumulative regret bound.\n\n* As per the definition of $C_{\\mathrm{reg}}$, it decreases with increasing $1/\\varepsilon$. The lower bound on the sketch size required for obtaining the cumulative regret bound is given by $c=\\mathrm{\\Omega}(d\\;\\mathrm{polylog}\\left(d\\delta_2^{-1}\\right)/\\varepsilon^2)$. This implies that for smaller preset sketching approximation errors $\\varepsilon$, a larger sketch size $c$ is needed, which in turn reduces the value of $C_{\\mathrm{reg}}$ in the cumulative regret bound.\n\nHence, the parameter $C_{\\mathrm{reg}}$ in the cumulative regret bound quantitatively characterizes the trade-off between sketching approximation error and cumulative regret. This serves as a key contribution of Thm.4, differentiating it from the existing batched contextual bandit theoretical analyses.\n\nDue to the existing focus of cumulative regret bounds for batched contextual bandits on the orders with respect to input dimension $d$ and the number of rounds $T$, many constants have been overlooked in their derivation. This perspective might lead to an initial impression that our proposed method does not exhibit a significant improvement in terms of these orders and other constants. \nHowever, it's important to emphasize that by considering the instantaneous regret bound in Thm.2, we can confidently assert: Within the cumulative regret bound Eq.(10), the cumulative variance terms $\\sqrt{10M}\\log(T+1)(\\sqrt{dT}+dB)$ associated with the proposed approaches have neglected constants that are undoubtedly smaller compared to the corresponding cumulative variance terms of the batched UCB policy without reward imputation. The added experimental results in the uploaded PDF (Fig.1 and Fig.2) validate this observation: it is evident that our PUIR and SPUIR consistently achieve lower cumulative regrets compared to batched UCB policy.\n\n**4. Response to Question 1: Simplified Discussion**\n\nWe have condensed the second paragraph of the introduction and streamline the discussion about full and partial feedback in Section 2.\n\n**5. Response to Question 2: Regret**\n\nCompared to recent algorithms addressing contextual batched bandits' regret analysis, our regret analysis quantitatively characterizes the trade-off between sketching approximation error and cumulative regret. This constitutes a significant contribution of Thm.4, setting it apart from existing theoretical analyses of contextual batched bandits (CBBs). The orders of the number of rounds $T$ and the input dimension $d in our regret upper bound, match the lower bound of CBBs. Furthermore, based on the analysis of bias and variance in Thm.2, the cumulative variance term within our regret bound demonstrates reduced magnitude in our regret bound. For detailed information, please refer to the feedback in *Response to Weaknesses 3*."}, {"review_id": "kuRAnVyNsA", "reviewer": "Reviewer_et1K", "summary": "This paper focuses on contextual batched bandit (CBB) problems, where only partial information (the rewards of executed actions) is available. The authors proposed an efficient reward imputation approach in CBB, which completes the unobserved reward, and the new objective can be solved by the imputation regularized ridge regression. They further proposed sketching to reduce time complexity. Theoretical guarantees are established, showing that this approach has a sublinear regret bound against the optimal policy.  Experiments are conducted, showing its superiority over baselines.", "questions": "- Is the batch size $B$ predetermined by the problem setup, or can it be manually adjusted by the learner? In the analysis conducted by the authors (e.g., Remark 3), they define $B$ to be on the order of $O(\\sqrt{T})$, indicating that it is likely the latter case. In that context, what are the theoretical advantages of this algorithm when setting $B=1$ compared to standard contextual bandit algorithms? Can we simply apply CB algorithms to this particular setting with $B=1$ then?\n\n- It looks like eq. (2) is a solution to eq. (1), which makes me wonder where the discount parameter $\\eta$ in line 156 comes from. Is $\\eta$ a predetermined hyperparameter or an arbitrary parameter? If it is the former, I did not find it in the problem setup; if it is the latter, it seems so weird as it suggests that any $\\eta$ would make eq. (2) a solution to eq. (1)? \n\n- Why is Theorem 2 referred to as the \"instantaneous regret bound\"? Shouldn't the instantaneous regret involve $\\max\\_a\\langle\\theta^*\\_A,s\\_{n,b}\\rangle$? This theorem seems to be more of a bound on estimation error.", "limitations": "No potential negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well-structured. The proposed reward imputation for the non-executed actions is innovative, and this idea seems widely applicable in many scenarios. Proof-of-concept experimental results support their theoretical claims. ", "weaknesses": "A high-level idea of reward imputation needs to be provided, especially regarding why reward imputation is effective statistically. At a high level, it seems counter-intuitive since the imputed rewards are derived from the observed rewards, so it should not yield any statistical improvement. If there is indeed no improvement, the position of this work would be in question. However, the authors did achieve improvement, so it would be valuable for them to offer a high-level explanation regarding why reward imputation works in this context.\n\nIn addition, the absence of definitions for certain notations in the paper somewhat makes it challenging to evaluate certain results. I apologize if I may have overlooked these definitions in the paper. I have listed these issues in the \"Questions\" section below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer et1K\n\nThank you for your reviews and suggestions.\n\n**1. Response to Weakness**\n\nWe appreciate the reviewer's insightful suggestion regarding the high-level idea. At first glance, the concept of reward imputation might appear counter-intuitive, as imputed rewards are derived from observed rewards, seemingly not providing any statistical advantage. However, in the context of our work, reward imputation proves effective due to the several key factors.\n\nReward imputation leverages the inherent structure within contextual bandit problems. Reward imputation capitalizes on the intrinsic structure inherent to contextual bandit problems. More specifically, contextual bandit problems often assume that the expected rewards for each arm are functions of the context (e.g., linear or nonlinear functions as explored in this paper). Traditionally, the structural assumptions of these reward functions are solely employed on executed actions within each interaction round, neglecting non-executed actions. The pivotal aspect introduced by our reward imputation approach lies precisely in incorporating a comprehensive range of reward function structural assumptions, encompassing both executed and non-executed actions. By utilizing observed rewards to impute unobserved or missing rewards, we create a more comprehensive dataset that captures underlying patterns and relationships. The introduction of imputed rewards fills information gaps and mitigates the influence of missing data, ultimately leading to a more accurate estimation of the true reward distribution.\n\nMoreover, the effectiveness of reward imputation stems from the interplay between exploration and exploitation. By incorporating imputed rewards, our proposed algorithms make informed decisions even in situations where observed rewards might be incomplete. This improves the agent's exploration strategy, enabling it to discover more valuable actions, which in turn contributes to the cumulative regret reduction. In essence, our reward computation approach approximates a scenario resembling full-information feedback, which mitigates the explore/exploit dilemma, introduces a lower variance, and introduces a controlled additional bias component within the regret. The extra information influencing policy towards exploitation and away from exploration emanates from the estimated reward structures of non-executed actions maintained within each episode. Our reward imputation approach effectively captures this additional information, underscoring its effectiveness and efficiency.\n\nIn summary, the key to understanding why reward imputation works in this context lies in the fact that it enhances the agent's decision-making process by effectively utilizing available data and reducing the impact of missing rewards. This, in turn, strengthens the exploration-exploitation trade-off, leading to the observed improvements in regret reduction. \n\n**2. Response to Question 1: Batch Size**\n\nIn practical online environments, bandit polices involve selecting an arm to execute in each round of interaction, while the batch size merely determines how often the bandit policy is updated. This update frequency can certainly be manually adjusted by the learner based on computational constraints, which is the specific focus of this paper.\n\nThe reward imputation approach we propose is applicable to scenarios with any batch size, including the case where $B=1$. Remark 3 analyzes the regret bound of SPUIR, which employs sketching techniques to accelerate the processing speed of each data batch. The theoretical value $B=O(\\sqrt{T/d})$ strikes the optimal balance between sketching approximation error and regret. Even in the setting of standard contextual bandit algorithms (i.e., $B=1$), the proposed reward imputation approach still holds advantages in reducing regret. Specifically, as Theorem 2 indicates, even when $B=1$, our reward imputation approach continues to yield smaller variance and a controllable bias, ensuring its effectiveness.\n\n**3. Response to Question 2: Discount Parameter**\n\nWhen the discount parameter $\\eta = 1$, Eq.(2) represents the closed least squares solution of Eq.(1). As mentioned in line 155, we refer to Eq.(2) as the \"discounted variant of the closed least squares solution,\" which introduces decay to the historical context matrix and reward vector on top of the original closed least squares solution. We observe that the discount parameter allows for control over the rate at which previous imputed rewards (which may be inaccurately estimated) are forgotten. This control can contribute to ensuring the regret bound as presented in Theorem 2. The theoretical value of $\\eta$ is discussed in Remark 2. Since the formulation of the regression problem corresponding to this discounted variant of the closed least squares solution becomes intricate, we have chosen to provide an explanation only at the point of the solution.\n\n**4. Response to Question 3: Instantaneous Regret Bound**\n\nThank you for your clarification! According to the original definition in the context of online learning, the definition of instantaneous regret should be $\\max_{A \\in \\mathcal{A}} \\langle \\theta_{A}^*,s_{n, b} \\rangle-\\langle \\theta_{A_{I_{n, b}}}^*,s_{n, b}\\rangle$. However, in the specific setting of contextual batched bandit (CBB) that is the focus of this paper, as derived in Appendix line 282 (second inequality), if we denote the upper bound of $|\\langle\\theta_A^n,s_{n, b}\\rangle-\\langle \\theta_A^*,s_{n, b}\\rangle|$ as $U$, then $2U$ serves as an upper bound for instantaneous regret. Thus, in the context of CBB explored in this paper, we are interested in an upper bound for $|\\langle \\theta_A^n,s_{n, b}\\rangle-\\langle\\theta_A^*,s_{n, b}\\rangle|$ and define it as the instantaneous regret bound (as presented in Theorem 2). We intend to incorporate the relationship between our defined instantaneous regret bound and the original instantaneous regret into the final version."}]

Author rebuttal:
Thank you for your feedback and valuable suggestions. We have carefully considered and incorporated all the comments and recommendations provided. Additionally, we have uploaded a new PDF file containing supplementary experimental results. We kindly request the reviewers to bring to our attention any remaining concerns, considering the limited time available. We are fully committed to making every effort to address these concerns to the best of our ability.

Meta-review: This paper studies the contextual batched bandits (CBB) setting, where a batch of actions is played together (i.e., the decision has to be made at the beginning at each batch) and the rewards are only observed at the end of this batch. 

The main contributions of this paper are: The authors use imputation to improve the learning of the reward parameters, even for nonexecuted steps. This results in better variance and empirical benefits over many existing algorithms. To further reduce computational complexity, the authors propose the usage of sketching to compress the matrix used in linear regression. Empirically, they show better performance in both synthetic and real-world experiments.

There was a strong consensus among the reviewers that this is a good paper and should be accepted. I also fully agree with this opinion, hence I recommend accepting the paper.
Decision: Accept (poster)