Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
Theoretical results in terms of sketching performance are also provided such as going down from O(Bd^2) to O(cd^2) for sketch size c as well as the regret bounds of the sketched approach SPUIR. 
Experimental results are shown on a couple of datasets to showcase the improved performance over state-of-the-art batched bandit algorithms such as BEXP3, BLTS-B.
main_review: Pros:
The paper is well-written and considers an important problem of batched linear bandits in the literature. 

(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.
(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}). 
(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. 

Questions: 

(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? 
(2) This uses the classic ``sketch and solve'' paradigm. Can we utilize the ``iterate and sketch'' to further speed up the approach?[a]

[a] Oblivious Sketching-based Central Path Method for Linear Programming. ICML 2021
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. 
Still unsure about the imputation approach taken and if we can further improve the sketching approach considered in the paper.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper considers the behavior of a series of algorithms for learning in a batched bandit setting,
where parameters are arm/action specific, rather than shared across arms/actions. 

These algorithms are based on UCB like techniques with the addition of a regularization term that aims
to use information from imputed, unobserved rewards. Such techniques are present in the linear regression
and dimensionality reduction literature where one aims to use either prior information or 
data distribution information to aid prediction. However, to my knowledge, these formalisms are quite 
new to online settings like bandits, thus making the presented approach appealing. 
main_review: 
Positive points:
* the paper is well written and generally easy to follow;
* the results are clearly communicated; both means and standard deviations are provided (e.g in Tables);
* in my biased opinion, the problem proposed  and the chosen approach are both interesting;


Major issues:
* details regarding the imputation procedure itself were scarce and hard to parse;
* the effect of different imputation methods could be rather large, this goes unaddressed in the current paper;
* 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;
* 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;
* simple Thompson Sampling seems to be performing comparatively well;

Minor issues:
* the number of iterations used to compute the means and standard deviations should be made explicit (10? 100?);
* for the top performing algorithms, it would be interesting to see the standard deviation bands throughout the plots;
* 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 
* occasional spelling

Suggestions for improvement
* assess the impact of imputation when different imputation methods are considered, be explicit about how the imputation is achieved
* assess the performance of the algorithms in settings where the arm/action parameters are the same across arm/actions
* 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.
* address minor issues; 


[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_review: Recommendation: weak reject.
The paper addresses an interesting question, and is generally well written, with a promising algorithmic direction. However,
I believe the central imputation idea gets lost in the many variants considered. I believe having sketching variants
is 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: PROS:
The 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.

MAJOR COMMENTS ON CONS:
My 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.

•	Construction of the imputation regularized ridge regression: 
o	The 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).

o	The jump from equation (1) to equation (2) is not obvious and could do with some further explanation.

o	Related 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?

o	At 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$?

•	Comments on the high-level idea of reward imputation and the exploration-exploitation trade-off:
o	Something 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. 

o	A 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.

•	THIS ISSUE HAS BEEN RESOLVED IN THE NEW VERSION: Error in the theory at eq (19)
o	I 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 \[
\sum_{i=0}^N \eta^{N-i} = \eta^N(1-\eta^{N+1})/(1-\eta)
\]

Which is not correct. It should be, with some simplification added for clarity,

\[
\sum_{i=0}^N \eta^{N-i} = 1+\sum_{i=1}^N \eta^N = 1+(1-\eta^N)\(1-\eta).
\]

This 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.

If 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.


MINOR COMMENTS ON CONS:
•	The 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). 

•	The 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.

•	I 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?

•	The 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.  

•	The distribution of the rewards is not made clear in section 2, only the functional form of their expectation – is this deliberate?

•	The 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.

•	On page 4 you say “for $\forall A_j$” which reads as saying ‘for’ twice.

•	From Section 4 the amount of whitespace seems to have been reduced between paragraphs? This makes things quite dense and hard to read.

•	At the start of the proof of theorem 2: *triangle inequality

•	I don’t think you need the $s \neq 0$ condition in Thm 2 since $\Gamma$ is positive semi-definite not positive-definite?

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.

I 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.
review_title: null

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