Context-lumpable stochastic bandits

Summary

The paper considers contextual bandit problem with S contexts and K actions, under the assumption that the contexts can be lumped into $r \leq \min\{S,K\}$ groups such that the mean reward for the various actions is the same for any two contexts that are in the same group. The paper considers the task of learning $\varepsilon$-optimal policy and prove sample complexity upper bound and a matching lower bound. The authors also present regret upper bound that depends on $r^{1.5}$. Although the results are original, the importance of the setting is unclear to me give the rich literature on CMAB, and the tight regret bounds known under minimal assumption of function approximation. (See e.g.,[1] Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability, Simchi-Levi and Xu, MoR 2021). The assumption that the contexts can be lumped into $r \leq \min\{S,K\}$ groups essentiality means that in practice there are only $r$ different contexts (although the cluster of each context is unknown), and the sample complexity and regret bounds depends in $r$ and $S$ (instead of $\log(S)$ which is the SOTA under function approximation).

Strengths

1) Tight sample complexity bound for the problem. 2) Nice applications.

Weaknesses

1) Given previous literature, the significant of the results is unclear to me. 2) Insufficient previous literature review. Mentioned results in equations (3) and (4) are not SOTA. Need to add a general review of CMAB literature and specifically [1]. 3) The setting of almost-uniform distribution seems trivial.

Questions

1) Equation (3): the sample complexity mentioned there seems trivial – basically run MAB algorithm for each context separately. The comparison is unclear to me. 2) Please consider [1] (SOTA for CMAB) and compare your results to those in [1]. Explain the difference between the settings and results.

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

3 good

Contribution

2 fair

Limitations

N/A

Summary

This work proposes a PAC learning algorithm and a regret minimization algorithm in the case when the contexts can be lumped into smaller partitions of contexts. The PAC algorithm achieves minimax sample complexity, while the regret minimization algorithm achieves a regret upper bound that could be less than the number of context groups before being lumped.

Strengths

This work provides a principled algorithm for contextual bandits for the case when contexts can be lumped into a smaller group. This case happens in real applications and is important to research. Compared to the previous works, this work relaxes the requirement of the knowledge of grouping of the contexts. This makes the algorithm more utilizable in the real world.

Weaknesses

1. Could the authors give an example of known $r$? Assuming $r$ is known to the algorithm seems not realistic since $r$ is usually unknown in practice. Or is there a way to relax the assumption on the knowledge of $r$? 2. The practicality and efficiency of the algorithm are not validated through experiments. An experiment that shows whether the algorithm finds the correct lumped groups for near-optimal arms would be a significant result.

Questions

Q1. The algorithm seems to have a lot of computation. Could the authors elaborate on the computational efficiency of the proposed algorithm?

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

2 fair

Contribution

3 good

Limitations

Yes. This work is mostly theoretical and potential negative societal impact is not applicable.

Summary

This paper considers the problem of context-lumpable bandits, which consists of contextual bandits with $K$ actions and $S$ contexts that can be partitioned into $r \\le \\min\\{S, K\\}$ blocks. The authors consider the case when mean rewards of the actions are fixed over different contexts that belong to the same block in the partition. In the setting of PAC learning, the authors design an algorithm that uses only $\\tilde{O}(r(S+K)/\\varepsilon^2)$ samples to find an $\\varepsilon$-optimal policy. The authors additionally prove a nearly matching lower bound (up to logarithmic factors) on the sample complexity of such an algorithm, thus proving that it achieves near optimal. performance. The authors further focus on regret minimization for the problem of context-lumpable bandits and design a strategy with $\\tilde{O}(\\sqrt{r^3(S+K)T})$ regret after $T$ rounds. These results are shown to be more general than prior work, as they allow for arbitrary context distributions and generalize to contextual low-rank bandits.

Strengths

- The results provide a significant contribution and improve upon prior work. - There is a careful adoption of multiple techniques and interesting ideas. - A thorough overview on similar problems in the literature is provided to better contextualize the work, thus justifying the originality of the work. - The techniques employed in both the design of the algorithms and their analysis are nontrivial and can be of independent interest.

Weaknesses

No major weaknesses were identified. Relative to the setting of regret minimization, the proposed algorithm essentially estimates the mean loss for each context in order to somehow recover the block partition by identifying large enough gaps between such estimates. Then, one may wonder whether an gap-dependent regret bound could be achievable, but this point does not appear to be directly addressed in the paper.

Questions

See weaknesses. In particular, do the authors believe that it would require a significant amount of work in order to devise and analyze an algorithm with a satisfactory gap-dependent regret bound?

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

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors did address the limitations of their work, such as the open problem of improving the current results in the regret minimization setting.

Summary

This paper studies the context-lumpable stochastic bandits, which can be understood as stochastic contextual bandits with low rank structure. A specific case of this problem where the contexts are linear was studied in previous literature, but there wasn't much study on this general problem. For this problem, this paper provides novel pure exploration lower and upper bounds. These two bounds match each other so the results in this paper are minimax optimal. For the upper bound, this paper provides an algorithm for it based on phased elimination.

Strengths

1. The bounds in this paper are minimax optimal. 2. The problem proposed in this paper is a natural extension of linear bandits with low-rank structure.

Weaknesses

1. At Line 9, $\Omega$ is better than $\widetilde \Omega$ because the latter could be understood as $\Omega(\cdot) / \mathrm{polylog}(\cdot)$. 2. In Algorithm 1 Line 1, $\mathrm{lg}$ is oftenly understood as an operator $\log_{10}$, so I suggest use another symbol to avoid confusion. 2. This paper can only solve the contextual bandits for stochastic contexts, while generally the contexts are considered to be adversarial. 3. The algorithm in this paper is for pure exploration and does not lead to an optimal algorithm for regret minimization.

Questions

1. Does the setting in (https://arxiv.org/pdf/1712.04644.pdf) apply here? 2. In most phased elimination algorithm, the sets $\mathcal D_n$ need be computed from $\mathcal D_{n-1}$, could you explain why it is not the case in Algorithm 1?

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

4 excellent

Contribution

3 good

Limitations

N/A