Symmetric Linear Bandits with Hidden Symmetry

Summary

The paper introduces and analyzes the problem of symmetric linear bandits with hidden symmetry. The authors study high-dimensional linear bandits where the reward function is invariant under certain unknown group actions on the set of arms. The key contributions are: - An impossibility result showing that no algorithm can benefit solely from knowing that the symmetry group is a subgroup of permutation matrices, necessitating further structural assumptions. - Establishment of a cardinality condition on the class of symmetric linear bandits with hidden symmetry, under which the learner can overcome the curse of dimensionality. - Introduction of a new algorithm called EMC (Explore Models then Commit) that achieves a regret bound of O(d_0^(1/3) * T^(2/3) * log(d)), where d is the ambient dimension and d_0 is the dimension of the true low-dimensional subspace (d_0 << d). - An improved regret bound of O(d_0 * sqrt(T) * log(d)) under an additional assumption of well-separated models. - Discussion of an open problem regarding adaptive algorithms that can achieve optimal regret in both well-separated and general cases. The paper provides theoretical analysis and proofs for the proposed algorithms and bounds. The authors position their work in the context of existing literature on sparse linear bandits and model selection, highlighting the novelty of their approach in leveraging symmetry for efficient exploration in high-dimensional linear bandits. This paper is primarily theoretical, focusing on the mathematical formulation of the problem, algorithm design, and regret analysis. It does not include experimental results.

Strengths

1. Originality: - Introduces a novel problem formulation of symmetric linear bandits with hidden symmetry, extending and generalizing the well-studied sparse linear bandit setting. - Creatively combines ideas from group theory, model selection, and bandit algorithms to address this new problem. - The proposed EMC algorithm represents an innovative approach to leveraging hidden symmetry in high-dimensional bandits. 2. Quality: - The technical analysis is rigorous and thorough, with well-structured proofs for all major claims. - Provides a comprehensive theoretical framework, including an impossibility result, regret bounds, and algorithm analysis. - Builds upon and extends existing results in a mathematically sound manner. 3. Clarity: - The problem motivation and significance are clearly articulated. - The paper is well-structured, with a logical flow from problem formulation to theoretical results. - Technical concepts are generally well-explained, with appropriate use of mathematical notation. - Some complex concepts, particularly around the equivalence between sparsity and interval partitions, could benefit from more intuitive explanations or concrete examples for broader accessibility. 4. Significance: - Addresses an important gap in the literature by considering hidden symmetry in high-dimensional linear bandits. - Provides new insights into the role of symmetry in sequential decision-making, with potential broad implications for reinforcement learning and online optimization. - Establishes connections between symmetry structures and sparsity, potentially opening new avenues for efficient exploration in high-dimensional spaces. - The proposed algorithms and bounds represent significant progress in overcoming the curse of dimensionality in certain bandit settings.

Weaknesses

1. Limited empirical validation: - The paper appears to be primarily theoretical, with no mention of experimental results or simulations to validate the proposed algorithms. - Including empirical studies, even on synthetic datasets, would strengthen the practical relevance of the theoretical results. - Comparison with existing methods in terms of computational efficiency and performance could provide valuable insights. 2. Complexity of concepts: - Some key concepts, such as the equivalence between sparsity and interval partitions, are not explained intuitively enough for a broader audience. - Additional examples or visual representations could make these complex ideas more accessible. 3. Practical applicability: - The paper lacks a detailed discussion on how the proposed algorithms could be implemented in real-world scenarios. 4. Computational complexity: - There's limited discussion on the computational complexity of the proposed algorithms, particularly for the EMC algorithm. - Understanding the trade-offs between theoretical performance and computational requirements is crucial for practical implementation. 5. Assumptions and limitations: - While the paper acknowledges some limitations, a more comprehensive discussion of the assumptions' implications and potential violations in real-world scenarios would be beneficial. 6. Comparison with related approaches: - While the paper discusses how it differs from some existing methods, a more comprehensive comparison with other approaches to high-dimensional bandits or symmetry exploitation could provide better context. These weaknesses are not meant to diminish the paper's overall contribution but rather to identify areas where the work could be further strengthened or extended in future research.

Questions

Empirical Validation: Could you provide any empirical results, even on synthetic data, to illustrate the performance of the EMC algorithm? How does it compare practically to existing methods for sparse linear bandits? Practical Implications of Assumptions: Could you elaborate on real-world scenarios where Assumption 5 (sub-exponential number of partitions) and Assumption 16 (well-separated partitioning) are likely to hold or be violated? Intuitive Explanations for Key Concepts: The connection between interval partitions and sparsity, as well as the concept of hidden symmetry, are intriguing but complex. Could you provide more intuitive explanations or concrete examples to illustrate these key ideas, particularly for readers less familiar with group theory or symmetry concepts in bandits?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

4

Limitations

The authors have adequately addressed the limitations of their work, particularly by acknowledging open problems and discussing constraints of their assumptions. While they could expand on practical implementation challenges and potential societal impacts, their upfront approach to discussing limitations is commendable. A brief section explicitly addressing broader implications would further strengthen the paper, but overall, the authors have done a good job in addressing limitations within the context of their theoretical work.

Summary

The authors study the problem of symmetric linear bandits with hidden symmetry (where the expected reward is a linear function of the selected arm, and is invariant under a hidden symmetry group). They show that, with no additional information, the minimax regret cannot be improved. When the partition corresponding to the hidden symmetry group is known to belong to a given set of a sub-exponential number of partitions, the authors provide an algorithm that that achieves a regret of $\tilde{O}(d_0^{1/3} T^{2/3})$. Under the assumption that the models are well separated, this regret guarantee is improved to $\tilde{O}(d_0 \sqrt{T})$.

Strengths

The authors generalize the study of sparse linear bandits to high-dimensional symmetric linear bandits, where the symmetry is unknown and must be learned. The authors show that 1) no algorithm can benefit solely from knowing that there exists some subgroup under which the expected reward is invariant, 2) that a regret of $\tilde{O}(d_0^{1/3} T^{2/3})$ can be achieved when the partition is known to belong to a set of sub-exponential size, and 3) that a regret of $\tilde{O}(d_0 \sqrt{T})$ can be achieved when the models are well separated. For the well separated case, they note that the initialization phase length $t_2$ depends on the separation $\epsilon_0$, and question how to adapt to this parameter that will be unknown in practice.

Weaknesses

- Adaptivity: the algorithm requires as input the set $\mathcal{Q}_{d,\le d_0}$ (currently not shown as in input). Additionally, the algorithm / regret do not appear to adapt to the complexity of the problem instance, but rather depend on the size of this input set. The manuscript should be revised to clarify (in the algorithm) that this is needed as input. - The algorithm does not appear to be implementable. The minimization step in equation 5 is over $\mathcal{M}$, which is of exponential size ($d^{d_0}$). In the high dimensional regime of interest, this is infeasible without additional structural assumptions. The authors touch on this at the very end of the paper (line 402: "for future work, we will explore convex relaxation techniques for efficient computation"), but do not provide any concrete suggestions for how this could be done. - Practical motivation: the authors do not provide any concrete examples of where this problem arises, and how the input set $\mathcal{Q}_{d,\le d_0}$ could be obtained in practice. The paper should be self contained and self-motivated (e.g. Line 20, referencing [24] alone is insufficient). The illustrative example of an ant robot does not seem very related to the problem at hand, as there are at most 4 symmetries. The authors briefly discuss possible hidden symmetries in Appendix D, but don't provide examples where we should expect to see these symmetries (anything besides sparsity, for which there already exist specialized methods). - Clarity: the paper is quite difficult to read, and should be revised for clarity. I've listed some typos below, but thorough proofreading is needed. Writing typos: - Line 9: hidden symmetry - Line 16: "Stochastic bandit is" incomplete sentence - Line 26: "fo" - Line 38: "most of studies" - Line 81: "the set of arm is exploratory". Also, exploratory is undefined (reused in line 98). - Line 100: data-poor regime is undefined - Line 112: "And able to obtain regret" - Line 114: "That are different to aggregation" - Line 120: "Making" shouldn't be capitalized - Line 124: missing "the" - Line 142: "*In* each round" - Line 148: in term*s* of regret - Line 179: grammar, missing "to" and "as"->"be" - Line 204: in term*s* of regret - Line 206: "the" missing before "regret" - Line 221: "are"->"is", unnecessary "the" - Line 222: partition*s* - Line 320: "designed"->"the design" - general comment: "the assumptions" -> "assumptions" Math typos / comments: - Line 144: Is $\eta_t$ supposed to be a 0 mean $\sigma$-sub-Gaussian random variable? - Line 144: Clearer to write $f(x_t) = \langle x_t, \theta_{\star}\rangle$ - Equations 1 and 2: $\phi$ and $\hat{\phi}$ perform the same operation on $\mathbb{R}^d$, so it is unclear why they are separately defined for operating on $x$ and on $\theta$. Also, $\hat{\phi}$ is confusing notation to use, as this is not an estimator of $\phi$. - Line 163: missing $\forall g \in \mathcal{G}$ - Line 188: should explicitly define dim before usage - Prop 3: some intuitive explanation / proof sketch would be helpful. - Line 234: "data"->"actions" - Algorithms 1 and 2 critically require as input $\mathcal{Q}_{d,\le d_0}$.

Questions

See weaknesses. At a high level: 1. Adaptivity: the algorithm requires as input the set $\mathcal{Q}_{d,\le d_0}$ , and it is not clear how to obtain this in practice. Additionally, it appears that the key regret improvement is the scaling with the log of the cardinality of this set, instead of with $d$. Is there a way to make these assumptions less restrictive, adapt to the ``true'' complexity of the partition, or to estimate this set in practice? 2. Implementability: the algorithm as written does not seem to be implementable. Can the authors either provide an implementation (comparing their results with existing algorithms for sparse linear bandits), or suggest how this could be done in practice? 3. Practical motivation: is there a motivating example (not sparsity) where the arms are high dimensional, the symmetry is unknown, and the partition is known to belong to a set of sub-exponential size?

Rating

3

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

The key limitations of this method, that have not been sufficiently discussed, are its required knowledge of $\mathcal{Q}_{d,\le d_0}$, and its computational intractability, both of which appear to be severe practical limitations.

Summary

The paper studies high-dimensional linear bandits that are invariant w.r.t. an *unknown* subgroup of coordinate permutations. The authors first show through a lower bound that further information about the structure of the hidden subgroup is required to achieve a dimension-independent regret bound. They then propose a subexponential cardinality constraint on the hidden subgroup, which is sufficient to avoid the dimension dependency. They specifically propose *Explore-Models-then-Commit*, which successfully avoids the worst-case dimension-dependency under certain conditions.

Strengths

- Well-written - Clear motivation and a novel problem-setting of importance - Solid motivation for subexponential cardinality assumption on the hidden subgroup, as well as interesting combinatorial concepts intertwined throughout the paper - First good regret bounds in the case of hidden symmetry

Weaknesses

- The only symmetry somewhat intuitive to me is the sparsity, equivalent to interval partitions. Despite the Introduction stating the importance of symmetry, it is unclear whether there is practically meaningful coordinate symmetry beyond sparsity. (Of course, theoretically, I appreciate the results here.) - No experimental results. Especially as the authors have stated that Algorithm 1 can be "parallelised using tools such as Ray", I was expecting at least some toy experiments (one showing the efficacy of learning the hidden symmetry and scaling of the algorithm as the number of models $M$ increase) - The algorithm is explore-then-commit style, which requires the horizon length $T$ in advance and inherits its suboptimality [1]. [1] https://papers.nips.cc/paper_files/paper/2016/hash/ef575e8837d065a1683c022d2077d342-Abstract.html

Questions

- The paper states that as sparsity is equivalent to interval partitions, the lower bound of Hao et al. (2020) also trivially applies. Then, is this lower bound tight for other combinatorial structures with similar subexponential cardinality constraints, e.g., non-crossing partition? - In sparse linear bandits, there is always an assumption about the context distribution or the arm set (e.g., compatibility condition, restricted eigenvalue, etc.). Can these assumptions be interpreted as part of the paper's proposed group-theoretic framework as well? - (minor) Would the principles here be extendable to information-directed sampling [3]? [2] https://proceedings.neurips.cc/paper/2020/hash/7a006957be65e608e863301eb98e1808-Abstract.html [3] https://openreview.net/forum?id=syIj5ggwCYJ

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes

Summary

The paper explores the impact of unknown symmetry on the regret for stochastic linear bandits. Under some assumptions on the set partition induced by the unknown subgroup G, the paper develops an "Explore-then-commit" algorithm that attains optimal scaling of the regret in terms of the dimension d_0 of the low-dimensional space induced by the group action.

Strengths

* The paper describes the assumptions clearly and develops a regret bound that matches the lower bound for sparse linear bandits. * The paper makes a good case motivating the generality of the symmetric bandits structure by showing how it can recover sparse bandits. * A discussion comparing the results to those in the model aggregation literature is given.

Weaknesses

- The writing could be made clearer in some sections. For eg, the implication $g \cdot \theta_* = \theta_*$ in line 164 seems valid only under some conditions on the set $\mathcal{X}$. Suppose $g$ only swaps the first and second components and all vectors in $\mathcal{X}$ have the same first and second components. It would be helpful if an example is used to describe the orbit and associated partition, the fixed-point subspace, etc. - The implications of the assumption on $\pi_{\mathcal{G}}$ in line 218 and Assumption 5 could be described more clearly. Again, a short example might help. - Experimental evaluation of their proposed approach is missing, Even a small simulation experiment could assure reader of the applicability of the algorithm.

Questions

Please see weaknesses above

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

NA

Summary

This paper studies stochastic linear bandits with hidden symmetry, where the reward function is invariant with respect to a subgroup $\mathcal{G}$ of coordinate permutations. The paper first presents an impossibility result, showing that solely knowing a low-dimensional symmetry structure exists does not help. However, when the collection of fixed-point subspaces of $\mathcal{G}$ is not too large, one can use model selection algorithms to first learn the symmetry structure. The paper provides regret bounds of the algorithms, including an improved bound under an additional assumption that the equivalence classes of coordinates are well-separated.

Strengths

- The low-dimensional symmetry structure in linear bandits studied in this paper seems novel and interesting. It also generalizes the sparsity assumption that has often been considered in the literature. - The impossibility result is not surprising but still good to have. - The mathematical formulation is clean, and the connection between fixed-point subspaces and set partitions allows for a relatively simple notion of cardinality assumption for the algorithms to work. - The improved regret bound in Section 5 leads to some interesting questions about additional structure that a learner could exploit. - The technical results are clear, and the paper is well-written and easy to follow.

Weaknesses

- The algorithms are not computationally-efficient. - The algorithms require a rather strong assumption on the size of the collection of fixed-point subspaces of $\mathcal{G}$. - While hidden symmetry is observed in many learning tasks (e.g., control, multi-agent reinforcement learning), the paper does not provide specific real-world applications of symmetry structures within the context of linear bandits. - The paper can be much stronger with an empirical validation on at least synthetic data. In particular, it would be interesting to see how the algorithms behave on sparse linear bandits, in comparison with specialized algorithms.

Questions

- In proposition 3, is the claim "let $\mathcal{G}$ be an unknown subgroup with $\dim(\mathrm{Fix}_{\mathcal{G}}) = 2$. Then, for any algorithm, there exists $\theta^* \in \mathrm{Fix}_{\mathcal{G}}$ such that..."? - What can be done if Assumption 5 does not hold? - Can you elaborate on the comparison with [1], especially given that the symmetry structure here is on the coordinates so there are more similarities to the "groups of similar arms" assumption in multi-armed bandits? Could you further compare the settings and the techniques? - In terms of presentation, I think a concrete running example in Section 2 can be very helpful. [1] F. Pesquerel, H. Saber, and O. A. Maillard. Stochastic bandits with groups of similar arms. In Advances in Neural Information Processing Systems, 2021.

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Assumptions are properly discussed.

Rebuttal Response

Thanks for the detailed response. 1. **Motivating example:** this seems interesting, and definitely should be included in the paper. I think that there some issues with this that still need to be fleshed out (e.g. in a workplace, one would expect to have the organization chart, i.e. the tree, revealed), but this appears to be a concrete setting going beyond sparsity. 2. **Adaptivity:** This remains my primary concern, which does not appear to have been addressed. The algorithm critically depends on knowledge of the set **$\mathcal{Q}_{d,\le d_0}$** , and cannot be run without this as input. The algorithm, as written, does not currently take this as input, and so doesn't work. Additionally, the proposed bandit algorithm cannot adapt to the actual difficulty of the problem: if the partition actually belongs to a much smaller class **$\mathcal{Q}_{d,\le \tilde{d}_0}$** where **$\tilde{d}_0 \ll d_0$**, the algorithm complexity still depends on **$\mathcal{Q}_{d,\le d_0}$**, the set it was provided as input. 3. **Computational Limitations:** the ability to evaluate models in parallel does not get at the core of the issue here, which is that for even reasonable $d$ and $d_0$ the number of models that need to be evaluated is an extremely large polynomial. Even considering the toy example provided by the authors in Figure 1, for a $d=20$ dimensional feature vector per individual, this yields $O(d^{d_0}) \approx 160000$ models to evaluate. Without an efficient implementation for this algorithm proposed in *any* setting, and no concrete plans for how this can be achieved, it is unclear how this algorithm can be used. 4. **Empirical validation:** I think that this addition will greatly strengthen the paper, as it shows that the algorithm can work in practice on small examples. However, it seems as though this example is quite artificial; as in the point above, considering the example the authors provided in Figure 1, even for this toy example, $d_0=4$, while the authors restricted to simulating $d_0=2$. The addition of the motivating example beyond sparsity and the addition of toy numerical results strengthens this paper, but due to the algorithmically required input of $\mathcal{Q}_{d,\le d_0}$, lack of adaptivity (beyond just evaluating this subset of models as opposed to all models), and the computational complexity scaling with $d^{d_0}$, I retain my score of reject.