Follow-ups Also Matter: Improving Contextual Bandits via Post-serving Contexts

Summary

The paper studies a variant of linear contextual bandits where a post-serving context is provided to the learner *after* the learner selects an arm. The reward is linear in the context and the post-serving context (but thus may not be linear in the original context on its own). The post-serving context is specified by noisy perturbation of a fixed (but unknown) function of the pre-specified context. The paper abstracts away the process of learning the function: the function is assumed to be learnable with sufficiently many pairs of context and noisy post-serving context pairs, and the “complexity” of the function is parameterized by the error of this learning process. The paper designs an algorithm based on LinUCB that creates a confidence set for the post-serving context in addition to the typical confidence set for the reward function parameters. The regret bound has a $O(T^{1-\alpha})$ term that depends on the complexity $\alpha$ of the function and a $O(\sqrt{T})$ term that depends on the dimension. The paper builds on the classical analysis of LinUCB, but requires a novel elliptical potential lemma. The paper further complements the theoretical analysis with simulations on synthetic data and real-world data (MovieLens dataset).

Strengths

The paper provides an intriguing model for additional information available to the learner beyond the reward. The idea of a post-serving context is natural and well-motivated. The approach of abstracting away the complexity of learning the function mapping contexts to means of post-serving contexts is also clean and elegant. The LinUCB-based algorithm in the paper is simple and elegant. The paper also provides a detailed discussion of shortcomings of relying on a point estimate of the post-serving contexts (in Section 2.2) and the need to appropriately address uncertainty in phi via a confidence set when computing an upper confidence-bound. The analysis of the algorithm is also technically interesting, with an introduction of the novel elliptical potential lemma. The paper clearly describes how the novel elliptical potential lemma accommodates slower learning rates and allows for noisy contexts, and furthermore highlights how the lemma is tight in several regimes. The paper is very well-written and explains the key ideas clearly.

Weaknesses

While the paper focuses solely on upper bounds, it could be interesting to investigate lower bounds. Is the dependence on alpha in the regret bound tight? (See question below.) That being said, this is a fairly minor weakness, since the upper bound analysis is already involved and interesting. Another minor weakness is that in Observation 1, it seems that the result is restricted to linear bandit algorithms (which should probably be clarified in the statement too). This seems to be a bit of an unfair comparison because the model is misspecified, and the linear bandit algorithm was not designed to handle misspecified rewards.

Questions

Questions: - Is the dependence on alpha in the regret bound tight? Typos: - “Generlaize” -> “generalize” p.5 - “Sketche” -> “sketch” p.6 - “Sthe” -> “the” p.6 - “Followings” -> “following” p.7

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Yes, the authors adequately addressed limitations.

Summary

This paper looks into contextual bandits in the scenario where only partial context is provided to the learner for making decisions. Specifically, this paper comes up with an environment setting where the full context consists of pre and post components which are revealed to the learner before and after she finalizes the action to take. Given the true reward is tied to the full context, the algorithm should include a post-context inferring step to get low regret. For the linear case, this paper proposes a low regret algorithm poLinUCB for this pre-post contextual bandit setting. The performance of poLinUCB is proved with theorems and evaluated by simulations, where a smaller regret rate is shown in contrast to other method/baselines.

Strengths

1. Both the theorem and simulation show in agreement that poLinUCB outperforms counter-method (Wang et al.) and baselines that are mentioned in the paper. 2. The theorem and its consequential sharper regret rate in $T$ compared to Wang et al. is built upon the generalized EPL, which may be considered as a new tool for other independent interests that take the uncertainties of context into account.

Weaknesses

**Soundness of the problem setup** Though the math content from problem formulation to algorithm to theorems are sound, it’s of independent evaluation that whether the setup at the first place is worth studying, put in other words, does the reward model (under line 107) cover/match any real-world problem. For me, some major drawbacks are: - it’s unlikely in reality that z_t will be fully revealed to learner - the learnability assumption fails when z_t is not fully determined by x_t, which is what usually happens in the hidden contextual setting where the hidden part is influenced by multiple factors, including but not limited to the revealed part x_t. - given this setting where z_t is fully predictable by x_t, then isn’t kernel/neural bandit already a good solution for this problem? **Method proposed is pretty similar to existing one** It’s in doubt that the outperformance is gained because poLinUCB has any essential algorithmic improvement than that of Wang at el. **or the formance gain is a only matter of new problem setting**. Wang at el. is not designed for the specific problem setting brought up by this work. - I can see that the original algorithm by Wang at el will suffer larger regret under your reward setup where true reward has component $<z_t, \beta_a^*>$. Since $z_t$’s from previous rounds are accessible to learner, the most accurate way for estimating \beta^* is certainly to utilize $z_t $rather than $\hat \phi (x_t)$ in loss. poLinUCB is more like an alternation of exsisting method as on adapting it to a new problem. - But what if true reward turns to have $<\phi^*(x_t), \beta_a^*>$, which is like a twin problem setup of this paper’s, then maybe Wang at el. will outperforms poLinUCB given $z_t$ is a noisy sample of $\phi^*(x_t)$ thus casts extra error into $\hat \beta_a$, while $\hat \phi (x)$ is ERM, which should have some noise reduction effect strengthened as $t$ goes up. Upper bound of regret in Wang at el. is inferior doesn’t necessarily mean the algorithm is less optimal, the performance may be underestimated by an upper bound that is not tight.

Questions

- What I’m not sure of is whether the problem setting is of good value to study, hopefully the author will respond with more evidence that may justify the problem setting. - Is the dependency on $d_u = d_x +d_z $able to further optimize, given $z_t$ is predictable by $x_t$, the effective dimension of this problem maybe smaller than $d_u$.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Identified Limitations are listed in Weakness and Questions.

Summary

The paper proposes a novel contextual bandit problem with post-serving contexts and introduces a new algorithm, poLinUCB, that achieves tight regret under standard assumptions. The authors demonstrate the effectiveness of their approach through both synthetic and real-world experiments, showing that poLinUCB consistently outperforms other strategies in leveraging post-serving information. Overall, the paper makes contributions to the field of online learning and contextual bandits.

Strengths

- Introduces a new contextual bandit problem with post-serving contexts and proposes a novel algorithm, poLinUCB, that achieves tight regret under standard assumptions. - Demonstrates the effectiveness of the proposed approach through both synthetic and real-world experiments. - Makes significant contributions to the field of online learning and contextual bandits, and has the potential to improve efficiency in a wide range of applications.

Weaknesses

- The paper does not seem to be fully finished. There is no conclusion section. - The paper could benefit from a more thorough discussion of the limitations and assumptions of the proposed approach, particularly in the context of real-world applications. - The experimental evaluation is limited. It could be expanded to include more datasets and scenarios. - The paper could provide more details on the implementation and computational complexity of the proposed algorithm.

Questions

- Could the authors provide more details on the choice of hyperparameters and the sensitivity of the proposed algorithm to their values? - Could the authors provide more insights into the practical implications and potential impact of the proposed approach? - How does the proposed algorithm handle noisy or incomplete post-serving context information, and what are the limitations of the approach in such scenarios?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

1 poor

Contribution

2 fair

Limitations

See comments above.

Summary

This paper introduces and analyzes the problem of contextual multi-armed bandits with post-serving contexts, where additional reward-relevant information is revealed after the the algorithm makes its choice. It divides the traditional context into a pre-serving context which is known the the algorithm at decision-time and a post-serving context which revealed later, but for which the algorithm can learn to produce an accurate estimate of its mean based on the pre-serving context. It then shows that the standard elliptical potential lemma needs updating in order to handle this case, and provides an alternative version. The paper then provides a novel algorithm which estimates the post-serving context in order to use in the new EPL, and proves its regret rate. Finally the paper performs experiments validating the performance of the poLinUCB algorithm.

Strengths

1) Makes a novel contribution to a more general version of the elliptical potential lemma which is well-motivated by their chosen application problem 2) Introduces a novel but useful-seeming problem setting where additional reward-relevant information is revealed after the algorithm's decision 3) Experiments clearly demonstrate the performance improvements benefits of their new algorithm, which nearly matches the performance of LinUCB which

Weaknesses

1) The paper doesn't have a conclusion section

Questions

1) Could you spell out an example of the setting in more detail? The paper does a good job of explaining situations where there is a post-serving context, but isn't that explicit about what the reward function is where the reward is revealed immediately after the decision but the post-serving context is clearly helpful for predicting performance 2) Could you say a bit more about why poLinUCB outperforms LinUCB even when $\phi$ is a linear function? If $z = Ax$, then $r = \theta x + \beta z = \theta x + \beta Ax = (\theta + \beta A)x$, and it is equivalent to a slightly different linear contextual bandits problem.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

The authors did not discuss the limitations of this work. While they would be similar to the limitations of normal bandit problems, adding the post-serving context could plausibly be more impactful than (for instance) a 20% performance improvement on a standard bandit problem. In particular, it seems plausible that the post-serving context could allow one to use more complex reward functions, which could be good or bad.

Summary

This work considered a novel contextual bandit problem with post-serving contexts and designed a new algorithm, poLinUCB. With a generalized version of Elliptical Potential Lemma (EPL), they provided tight regret under standard assumptions. Empirically, they showed on synthetic and real-world datasets, the proposed algorithms outperformed LinUCB with different types of contexts.

Strengths

- The paper is well-written and organised. Easy to read and well-defined notation. - The proposed new setting of contextual bandits is valid, interesting and well-motivated. The analysis of natural attempts fails provided good support evidence for the new proposed algorithm. - A generalised elliptical potential lemma (EPL) is proposed and well-explained. Can be an independent interest. - A regret bound is provided with parameters introduced in assumptions, with a clear description that how the parameter can be realised for the proposed algorithm. - The generalisations to action-dependent contexts, Linear Stochastic Bandits and Linear Bandits with Feature Mappings are interesting and useful extensions of the proposed setting. - Comparison to related algorithms in empirical is provided on both synthetic and real-world datasets.

Weaknesses

The regret analysis replies to Assumption 1 -- Generalised learnability of phi^ast, and the regret bound depends on the value of alpha. It is not clear when phi is not a linear function, how alpha will change. For example, when alpha approaches 0, the regret bound will approach linear regret.

Questions

- Can you provide a detailed discussion of how Assumption 1 will be realised when phi is not a linear function: how alpha will change, how regret bound would be? - Can you test in synthetic experiments for more types phi functions, to verify the discussion above? - would the form the phi function influence the parameter learning in Eq. (3)? - what if phi function depends on contexts? e.g. for different users, different types of contexts can be observed before and after serving, and those contexts can have different relationships.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

As mentioned by the authors in the appendix, this work heavily relies on Assumption 1 and the relationship between pre- and post-serving contexts. In practice, those assumptions may not hold.