Clusters Agnostic Network Lasso Bandits
multitask learning;contextual bandits;graph total variation;network lasso;clustering
Yes
No ethics review needed.
1. How do I interpret your results and their dependence on various parameters associated with the clusters? You mention different types of network structures but the results are very opaque ( so are the implications of the assumptions).
Key contributions include:

1. **Oracle Inequality:** The authors establish an oracle inequality leveraging a restricted eigenvalue condition, which helps ensure the accuracy of preference vector estimations.
2. **Regret Bound:** The proposed approach achieves sublinear regret, showing improved performance over independent task models, especially in large-scale graphs with high-dimensional contexts.
3. **Theoretical and Empirical Results:** The paper provides theoretical bounds on estimation error and regret, supported by experiments comparing this method to other graph-based and clustering bandit algorithms, demonstrating its effectiveness in high-dimensional settings.

The work is relevant for recommendation systems and similar applications where user preferences are unknown initially but can be inferred from limited interactions, exploiting known relationships among tasks to enhance learning efficiency.
The paper explores a multi-task contextual bandit setting where tasks are connected by a graph structure, encoding relationships between them. Here, user preference vectors are assumed to form clusters within the graph, but the algorithm doesn’t explicitly determine these clusters. Instead, it uses a **network lasso** approach with a dynamic regularization parameter, promoting smoothness in preferences within clusters while allowing for distinct clusters across the graph.
While the paper proposes a new problem, the results do not particularly exploit the network LASSO structure as much. They seem to be a straightforward extension of existing results from Oh et. al. (2021) to this setting.
Yes
No ethics review needed.
N/A
Network lasso seems to be an interesting technique applied to bandit problems.
This paper propose a bandit algorithm based on network lasso and provide improved regret bound based on the technique.
The current existing benchmarks are mostly using different bandit algorithms designs than the proposed greedy one. Thus, I don't think these are fair comparisons. Typically, greedy bandit algorithms have better performance than non-greedy ones. Can the authors compare their algorithm with other greedy algorithms, such as greedy OLS-Bandit (Bastani et al., 2021) and Lasso-Bandit (Bastani and Bayati, 2020)?
Yes
No ethics review needed.
1. The setting is agnostic to the graph. It then becomes opaque to me why we must utilize the graph structure, and how utilizing the graph structure could benefit.
3. The paper seems to restrict their study to the particular algorithm of network Lasso. This choice seems not justified, and I'm not convinced by its importance. 
3. The regret bound seems to have no dependency on dimension $d$. This seems strange, e.g. if we plug in $|\mathcal V| =1$ to Theorem 3.
This paper gives a rather complete analysis to the network Lasso policy.
This paper studies a multi-task linear contextual bandits setting. The tasks are embedded in a graph $G=(V,E)$. The paper shows the regret bound for the network Lasso policy, which updates the parameter estimation in a predefined way, and presents numerical experiment results to show the effectiveness of the network Lasso policy.
1. The paper mixes problem setting with algorithms which creates confusion: e.g., Eq. (2) about how $\hat \Theta$ is updated is not related to problem setting.
2. The paper sometimes refer to elements of $\mathcal V$ by task, sometimes by user (e.g. Line 129).
Yes
None
No ethics review needed.
1. What are the relaxed symmetry and balanced covariance assumptions in Assumption 2, and how do these assumptions impact the practical applicability of the method?

2. Assumption 3 states that tasks within the same cluster share the same reward parameter. Under this condition, the problem aligns with the well-explored domain of low-rank multi-task learning. As noted in the paper, the only justification for this approach is when the number of clusters exceeds the dimension d. However, this scenario is typically uncommon and may limit the broader applicability of the method. To this end, 

     a) Please clarify how the approach differs from or improves upon low-rank multi-task learning methods when the number of clusters exceeds d.

    b)  Also, discuss potential applications or scenarios where having more clusters than dimensions would be relevant.

3. In all the experiments conducted, the number of clusters is smaller than $d$, effectively reducing the problem to a low-rank multi-task learning problem, as studied in works such as Yang et al. and Lin et al. Therefore, the significance of the contribution needs to be reassessed, as it aligns with existing literature on low-rank multi-task learning. Some relevant representative works are:
Yang et al. Impact of representation learning in linear bandits, arXiv:2010.06531, 2020.
Lin et al., Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual, ICML, 2024.

    a) Can you include experimental comparisons with low-rank multi-task learning methods for the scenarios presented in Figure 1?

    b) Can you add experiments where the number of clusters exceeds d to demonstrate the unique benefits of their approach in those cases?

4. Can you provide an experimental comparison with the low-rank multi-task learning results presented in Yang et al. and Lin et al., given that all the plots in Figure 1 correspond to a low-rank case?

5. Can you compare the proposed approach with the low-rank multi-task learning results specifically for settings where the number of clusters exceeds the problem dimension? This comparison is crucial to demonstrate the effectiveness of the proposed method, as the paper emphasizes these scenarios.

6. Can you provide a table or figure comparing the regret bounds of the proposed approach in this paper with those of the relevant baseline methods? This comparison would help to clarify how the proposed method performs relative to established approaches in terms of regret guarantees. Further, can you discuss the implications of any differences in the regret bounds, particularly for cases where the number of clusters exceeds d?
The paper addresses federated multi-task learning, a growing area of interest due to its collaborative nature that enhances the effectiveness of the learning process. The paper presents both theoretical and experimental results.
This paper investigates multi-task contextual bandit settings, wherein the learner is provided with a graph that encodes the relationships among the bandit tasks. It is assumed that the preference vectors for these tasks are piecewise constant over the graph, thereby forming distinct clusters. To estimate the reward parameters, the paper formulates and solves a network lasso problem in each learning round.
The paper presents an approach to solving the multi-task learning problem by partitioning tasks into clusters, stipulating that tasks within each cluster share the same reward model, meaning they utilize the same feature vector. This approach is particularly relevant in scenarios where the number of clusters exceeds the problem dimension $d$; otherwise, the problem effectively reduces to a low-rank multi-task learning problem, which has been extensively studied in the literature. Therefore, to assess the significance of the results, it is crucial to compare both the theoretical and experimental findings with those from low-rank multi-task learning studies. However, the simulations conducted only address cases where the number of clusters is greater than the dimension, which raises questions about the completeness of the experimental analysis.
We solve and theoretically analyze a multi-task contextual bandit problem given a task relation graph using a network lasso objective..
@inproceedings{
anonymous2024clusters,
title={Clusters Agnostic Network Lasso Bandits},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=KWUFlIMn8A},
note={under review}
}
We consider a multi-task contextual bandit setting, where the learner is given a graph encoding relations between the bandit tasks. The tasks' preference vectors are assumed to be piecewise constant over the graph, forming clusters. At every round, we estimate the preference vectors by solving an online network lasso problem with a suitably chosen, time-dependent regularization parameter. We establish a novel oracle inequality relying on a convenient restricted eigenvalue assumption. Our theoretical findings highlight the importance of dense intra-cluster connections and sparse inter-cluster ones. That results in a sublinear regret bound significantly lower than its counterpart in the independent task learning setting. Finally, we support our theoretical findings by experimental evaluation against graph bandit multi-task learning and online clustering of bandits algorithms.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
multitask learning contextual bandits graph total variation network lasso clustering
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/62825be8966811512bbfc6a843a8b1c1a4049086.pdf
reinforcement learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/a5309f39f904bc239f3b6c37d13fc1082a846d1c.zip
Clusters Agnostic Network Lasso Bandits
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission